Chp9:参数推断本节课内容:计算似然的极大值牛顿法EM算法极大似然估计似然函数:令为IID,其pdf为,似然函数定义为log似然函数:极大似然估计(MLE):使得最大的,即();fxθ1,...,nXX()()1;nniifXθθ==∏L()()lognnlθθ=L()()ˆargmaxargmaxnnnlθθθθθ==Lθ()nθL极大似然估计计算MLE,需要求似然函数的极值解析法(如本章已讲过的例子)数值计算:通过迭代牛顿法:简单EM算法迭代需要初始值,矩方法得到的结果是一个较好的初始值的选择牛顿法亦称牛顿-拉夫逊(Newton-Raphson)方法牛顿在17世纪提出的一种近似求解方程的方法使用函数的泰勒级数的前面几项来寻找方程的根在MLE计算中,求的根对应处似然函数取极值()0nlθ′=()fx()0fx=()nlθ牛顿法将log似然函数的导数在处进行Taylor展开:从而得到因此迭代机制为:()()()()()ˆˆˆ0ttttlllOpθθθθθθθ′′′′==+−+−()lθ′tθ()()ˆtttllθθθθ′≈−′′()()1ˆttttllθθθθ+′≈−′′牛顿法当参数包含多个参数为向量时,迭代机制为:其中为log似然函数一阶偏导数(向量),为二阶偏导数矩阵,()11ˆtttnlHθθθ+−′≈−()()1ˆtntttnllθθθθ+′≈+′′()1,...,Kθθθ=()tnlθ′H()nlθ()2njkjklθθθ∂=∂∂HEM算法(ExpectationMaximization)EM:ExpectationMaximization特别适合:“缺失数据”(missingdata)问题中对参数用MLE求解由于观测过程的限制或问题引起的数据缺失(如聚类问题)直接对观测数据,似然函数极值解析不可求;但若假设缺失数据(隐含变量)的值已知,则似然函数形式很简单EM算法(ExpectationMaximization)EM:ExpectationMaximizationE—步:求期望(Expectation)在给定观测数据的条件下,计算完整似然的期望(随机变量为隐含变量)涉及计算缺失数据的条件期望,需要利用参数的当前估计值M—步:求极大值(Maximization)求使得完整似然的期望最大的参数又是一个极大值求解问题。通常可以解析求解,这时EM是一个很方便的工具;否则,需借助一个可靠的最大化方法求解混合模型(MixedModel)混合模型:其中,满足即混合模型由K个成分组成,每个成分的权重为如一个班级每个学生的身高为,假设男生身高和女生分别服从高斯分布、则其中p为男生的比例混合模型的参数估计是EM算法最典型的应用()()1||Kkkkkfxfxθαθ==∑()11,...,,,...,KKθααθθ=kα11Kkkα==∑()|kkfxθX()211,Nμσ()222,Nμσ()()()221122~,1,XpNpNμσμσ+−混合高斯模型(MixtureofGaussiansModel,GMM)若混合模型中每个成分为高斯分布,则称为混合高斯模型假设每个数据点根据如下规则产生:随机选择一个成分,选择第k个成分的概率为从第k个成分产生数据:即()YkP=()~,kkXNμΣ(),1kkkYkPαα===∑()()()()|~,;,kkkkkfxfxYkNxμφμ==Σ=Σ()()()11;,;,KKkkkkkkkfxfxxμααφμ==Σ==Σ∑∑混合高斯模型问题:给定IID数据,求参数MLE不能解析求得,因此我们通过数值计算(如EM算法)求解。将非完整数据转换为完整数据,其中为所属的类别。,,kkkαμΣ()()11,,...,,nnXYXYiYiX1,...,nXX1,...,nXX观测数据和缺失数据观测数据:观测到随机变量X的IID样本:缺失数据:未观测到的隐含变量Y的值:在GMM中,若来自第k个分成,则完整数据:包含观测到的随机变量X和未观测到的随机变量Y的数据,()1,...,nXXX=iXiYk=()1,...,nYYY=(),ZXY=似然函数给定观测数据,非完整数据的似然函数为:涉及求和的log运算,计算困难()1,...,nXXX=()()()1log|log|niiXfXθθ==∏L()11log|nKkkikikfXαθ==⎛⎞⎟⎜=⎟⎜⎟⎜⎟⎝⎠∑∑完整似然函数若隐含变量的值也已知,得到完整数据的似然函数为:明显简化()1,...,nYYY=()()()()()11log|,log,|log,|nniiiiiiXYfXYfXYθθθ====∑∏L()()()1log|,|niiiifXYfYθθ==∑()()1log|iiinYYiYifXαθ==∑()()()11log|log|nKkkikikXfXθαθ==⎛⎞⎟⎜=⎟⎜⎟⎜⎟⎝⎠∑∑L()()(),||,|fxyfxyfyθθθ=iYθiYαEM—Expectation由于Y是未知的,计算完整似然函数对Y求期望去掉完整似然函数中的变量Y定义根据贝叶斯公式:Y的分布为()()(),log|,|,ttQXYXθθθθ⎡⎤=⎣⎦LE()()()log|,|,tyXyfyXdyθθ∈ϒ=∫L()()()()()()1||,||,||iiittyyiyiiitiiKtikkikkfXfXyfyfyXfXfXαθθθθθαθ===∑()()1|,|,nttiiifyXfyXθθ==∏EM—Maximization对E步计算得到的完整似然函数的期望求极大值(Maximization),得到参数新的估计值,即每次参数更新会增大似然(非完整似然)值反复迭代后,会收敛到似然的局部极大值(),tQθθ()1argmax,ttQθθθθ+=EM的收敛性(1)()()(),log|,|,ttQXYXθθθθ⎡⎤=⎣⎦LE()()()log|,|,tyXyfyXdyθθ∈ϒ=∫L()()()()log|,||,tyfyXfXfyXdyθθθ∈ϒ=∫()()()log|,|,tyfyXfyXdyθθ∈ϒ=∫()()()()()log|,|,log|tyfyXfyXdyfXθθθ∈ϒ=+∫()()()log||,tyfXfyXdyθθ∈ϒ+∫()()()()|,,||,|XYfXYfYXfXθθθθ==LEM的收敛性(2)所以相邻两次似然之差为()()()()()(),log|,|,log|tttttyQfyXfyXdyfXθθθθθ∈ϒ=+∫tθθ=()()()|log|nlXfXθθ=()()()()11||,,ttttttnnlXlXQQθθθθθθ++−=−()()()()()(),log|,|,log|ttyQfyXfyXdyfXθθθθθ∈ϒ=+∫当时()()()1|,log|,|,tttyfyXfyXdyfyXθθθ+∈ϒ−∫EM的收敛性(3)所以其中为KL散度。所以:如果Q增大,则观测数据的似然增大在M步,Q肯定增大当Q取极大值时,观测数据的似然也在相同点取极大值EM算法会收敛到似然的局部极大值()()()()()111||,,,ttttttttnnlXlXQQDθθθθθθθθ+++−=−+()()()()11|,,log|,0|,tttttyfyXDfyXdyfyXθθθθθ++∈ϒ=≥∫()()()()()()()111|,||,,log|,|,ttttttttnntyfyXlXlXQQfyXdyfyXθθθθθθθθθ+++∈ϒ−=−−∫()()()(),logfxDfgfxdxgx⎛⎞⎟⎜⎟=⎜⎟⎜⎟⎟⎜⎝⎠∫混合模型中的EM算法完整似然函数:Y的条件分布:()()()()()1|,||,||iiityyiyiitiiKtikkikkfXfyXfyXfXfXαθθθθαθ===∑()()1|,|,nttiiifyXfyXθθ==∏()()()()1log|,log|iiinYYiYiXYfXθαθ==∑L()()1log|iiinYYiYifXαθ=∑()(),1log|iKylllillfXδαθ=∑()()log|,|,tyYXYfyXθθ∈=∑L()1|,ntjjjfyXθ=∏Expectation()()(),log|,|,ttQXYXθθθ⎡⎤=⎣⎦LEθθt:第t次猜测值∈=∑yY1ni∈==∑∑yY()1|,ntjjjfyX=∏θ()()()()1log|,log|iiinYYiYiXYfXθαθ==∑LExpectation(),tQθθ()()()(),111,log||,iKnnttllilyljjliyYjQfXfyXθθαθδθ==∈==∑∑∑∏()()()1,111111log||,iinKnKKKntllilyljjliyyyjfXfyXαθδθ=======∑∑∑∑∑∏当yi≠l等于01ni∈==∑∑yY()(),1log|iKylllillfXδαθ=∑()1|,ntiiifyX=∏θ()()11111111|,|,iinKKKKnttjjiyyyyjjifyXflXθθ−+=====≠⎛⎞⎜⎟⎜⎟⎜⎟⎝⎠∑∑∑∑∏()()11log|KnllillifXαθ===∑∑()()11111111|,|,iinKKKKnttiiiyyyyjjifyXflXθθ−+=====≠⎛⎞⎜⎟⎜⎟⎜⎟⎝⎠∑∑∑∑∏()()()()1111log||,|,jKnnKttlliliiilijyjifXfyXflXαθθθ====≠⎡⎤⎛⎞⎢⎥=⎜⎟⎜⎟⎢⎥⎝⎠⎢⎥⎣⎦∑∑∏∑Expectation()()()(),111,log||,iKnnttllilyljjliyYjQfXfyXθθαθδθ==∈==∑∑∑∏()()()1,111111log||,iinKnKKKntllilyljjliyyyjfXfyXαθδθ=======∑∑∑∑∑∏(),tQθθ()()11log|KnllillifXαθ===∑∑Expectation()()()()1111log||,|,jKnnKttlliliiilijyjifXfyXflXαθθθ====≠⎡⎤⎛⎞⎢⎥=⎜⎟⎜⎟⎢⎥⎝⎠⎢⎥⎣⎦∑∑∏∑(),tQθθ1()()()()11,log||,KnttllililiQfXflXθθαθθ===∑∑()()()()()1111,log|,log||,KnKntttlililililiQflXfXflXθθαθθθ=====+∑∑∑∑Maximization给定第t次的猜测θt,我们计算θ,使得上述期望最大。反复迭代,直到收敛。11(,,,,,,)KKθααθθ=……()()()()()1111,log|,log||,KnKntttlililililiQflXfXflXθθαθθθ=====+∑∑∑∑混合高斯模型GMM)中的EM算法高斯分布:最大化:目标:()()()()()1111,log|,log||,KnKntttlililililiQflXfXflXθθαθθθ=====+∑∑∑∑()()()()1/21/211|,exp22||TlllllldlfxxxΣΣμμμπ−⎡⎤Σ=−−−⎢⎥⎣⎦混合高斯模型GMM)中的EM算法高斯分布:目标:最大化:()()()()()1111,log|,log||,KnKntttlililililiQflXfXflXθθαθθθ=====+∑∑∑∑()()()()1/21/211|,exp22||TlllllldlfxxxΣΣμμμπ−⎡⎤Σ=−−−⎢⎥⎣⎦只与αl相关只与αl相关只与θl相关只与θl相关计算αl由于αl有限制,我们引入Lagrange乘子λ,并解下述方程。()()111log|,10,1,,KnKtlillillflXlKαλαα===⎡⎤∂⎛⎞+−==⎢⎥⎜⎟∂⎝⎠⎣⎦∑∑∑θ…()11|,0,1,,ntiilflXlK