公司网站推广现状,图书网站怎么做,清远市最新消息,中国门户网站排行经典机器学习模型(九)EM算法的推导
1 相关数据基础
1.1 数学期望
1.1.1 数学期望的定义 根据定义#xff0c;我们可以求得掷骰子对应的期望#xff1a; E ( X ) X 1 ∗ p ( X 1 ) X 2 ∗ p ( X 2 ) . . . X 6 ∗ p ( X 6 ) 1 ∗ 1 6 2 ∗ 1 6 1 ∗ 1 6 3 ∗ 1 6 …经典机器学习模型(九)EM算法的推导
1 相关数据基础
1.1 数学期望
1.1.1 数学期望的定义 根据定义我们可以求得掷骰子对应的期望 E ( X ) X 1 ∗ p ( X 1 ) X 2 ∗ p ( X 2 ) . . . X 6 ∗ p ( X 6 ) 1 ∗ 1 6 2 ∗ 1 6 1 ∗ 1 6 3 ∗ 1 6 4 ∗ 1 6 5 ∗ 1 6 6 ∗ 1 6 3.5 E(X)X_1*p(X_1)X_2*p(X_2)...X_6*p(X_6)\\ 1*\frac{1}{6}2*\frac{1}{6}1*\frac{1}{6}3*\frac{1}{6}4*\frac{1}{6}5*\frac{1}{6}6*\frac{1}{6}\\ 3.5 E(X)X1∗p(X1)X2∗p(X2)...X6∗p(X6)1∗612∗611∗613∗614∗615∗616∗613.5
要注意区分平均值和期望。平均值是一个统计量(对观察样本的统计)期望是一种概率论概念是一个数学特征。比如我们进行掷骰子掷了六次点数分别为222444这六次的观察就是我们的样本于是我们可以说平均值为(222444)/63但是千万不能说期望是3。平均值和期望的联系也是大数定理联系起来的。如果说概率是频率随样本趋于无穷的极限 期望就是平均数随样本趋于无穷的极限。可以用加权平均值来理解期望。
1.1.2 函数期望公式 1.1.3 常见分布的期望 具体推导可以参考
数学期望及常见分布的期望计算与推导
1.2 极大似然估计
极大似然估计法的出发点是已知被观测对象的分布但不知道其参数。极大似然法用得到观测值样本最高概率的那些参数的值来估计该分布的参数即产生该样本概率最大的原则。设 f ( y , θ ) f(y,θ) f(y,θ) 是随机变量 Y Y Y 的密度函数其中 θ θ θ是该分布的未知参数若有一随机样本 Y 1 , Y 2 , ⋯ , Y n Y_1,Y_2,⋯,Y_n Y1,Y2,⋯,Yn则 θ θ θ的极大似然估计值是具有产生该观测样本的最高概率的那个 θ θ θ值或者换句话说 θ θ θ的极大似然估计值是使密度函数 f ( y , θ ) f(y,θ) f(y,θ) 达到最大的 θ θ θ值。由于总体有离散型和连续型两种分离散型分布通过分布律来构造似然函数而连续型分布通过概率密度函数来构造似然函数。
求解极大似然估计问题步骤
写出似然函数对似然函数取对数并整理求导数令导数为0得到似然方程解似然方程得到的参数即为所求
1.2.1 离散型随机变量的极大似然原理
若总体为离散型分布其分布律为 P ( Y y ) p ( y , θ ) P(Yy)p(y,θ) P(Yy)p(y,θ)分布律的形式已知。 其中 θ ^ ( θ 1 , θ 2 , ⋯ , θ k ) ′ \hat\theta(θ_1,θ_2,⋯,θ_k)′ θ^(θ1,θ2,⋯,θk)′ 是待估参数向量其中一维随机变量离散型分布主要有 设 Y 1 , Y 2 , ⋯ , Y n Y_1,Y_2,⋯,Y_n Y1,Y2,⋯,Yn 表示总体 Y Y Y 的一个样本它们独立同分布。 y 1 , y 2 , ⋯ , y n y_1,y_2,⋯,y_n y1,y2,⋯,yn 是相应于样本 Y 1 , Y 2 , ⋯ , Y n Y_1,Y_2,⋯,Y_n Y1,Y2,⋯,Yn 的一组样本值容易求得从 Y 1 , Y 2 , ⋯ , Y n Y_1,Y_2,⋯,Y_n Y1,Y2,⋯,Yn 取到观察值$ y_1,y_2,⋯,y_n$ 的概率即事件 { Y 1 y 1 , Y 2 y 2 , ⋯ , Y n y n Y_1y_1,Y_2y_2,⋯,Y_ny_n Y1y1,Y2y2,⋯,Ynyn}发生的概率这个概率为 L ( θ ^ ) L ( y 1 , y 2 , . . . , y n ; θ ^ ) ∏ i 1 n p ( y i , θ ^ ) L(\hat\theta) L(y_1,y_2,...,y_n;\hat\theta)\prod\limits_{i1}^{n}p(y_i,\hat\theta) L(θ^)L(y1,y2,...,yn;θ^)i1∏np(yi,θ^) 这一概率随 θ ^ \hat\theta θ^的取值而变化它是 θ ^ \hat\theta θ^的函数$L(\hat\theta) $称为样本的似然函数。 极大似然估计法就是在 θ ^ \hat\theta θ^取值的可能范围内挑选使似然函数 L ( y 1 , y 2 , ⋯ , y n ; θ ^ ) L(y_1,y_2,⋯,y_n;\hat\theta) L(y1,y2,⋯,yn;θ^) 达到最大的参数值 θ ^ \hat\theta θ^ 一般求解的步骤就是对该似然函数取对数然后求导数令导数为0得到似然方程最后解似然方程。取对数是因为对数似然函 l n L ( θ ^ ) lnL(\hat\theta) lnL(θ^) 可以把乘积形式转为和的形式从而为简化运算提供了方便。
1.2.2 离散型分布的极大似然估计的举例
首先来看1次抛硬币假设参数正面向上的概率为 θ θ θ满足伯努利分布(也称0-1分布)可能的事件有2个正面向上的次数可能为0、1次其正面的条件概率为 p ( x ) θ x ( 1 − θ ) 1 − x , x 为正面向上的次数 p(x)\theta^x(1-\theta)^{1-x},x为正面向上的次数 p(x)θx(1−θ)1−x,x为正面向上的次数 现在我们朝空中扔 N N N次其中有 x x x次显示的是正面有 N − x N-x N−x次显示的是反面那么它所对应的**「正面的条件概率」**就可以写成下式满足二项分布 P ( x ∣ θ ) C N x θ x ( 1 − θ ) N − x , x 为正面向上的次数 P(x|\theta)C_{N}^x\theta^x(1-\theta)^{N-x},x为正面向上的次数 P(x∣θ)CNxθx(1−θ)N−x,x为正面向上的次数
现在我们已经知道硬币正面向上的概率 θ θ θ、一共抛了 N N N次 x x x次显示的是正面那么代入上式很容易就能求出该次事件出现的概率。
假如现在知道硬币一共抛了 N N N次 x x x次显示的是正面但是不知道硬币朝上的概率 θ \theta θ那么该怎么办呢这时咱们就可以让条件概率最大化来找到对应的 θ \theta θ即 a r g max θ P ( x ∣ θ ) arg \max \limits_{\theta} P(x|\theta) argθmaxP(x∣θ) 此时我们可以把它写成似然函数的形式 L ( θ ) L(\theta) L(θ)当然由于原来的条件概率函数都是指数乘积的形式为了计算方便我们接着把似然函数写成 【对数似然函数】。 θ ^ a r g max θ l n ( L ( θ ) ) a r g max θ l n ( θ x ( 1 − θ ) N − x ) ( 忽略常数项 ) a r g max θ ( x l n θ ( N − x ) l n ( 1 − θ ) ) 求最大值我们对 θ 求导并令其为 0 那么 ∂ L ( θ ) ∂ θ ∂ ( x l n θ ( N − x ) l n ( 1 − θ ) ) ∂ θ x θ − N − x 1 − θ 0 可以求得 θ x N \hat\theta arg \max \limits_{\theta} ln(L(\theta)) \\ arg \max \limits_{\theta} ln(\theta^x(1-\theta)^{N-x})(忽略常数项) \\ arg \max \limits_{\theta} (xln\theta (N-x)ln(1-\theta)) \\ 求最大值我们对\theta求导并令其为0那么\\ \frac{\partial L(\theta)}{\partial\theta}\frac{\partial (xln\theta (N-x)ln(1-\theta))}{\partial\theta}\frac{x}{\theta}-\frac{N-x}{1-\theta}0 \\ 可以求得\theta\frac{x}{N} θ^argθmaxln(L(θ))argθmaxln(θx(1−θ)N−x)(忽略常数项)argθmax(xlnθ(N−x)ln(1−θ))求最大值我们对θ求导并令其为0那么∂θ∂L(θ)∂θ∂(xlnθ(N−x)ln(1−θ))θx−1−θN−x0可以求得θNx 频率学派相信概率是确定的或者说 θ θ θ是个常量采样数据 x x x则是基于这个参数为 θ θ θ的分布中随机采样的因此通过采样数据可以求得 θ θ θ通过极大似然估计MLE而采样数据越多 θ θ θ越准确。 而贝叶斯学派则认为θ并非是个未知的常量而是个满足某种分布的随机变量而对于这个θ会有一个最初始的信仰即一个先验假设比如抛硬币中θ可以被视为一个均值为0.5的正态分布。 具体可参考概率学派和贝叶斯学派的区别 可以看出极大似然估计可以看成是对应于一组完全数据的情况但是当出现不完全的数据时比如未被观测到或者是缺失的数据时这时用极大似然估计来求解就相当复杂了。
1.2.3 连续型随机变量的极大似然原理
若总体为连续型分布其概率密度函数为 f ( y , θ ^ ) f(y,\hat\theta) f(y,θ^)密度函数的形式已知。
其中 θ ^ ( θ 1 , θ 2 , ⋯ , θ k ) ′ \hat\theta(θ_1,θ_2,⋯,θ_k)′ θ^(θ1,θ2,⋯,θk)′ 是待估参数向量其中一维随机变量连续型分布主要有 解法和离散型分布一致对该似然函数取对数然后求导数令导数为0得到似然方程最后解似然方程。
1.2.4 连续型分布的极大似然估计举例
我们假设样本服从高斯分布 1.3 Jensen不等式 这里简单介绍下结论感兴趣的可以详细了解下该不等式。 如果 f f f是凸函数(如下图)X是随机变量那么有 E [ f ( X ) ] f ( E [ X ] ) E[f(X)]f(E[X]) E[f(X)]f(E[X])也就是函数的期望大于等于期望的函数。 对于凹函数不等号方向反向即 E [ f ( X ) ] f ( E [ X ] ) E[f(X)]f(E[X]) E[f(X)]f(E[X])。 2 EM算法举例
如下图我们抛两枚硬币A和B一共抛了5轮每轮抛10次。
如果知道每次抛的是A还是B那么根据之前讲的极大似然估计就直接可以估计每种硬币的参数 θ A , θ B θ_A,θ_B θA,θB正面朝上的概率。 假如此时我们并不知道每轮抛掷的是A硬币还是B硬币只能知道每组实验的10次结果。这时候我们就需要EM算法了这时每组未知的硬币就是隐变量。 EM算法的核心就是猜数迭代。 对于第一轮抛掷使用硬币 A 的概率是 0.45使用硬币 B 的概率是 0.55。同理其他轮。这一步我们实际上是估计出了 Z 的概率分布这步就是 E-Step。 到隐变量 z z z后(即每轮是A硬币还是B硬币)我们可以去进行M步计算极大似然估计求得更好的θ 3 EM算法的推导
3.1 EM算法流程
我们先看下《统计学习方法》中EM算法的流程然后我们再去进行推导。 3.2 EM算法中E步的推导
对 m m m个样本观察数据 y ( y ( 1 ) , y ( 2 ) , . . . y ( m ) ) y(y^{(1)},y^{(2)},...y^{(m)}) y(y(1),y(2),...y(m))中找出样本的模型参数θ最大化模型分布的对数似然函数如下 θ ^ a r g max θ l o g ( L ( θ ) ) a r g max θ ∑ i 1 m l o g ( P ( y i ∣ θ ) ) a r g max θ l o g ( P ( Y ∣ θ ) ) 它表示参数 θ 的条件下对应的观测变量 Y 的概率对数化 Y 是离散变量时对应的是概率 ; Y 是连续变量对应的是概率密度。 后文以概率为代表解释概率密度类似。 \hat\theta arg \max \limits_{\theta} log(L(\theta)) \\ arg \max \limits_{\theta} \sum\limits_{i1}^m log(P(y^{i}|\theta)) \\ arg \max \limits_{\theta} log(P(Y|\theta)) \\ 它表示参数\theta的条件下对应的观测变量Y的概率对数化 \\ Y是离散变量时对应的是概率;Y是连续变量对应的是概率密度。 \\ 后文以概率为代表解释概率密度类似。\\ θ^argθmaxlog(L(θ))argθmaxi1∑mlog(P(yi∣θ))argθmaxlog(P(Y∣θ))它表示参数θ的条件下对应的观测变量Y的概率对数化Y是离散变量时对应的是概率;Y是连续变量对应的是概率密度。后文以概率为代表解释概率密度类似。
1因为这里包含缺失数据和隐变量无法直接得到对应的概率于是把对应的隐变量 Z Z Z添进来以全概率公式展开。 L ( θ ) l o g ( P ( Y ∣ θ ) ) l o g ∑ Z ( P ( Y , Z ∣ θ ) ) 这里的隐变量 Z 是对样本空间的分割就是在 Z 的所有取值下对应的概率。 L(\theta)log(P(Y|\theta))log\sum\limits_{Z}(P(Y,Z|\theta))\\ 这里的隐变量Z是对样本空间的分割就是在Z的所有取值下对应的概率。 L(θ)log(P(Y∣θ))logZ∑(P(Y,Z∣θ))这里的隐变量Z是对样本空间的分割就是在Z的所有取值下对应的概率。 2接下来我们就要用到极大似然估计的思想了。
我们令每次迭代后的 L ( θ ) L(\theta) L(θ)都比上轮的 L ( θ ( i ) ) L(\theta^{(i)}) L(θ(i))大目的就是为了让更新之后的似然函数更大即 L ( θ ) − L ( θ ( i ) ) l o g ∑ Z ( P ( Y , Z ∣ θ ) ) − l o g ( P ( Y ∣ θ ( i ) ) ) ≥ 0 注意上式中 θ ( i ) 已知 ( 上一轮推测出来的 ) θ 是未知的 L(\theta)-L(\theta^{(i)})log\sum\limits_{Z}(P(Y,Z|\theta))-log(P(Y|\theta^{(i)}))\geq0\\ 注意上式中\theta^{(i)}已知(上一轮推测出来的)\theta是未知的 L(θ)−L(θ(i))logZ∑(P(Y,Z∣θ))−log(P(Y∣θ(i)))≥0注意上式中θ(i)已知(上一轮推测出来的)θ是未知的
等号右侧前面的式子是将所有隐变量考虑在内的全概率密度函数也就是在EM例子中既然不知道每轮是A硬币还是B硬币那就把A和B的概率都分别计算出来。而后面的式子中参数 θ ( i ) \theta^{(i)} θ(i)是根据上轮结果推测出来A硬币/B硬币正面朝上的概率我们认为它是已知的目标就是用它来推测出新的一轮隐变量对应的概率并且找到新一轮的似然函数。
3接着用贝叶斯公式来把前面的式子进行改造通过观测结果 Y Y Y和上一轮的参数 θ ( i ) \theta^{(i)} θ(i)去猜出隐变量 对应的概率 Z Z Z将上式就可以继续写成 L ( θ ) − L ( θ ( i ) ) l o g ∑ Z ( P ( Y , Z ∣ θ ) ) − l o g ( P ( Y ∣ θ ( i ) ) ) l o g ∑ Z [ P ( Z ∣ Y , θ ( i ) ) P ( Y , Z ∣ θ ) P ( Z ∣ Y , θ ( i ) ] − l o g ( P ( Y ∣ θ ( i ) ) ) 分子分母同乘以一个数原式保持不变这样就引入了隐变量 z 的概率分布。 另外对数函数中有一个求和式直接计算是十分复杂的。 L(\theta)-L(\theta^{(i)})log\sum\limits_{Z}(P(Y,Z|\theta))-log(P(Y|\theta^{(i)}))\\ log\sum\limits_{Z}[P(Z|Y,\theta^{(i)})\frac{P(Y,Z|\theta)}{P(Z|Y,\theta^{(i)}}]-log(P(Y|\theta^{(i)})) \\ 分子分母同乘以一个数原式保持不变这样就引入了隐变量z的概率分布。 \\另外对数函数中有一个求和式直接计算是十分复杂的。 L(θ)−L(θ(i))logZ∑(P(Y,Z∣θ))−log(P(Y∣θ(i)))logZ∑[P(Z∣Y,θ(i))P(Z∣Y,θ(i)P(Y,Z∣θ)]−log(P(Y∣θ(i)))分子分母同乘以一个数原式保持不变这样就引入了隐变量z的概率分布。另外对数函数中有一个求和式直接计算是十分复杂的。
4此时我们需要借助Jensen不等式了。
我们已经知道期望 E ( X ) ∑ x p ( x ) E(X)\sum xp(x) E(X)∑xp(x)函数期望则为 E ( f ( x ) ) ∑ f ( x ) p ( x ) E(f(x))\sum f(x)p(x) E(f(x))∑f(x)p(x) ∑ Z P ( Z ∣ Y , θ ( i ) ) 1 \sum\limits_{Z}P(Z|Y,\theta^{(i)})1 Z∑P(Z∣Y,θ(i))1这是因变量 z z z的概率分布相当于上式的 p ( x ) p(x) p(x)。
我们 P ( Y , Z ∣ θ ) P ( Z ∣ Y , θ ( i ) ) \frac{P(Y,Z|\theta)}{P(Z|Y,\theta^{(i)})} P(Z∣Y,θ(i))P(Y,Z∣θ)把看作一个整体相当于上式中的 f ( x ) f(x) f(x)因此 ∑ Z [ P ( Z ∣ Y , θ ( i ) ) P ( Y , Z ∣ θ ) P ( Z ∣ Y , θ ( i ) ) ] \sum\limits_{Z}[P(Z|Y,\theta^{(i)})\frac{P(Y,Z|\theta)}{P(Z|Y,\theta^{(i)})}] Z∑[P(Z∣Y,θ(i))P(Z∣Y,θ(i))P(Y,Z∣θ)]可以看作一个期望。
根据Jensen不等式对于凸函数函数的期望大于等于期望的函数凹函数相反 l o g ∑ Z [ P ( Z ∣ Y , θ ( i ) ) P ( Y , Z ∣ θ ) P ( Z ∣ Y , θ ( i ) ] log\sum\limits_{Z}[P(Z|Y,\theta^{(i)})\frac{P(Y,Z|\theta)}{P(Z|Y,\theta^{(i)}}] logZ∑[P(Z∣Y,θ(i))P(Z∣Y,θ(i)P(Y,Z∣θ)]就是期望的函数此函数为log而log属于凹函数取相反结论因此函数的期望小于等于期望的函数。
我们可以得到下式 L ( θ ) − L ( θ ( i ) ) l o g ∑ Z ( P ( Y , Z ∣ θ ) ) − l o g ( P ( Y ∣ θ ( i ) ) ) l o g ∑ Z [ P ( Z ∣ Y , θ ( i ) ) P ( Y , Z ∣ θ ) P ( Z ∣ Y , θ ( i ) ) ] − l o g ( P ( Y ∣ θ ( i ) ) ) ≥ ∑ Z P ( Z ∣ Y , θ ( i ) ) l o g P ( Y , Z ∣ θ ) P ( Z ∣ Y , θ ( i ) ) − l o g ( P ( Y ∣ θ ( i ) ) ) 由于 ∑ Z P ( Z ∣ Y , θ ( i ) ) 1 因此在 l o g ( P ( Y ∣ θ ( i ) ) ) 中可以乘 ∑ Z P ( Z ∣ Y , θ ( i ) ) ∑ Z P ( Z ∣ Y , θ ( i ) ) l o g P ( Y , Z ∣ θ ) P ( Z ∣ Y , θ ( i ) ) − ∑ Z P ( Z ∣ Y , θ ( i ) ) l o g ( P ( Y ∣ θ ( i ) ) ) ∑ Z P ( Z ∣ Y , θ ( i ) ) l o g P ( Y , Z ∣ θ ) P ( Z ∣ Y , θ ( i ) ) ( P ( Y ∣ θ ( i ) ) ) 接着对分母的式子进行简化根据乘法公式 P ( Z ∣ Y , θ ( i ) ) P ( Y ∣ θ ( i ) ) P ( Y , Z ∣ θ ( i ) ) 它可以继续写成 ∑ Z P ( Z ∣ Y , θ ( i ) ) l o g P ( Y , Z ∣ θ ) P ( Y , Z ∣ θ ( i ) ) ≥ 0 L(\theta)-L(\theta^{(i)})log\sum\limits_{Z}(P(Y,Z|\theta))-log(P(Y|\theta^{(i)}))\\ log\sum\limits_{Z}[P(Z|Y,\theta^{(i)})\frac{P(Y,Z|\theta)}{P(Z|Y,\theta^{(i)})}]-log(P(Y|\theta^{(i)})) \\ \geq \sum\limits_{Z}P(Z|Y,\theta^{(i)})log\frac{P(Y,Z|\theta)}{P(Z|Y,\theta^{(i)})}-log(P(Y|\theta^{(i)}))\\ 由于\sum\limits_{Z}P(Z|Y,\theta^{(i)})1因此在log(P(Y|\theta^{(i)}))中可以乘\sum\limits_{Z}P(Z|Y,\theta^{(i)})\\ \sum\limits_{Z}P(Z|Y,\theta^{(i)})log\frac{P(Y,Z|\theta)}{P(Z|Y,\theta^{(i)})}-\sum\limits_{Z}P(Z|Y,\theta^{(i)})log(P(Y|\theta^{(i)}))\\ \sum\limits_{Z}P(Z|Y,\theta^{(i)})log\frac{P(Y,Z|\theta)}{P(Z|Y,\theta^{(i)})(P(Y|\theta^{(i)}))}\\ 接着对分母的式子进行简化根据乘法公式P(Z|Y,\theta^{(i)})P(Y|\theta^{(i)})P(Y,Z|\theta^{(i)})它可以继续写成\\ \sum\limits_{Z}P(Z|Y,\theta^{(i)})log\frac{P(Y,Z|\theta)}{P(Y,Z|\theta^{(i)})}\\ \geq0 L(θ)−L(θ(i))logZ∑(P(Y,Z∣θ))−log(P(Y∣θ(i)))logZ∑[P(Z∣Y,θ(i))P(Z∣Y,θ(i))P(Y,Z∣θ)]−log(P(Y∣θ(i)))≥Z∑P(Z∣Y,θ(i))logP(Z∣Y,θ(i))P(Y,Z∣θ)−log(P(Y∣θ(i)))由于Z∑P(Z∣Y,θ(i))1因此在log(P(Y∣θ(i)))中可以乘Z∑P(Z∣Y,θ(i))Z∑P(Z∣Y,θ(i))logP(Z∣Y,θ(i))P(Y,Z∣θ)−Z∑P(Z∣Y,θ(i))log(P(Y∣θ(i)))Z∑P(Z∣Y,θ(i))logP(Z∣Y,θ(i))(P(Y∣θ(i)))P(Y,Z∣θ)接着对分母的式子进行简化根据乘法公式P(Z∣Y,θ(i))P(Y∣θ(i))P(Y,Z∣θ(i))它可以继续写成Z∑P(Z∣Y,θ(i))logP(Y,Z∣θ(i))P(Y,Z∣θ)≥0 5)可以看出对数中的分子是在未知参数 θ \theta θ下的联合概率而分母是在已知参数 θ ( i ) \theta^{(i)} θ(i)的联合概率都是完全概率我们的目的是为了让每轮迭代后的概率比上轮的大自然写成 ∑ Z P ( Z ∣ Y , θ ( i ) ) l o g P ( Y , Z ∣ θ ) P ( Y , Z ∣ θ ( i ) ) ≥ 0 \sum\limits_{Z}P(Z|Y,\theta^{(i)})log\frac{P(Y,Z|\theta)}{P(Y,Z|\theta^{(i)})}\geq0 Z∑P(Z∣Y,θ(i))logP(Y,Z∣θ(i))P(Y,Z∣θ)≥0 到这一步我们的似然函数基本上就敲定了。
我们来验证下令似然函数最大就意味着令每轮迭代后的隐变量概率都比上轮大。
很简单只要对数部分大于零不等式自然成立也就是对数里面的部分大于等于1继续写成 P ( Y , Z ∣ θ ) P ( Y , Z ∣ θ ( i ) ) ≥ 1 \frac{P(Y,Z|\theta)}{P(Y,Z|\theta^{(i)})}\geq1 P(Y,Z∣θ(i))P(Y,Z∣θ)≥1 验证了每轮迭代的概率都比上轮大等同于令似然函数越来越大。
6)接着我们的目标就是要求出对应似然函数下的缺失变量 θ \theta θ的概率值。 我们已经知道 L ( θ ) − L ( θ ( i ) ) ≥ ∑ Z P ( Z ∣ Y , θ ( i ) ) l o g P ( Y , Z ∣ θ ) P ( Y , Z ∣ θ ( i ) ) 即 L ( θ ) ≥ L ( θ ( i ) ) ∑ Z P ( Z ∣ Y , θ ( i ) ) l o g P ( Y , Z ∣ θ ) P ( Y , Z ∣ θ ( i ) ) 我们令 L ( θ ) 的下界 B ( θ , θ ( i ) ) L ( θ ( i ) ) ∑ Z P ( Z ∣ Y , θ ( i ) ) l o g P ( Y , Z ∣ θ ) P ( Y , Z ∣ θ ( i ) ) 我们极大化似然函数 L ( θ ) 等同于最大化下界 B ( θ , θ ( i ) ) 而 L ( θ ( i ) ) 为常数就等同于最大化 ∑ Z P ( Z ∣ Y , θ ( i ) ) l o g P ( Y , Z ∣ θ ) P ( Y , Z ∣ θ ( i ) ) 我们已经知道L(\theta)-L(\theta^{(i)})\geq\sum\limits_{Z}P(Z|Y,\theta^{(i)})log\frac{P(Y,Z|\theta)}{P(Y,Z|\theta^{(i)})} \\ 即L(\theta) \geq L(\theta^{(i)}) \sum\limits_{Z}P(Z|Y,\theta^{(i)})log\frac{P(Y,Z|\theta)}{P(Y,Z|\theta^{(i)})}\\ 我们令L(\theta)的下界B(\theta,\theta^{(i)})L(\theta^{(i)}) \sum\limits_{Z}P(Z|Y,\theta^{(i)})log\frac{P(Y,Z|\theta)}{P(Y,Z|\theta^{(i)})} \\ 我们极大化似然函数L(\theta)等同于最大化下界B(\theta,\theta^{(i)}) \\ 而L(\theta^{(i)})为常数就等同于最大化\sum\limits_{Z}P(Z|Y,\theta^{(i)})log\frac{P(Y,Z|\theta)}{P(Y,Z|\theta^{(i)})} 我们已经知道L(θ)−L(θ(i))≥Z∑P(Z∣Y,θ(i))logP(Y,Z∣θ(i))P(Y,Z∣θ)即L(θ)≥L(θ(i))Z∑P(Z∣Y,θ(i))logP(Y,Z∣θ(i))P(Y,Z∣θ)我们令L(θ)的下界B(θ,θ(i))L(θ(i))Z∑P(Z∣Y,θ(i))logP(Y,Z∣θ(i))P(Y,Z∣θ)我们极大化似然函数L(θ)等同于最大化下界B(θ,θ(i))而L(θ(i))为常数就等同于最大化Z∑P(Z∣Y,θ(i))logP(Y,Z∣θ(i))P(Y,Z∣θ) 我们将式子拆开 ∑ Z P ( Z ∣ Y , θ ( i ) ) l o g P ( Y , Z ∣ θ ) P ( Y , Z ∣ θ ( i ) ) ∑ Z P ( Z ∣ Y , θ ( i ) ) l o g P ( Y , Z ∣ θ ) − ∑ Z P ( Z ∣ Y , θ ( i ) ) l o g P ( Y , Z ∣ θ ( i ) ) \sum\limits_{Z}P(Z|Y,\theta^{(i)})log\frac{P(Y,Z|\theta)}{P(Y,Z|\theta^{(i)})}\\ \sum\limits_{Z}P(Z|Y,\theta^{(i)})log{P(Y,Z|\theta)}-\sum\limits_{Z}P(Z|Y,\theta^{(i)})log{P(Y,Z|\theta^{(i)})} Z∑P(Z∣Y,θ(i))logP(Y,Z∣θ(i))P(Y,Z∣θ)Z∑P(Z∣Y,θ(i))logP(Y,Z∣θ)−Z∑P(Z∣Y,θ(i))logP(Y,Z∣θ(i)) 在减号后面的部分还是个常数不好含未知参数 θ \theta θ。因此我们只需要对前面的部分求出当它最大时对应的 θ \theta θ 。 即 Q ( θ , θ ( i ) ) ∑ Z P ( Z ∣ Y , θ ( i ) ) l o g P ( Y , Z ∣ θ ) ∑ Z P ( Z ∣ Y , θ ( i ) ) 1 是一个条件概率分布因此可以化简为期望形式即 E Z ∣ Y , θ ( i ) l o g P ( Y , Z ∣ θ ) 即Q(\theta,\theta^{(i)})\sum\limits_{Z}P(Z|Y,\theta^{(i)})log{P(Y,Z|\theta)}\\ \sum\limits_{Z}P(Z|Y,\theta^{(i)})1是一个条件概率分布因此可以化简为期望形式即\\ E_{Z|Y,\theta^{(i)}}log{P(Y,Z|\theta)} 即Q(θ,θ(i))Z∑P(Z∣Y,θ(i))logP(Y,Z∣θ)Z∑P(Z∣Y,θ(i))1是一个条件概率分布因此可以化简为期望形式即EZ∣Y,θ(i)logP(Y,Z∣θ) 这就是EM算法的E步的推导。
通过EM算法的E步我们得到了Q函数 Q ( θ , θ ( i ) ) ∑ Z P ( Z ∣ Y , θ ( i ) ) l o g P ( Y , Z ∣ θ ) E Z ∣ Y , θ ( i ) l o g P ( Y , Z ∣ θ ) Q(\theta,\theta^{(i)})\sum\limits_{Z}P(Z|Y,\theta^{(i)})log{P(Y,Z|\theta)}\\ E_{Z|Y,\theta^{(i)}}log{P(Y,Z|\theta)} Q(θ,θ(i))Z∑P(Z∣Y,θ(i))logP(Y,Z∣θ)EZ∣Y,θ(i)logP(Y,Z∣θ) 接下来我们只需要求使 Q ( θ , θ ( i ) ) Q(\theta,\theta^{(i)}) Q(θ,θ(i))极大化的 θ \theta θ确定第 i 1 i1 i1次的迭代参数的估计值 θ ( i 1 ) \theta^{(i1)} θ(i1)即M步。
3.3 EM算法的图形解释 在推导 E M 算法过程中我们知道 L ( θ ) ≥ L ( θ ( i ) ) ∑ Z P ( Z ∣ Y , θ ( i ) ) l o g P ( Y , Z ∣ θ ) P ( Y , Z ∣ θ ( i ) ) 我们令下界 B ( θ , θ ( i ) ) L ( θ ( i ) ) ∑ Z P ( Z ∣ Y , θ ( i ) ) l o g P ( Y , Z ∣ θ ) P ( Y , Z ∣ θ ( i ) ) 在推导EM算法过程中我们知道L(\theta) \geq L(\theta^{(i)}) \sum\limits_{Z}P(Z|Y,\theta^{(i)})log\frac{P(Y,Z|\theta)}{P(Y,Z|\theta^{(i)})}\\ 我们令下界B(\theta,\theta^{(i)})L(\theta^{(i)}) \sum\limits_{Z}P(Z|Y,\theta^{(i)})log\frac{P(Y,Z|\theta)}{P(Y,Z|\theta^{(i)})} 在推导EM算法过程中我们知道L(θ)≥L(θ(i))Z∑P(Z∣Y,θ(i))logP(Y,Z∣θ(i))P(Y,Z∣θ)我们令下界B(θ,θ(i))L(θ(i))Z∑P(Z∣Y,θ(i))logP(Y,Z∣θ(i))P(Y,Z∣θ) 我们想让似然函数越来越大等同于是让下界 B ( θ , θ ( i ) ) B(\theta,\theta^{(i)}) B(θ,θ(i))越来越大。 注意在每轮的迭代中都它所对应的下界函数 B ( θ , θ ( i ) ) B(\theta,\theta^{(i)}) B(θ,θ(i))都是在不断更新的。 我们说明一下下图中 L ( θ ) L(\theta) L(θ)和 B ( θ , θ ( i ) ) B(\theta,\theta^{(i)}) B(θ,θ(i))在 θ ( i ) \theta^{(i)} θ(i)处相等这句话。 L ( θ ) ≥ L ( θ ( i ) ) ∑ Z P ( Z ∣ Y , θ ( i ) ) l o g P ( Y , Z ∣ θ ) P ( Y , Z ∣ θ ( i ) ) 当 θ θ ( i ) 时 P ( Y , Z ∣ θ ( i ) ) P ( Y , Z ∣ θ ( i ) ) 1 , 那么 l o g P ( Y , Z ∣ θ ( i ) ) P ( Y , Z ∣ θ ( i ) ) 0 因此 L ( θ ( i ) ) ≥ L ( θ ( i ) ) 0 , 即 L ( θ ) 和 B ( θ , θ ( i ) ) 在 θ ( i ) 处相等 L(\theta) \geq L(\theta^{(i)}) \sum\limits_{Z}P(Z|Y,\theta^{(i)})log\frac{P(Y,Z|\theta)}{P(Y,Z|\theta^{(i)})}\\ 当\theta\theta^{(i)}时\frac{P(Y,Z|\theta^{(i)})}{P(Y,Z|\theta^{(i)})}1,那么log\frac{P(Y,Z|\theta^{(i)})}{P(Y,Z|\theta^{(i)})}0\\ 因此L(\theta^{(i)}) \geq L(\theta^{(i)}) 0,即L(\theta)和B(\theta,\theta^{(i)})在\theta^{(i)}处相等 L(θ)≥L(θ(i))Z∑P(Z∣Y,θ(i))logP(Y,Z∣θ(i))P(Y,Z∣θ)当θθ(i)时P(Y,Z∣θ(i))P(Y,Z∣θ(i))1,那么logP(Y,Z∣θ(i))P(Y,Z∣θ(i))0因此L(θ(i))≥L(θ(i))0,即L(θ)和B(θ,θ(i))在θ(i)处相等
现在我们再看3.1EM算法的流程就应该有更深刻的理解了。 有关EM算法收敛的证明可以参考
学会EM算法
接下来会介绍下《统计学习方法》中EM算法的三硬币模型例子以及EM算法在高斯混合模型中的应用。
