EM算法原理及其应用-一

作者 Lucyyang 日期 2018-08-06
EM算法原理及其应用-一

It gets easier everyday, but you should do it everyday, that's the hard part.

在最近的学习中,发现EM算法应用非常广泛,不止是在机器学习中,在传统通信的迭代译码、信道估计等问题上都涉及到了EM算法,因此针对EM算法进行一个专题总结。

引入

假如你有如下图的一些数据需要拟合,明确告诉你它们是从高斯分布生成$X \sim N ( \mu, \sigma ^{2})$的,那你要如何求这个高斯分布的参数-均值与方差呢?(记待估计参数为$\theta ^ {T}=(\mu , \sigma ^2))$呢? 1:http://oub7k42zb.bkt.clouddn.com//EM1Fig2.png

我们可以假设高斯分布的参数已知,那么对于每一个从这个高斯分布生成的数据的概率也就知道了,我们把它们进行相乘:

$$p(X| \theta )=\prod \limits_i p( x_i | \theta )$$ 我们所要求的$ \theta $就是使上式概率乘积结果最大的$ \theta $。因此我们对上式求微分,并使之等于0,这样可以方便地求出最大可能的均值和方差了。

但假如现在数据变成了下图这样,我们无法从单个的高斯分布中产生这些数据,那么刚刚的方法就不行了,这个时候就需要借助Expectation Maximization (EM) 算法进行估计了。 1:http://oub7k42zb.bkt.clouddn.com//EM1Pig1.png

最大似然估计

在介绍EM算法之前,我们先介绍一下最大似然估计问题。

假设我们现在有一个概率密度函数$p( \mathbf{x} | \Theta )$, 其中$ \Theta $是函数的参数(例如对于高斯分布来说$ \Theta $就是均值和方差)。 现在我们有$ N $个从这个分布中生成的数据,并且都是独立同分布的(i.i.d.)。因此,这些数据的联合分布可以写为: $$ p( \mathbf{x} | \Theta) = \prod_{i=1}^{N}p(x_i | \Theta) = L(\Theta | X) $$

其中,$L(\Theta | X)$ 就是给定数据的参数$\Theta$的似然函数(likelihood)。对于似然函数来说,数据$ \mathbf{x} $是固定的,而$\Theta$是变量。 在最大似然估计问题中, 我们的目标是找到使$L$最大的$\Theta$。即我们希望找到$ \Theta^{*} $使得: $$\Theta^{*} = arg \max \limits_{ \Theta } L( \Theta | X)$$

更多时候,为了简化问题,我们会直接最大化$log(L( \Theta | x))$。对于上述问题,给定了数据,要求其分布参数,就是一个非常典型的最大似然问题。

EM算法综述

隐变量引入

EM 算法的一个很重要的技巧是引入了隐变量(hidden variables),为什么要引入隐变量呢? 这要从EM算法的两个应用说起。第一种情况是观测值缺失,由于一些局限性可能只能观测到数据的一部分。另一种情况是似然函数的最大化是一件非常棘手的事情,但是当我们假定加入了缺失值或者隐变量之后问题可以被简化。(一般来说,加入的隐变量与分布是相关的,可以看做是数据产生的一些隐含条件。)第二种情况在计算模式识别(computational pattern recognition)中非常常见。

出于上述原因,我们将$ \mathbf{x} $称之为不完全数据(incomplete data) 并且假设$\mathbf{Z}=(\mathbf{x},\mathbf{y})$为完全观测集(complete data),而联合密度函数为: $$p(\mathbf{Z} | \Theta)=p(\mathbf{x}, \mathbf{y} | \Theta) =p(\mathbf{y}|\mathbf{x},\Theta)p(\mathbf{x}| \Theta)$$ 联合密度函数表示着观测值和缺失值之间的关系。

有了这个新的概率密度函数后,我们可以定义新的似然函数: $$L(\Theta | \mathbf{Z})=L(\Theta | \mathbf{x}, \mathbf{y})=p(\mathbf{x},\mathbf{y} | \Theta)$$ 并且称之为完整数据的似然函数(complete-data likelihood)。请注意缺失数据(或者隐变量)$y$是未知、随机并且是从一个先验的潜在分布中产生的。我们可以将$L( \Theta, \mathbf{x},\mathbf{y})=h_{\mathbf{x},\Theta}(y)$,即对于函数$h_{\mathbf{x},\Theta}(\dots)$,$\mathbf{x}$和$\Theta$都是常数而$y$是随机变量。

E-step

EM算法首先求完整数据似然函数$p(\mathbf{x,y}|\Theta)$的期望值,其中$y$是未知数据而$x$是给定的观测数据,$\Theta$也是当前的估计参数。 $$Q(\Theta,\Theta^{(i-1)})=E\left[\log p(\mathbf{x,y}|\Theta)|\mathbf{x},\Theta^{(i-1)} \right]$$ 其中$\Theta^{(i-1))}$是我们用来估计期望的现有估计参数(定值),而$\Theta$是我们用来增加$Q$的新变量。

理解上式的一个关键是,$\mathbf{x}$和$ \Theta^{(i-1)}$是常量, $\Theta$是我们将要在M-step中进行调整的参量,$\mathbf{y}$是服从分布$f(\mathbf{y}|\mathbf{x},\Theta^{(i-1)})$的随机变量。因此上式可以重新写为: $$ E\left[\log p(\mathbf{x,y}|\Theta)|\mathbf{x}, \Theta^{(i-1)} \right]=\int_{\mathbf{y} \in \mathbf{r}} \log p(\mathbf{x},y|\Theta)f(y|\mathbf{x},\Theta^{(i-1)})dy$$

其中$f(y | \mathbf{x}, \Theta^{(i-1)}) $ 是未被观测数据的边缘分布。实际情况中,最好情况是该分布只与$\Theta $有关,最坏情况是数据很难被获得。因此我们可能会用 $f(y, \mathbf{x} | \Theta^{(i-1)}) = f(y| \mathbf{x},\Theta^{(i-1)}) f(x|\Theta^{(i-1)})$进行计算。

一些额外的解释:假如函数$h(\Theta,\mathbf{y})$中$\Theta$是个常量,$\mathbf{Y}$是由分布$f_{\mathbf{Y}}(y)$产生的随机变量。那么只关于$\Theta$的函可以这样获得: $$q(\Theta)=E_{\mathbf{Y}}[h(\Theta,\mathbf{Y})]=\int_{\mathbf{y}}h(\Theta,\mathbf{y})f_{\mathbf{y}}(y)dy$$ 这个函数对于$\Theta$来说就可以求其最大值。

以上就是E-step所做的,即根据上一次估计的参数求出待被M-step进行最大化的期望函数$Q(\Theta,\Theta^{(i-1)})$。

M-step

M-step即最大化之前求出的期望函数$Q(\Theta,\Theta^{(i-1)})$ :

$$\Theta^{(i)}=arg\max\limits_{\Theta} Q( \Theta,\Theta^{(i-1)}) $$

就是说我们要找到使函数$Q(\Theta,\Theta^{(i-1)})$最大的$\Theta$。对于不同的具体问题,M-step实现方式不同,我们会在具体应用(二)和(三)中介绍相应的实现。

EM算法中的E-step和M-step是交替进行的,直到到达收敛或者停止准则。EM算法中的每一次迭代都保证了似然函数是递增的,即:

$$\log p(\mathbf{X}|\Theta^{(i+1)})= L(\Theta^{(i+1)}) \geq L(\Theta^{(i)}) $$

因此最终是会收敛到似然函数的最大值。

收敛性证明

琴生不等式(Jensen's inequality)

1:http://oub7k42zb.bkt.clouddn.com//EM1Fig3.png

对于任意凹函数(concave)有: $$f(tx_1 + (1-t)f(x_2)) \geq tf(x_1) + (1-t) f(x_2), t \in [0,1] $$ 在概率论中,有一般形式: $$\phi(E[\mathbf{X}]) \geq E[\phi(\mathbf{X})] $$ 其中$\mathbf{X}$是随机变量,$\phi$是凹函数。 对于$log(x)$显然是凹函数,有以上性质成立。

基于琴生不等式的收敛性证明

EM算法的收敛性证明方法有很多种,基于琴生不等式是比较直接明了的方式。 证明:

已知$\log P(X|\Theta)=\log P(X,Z|\Theta)-\log P(Z|X,\Theta)$, 使用分布$P(Z|X,\Theta^{(g)})$对上式求期望,有: $$E_{P(Z|X,\Theta^{(g)})}[\log P(X|\Theta)]=E_{P(Z|X,\Theta^{(g)})}[\frac{\log P(X,Z|\Theta)}{\log P(Z|X,\Theta)}]$$ 针对隐变量$Z$展开,则左式为: $$\log P(X|\Theta)=\int_{z}\log P(X|\Theta) P(z|X,\Theta^{(g)})dz$$ 右式为: $$\int_z \log P(X,z|\Theta) p(z|X,\Theta^{(g)})dz-\int_z \log p(z|X,\Theta)p(z|X,\Theta^{(g)})dz$$ 定义上式为: $$ Q(\Theta,\Theta^{(g)}) - H(\Theta,\Theta^{(g)}) $$ 现需证明:

$$ H(\Theta^{(g)}, \Theta^{(g)}) - H(\Theta,\Theta^{(g)}) \geq 0$$

$$\int \log p(z|X,\Theta^{(g)}) P(z|X,\Theta^{(g)})-\int \log p(z|X,\Theta) p(z|X, \Theta^{(g)})$$

$$=\int_{z} \log \left(\frac{P(z|X, \Theta^{(g)})}{P(z|X,\Theta)} \right) P(z|X,\Theta^{(g)}) dz$$

$$=\int_{z}-\log\left( \frac{P \left(z|X, \Theta \right)}{P \left (z|X, \Theta^{(g)} \right)} \right) p(z|X,\Theta^{(g)})$$

根据Jessen不等式,有:

$$ \int-\log\left(\frac{\left(P(z|X,\Theta) \right)}{P\left(z|X,\Theta^{(g)} \right)}\right)P(z|X,\Theta^{(g)})dz\geq -\log \int P(z|X,\Theta)dz = 1$$

证毕。