首页
学习
活动
专区
工具
TVP
发布
社区首页 >专栏 >LDA—基础知识

LDA—基础知识

原创
作者头像
用户1062972
发布2019-07-05 18:47:21
1.1K0
发布2019-07-05 18:47:21
举报
文章被收录于专栏:machine learningmachine learning

一、简介

隐含狄利克雷分布(Latent Dirichlet Allocation,简称LDA)是由 David M. Blei、Andrew Y. Ng、Michael I. Jordan 在2003年提出的,是一种词袋模型,它认为文档是一组词构成的集合,词与词之间是无序的。一篇文档可以包含多个主题,文档中的每个词都是由某个主题生成的,LDA给出文档属于每个主题的概率分布,同时给出每个主题上词的概率分布。LDA是一种无监督学习,在文本主题识别、文本分类、文本相似度计算和文章相似推荐等方面都有应用。

二、基础知识

1.1 贝叶公式

贝叶斯学派的最基本的观点是:任一个未知量 都可看作一个随机变量,应该用一个概率分布去描述对 的未知状况,这个概率分布是在抽样前就有关于 的先验信息的概率陈述,这个概率分布被称为先验分布。

从贝叶斯观点看,样本 的产生要分两步进行,首先设想从先验分布 产生一个样本 ,这一步是“老天爷”做的,人们是看不到的,故用“设想”二字。第二步是从总体分布 产生一个样本 ,这个样本是具体的,人们能看得到的,此样本 发生的概率是与如下联合密度函数成正比。

这个联合密度函数是综合了总体信息和样本信息,常称为似然函数,记为 。

由于 是设想出来的,它仍然是未知的,它是按先验分布 产生的,要把先验信息进行综合,不能只考虑 ,而应对 的一切可能加以考虑,故要用 参与进一步综合,所以样本 和参数 的联合分布(三种可用的信息都综合进去了):

我们的任务是要对未知数 作出统计推断,在没有样本信息时,人们只能根据先验分布对 作出推断。在有样本观察值 之后,我们应该依据 对 作出推断,为此我们把 作如下分解:

其中 是 的边缘密度函数。

它与 无关, 中不含 的任何信息。因此能用来对 作出推断的仅是条件分布 :

这就是贝叶斯公式的密度函数形式,在样本 给定下, 的条件分布被称为 的后验分布。它是集中了总体、样本和先验等三种信息中有关 的一切信息,而又是排除一切与 无关的信息之后得到的结果,故基于后验分布 对 进行统计推断是更合理的。

一般说来,先验分布 是反映人们在抽样前对 的认识,后验分布 是反映人们在抽样后对 的认识,之间的差异是由于样本 的出现后人们对 认识的一种调整,所以后验分布 可以看作是人们用总体信息和样本信息(抽样信息)对先验分布 作调整的结果。下面我们介绍三种估计方法:

1. 最大似然估计(ML)

最大似然估计是找到参数 使得样本 的联合概率最大,并不会考虑先验知识,频率学派和贝叶斯学派都承认似然函数,频率学派认为参数 是客观存在的,只是未知。求参数 使似然函数最大,ML估计问题可以用下面公式表示:

通常可以令导数为 0 求得 的值。ML估计不会把先验知识考虑进去,很容易出现过拟合的现象。我们举个例子,抛一枚硬币,假设正面向上的概率为 ,抛了 次,正面出现 次,反面出现 次, 表示正面, 表示反面,我们用ML估计:

如果 , ,则 ,似乎比我们认知的 0.5 高了很多。

2. 最大后验估计(MAP)

MAP是为了解决ML缺少先验知识的缺点,刚好公式(5)后验概率集中了样本信息和先验信息,所以MAP估计问题可以用下面公式表示:

MAP不仅希望似然函数最大,还希望自己出现的先验概率也最大,加入先验概率,起到正则化的作用,如果 服从高斯分布,相当于加一个L2范数正则化,如果 服从拉普拉斯分布,相当于加一个L1范数正则化。我们继续前面抛硬币的例子,大部分人认为 应该等于0.5,那么还有少数人认为 取其他值,我们认为 的取值服从Beta分布。

我们取 ,即 以最大的概率取0.5,得到 。

3. 贝叶斯估计

前面介绍的 ML 和 MAP 属于点估计,贝叶斯估计不再把参数 看成一个未知的确定值,而是看成未知的随机变量,利用贝叶斯定理结合新的样本信息和参数 的先验分布,来得到 的新的概率分布(后验分布)。贝叶斯估计的本质是通过贝叶斯决策得到参数 的最优估计 ,使得贝叶斯期望损失最小。贝叶斯期望损失为:

是损失函数,我们希望 最小。如果 ,则:

所以贝叶斯估计值为在样本 条件下 的期望值,贝叶斯估计的步骤为:

  • 确定参数 的先验分布
  • 利用贝叶斯公式,求 的后验分布:
  • 求出贝叶斯的估计值:

我们继续前面的抛硬币的例子,后验概率:

其中 B(α,β)=∫10pα−1(1−p)β−1dp,所以可以得:

^p=n(1)+αn(1)+n(0)+α+β(15)

1.2 Gamma函数

Γ(x)=∫∞0tx−1e−tdt(16)

通过分部积分的方法,可以得到一个递归性质。

Γ(x+1)=∫∞0txe−tdt=−∫∞0txde−t=−[txe−t]∞0+∫∞0e−tdtx=x∫∞0tx−1e−tdt=xΓ(x)(17)

Γ(x) 函数可以当成是阶乘在实数集上的延拓,Γ(n)=(n−1)!。

1.3 二项分布

在概率论中,试验 E 只有两个可能结果:A 及 ¯A ,则称 E 为伯努利(Bernoulli)试验。设 p(A)=p,则 p(¯A)=1−p。将 E 独立重复地进行 n 次,则称这一串重复的独立试验为 n 重伯努利试验,这里重复是指在每次试验中 p(A)=p 保持不变,独立是指各次试验的结果互不影响。以 X 表示 n 重伯努利试验中事件 A 发生的次数,称随机变量 X 服从参数为 n,p 的二项分布,记为 X∼B(n,p)。

p(X=k)=(nk)pk(1−p)n−k(18)

1.4 Beta分布

Beta分布是指一组定义在 (0,1) 区间的连续概率分布,其概率密度函数是:

Beta(p|α,β)=pα−1(1−p)β−1∫10pα−1(1−p)β−1dp=Γ(α+β)Γ(α)Γ(β)pα−1(1−p)β−1(19)

1)B(α,β)=Γ(α)Γ(β)Γ(α+β)=∫10pα−1(1−p)β−1dp。Γ(α)=∫∞0xα−1e−xdx,Γ(β)=∫∞0yβ−1e−ydy

证明:

Γ(α)Γ(β)=∫∞0xα−1e−xdx∫∞0yβ−1e−ydy=∫∞0∫∞0xα−1yβ−1e−(x+y)dydx(20)

令 t=x+y,当 y=0,t=x;y=∞,t=∞,可得:

Γ(α)Γ(β)=∫∞0∫∞xxα−1(t−x)β−1e−tdtdx=∫∞0∫t0xα−1(t−x)β−1e−tdxdt(21)

令 x=μt,μ∈[0,1],可得:

Γ(α)Γ(β)=∫∞0∫10(μt)α−1(t−μt)β−1e−tdμtdt=∫∞0tα+β−1e−tdt∫10μα−1(1−μ)β−1dμ=Γ(α+β)∫10μα−1(1−μ)β−1dμΓ(α)Γ(β)Γ(α+β)=∫10μα−1(1−μ)β−1dμ(22)

2)期望 E(p)=αα+β

证明:

E(p)=∫10pΓ(α+β)Γ(α)Γ(β)pα−1(1−p)β−1dp=Γ(α+β)Γ(α)Γ(β)∫10pα(1−p)β−1dp=Γ(α+β)Γ(α)Γ(β)Γ(α+1)Γ(β)Γ(α+β+1)∫10Γ(α+β+1)Γ(α+1)Γ(β)pα(1−p)β−1dp=Γ(α+β)Γ(α)Γ(β)Γ(α+1)Γ(β)Γ(α+β+1)∫10Beta(p|α+1,β)dp=Γ(α+β)Γ(α)Γ(β)αΓ(α)Γ(β)(α+β)Γ(α+β)=αα+β(23)

1.5 多项式分布

多项式分布是二项式分布的推广,二项式分布做 n 次伯努利试验,规定每次试验的结果只有两个,而多项式分布在 N 次独立试验中结果有 K 种,且每种结果都有一个确定的概率 p,仍骰子是典型的多项式分布。

Mult(→n|→p,N)=(N→n)K∏k=1pnkk(24)

其中 K∑k=1nk=N,K∑k=1pk=1(N→n)=N!∏knk!。

1.6 Dirichlet分布

Dirichlet 分布是 Beta 分布在高维度上的推广,概率密度函数是:

Dir(→p|→α)=Γ(∑Kk=1αk)∏Kk=1Γ(αk)K∏k=1pαk−1k=1Δ(→α)K∏k=1pαk−1k(25)

1)Δ(→α)=∏Kk=1Γ(αk)Γ(∑Kk=1αk)=∫10K∏k=1pαk−1kd→p

2)期望 E(→p)=(α1∑Kk=1αk,α2∑Kk=1αk,⋅⋅⋅,αK∑Kk=1αk)。

1.7 共轭先验分布

在贝叶斯中,如果后验分布与先验分布属于同类分布,则先验分布与后验分布被称为共轭分布,而先验分布被称为似然函数的共轭先验。

1.Beta-Binomial共轭

1)先验分布

Beta(p|α,β)=1B(α,β)pα−1(1−p)β−1(26)

2)二项式似然函数

B(n1,n2|p)=(nn1)pn1(1−p)n2(27)

3)后验分布

B(n1,n2|p)Beta(p|α,β)∫10B(n1,n2|p)Beta(p|α,β)dp=pα+n1−1(1−p)β+n2−1∫10pα+n1−1(1−p)β+n2−1dp=pα+n1−1(1−p)β+n2−1B(α+n1,β+n2)∼Beta(α+n1,β+n2)(28)

即可以表达为 Beta(p|α,β)+B(n1,n2|p)=Beta(p|α+n1,β+n2),取一个特殊情况理解

Beta(p|1,1)+B(α−1,β−1|p)=Beta(p|α,β),Beta(p|1,1) 恰好是均匀分布 uniform(0,1),假设有一个不均匀的硬币抛出正面的概率为 p,抛出 n 次后出现正面和反面的次数分别是 n1 和 n2 ,开始我们对硬币不均匀性一无所知,所以应该假设 p∼uniform(0,1) ,当有了试验样本,我们加入样本信息对 p 的分布进行修正, p 的分布由均匀分布变为 Beta 分布。

2.Dirichlet-Multinomial共轭

1)先验分布

Dir(→p|→α)=1Δ(→α)K∏k=1pαk−1k(29)

2)多项分布似然函数

Mult(→n|→p,N)=(N→n)K∏k=1pnkk(30)

3)后验分布

Dir(→p|→α)Mult(→n|→p,N)∫10Dir(→p|→α)Mult(→n|→p,N)d→p=K∏k=1pαk+nk−1k∫10K∏k=1pαk+nk−1kd→p=K∏k=1pαk+nk−1kΔ(→α+→n)∼Dir(→p|→α+→n)(31)

即可以表达为 Dir(→p|→α)+Mult(→n|→p,N)=Dir(→p|→α+→n)

1.8 马氏链及其平稳分布

马氏链的数学定义很简单,状态转移的概率只依赖于前一个状态。

P(Xt+1=x|Xt,Xt−1,⋅⋅⋅)=P(Xt+1=x|Xt)(32)

看一个马氏链的具体例子,马氏链表示股市模型,共有三种状态:牛市(Bull market)、熊市(Bear market)、横盘(Stagnant market),每一个转态都以一定的概率转化到下一个状态,如图1.1所示。

这个概率转化图可以以矩阵的形式表示,如果我们定义矩阵 P 某一位置 (i,j) 的值为 P(j|i),表示从状态 转化到状态 的概率,这样我们可以得到马尔科夫链模型的状态转移矩阵为:

P=⎛⎜⎝0.90.0750.0250.150.80.050.250.250.5⎞⎟⎠

假设初始概率分布为 π0=[0.30.40.3],π1=π0P,π2=π1P=π0P2,⋅⋅⋅,πn=πn−1P=π0Pn。从第60轮开始 π60,⋅⋅⋅,πn 的值保持不变,为 [0.6250.31250.0625] 。我们更改初始概率,π0=[0.70.20.1],从55轮开始 π55,⋅⋅⋅,πn 的值保持不变,为 [0.6250.31250.0625] 。两次给定不同的初始概率分布,最终都收敛到概率分布 π=[0.6250.31250.0625] ,也就是说收敛的行为和初始概率分布 π0 无关,这个收敛的行为主要是由概率转移矩阵 P 决定的,可以计算下 Pn。

P63=P64=⋅⋅⋅=⎡⎢⎣0.6250.31250.06250.6250.31250.06250.6250.31250.0625⎤⎥⎦

当 n 足够大的时候,Pn 矩阵的每一行都是稳定地收敛到 π=[0.6250.31250.0625] 这个概率分布。这个收敛现象并不是这个马氏链独有的,而是绝大多数马氏链独有的。关于马氏链的收敛有如下定理:

定理1.1 如果一个非周期马氏链具有转移概率矩阵 P,且它的任何两个状态是连通的,那么 limn→∞Pnij 存在且与 i 无关,我们有:

1)limn→∞Pnij=π(j)

2)limn→∞Pn=⎡⎢ ⎢ ⎢ ⎢ ⎢ ⎢⎣π(1)π(2)⋅⋅⋅π(j)⋅⋅⋅π(1)π(2)⋅⋅⋅π(j)⋅⋅⋅⋅⋅⋅⋅⋅⋅⋅⋅⋅⋅⋅⋅⋅⋅⋅π(1)π(2)⋅⋅⋅π(j)⋅⋅⋅⋅⋅⋅⋅⋅⋅⋅⋅⋅⋅⋅⋅⋅⋅⋅⎤⎥ ⎥ ⎥ ⎥ ⎥ ⎥⎦

3)π(j)=∞∑i=0π(i)Pij

4)π 是方程 πP=π 的唯一非负解,其中 π=[π(1)π(2)⋅⋅⋅π(j)⋅⋅⋅],∞∑j=1π(j)=1。

关于上述定理,给出几点解释:

1) 马氏链的状态数可以是有限的,也可以是无限的,因此可以用于连续概率分布和离散概率分布。

2) 非周期马氏链:马氏链的状态转化不是循环的,如果是循环的则永远不会收敛,我们遇到的一般都是非周期马氏链。对于任意某一状态 i,d 为集合 {n|n≥1,Pnii>0} 的最大公约数,如果 d=1,则该状态为非周期。

3) 任何两个状态是连通的:从任意一个状态可以通过有限步到达其他的任意状态,不会出现条件概率一直为0导致不可达的情况。

4) π 称为马氏链的平稳分布。

如果从一个具体的初始状态 x0 开始,沿着马氏链按照概率转移矩阵做跳转,那么可以得到一个转移序列 x0,x1,⋅⋅⋅,xn,xn+1,⋅⋅⋅,由于马氏链的收敛行为, 都将是平稳分布 的样本。

1.9 MCMC

1. 接受-拒绝采样

对于不常见的概率分布 样本,使用接受-拒绝采样对可采样的分布 进行采样得到,如图1.2所示,采样得到 的一个样本 ,从均匀分布 中采样得到一个值 ,如果 落在图中灰色区域则拒绝这次采样,否则接受样本 ,重复上面过程得到 个接受的样本,则这些样本服从 分布,具体过程见算法1.1。

下面我们来证明下接受-拒绝方法采样得到的样本服从 分布。

证明:accept 服从 分布,即 。

2. MCMC

给定概率分布 ,希望能够生成它对应的样本,由于马氏链能收敛到平稳分布,有一个很好的想法:如果我们能构造一个转移矩阵为 的马氏链,使得该马氏链的平稳分布恰好是 ,那么我们从任何一个初始状态出发沿着马氏链转移,得到一个转移序列 ,如果马氏链在第 步已经收敛了,于是我们可以得到 的样本 ,所以关键问题是如何构造转移矩阵 ,我们是基于下面的定理。

定理1.2(细致平稳条件) 如果非周期马氏链的转移矩阵 和分布 满足:

则 是马氏链的平稳分布。

证明很简单,有公式(34)得:

,满足马氏链的收敛性质。这样我们就有了新的思路寻找转移矩阵 ,即只要我们找到矩阵 使得概率分布 满足细致平稳条件即可。

假设有一个转移矩阵为 的马氏链( 表示从状态 转移到状态 的概率),通常情况下很难满足细致平稳条件的,即:

我们对公式(36)进行改造,使细致平稳条件成立,引入 。

如何取值才能使公式(37)成立?最简单的我们可以取:

, 所以我们有:

转移矩阵 满足细致平稳条件,因此马氏链 的平稳分布就是 !

我们可以得到一个非常好的结论,转移矩阵 可以通过任意一个马氏链转移矩阵 乘以 得到, 一般称为接受率,其取值范围为 ,可以理解为一个概率值,在原来的马氏链上,从状态 以 的概率跳转到状态 的时候,我们以一定的概率 接受这个转移,很像前面介绍的接受-拒绝采样,那里以一个常见的分布通过一定的接受-拒绝概率得到一个不常见的分布,这里以一个常见的马氏链状态转移矩阵 通过一定的接受-拒绝概率得到新的马氏链状态转移矩阵 。

总结下MCMC的采样过程。

MCMC采样算法有一个问题,如果接受率 比较小,马氏链容易原地踏步,拒绝大量的跳转,收敛到平稳分布 的速度很慢,有没有办法可以使 变大?

3. M-H采样

M-H采样可以解决MCMC采样接受概率过低问题,回到公式(37),若 ,,即:

公式(40)两边同时扩大5倍,仍然满足细致平稳条件,即:

所以我们可以把公式(37)中的 和 同比例放大,使得其中最大的放大到 1,这样提高了采样中的接受率,细致平稳条件也没有打破,所以可以取:

提出一个问题:按照MCMC中介绍的方法把 ,是否可以保证 每行加和为1?

1.10 Gibbs Sampling

对于高维的情形,由于接受率 ,M-H 算法效率不够高,我们能否找到一个转移矩阵 使得接受率 呢?从二维分布开始,假设 是一个二维联合概率分布,考察某个特征维度相同的两个点 和 ,容易发现下面等式成立:

所以可得:

也就是:

观察细致平稳条件公式,我们发现在 这条直线上,如果用条件分布 作为任何两点之间的转移概率,那么任何两点之间的转移都满足细致平稳条件。同样的,在 这条直线上任取两点 和 ,我们可以得到:

基于上面的发现,我们可以构造分布 的马氏链的状态转移矩阵 。

有了上面的转移矩阵 ,很容易验证对于平面任意两点 ,都满足细致平稳条件。

所以这个二维空间上的马氏链将收敛到平稳分布 ,称为Gibbs Sampling算法。

整个采样过程中,我们通过轮换坐标轴,得到样本 ,马氏链收敛后,最终得到的样本就是 的样本。当然坐标轴轮换不是必须的,我们也可以每次随机选择一个坐标轴进行采样,在 时刻,可以在 轴和 轴之间随机的选择一个坐标轴,然后按照条件概率做转移。

二维可以很容易推广到高维的情况,在 维空间中对于概率分布 。

1.11 EM算法

我们先介绍凸函数的概念, 的定义域是实数集,若 且 ,则 是凸函数,若 ,则 是严格凸函数;若 是向量且hessian矩阵 是半正定矩阵,则 是凸函数,若 是正定矩阵,则 是严格凸函数。

定理1.3(Jensen不等式) 的定义域是实数集,且是凸函数,则有:

如果 是严格凸函数,只有当 是常量,公式(49)等式成立即 。

假设训练集 ,每个样本相互独立,我们需要估计模型 的参数 ,由于含有隐变量 ,所以很难直接用最大似然求解,如果 已知,那么就可以用最大似然求解。

其实我们的目标是找到 和 使 最大,也就是分别对 和 求偏导,然后令其为0,理想是美好的,现实是残酷的,公式(49)求偏导后变的很复杂,求导前要是能把求和符号从对数函数中提出来就好了。EM算法可以有效地解决这个问题,引入 表示 的概率分布()。由公式(50)可得:

最后一步是利用Jensen不等式,,,所以 是凹函数,是 的期望,所以有:

由公式(51)可知,我们可以不断地最大化下界,以提高 ,最终达到最大值。如果固定 ,那么 的下界就取决于 ,可以通过调整这个概率,使得下界不断地上升逼近 ,最终相等,然后固定 ,调整 ,使下界达到最大值,此时 为新的值,再固定 ,调整 ,反复直到收敛到 的最大值。现在我们有两个问题需要证明,1. 下界何时等于 ;2. 为什么可以收敛到最大值。

第一个问题,由Jensen不等式定理中等式成立条件可知, 为常量,即:

再由 得:

下面我们先给出 EM 算法,然后再讨论第二个问题,E步:固定 ,根据公式(53)选择 使得下界等于 ,M步:最大化下界,得到新的 值。EM算法如下:

现在我们开始讨论第二个问题, 和 是EM迭代过程的参数估计,我们需要证明 ,也就是EM算法是单调地提高 ,。

第一个不等式是因为:

公式(57)中,,。

第二个不等式是因为 是为了

参考文献

1(http://www.arbylon.net/publications/text-est.pdf)

2(http://www.iro.umontreal.ca/~nie/IFT6255/Hofmann-UAI99.pdf)

3(http://www.jmlr.org/papers/volume3/blei03a/blei03a.pdf)

5(http://cs229.stanford.edu/notes/cs229-notes8.pdf)

原创声明:本文系作者授权腾讯云开发者社区发表,未经许可,不得转载。

如有侵权,请联系 cloudcommunity@tencent.com 删除。

原创声明:本文系作者授权腾讯云开发者社区发表,未经许可,不得转载。

如有侵权,请联系 cloudcommunity@tencent.com 删除。

评论
登录后参与评论
0 条评论
热度
最新
推荐阅读
目录
  • 一、简介
  • 二、基础知识
    • 1.1 贝叶公式
      • 1.2 Gamma函数
        • 1.3 二项分布
          • 1.4 Beta分布
            • 1.5 多项式分布
              • 1.6 Dirichlet分布
                • 1.7 共轭先验分布
                  • 1.8 马氏链及其平稳分布
                    • 1.9 MCMC
                      • 1.10 Gibbs Sampling
                        • 1.11 EM算法
                        领券
                        问题归档专栏文章快讯文章归档关键词归档开发者手册归档开发者手册 Section 归档