EM算法及其相关算法学习

作者: 奔向算法的喵 | 来源:发表于2018-09-23 20:43 被阅读0次

EM 算法
EM算法及其相关算法学习
EM算法
01 EM算法 - 大纲 - 最大似然估计(MLE)、贝叶斯算法
EM算法
04 EM算法 - EM算法收敛证明
EM算法
再学习EM算法
机器学习(十):EM算法与GMM算法原理及案例分析
2019-02-22-方法

EM算法是数据挖掘领域十大经典算法之，是一种基础的算法，用到非常用的有名的算法里面比如隐藏马尔科夫算法(HMM)、LDA主题模型、GAN/VAE等生成模型算法。后面的参考资料的EM算法认知的九重境界还是总结得非常到位的，这里主要是记录一些对EM算法的一个学习。大致各个博客都是综合了吴恩达的机器学习的EM算法篇章和李航博士的统计学习方法里面的介绍，这里稍微提一下，大家在看的时候，吴恩达的学习材料上面用的是概率派的方式进行的公式推导，然后李航博士的统计学习方法上面是基于频率派的方式进行的公式推导。其实本质都是一样的。

一、简单的一些概念

EM = expectation maximaization，它是一种迭代的算法，迭代的过程中主要就是两步：E步求期望，M步求期望的极大化。
1、模型参数的学习
在从样本数据出发的时候，找出样本的模型参数，一种常见的方式就是极大化模型概率分布的对数似然函数，这个时候的对数似然函数只是参数的函数的话，那么我们直接极大话处理，就能够得到最好的那个分布的模型参数。
但是要是我们观测数据中有未观测到的隐含数据的话，这个时候就存在未知隐含数据和参数，那么就无法直接用对数似然函数的极大似然估计来求模型的参数了。
解决思路：
既然我们的隐藏的数据是未知的，但是我们可以对隐藏的参数进行一个猜测，这样的话，就相当于固定住的隐藏数据，这一步就对应了我们EM算法的E步。正是因为现在我们的观测数据和猜测数据知道了，那么我们就能够采用对数似然函数的极大似然估计来进行模型参数的求解，第二步就对应了我们的M步。

二、进一步的学习和推导

1、EM算法推导

假设给定了m个样本x = {x^(i) | i=1,2, ... , m}，然后他们之间都是独立的，找到每个样本隐含的类别z，能够使得p(x, z)最大，那么p(x,z)的最大似然估计公式如下：
$L(\theta) = \sum_{i=1}^{m}logp(x^{(i)};\theta) = \sum_{i=1}^{m}log\sum_{z^{(i)}}p(x^{(i)},z^{(i)};\theta)$

这里的θ就是我们要学习的模型参数，z就是我们的隐藏变量，x就是我们的观测变量。
因为我们EM算法是一种迭代的Model，假设我们第i次循环得到的参数就是θ(i)，然后我们就需要去估计θ(i+1)，然后我们要去优化的目标函数就是:
$L(\theta) - L(\theta^{(i)}) = arg \max_\theta (logP(X;\theta) -logP(X;\theta^{(i)}))$
我们记T(θ)如下进行推导：
$\begin{eqnarray} T(\theta,\theta^{(i)}) &=&logP(X;\theta) -logP(X;\theta^{(i)}) \\ &=&log \sum_Z P(X,Z;\theta) -logP(X;\theta^{(i)}) \\ &=&log \sum_Z P(X|Z;\theta)P(Z;\theta) -logP(X;\theta^{(i)})\\ &=&log \sum_Z P(X|Z;\theta)P(Z;\theta) \cdot \frac{P(Z|X;\theta^{(i)})}{P(Z|X;\theta^{(i)})} -logP(X;\theta^{(i)}) \\ &=&log \sum_Z P(Z|X;\theta^{(i)}) \cdot \frac{P(X|Z;\theta) \cdot P(Z;\theta)}{P(Z|X;\theta^{(i)})} -logP(X;\theta^{(i)})\\ &\ge& \sum_Z P(Z|X;\theta^{(i)}) \cdot log \frac{P(X|Z;\theta) \cdot P(Z;\theta)}{P(Z|X;\theta^{(i)})}-logP(X;\theta^{(i)}) \end{eqnarray}$

这里不等号的来源就是利用到了Jassen不等式，也就是下面的公式，这个公式非常的重要。

$log\sum_j \lambda_{j}y_{j} \geq \sum_j \lambda_{j}logy_{j}, \lambda_{j} \geq 0, \sum_j \lambda_{j} =1$

由此我们就知道了：
$\sum_Z P(Z|X;\theta^{(i)}) =1$

然后我们就能够得到：
$L(\theta) \ge L(\theta^{(i)}) + \sum_Z P(Z|X;\theta^{(i)}) \cdot log \frac{P(X|Z;\theta) \cdot P(Z|\theta)}{P(Z|X;\theta^{(i)}) \cdot P(X;\theta^{9i)})}$

然后我们就能推出我们的θ(i+1)如下
$\begin{eqnarray} \theta^{(i+1)} &=& arg \max_\theta [L(\theta^{(i)})+ \sum_Z P(Z|X;\theta^{(i)}) \cdot log \frac{P(X|Z;\theta) \cdot P(Z|\theta)}{P(Z|X;\theta^{(i)}) \cdot P(X;\theta^{9i)})}] \end{eqnarray}$ 我们除去与θ不想关系的部分之后就知道：
$\begin{eqnarray} \theta^{(i+1)} &=& arg \max_\theta[\sum_Z P(Z|X;\theta^{(i)}) \cdot log P(X|Z;\theta) \cdot P(Z|\theta)] \\ &=& arg \max_\theta[\sum_Z P(Z|X;\theta^{(i)}) \cdot logP(X,Z;\theta)] \\ &=& arg \max_\theta[E_{Z|X;\theta^{(i)}} ( logP(X,Z;\theta))] \end{eqnarray}$

所以到这里，我们就知道E和M的操作了：
（E-step）：要求的就是在给定当前参数θ(i)和观测数据x的时候，我们去求未观测数据Z的条件概率分布的一个期望，我们就记做如下：
$Q(\theta,\theta^{(i)}) = E_{Z|X;\theta^{(i)}} ( logP(X,Z;\theta))$

（M-step）：要求的就是第i+1次要获得的模型参数，这一步就是去做极大化Q函数的操作：
$\theta^{(i+1)} = arg \max_\theta Q(\theta, \theta^{(i)})$

2、EM算法流程

输入：输入观测数据x和隐藏数据z，联合概率分布P(X, Z;θ)，条件概率分布P(Z|X;θ)，最大的迭代次数J。
输入：模型参数theta。
1、模型参数theta的初始化
2、迭代计算。
for i =1 to J开始进行迭代：
（1）E步：进行第i+1次迭代的时候，θ(i)已经确定，然后计算前面提到的期望
$Q(\theta,\theta^{(i)}) = E_{Z|X;\theta^{(i)}} ( logP(X,Z;\theta))$

（2）M步：有了E步的求期望之后，我们就能够对θ(i+1)进行估计，然后求E所得到的的期望的最大化：
$\theta^{(i+1)} = arg \max Q(\theta,\theta^{(i)})$
（3）如果θ(i+1)已经收敛，那么迭代就结束，这里注意我们收敛的条件，给以一个相对较小的整数，要是满足下面的条件，我们就认为收敛，结束迭代:
$||\theta^{(i+1)} - \theta^{(i)}|| < \varepsilon$

3、EM算法敛散性的证明

这里就是对EM算法敛散性的一个证明：

4、EM算法的两条重要的性质

（1）通过EM算法求解得到的解是局部最优解，不一定是全局的最优解。这个跟隐变量模型的目标函数不是凸函数息息相关。
（2）EM算法一定是严格增大。目标函数一定是严格递增的。所以EM算法一定是收敛的。

三、和EM算法相关的算法

和EM算法相联系的算法是非常多的，下面就以思维导图的形式给出它和其他一些算法的联系。

参考资料：
1、https://blog.csdn.net/fuqiuai/article/details/79484421
2、https://www.zhihu.com/question/40797593/answer/275171156
3、http://www.sohu.com/a/215759232_642762

EM 算法
参考: 从最大似然到EM算法浅解（EM算法）The EM Algorithm EM算法及其推广学习笔记 EM算法...
EM算法及其相关算法学习
EM算法是数据挖掘领域十大经典算法之，是一种基础的算法，用到非常用的有名的算法里面比如隐藏马尔科夫算法(HMM)、...
EM算法
问题 1. 什么是EM 2. EM算法流程是怎么样的 3. EM算法的优缺点 1. EM算法介绍 EM算法...
01 EM算法 - 大纲 - 最大似然估计(MLE)、贝叶斯算法
EM算法的讲解的内容包括以下几个方面： 1、最大似然估计2、K-means算法3、EM算法4、GMM算法 EM算法...
EM算法
EM算法作为数据挖掘领域十大经典算法之一，在统计学习领域也有诸多应用。EM算法（Expectation-maxim...
04 EM算法 - EM算法收敛证明
03 EM算法 - EM算法流程和直观案例八、EM算法收敛证明 EM算法的收敛性只要我们能够证明对数似然函数的值...
EM算法
EM算法 EM算法基本思想最大期望算法（Expectation-Maximization algorit...
再学习EM算法
EM 算法是十大经典的机器学习算法，【PS:MC是二十世纪十大算法】回顾下经典的EM算法，对其理解加深 1. 学...
机器学习(十):EM算法与GMM算法原理及案例分析
一、简介 EM算法最大期望算法(Expectation-maximization algorithm，简称EM，...
2019-02-22-方法
1.EM算法（1）从最大似然到EM算法浅解