EM-algorithm

EM算法

1.EM算法的引入

  EM算法是一种迭代算法，用于还有隐变量的概率模型参数的极大似然估计，或极大后验概率。EM算法可以分为两步,E步：求期望；M步：求极大。

1.1 EM算法的推导

  面对一个含有隐变量的概率模型，目标是极大化观测数据Y关于参数θ的对数似然函数，即极大化

                  L(θ)=logP(Y|θ)=log$\sum_{Z}$P(Y,Z|θ)=log($\sum_{Z}$P(Y|Z,θ)P(Z|θ))         (1)
  EM算法是通过迭代逐步近似极大化L(θ)的。假设在第i次迭代后θ的估计值为$θ^{(i)}$,我们希望θ能够增加，为此我们考虑L(θ)和L($θ^{(i)}$)的差：
                  L(θ) - L($θ^{(i)}$)=log($\sum_{Z}$P(Y|Z,θ)P(Z|θ)) - logP(Y|$θ^{(i)}$)        (2)
  这里L(θ)用是(1)中的第4个式子，L($θ^{(i)}$)用的是(1)中第3个式子

  利用Jensen不等式得到下界：log$\sum_{i}$$a_{i}$f(x) ≥ $\sum_{i}$$a_{i}$logf(x) ($a_{i}$$\geq$ 0 且 $\sum_{i}$$a_{i}$=1)
  由于P ( Z|Y,$θ^{(i)}$ )=1,所以可以使用Jensen不等式

                  L(θ) - L($θ^{(i)}$) $\geq$ $\sum_{Z}$P(Z|Y,$θ^{(i)}$) log [(P(Y|Z,θ)P(Z|θ))/P(Z|Y,$θ^{(i)}$)] - log[P(Y|$θ^{(i)}$)$\sum_{Z}$P(Z|Y,$θ^{(i)}$)]
                                      $\geq$ $\sum_{Z}$P(Z|Y,$θ^{(i)}$) log [(P(Y|Z,θ)P(Z|θ))/P(Z|Y,$θ^{(i)}$)] - $\sum_{Z}$P(Z|Y,$θ^{(i)}$)]log[P(Y|$θ^{(i)}$)
                                      =  $\sum_{Z}$P(Z|Y,$θ^{(i)}$)log [(P(Y|Z,θ)P(Z|θ))/(P(Z|Y,$θ^{(i)}$)P(Y|$θ^{(i)}$))]
                                      =  $\sum_{Z}$P(Z|Y,$θ^{(i)}$)log [(P(Y|Z,θ)P(Z|θ))/P(Z,Y|$θ^{(i)}$)]
  移项可得
                               L(θ) $\geq$ L($θ^{(i)}$) + $\sum_{Z}$P(Z|Y,$θ^{(i)}$)log [(P(Y|Z,θ)P(Z|θ))/P(Z,Y|$θ^{(i)}$)]

  令B(θ,$θ^{(i)}$)=L($θ^{(i)}$) + $\sum_{Z}$P(Z|Y,$θ^{(i)}$)log [(P(Y|Z,θ)P(Z|θ))/P(Z,Y|$θ^{(i)}$)]
  如果想使L(θ)极大，那么就应该使L(θ)的下界B(θ,$θ^{(i)}$)极大
$θ^{(i+1)}$=arg $max_{θ}$ B(θ,$θ^{(i)}$)
          = arg $max_{θ}$ L($θ^{(i)}$) + $\sum_{Z}$P(Z|Y,$θ^{(i)}$)log [(P(Y|Z,θ)P(Z|θ))/P(Z,Y|$θ^{(i)}$)]
  去掉对θ而言相当于常数的项，也就是直接去掉不包含θ的项，因为求导这部分为0
          = arg $max_{θ}$ $\sum_{Z}$P(Z|Y,$θ^{(i)}$) log[(P(Y|Z,θ)P(Z|θ))]

∴Q(θ,$θ^{(i)}$) = $\sum_{Z}$P(Z|Y,$θ^{(i)}$) log[P(Y|Z,θ)P(Z|θ)]
                 = $\sum_{Z}$P(Z|Y,$θ^{(i)}$) logP(Y,Z|θ)
                 = $E_{Z}$[P(Z|Y,$θ^{(i)}$) logP(Y,Z|θ)]

1.2 EM算法

  输入: 观测变量数据Y,隐变量数据Z,联合分布P(Y,Z|θ)，条件分布P(Z|Y,θ)；
  输出: 模型参数θ

  (1) 选择参数的初始值$θ^{(0)}$
  初始值是任意选取的，但会对结果有影响
  (2) E步：记$θ^{(i)}$为第i次迭代参数θ的估计值，在第i+1次迭代的E步，计算：
                 Q(θ,$θ^{(i)}$) = $E_{Z}$[P(Z|Y,$θ^{(i)}$) logP(Y,Z|θ)]
  (3)M步：求使Q(θ,$θ^{(i)}$)极大化的θ，确定第i+1次迭代的参数估计值$θ^{(i+1)}$
                 $θ^{(i+1)}$=arg $max_{θ}$ B(θ,$θ^{(i)}$)
  (4)重复(2)和(3),直至收敛
  收敛条件：||$θ^{(i+1)}$-$θ^{(i)}$||< $\epsilon_{1}$ 或 ||Q$(θ^{(i+1)}$,$θ^{(i)}$) - Q($θ^{(i)}$,$θ^{(i)}$)||< $\epsilon_{2}$

1.3 EM算法在无监督学习中的应用

  监督学习是由训练数据 {($x_{1}$,$y_{1}$),($x_{2}$,$y_{2}$),··($x_{n}$,$y_{n}$)}学习条件概率分布P(Y|X)或决策函数Y = f(X)作为模型，用于分类、回归、标注等任务。这时训练数据中的每个样本点由输入和输出对组成。
  有时训练数据只有输入没有对应的输出{($x_{1}$,·),($x_{2}$,·)，··,($x_{n}$,·)}，从这样的数据学习模型称为无监督学习问题。EM算法可以用于生成模型的无监督学习。生成模型由联合概率分布P(X,Y) 表示，可以认为无监督学习训练数据是联合概率分布产生的数据。X为观测数据，Y为未观测数据。

2.EM算法的收敛性

  由于P(Y|θ)为观测数据的似然函数,并且在0和1之间，所以证明收敛，只需要证明P(Y|θ)单调递增即可。
  证明略。