EM算法（一）

Why and When to Use EM Algorithm

不是所有的函数式都有解析解，EM算法是解决这种问题中的某一种（耦合问题），即一部分变量$A$相互依赖另一部分变量$B$，其中一部分变量确定另一部分就存在解析求解方法，但是都不确定没有办法直接求解。

k-means

description

先介绍一个k-means聚类方法实际观察这类耦合问题。一个最简单的问题就是二维平面上有若干个点，然后有一些点会挨得比较近，当然这个近涉及到距离的概念，挨得比较近的点称它们是一个堆。为说明问题，我们只是采用最简单的欧式距离。问题是给定一共有$k$个堆，怎样确定这些点分别属于哪个堆。

上图是一个简单的二类聚类。

mechanism

k-means聚类的思想是用一个点代表一个堆，最自然的就是用这个堆所有点的平均点代表这个堆。那么对于$k$个堆，有$k$个这样的代表点，每个点距离哪个代表点最近就属于哪个堆。目标优化值定为每个点与所属堆代表点的欧式距离之和的平均值。

记 $x^{(i)}$表示第$i$个样本点，$u^{(j)}$表示第$j$个堆得代表点，$r_{i}^{j}$表示第$i$个样本点属于第$j$个堆，$J$表示目标优化值，$N$表示样本点的数目，则

$r_{i}^{j}=\begin{cases} 1，j= \mathop{\arg\min}\limits_{k}||x^{(i)}-u^{(k)}||\\ 0，otherwise\end{cases}$ $J=\frac{1}{N}\sum\limits_{i=1}^{N}\sum\limits_{j=1}^{k}r_{i}^{j}||x^{(i)}-u^{(j)}||$

$J$这个解析式不能解析求解，但是可以发现以下两点：

给定所有代表点$u$，可以确定所有的$r$
给定所有的$r$, 我们可以求导确定所有的当前的最优的$u$

如果初始化所有代表点，上述过程可以迭代。注意到，$J$有下界，并且每轮$J$都不增，所以$J$会收敛。EM算法就是这种思想，对于耦合问题进行迭代求解。下面我们推算更一般的EM算法。

Jensen Inequality

对于上凸函数$f$, $n$个实数$\lambda_1,\lambda_2,…,\lambda_n$,满足$\sum\limits_{i=1}^{n}\lambda_i=1$,则有

$f(\sum\limits_{i=1}^{n}\lambda_ix_i) \geq \sum\limits_{i=1}^{n}f(\lambda_ix_i)$

取等条件：$x_1,x_2,…,x_n$

Derivation

EM mechanism

上文提及的两部分变量一部分称为隐变量，一部分则是正常变量，它的流程如下：

初始化正常变量
根据正常变量确定计算隐变量
根据当前隐变量更新优化正常变量
重复二三步

notation

$x_i$: 第$i$个样本
$y_i$: 第$i$个样本的观测值
$z$: 隐变量
$N$: 样本数目
$\theta$: 正常参数
$\theta_k$: 第$k$轮迭代得到的正常参数
$Q_i$: 第$i$个样本的隐变量的分布，简称隐分布

derivation

EM算法基于最大似然估计法（MLE），目标最大化概率

$P(Y|\theta)=\prod\limits_{i=1}^NP(y_i|\theta)$

取对数，目标最大化值$L$:

$\begin{align}L(Y|\theta)&=\sum\limits_{i=1}^N\log P(y_i|\theta)\\ &= \sum\limits_{i=1}^Nlog \sum_{z}P(y_i,z|\theta) \\ &=\sum\limits_{i=1}^Nlog\sum_{z}\frac{Q_i(z)P(y_i,z|\theta)}{Q_i(z)}\end{align}$

其中$Q_i$表示第$i$个样本的分布，比如k-means中，虽然不是基于MLE，但是基本思想还是EM算法的思想。隐变量是每个样本点所属的堆，对于每个样本，这个隐变量分布是不同的，所以隐分布是相对于每个样本点的隐变量而言。由于$Q_i$是个分布，有

$\sum\limits_zQ_i(z)=1$

结合 $\log$是上凸函数和$Jensen$不等式，有

$L(Y|\theta) \geq \sum\limits_{i=1}^N\sum\limits_zQ_i(z)\log \frac{P(y_i,z|\theta)}{Q_i(z)}\tag{*}$

等号成立时有

$\frac{P(y_i,z|\theta)}{Q_i(z)}=c$

对任意一个固定的$i$,所有$z$成立，其中$c$是一个数。

$P(y_i|\theta)=\sum\limits_{z}P(y_i,z|\theta)=c\sum\limits_zQ_i(z)=c$

所以有

$Q_i(z)=\frac{P(y_i,z|\theta)}{c}=\frac{P(y_i,z|\theta)}{P(y_i|\theta)}=P(z|y_i,\theta)$

记第$k$轮迭代时，确定的参数是$\theta_k$,并且

$q(\theta,\theta_k)=\sum\limits_{i=1}^N\sum\limits_zP(z|y_i,\theta_k)\log \frac{P(y_i,z|\theta)}{P(z|y_i,\theta_k)}$

EM算法由E（expectation）和M（maximization）两步，E步即根据$\theta_k$计算出上述$q$函数，M步则是更新得到新的$\theta_{k+1}$,

$\theta_{k+1} = \arg \max\limits_\theta q(\theta,\theta_k)$

然后重复迭代。

proof

往证：

$L(Y|\theta_{k+1}) \geq L(Y|\theta_k)$

首先由$Jensen$不等式和$\tag{*}$，

$L(Y|\theta)=\sum\limits_{i=1}^N\sum\limits_zP(z|y_i,\theta)\log \frac{P(y_i,z|\theta)}{P(z|y_i,\theta)}$

所以

$L(Y|\theta_{k+1})=q(\theta_{k+1},\theta_{k+1}) \geq q(\theta_{k+1},\theta_k) \geq q(\theta_k,\theta_k)=L(Y|\theta_k)$

其中第一个不等号是因为调整了$Q$分布破坏了$Jensen$不等式去等条件。

下一篇将介绍EM算法在经典的三硬币模型中的应用。

介绍和推导