你好赵伟

这个屌丝很懒，什么也没留下！

热门标签

EM算法推导详解_em 算法推导步骤

作者：你好赵伟 | 2024-04-01 06:30:07

踩

em 算法推导步骤

文章目录

一、算法简介
二、EM算法推导
参考：

一、算法简介

最大期望算法（Expectation-Maximization algorithm, EM），或Dempster-Laird-Rubin算法，是一类通过迭代进行极大似然估计（Maximum Likelihood Estimation, MLE）的优化算法，通常作为牛顿迭代法（Newton-Raphson method）的替代用于对包含隐变量（latent variable）或缺失数据（incomplete-data）的概率模型进行参数估计。

EM算法的标准计算框架由E步（Expectation-step，求期望）和M步（Maximization step，求最大值）交替组成，算法的收敛性可以确保迭代至少逼近局部极大值。

概率模型有时既含有观测变量，又含有隐变量或潜在变量。如果概率模型的变量都是观测变量，那么给定数据，可以直接用极大似然估计法，或贝叶斯估计法估计模型参数。

但是当模型中含有隐变量时，就不能简单的使用这些估计方法。EM算法就是含有隐变量的概率模型参数的极大似然估计，或极大后验概率估计法。

二、EM算法推导

下面给出详细的推导过程：

给定一组训练样本 ${x_{1},x_{2},...x_{n}}$ ，样本间独立，我们想找到每个样本间隐含的类别 $z$ ，能使 $p (x, z)$ 最大。

通过最大似然估计建立目标函数，其中 $θ$ 是需要估计的模型参数：
$\prod_{i=1}^{m}P(x_i|θ) \tag{1}$

对其取对数，则所以公式（1）又可以写成公式（2）：
$l(θ)=logf(x|θ)=\sum_{i}^{m}logP(x|θ)\\ =\sum_{i}^{m}log\sum_zP(x,z|θ)\tag{2}$

式中第一个等号是对极大似然估计取对数，第二步是对每个样例间的每个可能类别z求联合分布概率和。

通过这个式子去求 $l(\theta)$ 还是很懵。

假如，存在一个下界 $J$ ，使得 $l(\theta) ≥ J$ 成立

那么对于如何求解最大的 $l(\theta)$ 就变得稍微容易点了：

对于 $l(\theta)$ 的下界 $J$ ，使得 $J$ 不断增大，那么 $l(\theta)$ 也会不断增大。当 $J$ 收敛时， $l(\theta)$ 也随之达到最大值。

此时，问题就转移到了 $J$ 这个下界的函数推导以及求其最大值上了

这时就会用到著名的Jensen不等式了：

对于每一个样本 $x_{i}$ ，用 $Q_{i}$ 表示该样本隐含变量z的某种分布，那么 $Q_{i}$ 满足条件是:

$\sum_{z}Q_i(z) = 1，Q_i(z) \geq 0$

于是对于（2）上下同乘以 $Q_i(z^{(i)})$ ：

\begin{aligned} l(\theta) &= \sum_{i}^{m}log\sum_zP(x,z|θ)\\ &= \sum_{i}^{m}log\sum_z Q_i(z^{(i)}) \frac {P(x,z|θ)} {Q_i(z^{(i)})} \tag{3} \end{aligned}

$\begin{aligned} l(\theta) &= \sum_{i}^{m}log\sum_zP(x,z|θ)\\ &= \sum_{i}^{m}log\sum_z Q_i(z^{(i)}) \frac {P(x,z|θ)} {Q_i(z^{(i)})} \tag{3} \end{aligned}$

l (θ) = i \sum m l o g z \sum P (x, z ∣ θ) = i \sum m l o g z \sum Q_{i} (z^{(i)}) \frac{P ( x , z ∣ θ )}{Q _{i} ( z ^{(i)} )} (3)

由于 $\sum_{z}Q_i(z) = 1$ 。用到Jensen不等式，则有：

\begin{aligned} l(\theta) &= \sum_{i}^{m}log\sum_z Q_i(z^{(i)}) \frac {P(x,z|θ)} {Q_i(z^{(i)})}\\ & \geq \sum_{i}^{m}\sum_z Q_i(z^{(i)})log \frac {P(x,z|θ)} {Q_i(z^{(i)})} \tag{4} \end{aligned}

$\begin{aligned} l(\theta) &= \sum_{i}^{m}log\sum_z Q_i(z^{(i)}) \frac {P(x,z|θ)} {Q_i(z^{(i)})}\\ & \geq \sum_{i}^{m}\sum_z Q_i(z^{(i)})log \frac {P(x,z|θ)} {Q_i(z^{(i)})} \tag{4} \end{aligned}$

l (θ) = i \sum m l o g z \sum Q_{i} (z^{(i)}) \frac{P ( x , z ∣ θ )}{Q _{i} ( z ^{(i)} )} \geq i \sum m z \sum Q_{i} (z^{(i)}) l o g \frac{P ( x , z ∣ θ )}{Q _{i} ( z ^{(i)} )} (4)

到这里， $J$ 就已经出来了。即：

\begin{aligned} l(\theta) &\geq J(z, Q)\\ &= \sum_{i}^{m}\sum_z Q_i(z^{(i)})log \frac {P(x,z|θ)} {Q_i(z^{(i)})}\tag{5} \end{aligned}

$\begin{aligned} l(\theta) &\geq J(z, Q)\\ &= \sum_{i}^{m}\sum_z Q_i(z^{(i)})log \frac {P(x,z|θ)} {Q_i(z^{(i)})}\tag{5} \end{aligned}$

l (θ) \geq J (z, Q) = i \sum m z \sum Q_{i} (z^{(i)}) l o g \frac{P ( x , z ∣ θ )}{Q _{i} ( z ^{(i)} )} (5)

而 $J$ 中 $\sum_z Q_i(z^{(i)})log \frac {P(x,z|θ)} {Q_i(z^{(i)})}$ 就是变量 $\frac {P(x,z|θ)} {Q_i(z^{(i)})}$ 的期望。

可能这里会有点晕。。。。稍微解释下这里。

设Y是随机变量X的函数，Y = g(X)，那么：

若X是离散型变量，它的分布律有 $P(X = x_k) = p_k，k=1,2,3,...。$
若 $\sum_{k=1}^{\infty}g(x_k)p_k$ 绝对收敛，则：

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

对于上面的式子（5），Y是 $\frac{p(x^{(i)},z^{(i)};\theta)}{Q_{i}(z^{(i)})}$ ，X对应于 $z^{(i)}$ ， $Q_{i}(z^{(i)})$ 是 $p_k$ 。

故： $\sum_z Q_i(z^{(i)})log \frac {P(x,z|θ)} {Q_i(z^{(i)})}$ 就是变量 $\frac {P(x,z|θ)} {Q_i(z^{(i)})}$ 的期望。

$l(\theta)\geq J(z,Q)$ ，那么我们可以通过不断最大化这个下界，来使得 $l(\theta)$ 不断提高，最终达到它的最大值。

其实到这里，E步基本就完成了。

整个E步过程可以看作是对 $l(\theta)$ 求了下界。

对于 $Q_{i}$ 的选择，有许多种可能，那么哪一种更好呢？不妨假定 $\theta$ 已经给定，那么 $l(\theta)$ 的值就取决于 $Q_{i}(z^{(i)})$ 和 $p(x^{(i)},z^{(i)})$ 了。通过调整这两个参数使得下界不断上升，以逼近 $l(\theta)$ 的真实值。

那么什么时候算是调整好了呢？当然是当等号成立时，说明调整后的值等价于 $l(\theta)$ 了。

按照这个思路，我们要找到等式成立的条件，根据Jensen不等式，要想让等式成立，需要让随机变量变成常数值：

也就是 $X_1 = X_2 = ... = X_k$ ，进而 $g(X_1) = g(X_2) = ... = g(X_k)$ 。

即： $g(x_k) = C$ ，其中c为常数，并不依赖于 $z^{(i)}$ 。

也就得到：

$g(X_k) = \frac{p(x^{(i)},z^{(i)}|\theta)}{Q_{i}(z^{(i)})} = C\tag{6}$

所以：

\begin{aligned} C &= \frac{\sum_zp(x^{(i)},z^{(i)}|\theta)}{\sum_zQ_{i}(z^{(i)})} \\ &= \sum_zp(x^{(i)},z^{(i)}|\theta) \tag{7} \end{aligned}

$\begin{aligned} C &= \frac{\sum_zp(x^{(i)},z^{(i)}|\theta)}{\sum_zQ_{i}(z^{(i)})} \\ &= \sum_zp(x^{(i)},z^{(i)}|\theta) \tag{7} \end{aligned}$

C = \frac{\sum _{z} p ( x ^{(i)} , z ^{(i)} ∣ θ )}{\sum _{z} Q _{i} ( z ^{(i)} )} = z \sum p (x^{(i)}, z^{(i)} ∣ θ) (7)

即： $\sum_zp(x^{(i)},z^{(i)}|\theta)$ 。

将该式子带回到（6）中：

$\frac{p(x^{(i)},z^{(i)}|\theta)}{Q_{i}(z^{(i)})} = \sum_zp(x^{(i)},z^{(i)}|\theta) \tag{8}$

所以：

\begin{aligned} Q_{i}(z^{(i)}) &= \frac{p(x^{(i)},z^{(i)}|\theta)}{\sum_zp(x^{(i)},z^{(i)}|\theta)} \\ &= \frac{p(x^{(i)},z^{(i)}|\theta)}{p(x_{i}|\theta)}\\ &= p(z^{(i)}|x^{(i)},\theta) \tag{9} \end{aligned}

$\begin{aligned} Q_{i}(z^{(i)}) &= \frac{p(x^{(i)},z^{(i)}|\theta)}{\sum_zp(x^{(i)},z^{(i)}|\theta)} \\ &= \frac{p(x^{(i)},z^{(i)}|\theta)}{p(x_{i}|\theta)}\\ &= p(z^{(i)}|x^{(i)},\theta) \tag{9} \end{aligned}$

Q_{i} (z^{(i)}) = \frac{p ( x ^{(i)} , z ^{(i)} ∣ θ )}{\sum _{z} p ( x ^{(i)} , z ^{(i)} ∣ θ )} = \frac{p ( x ^{(i)} , z ^{(i)} ∣ θ )}{p ( x _{i} ∣ θ )} = p (z^{(i)} ∣ x^{(i)}, θ) (9)

至此，我们在固定参数 $\theta$ 后， $Q_{i}(z^{(i)})$ 的计算公式就是后验概率，接下来就是M步，就是在给定 $Q_{i}(z^{(i)})$ 后，调整 $\theta$ ，去极大化 $l(\theta)$ 的下界 $J (z, Q)$ 。

当 $J (z, Q)$ 收敛时， $l(\theta)$ 的最大值也迭代出来了。

其实，整个EM算法归纳下来理解还是比较容易的：

（1）E-Step：
对于每一个i，计算：
$Q_{i}(z^{(i)}) = p(z^{(i)}|x^{(i)},\theta)$

（2）M-Step：
计算：
$\theta = \underset{\theta}{argmax}\sum_{i}^{m}\sum_z Q_i(z^{(i)})log \frac {P(x,z|θ)} {Q_i(z^{(i)})}$

参考：

《统计学习方法》李航著
http://www.cnblogs.com/Determined22/p/5776791.html
https://blog.csdn.net/m0_37570854/article/details/88838267
https://blog.csdn.net/qq_16000815/article/details/80384024

声明：本文内容由网友自发贡献，不代表【wpsshop博客】立场，版权归原作者所有，本站不承担相应法律责任。如您发现有侵权的内容，请联系我们。转载请注明出处：https://www.wpsshop.cn/w/你好赵伟/article/detail/347691