EM

观测数据表示为 $Y=(y_1,\ldots,y_n)^T$ ,未观测数据表示为 $Z=(Z_1,\ldots, Z_n)^T$，则观测数据的似然函数为

$$L(\theta) = \log \prod_{j=i}^n P(Y|\theta) = \sum_{j=i}^n \log P(Y|\theta) = \sum_{j=i}^n \log \sum_z P(Z|\theta)P(Y|Z,\theta)$$

EM思路：先是对整体求极大似然估计对数，但因为隐藏变量Z的存在，所以直接最大化L就不可能了。但是可以通过不断的建立L的下界（E步），然后优化下界（M步）。

EM算法一般化分析

每次迭代优化的目标： $\ln p(Y|\theta^{g+1}) \ge \ln p(Y|\theta^g)$ 对 $\ln p(Y|\theta) = \ln \frac {p(Y,Z|\theta)} {p(Z|Y\theta)} = \ln p(Y,Z|\theta) - \ln p(Z|Y,\theta)$ 式子两边求期望。 注意，期望是对某个分布的而言的，这里是对$p(Z|Y,\theta^{g})$求期望的。

• 左边： $\int_Z \ln p(Y|\theta) p(Z|Y,\theta^g) dZ = \ln p(Y|\theta)$ 因为不包含Z，所以可以提到积分外，里面的概率分布积分就是1.

• 右边： $\color{Red}{ \int_Z \ln p(Y,Z|\theta) p(Z|Y,\theta^g) dZ } - \int_Z \ln p(Z|Y,\theta) p(Z|Y,\theta^g) dZ$ 每次迭代只对前面一部分求最大，即$\theta^{g+1} = \arg \max_{\theta} \int_Z \ln p(Y,Z|\theta) p(Z|Y,\theta^g) dZ$ ，这个就是《统计学习方法》中的Q函数。

《统计学习方法》page158,Q函数定义：完全数据的对数似然$\log P(Y,Z|\theta)$关于在给定的观测数据Y和当前参数$\theta^g$下对未观测数据Z的条件概率分布$P(Z|Y,\theta)$的期望

这个式子里面是期望，外面求最大，这就是Expectation Maximization。 在每次迭代后，后面一部分会变小，所以整体保证了迭代目标。

$$\begin{align} p(X|\theta) &= \sum_Z p(X,Z|\theta) \\ \ln p(X|\theta) &= L(q,\theta) + KL(q||p) \\ KL(q||p) &= -\sum_Z q(Z)\ln \frac {p(Z|X,\theta)}{q(Z)} \\ L(q,\theta) &= \sum_Z q(Z)\ln \frac {p(X,Z|\theta)}{q(Z)} = \sum_Z p(Z|X,\theta^{old})\ln p(X,Z|\theta) - \sum_Z p(Z|X,\theta^{old})\ln p(Z|X,\theta^{old}) \\ \end{align}$$

EM算法框架

• 选择合适的初始参数

• E-step，计算隐含变量的后验概率$p(Z|Y,\theta^{old})$。利用当前参数值计算隐含变量的后验概率，并基于此计算目标函数的期望

• M-step，优化$\theta^{old} = \arg max_{\theta} Q(\theta, \theta^{old})$，其中$Q(\theta, \theta^{old}) = \sum_Z p(Z|Y,\theta^{old})\ln p(Y,Z|\theta)$

• 收敛性判别，是否终止

以下是以前从jensen不等式看EM算法的，感觉不如EM一般化分析清晰

E步

完全数据的对数似然$\log P(Y,Z|\theta)$ 关于在给定观测数据$Y$和当前参数$\theta_i$下对未观测数据$Z$的条件概率分布$\log P(Z|Y,\theta_i)$的期望

$$-L(\theta) = -\sum_{j=i}^n \log \sum_{z_i} P(Y,z_i|\theta) = -\sum_{j=i}^n \log \sum_{z_i} Q(Z_i)\frac{P(Y,z_i|\theta)}{Q(Z_i)} \le \sum_{j=i}^n \sum_{z_i} Q(Z_i) (-\log \sum_{z_i} \frac{P(Y,z_i|\theta)}{Q(Z_i)})$$

其中$\sum_{z_i} Q(Z_i)\frac{P(Y,z_i|\theta)}{Q(Z_i)}$ 就是 $\frac{P(Y,z_i|\theta)}{Q(Z_i)}$ 的期望，$-\log$是凸函数，所以可以用 jensen 不等式。

将上式简化下，就得到《统计学习方法》上的形式：

$$L(\theta) \ge \sum_{j=i}^n \sum_{z_i} Q(Z_i) \log \sum_{z_i} \frac{P(Y,z_i|\theta)}{Q(Z_i)}$$

期望的 Lazy Statistician 规则

• x是离散型随机变量，分布律为$P(X=x_k)=p_k, k=1,2,\ldots$,则：

  $E(Y)=\sum_{k=1}^{\infty}g(x_k)p_k$

• x是连续型随机变量，概率密度函数为 $f(x)$，则有

  $E(Y) = \int_{-\infty}^\infty g(x)f(x)dx$

jensen不等式

如果f是凸函数，则$E[f(X)] \ge f(E[X])$ 。

其实凸函数的定义就一个jensen不等式。 $f(\lambda x_1 + (1-\lambda)x_2) \le \lambda f(x_1)+(1-\lambda)f(x_2)$

推广到多个变量，得：

$$f(\lambda_1 x_1 + \ldots +\lambda_n x_n) \le \lambda f_1(x_1)+ \dots + \lambda_nf(x_n) \\ \lambda_1 \ldots \lambda_n \le 0 \\ \lambda_1 + \ldots +\lambda_n = 1$$

M步

上式相当于给出了目标函数的下界，提高下界即最大化目标函数。这个不等式的最高就是等式成立，需要让随机变量或函数值为常数, 即 $\frac{P(Y,z_i|\theta)}{Q(Z_i)} = C$。假设$\theta$给定。 因为$\sum_{Z_i} Q(Z_i) = 1$，所以$\sum_{Z_i} P(Y,z_i|\theta) = C$。 则$Q(Z_i) = \frac{P(Y,z_i|\theta)}{C} = \frac{P(Y,z_i|\theta)}{\sum_{Z_i} P(Y,z_i|\theta)} = \frac{P(Y,z_i|\theta)}{P(Y|\theta)} = P(Z_i|Y,\theta)$

所以EM算法的步骤如下：

• 初始化参数：$\theta$

• E步：$Q(Z_i) = P(Z_i|Y,\theta)$

• M步：$\theta = \arg \max_{\theta} \sum_{j=i}^n \sum_{z_i} Q(Z_i) \log \sum_{z_i} \frac{P(Y,z_i|\theta)}{Q(Z_i)}$

• 收敛判断：若似然函数未收敛，则转至第二步。

半监督EM

网上没找到半监督式的EM，但是我想，在E步算每个样本分类的期望时，不改变已经标注的类别，这样在M步时，这些标注样本依然可以起效。

online EM

参考MLAPP和《Online EM for Unsupervised Models》

有batch EM，incremental EM，stepwise EM。

• Let $\phi(x, z)$ be a vector of sufficient statistics for a single data case.

• Let $s_i = \sum_z p(z|x_i,\theta) \phi (x_i,z)$ be the expected sufficient statistics for case i, and $\mu = \sum_{i=1}^N s_i$ be the sum of the ESS.

• let $\theta(\mu)$ denote the ML or MAP estimate of the parameters in the M step.

stepsize 和 mimi_batch_size很重要。 if we take $\eta_k = (k+2)^\alpha$ , then any $0.5 \lt \alpha \le 1$ is valid. mimi_batch_size越大，则越稳定。

个人理解就是 新来的样本训练出的新参数， 然后跟momentum方式一样结合老参数更新参数

Other EM variants

Variational EM , Monte Carlo EM , Generalized EM

The EM algorithm is simple, but can be much slower than direct gradient methods

EM算法的应用

• 混合高斯模型

• 混合朴素贝叶斯模型

• 因子分析

• 贝叶斯神经网络

EM算法存在的意义是什么？