EM算法详解

1 摘要

EM算法是最常见的隐变量估计方法，常被用来学习高斯混合模型（Gaussian mixture model，简称GMM）的参数；隐式马尔科夫算法（HMM）、LDA主题模型的变分推断等等。本文就对EM算法的原理做一个详细的总结。

2 EM算法简介

EM算法是一种迭代优化策略，由于它的计算方法中每一次迭代都分两步，其中一个为期望步（E步），另一个为极大步（M步），所以算法被称为EM算法（Expectation-Maximization Algorithm）。EM算法受到缺失思想影响，最初是为了解决数据缺失情况下的参数估计问题。通过迭代，不断求解下界的极大化，来逐步求解对数似然函数极大化。其基本思想是：

1. 首先根据己经给出的观测数据，估计出模型参数的值；（根据 $x$ 估计$\theta$）
2. 然后再依据上一步估计出的参数值估计缺失数据的值;（根据 $\theta$ 估计标签或者类簇指派 $y$ ）
3. 再根据估计出的缺失数据加上之前己经观测到的数据重新再对参数值进行估计；（根据 $y$ + $x$ 估计 $\theta$ ）
4. 然后反复迭代1-3，直至最后收敛，迭代结束。

优点： 简单性和普适性，可看作是一种非梯度优化方法（解决梯度下降等优化方法的缺陷：求和的项数将随着隐变量的数目以指数级上升，会给梯度计算带来麻烦）
缺点： 对初始值敏感，不同的初值可能得到不同的参数估计值；不能保证找到全局最优值。

3 预备知识

3.1 极大似然估计

（1）定义
目的：利用已知样本结果，反推最有可能（最大概率）导致这样结果的参数值θ。

只是一种概率论在统计学的应用，它是参数估计的方法之一。已知某个随机样本 $x$ 满足某种概率分布，但是其中具体的参数不清楚；参数估计就是通过若干次试验，观察其结果，利用结果推出参数的大概值。

最大似然估计是建立在这样的思想上：已知某个参数能使这个样本出现的概率最大，我们当然不会再去选择其他小概率的样本，所以干脆就把这个参数作为估计的真实值。

（2）问题描述
假如我们需要调查学校的男生和女生的身高分布 ，我们抽取100个男生和100个女生，将他们按照性别划分为两组。然后，统计抽样得到100个男生的身高数据和100个女生的身高数据。如果我们知道他们的身高服从正态分布，但是这个分布的均值 $\mu$ 和方差 ${\delta }^2$r455 是不知道，这两个参数就是我们需要估计的。

问题：我们知道样本所服从的概率分布模型和一些样本，我们需要求解该模型的参数。如图1所示。

对数似然方程：
$$l(\theta )=lnL(\theta )=ln\prod _{i=1}^{n}p(x_i;\theta )=\sum _{i=1}^{n}lnp(x_i;\theta )$$

对于n个样本观察数据 $x=(x_1,x_2,...,x_n)$ ，找出样本的模型参数θ, 极大化模型分布的对数似然函数如下：
$$\hat{\theta }=argmax\sum _{i=1}^{n}logp(x_i;\theta )$$

我们已知的条件有两个：样本服从的分布模型、随机抽取的样本。我们需要求解模型的参数。根据已知条件，通过极大似然估计，求出未知参数。总的来说：极大似然估计就是用来估计模型参数的统计学方法。

3.2 Jenson不等式

（1）定义
设f是定义域为实数的函数，如果对所有的实数x，f(x)的二阶导数都大于0，那么f是凸函数，X是随机变量，那么： $E[f(X)]\ge f(E[X])$ 。当且仅当自变量 $X$ 是常量时，该式取等号。其中，E(X)表示X的数学期望。

图2中，实线f表示凸函数，X是随机变量，有0.5的概率是a，有0.5的概率是b。X的期望值就是a和b的中值，从图中可以看到 $E[f(X)]\ge f(E[X])$ 成立。

由于对数函数是凹函数，如果f(x)是凹函数, 有:
$$f(E(x))\ge E(f(x))$$

即
$$log\sum _j{\lambda }_j{y}_j\ge \sum _j{\lambda }_{j}log{y}_j,$$

$$需要满足条件：{\lambda }_j\ge 0,\sum _j{\lambda }_j=1$$

4 EM详解

4.1 问题描述

我们目前有100个男生和100个女生的身高，但是我们不知道这200个数据中哪个是男生的身高，哪个是女生的身高，即抽取得到的每个样本都不知道是从哪个分布中抽取的。这个时候，对于每个样本，就有两个未知量需要估计：
（1）这个身高数据是来自于男生数据集合还是来自于女生？（即先验概率为${\pi }_i$）
（2）男生、女生身高数据集的正态分布的参数分别是多少？（即期望 $\mu$ 和方差 $\delta$）

4.2 EM算法推导流程

对于n个样本观察数据 $x=(x_1,x_2,...x_n)$ ，找出样本的模型参数θ, 极大化模型分布的对数似然函数如下：
$$\hat{\theta }=argmax\sum _{i=1}^n$$