ML-4-1 期望最大算法

1機(jī)器學(xué)習(xí)圖像中心第3章期望最大算法2內(nèi)容提要一、期望最大(ExpectationMaximization,EM)

算法及應(yīng)用二、GMM及其應(yīng)用3一、EM算法及應(yīng)用1最大似然估計(jì)(MaximizationLikelihood)設(shè)總體Ｘ的密度函數(shù)是參數(shù)或參數(shù)向量，是該總體的樣本，對給定的一組觀測值，其聯(lián)合密度是的函數(shù)，又稱似然函數(shù)，記為：4其中為參數(shù)集，若存在使就稱是的最大似然估計(jì)值，而是的最大似然估計(jì)量。求最大似然估計(jì)法的步驟第一步:寫出似然函數(shù);

計(jì)算;第二步:如果似然函數(shù)關(guān)于參數(shù)是可微的,求;第三步:解方程,從中得到使取得極大值的

,就是參數(shù)的最大似然估計(jì)量.5例設(shè)是正態(tài)總體的一個(gè)樣本,試求和的最大似然估計(jì).解：似然函數(shù)取對數(shù)6解方程得到7Problem1FittingpointstoonelineSolution:LSEFittingpointstotwolinesHowtodeterminewhichlinegenerateseachpoint?Solution:???2實(shí)際問題正規(guī)方程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在許多實(shí)際的學(xué)習(xí)問題框架中，相關(guān)實(shí)例特征中只有一部分可觀察到已有許多方法被提出來處理存在未觀察到變量的問題比如，如果某些變量有時(shí)能觀察到，有時(shí)不能，那么可以用觀察到該變量的實(shí)例去預(yù)測未觀察到的實(shí)例中的變量的值EM算法是存在隱含變量時(shí)廣泛使用的一種學(xué)習(xí)方法，可用于變量的值從來沒有被直接觀察到的情形，只要這些變量所遵循的概率分布的一般形式已知用于GMM的訓(xùn)練用于馬爾可夫模型的訓(xùn)練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應(yīng)用舉例例1假設(shè)我們觀察到隨機(jī)序列∽求：（這里用EM算法來求解該問題，當(dāng)然，也可以用優(yōu)化算法如Newton’smethod.）25對數(shù)似然函數(shù)為：引入輔助變量26∽X是完整的隨機(jī)序列，Y是觀察到的隨機(jī)序列。則，完整的隨機(jī)序列的對數(shù)似然函數(shù)為：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現(xiàn)在有來自一個(gè)概率分布的一些樣本需要使用這些樣本來估計(jì)概率密度函數(shù)。我們使用高斯混合模型來近似表示該概率密度函數(shù)其中，是均值和協(xié)方差陣分別為，的正態(tài)分布。31（1）假設(shè)所有中的均可表示為如下形式：

則，可表示為：求偏導(dǎo)數(shù)：

32最大似然函數(shù)的對數(shù)為：

33其中34由可得（a）（b）35在的條件下，估計(jì)需用拉格朗日乘子法由可得36對于j＝1,……,m將各式相加，得：由可得帶入上式可得（c）37EMIteration:設(shè)定一個(gè)起始參數(shù)值（j=1,……m（可用K-means方法設(shè)定一個(gè)較好的起始參數(shù)值）使用起始參數(shù)計(jì)算利用公式（a）（b）（c）來計(jì)算令若小于某一個(gè)極小的容忍值，則停止。否則令并跳回步驟2。38（2）中的不能表示為形式推導(dǎo)公式類似(1),請自己推導(dǎo)!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及其應(yīng)用1基于GMMs的簡單圖像分割方法基本思想：把圖像象素的R、G、B顏色分量分別看作兩個(gè)高斯模型的混疊，利用整個(gè)圖像顏色信息通過EM算法分別求出對應(yīng)于每一顏色分量的兩個(gè)高斯模型的參數(shù)，根據(jù)所得高斯模型，即可將所有象素的每一顏色分量分成兩類，并分別賦以對應(yīng)高斯模型的平均值。由于每個(gè)顏色分量都可分成兩類，則所有象素可分成8類。上述過程已將8類象素賦予不同的值，從而將整幅圖分割成8個(gè)區(qū)域。42432Skincolorsegmentation[Yang,Ahuja1999:GMMsforHumanSkinColor…]44[Zhu,Yang,Waibel2000:SegmentingHandsofArbitraryColor]45不同人種皮膚顏色分布圖感知均衡色彩系統(tǒng)(PerceptuallyuniformColorSystem)RGB-UCS：http://www.wakayama-u.ac.jp/~chen/ucs.html46Gaussian膚色模型473自動語言識別這方面的工作可參見MIT的lincoln實(shí)驗(yàn)室的最新進(jìn)展，網(wǎng)址是：/4人臉識別人臉識別算法的主要挑戰(zhàn)來自于當(dāng)被識別者改變姿勢時(shí)，臉的特征也相應(yīng)改變，這個(gè)問題的一個(gè)解決辦法就是預(yù)先建立由所有頭部位置決定的臉部圖象的相關(guān)模型。但是，在一個(gè)自由的場合，預(yù)先設(shè)定所有的頭部位置是不太可能的，例如在一個(gè)會議室里，可以利用GMM來對人臉進(jìn)行特征描述,從而進(jìn)一步發(fā)展新的算法。48作業(yè)：題目：基于有限混合高斯模型的圖像分割算法說明、流程請參考本次課講義、參考實(shí)驗(yàn)報(bào)告及程序。要求：用C++

編程實(shí)現(xiàn)該算法。可以2個(gè)同學(xué)一組，討論完成作業(yè)。（在研讀相關(guān)論文基礎(chǔ)上，至少實(shí)現(xiàn)一種改進(jìn)的EM算法。）49圖像建模方