01. はじめ
02. エントロピー正則化
03. Unbalanced Optimal Transport
Optimal Transportの拡張系であるUnbalanced Optimal Transportについて紹介します。
Unbalanced Optimal Transport (Unbalanced OT) Link to heading
まず，式を見ていきましょう。
$$ L_\mathbf{C}^\tau (\mathbf{a}, \mathbf{b}) = \min_{\mathbf{P}\in\mathbb{R}_+^{n\times m}} \langle \mathbf{C}, \mathbf{P} \rangle +\tau_1\mathbf{D}_\varphi(\mathbf{P}\mathbb{1}_m|\mathbf{a}) + \tau_2\mathbf{D}_\varphi(\mathbf{P}^\mathsf{T}\mathbb{1}_n|\mathbf{b}) $$第1項は通常のoptimal transportでの最小化目標です。そして、この第2, 3項が追加されたものとなります。
$$ \mathbf{D}_\varphi(\cdot|\cdot) $$はズレを表す関数で、 例えば、euclideanだったりKL距離だったりが考えられます。そして、 $ \tau_1, \tau_2 $ はそれらのズレに対するペナルティの大きさを表しています。つまり、$\tau_1 = \tau_2 \rightarrow +\infty$のときズレを許さない、つまり、“balanced"な (通常の) optimal transportとなります。また、$\mathbf{D}_\varphi = \mathbf{KL}$ で、$\tau_1 = \tau_2 \rightarrow 0$ のときHellinger距離と呼ばれる距離となります
$$ \mathrm{L}(\mathbf{a}, \mathbf{b}) = \sum_i(\sqrt{\mathbf{a}_i} - \sqrt{\mathbf{b}_i})^2 $$Unbalanced OTの計算にもSinkhorn’s iterationを使うことができます。更新は次の式を順番に行うことで行われます:
$$ \mathbf{u} \leftarrow \Bigl( \frac{\mathbf{a}}{\mathbf{Kv}}\Bigr)^{\tau_1/(\tau_1 + \varepsilon)} \quad \mathrm{and} \quad \mathbf{v} \leftarrow \Bigl(\frac{\mathbf{b}}{\mathbf{K}^\mathsf{T}\mathbf{v}}\Bigr)^{\tau_2/(\tau_2 + \varepsilon)} $$Unbalanced OTのイメージは次のようになります．
左図がClassical OT (通常のoptimal trasnport) 右図がUnbalanced OTを表しています。 Classical OTのとき．左側の山が２つに分散し，右側の山と合流して輸送が行われています。 それに対して，Unbalanced OTでは左側の山は左側に，右側の山は右側に移動しています。 つまり，Unnbalanced OTは，より柔軟な結果が得られるといえます。
実際の応用としては，input dataがノイジーな場合や完全に分かっていない場合に、classical OTよりunbalanced OTのほうが優れていることが多いようです。