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

しばらく間が空いたけど、今回も "Hierarchical Dirichlet Processes"(Teh+ JASA2006) を読んでいく。
この論文の5章に HDP の更新式が、6.1 章では HDP-LDA について書かれているのだが、最初と途中と最後が書かれていないので、どうやって導出したのかも、HDP-LDA の実装に直接必要な最終的な式も、自力で考えないといけなくて、エンジニア涙目。

今回見ていくのは 5章冒頭から 5.1章 Posterior sampling in the Chinese restaurant franchise の範囲。
HDP では DP が階層化されているので、Chinese restaurant process に従う確率変数は、客 x_ji が座っているテーブル t_ji と、テーブル t に出されている料理 k_jt の2つある。
というわけでこれらを交互にサンプリングするための全条件付き分布(full conditional)を導出してあげることになる。

以降、事後分布を導出していくが、論文では省略されている $\boldsymbol{x}$ あるいは $\boldsymbol{x}^{-ji}$ を given の項に適宜補っている。つーか、無いとわからん(だいぶ悩んだ)。

まず 5章に出てくる (30) 式。

$\displaystyle f_k^{-x_{ji}}(x_{ji}) = \frac{\int f(x_{ji}|\phi_k)\prod_{j'i'\neq ji,z_{j'i'}=k}f(x_{j'i'}|\phi_k)h(\phi_k)d\phi_k}{\int \prod_{j'i'\neq ji,z_{j'i'}=k}f(x_{j'i'}|\phi_k)h(\phi_k)d\phi_k}$ 　　(30)

なぜか文章だけで(しかも微妙に曖昧に)書かれているが、実はこれは $p(x_{ji}|\boldsymbol{t},\boldsymbol{k},\boldsymbol{x}^{-ji})$ (ただし $k=k_{jt_{ji}}$ )である。
つまり $\boldsymbol{\phi}=(\phi_1,\phi_2,\cdots)$ とすると、

$\displaystyle p(x_{ji}|\boldsymbol{t},\boldsymbol{k},\boldsymbol{x}^{-ji})=\frac{p(x_{ji},\boldsymbol{x}^{-ji}|\boldsymbol{t},\boldsymbol{k})}{p(\boldsymbol{x}^{-ji}|\boldsymbol{t},\boldsymbol{k})}$
$\displaystyle =\frac{\int p(x_{ji},\boldsymbol{x}^{-ji},\boldsymbol{\phi}|\boldsymbol{t},\boldsymbol{k})d\boldsymbol{\phi}}{\int p(\boldsymbol{x}^{-ji},\boldsymbol{\phi}|\boldsymbol{t},\boldsymbol{k})d\boldsymbol{\phi}}$
$\displaystyle =\frac{\int p(x_{ji},\boldsymbol{x}^{-ji}|\boldsymbol{t},\boldsymbol{k},\boldsymbol{\phi})p(\boldsymbol{\phi})d\boldsymbol{\phi}}{\int p(\boldsymbol{x}^{-ji}|\boldsymbol{t},\boldsymbol{k},\boldsymbol{\phi})p(\boldsymbol{\phi})d\boldsymbol{\phi}}$

ここで $\phi_1,\phi_2,\cdots$ は i.i.d. ゆえ、分子分母とも $\phi_1,\phi_2,\cdots$ ごとの積に分解できる。また x_ji らも t, k を止めれば条件付き独立かつそのトピックにひもづけられた φ_k のみに依存するので、積に分解できる。
そこで $k=k_{jt_{ji}}$ と書くことにすると、

$=\displaystyle \frac{\int p(x_{ji}|\phi_k)\prod_{h}\left(\prod_{x_{mn}:(m,n)\neq (j,i), k_{mt_{mn}}=h}p(x_{mn}|\phi_{h})\right)p(\phi_{h})d\phi_{h}}{\int \prod_{h}\left(\prod_{x_{mn}:(m,n)\neq (j,i), k_{mt_{mn}}=h}p(x_{mn}|\phi_{h})\right)p(\phi_{h})d\phi_{h}}$

このとき、h=k 以外の因子は分子分母に共通のためキャンセルして、残ったものが $f_k^{-x_{ji}}(x_{ji})$ となる。

(32) 式は t の全条件付き事後分布。

$p(t_{ji}=t|\boldsymbol{t}^{-ji},\boldsymbol{k})\propto\begin{cases}n_{jt}^{-ji}f_{k_{jt}}^{-x_{ji}}(x_{ji})&\text{if t previously used,}\\\alpha_0p(x_{ji}|\boldsymbol{t}^{-ji},t_{ji}=t^{\text{new}},\boldsymbol{k})\hspace{5ex}&\text{if}\; t=t^{\text{new}}\end{cases}$ 　　(32)

これも導出してみよう。まずは t_ji=t、つまり既存のテーブルを draw する確率。
おっと、ここで given に省略されていた $\boldsymbol{x}$ を補っておこう。でないとこの変形が出てこない。

$\displaystyle p(t_{ji}=t|\boldsymbol{t}^{-ji},\boldsymbol{k},\boldsymbol{x})=\frac{p(x_{ji}|t_{ji}=t,\boldsymbol{t}^{-ji},\boldsymbol{k},\boldsymbol{x}^{-ji})p(t_{ji}=t|\boldsymbol{t}^{-ji},\boldsymbol{k},\boldsymbol{x}^{-ji})}{p(x_{ji}|\boldsymbol{t}^{-ji},\boldsymbol{k},\boldsymbol{x}^{-ji})}$

ここで分子の第1因子 $p(x_{ji}|t_{ji}=t,\boldsymbol{t}^{-ji},\boldsymbol{k},\boldsymbol{x}^{-ji})$ は先ほど導出した $f_k^{-x_{ji}}(x_{ji})$ である。第2因子 $p(t_{ji}=t|\boldsymbol{t}^{-ji},\boldsymbol{k},\boldsymbol{x}^{-ji})$ は Chinese restaurant franchise より $n_{jt}^{-ji}$ に比例することがわかる(論文の (24) 式参照)。

次に t_ji=t^new、つまり新規テーブルを draw する確率。

$\displaystyle p(t_{ji}=t^{\text{new}}|\boldsymbol{t}^{-ji},\boldsymbol{k},\boldsymbol{x})=\frac{p(x_{ji}|t_{ji}=t^{\text{new}},\boldsymbol{t}^{-ji},\boldsymbol{k},\boldsymbol{x}^{-ji})p(t_{ji}=t^{\text{new}}|\boldsymbol{t}^{-ji},\boldsymbol{k},\boldsymbol{x}^{-ji})}{p(x_{ji}|\boldsymbol{t}^{-ji},\boldsymbol{k},\boldsymbol{x}^{-ji})}$

分子の第1因子は (31) 式にて展開されている。これは後で計算することにしよう。
分子の第2因子は、既存テーブルの場合と同様に (24) 式から α_0 に比例することがわかる。
分母はどちらの場合にも共通ゆえ、それらを比例定数に押し込めてしまえば (32) 式が得られる。

次に、さっき出てきた (31) 式もまじめに計算してみよう。

$p(x_{ji}|\boldsymbol{t}^{-ji},t_{ji}=t^{\text{new}},\boldsymbol{k})=\sum_{k=1}^K\frac{m_{\cdot k}}{m_{\cdot\cdot}+\gamma}f_k^{-x_{ji}}(x_{ji})+\frac{\gamma}{m_{\cdot\cdot}+\gamma}f_{k^{\text{new}}}^{-x_{ji}}(x_{ji})$ 　　(31)

t^new ということは、新しいテーブルに割り当てられる料理 k を決めなくては、 x_ji の確率を求めることが出来ないが、(31) 式の左辺には現れていない。ということは次のように周辺化される前の状態にして考える必要がある。

$p(x_{ji}|\boldsymbol{t}^{-ji},t_{ji}=t^{\text{new}},\boldsymbol{k},\boldsymbol{x}^{-ji})=\sum_k p(x_{ji}, k_{jt^{\text{new}}}=k|\boldsymbol{t}^{-ji},t_{ji}=t^{\text{new}},\boldsymbol{k},\boldsymbol{x}^{-ji})$

同じく given に $\boldsymbol{x}^{-ji}$ を補っている。
ここで k はすでに割り振られているテーブルがある料理 k=1,……,K だけではなく、新規料理 k^new も動くので、

$=\sum_{k=1}^K p(x_{ji}, k_{jt^{\text{new}}}=k|\boldsymbol{t}^{-ji},t_{ji}=t^{\text{new}},\boldsymbol{k},\boldsymbol{x}^{-ji}) + p(x_{ji}, k_{jt^{\text{new}}}=k^{\text{new}}|\boldsymbol{t}^{-ji},t_{ji}=t^{\text{new}},\boldsymbol{k},\boldsymbol{x}^{-ji})$
$=\sum_{k=1}^K p(x_{ji}|k_{jt^{\text{new}}}=k,\boldsymbol{t}^{-ji},t_{ji}=t^{\text{new}},\boldsymbol{k},\boldsymbol{x}^{-ji})p(k_{jt^{\text{new}}}=k|\boldsymbol{t}^{-ji},t_{ji}=t^{\text{new}},\boldsymbol{k},\boldsymbol{x}^{-ji})\\\;\;+p(x_{ji}|k_{jt^{\text{new}}}=k^{\text{new}},\boldsymbol{t}^{-ji},t_{ji}=t^{\text{new}},\boldsymbol{k},\boldsymbol{x}^{-ji})p(k_{jt^{\text{new}}}=k^{\text{new}}|\boldsymbol{t}^{-ji},t_{ji}=t^{\text{new}},\boldsymbol{k},\boldsymbol{x}^{-ji})$
$=\sum_{k=1}^K f_k^{-x_{ji}}(x_{ji})\frac{m_{\cdot k}}{m_{\cdot\cdot}+\gamma} + p(x_{ji}|k_{jt^{\text{new}}}=k^{\text{new}},\boldsymbol{t}^{-ji},t_{ji}=t^{\text{new}},\boldsymbol{k},\boldsymbol{x}^{-ji})\frac{\gamma}{m_{\cdot\cdot}+\gamma}$

p(k|・) たちは、料理 k が割り当てられているテーブル数 m_jk を使って、論文の (25) 式に示されている確率がそれぞれ割り当てられることになる。
ここで、 $p(x_{ji}|k_{jt^{\text{new}}}=k^{\text{new}},\boldsymbol{t}^{-ji},t_{ji}=t^{\text{new}},\boldsymbol{k},\boldsymbol{x}^{-ji})=f_{k^{\text{new}}}^{-x_{ji}}(x_{ji})$ とおけば、(31) 式が得られる。