[LDA工程实践之算法篇-1]算法实现正确性验证

研究生二年级实习(2010年5月)开始,一直跟着王益(yiwang)和靳志辉(rickjin)学习LDA,包括对算法的理解、并行化和应用等等。毕业后进入了腾讯公司,也一直在从事相关工作,后边还在yiwang带领下,与孙振龙、严浩等一起实现了一套大规模并行的LDA训练系统——Peacock。受rick影响,决定把自己对LDA工程实践方面的一些理解整理出来,分享给大家,其中可能有一些疏漏和错误,还请批评指正。

Rickjin在《LDA数学八卦》[1]一文中已经对LDA的数学模型以及基本算法介绍得比较充分了,但是在工程实践上,我们还是有一些需要注意的问题,比如:

  • 怎样验证算法实现的正确性?
  • 怎样加速Gibbs sampling?
  • 在线推断(inference)时,需要注意些什么问题?
  • 超参数对模型的影响以及怎样做超参数优化?

本文将涉及以上内容,不包括:LDA并行化和应用,后续会在文章《LDA工程实践之架构篇》和《LDA工程实践之应用篇》中进行介绍。

为了方便大家理解,本文所有数学符号和 [2] 保持一致,具体见表 1。


Table 1: Symbols

1 算法实现正确性验证

在实现机器学习算法的时候,由于数值算法特有的收敛性问题,让这项本来相对简单的工作增加了难度。这其中的典型是多层次神经网络的优化算法——反向传播(Back Propagation,BP)算法,由于神经网络的强大表述能力,即使实现有误,在简单数据实验上,我们可能也发现不了问题。LDA算法的实现较BP简单,工作中我们常采用如下几个方法进行算法正确性的先期验证。

1.1 Toy data实验


Figure 1: KMeans toy data

在实现算法之前,toy data的准备必不可少。Toy data需要尽量简单——纬度低、数据量少,能表述清楚问题即可,这样方便我们实现算法时进行单元测试和调试。比如做KMeans聚类,可以采用2D高斯混合模型生成toy data(见图1,类别数为3)。LDA实现过程中,我们构造的toy data类似表 2(假设模型主题数 $K=2$),此时模型训练过程中的每一个迭代以及最终模型输出都是可预测的(表 2 数据收敛后,Doc1-3的词赋予的主题应该都是1,Doc4-6的词赋予的主题应该都是2,或者二者主题互换)。


Table 1: LDA toy data

随机算法在开发调试过程中,稳定不变的随机数序列是非常重要的,这样有利于定位问题。获取稳定不变的随机数非常简单,只需要我们额外提供一个伪随机数种子的命令行参数。

1.2 合成实验

算法包最终实现,toy data实验符合预期,此时如果我们想进一步验证LDA算法的效果呢?考虑到LDA是一种生成模型[3],Griffiths等人[4]在论文中采用合成实验来演示模型的效果,当然,这也可以作为算法正确性的验证。

假设已知LDA模型的主题数 $K$、词典大小 $V$、文档主题的超参数 $\vec{\alpha}$、主题 $k$ 的分布 $\vec{\varphi}_{k}$,生成 $M$ 个长度为 $N_m$ 文档的过程如算法LdaGenerate。

假设已知LDA模型主题数 $K$、文档主题超参数 $\vec{\alpha}$、词的超参数 $\beta$,训练文档 $\{\vec{w}\}$,以及迭代次数 $B$,LDA训练算法如算法LdaGibbs(注意:此处主要给出框架,具体算法可以参考[4,2])。其中具体符号含义可以参考表1,$i$ 表示当前词即 $i=(m, t)$,$\neg i$ 表示剔除词 $i$(比如 $n_{k,\neg i}$ 表示剔除词 $i$ 的主题后主题 $k$ 的频次,因此在具体实现算法时,通常采样之前会对 $n^{k}_m$、$n^{t}_k$ 和 $n_k$进行减减操作)。训练算法除了输出模型,还可以得到一个副产物 $\vec{\vartheta}_m$ ——训练文档 $m$ 的主题分布(Eq. 3)。

\begin{eqnarray}
p(z_i=k|\{\vec{z}\}_{\neg i}, \{\vec{w}\})
&=& \frac{n^{t}_{k,\neg i} + \beta}{n_{k,\neg i} + \beta V} \cdot \frac{n^{k}_{m,\neg i} + \alpha_k}{N_m – 1 + \sum^{K}_{k=1} \alpha_k} \notag \\
&\propto& \frac{n^{t}_{k,\neg i} + \beta}{n_{k,\neg i} + \beta V}(n^{k}_{m,\neg i} + \alpha_k) \label{eq:gibbs}
\end{eqnarray}

\begin{equation}\label{eq:phi}
\varphi_{k,t} = \frac{n^t_k + \beta}{n_k + \beta V}
\end{equation}

\begin{equation}\label{eq:theta}
\vartheta_{m,k} = \frac{n^k_m + \alpha_k}{N_m + \sum^{K}_{k=1} \alpha_k}
\end{equation}

给定 $\vec{\alpha}$ 和 $\Phi$,调用算法 LdaGenerate 即可生成 $M$ 个长度为 $N_m$ 的文档,将其作为训练集,调用LDA训练算法 LdaGibbs(将主题数设置为真实值) 即可得到预估的模型 $\tilde{\Phi}$。通过比对真实的模型 $\Phi$ 和预估的模型 $\tilde{\Phi}$,我们就可以验证算法实现的正确性。然而,LDA是一种聚类算法,并不保证预估模型的主题和真实模型的主题顺序一致,我们怎么找到对应关系呢?验证算法正确性时,我们将训练主题数设置为真实值,如果不是真实值会怎么样呢?小伙伴们赶紧自己动手试一试吧!


Figure 2: Griffiths Ground truth $\Phi$

Griffiths等人 [4] 为了使合成实验更加直观,将每个 $\vec{\varphi}_{k}$ 渲染成大小为 $\sqrt{V} \times \sqrt{V}$ 图片,其中 $\varphi^{t}_{k}$ 为对应图片位置的像素值(相当于将 $V$ 维向量 $\vec{\varphi}_{k}$ Reshape成大小为 $\sqrt{V} \times \sqrt{V}$的图像矩阵;同时,因为 $\vec{\varphi}_{k}$ 为浮点向量,图像像素值为0-255整数,我们需要将向量 $\vec{\varphi}_{k}$  元素值Normalized成0-255的整数,$\varphi^{t}_{k}$ 值越大,对应图像像素越“亮”)。Griffiths等人选用的真实 $\Phi$ 是10张包含白色Bar的图片,相当于 $K=10$,详情见图 2(真实模型 $\Phi_{10 \times V}$ 的一行对应一张图片)。


Figure 3: Griffiths Synthesis Experiment [4]

图 3 给出了预估 $\tilde{\Phi}$ 渲染成的图像随训练迭代的变化情况,可以看到预估 $\tilde{\Phi}$渲染成的图像逐渐“清晰”,模型质量越来越好。我们采用中国的十二生肖图像,重复了Griffiths等人的实验,如图 4 和 5。


Figure 4: Ground truth $\Phi$

Figure 5: Estimated $\tilde{\Phi}$

合成实验过程中需要用到Dirichlet采样,一般的标准库中没有提供:对c/c++来说,gsl [5] 是不错的选择;对python来说,numpy [6] 有提供实现。

合成实验的基本原理就是这样,虽然简单,但是如果我们善加利用,却可以得出许多有用的结论,比如利用合成实验来模拟LDA算法在“真实”的互联网语料数据上的表现。互联网语料的模型 $\Phi$ 至少应该具有如下性质:主题数 $K$ 非常大(比如几十万的级别);主题之间具有层次关系;语料中主题和词的出现频次应该满足长尾分布。给定满足这些性质的模型 $\Phi$ 以后,生成语料,我们就可以实验不同的训练算法变形的具体效果,以及各种算法参数对预估模型质量的影响。

1.3 Perplexity曲线

在自然语言处理中,Perplexity [7] 常用来度量语言模型的质量,值越小,模型质量越好。Perplexity定义为模型在给定测试集上每个词似然度(likelihood)的几何平均的倒数 [2,8]。在给定测试集 $\{\vec{w}\}$ 上,模型的Log Likelihood为 Eq. 4,Perplexity和Log Likelihood之间满足Eq. 5。
\begin{equation}\label{eq:logll}
\begin{aligned}
Loglikelihood(\{\vec{w}\}|\mathcal{M}) &= \sum^{M}_{m=1} \sum^{N_m}_{n=1} log\left(p(w_{m,n}|\mathcal{M})\right)
\end{aligned}
\end{equation}

\begin{equation}\label{eq:plexlogll}
\begin{aligned}
Perplexity(\{\vec{w}\}|\mathcal{M}) &= exp \left( -\frac{Loglikelihood(\{\vec{w}\}|\mathcal{M})}{\sum^{M}_{m=1} N_m} \right)
\end{aligned}
\end{equation}

具体到LDA模型,Perplexity计算公式如Eq. 6。训练过程中,计算Perplexity严谨的做法应该使用当前迭代获得的模型在线Inference测试集文档,得到文档的的主题分布后代入Eq. 6,在第三章我们将看到,在线Inference新文档的主题分布也满足
Eq. 3。当然,工程上为了节省计算资源,我们通常就在训练集上计算当前迭代的Perplexity。

\begin{equation}\label{eq:perplexity}
\begin{aligned}
Perplexity\left(\{\vec{w}\}|\mathcal{M}\right) &= \left(\prod^{M}_{m=1} \prod^{N_m}_{n=1} p\left(w_{m,n}|\mathcal{M}\right)\right)^{-\frac{1}{\sum^{M}_{m=1} N_m}} \\
&= exp\left(log\left(\left(\prod^{M}_{m=1} \prod^{N_m}_{n=1} p\left(w_{m,n}|\mathcal{M}\right)\right)^{-\frac{1}{\sum^{M}_{m=1} N_m}}\right)\right) \\
&= exp\left(-\frac{\sum^{M}_{m=1} \sum^{N_m}_{n=1} log\left(p\left(w_{m,n}|\mathcal{M}\right)\right)}{\sum^{M}_{m=1} N_m}\right) \\
&= exp\left(-\frac{\sum^{M}_{m=1} \sum^{N_m}_{n=1} log \sum^K_{k=1} p\left(w_{m,n},z_{m,n}=k|\mathcal{M}\right)}{\sum^{M}_{m=1} N_m}\right) \\
&= exp\left(-\frac{\sum^{M}_{m=1} \sum^{N_m}_{n=1} log \sum^K_{k=1} p\left(w_{m,n}=t|z_{m,n}=k\right)p\left(z_{m,n}=k|m\right)}{\sum^{M}_{m=1} N_m}\right) \\
&= exp\left(-\frac{\sum^{M}_{m=1} \sum^{N_m}_{n=1} log \sum^K_{k=1} \varphi_{k,t} \vartheta_{k,m}}{\sum^{M}_{m=1} N_m}\right) \\
\end{aligned}
\end{equation}

LDA模型训练过程中,随着迭代的进行,模型的Perplexity曲线会逐渐收敛。因此,我们通常会根据训练过程中模型的Perplexity曲线是否收敛来判定模型是否收敛。Perplexity曲线收敛性也从侧面可以证明算法实现的正确性。图 6 给出了一次模型训练过程的LogLikelihood和Perplexity曲线(主题数 $K=10,000$,迭代130左右的曲线突变将在第四章给出解释)。


Figure 6: LogLikelihood and perplexity curve

注意:合成实验小节中图 3 同时给出了模型训练过程中,Log Likelihood取值和预估 $\tilde{\Phi}$ 的图像情况,可以看到Log Likelihood曲线收敛后,预估 $\tilde{\Phi}$ 的图像任然有非常正向的变化,说明模型还在优化。因此,模型训练时,工程上一般在Log Likelihood曲线收敛后,任然继续进行一定量的迭代再输出最终模型。至于Log Likelihood曲线的收敛和模型的收敛之间的关系究竟如何呢,小伙伴们知道么?

参考文献

  • [1] 靳志辉. LDA数学八卦. http://cos.name/2013/03/lda-math-lda-text-modeling.
  • [2] Gregor Heinrich. Parameter estimation for text analysis. Technical Report, 2009.
  • [3] Generative model. http://en.wikipedia.org/wiki/Generative_model.
  • [4] Thomas L. Griffiths, and Mark Steyvers. Finding scientific topics. In PNAS ‘2004.
  • [5] http://www.gnu.org/software/gsl/manual/html_node/The-Dirichlet-Distribution.html.
  • [6] http://docs.scipy.org/doc/numpy/reference/generated/numpy.random.dirichlet.html.
  • [7] Perplexity. http://en.wikipedia.org/wiki/Perplexity.
  • [8] David M. Blei, Andrew Y. Ng, and Michael I. Jordan. Latent Dirichlet Allocation. In JMLR ‘2003.

本文链接:[LDA工程实践之算法篇-1]算法实现正确性验证
本站文章若无特别说明,皆为原创,转载请注明来源:火光摇曳,谢谢!^^


火光摇曳

[LDA工程实践之算法篇-1]算法实现正确性验证》有12个想法

  1. 这种LDA模型在实践中有个疑问:1.主题数K如何设置?有动态确定的办法吗? 2.如何设置超参数alpha和beta

    1. 1. 对lda,K一般还是根据应用来cross validation,没有非常好的办法。那些不设定K的算法或者有别的参数,或者工程实现上复杂度较高(比如hdp),我们没有采用。如果最优的K=1000,我们设置成了2000,其实效果上也差不多太多,所以。。。当然这个问题有学术上的价值。2. alpha/beta我们是自动优化的,当然初始值也有一些讲究,后边会有介绍。

      1. 是根据Parameter estimation for text analysis中的介绍自动优化的吗?优化,是在Training还是在Inference中?

  2. 博主。。。可不可以请教你几个问题。。。关于MCMC的。博主能否给我举一个其他方法不能采样的 而能用MCMC-Metropolis-Hastings(其实是不能理解其用途),另外算法中为什么要设置一个接受率。。。博主可否给一个你的联系方式 有问题 可以找你请教一下?

    1. 引入接受率,构造新的转移矩阵,让新构造的转移矩阵对应的平稳分布为p(x)

    2. 引入接受率,构造新的转移矩阵,让新构造的转移矩阵对应的平稳分布为p(x)

  3. 博主你好,请问如何确定训练文本的分类和LDA的分类的对应关系呢?我想的是用LDA再分类一下训练文本,然后就知道关系了。有没有更快的方法呢?谢谢!

  4. 博主你好~对于perplexity的计算还是有很多盲点,我用的是TEH的MATLAB的代码,里边没有给出perplexity的计算方法,自己去写的时候又不知道从何下手,您有时间的话可以给我提示一下么。 1055251337@qq.com 期待您的回复。

发表评论

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

*