本节课内容：计算似然的极大值 牛顿法 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