Latent dirichlet allocation note
By: Zhou Li ()
Blog:
Code&Doc: /p/lsa-lda/
July 31, 2009
1 基础知识：贝叶斯统计
假设有两个箱子，每个箱子装了8个球，A箱子3个红球5个白球，B箱子6个红球2个白球。如果问从A箱子摸出一个红球的概率，那么答案是3/8，如果问从B箱子摸出一个白球的概率，那么为2/8。这样的正向推理很简单。但是如果问摸出一个红球，它是从A箱子中摸出的概率是多少，这又如何求呢？贝叶斯方法正是用来求这种”逆”概率。 P(X,Y)表示X,Y的联合概率，有如下公式P(X,Y)=P(Y|X)P(X)，由于P(X,Y)=P(Y,X)，于是我们得到P(Y|X)P(X)=P(X|Y)P(Y)，将左边P(X)移到右边得到：
这就是贝叶斯公式，其中P(Y|X)称为后验分布，P(X)称为先验分布，P(X|Y)称为似然函数。贝叶斯问题的详细描述可以参考Pattern Recognition and Machine Learning[1].该书第一章对 贝叶斯方法做了详细的解释。
下面讨论一个概率问题，一对夫妇有两个孩子，已知其中一个是男孩，问另一个也是男孩的概率？
令A=另一个也是男孩B=已知其中一个是男孩
由贝叶斯：P(A|B) = P(B|A)P(A)/P(B)
其中P(B|A) = 1 ，因为另一个也是男孩，表示两个都是男孩。
P(A) = 0.25 即如果有两个孩子，两个都是男孩的概率0.25
P(B) = 0.75 即如果有两个孩子，那么其中一个是男孩的概率为0.75
因此P(A|B) = 1*0.25/0.75=1/3
1.1 基础知识：Dirichlet distribution
假设我们在和一个不老实的人玩掷骰子游戏。按常理我们觉得骰子每一面出现的几率都是
1/6，但是掷骰子的人连续掷出6，这让我们觉得骰子被做了手脚，而这个骰子出现6的几率更高。而我们又不确定这个骰子出现6的概率到底是多少，所以我们猜测有50%的概率是：6出现的概率2/7，其它各面1/7；有25%的概率是：6出现的概率3/8，其它各面1/8；还有25%的概率是：每个面出现的概率都为1/6，也就是那个人没有作弊，走运而已。用图表表示如下：
我们所猜测的值，如果设为X的话，则表示X的最自然的分布便是Dirichlet distribution。设随机变量X服从Dirichlet分布，简写为Dir(α)，即X~Dir(α)。Α是一个向量，表示的是某个事件出现的次数。比如对于上例，骰子的可能输出为{1,2,3,4,5,6}，假设我们分别观察到了5次1~5，10次6，那么α = {5,5,5,5,
5,10}。X则表示上例中的各种概率组合，比如{1/7,1/7,1/7, 1/7,1/7,2/7}；{1/8, 1/8, 1/8, 1/8, 1/8, 3/8}；{1/6, 1/6, 1/6, 1/6, 1/6, 1/6}，那么P(X)则表示了该概率组合出现的概率，也就是概率的概率。
以下是公式：
下图来自WIKI[2]，图像化了当K=3时的dirichlet分布。
Dirichlet分布的重要性质：
Dirichlet分布是多项分布的共轭分布，也就是说，先验分布为Dirichlet分布，似然函数为多项分布，那么后验分布仍为Dirichlet分布。
在LDA中，Dirichlet分布是为了描述文档—主题层面的概率分布，一个文档由多个主题组成，而Dirichlet分布描述了主题集合的分布。具体将在后面讨论。
之所以选择Dirichlet分布是因为其共轭特性大大减小了计算量。 1.2 基础知识：Expectation-Maximization (EM) Algorithm[3][4]
EM算法是用来计算极大似然估计。EM有两个主要应用环境，第一个是观测到的数据不完整或其它原因导致数据丢失，第二个是似然函数无法直接计算但可以用隐含变量表示。LDA 中的参数估计属于后者。
概括的说，EM算法首先随机给每个参数赋值，然后迭代的执行两个步骤，分别叫做E-STEP 和M-STEP。在E-STEP，EM算法计算出期望的似然函数，由于这时已经为所有参数赋值，所以似然函数是可以计算的。在M-STEP，EM算法重新估计参数值，按照最大化似然函数的标准。这样多次迭代直到收敛为止。
本文大致讨论下EM的推理，更具体的分析参考Further Reading中EM相关资料。
假设某次迭代中我们估计的参数是θ(n)，而我们的目的是希望到θ(n+1)使得P(X|θ(n+1))尽可能的大于P(X|θ(n))。将lnP(X|θ)表示成L(θ|X)，则我们的目标是使使下式尽可能的大：
(1)
现在考虑隐含变量Z：
于是(1)式改写成：
(2)
下面是The Expectation Maximization Algorithm A short tutorial[3]关于(2)式的推导：
因此：
(3)
现在令：
(4)
前面已经提高过，我们的目的是到θ，使得L(θ)最大。而从(3)，(4)中我们可以看到l(θ|θn)就是L(θ)的下界，所以我们的目标就成了到一个下界逼近L(θ):
E-STEP:
计算条件数学期望
M-STEP：
最大化这个数学期望，得出此时的θ。
1.3 基础知识：Variational Inference[5]
Variational Inference是用来估计后验分布的方法。该方法无法直接计算后验分布的情况。在Variational Message Passing and its Applications[5]的1.8节有该方法的非常详细的推理，我这里只大致介绍该方法的思想。
当我们遇到无法计算后验分布的情况，会希望使用一个函数来近似它，设为Q：
我们自然希望P,Q的差最小。这里的差用Kullback-Leibler (KL) divergence表示：
经过下式的变换：
可以从上面看到，右边的logP(D)不依赖于Q，所以我们的工作相当于使右式加号左边的表达式最小。另该项为L(Q)：
经过推导（具体见论文[5]）可得下式：
右边第一项为似然函数，第二项L(Q)相当于一个下界。要使KL尽量下，就要使右边两项尽可能的接近。所以L(Q)相当于logP(D|H)的下界。我们现在要做的，就是用L(Q)下届逼近logP(D|H)。还要记住我们是要用Q(H)来近似后验分布，因此我们需要一个可解的Q。最简单的方法是认为Q的n个参数都是独立的，于是：
豫公网安备41160202000603
站长QQ:729038198
关于我们
投诉建议