Articles tagged as

  1. Probabilistic latent semantic analysis (pLSA)

    Probabilistic latent semantic analysis (概率潜在语义分析,pLSA) 是一种 Topic model,在99年被 Thomas Hofmann 提出。它和随后提出的 LDA 使得 Topic Model 成为了研究热点,其后的模型大都是建立在二者的基础上的。

    我们有时会希望在数量庞大的文档库中自动地发现某些结构。比如我们希望在文档库发现若干个“主题”,并将每个主题用关键词的形式表现出来。 我们还希望知道每篇文章中各个主题占得比重如何,并据此判断两篇文章的相关程度。而 pLSA 就能完成这样的任务。

    我之前取了 Wikinews 中的 1000 篇新闻,试着用 pLSA 在其中发现 K=15 个主题。比如一篇关于 Wikileaks 的阿萨奇被保释消息的新闻,算法以 100% 的概率把它分给了主题 9,其关键词为:

    media phone hacking wikileaks assange australian stated information investigation murdoch

    可以看到这个主题的发现还是非常靠谱的。又比如这条中国人民的老朋友威胁要大打打核战争 的新闻。 算法把它以 97.7% 的概率分给了主题 3,2.3% 的概率分给了主题 7。主题 3 的关键词是:

    south north court china military death tornado service million storm

    主题 7 的关键词是:

    nuclear plant power japan million carbon radiation china water minister

    可以看到这条新闻和主题 3 中的“南北”、“军事”、“中国”、“死亡”这些信息联系在一起,和主题 7 中的“核”、“中国”联系在一起。 应该是因为我的数据集中与北朝鲜核问题相关的新闻只有不到 10 条,而 10 个主题的划分并不够细致,所以关于“朝核问题”或者“核武器”的这样的主题并没能被分离出来。但可以看到即使是这样结果也是很 make sense 的。

    那我们就来看看 pLSA 模型是怎么回事吧。和很多模型一样,pLSA 遵从 bag-of-words 假设, 即只考虑一篇文档中单词出现的次数,忽略单词的先后次序关系,且每个单词的出现都是彼此独立的。 这样一来,我们观察到的其实就是每个单词 \(w \in W\) 在每篇文档 \(d \in D\) 中出现的次数 \(n(w,d)\)。 pLSA 还假设对于每对出现的 \((d,w)\) 都对应着一个表示“主题”的隐藏变量 \(z \in Z\)。 pLSA 是一个生成模型,它假设 \(d\)\(w\)\(z\) 之间的关系用贝叶斯网络表示是这样的(从 [Blei03] 偷的图):

    image0

    实心的节点 \(d\)\(w\) 表示我们能观察到的文档和单词,空心的 \(z\) 表示我们观察不到的隐藏变量,用来表示隐含的主题。图中用了所谓的“盘子记法”, 即用方框表示随机变量的重复。这里方框右下角的字母 \(M\)\(N\) 分别表示有 \(M\) 篇文档,第 \(j\) 篇文档有 \(N_j\) 个单词。每条有向边表示随机变量间的依赖关系 ...

  2. Expectation-Maximization(EM) 算法

    Expectation-Maximization 算法是统计学中用来给带隐含变量的模型做最大似然(和最大后验概率)的一种方法。EM 的应用特别广泛,经典的比如做概率密度估计用的 Gaussian Mixture Model。这两天我或许还会写 p 的笔记放上来,也是 EM 应用的例子。

    下面我会先解释 EM 算法要解决的问题,然后直接给出算法的过程,最后再说明算法的正确性。

    问题

    首先我们定义要解决的问题。给定一个训练集 \(X=\{x^{(1)},…,x^{(m)}\}\),我们希望拟合包含隐含变量 \(z\) 的模型 \(P(x,z;\theta)\) 中的参数 \(\theta\)。根据模型的假设,每个我们观察到的 \(x^{(i)}\) 还对应着一个我们观察不到的隐含变量 \(z^{(i)}\),我们记 \(Z=\{z^{(1)},…,z^{(m)}\}\)。做最大对数似然就是要求 \(\theta\) 的“最优值”:

    \begin{equation*} \theta=\arg\max_\theta{L(\theta;X)} \end{equation*}

    其中

    \begin{equation*} L(\theta;X)=log{P(X;\theta)}=\log{\sum_Z P(X,Z;\theta)} \end{equation*}

    想用这个 \(\log\)\(\sum\) 的形式直接求解 \(\theta\) 往往非常困难。而如果能观察到隐含变量 \(z\) ,求下面的似然函数的极大值会容易许多:

    \begin{equation*} L(\theta;X,Z)=\log{P(X, Z;\theta)} \end{equation*}

    问题是实际上我们没法观察到 \(z\) 的值,只能在给定 \(\theta\) 时求 \(z\) 的后验概率 \(P(z|x;\theta)\)[1] EM 算法就可以帮我们打破这样的困境。

    算法

    下面给出 EM 算法的过程。其中 \(\theta_t\) 是第 t-1 次迭代时算出的 \(\theta\) 值;\(\theta_0\) 为任意初值。

    Repeat until converge {

    1. (E-step) 计算 \(P(Z|X;\theta_t)\) 以得到

      \begin{align*} E_{Z|X;\theta_t}[L(\theta;X,Z)] &:= E_{Z|X;\theta_t}[\log{P(X,Z;\theta)}] \\ &= \sum_Z P(Z|X;\theta_t) \log{P(X,Z;\theta)} \end{align*}
    2. (M-step)

      \begin{equation*} \theta_{t+1} := \arg\max_\theta E_{Z|X;\theta_t}[\log{P(X,Z;\theta)}] \end{equation*}

    }

    对,就这么短 ...

Page 1 / 1