PLSA 主题分析与关键词提取的利器

背景问题 文档相似度比较

假设我们现在有若干文档,我们想比较其中两个文档的相似度,或者说我们希望知道这两份文档说的是不是一样的或者类似的事情。一个naive的想法就是,直接进行词频统计,也就是说,先选取一个大小为\(M\)的常用词汇集\(W\),然后比较这样两个向量

\[ p(w_1|d_1), p(w_2|d_1),\cdots , p(w_M|d_1) \]

\[ p(w_1|d_2), p(w_2|d_2), \cdots, p(w_M|d_2) \]

这个方法很显然是不太可行的,因为词汇类似但内容迥异或者词汇迥异但内容类似的情况数见不鲜。

PLSA模型的建立

一个更加好的想法是,考虑引入若干隐变量,这些隐变量表示的含义是“主题”。也就是说,引入\(K\)个主题隐变量\(Z = (z_1, z_2, \cdots, z_K)\),在此基础上我们比较两份文档的这两个向量

\[ p(z_1|d_1), p(z_2|d_1), \cdots, p(z_K,d_1) \]

\[ p(z_1|d_2), p(z_2|d_2), \cdots, p(z_K|d_2) \]

这两个向量分别表示了两份文档在多大的程度上谈论了什么话题。下面的主要问题就在于计算这些条件概率。

假设我们现在有\(N\)份文档,预设的词汇集内共有\(M\)个词汇,引入的主题隐变量有\(K\)个。首先,我们已经有的数据是这样一个矩阵\( (c_i^j) \),表示第\(i\)个文档中的第\(j\)个词汇出现了多少次(这一矩阵称为共现矩阵,顾名思义是记录文档-词汇共同出现的矩阵)。那么对于我们的样本,可能性函数为

\[ L = \prod_{i=1}^{N} \prod_{j=1}^M p(d_i, w_j)^{n(d_i, w_j)} \]

对上式取自然对数,得到

\[ \ln{L} = \sum_{i=1}^N \sum_{j=1}^M n(d_i, w_j)\ln{p(d_i, w_j)} \]

在现有条件下,\( p(d_i, w_j) \)无法计算。考虑到

\[ p(d_i, w_j) = \sum_{k=1}^K p(d_i, w_j, z_k) \]

实际上问题的关键在于上述的全概率公式如何计算。这里略去一些有关概率图模型的讨论,这样来看待这个问题。按照条件概率公式,全概率可以被写成

\[ p(d_i, w_j, z_k) = p(w_j|z_k, d_i) p(z_k|d_i) p(d_i) \]

再做一些假设:认为主题与文档有关,词汇仅仅与主题有关而与出现这一词汇的文档无关。于是上式变为

\[ p(d_i, w_j, z_k) = p(w_j|z_k) p(z_k|d_i) p(d_i) \]

把这一公式代入取了自然对数的可能性函数,得到了

\[ \ln{L} = \sum_{i=1}^N n(d_i)p(d_i) + \sum_{i=1}^N \sum_{j=1}^M n(d_i, w_j) \ln{ \sum_{k=1}^K p(w_j|z_k)p(z_k|d_i) } \]

上述求和式的第一部分是可以直接根据共现矩阵算出来的,对于我们的隐变量参数\(Z\)而言是常数,因此我们真正的目标是最大化如下的目标函数

\[ T = \sum_{i=1}^N \sum_{j=1}^M n(d_i, w_j) \ln{ \sum_{k=1}^K p(w_j|z_k)p(z_k|d_i) } \]

s.t.

\begin{align*}
p(w_j|z_k) &\ge 0 \\
p(z_k|d_i) &\ge 0 \\
\sum_{j=1}^M p(w_j|z_k) &= 1 \\
\sum_{k=1}^K p(z_k|d_i) &= 1
\end{align*}

这一函数的最大值甚至是极大值都是非常不好求的,原因在于对数里面有求和。

EM算法求解PLSA

EM算法是一个经典算法,用于求解函数的局部极值。这一算法的基本思想在于如果函数本身不好处理,我们转而处理函数的一个下界,这样求得一组使得函数的下界取到最值(或极值)的参数值,再重新利用这一组参数值计算得到新的下界。重复这一过程直到收敛。对于PLSA模型而言,具体的操作过程是这样的。

利用对数函数的凸性,根据Jason不等式

\begin{align*}
& \sum_{i=1}^N \sum_{j=1}^M n(d_i, w_j) \ln{ \sum_{k=1}^K p(w_j|z_k)p(z_k|d_i) } \\
& \sum_{i=1}^N \sum_{j=1}^M n(d_i, w_j)
\ln{ \sum_{k=1}^K Q(z_k) \frac{p(w_j|z_k)p(z_k|d_i)}{Q(z_k)} } \\
& \ge \sum_{i=1}^N \sum_{j=1}^M n(d_i, w_j)
\sum_{k=1}^K Q(z_k) \ln{ \frac{p(w_j|z_k)p(z_k|d_i)}{Q(z_k)} } \\
&= \sum_{i=1}^N \sum_{j=1}^M n(d_i, w_j)
\sum_{k=1}^K Q(z_k) \ln{p(w_j|z_k)p(z_k|d_i) } + constant
\end{align*}

其中\(Q(z_k)\)是人为给定的加权因子,对于我们的模型而言是常数,因为无论它被赋予了什么样的值,它实际上都不依赖于已经出现的任何一个概率。加权因子还有一个限制条件

\[ \sum_{k=1}^K Q(z_k) = 1, Q(z_k) \ge 0 \]

除此之外还有之前已经提到的对于条件概率的约束条件。在这一模型中,条件概率\(p(w_j|z_k), p(z_k|d_i)\)是函数的自变量,它们有各自的求和为1的约束条件,而\(Q(z_k)\)是给定的参数,不是自变量。无论如何,现在的下界函数中的对数内部已经没有求和了,处理起来是比较方便的。带约束的函数极值的求解方法,很自然地是拉格朗日乘数法。把上述下界记作\(S\),根据拉格朗日乘数法,得到

\[ S + \sum_{k=1}^K \alpha_k(1 – \sum_{j=1}^M) p(w_j|z_k) + \sum_{i=1}^N \beta_i(1 – \sum_{k=1}^K p(z_k|d_i))\]

利用偏导数等于0,得到了

\[ \sum_{i=1}^N n(d_i,w_j)Q(z_k) – \alpha_k p(w_j|z_k) = 0 \]

\[ \sum_{j=1}^M d(d_i,w_j)Q(z_k) – \beta_i p(z_k|d_i) = 0 \]

对上述第一个式子,结合\( \sum_{j=1}^M p(w_j|z_k) = 1 \),可以得到

\[ p(w_j|z_k) = \frac{
\sum_{i=1}^N n(d_i,w_j)Q(z_k)
}
{
\sum_{j=1}^M \sum_{i=1}^N n(d_i,w_j)Q(z_k)
} \]

类似地可以得到

\[ p(z_j|d_i) = \frac{
\sum_{j=1}^M d(d_i,w_j)Q(z_k)
}{
n(d_i)
} \]

这样,如果我们预先给定了\(Q(z_k)\),这两类条件概率的值都是可以计算得到的了。但是我们的目的不仅限于此。我们希望通过这个利用优化下界得到的条件概率可以给出一个新的下界用于迭代。所谓的新的下界,在这里就是一组新的\(Q(z_k)\)。这一目标要求我们可以利用\( p(w_j|z_k), p(z_k|d_i) \) 来计算新的\( Q(z_k) \),同时不能破坏\( Q(z_k) \)应当满足的限制条件。值非负并且求和为1,很自然地想到可以使用概率分布来给\( Q(z_k) \)赋值。

于是,取\( Q(z_k) = p(z_k|d_i,w_j) \)。

再一次,由于\( Q(z_k) \)的值是人为选取的,无论把它设定成什么值,它都没有真的和上述的两组条件概率产生相关,因此上述推导中将它作为常数并没有问题。一个更加直观的理解是,我们使用已经计算得到的“条件概率的估计值”更新了这一组“未知常数的估计值”。

结合之前提到的全概率公式,有

\begin{align*}
Q(z_k) &= p(z_k|d_i,w_j) \\
&= \frac{ p(z_k,d_i,w_j) }{ \sum_{k=1}^K p(z_k,d_i,w_j) } \\
&= \frac{ p(z_k, d_i, w_j) }{ \sum_{k=1}^K p(z_k, d_i, w_j) } \\
&= \frac{ p(w_j|z_k)p(z_k|d_i)p(d_i) }{ \sum_{k=1}^K p(w_j|z_k)p(z_k|d_i)p(d_i) } \\
&= \frac{ p(w_j|z_k)p(z_k|d_i) }{ \sum_{k=1}^K p(w_j|z_k)p(z_k|d_i) }
\end{align*}

至此我们得到了这样一组迭代公式

\begin{align*}
Q(z_k) &= \frac{ p(w_j|z_k)p(z_k|d_i) }{ \sum_{k=1}^K p(w_j|z_k)p(z_k|d_i) } \\
p(w_j|z_k) &=
\frac{\sum_{i=1}^N n(d_i,w_j)Q(z_k) }
{\sum_{j=1}^M \sum_{i=1}^N n(d_i,w_j)Q(z_k) } \\
p(z_k|d_i) &=
\frac{\sum_{j=1}^M d(d_i,w_j)Q(z_k) }
{n(d_i)}
\end{align*}

初始化\( p(w_j|z_k), p(z_k|d_i) \)后就可开始反复迭代直到收敛。

这样我们就可以分析出文档的主题相似度了。同样,我们可以选取文档最可能的几个主题,再把这个主题下概率最高的几个词汇选出来,就达到了关键词提取的目的。

短文本下的PLSA

在社交网络出现的文本,如微博,QQ空间等,大量的都是短文本。这些文本整个文档只有几十个单词,文本长度很短。这样的文本构成的文档-词汇共现矩阵相比于文本长度而言尺寸很大,而其中绝大部分都是零。由于文档长度过短,词汇和文档的共现意义并不总是很明显,在处理社交网络上广泛出现的短文本上,上述的模型并不是很有力。

此时,文档本身的意义已经不大,我们更加应该考虑的是,不同词汇在同一文本内出现这一事实。考虑在若干主题的条件下词汇的共现。此时我们观察到的是短文本的词汇\( w_i \)与同一文本中的词汇\( w_j’ \)共现。

此时对于一个给定的数据集,我们观察到的可能性函数为

\[ L = \prod_{i=1}^N \prod_{j=1}^M p(w_i,w_j’)^{n(w_i,w_j’)} \]

其中\( n(w_i,w_j’) \)表示两个词汇共现的次数,可以取为该短文本中词汇\( w_i \)与\( w_j’ \)各自出现次数的最小值。

引入主题隐变量\(Z\),同时作一些条件独立的假设,认为词汇的出现仅仅与主题有关,而不与其余的词汇直接相关

\begin{align*}
p(w_i,w_j’) &= \sum_{k=1}^K p(w_i,w_j’,z_k) \\
&= \sum_{k=1}^K p(w_i,w_j’|z_k) p(z_k) \\
&= \sum_{k=1}^K p(z_k)p(w_i|z_k)p(w_j’|z_k)
\end{align*}

因此可以得到目标函数的一个下界:

\begin{align*}    
\ln{L} &= \sum_{i=1}^N \sum_{j=1}^M n(w_i,w_j’) \ln{p(w_i,w_j’)} \\           
&= \sum_{i=1}^N \sum_{j=1}^M n(w_i,w_j’) \ln{ \left[ \sum_{k=1}^K p(z_k)p(w_i|z_k)p(w_j’|z_k) \right] } \\           
&= \sum_{i=1}^N \sum_{j=1}^M n(w_i,w_j’) \ln{ \left[ \sum_{k=1}^K Q(z_k)\frac{p(z_k)p(w_i|z_k)p(w_j’|z_k)}{Q(z_k)} \right] } \\           
&\ge \sum_{i=1}^N \sum_{j=1}^M n(w_i,w_j’) \sum_{k=1}^K Q(z_k) \ln{ \left[ \frac{p(z_k)p(w_i|z_k)p(w_j’|z_k)}{Q(z_k)} \right] } \\           
&= \sum_{i=1}^N \sum_{j=1}^M n(w_i,w_j’) \sum_{k=1}^K Q(z_k) \ln{ \left[ p(z_k)p(w_i|z_k)p(w_j’|z_k) \right] } + constant
\end{align*}

其中\( \sum_{k=1}^K Q(z_k) = 1, \forall k\ Q(z_k) \ge 0 \)且\( Q(z_k) \)是给定的。

利用拉格朗日乘数法,定义

\begin{align*}    
T &= \sum_{i=1}^N \sum_{j=1}^M n(w_i,w_j’) \sum_{k=1}^K Q(z_k) \ln{ \left[ p(z_k)p(w_i|z_k)p(w_j’|z_k) \right] } \\      
&+ \sum_{k=1}^K \alpha_k (1 – \sum_{i=1}^N p(w_i|z_k)) + \sum_{k=1}^K \beta_k (1 – \sum_{j=1}^M p(w_j’|z_k)) \\      
&+ \gamma (1 – \sum_{k=1}^K p(z_k))
\end{align*}

求偏导,得到

\[    \frac{\partial{T}}{\partial{p(w_i|z_k)}} = \sum_{j=1}^M n(w_i,w_j’)\frac{Q(z_k)}{p(w_i|z_k)} – \alpha_k = 0 \]

于是

\[    p(w_i|z_k) = \frac{\sum_{j=1}^M n(w_i,w_j’)Q(z_k)}{\alpha_k}\]

利用

\[    1 = \sum_{i=1}^N p(w_i|z_k) = \sum_{i=1}^N \sum_{j=1}^M \frac{ n(w_i,w_j’)Q(z_k)}{\alpha_k}\]

得到

\[    p(w_i|z_k) = \frac{\sum_{j=1}^M n(w_i,w_j’)Q(z_k)}{ \sum_{i=1}^N \sum_{j=1}^M n(w_i,w_j’)Q(z_k)}\]

类似地,利用\( \frac{\partial{T}}{\partial{p(w_j’|z_k)}} = 0 \),可以得到

\[    p(w_i|z_k) = \frac{\sum_{i=1}^N n(w_i,w_j’)Q(z_k)}{ \sum_{i=1}^N \sum_{j=1}^M n(w_i,w_j’)Q(z_k)}\]

再利用\( \frac{\partial{T}}{\partial{p(z_k)}} = 0 \),得到了

\[    p(z_k) = \frac{Q(z_k) \sum_{i=1}^N \sum_{j=1}^M n(w_i,w_j’)}{ \sum_{k=1}^K Q(z_k) \sum_{i=1}^N \sum_{j=1}^M n(w_i,w_j’) }\]

如果选取

\begin{align*}    
Q(z_k) &= p(z_k|w_i,w_j’) \\           
&= \frac{p(w_i,w_j’,z_k)}{p(w_i,w_j’)} \\           
&= \frac{p(z_k)p(w_i|z_k)p(w_j’|z_k)}{\sum_{k=1}^K p(z_k)p(w_i|z_k)p(w_j’|z_k)}
\end{align*}

就得到了如下的一组EM算法迭代公式

\begin{align*}    
p(w_i|z_k) &= \frac{\sum_{j=1}^M n(w_i,w_j’)Q(z_k)}{ \sum_{i=1}^N \sum_{j=1}^M n(w_i,w_j’)Q(z_k)} \\    
p(w_i|z_k) &= \frac{\sum_{i=1}^N n(w_i,w_j’)Q(z_k)}{ \sum_{i=1}^N \sum_{j=1}^M n(w_i,w_j’)Q(z_k)} \\    
p(z_k)     &= \frac{Q(z_k) \sum_{i=1}^N \sum_{j=1}^M n(w_i,w_j’)}{ \sum_{k=1}^K Q(z_k) \sum_{i=1}^N \sum_{j=1}^M n(w_i,w_j’) } \\    
Q(z_k)     &= \frac{p(z_k)p(w_i|z_k)p(w_j’|z_k)}{\sum_{k=1}^K p(z_k)p(w_i|z_k)p(w_j’|z_k)} \end{align*}

使用神经网络的方法建模求解PLSA

先等等。

发表评论

电子邮件地址不会被公开。 必填项已用*标注