对于给定的文档，概率主题模型学习所有文档中单词的分布，以及对每个文档学习其主题的分布，并把文档中的每个单词赋给一个主题。例如，对于体育主题，权重最大的单词可能是team，值为0.03，而对医疗主题权重最大的单词可能是health。对某篇文章，根据文章里的词语，可以判断该文应该属于医疗主题还是体育主题。
LDA
LDA的两个重要组成成分包括：1. 词的分布，即对相同的词汇表，主题不同则词的分布也不同。2. 对于某文档主题的分布，即假设对于给定的文档其内容肯定倾向于某些主题。LDA也可以用贝叶斯方法处理，所以我们要对数据是如何分布的进行假设
假设数据集中有\(K\)个不同的主题，\(D\)篇文档，则LDA的生成过程为
- 生成主题。主题是单词的分布，即对\(k=1,\ldots, K\)有 \[ \beta_k \sim {\rm Dirichlet}(\gamma) \]
- 对每篇文档，生成主题的分布，即对\(d=1,\ldots, D\)有 \[ \theta_d \sim {\rm Dirichlet}(\alpha) \]
- 对第\(d\)篇文档的第\(n\)个单词，首先找到这篇文章应该属于什么主题，即\(c_{dn} \sim {\rm Discrete}(\theta_d)\)。然后，根据选定的主题，从该主题生成一个单词，即\(x_{dn} \sim {\rm Discrete}(\beta_{c_{dn}})\)
注意：1. 这里只有\(x\)是已知的，其它都要学习出来；2. 这里使用了词袋模型，没有使用其它语言模型。即这里我们没有考虑词语之间的先后顺序。
Dirichlet分布
Dirichlet分布是非负、总和为1的向量上的概率分布。如果\(\beta_k\)是从Dirichlet分布生成的随机变量，则\(\beta_k\)的每一个分量都非负，所有分量总和为1，可以看做是一个离散分布。也就是说，Dirichlet分布是离散分布的分布——不过注意Dirichlet分布本身是一个连续分布。设\(\beta_k\)是一个概率向量，\(\gamma\)是Dirichlet分布的正参数向量，向量有\(V\)个维度，则 \[ p(\beta_k | \gamma) = \frac{\Gamma(\sum_v \gamma_v)}{\prod_{v=1}^V\Gamma(\gamma_v)}\prod_{v=1}^V \beta_{k,v}^{\gamma_v - 1} \]
\(\gamma\)越大，得到的概率向量越接近于均匀分布；反之则使得向量中的某几个维度概率值更大。做LDA时倾向于给一个小的\(\gamma\)，因为一篇文章可能只能覆盖少数几个主题，一个主题可能只能包含单词表中的一部分单词。
LDA与矩阵分解
这里要解决的问题是，对某篇给定的文档，\(P(x_{dn} = i|\beta, \theta_d)\)是多少？即，给定\(\beta\)和\(\theta_d\)的前提下，第\(d\)篇文档中第\(n\)个单词是单词表里第\(i\)个单词的概率是多大。注意这里没有\(c_{dn}\)，换句话说\(c_{dn}\)可以被积分掉，即 \[ \begin{align*} P(x_{dn} = i | \beta, \theta) &= \sum_{k=1}^K P(x_{dn} = i, c_{dn} = k|\beta, \theta_d) \\ &= \sum_{k=1}^K \underbrace{P(x_{dn} = i|\beta, c_{dn} = k)}_{=\beta_{ki}} \underbrace{P(c_{dn}=k|\theta_d)}_{=\theta_{dk}} \end{align*} \] 令\(B=[\beta_1, \ldots, \beta_K]\)，\(\Theta = [\theta_1, \ldots, \theta_D]\)，则\(P(x_{dn} = i | \beta, \theta) = (B\Theta)_{id}\)
假设单词表大小为\(V\)，则\(B\)为\(V\times K\)的矩阵，\(\Theta\)为\(K \times D\)的矩阵。注意\(B\)、\(\Theta\)也都是非负矩阵，则主题模型问题可以看做是非负矩阵分解问题（即如何将一个非负矩阵分解为两个非负矩阵的乘积）
非负矩阵分解 (NMF)
与概率矩阵分解 (PMF) 类似。不过PMF中原矩阵大部分都是缺失值，NMF中原矩阵大部分都是0值（但是是一个完整的矩阵）
目标函数
NMF要最小化的目标函数可以有两种，均以\(W\)和\(H\)为变量。使用时选择其中一个求解
- 平方误差 \[ |\!|X-WH|\!|^2 = \sum_i\sum_j(X_{ij} - (WH)_{ij})^2 \]
- 距离 (divergence) \[ D(X|\!|WH) = -\sum_i \sum_j [X_{ij}\ln(WH)_{ij} - (WH)_{ij}] \]
NMF算法类似于之前的EM算法，也是引入了一个辅助函数，然后使辅助函数与原函数的KL距离最小（？）。这里不讨论。细节见 D.D. Lee and H.S. Seung (2001). "Algorithms for non-negative matrix factorization." Advances in Neural Information Processing Systems
最小化平方误差
其求解问题为 \[ \min \sum_{ij}(X_{ij} - (WH)_{ij})^2\ \ \ {\rm subject\ to}\ W_{ik} \ge 0, H_{kj} \ge 0 \] 算法随机使用非负数初始化\(H\)和\(W\)，然后迭代下面两个式子直到\(|\!|X-WH|\!|^2\)变化量足够小 \[ \begin{align*} H_{kj} &\leftarrow H_{kj}\frac{(W^\mathsf{T}X)_{kj}}{(W^\mathsf{T}WH)_{kj}} \\ W_{ik} &\leftarrow W_{ik}\frac{(XH^\mathsf{T})_{ik}}{(WHH^\mathsf{T})_{ik}} \end{align*} \]
最小化距离
其求解问题为 \[ \min \sum_{ij}\left[ X_{ij}\ln\frac{1}{(WH)_{ij}} + (WH)_{ij}\right]\ \ \ {\rm subject\ to}\ W_{ik} \ge 0, H_{kj} \ge 0 \] 算法随机使用非负数初始化\(H\)和\(W\)，然后迭代下面两个式子直到\(D(X|\!|WH)\)变化量足够小 \[ \begin{align*} H_{kj} &\leftarrow H_{kj}\frac{\sum_i W_{ik}X_{ij}/(WH)_{ij}}{\sum_i W_{ik}} \\ W_{ik} &\leftarrow W_{ik}\frac{\sum_j H_{kj}X_{ij} / (WH)_{ij}}{\sum_j H_{kj}} \end{align*} \]
最小化距离有一种更好的概率解释（最小化平方误差也可以有，尽管好用但是意义不大），即我们假设\(X_{ij}\)服从参数为\((WH)_{ij}\)的泊松分布，即 \[ X_{ij} \sim {\rm Pois}((WH)_{ij}),\ {\rm Pois}(x|\lambda) = \frac{\lambda^x}{x!}e^{-\lambda},x\in \{0,1,2,\ldots\} \] 由于独立性，有 \[ P(X|W,H) = \prod_{ij}P(X_{ij}|W,H) = \prod_{ij}{\rm Pois}(X_{ij}|(WH)_{ij}) \] 代入求解就可以得到目标函数
使用NMF求解主题建模问题
从前面的分析可知，divergence penalty从数学角度跟LDA更相关，因此可以分以下几步做
- 生成词频矩阵\(X\)。（\(X_{ij}\) = 单词\(i\)在文档\(j\)出现的次数）
- 运行NMF，使用\(D(X|\!|WH)\)惩罚项来学习\(W\)和\(H\)
- 额外地，在上一步结束以后，对\(k=1,\ldots, K\)，
- 设\(a_k = \sum_i W_{ik}\)
- 对所有\(i\)，把\(W_{ik}\)除以\(a_k\)
- 对所有\(j\)，把所有\(H_{ij}\)乘以\(a_k\)
这里\(W\)的第\(k\)列可以看做是第\(k\)个主题，\(H\)的第\(j\)列可以看作是对每个主题有多少文档可以划归其下
