机器学习笔记

机器学习笔记—EM 算法

EM 算法所面对的问题跟之前的不一样，要复杂一些。

EM 算法所用的概率模型，既含有观测变量，又含有隐变量。如果概率模型的变量都是观测变量，那么给定数据，可以直接用极大似然估计法，或贝叶斯估计法来估计模型参数，但是，当模型含有隐变量时，情况就复杂一些，相当于一个双层的概率模型，要估计出两层的模型参数，就需要换种方法求解。EM 算法是通过迭代的方法求解。

监督学习是由训练数据 {(x⁽¹⁾,y⁽¹⁾),(x⁽²⁾,y⁽²⁾),...,(x^(m),y^(m))} 学习条件概率分布 P(Y|X) 或决策函数 Y=f(X) 作为模型，用于分类、回归等任务，这时训练数据中的每个样本点由输入和输出组成。但有时训练数据只有输入没有对应的输出 {(x⁽¹⁾,•),(x⁽²⁾,•),...,(x^(m),•)}，从这样的数据学习模型称为非监督学习问题。EM 算法可用于生成模型的非监督学习，生成模型由联合概率分布 P(X,Y) 表示，可以认为非监督学习训练数据是联合概率分布产生的数据。X 为观测数据，Y 为未观测数据。

我们先不管上一篇文章介绍的高斯混合模型，先来看通用的 EM 算法。

假设有训练集 {x⁽¹⁾,x⁽²⁾,...,x^(m)}，我们要寻找模型 p(x,z) 的参数来拟合这些数据，数据的似然估计为：

要直接使用极大似然估计来求 θ 是很难的，因为 z⁽ⁱ⁾ 是隐随机变量，如果 z⁽ⁱ⁾ 不是隐变量，而是可以观察到的，那使用极大似然估计就简单多了。

在这种情况下，EM 算法给出了一种高效的极大似然估计方法，直接最大化 L(θ) 很难，我们的策略是不断地构建 L 的下界（E-step），然后优化下界（M-step）。

对于每个 i，使 Q_i 为 z 上的分布（∑_zQ_i(z)=1，Q_i(z)≥0），那么

最后一步的推导是用了 Jensen 不等式定理和 f(x)=log(x) 是凹函数的事实。

现在，对于一些 Q_i 的分布，上式给出了 L(θ) 的下界，Q_i 有很多种选择，该选择哪个呢？如果已经有 θ 的猜测值，那么自然会想到让下界贴近 θ 值，也就是使不等式在 θ 处等号成立。根据 Jensen 不等式，如果要使 E[f(X)]=f(EX) 成立，应使 X 为常数。即

也就是

因为 ∑_zQ_i(z⁽ⁱ⁾)=1，所以可使

所以，就简单地把 Q_i 设为给定 x⁽ⁱ⁾ 和 θ 后 z⁽ⁱ⁾ 的后验分布即可。

现在，有了 Q 的这个选择，就得到了 L 的下界，这是 E-step。在 M-step，对参数 θ 作极大似然估计。重复执行这两步，就是 EM 算法：

我们怎么知道算法是不是收敛呢？假设 θ^(t) 和 θ^(t+1) 是 EM 算法连续迭代的两个参数，我们现在证明 L(θ^(t))≤L(θ^(t+1))，以证明 EM 单调改进 log 似然。证明的关键就在于 Q_i 的选择，不失一般性，我们从 EM 迭代的 θ^(t) 开始，Q_i^(t)(z⁽ⁱ⁾) :=p(z⁽ⁱ⁾)p(x⁽ⁱ⁾;θ^(t))，我们知道这使得 Jensen 不等式变恒等。

参数 θ^(t+1) 由最大化上式右边所得。

第一个不等式来自一个事实：

第二个不等式是因为 θ^(t+1) 等于

最后一个等式是因为 Q_i 的选择使得 Jenson 不等式在 θ^(t) 处等式成立。

所以 EM 使似然单调收敛，EM 算法一直运行知道收敛，收敛测试就是看两次结果的差是不是小于一个设置的容忍值，如果 EM 改进很慢就说明收敛了。

如果我们定义：

从之前的推导我们知道 L(θ)≥J(Q,θ)，EM 算法可以看作是 J 的坐标上升法，在 E-step，以 Q 为参数最大化，在 M-step，以 θ 为参数最大化。

有了通用 EM 算法的定义，我们再来看下高斯混合模型中 Φ，µ 和 ∑ 的参数拟合。高斯混合模型应用广泛，在许多情况下，EM 算法是学习高斯混合模型的有效方法。简单起见，在 M-step 我们只推导 Φ 和 μ_i 的参数更新，有兴趣的可以推导下 ∑_i。

假设有训练集 {x⁽¹⁾,x⁽²⁾,...,x^(m)}，要把数据建模成一个联合分布 p(x⁽ⁱ⁾,z⁽ⁱ⁾)=p(x⁽ⁱ⁾|z⁽ⁱ⁾)p(z⁽ⁱ⁾)，其中 z⁽ⁱ⁾~Multinomial(Φ)，x⁽ⁱ⁾|z⁽ⁱ⁾=j~N(µ_j,∑_j)，k 表示 z⁽ⁱ⁾ 的可取值个数。数据 x⁽ⁱ⁾ 是这样生成的：先从 {1,...,k} 中随机选择一个 z⁽ⁱ⁾，再从 z⁽ⁱ⁾ 所关联的高斯分布中生成 x⁽ⁱ⁾。这就是高斯混合模型，其中 z⁽ⁱ⁾ 是隐变量，也就是未观测变量，正是这个变量使得问题变得复杂。