ダイバージェンス

  • こちらにいろいろなダイバージェンス(2点間の遠近を数値化する方法)について書かれている
  • ぱらぱらめくってメモってみる
  • 大きく2つある
    • Bregman divergence
    • f-divergence
  • 両者の交わりに、α-divergenceがあり、その一つがKLdivergence
  • Bregman divergence
    • 空間に凸関数があるときに定められるダイバージェンス
    • ダイバージェンスを定義したい2点間について、凸関数の値の差から、2点のうち基準となる1点における接方向線での凸関数の値の「予測変化量」を差し引いた値
    • ルジャンドル変換によって、dualな関数を作ってそちらにdualになっているダイバージェンスがとれる。ちなみにルジャンドル変換は、凸関数に接線を引いて、そのy切片を扱うことで別の関数を取り出す方法で、dualを作る
    • この関数において局所に二階の微分が取れて、それがpositive definiteな行列を作れば、それは内積が入れられたことになるので、リーマン多様体になっていることもわかる
    • ある凸関数(これがポテンシャル関数)k(x)があったとき、その双対をルジャンドル変換でk^*(x^*)と取る。x^*は双対座標系。このとき、ダイバージェンスD(x||y) = k(x) + k^*(y^*) -x^T y^*となる
    • 一般化ピタゴラスの定理を満足するダイバージェンスになっている
    • ユークリッド空間の距離の二乗の半分はBregman divergenceの例
    • 正単体に納まる離散確率分布のKLdもBregman divergenceの例
    • 正定値行列の空間に行列のdeterminantの対数という関数を取ると、それがBregman divergenceを持つ多様体になっているという
    • Linear Programming(線形関数の最適化問題)もBregman divergenceで考えることができるらしい
    • その他。Itakura-Saito divergenceとか、Fermi-Dirac divergenceなどもBregman divergenceの一つとみなせるらしい
    • KLd, Itakura-Satiro divergenceはベータ-divergenceとしてひとくくりにもできるという
  • f-divergence: Invariant divergence in manifolds
    • 何かを細かく知ることができる場合と、おおざっぱにしか知ることができない場合がある。たとえば、生物の亜種まで知ることができてその割合を考えるか、亜種はわからないけれど種まではわかる場合の違いのようなもの。そのようなときに、細かい場合と大雑把な場合との両方について、対応する2点間のダイバージェンスを考えるとしたときに、あらっぽい方のダイバージェンスが細かいほうのダイバージェンス以下になるという条件をInformation monotonicityと言う
    • これを満足するようなdivergenceがInvariant divergence
    • D[p||q} = \sum p_i f(\frac{q_i}{p_i})f(1)=0\frac{q_i}{p_i}の関数fが決めるダイバージェンス。ちなみに、KLdの場合はf(u) = u - 1 - \log{u}
    • たくさんの例があるそうだ。Total variation, squared Hellinger distance, Pearson and Neyman Chi-square diverence, KLd, α-divergence(αのペアが±1のときがKLd)
    • α-divergence
      • f-divergenceの一つなのでinvariant divergenceである。その他、dually flatな性質も持つ
  • KLdを例に
    • KLdでは、D(p||q) = \phi(\theta(q)) + \psi(\eta(p)) - \eta(p)^T \theta(q)であるところが、Bregman の性質を表していて、D(p||q) = \sum p \frac{\log(p)}{\log(q)}なところ(f(u) = u - 1 - \log{u})がf-divergenceの性質を表している
  • Divergence 関数からそれを満足する多様体を考える
    • 確率分布間のDivergenceは2つの分布の式で与えられる。たとえばKLd(P||Q) = \sum p (\log{p} - \log{q})
    • Divergence関数の二階微分はリーマン計量
    • リーマン多様体の上に、座標系を取りたい。そのためには、多様体の局所に置いた座標系がどのように接続するかまでをコントロールする必要がある
    • さらに、二重平坦座標系を取ろうと思ったら、2つの座標系の接続具合をうまくコントロールする必要が出る
    • 一方、あるリーマン多様体にはdivergenceがいかようにも取れる。その中で、canonical なものとは何か、ということを考えることができて、そうすると、dually flat多様体のそれはBregman divergenceになるし、positive measures(確率分布とか?)の二重平坦な空間でのcanonical divergeneはα-divergenceなのだそう。また、KLdは、nカテゴリの離散確率分布のcanonical divergenceなのだという
    • Divergenceは一般に非対称だが、算術平均をとれば、対称なdivergenceが作れる。SJdはそういうもの。対称化したdivergenceとその元の非対称性divergenceとは、同じリーマン計量を与えるのだという。"squared Riemannian distance is the canonical divergence of a space with a symmetric divergence."とのこと
  • 以下、KLdのメモ
---
title: "DivergenceOfExponential"
author: "ryamada"
date: "2018年2月3日"
output: 
  html_document:
    toc: true
    toc_depth: 6
    number_section: true
---

# Exponential Family の確率密度関数表現

$$
p(x|\Theta) = e^{C(x) + \Theta^T F(x) - \phi(\Theta)} = e^{C(x) + \sum_{i=1}f_i(x) \theta_i - \phi(\Theta)}\\
$$


where
$$
\Theta^T = (\theta_1,...)\\
F(x)^T = \begin{pmatrix} f_1(x),...\end{pmatrix}\\
$$

$$
\log{p(x|\Theta)} = C(x) + \Theta^T F(x) - \phi(\Theta)
$$

# Exponential Family の2つの座標系

$$
\Theta^T = (\theta_1,...)
$$

$$
H ^T = (\eta_1,...) = E_\Theta[F(x)] = (E_\Theta[f_1(x)],...)
$$
where

$$
\eta_i = E_\Theta[f_i(x)] = \int p(x|\Theta) f_i(x) dx
$$

# Exponential Family のダイバージェンス

ダイバージェンスというのは、「距離の二乗」に似た概念。

ただし、距離という言うとき、AからBの距離とBからAの距離とは等しく、それを対称性であると言うが、ダイバージェンスでは、非対称性である。

天下り的には指数型分布のダイバージェンスは二種類のポテンシャル関数 $\phi(\Theta),\psi(H)$とを用いて、以下のように表されることが知られている。

$$
D(P||Q) = \phi(\Theta(Q)) + \psi(H(P)) - \Theta(Q)^T H(P)\\
\Theta(Q)^T H(P) = \sum_i \theta(Q)^i \eta(P)_i
$$

ダイバージェンスの非対称性は$D(P||Q) \ne D(Q||P)$ということである。

## Exponential Family のポテンシャル関数

指数型分布では

$$
\log{p(x|\Theta)} = C(x) + \Theta^T F(x) - \phi(\Theta)
$$

であり、このポテンシャル関数 $\phi(\Theta)$は、確率分布の特徴

$$
\int p(x|\Theta) dx = 1
$$

から、
$$
\phi(\Theta) = \log{ \int e^{C(x) + \Theta^T F(x)} dx}
$$

である。

他方、

$$
\psi(H) = \int p(x|\Theta) \log{p(x|\Theta)} - E_\Theta[C(x)]
$$
である。

これは、以下のようにして導ける。

### $\psi(H) = \int p(x|\Theta) \log{p(x|\Theta)} - E_\Theta[C(x)]$ の導出

また、$D(P||P)=0$であるから

$$
D(P||P)=0 = \phi(\Theta(P)) + \psi(H(P)) - \Theta(P)^T H(P)\\
\psi(H(P)) = \Theta(P)^T H(P) - \phi(\Theta(P)) 
$$

ここで、

$$
H(P) = E[F(x)] = \int p(x|\Theta) F(x) dx
$$
であるから、
$$
\Theta(P)^T H(P) = \int p(x|\Theta) \Theta^T F(x) dx
$$

したがって、

$$
\psi(H(P)) = \Theta(P)^T H(P) - \phi(\Theta(P))\\
\psi(H(P)) = \int p(x|\Theta) \Theta^T F(x) dx -\int p(x|\Theta) \phi(\Theta(P)) dx \\
\psi(H(P)) = \int p(x|\Theta) (\Theta^T F(x)-\phi(\Theta(P)) dx \\
\psi(H(P)) = \int p(x|\Theta) (C(x) + \Theta^T F(x)-\phi(\Theta(P)) dx - \int p(x|\Theta) C(x) dx\\
\psi(H(P)) = \int p(x|\Theta) \log(p(x|\Theta)) dx - E_\Theta[C(x)]\\
$$


## ユークリッド空間での距離の二乗

ユークリッド空間では、点の位置が座標 $Z=(z_1,...)$と表される。

2点$Z_U=(z_{u1},...)$,$Z_V=(z_{v1},...)$の距離の2乗は

$$
d(U,V) = d(V,U) = ||Z_U-Z_V||^2 = \sum_i (z_{ui}-z_{vi})^2 = \sum_i z_{ui}^2 + \sum_i z_{vi}^2 -2 \sum_i z_{ui} z_{vi}
$$

と表される。

ここで、ダイバージェンスが、非対称性であることを考慮して、$d(U,V)=d(V,U)$$\delta(U||V)$$\delta(V||U)$とに分けることにする。

$$
d(U,V) = d(V,U) = \delta(U||V) + \delta(V||U)\\
d(U,V) = d(V,U) = (\frac{1}{2} \sum_i z_{ui}^2 + \frac{1}{2} \sum_i z_{vi}^2 - \sum_i z_{ui} z_{vi}) + (\frac{1}{2} \sum_i z_{vi}^2 + \frac{1}{2} \sum_i z_{ui}^2 - \sum_i z_{vi} z_{ui})) \\
d(U,V) = d(V,U) =(\frac{1}{2} ||Z_U||^2 + \frac{1}{2} ||Z_V||^2 - Z_U^T Z_V) + (\frac{1}{2} ||Z_V||^2 + \frac{1}{2} ||Z_U||^2 - Z_V^T Z_U) 
$$

この$\delta(U||V)$をダイバージェンス
$$
D(U||V) = \phi(\Theta(U)) + \psi(H(V)) - \Theta(U)^T H(V)
$$
と対応付ける。

その結果
$$
\phi(\Theta(U)) =\frac{1}{2}||Z_U||^2\\
\psi(H(V)) =\frac{1}{2} ||Z_V||^2\\
\Theta(U)^T H(V) = Z_U^T Z_V
$$

となり、

$$
\phi(X) = \psi(X) = \frac{1}{2} ||X||^2\\
\Theta(X) = H(X) = Z_X
$$

がこの関係を満足することがわかる。

したがって、ユークリッド空間は、2つの座標系等しく、2つのポテンシャル関数も等しい特別な空間であることも読み取れる。

# 分布間の違いのいろいろな計量

## KL divergence

$$
KLd(P||Q) = D(P||Q) = \phi(\Theta(Q)) + \psi(H(P)) - \Theta(Q)^T H(P)\\
KLd(P||Q) = \phi(\Theta(Q)) + \int p(x|\Theta(P)) \log(p(x|\Theta_P)) dx - E_{\Theta(P)}[C(x)] - \Theta(Q)^T \int p(x|\Theta(P)) F(x) dx\\
KLd(P||Q) = \int p(x|\Theta(P)) ( \phi(\Theta(Q)) + \log(p(x|\Theta(P))) - C(x) - \Theta_Q^T F(x)) dx\\
KLd(P||Q) = \int  p(x|\Theta(P)) ( \phi(\Theta(Q)) + C(x) + \Theta(P)F(x) - \phi(\Theta(P)) - C(x) - \Theta(Q)^T F(x)) dx\\
KLd(P||Q) = \int  p(x|\Theta(P))) ( C(x) + \Theta(P)F(x) -\phi(\Theta(P)) - C(x) - \Theta(Q)^T F(x)) + \phi(\Theta(Q))  dx\\
KLd(P||Q) = \int p(x|\Theta(P)) ( \log(p(x|\Theta(P))) - \log(p(x|\Theta(Q)))) dx\\
KLd(P||Q) = \int p(x|\Theta(P))\frac{\log(p(x|\Theta(P)))}{\log(p(x|\Theta(Q)))}dx
$$