期望最大算法优化：原理与应用

期望最大(Expectation-Maximization，EM)算法是一种迭代计算的最大似然过程，适用于不完全数据的参数估计，可用于估计隐随机变量或过程。EM过程的每次迭代由两步构成：E-步骤(Expectation，期望)和M-步骤(Maximization，最大化)。在E-步骤中，计算隐数据(给出观测数据和当前估计的参数)的似然条件期望；在M-步骤中，通过使在E-步骤中求得的条件期望最大，修正参数估计。

对图像数据而言，记观察到的图像数据为y，它是不完全数据。完全数据z应包含两部分z={x,y}，其中y是观测到的数据， x对应图像的分割结果，是不可见的数据，称为隐数据。采用EM算法可解决只给定图像数据的随机场的参数θ的极大似然估计问题：

(2.3-24)

在给定隐数据的初始值后，EM算法的迭代过程如下：

(1)根据当前参数θ的取值，估计隐数据即图像的一个分割结果，隐数据与观测图像y则共同构成了完全数据:

(2.3-25)

(2)通过当前的完全数据估计参数θ，

(2.3-26)

EM算法在步骤(1)和步骤(2)之间不停地迭代计算，这个过程中参数估计和图像分割交替进行，直至算法收敛。EM算法是通过搜索使得E[lnP(z|θ)]达到最大来寻找参数θ的极大似然估计。首先，P(z|θ)是在给定参数θ的条件下完全数据z的似然度。其合理性在于算法要寻找一个θ的取值使得某个函数值最大化；其次，使对数lnP(z|θ)最大化也同时使P(z|θ)取得最大值；第三，引入期望值E[lnP(z|θ)]的原因在于完全数据z本身也是一个随机变量的集合。已知完全数据是由观测数据y和未观测数据x共同构成，则须在未观测数据的可能取值上平均并以相应的概率为权值。换言之，要在随机变量z服从的概率分布上去期望E[lnP(z|θ)]。这个分布由观测数据y和未观测数据x的分布来确定。

然而，完全数据z的分布通常是未知的，因为它是由待估计的参数θ来确定的。EM算法可采用当前估计的参数θ′代替实际参数θ，以估计z的分布。现定义一个函数Q(θ′|θ)，它在θ=θ′和完全数据z的观测数据部分y已知的条件下将E[lnP(z|θ)]作为θ′的一个函数给出：

Q(θ|θ′)=E[lnP(z|θ)|θ′,y]

(2.3-27)(https://www.xing528.com)

将Q函数写成Q(θ′|θ)的意义是为了表达在当前假设θ′等于θ的条件下的目标函数。在EM算法的一般步骤中，重复以下两个步骤直至算法收敛。

(1)E-步骤：使用当前假设θ′和观测数据y来估计完全数据z的概率分布来计算Q(θ′|θ)：

Q(θ′|θ)←E[lnP(z|θ)|θ′,y]

(2.3-28)

(2)M-步骤：将假设θ′替换为使Q最大化的那个假设

(2.3-29)

当x取离散值时，条件期望可表示为：

(2.3-30)

由于计算P(x|y,θ′)比较复杂，仍然是EM算法参数估计的最大困难，因为在随机场参数估计中Gibbs随机场的拆分函数计算仍然是一个难以回避的问题。利用伪似然方法或者均场近似可以估计Gibbs分布的拆分函数。因此，在应用期望最大算法估计马尔可夫随机场的参数时，通常需要将其他的方法结合起来。

当Q函数连续时，EM算法收敛到似然函数P(z|θ)的一个不动点。若此似然函数有单个的极大值时，EM算法可以收敛到一个参数值θ′为全局的极大似然估计。否则，它只保证收敛到一个局部极大值点。因此，EM算法与其他诸如梯度下降法、先搜索和共轭梯度等算法有同样的局限性。