階層ディリクレ過程を実装してみる (2) HDP-LDA の更新式を導出・前編

階層ディリクレ過程を実装してみる (1) HDP-LDA と LDA のモデルを比較 - Mi manca qualche giovedi`? の続き。
今回も [Teh+ 2006] に基づいて、Chinese Restaurant Franchise(中華料理店フランチャイズ, CRF) の枠組みで Hierarchical Dirichlet Process(階層ディリクレ過程, HDP) の Collapsed Gibbs sampling 推論を行う場合の更新式を導出していく。

まず今回は一般の HDP を CRF に落とすところ。次回はそこから full conditional を導出([Teh+ 2006] にある $f_k^{-x_{ji}}(x_{ji})$ および t や k の事後分布を導出)、そして次々回あたりで、それらの更新式を HDP-LDA に当てはめた場合(つまり前回記事の base measure H と emission? F(φ) に具体的な分布を適用する場合)をやっつけるイメージ。

まず、上で書いたように CRF の枠組みを導入するわけだが、その理由は (Hierarchical) Dirichlet Process のままでは無限回サンプリングしなければならなくなってしまうから。CRF なら有限回で済ませられる。
本来ならここで Stick-Breaking Process とか CRF とかちゃんと説明した方がいいんだろうが、ずばっと省略して、CRF の記法の説明に入ってしまう。
ので、いきなり「客」とか「テーブル」とか「料理」とか「店」という単語が出てくるが、まあ、なんと言うか、ほんと申し訳ない(苦笑)。
ちなみに HDP-LDA の場合だと、「店＝文書」、「料理＝トピック」、「客＝単語(x_ji)」、であり、「テーブル」は客と料理を(つまり、単語とトピックを)結びつけるものというメタファー、というほど似てる気はしないが、まあそういう対応である、というひどい説明でお茶を濁しておく……。

K を「サンプリング時点での有効な(つまり少なくとも１つ以上の客やテーブルが割り当てられている)料理の個数」とし、 $\phi_1,\cdots,\phi_K \sim H$ をその K 個の料理とする。
j を店のインデックスとし、θ_ji を i 番目の客が食べている料理、ψ_jt を t 番目のテーブルに提供されている料理とする。
つまり、客 x_ji が着いているテーブルが t_ji で、テーブル t に提供されている料理が k_jt のとき、 $\theta_{ji}=\psi_{j{t_ji}}=\varphi_{k_{jt_{ji}}}$ ということである。

少々ややこしいが、要は θ_ji や ψ_jt は、最初に H からサンプリングした料理 φ_k のどれかである、ということ。
下の図で言えば、店１番の客７番はテーブル３番に着いており、料理１番を食べている(一番上の囲みの左から三番目)。
それを θ_17 = ψ_13 = φ_1 という式で表そうという考え方なわけだ。

【Teh+ 2006 より】

さて、こういう設定の元で CRF の枠組みを柔らかく言うと、「来店した客は、客の多いテーブルに着きたがる」「新規テーブルに着く可能性も若干残っている」。
数式で書くと次の通り。

$\theta_{ji}|\theta_{j1},\cdots,\theta_{j,i-1},\alpha_0,G_0 \;\sim\; \sum_{t=1}^{m_{j\cdot}}\frac{n_{jt\cdot}}{i-1+\alpha_0}\delta_{\psi_{jt}}+\frac{\alpha_0}{i-1+\alpha_0}G_0$

n_jtk は「j 番目の店の、t 番目のテーブルで、k 番目の料理を食べている客の数」、インデックスが点になったものはその周辺化というよくある記法としている。
この式では i 番目に新しく来た客がどのテーブルに着くかを示しており、先客がいる t 番目のテーブルに着く確率が $\frac{n_{jt\cdot}}{i-1+\alpha_0}$ 、客のいない新規テーブルに着く確率が $\frac{\alpha_0}{i-1+\alpha_0}$ という意味の式である。
新規テーブルに着く場合は、H から作られたディリクレ過程 G_0 からのサンプリングが行われるわけだが、それも同じように CRF に落とし込むことで、上とよく似た式が得られる。

$\psi_{jt}|\psi_{j1},\cdots,\psi_{j,t-1},\gamma,H \;\sim\; \sum_{k=1}^{K}\frac{m_{\cdot k}}{m_{\cdot\cdot}+\gamma}\delta_{\varphi_k}+\frac{\gamma}{m_{\cdot\cdot}+\gamma}H$

m_jk は「j 番目の店の、k 番目の料理が提供されているテーブルの数」で、インデックスが点は以下同文。
やはり同様に、「 k 番目の提供済みの料理」か「新規料理」がそれぞれの確率で選ばれる。新規料理の場合は base measure H から新しい料理が選ばれ、 K は１つ増やされることになる。
なお、α_0 や γ はなにがしかのハイパーパラメータであり、ここでは詳細は省略する。

どうにもややこしくてしかたないが、最初に書いたとおり、これも「ディリクレ過程のままでは、無限回サンプリングしなければならない」のを回避したいがため。
つまり、正攻法では事実上サンプリングできないディリクレ過程を、有限回の初等的な手順でサンプリングできるようにしたアルゴリズムだ、と考えれば少しは心に平安が訪れる……のかもしれない(苦笑)。

階層ディリクレ過程を実装してみる (3) HDP-LDA の更新式を導出 ( t の全条件付き分布) - Mi manca qualche giovedi`?