EM算法

EM算法EM算法简介•EM算法：期望最大化(ExpectationMaximization)算法。是一种迭代算法，是在概率模型中寻找参数极大似然估计的算法，其中概率模型依赖于无法观测的隐含变量。它主要用于从含有隐含变量的数据中计算极大似然估计。是解决存在隐含变量优化问题的有效方法。主要内容一.似然函数与极大似然估计二.Jensen不等式三.数学期望的相关定理四.边际分布列五.EM算法一、似然函数与极大似然估计),(,,);(1Lxxxpn记为的函数，示成样本的联合概率函数表将是来自该总体的样本，取值的参数空间。是可能数组成的参数向量，未知参数或几个未知参是一个，其中，设总体的概率函数为称为样本的似然函数。，)();();();();,()(111LxpxpxpxxLLniinn一、似然函数与极大似然估计)(maxarg},...x{x);()(*n11LxpLnii来极大化似然函数，即优的固定的情况下，寻找最就是在样本点而极大似然估计的目的也要发生变化。的变化，似然函数的值在参数空间的函数。显然随着参数是似然函数一、似然函数与极大似然估计就是我们的估计值。极大值对应的极大化，的似然函数，只需要使想要求**)(L.0)(ln);(ln))(ln()(ln)(*1LddxpLLLnii也可从下述方程解得：的极大似然估计因此所以对数化似然函数处取到极值，在同一与因二、Jensen不等式。即，不等号方向相反。不等式应用于凹函数时成立。才有是常量即当且仅当是严格的凸函数如果是随机变量，那么是凸函数，如果不等式表达如下：是凸函数。那么，如果对于所有的实数是定义域为实数的函数设)()]([][,,1])[(,)()]([,0)('',EXfxfEJensenEXfXfEXXEXpfEXfXfEXfJensenfxfXf三、数学期望相关定理连续型离散型学期望为的数的某一函数表示，则密度函数或用的分布用分布列若随机变量dxxpxgXgExpxgXgEXgXxpxpXiiii)()()]([)()()]([:)()()(四、边际分布列的分布列。称为求和所得的分布列中，对的联合分布列在二维离散随机变量XjyYxXPYXji,,ijjixXPyYxXP1,的分布列。称为求和所得的分布列类似地，对YiiIjiyYPyYxXP1,EM算法),(xX本的X机变观测数据：观测到的随1nx，样量),,(1nzzZZ的值随机变量隐含变量：未观测到的)),(),,((),(11nnzxzxYZXYZX的数据：隐含变量和的随机变量完整数据：包含观测到1、完整数据：2、EM算法的推导EM算法1);,(ln);(ln)()()()(iiiziizxpxpLi：根据边缘分布列的定义ijjixXPyYxXP1,似然估计。入手，对参数进行极大观测数据是隐含变量，则可从可由于极大似然估计中计算完整数据的数据算法是从含有隐含变量ZEM,)(EM算法)2()();,()(ln)1();,(ln);(ln)()()()()()()()()(iiiiiiziiiiziizQzxpzQzxpxpii0)(1)()(zQzQQZQiiZiii满足的条件是的某种分布，表示隐含变量EM算法)()()]([iiixpxfXfE理：根据数学期望的相关定)2()();,()(ln)()()()()(iiiiiizizQzxpzQi)3()])();,([ln()()()(iiiiizQzxpE;)();,()();()()()()()()()(iiiiiiiizQzxpzfzQzp的数学期望是)();,()();,()()()()()()()()()(iiiiiiiiizizQzxpzQzxpzQi根据Jensen不等式：EM算法)()(ln)(xfEXEfxxf是凹函数XEXEln][ln)3()])();,([ln()()()(iiiiizQzxpE)4()();,(ln)()()(iiiiizQzxpEEM算法)5()();,(ln)()4()();,(ln)()()()()()()()(iiiiiziiiiiiizQzxpzQzQzxpEi)()()]([iiixpxfXfE理：根据数学期望的相关定);)();,(ln()();()()()()()()()(iiiiiiiizQzxpzfzQzpEM算法。的对数似然函数的下界）是参数所以（求了下界的过程。上述过程看成是对又是我模型里的参数。的函数）看成是将（5,5L)5()();,(ln)()()()()()(iiiiiizizQzxpzQLiEM算法处。的最大值直到收敛到似然函数调整。再固定为新的到的使下界达到最大值，得计调整，利用极大似然估然后固定的值相等。对应的至与此使下界上升，，调整固定*11,LzQzQLzQttttt优化了目标函数。个下界的时候，才真正我才能保证当我优化这的对数似然函数时，当前只有当此时的下界等于3.寻找等式成立的条件：EM算法成立。前的让此不等式的等号对当的可能分布，，我们选择首先固定Q)5()();,(ln)()()()()()(iiiiiziizQzxpzQi)3()])();,([ln()()()(iiiiizQzxpEXEXEJensenln][ln不等式：根据)5()();,(ln)()()()()()(iiiiiizizQzxpzQLiEM算法CzQzxpiiii)();,()()()(仅当等号成立的条件是当且CzxPzQCzxPzQCzxPCzQzxpziiziiziiiiiiiiii;,;,;,)();,()()()(0)(1)()(zQzQQZQiiZiii满足的条件是的某种分布，表示隐含变量EM算法CzQzxpiiii)();,()()()(仅当等号成立的条件是当且);|();();,();,();,()()()()()()()()()()(iiiiiziiiiiixzpxpzxpzxpzxpzQEM算法E-step：固定θ后，得到的计算公式，建立L(θ)的下界。)()(iizQ;|::)()(iiiiixzpzQzstepE的概率分布，选择隐含变量固定)6()();,(ln)()()()()()(iiiiiizizQzxpzQLiEM算法)6()();,(ln)()()()()()(iiiiiizizQzxpzQLiM-step：就是在给定后，根据求极大似然估计量的过程，去极大化L(θ)的下界，得到新的参数θ。)()(iizQiiiiiziizQzxpzQstepMi;,lnmaxarg::5.EM算法的收敛：EM算法收敛，L(θ)不再变化或者是增量小于某一给定的值。想要保证EM是收敛的，就要证明极大似然估计单调增加。EM算法)()(1)1()()1()(ttttLLttEM单调增加，就要证明想要证明极大似然估计次迭代后的结果。次和第第是和假定E-stepM-stepEM算法)();,(ln)()(ensen);|(:)(,)()()()()()()()()()()()()()()(itiiiitizitttiiititzQzxpzQLJxzpzQi即：不等式中的等式成立。时，这一步保证了给定得到选定。得到求导，视作变量，对上面的并将固定)1()()()()()(),(tttitiLzQ)3()()2()();,(ln)()1()();,(ln)()();,()(ln)()()()()()()()()()()()1()()()()()()()1()()()()()1()()()(tititiiiiztiititiiiiztiititiiiiztitLzQzxpzQzQzxpzQzQzxpzQLiiiEM算法时才能成立。步得到按，并固定立。等式成立只有是在下界，而没有使等式成的不等式得到的。也就是不等式是根据itQELJensen)()1()1(使得下界最大化。，调整到步就是将步的定义，利用了)1()()2(ttMM4.EM算法总结：EM算法;|::)()(iiiiixzpzQzstepE的概率分布，选择隐含变量固定iiiiiziizQzxpzQstepMi;,lnmaxarg::