【概述】
潜在狄利克雷分配 LDA 模型的学习是一个复杂的最优化问题，难以精确求解，只能近似求解，常用的求解方法有吉布斯抽样和变分推理，本文仅介绍使用吉布斯抽样进行 LDA 模型的学习
对于给定文本的集合 $D=\{\mathbf{w}_1,\mathbf{w}_2,\cdots,\mathbf{w}_M\}$，其中 $\mathbf{w}_m=(w_{m1},w_{m2},\cdots,w_{mN_m})$ 是第 $m$ 个文本，以 $\mathbf{w}$ 表示文本集合的单词序列，即：
在超参数 $\boldsymbol{\alpha},\boldsymbol{\beta}$ 已知的情况下，潜在狄利克雷分配 LDA 的学习就是推断：
- 话题序列集合 $\mathbf{z}=\{\mathbf{z}_{1},\mathbf{z}_{2},\cdots,\mathbf{z}_{M}\}$ 的后验概率分布，其中 $\mathbf{z}_{m}=(z_{m1},z_{m2},\cdots,z_{mN_m})$ 是第 $m$ 个文本的话题序列
- 参数 $\boldsymbol{\Theta}=\{\boldsymbol{\theta}_{1},\boldsymbol{\theta}_{2},\cdots,\boldsymbol{\theta}_{M}\}$，其中 $\boldsymbol{\theta}_{M}$ 是文本 $\mathbf{w}_m$ 的话题分布的参数
- 参数 $\boldsymbol{\phi}=\{\boldsymbol{\varphi}_{1},\boldsymbol{\varphi}_{2},\cdots,\boldsymbol{\varphi}_{K}\}$，其中 $\boldsymbol{\varphi}_{K}$ 是话题 $z_k$ 的单词分布的参数
也就是说，对联合概率分布 $p(\mathbf{w},\mathbf{z},\boldsymbol{\Theta},\boldsymbol{\phi}|\boldsymbol{\alpha},\boldsymbol{\beta})$ 进行估计，其中 $\mathbf{w}$ 是观测变量，$\mathbf{z},\boldsymbol{\Theta},\boldsymbol{\phi}$ 是隐变量
使用吉布斯抽样进行 LDA 的学习通常采用收缩的吉布斯抽样（Collapsed Gibbs sampling）方法，其基本思路是对隐变量 $\boldsymbol{\Theta},\boldsymbol{\phi}$ 积分，得到边缘概率分布 $p(\mathbf{w},\mathbf{z}|\boldsymbol{\alpha},\boldsymbol{\beta})$，再对后验概率分布 $p(\mathbf{z}|\mathbf{w},\boldsymbol{\alpha},\boldsymbol{\beta})$ 进行吉布斯抽样，得到分布 $p(\mathbf{z}|\mathbf{w},\boldsymbol{\alpha},\boldsymbol{\beta})$ 的样本集合，进而利用这个样本集合对参数 $\boldsymbol{\Theta},\boldsymbol{\phi}$ 进行估计，最终得到 LDA 模型 $p(\mathbf{w},\mathbf{z},\boldsymbol{\Theta},\boldsymbol{\phi}|\boldsymbol{\alpha},\boldsymbol{\beta})$ 的所有参数估计
【基本思想】
抽样分布的表达式
对于后验概率分布 $p(\mathbf{z}|\mathbf{w},\boldsymbol{\alpha},\boldsymbol{\beta})$，有：
由于分布相同，可以不予考虑，只考虑联合分布概率 $p(\mathbf{w},\mathbf{z}|\boldsymbol{\alpha},\boldsymbol{\beta})$，其可以分解为：
其中，两个因子 $ p(\mathbf{w}|\mathbf{z},\boldsymbol{\beta})$ 和 $p(\mathbf{z}|\boldsymbol{\alpha})$ 可分别进行处理
对于第一个因子 $ p(\mathbf{w}|\mathbf{z},\boldsymbol{\beta})$，由于 $p(\mathbf{w}|\mathbf{z},\boldsymbol{\phi})=\prod\limits_{k=1}^K\prod\limits_{v=1}^V\varphi_{kv}^{n_{kv}}$，故有：
其中，$\varphi_{kv}$ 是第 $k$ 个话题生成单词集合第 $v$ 个单词的概率，$\boldsymbol{n}_k=\{n_{k1},n_{k2},\cdots,n_{kV}\}$，$n_{kv}$ 是数据中第 $k$ 个话题生成第 $v$ 个单词的次数
对于第二个因子 $p(\mathbf{z}|\boldsymbol{\alpha})$，由于 $p(\mathbf{z}|\boldsymbol{\Theta})=\prod\limits_{m=1}^M\prod\limits_{k=1}^K\theta_{mk}^{n_{mk}}$，故有：
其中，$\theta_{mk}$ 是第 $m$ 个文本生成单词集合第 $k$ 个话题的概率，$\boldsymbol{n}_m=\{n_{m1},n_{m2},\cdots,n_{mK}\}$，$n_{mk}$ 是数据中第 $m$ 个文本生成第 $k$ 个话题的次数
因此，对于 $p(\mathbf{w},\mathbf{z}|\boldsymbol{\alpha},\boldsymbol{\beta})$ 就有：
故而有：
满条件分布的表达式
分布 $p(\mathbf{z}|\mathbf{w},\boldsymbol{\alpha},\boldsymbol{\beta})$ 的满条件分布可写为：
其中，$w_i$ 表示所有文本的单词序列的第 $i$ 个位置的单词，$z_i$ 表示单词 $w_i$ 对应的话题，$i=(m,n),i=1,2,\cdots,I$，$\mathbf{z}_{-i}=\{z_j:j\neq i\}$ ，$Z_{z_i}$ 表示分布 $p(\mathbf{z}|\mathbf{w},\boldsymbol{\alpha},\boldsymbol{\beta})$ 对变量 $z_i$ 的边缘化因子
上式可理解为在所有文本单词序列、其他位置话题序列给定条件下，第 $i$ 个位置的话题的条件概率分布
根据抽样分布的表达式，可推出：
其中，第 $m$ 个文本的第 $n$ 个位置的单词 $w_i$ 是单词集合的第 $v$ 个单词，其话题 $z_{i}$ 是话题集合的第 $k$ 个话题，$n_{kv}$ 是第 $k$ 个话题中第 $v$ 个单词的减去当前单词的计数，$n_{mk}$ 是第 $m$ 个文本中第 $k$ 个话题减去当前单词的话题的计数
算法的后处理
对于参数 $\boldsymbol{\Theta}=\{\boldsymbol{\theta}_m\}$ 的估计，根据 LDA 模型的定义，后验概率满足：
其中，$\boldsymbol{n}_m=\{n_{m1},n_{m2},\cdots,n_{mK}\}$ 是第 $m$ 个文本的话题的计数，$Z_{\boldsymbol{\theta}_m}$ 表示分布 $p(\boldsymbol{\theta}_m,\mathbf{z}_m|\boldsymbol{\alpha})$ 对变量 $\boldsymbol{\theta}_{m}$ 的边缘化因子
故而可以得到参数 $\boldsymbol{\Theta}=\{\boldsymbol{\theta}_m\}$ 的估计式：
对于参数 $\boldsymbol{\phi}=\{\boldsymbol{\varphi}_m\}$ 的估计，根据 LDA 模型的定义，后验概率满足：
其中，$\boldsymbol{n}_k=\{n_{mk},n_{k2},\cdots,n_{kV}\}$ 是第 $k$ 个话题的单词的计数，$Z_{\boldsymbol{\varphi}_m}$ 表示分布 $p(\boldsymbol{\varphi}_k|\mathbf{w},\mathbf{z},\boldsymbol{\beta}) $ 对变量 $\boldsymbol{\varphi}_{k}$ 的边缘化因子，$I$ 是文本集合单词序列 $\mathbf{w}$ 的单词总数
故而可以得到参数 $\boldsymbol{\phi}=\{\boldsymbol{\varphi}_m\}$ 的估计式：
基本流程
综上所述，可以总结 LDA 的吉布斯抽样的具体算法
对于给定的所有文本的单词序列 $\mathbf{w}$，每个位置上随机指派一个话题，整体构成所有文本的话题序列 $\mathbf{z}$，然后循环执行以下操作：在每个位置上计算在该位置上的话题的满条件概率分布，然后随机抽样，得到该位置的新的话题，分派给这个位置
这个条件概率分布由两个因子组成，第一个因子表示话题生成该位置的单词的概率，第二个因子表示该位置的文本生成话题的概率
整体准备两个计数矩阵：话题-单词矩阵 $N_{K\times V}=[n_{kv}]$、文本-话题矩阵 $N_{M\times K}=[n_{mk}]$，在每一个位置，对两个矩阵中该位置的已有话题的计数减 $1$，计算满条件概率分布，然后进行抽样，得到该位置的新话题，之后对两个矩阵中该位置的新话题的计数加 $1$，计算移到下一个位置
在燃烧期后得到的所有文本的话题序列，即条件概率分布的样本 $p(\mathbf{z}|\mathbf{w},\boldsymbol{\alpha},\boldsymbol{\beta})$
【算法流程】
输入：文本的单词序列 $\mathbf{w}=\{\mathbf{w}_1,\mathbf{w}_2,\cdots,\mathbf{w}_M\}$，其中 $\mathbf{w}_m=(w_{m1},w_{m2},\cdots,w_{mN_m})$ 是第 $m$ 个文本
输出：模型参数 $\boldsymbol{\Theta},\boldsymbol{\phi}$ 的估计值、文本的话题序列 $\mathbf{z}=\{\mathbf{z}_{1},\mathbf{z}_{2},\cdots,\mathbf{z}_{M}\}$ 的后验概率分布 $p(\mathbf{z}|\mathbf{w},\boldsymbol{\alpha},\boldsymbol{\beta})$ 的样本计数，其中 $\mathbf{z}_{m}=(z_{m1},z_{m2},\cdots,z_{mN_m})$ 是第 $m$ 个文本的话题序列
参数：超参数 $\boldsymbol{\alpha},\boldsymbol{\beta}$、话题个数 $K$
算法流程：
Step 1：设所有计数矩阵的元素 $n_{mk},n_{kv}$，计数向量的元素 $\boldsymbol{n}_m,\boldsymbol{n}_k$ 的初值为 $0$
Step 2：对所有文本 $\mathbf{w}_m,m=1,2\cdots,M$，第 $m$ 个文本中的所有单词 $w_{mn},n=1,2,\cdots N_m$
抽样话题：$z_{mn} = \mathbf{z}_{k} \sim \text{Mult}(\frac{1}{K})$
增加文本-话题计数：$n_{mk}=n_{mk}+1$
- 增加文本-话题和计数：$\boldsymbol{n}_m=\boldsymbol{n}_m+\mathbf{1}$
- 增加话题-单词计数：$n_{kv}=n_{kv}+1$
- 增加话题-单词和计数：$\boldsymbol{n}_k=\boldsymbol{n}_k+\mathbf{1}$
Step 3：循环执行以下操作，直到进入燃烧期
对所有文本 $\mathbf{w}_m,m=1,2\cdots,M$，第 $m$ 个文本中的所有单词 $w_{mn},n=1,2,\cdots N_m$
1）若当前的单词 $w_{mn}$ 是第 $v$ 个单词，话题指派 $z_{mn}$ 是第 $k$ 个话题，减少计数
2）按照满条件分布
进行抽样，得到新的第 $k’$ 个话题，分配给 $z_{mn}$
3）增加计数
4）得到更新的两个计数矩阵：话题-单词矩阵 $N_{K\times V}=[n_{kv}]$、文本-话题矩阵 $N_{M\times K}=[n_{mk}]$，表示后验概率分布 $p(\mathbf{z}|\mathbf{w},\boldsymbol{\alpha},\boldsymbol{\beta})$ 的样本计数
Step 4：利用得到的样本计数，计算模型参数 $\boldsymbol{\Theta},\boldsymbol{\phi}$ 的估计值
