EM算法

EM算法

唉，em算法是我看过最恶心的算法。

参考资料：$Andrew Ng$ $cs229-notes8$ 、统计学习方法（第二版）

1.极大似然估计

• 似然（$likelihood$）与概率（$probability$）

  ​ 概率，用于在已知一些参数的情况下，预测接下来在观测上所得到的结果；似然性，则是用于在已知某些观测所得到的结果时，对有关事物之性质的参数进行估值，即估计参数的可能性。

  参见：https://zh.wikipedia.org/wiki/%E4%BC%BC%E7%84%B6%E5%87%BD%E6%95%B0

​ 其实极大似然估计就是根据样本来估计统计模型的参数，选取一个参数使得当前观测的概率最大。似然函数取得最大值表示相应的参数能够使得统计模型最为合理。

推荐宋浩老师的这节课。https://www.bilibili.com/video/av36206436?t=3565&p=67

主要有以下步骤：

1. 写出总体的概率函数或概率密度函数
2. 写出似然函数（通常是概率连乘的形式）。在数理统计学中，似然函数是一种关于统计模型中的参数的函数。
3. 两边取对数，得到对数似然函数
4. 求对数似然函数关于参数的导数或偏导，并求出使得导数或偏导为0的参数。该参数即为所求

注意：

• Q：为什么是连乘的形式？A：所有样本之间的概率是相互独立的。
• 通常某个函数的极值点，导数为0或不存在。

例子：

已知存在一批可观测样本$\{x_1,x_2,…,x_n\}$，随机变量 $X$ 满足正态分布 $N(\mu,\sigma^2)$，利用极大似然估计，求出正态分布的相关参数。

解：

1. 先写出正态分布的概率密度函数：

   $$f(x) = \frac{1}{\sqrt{2\pi}\sigma}\exp^{-\frac{(x - \mu)^2}{2\sigma^2}}$$

2. 写出似然函数

   $$L(\mu,\sigma^2) = \prod_{i=1}^{n} \frac{1}{\sqrt{2\pi}\sigma}e^{-\frac{(x_i - \mu)^2}{2\sigma^2}} = (\frac{1}{\sqrt{2\pi}})^n(\sigma^2)^{-\frac{1}{2}n}e^{-\frac{\sum_{i}^{n}(x_i-\mu)^2 }{2\sigma^2}}$$

3. 两边取对数，得到对数似然函数

   $$\ln L(\mu,\sigma^2) = n\ln(\frac{1}{\sqrt{2\pi}})-\frac{1}{2}n\ln(\sigma^2)-\frac{\sum_{i=1}^n (x_i-\mu)^2}{2\sigma^2}$$

4. 求对数似然函数关于$\mu$ ，$\sigma^2$ 的偏导

   $$\frac{\partial \ln(L(\mu,\sigma^2))}{\partial \mu} = \frac{\sum_{i=1}^n(x_i-\mu)}{\sigma^2} = 0$$ $$\sum_{i=1}^n(x_i-\mu) = 0 \rightarrow x_1+x_2+...+x_n-n\mu = 0$$

$$\mu = \frac{x_1+x_2+x_3+...+x_n}{n}$$ $$\frac{\partial \ln(L(\mu,\sigma^2))}{\partial \sigma^2} =-\frac{n}{2\sigma^2}+\frac{\sum_{i=1}^n (x_i-\mu)^2}{2\sigma^4} = 0$$

化简，可得：

$$\sigma^2 = \frac{(x_1-\mu)^2 + (x_2-\mu)^2 +...+(x_n-\mu)^2}{n}$$

观察上式可知:

• $\mu$ 即为样本均值
• $\sigma^2$ 为样本的方差

2. Jensen不等式

3. E-M算法的导出

$$L(\theta) = \prod_i^n P(x_i|\theta)$$ $$L(\theta) = \sum_i^n \log P(x_i|\theta) =\\ \sum_i^n\log\sum_Z P(x_i,z|\theta) = \\ \sum_i^n\log\sum_ZQ(z)\frac{p(x_i,z|\theta)}{Q(z)}$$

注意：$z$为隐变量（latent variables）$Q(z)$为$z$的一个分布，是啥分布不确定。

求这个似然函数的导数比较麻烦和困难，因此提出了EM算法，通过迭代的方式逐步求解。

继续推导，有Jensen不等式有：

$$\sum_i^n\log\sum_ZQ(z)\frac{p(x_i,z|\theta)}{Q(z)} >= \sum_i^n\sum_ZQ(z)\log\frac{p(x_i,z|\theta)}{Q(z)}$$

当且仅当$\frac{p(x_i,z|\theta)}{Q(z)}$ 为常数时取等。即：

$$\frac{p(x_i,z|\theta)}{Q(z)} = c \\ \sum_Z Q(z) = 1 \\ Q(z) ∝ p(x_i,z;\theta) Q(z) = p(z|x_i;\theta)$$

可以看出，Q是给定观测数据、参数的条件下，隐变量的一个后验分布(条件分布)。

带回到上个式子：

$$\theta^{j+1} = \arg\max_\theta \sum_i^n\sum_ZQ(z)\log\frac{p(x_i,z|\theta^j)}{Q(z)} = \\ \arg\max_\theta \sum_i^n\sum_Z p(z|x_i;\theta^j)\log p(x_i,z;\theta^j)$$

(与z无关的省略掉，给定参数$\theta^j$ 、观测数据，计算出$p(z|x_i;\theta^j)$ 再带进去。然后就只需要最大化$p(x,z;\theta)$ 得到$\theta^{j+1}$)。上述就是M步；我们来看看要极大化的那个式子

$$Q(z)\log p(x_i,z;\theta^j) = E_{Q}[\log p(x_i,z;\theta^j)] = \\ E_{p(z|x_i,\theta^j)}[\log p(x_i,z;\theta^j)] = \\ E_Z[\log p(x_i,z;\theta)|x_i;\theta^j]$$

我们将最后一个式子称为Q函数。注意，这个Q不同于上面那个Q分布。

​ Q函数是完全数据（观测数据和隐变量）的对数似然函数关于隐变量在给定观测数据和参数的情况下的条件分布的期望。E步的求期望，求的就是这个期望。

​ 念起来真的很抽象，结合例子做的话就好多了。