先验知识

Gamma 函数

Beta/Dirichlet 分布与共轭

MCMC, 吉布斯采样

这块资料暂时自己去找, 等我有空写了 $\textrm{MCMC}$ 的教程再补上.

LDA 介绍

构成

 $\textrm{LDA (Latent Dirichlet Allocation)}$ 是一种词袋模型. 由语料, 文档, 话题. , 这三个概念组成.

  • 语料

    语料是文档的集合.

  • 文档

    文档是词的集合, 可以看做是一篇作文, 或是像这篇一样的博文, 反正就是一篇完整的文本.

  • 话题

    话题给出了某个词出现的概率. 到底是啥呢? $\textrm{LDA}$ 认为, 文档中每个词都应该有它的话题, 词是由话题来生成的. 比如说某个词的话题是 “概率论” , 那么这个词就很有可能是 “$\textrm{Gamma}$ 函数” , 而不太可能是 “吃饭” . “可能” 与 “不太可能” 在数学上用概率描述, 而话题就给出了这个概率的值.

  • 这应该无需多解释, “词” 本身就是一个词. 文档是由一个个词组成的

生成文档过程

生成文本的过程, 就像是上帝抛骰子. 关于这个骰子如何抛, 频率派与贝叶斯派有不同的解释, 而 $\textrm{LDA}$ 就是基于贝叶斯派的解释.

频率派

频率派认为, 上帝有两种骰子, 一种是 $\textrm{doc-topic}$ 骰子, 它有 $K$ 个面, 每个面都是一个 $\textrm{topic}$ 的编号. 还有一种是 $\textrm{topic-word}$ 骰子, 一共有 $K$ 个, 正好对应 $\textrm{doc-topic}$ 的 $K$ 个面. 每个 $\textrm{topic-word}$ 骰子有 $V$ 个面, 每一个面都对应一个词. 生成文档包括两个过程:抛投 骰子, 得到一个 编号.

  1. 抛投 $\textrm{doc-topic}$ 骰子, 得到一个 $\textrm{topic}$ 编号.
  2. 按照这个 $\textrm{topic}$ 编号, 找到对应的 $\textrm{topic-word}$ 骰子, 再次抛投, 生成一个词.

假如说一个文档有 $N$ 个词, 那么以上过程就重复 $N$ 次, 这样就生成了这篇文档所有的词, 这篇文档也就生成完毕.

贝叶斯派

对于这样的抛骰子过程, 贝叶斯派可就不满意了. 无论是 $\textrm{doc-topic}$ 骰子, 还是 $\textrm{topic-word}$ 骰子, 都是模型里的参数, 参数都是随机变量, 怎么能没有先验呢?

于是, 就有了两大缸骰子, 一缸装了 $\textrm{doc-topic}$ 骰子, 一缸装了 $\textrm{topic-word}$ 骰子, 相比频率派, 贝叶斯派多了 $1,2$ 两个过程.

  1. 从 $\textrm{topic-word}$ 缸中取出 $K$ 个 $\textrm{topic-word}$ 骰子, 每个 $\textrm{topic-word}$ 骰子有 $V$ 个面, 每一个面都对应一个词.
  2. 从 $\textrm{doc-topic}$ 缸中取出一个 $\textrm{doc-topic}$ 骰子, 所有的 $\textrm{doc-topic}$ 骰子都只有 $K$ 个面.
  3. 抛投 $\textrm{doc-topic}$ 骰子, 得到一个 $\textrm{topic}$ 编号.
  4. 按照这个 $\textrm{topic}$ 编号, 找到对应的 $\textrm{topic-word}$ 骰子, 再次抛投, 生成一个词. 如果一篇文档所有的词没有生成完毕, 那么就跳到第 $3$ 点继续重复生成词.

执行完这 $4\,$$ 个过程一篇文档就生成完成, 然后重新回到 $2\,$$ , 生成下一篇文档 (也就是说 $K\,$$ 个 $\textrm{topic-word}\,$$ 骰子不用重新抽取), 直到整个语料 (包含 $M\,$$ 篇文档) 生成完毕, 也就是重复 $M\,$$ 次. **每篇文档都是独立的, 每个词也是, 所以生成的过程可以互相交换.** ## 目标  $\textrm{LDA}$ 的目标就是给定文档 然后估计文档中每个词的 $\textrm{topic}$ , 以及估计出你取到的 $\textrm{doc-topic}$ 骰子与 $\textrm{topic-word}$ 骰子到底是长啥样 (每个面的概率) . 我们这里将某篇文档的 $\textrm{doc-topic}$ 骰子记为 $\vec{\theta}m$ , 整个语料中的 $\textrm{doc-topic}$ 骰子记为 $\vec{\theta}_1,\dots,\vec{\theta}_M$ . $\vec\theta_m$ 向量的每个分量的值就是取到某个 $\textrm{topic}$ 编号的概率. 而 $K$ 个 $\textrm{topic-word}$ 骰子记为 $\vec\varphi_1, \vec\varphi_2,\dots,\vec\varphi_K$ . 我们的目的就是求出 $\varphi_1, \varphi_2,\dots,\varphi_K$ 与 $\vec{\theta}_1,\dots,\vec{\theta}_M$. 我们再将每篇文档中的词记为 $\vec{w}$ , 整个语料 $\mathcal{W}$ 包含 $M$ 篇文档记为 $\vec{\boldsymbol{\mathrm{w}}}=(\vec{w}_1,\dots\vec{w}_M)$ , 所有的 $\textrm{word}$ 对应的 $\textrm{topic}$ 记为 $\boldsymbol{\vec{\mathrm{z}}}=(\vec{z}_1,\dots\vec{z}_M)$ . ## 先验分布 由于 $\textrm{topic}$ 与 $\textrm{word}$ 的数量服从 $\textrm{Multinomial}$ 分布, 很自然就把骰子的分布设为与其共轭的 $\textrm{Dirichlet}$ 分布. 于是有 $$ p(\vec\theta_m\mid\vec{\alpha})=Dir(\vec\theta_m\mid \vec{\alpha})\\\\ p(\vec\varphi_k\mid\vec{\beta})=Dir(\vec\varphi_k\mid\vec{\beta})\\\\ p(\vec n_m\mid\vec\theta_m)= Mult(\vec n_m\mid\vec\theta_m)\\\\ p(\vec n_k\mid\vec z_m,\varphi)=Mult(\vec n_k\mid \vec z_m,\varphi) $$ 其中 $\vec\alpha, \vec\beta$ 是 $\textrm{Dirichlet}$ 分布的参数, 求取前就已经确定, $\varphi=(\vec\varphi_1, \vec\varphi_2,\dots,\vec\varphi_K)$ , $N_m$ 是第 $m$ 篇文档中词的数量. $\vec{n}_m=(\vec{n}_m^{(1)},\dots,\vec{n}_m^{(K)})$ , 它的分量 $\vec{n}_m^{(k)}$ 代表第 $m$ 篇文档中第 $k$ 个 $\textrm{topic}$ 产生的词的数量. $\vec{n}_k=(\vec{n}_k^{(1)},\dots,\vec{n}_k^{(V)})$ , $\vec n_k^{(v)}$ 表示第 $k$ 个 $\textrm{topic}$ 产生的词中 $\mathrm{word}\;v$ 的个数. 当然这里表述有点不严谨, 因为都用的是字母 $n$ , 只是根据下标区别. ## 联合分布 这里注意到, 整个 $\textrm{LDA}$ 过程就是 $(M+K)$ 个 $\textrm{Dirichlet-Multinomial}$ 共轭. $$ p(\vec{\boldsymbol{\mathrm{w}}}, \boldsymbol{\vec{\mathrm{z}}}\mid\vec{\alpha},\vec{\beta})=p(\vec{\boldsymbol{\mathrm{w}}}\mid \boldsymbol{\vec{\mathrm{z}}},\vec{\beta})p(\boldsymbol{\vec{\mathrm{z}}}\mid \vec{\alpha}) $$ 现在我们要分别求出 $p(\vec{\boldsymbol{\mathrm{w}}}\mid \boldsymbol{\vec{\mathrm{z}}},\vec{\beta})$ , 与 $p(\boldsymbol{\vec{\mathrm{z}}}\mid \vec{\alpha})$ .这里设. 那么有 $$ \begin{aligned} p(\boldsymbol{\vec{\mathrm{z}}}\mid \vec{\alpha})&=\prod_{m=1}^Mp(\vec{z}_m\mid\vec{\alpha})\\\\ &=\prod_{m=1}^M\int p(\vec{z}_m\mid\vec{\theta}_m)p(\vec{\theta}_m\mid\vec{\alpha})\,\rm{d}\vec{\theta}_m\\\\ &=\prod_{m=1}^M\int p(\vec{z}_m\mid\vec{\theta}_m) Dir(\vec\theta_m\mid \vec{\alpha})\,\rm{d}\vec{\theta}_m\\\\ &=\prod_{m=1}^M\int \prod_{k=1}^K{\left(\vec{\theta}_m^{(k)}\right)}^{\vec{n}_m^{(k)}}\frac{1}{\Delta(\vec{\alpha})} \prod_{k=1}^K{\left(\vec{\theta}_m^{(k)}\right)}^{\alpha_v-1}\,\mathrm{d}\vec{\theta}_m\\\\ &=\prod_{m=1}^M\frac{1}{\Delta(\vec{\alpha})}\int \prod_{k=1}^K{\left(\vec{\theta}_m^{(k)}\right)}^{\vec{n}_m^{(k)}+\alpha_v-1} \,\mathrm{d}\vec{\theta}_m\\\\ &=\prod_{m=1}^M\frac{\Delta(\vec{n}_m+\vec{\alpha})}{\Delta(\vec{\alpha})} \end{aligned} $$ 上式已经给出了 $M$ 个 $\textrm{Dirichlet-Multinomial}$ 共轭. 其中 $\Delta(\vec\alpha)$ 是归一化因子, 也可以看做是高维的 $\textrm{Beta}$ 函数. (本来还想根据规律称其为狄利克雷函数, 但是这个名字已经被占用了) . $$ \Delta(\vec\alpha)=\int\prod_{k=1}^K{\left(\vec{\theta}_m^{(k)}\right)}^{\alpha_k-1}\,\mathrm{d}\vec{\theta}_m $$ 还记得我上面提到的吗, 由于**每篇文档都是独立的, 每个词也是, 所以生成的过程可以互相交换.** 那么在每个词的 $\textrm{topic}$ (也就是 $\vec{\varphi}$ 与 $\vec{z}_m$) 已经生成的条件下, 可以将语料中的词进行交换, 将相同 $\textrm{topic}$ 的词放在一起生成 $$ \vec{\boldsymbol{\mathrm{w}}}'=(\vec{w}_{(1)},\dots\vec{w}_{(K)})\\\\ \boldsymbol{\vec{\mathrm{z}}}'=(\vec{z}_{(1)},\dots\vec{z}_{(K)}) $$ 因此有 $$ \begin{aligned} p(\vec{\boldsymbol{\mathrm{w}}}\mid \boldsymbol{\vec{\mathrm{z}}},\vec{\beta})&=p(\vec{\boldsymbol{\mathrm{w}}}'\mid \boldsymbol{\vec{\mathrm{z}}}',\vec{\beta})\\\\ &=\prod_{k=1}^Kp(\vec{w}_{(k)}\mid\vec{z}_{(k)}, \vec\beta)\\\\ &=\prod_{k=1}^K\int p(\vec w_{(k)}\mid\vec z_{(k)},\vec\varphi_k)p(\vec\varphi_k\mid\vec{\beta})\,\mathrm{d}\vec\varphi_k\\\\ &=\prod_{k=1}^K\int \prod_{v=1}^V\left({\vec\varphi_k^{(v)}}\right)^{\vec n_k^{(v)}}\frac{1}{\Delta(\vec{\beta})}\prod_{v=1}^V\left({\vec\varphi_k^{(v)}}\right)^{\vec\beta_v-1}\,\mathrm{d}\vec\varphi_k\\\\ &=\prod_{k=1}^K\frac{1}{\Delta(\vec{\beta})}\int \prod_{v=1}^V\left({\vec\varphi_k^{(v)}}\right)^{\vec n_k^{(v)}+\vec\beta_v-1}\,\mathrm{d}\vec\varphi_k\\\\ &=\prod_{k=1}^K\frac{\Delta(\vec{n}_k+\vec{\beta})}{\Delta(\vec{\beta})} \end{aligned} $$  $\Delta(\beta)\,$$ 同样是归一化因子 $$
\Delta(\beta)=\int \prod
{v=1}^V\left({\vec\varphik^{(v)}}\right)^{\vec\beta_v-1}\,\mathrm{d}\vec\varphi_k
$$ 最终有 $$
\begin{aligned}
p(\vec{\boldsymbol{\mathrm{w}}}, \boldsymbol{\vec{\mathrm{z}}}\mid\vec{\alpha},\vec{\beta})&=p(\vec{\boldsymbol{\mathrm{w}}}\mid \boldsymbol{\vec{\mathrm{z}}},\vec{\beta})p(\boldsymbol{\vec{\mathrm{z}}}\mid \vec{\alpha})\\
&=\prod
{k=1}^K\frac{\Delta(\vec{n}k+\vec{\beta})}{\Delta(\vec{\beta})}\prod{m=1}^M\frac{\Delta(\vec{n}m+\vec{\alpha})}{\Delta(\vec{\alpha})}
\end{aligned}
$$ 多么简洁漂亮! ## 吉布斯采样 我们要估计的是 $p(\boldsymbol{\vec{\mathrm{z}}}\mid\vec{\boldsymbol{\mathrm{w}}})$ , 根据吉布斯采样的要求, 我们要求出 $p(z_i\mid\boldsymbol{\vec{\mathrm{z}}}
{-i},\vec{\boldsymbol{\mathrm{w}}})$ . $$ p(z_i=k\mid\boldsymbol{\vec{\mathrm{z}}}_{-i},\vec{\boldsymbol{\mathrm{w}}})p(w_i=v\mid\boldsymbol{\vec{\mathrm{z}}}_{-i},\vec{\boldsymbol{\mathrm{w}}}_{-i})=p(z_i=k,w_i=v\mid\boldsymbol{\vec{\mathrm{z}}}_{-i},\vec{\boldsymbol{\mathrm{w}}}_{-i}) $$ 注意到 $p(wi=t\mid\boldsymbol{\vec{\mathrm{z}}}{-i},\vec{\boldsymbol{\mathrm{w}}}{-i})$ 与 $p(z_i=k\mid\boldsymbol{\vec{\mathrm{z}}}{-i},\vec{\boldsymbol{\mathrm{w}}})$ 无关, 因此有 $$ p(z_i=k\mid\boldsymbol{\vec{\mathrm{z}}}_{-i},\vec{\boldsymbol{\mathrm{w}}})\propto p(z_i=k,w_i=v\mid\boldsymbol{\vec{\mathrm{z}}}_{-i},\vec{\boldsymbol{\mathrm{w}}}_{-i}) $$ 那么就有 $$ \begin{aligned} p(z_i=k\mid\boldsymbol{\vec{\mathrm{z}}}_{-i},\vec{\boldsymbol{\mathrm{w}}})&\propto p(z_i=k,w_i=v\mid\boldsymbol{\vec{\mathrm{z}}}_{-i},\vec{\boldsymbol{\mathrm{w}}}_{-i})\\\\ &=\left(\int p(z_i=k,\vec\theta_m\mid\boldsymbol{\vec{\mathrm{z}}}_{-i},\vec{\boldsymbol{\mathrm{w}}}_{-i})\,\mathrm{d}\vec\theta_m\right)\left(\int p(w_i=v,\vec{\varphi}_k\mid\boldsymbol{\vec{\mathrm{z}}}_{-i},\vec{\boldsymbol{\mathrm{w}}}_{-i})\,\mathrm{d\vec\varphi_k}\right)\\\\ &=\left(\int p(z_i=k\mid\vec{\theta}_m)p(\vec\theta_m\mid\boldsymbol{\vec{\mathrm{z}}}_{-i},\vec{\boldsymbol{\mathrm{w}}}_{-i})\,\mathrm{d}\vec\theta_m\right)\left(\int p(w_i=v\mid \vec\varphi_k)p(\vec{\varphi}_k\mid\boldsymbol{\vec{\mathrm{z}}}_{-i},\vec{\boldsymbol{\mathrm{w}}}_{-i})\,\mathrm{d\vec\varphi_k}\right) \end{aligned} $$ 注意到 $p(\vec\thetam\mid\boldsymbol{\vec{\mathrm{z}}}{-i},\vec{\boldsymbol{\mathrm{w}}}{-i})$ 是一个 $\textrm{Dirichlet-Multinomial}$ 共轭结构即 $$ Dir(\vec\theta_m\mid\vec\alpha)+Mult(\vec n_m\mid \vec\theta_m)=Dir(\vec\theta_m\mid\vec n_m+\vec\alpha) $$ 所以 $$ p(\vec\theta_m\mid\boldsymbol{\vec{\mathrm{z}}}_{-i},\vec{\boldsymbol{\mathrm{w}}}_{-i})=Dir(\vec\theta_m\mid\vec n_{m,-i}+\vec\alpha) $$  $p(\vec{\varphi}_k\mid\boldsymbol{\vec{\mathrm{z}}}{-i},\vec{\boldsymbol{\mathrm{w}}}_{-i})$ 也有类似的结论. 因此有 $$ \begin{aligned} p(z_i=k\mid\boldsymbol{\vec{\mathrm{z}}}_{-i},\vec{\boldsymbol{\mathrm{w}}})&\propto \left(\int p(z_i=k\mid\vec{\theta}_m)p(\vec\theta_m\mid\boldsymbol{\vec{\mathrm{z}}}_{-i},\vec{\boldsymbol{\mathrm{w}}}_{-i})\,\mathrm{d}\vec\theta_m\right)\left(\int p(w_i=v\mid \vec\varphi_k)p(\vec{\varphi}_k\mid\boldsymbol{\vec{\mathrm{z}}}_{-i},\vec{\boldsymbol{\mathrm{w}}}_{-i})\,\mathrm{d\vec\varphi_k}\right)\\\\ &=\left(\int \theta_{mk} Dir(\vec\theta_m\mid\vec n_{m,-i}+\vec\alpha)\,\mathrm{d}\vec\theta_m\right)\left(\int \varphi_{kv}Dir(\vec\varphi_k\mid\vec n_{k,-i}+\vec\beta)\,\mathrm{d\vec\varphi_k}\right)\\\\ &=E(\theta_{mk})E(\varphi_{kv})\\\\ &=\hat{\theta}_{mk}\hat{\varphi}_{kv} \end{aligned} $$ 根据 $\textrm{Dirichlet}$ 分布的期望, 我们得到 $$ \hat{\theta}_{mk}=\frac{\vec{n}_{m,-i}^{(k)}+\alpha_k}{\sum_{k=1}^K(\vec{n}_{m,-i}^{(k)}+\alpha_k)}\\\\ \hat{\varphi}_{kv}=\frac{\vec{n}_{k,-i}^{(v)}+\alpha_k}{\sum_{v=1}^V(\vec{n}_{k,-i}^{(v)}+\alpha_k)} $$ 因此 $$ p(z_i=k\mid\boldsymbol{\vec{\mathrm{z}}}_{-i},\vec{\boldsymbol{\mathrm{w}}})\propto\frac{\vec{n}_{m,-i}^{(k)}+\alpha_k}{\sum_{k=1}^K(\vec{n}_{m,-i}^{(k)}+\alpha_k)}\cdot\frac{\vec{n}_{k,-i}^{(v)}+\alpha_k}{\sum_{v=1}^V(\vec{n}_{k,-i}^{(v)}+\alpha_k)} $$ 通过吉布斯采样, 我们就可以估计出 $\varphi_1, \varphi_2,\dots,\varphi_K$ 与 $\vec{\theta}_1,\dots,\vec{\theta}_M$ 了.