Li_阴宅

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

热门标签

期望最大化 (EM)（原理详细说明与推导）

作者：Li_阴宅 | 2024-07-04 03:32:27

踩

期望最大化

在此之前大家可以了解一下：一元高斯分布、多元高斯分布

在深入理解 EM 算法前，先了解一下模型参数求解方法和Jensen's inequality。

1、模型参数求解方法

有两种方法：

1）训练数据是完整的，即不缺少某些属性值，则直接用训练数据去拟合模型得到模型的参数即可，如极大似然估计和最大后验估计等。

2）训练数据是不完整的，即缺少某些属性数据，则此时不可用训练数据去拟合模型（某些属性没有数据，则无法对该属性进行拟合，所以该属性的参数无法获取）。但可以假设某些属性存在，先对其参数进行猜测，然后用观测数据去修正猜测的参数，直到参数接近最优值，如 EM 算法等。

2、Jensen's 不等式

$f$ 是一组实数的函数。若 $f''(x)\geq 0(\forall x\in R )$ 则 $f$ 是凸函数。若 $f$ 的输入参数是向量，则其是凸函数的条件可以扩展到半正定矩阵 hessian H ( $H\geq 0$ )。

如果 $f''(x)> 0(\forall x )$ ，则其是严格的凸函数（在向量中，其 H 必须是正定的（ $H> 0$ ））。

如何理解严格的凸函数：

左中右

如上图所示，左图中 x 轴有直线，中间的图 y轴有直线，则不能叫严格的凸函数，因为在直线阶段时 $f''(x) = 0$ 。对于右边图对于任意的 x 恒有 $f''(x)> 0$ 。

Jensen's inequality 定理： $f$ 是凸函数，设 $X$ 是一随机变量，则： $E[f(X)]\geq f(EX)$ 。

此外，若 $f$ 是严格的凸函数，则当且仅当 $X=EX$ 且概率为1 时 $E[f(X)]= f(EX)$

注：在写期望的时候，偶尔去掉括号，所以有 $f(E[X])= f(EX)$ 。

对上述定理的解释：

如上图所示，实线代表凸函数 $f$ 。

在 $x$ 轴上， $X$ 是一随机变量，有 0.5 的概率出现在 $a$ 处，0.5 的概率出现在 $b$ 处，因此 $X$ 的期望值在 $a$ 和 $b$ 的中间（midpoint）。

在 $y$ 轴上，有 $f(a),f(b),f(E[X])$ 和 $E[f(X)]$ 。 $E[f(X)]$ 是 $f(a)$ 和 $f(b)$ 的中点值（midpoint）。因为 $f$ 是凸函数，所以一定有 $E[f(X)]\geq f(EX)$ 。

注：当 $f$ 是向下凸的凸函数 ( $f''(x)\leq 0$ 或 $H\leq 0$ ) 时 $E[f(X)]\leq f(EX)$ 。EM 算法用到的正是这部分。

3、EM算法

3.1 EM 定义

In statistics, an expectation maximization (EM) algorithm is an iterative method to find maximum likelihood or maximum a posteriori (MAP) estimates of parameters in statistical models, where the model depends on unobserved latent variables. -- Wikipedia

EM 算法是在数据不完整、缺少数据点或有未观察（隐藏）的潜在变量时，为模型参数找到最大似然估计值的一种方法。这是一种近似极大似然函数的迭代方法。虽然极大似然估计可以找到一组数据的最佳拟合模型，但对于不完整数据集表现不是很好。但复杂的EM算法可以找到模型参数即使数据存在缺失值。其工作原理是为缺失的数据点选择随机值，并使用这些猜测来估计第二组数据。得到的新值用于为第一个数据集创建更好的猜测，这个过程一直持续下去，直到算法收敛到一个固定点。

总的来说，EM算法是用于含有隐含变量（潜在变量或缺失值）的概率模型参数的极大似然估计和最大后验估计。EM 算法的每次迭代由两步组成：

1）E 步：求期望

2）M 步：求极大

隐含变量的理解？：这是相对于观测变量。若观测变量是完整的，则可直接用极大似然或贝叶斯估计模型参数，但在现实中会遇到不完整的训练样例，即一些属性数据未知或结果未知（如非监督分类无标签、线性回归中的w、b），这就叫隐含变量，此时不可以用上述方法估计模型参数，而 EM 算法就是对含有隐变量的不完整训练样本的概率模型参数估计的极大似然或最大化后验概率估计的方法。

假设观测变量有：A1，A2，A3，隐含变量（未被观测到或缺失变量）有 B1，B2，Y1，则完整观测变量 = 观测变量+隐含变量

EM：直译为期望最大化算法，一般叫 EM 算法。

3.2 EM 算法原理

期望最大化(EM)是一种用于点估计的技术。给定一组可观察到的变量X和未知的(潜在的)变量Z我们想估计模型中的参数θ。

点估计的两个标准是极大似然和极大后验:

$\hat{\theta}_{ML}=\arg \max_{\theta} \log p(x|\theta)$

$\hat{\theta}_{MAP}=\arg \max_{\theta} \log p(x,\theta) =\arg \max_{\theta} [\log p(x|\theta)+\log p(\theta)]$

下面主要考虑的是似然估计，最大后验的计算方法与似然估计类似。

考虑所有的观察数据集为 $X(x_n^T)$ ，所有的潜在变量数据集为 $Z(z_n^T)$ ，所有模型参数为 $\theta$ 。对参数 $\theta$ 建立概率分布的似然估计：

$L(\theta) = \sum_{n=1}^N \ln p(x_n|\theta) =\sum_{n=1}^N \ln \sum_{z_n}p(x_n,z_n|\theta)$

$L$ 代表 $\log$ or $\ln$ ； $z_n$ 表示第 n 个隐变量，该隐变量可能有多个取值（v1,v2,...），因此需要考虑所有取值的情况，即在 $p(x_n,z_n|\theta)$ （代表单个变量某个取值的概率）前面加一个求和的符号。注意，同样适用于连续的潜在变量，只需将 $p(x_n,z_n|\theta)$ 前的和替换为一个积分。

注：联合分布 $p(X,Z|\theta)$ 属于指数家族。

上式很难优化求解 $\theta$ ，因为 $\ln$ 不能放到和的里面，且 $z_n$ 是潜在随机变量不可知，所以上式不可算。若 $z_n$ 可以被观测到，则极大似然估计会容易。

EM 算法的策略是构建 $L(\theta)$ 的下界（E-step），然后对下界进行最大化（M-step）。

这两步的基本思想：若参数 $\theta$ 已知（E步），则可根据训练数据推断出最优隐变量 $z_n$ 的值；反之，若 $z_n$ 的值已知，则可对参数 $\theta$ 做出极大似然估计（M步）。这两步交替计算，直到收敛到局部最优解。

对于每个样本，用 $Q_n$ 表示潜在变量 $z_n$ 的分布则有：

$\sum_{z}Q_{n}(z)=1,Q_{n}(z)\geq 0$

$\sum_{n} \ln p(x_n|\theta) =\sum_{n} \ln \sum_{z_n}p(x_n,z_n|\theta)$

$=\sum_{n} \ln \sum_{z_n}Q_{n}(z_n)\frac{p(x_n,z_n|\theta)}{Q_{n}(z_n)}$

$=\sum_{n} \ln E[\frac{p(x_n,z_n|\theta)}{Q_{n}(z_n)}]$

$\geq \sum_{n} E [\ln \frac{p(x_n,z_n|\theta)}{Q_{n}(z_n)}]$

$\geq \sum_{n}\sum_{z_n} Q_{n}(z_n) \ln \frac{p(x_n,z_n|\theta)}{Q_{n}(z_n)}$ （式1）

这个推导的最后一步使用了Jensen's 不等式。在上式中函数 $f(x)=\log x=\ln x$ ，其 $f(x)''=-1/ x^2<0(\forall x\in R^{+})$ ，且求和项 $\sum_{z_n}Q_{n}(z_n)[\frac{p(x_n,z_n|\theta)}{Q_{n}(z_n)}]$ 是数量 $[\frac{p(x_n,z_n|\theta)}{Q_{n}(z_n)}]$ （ $z_n$ 服从 $Q_n$ 的分布）的期望。

log 函数的 Jensen's 不等式：

对于 $\alpha_n\geq 0,\sum\alpha_n=1,x_n>0$ 有：

$\log(\sum_n \alpha_nx_n)\geq \sum_n\alpha_n\log(x_n)$

当且仅当 $\alpha_n=1$ 时，等式成立。

$Q_n$ 类似于这里的 $\alpha_n$ ， $[\frac{p(x_n,z_n|\theta)}{Q_{n}(z_n)}]$ 类似于这里的 $x_n$ 。

通过 Jensen's 不等式，有：

$f(E_{z_n\sim Q_n}[\frac{p(x_n,z_n|\theta)}{Q_{n}(z_n)}])\geq E_{z_n\sim Q_n}[f(\frac{p(x_n,z_n|\theta)}{Q_{n}(z_n)})]$

$z_n\sim Q_n$ 表明期望是关于来自 $Q_n$ 分布的 $z_n$ 。 $Q_n$ 叫辅助函数（auxiliary function）。

对于 $Q_n$ 分布的任何数据集，式1 给出了 $L(\theta)$ 的下界。 $Q_n$ 有很多分布可以选择，应该选取哪一个呢？

如果当前参数为 $\theta$ ，则应在靠近 $\theta$ 处求其下界。将上面的不等式在特定值 $\theta$ 处成为等式（ $L(\theta)$ 会随着EM的迭代单调递增（后面证明））。

为了找到特定值 $\theta$ ，需要在上面的推导过程中保持等式成立。为让等式成立，则只需知道期望值可以用一个常数（constant）表示，即：

$\frac{p(x_n,z_n|\theta)}{Q_{n}(z_n)}=c,(\forall z_n)$

则：

$Q_{n}(z_n) \propto p(x_n,z_n|\theta)$

因为 $\sum_{z}Q_{n}(z)=1$ （ $Q_n$ 是分布函数），所以要对 $Q_n$ 进行标准化：

$Q_{n}(z_n)=\frac{p(x_n,z_n|\theta)}{\sum_{z_n}p(x_n,z_n|\theta)} =\frac{p(x_n,z_n|\theta)}{p(x_n|\theta)}$

$=\frac{p(x_n,z_n,\theta)}{p(\theta)p(x_n|\theta)} =\frac{p(z_n|x_n,\theta)p(x_n,\theta)}{p(x_n,\theta)} =p(z_n|x_n,\theta)$

由上可知， $Q_n$ 是在给定 $x_n$ 和参数 $\theta$ 条件下的 $z_n$ 的后验分布，对应 EM 算法的E步。对式1 求最大化下界对应M步。一直重复这两步，直至算法收敛。

注：对于 $X$ 中的每个观测值，其潜在变量 $Z$ 中都有相应的值，因此 $\left \{ X,Z \right \}$ 叫完整数据集（complete data set），则实际观测数据 $X$ 是不完整的。完整数据集的似然函数形式是 $\ln p(X,Z|\theta)$ ，应最大化完整数据集的对数似然函数。但实际中没有完整数据集 $\left \{ X,Z \right \}$ ，只有不完整数据集 $X$ 。对 $Z$ 中潜在变量值的状态只由后验分布 $p(Z|X,\theta)$ 给出。

如何知道算法是否收敛？

假设 $\theta^t$ 和 $\theta^{t+1}$ 表示EM算法两个连续的迭代的模型参数，将证明 $L(\theta^{t})\leq L(\theta^{t+1})$ 。这个证明的关键在于 $Q_n$ 的选取。

迭代从 $\theta^t$ 开始，则 $Q^t_{n}(z_n)=p(z_n|x_n,\theta^t)$ 。需要让式1的等式成立，所以有：

$L(\theta^{t})= \sum_{n}\sum_{z_n} Q^{t}_{n}(z_n) \ln \frac{p(x_n,z_n|\theta^{t})}{Q^{t}_{n}(z_n)}$

将上式等式右边最大化得到 $\theta^{t+1}$ ，因此有：

$L(\theta^{t+1})\geq \sum_{n}\sum_{z_n} Q^{t+1}_{n}(z_n) \ln \frac{p(x_n,z_n|\theta^{t})}{Q^{t}_{n}(z_n)}$

$\geq \sum_{n}\sum_{z_n} Q^{t}_{n}(z_n) \ln \frac{p(x_n,z_n|\theta^{t})}{Q^{t}_{n}(z_n)}$

$=L(\theta^{t})$

方程在 $\theta^{t+1}$ 处的值一定大于等于方程在 $\theta^t$ 的值。最终两者的值会相等（不断逼近）。因此，EM算法会使似然函数单调收敛。若EM收敛过慢，则两个迭代的差值小于某个容差也可以。

一般 EM 算法步骤：

1）初始化参数 $\theta_0$ ，参数的初值可以任意选择，但需要注意 EM 算法对初值是敏感的。常用的办法是选取儿个不同的初值进行法代，然后对得到的各个估计值加以比较，从中选择最好的。

2）E step，求解 $Q_n=p(Z|X,\theta^{old})$ ，得到 $Z$

3）M step，将上步得到的 $Z$ 带入下式，求解 $\theta^{new}$ ：

$\theta^{new}=\arg \max_{\theta} \sum_{n}\sum_{z_n} Q_{n}(z_n) \ln \frac{p(x_n,z_n|\theta)}{Q_{n}(z_n)}$

4）给出停止迭代的条件，一般是对较小的整数 $\epsilon$ ，若满足：

$|\theta^{new}-\theta^{old}|<\epsilon$

则停止迭代，否则将 $\theta^{new}$ 带回到 2）继续计算。

隐变量估计问题也可通过梯度下降等优化方法求解，但由于求和的项数将随着隐变量的数目以指数级上升，会给梯度计算带来麻烦；而 EM 算法则可看做是一种非梯度优化方法。

极大似然估计（MLE）和期望最大化估计的比较：

两者都可以找到最适合的参数，但是它们找到模型的方式却有很大的不同。

MLE首先收集所有数据，然后使用这些数据构建最有可能的模型。

EM对参数进行猜测，首先考虑缺失的数据，然后调整模型以适应猜测和观察到的数据。

EM算法的优缺点：

优点：

它总是保证可能性会随着每次迭代而增加。
对于许多问题，E-step和M-step通常非常简单。
M步的解通常在一定范围内。

缺点：

EM算法运行非常慢，即使在最快的计算机上。当只有一小部分丢失的数据并且数据的维数不是太大的时候，它是最有效的。维度越高，E步越慢；对于维数较大的数据，E-step在接近局部最大值时运行非常慢。
它只收敛到局部最优。
它既需要正向概率，也需要反向概率(数值优化只需要正向概率)。

3.3 EM 算法的应用

EM 算法常见的应用包括聚类、计算机视觉、混合模型拟合、用潜数据学习贝叶斯网络参数、学习隐马尔可夫模型。

参考：PRML

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