Contrastive Divergenceについてお勉強してみた

今週はMLど素人でありながら初めてIBISに参加し，様々な刺激を受けて大変良い1週間でした．いつもtwitter上でご活躍を拝見している方々とリアルに会ったり，遠目に眺めてみたり，話をしたりできたので良かったです．

刺激を受けたご講演・発表は数多くあったのですが，Salakhutdinov先生（いまだに発音がわからない）の基調講演も面白い内容でした．Deep Learningが実装できるような計算機環境やデータを自分が準備できそうにないので，Deep Learning自体の進展については遠巻きにながめているしかないのですが，Restricted Boltzmann Machines (RBM)周辺の話は面白いなぁと素直に感じた次第です．現在，学生さんと自分の研究でGaussian Markov Random Fieldの欠損値推定をノリで行っているのですが，IBISに参加してRBM周辺のお勉強をしなくては！と思い立ち，Salakhutdinov, Mnih and Hinton (2007)*1を読み始めました．そこで，Contrastive Divergenceが重要な概念だなぁと気付き，結局Hinton (2002) *2を読むことにしました．ということで，自分の理解のために，とりあえずまとめてみます．

PoEモデルと最尤推定

次のようなモデルを考えます．
$p({\bf d|\theta}_1,...,{\bf \theta}_n) = \frac{\prod_m f_m ({\bf d|\theta}_m)}{\sum_c\prod_m f_m ({\bf c|\theta}_m)}$
これはProducts of Experts (PoE)モデルと呼ばれており，高次元空間では非効率になりがちな混合モデルに対して，Expertsと呼ばれる個々の複雑なモデルの積として表現することでパワフルなモデルになっています．このPoEを真面目に最尤推定することを考えると，次のようになります．
$\frac{\partial \log p({\bf d | \theta}_1,...,{\bf \theta}_n)}{\partial {\bf \theta}_m} = \frac{\partial \log f_m ({\bf d|}\theta_m)}{\partial {\bf \theta}_m} -$ $\sum\limits_{\bf c} p({\bf c | \theta}_1,...,{\bf \theta}_n) \frac{\partial \log f_m ({\bf c|\theta}_m)}{\partial {\bf \theta}_m}$ 　　　(a)
ここで，第2項はfantasy dataにおける対数尤度の偏微分の期待値となっており，これに真面目に対応するのは大変です．一つにはGibbs Samplingが考えられますが，計算的に大変なだけでなくfantasy dataの分散が大きいという問題があります．

KL DivergenceとContrastive Divergence

このような得られたデータに対する対数尤度を最大化することはデータ分布 $P^0$ と観測変数の均衡分布 $P_{\theta}^\infty$ の間のKL Divergenceを最小化することと等価であることはよく知られています．そこで，KL Divergenceを考えると，次式で表すことができます．
$P^0||P_{\theta}^\infty = \sum\limits_{{\bf d}} P^0({\bf d}) \log P^0 ({\bf d}) - \sum\limits_{{\bf d}}P^0({\bf d})\log P_{\theta}^\infty ({\bf d})$
　　　　 $= -H(P^0) - \left< \log P_{\theta}^\infty \right>_{P^0}$
ここで，<>はある分布上の期待値を表します．H(P^0)はデータ分布上のエントロピーであり，モデルのパラメータに依存しないので，最適化とは無関係です．最適化のために第2項の偏微分を考えるわけですが，データ分布上で平均化すると，式(a)は次のように書き直すことができます．
$\left< \frac{\partial \log P_{\theta}^{\infty} ({\bf D})}{\partial {\bf \theta}_m}\right>_{P^0} = \left< \frac{\partial \log f_{\theta_m}}{\partial {\bf \theta}_m}\right>_{P^0}$ $- \left< \frac{\partial \log f_{\theta_m}}{\partial {\bf \theta}_m}\right>_{P_{\theta}^\infty}$

ここで $P^1$ は1回のfull stepのGibbs Samplingから生成されるデータベクトルの分布とすると，この式の右辺における $P_\theta^\infty$ 上での扱いづらい期待値は次のようにキャンセルアウトできます．
$- \frac{\partial}{\partial {\bf \theta}_m} (P^0||P_\theta^\infty - P^1_\theta ||P_\theta^\infty) = \left< \frac{\partial \log f_{\theta_m}}{\partial {\bf \theta}_m}\right>_{P^0} -$ $\left< \frac{\partial \log f_{\theta_m}}{\partial {\bf \theta}_m}\right>_{P^1_\theta}$ $+ \frac{\partial P_\theta^1}{\partial {\bf \theta}_m}\frac{\partial (P^1_\theta||P_\theta^\infty)}{\partial P^1_\theta}$ 　　　　(b)
PoEモデルでは各expertは扱いやすいモデルが選ばれているため，式(b)の第1項，第2項は計算することができます．第3項は ${\bf \theta}_m$ の変化によって起こる1 stepの分布の変化が $P^1_\theta||P_\theta^\infty$ に与える影響を表しています．これを計算するのは難しいのですが，これは他の2項の影響と比べると小さいので無視することができます．そのため，expertのパラメータはContrastive Divergenceの近似的な微分値に比例する形で調節できます．
$\Delta {\bf \theta}_m \prop \left< \frac{\partial \log f_{\theta_m}}{\partial {\bf \theta}_m}\right>_{P^0} - \left< \frac{\partial \log f_{\theta_m}}{\partial {\bf \theta}_m} \right>_{P^1_\theta}$ (c)

また，式(c)は学習アルゴリズムにおける新たなjustificationを与えています．高次元データセットにおいても，多くの場合，非常に低次元のなめらかな曲がった多様体上にデータはほとんどペタっとなっていたり，近くに集まっていたりします．なので，多様体上の点から始めることで，実用上うまくいきます（いくそうです）．

Contrastive Divergenceの解釈

この変形のありがたいところは，式(a)の均衡分布からのサンプリングによる煩雑な計算を避け， $P^0||P_\theta^\infty$ を最小化するのではなく， $P^0||P_\theta^\infty$ と $P^1||P_\theta^\infty$ の差を最小化する問題として捉えなおす点です．

直観的には均衡分布へのマルコフ連鎖を実行し，initial derivativeとfinal derivativeを比較することの代わりに，1回のfull step チェインを実行して，最初のステップで初期分布からうろうろするチェインの傾向を小さくするようにパラメータを更新するイメージです．ここらへんは自分もまだなんとなくしか理解していないので，この直観的なイメージがあっているのかわかりませんが…．ただ， $P^1_\theta$ は $P^0$ よりも均衡分布に対して1 step近い分布なので， $P^0||P_\theta^\infty$ は $P^1_{\theta}||P_\theta^\infty$ よりも大きいことが保証されており，このContrastive Divergenceは決して負にならないという性質をもっています．

おわりに

1回のfull step Gibbs Samplingで済むというのがContrastive Divergenceの1番のメリットだと思うので，そのあたりを意識すると，最初に読もうとしていたSalakhutdinov, Mnih and Hinton (2007)も読みやすくなるのでは，と思って次はそっちを読みます．まだ納得するほど理解が進んでいないので，Hinton(2002)に書いてある簡単な例なども手を動かしながら理解したいと思います．

そして，ここまで読んだ人へのご褒美ですが，自分が書いた上よりもわかりやすく書いてある持橋さんの資料を見つけましたので，関心がある人は是非ご覧くださいｗ

*1:Salakhutdinov, Mnih and Hinton, Restricted Boltzmann machines for collaborative filtering, ICML, 2007.

*2:Hinton, Training products of experts by minimizing contrastive divergence, Neural Computation, 14, 1711-1800.