LDA

LDA（Latent Dirichlet Allocation）

LDA 的论文作者是戴维·布雷（David Blei）、吴恩达和迈克尔·乔丹（Michael Jordan）。

产生式模型（Generative Model）

判别式模型常常直接对 Y 的产生过程（Generative Process) 进行描述，而对特征信息本身不予建模。这使得判别式模型天生就成为构建分类器或者回归分析的有利工具。而产生式模型则要同时对 X 和 Y 建模，这使得产生式模型更适合做无标签的数据分析，比如聚类。当然，因为产生式模型要对比较多的信息进行建模，所以一般认为对于同一个数据而言，产生式模型要比判别式模型更难以学习。

一般来说，产生式模型希望通过一个产生过程来帮助读者理解一个模型。注意，这个产生过程本质是描述一个联合概率分布（Joint Distribution）的分解过程。也就是说，这个过程是一个虚拟过程，真实的数据往往并不是这样产生的。这样的产生过程是模型的一个假设，一种描述。任何一个产生过程都可以在数学上完全等价一个联合概率分布。

LDA 的产生过程描述了文档以及文档中文字的生成过程。在原始的 LDA 论文中，作者们描述了对于每一个文档而言有这么一种生成过程：

首先，从一个全局的泊松（Poisson）参数为β的分布中生成一个文档的长度 N；从一个全局的狄利克雷（Dirichlet）参数为α的分布中生成一个当前文档的θ；然后对于当前文档长度 N 的每一个字执行以下两步，一是从以θ为参数的多项（Multinomial）分布中生成一个主题（Topic）的下标（Index）z_n；二是从以φ和 z 共同为参数的多项分布中产生一个字（Word）w_n。

从这个描述我们可以马上得到这些重要的模型信息。第一，我们有一个维度是 K 乘以 V 的主题矩阵（Topic Matrix）。其中每一行都是一个φ，也就是某一个生成字的多项分布。当然，这个主题矩阵我们在事先并不知道，是需要学习得到的。另外，对每一个文档而言，θ是一个长度为 K 的向量，用于描述当前文档在 K 个主题上的分布。产生过程告诉我们，我们对于文档中的每一个字，都先从这个θ向量中产生一个下标，用于告诉我们现在要从主题矩阵中的哪一行去生成当前的字。

这个产生模型是原论文最初提出的，有两点值得注意。

第一，原始论文为了完整性，提出了使用一个泊松分布来描述文档的长度这一变化信息。然而，从模型的参数和隐变量的角度来说，这个假设并不影响整个模型，最终作者在文章中去除了这个信息的讨论。在主题模型的研究中，也较少有文献专注这个信息。

第二，原始论文并没有在主题矩阵上放置全局的狄利克雷分布作为先验概率分布。这一缺失在后续所有的主题模型文献中得到修正。于是今天标准的 LDA 模型有两类狄利克雷的先验信息，一类是文档主题分布的先验，参数是α，一类是主题矩阵的先验，参数是β。

LDA 并不是所谓的狄利克雷 - 多项（Dirichlet-Multinomial）聚类模型。这里，LDA 对于每个文档的每一个字都有一个主题下标。也就是说，从文档聚类的角度来看，LDA 是没有一个文档统一的聚类标签，而是每个字有一个聚类标签，在这里就是主题。这也是 LDA 是 Mixed-Membership 模型的原因——每个字有可能属于不同的类别、每个文档也有可能属于不同的类别。

LDA 很类似在 2000 年初提出的另外一类更简单的主题模型——概率隐形语义索引（Probabilistic Latent Semantic Indexing），简称 PLSI。其实从本质上来说，LDA 借用了 PLSI 的基本架构，只不过在每个文档的主题分布向量上放置了狄利克雷的先验概率，以及在主题矩阵上放置了另外一个狄利克雷的先验概率。

尽管看上去这是一个非常小的改动，但是这样做的结果则是 LDA 的参数个数并不随着文档数目的增加而增加。那么，相对于 PLSI 来说，LDA 并不容易对训练数据过度拟合（Overfitting）。

值得注意的，原始文章说过度拟合主要是指，对于 PLSI 而言，文档的主题分布向量是必须需要学习的，而这个向量对于 LDA 是可以被忽略或者说是并不需要保存的中间变量。然而在实际的应用中，我们其实常常也需要这个向量的信息，因此这部分对于过度拟合的讨论在后来的应用中并没有特别体现。

LDA 虽然从某种意义上来说仅仅是在 PLSI 上增加了先验信息。然而，这一个改动为整个模型的训练学习带来了非常大的挑战。应该说，整个 LDA 的学习直到模型提出后近 10 年，才随着随机变分推理（Stochastic Variational Inference）的提出以及基于别名方法（Alias Method）的抽样算法（Sampling Method）而得以真正的大规模化。一直以来，LDA 的训练学习都是一件很困难的事情。

不像 PLSI 可以依靠最大期望（EM）算法得以比较完美的解决，传统上，LDA 的学习属于贝叶斯推理（Bayesian Inference），而在 2000 年代初期，只有马尔科夫蒙特卡洛（Markov chain Monte Carlo），简称 MCMC，以及迈克尔·乔丹等人推崇的变分推理（Variational Inference），简称 VI，作为工具可以解决。这篇文章因为出自迈克尔的实验室，当仁不让地选择了 VI。比较有意思的是，后续大多数 LDA 相关的论文都选择了 MCMC 为主的吉布斯（Gibbs）采样来作为学习算法。

从最高的层次上来理解，VI 是选取一整组简单的、可以优化的所谓变分分布（Variational Distribution）来逼近整个模型的后验概率分布。当然，由于这组分布的选取，有可能会为模型带来不小的误差。不过好处则是这样就把贝叶斯推理的问题转化成了优化问题。

从 LDA 的角度来讲，就是要为θ以及 z 选取一组等价的分布，只不过更加简单，更不依赖其他的信息。在 VI 进行更新θ以及 z 的时候，算法可以根据当前的θ以及 z 的最新值，更新α的值（这里的讨论依照原始的 LDA 论文，忽略了β的信息）。整个流程俗称变分最大期望（Variational EM）算法。

文章在 TREC AP 的文档数据中做了实验。首先，作者们使用了一个叫困惑度（Perplexity）的评估值来衡量文档的建模有效程度，这个值越低越好。LDA 在好几个数据集中都明显好于 PLSI 以及其他更加简单的模型。从这篇文章之后，主题模型的发展和对比都离不开困惑度的比较，也算是开启了一个新时代。

然后，作者们展示了利用 LDA 来做文档分类，也就是利用文档主题向量来作为文档的特征，从而放入分类器中加以分类。作者们展示了 LDA 作为文档分类特征的有力证据，在数据比较少的情况下优于文本本身的特征。不过总体说来，在原始的 LDA 论文中，作者们并没有特别多地展现出 LDA 的所有可能性。

LDA 就是一个出色的无监督学习的文本挖掘模型。这个模型在过去的十年里开启了主题模型（Topic Model）这个领域。

LDA 的扩展

LDA 只是对文档的文字信息本身进行建模。但是绝大多数的文档数据集还有很多额外的信息，如何利用这些额外信息，就成为了日后对 LDA 扩展的最重要的工作。

第一个很容易想到的需要扩展的信息就是作者信息。

论文《用于作者和文档信息的作者主题模型》（The author-topic model for authors and documents）[1]，这是最早利用额外信息到 LDA 模型中的扩展模型。文章提出的模型叫作“作者 LDA”（Author LDA）。这个模型的主要思想是，每篇文档都会有一些作者信息，我们可以把这些作者编码成为一组下标（Index）。对于每一个文档来说，我们首先从这组作者数组中，选出一个当前的作者，然后假定这个作者有一组相对应的主题。这样，文档的主题就不是每个文档随机产生了，而是每个作者有一套主题。这个时候，我们从作者相对应的主题分布中取出当前的主题，然后再到相应的语言模型中，采样到当前的单词。

可以看到，作者 LDA 和普通的 LDA 相比，最大的不同就是主题分布不是每个文档有一个，而是每个作者有一个。这个主题分布决定着当前的单词是从哪一个语言模型中采样的单词。作者 LDA 也采用吉布斯采样的方法学习，并且通过模型的学习之后，能够看得出不同作者对于文档的影响。

从作者 LDA 之后，大家看出了一种扩展 LDA 的思路，那就是依靠额外的信息去影响主题分布，进而影响文档字句的选择。这种扩展的方法叫作“上游扩展法”（Upstream）。什么意思呢？就是说把希望对模型有影响的信息，放到主题分布的上游，去主动影响主题分布的变化。这其实是概率图模型的一种基本的思路，那就是把变量放到这个产生式模型的上游，使得下游的变量受到影响。

那你可能要问，有没有把需要依赖的变量放到下游的情况呢？答案是肯定的。我们再来看一篇论文《同时进行图像分类和注释》（Simultaneous image classification and annotation）[2]，这篇文章就发明了一种方法。具体来说，文章希望利用 LDA 到多模数据领域（Multiple Modal）。也就是数据中可能有文字，也可能有图像，还可能有其他信息。在这样的多模数据的情况下，如何让 LDA 能够对多种不同的数据进行建模呢？

这里面的基本思路就是认为所有的这些数据都是通过主题分布产生的。也就是说，一个数据点，我们一旦知道了这个数据点内涵的主题（比如到底是关于体育的，还是关于金融的），那么我们就可以产生出和这个数据点相关的所有信息，包括文字、图像、影音等。

具体到这篇文章提出的思路，那就是这组数据的图像标签以及图像所属的类别都是主题产生的。我们可以看到，和之前的作者 LDA 的区别，那就是其他信息都是放在主题变量的下游的，希望通过主题变量来施加影响。

这两种模型代表了一系列丰富的关于 LDA 的扩展思路，那就是如何把扩展的变量设置在上游或者是下游，从而能够对主题信息产生影响或者是受到主题信息的影响。

除此以外，LDA 的另外一大扩展就是把文档放到时间的尺度上，希望去分析和了解文档在时间轴上的变化。这就要看经典的论文《动态主题模型》（Dynamic topic models）[3]。这篇论文最后获得了 ICML 2010 年的最佳贡献奖。那么，我们怎么修改 LDA 使其能够理解时间的变化呢？很明显，还是需要从主题分布入手，因为主题分布控制了究竟什么文字会被产生出来。因此，我们可以认为主题分布会随着时间的变化而变化。

在之前的模型中，我们已经介绍了，每个文档的主题分布其实来自一个全局的狄利克雷（Diriclet ）先验分布。那么，我们可以认为不同时间的先验分布是不一样的，而这些先验分布会随着时间变化而变化。怎么能够表达这个思想呢？作者们用到了一个叫“状态空间”（State-Space）的模型。简而言之，状态空间模型就是把不同时间点的狄利克雷分布的参数给串起来，使得这些分布的参数会随着时间的变化而变化。把一堆静态的参数用状态空间模型串接起来，可以说是这篇文章开创的一个新的思维。

LDA 模型训练

LDA 模型中最重要的未知变量就是每个单词对应的主题下标（Index）或者说是主题“赋值”（Assignment）。这个主题下标是从每个文档对应的主题分布中“采样”得来的。每个文档的主题分布本身也是一个未知的多项式分布，用来表达当前这个文档的所属主题，比如有多少百分比属于运动、有多少百分比属于金融等等。这个分布是从一个全局的狄利克雷（Diriclet）分布中产生的。狄利克雷分布在这里起到了超参数的作用，其参数的取值往往也是未知的。但是我们可以根据一些经验值对其进行设置。除了每个文档的主题分布和主题赋值以外，我们还需要对全局的主题语言模型进行估计。这些语言模型直接决定了，各类词语出现的概率是多少。

流行的 LDA 训练方法有两个，一个是基于 吉布斯采样（Gibbs Sampling）的随机方法，一个是基于变分推断（Variational Inference）的确定性方法（Deterministic）。这两种方法的初始形态都无法应对大型数据。这里我们来简要介绍一下这两种方法。

吉布斯采样主要是针对主题赋值进行采样，最开始是完全随机的结果，但是慢慢会收敛到参数的后验概率的真值。这里面比较慢的一个原因，是这个收敛过程可能需要几百到几千个不等的迭代。同时，吉布斯采样只能一个文档一个文档进行，所有的数据结构都需要在采样的过程中进行更改。这个过程比较慢的另外一个原因，是吉布斯采样的核心是如何对一个离散分布进行采样。而离散分布采样本身，如果在分布的参数变化的情况下，最好能够达到 O（KlogK），这里 K 是主题的数目。因此，从原理上来说，这也是阻碍吉布斯采样能够扩展到大型数据的一个原因。

变分推断的思路则和吉布斯采样很不一样。它是把对隐含参数的估计问题变成一个确定性的优化问题，这样我们就可以利用种种优化算法来解决贝叶斯推断的问题。不过和吉布斯采样相比，变分推断存在一个问题，因为这种方法并不是解决原来的优化问题，因此新的优化问题可能并不能带来原来问题的解。同时，变分推断也需要一个文档一个文档单独处理，因此推广到大规模数据上有其局限性。

LDA 的大规模优化算法

首先，我们来看吉布斯采样。吉布斯采样慢的一个核心就是我们刚才说的，需要从一个离散分布中采样出一个样本，在我们这个例子中也就是每个单词的主题赋值。那么，有没有什么方法让这个步骤加速呢？答案是，有的。

在 KDD 2009 上发表了一篇论文《应用于流文档集合的主题模型推断的高效方法》（Efficient methods for topic model inference on streaming document collections）[1]，算是在这方面取得突出成绩的一个重要参考文献。这篇论文的主要贡献就是，对原有的采样公式进行了一个比较仔细的分析。

作者们发现，原来的吉布斯采样公式可以被分解为几个部分：和全局的语言模型有关、和文档有关以及和当前需要采样的单词有关。这是一个非常有价值的观察，之后很多加速吉布斯采样的工作基本上都采用了类似的思路，也就是试图把原始的吉布斯采样公式拆分成好几个组成部分，并且每一个部分所代表数据的变化率是不一样的。

以这篇文章提出的方法来说，全局语言模型在每个文档的采样过程中是不变的，于是这部分的计算不需要每个单词都重算。同理，只与文档相关的部分，也可以每个单词的采样过程中，只算一次，而不需要每个主题算一次。在这样一个简化了的流程里，采样速度得到了极大的提升。

在这篇文章之后，通过吉布斯采样这个方法，LDA 的采样速度还是没有得到明确的提升，直到《降低主题模型的采样复杂度》（Reducing the sampling complexity of topic models）[2]这篇论文的出现。这篇论文获得了 KDD 2014 年的最佳论文奖。文章的思想还是针对吉布斯采样的公式，不过这一次，拆分的方法略不一样。作者们把采样的公式拆分成了与当前文档有关系的一部分，以及和当前文档没关系的全局语言模型的部分。

同时，作者们提出了一个“Alias 方法”（Alias Method），简称 A 算法，来加速采样。这个 A 算法其实并不是作者们为了 LDA 发明的，而是一个普遍的可以对离散分布采样的一个算法。A 算法的核心思想是，如果我们要针对一个分布进行反复采样，那么就可以建立一种数据结构，使得这种采样只有在第一遍的时候有一定的计算成本，而后都会以 O(1) 的成本进行采样。这个方法极大地加速了 LDA 通过吉布斯采样的效率。值得一提的是，在这篇论文之后，很多研究者发布了一系列的后续工作。

那么在变分推断的道路上，有没有什么方法能够加速呢？答案依然是肯定的。

这方面的代表作无疑就是论文《LDA 的在线学习》（Online learning for Latent Dirichlet Allocation）[3]。

我们回到变分推断的场景中，把一个贝叶斯推断的问题变成了优化的问题。那么，在优化的场景里，是怎么针对大规模数据的呢？

在优化的场景里，特别是基于梯度（Gradient）的优化方法中，大数据的应用往往需要 SGD（Stochastic Gradient Descent，随机梯度下降）的方法。通俗地讲，就是在计算梯度的时候，我们不需要处理完所有的数据之后才计算一次梯度，而是针对每一个文档，都可以计算一次梯度的估计值。

作者们其实就是把这个思想给搬到了变分推断里。总的来说，新发明出来的变分推断其实就是希望能够推演出一种类似 SGD 的变分方法，这种方法在后来的很多论文中都有所应用。