EM算法

实际问题

假设我们有一个样本集$\{x_1,x_2,…,x_n\}$,各样本独立。但是,各样本对应的分布$z_i$未知。换言之,该样本集并不是从同一分布中取出,而是从多个分布中的某一个取出。$z$ 是隐含变量,表示服从哪个分布。
在此种情况下,使用极大似然法,求使得似然概率最大的参数$\theta$(没有先验,也就谈不上后验概率)。

极大似然法

依旧希望似然概率最大,即:
$$\arg \max_\theta \sum_{x_i} \log p(x_i;\theta)$$

由于无法直接求出似然函数解析解,EM算法通过不断寻找似然函数的紧密下界,然后寻找使下界最优的$\theta$(由于紧密,往往也可以优化似然函数),如此不断迭代至似然函数最优。正是因为这个想法,才会想到使用Jensen不等式去找寻下界。

其中,根据Jensen不等式可推得:
\begin{eqnarray} l(\theta) = \sum_{x_i} \log p(x_i;\theta) && = \sum_{x_i} \log \sum_{z_j} p(x_i,z_j;\theta) \tag{1} \newline
&& = \sum_{x_i} \log \sum_{z_j} p(z_j) \frac{p(x_i,z_j;\theta)}{p(z_j)} \tag{2} \newline
&& \geq \sum_{x_i} \sum_{z_j} p(z_j) \log \frac{p(x_i,z_j;\theta)}{p(z_j)} \tag{3}\end{eqnarray}

因此,可以通过不断优化(3)式来不断提高似然函数下界,最终使之收敛到最优$\theta$。

这里需要说明,$p(z)$是为了数学优化目的而出现的一个概率分布列,它和隐变量分布的参数并不等同。事实上,它是给定参数(包括隐变量参数和各分布参数)和样本情况下的后验概率。

EM算法


(图中Q(z)即指p(z))

  1. 首先固定$\theta$,寻找合适的$p(z)$,使(3)成为似然函数的合宜下界。显然,在(1)=(3)时最为合宜。因为合宜,故而在此时,我们可以理解为(3)和(1)有相近的性质;
  2. 然后固定求得的$p(z)$,求使得(3)式达到最大值的$\theta$。因为(3)和(1)有相近的性质,因此使得(3)式达到最大值的$\theta$应该可以让似然函数变大;
  3. 不断迭代最终得到最优解。
    (严格证明见下一部分)

由于$\log x$严格凹,$\lambda_i > 0$,当且仅当自变量为常数时取等号:
\begin{split}&& \sum_i \log \lambda_i x_i \geq \sum_i \lambda_i \log x_i \newline
&& \text{equality is true,if and only if } \quad x_i = c,i=1,2,3,…
\end{split}

因此,当(1)=(3)时:
\begin{split}\frac{p(x_i,z_j;\theta)}{p(z_j)} = c,i=1,2,3,…\end{split}
由于多个等式分子分母相加不变:
\begin{split}c = \frac{\sum_j p(x_i,z_j;\theta)}{\sum_j p(z_j)} = \sum_j p(x_i,z_j;\theta) = p(x_i;\theta)\end{split}
因此:
\begin{eqnarray} p(z_j) &&= \frac{p(x_i,z_j;\theta)}{c} \tag{4} \newline
&&= \frac{p(x_i,z_j;\theta)}{\sum_j p(x_i,z_j;\theta)} \tag{5} \newline
&&= \frac{p(x_i,z_j;\theta)}{p(x_i;\theta)} \tag{6} \newline
&&= p(z_j|x_i;\theta) \tag{7} \end{eqnarray}

另一方面:
\begin{eqnarray} p(x_i;\theta) = \sum_j p(x_i,z_j;\theta) = \sum_j p(z_j;\theta) p(x_i|z_j;\theta) \tag{8} \end{eqnarray}

这里需要作出一些重要说明,我所看到的部分EM讲解(references中已列出部分)将z的角标也用成i,我在这里区分为j。同时,它们往往给出(7)式就结束,并没有明确说明如何求出p(z)。我在这里说明下我对其求法的理解:

  1. $p(z)$一般是多项分布的概率分布列,z取值个数已知([TBC]如果z是连续值呢?);
  2. $p(z_j)$应该是通过(6)式即贝叶斯公式求得。其中分母利用(8)式求得;
  3. 显见的,对于每一个$x_i$,都可以求出整体$p(z_j),j=1,2,3,…$,标记为$p_{x_i}(z_j)$。故而,最终应该有:
    \begin{eqnarray} p(z_j) = \sum_{x_i} p_{x_i}(z_j),j = 1,2,3,… \tag{9}\end{eqnarray}
    正是因为(9),E步叫做求期望。(我是这样理解的~但貌似不对?)

EM算法整体步骤:

  1. 给定参数初值(包括隐变量参数和各分布参数),
  2. (E步,求期望)根据上一步给定的$\theta$,计算后验概率$p(z)$
  3. (M步,最大化)根据计算出的$p(z)$,带回(3)式,求使之最大的$\theta$
    循环往复,直至收敛。

期望-最大算法不是指最大化期望!只是两个步骤而已。

收敛性证明

首先明确顺序问题:初始状态,给定初始$\theta^{(1)}$和$p^{(0)}(z)$;第一次迭代,E步求出$p^{(1)}(z)$,然后M步求出$\theta^{(2)}$;第t次迭代,给定$\theta^{(t)}$,E步求出$p^{(t)}(z)$,然后M步求出$\theta^{(t+1)}$。

那么,因为在t时刻是根据(1)=(3)求出$p^{(t)}(z)$,那么有:
$$ l(\theta^{(t)}) = \sum_{x_i} \sum_{z_j} p^{(t)}(z_j) \log \frac{p(x_i,z_j;\theta^{(t)})}{p^{(t)}(z_j)}$$
而$\theta^{(t+1)}$是对上式右边求最大值得到的,因此显然有:
$$\sum_{x_i} \sum_{z_j} p^{(t)}(z_j) \log \frac{p(x_i,z_j;\theta^{(t+1)})}{p^{(t)}(z_j)} \geq \sum_{x_i} \sum_{z_j} p^{(t)}(z_j) \log \frac{p(x_i,z_j;\theta^{(t)})}{p^{(t)}(z_j)} = l(\theta^{(t)})$$
另一方面:
\begin{eqnarray} l(\theta^{(t+1)}) = \sum_{x_i} \log p(x_i;\theta^{(t+1)}) && = \sum_{x_i} \log \sum_{z_j} p(x_i,z_j;\theta^{(t+1)}) \newline
&& = \sum_{x_i} \log \sum_{z_j} p(z_j) \frac{p(x_i,z_j;\theta^{(t+1)})}{p(z_j)} \newline
&& \geq \sum_{x_i} \sum_{z_j} p(z_j) \log \frac{p(x_i,z_j;\theta^{(t+1)})}{p(z_j)} \newline
&& \geq \sum_{x_i} \sum_{z_j} p^{(t)}(z_j) \log \frac{p(x_i,z_j;\theta^{(t)})}{p^{(t)}(z_j)} \newline
&& = l(\theta^{(t)})\end{eqnarray}
如此就可以证明迭代过程中似然函数的单调增性。单调有界故而收敛。
似然函数是凸函数才能收敛到全局最优值。

实例:三硬币模型

参 李航《统计学习方法——EM算法》

PRML角度

[TBC]PRML角度
PRML EM

EM & K-means

K-means的损失函数可以写成:
$$J(C,\mu) = \sum_i || x_i - \mu_C||^2$$
其中,C是类分配,$\mu$是类重心。因此可以将K-means视为坐标上升或者EM算法。

高斯混合模型

[TBC]

references

从最大似然到EM算法浅解

The EM Algorithm

李航《统计学习方法》