Shinkhorn Distances
$ ∀r, c \in Σ_d, ∀P \in U(r, c), h(P) \le h(r) + h(c). (1)
情報理論的不等式
二つの事象の関係性を知っていると, もう片方の値からもう片方の値を推測しやすくなり, 曖昧さが減る, 情報量が低下する
r, cが独立なら等式が立ち, そうではなく関係があるなら不等式になる
$ \text{KL}(P \parallel Q) = \sum_{i,j} p_{ij} \log \frac{p_{ij}}{q_{ij}}
$ log \frac{A}{B} = logA-logBより分解する
$ \text{KL}(P \parallel Q) = \sum_{i,j} p_{ij} \log p_{ij} - \sum_{i,j} p_{ij} \log (r_i c_j)
ここで右辺第一項は, 符号を反転すれば結合エントロピー$ h(P)になる
$ \sum_{i,j} p_{ij} \log p_{ij} = -h(P)
第二項はlogを分解し, 周辺確率の性質で整理する 周辺確率: $ \sum_j p_{ij} = r_i や $ \sum_i p_{ij} = c_j
$ \sum_{i,j} p_{ij} \log (r_i c_j) = \sum_{i,j} p_{ij} \log r_i + \sum_{i,j} p_{ij} \log c_j
$ \quad = \sum_{i} \left( \sum_j p_{ij} \right) \log r_i + \sum_{j} \left( \sum_i p_{ij} \right) \log c_j
$ \quad = \sum_{i} r_i \log r_i + \sum_{j} c_j \log c_j = -h(r) - h(c)
元のKL情報量の式に代入する
$ \text{KL}(P \parallel Q) = -h(P) - (-h(r) - h(c)) = h(r) + h(c) - h(P)
KL情報量は常に0以上であるから
$ h(r) + h(c) - h(P) \ge 0
移行して $ h(P) \le h(r) + h(c)
(1)の制約は独立性表として知られる$ rc^Tのエントロピーを$ h(rc^T) = h(r) + h(c)と表現できる, 厳密な定義である $ rc^Tは任意の確率分布$ Qに相当する. 独立性表と言っているのは, r, cが独立している仮定を置いているため エントロピーを考える時, 2要素が独立していると最大になる
非独立の時は関係性から情報を推測できてエントロピーが小さくなる, つまりある程度の秩序だった状態なのに対して, 独立しているならその逆として解釈できる
これを基準に部分集合を考えると定義しやすい
エントロピーの凹 (くぼ) 性より, 凸集合$ U \alpha (r, c) \subset U(r,c)を用いて導ける
上に凸なグラフのこと
convexは凸
今回の例で行くと, r, cについて, P, rc^tを用意した時, どんな組み合わせてあっても定義内ならr, cの定義から外れない
凸集合自体は, エントロピーの凹関数をalphaで区切った部分が該当する. 凹関数がalpha以上になる領域に現れる
独立しているとエントロピーが最大になり, 唯一$ h(P)=h(r)+h(c)となる場合である. これを基準とすると, 定義がやりやすい
定義: $ U \alpha (r, c) \stackrel{\mathrm{def}}{=} \{P \in U(r, c) | KL(P ‖rc^T ) \le \alpha\}= \{P \in U(r, c) | h(P) \ge h(r) + h(c) − \alpha\}
これは$ KL(P ‖rc^T ) = h(r) + h(c) − h(P)が求まるので等価
これさっき証明で出した式じゃんcustard.icon*2
一つ目の式: $ \{P \in U(r, c) | KL(P ‖rc^T ) \le \alpha\}
実際に存在するテーブル (データ分布)$ Pと, 独立性テーブル$ rc^Tの情報量の差が$ \alpha以下なPの集まりがU
ほぼ独立な範囲を定義
$ \alphaはハイパーパラメータ?
二つ目の式: $ \{P \in U(r, c) | h(P) \ge h(r) + h(c) − \alpha\}
KL情報量の式を変形して示せる
$ KL(P ‖rc^T ) = h(r) + h(c) − h(P)で, 一つ目の式の左辺に代入して整理すると求まる
実在する同時確率テーブルのエントロピーである$ h(P)は, ヒストグラムr, cのエントロピーの和から$ \alphaを引いたもの以上になる
このr, cが独立?
$ \alphaの凸集合を用いているが, 実在のテーブルのエントロピーが最大値から$ \alphaだけ小さくなった値より上にあることを示す
つまり十分に無秩序である
KL情報量が閾値以下となる表$ Pがある時
$ h(r), h(c)について, 十分なエントロピーを持つ$ U(r,c)の空間内の集合$ Pとして解釈できる
また, $ X, Y が結合確率分布$ Pに従うときの相互情報量$ I(X||Y)としても考えられる. このとき, 相互情報量は十分に小さい, ?つまり独立に近い状態となっている? 最大エントロピー原理より, 輸送コストは条件下で最も滑らかな結合確率になる
エントロピーが最大に近い場合の値を取るので, 程よく秩序がなく, 確率が分散する
数学的には, 元の線形計画法だと, 輸送ポリトープの頂点が解になったが, エントロピーを取ると内側になり, その位置は曖昧になる
Figure 1で図示されている. 確かに, ポリトープの外側の一点ではなく, 内側のalphaの領域に対して内積が取られている
特定の位置から位置に送る線形計画法より, エントロピーに従うと確率が散らばり, 自然な結合確率表が得られる
コスト最小化のために特定の点に確率が集約されるのではなく, エントロピーの制約によって薄まって分散される. 結合確率表の特定の点のみ使うより, 複数の点で色々な確率が存在する方が自然
ノイズや不確実性に強くなる. 極端な計画でなくなり, 一対一の関係でなくなるので, 柔軟になる
関連研究でグラフベースのノルムによる罰則項を用いて輸送行列を正則化するのに対し, 提案ではエントロピー正則化を用いて距離を定義する. これがShinkhorn距離
定義1 Shinkhorn Distances. $ d_{M,\alpha} (r, c) \stackrel{\mathrm{def}}{=} \underset{P \in U_\alpha(r,c)}{min}〈P, M 〉
>3.2 Metrci Properties, Shinkhorn距離が距離としての性質を持つことを示す? あまりにも難しいし, 飛ばして良さそうなため後回し
Properties 1
$ \alphaが十分に大きい時, 古典的な最適輸送距離と一致する
Property 1.
$ \alpha \to \inftyの時, つまり正則化がないとき, 純粋な輸送コストが求まる
$ \alpha=0の時, Shinkhorn 距離は閉形式を持ち, $ Mが負定値距離 (ユークリッド距離) と仮定すると負定値カーネルになる
$ \alpha=0は正則化最大
閉形式, closed-form
有限の計算で終わり, 四則演算やlogなどの関数で構成された式のこと
解として計算しやすい形になっていて良いということらしい
負定値は指数関数に通すと正定値になる
カーネルはよく分からない
すごく長い...
ここでは, 高次元の計算を不要にする便利な道具くらいの認識でOK
e.g. RBFカーネル. いわゆるカーネルトリック
正定値カーネルがデータの類似度を表し, 負定値カーネルは簡単に正定値に直せるので, どちらも有用?
3.1 で登場した定義を再掲: $ d_{M,\alpha} (r, c) \stackrel{\mathrm{def}}{=} \underset{P \in U_\alpha(r,c)}{min}〈P, M 〉
$ <,>行列の内積を取る計算だったはず. コスト行列と独立か独立に近い確率分布とを線形に組み合わせることで距離を求めている
正則化が最大ということは, 距離を知りたい確率分布同士が独立している. 上の式がこの時 ($ \alpha=0)に簡便に使えるという話かな
コスト行列が負定値の時, それを使うShinkhorn距離も性質を受け継ぐので, 機械学習などの応用で非常に使いやすい
確率分布の空間における性質を引き継ぐ
Properties 2は上で触れた正定値カーネルと独立の話だったので省略
>これのPloofと, その例外の話も一旦置いておく. 後でも良いはず Theorem 1もこの話
Lemma 1
接着補題をエントロピー制約について書き直している?
最適輸送距離が実際に距離として定義できるかを示すのかな