2.14 EM算法

最大期望算法(Expectation-Maximization Algorithm,EM算法),是一类通过迭代进行极大似然估计的优化算法,通常作为牛顿迭代法的替代,用于对包含隐变量或缺失数据的概率模型进行参数估计。

2.14.1 EM算法的基本思想

EM算法的基本思想经过两个步骤交替计算。

(1)计算期望(下文称为“E步”),利用对隐藏变量的现有估计值,计算其极大似然估计值。

(2)最大化(下文称为“M步”),最大化在E步上求得的极大似然值来计算参数的值。

M步上找到的参数估计值被用于下一个E步计算中,这个过程不断交替进行。

2.14.2 EM算法推导

对于m个样本观察数据,现在想找出样本的模型参数θ,其极大化模型分布的对数似然函数为:

如果得到的观察数据有未观察到的隐含数据,那么极大化模型分布的对数似然函数则为:

因为上式不能直接求出θ,所以采用缩放技巧:

上式用到了Jensen不等式:

并且引入了一个未知的新分布

此时,如果需要满足Jensen不等式中的等号,所以有:

由于是一个分布,所以满足

综上,可得:

如果,则式(2-90)是我们的包含隐藏数据的对数似然的一个下界。如果能极大化这个下界,则也在尝试极大化对数似然。即需要最大化下式:

简化得:

以上即为EM算法的M步。此外,注意到上式中是一个分布,因此可理解为基于条件概率分布的期望,即为E步。

2.14.3 图解EM算法

考虑到式(2-89)中存在隐变量,直接找到参数估计比较困难,我们通过EM算法迭代求解下界的最大值到收敛为止。EM算法求解示意图如图2-23所示。

图2-23 EM算法求解示意图

在图2-23中,目标模型px|θ)复杂,难以求解析解,为了消除隐变量的影响,可以选择一个不包含的模型rx|θ),使其满足条件

求解步骤如下。

(1)选取θ1,使得,然后对此时的r求取最大值,得到极值点θ2,实现参数的更新。

(2)重复以上过程到收敛为止,在更新过程中始终满足rp

2.14.4 EM算法流程

输入:观察数据,联合分布pxzθ),条件分布pz|xθ),最大迭代次数J

(1)随机初始化模型参数θ的初值θ0

(2)设当前迭代次数为jj从1到J进行迭代:

• E步。计算联合分布的条件概率期望:

• M步。极大化Lθθj),得到θj+1

• 如果θj+1收敛,则算法结束,否则继续进行E步迭代。

输出:模型参数θ