EM算法

对于一般概率模型的学习策略，我们往往会采取极大似然估计或者贝叶斯估计的方法对模型的参数进行估计，但是需要注意的是这种估计方法都是建立在待估参数全部为已经知道结果的参数的基础之上的(complete-data problem)。当模型中有隐变量/潜在变量（数据不可观测的变量）时，似然函数的最大化变得困难。这是就可以使用EM算法,EM算法是在不完全数据下求解MLE估计结果的一种近似求解方法，用迭代去逼近原来不完整数据问题的结果。EM算法主要分为两步：

  • E:求期望(expectation)
  • M:求极大(maximization)

EM算法的核心思想是在既定样本数据下在因变量最有可能的分布状态下利用极大似然估计模型的参数。

算法导出

针对一个含有隐变量的概率模型，这里假设隐变量为Z，观测数据Y关于参数θ\theta的对数似然函数为L(θ)L(\theta):

\begin{equation} \begin{aligned} L(\theta) & = \log P(Y|\theta)=log\sum_{Z}P(Y,Z|\theta)\\ &=\log\large( \sum_{Z}P(Y,Z|\theta)P(Z|\theta)\large) \end{aligned} \end{equation}

迭代主要是确定待估参数θ\theta的最可能取值，记第i次迭代后的估计值为θ(i)\theta^{(i)}:

\begin{equation*} \begin{aligned} L(\theta)-L\left(\theta^{(i)}\right) &=\log \left(\sum_{Z} P(Y \mid Z, \theta) P(Z \mid \theta)\right)-\log P\left(Y \mid \theta^{(i)}\right)\\&=\log \left(\sum_{Z} P\left(Z \mid Y, \theta^{(i)}\right) \frac{P(Y \mid Z, \theta) P(Z \mid \theta)}{P\left(Z \mid Y, \theta^{(i)}\right)}\right)-\log P\left(Y \mid \theta^{(i)}\right) \\ & \geqslant \sum_{Z} P\left(Z \mid Y, \theta^{(i)}\right) \log \frac{P(Y \mid Z, \theta) P(Z \mid \theta)}{P\left(Z \mid Y, \theta^{(i)}\right)}-\log P\left(Y \mid \theta^{(i)}\right) \\ &=\sum_{Z} P\left(Z \mid Y, \theta^{(i)}\right) \log \frac{P(Y \mid Z, \theta) P(Z \mid \theta)}{P\left(Z \mid Y, \theta^{(i)}\right) P\left(Y \mid \theta^{(i)}\right)} \end{aligned} \end{equation*}

欲求使得似然函数增加的参数估计值，需要将上述放缩后的函数最大化，抛去无关常数，则问题转化为：

\begin{equation*} \begin{aligned} \theta^{(i+1)} &=\arg \max _{\theta}\left(L\left(\theta^{(i)}\right)+\sum_{Z} P\left(Z \mid Y, \theta^{(i)}\right) \log \frac{P(Y \mid Z, \theta) P(Z \mid \theta)}{P\left(Z \mid Y, \theta^{(i)}\right) P\left(Y \mid \theta^{(i)}\right)}\right) \\ &=\arg \max _{\theta}\left(\sum_{Z} P\left(Z \mid Y, \theta^{(i)}\right) \log (P(Y \mid Z, \theta) P(Z \mid \theta))\right) \\ &=\arg \max _{\theta}\left(\sum_{Z} P\left(Z \mid Y, \theta^{(i)}\right) \log P(Y, Z \mid \theta)\right) \\ &=\arg \max _{\theta} Q\left(\theta, \theta^{(i)}\right) \end{aligned} \end{equation*}

EM算法就是通过不断求解下界的极大化逼近求解对数似然函数极大化的算法，这里的Q其实就是求logP(Y,Z∣θ)logP(Y,Z|\theta)的期望值（注意这里的YY是观测值，换言之相当于是在Y和模型参数给定的条件下最大化期望值）
image.png

B(θ,θ(i))B(\theta,\theta^{(i)})即我们求得的真实下界
image.png
image.png

算法收敛性

可以证明随着迭代次数的增加，似然函数的值会不断增大，这也意味着如果似然函数有界，那么一定存在局部最优解或者全局最优解。本身是局部最优的算法，

坐标上升法（Coordinate ascent）

坐标上升法是一种与梯度下降法类似的方法，与梯度下降法不同之处在于梯度下降法目的是最小化代价函数，坐标上升法的目的是最大化似然函数；

梯度下降法每一步只更新模型参数，而Em算法的每一步既更新模型参数又更新隐含参数：

image-20220710214242845

需要注意的是EM算法每一步只会优化一种参数，因此我们看到的优化路径是一种阶梯类型的（E步固定模型参数优化隐变量，M步固定因变量优化模型参数）

应用

本质上来说算法的应用首先是一种局部固定单点突破的思想。

如果我们从算法思想的角度来思考EM算法，我们可以发现我们的算法里已知的是观察数据，未知的是隐含数据和模型参数，在E步，我们所做的事情是固定模型参数的值，优化隐含数据的分布，而在M步，我们所做的事情是固定隐含数据分布，优化模型参数的值。

高斯混合模型

image.png

支持向量机的SMO算法

K-means

马尔科夫模型