概率潜在语义分析（Probabilistic Latent Semantic Analysis, PLSA）

$$\begin{align} \end{align}$$

单词集合$W=\{w_1,w_2,\cdots,w_M\}$
文本集合$D=\{d_1,d_2,\cdots,d_N\}$
话题集合$Z=\{z_1,z_2,\cdots,z_K\}$
单词-文本共现数据$T=\left[n\left(w_i,d_j\right)\right],i=1,2,\cdots,M;j=1,2,\cdots,N;$

文本-单词共现数据的生成过程：

1. 依据概率分布$P\left(d\right)$，从文本集合中随机选取一个文本$d$，共生成$N$个文本；针对每个文本，执行以下操作；
2. 在文本$d$给定条件下，依据条件概率分布$P\left(z|d\right)$，从话题集合中随机选取一个话题$z$，共生成$L$个话题（$L$为文本长度）；
3. 在话题$z$给定条件下，依据条件概率分布$P\left(w|z\right)$，从单词集合中随机选取一个单词$w$。

文本-单词共现数据$T$的生成概率

$$P\left(T\right)=\prod_{\left(w,d\right)} P\left(w,d\right)^{n\left(w,d\right)}$$

其中，$n\left(w,d\right)$表示$\left(w,d\right)$的出现次数，单词-文本对出现的总次数是$N\times L$。

每个单词-文本对$\left(w,d\right)$的生成概率

$$\begin{align} P\left(w,d\right)&=P\left(d\right)P\left(w|d\right) \\ &=P\left(d\right)\sum_z P\left(w,z|d\right) \\ &=P\left(d\right)\sum_z P\left(z|d\right)P\left(w|z\right) \end{align}$$

假设在话题$z$给定条件下，单词$w$与文本$d$条件独立

$$\begin{align} P\left(w,z|d\right)&=P\left(z|d\right)P\left(w|z,d\right) \\ &=P\left(z|d\right)P\left(w|z\right) \end{align}$$

单词-文本共现数据$T$的对数似然函数

$$\begin{align} L\left(T\right) &=\log\prod_{w,d}P\left(w,d\right)^{n\left(w,d\right)} \\ &=\sum_{i=1}^M\sum_{j=1}^N n\left(w_i,d_j\right)\log P\left(w_i,d_j\right) \\ &=\sum_{i=1}^M\sum_{j=1}^N n\left(w_i,d_j\right)\log \sum_{k=1}^K P\left(w_i,d_j,z_k\right) \\ &=\sum_{i=1}^M\sum_{j=1}^N n\left(w_i,d_j\right)\log \sum_{k=1}^K P\left(w_i,z_k|d_j\right) P\left(d_j\right) \\ &=\sum_{i=1}^M\sum_{j=1}^N n\left(w_i,d_j\right)\log \sum_{k=1}^K P\left(w_i|z_k\right) P\left(z_k|d_j\right) P\left(d_j\right) \\ \end{align}$$

应用EM算法求解含有隐变量的对数似然函数优化问题。
E步：定义Q函数

$$\begin{align} Q &= \sum_z\log\prod_{w,d}P\left(w,d,z\right)^{n\left(w,d\right)}P\left(z|w,d\right) \\ &= \sum_z\log\prod_{w,d}\left[P\left(w,z|d\right)P\left(d\right)\right]^{n\left(w,d\right)}P\left(z|w,d\right) \\ &= \sum_z\left\{\sum_{w,d}n\left(w,d\right)\left[\log P\left(d\right)+\log P\left(w,z|d\right)\right]\right\}P\left(z|w,d\right) \\ &= \sum_z\left\{\sum_d\left[\sum_w n\left(w,d\right)\log P\left(d\right)+\sum_w n\left(w,d\right)\log P\left(w|z,d\right)P\left(z|d\right)\right]\right\}P\left(z|w,d\right) \\ &= \sum_z\left\{\sum_d\left[n\left(d\right)\log P\left(d\right)+\sum_w n\left(w,d\right)\log P\left(w|z\right)P\left(z|d\right)\right]\right\}P\left(z|w,d\right) \\ &= \sum_z\left\{\sum_d n\left(d\right)\left[\log P\left(d\right)+\sum_w\frac{n\left(w,d\right)}{n\left(d\right)}\log P\left(w|z\right)P\left(z|d\right)\right]\right\}P\left(z|w,d\right) \\ &= \sum_{k=1}^K\left\{\sum_{j=1}^N n\left(d_j\right)\left[\log P\left(d_j\right)+\sum_{i=1}^M\frac{n\left(w_i,d_j\right)}{n\left(d_j\right)}\log P\left(w_i|z_k\right)P\left(z_k|d_j\right)\right]\right\}P\left(z_k|w_i,d_j\right) \end{align}$$

其中，$n\left(w,d\right)$表示单词$w$在文本$d$中出现的次数，$n\left(d\right)=\sum_w\left(w,d\right)$表示文本$d$中单词的个数。

由于可以从数据中直接统计得出$P\left(d_j\right)$的估计，可将$Q$函数简化为只考虑$P\left(w_i|z_k\right)$和$P\left(z_k|d_j\right)$的函数$Q^{‘}$

$$Q^{'}=\sum_{i=1}^M \sum_{j=1}^N n\left(w_i,d_j\right)\sum_{k=1}^K P\left(z_k|w_i,d_j\right)\log\left[P\left(w_i|z_k\right)P\left(z_k|d_j\right)\right]$$

$Q^{‘}$函数中$P\left(z_k|w_i,d_j\right)$根据贝叶斯公式

$$\begin{align} P\left(z_k|w_i,d_j\right)&=\frac{P\left(w_i,z_k|d_j\right)}{P\left(w_i|d_j\right)} \\ &=\frac{P\left(w_i,z_k|d_j\right)}{\sum_{k=1}^K P\left(w_i,z_k|d_j\right)} \\ &=\frac{P\left(w_i|z_k\right)P\left(z_k|d_j\right)}{\sum_{k=1}^K P\left(w_i|z_k\right)P\left(z_k|d_j\right)} \end{align}$$

其中，$P\left(z_k|d_j\right)$和$P\left(w_i|z_k\right)$可由上一次迭代得到。

M步：极大化Q函数

$$\begin{align} \max Q^{'} \\ s.t.\quad \sum_{i=1}^M P\left(w_i|z_k\right)&=1,\quad k-1,2,\cdots,K \\ \sum_{k=1}^K P\left(z_k|d_j\right)&=1,\quad j=1,2,\cdots,N \end{align}$$

定义拉格朗日函数

$$\Lambda=Q^{'}+\sum_{k=1}^K\tau_k\left(1-\sum_{i=1}^M P\left(w_i|z_k\right)\right)+\sum_{j=1}^N\rho_j\left(1-\sum_{k=1}^K P\left(z_k|d_j\right)\right)$$

拉格朗日函数$\Lambda$对$P\left(w_i|z_k\right)$求偏导，并令其等于0，得

$$\frac{\partial\Lambda}{\partial P\left(w_i|z_k\right)}=\sum_{j=1}^N n\left(w_i,d_j\right)P\left(z_k|w_i,d_j\right)\frac{1}{P\left(w_i|z_k\right)}-\tau_k=0,\quad i=1,2,\cdots,M; \quad k=1,2,\cdots,K$$ $$\begin{align} \tau_k P\left(w_i|z_k\right) &= \sum_{j=1}^N n\left(w_i,d_j\right)P\left(z_k|w_i,d_j\right) \\ \sum_{m=1}^M \tau_k P\left(w_m|z_k\right) &= \sum_{m=1}^M \sum_{j=1}^N n\left(w_m,d_j\right)P\left(z_k|w_m,d_j\right) \\ \tau_k &= \sum_{m=1}^M \sum_{j=1}^N n\left(w_m,d_j\right)P\left(z_k|w_m,d_j\right) \end{align}$$ $$P\left(w_i|z_k\right)=\frac{\sum_{j=1}^N n\left(w_i,d_j\right)P\left(z_k|w_i,d_j\right)}{\sum_{m=1}^M \sum_{j=1}^N n\left(w_m,d_j\right)P\left(z_k|w_m,d_j\right) }$$

拉格朗日函数$\Lambda$对$P\left(z_k|d_j\right)$求偏导，并令其等于0，得

$$\frac{\partial\Lambda}{\partial P\left(z_k|d_j\right)}=\sum_{i=1}^M n\left(w_i,d_j\right)P\left(z_k|w_i,d_j\right)\frac{1}{P\left(z_k|d_j\right)}-\rho_j=0,\quad j=1,2,\cdots,N; \quad k=1,2,\cdots,K$$ $$\begin{align} \rho_j P\left(z_k|d_j\right) &= \sum_{i=1}^M n\left(w_i,d_j\right)P\left(z_k|w_i,d_j\right) \\ \sum_{k=1}^K\rho_j P\left(z_k|d_j\right) &= \sum_{k=1}^K\sum_{i=1}^M n\left(w_i,d_j\right)P\left(z_k|w_i,d_j\right) \\ \rho_j &= \sum_{k=1}^K\sum_{i=1}^M n\left(w_i,d_j\right)P\left(z_k|w_i,d_j\right) \end{align}$$ $$\begin{align} P\left(z_k|d_j\right)&=\frac{\sum_{i=1}^M n\left(w_i,d_j\right)P\left(z_k|w_i,d_j\right)}{\sum_{k=1}^K\sum_{i=1}^M n\left(w_i,d_j\right)P\left(z_k|w_i,d_j\right)} \\ &= \frac{\sum_{i=1}^M n\left(w_i,d_j\right)P\left(z_k|w_i,d_j\right)}{n\left(d_j\right)} \end{align}$$

概率潜在语义模型参数估计的EM算法：
输入：设单词集合为$W=\{w_1,w_2,\cdots,w_M\}$，文本集合为$D=\{d_1,d_2,\cdots,d_N\}$，话题集合为$Z=\{z_1,z_2,\cdots,z_K\}$，共现数据$\{n\left(w_i,d_j\right)\},i=1,2,\cdots,M,j=1,2,\cdots,N$
输出：$P\left(w_i|z_k\right)$和$P\left(z_k|d_j\right)$

1. 设置参数$P\left(w_i|z_k\right)$和$P\left(z_k|d_j\right)$的初始值；
2. 迭代执行以下E步，M步，直到收敛为止
   E步骤： $$\begin{align} P\left(z_k|w_i,d_j\right)=\frac{P\left(w_i|z_k\right)P\left(z_k|d_j\right)}{\sum_{k=1}^K P\left(w_i|z_k\right)P\left(z_k|d_j\right)} \end{align}$$ M步骤： $$\begin{align} P\left(w_i|z_k\right)&=\frac{\sum_{j=1}^N n\left(w_i,d_j\right)P\left(z_k|w_i,d_j\right)}{\sum_{m=1}^M \sum_{j=1}^N n\left(w_m,d_j\right)P\left(z_k|w_m,d_j\right) } \\ P\left(z_k|d_j\right)&=\frac{\sum_{i=1}^M n\left(w_i,d_j\right)P\left(z_k|w_i,d_j\right)}{n\left(d_j\right)} \end{align}$$