Type-based MCMC - murawaki の雑記

Percy Liang, Michael I. Jordan, Dan Klein: Type-based MCMC (PDF).

スライドが神。そっちを見ればやりたいことはわかる。

自分用のメモ。間違っていたら指摘してほしい。

3.3 Prior

いきなり事前分布として Dirichlet distribution ではなく Dirichlet process を設定するあたり、難易度が高い。Dirichlet distribution 版の p(z) を導出してみる。

本当はパラメータ θ は |R| 個あるけど、簡略化のために一つにする。複数のパラメータの場合は積を取ればいい。

論文の ascending factorial は表記が気持ち悪いので、普通にガンマ関数同士の割り算にしておく。

$\begin{eqnarray}p(\mathbf{z})&=&\int_{\mathbf{\theta}} p(\mathbf{z}|\mathbf{\theta})p(\mathbf{\theta})d\mathbf{\theta}\\ &=& \int_{\mathbf{\theta}}\prod_{o} \theta_o^{n_o(\mathbf{z})} \,\times\, \frac{\Gamma(\alpha_{(\cdot)})}{\prod_{o} \Gamma(\alpha_{o})}\prod_o \theta_o^{\alpha_o - 1}\,d\mathbf{\theta}\\ &=& \frac{\Gamma(\alpha_{(\cdot)})}{\prod_{o} \Gamma(\alpha_{o})} \int_{\mathbf{\theta}} \prod_o \theta_o^{\alpha_o + n_o(\mathbf{z}) - 1}\,d\mathbf{\theta}\\ &=& \frac{\Gamma(\alpha_{(\cdot)})}{\prod_{o} \Gamma(\alpha_{o})} \frac{\prod_o \Gamma(\alpha_o + n_o(\mathbf{z}))}{\Gamma(\alpha_{(\cdot)} + n_{(\cdot)}(\mathbf{z}))}\\ &=& \frac{\Gamma(\alpha_{(\cdot)})}{\Gamma(\alpha_{(\cdot)} + n_{(\cdot)}(\mathbf{z}))} \prod_o \frac{\Gamma(\alpha_o + n_o(\mathbf{z}))}{\Gamma(\alpha_o)} \end{eqnarray}$

Dirichlet process 版の $\alpha$ が $\alpha_o$ の和を取った $\alpha_{(\cdot)}$ に、 $\alpha_{o} \mu_{o}$ が $\alpha_o$ に代わる。あれっ、Dirichlet process 版は $\alpha \mu_{o}$ のような気がする。 $\alpha$ はスカラーで $\alpha_o$ なんてないように思うのだが。

ascending factorial を見ると面喰うが、少し考えて見れば、当たり前の結果。すでにいくつかのデータを観測した状態で、次の一個が入ってきたときの更新を考える。データの値に対応するカウント $n_o(\mathbf{z})$ が1増えて、 $\alpha_o + n_o(\mathbf{z})$ がかけられる。同時に、総数 $n_{(\cdot)}(\mathbf{z}))$ も1増えて、 $1 / (\alpha_{(\cdot)} + n_{(\cdot)}(\mathbf{z}))$ がかけられる。これを繰り返すわけだから、階乗が出てくるのは当然。

論文を普通に前から読み始めると、いきなり2節の式 (1) が導出できなくて涙目になったりするのだが、上の式に Dirichlet(1, 1, 1), Multi(m, m, n-1) を入れるとすぐに出てくる。

4.1 Binary Representation

$\mathbf{z}^{s:0}$ と $\mathbf{z}^{s:1}$ は基本的には z 全体を表していて、ただし s が b = 0 あるいは b = 1 に対応する状態になっている。最初勘違いして、z の中から s に関係する部分を抜き出したものだと思い込んだ。そうすると、
$\mathbf{z}^{-s} \stackrel{\mathrm{def}}{=} \mathbf{z}^{s:0} \cap \mathbf{z}^{s:1}$
が意味を成さないので気付いた。

4.2 Sampling One Site

式(4)の導出。ここで $p(\mathbf{z}^{s:b})=p(b_s=b,\mathbf{b}\setminus\mathbf{b}_s)$ 。

$\begin{eqnarray}p(b_s=b|\mathbf{b}\setminus\mathbf{b}_s) &=& \frac{p(b_s=b,\mathbf{b}\setminus\mathbf{b}_s)}{p(\mathbf{b}\setminus\mathbf{b}_s)} \\ &\propto& p(b_s=b,\mathbf{b}\setminus\mathbf{b}_s) \\ &=& \prod_{r \in R}\frac{\prod_o (\alpha_{r}\mu_{ro})^{(n_{ro}^{-s}+\triangle n_{r\cdot}^{s:b})}}{\alpha_r^{(n_{r\cdot}^{-s}+\triangle n_{r\cdot}^{s:b})}} \\ &=& \prod_{r \in R}\frac{\prod_o (\alpha_{r}\mu_{ro})^{(n_{ro}^{-s})} (\alpha_{r}\mu_{ro} + n_{ro}^{-s})^{(\triangle n_{r\cdot}^{s:b})}}{\alpha_r^{(n_{r\cdot}^{-s})} (\alpha_r + n_{r\cdot}^{-s})^{(\triangle n_{r\cdot}^{s:b})}} \\ &\propto& \prod_{r \in R}\frac{(\alpha_{r}\mu_{ro} + n_{ro}^{-s})^{(\triangle n_{r\cdot}^{s:b})}}{(\alpha_r + n_{r\cdot}^{-s})^{(\triangle n_{r\cdot}^{s:b})}} \\ \end{eqnarray}$

4.3 Sampling Multiple Sites

式 (9) の ascending factorial の scope が変。内側の分母は $(\alpha_r + n_{r \cdot}(\mathbf{z}^{-S}))^{(\triangle n_{r o}^{S:m})}$ が正しいはず。

その他

普通の多項分布で、事前分布に Dirichlet distribution を設定しているものなら、式 (7),(9) を使えば sampling の計算ができる。もっと複雑なモデルになるとよくわからない。要は多項分布の θ が残っていたら不都合で、消去してあればよさそう。例えば LDA の Griffiths の Gibbs sampling に適用できる? この場合、同じ type というのは、同一文書中の同じ単語?