本节课内容:计算似然的极大值 牛顿法 EM

整理文档很辛苦,赏杯茶钱您下走!

免费阅读已结束,点击下载阅读编辑剩下 ...

阅读已结束,您可以下载文档离线阅读编辑

资源描述

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:ExpectationMaximization„E—步:求期望(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

1 / 54
下载文档,编辑使用

©2015-2020 m.777doc.com 三七文档.

备案号:鲁ICP备2024069028号-1 客服联系 QQ:2149211541

×
保存成功