読者です 読者をやめる 読者になる 読者になる

#10 Sharing clusters among related groups: Hierarchical Dirichlet processes

論文100本ノック HDP NIPS

Hierarchical Dirichlet processes(HDP)の元論文。Group化されたようなデータに対してDPをそのまま使うとグループ間での特徴を共有できないので、どうにかしたい(ノンパラのいいところはそのままにしつつ)。テキストで考えると分かりやすいので、今後はグループのことをdocument、それより大きい単位のをコーパスで考えることにする。

HDPでの生成過程は以下のようになっている。

  • G_0 | \gamma, H \sim DP(\gamma, H)
  • G_j | \alpha, G_0 \sim DP(\alpha, G_0)
  • \phi_{ji} | G_j \sim G_j
  • x_{ji} | \phi_{ji} \sim F(\phi_{ji})

ここで重要なのは「H、G_0G_jがそれぞれどういう分布なのか?」というのを理解すること。

  • Hは連続な分布(大抵の場合は事前知識がないので平坦なものを考えることが多い。連続データに対して考えるならNormal-Inverse-Wishart分布のようなものだし、離散ならDirichlet分布がHとなることが多いだろう)
  • G_0G_0 = \sum_{k=1}^\infty \beta_k \delta_{\theta_k}と書き表わすことができるという事実が知られており、これからG_0はHと同じ定義域を持つ離散的な分布となる、ということが分かる
    • パラメータの空間に棒がわーっと立っているのだが、その棒の高さ\beta_kはstick breaking processで決まる。高いほうが生成される確率が高い

G_jG_j | \alpha, G_0 \sim DP(\alpha, G_0)となっているが、これはどういうことであろうか?DPから生成されるのでG_jはパラメータの空間で離散的な分布である、ということが分かる。では一体どういう離散的な分布なのか?G_0をベースとして生成してくるので、生成されるとしたらG_0で棒が立っているところからである。しかし、これの棒の長さが違ってくる(この長さはstick breaking processというもので記述することができる)。

ちょっとまとめる。Hは(なんとなくな)コーパスレベルでの(単語の多項分布に関する)パラメータについての事前知識(事前分布)である。これを元に「theやIとかはどれにでも出てきやすいだろjk」といったものが反映されているような分布G_0がコーパスレベルで1つ生成される。G_0は各パラメータがどれだけ生成されやすいかを表わす分布なので

  • theやIとかは出てきやすいだろjk => 確率0.4
  • aやmeとかは出てきやすいだろjk => 確率0.5
  • HDPやDPMとかは出てきやすいだろjk => 確率0.00000001
  • ...

といったものを表わしている(パラメータ自体を確率変数と見なし、それに確率を付与しているということ)。若干混乱しそうになるが、各パラメータは(語彙の次元だけある)有限なものであり、そのパラメータの取り得るバリエーションが加算無限個あって、それに対してstick breaking processでそれぞれ確率が付与されているといったイメージである。どれくらい元のBase Measure Hに似ているかは\gammaによって制御される。単語の場合だと高次元空間での単体の分布になって分かりづらいかもしれないので、1次元の正規分布の例で考えると分かりやすいかもしれない*1。以上より、コーパスレベルで「「どういう単語が出やすいのかを表わすパラメータ」がどれくらい出やすいのか」を表わすG_0が生成される、ということ(分かりにくいが落ち付いて考えれば分かるはず)。

このG_0を元にしてdocument levelのことについて考える。document levelではG_j | \alpha, G_0 \sim DP(\alpha, G_0)となっているが、これは

  • theやIとかは出てきやすいだろjk => 確率0.4
  • aやmeとかは出てきやすいだろjk => 確率0.5
  • HDPやDPMとかは出てきやすいだろjk => 確率0.00000001
  • ...

から同じような分布をサンプリングしてくるのだが、このdocumentがたまたまNIPSのdocumentだった場合

  • theやIとかは出てきやすいだろjk => 確率0.3
  • aやmeとかは出てきやすいだろjk => 確率0.4
  • HDPやDPMとかは出てきやすいだろjk => 確率0.01
  • ...

という風なものがサンプリングされるというイメージである。G_jG_0を元にしてできているので、G_jG_0似ているのだが若干違う。どれくらい違うかは\alphaによって制御される。また、最初はよく分かっていなかったが、G_jG_0を元にしてできているので、例えばG_0にはなかったような

  • XXXやYYYとかは出てきやすいだろjk => 確率0.3

という棒が立たないことに注意したい(この辺が"The atoms \phi_k are shared among the Multiple DPs, yielding the desired sharing of atoms among groups"とかってところだろうか)。

  1. documentごとにG_jは生成されるので、documentごとの特徴をしっかり捕えることができる
  2. コーパスレベルでG_0を共有しているので、文書にはそもそもどういう単語が出てきやすいのかを共有することができる

という2点がHDPの強いところ。これだけだとLDAと変わらないじゃないかという気がするが、コーパスレベルで

  • theやIとかは出てきやすいだろjk => 確率0.4
  • aやmeとかは出てきやすいだろjk => 確率0.5
  • HDPやDPMとかは出てきやすいだろjk => 確率0.00000001
  • ...

といったもののバリエーションやdocument levelで

  • theやIとかは出てきやすいだろjk => 確率0.3
  • aやmeとかは出てきやすいだろjk => 確率0.4
  • HDPやDPMとかは出てきやすいだろjk => 確率0.01
  • ...

といったもののバリエーションの数がどれくらいがふさわしいかをデータによって語らせることができる、というのがHDP-LDAの大きな特徴である。

CRPをベースにした自分の説明はHierarchical Dirichlet Processに関するメモ - Seeking for my unique color.に書いたし、Erik Sudderthさんの博士論文のSection 2.5の図とかが今見るとかなり分かりやすいなと思ったので参考になるはず。

@INPROCEEDINGS{Teh05sharingclusters,
    author = {Yee Whye Teh and Michael I. Jordan and Matthew J. Beal and David M. Blei},
    title = {Sharing clusters among related groups: Hierarchical Dirichlet processes},
    booktitle = {In Advances in Neural Information Processing Systems},
    year = {2005},
    pages = {1385--1392},
    publisher = {MIT Press}
}