Sinkhorn Distances: Lightspeed Computation of Optimal Transportation Distances
元々は非公開領域に載っけていたが, 研究のアイデアだけ分離すればよく, 理解自体はむしろ公開領域に置いた方が議論しやすくて良いので移動する (2026/7/5) . 書誌情報
Cuturi, Marco. "Sinkhorn distances: Lightspeed computation of optimal transport." Advances in neural information processing systems 26 (2013).
Proceedings: NIPS'13: Proceedings of the 27th International Conference on Neural Information Processing Systems - Volume 2 Pages 2292 - 2300, 2013年の 26巻
一言で表すと
最適輸送問題を緩和し, 現実的な時間で解ける近似的な手法を提案
節ごとにまとめる
2. Reminders on Optimal Rransportation
最適輸送の紹介
4. Computing Sinkhorn Distances with the Sinkhorn-Knopp Algorithm
$ d^\lambda_ M(r, c) \stackrel{\mathrm{def}}{=} 〈P^\lambda, M 〉, \text{where } P^\lambda = \underset{P \in U(r,c)}{\text{argmin}}〈P,M〉− \frac{1}{λ} h(P ).
Shinkhorn距離をエントロピーの制約を含めて, ラグランジュ乗数で示したのが(2)式
各$ \alphaに対応する$ \lambda \in \lbrack 0, \infty \rbrackがある時, $ d_{M,α}(r,c) = d^\lambda_M(r,c)が成り立つ
dual-Sinkhorn divergence
dualは双対のこと
$ \lambda
?ラグランジュの未定乗数法, Lagrange multiplier スライドを参照
4.1 Computing $ d^{\lambda}_M
4.2 Computing $ d_{M,α} through $ d^{\lambda}_M
ざっくりまとめる
最適輸送による分布間の距離は, 他の距離や情報量に比べて, 多次元のパラメータでも上手く考慮できる点で優れているが, 計算時間が非常にかかる点が問題. そこで, 最大エントロピーによる正則化と, Shinkhorn-Knoppy行列スケーリングアルゴリズムによって近似的に解く手法を提案する.
最適輸送の問題を定式化する前に, 前提として輸送表と同時確率分布 (結合確率) を説明する. あるヒストグラムr, cは単体 (全要素が0以上, 和が1) とする. U(r,c)は輸送表で, rをcの分布にするために必要な行列を表す. ここでrはUの列和, cは行和を表す. U(r,c)は確率論的に解釈でき, {1, ..., d}のいずれかの値を取り, それぞれ確率分布r, cに対応する変数X, Yを考えると, 行列Uの各要素はr, cについての同時確率とみなせる. 例えば, 任意のrはcの和をとって影響を排した状態と考えられる. ここで, r, c, U(r, c)に属する確率分布Pのエントロピーと, Pに似た確率分布QとPのKL情報量を定式化する. これらは後ほど使用する.
先の結合確率分布を用いて, 最適輸送を定式化する. コスト行列Mを用いて表されるが, これはどのアルゴリズムを用いても最悪計算量がO(d^3logd)となる. ここでdはベクトルの次元数である. ただ, 適用範囲が狭くなる代わりに, 制約を受け入れ, 近似的な解を出すのであれば早くなることが知られている.
次に, 近似的な解を求めるための制約について考える. 一つはエントロピーによるもので, ここで先に定義した式を使う. エントロピーの凹な性質により, 凸な集合 U_alpha(r, c) (Uの部分集合) を考える. エントロピーの最大値は確率分布r, cが独立した際に得られる. そのような輸送表をrc^Tとすると, 実在する分布Pのエントロピーは最大値からalpha引いた以上になり, これはある程度の無秩序さを持っていることを保証する.
Shinkhron距離: $ d_{M,\alpha} (r, c) \stackrel{\mathrm{def}}{=} \underset{P \in U_\alpha(r,c)}{min}〈P, M 〉
Shinkhorn距離はPとMの内積 (ベクトルの内積のように行の要素同士をかける??) で求まる.
$ U(r,c)はヒストグラム$ r, cが行と列の要素になる, $ r,cの結合 (同時) 確率分布の集合
分割表, contingency tablesとも言う. クロステーブルがds的に馴染みがある?
同時確率が輸送計画に相当し, それがどのような値を取るかを考える, ということ
非負の$ d \times d行列$ U(r,c)は各行の和 (列和)が$ rに等しく, 各列の和 (行和) が$ cに等しい
$ r, cは要素が全て0以上かつ和が0になる単体
$ U_\alpha (r,c)はエントロピー制約を考慮している
$ r, cが独立な表$ rc^Tは, $ r,cのKL情報量が最大になる
エントロピーは関係性があると低くなる
逆に独立で, 片方の値がもう片方に影響を与えない場合, 最大になる
この$ rc^Tを用いてエントロピーの制約を定義すると, $ h(P)は$ h(r)+h(c) -\alpha以上だと言える
$ rc^Tにおける$ r,cのKL情報量が閾値$ \alpha以下になる行列$ Pを考えている
$ Mは輸送コストを表す行列. ヒストグラム$ rから$ cにするために必要な行列...?
これを何と表現すれば良い?
どうやって求めるのか
実際には閾値$ \alphaは使わず, 代わりにラグランジュ定数$ \lambdaを用いてShinkhorn距離を計算する
dual-Shinkhorn距離. ラグランジュ緩和による双対形式
定義: $ d^\lambda_ M(r, c) \stackrel{\mathrm{def}}{=} 〈P^\lambda, M 〉, where P^\lambda = \underset{P \in U(r,c)}{argmin}〈P,M〉− \frac{1}{λ} h(P ).
特に$ P^\lambda = \underset{P \in U(r,c)}{argmin}〈P,M〉− \frac{1}{λ} h(P)について
$ argminは最小となるパラメータを求める, ということ
$ <, >はフロベニウス内積
$ Pは周辺分布$ r, cの結合確率分布
$ Mは輸送コスト行列
$ − \frac{1}{λ} h(P)はエントロピーとラグランジュ定数による正則化項
$ P^\lambdaは周辺分布$ r,cの結合確率分布 $ P(輸送表)について, コスト行列との内積が最小になるような$ Pを求め, そこからラグランジュ定数を含めたエントロピーを差し引くことで, 制約を満たす最適輸送問題の近似解が得られる?
括弧を付け足す: $ P^\lambda = \underset{P \in U(r,c)}{argmin} \lbrack〈P,M〉− \frac{1}{λ} h(P) \rbrack
$ P^\lambdaは$ r,cを周辺分布に持つ全ての結合確率行列 $ P \in U(r,c)(輸送表) について, コストの期待値 (コスト行列との内積, 同じ位置にある要素同士を掛け合わせて、すべて足した総和) からエントロピー項を引いた値を最小化する具体的な行列$ Pである
周辺分布というのは, 結合 (同時) 確率行列 (分割表) について, 片方の要素の和を取った時, もう片方の要素の値が現れるが, そういう確率分布のことをいう
クロステーブルを考えると良い. 天気が雨かそうでないかと, 傘を持つか持たないかの行と列があるとする. この時, 雨が降る確率を求めたいなら, 雨が降る時に傘を持つか, 雨が降る時に傘を持たないという, 天気と傘の有無の同時確率について, 傘の有無で和を取ることで求められる. この, 片側の要素が周辺分布である
論文では$ r, cは正規化された確率分布 (要素が全て0以上, 和が1のベクトル)
$ rが供給, $ cが需要で, $ rから$ cへの輸送計画というのは, 以下に効率的に (輸送コストを抑えながら) $ rの物資を$ cのどの地点にどう配分して移動するか
要は割り当ての問題
ある同時確率, 結合確率分布行列 (カップリング) , 輸送計画 (輸送ポリトープ)$ Pは, 行の合計 (row sum)が$ r, 列の合計 (colmun sum)$ cとなる. つまり, 要素$ p_{ij}がどこにどれだけ配分するかに相当
$ P_{ij} \ge 0. 各要素は負にならない. 供給側が増えることはない
行列$ Pの$ i行目の和が$ r. 供給する量と一致する
行列$ Pの$ j列目の和が$ c. 需要の量と一致する
これは輸送コストの最小化ととエントロピーの最大化のトレードオフを考えることになる. どちらも$ Pを考えるため. これらのバランスが最適となる$ Pを求めるのが問題になっている
何が分かっていない?
輸送計画って何? rとcのマッピングって何?
上に書いた
コストって何?
地点$ iから$ jに運ぶ際に生じる何か. 物理的な距離や移動の難しさ
$ M_{ij}が個別のコスト. 別で用意する?
コストの期待値ってなに?
$ <P, M>について考える
$ P_{ij}は$ iから$ jに運ぶ確率
$ M_{ij}は$ iから$ jに運ぶコストで, 確率変数の値
これらをかけているので, 期待値の定義になる
輸送計画$ Pに従って$ iから$ jにコスト$ M_{ij}でランダムに物資を運んだ時, 一つあたり平均してどれくらいのコストがかかるか
コスト行列はなぜ与えられる? どうやって与えられる?
コストはデータ空間における距離. Ground Metric
事前に計算の対象となる分布について, 計算しておく
これを与えることで, どうすればコストを抑えて輸送できるかが解ける
今一度まとめ直す
論文の問題設定は, 多次元の確率分布同士の距離を測るのが機械学習などで重要で, これはKL情報量などのいろいろな手法がある中で最適輸送が多次元に対応できて良いが, 与えられた確率分布の行列の次元数dの立方体を超える計算量がかかる (最悪計算量がO(d^3logd)). これはどの最適輸送のアルゴリズムでも同じだが, 幾らかの制約を施すと, 適用範囲が狭くなる代わりに計算速度が向上される. 本研究ではエントロピーによる正則化を行い, Shinkhorn-knoppyスケーリングアルゴリズムを用いることで, 高速に輸送問題の近似解を導く.
ここで輸送問題は, 入力が 確率分布r, c, コスト行列M. 出力は確率分布rからcに移動するコストを最小化する, rとcの結合確率行列となる. これは分割表や輸送表とも呼ぶ
ここで, 輸送問題の前提を定義する.
ヒストグラムr, cは正規化されたベクトルである.
これらの同時 (結合) 確率分布の集合をU(r, c)とし, それに属する分布をPとする
P_ijはiからjにどのくらい移動するかを表し, 0以上となる.
行の和はr_i, 列の和はc_jである. 同時確率について, 片方の和がもう片方の値になるような確率分布を周辺分布という.
Pは分割表ともいう. 実際に, 天気が雨かそれ以外を行, 傘を持つかどうかを列として考えて作成した表を考える.
天気が雨の時, 天気が雨で傘を持つ場合と, 天気が雨で傘を持たない場合がある. これらは同時確率である
これらの和をとると天気が雨である確率が求まるが, 表の片一方を構成する傘の有無の影響がなくなっている
こうした分布が周辺分布である
このrについてエントロピーを定義し, Pのような行列QとPのKL情報量も定義する.
輸送問題は, 距離dがコスト行列Mと, 輸送表Pによって求まる.
提案ではKL情報量に閾値alphaを設け, エントロピーが最大となる輸送表 rc^Tを考える. このr,cは独立している
上で定義したKL情報量は独立している場合にのみ等式が成り立つ. つまり最大となる
エントロピー最大の状態を制約として, 実際に求まる分布Pのエントロピーは最大よりalpha下回ることが示される. これは十分にエントロピーが大きく, 輸送問題を線形計画法で解いた時よりも確率の値が行列の中で散らばり, より自然な輸送計画が導出できる. つまり実データを用いる際, ノイズや?コストの変更に頑健になる 輸送問題の目的関数にラグランジュの未定乗数法でエントロピー正則項を入れ込む(式略). これにより, 輸送表Pは輸送コストの期待値 <P, M> (Pijはiからjに移動する確率, Mijは移動にかかるコストで確率変数)を最小化しつつ, エントロピーを最大化する必要があり, これらのバランスを取ったPをP^lambdaとして導出する
資料の$ \epsilonは論文では$ \alpha
エントロピー正則化によって解の行列が密になる
エントロピー最大化の原理より, エントロピーを最大化するために行列が密になる.
エントロピーの考え方では, 知らない時は確率的に振る舞う. そこに偏りはない. よって, 確率の配置, 割り当てもまた前提条件 (供給量と需要量が保存される) とコストの大きさに従って均等になる
エントロピーは未知の情報に対して大きくなる. つまり不確実性が高いと大きくなる. 同じコストの輸送計画に対しては同じように確率を割り当てることで, 運び方はどれかに偏らず, 不確実性を最大化できる
何が分からない?
解のタイブレーク: 最終的に解が幾つか出てきた時にどれに決定するか定めておく
$ \epsilonが十分小さい時, すなわちほとんど元の最適輸送問題と同じになった時, エントロピーの正則項があるおかげで解が一意に定まるということか
全体で強凸
エントロピー制約の話であったが流した
エントロピーは凹性を持つ
最適解が一意に定まるらしい. 元の線形計画だと面に対して考えるが, この場合は一部の領域で考える
凸ということは, 最小値が一つに定まるということかな
コストに対して微分可能
コストの変更によって輸送計画がどう変化するか, の勾配情報を計算することで, 最適なコストを導出できる
線形計画法で解く際と異なり, どの移動計画でも輸送が生じるため, 微分ができるということかな
ラグランジュ関数
?微分結果から論文で言うところの$ P^\lambdaを導いたか ?$ P^\lambdaをどう代入すると双対のソフトな制約がまとまった式が出るか 目的関数の勾配
?勾配の式にf, gが出てこないことの何が嬉しいのか. 逆に何なら出てくるのか f, gの最適化
?片方を固定した時のf, gの最適化の式をどう出したか C-transformとの関連
変数変換とカーネルはそういうものとして処理する
応用: 配置問題や距離としての損失関数. 後で良い
何をすれば良い?
エントロピー含む情報理論の基礎を勉強
ラグランジュの未定乗数法を勉強
関連
論文