Advertisement

机器学习：《统计学习方法》笔记（三）—— EM算法

阅读量：

参考：《统计学习方法》——李航；

摘要

介绍了EM算法的推导过程、步骤及在三硬币模型中的应用等内容。

正文

1. 什么地方要用EM算法

EM算法主要用于含有隐含变量的模型参数估计问题 。如果概率模型的变量都是观测变量，那么给定数据，可以直接用极大似然估计或极大后验估计。当概率模型含有隐含变量时，就需要用EM算法来估计参数了。EM算法就是含有隐含变量的概率模型参数的极大似然估计或极大后验估计。

2. EM算法的推导

给定观测数据Y，目标是极大化观测数据（不完全数据）Y关于参数heta的对数似然函数，即
L=og P=og um_{Z}P=og eft um_Z P Pight
P表示在模型参数为heta时，观测数据Y的概率分布。
egin{align*} P&=um_Z P=um_Z PP &=i py(1-p){1-y}+qy(1-q){1-y} nd{align*}

EM算法通过逐步迭代来逐步近似极大化L。假设第i次迭代后heta的估计值为heta^{}。下一轮的估计值heta要使L> L} 。故
L-L} =og eft um_Z PP ight -og P}

利用Jensen不等式得到下界：
egin{align*} L-L} &=og eft um_Z P} rac{P P}{P} } ight - og P} &eq um_Z P} og rac{P P}{P}} - og P} &= um_Z P} og rac{P P}{P}} - um_ZP} og P} &= um_Z P} og rac{P P}{P} P}} nd{align*}

令
B}=L}+um_Z P} og rac{P P}{P} P}}是

则
B}是L的一个下界。任何可使B}增大的heta，都可以使L增加。选择能使当前B}极大的heta^{}作为新的heta值。
egin{align*} heta^{} &=rg ax }+um_Z P} og rac{P P}{P} P}} &=rg ax }og P &=rg ax }og &=rg ax Q} nd{align*}

所以EM算法就是通过迭代不断求Q函数，并将之极大化，直至收敛。下图为EM算法的直观解释，B}是L的一个下界。

图中，在heta^{}处两个函数的函数值相等，当前迭代中，要找到heta^{}使B}极大化。EM算法在点heta^{}处重新计算Q函数，进行下次迭代。笔者认为这时B}的图像发生变化，不再是上图。

从图中可以看出，EM算法不能保证全局最优。

3. EM算法的步骤

分为E步和M步，即求Q函数，极大化Q函数。

输入：观测数据Y，隐变量数据Z，联合分布P，条件分布P；

输出：模型参数heta。

第一步：选取参数heta的初始值heta{(0)}=(\pi^{(0)},p{},q^{}；（注：模型为p=i py(1-p){1-y}+qy(1-q){1-y}）

第二步（E步）：假设第i迭代后，模型代参数为heta^{}，在第i+1次迭代的E步，计算
egin{align*} Q} &= E_Z &=um_Z P} og P nd{align*}
P}是给定观测数据Y和当前的参数估计heta^{}下隐变量数据Z的条件概率分布；

第三步（M步）：极大化Q函数，求出heta^{}=rg ax Q}；

第四步：重复E步，M步直到收敛。

停止迭代的条件：eft heta{(i+1)}-\theta{} ight <arepsilon_1 或eft Q}, heta{(i)})-Q(\theta^{(i)},\theta{} ight <arepsilon_2。

4. EM算法的收敛性

EM算法的收敛性是指EM算法得到的估计序列是否收敛，主要由两个定理来证明 。

定理一：P为观测数据的似然函数，heta^{}是EM算法得到的参数估计序列，P}是对应的似然函数序列，则P}是单调递增的。

定理二：L=og P是观测数据的对数似然函数，heta^{}是EM算法得到的参数估计序列，L}是对应的对数似然函数序列。如果P有上界，则L}=og P}收敛到某一值L^*；在函数Q与L满足一定条件下，EM算法得到的参数估计序列heta^{}的收敛值heta^*是L的稳定点。

这里不再展开讨论。

5. 三硬币模型的EM算法

问题：有三枚硬币（ABC）正面向上的概率分别为i，p和q。进行如下试验——先掷A，如果A正面向上则掷B，如果A反面向上则掷C。如此独立地重复做n次试验；记录B和C的结果，正面向上记为1，反面向上记为0。观测结果为：1,1,0,0,1,0，...。

若只能观测到结果，不能观测到掷硬币过程，即每一次的观测结果（1或0）由B或C中的哪枚硬币掷出的是未知的。如此情况下估计三枚硬币正面向上的概率i，p和q。观测数据表示为Y=^T，未观测数据表示为Z=^T。

一次实验得到的概率为
P=i py(1-p){}+qy(1-q){}

y是观测变量，结果为1或0；

所以三硬币模型可以写作：
egin{align*} P &=um_Z P &=um_Z PP &=i py(1-p){}+qy(1-q){} nd{align*}

故
egin{align*} P &=um_Z PP &=rod_{j=1}^{n} nd{align*}
at{heta}=rg ax_heta og P

EM算法先对参数选初始值heta{(0)}=(\pi^{(0)},p{},q^{}，再迭代直至收敛；设第i次迭代的估计值为heta{(i)}=(\pi^{(i)},p{},q^{}

在第i+1次，E步的计算为，计算数据y_j来自硬币B的概率
u{(i+1)}=\frac{\pi{}}}{(1-y_i)}}{\pi{}}}{(1-y_i)}+(1-\pi^{(i)})(q^{(i)})(1-q^{(i)}){}}

M步计算模型参数的新估计值
i{(i+1)}=\frac{1}{n}\sum_{j=1}{n}u_j^{}
p{(i+1)}=\frac{\sum_{j=1}{n}u_{j}{(i+1)}y_{j}}{\sum_{j=1}{n}u_{j}^{}}
q{(i+1)}=\frac{\sum_{j=1}{n}y_j}{um_{j=1}^{n}}

注1：本博客只作笔者笔记用途，仅供参考用，若有侵权行为请留言联系，笔者会在第一时间回复。

注2：码字不易，若转载请注明出处。

全部评论 (0)

还没有任何评论哟~

相关文章推荐

机器学习：《统计学习方法》笔记（三）—— EM算法

参考：《统计学习方法》——李航； 摘要 介绍了EM算法的推导过程、步骤及在三硬币模型中的应用等内容。 正文 1\.什么地方要用EM算法 EM算法主要用于含有隐含变量的模型参数估计问题。如果概率模型的变...

统计学习方法笔记9—EM算法2

9.2EM算法的收敛性 收敛定理9.1 观测数据的似然函数单调递增 收敛定理9.2 EM算法是收敛性包含对数似然函数序列的收敛性和关于参数估计序列的收敛性，即一定可以通过迭代发现似然函数的极值点。

统计学习方法 第九章笔记： EM 算法

文章目录 三硬币模型 EM推导背景 EM算法步骤 EM算法的导出 EM算法的收敛性 如果概率模型都是观测变量，那么给定数据就可以用极大似然估计法或者贝叶斯估计发去获得模型。但是，有时候概率模型既有观测...

机器学习笔记之EM算法(四)广义EM

机器学习笔记之EM算法——广义EM 引言 回顾：引如隐变量与EM算法的本质 狭义EM与广义EM 回顾：狭义EM算法 狭义EM算法的问题 引言 上一节介绍了引入隐变量的本质，本节将狭义EM算法推广至广义...

EM算法学习笔记

EMistypicallyusedtocomputemaximumlikelihoodestimatesgivenincompletesamples.TheEMalgorithmestimatesth...

《机器学习》 小白Python学习笔记（十） ————EM算法

《机器学习》小白Python学习笔记（十）————EM算法 简介 算法原理 算法流程 简介 作为数据挖掘十大算法之一的EM算法的全称是ExpectationMaximizationAlgorithm，...

机器学习笔记之EM算法(三)隐变量与EM算法的本质

机器学习笔记之EM算法——隐变量与EM算法的本质 引言 回顾：EM算法 从性质上介绍EM算法 其他概念回顾 线性回归 感知机算法 支持向量机 需要使用EM算法求解的问题 概率生成模型 EM算法的本质 ...

机器学习笔记之统计学习方法三要素

前言 本学期学习了机器学习的课程，读了《统计学习方法》——李航著，做为笔记。统计学习方法都是由模型、策略和算法构成的，作为初学者，可能大部分人都直接上手，各种python库一顿乱调，但其实知识不成体系...

王小草【机器学习】笔记--EM算法

标签（空格分隔）：王小草机器学习笔记 EM算法的英文全称是ExpectationMaximizationAlgorithm，也就是求期望最大化，也就是我们常说的目标函数求最大值的算法。

统计学习方法---EM

EM算法详解 基本了解 什么是EM算法？ EM的全称是ExpectationMaximization即期望最大化。它是用来求解含有隐变量的概率模型参数的参数估计方法。