背景
- 前回: Computational Optimal Transport 精読会 記録 (#1: 2.1-2.3)
- 職場でCOTを読んでおり，{自己満足,復習,将来のため}などの理由で記録をしている
今回の範囲の内容
- $p$-Wasserstein distanceが距離であること
§2.4
-
これまでの議論と同じく $n$ 次元ヒストグラムを考えていく（もしくは離散測度 $\alpha, \beta$ ）
-
同種のヒストグラムを考え，ビン (砂山の位置に対応) 間の移動コストなどに対応する ground metric $\mathbf{C}$を仮定
- (補足) 精読回中に議論が出たが，ここのmetricはdistanceと同意味で使われていると思われる
-
以降ではしばらく，ビンの個数が同じ2つのヒストグラムを想定
- (補足) これまでビンは重さ$0$ではないと想定していたが，長さを揃えると重さが$0$になる場合を扱う必要があるのだと思う(特にProp 2.2)
Prop 2.2
-
前提
- Monge Problemで利用するコスト行列 $\mathbf{C}$ として，ある距離 $\mathbf{D}$の$p$乗を利用すると
- $\mathbf{D}$ は距離である
- (i) $\mathbf{D}$ はsymmetric
- (ii) $\mathbf{D}(i,j) = 0$ は $i=j$ に限る
- (iii) $\mathbf{D}$ は三角不等式を満たす
- $p$-Wasserstein distanceを $\mathrm{W}_p(\mathbf{a,b}) = L_{\mathbf{D}^p} (\mathbf{a, b})^{1/p}$ で定める
-
主張
- $\mathrm{W}_p(\mathbf{a,b})$ はヒストグラム間の距離である (つまり (i)-(iii)を満たす)
Prop 2.2 証明の精読
-
対称性について: 以下の2つの事実から導かれる
- $L(\mathbf{a,b}) = \min_{P\in U(\mathbf{a,b})} \sum C_{i,j} P_{i, j}$
- $P\in U(\mathbf{a,b})$であるとき，$P^T\in U(\mathbf{a,b})$である
- $C_{i,j}$ が対称行列であるので，$C_{i,j}=C^T_{i,j}$
-
正性(?)について
- $\mathbf{a} \neq \mathbf{b}$ であるとき，$P$は対角成分以外に非ゼロ要素を持つ
- 非ゼロ要素の和は0より真に大きいため，$\mathrm{W}(\mathbf{a,b}) > 0$である
- $\mathbf{a} = \mathbf{b}$ であるとき，$P$を$\mathrm{diag}(\mathbf{a})$と置くと，$\mathrm{W}(\mathbf{a,b})=0$となり，距離であるかれこれが最適であるので，主張が正しい
- $\mathbf{a} \neq \mathbf{b}$ であるとき，$P$は対角成分以外に非ゼロ要素を持つ
-
三角不等式について
- ヒストグラムと離散測度についてのみ読む場合，2.4章の最大の山場（特に証明を細かく追う場合）
- 上に書いた通り，$n=m$と設定すると，真面目に$0$が入っているヒストグラムを扱う場合がある
- これを回避するため，$0$である要素を$1$にして回避する新しいヒストグラム$\tilde{\mathbf{b}}$を扱うというテクニックが出てきて，これが賢い
-
前提
- ヒストグラム3つ: $\mathbf{a,b,c}$
- Monge Problemの解: $\mathbf{P, Q}$ ($\mathbf{P}\in U(\mathbf{a,b})$, $\mathbf{Q}\in U(\mathbf{b,c})$)
- ゼロ要素を回避するため，coupling matrix $\mathbf{S} = \mathbf{P} \mathrm{diag}(1 / \tilde{\mathbf{b}}) \mathbf{Q} \in \mathrm{R}_+^{n\times n} \in U(\mathbf{a, b})$ を導入するのがポイント
- 本文中の解説通り，$\mathbf{S}\mathbb{1}_n = \mathbf{a}$となる
-
三角不等式の証明のポイント
- $\frac{\mathbf{P}_{ij} \mathbf{Q}_{jk}}{\tilde{\mathbf{b}_j}}$ という一見分からない項がMinkowski's inequalityを適用するときに出てくる
- (補足) 個人的に悩んだが，これはよく見るとタダの数なので，$((\cdot)^{1/p})^p$ という式変形をしてカッコの中に入れる．あとは適当に文字を置き換えて，通常のMinkowski's inequalityを利用し，不等式を展開する．
- $\frac{\mathbf{P}_{ij} \mathbf{Q}_{jk}}{\tilde{\mathbf{b}_j}}$ という一見分からない項がMinkowski's inequalityを適用するときに出てくる
Remark 2.15
- $0 < p \leq 1$の場合，Minkowski's inequalityが利用できないため，特殊ケースとして扱う必要がある
その1
- $\mathbf{D}^p$が 証明なしに 距離であるとする
- すると$\mathrm{W}_p(\mathbf{a,b})^p = L_{\mathbf{D}^p}(\mathbf{a,b})$ は Prop 2.2より距離になっている
その0: $\mathbf{D}^p$ が距離の(i)-(iii) を満たす証明
-
精読会でいろいろ議論されたが，概ね次のような手法で証明された（自分はよく分からなかったので聞いていた）
-
パターン1
- 三角不等式を直接(何らかの手法で)証明する
-
パターン2
- 今$p \leq 1$であるため，これが$q=1/p$であれば$q > 1$となって，Minkowski's inequalityが利用できるように式変形する
-
教えてもらったパターン2の証明(概略)を以下にメモする
- $\mathbf{D}$自体が三角不等式を満たしているとき，これを$p$乗した場合に成り立つかどうかを示す
- 今 $0 < p$であるため，$a \leq b + c$である3要素について，$a^p \leq (b + c)^p$が成り立つ
- ここで右辺を$(b + c)^p = {(b^p)^{1/p} + (c^p)^{1/p})}^p = {((b + \mathbf{0})^p)^{1/p} + ((c + \mathbf{0})^p)^{1/p})}^p$ というやばい気がする式展開を信じると
- 結果としてMinkowski's inequalityより$b^p + q^p$となる
Remark 2.16, 2.18, 2.20
- Skip
Remark 2.19
-
測度の積分を扱う必要があり，簡単には理解できないが，**仮にこの議論を離散測度でやったら？**という観点から議論したのでメモしておく
-
離散測度の場合， $\alpha = \sum \mathbf{a}_i \delta_{x_i}$ である砂の地位が，$\tau$分だけずらされるイメージで$T_\tau$をイメージすれば良い（はず）
-
このとき以下が成り立つ
\begin{align}
\mathcal{W}_2^2(T_{\tau\#}\alpha, T_{\tau'\#}\beta) &= L_{\mathbf{D}^2}(T_{\tau\#}\alpha, T_{\tau'\#}\beta) \\
&= \min_{P\in U(a,b)} \langle \mathbf{D}^2, P\rangle \\
\end{align}
-
距離$\mathbf{D}^2$について，それぞれ$\tau, \tau'$分だけスライドさせられているので以下のように展開する
- $||x - y||^2 = ||x - y||^2 - 2\langle \tau - \tau', x - y\rangle + ||\tau - \tau'||^2$
- つまり$\mathbf{D}^2$の部分は，これら3つの項の和に分けて評価すれば良さそう
-
第一項: 最適化問題の対象としてそのまま残り，これが$\mathcal{W}_2^2(\alpha, \beta)$ となる
-
第二項: それぞれ$\sum_{i,j}$を考えると，$x$の場合は$\sum_{j} y_j$が，$y$の場合はその逆が計算され，結果として平均的なものになる
-
第三項: 最適化問題に寄与しない定数項として，シフト分が残る
-
これらを考慮してRemark 2.19の意味が概ね理解できる（離散測度，ヒストグラムの場合）
次回
- 2.5のDual Problemを読み解く