23oclock 阅读(22) 评论(0)

最近看了一下LDA的文章, 写个小结, 理解正确与否有待验证.

Latent Dirichlet Allocation(LDA)是三层的层次概率贝叶斯模型(生成模型), 用于处理离散数据, 比如文本数据.

1. 概念

  • 单词(word): 形成数据的基本单元
  • 文档(document): 单词形成的有限序列
  • 语料库(corpus): 所有文档的集合

2. 记号

假设一共有 \(V\) 个单词, 则第 \(j\) 个单词表示为:

\[w = (0,\cdots,0,1,0,\cdots, 0), \text{其中$ 1 $位于第$ j $个位置.} \]

假设一共有 \(K\) 个主题, 则第 \(i\) 个主题表示为:

\[z = (0,\cdots,0,1,0,\cdots, 0), \text{其中$ 1 $位于第$ i $个位置.} \]

3. 流程

生成一个文档的过程如下:

  1. 从参数为 \(\xi\) 的Poisson分布中选取文档单词数 \(N\);
  2. 从参数为 \(\alpha\) 的Dirichlet分布中选择一个参数 \(\theta\);
  3. 依次生成每个单词 \(w_n\)(\(n=1,\cdots,N\)):
    1. 从参数为 \(\theta\) 的多项分布中选择一个主题 \(z_n\);
    2. 从以 \(\beta\) 为参数的条件多项分布 \(p(w_n|z_n, \beta)\) 中选取出单词 \(w_n\).

其中假设Dirichlet分布的维数固定为 \(K\)(即主题数固定为 \(K\)).

各参数分析如下:

  • 参数 \(\xi\) 是一个数;

  • 参数 \(\theta = (\theta^1, \cdots, \theta^K)\) 是一个 \(K\)维向量, 表示 \(K\) 个主题的概率分布;

  • 参数 \(\alpha=(\alpha^1, \cdots, \alpha^K)\) 是一个 \(K\) 维向量, \(\alpha^i\) 表示 \(\theta^i\) 对应的Dirichlet分布参数;

  • 参数 \(\beta\) 是一个 \(K\times V\) 的矩阵, \(\beta_{ij} = p(w^j=1|z^i=1)\), 即第 \(i\) 个主题中第 \(j\) 个单词的概率.

从上面的参数分析可以看见, 之所以使用Dirichlet先验分布, 是因为它恰到好处地, 给了我们想要的主题分布的每个参数 \(\theta^i\) 一个对应的参数 \(\alpha^i\), 并且对后面的变分推断和参数估计有益.

给定参数 \(\alpha\)\(\beta\), 可以得到 \(\theta = (\theta^1, \cdots,\theta^K)\), \(z=(z_1, \cdots, z_N)\), \(w = (w_1, \cdots, w_N)\)的联合分布

\[p(\theta,z,w|\alpha, \beta) = p(\theta|\alpha)\prod_{n=1}^{N}p(z_n|\theta)p(w_n|z_n, \beta), \]

\(\theta\)\(z\) 分别积分求和, 可以得到关于文档的边际分布

\[p(w|\alpha, \beta) = \int p(\theta|\alpha) \bigg(\prod_{n=1}^{N}\sum_{z_n} p(z_n|\theta)p(w_n|z_n, \beta) \bigg) d\theta. \]

4. 推断

LDA的推断问题是, 给定文档后, 隐变量的后验分布

\[p(\theta, z|w, \alpha, \beta) = \frac{p(\theta, z, w|\alpha, \beta)}{p(w|\alpha, \beta)}. \]

上式分母不可计算, 近似的方法包括Laplace逼近, 变分逼近, Markov链蒙特卡罗法等.

用上面后验分布的解耦样式

\[q(\theta, z|\gamma, \phi) = q(\theta|\gamma)\prod_{n=1}^{N} q(z_n|\phi_n) \]

逼近, 其中 \(\gamma=(\gamma^1, \cdots, \gamma^K)\) 为Dirichlet参数(近似 \(\alpha\)), \(\phi = (\phi_1, \cdots, \phi_N)\) 每个分量都是多项分布参数(近似 \(\beta\)). 极大似然问题变为极小化KL散度的优化问题:

\[(\gamma^{*}, \phi^{*}) = \arg\min_{(\gamma, \phi)} D(a(\theta, z)\Vert p(\theta, z|w, \alpha, \beta)), \]

可以得到

\[\begin{aligned} \phi_{ni} &\propto \beta_{iw_n} e^{E_q[\log(\theta_i)|\gamma]} \\ \gamma_i &= \alpha_i + \sum_{n=1}^{N} \phi_{ni}. \end{aligned} \]

计算伪码为

5. 参数估计

参数应极大化对数似然

\[l(\alpha, \beta) = \sum_{d=1}^{M} \log p(w_d|\alpha, \beta), \]

但是对数似然却难以计算. 我们可以利用变分推断得到的下界近似对数似然, 可以在EM算法的M步, 极大化证据下界以更新变分参数 \(\gamma\)\(\phi\), 而对于固定的变分参数, 又可以通过极大化证据下界更新参数 \(\alpha\)\(\beta\).

EM算法:

  1. (E步)对每个文档, 寻找最优变分参数 \(\{\gamma_d^{*}, \phi_d^{*}: d\in D\}\), 这一步由变分推断得到;
  2. (M步)通过极大化证据下界更新参数 \(\alpha\)\(\beta\).

其中第二步中, 参数 \(\beta\) 可以解析表示

\[\beta_{ij} \propto \sum_{d=1}^{M}\sum_{n=1}^{N_d} \phi_{dni}^{*} w_{dn}^j, \]

但参数 \(\alpha\) 则需要用Newton-Raphson方法计算.

接下来希望能够弄清楚具体的代码实现.