EM算法详细推导
EM算法
step 1.根据目前参数估计期望
step 2.最大化似然函数
step 3.更新算法
算法思路
假设结果由k个高斯分布产生，$\mathcal{N}_i(\mu_i,\sigma_i)(i=1,2…k)$，系数为$\pi_i(i=1,2…k)$,结果为$x_j(j=1,2,…n)$,
$P(x|\theta)=\sum_i a_i\phi(x|\theta)$,(其中$\phi$是高斯分布的密度函数)
对于n元高斯分布，$f(x)=\frac{1}{\sqrt{(2\pi)^n\det|\Sigma|}}\exp(-\frac{1}{2}(x^T-\mu^T)\Sigma^{-1}(x-\mu))$
$$ L(\theta)=\sum_jlogP(x_j|\theta),记Q(z)为隐变量z出现的概率,满足\sum q(z)=1\\改写为L(\theta)=\sum_j log\sum_z P(x_j,z|\theta) (z含各种情况)=\sum_j log\sum_z q(Z) \frac{ P(x_j,z|\theta)}{q(z)}\ge\sum_j \sum_zq(Z)log \frac{ P(x_j,z|\theta)}{q(z)} $$det:行列式
$\Sigma$:协方阵，对角线为方差，非对角线为协方差，cov(X,Y)表示线性相关程度
由Jensen 不等式：$ f(\mathbb{E}[X]) \leq \mathbb{E}[f(X)] $,f为凹函数
相当于求$E[\log\frac{P(x_j,z|\theta)}{Q(z)}|\theta^{{i}}]$
1. 目标：最大化对数似然函数
$$ L(\theta) = \sum_j \log P(x_j | \theta) $$$$ L(\theta) = \sum_j \log \sum_z P(x_j, z | \theta) $$$$ \sum_z q(z) = 1 $$$$ L(\theta) = \sum_j \log \sum_z q(z) \frac{P(x_j, z | \theta)}{q(z)} $$$$ \sum_j \log \sum_z q(z) \frac{P(x_j, z | \theta)}{q(z)} \geq \sum_j \sum_z q(z) \log \frac{P(x_j, z | \theta)}{q(z)} $$$$ Q(\theta | \theta^{(t)}) = \sum_j \sum_z q(z) \log P(x_j, z | \theta) $$
- 先验概率 (Prior Probability) 先验概率是指在观察数据或证据之前，根据已有知识或经验对事件发生可能性的主观评估。 例如，在没有任何额外信息的情况下，你认为某人感染某种疾病的可能性是 1%。
- 后验概率 (Posterior Probability) 后验概率是在观察数据或证据之后，根据新信息对事件发生可能性的更新评估。它是在先验概率的基础上结合新数据计算得出的。 例如，经过医学检测后，结合检测结果重新评估某人感染该疾病的可能性。
2. E 步（Expectation Step）
$$ q(z) = P(z | x, \theta^{(t)}) $$$$ P(z | x, \theta^{(t)}) = \frac{P(x | z, \theta^{(t)}) P(z | \theta^{(t)})}{P(x | \theta^{(t)})} $$其中：
- $P(z | \theta^{(t)}) $是隐变量的先验概率
- $ P(x | z, \theta^{(t)}) $ 是在给定隐变量 $ z $的情况下 $ x $ 的概率
其中：
- $ \mathcal{N}(x | \mu_k, \Sigma_k) $ 是高斯密度函数
- $\pi_k^{(t)} $ 是第 $ k $ 个高斯分量的权重
- $ \gamma_{jk} $ 是数据点$ x_j $ 属于第$ k $ 个高斯分量的责任度
E步相当于我们已经固定了$q(z)$，所以M步我们不需要考虑$q(z)$，它已经相当于不变量了
3. M 步（Maximization Step）
$$ Q(\theta | \theta^{(t)}) = \sum_j \sum_z P(z | x_j, \theta^{(t)}) \log P(x_j, z | \theta) $$$$ P(x_j, z | \theta) = P(x_j | z, \theta) P(z | \theta) $$$$ Q(\theta | \theta^{(t)}) = \sum_j \sum_k \gamma_{jk} \log \left( P(x_j | z_k, \theta) P(z_k | \theta) \right) $$对每个参数进行最大化：
1. 更新均值 $ \mu_k $
$$ \sum_j P(z_k | x_j, \theta^{(t)}) \log P(x_j | z_k, \theta) $$$$ \log P(x_j | z_k, \theta) = -\frac{1}{2} (x_j - \mu_k)^T \Sigma_k^{-1} (x_j - \mu_k) - \frac{1}{2} \log |\Sigma_k| - \frac{d}{2} \log(2\pi) $$$$ Q(\mu_k) = \sum_j P(z_k | x_j, \theta^{(t)}) \left( -\frac{1}{2} (x_j - \mu_k)^T \Sigma_k^{-1} (x_j - \mu_k) \right) $$$$ \frac{\partial Q}{\partial \mu_k} = \sum_j P(z_k | x_j, \theta^{(t)}) \Sigma_k^{-1} (x_j - \mu_k) $$$$ \sum_j P(z_k | x_j, \theta^{(t)}) (x_j - \mu_k) = 0 $$$$ \mu_k^{(t+1)} = \frac{\sum_j P(z_k | x_j, \theta^{(t)}) x_j}{\sum_j P(z_k | x_j, \theta^{(t)})} $$2. 更新协方差矩阵 $\Sigma_k $
$$ \sum_j P(z_k | x_j, \theta^{(t)}) \log P(x_j | z_k, \theta) $$$$ Q(\Sigma_k) = \sum_j P(z_k | x_j, \theta^{(t)}) \left( -\frac{1}{2} (x_j - \mu_k)^T \Sigma_k^{-1} (x_j - \mu_k) - \frac{1}{2} \log |\Sigma_k| \right) $$$$ \frac{\partial Q}{\partial \Sigma_k} = -\frac{1}{2} \sum_j P(z_k | x_j, \theta^{(t)}) \left( \Sigma_k^{-1} (x_j - \mu_k) (x_j - \mu_k)^T \Sigma_k^{-1} - \Sigma_k^{-1} \right) $$$$ \Sigma_k^{(t+1)} = \frac{\sum_j P(z_k | x_j, \theta^{(t)}) (x_j - \mu_k)(x_j - \mu_k)^T}{\sum_j P(z_k | x_j, \theta^{(t)})} $$3. 更新混合权重 $ \pi_k $
$$ \sum_j P(z_k | x_j, \theta^{(t)}) \log P(z_k | \theta) $$$$ P(z_k | \theta) = \pi_k $$$$ \sum_j P(z_k | x_j, \theta^{(t)}) \log \pi_k $$$$ \sum_k \pi_k = 1 $$$$ \mathcal{L}(\pi_k, \lambda) = \sum_j \sum_k P(z_k | x_j, \theta^{(t)}) \log \pi_k + \lambda \left( \sum_k \pi_k - 1 \right) $$$$ \frac{\partial \mathcal{L}}{\partial \pi_k} = \sum_j P(z_k | x_j, \theta^{(t)}) \frac{1}{\pi_k} + \lambda = 0 $$$$ \pi_k = -\frac{1}{\lambda} \sum_j P(z_k | x_j, \theta^{(t)}) $$$$ \sum_k \pi_k = 1 $$$$ \pi_k^{(t+1)} = \frac{1}{N} \sum_j P(z_k | x_j, \theta^{(t)}) $$其中 N 是数据点总数。
4. 迭代过程
- E步: 计算 责任度 $ \gamma_{jk}$。
- M步: 更新 $ \mu_k, \Sigma_k, \pi_k $。
- 迭代直到收敛，即： $$ \|\theta^{(t+1)} - \theta^{(t)}\| < \epsilon $$ 或达到最大迭代次数。
总结
E步
- 计算后验概率： $$ P(z_k | x_j, \theta^{(t)}) = \frac{\pi_k^{(t)} \mathcal{N}(x_j | \mu_k^{(t)}, \Sigma_k^{(t)})}{\sum_{k'} \pi_{k'}^{(t)} \mathcal{N}(x_j | \mu_{k'}^{(t)}, \Sigma_{k'}^{(t)})} $$
- 计算 Q 函数。
M步
- 更新均值： $$ \mu_k^{(t+1)} = \frac{\sum_j P(z_k | x_j, \theta^{(t)}) x_j}{\sum_j P(z_k | x_j, \theta^{(t)})} $$
- 更新协方差： $$ \Sigma_k^{(t+1)} = \frac{\sum_j P(z_k | x_j, \theta^{(t)}) (x_j - \mu_k)(x_j - \mu_k)^T}{\sum_j P(z_k | x_j, \theta^{(t)})} $$
- 更新混合系数： $$ \pi_k^{(t+1)} = \frac{1}{N} \sum_j P(z_k | x_j, \theta^{(t)}) $$
这样，EM算法不断更新参数，最终收敛到局部最优解。