机器学习 学习笔记（12） EM算法

在实际情况中，往往会遇到未观测变量，未观测变量的学名是隐变量（latent variable）。令X表示已观测变量集，Z表示隐变量集，

\theta

表示模型参数。若欲对

\theta

做极大似然估计，则应最大化对数似然

LL(\theta |X,Z)=ln P(X,Z|\theta )

，由于Z是隐变量，上式无法直接求解，此时可以通过对Z计算期望，来最大化已观测数据的对数“边际似然”。

LL(\theta |X)=ln P(X|\theta )=ln \sum_ZP(X,Z|\theta )

EM期望极大算法就是含有隐变量的概率模型参数的极大似然估计法，或极大后验概率估计法。

EM(Exceptation-Maximization)算法是常用的估计参数隐变量的力气，它是一种迭代式的方法，基本思想是：若参数

\theta

一直，则可跟进训练数据推断出出最优隐变量Z的值（E步），反之，若Z的值已知，则可方便地对参数

\theta

做极大似然估计（M步）。

EM算法的两个步骤是：

• E步（Exceptation）：当以前参数

\theta ^t

推断隐变量分布

P(Z|X,\theta ^t)

，并计算对数似然

LL(\theta |\theta ^t)=E_{Z|X,\theta ^t}LL(\theta |X,Z)

• M步（Maximization）：寻找参数最大化期望似然，即

\theta ^{t+1}=\arg \max \limits_{\theta} Q(\theta|\theta^t)

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

EM算法与初值的选择有关，选择不同的初值可能得到不同的参数估计值。

一般地，用Y表示观测随机变量的数据，Z表示隐随机变量的数据。Y和Z连在一起称为完全数据，观测数据Y又称为不完全数据。假设给定观测数据Y，其概率分布是

P(Y|\Theta )

，其中

\Theta

是需要估计的参数模型，那么不完全数据Y的似然函数是

P(Y|\Theta )

，对数似然函数

L(\Theta )=log P(Y|\Theta )

，假设Y和Z的联合概率分布是

P(Y,Z|\Theta )

，那么完全数据的对数似然函数是

log P(Y,Z|\Theta )

。

EM算法描述如下：

输入：观测变量数据Y，隐变量数据Z，联合分布

P(Y,Z|\Theta )

，条件分布

P(Z|Y,\Theta )

输出：参数模型

\Theta

（1）选择参数的初值

\Theta ^0

，开始迭代

（2）E步：记

\Theta ^i

为第i次迭代参数

\Theta

的估计值，在第i+1次迭代的E步，计算：

Q(\Theta,\Theta^{(i)})=E_Z[logP(Y,Z|\Theta)|Y,\Theta^{(i)}]=\sum_Z logP(Y,Z|\Theta)P(Z|Y,\Theta^{(i)})

这里

P(Z|Y,\Theta^{(i)})

是在给定观测数据Y和当前的参数估计

\Theta^{(i)

下隐变量数据Z的条件概率分布

（3）M步：求使得

Q(\Theta,\Theta^{(i)})

极大化的

\Theta

，确定第i+1次迭代的参数的估计值

\Theta^{i+1}

\Theta^{i+1}=\arg \max \limits_{\theta}Q(\Theta,\Theta^{(i)})

（4）重复（2）和（3）直至收敛。

Q(\Theta,\Theta^{(i)})

是EM算法的核心，称为Q函数

EM算法可以用于生成模型的非监督学习，生成模型由联合概率分布P(X,Y)表示，可以认为非监督学习训练数据是联合概率分布产生的数据，X为观测数据，Y为未观测数据。

EM 算法提供一种近似计算含有隐变量概率模型的极大似然估计的方法，EM算法最大的优点是简单性和普适性。

定理：设

P(Y|\theta )

为观测数据的似然函数，

\theta ^{(i)},i=1,2,...

为EM算法得到的参数估计序列，

P(Y|\theta^{(i)} )

为对应的似然函数序列，则

P(Y|\theta^{(i)} )

是单调递增的，即

P(Y|\theta^{(i+1)} )\geqslant P(Y|\theta^{(i)} )

定理：设

L(\theta )=log P(Y|\theta )

为观测数据的对数似然函数，

\theta ^{(i)},i=1,2,...

为EM算法得到的参数估计序列，

L(\theta ^{(i)})

为对应的对数似然函数序列：

（1）如果

P(Y|\theta )

有上界，则

L(\theta ^{(i)})=log P(Y|\theta^{(i)} )

收敛到某一值

（2）在函数

Q(\theta ,\theta ')

与

L(\theta )

满足一定条件下，由EM算法得到的参数估计序列

\theta ^{(i)}

的收敛值

\theta ^*

是

L(\theta )

的稳定点

高斯混合模型参数估计的EM算法

输入：观测数据

y_1,y_2,...,y_N

，高斯混合模型

输出：高斯混合模型参数

（1）取参数初始值开始迭代

（2）E步依据当前模型参数，计算分模型k对观测数据

y_j

的响应度：

\hat{\gamma }_{jk}=\frac{\alpha _k\varphi (y_j|\theta _k)}{\sum_{k=1}^K\alpha _k\varphi (y_j|\theta _k)},j=1,2,...,N;k=1,2,...,K

（3）M步，计算新一轮迭代的模型：

\hat{\mu}_k=\frac{\sum_{j=1}^N\hat{\gamma }_{jk}y_j}{\sum_{j=1}^N\hat{\gamma }_{jk}},k=1,2,...,K

\hat{\sigma }_k^2=\frac{\sum_{j=1}^N\hat{\gamma }_{jk}(y_j-\mu_k)^2}{\sum_{j=1}^N\hat{\gamma }_{jk}},k=1,2,...,K

\hat{\alpha }_k=\frac{\sum_{j=1}^N\hat{\gamma }_{jk}}{N},k=1,2,...,K

（4）重复（2）和（3）直到收敛

采用EM求解的模型有哪些？蒙特卡罗算法，混合高斯、协同过滤、k-means

参考：

1. 《机器学习》
2. 《统计学习方法》
3. Expectation-Maximum（EM算法）