Hierechical Dirichlet Process(HDP, 階層ディリクレ過程) を実装するのに必要な式を導出しつつ、実装してみるお話。
参照するのはこちらの論文。
- [Y.W.Teh, M.I.Jordan, M.J.Beal & D.M.Blei. JASA2006] Hierarchical Dirichlet Processes
しかし全部拾っていくのは大変なので、ちょびっとずつ小分けに、かつ他の方がブログとかで書いていてくれそうなところ(ディリクレ過程とか、中華料理店フランチャイズとか)はまるっと飛ばして、実装に必要な定式化&導出にしぼってまとめていくつもり。*1
とりあえず syou6162 さんや nokuno さんのこの辺の記事とかご参考。
- ディリクレ過程とディリクレ過程混合モデル - yasuhisa's blog
- Introduction to Dirichlet Process and its Applications - yasuhisa's blog
- ノンパラベイズのあれこれ - yasuhisa's blog
- Hierarchical Dirichlet Processに関するメモ - yasuhisa's blog
- http://d.hatena.ne.jp/nokuno/20090328/1238320021
- http://d.hatena.ne.jp/nokuno/20090329/1238341173
- 独断と偏見によるノンパラ入門 - Mi manca qualche giovedi`?
HDP 自体は単なるノンパラベイズな分布なので、なにがしかのアプリケーションの中で実装することになる。ここでは、LDA のトピック分布を HDP にした HDP-LDA を題材としよう。
通常の LDA と比較した HDP-LDA のメリットは、トピック数をあらかじめ決めなくても良いこと(学習により適切なトピック数が自動的に決まる)。また LDA の一般的な定式化で現れる、トピックのディリクレ分布のハイパーパラメータαにあたるパラメータも階層化(確率変数化)され、自動的に決定(しかも非対称)してくれるので、perplexity などの指標が改善されることが期待できる。
では LDA (Smoothed LDA) と HDP-LDA のモデルを見てみよう。
実はどちらも同じグラフィカルモデルで表すことができる(ハイパーパラメータは省略)。
グラフィカルモデルは同じだが、生成過程が異なる。
まず HDP-LDA の生成過程は参照論文に載っているとおり。
- G_0 〜 DP(γ,H)
- G_j 〜 DP(α_0,G_0)
- θ_ji 〜 G_j
- x_ji 〜 F(θ_ji)
H は base measure、F は与えられた θ_ji によって決まる x_ji の分布。HDP を適用するアプリケーションに応じて、これらを適切なものに設定することになる。
トピック言語モデルの場合は、H として対称なディリクレ分布 Dir(β) を取る。これは単語多項分布の事前分布で、LDA の一般的な定式化に出てくる Dir(β) に相当する。
また、この構成において θ_ji は H の台(V-1 次元の単体, V は語彙数)上の点であり、それが語彙の多項分布のパラメータとなっているので、 F(θ_ji) としてはその多項分布を取る。
LDA の生成過程は参照論文に載っていないが、以下のような構成になっているはず*2。H と F は HDP-LDA と同様。
- G_j 〜 Dir(αG_0)
- θ_ji 〜 G_j
- x_ji 〜 F(θ_ji)
つまり LDA と HDP-LDA の実質的な違いは G_0 の生成にある。
LDA では、H からサンプリングした K 個の {φ_k} を台とする対称な measure を G_0 としている。
一方の HDP-LDA では、G_0 は DP(γ,H) からサンプリングする。これは H を base measure とするディリクレ過程であり、つまり G_0 は、H からサンプリングした無限個の点を台とする非対称な(指数オーダーで重みが減衰する) measure である。
もう少し柔らかく説明してみる。
割り振られたトピックを区別するのに k=1, …, K, … というインデックスを与えるのではなく、φ_1, …, φ_K, … という、とある空間内にある(それぞれ異なる)点を使っているというのが今回のミソ。
その点は V 次元線形空間の点 φ_k=(φ_k1, ……, φ_kV) で、φ_kv≧0, Σ_v φ_kv=1 を満たしている。つまり、V 次の多項分布を定めることができる点であり、トピック φ_k に対して、トピック-単語分布をそのまま φ_k 自身で与えるという、こう見えてなかなか効率的な構成になっている。
ここまでは LDA でも HDP-LDA でも一緒。違いは、そういう φ_k という点をぴったり K 個しか考えないのか、いくつでも考えられるようにしておくのか、という部分であり、それが G_0 の構成に現れている、というわけだ。
つまり、トピックの生成に「ディリクレ分布を使って定数個」か、「ディリクレ過程を使って可変個」か、が LDA と HDP-LDA のほぼ唯一の違い、と言えばすっきりわかりやすい……と思うのは気のせいだろうか(苦笑)。
ちなみに、Latent Dirichlet Allocations(LDA) の実装について - Mi manca qualche giovedi`? で引用したような、よく見る LDA のグラフィカルモデルや生成過程とはちょっと違っているが、ちゃんと等価なモデルである。pLSA をベイズ化したものとして LDA を構成した場合も、また別のグラフィカルモデルが得られたりする。余談だけどね。
これらのモデルに対して、その推論には参照論文にあるとおり Collapsed Gibbs sampling を使うのだが、その更新式の導出は次回以降。
*1:中華料理店フランチャイズは余裕があったらなんか書くかも
*2:これを論文に書いていてくれれば、HDPがわかんないと騒いでいたら、実はLDAがわかってなかった!? でござるの巻 - Togetter のような無理解を披露しなくて良かったはず……と言い訳してみるw