唯物是真 @Scaled_Wurm

プログラミング(主にPython2.7)とか機械学習とか

正規分布間のKLダイバージェンスの導出

上の記事を読んで勉強になったのですが、数式がテキストで読みづらかったのと、多変量でない1次元の正規分布の導出の段階でよくわからなかったので調べて記事にまとめました

注意

数式はMathJax(JavaScriptのライブラリ)を使って表示しています
SVGが描画できないと表示されないので、最近のブラウザで閲覧してください

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

確率分布の差の大きさを測る尺度。
機械学習の分野だとパラメータの最適化などは、結局KLダイバージェンスの最小化と同じになることが多い。
本とか論文を読んでいるとよく出てくる

2つの確率分布\(P, Q\)を考える

確率分布が連続確率分布の時KLダイバージェンスは以下のようになる
$$D_{\mathrm{KL}}(P\|Q) = \int_{-\infty}^{\infty} p(x) \log \frac{p(x)}{q(x)} \; dx$$

性質

常に0以上であり、0になるのは2つの分布が等しい時であることと、\(D_{\mathrm{KL}}(P\|Q) \ne D_{\mathrm{KL}}(Q\|P)\)であることに注意
その他の詳しい性質は以下の記事参照

1次元正規分布のKLダイバージェンス

1次元正規分布は平均を\(\mu\)、分散を\(\sigma^2\)としたとき以下のような式になっている
$$N(\mu, \sigma)=\frac{1}{\sqrt{2\pi\sigma^{2}}} \exp\!\left(-\frac{(x-\mu)^2}{2\sigma^2} \ \right) $$
2つの正規分布\(p(x)=N(\mu_1, \sigma_1), q(x)=N(\mu_2, \sigma_2)\)の間のKLダイバージェンスを考えます

$$D_{\mathrm{KL}}(P\|Q) = \int_{-\infty}^{\infty} p(x) \log \frac{p(x)}{q(x)} \; dx$$
まず\(\log\)とその中身について式展開します

$$
\begin{eqnarray*}
\log \frac{p(x)}{q(x)} &=& \log p(x) - \log q(x) \\
&=& \log \frac{1}{\sqrt{2\pi\sigma^{2}_1}} \exp\!\left(-\frac{(x-\mu_1)^2}{2\sigma^2_1} \ \right)- \log \frac{1}{\sqrt{2\pi\sigma^{2}_2}} \exp\!\left(-\frac{(x-\mu_2)^2}{2\sigma^2_2} \ \right) \\
&=& \left( -\frac{1}{2} \log 2\pi\sigma^{2}_1 - \frac{(x-\mu_1)^2}{2\sigma^2_1} \right) - \left( -\frac{1}{2} \log 2\pi\sigma^{2}_2 - \frac{(x-\mu_2)^2}{2\sigma^2_2} \right) \\
&=& \log \frac{\sigma_2}{\sigma_1} + \frac{(x-\mu_2)^2}{2\sigma^2_2} - \frac{(x-\mu_1)^2}{2\sigma^2_1}
\end{eqnarray*}
$$

ここで確率分布\(p(x)\)に基づく期待値を\(\mathrm{E}_p\left[\cdot\right]\)とすると、以下のように期待値を使って表すことができる
$$
\begin{eqnarray*}
\int_{-\infty}^{\infty} p(x) \log \frac{p(x)}{q(x)} \; dx
&=& \mathrm{E}_p\left[ \log \frac{p(x)}{q(x)} \right] \\
&=& \mathrm{E}_p\left[\log \frac{\sigma_2}{\sigma_1}\right] + \mathrm{E}_p\left[\frac{(x-\mu_2)^2}{2\sigma^2_2}\right] - \mathrm{E}_p\left[\frac{(x-\mu_1)^2}{2\sigma^2_1}\right]
\end{eqnarray*}
$$
1つ目の期待値は\(x\)に関する項を含まないのでそのままになる。
$$\mathrm{E}_p\left[\log \frac{\sigma_2}{\sigma_1}\right]=\log \frac{\sigma_2}{\sigma_1}$$
2つ目の期待値は確率変数の分散の定義から次の関係\(\mathrm{E}_p\left[x^2\right] = \sigma^2_1 + \mu^2_1\)を用いると、以下のように計算できる
$$
\begin{eqnarray*}
\mathrm{E}_p\left[\frac{(x-\mu_2)^2}{2\sigma^2_2}\right]&=&\frac{\mathrm{E}_p\left[x^2\right] + \mathrm{E}_p\left[-2x\mu_2\right] + \mathrm{E}_p\left[\mu_2^2\right]}{2\sigma^2_2} \\
&=& \frac{(\sigma^2_1 + \mu_1^2 ) - 2\mu_1\mu_2 + \mu_2^2}{2\sigma^2_2} \\
&=& \frac{\sigma_1^2 + (\mu_1 - \mu_2)^2}{2\sigma^2_2}
\end{eqnarray*}
$$
3つ目の期待値も同様に計算できる
$$
\begin{eqnarray*}
\mathrm{E}_p\left[\frac{(x-\mu_1)^2}{2\sigma^2_1}\right] &=& \frac{\mathrm{E}_p\left[x^2\right] - \mathrm{E}_p\left[2x \mu_1\right] + \mathrm{E}_p\left[\mu_1^2\right]}{2\sigma^2_1} \\
&=& \frac{(\sigma^2_1 + \mu^2_1) - 2\mu_1^2 + \mu_1^2}{2\sigma^2_1} \\
&=&\frac{1}{2}
\end{eqnarray*}
$$
まとめると
$$
\begin{eqnarray*}
D_{\mathrm{KL}}(P\|Q) &=& \log \frac{\sigma_2}{\sigma_1} + \frac{\sigma_1^2 + (\mu_1 - \mu_2)^2}{2\sigma^2_2} - \frac{1}{2}
\end{eqnarray*}
$$

多変量正規分布のKLダイバージェンス

\(d\)次元の多変量正規分布は平均(ベクトル)を\(\vec \mu\)、共分散行列を\(\Sigma\)としたとき以下のような式になっている
$$N({\vec \mu}, \Sigma)=\frac{1}{\sqrt{(2\pi)^d|\Sigma|}} \exp\!\left(-\frac{1}{2}({\vec x}-{\vec \mu})^\mathrm{T} \Sigma^{-1} ({\vec x}-{\vec \mu}) \right) $$
2つの正規分布\(p({\vec x})=N(\vec\mu_1, \Sigma_1), q({\vec x})=N(\vec \mu_2, \Sigma_2)\)の間のKLダイバージェンスを考えます

$$D_{\mathrm{KL}}(P\|Q) = \int_{-\infty}^{\infty} p({\vec x}) \log \frac{p({\vec x})}{q({\vec x})} \; d{\vec x}$$
まず\(\log\)とその中身について式展開します

$$
\begin{eqnarray*}
\log \frac{p({\vec x})}{q({\vec x})} &=& \log p({\vec x}) - \log q({\vec x}) \\
&=& \log \frac{1}{\sqrt{(2\pi)^d|\Sigma_1|}} \exp\!\left(-\frac{1}{2}({\vec x}-{\vec \mu_1})^\mathrm{T} \Sigma_1^{-1} ({\vec x} -{\vec \mu_1}) \right) \\
&&- \log \frac{1}{\sqrt{(2\pi)^d|\Sigma_2|}} \exp\!\left(-\frac{1}{2}({\vec x}-{\vec \mu_2})^\mathrm{T} \Sigma_2^{-1} ({\vec x}-{\vec \mu_2}) \right) \\
&=& \left( -\frac{d}{2} \log 2\pi -\log |\Sigma_1| - \frac{1}{2}({\vec x}-{\vec \mu_1})^\mathrm{T} \Sigma_1^{-1} ({\vec x} -{\vec \mu_1}) \right)\\
&& - \left( -\frac{d}{2} \log 2\pi -\log |\Sigma_2| - \frac{1}{2}({\vec x}-{\vec \mu_2})^\mathrm{T} \Sigma_2^{-1} ({\vec x} -{\vec \mu_2}) \right)\\
&=& \frac{1}{2}\log \frac{|\Sigma_2|}{|\Sigma_1|} + \frac{1}{2}({\vec x}-{\vec \mu_2})^\mathrm{T} \Sigma_2^{-1} ({\vec x} -{\vec \mu_2}) - \frac{1}{2}({\vec x}-{\vec \mu_1})^\mathrm{T} \Sigma_1^{-1} ({\vec x} -{\vec \mu_1})
\end{eqnarray*}
$$
1次元正規分布の場合と同様にKLダイバージェンスを期待値で表すと以下のようになる
$$
\begin{eqnarray*}
D_{\mathrm{KL}}(P\|Q)
&=& \mathrm{E}_p\left[\frac{1}{2}\log \frac{|\Sigma_2|}{|\Sigma_1|}\right]\\
&& + \mathrm{E}_p\left[\frac{1}{2}({\vec x}-{\vec \mu_2})^\mathrm{T} \Sigma_2^{-1} ({\vec x} -{\vec \mu_2})\right]\\
&& - \mathrm{E}_p\left[\frac{1}{2}({\vec x}-{\vec \mu_1})^\mathrm{T} \Sigma_1^{-1} ({\vec x} -{\vec \mu_1})\right]
\end{eqnarray*}
$$
第1項は定数なので
$$\mathrm{E}_p\left[\frac{1}{2}\log \frac{|\Sigma_2|}{|\Sigma_1|}\right] = \frac{1}{2}\log \frac{|\Sigma_2|}{|\Sigma_1|}$$
第2項以降は行列の二次形式の性質\(({\vec x}-{\vec \mu})^\mathrm{T} \Sigma^{-1} ({\vec x} -{\vec \mu})=\mathrm{tr}\left\{({\vec x}-{\vec \mu})^\mathrm{T} \Sigma^{-1} ({\vec x} -{\vec \mu})\right\}\)とトレースの性質\(\mathrm{tr}\left\{({\vec x}-{\vec \mu})^\mathrm{T} \Sigma^{-1} ({\vec x} -{\vec \mu})\right\}=\mathrm{tr}\left\{\Sigma^{-1}({\vec x}-{\vec \mu}) ({\vec x} -{\vec \mu})^\mathrm{T} \right\}\)を用いる
$$
\begin{eqnarray*}
\mathrm{E}_p\left[({\vec x}-{\vec \mu_2})^\mathrm{T} \Sigma_2^{-1} ({\vec x} -{\vec \mu_2})\right]
&=&\mathrm{E}_p\left[\mathrm{tr}\left\{\Sigma_2^{-1}({\vec x}-{\vec \mu_2}) ({\vec x} -{\vec \mu_2})^\mathrm{T} \right\}\right]\\
&=&\mathrm{tr}\left\{\Sigma_2^{-1} \mathrm{E}_p\left[({\vec x}-{\vec \mu_2}) ({\vec x} -{\vec \mu_2})^\mathrm{T}\right] \right\}\\
&=&\mathrm{tr}\left\{\Sigma_2^{-1} \left(\mathrm{E}_p\left[{\vec x}{\vec x}^\mathrm{T}\right] - \mathrm{E}_p\left[{\vec x}{\vec \mu_2}^\mathrm{T}\right] - \mathrm{E}_p\left[{\vec \mu_2}{\vec x}^\mathrm{T}\right] + \mathrm{E}_p\left[{\vec \mu_2}{\vec \mu_2}^\mathrm{T}\right]\right) \right\}\\
&=&\mathrm{tr}\left\{\Sigma_2^{-1} \left(\mathrm{E}_p\left[{\vec x}{\vec x}^\mathrm{T}\right] - 2\mathrm{E}_p\left[{\vec x}{\vec \mu_2}^\mathrm{T}\right] + \mathrm{E}_p\left[{\vec \mu_2}{\vec \mu_2}^\mathrm{T}\right]\right) \right\}
\end{eqnarray*}
$$
上の式の最後でトレース内で転置をとっても等しいという性質\(\mathrm{tr}\left\{{\vec \mu_2}{\vec x}^\mathrm{T}\right\}=\mathrm{tr}\left\{\left({\vec \mu_2}{\vec x}^\mathrm{T}\right)^\mathrm{T}\right\}=\mathrm{tr}\left\{{\vec x}{\vec \mu_2}^\mathrm{T}\right\}\)を用いた


ここで共分散行列の定義\(\Sigma_1=\mathrm{E}_p\left[{({\vec x}-{\vec \mu_1})}{({\vec x}-{\vec \mu_1})}^\mathrm{T}\right]=\mathrm{E}_p\left[{\vec x}{\vec x}^\mathrm{T}\right]-\mathrm{E}_p\left[{\vec x}\right]\mathrm{E}_p\left[{\vec x}^\mathrm{T}\right]\)を用いて

$$
\begin{eqnarray*}
\mathrm{E}_p\left[({\vec x}-{\vec \mu_2})^\mathrm{T} \Sigma_2 ({\vec x} -{\vec \mu_2})\right]
&=&\mathrm{tr}\left\{\Sigma_2^{-1} \left(\mathrm{E}_p\left[{\vec x}{\vec x}^\mathrm{T}\right] - 2\mathrm{E}_p\left[{\vec x}{\vec \mu_2}^\mathrm{T}\right] + \mathrm{E}_p\left[{\vec \mu_2}{\vec \mu_2}^\mathrm{T}\right]\right) \right\}\\
&=&\mathrm{tr}\left\{\Sigma_2^{-1} \left(\left(\Sigma_1 + {\vec \mu_1}{\vec \mu_1}^\mathrm{T} \right) - 2{\vec \mu_1}{\vec \mu_2}^\mathrm{T} + {\vec \mu_2}{\vec \mu_2}^\mathrm{T}\right) \right\}\\
&=&\mathrm{tr}\left\{\Sigma_2^{-1} \left(\Sigma_1 + ({\vec \mu_1} - {\vec \mu_2})({\vec \mu_1} - {\vec \mu_2})^\mathrm{T}\right) \right\}\\
&=&\mathrm{tr}\left\{\Sigma_2^{-1}\Sigma_1\right\} + ({\vec \mu_1} - {\vec \mu_2})^\mathrm{T} \Sigma_2^{-1} ({\vec \mu_1} - {\vec \mu_2})
\end{eqnarray*}
$$
次に第3項についても同様に計算する
ただし\(\mathrm{E}_p\left[{({\vec x}-{\vec \mu_1})}{({\vec x}-{\vec \mu_1})}^\mathrm{T}\right]\)は共分散行列の定義そのものである
$$
\begin{eqnarray*}
\mathrm{E}_p\left[({\vec x}-{\vec \mu_1})^\mathrm{T} \Sigma_1^{-1} ({\vec x} -{\vec \mu_1})\right]
&=&\mathrm{E}_p\left[\mathrm{tr}\left\{\Sigma_1^{-1}({\vec x}-{\vec \mu_1}) ({\vec x} -{\vec \mu_1})^\mathrm{T} \right\}\right]\\
&=&\mathrm{tr}\left\{\Sigma_1^{-1} \mathrm{E}_p\left[({\vec x}-{\vec \mu_1}) ({\vec x} -{\vec \mu_1})^\mathrm{T}\right] \right\}\\
&=&\mathrm{tr}\left\{\Sigma_1^{-1} \Sigma_1\right\}\\
&=&\mathrm{tr}\left\{I\right\}\\
&=&d
\end{eqnarray*}
$$
以上をまとめると以下のようになる
$$
\begin{eqnarray*}
D_{\mathrm{KL}}(P\|Q)
&=& \mathrm{E}_p\left[\frac{1}{2}\log \frac{|\Sigma_2|}{|\Sigma_1|}\right]\\
&& + \mathrm{E}_p\left[\frac{1}{2}({\vec x}-{\vec \mu_2})^\mathrm{T} \Sigma_2^{-1} ({\vec x} -{\vec \mu_2})\right]\\
&& - \mathrm{E}_p\left[\frac{1}{2}({\vec x}-{\vec \mu_1})^\mathrm{T} \Sigma_1^{-1} ({\vec x} -{\vec \mu_1})\right]\\
&=& \frac{1}{2}\left[\log \frac{|\Sigma_2|}{|\Sigma_1|} + \mathrm{tr}\left\{\Sigma_2^{-1}\Sigma_1\right\} + ({\vec \mu_1} - {\vec \mu_2})^\mathrm{T} \Sigma_2^{-1} ({\vec \mu_1} - {\vec \mu_2}) -d\right]
\end{eqnarray*}
$$

まとめ

というわけで正規分布間のKLダイバージェンスが導出できた
上を読めばわかるように結構手間がかかりました

以下のように1次元と\(d\)次元それぞれの正規分布のKLダイバージェンスを並べて見比べると、式としては同じ形をしているのがわかる

1次元の正規分布のKLダイバージェンスを見比べやすいように変形したもの
$$
\begin{eqnarray*}
D_{\mathrm{KL}}(P\|Q) &=& \frac{1}{2}\left[\log \frac{\sigma_2^2}{\sigma_1^2} + \frac{\sigma_1^2}{\sigma^2_2} + \frac{(\mu_1 - \mu_2)^2}{\sigma^2_2} - 1 \right]
\end{eqnarray*}
$$
\(d\)次元の多変量正規分布のKLダイバージェンス
$$
\begin{eqnarray*}
D_{\mathrm{KL}}(P\|Q) &=& \frac{1}{2}\left[\log \frac{|\Sigma_2|}{|\Sigma_1|} + \mathrm{tr}\left\{\Sigma_2^{-1}\Sigma_1\right\} + ({\vec \mu_1} - {\vec \mu_2})^\mathrm{T} \Sigma_2^{-1} ({\vec \mu_1} - {\vec \mu_2}) -d\right]
\end{eqnarray*}
$$

参考

共分散行列の二次形式の期待値とかは上でやったようにがんばって計算しないでもThe Matrix Cookbook(PDF)の8.2章に公式として書いてあったりします
The Matrix Cookbook(PDF)はいろんな行列の公式がまとまっていてわかりやすいです