> For the complete documentation index, see [llms.txt](https://json007.gitbook.io/svm/llms.txt). Markdown versions of documentation pages are available by appending `.md` to page URLs; this page is available as [Markdown](https://json007.gitbook.io/svm/em.md).

# 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**。\
在每次迭代后，后面一部分会变小，所以整体保证了迭代目标。

![](https://2270971654-files.gitbook.io/~/files/v0/b/gitbook-legacy-files/o/assets%2F-M7DcNFhVrwIk3Tks_pB%2Fsync%2F164fa3dc024f237d774877209e800ec7d2cf89f7.JPG?generation=1589383929543063\&alt=media)

$$
\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}
$$

![](https://2270971654-files.gitbook.io/~/files/v0/b/gitbook-legacy-files/o/assets%2F-M7DcNFhVrwIk3Tks_pB%2Fsync%2Ff32ebbb40a5ac1fa81a3fe757ee0dafa3f675d0f.png?generation=1589383929822263\&alt=media)

### 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](http://cs.stanford.edu/~pliang/papers/online-naacl2009.pdf)》

有batch EM，incremental EM，stepwise EM。

![](https://2270971654-files.gitbook.io/~/files/v0/b/gitbook-legacy-files/o/assets%2F-M7DcNFhVrwIk3Tks_pB%2Fsync%2Fdb928d49e94d93809a5cbf885ed64a10263d5ed6.JPG?generation=1589383929739676\&alt=media)

![](https://2270971654-files.gitbook.io/~/files/v0/b/gitbook-legacy-files/o/assets%2F-M7DcNFhVrwIk3Tks_pB%2Fsync%2F4090ed3a690f316856da826d7ce81391053c1700.png?generation=1589383929390894\&alt=media)

* 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算法存在的意义是什么？](https://www.zhihu.com/question/40797593)