1.EM算法详解

EM算法：Expectation Maximization Algorithm

EM算法用于含有隐变量(hidden variable)的概率模型参数的极大似然估计，又称极大后验概率估计。

EM算法是一种迭代算法，每次迭代由两步组成：

    E步-求期望(Expectation)；

    M步-求极大(Maximization)；

所以这一算法称为期望-极大算法(Expectation Maximization Algorithm)，简称EM算法

关于EM算法的数学基础知识，请详见前面博客：【机器学习】【EM算法】数学基础:(半)正(负)定矩阵+(严格)凹(凸)函数+(最大)似然函数+Hessian矩阵+Jensen不等式

在一般情况下EM算法是收敛的，但是不能保证收敛到全局最优

EM算法与初值的选择有关，不同的初始值EM孙发最终可能得到不同的参数估计值

EM算法在非监督学习中的应用

    监督学习由训练数据{(x1,y1),(x2,y2),……,(xn,yn)}学习概率分布P(Y|X)或者决策函数Y=f(X)作为模型，用于分类、回归、标注等任务。 这时候训练数据中的每个样本点由输入和输出对组成。

   有时训练数据只有输入没有对应的输出{(x1, ),(x2, ),……,(xn, )}，从这样的数据学习模型称之为非监督学习问题。

    EM算法可以用于生成模型的非监督学习。生成模型由联合概率分布P(X, Y)表示，即我们可以认为非监督学习训练数据是联合概率分布产生的数据。X为观测数据，Y为未观测数据。

2.样本集实例详解

2.1求没有隐变量的概率模型参数的极大似然估计

EM算法可以求解含有隐变量的概率模型参数的极大似然估计，但是我们先看一个没有隐变量的样本集：

我们求A,B,C硬币的投出正面的概率：

则可以将0.4,0.5,0.6依次作为硬币A,B,C出现正面概率的最大似然估计

2.2求含有隐变量的概率模型参数的极大似然估计

上面的训练样本集，由于每个样本使用的硬币号未知，所以硬币号是样本中一个未知的变量，即每个样本都有一个隐变量。

根据2.1可知如果知道每轮使用的硬币号，很轻松可以求出每个硬币出现正面的概率。

但是2.2是硬币号为隐变量的样本集，你不知道每轮使用的硬币号，我们的任务还是估计每个硬币出现正面的概率，应该怎么求每个硬币出现正面的概率？？？

硬币号这个特征就是样本的一个隐含变量X，如果我们我们不知道X，就无法去估计PA,PB,PC。

而我们要估计PA,PB,PC,就必须先估计出X，但是要估计X，又必须先知道PA,PB,PC，好像我们进入了鸡生蛋和蛋生鸡的问题。

EM算法通过先随机初始化一组PA,PB,PC，用初始化的PA,PB,PC来估计X，然后用估计出的X，按照最大似然估计法则去估计新的PA,PB,PC，新的PA,PB,PC会更接近实际的PA,PB,PC数值。

Step1:然后用新估计出来的PA,PB,PC再估计X，

Step2:然后用估计出的X，按照最大似然估计法则去估计新的PA,PB,PC

如果PA,PB,PC仍和旧的PA,PB,PC相比不收敛就继续进行Step1-->Step2,直到PA,PB,PC收敛。

好，下面我们按照以上EM算法思路进行数学计算演示：

2.2.1随机初始化一组PA,PB,PC

2.2.2进行EM算法迭代计算直到PA,PB,PC收敛

已知每个硬币的出现正面概率初始值，可以求每轮使用不同硬币时正反面事件发生的概率

根据上面求出的每轮使用不同硬币时正反面事件发生的概率，计算每轮使用不同硬币的概率

现在我们有了每轮使用每个硬币的概率，则就相当于求出了隐变量X，则可以用估计出的隐变量X来重新估计每个硬币的正面概率即重新估计PA,PB,PC：

下面是第一次迭代计算后的概率模型参数值PA,PB,PC：

可知通过EM算法第一次迭代得到的新估计值相比初始化值更接近真实值。

因为新估计值和初始化值仍有变化，所以继续按照上面步骤继续迭代计算PA,PB,PC:

用新估计值作为初始值：

    PA=0.44076    PB=0.50024    PC=0.53888

    用新的PA,PB,PC估计X

    然后基于X重新估计PA,PB,PC，继续用新估计的PA,PB,PC作为初始值开新一轮的EM迭代计算，直到PA,PB,PC收敛。

2.2.3解释说明

    E步：用已有的PA,PB,PC，估计出了X的概率分布，这个步骤称为E步

    M步：用E步中估计出的X，按照最大似然概率法则来估计PA,PB,PC，这个步骤称为M步

    当M步估计出的PA,PB,PC收敛时EM算法才会结束（PA,PB,PC收敛差值小于自己给定的阈值时，可以判定EM算法停止）

    不可置疑的事实1：M步新估计出的PA,PB,PC一定会更接近真实的PA,PB,PC，即每次迭代得到的参数估值更接近真实数值

    不可置疑的事实2：EM算法迭代不一定收敛到真实的PA,PB,PC，即最终不一定收敛到全局最优

    不可置疑的事实3：PA,PB,PC的随机初始值影响最后收敛得到的PA,PB,PC和真实的PA,PB,PC的差距，如果初始值取的好最后收敛得到的PA,PB,PC就是完全等于真实的PA,PB,PC，如果取得初始值不够好的话，可能最后EM收敛得到的PA,PB,PC不等于真实的PA,PB,PC，但一定会更接近真实的PA,PB,PC。不一定收敛到真实的概率模型参数这是由最大似然“估计”的真实体现，要就不称之为“估计”了~。

3.参考文献

[1]李航.统计学习方法[J].2012.

[2]What is the expectation maximizationalgorithm.pdf

        链接(无密码)：https://pan.baidu.com/s/1rgC9QtAUrebuUcNgbmn-qg

(end)