最適輸送のお話
メリー・クリスマス!!この記事は、「日曜数学Advent Calendar 2023」の24日目の記事です。
昨日23日目の記事は、Seiichi Manyamaさんの「n 次多項式の判別式の項数」でした。
はじめに
今年の日曜数学Advent Calendarは、最適輸送のお話をさせて頂きます。
最適輸送とは?
最適輸送とは、その名の通り、複数の地点にある資源を、需要のある地点にいかに効率よく運ぶかを考える、物資輸送問題として18世紀頃から研究されていたものだそうです。その後、経済資源の割当や、流体力学の理論に応用されるようになり、さらにはコンピュータサイエンスの世界でも登場するようになりました。
特に、機械学習の世界では、確率分布と確率分布を比較するためのツールとして利用されています。ここで、確率分布としてはヒストグラム、点群、連続分布(経験分布で近似)などが扱われます。
KLダイバージェンスとの比較
機械学習に詳しい方はご存知のとおり、確率分布と確率分布を比較するものとして有名なのはKL(カルバック=ライブラー)ダイバージェンスです。参考までに離散分布におけるKLダイバージェンスについて下記します。KLダイバージェンスは、最尤推定を行う場面などで現れます。
- 離散分布におけるKLダイバージェンス
ただし、とし、あるにおいてである場合は とする。
機械学習を行う場合、分布を近付けたい対象との比較方法として、このKLダイバージェンスにはない最適輸送の利点がいくつかあります。その中でも、「適切な仮定の下で距離の公理を満たす」というものがあります。ここで距離の公理を復習してみましょう。
距離の公理
を集合とする。関数が、任意のに対して以下をすべて満たすとき、は上の距離であるという
- (1).(非負性)
- (2).(同一性)
- (3).(対称性)
- (4).(三角不等式)
これら4つの条件を距離の公理という(ただし、(1)は(2),(3),(4)から導くことができる)。
KLダイバージェンスは、上記の式を見て頂ければ明らかですが、一般には(3)対称性も、(4)三角不等式も満たさないので、距離の公理を満たしません。
最適輸送とWasserstein距離
点群の最適輸送問題を線型計画問題として定式化すると、 と表される。ここではそれぞれ輸送元と輸送先の点に対する重みベクトル、はそれぞれの確率分布、は実行可能解の集合、Cはコスト行列、Pは輸送行列で、は行列の要素同士を掛けた和である。
なお、輸送元の各点から輸送先の重みで輸送すれば制約を満たすので、は実行可能解になります。
最適輸送コスト自体は、最適輸送距離とも呼ばれますが、距離の公理を満たしません。例えば、コスト行列Cが0行列の場合には任意の輸送行列Pが解となり、同一性を満たさないからです。
そこで、距離の公理を満たす最適輸送距離として、以下のようなWasserstein距離を紹介します。
上の距離関数と実数について、と定義する。このとき、について をとのp-Wasserstein距離といいます
この(p-)Wasserstein距離は、距離の公理を満たします。点群に関する証明は参考文献に載っているのでご参照ください。
おわりに
今回は最適輸送とWasserstein距離の話を書かせて頂きました。 Wasserstein距離は、何か色々使えそうな予感がするので、もう少し勉強したいなと思っています。
それでは、みなさま、良いクリスマスを!!
参考文献
[1] 佐藤竜馬 著, 「最適輸送の理論とアルゴリズム」, 講談社
chatGPTが登場して思うこと
chatGPT(https://chat.openai.com/chat)が世界を席巻しているので、思うところについて整理します。
私はDeep Learningへの期待感から、2017年頃から主に自然言語処理(以下、NLP)の可能性について探るため、色々とウォッチしてきました。具体的には、yans(NLP若手の会)、松尾研のDeep Learning基礎講座に参加したり、JDLAのGeneralist検定や、Engineering資格などを取得したりしていました。
一方で、ウォッチする中で、NLPについては言語の意味理解というシンギュラリティのようなものには程遠いという実感を得たため、最近はローキーでウォッチングに切り替えていました。
そう、chatGPTが登場するまでは。
世の中の動き
chatGPTの登場
chatGPTは、Open AI(MSから多額の出資を受けている)が、2022年11月30日に公開したGPT-3をベースにした会話応答サービスで、当初は無料で使えるものでした。2023年2月19日現在は$20/monthのプランが存在し、無料プランはアクセス数が少ない場合にしか繋がらなくなっています。
Big Techの動き
Open AIに出資しているMicrosoftは、自社製品に順次chatGPTの機能を載せていくと述べ、GoogleはchatGPTを驚異として"Code Red"を出し、対抗馬として対話AI "Bard"を一般公開しました。
日本国内の意見
日経ではchatGPTをどう見るか、東大・松尾先生、SONY・北野さんなどの意見をまとめています。 www.nikkei.com
自民党では、AI戦略のあり方や政策提言のまとめを行っているようです。衆議院議員の塩崎さんのnoteに説明があり、内閣府やデジタル庁、松尾先生の資料などをダウンロード出来るようになっています。 note.com
思うところ
chatGPTの精度について
現在のchatGPTで用いられているのは、GPT-3.5モデルで、大まかには以下のとおりの手順で学習されていると、松尾先生の資料のスライド18(20230217_AIの進化と日本の戦略_松尾研, https://note.com/api/v2/attachments/download/a29a2e6b5b35b75baf42a8025d68c175 )から見てとれます。
- STEP1: 教師あり学習; チャット時の応答で適切なものを人(アノテーター)が考えて正解データセットを準備
- STEP2: 報酬モデルの学習;アノテーターがモデルの回答に順位付けし、報酬モデルを学習させる
- STEP3: 強化学習;上記STEP1,2で強化学習
アノテーターが準備しているので、くだけた表現でも正しく理解でき、AI倫理的な側面もカバーされているとのことです。スライド29にあるように、専門知識を要する受け答えに対してのモデルが作れると便利ではありますね。
ただ、専門分野への適用に関して、課題ではないかと思うところがあります。それは、「正解データセットの準備」です。科学の分野では、一度正しいと確認されたものは、普遍的に正しいとされるものが多いです。一方で、人が介在する、法律などは普遍的に正しいという訳ではありません。たとえば、米国などのコモンローの国では、判決がそのまま法律の代わりのような扱いを受け、「先月までは正しかったが今月からは正しくない」という事例も存在し得ます。『日々正解が変わるような分野で、学習させるのに十分な数の正解データセットを準備するまでに時間が掛かるし、どの段階で適用可能と判断するのか』など、非常に難しそうな問題があるように思います。
Big Tech以外はどう動くのか
投資額を考えると、Microsoft, Google, Amazonなどはクラウドサービスを行っているため、膨大な計算機資源を時前で準備することも比較的容易だと思われます(計算機資源の在庫もあるかも知れないし、調達も比較的安価と想像)が、それでも大規模言語モデルを作るのに数百億円は掛かっているようです。 時期的なものを考えると、今から大規模言語モデルを作るには、それなりの時間が掛かるため、後追いの状態になってしまいます。それでも、世界の需要を考察して最適なインターフェースや、サービスとして何が成立するのかを考え出せれば可能性はあるのかも知れません。
自前で作らないとすれば、Big Techが提供するものを利用するので、利用料が発生してしまいます。これは、YouTubeやApple Storeを見ると分かりますが、Big Techに資本が集中してしまう状態を長引かせることになりますので、なんとか国をあげて自前のものを作る方針で行って欲しいですね。
参考
129について調べてみる
この記事は、「日曜数学Advent Calendar 2022」の9日目の記事です。
昨日8日目の記事は、みぽさんの「「p2-1は12の倍数(p>3)」を群論っぽく考えてみる~整数問題から代数系へ~」でした。
129について
今年のAdvent Calendarは12/9の記事ということで、なんと129について調べて観ようと思います。
因数分解
自然数を見ると、まずは因数分解したくなるのはサガ*1ですかね。
129は明らかに3で割れますので、 と因数分解出来ます。43といえば日本の県の数ですね。すべての県を魏呉蜀みたいに3つの地域に分けたら129つになるわけで、そういう規模感の数字になるわけですね。何となく、比較的身近な大きさの数字だなあという心象ですね。*2
2進法
さて、129自身について他の分け方も考えてみましょう。129って、 に1を足した数字なので、2進法だと10000001と8桁で左右対称になりますね。なんかきれい。そういえば、桁数が偶数で左右対称の数字は10進法だと11で割り切れるんですけど、こいつも11(2進法で3)で割り切れますね。
なお、11の倍数判定としては、偶数桁の合計値と奇数桁の合計値の差が11で割り切れると、11の倍数になるというのが基本にあるわけですが、桁数が偶数で左右対称だと、偶数桁の合計値と奇数桁の合計値の差が0になるので、11で割り切れる訳です。
ここで、「偶数桁の合計値と奇数桁の合計値の差が11で割り切れる」ということの基になっているのは、「11の倍数を引いても、11で割り切れるかどうかの判定は変わらない」ということで、99のA倍をA00(Aは百の位の数字。A=9なら900)から引くことを考えてやれば、となるので、「任意の桁の数字を2桁下に移動(足し算)してやっても、割り切れるかどうかの判定は変わらない」というところから来ています。
2進数だと、上記Aには1しか入らないので、シンプルに100-11=1になり、「任意の桁の数字を2桁下に移動(足し算)してやっても、割り切れるかどうかの判定は変わらない」ので、よってもって「桁数が偶数で左右対称の数字は11で割れる」ことになります。
2進法で10000001は11で割れる、つまり10進法で考えると129は3で割れることが分かるのです。やったね。 ちなみに、2進数を手で数える方法を小学生のときに知ったのですが、それで129を数えるとえらいことになるので、人前で数えるのはやめましょう。 二進指数え法 - Wikipedia
刑法129条
刑法129条は過失往来危険罪です。危険行為はやめましょう。
1.過失により、汽車、電車若しくは艦船の往来の危険を生じさせ、又は汽車若しくは電車を転覆させ、若しくは破壊し、若しくは艦船を転覆させ、沈没させ、若しくは破壊した者は、30万円以下の罰金に処する。 2.その業務に従事する者が前項の罪を犯したときは、3年以下の禁錮又は50万円以下の罰金に処する。
全然関係無さ過ぎてびっくりすると思うのですけれども、2022年の改正で、懲役と禁固が柔軟に織り交ぜられるように拘禁刑という刑罰に変更されて、2025年から施行される見込みらしいですね。へー。 刑法第129条 - Wikibooks
さいごに
今年のネタはゆるっとしてみましたので、普段は数学の記事を読まない方にも読んで貰えてたら幸いです。
では、おやすみなさいzzz
ゆる数学の気持ち in 第25回 日曜数学会
先週の土曜日、10月15日に開催された第25回 日曜数学会で発表した「ゆる数学の気持ち」について、発表資料を以下のとおりSlideShareに置きました。
数学はスマホゲーと違って、サービス終了しないので安心して取り組める趣味ですよね。
素因数分解ビンゴのLINE Bot 復活!!
素因数分解ビンゴとは?
素因数分解ビンゴは、3人以上(読み手が1人以上、プレイヤーが2人以上)が集まって行なうゲームです。基本の考え方はビンゴゲームと同じですが、最初にプレイヤーは以下の準備を行います。
事前準備(プレイヤーのみ)
- 5×5のマスに、2から97までの素数(ちょうど25個)を1つずつ書き込んだカードを用意します。
- 書き込んだカードを右隣りのプレイヤーに渡します。
その場でカードを作ることを想定してこのような手順を踏んでいますが、事前に複数枚用意して配って頂く場合には態々このような手順を踏む必要はありません。
プレイング
- 読み手は、プレイヤーには見えないように、任意の手段で2から97までの素数から重複を許して3つ取り出しかけ合わせ読み上げる
- 読み手は、上記1.を1分ごとに繰り返す
- プレイヤーは、読み手が読み上げた数の素因数を計算することが出来た場合には、通常のビンゴと同じように、その素因数が書かれたマスを潰すことが出来ます。
- プレイヤーは、以前に読み上げられた数に関しても、いつでも素因数を計算して構いませんし、計算出来たタイミングでマスを潰すことが出来ます。
実例
たとえば、以下のようなビンゴカードが手元にあるとしましょう。
読み手は以下のように数字を提示していきます。実際には1分ごとに読み上げますが、ここでは3つ一気に書いてしまいますので、皆さん素因数分解して、ビンゴカードの数字を潰していきましょう。
- 15423
- 64823
- 181189
なお、素因数分解ビンゴが生まれた経緯と、簡単な倍数判定法について、以下の書籍に書きましたのでご興味のある方はお手に取ってみて下さい。
素因数分解ビンゴの補助ツール(LINE Bot)
LINEを起動して、QRを利用したLINEの友達追加で、以下のQRコードを読み取ってください。
使い方は以下の通りです。
事前準備(プレイヤーのみ)の補助
- スタンプを送る: ビンゴカードを生成
読み手の補助
Enjoy the game !!
趣味で数学の勉強をすることについて
気が向いたので
普段、仕事に全く関係しない数学を趣味で勉強しているのですが、何を思って勉強しているのか、気が向いたので書いてみたいと思います。
一応前置きとして、これは単なる個人の感想であって、一般論でも無いし、人それぞの考え方や向き合い方があると思うので、そんな感じでゆるく見て下さい。
何を考えているか
5年ほど前に趣味数学を始めた頃は、雑食で大学数学に関連する話をつまみ食いしていました。そして、短期でやらないといけないという縛りは仕事の方でお腹いっぱいなんで、、超長期(30年くらい)で東大や京大の数学科(学部)で学ぶであろう数学を全部学ぼうという目標を立てていました。長期の目標なので、やれるときにやって、やれないときはやらない、こうすれば理解出来な過ぎても嫌になってやめたりはしないハズと。知らんけど。
それから数年後、やはり分野をまず絞ろうと思い、昔から好きな整数論をやろうと思い立ちました。
目下の目標は(それで終わるかも知れんけど)、「フェルマーの最終定理の証明を理解すること」で、もう少し具体的に言うと、斎藤先生の「フェルマー予想」の内容を理解することです。理解といっても、どこまで何を分かれば理解というのか、現段階では敢えて厳密には定義していません。その代わり、内容を理解するために必要だろうと思われる理論をこつこつ勉強することにしました。(それ自体が目的になることもOKとします。趣味なので。)
最近流行りのPoCじゃないですけれど、進みながらやり方や目的も修正しながら勉強していこうかなあと。
今年は類体論に入門することにしたので、牛歩ですけれども、徐々に理解できていければなあという感じですね。
とはいうものの
仕事では必要とされない数学をやるのは楽しいのですが、まあ折角なので実用的な数学も平行してやっておこうかと、食わず嫌いだった統計学の勉強も少し始めました。もともと、”神はサイコロを振らぬ”信者なので、大学時代から拒絶してたんですが、「数理モデルの対象を完全に観測出来ないことは往々にしてあるし、パラメータに依存させて幅を持たせたら良いんじゃね?」という考えだと解釈したら、まあ一応修士で数理モデル扱ってた身としては納得出来ました。
社会的に数学流行って来たよね?
Deep Learningのお陰で、数学が分かる人の需要は増えて来たと思います(Google Brainの方もDLはtoo much mathだと言ってました)。他にも量子コンピュータもある程度の数学力は要るし、暗号系は数論の知識が要りますから、ますます需要は増えるんだろうなあという心象です。
Google とか海外のテックジャイアントは数学系の人を積極採用している一方で、日本では法的に基礎研究が義務付けられているらしいNTTに数学の基礎研究所が出来ました。まあ、株式会社は売上・利益の短期目標の達成を義務付けられているので、他の民間企業ではなかなか大規模な採用は難しいのかも知れませんが、需要は増えていると思っています。
数学を勉強出来る場は増えていると思う
5年前には、大学の外で、大学の数学を手軽に勉強する方法が無かったように思いますが、東京では社会人向けの数学塾(塾なのかな?)もありますし、さらには様々な方の努力に寄って、勉強出来る場は増えているように感じます。
これから
ゆるくやっているお陰なのか、今のところ数学をやる気がゼロになることは無かったので、このまま一生やってくんだと思ってます。ちなみに、大学は工学系なんですが、工学は当時モチベーションがほぼ無い状態で無理して勉強していたので(成績は院試免除になる程度には良かったですが)、あれは良くなかったなあと思っています。モチベーションは大事。
勉強会をやっていて思うこと
毎週水曜日に開催している勉強会「ゆるにじたい」が始まってそろそろ2年が経ちます。
当初は「素数と2次体の整数論」(共立出版, 青木 昇 著)を進めるゼミで、1年掛けて読み終わったあとに、さらに「数論序説」(裳華房, 小野 孝 著)を進めています。
そんな中で、これら専門書には行間があることはもちろんですが、誤った記載も見受けられます。おそらく、著者にとっては本質的な部分ではない等もあって、適当に流してしまっているためかと思いますが、循環論法になっている箇所や、根本的に論理が間違っているところもあります。
ここでは間違いを批判するつもりは毛頭なく、そもそも少し間違っている方が、専門書を絶対的に信じるのではなくて自分の頭で考える習慣が着くので良いくらいに思っています。そもそも勉強出来る専門書を出して頂いた著者、出版社の方には感謝しか無いです。
では、何が言いたいかというと、勉強会で折角まとめた内容も、著作権の関係で、同じ本を勉強する方*1に還元出来ないのが勿体ないなあという事です。
無償で公開してしまうと、そもそもの書籍が読まれなくなって、著作権者に損害を与えることになりますので、業界にとっても良くありませんし、また許可なく公開すると、著作権侵害になります*2。
そこで、出版社側で、書籍に以下のような権利を付随して貰えないものだろうかと夢想してみました。 ①書籍の購入者は、書籍の勉強会の成果物(まとめノート、勉強会動画など)をある限定公開のwebサイトにuploadして良い権利を得られる。 ②書籍の購入者は、第三者がuploadした上記成果物を、閲覧できる権利を得られる。
こういう形であれば、書籍の売上は下がらないだろうし、成果物をまとめる側も勉強会のモチベーションが上がる、その分野に入門する人は先人の知恵が得られるし、良いまとめがあると評判になれば、むしろ教科書の売上も上がるのではないかと想像されます。
一般の出版社では敷居が高いかも知れませんが、技術書展などの商業誌以外のところから、こういう仕組みが広がっていくと、もしかしたらデファクト・スタンダードになって、気が付けば商業誌も同じ仕組みが取り入れられたりしないもんでしょうかね。