ML-4-1 期望最大算法

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

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

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

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

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

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

33其中34由可得（a）（b）35在的條件下，估計需用拉格朗日乘子法由可得36對于j＝1,……,m將各式相加，得：由可得帶入上式可得（c）37EMIteration:設(shè)定一個起始參數(shù)值（j=1,……m（可用K-means方法設(shè)定一個較好的起始參數(shù)值）使用起始參數(shù)計算利用公式（a）（b）（c）來計算令若小于某一個極小的容忍值，則停止。否則令并跳回步驟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顏色分量分別看作兩個高斯模型的混疊，利用整個圖像顏色信息通過EM算法分別求出對應(yīng)于每一顏色分量的兩個高斯模型的參數(shù)，根據(jù)所得高斯模型，即可將所有象素的每一顏色分量分成兩類，并分別賦以對應(yīng)高斯模型的平均值。由于每個顏色分量都可分成兩類，則所有象素可分成8類。上述過程已將8類象素賦予不同的值，從而將整幅圖分割成8個區(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實驗室的最新進展，網(wǎng)址是：/4人臉識別人臉識別算法的主要挑戰(zhàn)來自于當(dāng)被識別者改變姿勢時，臉的特征也相應(yīng)改變，這個問題的一個解決辦法就是預(yù)先建立由所有頭部位置決定的臉部圖象的相關(guān)模型。但是，在一個自由的場合，預(yù)先設(shè)定所有的頭部位置是不太可能的，例如在一個會議室里，可以利用GMM來對人臉進行特征描述,從而進一步發(fā)展新的算法。48作業(yè)：題目：基于有限混合高斯模型的圖像分割算法說明、流程請參考本次課講義、參考實驗報告及程序。要求：用C++

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