此 LDA 是隐含狄利克雷分布模型，区别于线性判别分析这个降维模型 LDA。

原理

LDA 衍生于 pLSA，在后者的原理中，每个文档有一个待估计的 p(z|d) 分布，而每个主题有一个待估计的 p(w|z)分布，它们分别被简称为 θ 和 φ。
LDA 同样如此，不过它站在贝叶斯估计的角度，认为参数 θ 和 φ 本身应该是随机的，所以为它们引入了先验随机分布。
引入什么样的先验分布也是有考究的，因为 θ 和 φ 都是多项分布，则引入狄利克雷 Dir 分布作为先验有一个良好的性质：在观察到一些数据之后，后验分布同样是 Dir 分布，无论在表示还是计算上都非常方便。

文档生成的过程：

有一个更加形象的过程解释：

概率密度估计

为了优化，我们总要找一个目标，一般来说我们会去最大化/最小化一个目标，比如极大似然估计，最小化负对数似然。
类似于 pLSA 的优化，我们也可以计算数据的似然函数，然后最大化它。也采用 EM 算法去实现。但是在 E-step 中要使用变分推断来计算隐含变量的后验概率。
因此，我们转变目标，对目标概率分布进行采样，然后用样本的频率来近似真实的概率。
回顾一下，我们的目标是估计这两个参数 θ (p(z|d)) 和 φ（p(w|z)）。
我们观察到的是词的向量W（N 个文档，第 i 个文档中有 Ni 个词），它的概率分布是 p(W)，这是不完全数据的分布。而完全数据的分布是含带隐变量的 p(W,Z)，注意 Z 和 W 是同长度的向量，每个词有自己的隐含主题。再进一步，我们要估计的是在可观察数据下隐变量的条件概率 p(Z|W)。注意，上面的概率表达都省略了先验分布 α 和 β，它们应该出现在条件概率形式的右边，比如 p(W| α,β)。

吉布斯采样原理

吉布斯采样（Gibbs Sampling）是马尔科夫链蒙特卡洛采样（MCMC）的一种方法，针对在高维空间（即有多个随机变量）的情况。

MCMC

MCMC 告诉我们，一个随机变量有多个状态，如果状态之间的转移概率是恒定的，且当前步的状态只依赖于前一步的状态，那状态转移可以由转移矩阵 P 来表示。神奇的是，无论初始状态是什么，按照 P 来转移，经过无限步转移之后，状态都会收敛到一个稳态 π。也就是说，如果要给一个随机分布 q 做采样，只需要找到一个合适的转移矩阵 P，使最终的稳态 π 就是 q，那就可以在稳态之后继续按照 P 来转移，从而获得状态的随机变化样本。

那么问题来了，P 怎么找？注意到，如果两个状态 i 和 j 满足这样的条件 π(i)P(j|i) = π(j)P(i|j)，则稳态就是 π，这称作细致平稳条件。形象地解释，从任意状态 i 的输出跟它的输入相等，就很稳。也就是说，P 和 π 不见得就一定满足这个条件，只是说满足细致平稳条件是一种有良好性质的特例。那么，让 P(j|i) = q(j), P(i|j) = q(i) 就好了吗？（TODO：有点难回答，这个问题跟为何不直接按照 p(i)来采样是等价的）

MCMC利用细致平稳条件来构造转移矩阵 P：给定一个普通马氏链 Q，即不满足细致平稳条件 q(i)Q(j|i) = q(j)Q(i|j)，那么可以通过在等式两边各乘上一个因子，让它变成 q(i)Q(j|i)a(j|i) = q(j)Q(i|j)a(i|j)，a 的取值是 a(j|i) = q(j)Q(i|j)，这样相当于构建了一个满足细致平稳的 Q'，Q'(i|j) = Q(i|j)a(i|j) = Q(i|j)q(i)Q(j|i)。实际操作的时候，因子 a 是拒绝采样的接受率。也就是说，在采样时，先在均匀采样上采样一个值 u，接下来如果 u < a 则接受新的样本，否则维持旧样本。

MH 采样

普通 MCMC 采样有个问题，就是a可能过小，即拒绝的比例很大，采样效率很低。MH 采样指出，可以同比例扩大 a(i|j)和 a(j|i)，细致平稳条件依然满足。因此 a 尽可以扩大到 1 去，如果超过 1 就取 1（TODO：扩大 a，并且超过 1 就取 1，是如何做到让 Q‘ 依然满足概率定义的？即 Σ_jQ‘(j|i) = 1 不会破坏吗）

吉布斯采样

吉布斯采样则指出，在高维情况下，维持所有其他变量相同，仅仅改变一个维度的值，有另一个方法来维持细致平稳条件。以二维为例，两个点 A (x1, y1), B(x1, y2), 注意它们横坐标相同。 根据贝叶斯定理，有：

也就是说，如果保持 x 不变，转移概率采用 p(y|x)，就满足细致平稳条件。那可以在每采样一个新的点时，在现在样本点上，固定其他轴，而改变一个轴，采用对应的转移概率进行转移。吉布斯采样过程需要有一个 burn-in 阶段（实际 MCMC 采样都需要）

LDA 中的吉布斯采样

LDA 对概率 p(Z|W) 进行采样，吉布斯采样要求只改变一个维度，那么只改变一个单词 wi 的 topic zi，即转移概率是 p(zi=k|Z~i,W)，Z~i 就是刨除词 ci 的其他词的topic 构成的向量。这个转移概率有一个非常简洁的结果：

而 公式的结尾也有非常简洁的物理表示：

这种简洁得益于 θ 和 φ 是多项分布，且它们的先验分布是狄利克雷分布。这也形象地解释了 LDA 对于文本单词的生成过程的假设，先按照 θ 生成主题，再按照主题生成词。

LDA 的训练过程总结如下

优化实践

在数据量巨大的情况下，内存和 CPU 都消耗巨大。这分为几个方面：

1. 文档-词的矩阵。在大文档的情况下，要将文档全部载入内存是很难的。如果要从磁盘直接读取而不缓存在内存，则有很大的磁盘 IO 开销。当然这可以通过另开 IO 线程来实现预读取。
2. 模型参数。θ 和 φ 的体积分别是 文档数主题数，主题数词典大小，这是非常巨大的，尤其是 θ 的文档数这个因子。有时甚至能够撑爆内存。
3. 每一次采样的时间复杂度是 O(K)，因为需要计算归一化的概率，也需要在均匀采样之后看采样概率落在了 K 个区间的哪一个

并行化

单个线程改多个线程，单个机器扩展到多个机器，通过引入多线程和多机器，我们可以均摊内存和 CPU 需求。具体的：

1. 划分文档-词矩阵，横纵二维划分，两个划分块之间的数据不同，即要么文档 id 不同，要么词 id 不同，要么都不同。这种数据并行，可以缓解一定的文档规模量的问题，数据可以加载进内存。同时，也仍然实现了另开线程来预读取数据的功能，满足超大量级的文档。
2. 划分参数矩阵，θ 和 φ 矩阵也被横纵二维划分。在文档和词的维度上，划分的方式和文档-词矩阵一样。在 K 这个维度上，实现均匀分配。如此，参数矩阵也可以尽可能放入内存。当然，为了应对超大量级的挑战，实现基于磁盘 IO 的参数读取模式，也是必不可少的。此外，θ 和 φ 可以稀疏存储，因为他们的稀疏特点很明显。

sparse LDA

注意到一次采样的时间复杂度是 O(K)，但 θ 和 φ 其实非常稀疏。试想，一个文档的主题应该常常在个位数，不至于达到 K 个那么多，主题下词的分布也应该是远小于词典大小的。通过继续推导 p(zi=k|Z~i,W) = θ(mk) · φ(kt) 这个公式，可以将公式分解成三个部分 e/f/g，可以先均匀采样落入这三个区间中的一个，再根据对应的公式继续做第二次采样，平均意义上讲，这样的采样复杂度是 O(1)。具体地参考 sparse LDA 相关文档。