2013年10月10日更新。

LDA的概率图如下图1所示：

参数的意思如图2所示：

根据模型，文章m的第n个词t是这样生成的：先从文章m的doc-topic分布中生成一个topic编号\(z_{m,n}\)，在根据编号第\(z_{m,n}\)个的topic-word分布中生成这个词，总够有\(K\)个topic，所以总的概率为： \[ p(w_{m,n}=t|\vec{\theta}_m,\underline{\Phi})=\sum^K_{k=1}p(w_{m,n}=t|\vec{\phi}_k)p(z_{m,n}=k|\vec{\theta}_m)\] 如果我们写出这篇文章的complete-data的联合分布（意思就是所以变量都已知的情况下），那么式子就是这样的：

通过对\(\vec{\vartheta_m}\)（doc-topic分布）和\(\underline{\Phi}\)（topic-word分布）积分以及\(z_{m,n}\)求和，我们可以求得\(\vec{w_m}\)的边缘分布：

(实际上这个边缘分布是求不出来的，因为\(z_{m,n}\)是隐藏变量，从而导致\(\underline{\vartheta}\)与\(\underline{\Phi}\)存在耦合现象，无法积分得到。要注意联合分布和边缘分布对Z乘积与加和的区别）

因为一个语料库有很多篇文章，而且文章之间都是相互独立的，所以整个语料库的似然为 \[ p(\mathcal{W}|\vec{\alpha},\vec{\beta})=\prod^{M}_{m=1}p(\vec{w_m}|\vec{\alpha},\vec{\beta})\]

虽然LDA（latent Dirichlet allocation)是个相对简单的模型，对它直接推断一般也是不可行的，所以我们要采用近似推断的方法，比如Gibbs sampling。

Gibbs sampling

Gibbs sampling是MCMC(Markov-chain Monte Carlo)算法的一种特殊情况，经常用于处理高维模型的近似推断。MCMC方法可以通过马尔科夫链的平稳分布模拟高维的概率分布\(p(\vec{x})\)。当马尔科夫链经过了burn-in阶段，消除了初始参数的影响，进入平稳状态之后，它的每次转移都能生成一个\(p(\vec{x})\)的样本。Gibbs samppling 是MCMC的特殊情况，它每次固定一个维度的\(x_i\),然后通过其他维度的数据（\(\vec{x}_{\neg i})\)生成这个维度的样本。算法如下：

1. choose dimension i(random by permutation)。

2. sample \(x_i\) from $p(x_i|_{i}) $。

为了构造Gibbs抽样，我们必须知道条件概率\(p(x_i|\vec{x}_{\neg i})\)，这个概率可以通过以下公式获得: \[p(x_i|\vec{x}_{\neg i})=\frac{p(x_i,\vec{x}_{\neg i})}{p(\vec{x}_{\neg i})}=\frac{p(x_i,\vec{x}_{\neg i})}{\int{p(\vec{x})d x_i}}\] 对于那些含有隐藏变量\(\vec{z}\)的模型来说，通常需要求得他们的后验概率\(p(\vec{z}|\vec{x})\)，对于这样的模型，Gibbs sampler的式子如下： \[ p(z_i|\vec{z}_{\neg i},\vec{x})=\frac{p(\vec{z},\vec{x})}{p(\vec{z}_{\neg i},\vec{x})}=\frac{p(\vec{z},\vec{x})}{\int_z{p(\vec{z},\vec{x})d x_i}}\] 当样本\(\tilde{\vec{z_r}},r\in[1,R]\)的数量足够多时，隐藏变量的后验概率可以用以下式子来估计： \[ p(\vec{z}|\vec{x})=\frac{1}{R}\sum^R_{r=1}\delta(\vec{z}-\tilde{\vec{z_r}})\] 其中Kronecker delta $()={1 $ if \(\vec{u}=0;0\) otherwise $ }$。

为了构造LDA的采样器，我们首先确定模型中的隐含变量为\(z_{m,n}\)。而参数\(\underline{\Theta}\)和\(\underline{\Phi}\)都可以用观察到的\(w_{m,n}\)和对应的\(z_{m,n}\)求积分得到((这个方法叫collapsed Gibbs Sampling，即通过求积分去掉一些未知变量，使Gibbs Sampling的式子更加简单))。贝叶斯推断的目标是分布\(p(\vec{z}|\vec{w})\)，它与联合分布成正比: \[p(\vec{z}|\vec{w})=\frac{p(\vec{z},\vec{w})}{p(\vec{w})}=\frac{\prod^W_{i=1}p(z_i,w_i)}{\prod^W_{i=1}\sum^K_{k=1}p(z_i=k,w_i)}\] 这里忽略了超参数（hyperparameter)\(\vec{\alpha}\)和\(\vec{\beta}\)。可以看到分母部分(也就是\(p(\vec{w}|\vec{\alpha},\vec{\beta})\))十分难求，它包括了\(K^W\)个项的求和。所以我们使用Gibbs Sample方法，通过全部的条件分布\(p(z_i|\vec{z}_{\neg i},\vec{w})\)来模拟得到\(p(\vec{z}|\vec{w})\)。

LDA的联合分布

LDA的联合分布可以写成如下的式子（要记得这是个联合分布，所以Z都是已知的，所以\(\underline{\Theta}\)和\(\underline{\Phi}\)都被积分积掉了） \[p(\vec{z},\vec{w}|\vec{\alpha},\vec{\beta})=p(\vec{w}|\vec{z},\vec{\beta})p(\vec{z}|\vec{\alpha})\] 因为式子中的第一部分与\(\alpha\)独立，第二部分与\(\beta\)独立，所以两个式子可以分别处理。先看第一个分布\(p(\vec{w}|\vec{z})\)，可以从观察到的词以及其主题的多项分布中生成： \[ p(\vec{w}|\vec{z},\underline{\Phi})=\prod^W_{i=1}p(w_i|z_i)=\prod^W_{i=1}\varphi_{z_i,w_i}\] 意思是，语料中的\(W\)个词是根据主题\(z_i\)观察到的独立多项分布。(我们把每个词看做独立的多项分布产生的结果，忽略顺序因素，所以没有多项分布的系数）。\(\varphi_{z_i,w_i}\)是一个\(K\ast V\)的矩阵，把词划分成主题和词汇表，公式如下： \[ p(\vec{w}|\vec{z},\underline{\Phi})=\prod^K_{k=1}\prod_{i:z_i=k}p(w_i=t|z_i=k)=\prod^K_{k=1}\prod^V_{t=1}\varphi^{n^{(t)}_k}_{k,t}\] \(n^{(t)}_k\)代表了主题\(k\)下词\(t\)出现的次数。目标分布\(p(\vec{w}|\vec{z},\vec{\beta})\)可以通过对\(\underline{\Phi}\)求狄利克雷积分得到:

类似地，主体分布\(p(\vec{z}|\vec{a})\)也可以通过这种方法产生，\(\underline{\Theta}\)为\(D*K\)的矩阵，公式如下： \[p(\vec{z}|\underline{\Theta})=\prod^W_{i=1}p(z_i|d_i)=\prod^M_{m=1}\prod^K_{k=1}p(z_i=k|d_i=m)=\prod^M_{m=1}\prod^K_{k=1}\theta^{n^{(k)}_m}_{m,k}\] \(n^{(k)}_m\)代表了文章\(m\)下主题\(k\)出现的次数。对\(\underline{\Theta}\)求积分，我们得到:

然后联合分布就变成了 \[p(\vec{z},\vec{w}|\vec{\alpha},\vec{\beta})=\prod^K_{z=1}\frac{\Delta(\vec{n_z}+\vec{\beta})}{\Delta(\vec{\beta})}\cdot\prod^M_{m=1}\frac{\Delta(\vec{n_m}+\vec{\alpha})}{\Delta(\vec{\alpha})}\]

完全条件分布(full conditional)

我们令\(i=(m,n)\)代表第\(m\)篇文章中的第\(n\)个词，\(\neg i\)代表除去这个词之后剩下的其他词，令\(\vec{w}=\{w_i=t,\vec{w}_{\neg i}\}\)，\(\vec{z}=\{z_i=k,\vec{z}_{\neg i}\}\)，我们求得

这个式子需要注意的：

1. 因为忽略了\(p(w_i)\)这个常数，所以后来的式子是\(\propto\)成正比。

2. 对于第\(m\)篇文章中的第\(n\)个词，其主题为\(k\)。\(n^{(t)}_k=n^{(t)}_{k,\neg i}+1,n^{(k)}_m=n^{(k)}_{m,\neg i}+1\)，对于其他文档和其他主题都没有影响。

这个公式很漂亮，右边是\(p(topic|doc)\cdot p(word|topic)\)，这个概率其实就是\(doc\rightarrow topic \rightarrow word\)的路径概率，所以Gibbs Sampling 公式的物理意义就是在K条路径中采样。（图）

多项分布参数

根据图3和图4的Dirichlet-Multinomial结构，我们知道\(\vec{\theta_m}\)和\(\vec{\phi_k}\)的后验概率为:(令\(\mathcal{M}=\{\vec{w},\vec{z}\}\))（备注1）：

最后，根据狄利克雷分布的期望\(<Dir(\vec{a})>=a_i/\sum_i{a_i}\)（备注2），我们得到 \[\phi_{k,t}=\frac{n^{(t)}_k+\beta_t}{\sum^V_{t=1}n^{(t)}_k+\beta_t}\] \[\theta_{m,k}=\frac{n^{(k)}_m+\alpha_k}{\sum^K_{k=1}n^{(k)}_m+\alpha_k}\]

最后，整个LDA算法的流程图为

备注： 1.狄利克雷分布的后验概率公式：

2.由于狄利克雷分布为： \[Dir(\vec{p}|\vec{\alpha})=\frac{\Gamma(\sum^K_{k=1}\alpha_k)}{\prod^K_{k=1}\Gamma{(\alpha_k)}}\prod^K_{k=1}p_k^{\alpha_k-1}\] 对于\(\vec{p}\)中一项\(p_i\)的期望为： \[\begin{split} E(p_i) &=\int^1_0 p_i\cdot Dir(\vec{p}|\vec{\alpha})dp \\ &=\frac{\Gamma(\sum^K_{k=1}\alpha_k)}{\Gamma(\alpha_i)}\cdot\frac{\Gamma(\alpha_i+1)}{\Gamma(\sum^K_{k=1}\alpha_k+1)} \\ &=\frac{\alpha_i}{\sum^K_{k=1}\alpha_k} \\\end{split}\] 参考文献： 1.主要来自《Parameter estimation for text analysis》 2.《LDA数学八卦》