机器学习（二）——EM算法详解

EM算法作为机器学习领域的一个重要算法。在理解上还是具有一定的难度的，尤其是书籍上复杂的公式，会让人望而止步。本人在书籍和视频的基础上，根据自身的理解和认知试着解释一下EM算法，一者让大家指正，二者作为学习记录。

算法概述

EM算法是一种迭代算法，用于含有隐变量的概率模型参数的极大似然估计，或极大后验概率。举个例子：我们在已知样本数据的情况下，且已知数据是由n个高斯分布叠加而成的（先验知识），想知道具体的每一个高斯分布的参数和选取的概率（选取的概率）。EM算法就是为了解决这类问题而产生的。
EM算法主要分为两步：
*1.E步：求期望
2.M步：求极大似然估计*

算法原理

一.预备知识
1.Jensen不等式，在f(x)是凸函数的情况下：

扩展上述不等式，得到如下式:

而，可以认为是随机变量，所以上述的不等式可以化为：
。
2.最大似然估计（MLE）
找出与样本的分布最接近的概率分布模型。
例如：给定一组样本X1，…Xn,已知其来自于高斯分布N（μ，Σ）。来估计参数μ、Σ。
高斯分布的概率密度为函数为：

计算所有样本的联合概率密度——似然函数

之后对似然函数取对数，求极值即可得到目标参数的值。
利用最大似然估计计算概率分布模型的参数的实质是找到一组最优的模型参数，使得样本中所有数据发生的联合概率最大。
二.基于高斯混合模型的EM算法
针对我们在概述中提到的如何将一个混合高斯模型分解为两个单独的高斯分布问题，作为一个典型的含有隐变量的模型。我们先看EM算法如何在该模型上使用，再抽象得到一般的EM算法。
问题假设:
假设我们数据由两个高斯分布混合而成。且服从:.且每次选取N1，N2的概率分别为：。在观测到变量X的一系列样本X1，X2，X3，…，Xn,试估计参数。
求解方法：
我们针对上述的问题，建立对数似然函数：

上式中对数函数较为复杂，我们采用两步的方法来求解其最大值
（1）估算数据来自于哪个组分（哪个高斯分布）
估计数据由每个组分生成的概率：

然而上式中μ和σ也是带估计的值，因而我们必须采用迭代法来计算r（i,k）.
需要先验的给定μ和σ，与初始的w。
设是隐变量Z的某一个分布。有
E—step：
对数似然函数可以写为：

则有：

其中最后一步采用了jensen不等式。
令等号成立，则就为了找到了下界。有

解上述的式子,根据定义：

得：

这样我们就得到了数据由每一个组分生成的概率。
（2）.估计每个组分的参数。
对于所有的样本点，对于组分而言，可以看成生成了r（i,k）xi个点。利用上述的结论。采用最大似然估计法可以得到;
M—step：采用似然函数的下界表达式：


对上述似然函数求偏导来解μ和σ。
对μ求偏导时，与和无关，同理可以可得：

很符合人的直观认知。即分组一的均值是，所有样本中属于分组一的部分的加权求和取均值。分组一的方差是属于分组一的部分的数据的加权方差。
这里我们已经将每一个样本的均值和方差得到了。下面就需要重新求解样本数据属于每一个分组的概率,结合所满足的条件。可得：

综合上述的式子，可以得到最终对每一个参数的计算结果。

反复利用上式进行迭代，最终收敛的参数，就是采用EM算法得到的最终参数。

EM算法原理

EM算法是有一个使用多次迭代来完成寻优的算法。其主要的算法原理是：采用jensen不等式，对每一次迭代是的似然函数进行下界估计。似然函数的每一个点对应的是一个下界函数。下界函数整体上不会超过似然函数。利用下界函数的极大值来近似的逼近似然函数的极大值，以期望尽可能的找到似然函数的极值。这种方法的思想和最大似然估计很相似，只不过最大似然估计不包含隐变量，可以直接构建似然函数求导得到参数，而EM算法因为有隐变量的存在使得，直接对似然函数求解并不可行。因而使用迭代的方法，在初始的参数的假设下，例利用下界函数的极值来逼近似然函数的极值。从而间接的寻找似然函数的极值。
如下图所示;

图中表示似然函数在这一点出的下界函数（蓝线表示）。而表示下界函数在出取得极值，我们利用这个值来近似的认为是似然函数的值。依次方法来求得似然函数的极值。