More than 5 years have passed since last update.

Computational Optimal Transport 精読会記録 (#4: 2.5後半-2.6)

Posted at 2019-04-12

背景

Kantorovich problem: $L_C(\mathbf{a,b}) = \min_{\mathrm{P}\in U(\mathbf{a, b})} \langle C, P \rangle$
- coupling matrix: $U(a, b) = \{\mathrm{P}\in \mathbb{R}_+^{n\times m}\mid \mathrm{P} \mathbb{1}_m = \mathbf{a}, \mathbf{P}^T \mathbb{1}_n = \mathbf{b} \}$
Dual problem $L_C(\mathbf{a,b}) = \max_{(\mathbf{f, g})\in R(C)} \langle \mathbf{f, a}\rangle + \langle \mathbf{g, b}\rangle$
- ただし $R(C) = \{(\mathbf{f,g})\in\mathbb{R}^n\times \mathbb{R}^m \mid \mathbf{f \oplus g} \leq C\}$

$a$を原材料置き場（倉庫），$b$を工場と考え，$a$から$b$へ輸送する問題を考える
主問題を解ける場合，その最適化解 $P^\star$ のように材料を輸送すればよい
主問題を解くリソースが存在しないと仮定し，集配側(a側)と分配側(b側)で仕事をアウトソーシングすると想定する
アウトソーシングする場合の価格を$\bf f$と$\bf g$で考える
考え方: 輸送する側は価格を最小化したい，アウトソーシングされる側は得られる報酬を最大化したい
- アウトソーシングを請け負う側が得られる報酬とは要するに $\langle \bf f, a\rangle + \langle \bf g, b\rangle$ である
- 補足: 両方同時に上げたい（$\bf f$で減った分は$\bf g$側に入れることで解消できるイメージ）
輸送する側は設定された価格$\bf f, g$が正しいか(reasonable)を確認しないといけない
- 主問題を解けば分かるが，主問題を解くリソースがない
- けれども$\bf f_i, g_j$が分かっていれば，これと$C_{i,j}$を比較すれば良い
  - $f_i + g_j \leq C_{i,j}$であれば，アウトソーシングをOKする
  - この条件が満たされていれば，双対問題は主問題で計算されるコストと比較して良いかどうか確認できる

$\bf C = \mathbb{1}_{n\times n} - \mathbb{I}_n$ であるような場合の1-Wasserstein distance
- 注: 対角線が0，他が1であるようなコスト行列
- $L_C(a,b) = \frac{1}{2} ||a - b||_1$ (注: ここでノルムに1/2が必要だけどarXiv版では抜けている)
証明の考え方
- 対角線のコストが0なので，最適解について対角線に可能な限り輸送するのが良い
- 輸送できる最大量はmarginalの制約から各$i$について$\min(a_i,b_i)$であり，仮に$a_i<b_i$であれば，$a$の方向(行方向)はすべて$0$になる，逆に$0$にならない側の輸送量は$|a_i - b_i|$となっている（対角線で送る分の残り）
- これを全部の輸送パターンでやっていくと，全体で送る量は$\sum_{i} |a_i - b_i|$の半分になって，これは主張になる

1-Dのヒストグラムを考えソートされているような問題を考え，それぞれ$1/n$ずつ重みが置かれている状況を想定する
このとき$\mathcal{W}_p(\alpha, \beta)^p = \frac{1}{n} \sum_{i} |x_i - y_i|^p$ となる
- 意味: ソートされた順でマッチングしていくような計算で良い

(本の図を参照)

次回からは§3をやっていく