EM算法

Jensen’s inequality

这一部分引入了Jensen不等式来导出EM算法，利用jensen不等式取等号的条件构造似然函数的下界，并且可以证明EM算法是可以收敛的。最后一部分将算法代入高斯混合模型求解。

convex function(凸函数)

设$f$是一个值域为实数的的函数，如果对于$x\in R$有$f’’(x)\ge0$，那么$f$是一个凸函数。在$f$的输入是向量化的值的情况下，那么该函数的Hessian矩阵是半正定的($H\ge0$)，如果二阶导是大于0的，该函数就是“strictly convex”的，输入是向量化的情况下，Hessian矩阵就是严格半正定的。

公式

如果$f$是一个凸函数，设$X$为随机变量，则有

$$E[f(x)]\ge f(E(X))$$

另外，如果$f$是”strictly convex”的，那么当且仅当$X=E[X]$的概率为1时，等式$E[f(x)]=f[E(X) ]$成立，由于表示期望可以删除括号的约定，$f(EX)=f(E[X])$

为了对该不等式有一个直观的理解，可以用下图来说明：

Remark：如果函数是一个凹函数，那么不等式为$E[f(x)]\le f[E(X)]$

EM算法

建模问题

假如有由m个独立样本组成的训练集$\{x^{(1)},…,x^{(m)}\}$，现在希望通过模型$p(x,z)$对数据进行建模，通过最大似然估计拟合参数：

$$\ell(\theta)=\sum_{i=1}^mlogp(x;\theta)=\sum_{i=1}^{m}log\sum_zp(x,z;\theta)$$

但是，直接求解最大似然估计可能很困难，因为$z^{(i)}$是一个随机隐变量，如果能够观测到$z^{(i)}$的话，求解将会变得容易。

求解思路

E步：重复构造一个似然函数的下界
M步：进一步优化这个下界的取值

利用jensen不等式：

$$\begin{align} \sum_i logp(x^{(i)};\theta) &= \sum_{i}log_{z^{(i)}}p(x^{(i)},z^{(i)};\theta) \\ &=\sum_ilog\sum_{z^{(i)}}Q_i(z^{(i)})\frac{p(x^{(i)},z^{(i)};\theta)}{Q_i(z^{(i)})}\\ &\ge \sum_i\sum_{z^{(i)}}Q_i(z^{(i)})log\frac{p(x^{(i)},z^{(i)};\theta)}{Q_i(z^{(i)})} \end{align}$$

证明过程：
有$X_i=\frac{p(x_{(i)},z^{(i)};\theta)}{Q_i(z^{(i)})} \in X,i=1,2,…,m$,在这个式子中，$X_i$的取值受未知的$z^{(i)}$和$Q(Z^{(i)})$所影响，现在设$z^{(i)}$的分布函数就是$Q(z^{(i)})$，所以整个式子的值只受$z^{(i)}$所影响。
设$f(X)=logX$
那么(第二步)，$X_i$的期望$E(X_i)=\sum_{z^{(i)}}Q_i(z^{(i)})X_i=\sum_{z^{(i)}}Q_i(z^{(i)})\frac{p(x_{(i)},z^{(i)};\theta)}{Q_i(z^{(i)})}$
所以，$f(E(X_i))=log\sum_{z^{(i)}}Q_i(z^{(i)})\frac{p(x_{(i)},z^{(i)};\theta)}{Q_i(z^{(i)})}$
另外(第三步)，$f(X_i)$的期望$E(f(X_i))=\sum_{(z^{(i)})}Q_i(z^{(i)})log\frac{p(x^{(i)},z^{(i)};\theta)}{Q_i(z^{(i)})}$
由于$f(X)=logX$的二阶导小于0，所以该函数是一个凹函数，所以有$f(E(X_i))\ge E(f(X_i))$，综上，每一个$X_i$的期望对应的函数值都大于$f(X_i)$的期望，上式得证。

$Q_i(z^{(i)})$的选择

现在，对于任何分布函数$Q_i$，公式3都对最大似然估计$\ell(\theta)$限定了一个下界。为了让估计更准确，要尽量让似然函数与下界更接近。根据jensen不等式的性质，当且仅当$f(X)$的输入都是一个常量时，等号才成立，当等号成立时，此时的下界是最接近的似然函数的，所以，要求不等式的输入为一个常量，使等式成立。

$$\frac{p(x^{(i)},z^{(i)};\theta)}{Q_i(z^{(i)})}=c$$

要使上式成立，易得:

$$Q_i(z^{(i)})\propto p(x^{(i)},z^{(i)};\theta)$$

由于$\sum_zQ_i(Z^{(i)})=1$，可得:

$$\begin{align} Q_i(z^{(i)}) &= \frac{p(x^{(i)},z^{(i)};\theta)}{\sum_zp(x^{(i)}),z;\theta)} \\ &=\frac{p(x^{(i)},z^{(i)};\theta)}{p(x^{(i)});\theta} \\ &=p(z^{(i)}|x^{(i)};\theta) \end{align}$$

因此，将$Q_i$设为给定$x^{(i)}$后$z^{(i)}$的后验分布。

算法导出

E步,对于每一个i:

$$Q_i(z^{(i)}):=p(z^{(i)}|x^{(i)};\theta)$$

M步:

$$\theta:=arg\quad max_\theta\sum_i\sum_{z^{(i)}}Q_i(z^{(i)})log\frac{p(x^{(i)},z^{(i)};\theta)}{Q_i(z^{(i)})}$$

算法收敛的证明

不断重复以上两步，直到算法收敛，如何保证算法是收敛的呢？假设$\theta^{(t)}$和$\theta^{(t+1)}$是两次连续迭代的参数，由于$Q_{i}$的选择使式(3)的等号成立，所以有:

$$\ell(\theta^{(t)})=\sum_i\sum_{z^{(i)}}Q_i^{(t)}(z^{(i)})log\frac{p(x^{(i)},z^{(i)};\theta^t)}{Q_i^{(t)}(z^{(i)})}$$

由于$\theta^{(t+1)}$是用来最大化上式的，因此有:

$$\begin{align} \ell(\theta^{t+1}) &\ge \sum_i\sum_{z^{(i)}}Q_i^{(t)}(z^{(i)})log\frac{p(x^{(i)},z^{(i)};\theta^{t+1})}{Q_i^{(t)}(z^{(i)})} \\ &\ge \sum_i\sum_{z^{(i)}}Q_i^{(t)}(z^{(i)})log\frac{p(x^{(i)},z^{(i)};\theta^t)}{Q_i^{(t)}(z^{(i)})} \\ &=\ell(\theta^{(t)}) \end{align}$$

第一个不等式来自于公式(3)，为什么不是等号呢，因为$Q_i$的参数是$\theta^t$,而第二个不等式成立的原因是因为在M步中，$\theta^{(t+1)}$正是通过最大化

$$\sum_i\sum_{z^{(i)}}Q_i^t(z^{(i)})log\frac{p(x^{(i)},z^{(i)};\theta)}{Q_i^t{z^{(i)}}}$$

得到的，所以第一个式子的值必定大于等于第二个式子的值，因此该算法必定会收敛。

Remarks

如果定义

$$J(Q,\theta)=\sum_i\sum_{z^{(i)}}Q_i(z^{(i)})log\frac{p(x^{(i)},z^{(i)};\theta)}{Q_i(z^{(i)})}$$

此时EM算法可以看作一个坐标上升算法。

高斯混合模型

E步：
计算

$$w_j^{(i)}=Q_i(z^{(i)=j})=P(z^{(i)}=j|x^{(i)};\phi,\mu,\Sigma)$$

M步:
我要贴图片啦，反正就是把$Q_i(z^{(i)})$和高斯分模型表示出来代入原始模型，如下：

现在要更新$\mu_l$，对上式求偏导置为0，解得,依旧是贴图片:

</div>

</div>
要更新$\phi_j$，把由$\phi_j$决定的项加起来，发现我们需要最大化：
</div>

</div>
由于有一个所有$\phi_j$的和为1的限制，所以可以构造拉格朗日函数：
</div>

</div>
$\beta$是拉格朗日乘子，求偏导置0，解得
</div>

</div>

$$\phi_j=\frac{\sum_{i=1}^mw_j^{(i)}}{-\beta}$$

所以$\sum_j\phi_j=1=\frac{\sum_{i=1}^m\sum_{j=1}^kw_j^{(i)}}{-\beta}$
又因为

$$\sum_jw_j^{(i)}=1$$

所以$\sum_{i=1}^m1=-\beta$
所以$\phi_j:=\frac{1}{m}\sum_{i=1}^mw_j^{(i)}$