EM算法 since 2013-11-11

期望极大算法-ExpectationMaximization算法

介绍

Expectation Maximization (EM) 是一种以迭代的方式来解决一类特殊最大似然 (Maximum Likelihood) 问题的方法，这类问题通常是无法直接求得最优解，但是如果引入隐含变量，在已知隐含变量的值的情况下，就可以转化为简单的情况，直接求得最大似然解。

EM是一种解决存在隐含变量优化问题的有效方法。竟然不能直接最大化，我们可以不断地建立的下界（E步），然后优化下界（M步）。

EM中每次迭代分两步： 1. E步，期望，通过观测数据和现有模型参数，估计missing data； 2. M步，极大化，加上missing data已知的情况下，最大化似然函数，更新模型参数

Kmeans就是应用EM思想的例子，E步，对所有数据点进行聚类(初始聚类中心可以随机)；M步，更新聚类中心

问题描述

输入：观测变量数据为Y
中间变量：隐变量数据为Z
输出：模型参数 $\theta$

推导过程

我们的目标是极大化观测数据Y关于参数 $\theta$ 的对数似然函数，即：

$\max_\theta L(\theta) \\ \begin{align} L(\theta) &= logP(Y|\theta) = log \sum_Z P(Y,Z|\theta) \\ &= log (\sum_Z P(Y|Z,\theta)P(Z|\theta)) \end{align}$

上式中含有未知变量和的对数，很难得到解析解，EM通过迭代的方法，逐步逼近最优解

目标是极大化 $L(\theta)$ ，所以第i+1次迭代，要求 $L(\theta) > L(\theta^{i})$ ，考虑二者之差：

$\begin{align} L(\theta)-L(\theta^i) &= log \left( \sum_Z P(Y|Z,\theta)P(Z|\theta) \right)-log P(Y|\theta^i) \\ &= log \left( \sum_Z P(Z|Y,\theta^i) \frac{P(Y|Z,\theta)P(Z|\theta)}{P(Z|Y,\theta^i)} \right)-log P(Y|\theta^i)\\ &\geq \sum_Z P(Z|Y,\theta^i) log \frac{P(Y|Z,\theta)P(Z|\theta)}{P(Z|Y,\theta^i)} -log P(Y|\theta^i)\\ &= \sum_Z P(Z|Y,\theta^i) log \frac{P(Y|Z,\theta)P(Z|\theta)}{P(Z|Y,\theta^i)P(Y|\theta^i)} \\ &= B(\theta, \theta^i) \end{align}$

其中不等号是根据Jensen不等式得到的，简单说就是，如果f(x)是凸函数，X是随机变量，则有： $E[f(X)] \geq f(E[X])$

倒数第二步是根据 $$ \sum_Z P(Z

Y,\theta^i)=1 $$ 得到的

显然有： $B(\theta, \theta^i) \leq L(\theta^i)$ ，因此， $B(\theta, \theta^i)$ 是 $L(\theta^i)$ 的下限，极大化前者也可使后者增大，因此：

$\theta^{i+1} := arg~\max_\theta B(\theta, \theta^i)$

其中 $\theta^i$ 是常数，化简得：

$\begin{align} \theta^{i+1} &= arg\max_\theta~B(\theta, \theta^i) \\ &= arg\max_\theta~\sum_Z P(Z|Y,\theta^i) log P(Y,Z|\theta)\\ &= arg\max_\theta~Q(\theta, \theta^i) \end{align}$

所以，EM的迭代过程相当于求Q函数并最大化的过程

计算过程：

初始化参数 $\theta^0$
E步：记 $\theta^i$ 为第i次迭代参数 $\theta$ 的估计值，对于第i+1次迭代，计算：

$\begin{align} Q(\theta, \theta^i)&=E_Z[logP(Y,Z|\theta)|Y,\theta^i]\\ &=\sum_ZlogP(Y,Z|\theta)P(Z|Y,\theta^i) \end{align}$

M步：求使 $Q(\theta, \theta^i)$ 极大化的 $\theta$ ，作为第i+1次迭代参数的估计值 $\theta^{i+1}$ $\theta^{i+1} = arg~\max_\theta Q(\theta, \theta^i)$
重复E,M步，直到收敛

参考

统计机器学习，李航博士
（EM算法）The EM Algorithm
漫谈 Clustering (番外篇): Expectation Maximization