EM 算法(Expectation Maximization Algorithm)

EM 算法(Expectation Maximization Algorithm)


    1. EM 算法简介
    1. 准备知识
      • 2.1 极大似然估计
      • 2.2 Jensen 不等式
    1. EM 算法详解
      • 3.1 问题描述
      • 3.2 EM 算法推倒
      • 3.3 EM 算法流程
    1. EM 算法小结

1. EM 算法简介

  • EM算法是一种迭代优化策略,由于它的计算方法中每一次迭代都分两步,其中一个为期望步(E步),另一个为极大步(M步),所以算法被称为EM算法(Expectation Maximization Algorithm)。EM算法受到缺失思想影响,最初是为了解决数据缺失情况下的参数估计问题,其算法基础和收敛有效性等问题在Dempster,Laird和Rubin三人于1977年所做的文章Maximum likelihood from incomplete data via the EM algorithm中给出了详细的阐述。其基本思想是:首先根据己经给出的观测数据,估计出模型参数的值;然后再依据上一步估计出的参数值估计缺失数据的值,再根据估计出的缺失数据加上之前己经观测到的数据重新再对参数值进行估计,然后反复迭代,直至最后收敛,迭代结束。

  • EM算法作为一种数据添加算法,在近几十年得到迅速的发展,主要源于当前科学研究以及各方面实际应用中数据量越来越大的情况下,经常存在数据缺失或者不可用的的问题,这时候直接处理数据比较困难,而数据添加办法有很多种,常用的有神经网络拟合、添补法、卡尔曼滤波法等等,但是EM算法之所以能迅速普及主要源于它算法简单,稳定上升的步骤能非常可靠地找到“最优的收敛值”。随着理论的发展,EM算法己经不单单用在处理缺失数据的问题,运用这种思想,它所能处理的问题更加广泛。有时候缺失数据并非是真的缺少了,而是为了简化问题而采取的策略,这时EM算法被称为数据添加技术,所添加的数据通常被称为“潜在数据”,复杂的问题通过引入恰当的潜在数据,能够有效地解决我们的问题。

2. 准备知识

  • 介绍EM算法之前,我们需要介绍极大似然估计以及Jensen不等式。

2.1 极大似然估计

(1)举例说明:经典问题——学生身高问题

  • 我们需要调查我们学校的男生和女生的身高分布。 假设你在校园里随便找了100个男生和100个女生。他们共200个人。将他们按照性别划分为两组,然后先统计抽样得到的100个男生的身高。假设他们的身高是服从正态分布的。但是这个分布的均值 $\mu $ 和方差 $\sigma^2$ 未知, 这连个参数就是我们要估计的。记作$\theta=[\mu, \sigma]^T$。
  • 问题:我们知道样本所服从的概率分布和模型一些样本,需要求解该模型的参数。
    image1
  • 我们已知的有两个:样本服从的分布模型、随机抽取的样本;我们未知的有一个:模型的参数。根据已知条件,通过极大似然估计,求出未知参数。总的来说:极大似然估计就是用来估计模型参数的统计学方法。

(2)如何估计

  • 问题数学化:设样本集 $X=x_1,x_2,…,x_N$其中 N=100 , $p(x_i|\theta)$ 为概率。由于 100 个样本之间独立同分布,所以我同时抽到这100个男生的概率就是他们各自概率的乘积,也就是样本集X
    中各个样本的联合概率,用下式表示:
    $$L(\theta) = L(x_1,…,x_n;\theta)=\prod _{i=1}^np(x_i;\theta),\theta\in \Theta$$
  • 这个概率反映了,在概率密度函数的参数是 $\theta$ 时,得到$X$这组样本的概率。 我们需要找到一个参数 $\theta$,使得抽到$X$这组样本的概率最大,也就是说需要其对应的似然函数$L(\theta)$最大。满足条件的$\theta$叫做$\theta$的最大似然估计量,记为$$\hat\theta=arg\max L(\theta) $$

(3)求最大似然函数估计值的一般步骤

  • 首先,写出似然函数:$$L(\theta)=L(x_1,…x_n;\theta)=\prod^n_{i=1}p(x_i;\theta),\theta \in \Theta$$
  • 然后对似然函数取对数:$$H(\theta)=\ln\prod^n_{i=1}p(x_i;\theta)=\sum \ln p(x_i;\theta)$$
  • 接着对上式求导,另导数为0,得到似然方程;
  • 最后,求解似然方程,得到的参数 $\theta$ 即为所求。

2.2 Jensen 不等式

  • 设$f$是定义域为实数的函数,如果对于所有的实数$x$, $f(x)$的二次导数大雨等于0,那么$f$是凸函数
  • Jensen不等式表述如下:如果$f$是凸函数,$X$是随机变量,那么:$E[f(X)]≥f(E[X])$。当且仅当$X$是常量时,上式取等号。其中,$E[X]$表示$X$的数学期望。
  • 例如:下图中,$f$是凸函数,$X$是随机变量,有0.5的概率是$a$,有0.5的概率是$b$。$X$的期望值就是$a$和$b$的中值了。下图可以看出$E[f(X)]≥f(E[X])$成立。
  • ⚠️注:
    1. Jensen不等式应用于凹函数时,不等号方向反向。当且仅当X
      是常量时,Jensen不等式等号成立。
    2. 关于凸函数,百度百科中是这样解释的——“对于实数集上的凸函数,一般的判别方法是求它的二阶导数,如果其二阶导数在区间上非负,就称为凸函数(向下凸)”。关于函数的凹凸性,百度百科中是这样解释的——“中国数学界关于函数凹凸性定义和国外很多定义是反的。国内教材中的凹凸,是指曲线,而不是指函数,图像的凹凸与直观感受一致,却与函数的凹凸性相反。只要记住“函数的凹凸性与曲线的凹凸性相反”就不会把概念搞乱了”。关于凹凸性这里,确实解释不统一,博主暂时以函数的二阶导数大于零定义凸函数,此处不会过多影响EM算法的理解,只要能够确定何时$E[F(X)]≥F(E[X])$或者$E[F(X)]≤F(E[X])$就可以。
      jensen

3. EM 算法详解

3.1 问题描述

我们目前有100个男生和100个女生的身高,共200个数据,但是我们不知道这200个数据中哪个是男生的身高,哪个是女生的身高。假设男生、女生的身高分别服从正态分布,则每个样本是从哪个分布抽取的,我们目前是不知道的。这个时候,对于每一个样本,就有两个方面需要猜测或者估计: 这个身高数据是来自于男生还是来自于女生?男生、女生身高的正态分布的参数分别是多少?EM算法要解决的问题正是这两个问题:
E

3.2 EM 算法推导

样本集$X=(x_1,…,x_m)$,包含$m$各独立的样本;每个样本对应的类别$z_i$是未知的(即上文中每个样本属于哪个分布是未知的);我们需要以及概率模型$p(x,z)$的参数 $\theta$,即需要找到适合的 $\theta$ 让 $:(\theta)$ 最大。根据上文 2.1 极大似然估计 中的似然函数取对数所得$\log L(\theta)$,可以得到如下式:

$$\sum \log p(x_i;\theta)=\sum i\log \sum{z_i}p(x_i,z_i;\theta)$$
$$=\sum_i\log \sum_{z_i}Q_i(z_i)\frac{p(x_i,z_i;\theta)}{Q_i(z_i)}$$
$$≥\sum_i\sum_{z_i}Q_i(z_i)\log \frac{p(x_i,z_i;\theta)}{Q(z_i)}$$

其中,第一步是根据$x_i$的边缘概率计算得来,第二步是分子分母同乘一个数得到,第三步是根据Jensen不等式得到。
这里对第三步进行展开:由于$\sum Q_i(z_i)[\frac{p(x_i,z_i;\theta)}{Q_i(z_i)}]$为$\frac{p(x_i,z_i;\theta)}{Q(z_i)}$的期望,且$\log (x)$为凹函数,根据Jensen不等式(当$f$为凹函数时:$E[f(X)]≤f(E[X])$)。The EM Algorithm

上述过程可以看作是对$\log L(\theta)$(即$L(\theta)$)求下界。对于$Q_i(z_i)$的钻则,有很多可能,那么哪种更好呢? 假设$\theta$已经给定,那么$\log L(\theta)$的值就取决于$Q_i(z_i)$和$p(x_i,z_i;\theta)$了。我们可以通过调整这两个概率使下界不断上升,以逼近$\log L(\theta)$的真实值,那么什么时候算事调整好了呢?当不等式变成等式时说明我们调整后的概率能够等价于$\log L(\theta)$了。按照这个思路,我们要找到等式成立的条件。根据Jensen不等式,要想让等式成立,需要让随机变量变成常数值,这里得到:
$$\frac{p(x_i,z_i;\theta)}{Q_i(z_i)}=c $$
$c$ 为常数,不依赖于 $z_i$。对此式作进一步推到:由于$\sum_{z_i}Q_i(z_i)=1$,则有 $\sum_{z_i}p(x_i,z_i;\theta)=c$(多个等式分子分母相加不变,则认为每个样例的两个概率比值都是$c$),因此得到下式:
$$Q_i(z_i)=\frac{p(z_i,z_i;\theta)}{\sum _zp(x_i,z;\theta)}$$
$$=\frac {p(x_i,z_i;\theta)}{p(z_i;\theta)}$$
$$=p(z_i|x_i;\theta)$$
至此,我们推出了在固定其他参数$\theta$后,$Q_i(z_i)$的计算公式就是后验概率,解决了$Q_i(z_i)$如何选择的问题。这一步就是 E 步,建立$\log L(\theta)$的下界。接下来的 M 步,就是在给定 $Q_i(z_i)$后,调整 $\theta$,取极大化 $\log L(\theta)$ 的下界(在固定$Q_i(z_i)$后, 下界还可以调整的更大)。这里可以参考 EM算法

3.3 EM 算法流程

  • 初始化分布参数 $\theta$;重复 E、M 步骤直至收敛;
  • E步骤:根据参数 $\theta$ 初始值或上一次迭代所得参数值来计算出隐形变量的后验概率(即隐形变量的期望),作为隐形变量的现估计值:$$Q_i(z_i):=p(z_i|x_i;\theta)$$
  • M 步骤:将似然函数最大化以获得新的参数值:$$\theta:=\arg\max_\theta\sum_i\sum_{z_i}\log\frac{p(x_i,z_i;\theta)}{Q_i(z_i)} $$

4. EM 算法总结

  • 优点:EM的收敛性证明方法确实很厉害,能够利用log的凹函数性质,还能够想到利用创造下界,拉平函数下界,优化下界的方法来逐步逼近极大值。而且每一步迭代都能保证是单调的。最重要的是证明的数学公式非常精妙,硬是分子分母都乘以z的概率变成期望来套上Jensen不等式。
  • 缺点:对初始值敏感。 EM算法需要初始化参数$\theta$,而参数$\theta$
    的选择直接影响收敛效率以及能否得到全局最优解。

  • EM 算法的应用:K-means 算法是 EM 算法思想的体现,E 为聚类过程,M 为更新类簇中心。 GMM(高丝混合模型)也是 EM 算法的一个应用。