潜在狄利克雷分布LDA

潜在狄利克雷分布(latent Dirichlet allocation,LDA)，作为基于贝叶斯学习的话题模型，是潜在语义分析、概率潜在语义分析的扩展。

LDA模型是文本集合的生成概率模型。假设每个文本由话题的一个多项分布表示，每个话题由单词的一个多项分布表示，特别假设文本的话题分布的先验分布是狄利克雷分布，话题的单词分布的先验分布也是狄利克雷分布。

先验分布的导入使LDA能够更好的应对话题模型学习中的过拟合现象。

LDA的文本集合的生成过程如下：首先，随机生成一个文本的话题分布，之后在该文本的每个位置，依据该文本的话题分布随机生成一个话题，然后在该位置依据该话题的单词分布生成一个单词，直至文本的最后一个位置，生成整个文本。重复以上过程生成所有文本。

LDA模型是含有隐变量的概率图模型。每个话题的单词分布，每个文本的话题分布，文本的每个位置的话题是隐变量；文本的每个位置的单词是观测变量。

LDA模型的学习与推理无法直接求解，通常使用吉布斯抽样和变分EM算法(variational EM algorithm)，前者是蒙特卡罗法，而后者是近似算法。

狄利克雷分布

分布定义

多项分布

多项分布是一种多元离散随机变量的概率分布，是二项分布的扩展。

假设重复进行n次独立随机试验，每次试验可能出现的结果有k种，第i种结果出现的概率为$p_i$，第i种结果出现的次数为$n_i$。如果用随机变量$X=(X_1,X_2,\dots,X_k)$表示试验所有可能结果的次数，其中$X_i$表示第i种结果出现的次数，那么随机变量X服从多项分布。

定义20.1(多项分布) 若多元离散变量$X=(X_1,X_2,\dots,X_k)$的概率质量函数为:

$$\begin{aligned} P(X_1=n1,X_2=n2,\dots,X_k=n_k) &= \frac{n!}{n_1!n_2!\dots n_k!}p^{n_1}_1p_2^{n_2}\dots p_k^{n_k}\\ &= \frac{n!}{\prod_{i=1}^kn_i!}\prod_{i=1}^k p_i^{n_I} \end{aligned}\tag{20-1}$$

其中$p=(p_1,p_2,\dots,p_k),p_i\ge0 \ ,i=1,2,\dots,k \ , \sum_{i=1}^k p_i=1 \ , \sum_{i=1}^k n_i = n$，则称随机变量X服从参数为(n,p)的多项分布，记作$X \sim \mathrm{Mult}(n,p)$。

当试验的次数n为1时，多项分布变成类别分布(categorical distribution)。类别分布表示试验可能出现的k种结果的概率。

狄利克雷分布

狄利克雷分布是一种多元连续随机变量概率分布，是贝塔分布(beta distribution)的扩展。在贝叶斯学习中，狄利克雷分布常作为多项式分布的先验分布使用。

定义20.2(狄利克雷分布) 若多元连续随机变量$\theta(\theta_1,\theta_2,\dots,\theta_k)$的概率密度函数为：

$$p(\theta|\alpha) = \frac{\varGamma\left(\sum_{i=1}^k \alpha_i\right)}{\prod_{i=1}^k \varGamma(\alpha_i)}\prod_{i=1}^k \theta_i^{\alpha_i-1} \tag{20-2}$$

其中$\sum_{i=1}^k \theta_i=1\ , \theta_i\ge0\ , \alpha=(\alpha_1,\alpha_2,\dots,\alpha_k) \ , \alpha_i>0 \ , i=1,2,\dots,k$，则称随机变量$\theta$服从参数为$\alpha$的狄利克雷分布，记作 $\theta \sim \mathrm{Dir}(\alpha)$。

式中$\varGamma(s)$是伽马函数，定义为：

$$\varGamma(s) = \int_0^{\infty} x^{s-1}e^{-x}dx \ , s>0$$

具有性质

$$\varGamma(s+1) = s\varGamma(s)$$

当s是自然数时，有

$$\varGamma(s+1) = s!$$

由于满足条件

$$\theta_i \ge 0 \ , \sum_{i=1}^k \theta_i = 1$$

所以狄利克雷分布$\theta$存在于(k-1)维单纯形上。

令

$$B(\alpha) = \frac{\prod_{i=1}^k \varGamma(\alpha_i)}{\varGamma\left(\sum_{i=1}^k \alpha_i\right)} \tag{20-3}$$

则狄利克雷分布的密度函数可以写成：

$$p(\theta|\alpha) = \frac{1}{B(\alpha)} \prod_{i=1}^k \theta_i^{\alpha_i-1} \tag{20-4}$$

其中，$B(\alpha)$是规范化因子，称为多元贝塔函数(或扩展的贝塔函数)。由密度函数的性质：

$$\int \frac{\varGamma\left(\sum_{i=1}^k \alpha_i\right)}{\prod_{i=1}^k \varGamma(\alpha_i)}\prod_{i=1}^k \theta_i^{\alpha_i-1} d\theta = \frac{\varGamma\left(\sum_{i=1}^k \alpha_i\right)}{\prod_{i=1}^k \varGamma(\alpha_i)} \int \prod_{i=1}^k \theta_i^{\alpha_i-1} d\theta = 1$$

得

$$B(\alpha) = \int \prod_{i=1}^k \theta_i^{\alpha_i-1} d\theta \tag{20-5}$$

所以式(20-5)是多元贝塔函数的积分表示。

二项分布和贝塔分布

二项分布是多项分布的特殊情况，贝塔分布是狄利克雷分布的特殊情况。

二项分布是指如下概率分布。X为离散随机变量，取值为m，其概率质量函数为:

$$P(X=m) = \begin{pmatrix}n\\m\end{pmatrix}p^m(1-p)^{n-m} \ , m=0,1,2,\dots,n \tag{20-6}$$

其中n和p$(0\le p \le 1)$是参数。

贝塔分布是指如下概率分布，X为连续随机变量，取值范围为[0,1]，其概率密度函数为:

$$p(x) = \left\{\begin{aligned}&\frac{1}{B(s,t)}x^{s-1}(1-x)^{t-1},0\le x\le 1 \\ &0, 其它\end{aligned}\right . \tag{20-7}$$

其中，s>0和t>0是参数，$B(s,t) = \frac{\varGamma(s)\varGamma(t)}{\varGamma(s+t)}$是贝塔函数，定义为:

$$B(s,t) = \int_0^1 x^{s-1}(1-x)^{t-1}dx \tag{20-8}$$

当s,t是自然数时，

$$B(s,t) = \frac{(s-1)!(t-1)!}{(s+t-1)!} \tag{20-9}$$

当n=1时，二项分布变成伯努利分布或0-1分布。伯努利分布表示试验可能出现的2种结果的概率。

下图给出了几种概率分布的关系：

共轭先验

狄利克雷分布的一些重要性质：

1. 狄利克雷分布属于指数分布族；
2. 狄利克雷分布是多项分布的共轭先验

贝叶斯学习中常使用共轭分布。如果后验分布与先验分布属于同类，则先验分布与后验分布称为共轭分布(conjugate distribution)，先验分布称为共轭先验(conjugate prior)。

作为先验分布的狄利克雷分布的参数又称为超参数。使用共轭分布的好处是便于从先验分布计算后验分布。

设$\mathcal{W} = \{w_1,w_2,\dots,w_k\}$是由k个元素组成的集合。随机变量X服从$\mathcal{W}$上的多项分布，$X \sim \mathrm{Mult}(n,\theta)$，其中$n=(n_1,n_2,\dots,n_k)$和$\theta=(\theta_1,\theta_2,\dots,\theta_k)$是参数。参数n为从$\mathcal{W}$中重复独立抽取样本的次数，$n_i$为样本中$w_i$出现的次数$(i=1,2,\dots,k)$；参数$\theta_i$为$w_i$出现的概率$(i=1,2,\dots,k)$。

将样本数据表示为D，目标是计算在样本数据D给定条件下参数$\theta$的后验概率$p(\theta|D)$。对于给定的样本数据D，似然函数是:

$$p(D|\theta) = \theta_1^{n_1}\theta_2^{n_2}\dots\theta_k^{n_k} = \prod_{i=1}^k \theta_i^{n_i} \tag{20-10}$$

假设随机变量$\theta$服从狄利克雷分布$p(\theta|\alpha)$，其中$\alpha=(\alpha_1,\alpha_2,\dots,\alpha_k)$为参数。则$\theta$的先验分布为：

$$p(\theta|\alpha) = \frac{\varGamma\left(\sum_{i=1}^k \alpha_i\right)}{\prod_{i=1}^k \varGamma(\alpha_i)}\prod_{i=1}^k \theta_i^{\alpha_i-1} = \frac{1}{B(\alpha)} \prod_{i=1}^k \theta_i^{\alpha_i-1} =\mathrm{Dir}(\theta|\alpha) \ , \alpha_i > 0 \tag{20-11}$$

根据贝叶斯规则，在给定样本数据D和参数$\alpha$条件下，$\theta$ 的后验概率分布是：

$$\begin{aligned} p(\theta|D,\alpha) &= \frac{p(D|\theta)p(\theta|\alpha)}{p(D|\alpha)}\\ &=\frac{\prod_{i=1}^k \theta_i^{n_i} \frac{1}{B(\alpha)} \prod_{i=1}^k \theta_i^{\alpha_i-1}}{\int \prod_{i=1}^k \theta_i^{n_i} \frac{1}{B(\alpha)} \prod_{i=1}^k \theta_i^{\alpha_i-1} d\theta}\\ &= \frac{1}{B(\alpha+n)} \prod_{i=1}^k \theta_i^{\alpha_i+n_i-1}\\ &= \mathrm{Dir}(\theta|\alpha+n) \end{aligned}\tag{20-12}$$

狄利克雷后验分布的参数等于狄利克雷先验分布参数$\alpha=(\alpha_1,\alpha_2,\dots,\alpha_k)$加上多项分布的观测计数$n=(n_1,n_2,\dots,n_k)$。好像试验之前就已经观察到计数$\alpha=(\alpha_1,\alpha_2,\dots,\alpha_k)$，因此也把$\alpha$叫做先验伪计数(prior pseudo-counts)。

潜在狄利克雷分配模型

基本想法

潜在狄利克雷分配是文本集合的生成概率模型。

LDA模型表示文本集合的自动生成过程：

1. 首先，基于单词分布的先验分布(狄利克雷分布)生成多个单词分布，即决定多个主题内容；
2. 之后，基于话题分布的先验分布(狄利克雷分布)生成多个话题分布，即决定多个文本内容；
3. 然后，基于每一话题分布生成话题序列，针对每个话题，基于话题的单词分布生成单词，整体构成一个单词序列，即生成文本。重复这个过程生成所有文本。

下图显示LDA的文本生成过程：

LDA模型是概率图模型，其特点是以狄利克雷分布为多项分布的先验分布，学习就是给定文本集合，通过后验概率分布的估计，推断模型的所有参数。利用LDA进行话题分析，就是对给定文本集合，学习到每个文本的话题分布，以及每个话题的单词分布。

LDA与PLSA的区别：

不同点：

1. LDA使用狄利克雷分布作为先验分布，而PLSA不使用先验分布(或者说假设先验分布是均匀分布)，两者对文本生成过程有不同假设。
2. 学习过程LDA基于贝叶斯学习，而PLSA基于极大似然估计

相同点：两者都假设话题是单词的多项分布，文本是话题的多项分布。

LDA的优点是，使用先验概率分布，可以防止学习过程中产生的过拟合。

模型定义

模型要素

潜在狄利克雷分配使用三种集合:

1. 单词集合$\mathcal{W} = \{w_1,\dots,w_v,\dots,w_V\}$，其中$w_v$是第v个单词，$v=1,2,\dots,V$，V是单词的个数。
2. 文本集合$D = \{\boldsymbol{w}_1,\dots,\boldsymbol{w}_m,\dots,\boldsymbol{w}_M\}$，其中$\boldsymbol{w}_m$是第m个文本,m=1,2,…,M，M是文本的个数。文本$\boldsymbol{w}_m$是一个单词序列$\boldsymbol{w}_m = (w_{m1},\dots,w_{mn},\dots,w_{mN_m})$，其中$w_{mn}$是文本$\boldsymbol{w}_m$的第n个单词，$n=1,2,\dots,N_m$，$N_m$是文本$\boldsymbol{w}_m$中单词的个数。
3. 话题集合$Z = \{z_1,\dots,z_k,\dots,z_K\}$，其中$z_k$是第k个话题，k=1,2,…,K，K是话题的个数。

每个话题$z_k$由一个单词的条件概率分布$p(w|z_k)$决定，$w\in W$。分布$p(w|z_k)$服从多项分布(严格意义上类别分布)，其参数为$\varphi_k$。

参数$\varphi_k$服从狄利克雷分布(先验分布)，其超参数为$\beta$。参数$\varphi_k$是一个V维向量$\varphi_k=(\varphi_{k1},\varphi_{k2},\dots,\varphi_{kV})$，其中$\varphi_{kv}$表示话题$z_k$生成单词$w_v$的概率。

所有话题的参数向量构成一个KxV矩阵$\boldsymbol{\varphi} = \{\varphi_k\}_{k=1}^K$。超参数$\beta$也是一个V维向量$\beta = (\beta_1,\beta_2,\dots,\beta_V)$。

每个文本$\boldsymbol{w}_m$由一个话题的条件概率分布$p(z|\boldsymbol{w}_m)$决定的，$z \in Z$。分布$p(z|\boldsymbol{w}_m)$服从多项分布(严格意义上类别分布)，其参数为$\theta_m$。

参数$\theta_m$服从狄利克雷分布(先验分布)，其超参数为$\alpha$。参数$\theta_m$是一个K维向量$\theta_m = (\theta_{m1},\theta_{m2},\dots,\theta_{mK})$，其中$\theta_{mk}$表示文本$\boldsymbol{w}_m$生成话题$z_k$的概率。

所有文本的参数向量构成一个MxK矩阵$\boldsymbol{\theta} = \{\theta_m\}_{m=1}^M$。超参数$\alpha$也是一个K维向量$\alpha=(\alpha_1,\alpha_2,\dots,\alpha_K)$。

每个文本$\boldsymbol{w}_m$中的每个单词$w_{mn}$由该文本的话题分布$p(z|\boldsymbol{w}_m)$以及所有话题的单词分布$p(w|z_k)$决定。

生成过程

LDA文本集合的生成过程如下：

给定单词集合W，文本集合D，话题集合Z，狄利克雷分布的超参数$\alpha$和$\beta$。

1. 生成话题的单词分布

   随机生成K个话题的单词分布。具体过程如下：

   按照狄利克雷分布$\mathrm{Dir}(\beta)$随机生成一个参数向量$\varphi_k$，$\varphi \sim \mathrm{Dir}(\beta)$，作为话题$z_k$的单词分布$p(w|z_k),w \in W$ ，k=1,2,…,K

2. 生成文本的话题分布

   随机生成M个文本的话题分布。具体过程如下：

   按照狄利克雷分布Dir($\alpha$)随机生成一个参数向量$\theta_m$，$\theta_m \sim \mathrm{Dir}(\alpha)$，作为文本$\boldsymbol{w}_m$的话题分布$p(z|\boldsymbol{w}_m)$，m=1,2,…,M。

3. 生成文本的单词序列

   随机生成M个文本的$N_m$个单词。文本$\boldsymbol{w}_m$(m=1,2,…,M)的单词$w_{mn}(n=1,2,\dots,N_m)$的生成过程如下：

   1. 首先，按照多项分布Mult($\theta_m$)随机生成一个话题$z_{mn}\ , z_{mn} \sim \mathrm{Mult}(\theta_m)$。
   2. 然后，按照多项分布Mult($\varphi_{z_{mn}}$)随机生成一个单词$w_{mn}\ , w_{mn}\sim \mathrm{Mult}(\varphi_{z_{mn}})$。

   文本$\boldsymbol{w}_m$本身是单词序列$\boldsymbol{w}_m = (w_{m1},\dots,w_{mn},\dots,w_{mN_m})$，对应着隐式的话题序列:$\boldsymbol{z}_m = (z_{m1},z_{m2},\dots,z_{mN_m})$。

算法20.1(LDA的文本生成算法)

1. 对于话题$z_k(k=1,2,\dots,K)$：

   生成多项分布参数$\varphi_k \sim \mathrm{Dir}(\beta)$，作为话题的单词分布$p(w|z_k)$

2. 对于文本$\boldsymbol{w}_m(m=1,2,\dots,M)$：

   生成多项分布参数$\theta_m \sim \mathrm{Dir}(\alpha)$，作为文本的话题分布$p(z|\boldsymbol{w}_m)$。

3. 对于文本$\boldsymbol{w}_m$的单词$w_{mn}(m=1,2,\dots,M,n=1,2,\dots,N_m)$

   1. 生成话题$z_{mn} \sim \mathrm{Mult}(\theta_m)$，作为单词对应的话题。
   2. 生成单词$w_{mn}\sim \mathrm{Mult}(\varphi_{z_{mn}})$

LDA的文本生成过程中，假定话题个数K给定(通常通过试验给定)，狄利克雷分布的超参数$\alpha$和$\beta$通常也是事先给定的(在没有其它先验知识情况下,可以假设向量$\alpha$和$\beta$的所有分量均为1)。这时的文本的话题分布$\theta_m$是对称的，话题的单词分布$\varphi_k$也是对称的。

概率图模型

如下图所示，结点表示随机变量，双边圆是观测变量，单边圆是隐变量；有向边表示概率依存关系；矩形表示重复，矩形内的数字表示重复次数。

上图的LDA板块表示，结点$\alpha$和$\beta$是模型的超参数，结点$\varphi_k$表示话题$z_k$的单词分布的参数，结点$\theta_m$表示文本$\boldsymbol{w}_m$的话题分布的参数，结点$z_{mn}$表示话题，结点$w_{mn}$表示单词。

结点$\beta$指向结点$\varphi_k$，重复K次，表示根据超参数$\beta$生成K个话题的单词分布的参数$\varphi_k$;

结点$\alpha$指向结点$\theta_m$，重复M次，表示根据超参数$\alpha$生成M个文本的话题分布的参数$\theta_m$；

结点$\theta_m$指向结点$z_{mn}$，重复$N_m$次，表示根据文本的话题分布$\theta_m$生成$N_m$个话题$z_{mn}$；

结点$z_{mn}$指向结点$w_{mn}$，同时K个结点$\varphi_k$也指向结点$w_{mn}$，表示根据话题$z_{mn}$以及K个话题的单词分布$\varphi_k$生成单词$w_{mn}$。

把板块图展开得到以下的有向图表示形式：

随机变量序列的可交换性

一个有限的随机变量序列是可交换的，是指随机变量的联合概率分布对随机变量的排列不变：

$$P(x_1,x_2,\dots,x_N) = P(x_{\pi(1)},x_{\pi(2)},\dots,x_{\pi(N)}) \tag{20-13}$$

这里$\pi(1),\pi(2),\dots,\pi(N)$表示自然数1,2,…,N的任意一个排列。一个无限的随机变量序列是无限可交换的，是指它的任意一个有限子序列都是可交换的。

如果一个随机变量序列$X_1,X_2,\dots,X_N,\dots$是独立同分布的，那么它们是无限可交换的。反之不然。

根据De Finetti定理，任意一个无限可交换的随机变量序列对一个随机参数是条件独立同分布的。即任意一个无限可交换的随机变量序列$X_1,X_2,\dots,X_i,\dots$的i基于一个随机参数Y的条件概率，等于基于这个随机参数Y的各个随机变量$X_1,X_2,\dots,X_i,\dots$的条件概率的乘积：

$$P(X_1,X_2,\dots,X_i,\dots|Y) = P(X_1|Y)P(X_2|Y)\dots P(X_i|Y)\dots \tag{20-14}$$

LDA的假设前提为：文本中的话题对一个随机参数是条件独立同分布的。因此，在参数给定的情况下，文本中的话题的顺序可以忽略。

概率公式

LDA模型整体是由观测变量和隐变量组成的联合概率分布，可以表示为：

$$p(\boldsymbol{w},\boldsymbol{z},\theta,\varphi|\alpha,\beta) = \prod_{k=1}^K p(\varphi_k|\beta)\prod_{m=1}^Mp(\theta_m|\alpha)\prod_{n=1}^{N_m}p(z_{mn}|\theta_m)p(w_{mn}|z_{mn},\varphi) \tag{20-15}$$

其中观测变量$\boldsymbol{w}$表示所有文本中的单词序列，隐变量$\boldsymbol{z}$表示所有文本中的话题序列，隐变量$\theta$表示所有文本的话题分布的参数，隐变量$\varphi$表示所有话题的单词分布的参数，$\alpha$和$\beta$是超参数。

• $p(\varphi_k|\beta)$表示超参数$\beta$给定的情况下，第k个话题的单词分布的参数$\varphi_k$的生成概率；
• $p(\theta_m|\alpha)$表示超参数$\alpha$给定的情况下，第m个文本的话题分布的参数$\theta_m$的生成概率；
• $p(z_{mn}|\theta_m)$表示第m个文本的话题分布$\theta_m$给定的情况下，文本的第n个位置的话题$z_{mn}$的生成概率；
• $p(w_{mn}|z_{mn},\varphi)$，表示在第m个文本的第n个位置的话题$z_{mn}$及所有话题的单词分布的参数$\varphi$给定的情况下，第m个文本的第n个位置的单词$w_{mn}$的生成概率。

第m个文本的联合概率分布可以表示为：

$$p(\boldsymbol{w}_m,\boldsymbol{z}_m,\theta_m,\varphi|\alpha,\beta) = \prod_{k=1}^K p(\varphi_k|\beta)p(\theta_m|\alpha)\prod_{n=1}^{N_m}p(z_{mn}|\theta_m)p(w_{mn}|z_{mn},\varphi) \tag{20-16}$$

其中，$\boldsymbol{w}_m$表示该文本中的单词序列，$\boldsymbol{z}_m$表示该文本的话题序列，$\theta_m$表示该文本的话题分布参数。

LDA模型的联合分布含有隐变量，对隐变量进行积分得到边缘分布。

参数$\theta_m,\varphi$给定的情况下，第m个文本的生成概率是：

$$p(\boldsymbol{w}_m|\theta_m,\varphi)=\prod_{n=1}^{N_m}\left[\sum_{k=1}^Kp(z_{mn}=k|\theta_m)p(w_{mn}|\varphi_k)\right] \tag{20-17}$$

超参数$\alpha , \beta$给定的条件下，第m个文本的生成概率是：

$$p(\boldsymbol{w}_m|\alpha,\beta) = \prod_{k=1}^K \int p(\varphi_k|\beta)\left\{\int p(\theta_m|\alpha)\prod_{n=1}^{N_m}\left[\sum_{l=1}^Kp(z_{mn}=l|\theta_m)p(w_{mn}|\varphi_l)\right]d\theta_m \right\}d\varphi_k \tag{20-18}$$

超参数$\alpha , \beta$给定的条件下，所有文本的生成概率是

$$p(\boldsymbol{w}|\alpha,\beta) = \prod_{k=1}^K \int p(\varphi_k|\beta)\left\{\prod_{m=1}^M\int p(\theta_m|\alpha)\prod_{n=1}^{N_m}\left[\sum_{l=1}^Kp(z_{mn}=l|\theta_m)p(w_{mn}|\varphi_l)\right]d\theta_m \right\}d\varphi_k \tag{20-19}$$

LDA的吉布斯抽样算法

潜在狄利克雷分布的学习(参数估计)是一个复杂的最优化问题，很难精确求解，只能近似求解。

常用的近似求解方法有吉布斯抽样和变分推理。

吉布斯抽样优点是实现简单，缺点是收敛速度慢。

基本想法

给定文本(单词序列)的集合$D = \{\boldsymbol{w}_1,\dots,\boldsymbol{w}_m,\dots,\boldsymbol{w}_M\}$，其中$\boldsymbol{w}_m$是第m个文本,m=1,2,…,M，M是文本的个数。文本$\boldsymbol{w}_m$是一个单词序列$\boldsymbol{w}_m = (w_{m1},\dots,w_{mn},\dots,w_{mN_m})$，其中$w_{mn}$是文本$\boldsymbol{w}_m$的第n个单词，$n=1,2,\dots,N_m$，$N_m$是文本$\boldsymbol{w}_m$中单词的个数。

超参数$\alpha,\beta$已知。目标是要推断：

1. 话题序列的集合$\boldsymbol{z}=\{\boldsymbol{z}_1,\dots,\boldsymbol{z}_m,\dots,\boldsymbol{z}_M\}$的后验概率分布，其中$\boldsymbol{z}_m$是第m个文本的话题序列，$\boldsymbol{z}_m = (z_{m1},z_{m2},\dots,z_{mN_m})$；
2. 参数$\theta=\{\theta_1,\dots,\theta_m,\dots,\theta_M\}$，其中$\theta_m$是文本$\boldsymbol{w}_m$的话题分布的参数；
3. 参数$\varphi=\{\varphi_1,\dots,\varphi_k,\dots,\varphi_K\}$，其中$\varphi_k$是话题$z_k$的单词分布的参数。

也就是说，要对联合概率分布$p(\boldsymbol{w},\boldsymbol{z},\theta,\varphi|\alpha,\beta)$进行估计，其中$\boldsymbol{w}$是观测变量，而$\boldsymbol{z},\theta,\varphi$是隐变量。

使用吉布斯抽样对多元随机变量x的联合分布进行估计：

为了估计多元随机变量x的联合分布p(x)，吉布斯抽样法选择x的一个分量，固定其它分量，按照其条件概率分布进行随机抽样，依次循环对每一分量执行这个操作，得到联合分布p(x)的一个随机样本，重复这个过程，在燃烧期之后，得到联合概率分p(x)的样本集合。

LDA模型的学习通常采用收缩的吉布斯抽样(collapsed Gibbs sampling)方法。基本想法是，

1. 通过对隐变量$\theta$和$\varphi$积分，得到边缘概率分布$p(\boldsymbol{w},\boldsymbol{z}|\alpha,\beta)$，其中$\boldsymbol{w}$是可观测变量，变量$\boldsymbol{z}$是e不可观测的；
2. 对后验概率分布$p(\boldsymbol{z}|\boldsymbol{w},\alpha,\beta)$进行吉布斯抽样，得到分布$p(\boldsymbol{z}|\boldsymbol{w},\alpha,\beta)$的样本集合；
3. 利用这个样本集合对参数$\theta$和$\varphi$进行估计，最终得到LDA模型$p(\boldsymbol{w},\boldsymbol{z},\theta,\varphi|\alpha,\beta)$的所有参数估计。

算法 的主要部分

根据前面的分析，问题转化为对后验概率分布$p(\boldsymbol{z}|\boldsymbol{w},\alpha,\beta)$的吉布斯抽样，该分布表示在所有文本的单词序列给定的情况下，所有可能话题序列的条件概率。

抽样分布的表达式

首先，

$$p(\boldsymbol{z}|\boldsymbol{w},\alpha,\beta) = \frac{p(\boldsymbol{w},\boldsymbol{z}|\alpha,\beta)}{p(\boldsymbol{w}|\alpha,\beta)} \propto p(\boldsymbol{w},\boldsymbol{z}|\alpha,\beta) \tag{20-20}$$

这里变量$\boldsymbol{w},\alpha,\beta$已知。联合分布$p(\boldsymbol{w},\boldsymbol{z}|\alpha,\beta)$的表达式可进一步分解为：

$$p(\boldsymbol{w},\boldsymbol{z}|\alpha,\beta) =p(\boldsymbol{w}|\boldsymbol{z},\alpha,\beta)p(\boldsymbol{z}|\alpha,\beta) = p(\boldsymbol{w}|\boldsymbol{z},\beta)p(\boldsymbol{z}|\alpha) \tag{20-21}$$

两个因子可以分开处理。

推导第一个因子$p(\boldsymbol{w}|\boldsymbol{z},\beta)$的表达式。首先：

$$p(\boldsymbol{w}|\boldsymbol{z},\varphi) = \prod_{k=1}^K \prod_{v=1}^V \varphi_{kv}^{n_{kv}} \tag{20-22}$$

其中，$\varphi_{kv}$是第k个话题生成单词集合第v个单词的概率，$n_{kv}$是数据中第k个话题生成第v个单词的次数。于是

$$\begin{aligned} p(\boldsymbol{w}|\boldsymbol{z},\beta) &= \int p(\boldsymbol{w}|\boldsymbol{z},\varphi) p(\varphi|\beta)d\varphi \\ &= \int \prod_{k=1}^K \frac{1}{B(\beta)}\prod_{v=1}^V \varphi_{kv}^{n_{kv}+\beta_v-1}d \varphi\\ &= \prod_{k=1}^K \frac{B(n_k+\beta)}{B(\beta)} \end{aligned} \tag{20-23}$$

其中，$n_k = \{n_{k1},n_{k2},\dots,n_{kV}\}$

第二个因子$p(\boldsymbol{z}|\alpha)$的表达式可以类似推导。首先：

$$p(\boldsymbol{z}|\theta) = \prod_{m=1}^M \prod_{k=1}^K \theta_{mk}^{n_{mk}} \tag{20-24}$$

其中，$\theta_{mk}$是第m个文本生成第k个话题的概率，$n_{mk}$是数据中第m个文本生成第k个话题的次数。于是：

$$\begin{aligned} p(\boldsymbol{z}|\alpha) &= \int p(\boldsymbol{z}|\theta) p(\theta|\alpha) d\theta\\ &= \int \prod_{m=1}^M \frac{1}{B(\alpha)}\prod_{k=1}^K \theta_{mk}^{n_{mk}+\alpha_k-1} d\theta\\ &= \prod_{m=1}^M \frac{1}{B(\alpha)}\int \prod_{k=1}^K \theta_{mk}^{n_{mk}+\alpha_k-1} d\theta\\ &= \prod_{m=1}^M \frac{B(n_m+\alpha)}{B(\alpha)} \end{aligned}\tag{20-25}$$

其中$n_m = \{n_{m1},n_{m2},\dots,n_{mK}\}$。由式(20-23)和式(20-25)得

$$p(\boldsymbol{w},\boldsymbol{z}|\alpha,\beta) = \prod_{k=1}^K \frac{B(n_k+\beta)}{B(\beta)} \bullet \prod_{m=1}^M \frac{B(n_m+\alpha)}{B(\alpha)} \tag{20-26}$$

故由式(20-20)和式(20-26)，得收缩的吉布斯抽样分布的公式：

$$p(\boldsymbol{z}|\boldsymbol{w},\alpha,\beta) \propto \prod_{k=1}^K \frac{B(n_k+\beta)}{B(\beta)} \bullet \prod_{m=1}^M \frac{B(n_m+\alpha)}{B(\alpha)} \tag{20-27}$$

满条件分布 的表达式

分布$p(\boldsymbol{z}|\boldsymbol{w},\alpha,\beta)$的满条件分布可以写成：

$$p(z_i|\boldsymbol{z}_{-i},\boldsymbol{w},\alpha,\beta) = \frac{1}{Z_{z_i}} p(\boldsymbol{z}|\boldsymbol{w},\alpha,\beta) \tag{20-28}$$

这里$w_i$表示所有文本的单词序列的第i个位置的单词，$z_i$表示单词$w_i$对应的话题，i=(m,n)，$i=1,2,\dots,I,\boldsymbol{z}_{-i}=\{z_j:j\ne i\}$，$Z_{z_i}$表示分布$p(\boldsymbol{z}|\boldsymbol{w},\alpha,\beta)$对变量$z_i$的边缘化因子。

式(20-28)是在所有文本单词序列、其它位置话题序列给定条件下，第i个位置的话题的条件概率分布。由式(20-27)和式(20-28)可以推出：

$$p(z_i|\boldsymbol{z}_{-i},\boldsymbol{w},\alpha,\beta) \propto \frac{n_{kv}+\beta_v}{\sum_{v=1}^V(n_{kv}+\beta_v)}\bullet \frac{n_{mk}+\alpha_k}{\sum_{k=1}^K(n_{mk}+\alpha_k)} \tag{20-29}$$

其中第m个文本的第n个位置的单词$w_i$是单词集合的第v个单词，其话题$z_i$是话题 集合的第k个话题，$n_{kv}$表示第k个话题中第v个单词的计数，但减去当前单词的计数，$n_{mk}$表示第m个文本中第k个话题的计数，但减去当前单词的话题的计数。

算法的后处理

通过吉布斯抽样得到的分布$p(\boldsymbol{z}|\boldsymbol{w},\alpha,\beta)$的a样本，可以得到变量$\boldsymbol{z}$的分配值，也可以估计变量$\theta$和$\varphi$。

参数估计

• 参数$\theta=\{\theta_m\}$

  根据LDA模型的定义，后验概率满足：

  $$p(\theta_m|\boldsymbol{z}_m,\alpha) = \frac{1}{Z_{\theta_m}} \prod_{n=1}^{N_m} p(z_{mn}|\theta_m)p(\theta_m|\alpha) = \mathrm{Dir}(\theta_m|n_m+\alpha) \tag{20-30}$$

这里$n_m = \{n_{m1},n_{m2},\dots,n_{mK}\}$是第m个文本的话题计数，$Z_{\theta_m}$表示 分布$p(\theta_m，\boldsymbol{z}_m|\alpha)$对变量$\theta_m$的边缘化因子。于是得到参数$\theta=\{\theta_m\}$的估计式：

$$\theta_{mk} = \frac{n_{mk}+\alpha_k}{\sum_{k=1}^K (n_{mk}+\alpha_k)} \ , m=1,2,\dots,M;k=1,2,\dots,K \tag{20-31}$$

• 参数$\varphi=\{\varphi_k\}$

  后验概率满足

  $$p(\varphi_k|\boldsymbol{w},\boldsymbol{z},\beta) = \frac{1}{Z_{\varphi_k}} \prod_{i=1}^I p(w_i|\varphi_k)p(\varphi_k|\beta) = \mathrm{Dir}(\varphi_k|n_k+\beta) \tag{20-32}$$

这里$n_k = \{n_{k1},n_{k2},\dots,n_{kV}\}$是第k个话题的单词计数,$Z_{\varphi_k}$表示分布$p(\varphi_k,\boldsymbol{w}|\boldsymbol{z},\beta)$对变量$\varphi_k$的边缘化因子，I是文本集合单词序列$\boldsymbol{w}$的单词总数。于是，得到参数的估计式：

$$\varphi_{kv} = \frac{n_{kv}+\beta_v}{\sum_{v=1}^V (n_{kv}+\beta_v)} \ , k=1,2,\dots,K;v=1,2,\dots,V \tag{20-33}$$

算法

算法20.2(LDA吉布斯抽样算法)

输入：文本的单词序列$\boldsymbol{w} = \{\boldsymbol{w}_1,\dots,\boldsymbol{w}_m,\dots,\boldsymbol{w}_M\}$，$\boldsymbol{w}_m = (w_{m1},\dots,w_{mn},\dots,w_{mN_m})$；

输出：文本的话题序列$\boldsymbol{z}=\{\boldsymbol{z}_1,\dots,\boldsymbol{z}_m,\dots,\boldsymbol{z}_M\}$，$\boldsymbol{z}_m = (z_{m1},z_{m2},\dots,z_{mN_m})$的后验概率分布$p(\boldsymbol{z}|\boldsymbol{w},\alpha,\beta)$的样本计数，模型的参数$\varphi$和$\theta$的估计值

参数：超参数$\alpha,\beta$ 和话题个数K

1. 设所有计数矩阵的元素$n_{mk},n_{kv}$，计数向量的元素$n_m,n_k$初值为0；

2. 对所有文本$\boldsymbol{w}_m$，$m=1,2,\dots,M$

   对第m个文本中的所有单词$w_{mn}$，n=1,2,…,$N_m$

   1. 抽样话题$z_{mn} = z_k \sim \mathrm{Mult}\left(\frac{1}{K}\right)$

      增加文本-话题计数$n_{mk}=n_{mk}+1$,

      增加文本-话题和计数$n_m=n_m+1$，

      增加话题-单词计数$n_{kv}=n_{kv}+1$,

      增加话题-单词和计数$n_{k}=n_{k}+1$

3. 循环执行以下操作，直到进入燃烧期

   对所有文本$\boldsymbol{w}_m,m=1,2,\dots,M$

   对第m个文本中的所有单词$w_{mn}$，$n=1,2,\dots,N_m$

   1. 当前的单词$w_{mn}$是第v个单词，话题指派$z_{mn}$是第k个话题

      减少计数$n_{mk}=n_{mk}-1,n_m=n_m-1,n_{kv}=n_{kv}-1,n_k=n_k-1$

   2. 按照满条件分布进行抽样

      $$p(z_i|\boldsymbol{z}_{-i},\boldsymbol{w},\alpha,\beta) \propto \frac{n_{kv}+\beta_v}{\sum_{v=1}^V(n_{kv}+\beta_v)}\bullet \frac{n_{mk}+\alpha_k}{\sum_{k=1}^K(n_{mk}+\alpha_k)}$$

      得到新的第$k^{'}$个话题，分配给$z_{mn}$

   3. 增加计数$n_{mk^{'}}= n_{mk^{'}}+1,n_m=n_m+1,n_{k^{'}v}=n_{k^{'}v}+1,n_k=n_k+1$

   4. 得到更新的两个计数矩阵$N_{K\times V} = [n_{kv}]$和$N_{M\times K}=[n_{mk}]$，表示后验概率分布$p(\boldsymbol{z}|\boldsymbol{w},\alpha,\beta)$的样本计数

4. 利用得到的样本计数，计算模型参数：

   $$\theta_{mk} = \frac{n_{mk}+\alpha_k}{\sum_{k=1}^K(n_{mk}+\alpha_k)}$$ $$\varphi_{kv} = \frac{n_{kv}+\beta_v}{\sum_{v=1}^V (n_{kv}+\beta_v)}$$

LDA的变分EM算法

变分推理

变分推理(variational inference)是贝叶斯学习中常用的、含有隐变量模型的学习和推理方法。

MCMC通过随机抽样的方法近似的计算模型的后验概率；

变分推理则通过解析的方法计算模型的后验概率的近似值。

变分推理的基本想法：假设模型是联合概率分布p(x,z)，其中x是观测变量，z是隐变量，包括参数。目标是学习模型的后验概率分布p(z|x)，用模型进行概率推理。由于目标分布很复杂，因此通过使用概率分布q(z)近似条件概率分布p(z|x)，用KL散度$D(q(z)\|p(z|x))$计算两者的相似度，q(z)称为变分分布(variational distribution)。

如果能找到与p(z|x)在KL散度意义下最近的分布$q^{*}(z)$，则可以用这个分布近似$p(z|x)$。

$$p(z|x) \approx q^{*}(z) \tag{20-34}$$

下图给出了$q^{*}(z)$与$p(z|x)$的关系：

KL散度可以写成以下形式：

$$\begin{aligned} D(q(z)\|p(z|x)) &= E_q[\log q(z)]-E_q[\log p(z|x)]\\ &= E_q[\log q(z)]-E_q[\log p(x,z)]+\log p(x)\\ &= \log p(x) - \left\{E_q[\log p(x,z)]-E_q[\log q(z)]\right\} \end{aligned}\tag{20-35}$$

KL散度大或等于0，当且仅当两个分布一致时为0，由式(20-35)可推出：

$$\log p(x) \ge E_q[\log p(x,z)]-E_q[\log q(z)] \tag{20-36}$$

不等式右端是左端的下界，左端称作证据(evidence)，右端称为证据下界(evidence lower bound,ELBO)，证据下界记作：

$$L(q) = E_q[\log p(x,z)]-E_q[\log q(z)] \tag{20-37}$$

KL散度(20-35)的最小化可以通过证据下界(20-37)最大化实现，因为目标是求q(z)使KL散度最小化，这时$\log p(x)$是常量。

因此，变分推理变成求解证据下界最大化的问题。

假设q(z)对z的所有分量都是相互独立的(实际是条件独立于参数)，即满足：

$$q(z) = q(z_1)q(z_2)\dots q(z_n) \tag{20-38}$$

这时，变分分布称为平均场(mean field)。

KL散度的最小化或证据下界最大化实际是在平均场的集合，即满足独立假设的分布集合$Q = \{q(z)|q(z)=\prod_{i=1}^nq(z_i)\}$之中进行的。

变分推理有以下几个步骤：

1. 定义变分分布q(z)
2. 推导其证据下界表达式
3. 用最优化方法对证据下界进行优化，如坐标上升，得到最有分布$q^*(z)$，作为后验概率分布p(z|x)的近似

变分EM算法

变分推理中，可以通过迭代的方法最大化证据下界，此算法是EM算法的推广，称为变分EM算法。

假设模型是联合概率分布$p(x,z|\theta)$，其中x是观测变量，z是隐变量，$\theta$是参数。目标是通过观测数据的概率(证据)$\log p(x|\theta)$ 的最大化，估计模型的参数$\theta$。

使用变分推理，导入平均场$q(z) = \prod_{i=1}^n q(z_i)$，定义证据下界：

$$L(q,\theta) = E_q[\log p(x,z|\theta)]-E_q[\log q(z)] \tag{20-39}$$

通过迭代，分别以q和$\theta$为变量，对证据下界进行最大化。

算法20.3(变分EM算法)

循环执行以下E步和M步，直到收敛。

1. E步：固定$\theta$，求$L(q,\theta)$对q的最大化
2. M步：固定q，求$L(q,\theta)$对$\theta$的最大化

给出模型参数$\theta$的估计值。

根据变分推理原理，观测数据的概率和证据下界满足：

$$\log p(x|\theta) - L(q,\theta) = D(q(z)\|p(z|x,\theta)) \ge 0 \tag{20-40}$$

变分EM算法的迭代过程中，以下关系成立：

$$\log p(x|\theta^{(t-1)}) = L(q^{(t)},\theta^{(t-1)}) \le L(q^{(t)},\theta^{(t)}) \le \log p(x|\theta^{(t)}) \tag{20-41}$$

其中上角标t-1和t表示迭代次数。

左边的等式基于E步计算和变分推理原理，中间的不等式基于M步计算，右边的不等式基于变分推理原理。说明了变分EM算法的收敛性。

对照《统计学习方法》9.4节，EM算法的推广，EM算法的推广是求F函数的极大-极大算法，其中的F函数就是证据下界。

EM算法假设q(z) = p(z|x)且p(z|x)容易计算；而变分EM算法则考虑一般情况，使用容易计算的平均场$q(z)=\prod_{i=1}^n q(z_i)$。

当模型复杂时，EM算法未必可用，但变分EM算法仍然可以使用。

算法推导

将变分EM算法应用到下图的LDA模型的学习上。

首先定义具体的变分分布，推导证据下界的表达式，接着，推导变分分布的参数和LDA模型的参数的估计式，最后给出LDA模型的变分EM算法。

证据下界的定义

一次只考虑一个文本。记作$\boldsymbol{w}$

文本的单词序列$\boldsymbol{w} = (w_1,\dots,w_n,\dots,w_N)$，对应的话题序列$\boldsymbol{z}=(z_1,\dots,z_n,\dots,z_N)$，以及话题分布$\theta$，随机变量$\boldsymbol{w},\boldsymbol{z}$和$\theta$的联合分布是：

$$p(\theta,\boldsymbol{z},\boldsymbol{w}|\alpha,\varphi) = p(\theta|\alpha)\prod_{n=1}^Np(z_n|\theta)p(w_n|z_n,\varphi) \tag{20-42}$$

其中，$\boldsymbol{w}$是观测变量，$\theta$和$\boldsymbol{z}$是隐变量，$\alpha,\varphi$是参数。

定义基于平均场的变分分布：

$$q(\theta,\boldsymbol{z}|\gamma,\eta) = q(\theta|\gamma)\prod_{n=1}^N q(z_n|\eta_n) \tag{20-43}$$

其中$\gamma$是狄利克雷分布参数，$\eta=(\eta_1,\eta_2,\dots,\eta_n)$是多项分布的参数，变量$\theta$和$\boldsymbol{z}$的各个分量都是条件独立的。目标是求KL散度意义下最相近的变分分布$q(\theta,\boldsymbol{z}|\gamma,\eta)$，以近似LDA模型的后验分布$p(\theta,\boldsymbol{z}|\boldsymbol{w},\alpha,\varphi)$。

下图为变分分布的板块表示：

LDA模型中的隐变量$\theta,\boldsymbol{z}$之间存在依存关系，变分分布中这些依存关系被去掉，变量$\theta,\boldsymbol{z}$条件独立。由此得到一个文本的证据下界：

$$L(\gamma,\eta,\alpha,\varphi) = E_q[\log p(\theta,\boldsymbol{z},\boldsymbol{w}|\alpha,\varphi)]-E_q[\log q(\theta,\boldsymbol{z}|\gamma,\eta)] \tag{20-44}$$

其中，数学期望是对分布$q(\theta,\boldsymbol{z}|\gamma,\eta)$定义的，为了方便写作$E_q[\bullet]$，$\gamma,\eta$是变分分布的参数，$\alpha,\varphi$是LDA模型参数。

所有文本的证据下界为：

$$L_{\boldsymbol{w}}(\gamma,\eta,\alpha,\varphi) = \sum_{m=1}^M \{E_{q_m}[\log p(\theta_m,\boldsymbol{z}_m,\boldsymbol{w}_m|\alpha,\varphi)]-E_{q_m}[\log q(\theta_m,\boldsymbol{z}_m|\gamma_m,\eta_m)]\} \tag{20-45}$$

为求解证据下界$L(\gamma,\eta,\alpha,\varphi)$的最大化，首先写出证据下界的表达式。为此展开证据下界(20-44)：

$$\begin{aligned} L(\gamma,\eta,\alpha,\varphi) &= E_q[\log p(\theta|\alpha)]+E_q[\log p(\boldsymbol{z}|\theta)]+E_q[\log p(\boldsymbol{w}|\boldsymbol{z},\varphi)]-E_q[\log q(\theta|\gamma)]-E_q[\log q[\boldsymbol{z}|\eta]] \end{aligned}\tag{20-46}$$

根据变分参数$\gamma$和$\eta$，模型参数$\alpha$和$$\varphi$$继续展开，并将展开式的每一项写成一行：

$$\begin{aligned} L(\gamma,\eta,\alpha,\varphi) = &\log \Gamma\left(\sum_{l=1}^K \alpha_l\right) - \sum_{k=1}^K \log \Gamma(\alpha_k)+\sum_{k=1}^K(\alpha_k-1)\left[\varPsi(\gamma_k)-\varPsi\left(\sum_{l=1}^K \gamma_l\right)\right]+\\ &\sum_{n=1}^N\sum_{k=1}^K \eta_{nk}\left[\varPsi(\gamma_k)-\varPsi\left(\sum_{l=1}^K \gamma_l\right)\right] + \\ &\sum_{n=1}^N\sum_{k=1}^K\sum_{v=1}^V \eta_{nk}w_{n}^v\log \varphi_{kv}-\\ & \log\Gamma\left(\sum_{l=1}^K \gamma_l\right)+\sum_{k=1}^K \log \Gamma(\gamma_k)-\sum_{k=1}^K(\gamma_k-1)\left[\varPsi(\gamma_k)-\varPsi\left(\sum_{l=1}^K \gamma_l\right)\right]-\\ &\sum_{n=1}^N\sum_{k=1}^K\eta_{nk}\log \eta_{nk} \end{aligned} \tag{20-47}$$

式中$\varPsi(\alpha_k)$是对数伽马函数的导数，即：

$$\varPsi(\alpha_k) = \frac{d}{d\alpha_k}\log \Gamma(\alpha_k) \tag{20-48}$$

第一项推导，求$E_q[\log p(\theta|\alpha)]$，是关于分布$q(\theta,\boldsymbol{z}|\gamma,\eta)$的数学期望。

$$E_q[\log p(\theta|\alpha)] =\sum_{k=1}^K(\alpha_k-1)E_q[\log\theta_k] + \log \Gamma\left(\sum_{l=1}^K \alpha_l\right) - \sum_{k=1}^K \log \Gamma(\alpha_k) \tag{20-49}$$

其中$\theta \sim \mathrm{Dir}(\theta|\gamma)$，根据这里的狄利克雷分布的相关性质，可得：

$$E_{q(\theta|\gamma)}[\log \theta_k] = \varPsi(\gamma_k)-\varPsi\left(\sum_{l=1}^K \gamma_l\right) \tag{20-50}$$

故得：

$$E_q[\log p(\theta|\alpha)] = \log \Gamma \left(\sum_{l=1}^K \alpha_l\right)-\sum_{k=1}^K \log \Gamma(\alpha_k)+\sum_{k=1}^K (\alpha_k-1)\left[\Psi(\gamma_k)-\Psi\left(\sum_{l=1}^K \gamma_l\right)\right] \tag{20-51}$$

式中$\alpha_k,\gamma_k$表示第k个话题的狄利克雷分布参数。

第二项推导，求$E_q[\log p(\boldsymbol{z}|\theta)]$，是关于分布$q(\theta,\boldsymbol{z}|\gamma,\eta)$的数学期望。

$$\begin{aligned} E_q[\log p(\boldsymbol{z}|\theta)] &= \sum_{n=1}^N E_q[\log p(z_n|\theta)]\\ &= \sum_{n=1}^N E_{q(\theta,z_n|\gamma,\eta)}[\log(z_n|\theta)]\\ &= \sum_{n=1}^N \sum_{k=1}^K q(z_{nk}|\eta)E_{q(\theta|\gamma)}[\log \theta_k]\\ &= \sum_{n=1}^N \sum_{k=1}^K \eta_{nk} \left[\varPsi(\gamma_k)-\varPsi\left(\sum_{l=1}^K \gamma_l \right)\right] \end{aligned}\tag{20-53}$$

式中$\eta_{nk}$表示文档第n个位置的单词由第k个话题产生的概率，$\gamma_k$表示第k个话题的狄利克雷分布参数。最后一步请参考这里的狄利克雷分布的相关性质。

第三项推导，求$E_q[\log p(\boldsymbol{w}|\boldsymbol{z},\varphi)]$，是关于分布$q(\theta,\boldsymbol{z}|\gamma,\eta)$的数学期望。

$$\begin{aligned} E_q[\log p(\boldsymbol{w}|\boldsymbol{z},\varphi)] &= \sum_{n=1}^N E_q[\log p(w_n|z_n,\varphi)]\\ &= \sum_{n=1}^N E_{q(z_n|\eta)}[\log p(w_n|z_n,\varphi)]\\ &= \sum_{n=1}^N \sum_{k=1}^K q(z_{nk}|\eta)\log p(w_n|z_n,\varphi)\\ &= \sum_{n=1}^N \sum_{k=1}^K \sum_{v=1}^V \eta_{nk}w_n^v \log \varphi_{kv} \end{aligned}\tag{20-53}$$

式中$\eta_{nk}$表示文档第n个位置的单词由第k个话题产生的概率，$w_n^v$在第n个位置的单词是单词集合的第v个单词时为1，否则取值为0，$\varphi_{kv}$表示第k个话题生成单词集合中第v个单词的概率。

第四项推导，求$E_q[\log q(\theta|\gamma)]$，是关于分布$q(\theta,\boldsymbol{z}|\gamma,\eta)$的数学期望。

由于$\theta \sim \mathrm{Dir}(\gamma)$，类似于(20-50)，可以得到：

$$E_q[\log q(\theta|\gamma)] = \log \Gamma \left(\sum_{l=1}^K \gamma_l\right)-\sum_{k=1}^K \log \Gamma(\gamma_k)+\sum_{k=1}^K (\gamma_k-1)\left[\Psi(\gamma_k)-\Psi\left(\sum_{l=1}^K \gamma_l\right)\right] \tag{20-54}$$

式中$\gamma_k$表示第k个话题的狄利克雷分布参数。

第五项推导，求$E_q[\log q[\boldsymbol{z}|\eta]]$，是关于分布$q(\theta,\boldsymbol{z}|\gamma,\eta)$的数学期望。

$$\begin{aligned} E_q[\log q[\boldsymbol{z}|\eta]] &= \sum_{n=1}^N E_q[\log q[z_n|\eta]]\\ &=\sum_{n=1}^N E_{q(z_n|\eta)}[\log q[z_n|\eta]]\\ &=\sum_{n=1}^N\sum_{k=1}^K E_{q(z_{nk}|\eta)}[\log q[z_{nk}|\eta]]\\ &=\sum_{n=1}^N\sum_{k=1}^K \eta_{nk}\log \eta_{nk} \end{aligned}\tag{20-55}$$

式中$\eta_{nk}$表示文档第n个位置的单词由第k个话题产生的概率，$\gamma_k$表示第k个话题的狄利克雷分布参数。

变分参数估计

• 参数$\eta$

  首先，通过证据下界最优化估计参数$\eta$。$\eta_{nk}$表示第n个位置的单词是由第k个话题生成的概率。

  考虑式(20-47)关于$\eta_{nk}$的最大化，$\eta_{nk}$满足约束条件$\sum_{l=1}^K \eta_{nl}=1$。使用拉格朗日乘子法，得：

  $$L_{[\eta_{nk}]} = \eta_{nk }\left[\varPsi(\gamma_k)-\varPsi\left(\sum_{k=1}^K \gamma_l\right)\right]+\eta_{nk}\log \varphi_{kv}-\eta_{nk}\log \eta_{nk}+\lambda_n\left(\sum_{l=1}^K\eta_{nl}-1\right) \tag{20-56}$$

这里$\varphi_{kv}$是(在第n个位置)由第k个话题生成第v个单词的概率。

对$\eta_{nk}$求偏导数得:

$$\frac{\partial L}{\partial{\eta_{nk}}} = \varPsi(\gamma_k)-\varPsi\left(\sum_{l=1}^K \gamma_l\right) +\log \varphi_{kv}-\log \eta_{nk}-1+\lambda_n \tag{20-57}$$

令偏导数为0，得到参数$\eta_{nk}$的估计值：

$$\eta_{nk} \propto \varphi_{kv}\exp\left[\varphi(\gamma_k)-\varphi\left(\sum_{l=1}^K \gamma_l \right)\right]\tag{20-58}$$

• 参数$\gamma$

  接着，通过证据下界最优化估计参数$\gamma$。$\gamma_k$是第k个话题的狄利克雷分布参数。

  考虑式(20-47)关于$\gamma_k$得最大化：

  $$\begin{aligned} L_{[\gamma_k]} = &\sum_{k=1}^K(\alpha_k-1)\left[\varPsi(\gamma_k)-\varPsi\left(\sum_{l=1}^K \gamma_l\right)\right]+\sum_{n=1}^N\sum_{k=1}^K \eta_{nk}\left[\varPsi(\gamma_k)-\varPsi\left(\sum_{l=1}^K \gamma_l\right)\right] - \\ &\log\Gamma\left(\sum_{l=1}^K \gamma_l \right)+\log \Gamma(\gamma_k)-\sum_{k=1}^K(\gamma_k-1)\left[\varPsi(\gamma_k)-\varPsi\left(\sum_{l=1}^K\gamma_l\right)\right] \end{aligned} \tag{20-59}$$

简化为：

$$L_{[\gamma_k]} = \sum_{k=1}^K\left[\varPsi(\gamma_k)-\varPsi\left(\sum_{l=1}^K \gamma_l\right)\right]\left(\alpha_k+\sum_{n=1}^N\eta_{nk}-\gamma_{k}\right)-\log\Gamma\left(\sum_{l=1}^K\gamma_l \right)+\log\Gamma(\gamma_k)\tag{20-60}$$

对$\gamma_k$求偏导数得：

$$\frac{\partial L}{\partial \gamma_k} = \left[\varPsi^{'}(\gamma_k)-\varPsi^{'}\left(\sum_{l=1}^K \gamma_l\right)\right]\left(\alpha_k+\sum_{n=1}^N \eta_{nk}-\gamma_k\right) \tag{20-61}$$

令偏导数为0，求解得到参数$\gamma_k$的估计值：

$$\gamma_k = \alpha_k+\sum_{n=1}^N \eta_{nk} \tag{20-62}$$

据此 ，得到由坐标上升法估计变分参数的方法，具体算法如下：

算法20.4(LDA的变分参数估计算法)

1. 初始化：对所有k和n，$\eta_{nk}^{(0)} = 1/K$

2. 初始化：对所有k,$\gamma_k=\alpha_k+N/K$

3. 重复

   1. 对n=1到N

      1. 对k=1到K

         $$\eta_{nk}^{(t+1)} = \varphi_{kv}\exp\left[\varphi(\gamma_k^{(t)})-\varphi\left(\sum_{l=1}^K \gamma_l^{(t)} \right)\right]$$

      2. 规范化$\eta_{nk}^{(t+1)}$使其和为1

   2. $$\gamma^{(t+1)} = \alpha+\sum_{n=1}^N\eta_n^{(t+1)}$$

4. 直到收敛

模型参数的估计

• 参数$\varphi$

  给定一个文本集合$D = \{\boldsymbol{w}_1,\dots,\boldsymbol{w}_m,\dots,\boldsymbol{w}_M\}$，模型参数估计对所有文本同时进行。

  首先，通过证据下界的最大化估计$\varphi$。$\varphi_{kv}$表示第gek话题生成单词集合第v个单词的概率。

  将式(20-47)扩展到所有文本，并考虑关于$\varphi$的最大化。满足K个约束条件:

  $$\sum_{v=1}^V \varphi_{kv} =1, k=1,2,\dots,K$$

从而得到对应的拉格朗日函数：

$$L_{[\beta]} = \sum_{m=1}^M\sum_{n=1}^{N_m}\sum_{k=1}^K\sum_{v=1}^V \eta_{mnk}w_{mn}^v\log\varphi_{kv}+\sum_{k=1}^K\lambda_k\left(\sum_{v=1}^V \varphi_{kv}-1\right) \tag{20-63}$$

求$\varphi_{kv}$求偏导数并令其为0，归一化求解，得到参数$\varphi_{kv}$的估计值为：

$$\varphi_{kv} = \sum_{m=1}^m\sum_{n=1}^{N_m} \eta_{mnk}w_{mn}^v \tag{20-64}$$

其中，$\eta_{mnk}$为第m个文本的第n个单词属于第k个话题的概率，$w_{mn}^v$ 在第m个文本的第n个单词是单词集合的第v个单词时取值为1，否则为0.

• 参数$\alpha$

  接着，通过证据下界的最大化估计参数$\alpha$。$\alpha_k$表示第k个话题的狄利克雷分布参数。

  将式(20-47)扩展到所有文本，并考虑关于$\alpha$的最大化：

  $$L_{[\alpha]} = \sum_{m=1}^M \left\{\log\Gamma\left(\sum_{l=1}^K\alpha_l\right)-\sum_{k=1}^K\log\Gamma(\alpha_k)+\sum_{k=1}^K(\alpha_k-1)\left[\varPsi(\gamma_{mk})-\varPsi\left(\sum_{l=1}^K\gamma_{ml}\right)\right]\right\} \tag{20-65}$$

对$\alpha_k$求偏导数得：

$$\frac{\partial L}{\partial \alpha_k} = M\left[\varPsi\left(\sum_{l=1}^K\alpha_l\right)-\varPsi(\alpha_k)\right]+\sum_{m=1}^M\left[\varPsi(\gamma_{mk})-\varPsi\left(\sum_{l=1}^K\gamma_{ml}\right)\right] \tag{20-66}$$

再对$\alpha_l$求偏导数，得：

$$\frac{\partial^2L}{\partial \alpha_k\partial \alpha_l} = M\left[\varPsi^{'}\left(\sum_{l=1}^K\alpha_l\right)-\delta(k,l)\varPsi^{'}(\alpha_k)\right] \tag{20-67}$$

这里$\delta(k,l)$是delta函数。

式2(0-66)和式(20-67)分别是函数(20-65)对变量$\alpha$的梯度$g(\alpha)$和Hessian矩阵$H(\alpha)$。

应用牛顿法求该函数的最大化。用以下公式迭代，得到参数$\alpha$的估计值。

$$\alpha_{new} = \alpha_{old}-H(\alpha_{old})^{-1}g(\alpha_{old}) \tag{20-68}$$

​ 据此，得到估计参数$\alpha$的算法。

算法总结

根据上面的推导，给出LDA的变分EM算法：

算法20.5(LDA的变分EM算法)

输入：给定文本集合$D = \{\boldsymbol{w}_1,\dots,\boldsymbol{w}_m,\dots,\boldsymbol{w}_M\}$；

输出：变分参数$\gamma,\eta$，模型参数$\alpha,\varphi$。

交替迭代E步和M步，直到收敛。

1. E步

   固定模型参数$\alpha,\varphi$，通过关于变分参数$\gamma,\eta$的证据下界的最大化，估计变分参数$\gamma,\eta$。具体见算法20.4

2. M步

   固定变分参数$\gamma,\eta$，通过关于模型参数$\alpha,\varphi$的证据下界的最大化，估计模型参数$\alpha,\varphi$。具体见式(20-64)和式(20-68)。

   根据变分参数($\gamma,\eta$)可以估计模型参数$\theta=(\theta_1,\dots,\theta_m,\dots,\theta_M)$，$\boldsymbol{z}=(\boldsymbol{z}_1,\dots,\boldsymbol{z}_m,\dots,\boldsymbol{z}_M)$。

参考文献

• Parameter estimation for text analysis
• LDA-math-LDA 文本建模