A Blog Entry on Bayesian Computation by an Applied Mathematician
$$
$$
最適輸送に関する記事
はじめに
最適輸送問題は,変分法の黎明期に提案された,変分問題の1つである.
しかし,Lagrange と Hamilton による解析力学の変分原理や,Plateau 問題から続く極小曲面の理論と違い,最適輸送問題は変分法の黎明期に提案されたにも拘らず,その発展は大きく遅れた.
実際,(Monge, 1781) の問題が解かれたのは (Brenier, 1987),(Kantorovich, 1942) が拡張した形が厳密に解かれたのは独立な結果 (Evans and Gangbo, 1999), (Ambrosio, 2003) まで待つ必要がある.
そこで,本章では変分法の歴史(第 1 節)を見ることから始め,続いて (Kantorovich, 1942) の定式化と双対性理論を見る(第 2 節).
Kantorovich の問題は離散空間上に限っていたが,一般の Polish 空間上の理論を第 3 節でみる.最後にまとめる(第 4 節).
1 変分法の始まり
変分法 (calculus of variations) とは,関数空間上の関数(汎函数という)の最適化問題をいう.
1.1 Fermat の原理
歴史上,最初に解析的な解答が与えられた変分法の問題は Fermat の原理 (Fermat, 1657) である (Goldstine, 1980).
これは 光の経路は,進むのにかかる時間が停留するような曲線として実現される というものであり,この原理から光の直進性や反射・屈折の法則が導かれる.
実は約 200 年後の Hamilton は,自身の名前も冠されている Hamilton 力学の研究の前に光学の研究を行なっている.
そこで光の反射・屈折などの法則から Fermat の原理を逆に導き,2つの定式化が等価であることを導いた (中根美知代, 2000).その際に用いた表現が「特性関数」と呼んだ汎函数
Hamiltonian はこの定式化を光学から力学に拡張し,Hamilton 形式の力学となった.現代では Hamiltonian と呼べる量は (Hamilton, 1834) で最初に出現し,「主関数」と呼ばれている (中根美知代, 2000).主関数
1.2 最急降下問題
続いて (Bernoulli, 1696) にて John Bernoulli が 最急降下曲線 (Brachistochrone problem) 2 を自身の著書で取り上げた.
「誰も答えられなかった場合は自分の回答を発表する」というスタイルが挑戦的で,Leibniz, Newton など多くの数学者がこれに取り組んだ.John 自身は「最速の粒子の軌道は光と同じ原理で進むはずだ」との仮定から,Fermat の原理の繰り返しと見ることで幾何学的にこの問題を解いた (Levi, 2014).
同時に関連する複数の「変分問題」を発表した.これを (Euler, 1744) が組織的に取り上げるとともに,変分法 の名前をつけた.
1.3 Euler の直接法
(Euler, 1744) は曲線全体の集合
しかし (Euler, 1744) は専ら幾何学的な手法を用いており,「幾何学的でない方法の開発が望まれる」という但し書きが p.52 に付けられているという.
これに対して当時 19 才であった Lagrange が Euler に自身のアイデアを手紙に綴り,すぐさま非凡なアイデアを感得した Euler は Lagrange を呼び出した.
Lagrange の方法は,変分作用素
Euler ものちに Lagrange の方法が優れていることを認め,自身のスタイルを完全に Lagrange の方法に移した.
一方で近年,Euler の方法は具体的な構成を与えることと,数値解法との相性が良いことから,直接法 (direct method) として復活を見ている (Hanc, 2017).
1.4 Plateau 問題
Lagrange は 1760 年に,与えられた境界条件を満たす曲面の中で面積が最小になるものを決定するという,現代でいう プラトー問題 を定式化した.
これは現在でも変分法の中心問題の一つである.特に,一般の
1.5 最適輸送問題
最適輸送の問題はフランス革命の最中に (Monge, 1781) によって考えられた.
論文のタイトルにある déblai とは掘削現場の残土のことであり,remblai は建築時の盛り土を指す.
掘削現場と建築現場が分離している際に,どの地点からどの地点に土をどれほど運べば,最もコストが低く済むかを考えることが Monge の問題である.
現代的には
しかし (Monge, 1781) では決定論的な解,すなわち「1箇所の掘削現場の土は全て同一の現場に輸送し,複数箇所に分割して輸送することはない」という状況に限って考察していた.
1.6 最適輸送問題の特殊性
しかし,曲線や力学の変分問題や Plateau 問題とは異なり,(Kantorovich, 1942) が独立に定式化するまで,ほとんど目ぼしい発展はなかったのである!
これは他の問題と比べて確率論が重要な位置をしめるため,特に定式化が難しかったためだろうと考えられる (Ambrosio and Quarteroni, 2024).実際,公理的な確率論の展開は (Kolmogorov, 1933) まで待つ必要があった.
実際,Monge の問題が厳密に解かれたのは独立な結果 (Evans and Gangbo, 1999), (Ambrosio, 2003) まで待つ必要がある.
なお,のちに (Kantorovich, 1948) にて Monge の問題と関連づけているが,Kantorovich ははじめは Monge の議論がすでに存在することを知らなかったという (Vershik, 2013).
2 Kantorovich の定式化と最適化
2.1 はじめに
最適輸送は数学,特に偏微分方程式論,非線型解析の分野で重要な道具になりつつあるが,その遥かに前から最適化,経済学の分野で活躍を始めた.
特に,Leonid Kantorovich は線型計画法による解決から,ノーベル経済学賞を与えられている.
この章では Kantorovich のオリジナルの理論を離散の場合に見て,次章 3 で一般の確率測度に対して一般化する.
2.2 Kantorovich の問題
この輸送計画のうち,コスト
実はこの問題は,凸制約
従って,simplex 法などの線型計画法により解くことができる.
2.3 機械学習への応用
特に
このような構成は
すなわち最適輸送の考え方は,コスト
特に距離
2.4 双対問題
3 一般の最適輸送問題
3.1 はじめに
前節では離散空間の場合を扱った.
一般的には最適輸送問題の解は カップリング によって与えられる.
カップリングとは確率論的な概念であり,「輸送計画」を数学的に表現する格好の概念である.
逆に言えば解の表現に確率論的な発想が必要であった点が,力学や Plateau 問題における曲線や曲面が解となる変分問題とは違い,変分問題の中でも異色なものであると言える.
そこでまずカップリングの概念を定義し,一般の空間上での最適輸送問題を定式化する.
3.2 カップリング
可測空間
カップリングの全体を
この名前の由来は,次の分解を与える 確率核
3.3 最適輸送問題
最適輸送問題は2地点間の輸送コストを表す関数
輸送計画はカップリング
3.4 Monge の輸送計画
一方で Monge の最適輸送問題 は,この解を Monge カップリングの中で探す(第 1.5 節).6
この制約は極めて強く,一般に解が存在するとは限らない.実際 Monge の問題では,一箇所の資源を分割しそれぞれを別の目的地に運ぶことが許されないから,Delta 測度は Delta 測度以外に輸送することが出来ないことになる.7
Kantorovich の最適輸送問題は,極めて一般的な設定で最適カップリング
さらに,
3.5 最適輸送計画
3.6 双対問題
4 最適輸送と数学
4.1 はじめに
連続体力学における連続方程式,多孔質媒体方程式をはじめとして,種々の方程式は密度
だが,密度とは本質的に確率測度として理解できる.物理的には点群であるような対象は,むしろ確率測度と見た方が直接的である.
1つの方程式を関数方程式と測度方程式の両面で解釈することができるとき,前者を Euler 流,後者を Lagrange 流の解釈ともいう (Villani, 2009, p. 14).
最適輸送理論の大きな貢献の1つに,従来 Euler 流に解釈されていたものを,Lagrange 流に解釈し直す方法を与えることが挙げられる (Ambrosio and Quarteroni, 2024).
4.2 連続方程式
これは
4.3 Schrödinger 橋問題
Schrödinger 橋問題 (Schrödinger, 1931), (Schrödinger, 1932) は,確率過程の分布の空間
5 文献紹介
Springer Math Podcast では 2023 年に最適輸送に関連する Podcast を3つ発表しており,(Ambrosio and Quarteroni, 2024), (Figalli and Ambrosio, 2024), (Gigli and De Lellis, 2024) はその記事化である.最適輸送について深入りする前に,数学的な背景を知ったり,モチベーションを上げるために格好である.
References
Footnotes
ホロノミック拘束系などでは.↩︎
3blue1brown の YouTube 動画 も参照.↩︎
輸送多面体 (transportation polytope) という.コスト行列
との衝突を防ぐため,ここでは と表した.↩︎(Villani, 2009, p. 6), (Def. 1.4.1 Figalli and Glaudo, 2023) も参照.↩︎
(Figalli, 2023, p. 3), (Figalli and Glaudo, 2023) に従った.↩︎
しかし,任意の連続分布の間には輸送写像が存在する. (Figalli and Glaudo, 2023, p. 9).↩︎
(Kulik, 2018, p. 122), (Villani, 2009, p. 10) も参照.↩︎
(Kulik, 2018, p. 124) 命題4.3.3,(Villani, 2009, p. 10) も参照.↩︎
(Ambrosio et al., 2008, p. 183) 定理8.3.1 は (Villani, 2009, p. 14) にも取り上げられている.↩︎
(Villani, 2009, p. 19) Bibliographical notes も参照.↩︎