【机器学习基础】算法工程师必备的机器学习--EM-技术圈

『运筹OR帷幄』原创

作者：华校专

作者信息：

华校专，曾任阿里巴巴资深算法工程师、智易科技首席算法研究员，现任腾讯高级研究员，《Python 大战机器学习》的作者。

编者按：

算法工程师必备系列更新啦！继上次推出了算法工程师必备的贝叶斯分类器后，小编继续整理了必要的机器学习知识，全部以干货的内容呈现，哪里不会学哪里，老板再也不用担心你的基础问题！本章介绍EM算法。

如果概率模型的变量都是观测变量，则给定数据之后，可以直接用极大似然估计法或者贝叶斯估计法来估计模型参数。但是当模型含有隐变量时，就不能简单的使用这些估计方法。此时需要使用EM 算法。

EM 算法是一种迭代算法。
EM 算法专门用于含有隐变量的概率模型参数的极大似然估计，或者极大后验概率估计。

EM算法的每次迭代由两步组成：

E步求期望。
M步求极大。所以EM算法也称为期望极大算法。

1 示例

1.1 身高抽样问题

假设学校所有学生中，男生身高服从正态分布，女生身高服从正态分布。现在随机抽取200名学生，得到这些学生的身高，求参数的估计。
定义隐变量为，其取值为，分别表示男生、女生 。
(1) 如果隐变量是已知的，即已知每个学生是男生还是女生，则问题很好解决：
(1.1) 统计所有男生的身高的均值和方差，得到：
其中表示满足的构成的集合。分别表示平均值和方差。

(1.2) 统计所有女生的身高的均值和方差，得到：
其中表示满足的构成的集合。分别表示平均值和方差。

(2) 如果已知参数，则任意给出一个学生的身高，可以知道该学生分别为男生/女生的概率。

则有：

因此也就知道该学生更可能为男生，还是更可能为女生。

因此：参数 学生是男生/女生，这两个问题是相互依赖，相互纠缠的。
为解决该问题，通常采取下面步骤：
(1) 先假定参数的初始值：

(2) 迭代：
(2.1) 根据来计算每个学生更可能是属于男生，还是属于女生。这一步为E 步（Expectation），用于计算隐变量的后验分布。
(2.2) 根据上一步的划分，统计所有男生的身高的均值和方差，得到；统计所有女生的身高的均值和方差，得到。这一步为 M 步（Maximization ），用于通过最大似然函数求解正态分布的参数。
(2.3) 当前后两次迭代的参数变化不大时，迭代终止。

1.2 三硬币模型

已知三枚硬币 A，B，C ，这些硬币正面出现的概率分别为。进行如下试验：

先投掷硬币 A，若是正面则选硬币 B；若是反面则选硬币 C 。
然后投掷被选出来的硬币，投掷的结果如果是正面则记作 1；投掷的结果如果是反面则记作0 。
独立重复地次试验，观测结果为：1,1,0,1,0,...0,1。现在只能观测到投掷硬币的结果，无法观测投掷硬币的过程，求估计三硬币正面出现的概率。

设：
注意：随机变量的数据可以观测，随机变量的数据不可观测

随机变量是观测变量，表示一次试验观察到的结果，取值为 1 或者0
随机变量是隐变量，表示未观测到的投掷A硬币的结果，取值为 1 或者 0
是模型参数则：

将观测数据表示为，未观测数据表示为。由于每次试验之间都是独立的，则有：
考虑求模型参数的极大似然估计，即：
这个问题没有解析解，只有通过迭代的方法求解，EM算法就是可以用于求解该问题的一种迭代算法。
EM算法求解：首先选取参数的初值，记作，然后通过下面的步骤迭代计算参数的估计值，直到收敛为止：设第次迭代参数的估计值为：，则EM算法的第次迭代如下：

第一个式子：通过后验概率估计值的均值作为先验概率的估计。
第二个式子：通过条件概率的估计来求解先验概率的估计。
第三个式子：通过条件概率的估计来求解先验概率的估计。
E步：计算模型在参数下，观测数据来自于投掷硬币 B 的概率：
它其实就是，即：已知观测变量的条件下，观测数据来自于投掷硬币 B 的概率。
M 步：计算模型参数的新估计值：

EM 算法的解释：

初始化：随机选择三枚硬币 A，B，C 正面出现的概率的初始值。
E 步：在已知概率的情况下，求出每个观测数据是来自于投掷硬币 B 的概率。即：。于是对于次实验，就知道哪些观测数据是由硬币 B 产生，哪些是由硬币 C 产生。
M 步：在已知哪些观测数据是由硬币 B 产生，哪些是由硬币 C 产生的情况下：
(1) 就等于硬币 B 产生的次数的频率。
(2) 就等于硬币B 产生的数据中，正面向上的频率。
(3) 就等于硬币 C 产生的数据中，正面向上的频率。

2 EM算法原理

2.1 观测变量和隐变量

令表示观测随机变量，表示对应的数据序列；令表示隐随机变量，表示对应的数据序列。和连在一起称作完全数据，观测数据又称作不完全数据。
假设给定观测随机变量，其概率分布为，其中是需要估计的模型参数，则不完全数据的似然函数是，对数似然函数为。假定和的联合概率分布是，完全数据的对数似然函数是，则根据每次观测之间相互独立，有：
由于发生，根据最大似然估计，则需要求解对数似然函数：
的极大值。其中表示对所有可能的Z 求和，因为边缘分布。该问题的困难在于：该目标函数包含了未观测数据的的分布的积分和对数。

2.2 算法

2.2.1 原理

EM 算法通过迭代逐步近似极大化。假设在第次迭代后，的估计值为：。则希望新的估计值能够使得增加，即：。为此考虑两者的差：

这里已知，所以可以直接计算得出。
Jensen 不等式：如果是凸函数，x 为随机变量，则有：。

如果是严格凸函数，当且仅当是常量时，等号成立。
当满足时，将视作概率分布。设随机变量满足概率分布，则有：。

考虑到条件概率的性质，则有。因此有：
等号成立时，需要满足条件：
其中为随机变量的取值个数。
令
则有：，因此是的一个下界。

任何可以使得增大的，也可以使增大。为了使得尽可能增大，则选择使得取极大值的：。
根据定义有：。因为此时有：

求极大值：

其中：
与无关，因此省略。

2.2.2 算法

EM 算法：
联合分布和条件分布的形式已知（比如说高斯分布等），但是参数未知（比如均值、方差）

输出：模型参数
算法步骤：
(1) 选择参数的初值，开始迭代。
(2) E步：记为第次迭代参数的估计值，在第步迭代的 E 步，计算：
其中
表示：对于观测点，关于后验概率的期望。

(3) M步：求使得最大化的，确定次迭代的参数的估计值 $\theta^{(i+1)}
(4) 重复上面两步，直到收敛。
输入：
(1) 观测变量数据
(2) 联合分布，以及条件分布

通常收敛的条件是：给定较小的正数，满足：或者。
是算法的核心，称作函数。其中：

第一个符号表示要极大化的参数（未知量）。
第二个符号表示参数的当前估计值（已知量）。

EM算法的直观理解：EM算法的目标是最大化对数似然函数。

直接求解这个目标是有问题的。因为要求解该目标，首先要得到未观测数据的分布。如：身高抽样问题中，已知身高，需要知道该身高对应的是男生还是女生。但是未观测数据的分布就是待求目标参数的解的函数。这是一个“鸡生蛋-蛋生鸡” 的问题。
EM算法试图多次猜测这个未观测数据的分布。每一轮迭代都猜测一个参数值，该参数值都对应着一个未观测数据的分布。如：已知身高分布的条件下，男生/女生的分布。
然后通过最大化某个变量来求解参数值。这个变量就是变量，它是真实的似然函数的下界。
(1) 如果猜测正确，则就是真实的似然函数。(2) 如果猜测不正确，则就是真实似然函数的一个下界。

隐变量估计问题也可以通过梯度下降法等算法求解，但由于求和的项数随着隐变量的数目以指数级上升，因此代价太大。

EM算法可以视作一个非梯度优化算法。
无论是梯度下降法，还是EM 算法，都容易陷入局部极小值。

2.2.3 收敛性定理

定理一：设为观测数据的似然函数，为EM算法得到的参数估计序列，为对应的似然函数序列，其中。则：是单调递增的，即：
定理二：设为观测数据的对数似然函数，为EM算法得到的参数估计序列，为对应的对数似然函数序列，其中。
关于“满足一定条件”：大多数条件下其实都是满足的。

如果有上界，则会收敛到某一个值。
在函数与满足一定条件下，由 EM 算法得到的参数估计序列的收敛值是的稳定点。

定理二只能保证参数估计序列收敛到对数似然函数序列的稳定点，不能保证收敛到极大值点。
EM算法的收敛性包含两重意义：

关于对数似然函数序列的收敛。
关于参数估计序列的收敛。前者并不蕴含后者。

实际应用中，EM 算法的参数的初值选择非常重要。

参数的初始值可以任意选择，但是 EM 算法对初值是敏感的，选择不同的初始值可能得到不同的参数估计值。
常用的办法是从几个不同的初值中进行迭代，然后对得到的各个估计值加以比较，从中选择最好的（对数似然函数最大的那个）。

EM 算法可以保证收敛到一个稳定点，不能保证得到全局最优点。其优点在于：简单性、普适性。

3 EM算法与高斯混合模型

3.1 高斯混合模型

高斯混合模型(Gaussian$ mixture model,GMM)：指的是具有下列形式的概率分布模型：
其中是系数，满足：

。
是高斯分布密度函数，称作第个分模型，

如果用其他的概率分布密度函数代替上式中的高斯分布密度函数，则称为一般混合模型。

3.2 参数估计

假设观察数据
由高斯混合模型
生成，其中
可以通过EM算法估计高斯混合模型的参数。
可以设想观察数据是这样产生的：

首先以概率选择第个分模型。
然后以第个分模型的概率分布生成观察数据。这样，观察数据是已知的，观测数据来自哪个分模型是未知的。对观察变量，定义隐变量，其中。

完全数据的对数似然函数为：
其对数为：
后验概率为：
即：
则函数为：

求极大值：
根据偏导数为 0，以及
得到：

(1) ：
其中：
其物理意义为：所有的观测数据中，产生自第个分模型的观测数据的数量。
(2) ：
其中：
其物理意义为：所有的观测数据中，产生自第个分模型的观测数据的总和。
(3) ：
其中：
其物理意义为：所有的观测数据中，产生自第个分模型的观测数据，偏离第个模型的均值（）的平方和。
高斯混合模型参数估计的EM算法：

输入：
(1) 观察数据
(2) 高斯混合模型的分量数 K
输出：高斯混合模型参数
算法步骤：
(1) 随机初始化参数。
(2) 根据迭代求解，停止条件为：对数似然函数值或者参数估计值收敛。
其中：
(2.1)
其物理意义为：所有的观测数据中，产生自第个分模型的观测数据的数量。

(2.2)
其物理意义为：所有的观测数据中，产生自第个分模型的观测数据的总和。
(2.3)
其物理意义为：所有的观测数据中，产生自第个分模型的观测数据，偏离第个模型的均值（）的平方和。

4 EM 算法与模型

kmeans算法：给定样本集
针对聚类所得簇划分
最小化平方误差：

其中是簇的均值向量。
定义观测随机变量为，观测数据为。定义隐变量为，它表示所属的簇的编号。设参数，则考虑如下的生成模型：
其中表示距离最近的中心点所在的簇编号。即：

若最近的簇就是代表的簇，则生成概率为。
若最近的簇不是代表的簇，则生成概率等于 0 。

计算后验概率：
即：

若最近的簇就是代表的簇，则后验概率为 1 。
若最近的簇不是代表的簇，则后验概率为 0 。

计算函数：
设距离最近的聚类中心为，即它属于簇，则有：
则有：
定义集合
，它表示属于簇的样本的下标集合。则有：

则有：
这刚好就是 k-means 算法的目标：最小化平方误差。
由于求和的每一项都是非负的，则当每一个内层求和
都最小时，总和最小。即：
得到：
其中表示集合的大小。这就是求平均值来更新簇中心。 $$

5.1 函数

F函数：假设隐变量的概率分布为，定义分布与参数的函数为：
其中是分布的熵。通常假定是的连续函数，因此为和的连续函数。
函数有下列重要性质：

对固定的，存在唯一的分布使得极大化。此时，并且随着连续变化。
若，则。

定理一：设为观测数据的对数似然函数，为 EM 算法得到的参数估计序列，函数
则：

如果在和有局部极大值，那么也在有局部极大值。
如果在和有全局极大值，那么也在有全局极大值。

定理二：EM算法的一次迭代可由 F 函数的极大-极大算法实现：设为第次迭代参数的估计，为第次迭代函数的估计。在第次迭代的两步为：

对固定的，求使得极大化。
对固定的，求使得极大化。

5.2 算法1

GEM算法1（EM算法的推广形式）：

输入：
(1) 观测数据

(2) 函数
输出：模型参数
算法步骤：
(1) 初始化参数，开始迭代。
(2) 第次迭代：
(2.1) 记为参数的估计值，为函数的估计值。求使得极大化。
(2.2) 求使得极大化。
(2.3) 重复上面两步直到收敛。

该算法的问题是，有时候求极大化很困难。

5.3 算法2

GEM算法2（EM算法的推广形式）：

输入：
(1) 观测数据

(2) 函数
输出：模型参数
算法步骤：
(1) 初始化参数，开始迭代。
(2) 第次迭代：
(2.1) 记为参数的估计值，计算
(2.2) 求使得
(2.3) 重复上面两步，直到收敛。

此算法不需要求的极大值，只需要求解使它增加的即可。

5.4 算法3

GEM算法3（EM算法的推广形式）：

输入：
(1) 观测数据

(2) 函数
输出：模型参数
算法步骤：
(1) 初始化参数
开始迭代

(2) 第次迭代：
(2.1) 记
为参数
的估计值，计算

(2.2) 进行次条件极大化：
(2.2.1) 首先在保持不变的条件下求使得达到极大的
(2.2.2) 然后在
的条件下求使得达到极大的

(2.2.3) 如此继续，经过次条件极大化，得到
使得

(2.3) 重复上面两步，直到收敛。

该算法将 EM 算法的 M 步分解为次条件极大化，每次只需要改变参数向量的一个分量，其余分量不改变。

文章须知

文章作者：华校专

责任编辑：征帆周岩 logic

审核编辑：阿春

微信编辑：征帆

本文由『运筹OR帷幄』原创发布

如需转载请在公众号后台获取转载须知

往期精彩回顾




适合初学者入门人工智能的路线及资料下载
机器学习及深度学习笔记等资料打印
机器学习在线手册
深度学习笔记专辑
《统计学习方法》的代码复现专辑
AI基础下载
机器学习的数学基础专辑

获取本站知识星球优惠券，复制链接直接打开：

https://t.zsxq.com/y7uvZF6

本站qq群704220115。

加入微信群请扫码：

【机器学习基础】算法工程师必备的机器学习--EM