EM算法

EM算法

隐变量：属性值未知的变量；未观测的变量。

令$\boldsymbol X$表示已观测变量集，$\boldsymbol Z$表示隐变量集，$\Theta$表示模型参数。

若对$\Theta$做极大似然估计，则应最大化对数似然

$$LL(\Theta|\boldsymbol X, \boldsymbol Z) = lnP(\boldsymbol X, \boldsymbol Z|\Theta)$$

由于$\boldsymbol Z$是隐变量，上式无法直接求解。可以对$\boldsymbol Z$计算期望，来最大化已观测数据的对数“边际似然”

$$LL(\Theta|\boldsymbol X)=lnP(\boldsymbol X|\Theta) = ln \sum _{\boldsymbol Z}P(\boldsymbol X,\boldsymbol Z|\Theta)$$

EM(Expectation-Maximization)算法(期望最大化算法):
是一种迭代式的方法

EM使用两个步骤交替计算，直至收敛到最优解。

算法原型：

• E步(Expectation)：基于$\Theta^t$推断隐变量$\boldsymbol Z$的值，记为$\boldsymbol Z^t$;
• M步(Maximization)：基于已观测变量$\boldsymbol X$和$\boldsymbol{Z^t}$对参数$\Theta$做极大似然估计，记为$\Theta^{t+1}$

若不是，取$\boldsymbol{Z}$的期望，而是基于$\Theta^t$计算隐变量$\boldsymbol Z$的概率分布$P(\boldsymbol Z|\boldsymbol X, \Theta^t)$,则EM算法的两个步骤是：

• E步(Expectation)：以当前参数$\Theta^t$推断隐变量分布$P(\boldsymbol Z|\boldsymbol{X},\Theta)$，并计算对数似然$LL(\Theta|\boldsymbol{X},\boldsymbol{Z})$关于$\boldsymbol{Z}$的期望

$$Q(\Theta|\Theta^t)=E_{\boldsymbol{Z}|\boldsymbol{X},\Theta^t}LL(\Theta|\boldsymbol{X},\boldsymbol{Z})$$

• M步(Maximization):寻找参数最大化期望似然，即

$$\Theta^{t+1}=\underset{\Theta}{argmax}Q(\Theta|\Theta^t)$$

EM算法可看作用坐标下降法来最大化对数似然下界的过程，是一种非梯度的优化方法。

总结

根据对属性间依赖的涉及程度，贝叶斯分类器形成了一个“谱”：朴素贝叶斯分类器不考虑属性见的依赖性，贝叶斯网能表示任意属性间的依赖性，二者分别位于“谱”的两端；介于两者之间的则是一系列半朴素贝叶斯分类器，它们基于各种假设和约束来对属性间的部分依赖性进行建模。

EM算法是最常见的隐变量估计方法，在机器学习中有极为广泛的用途，例如常被用来学习高斯混合模型(GMM)的参数。K均值聚类算法就是一个典型的EM算法。