---
title: Sinkhorn_Distances_0705
tags: 
author: [custard](https://www.docswell.com/user/custard-1855)
site: [Docswell](https://www.docswell.com/)
thumbnail: https://bcdn.docswell.com/page/YJ6WDZ86JV.jpg?width=480
description: 講義で使用したスライドです. 最適輸送の理解を深めようと試みました.
published: July 10, 26
canonical: https://www.docswell.com/s/custard-1855/ZJWEWN-2026-07-10-215113
---
# Page. 1

![Page Image](https://bcdn.docswell.com/page/YJ6WDZ86JV.jpg)

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


# Page. 2

![Page Image](https://bcdn.docswell.com/page/GJ5M3W95J4.jpg)

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


# Page. 3

![Page Image](https://bcdn.docswell.com/page/LE3W64Y5E5.jpg)

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


# Page. 4

![Page Image](https://bcdn.docswell.com/page/8EDKVQ5Y7G.jpg)

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


# Page. 5

![Page Image](https://bcdn.docswell.com/page/V7PKVLG2J8.jpg)

最適輸送の具体例
コスト: 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


# Page. 6

![Page Image](https://bcdn.docswell.com/page/2JVVZQ6XJQ.jpg)

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


# Page. 7

![Page Image](https://bcdn.docswell.com/page/5EGL4WNRJL.jpg)

最適輸送の定式化
入力: 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


# Page. 8

![Page Image](https://bcdn.docswell.com/page/4JQYG3QY7P.jpg)

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


# Page. 9

![Page Image](https://bcdn.docswell.com/page/K74W51NZE1.jpg)

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


# Page. 10

![Page Image](https://bcdn.docswell.com/page/LJ1YWG5DEG.jpg)

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


# Page. 11

![Page Image](https://bcdn.docswell.com/page/GJWG6K5872.jpg)

最適輸送の双対
•
物資一つの回収費用が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


# Page. 12

![Page Image](https://bcdn.docswell.com/page/4EZLYZN973.jpg)

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


# Page. 13

![Page Image](https://bcdn.docswell.com/page/Y76WDZ8D7V.jpg)

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


# Page. 14

![Page Image](https://bcdn.docswell.com/page/G75M3W9874.jpg)

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


# Page. 15

![Page Image](https://bcdn.docswell.com/page/9J29ZQ2VER.jpg)

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


# Page. 16

![Page Image](https://bcdn.docswell.com/page/DEY4RWYQJM.jpg)

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


# Page. 17

![Page Image](https://bcdn.docswell.com/page/VJNYD9P278.jpg)

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


# Page. 18

![Page Image](https://bcdn.docswell.com/page/YE9PG23DJ3.jpg)

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


# Page. 19

![Page Image](https://bcdn.docswell.com/page/GE8DV5M5ED.jpg)

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


# Page. 20

![Page Image](https://bcdn.docswell.com/page/LELM5Y337R.jpg)

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


# Page. 21

![Page Image](https://bcdn.docswell.com/page/4JMY3NDMJW.jpg)

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