统计学习方法---EM

EM算法详解

基本了解

什么是EM算法？
EM的全称是Expectation Maximization 即期望最大化。它是用来求解含有隐变量的概率模型参数的参数估计方法。因为若概率模型含有隐变量，则无法使用极大似然估计法或贝叶斯估计法来估计参数，所以提出了通过迭代不断求解似然函数的下界逼近求解对数似然函数极大化的算法即EM算法。

    为什么不能用极大似然估计法或贝叶斯估计法来估计参数？
    对数似然函数的log内具有连加操作，无法进行极大化。
    
    
      
      
    

EM的特点
EM算法主要用于生产模型

EM算法的优点：简单性，普适性

EM算法的缺点：
1. 不能保证找到全局最优值
2. 对初值敏感，常用方法是选取不同的初值进行迭代，然后选择估计值最好的初值

EM算法收敛吗？
EM算法在大多数情况下是能使收敛到一个稳定值的，但是只能保证局部最优。

EM算法的推导

EM算法是一个不断迭代的过程，一轮迭代分为两个步骤：

\quadE：求期望 E_Z[P(Y,Z|\theta)|Y, \theta^{\{i\}}]，即完全数据的对数似然函数logP(Y,Z|\theta) 关于在给定观测数据Y和当前参数 \theta^{\{i\}} 下对未观测数据 Z 的条件概率分布 P(Z|Y, \theta^{\{i\}}) 的期望。简要理解为求 Z 的期望。
\qquad我们将期望称为 Q函数 ：
Q(\theta, \theta^{(i)}) = E_Z[P(Y,Z|\theta)|Y, \theta^{(i)}]\\ \qquad\qquad\qquad\quad=\sum_Z logP(Y,Z|\theta)P(Z|Y,\theta^{(i)}) \\ 或\int_{Z} logP(Y,Z|\theta)P(Z|Y,\theta^{(i)}) dZ

\quadM：求极大 ，\theta^{(i+1)} = argmax_\theta \ Q(\theta, \theta^{(i)})

接下来我们需要了解为什么以上步骤得出参数估计序列 \{\theta^{(0)}, \theta^{(1)}, ...,\theta^{(i)}\} 近似等于极大似然估计参数。

主要有两个结论：

1. 导出EM公式：对数似然函数 L(\theta^{(i)})=log \ P(Y\theta^{(i)}) 有下界，可以不断的求解下界的极大化即 Q函数 逼近求解对数似然函数极大化。
2. 验证EM算法正确：对数似然函数 L(\theta^{(i)})=log \ P(Y|\theta^{(i)})是单调递增的，所以每一轮迭代求得的新估计值\theta能使 L(\theta)增加。

导出EM公式：
我们可以通过不同的方法导出EM公式。以下从三种方法介绍如何导出EM公式。
目标：极大化
L(\theta) =log \ P(Y|\theta)

方法一：ELBO + KL
q(Z) 是一个Z可能取值的概率分布，\int_Z q(Z) = 1
log \ P(Y|\theta) = log \ P(Y, Z | \theta) - log P(Z | Y, \theta) \\ = log \ \frac {P(Y, Z | \theta)} {q(Z)} - log \ \frac {P(Z | Y, \theta)} {q(Z)}
两边同时对Z求积分：
左边 = \int_{Z} log \ P(Y|\theta) {q(Z)} dZ = log \ P(Y|\theta) \\ 右边 = \int_{Z} q(Z) log \ \frac {P(Y, Z | \theta)} {q(Z)} dZ- \int_{Z} q(Z) log \ \frac {P(Z | Y, \theta)} {q(Z)} dZ
令
ELBO = \int_{Z} q(Z) log \ \frac {P(Y, Z | \theta)} {q(Z)} dZ \\ KL = \int_{Z} q(Z) log \ \frac {P(Z | Y, \theta)} {q(Z)} dZ
则
log \ P(Y|\theta) = ELBO + KL
因为 KL(q || p) \ge 0 ,
log \ P(Y|\theta) \ge ELBO
此时，log \ P(Y|\theta) 有一个下界ELBO，当且仅当 q = p 时，即q(Z) = P(Z|Y, \theta) ，也就是在给定Y下 Z 的后验分布。KL = 0， log \ P(Y|\theta) = ELBO，此时 ELBO 的值等价于对数似然函数。

在以 \theta^{(i)} 开始的迭代中，我们选择q^{(i)}(Z) = P(Z|Y, \theta^{(i)}) ，这时能够使l(\theta^{(i+1)}) \ge l(\theta^{(i)})，证明如下
l(\theta^{(i)}) = ELBO(X, q^{(i)}, \theta^{(i)})
因为参数\theta^{(t+1)} 是通过最大化上述公式的右手边获得的，因此
l(\theta^{(i+1)}) \ge ELBO(X, q^{(i)}, \theta^{(i+1)})\\ \ge ELBO(X, q^{(i)}, \theta^{(i)})\\ = l(\theta^{(i)})
通过极大化ELBO，即可极大化 log \ P(Y|\theta)，
\hat{\theta} = argmax_{\theta}ELBO \\ = argmax_{\theta} \int_{Z} P(Z|Y, \theta^{(i)} ) \ log \ \frac {P(Y, Z | \theta)} {q(Z)} dZ \\ = argmax_{\theta} \int_{Z} P(Z|Y, \theta^{(i)} ) log \ P(Y, Z | \theta) dZ

方法2：ELBO + Jenson inequality
log \ P(Y|\theta) =log \int_{Z} \ P(Y, Z | \theta) dZ \\ = log \int_{Z} \ \frac {P(Y, Z | \theta)} {q(z)} q(z) dZ \\ = log \ E_{q(Z)}[ \ \frac {P(Y, Z | \theta)} {q(z)}] \\ \ge E_{q(Z)} log \ [ \frac {P(Y, Z | \theta)} {q(z)}] \\ \ge ELBO
第一个不等式由jenson 不等式得出，因为 log \ \cdot 是凹函数，所以函数的期望小于于期望的函数。
当且仅当 \frac {log \ P(Y, Z | \theta)} {q(z)} = C 时，取等，即 q(Z) = P(Z | Y,\theta)
以下步骤同方法一

:注意：这里的 ELBO 即为 Q函数

验证EM算法正确：
证明log \ P(Y|\theta^{\{i\}}) 单调递增，即
log \ P(Y|\theta^{(i+1)}) \ge log \ P(Y|\theta^{(i)})
证明如下：
log \ P(Y|\theta) = log \ P(Y, Z | \theta) - log P(Z | Y, \theta) \\

令
Q(\theta, \theta^{(i)}) = \int_{Z} logP(Y,Z|\theta)P(Z|Y,\theta^{(i)}) dZ \\ H(\theta, \theta^{(i)}) = \int_{Z} log P(Z | Y, \theta)P(Z|Y,\theta^{(i)}) dZ
则
log \ P(Y|\theta) = Q(\theta, \theta^{(i)}) - H(\theta, \theta^{(i)})
令
log \ P(Y|\theta^{(i+1)}) - log \ P(Y|\theta^{(i)})
则要使结论正确，则要证明，
Q(\theta^{(i+1)}, \theta^{(i)}) - Q(\theta^{(i)}, \theta^{(i)})- [H(\theta^{(i+1)}, \theta^{(i)}) - H(\theta^{(i)}, \theta^{(i)})] \ge0
首先因为 \theta^{(i+1)} 使 Q(\theta^, \theta^{(i)}) 最大，所以Q(\theta^{(i+1)}, \theta^{(i)}) \ge Q(\theta^{(i)}, \theta^{(i)})
再证明 H(\theta^{(i+1)}, \theta^{(i)}) - H(\theta^{(i)}, \theta^{(i)}) <= 0
H(\theta^{(i+1)}, \theta^{(i)}) - H(\theta^{(i)}, \theta^{(i)}) \\ = \int_{Z} log P(Z | Y, \theta^{(i+1)})P(Z|Y,\theta^{(i)}) dZ - \int_{Z} log P(Z | Y, \theta^{(i)})P(Z|Y,\theta^{(i)}) dZ \\ = \int_{Z} log \frac {P(Z | Y, \theta^{(i+1)})}{ P(Z | Y, \theta^{(i)})} P(Z|Y,\theta^{(i)}) dZ \\ \le log \ \int_{Z} \frac {P(Z | Y, \theta^{(i+1)})}{ P(Z | Y, \theta^{(i)})} P(Z|Y,\theta^{(i)}) dZ \\ = log \ 1 = 0
综上，结论成立，即 log \ P(Y|\theta^{\{i\}}) 单调递增。

EM步骤简单阐述

ELBO(Y, q(z), \theta)为图中绿色曲线，log \ P(Y|\theta)为图中黑色曲线，横轴为\theta

步骤如下：

选取初值\theta^{(0)}

由以下公式可以得知ELBO曲线为对数似然函数曲线的下界，那么为了使两条曲线尽可能紧密，则要等于 ‘=’ 在某一个特定的 \theta 时成立，即两条曲线有相交点
log \ P(Y|\theta) \ge \int_{Z} q(Z) log \ \frac {P(Y, Z | \theta)} {q(Z)} dZ = ELBO
每一轮迭代：
1). 找到距离对数似然函数曲线最紧密的ELBO(Y, q(z), \theta)
q(Z) = P(Z | Y,\theta^{(i)})时，ELBO(Y, q^{(i)}(z), \theta^{(i)}) = log \ P(Y|\theta^{(i)})，此时，该ELBO函数与对数似然函数曲线最紧。所以ELBO(Y, q^{(i)}(z), \theta) = \int_{Z} P(Z | Y,\theta^{(i)})log \ \frac {P(Y, Z | \theta)} {P(Z | Y,\theta^{(i)})} dZ

2). 找到ELBO(Y, q^{(0)}(z), \theta)的极大值点对象的参数\theta^{(i+1)}
\theta^{(i+1)} = argmax_{\theta} \int_{Z} P(Z|Y, \theta^{(i)} ) log \ P(Y, Z | \theta) dZ

重复第 2 步操作，直到收敛，一般是对较小的正数 \epsilon_1, \epsilon_2，若满足
||\theta^{(i+1)}-\theta^{(i)}|| < \epsilon_1 或 Q(||\theta^{(i+1)},\theta^{(i)})-Q(\theta^{(i)},\theta^{(i)})|| < \epsilon_2
则停止迭代。

用另外一种思想阐述EM算法
EM算法与坐标上升法的思想大致一样，函数是J(Q, \theta)，首先更新Q，然后再更新\theta，重复计算，直到达到收敛条件。

EM算法的应用—高斯混合模型

EM算法的推广—GEM