背景
- 前回: Computational Optimal Transport 精読会 記録 (#13: 4.2 その3)は6/28に開催，今回は7/4に開催
- 職場でCOTを読んでおり，{自己満足,復習,将来のため}などの理由で記録をしている
前回の振り返りと今回の内容
- エントロピー正則化付きの輸送問題
- $L^\varepsilon_C({\bf a}, {\bf b}) = \min_{{\bf P}\in U({\bf a},{\bf b})} \langle {\bf P}, C\rangle - \varepsilon H({\bf P})$
- Sinkhornアルゴリズム最高 → ちゃんと収束するよ
- $\mathbf{u}^{(l+1)} = \frac{\mathbf{a}}{\mathbf{Kv}^{(l)}}$, $\mathbf{v}^{(l+1)} = \frac{\mathbf{b}}{\mathbf{K}^T\mathbf{u}^{(l + 1)}}$
- 今回: Sinkhornアルゴリズムの加速
§4.3 Speeding Up Sinkhorn's Iterations
-
毎回$K$やら$K^T$の掛け算が必要になるので一見思い気がするが，GPUを使えばとりあえず複数本ヒストグラムの計算は同時に可能
-
Sinkhornの更新式はほとんどそのまま行列形になる
- $U^{(l+1)} = \frac{A}{KV^{(l)}}$
- $V^{(l+1)} = \frac{B}{K^T U^{(l+1)}}$
-
$V$と$U$が収束したかどうかを確認するような式として(4.26)の下に載っている式は間違っているらしい（詳細不明）
- 誰か教えて
カーネルの分割 (separable kernel)
-
高速化するための一つの特殊ケースとして，カーネル$K$が分割できる場合
-
イメージが難しいが，コスト行列が小さいコスト行列の和で書き直せるケースを言っている
- $i=(i_k)_{k=1}^d, j=(j_k)_{k=1}^d \in [n_1]\times\dots\times[n_d]$
- $C_{ij} = \sum_{k=1}^d C^k_{i_k, j_k}$
- Sinkhornアルゴリズムでは$C$は$\exp(\cdot)$の中に入って使われるので，カーネルとしては$K=\prod_{k=1}^d K^k_{i_k, j_k}$となる
-
例: 格子上のヒストグラムで，各次元ごとの距離の和になるようなケース($q$-ノルム)
-
あまりよくわかってない
-
ノートには謎の図だけ残されていた
Next
- 次回は7/16に§4.3の続きを読む