背景
- 前回: Computational Optimal Transport 精読会 記録 (#14: 4.3 その1)は7/4に開催，今回は7/16に開催
- 職場で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)}}$
- カーネル$K$がうまい形をしているとき，高速な計算ができる（特にGPU利用）
- 今回: 詳細を確認していく
Remark 4.18
- 行列積の計算は頑張って高速化する枠組みがたくさんある（おそらく）
- 例えばカーネルがインデクスの間についてのみ依存する場合（＝前回の謎の図がこれに相当）: $K_{i,j}=k_{i-j}$
- 格子状に区切るような問題
- このとき，$Kv$などの計算は，新しく作った$k_{i-j}$との畳込み計算になっている: $Kv = k \star v$
- 畳み込み計算は，例えばフーリエ変換すればよい: $\mathcal{F}(k\times v) = \mathcal{F}(k) \odot \mathcal{F}(v)$
- フーリエ変換を高速に計算したり，近似する手法はいろいろ研究されている
Remark 4.19
- 熱(heat)に関する方程式についての知見を使ってみる(Varadhan's formula, 1967)
-
熱の拡散方程式的な文脈
- ここで熱は平面を伝わっていくのではないので，曲がった空間（CS的には多様体）を考えられる
- コストはその曲がった空間上での距離としておく: $C_{ij} = d_\mathcal{M}(x_i, y_j)^p$
- 熱量をイメージ
- カーネル $K=\exp(-d_\mathrm{M} / \varepsilon)$ をベクトルに作用させる点を近似しよう
-
とくに$p=1, p=2$の場合に議論がされている(Varadhan's formula)
- $p=1$
- $-\frac{\sqrt{t}}{2} \log(\mathcal{P}_t (x, y)) = d_\mathcal{M}(x, y) + o(t), \mathcal{P}_t = (\mathrm{Id} - t\Delta_\mathcal{M})^{-1}$
- この$\Delta_\mathcal{M}$は多様体上で熱が拡散していく様を表すオペレータ（たぶん）
- ここで$ g - t\Delta_\mathcal{M}g = f$という高等な関係がある
- $p=2$
- $\sqrt{-4t\log(\mathcal{H}_t(x,y))} = d_\mathcal{M}(x,y) + o(t)$
- ここで$g_t = \int_\mathcal{M} \mathcal{H}_t(x,y)f(y)dy$ は $\frac{\partial g_t(x)}{\partial t} = (\Delta_\mathcal{M} g_t)(x)$という高等な関係がある（謎）
- $p=1$
-
まったくわからないが，式が言っていることはこういうこと
- 多様体$\mathcal{M}$上の$\Delta_\mathcal{M}$は直接扱えないので，離散化してラプラシアン$L$で扱う
- $p=1$の場合，$\varepsilon = \frac{\sqrt{t}}{2}$と設定し，$K$を掛けるところを$(\mathrm{Id}-tL)^{-1}$に置き換える．
- $p=2$の場合，$4t=\varepsilon$と設定し，$K$の掛け算のところを$(\mathrm{Id}-\frac{t}{R}L)^{-R}$で置き換える．
これらの方程式(linear system)は，単純に解くのは難しそうに見えるが，たとえばコレスキー分解でシステム行列を分解してうまくやると効率的に計算できる
Remark 4.20
- 最適化の世界では最適化法を加速させる手法があるが，これを利用できる
§4.4 Stability and Log-Domain Computations
- 以前Sinkhornアルゴリズムの紹介をしたときに，$\log$ ドメインじゃないとつらいという話があったが，それに関係する話
- ついでにdual側の話をする
Prop 4.4 エントロピー正則化付き輸送問題のデュアル側について
- 次のような目的関数(4.30)の制約なし最適化問題を考える
- これまでと同じデュアルのベクトル$f, g$だが面倒なので細字
$$L_C^\varepsilon(a,b) = \max_{f, g} \langle f, a\rangle + \langle g, b\rangle - \varepsilon \langle \exp(f/\varepsilon), K\exp(g/\varepsilon)\rangle$$
- このとき最適解$f^\star, g^\star$は，以前出てきた$u, v$と$u = \exp(f/\varepsilon), v=\exp(g/\varepsilon)$という関係を持っている(4.31)
Prop 4.4の証明
- 以前の証明から，ラグランジュの未定定数$f, g$を用いてPrimalの最適解は $P_{ij} = \exp(f_i/\varepsilon) \exp(-C_{ij}/\varepsilon) \exp(g_j/\varepsilon)$ という形になるという話があった（3回前ぐらい）
- ラグランジュ関数(日本語がダメ)にこの最適解を代入することで，式(4.32)を得る．これはラグランジュ関数についていた制約に関する項は消える（なぜなら最適解は条件を満たしているから）（下の式はexpを書くのが面倒でもうu, vになっている）
$$\langle u, (K \odot C) v\rangle - \varepsilon H(\mathrm{diag}(u) K \mathrm{diag}(v)$$
- エントロピー正則化の項は書き直すと $\varepsilon \langle P, \log P - 1\rangle$で，これを$P$に上の解の形を代入することで
$$-\langle u, (K\odot C) v\rangle + \langle f, a\rangle + \langle g, b\rangle - \varepsilon \langle u, Kv\rangle$$
- となる．第一項同士が打ち消し合うので，双対定理からProp 4.4を得る．
Next
- §4.4をやっていく(7/26)