统计学习方法读书笔记第九章:EM算法及其推广
统计学习方法读书笔记第九章:EM算法及其推广
统计学习方法读书笔记第九章:EM算法及其推广
EM算法是一种迭代算法,用于含有隐变量的概率模型参数的极大似然估计,或极大后验概率估计。EM算法的每次迭代由两步组成:E步,求期望(expectation);M步,求极大(maximization)。所以这一算法称为期望极大算法,简称EM算法。
EM算法的引入
概率模型有时既含有观测变量,又含有隐变量或潜在变量。如果概率模型的变量都是观测变量,那么给定数据,可以直接用极大似然估计法,或贝叶斯估计法估计模型参数。但是,当模型含有隐变量时,就不能简单地使用这些估计方法。EM算法就是含有隐变量的概率模型参数的极大似然估计法,或极大后验概率估计法。
- EM算法
将观测数据表示为,未观测数据表示为,则观测数据的似然函数为
考虑求模型参数的极大似然估计,即
这个问题没有解析解,只有通过迭代的方法求解。EM算法就是可以用于求解这个问题的一种迭代算法。
一般地,用表示观测随机变量的数据,表示隐随机变量的数据。和连在一起称为完全数据,观测数据又称为不完全数据。假设给定观测数据,其概率分布是,其中是需要估计的模型参数,那么不完全数据的似然函数是,对数似然函数;假设和的联合概率分布是,那么完全数据的对数似然函数是。
EM算法通过迭代求的极大似然估计。每次迭代包含两步:E步,求期望;M步,求极大化。下面来介绍EM算法。
EM算法
输入:观测变量数据,隐变量数据,联合分布,条件分布;
输出:模型参数。
(1) 选择参数的初值,开始迭代;
(2) E步:记为第次迭代参数的估计值,在第次迭代的E步,计算
这里,实在给定观测数据和当前的参数估计下隐变量数据的条件概率分布;
(3) M步:求使极大化的,确定第次迭代的参数的估计值
(4) 重复第(2)步和第(3)步,直到收敛。
第(2)步中的函数是EM算法的核心,称为函数。
定义1(Q函数) 完全数据的对数似然函数关于在给定观测数据和当前参数下对未观测数据的条件概率分布的期望称为函数,即
下面关于EM算法作几点说明:
步骤(1) 参数的初值可以任意选择,但需注意EM算法对初值是敏感的。
步骤(2) E步求。函数式中是未观测数据,是观测数据。注意,的第1个变元表示要极大化的参数,第2个变元表示参数的当前估计值。每次迭代实际在求函数及其极大。
步骤(3) M步求Q(\theta,\theta^{(i)})的极大化,得到,完成一次迭代。后面将证明每次迭代使似然函数增大或达到局部极值。
步骤(4) 给出停止迭代的条件,一般是对较小的正数,,若满足
则停止迭代。 - EM算法的导出
上面叙述了EM算法。为什么EM算法能近似实现对观测数据的极大似然估计呢?下面通过近似求解观测数据的对数似然函数的极大化问题来导出EM算法,由此可以清楚地看出EM算法的作用。
我们面对一个含有隐含量的概率模型,目标是极大化观测数据(不完全数据)关于参数的对数似然函数,即极大化
注意到这一极大化的主要困难是上式中有未观测数据并有包含和(或积分)的对数。
事实上,EM算法是通过迭代逐步近似极大化的。假设在第次迭代后的估计值是。我们希望新估计值能使增加,即,并逐步达到极大值。为此,考虑两者的差:
利用Jensen不等式得到其下界:
令
则
即函数是的一个下界,且由上式可知,
因此,任何可以使增大的,也可以使增大。为了使有尽可能大的增长,选择使达到极大,即
现在求的表达式。省去对的极大化而言是常数的项,则有
上式等价于EM算法的一次迭代,即求函数及其极大化。算法是通过不断求解下界的极大化逼近求解对数似然函数极大化的算法。
下图给出EM算法的直观解释。途中上方曲线为,下方曲线为。为对数似然函数的下界。同时,两个函数在点处相等。则EM算法找到下一个点使函数极大化,也使函数极大化。这时由于,函数的增加,保证对数似然函数在每次迭代中也是增加的。EM算法在点重新计算函数值,进行下一次迭代。在这个过程中,对数似然函数不断增大。从图可以推断出EM算法不能保证找到全局最优解。 - EM算法在非监督学习中的应用
监督学习是由训练数据学习条件概率分布或决策函数作为模型,用于分类、回归、标注等任务。这时训练数据中的每个样本点由输入和输出对组成。
有时训练数据只有输入没有对应的输出,从这样的数据学习模型称为非监督学习问题。EM算法可以用于生成模型的非监督学习。生成模型由联合概率分布表示,可以认为非监督学习训练数据是联合概率分布产生的数据。为观测数据,为未观测数据。
EM算法的收敛性
EM算法提供一种近似计算含有隐变量概率模型的极大似然估计的方法。EM算法的最大优点是简单性和普适性。我们很自然地要问:EM算法得到的估计序列是否收敛?如果收敛,是否收敛到全局最大值或局部最大值?下面给出关于EM算法收敛性的两个定理。
-
定理1 设为观测数据的似然函数,为EM算法得到的参数估计序列,为对应的似然函数序列,则是单调递增的,即
证明 由于
取对数有
由Q函数
令
于是对数似然函数可以写成
在上式中分别取为和并相减,有
为证式(12),只需证式(15)右端是非负的。式(15)右端的第1项,由于使达到极大,所以有
其第2项,由式(13)可得:
这里的不等号由Jensen不等式得到。
由式(16)和式(17)即知式(15)右端是非负的。
定理2 设为观测数据的对数似然函数,为EM算法得到的参数估计序列,为对应的对数似然函数序列。
(1) 如果有上界,则收敛到某一值;
(2) 在函数与满足一定条件下,由EM算法得到的参数估计序列的收敛值是的稳定点。
证明 (1)由的单调性及的有界性立即得到。
(2) 证明从略。
定理2关于函数与的条件在大多数情况下都是满足的。EM算法的收敛性包含关于对数似然函数序列的收敛性和关于参数估计序列的收敛性两层意思,前者并不蕴含后者。此外,定理只能保证参数估计序列收敛到对数似然函数序列的稳定点,不能保证收敛到极大值点。所以在应用中,初值的选择变得非常重要,常用的办法是选取几个不同的初值进行迭代,然后对得到的各个估计值加以比较,从中选择最好的。
EM算法在高斯混合模型学习中的应用
EM算法的一个重要应用是高斯混合模型的参数估计。高斯混合模型应用广泛,在许多情况下,EM算法是学习高斯混合模型的有效方法。
-
高斯混合模型
定义2(高斯混合模型) 高斯混合模型是指具有如下形式的概率分布模型:
其中,是系数,,;是高斯分布密度,,
称为第个分模型。
一般混合模型可以由任意概率分布密度代替式(19)中的高斯分布密度,我们只介绍最常用的高斯混合模型。 -
高斯混合模型参数估计的EM算法
假设观测数据由高斯混合模型生成,
其中,。我们用EM算法估计高斯混合模型的参数。
-
明确隐变量,写出完全数据的对数似然函数
可以摄像观测数据,是这样产生的:首先依概率选择第个高斯分布模型;然后依第个分模型的概率分布生成观测数据。这时观测数据,是已知的;反映观测数据来自第个分模型的数据是未知的,,以隐变量表示,定义如下:
是0-1随机变量。
有了观测数据及未观测数据,那么完全数据是
于是,可以写出完全数据的似然函数:
式中,,。
那么,完全数据的对数似然函数为
- EM算法的E步:确定Q函数
这里需要计算,记为。
是在当前模型参数下第个观测数据来自第个分模型的概率,称为分模型对观测数据的响应度。
将及代入式(22)即得
- 确定EM算法的M步
迭代的M步是求函数对的极大值,即求新一轮迭代的模型参数:
用,及,,表示的各参数。求,只需将式(23)分别对,求偏导数并令其为0,即可得到;求是在条件下求偏导数并令其为0得到的。结果如下:
重复以上计算,直到对数似然函数值不再有明显的变化为止。
现将估计高斯混合模型参数的EM算法总结如下:
算法2(高斯混合模型参数估计的EM算法)
输入:观测数据,高斯混合模型;
输出:高斯混合模型参数。
(1) 取参数的初始值开始迭代
(2) E步:依据当前模型参数,计算分模型对观测数据的响应度
(3) M步:计算新一轮迭代的模型参数
(4) 重复第(2)步和第(3)步,直到收敛。
EM算法的推广
EM算法还可以解释为F函数的极大-极大算法,基于这个解释有若干变形与推广,如广义期望极大算法。下面予以介绍。
-
F函数的极大-极大算法
首先引进F函数并讨论其性质。
定义3(F函数) 假设隐变量数据的概率分布为,定义分布与参数的函数如下:
称为F函数。式中是分布的熵。
在定义3中,通常假设是的连续函数,因而是和的连续函数。函数还有以下重要性质:
引理1 对于固定的,存在唯一的分布极大化,这时由下式给出:
并且随连续变化。
证明 对于固定的,可以求得使达到极大的分布。为此,引进拉格朗日乘子,拉格朗日函数为
将其对求偏导数:
令偏导数等于0,得出
由此推出与成比例
再从约束条件得式(28)。
由假设是的连续函数,得到是的连续函数。
引理2 若,则
由以上引理,可以得到关于EM算法用F函数的极大-极大算法的解释。
定理3 设为观测数据的对数似然函数,,为EM算法得到的参数估计序列,函数由式(27)定义。若果在和有局部极大值,那么也在有局部极大值。类似地,如果在和达到全局最大值,那么也在达到全局最大值。
证明 由引理1和引理2可知,对任意成立。特别地,对于使达到极大的参数,有
为了证明是的极大点,需要证明不存在接近的点,使。加入存在这样的点,那么应有,这里。但因是随连续变化的,应接近,这与和是的局部极大点的假设矛盾。
类似可以证明关于全局最大值的结论。
定理4 EM算法的一次迭代可由F函数的极大-极大算法实现。
设为第次迭代参数的估计,为第次迭代函数的估计。在第次迭代的两步为
(1) 对固定的,求使极大化;
(2) 对固定的,求使极大化。
证明 (1) 由引理1,对于固定的,
使极大化。此时
由的定义式(5)有
(2) 固定,求使极大化。得到
通过以上两步完成了EM算法的一次迭代。由此可知,由EM算法与F函数的极大-极大算法得到的参数估计序列,是一致的。
这样,就有EM算法的推广。 -
GEM算法
算法3(GEM算法1)
输入:观测数据,F函数;
输出:模型参数。
(1) 初始化参数,开始迭代
(2) 第次迭代,第1步:记为参数的估计值,为函数的估计。求使极大化
(3) 第2步:求使极大化
(4) 重复(2)和(3),直到收敛。
在GEM算法1中,有时求的极大化是很困难的。下面介绍的GEM算法2和GEM算法3并不是直接求使达到极大的,而是找一个使得。
算法4(GEM算法2)
输入:观测数据,Q函数;
输出:模型参数。
(1) 初始化参数,开始迭代
(2) 第次迭代,第1步:记为参数的估计值,计算
(3) 第2步:求使
KaTeX parse error: Expected 'EOF', got '\thata' at position 35: …theta^{(i)})>Q(\̲t̲h̲a̲t̲a̲{(i)},\theta^{(…
(4) 重复(2)和(3),直到收敛。
当参数的维数为时,可采用一种特殊的GEM算法,它将EM算法的M步分解为d次条件极大化,每次只改变参数向量的一个分量,其余分量不改变。
算法5(GEM算法3)
输入:观测数据,Q函数;
输出:模型参数。
(1) 初始化参数,开始迭代
(2) 第次迭代,第1步:记为参数的估计值,计算
(3) 第2步:进行d次条件极大化:
首先,在保持不变的条件下求使达到极大的;
然后,在的条件下求使达到极大的;
如此继续,经过d次条件极大化,得到使得
KaTeX parse error: Expected 'EOF', got '\thata' at position 35: …theta^{(i)})>Q(\̲t̲h̲a̲t̲a̲{(i)},\theta^{(…
(4) 重复(2)和(3),直到收敛。