Sinkhorn_Distances_0705

Sinkhorn Distances 最適輸送における双対性の利用 2026/7/6 3F10260003 竹本 志恩 1

発表のゴール • 最適輸送問題は何で, 双対性を使うとどう解けるか • 特に近似的にどう解くか紹介し, 研究のタネに? 2

最適輸送とは何か • 荷物をどこに, どう運ぶと最小コスト? • • 荷物を必要とする量は既定 コストを最小化する最適化問題 3

最適輸送の具体例 • 以下の条件で輸送の最小コストを求めたい • 工場と店舗 (パン屋)が存在 • • 工場はn kgの小麦を保持 • パン屋はm kgの小麦が必要 なお: • 工場からパン屋への輸送コストは既知 • 小麦は消えないし, 増えない 4

最適輸送の具体例 コスト: 3 + 4 + 2 + 2 + 1 = 12 a1 3 a2 工場 2 a3 1 b1 1*3 2*2 2*1 1*2 1*1 1 C 1 2 3 1 3 2 2 2 1 1 2 3 2 1 1 b2 4 店舗 b3 2 輸送量*コスト 5

最適輸送の定式化 • 入力: 供給/需要の確率分布, コスト行列 • • m ベクトル a ∈ R , b ∈ R , 行列C ∈ R n×m 出力: aからbへの最小輸送コスト • • n aiからbjにPij輸送すると, コストは PijCij なお輸送は過不足なく実行 • • a1 + . . . + an = b1 + . . . + bn = 1 a, bは確率 6

最適輸送の定式化 入力: a ∈ R n, b ∈ R m, C ∈ R n×m, 決定変数: P 目的関数: minimize P∈R n×m n m i j ∑∑ 制約: subject to Pij ≥ 0 n PijCij 総輸送コスト ∀i , ∀j 輸送量は非負 ∑ Pij = ai ∀i 余りなし ∑ Pij = bj ∀j 不足なし i m j 7

問題の見方を変える • • ここまで, 輸送コスト最小化を見てきた • 工場aiから店舗bjに輸送計画Pij, コストCijで輸送 • これを主問題と呼ぶ 線形計画法では主問題の逆を見る双対問題が存在 • 今回なら, 輸送を代替する物流業者の売上最大化 • 工場から店舗に輸送せず, 業者が仲介 8

最適輸送の具体例: 主問題 a1 3 a2 工場 2 a3 1 直接, 輸送する C_11 C_12 C_22 C_23 C_33 b1 1 b2 4 店舗 b3 2 9

最適輸送の具体例: 双対問題 a1 業者 買取 輸送は間接的 b1 a2 b2 a3 b3 業者 売却 10

最適輸送の双対 • 物資一つの回収費用がfi, 売上がgj • • それぞれ主問題の制約に対応 Pに対応する制約: • 主問題のコスト以下なら工場は物資を輸送しない maximize f∈R n, g∈R m subject to n ∑ i=1 ai fi + m ∑ j=1 fi + gj ≤ Cij bjgj ∀i , ∀j 11

主問題と双対問題の関係性 • 双対定理など, 証明は省略 • • n m i j ∑∑ というかできない. 勉強不足 PijCij 今回は主問題が上から押さえつけ, 双対が下から迫る形 • イコールなら実行可能なP, f,gが存在 n ∑ i=1 最適値 ai fi + m ∑ j=1 bjgj 12

Sinkhorn Distances: 主問題の定式化 • 論文では近似的手法を提案 • h(P)がエントロピー. なお, ϵ > 0 • PijCijを抑えつつ, h(P)を増やす minimize P∈R n×m n m ∑∑ i=1 j=1 PijCij − ϵh(P) subject to Pij ≥ 0, ΣiPij = ai, ΣjPij = bj 13

Sinkhorn Distances: 主問題の定式化 • ちなみに, エントロピーの元の式を代入すると minimize P∈R n×m n m ∑∑ i=1 j=1 PijCij + ϵ h(P) = − d ∑ i,j=1 d ∑ i,j=1 Pij log Pij Pij log Pij 14

Sinkhorn Distances: 双対性の利用 • ラグランジュの未定乗数法より 双対問題のf, gを乗数として導入すると ラグランジュ関数は ℒ(P, f, g) = ∑ ij + PijCij + ∑ i fi ∑ ∑ j ij ϵpij log pij pij − ai + ∑ (∑ j i gj pij − bj ) 15

Sinkhorn Distances: 双対性の利用 • 主問題の決定変数はPij. Pijについて偏微分すると ∂ℒ = ϵ(log pij + 1) + Cij + fi + gj = 0 ∂pij • このまま指数を取ると ⋆ Pij = exp(( fi + gi − Cij)/ϵ) • これはラグランジュ関数が最小となるP 16

Sinkhorn Distances: 双対性の利用 • Pij⋆ = exp(( fi + gi − Cij)/ϵ)で双対問題を表現 maximize f∈R n, g∈R m n ∑ i=1 n −ϵ ai fi + m ∑∑ i=1 j=1 m ∑ j=1 bjgj exp(( fi + gi − Cij)/ϵ) 17

Sinkhorn Distances: 提案の工夫 1 • ϵは定数 を置き換えたもの. λ 戻して整理し, 指数を取ると ∂ℒ = ϵ(log pij + 1) + Cij + fi + gj = 0 ∂pij 1 1 Pij = exp − − λfi exp(−λCij)exp − − λgj ( 2 ) ( 2 ) 18

Sinkhorn Distances: 提案の工夫 • 先のPijについてそれぞれ文字で置くと 1 1 Pij = exp − − λfi exp(−λCij)exp − − λgj ( 2 ) ( 2 ) 1 1 ui = exp − − λfi , vj = exp − − λgj , Kij = exp(−λCij) ( 2 ) ( 2 ) Pij = uiKijvj • なお、Kはカーネル関数. 非線形な計算を単純化 19

Sinkhorn Distances: 提案の工夫 • 対角行列で置くとP = diag(u)Kdiag(v) • これでカーネル関数に対して 左右から対角行列をかければPが求まる • • 交互にPの行和aと列和bに合わせればOK 行列ベクトル積に帰着 20

参考文献 • Marco Cuturi. “Sinkhorn distances: Lightspeed computation of optimal transport.” NeurIPS 2013. • 佐藤 竜馬. “最適輸送の解き方.” https:// speakerdeck.com/joisino/zui-shi-shu-song-nojie-kifang 21