LDA

1. What is LDA?

LDA一般被认为是两个概念的缩写，Linear Discriminant Analysis（线性判别分析）和Latent Dirichlet Allocation，本文讨论的内容是后者。LDA是PLSA模型的贝叶斯化，这个贝叶斯化极大地减少了参数的个数，从而在较小的语料集中获得较好地表现。
在了解LDA的原理之前，首先我们要看LDA是用来做什么的：假设我们有多个Document，同时指定要获取的Topic的数目，LDA会告诉我们每个Document归属于某个Topic的概率。根据这功能，我们其实是可以将文本按照topic进行聚类；除了document存在一个topic分布概率之外，每个topic下，所有的word也存在一定的概率分布。
LDA从矩阵的角度分析：原始矩阵为正的（词频或者TF-IDF值）分解成的两个矩阵，两个矩阵的每一行相加都为1，分别表示document在各个topic上的概率，以及topic在各个词上的概率。

2. How it works?

LDA对于document的形成是有如下的假设的：

根据Poisson分布，选择这篇document的字数。
根据Dirichlet分布，决定这篇文章所属的topic分布。每篇文章都是包括多个topics的，比如我写这篇blog时，选择的topic可能是LDA占60%，统计方法占20%，代码应用占20%。
接下来对于每个我在document中输入的词选择其所属的topic。词首先依概率归属于(LDA, 统计方法，代码应用) ，比如60%可能性选择到LDA。
对于我即将输入的这个属于LDA topic的词，它又有一定的概率分布（比如用词a可能性10%，词b为15%…）。

接下来，有了以上的假设。当我们使用LDA，来对一些documents进行分析时，假定我们选择了数目为K的topics，我们想要得到每篇document分别属于上述K的topics的概率，以及每个topic下的words分布。LDA实现的步骤如下：

遍历所有的documents，随机的选择each word in document归属于某个topic（这里是赋予topic的编号），这样我们就得到每篇document的topic distribution和每个topic的words distribution.
接下来我们再次进行遍历（遍历每篇document，每篇document的每个word），来改善上述的random的分布。首先定义：
- $P(topic \ t \ \| \ document \ d) = \frac{num \ of \ words \ belong \ to \ topic \ t}{num \ of \ words \ in \ document \ d}$ ，document下某topic的概率等于该document下属于该topic的词汇的出现概率
- $P(word \ w \ \| \ topic \ t) = \frac{num \ of \ word \ w}{num \ of \ words \ belong \ to \ topic \ t}$ ，即我们想到的第二个分布,这里是over all documents，属于topic t的word w的数目/所有属于topic t的word的出现总数。
用公式来表示 $P(word \ w \ \| \ document \ d) = P(word \ w \ \| \ topic \ t)*P(topic \ t \ \| \ document \ d)$ 。这样对于词w，在不同的topic下都可以计算出它的 $P(word \ w \ \| \ document \ d)$ 。这里我们设定一些策略来选择新的topic，在这些策略中，最常用的是Gibbs Sampling，其是一种依概率产生样本数据的方式。
重复上述，直到达到一个steady state（convergence），也就是Gibbs Sampling收敛。

此外，需要指出的是Gibbs Sampling是一个序列相关的算法，很难写成分布式，对于大规模数据，较难支撑。

3. Mathematics under the LDA

在理解了实践操作之后，我们尝试了解Gibbs Sampling的概念。

Gamma函数和Gamma分布：

$\Gamma(x) = \int_0^\infty t^{x-1}e^{-t} dt$

Gamma函数被设计出来，是因为其具有这样的性质： $\Gamma(n) = (n-1)!$

我们稍作变换，可以得出最简单的Gamma分布的密度函数:

$\int_0^\infty \frac{x^{\alpha - 1}e^{-x}}{\Gamma(\alpha)} dx= 1$ $Gamma(x \| \alpha) = \frac{x^{\alpha - 1}e^{-x}}{\Gamma(\alpha)}$

接着，我们做变换令 $x = \beta t$ ，则：

$Gamma(t \| \alpha,\beta) = \frac{\beta^{\alpha}t^{\alpha - 1}e^{-\beta t}}{\Gamma(\alpha)}$

上式中多出来地一个 $\beta$ ,来自 $d\beta x$

对于Gamma分布， $\alpha$ 称为shape parameter, $\beta$ 称为rate parameter，且 $\alpha$ 决定了分布的形状， $\beta$ 决定了分布的坡度。卡方分布和指数分布都是Gamma分布的特殊形式。

Beta分布：

$\frac{\Gamma(\alpha + \beta )}{\Gamma(\alpha)\Gamma(\beta)} x^{\alpha-1} (1-x)^{\beta-1}$

Beta分布的产生是与次序统计量关联起来的，IID产生的n个数，按照从小到大的顺序排列，则k-1个比第k的次序统计量小，n-k个比其大，则次序统计量 $X_{(k)} \sim Beta(k-1, n-k)$ ，Beta分布的均值可以用 $\frac{\alpha}{\alpha+\beta}$ 估计。

Dirichlet分布是Beta分布在高维度上的推广，可以用来表示次序统计量之间的联合密度函数，其密度函数：

$f(x_1,...,x_K;\alpha_1,...,\alpha_K)=\frac{\Gamma(\sum_{i=1}^K \alpha_i)}{\prod_{i=1}^k \Gamma(\alpha_i)}\prod_{i=1}^K x_i^{\alpha_i -1}$

Simulation 仿真，通过产生随机数的方式来量化无法求出闭式解的问题，这种随机数一般满足一定的分布。下面介绍MCMC(Markov Chain Monte Carlo)和Gibbs Sampling.

在介绍MCMC之前，首先需要了解马氏链以及其平稳分布。马氏链的基本假设是状态转移只与前一个状态有关，即：

$P(X_{t+1} = x \mid X_t,X_{t-1}...) = P(X_{t+1} = x \mid X_t)$

如果一个非周期马氏链具有转移概率矩阵P，且它的任何两个状态是连通的，那么当n足够大时，马氏链将收敛，收敛之后的状态是同分布的随机变量（并不独立）。

$\lim_{n \to \infty} P^n = \left[ \begin{matrix} \pi(1) & \pi(2) &... &\pi(j) &... \\ \pi(1) & \pi(2) &... & \pi(j) & ... \\ ... & ... & ... & ... & ... \end{matrix} \right]$

$\pi = [\pi(1),\pi(2)...\pi(j)...]$ 称为马氏链的平稳分布。且 $\sum_{i=0}^{\infty} \pi(i) =1$

假设我们使马氏链的平稳分布等于p(x)，这样就可以采样出满足该概率分布的随机样本，MCMC采样便是基于此的。而Gibbs Sampling则是多维的 $p(x_1,x_2...x_n)$ 。

4. 评价指标

除了主观的评价主题模型的好坏之外，可以使用学习出来的参数来生成一些文档，与原文档比较，计算hold-out likelihood或complexity(是likelihood的变形). 除了定量计算方法外，还可以使用Intrusion Word的方法。

Reference

Websites quora
rickjin LDA数学八卦