【机器学习】EM算法

本文介绍了一种经典的迭代求解算法—EM算法。首先介绍了EM算法的概率理论基础，凸函数加jensen不等式导出算法的收敛性，算法核心简单概况为固定其中一个参数，优化另一个参数逼近上界，不断迭代至收敛的过程。然后介绍高斯混合，朴素贝叶斯混合算法基于EM算法框架的求解流程。最后介绍了基于概率隐因子的LDA主题模型，这一类基于隐因子模型-包括因子分解，概率矩阵分解皆可通过EM算法求解，且与EM思想相通。

作者 | 文杰

编辑 | yuquanle

EM算法

EM算法是一种迭代算法，用于带隐变量的概率模型参数的极大似然估计，是无监督学习中一大类算法求解的算法。

EM算法每次迭代由两步组成，E步：假设隐变量和特征变量的联合分布，求解样本关于隐变量的概率函数（使Jensen不等式等号成立）；M步：在已知样本的联合分布（确定样本特征和类标），采用极大似然估计最大化似然函数求解参数。

在讨论EM算法之前，先介绍Jensen inequality（由凸函数性质导出）。

假设f是定义在实数上的凸函数，由凸函数的定义有：

严格凸函数则严格大于，凸函数的判定是其二阶可微的话，其Hesse矩阵半正定。对凸函数的性质推广有：

当表示的概率时，那么有：

当且仅当：，即为常数函数，等号成立。

反之，对于凹函数不等式方向相反。

现在来看EM算法，给定训练样本，引入隐含的类别标签，在有监督方法中，最大对数似然函数，同样这里最大化对数似然函数的在隐变量的全期望：

其中为样本的隐变量的概率分布，。不同选择，会得到EM在不同情况下的模型，比如高斯混合，朴素贝叶斯混，LDA等。

因为函数是一个严格凹函数，由Jessen不等式有：

其中，因此当且仅当，，等号成立。

因为，所以可以看做是样本关于隐变量的概率分布，等于联合概率归一化，即比上联合概率对的全期望：

因此，EM算法的第一步就是计算在给定下隐变量的条件概率。

当已知之后，且Jessen不等式等号成立，回过头来再最大化似然函数：

因此，EM算法的极大似然估计可以看作是坐标上升过程，第一步在给定的参数下最大化似然函数，第二步则是在当前的下最大化似然函数。

收敛性：

下面的第一个不等号由最大似然估计得到，第二个不等号Jessen不等式得到，但是求解过程是先由Jessen不等式确定似然函数的下界，后最大似然函数下界。

EM算法的一般流程：

E-step：（固定参数下，求隐变量条件分布）

M-step：（最大化似然函数下界）

EM求解的过程大致如图所示，是否能收敛到全局最优，取决于目标函数是否为凸函数：

从上图可以看出，EM算法的思想也是坐标上升的思想，即固定一组变量求解另一组变量，不断地迭代。

比较特殊的是，EM算法针对于带隐变量的概率模型参数的极大似然估计，求解过程又称“期望最大化”，第一步求期望，第二步最大化，这是带隐变量的概率模型特有的，不是EM算法的特点。

EM算法例子-高斯混合，朴素贝叶斯混合

高斯混合模型

为什么要采用EM算法求解高斯混合模型呢？回顾高斯混合模型的目标函数，我们发现函数在求和外面。特别是当类标签已知，像高斯判别模型那么进行参数估计，但在混合高斯模型中，而隐变量却是未知，所以我们很难直接优化。采用EM算法的Jessen不等式，我们将函数放到里面，并使等号成立，对目标函数进行转化：

其中条件概率分布。

下面从EM思想来看高斯混合模型，给出高斯混合模型最大似然估计计算出参数的推导过程：

E-step:（固定参数下，求隐变量条件分布）

其中服从高斯分布，服从伯努利分布。

M-step:（最大化似然函数下界）

对求导：

令导数为0，有：

对目标函数求解参数，去掉无关项，有：

由，对其拉格朗日函数求导：

令其导数为0，有：

所以，，又，所以得

所以：

朴素贝叶斯混合

在文本聚类问题中，当采用One-hot编码时，则一篇文档的类别可以看作是隐变量服从伯努利分布，文档中词在类别下的条件概率也可看作是一个伯努利分布（如果文档采用词在字典中的位置表示，则对应一个N元伯努利分布）。所以有：

其中由于概率和为1，所有的变量我们只需要求解一般，即。

由于朴素贝叶斯中词（特征）的独立性假设有：

其中为特征下标。

同样，最大化对数似然函数：

套入EM框架：

E-step:（固定参数下，求隐变量条件分布）

由于该聚类是二聚类，表示是属于其中一类的概率，样本属于另一类的概率则为。

M-step:（最大化似然函数下界）

其中:

似然函数对求导：

令偏导为0，得：

对求偏导：

令偏导为0，得：

同理，求导令其偏导为0有：

可以看出，朴素贝叶斯混合和高斯混合惊人的相似。M-step的参数估计与有监督最大似然参数估计的结果一致。

LDA主题模型

在了解主题模型之前，我们顺着朴素贝叶斯混合模型在多元伯努利分布上的推广导出隐语义分析（pLSA）模型。在PLSA模型中，我们假设隐变量的语义是主题，而一篇文档涉及多个主题，不同的主题下产生词的概率不同。那么一篇文档的生成的概率可以写作：

其中表示第篇文档被选中的概率，表示第篇文档生成第个主题的概率，表示第个主题下产生词的概率。其中后两个概率服从多项分布。采用EM算法，我们同样可以在E-step假设参数，来确定主题的条件概率；在M-step最大化似然函数的下界更新参数。

LDA同pLSA极为相似，不同的是pLSA是频率学派的角度来看待文档-主题-词的关系，而LDA是贝叶斯学派角度来看待文档-主题-词关系。频率学派认为数据服从参数一定的概率分布，贝叶斯学派则从数据中估计参数的概率，认为参数本身服从一个先验概率，由贝叶斯公式，最大化后验概率：

也就是说LDA比pLSA多了两个先验分布：

其中表示文档，表示主题，表示词。

LDA模型从贝叶斯角度引入先验概率的目的是构造似然函数的一个共轭先验分布，用实践作为超参来调节似然函数模型。关于LDA的求解可以采用吉布斯采样和变分的EM算法，这里不细究，在专门介绍LDA时再详细学习。

The End