ML-4-1 期望最大算法

1机器学习图像中心第3章期望最大算法2内容提要一、期望最大(ExpectationMaximization,EM)

算法及应用二、GMM及其应用3一、EM算法及应用1最大似然估计(MaximizationLikelihood)设总体Ｘ的密度函数是参数或参数向量，是该总体的样本，对给定的一组观测值，其联合密度是的函数，又称似然函数，记为：4其中为参数集，若存在使就称是的最大似然估计值，而是的最大似然估计量。求最大似然估计法的步骤第一步:写出似然函数;

计算;第二步:如果似然函数关于参数是可微的,求;第三步:解方程,从中得到使取得极大值的

,就是参数的最大似然估计量.5例设是正态总体的一个样本,试求和的最大似然估计.解：似然函数取对数6解方程得到7Problem1FittingpointstoonelineSolution:LSEFittingpointstotwolinesHowtodeterminewhichlinegenerateseachpoint?Solution:???2实际问题正规方程8Problem2:ParameterEstimationforMixtureModelsSingleGaussianSolution:MLEbymaximizing

9MultipleGaussiansWhichcomponentdoeseachpointbelongto?Solution:???10IncompletenessAnalyticallyhardCommonFeatureLikelihoodofparameterΘgivendataX:MaximizeexpectationofLby“tweaking”

Θ11CommonFeature----

IncompletenessObservationProbDistributionNotKnownParametersAparadox:InterdependencybetweenhiddenvaluesandparametersgoverningthedistributionHiddenValueHiddenValue12Amoregeneralproblem:estimatingtheparametersofap.d.f.Nodirectaccesstotheneededdata(missed)Outcomeisanaccumulationofsimpleroutcomes(grouped)Thenumberofunderlyingdataisunknown(truncated)13A.P.Dempster,etal1977:“MaximumlikelihoodfromincompletedataviatheEMalgorithm”GeneralstatementofthealgorithmProveconvergenceCointheterm”EMalgorithm”2EMAlgorithm－Creativework14在许多实际的学习问题框架中，相关实例特征中只有一部分可观察到已有许多方法被提出来处理存在未观察到变量的问题比如，如果某些变量有时能观察到，有时不能，那么可以用观察到该变量的实例去预测未观察到的实例中的变量的值EM算法是存在隐含变量时广泛使用的一种学习方法，可用于变量的值从来没有被直接观察到的情形，只要这些变量所遵循的概率分布的一般形式已知用于GMM的训练用于马尔可夫模型的训练15StochasticallyindependentBayes’ruleLogarithmExpectationReview16MaximizeexpectationofLbytweakingΘ:AnalyticallyhardIdea：IntroducenonexistentdataYIncompletedataXStochasticallyindependentYCompletedataZ:=(X,Y)-Easier!17Solution：IntroducingadditionalvariablestomakeitcompleteObservedDataX={x1,x2,…,xn}HiddenVariableY={y1,y2,…,yn}Z=(X,Y)IncompletedatalikelihoodCompletedatalikelihood18Define19Initializewithrandom/guess,setn=1E-step:usecurrentparameterstoestimateM-step:

computemaximumlikelihoodestimationofusing

setn=n+1repeatuntilconvergenceEMAlgorithm步骤20SolutiontoLineFittingParameters:Θ={a1,b1,a2,b2}PosteriorProbability:

where,l=1,221Expectation:Maximization:TakingthederivativeofQwithrespecttoal,blandsettingtheresulttozero,weobtainWherel=1,222SolutiontoMixtureModellingParameters:PosteriorProbability:

whereisasingleGaussian,

centeredatμi

withcovariancematrixΣiai

isthemixingweight,

i=1,2,…,M23Expectation:Maximization:TakingthederivativeofQwithrespecttoal,ulandΣandsettingtheresulttozero,weobtainthefollowingupdaterules244EMAlgorithm应用举例例1假设我们观察到随机序列∽求：（这里用EM算法来求解该问题，当然，也可以用优化算法如Newton’smethod.）25对数似然函数为：引入辅助变量26∽X是完整的随机序列，Y是观察到的随机序列。则，完整的随机序列的对数似然函数为：27EStep:注：∽28MStep:29EMIterationResults:IterationThetaError12345678910110.60824740.6243210.62648890.62677730.62681560.62682070.62682140.62682150.62682150.62682150.62682150.10824740.016073630.0021678290.00028844333.830976e-055.086909e-066.754367e-078.968368e-081.190809e-081.581141e-092.099418e-1030例2现在有来自一个概率分布的一些样本需要使用这些样本来估计概率密度函数。我们使用高斯混合模型来近似表示该概率密度函数其中，是均值和协方差阵分别为，的正态分布。31（1）假设所有中的均可表示为如下形式：

则，可表示为：求偏导数：

32最大似然函数的对数为：

33其中34由可得（a）（b）35在的条件下，估计需用拉格朗日乘子法由可得36对于j＝1,……,m将各式相加，得：由可得带入上式可得（c）37EMIteration:设定一个起始参数值（j=1,……m（可用K-means方法设定一个较好的起始参数值）使用起始参数计算利用公式（a）（b）（c）来计算令若小于某一個极小的容忍值，则停止。否则令并跳回步骤2。38（2）中的不能表示为形式推导公式类似(1),请自己推导!395GeneralizedEMAssumeandfunctionaredifferentiablein.TheEMlikelihoodconvergestoapointwhereGEM:Insteadofsettingθ(n)=argmaxQ(θ,θ(n-1))Justfindθ(n)suchthat

Q(θ,θ(n))>Q(θ,θ(n-1))GEMalsoisguaranteedtoconverge40J.Bilmes,AGentleTutorialoftheEMalgorithmanditsApplicationtoParameterEstimationforGaussianMixtureandHiddenMarkovModels.TR-CS-Berkeley,1998A.Dempster,Laird,Rubin.MaximumLikelihoodfromIncompleteDataviatheEMAlgorithm.JournaloftheRoyalStatisticalSociety,1977Neal,Hinton.AviewoftheEMAlgorithmthatJustifiesIncremental,SparseandotherVariants.LearninginGraphicalModels,1998A.Moore,VeryFastMixtureModelbasedClusteringusingMulti-resolutionk-dtrees.NIPS1999N.Friedman,TheBayesianStructuralEMAlgorithm.UAI1998Belongieet.al,Color-andTexture-BasedImageSegmentationUsingEMandItsApplicationtoContent-BasedImageRetrieval,ICCV98RecommendedFurtherReadings41三、GMM及其应用1基于GMMs的简单图像分割方法基本思想：把图像象素的R、G、B颜色分量分别看作两个高斯模型的混叠，利用整个图像颜色信息通过EM算法分别求出对应于每一颜色分量的两个高斯模型的参数，根据所得高斯模型，即可将所有象素的每一颜色分量分成两类，并分别赋以对应高斯模型的平均值。由于每个颜色分量都可分成两类，则所有象素可分成8类。上述过程已将8类象素赋予不同的值，从而将整幅图分割成8个区域。42432Skincolorsegmentation[Yang,Ahuja1999:GMMsforHumanSkinColor…]44[Zhu,Yang,Waibel2000:SegmentingHandsofArbitraryColor]45不同人种皮肤颜色分布图感知均衡色彩系统(PerceptuallyuniformColorSystem)RGB-UCS：http://www.wakayama-u.ac.jp/~chen/ucs.html46Gaussian肤色模型473自动语言识别这方面的工作可参见MIT的lincoln实验室的最新进展，网址是：/4人脸识别人脸识别算法的主要挑战来自于当被识别者改变姿势时，脸的特征也相应改变，这个问题的一个解决办法就是预先建立由所有头部位置决定的脸部图象的相关模型。但是，在一个自由的场合，预先设定所有的头部位置是不太可能的，例如在一个会议室里，可以利用GMM来对人脸进行特征描述,从而进一步发展新的算法。48作业：题目：基于有限混合高斯模型的图像分割算法说明、流程请参考本次课讲义、参考实验报告及程序。要求：用C++

编程实现该算法。可以2个同学一组，讨论完成作业。（在研读相关论文基础上，至少实现一种改进的EM算法。）49图像建模方