EM算法详细推导_快速米算法

在深度学习的路上，从头开始了解一下各项技术。本人是DL小白，连续记录我自己看的一些东西，大家可以互相交流。

在看代码的过程中，发现EM算法的了解不是很透彻，又回头来手动推导了一遍EM算法，算是一个补充吧。如果不需要了解具体细节，可以看我之前这篇文章：

https://blog.csdn.net/weixin_38206214/article/details/81064625

一、前言

EM算法即期望最大化(Expection Maximization)算法。是一种迭代算法，作为一种数据添加算法，在现在的DL学习中经常见到。参考了很多网上的博客，很多都省略了部分推导细节，让推导看起来有点不明不白，自己重新整理了一下，手动推导了一边过程，大家可以作为细节补充看看。

二、似然函数和极大似然估计

假设总体的概率函数为 p(x ; θ)， 其中 θ 是一个未知参数或几个未知参数组成的参数向量，属于取值的参数空间。

x1, x2 ... xn是来自该总体的样本，将样本的联合概率函数表示为 θ 的函数。

设 L(θ) = L(x1, ..., xn; θ)，表示我们从总体样本(参数为 θ )中，连续抽取到x1,...xn样本的概率，即为单个样本的乘积，所以L(θ) 是一个连乘函数。称为样本的似然函数。

L(θ)是参数 θ 的函数，随着 θ 在参数变化，L函数也在变化。而极大似然估计目的就是在样本{x1,...,xn}固定的情况下，寻找最优的 θ 来极大化似然函数：

上式在数学领域，可以看作是对 θ* 求解，求L(θ) 函数的极值点，导数为0处，即为 θ* 的点。

又因为L(θ) 和 ln(θ) 在同一个 θ 处取得极值，我们可以对 L(θ) 取对数，将连乘转化为连加(方便求导)，得到对数化似然函数：

  

三、Jensen不等式

设 f 是定义域为实数的函数，如果对所有实数X，f的二阶导数恒大于等于0，那么f为凸函数。Jensen不等式表达如下：

如果 f 为凸函数，X为随机变量，那么：

其中E[ ] 为期望，也称为均值。上张图解释一下：

设a, b为X上的两个点，设 f 为凸函数，图像如上。那么a，b的期望(均值)的 f 映射，要小于 a 在 f 上的映射和 b 在 f 上的映射的均值。即：

[ f (a) + f (b) ] / 2 大于等于 f [ ( a + b ) / 2 ] 

原理其实学过导数和图像的关系就能理解，可能这个名字比较没见过，别害怕啦。

Jensen不等式的等号成立的条件是当X为常量，即：函数f 的值为一条直线。

PS.数学期望相关定理

若随机变量X的分布用分布列 p(xi)或用密度函数 p(x)表示，则X的某一函数的数学期望为：

我们这里的数据为样本点，是离散型，所以用上面的形式。

四、边际分布列

在二维离散随机变量(X, Y)的联合分布列{P(X=xi, Y=yj)}中，对j求和所得的分布列

称为X的分布列。

对Y求和同理。

五、EM算法推导

1、数据集：

观测数据：观测到的随机变量X的样本：
X = (x1,..., xn)

隐含变量：未观测到的随机变量Z的值：

Z = (z1,..., zn)

完整数据：包含观测到的随机变量X和隐含变量Z的数据：

Y = (X, Z)

Y = ((x1, z1),..., (xn, zn))

2、EM算法的推导

Em算法是从含有隐含变量的数据(完整数据)中计算极大似然估计。Z为隐含变量，则从可观测数据入手，对参数进行极大似然估计。

根据边缘分布列的定义：

首先改写L(θ) ：

式(1)将p (xi) 用边缘分布列反向拆分为联合分布。

接下来，定义隐含变量Z的分布Qi：

我们在(1)式的 ln 里，分子分母同乘一个值，得到(2)式：

接下来需要利用到Jensen不等式和数学期望，在期望方程中，我们用到了

如上公式。套用在(2)式中，我们定义为：

套用到Jensen不等式中，即为：

根据Jensen不等式，其中lnx为凹，公式如下：

接下来我们将(4)式展开，得到如下：

那么，我们可以得到L(θ) 和 (5) 的关系：

我们可以将(5)式看作是 θ 的函数，θ 又是概率模型中的参数，那么上式求得的左式，即为L(θ)的下界。

我们求θ的过程，可以看作图中右移的过程， 在给定θ之后，求Qi的过程，即为上移的过程。

3、等式成立的条件

将上图推导的(5)式复制下来：

我们首先固定住 θ，选择Q的可能分布，当等号成立的时候，即为达到L(θ)的下界。

根据Jensen不等式等号成立的条件：

Jensen不等式的等号成立的条件是当X为常量，即：函数f 的值为一条直线。

在(3)式和(5)式的关系可看出：

等号成立的条件：

即Jensen不等式中，上图为我们定义的X。我们可以通过如下方法对C进行变换：

可以得到C的代值。

我们用C的代值来代替下式的右边C：

那么可以进一步推理：

则可以得到Qi(zi)的代值，即p(zi | xi ; θ)。从概率的角度而言，表示为在θ参数的模型中，在xi的条件下，取到zi的概率。

至此，EM算法推导就结束了，接下来系统的讲一下EM算法的逻辑步骤。

总结而言：

E步骤：固定 θ ，求隐含变量zi的概率分布，Qi(zi)。

M步骤：给定Qi(zi)，用极大似然估计来计算 θ，并更新。