ダイバージェンス一覧

machine-learning

交差エントロピー

定義

離散

\mathcal{H}(p, q) \equiv -\sum p(x) \ln q(x)

連続

\mathcal{H}(p, q) \equiv -\int_\Omega p(x) \ln q(x) dx

KL (Kullback–Leibler) ダイバージェンス

確率分布間の距離を定義する (対称性がないので距離の公理は満たしていない)

定義

離散

\mathcal{D}_\mathrm{KL}(P \parallel Q) \equiv
  \sum p(x) \ln \frac{p(x)}{q(x)}

連続

\mathcal{D}_\mathrm{KL}(P \parallel Q) \equiv
  \int_\Omega p(x) \ln \frac{p(x)}{q(x)} dx

KL ダイバージェンスの最小化

$P$ を固定しての KL ダイバージェンスの最小化は、交差エントロピーの最大化と一致する。

指数分布

\mathcal{Exp}(x; \lambda) \equiv \frac{1}{\lambda} \exp\left(-\frac{x}{\lambda} \right)

指数分布間の KL ダイバージェンスは

\mathcal{D}_{KL}(P \parallel Q) = \ln\frac{\lambda_{q}}{\lambda_{p}} + \frac{\lambda_{p}}{\lambda_{q}} - 1

より、分布パラメータ間の板倉斉藤距離と一致する。

Maxima: expand(rat(integrate(exp(-x/a)/a * log((exp(-x/a)/a)/(exp(-x/b)/b)), x, 0, inf)));
\mathcal{D}_\mathrm{KL}(P \parallel Q) = \ln\frac{\lambda_{q}}{\lambda_{p}} + \frac{\lambda_{p}}{\lambda_{q}} - 1

最適化するときは $\lambda_{p}$ が定数になるので $\ln\lambda_{q} + \frac{\lambda_{p}}{\lambda_{q}}$ を最小化すればよい

ポアソン分布

\mathcal{Pois}(x; \lambda) = \frac{\lambda^{x} e^{-\lambda}}{x!}

ポアソン分布の KL ダイバージェンスは

より、分布パラメータ間の I ダイバージェンス(=p log(p/q) + (q-p))と一致する

\begin{aligned}
\mathcal{D}_\mathrm{KL}(P \parallel Q)
  &= \sum_{x=0}^{\infty}
    \mathcal{Pois}(x; \lambda_{p})
        \ln \frac{\mathcal{Pois}(x; \lambda_{p})}
                    {\mathcal{Pois}(x; \lambda_{q})} \\
  &= \lambda_{p} \ln \frac{\lambda_{p}}{\lambda_{q}} + (\lambda_{q} - \lambda_{p})
\end{aligned}
  Sum[λp^n Exp[-λp] / n! {Ln[(λp/λq)^n Exp[λq-λp]]}, n, 0, inf]
= Sum[λp^n Exp[-λp] / n! {Ln[(λp/λq)^n] + (λq-λp)]}, n, 0, inf]
= Sum[λp^n Exp[-λp] / n! {n (Ln[λp/λq]) + (λq-λp)]}, n, 0, inf]
= Sum[λp λp^(n-1) Exp[-λp] / (n-1)! (Ln[λp/λq]), n, 1, inf]
+ Sum[λp^n Exp[-λp] / n! (q-p)], n, 0, inf]
= λp Ln[λp/λq] + (λq - λp)

最適化するときは $\lambda_{p}$ が定数になるので $\lambda_{q} - \lambda_{p} \ln \lambda_{q}$ を最小化すればよい。

正規分布

一次元

\mathcal{D}_\mathrm{KL}(P \parallel Q)
 = \frac{1}{2} \left[ \ln\frac{\sigma_{p}^{2}}{\sigma_{q}^{2}}
    + \frac{\sigma_{q}^{2}}{\sigma_{p}^{2}}
    + \left( \frac{\mu_{q} - \mu_{p}}{\sigma_{p}} \right)^{2} - 1
 \right]

多変量

\mathcal{D}_\mathrm{KL}(P \parallel Q)
 = \frac{1}{2} \left[ \ln \frac{|\Sigma_{p}|}{|\Sigma_{q}|}
     + \mathrm{tr}(\Sigma_{p}^{-1} \Sigma_{q})
     + (\mu_{q} - \mu_{p})^{\top} \Sigma_{p}^{-1} (\mu_{q} - \mu_{p})
     - d
 \right]
おまけ

$\Sigma = \Sigma_{p} = \Sigma_{q}$ を仮定すると

\mathcal{D}_\mathrm{KL}(P \parallel Q)
 = \frac{1}{2} \left[
     (\mu_{q} - \mu_{p})^{\top} \Sigma^{-1} (\mu_{q} - \mu_{p})
 \right]

ガンマ分布

\mathcal{D}_\mathrm{KL}(P \parallel Q)
  = (k_{p} - k_{q}) \psi(k_{p}) - \ln \frac{\Gamma(k_{p})}{\Gamma(k_{q})}
  - k_{q} \ln \frac{\theta_{p}}{\theta_{q}} + k_{p} \frac{\theta_{p} - \theta_{q}}{\theta_{q}}

ここで $\psi$ は digamma function であり、

\psi(x) = \frac{d}{dx} \ln \Gamma(x) = \frac{1}{\Gamma(x)} \frac{d}{dx} \Gamma(x)

で定義される。ちなみに $\psi(1) = -\gamma$ である ($\gamma$ はオイラー・マスケローニ定数)。

おまけ

$\theta_{p} = \theta_{q} = 1$ とすると

\mathcal{D}_\mathrm{KL}(P \parallel Q) = (k_{p} - k_{q}) \psi(k_{p}) - \ln \frac{\Gamma(k_{p})}{\Gamma(k_{q})}

これを $k_{p}$ で微分すると $k’_{q} (\psi(k_{q}) - \psi(k_{p}))$ となる。

リンク関数を log として、これを利用すると、勾配方向は $(\psi(x) - \psi(z)) z$ となる。

JS (Jensen-Shannon) ダイバージェンス

対称化 KL ダイバージェンス

\begin{aligned}
\mathcal{D}_\mathrm{JS}(P \parallel Q) &\equiv
  \frac{1}{2} \left\{\int p(x) \ln \frac{2 p(x)}{p(x) + q(x)} dx + \int q(x) \ln \frac{2 q(x)}{p(x) + q(x)} dx\right\} \\&=
  \frac{1}{2} \left\{
    \mathcal{D}_\mathrm{KL}(P \parallel R) +
    \mathcal{D}_\mathrm{KL}(Q \parallel R) \right\}
\end{aligned}

ここで $r(x) = \frac{p(x)+q(x)}{2}$ ($R = \frac{P + Q}{2}$) とおいた。

Frobenius ノルム (二乗誤差)

\mathcal{D}_\mathrm{F}(y, x) \equiv \frac{1}{2} (y - x)^2

板倉斉藤距離 (ISダイバージェンス)

\mathcal{D}_\mathrm{IS}(y, x) \equiv \frac{y}{x} + \ln \frac{x}{y} - 1
  • 平均が $x$, $y$ の指数分布間の KL ダイバージェンスに等しい
  • 形状パラメータが $1$ で期待値と分散が一致するガンマ分布間の KL ダイバージェンスに等しい
  • 形状パラメータが等しく、期待値と分散が一致するガンマ分布間の KL ダイバージェンスは $k \mathcal{D}_\mathrm{IS}(y, x)$ となる
  • 複素正規分布 $z_{i} \sim \mathcal{N}(0, \lambda_{i})$ における $|z_{i}|^2$ のもとでの $\Lambda$ の最尤推定は、板倉斉藤距離の最小化に等しい (?)

I ダイバージェンス (一般化 KL ダイバージェンス)

\mathcal{D}_\mathrm{I}(y, x) \equiv y \ln \frac{y}{x} + (x - y)

複素ポアソン分布

f_{z}(z; \lambda, p) \equiv
    \frac{p e^{-\lambda}}{2 \pi}
    \frac{|z|^{p-2} \lambda^{|z|^p}}{(|z|^p)!}

ここで、$|z|^p$ が平均 $\lambda$ のポアソン分布に従う。

複素ポアソン分布 $z_{i} \sim \mathrm{cPois}(\lambda_{i}, 2)$ における $|z_{i}|^2$ のもとでの $\Lambda$ の最尤推定と、I ダイバージェンスの最小化は等価 (?)

  • 定常ガウス過程 → 複素正規分布 → 板倉斉藤距離
  • 定常・・・過程 → 複素ポアソン分布 → Iダイバージェンス

Bregman ダイバージェンス

\mathcal{D}_{\phi}(y, x) \equiv \phi(y) - \phi(x) - \frac{d\phi(x)}{dx} (y - x)
\mathcal{D}_{\phi}(P \parallel Q) = \phi(q) - \phi(p) - \langle q - p, \nabla \phi(p) \rangle

ここで $\phi$ は任意の微分可能な凸関数。

$\phi(z)$   $\phi’(xy)$
$z^2$ 二乗誤差 (正規分布) $\frac{\phi’(x) \phi’(y)}{\phi’(1)}$
$-\ln z$ 板倉斉藤距離 (指数分布) $\phi’(x) + \phi’(y) + \phi’(1)$
$z (\ln z + 1)$ Iダイバージェンス (ポアソン分布) 同上
$\frac{1}{(\beta - 1) \beta} \left( z^{\beta} - \beta z + \beta - 1 \right)$ $\beta$ ダイバージェンス  
$\sum_{i} p_{i} \ln p_{i}$ KL ダイバージェンス  
$z \ln z + (1 - x) \ln(1 - x)$ ロジスティック損失  

行列ダイバージェンス

定義

行列間の距離尺度。

C_{\phi}(B \mid A) = \phi(B) - \phi(A) - \textrm{tr}\left(\nabla\phi(A)^{\top} (B - A) \right)

ここで $\phi(\cdot)$ は行列を引数にとるスカラー関数 (微分可能な凸関数) である。

Log-Determinant ダイバージェンス

\phi(Z) = -\ln\textrm{det}(Z)

と定義すると

C_\textrm{LD}(B \mid A) = -\ln \textrm{det}(B A^{-1}) + \textrm{tr}(B A^{-1}) - M

として Log-Determinant ダイバージェンスが導かれる (A と B はそれぞれ M 行 M 列の行列)。

von Neumann ダイバージェンス

\phi(Z) = \textrm{tr}(Z \ln Z - Z)

と定義すると

C_\textrm{vN}(B \mid A) = \textrm{tr}(B \ln B - B \ln A - B + A)

として von Neumann ダイバージェンスが導かれる。

導出

行列を引数にとるスカラー関数 $\phi(\cdot)$ のテイラー展開を考える。

\phi(A + \Delta) = \phi(A) + \textrm{tr}\left(\nabla\phi(A)^{\top} \Delta \right) + O(|\Delta|^{2})

ここで $\Delta$ は微小変化行列である。

$\Delta = B - A$ とすると

\begin{aligned}
\phi(A + \Delta)
 &= \phi(B) \\
 &= \phi(A) + \textrm{tr}\left(\nabla\phi(A)^{\top} (B - A) \right) + O(|B - A|^{2})
\end{aligned}

より

O(|B - A|^{2}) = \phi(B) - \phi(A) - \textrm{tr}\left(\nabla\phi(A)^{\top} (B - A) \right)

となるので、Bregman 行列ダイバージェンスは、2 次以降の誤差を測っていることになる。

ベクトルダイバージェンス

行列ダイバージェンスの列数が 1 の特殊形。

定義

C_{\phi}(\vec{y} \parallel \vec{x})
  = \phi(\vec{y}) - \phi(\vec{x})
  - \nabla \phi(\vec{x})^{\top} (\vec{y} - \vec{x})

特殊形 1

\phi(\vec{z}) = \| \vec{z} \|^{2}

と定義すると

\begin{aligned}
C_{\phi}(\vec{y}, \vec{x})
  &= \| \vec{y} \|^{2} - \| \vec{x} \|^{2} - (2 x)^{\top} (\vec{y} - \vec{x}) \\
  &= \| \vec{y} \|^{2} - \| \vec{x} \|^{2} - 2 x^{\top} \vec{y} + 2 \| \vec{x} \|^2 \\
  &= \| \vec{y} \|^{2} - 2 x^{\top} \vec{y} + \| \vec{x} \|^2 \\
  &= \| \vec{y} - \vec{x} \|^{2} \\
\end{aligned}

となり、ユークリッド距離になる。

特殊形 2

\phi(\vec{z}) = -\ln \| \vec{z} \| = -\frac{1}{2} \ln \| \vec{z} \|^{2}

と定義すると

\begin{aligned}
C_{\phi}(y, x)
  &= -\ln \| \vec{y} \|
     +\ln \| \vec{x} \|
     + \frac{\vec{x}}{\| \vec{x} \|^{2}}  (\vec{y} - \vec{x}) \\
  &= \ln \frac{\| \vec{x} \|}{\| \vec{y} \|}
     + \frac{\vec{x}^{\top}}{\| \vec{x} \|^{2}}  (\vec{y} - \vec{x}) \\
  &= \ln \frac{\| \vec{x} \|}{\| \vec{y} \|}
     + \frac{\vec{x}^{\top} \vec{y}}{\| \vec{x} \|^{2}}  - 1 \\
  &= \frac{\vec{x}^{\top} \vec{y}}{\| \vec{x} \|^{2}}
   + \ln \frac{\| \vec{x} \|}{\| \vec{y} \|}
   - 1 \\
 \end{aligned}
最適化

$\vec{y}$ をパラメータとする。

最小化問題としたいとき
\begin{aligned}
\frac{\vec{x}^{\top} \vec{y}}{\| \vec{x} \|^{2}}
  + \ln \frac{\| \vec{x} \|}{\| \vec{y} \|} - 1
&\Rightarrow
\vec{x}^{\top} \vec{y}
  + \| \vec{x} \|^{2} \ln \frac{\| \vec{x} \|}{\| \vec{y} \|}
  - \| \vec{x} \|^{2} \\
&\Rightarrow
\vec{x}^{\top} \vec{y}
  - \| \vec{x} \|^{2} \ln \| \vec{y} \|
\end{aligned}

を最小化すればいい。

最大化問題としたいとき

最小化の場合の符号を反転した

\| \vec{x} \|^2 \ln \| y \| - \vec{x}^{\top} \vec{y}

を最大化すればよい。

特殊形 3

\phi(\vec{z}) = \| \vec{z} \| \ln \| \vec{z} \|
              = \frac{1}{2} \| \vec{z} \| \ln \| \vec{z} \|^{2}

と定義すると

\begin{aligned}
\nabla_{\vec{x}} \| \vec{x} \| \ln \| \vec{x} \|
 &= \frac{\vec{x}}{\| \vec{x} \|} \ln \| \vec{x} \|
  + \| \vec{x} \| \frac{\frac{\vec{x}}{\| \vec{x} \|}}{\| \vec{x} \|} \\
 &= \frac{\vec{x}}{\| \vec{x} \|} \ln \| \vec{x} \|
  + \frac{\vec{x}}{\| \vec{x} \|} \\
 &= \frac{1 + \ln \| \vec{x} \|}{\| \vec{x} \|} \vec{x}
\end{aligned}

より

\begin{aligned}
C_{\phi}(\vec{y} \parallel \vec{x})
 &= \| \vec{y} \| \ln \| \vec{y} \|
  - \| \vec{x} \| \ln \| \vec{x} \|
  - \frac{1 + \ln \| \vec{x} \|}{\| \vec{x} \|} \vec{x}^{\top} (\vec{y} - \vec{x}) \\
 &= \| \vec{y} \| \ln \| \vec{y} \|
  - \| \vec{x} \| \ln \| \vec{x} \|
  - \frac{1 + \ln \| \vec{x} \|}{\| \vec{x} \|} \vec{x}^{\top} \vec{y}
  + \| \vec{x} \| + \| \vec{x} \| \ln \| \vec{x} \| \\
 &= \| \vec{y} \| \ln \| \vec{y} \|
  - \frac{1 + \ln \| \vec{x} \|}{\| \vec{x} \|} \vec{x}^{\top} \vec{y}
  + \| \vec{x} \|
\end{aligned}

となる。

最適化

$\vec{y}$ をパラメータとする。

最小化問題としたいとき
\begin{aligned}
\| \vec{y} \| \ln \| \vec{y} \|
  - \frac{1 + \ln \| \vec{x} \|}{\| \vec{x} \|} \vec{x}^{\top} \vec{y}
  + \| \vec{x} \|
&\Rightarrow
  \| \vec{x} \| \| \vec{y} \| \ln \| \vec{y} \|
  - (1 + \ln \| \vec{x} \|) \vec{x}^{\top} \vec{y}
  + \| \vec{x} \|^{2} \\
&\Rightarrow
  \| \vec{x} \| \| \vec{y} \| \ln \| \vec{y} \|
  - (1 + \ln \| \vec{x} \|) \vec{x}^{\top} \vec{y}
\end{aligned}

を最小化すればよい。

最大化問題としたいとき

最小化の場合の符号を反転した

(1 + \ln \| \vec{x} \|) \vec{x}^{\top} \vec{y} -
\| \vec{x} \| \| \vec{y} \| \ln \| \vec{y} \|

を最大化すればよい。

f ダイバージェンス

\mathcal{D}_{f}(P \parallel Q) \equiv
  \int f\left(\frac{p(x)}{q(x)}\right) q(x) d\mu(x)
  • $\mathcal{D}_{f(t)=t \ln t}(P \parallel Q) = \mathcal{D}_\mathrm{KL}(P \parallel Q)$ (KL-divergence)
  • $\mathcal{D}_{f(t)=-\ln t}(P \parallel Q) = \mathcal{D}_\mathrm{KL}(Q \parallel P)$ (reverse KL-divergence)
f(t)  
$(\sqrt{t} - 1)^{2}$ or $2 (1 - \sqrt{t})$ Hellinger distance
$\frac{1}{2} |t - 1|$ total variation distance
$(t - 1)^{2}$ or $t^2 - 1$ $\chi^{2}$-divergence

また

f(t) = \left\{ \begin{array}{ll}
    \frac{1}{\alpha (1 - \alpha)} (1 - t^{\alpha}) & \alpha \neq 1, \alpha \neq 0 \\
    t \ln t                                        & \alpha = 1        \\
    -\ln t                                         & \alpha = 0
\end{array} \right.

のときは $\alpha$ ダイバージェンスになる。

α ダイバージェンス

\mathcal{D}_{\alpha}(P \parallel Q) \equiv
  \frac{1}{\alpha (1 - \alpha)} \left(
    1 - \int p^{\alpha}(x) q^{1 - \alpha}(x) d\mu(x)
  \right)
  • $\mathcal{D}_{1}(P \parallel Q) = \mathcal{D}_\mathrm{KL}(P \parallel Q)$ (KL-divergence)
  • $\mathcal{D}_{-1}(P \parallel Q) = \mathcal{D}_\mathrm{KL}(Q \parallel P)$ (inclusive KL-divergence)
  • $\mathcal{D}_{\frac{1}{2}}(P \parallel Q) = \mathcal{D}_\mathrm{H}(P, Q)$ (Hellinger 距離)

β ダイバージェンス

定義

\mathcal{D}_{\alpha}(P \parallel Q) \equiv
  \frac{p^{\beta}}{\beta (\beta - 1)} +
  \frac{q^{\beta}}{\beta} - \frac{p q^{\beta - 1}}{\beta - 1}

二乗誤差

$\beta = 2$ のとき二乗誤差 (Frobenius ノルム) になる。

\begin{aligned}
\mathcal{D}_{2}(y, x)
  &= \frac{y^{2}}{2} + \frac{x^{2}}{2} - y x \\
  &= \frac{1}{2} \left( y^{2} - 2 x y + x^{2} \right) \\
  &= \frac{1}{2} ( y - x )^{2} \\
\end{aligned}
\therefore \mathcal{D}_{2}(P \parallel Q) = \mathcal{D}_\mathrm{F}(P, Q)

I ダイバージェンス

$\beta = 1$ のとき I ダイバージェンスになる。

\begin{aligned}
\mathcal{D}_{1}(y, x)
  &= \lim_{\beta \rightarrow 1} \frac{1}{\beta} \frac{y y^{\beta-1}}{\beta - 1} +
  x - \lim_{\beta \rightarrow 1} \frac{x y^{\beta-1}}{\beta - 1} \\
  &= y \ln y + x - y \ln x \\
  &= y \ln \frac{y}{x} + x
\end{aligned}

ここで

\begin{aligned}
\lim_{\beta \rightarrow 1} \frac{y x^{\beta - 1}}{\beta - 1}
  &= \lim_{\beta \rightarrow 1} y x^{\beta - 1} \ln x \\
  &= y \ln x
\end{aligned}

を利用した。

\therefore \mathcal{D}_{1}(P \parallel Q) = \mathcal{D}_\mathrm{I}(P \parallel Q)

板倉斉藤距離

$\beta = 0$ のとき板倉斉藤距離 (IS-distance) になる。

\begin{aligned}
\mathcal{D}_{0}(y, x) &=
  \lim_{\beta \rightarrow 0} \frac{1}{\beta - 1} \frac{y^{\beta}}{\beta} +
  \lim_{\beta \rightarrow 0} \frac{x^{\beta}}{\beta} -
  \frac{y}{x} \\
 &= \frac{y}{x} - \ln \frac{y}{x} \\
\end{aligned}

ここで、

\begin{aligned}
\lim_{\beta \rightarrow 0} \frac{x^{\beta}}{\beta}
  &= \lim_{\beta \rightarrow 0} x^{\beta} \ln x \\
  &= \ln x
\end{aligned}

を利用した。

\therefore \mathcal{D}_{0}(P \parallel Q) = \mathcal{D}_\mathrm{IS}(P \parallel Q) 

Hellinger 距離

\begin{aligned}
\mathcal{D}_{H}(P, Q)
 &= \sqrt{\frac{1}{2} \int \left( \sqrt{p(x)} - \sqrt{q(x)} \right)^{2} dx}
 \\
 &= \sqrt{1 - \int \sqrt{p(x) q(x)} dx}
\end{aligned}

p-Wasserstein 距離

w_{p}(P, Q) \equiv \left\{ \int_{0}^{1} du: \left| F_{P}^{-1}(u) -F_{Q}^{-1}(u) \right|^{p} \right\}^{\frac{1}{p}}

ここで、$F_{P}(\cdot)$ と $F_{Q}(\cdot)$ は、それぞれ確率分布 $P$ と $Q$ の累積分布関数である。

正規分布

正規分布 $\mathcal{N}(\mu_{P}, \sigma_{P}^{2})$ と $\mathcal{N}(\mu_{Q}, \sigma_{Q}^{2})$ の間の $w_{2}^{2}(P, Q)$ ($p=2$) は

w_{2}^{2}(P, Q) = \| \mu_{P} - \mu_{Q} \|_{2}^{2} + (\sigma_{P}^{2} + \sigma_{Q}^{2} - 2 \sqrt{\sigma_{P}^{2} \sigma_{Q}^{2}})

となる。

多変量正規分布

多変量正規分布 $\mathcal{N}(\mu_{P}, \Sigma_{P})$ と $\mathcal{N}(\mu_{Q}, \Sigma_{Q})$ の間の $w_{2}^{2}(P, Q)$ ($p=2$) は

w_{2}^{2}(P, Q) = \| \mu_{P} - \mu_{Q} \|_{2}^{2} + \mathrm{tr}\left(\Sigma_{P} + \Sigma_{Q} - 2 \left(\Sigma_{Q}^{\frac{1}{2}} \Sigma_{P}^{2} \Sigma_{Q}^{\frac{1}{2}}\right)^{\frac{1}{2}} \right)

となる。

Cramér 距離

l_{p}(P, Q) \equiv \left\{ \int_{-\infty}^{\infty} dx: \left| F_{P}(x) -F_{Q}(x) \right|^{p} \right\}^{\frac{1}{p}}

ここで、$F_{P}(\cdot)$ と $F_{Q}(\cdot)$ は、それぞれ確率分布 $P$ と $Q$ の累積分布関数である。