9. EM算法

2 minutes read
ML
#ML • #西瓜书
views 308 words

本篇将介绍另一个当选为数据挖掘十大算法之一的EM算法

8、EM算法

EM（Expectation-Maximization）算法是一种常用的估计参数隐变量的利器，也称为“期望最大算法”，是数据挖掘的十大经典算法之一。EM算法主要应用于训练集样本不完整即存在隐变量时的情形（例如某个属性值未知），通过其独特的“两步走”策略能较好地估计出隐变量的值。

8.1 EM算法思想

EM是一种迭代式的方法，它的基本思想就是：若样本服从的分布参数θ已知，则可以根据已观测到的训练样本推断出隐变量Z的期望值（E步），若Z的值已知则运用最大似然法估计出新的θ值（M步）。重复这个过程直到Z和θ值不再发生变化。

简单来讲：假设我们想估计A和B这两个参数，在开始状态下二者都是未知的，但如果知道了A的信息就可以得到B的信息，反过来知道了B也就得到了A。可以考虑首先赋予A某种初值，以此得到B的估计值，然后从B的当前值出发，重新估计A的取值，这个过程一直持续到收敛为止。

1.png

现在再来回想聚类的代表算法K-Means：【首先随机选择类中心=>将样本点划分到类簇中=>重新计算类中心=>不断迭代直至收敛】，不难发现这个过程和EM迭代的方法极其相似，事实上，若将样本的类别看做为“隐变量”（latent variable）Z，类中心看作样本的分布参数θ，K-Means就是通过EM算法来进行迭代的，与我们这里不同的是，K-Means的目标是最小化样本点到其对应类中心的距离和，上述为极大化似然函数。

8.2 EM算法数学推导

在上篇极大似然法中，当样本属性值都已知时，我们很容易通过极大化对数似然，接着对每个参数求偏导计算出参数的值。但当存在隐变量时，就无法直接求解，此时我们通常最大化已观察数据的对数“边际似然”（marginal likelihood）。

2.png

这时候，通过边缘似然将隐变量Z引入进来，对于参数估计，现在与最大似然不同的只是似然函数式中多了一个未知的变量Z，也就是说我们的目标是找到适合的θ和Z让L(θ)最大，这样我们也可以分别对未知的θ和Z求偏导，再令其等于0。

然而观察上式可以发现，和的对数（ln(x1+x2+x3)）求导十分复杂，那能否通过变换上式得到一种求导简单的新表达式呢？这时候 Jensen不等式就派上用场了，先回顾一下高等数学凸函数的内容：

Jensen’s inequality：过一个凸函数上任意两点所作割线一定在这两点间的函数图象的上方。理解起来也十分简单，对于凸函数f(x)“>0，即曲线的变化率是越来越大单调递增的，所以函数越到后面增长越厉害，这样在一个区间下，函数的均值就会大一些了。

3.png 若f(x)是区间(a,b)上的凹函数，则对任意的x1,x2,…,xn，有不等式: 若f(x)是区间(a,b)上的凸函数，则对任意的x1,x2,…,xn，有不等式:

因为ln(*)函数为凹函数，故可以将上式“和的对数”变为“对数的和”，这样就很容易求导了。

4.png

接着求解Qi和θ：首先固定θ（初始值），通过求解Qi使得J（θ，Q）在θ处与L（θ）相等，即求出L（θ）的下界；然后再固定Qi，调整θ，最大化下界J（θ，Q）。不断重复两个步骤直到稳定。通过jensen不等式的性质，Qi的计算公式实际上就是后验概率：

5.png

通过数学公式的推导，简单来理解这一过程：固定θ计算Q的过程就是在建立L（θ）的下界，即通过jenson不等式得到的下界（E步）；固定Q计算θ则是使得下界极大化（M步），从而不断推高边缘似然L（θ）。从而循序渐进地计算出L（θ）取得极大值时隐变量Z的估计值。

EM算法也可以看作一种“坐标下降法”，首先固定一个值，对另外一个值求极值，不断重复直到收敛。这时候也许大家就有疑问，问什么不直接这两个家伙求偏导用梯度下降呢？这时候就是坐标下降的优势，有些特殊的函数，例如曲线函数z=y^2+x^2+x^2y+xy+…，无法直接求导，这时如果先固定其中的一个变量，再对另一个变量求极值，则变得可行。

6.png

8.3 EM算法流程

版本一：

7.png

版本二：

8.png

EM算法

什么是EM算法

  • 理论角度: EM算法就是解决包含隐变量(Hidden Variable)的参数估计问题(MLE)
  • 工程角度: EM算法就是先用有标签的样本训练个分类器，再给未知标签的样本贴标签，然后再拿全部样本再训练分类器，就这样来回计算

思想

  • EM算法的核心思想非常简单，分为两步：Expection-Step 和 Maximization-Step
    • E-Step 主要通过观察数据和现有模型来估计参数，然后用这个估计的参数值来计算上述对数似然函数的期望值
    • M-Step 是寻找似然函数最大化时对应的参数
  • 由于算法会保证在每次迭代之后似然函数都会增加，所以函数最终会收敛

例子

  1. 公式1是对极大似然函数取对数
    • p(x;θ)代表着固定θ的值，求p(x)的概率
  2. 公式2是对每个样本的每个可能的类别 z 求联合概率分布之和. 如果这个 z 是已知的数，那么使用极大似然法会很容易. 但如果 z 是隐变量(隐含的随机变量)，就需要用 EM 算法来求.
    • 显然，这里似然函数讨论的是离散情况（都是∑符号而不是∫符号), 因此，在p(x;θ)中加上z这个随机变量后，只能将这个随机变量积分掉才能保证加上z以后的式子依然等于p(x;θ)，当然，z是离散的，所以积分掉的意思是“求和”掉
    • （回顾: 对于任何一个连续随机变量x，∫p(x)dx=1；对于任何一个离散随机变量x，∑p(x)=1）

对于每个样本 i，用 $Q_i(z)$ 表示样本 i 隐含变量 z 的某种分布，且 $Q_i(z)$ 满足条件（ $\sum_z^Z Q_i(z)=1, ~~Q_i(z) \geq 0$ ）(概率分布函数的性质)

将上面的式子做以下变化： $\begin{align} L(\theta ) &=\sum^m_{i=1} log \sum_z p(x_i,z;\theta) \\ &=\sum^m_{i=1} log \sum_z^Z Q_i(z) \frac{p(x_i,z;\theta)}{Q_i(z)} \\ &\geq\sum^m_{i=1} \sum_z Q_i(z) log\frac{p(x_i,z;\theta)}{Q_i(z)} \end{align}$

  1. 公式3是求和每个样本的所有可能的类别 z 的联合概率密度函数
  2. 但是公式3直接求导非常困难，所以将其分母都乘以函数 $Q_i(z)$, 转换到公式4
  3. 从公式4到公式5是利用 Jensen 不等式

Jensen 不等式

Jensen 不等式给出：如果 $f$ 是严格的凹函数, X 是随机变量, 则 $f(E[X]) \geq E[f(X)]$, 凸函数反之. 当 $X=E[X]$ (恒成立)时, (即X为常数时), 等式成立(上式取等号).

把第一步中的 log 函数看成一个整体($log(x)$)，由于 $log(x)$ 的二阶导数小于 0，所以原函数为凹函数. 把 $Q_i(z)$ 看成一个概率 $p_z$, 把 $\frac{p(x_i,z;\theta)}{Q_i(z)}$ 看成 z 的函数 $g(z)$. 根据期望公式($E[X] = \sum_i p_i x_i$)有： $\begin{align} E(z) &=p_zg(z) \\ &=\sum_z Q_i(z) [\frac{p(x_i,z;\theta)}{Q_i(z)}]\end{align}$

根据 Jensen 不等式的性质： $\begin{align}f(\sum_z Q_i(z) [\frac{p(x_i,z;\theta)}{Q_i(z)}])=f(E[z]) ~~\geq~~ E[f(z)]=\sum_z Q_i(z) f([\frac{p(x_i,z;\theta)}{Q_i(z)}])\end{align}$

似然函数的下界

通过上面得到了： $L(\theta) \geq J(z,Q)$ (即$f(E[z]) \geq E[f(z)]$)的形式（z 为隐变量），那么就可以通过不断最大化 $J(z,Q)$ 的下界来使得 $L(\theta)$ 不断提高. 下图更加形象： -w766

这张图的意思就是：首先固定 θ ，调整 Q(z) 使下界 J(z,Q) 上升至与 L(θ) 在此点 θ 处相等（绿色曲线到蓝色曲线），然后固定 Q(z) ，调整 θ 使下界 J(z,Q) 达到最大值（ θt 到 θt+1 ），然后再固定 θ ，调整 Q(z) ，一直到收敛到似然函数 L(θ) 的最大值处的 θ*.

也就是说，EM 算法通过引入隐含变量，使用 MLE（极大似然估计）进行迭代求解参数。通常引入隐含变量后会有两个参数，EM 算法首先会固定其中的第一个参数，然后使用 MLE 计算第二个变量值；接着通过固定第二个变量，再使用 MLE 估测第一个变量值，依次迭代，直至收敛到局部最优解

最优化下界

但是什么时候下界 $J(z,Q)$ 与 $L(\theta)$相等, 即什么时候E[f(X)]=f(E[X])？

根据Jensen不等式的等号成立条件，即为了E[f(X)]=f(E[X]), 随机变量X必须恒等于常数, 也就是需要： $\begin{align}\frac{p(x_i,z;\theta)}{Q_i(z)} \equiv c\end{align}$ (c为常数)

做个变换: $\begin{align}\sum_zp(x_i,z;\theta) = \sum_zQ_i(z)~ c \end{align}$

其中$\sum_z Q_i(z) = 1$, 所以可以推导出: $\begin{align}\sum_zp(x_i,z;\theta) = c \end{align}$

因此恒等式的条件满足, Jensen 不等式可以取等号, 最终得到了： $\begin{align} Q_i(z) &= \frac{p(x_i,z;\theta)}{c} \\ &= \frac{p(x_i,z;\theta)}{\sum_z p(x_i,z;\theta)}\\ &= \frac{p(x_i,z;\theta)}{ p(x_i;\theta)} \\ &=p(z | x_i;\theta) \end{align}$

  • 公式9可以变形成公式12 $Q_i(z) = \frac{p(x_i,z;\theta)}{c}$
  • 同时又因为公式11 $c = \sum_zp(x_i,z;\theta) $, 所以最终得到公式13

所以:

  • 推到最后可以发现$Q_i(z)$就是每个样本的隐变量z的后验概率!!!
  • 也就是说只要求出来了每个样本的隐变量的每个取值的后验概率，就能得到这个样本的Qi!!!
  • 就能让Jensen不等式的等号成立!!!
  • 就能让log(∑…)的不可计算成功变成可计算!!!
  • 就能计算我们的目标——似然函数!!!

总结

  • 首先固定一个θ（也就是随便给θ取个初始值），然后计算出隐变量z的取值的后验概率，就能让这个包含隐变量的似然函数变成传统意义上的似然函数, 也就是只考虑参数θ的似然函数（这个过程称为E步）
  • 而最大化传统意义上的似然函数后就得到了当前的最优θ（这个过程称为M步）
  • 而得到了当前的最优θ以后，又可以重新计算出隐变量z的取值的后验概率，即E步，然后又M步，然后又E，又M……
  • 就这样一直重复，一直重复，直到似然函数的值不再变化，此时每个样本的Qi就是每个样本的标签, 而此时的θ就是最终那个最优的θ
  • -w783
  • EM可以看作是J的坐标上升法(Coordinate ascent)，
    • 途中直线为迭代优化路径，因为每次只优化一个变量，所以可以看到它没走一步都是平行与坐标轴的
    • E步固定θ，优化Q，M步固定Q优化θ