机器学习之从极大似然估计到最大熵原理以及EM算法详解

简介: 一、极大似然估计极大似然估计是建立在极大似然原理的基础上的一个统计方法,极大似然原理的直观想法是,一个随机试验如有若干个可能的结果A,B,C,… ,若在一次试验中,结果A出现了,那么可以认为实验条件对A的出现有利,也即出现的概率P(A)较大。

一、极大似然估计

极大似然估计是建立在极大似然原理的基础上的一个统计方法,极大似然原理的直观想法是,一个随机试验如有若干个可能的结果A,B,C,… ,若在一次试验中,结果A出现了,那么可以认为实验条件对A的出现有利,也即出现的概率P(A)较大。极大似然原理的直观想法我们用下面例子说明。设甲箱中有99个白球,1个黑球;乙箱中有1个白球.99个黑球。现随机取出一箱,再从抽取的一箱中随机取出一球,结果是黑球,这一黑球从乙箱抽取的概率比从甲箱抽取的概率大得多,这时我们自然更多地相信这个黑球是取自乙箱的。一般说来,事件A发生的概率与某一未知参数 θ θ有关, θ θ取值不同,则事件A发生的概率P(A| θ θ)也不同,当我们在一次试验中事件A发生了,则认为此时的 θ θ值应是t的一切可能取值中使P(A| θ θ)达到最大的那一个,极大似然估计法就是要选取这样的t值作为参数t的估计值,使所选取的样本在被选的总体中出现的可能性为最大。

假设总体分布为f(x, θ θ), X1,X2,X3...Xn X1,X2,X3...Xn为该总体采样取得的样本。因为 X1,X2,X3...Xn X1,X2,X3...Xn是独立同分布的,于是,它的联合密度函数为:

L(X1,X2...Xn;θ1,θ2...θk)=i=1nf(xi;θ1,θ2...θk)
L(X1,X2...Xn;θ1,θ2...θk)=ni=1f(xi;θ1,θ2...θk)

在上面这个式子中, θ θ被看做是确定但是未知的参数,并且应为样本已经存在,所以 x1,x2,x3...xn x1,x2,x3...xn也是固定的。因此 L(x,θ) L(x,θ)是关于 θ θ的函数,即似然函数。求解参数 θ θ的值,使似然函数取得极大值,这就是极大似然估计。

在实践中,由于求导数的需要,往往将似然函数取对数,得到对数似然函数;如果似然函数可导,那么就可以通过求导数的方式得到驻点,从而算出极大值。

logL(θ1,θ2...θk)=ni=1logf(xi;θ1,θ2...θk) logL(θ1,θ2...θk)=ni=1logf(xi;θ1,θ2...θk)
L(θ)θi=0,i=1,2....k L(θ)θi=0,i=1,2....k

求极大似然估计量的一般步骤:
(1)写出似然函数;
(2)对似然函数取对数,并整理;
(3)求导数;
(4)解似然方程。

例子:

这里写图片描述
这里写图片描述

极大似然估计的特点:

1.比其他估计方法更加简单;
2.收敛性:无偏或者渐近无偏,当样本数目增加时,收敛性质会更好;
3.如果假设的类条件概率模型正确,则通常能获得较好的结果。但如果假设模型出现偏差,将导致非常差的估计结果。


二、最大熵原理

最大熵原理是一种选择随机变量统计特性最符合客观情况的准则,也称为最大信息原理。随机量的概率分布是很难测定的,一般只能测得其各种均值(如数学期望、方差等)或已知某些限定条件下的值(如峰值、取值个数等),符合测得这些值的分布可有多种、以至无穷多种,通常,其中有一种分布的熵最大。选用这种具有最大熵的分布作为该随机变量的分布,是一种有效的处理方法和准则。这种方法虽有一定的主观性,但可以认为是最符合客观情况的一种选择。在投资时常常讲不要把所有的鸡蛋放在一个篮子里,这样可以降低风险。在信息处理中,这个原理同样适用。在数学上,这个原理称为最大熵原理。

那么,到底什么是熵呢?简单来说,熵是对平均不确定性的度量:

H(X)=xϵXp(x)lnp(x) H(X)=xϵXp(x)lnp(x)

由以上公式可知,熵是随机变量不确定性的度量,不确定性越大,熵也越大;当随机变量变成一个确定的值时,熵就变成了0。需要指出的是均匀分布是“最不确定”的分布。

最大熵的一般模型:

max(pϵP)H(Y|X)=(x,y)p(x,y)logp(y|x) max(pϵP)H(Y|X)=(x,y)p(x,y)logp(y|x)

其中P={p|p是X上满足条件的概率分布}

这里写图片描述

这里写图片描述

例子:

假设随机变量X有5个取值{A,B,C,D,E},且满足条件P(A)+P(B)=0.3且P(A)+P(B)+P(C)+P(D)+P(E)=1。求最大熵模型。

为了方便,分别用 y1 y1~ y5 y5表示A~E,于是最大熵模型的最优化问题是:

minH(p)=5i=1p(yi)logp(yi) minH(p)=5i=1p(yi)logp(yi)

s.t.p(y1)+p(y2)=p˜(y1)+p˜(y2)=310 s.t.p(y1)+p(y2)=˜p(y1)+˜p(y2)=310

5i=1p(yi)=5i=1p˜(yi)=1 5i=1p(yi)=5i=1˜p(yi)=1

引进拉格朗日乘子w0和w1,定义拉格朗日函数如下:

L(p,w)=p(yi)logp(yi)+w1(p(y1)+p(y2)310)+w0(i=15p(yi)1)
L(p,w)=p(yi)logp(yi)+w1(p(y1)+p(y2)310)+w0(5i=1p(yi)1)

根据拉格朗日对偶性,可以通过求解对偶最优化问题得到原始最优化问题的解。所以求解max min L(p,w)首先需要求解关于p的极小化问题。为此需要固定w0和w1。求偏导数:

L(p,w)p(y1)=1+logp(y1)+w1+w0 L(p,w)p(y1)=1+logp(y1)+w1+w0

L(p,w)p(y2)=1+logp(y2)+w1+w0 L(p,w)p(y2)=1+logp(y2)+w1+w0

L(p,w)p(y3)=1+logp(y3)+w0 L(p,w)p(y3)=1+logp(y3)+w0

L(p,w)p(y4)=1+logp(y4)+w0 L(p,w)p(y4)=1+logp(y4)+w0

L(p,w)p(y5)=1+logp(y5)+w0 L(p,w)p(y5)=1+logp(y5)+w0

令上面的五个偏导数都等于0,可求得:

p(y1)=p(y2)=ew1w01p(y3)=p(y4)=p(y5)=ew01
p(y1)=p(y2)=ew1w01p(y3)=p(y4)=p(y5)=ew01

p(y1)p(y2)p(y3)p(y4)p(y5) p(y1)p(y2)p(y3)p(y4)p(y5)代入到 L(p,w) L(p,w)中,再求 L(p,w) L(p,w)关于w的极大化问题:

maxL(pw,w)=2ew1w013ew01310w1w0
maxL(pw,w)=2ew1w013ew01310w1w0

分别对 w0 w0 w1 w1求偏导,并令其等于0,可以得到:

ew1w01=320ew01=730
ew1w01=320ew01=730

解得:

p(y1)=p(y2)=320p(y3)=p(y4)=p(y5)=730
p(y1)=p(y2)=320p(y3)=p(y4)=p(y5)=730

总结:

最大熵模型在分类方法里算是比较优的模型,但是由于它的约束函数的数目一般来说会随着样本量的增大而增大,导致样本量很大的时候,对偶函数优化求解的迭代过程非常慢,scikit-learn甚至都没有最大熵模型对应的类库。但是理解它仍然很有意义,尤其是它和很多分类方法都有千丝万缕的联系。 

优点

a) 最大熵统计模型获得的是所有满足约束条件的模型中信息熵极大的模型,作为经典的分类模型时准确率较高。

b) 可以灵活地设置约束条件,通过约束条件的多少可以调节模型对未知数据的适应度和对已知数据的拟合程度。

缺点

由于约束函数数量和样本数目有关系,导致迭代过程计算量巨大,实际应用比较难。


三、EM算法

首先举一个例子:

现在一个班里有50个男生,50个女生,且男生站左,女生站右。我们假定男生的身高服从正态分布: N(μ1,σ21) N(μ1,σ21),女生的身高则服从另一个正态分布: N(μ2,σ22) N(μ2,σ22) 。这时候我们可以用极大似然法(MLE),分别通过这50个男生和50个女生的样本来估计这两个正态分布的参数。但现在我们让情况复杂一点,就是这50个男生和50个女生混在一起了。我们拥有100个人的身高数据,却不知道这100个人每一个是男生还是女生。这时候情况就有点尴尬,因为通常来说,我们只有知道了精确的男女身高的正态分布参数我们才能知道每一个人更有可能是男生还是女生。但从另一方面去考量,我们只有知道了每个人是男生还是女生才能尽可能准确地估计男女各自身高的正态分布的参数。这个时候有人就想到我们必须从某一点开始,并用迭代的办法去解决这个问题:我们先设定男生身高和女生身高分布的几个参数(初始值),然后根据这些参数去判断每一个样本(人)是男生还是女生,之后根据标注后的样本再反过来重新估计参数。之后再多次重复这个过程,直至稳定。这个算法也就是EM算法。

假设我们有一个样本集{ x1,x2...xm x1,x2...xm},包含m个独立的样本。但每个样本i对应的类别 zi zi是未知的(相当于聚类),也即隐含变量。故我们需要估计概率模型p(x,z)的参数θ,但是由于里面包含隐含变量z,所以很难用最大似然求解,但如果z知道了,那我们就很容易求解了。

下面我们通过建立极大似然函数来建立目标函数:

l(θ)=i=1mlogp(x;θ)=i=1mlogzp(x,z;θ))
l(θ)=mi=1logp(x;θ)=mi=1logzp(x,z;θ))

进一步计算可得:
ilogp(x(i);θ)==ilogz(i)p(x(i),z(i);θ)(1)ilogz(i)Qi(z(i))p(x(i),z(i);θ)Qi(z(i))(2)iz(i)Qi(z(i))logp(x(i),z(i);θ)Qi(z(i))(3)
ilogp(x(i);θ)=ilogz(i)p(x(i),z(i);θ)(1)=ilogz(i)Qi(z(i))p(x(i),z(i);θ)Qi(z(i))(2)iz(i)Qi(z(i))logp(x(i),z(i);θ)Qi(z(i))(3)

本质上我们是需要最大化(1)式(对(1)式,我们回忆下联合概率密度下某个变量的边缘概率密度函数的求解,注意这里z也是随机变量。对每一个样本i的所有可能类别z求等式右边的联合概率密度函数和,也就得到等式左边为随机变量x的边缘概率密度),也就是似然函数,但是可以看到里面有“和的对数”,求导后形式会非常复杂(自己可以想象下log(f1(x)+ f2(x)+ f3(x)+…)复合函数的求导),所以很难求解得到未知参数z和θ。那OK,我们可否对(1)式做一些改变呢?我们看(2)式,(2)式只是分子分母同乘以一个相等的函数,还是有“和的对数”啊,还是求解不了,那为什么要这么做呢?咱们先不管,看(3)式,发现(3)式变成了“对数的和”,那这样求导就容易了。我们注意点,还发现等号变成了不等号,为什么能这么变呢?这就是Jensen不等式的大显神威的地方。

Jensen不等式

设f是定义域为实数的函数,如果对于所有的实数x。如果对于所有的实数x,f(x)的二次导数大于等于0,那么f是凸函数。当x是向量时,如果其hessian矩阵H是半正定的,那么f是凸函数。如果只大于0,不等于0,那么称f是严格凸函数。

Jensen不等式表述如下:

如果f是凸函数,X是随机变量,那么:E[f(X)]>=f(E[X])
特别地,如果f是严格凸函数,当且仅当X是常量时,上式取等号。Jensen不等式应用于凹函数时,不等号方向反向。

一般意义上的Jensen不等式可以参考:百度词条:Jensen不等式

回到公式(2),因为f(x)=log x为凹函数(其二次导数为 1x2<0 1x2<0)。

(2)式中 z(i)Qi(z(i))[p(x(i),z(i);θ)Qi(z(i))] z(i)Qi(z(i))[p(x(i),z(i);θ)Qi(z(i))] p(x(i),z(i);θ)Qi(z(i)) p(x(i),z(i);θ)Qi(z(i))的期望,(考虑到 E(X)=xp(x) E(X)=xp(x),f(x)是x的函数,则 E(f(X))=f(x)p(x) E(f(X))=f(x)p(x),又 zQi(z(i))=1 zQi(z(i))=1所以就可以得到公式(3)的不等式了。

OK,到这里,现在式(3)就容易地求导了,但是式(2)和式(3)是不等号啊,式(2)的最大值不是式(3)的最大值啊,而我们想得到式(2)的最大值,那怎么办呢?

现在我们就需要一点想象力了,上面的式(2)和式(3)不等式可以写成:似然函数 L(θ) L(θ)>=J(z,Q),那么我们可以通过不断的最大化这个下界J,来使得 L(θ) L(θ)不断提高,最终达到它的最大值。

这里写图片描述

见上图,我们固定 θ θ,调整Q(z)使下界J(z,Q)上升至与 L(θ) L(θ)在此点 θ θ处相等(绿色曲线到蓝色曲线),然后固定Q(z),调整θ使下界J(z,Q)达到最大值( θtθt+1 θtθt+1),然后再固定 θ θ,调整Q(z)……直到收敛到似然函数 L(θ) L(θ)的最大值处的 θ θ。这里有两个问题:什么时候下界J(z,Q)与 L(θ) L(θ)在此点 θ θ处相等?为什么一定会收敛?

首先第一个问题,在Jensen不等式中说到,当自变量X是常数的时候,等式成立。而在这里,即:

p(x(i),z(i);θ)Qi(z(i))=c
p(x(i),z(i);θ)Qi(z(i))=c

再推导下,由于 zQi(z(i))=1 zQi(z(i))=1(因为Q是随机变量z(i)的概率密度函数),则可以得到:分子的和等于c(分子分母都对所有z(i)求和:多个等式分子分母相加不变,这个认为每个样例的两个概率比值都是c),则:

Qi(z(i))=p(x(i),z(i);θ)zp(x(i),z;θ)=p(x(i),z(i);θ)p(x(i);θ)=p(z(i)|x(i);θ)
Qi(z(i))=p(x(i),z(i);θ)zp(x(i),z;θ)=p(x(i),z(i);θ)p(x(i);θ)=p(z(i)|x(i);θ)

至此,我们推出了在固定参数后,使下界拉升的Q(z)的计算公式就是后验概率,解决了Q(z)如何选择的问题。这一步就是E步,建立 L(θ) L(θ)的下界。接下来的M步,就是在给定Q(z)后,调整 θ θ,去极大化 L(θ) L(θ)的下界J(在固定Q(z)后,下界还可以调整的更大)。

EM算法整体框架:

这里写图片描述

E步(第一步):
如果是首次运行,则根据先验知识给定一个θ;如果不是,则这个θ就是M步求出来的。利用这个θ和样本x,求出隐变量z的条件概率,即Q。

M步(第二步): 将E步求出的Q带入式1后求出θ的最大值。 重复上面两步,直到收敛。

详细推导过程可以参考:(EM算法)The EM Algorithm

优缺点:

要有一些训练数据,再定义一个最大化函数,采用EM算法,利用计算机经过若干次迭代,就可以得到所需的模型。EM算法是自收敛的分类算法,既不需要事先设定类别也不需要数据见的两两比较合并等操作。缺点是当所要优化的函数不是凸函数时,EM算法容易给出局部最佳解,而不是最优解。

关于怎么更通俗易懂地理解EM算法可以参考以下链接:

https://www.zhihu.com/question/27976634/answer/39132183

https://www.zhihu.com/question/27976634/answer/153567695


理解EM算法的九层境界

参考资料:

  1. 从最大似然到EM算法浅解

  2. 百度文库:极大似然估计

目录
打赏
0
0
0
0
9
分享
相关文章
【重磅发布】AllData数据中台核心功能:机器学习算法平台
杭州奥零数据科技有限公司成立于2023年,专注于数据中台业务,维护开源项目AllData并提供商业版解决方案。AllData提供数据集成、存储、开发、治理及BI展示等一站式服务,支持AI大模型应用,助力企业高效利用数据价值。
K-means聚类算法是机器学习中常用的一种聚类方法,通过将数据集划分为K个簇来简化数据结构
K-means聚类算法是机器学习中常用的一种聚类方法,通过将数据集划分为K个簇来简化数据结构。本文介绍了K-means算法的基本原理,包括初始化、数据点分配与簇中心更新等步骤,以及如何在Python中实现该算法,最后讨论了其优缺点及应用场景。
322 6
AI训练师入行指南(三):机器学习算法和模型架构选择
从淘金到雕琢,将原始数据炼成智能珠宝!本文带您走进数字珠宝工坊,用算法工具打磨数据金砂。从基础的经典算法到精密的深度学习模型,结合电商、医疗、金融等场景实战,手把手教您选择合适工具,打造价值连城的智能应用。掌握AutoML改装套件与模型蒸馏术,让复杂问题迎刃而解。握紧算法刻刀,为数字世界雕刻文明!
86 6
基于机器学习的人脸识别算法matlab仿真,对比GRNN,PNN,DNN以及BP四种网络
本项目展示了人脸识别算法的运行效果(无水印),基于MATLAB2022A开发。核心程序包含详细中文注释及操作视频。理论部分介绍了广义回归神经网络(GRNN)、概率神经网络(PNN)、深度神经网络(DNN)和反向传播(BP)神经网络在人脸识别中的应用,涵盖各算法的结构特点与性能比较。
机器学习算法的优化与改进:提升模型性能的策略与方法
机器学习算法的优化与改进:提升模型性能的策略与方法
669 13
机器学习算法的优化与改进:提升模型性能的策略与方法
使用 PAI-DSW x Free Prompt Editing图像编辑算法,开发个人AIGC绘图小助理
使用 PAI-DSW x Free Prompt Editing图像编辑算法,开发个人AIGC绘图小助理
CCS 2024:如何严格衡量机器学习算法的隐私泄露? ETH有了新发现
在2024年CCS会议上,苏黎世联邦理工学院的研究人员提出,当前对机器学习隐私保护措施的评估可能存在严重误导。研究通过LiRA攻击评估了五种经验性隐私保护措施(HAMP、RelaxLoss、SELENA、DFKD和SSL),发现现有方法忽视最脆弱数据点、使用较弱攻击且未与实际差分隐私基线比较。结果表明这些措施在更强攻击下表现不佳,而强大的差分隐私基线则提供了更好的隐私-效用权衡。
105 14
解锁机器学习的新维度:元学习的算法与应用探秘
元学习作为一个重要的研究领域,正逐渐在多个应用领域展现其潜力。通过理解和应用元学习的基本算法,研究者可以更好地解决在样本不足或任务快速变化的情况下的学习问题。随着研究的深入,元学习有望在人工智能的未来发展中发挥更大的作用。
|
5月前
|
PAI下面的gbdt、xgboost、ps-smart 算法如何优化?
设置gbdt 、xgboost等算法的样本和特征的采样率
160 2
C语言在机器学习中的应用及其重要性。C语言以其高效性、灵活性和可移植性,适合开发高性能的机器学习算法,尤其在底层算法实现、嵌入式系统和高性能计算中表现突出
本文探讨了C语言在机器学习中的应用及其重要性。C语言以其高效性、灵活性和可移植性,适合开发高性能的机器学习算法,尤其在底层算法实现、嵌入式系统和高性能计算中表现突出。文章还介绍了C语言在知名机器学习库中的作用,以及与Python等语言结合使用的案例,展望了其未来发展的挑战与机遇。
119 1
AI助理

你好,我是AI助理

可以解答问题、推荐解决方案等