期望最大算法

EM算法的理解

考虑这样一个场景,我们需要调查学校里男生和女生的身高分布,假设我们在校园中随机抽取了 $100$ 个男生和 $100$ 个女生,随后让男生和女生分开站,分别统计男生和女生的身高,假设身高的分布是服从高斯分布的,那么通过最大化似然函数,我们可以得到对应高斯分布的均值和方差。
如果我们没有把男生和女生分开,那么这 $200$ 个人混在一起,从中随机抽取一个人,我们甚至不知道他是男生还是女生,换句话说,我们不知道这个样本是属于哪个分布的,这是就无法通过上述方法估计男女生的身高分布的均值和方差,此时我们只有估计出了分布的参数,才能知道某个样本是属于哪个分布的。

$EM$ 算法($Expectation\;Maximization\;Algorithm$)即为期望极大算法,假设估计 $A$ 和 $B$ 两个参数,开始状态下二者都是未知的,但是如果知道 $A$ 的信息就知道了 $B$ 的信息,反过来知道了 $B$ 的信息也就得到了 $A$ 的信息,可以考虑首先赋予 $A$ 一个初值,以此得到 $B$ 的估计值,然后从 $B$ 的当前值出发,重新估计 $A$ 的取值,直到这个过程收敛。
在上面的身高问题中,先随便估计两个高斯分布的参数,假设男生均值为 $170$,方差为 $10$,女生均值为 $160$,方差为 $10$,然后计算出每个人更可能属于男生分布还是女生分布,例如一个人的身高是 $180$,那么他会更可能属于男生分布,这是 $EM$ 算法中的 $E$ 步,这样,我们就大致上将 $200$ 个人分为了男生和女生两个部分。接下来,我们使用被分为男生的 $n$ 个人重新估计男生身高分布的参数,用被分为女生的 $200-n$ 个人重新估计女生身高分布的参数,这是 $EM$ 算法中的 $M$ 步。随后更新两个分布的参数,每个样本属于两个分布的概率又会发生变化,那么在根据划分的样本估计高斯分布的参数,如此循环往复直至参数不再发生变化,算法收敛,我们也就找到了合适的模型参数。

EM算法的流程

输入:训练样本集$x={x_1,x_2,\dots,x_m}$,联合分布概率模型 $P(x,c|\theta)$,条件分布概率模型 $P(c|x,\theta)$,最大迭代次数 $J$
输出:模型参数 $\theta$

  1. 随机选取参数初值 $\theta^{(0)}$
  2. 开始迭代:
    • $E$ 步:计算联合分布的条件概率期望
      $$ L(\theta) = \sum\limits_{i=1}^m \sum\limits_{j=1}^n P(c_j|x_i,\theta^{(i)}) log P(x_i, c_j|\theta) $$
    • $M$ 步:极大化 $L(\theta)$,得到 $\theta^{(i+1)}$
      $$ \theta^{(i+1)} = \arg\max_{\theta}L(\theta) $$
    • 如果 $|\theta^{(i+1)}-\theta^{(i)}|<\epsilon$,停止迭代

李航的《统计学习方法》中有另外一种表述,其本质都是一样的。

EM算法的推导

有 $m$ 个样本观测数据 $x={x_1,x_2,\dots,x_m}$,我们要估计概率模型 $P(x|\theta)$ 的参数向量 $\theta$,假设观察数据有未观察到的隐含数据 $c={c_1, c_2,\dots,c_k}$,此时我们的对数似然函数可以写为:

$$ \begin{align}\theta^* &= \arg \max \limits_{\theta}\sum\limits_{i=1}^m logP(x_i|\theta)
\\ & = \arg \max \limits_{\theta}\sum\limits_{i=1}^m log\sum\limits_{j=1}^nP(x_i,c_j|\theta)
\\ & = \arg \max \limits_{\theta} \sum\limits_{i=1}^m log \left(\sum\limits_{j=1}^nP(x_i|c_j,\theta) P(c_j|\theta) \right)\end{align}$$

事实上,$EM$ 算法是通过迭代增加 $L(\theta)$ 来逐步更新 $\theta$ 的,假设在第 $i$ 次更新后 $\theta$ 的估计值为 $\theta^{(i)}$,我们希望新产生的估计值 $\theta^{(i+1)}$ 能使 $L(\theta)$ 增大,也就是 $ L(\theta^{(i+1)}) \gt L(\theta^{(i)}) $,我们可以考虑二者的差值:

$$\begin{align} L(\theta^{(i+1)}) - L(\theta^{(i)}) &= \sum\limits_{i=1}^m \left[ log \left(\sum\limits_{j=1}^nP(x_i|c_j,\theta^{(i+1)}) P(c_j|\theta^{(i+1)}) \right) -log P(x_i|\theta^{(i)})\right] \\
&= \sum\limits_{i=1}^m \left[ log \left(\sum\limits_{j=1}^n P(c_j|x_i,\theta^{(i)}) \frac {P(x_i|c_j,\theta^{(i+1)}) P(c_j|\theta^{(i+1)})} {P(c_j|x_i,\theta^{(i)})} \right) -log P(x_i|\theta^{(i)})\right] \\
&\ge \sum\limits_{i=1}^m \left[\sum\limits_{j=1}^n P(c_j|x_i,\theta^{(i)}) log \frac {P(x_i|c_j,\theta^{(i+1)}) P(c_j|\theta^{(i+1)})} {P(c_j|x_i,\theta^{(i)})} - \sum\limits_{j=1}^n P(c_j|x_i,\theta^{(i)}) log P(x_i|\theta^{(i)})\right] \\
&= \sum\limits_{i=1}^m \sum\limits_{j=1}^n P(c_j|x_i,\theta^{(i)}) log \frac {P(x_i|c_j,\theta^{(i+1)}) P(c_j|\theta^{(i+1)})} {P(c_j|x_i,\theta^{(i)})P(x_i|\theta^{(i)})} \\
&= \sum\limits_{i=1}^m \sum\limits_{j=1}^n P(c_j|x_i,\theta^{(i)}) log \frac {P(x_i, c_j|\theta^{(i+1)})} {P(x_i, c_j|\theta^{(i)})} \end{align}$$

其中,$log P(x_i|\theta^{(i)})$ 在 $\theta^{(i)}$ 给定的情况下是定值,$\sum_{j=1}^n P(c_j|x_i, \theta^{(i)}) =1$。

此外,上面的转换还用到了 $Jensen$ 不等式,$Jensen$ 不等式有两种形式,一种是有限形式,一种是概率论形式。
有限形式的表述如下,如果 $f$ 是凸函数,则有:

$$ f\left(\sum_{i=1}^n\lambda_ix_i\right) \le \sum_{i=1}^n \lambda_i f(x_i)\;;\quad \lambda_i \gt 0,\sum_{i=1}^n\lambda_i = 1 $$

当且仅当 $x_1=x_2=\dots =x_n=c$,$c$ 为常数时,上式取等号。

概率论形式的表述如下,如果 $f$ 是凸函数,$X$ 是随机变量,那么:

$$ E(f(X) \ge f(E(X) $$

当且仅当 $X$ 为常量时,上式取等号。

第 $i$ 轮迭代得到的对数似然函数最大值为 $L(\theta^{(i)})$,如果第 $i+1$ 轮的 $\theta^{(i+1)}$ 能够最大化 $L(\theta^{(i+1)})-L(\theta^{(i)})$,那也就是相当于最大化了第 $i+1$ 轮的似然函数 $L(\theta^{(i+1)})$。所以有:

$$\begin{align} \theta^{(i+1)} &= \arg \min_{\theta^{(i+1)}} L(\theta^{(i+1)}) \\
&=\arg \min_{\theta^{(i+1)}} (L(\theta^{(i+1)})-L(\theta^{(i)})) \\
&=\arg \min_{\theta^{(i+1)}}\sum\limits_{i=1}^m \sum\limits_{j=1}^n P(c_j|x_i,\theta^{(i)}) log \frac {P(x_i, c_j|\theta^{(i+1)})} {P(x_i, c_j|\theta^{(i)})}\\
&=\arg \min_{\theta^{(i+1)}}\sum\limits_{i=1}^m \sum\limits_{j=1}^n P(c_j|x_i,\theta^{(i)}) log P(x_i, c_j|\theta^{(i+1)}) \end{align} $$

上式约去了对 $\theta^{(i+1)}$ 来说是常数的部分,此时 $\theta^{(i)}$ 是已知的常数,$P(c_j|x_i,\theta^{(i)})$ 同样也已知,根据期望定义 $E(f(X)) = \sum_i P(X=x_i)f(x_i)$,所以上式右半部分可以看做是 $log P(x_i, c_j|\theta^{(i+1)})$ 基于条件概率 $P(c_j|x_i,\theta^{(i)})$ 的期望,上式也就是使得 $m$ 个期望加和最大的 $\theta^{(i+1)}$ 的取值,这就是最大期望一词的由来。

EM算法的解释

由上图可以看出,$EM$ 算法可以保证收敛到一个稳定点,但是却不能保证收敛到全局的极大值点,因此它是局部最优的算法,当 然,如果优化目标是凸的,则 $EM$ 算法可以保证收敛到全局最大值。

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


参考文献:
[1] 李航,《统计学习方法》,清华大学出版社