1、1,機器學習,圖像中心,第3章 期望最大算法,2,內(nèi)容提要,一、期望最大(Expectation Maximization, EM) 算法及應(yīng)用 二、GMM及其應(yīng)用,3,一、EM算法及應(yīng)用,1 最大似然估計(Maximization Likelihood),設(shè)總體的密度函數(shù) 是參數(shù)或參數(shù)向量， 是該總體的樣本，對給定的一組觀測值 ，其聯(lián)合密度是 的函數(shù)，又稱似然函數(shù)，記為：,4,其中 為參數(shù)集，若存在 使 就稱 是 的最大似然估計值，而 是 的最大似然估計量。,求最大似然估計法的步驟,第一步:寫出似然函數(shù) ; 計算 ; 第二步:如果似然函數(shù)關(guān)于參數(shù)是可微的,求 ; 第三步:解方程 , 從中得到

2、使 取得極大值的 , 就是參數(shù) 的最大似然估計量.,5,6,解方程,得到,7,Problem 1,Fitting points to one line,Solution: LSE,Fitting points to two lines,How to determine which line generates each point? Solution: ?,2 實際問題,8,Problem 2: Parameter Estimation for Mixture Models,Single Gaussian,Solution: MLE by maximizing,9,Multiple Gauss

3、ians,Which component does each point belong to? Solution: ?,10,Incompleteness Analytically hard,Common Feature,Likelihood of parameter given data X: Maximize expectation of L by “tweaking” ,11,Common Feature - Incompleteness,Not Known,A paradox: Interdependency between hidden values and parameters g

4、overning the distribution,12,A more general problem: estimating the parameters of a p.d.f.,No direct access to the needed data (missed) Outcome is an accumulation of simpler outcomes(grouped) The number of underlying data is unknown (truncated),13,A.P.Dempster, et al 1977: “Maximum likelihood from i

5、ncomplete data via the EM algorithm” General statement of the algorithm Prove convergence Coin the term ”EM algorithm”,2 EM Algorithm Creative work,14,在許多實際的學習問題框架中，相關(guān)實例特征中只有一部分可觀察到 已有許多方法被提出來處理存在未觀察到變量的問題 比如，如果某些變量有時能觀察到，有時不能，那么可以用觀察到該變量的實例去預(yù)測未觀察到的實例中的變量的值 EM算法是存在隱含變量時廣泛使用的一種學習方法，可用于變量的值從來沒有被直接觀察到的

6、情形，只要這些變量所遵循的概率分布的一般形式已知 用于GMM的訓練 用于馬爾可夫模型的訓練,15,Stochastically independent Bayes rule Logarithm Expectation,Review,16,Maximize expectation of L by tweaking : Analytically hard,Idea：,Introduce nonexistent data Y Incomplete data X Stochastically independent Y Complete data Z := (X, Y) - Easier!,17,So

7、lution ： Introducing additional variables to make it complete,Z=(X,Y),Incomplete data likelihood,Complete data likelihood,18,Define,19,Initialize with random/guess, set n=1 E-step: use current parameters to estimate M-step: compute maximum likelihood estimation of using set n = n+1 repeat until conv

8、ergence,EM Algorithm步驟,20,Solution to Line Fitting,Parameters: = a1, b1, a2, b2,Posterior Probability:,where, l=1,2,21,Expectation:,Maximization: Taking the derivative of Q with respect to al, bl and setting the result to zero, we obtain,Where l=1,2,22,Solution to Mixture Modelling,Parameters:,Poste

9、rior Probability:,where,is a single Gaussian,centered at i with covariance matrixi ai is the mixing weight, i=1,2,M,23,Expectation:,Maximization:,Taking the derivative of Q with respect to al, ul and and setting the result to zero, we obtain the following update rules,24,4 EM Algorithm應(yīng)用舉例,例1,假設(shè)我們觀察

10、到隨機序列,求：,（這里用EM算法來求解該問題，當然，也可以用優(yōu)化算法如Newtons method.）,25,對數(shù)似然函數(shù)為：,引入輔助變量,26,X是完整的隨機序列，Y是觀察到的隨機序列。 則，完整的隨機序列的對數(shù)似然函數(shù)為：,27,E Step:,注：,28,M Step:,29,EM Iteration Results:,Iteration,Theta,Error,1 2 3 4 5 6 7 8 9 10 11,0.6082474 0.624321 0.6264889 0.6267773 0.6268156 0.6268207 0.6268214 0.6268215 0.6268215

11、 0.6268215 0.6268215,0.1082474 0.01607363 0.002167829 0.0002884433 3.830976e-05 5.086909e-06 6.754367e-07 8.968368e-08 1.190809e-08 1.581141e-09 2.099418e-10,30,例2,現(xiàn)在有來自一個概率分布的一些樣本,需要使用這些樣本來估計概率密度函數(shù)。,我們使用高斯混合模型來近似表示該概率密度函數(shù),其中 ， 是均值和協(xié)方差陣分別為,，,的正態(tài)分布。,31,（1）假設(shè)所有 中的 均可表示為如下形式：,則， 可表示為：,求 偏導(dǎo)數(shù)：,32,最大似然函數(shù)的

12、對數(shù)為：,33,其中,34,由,可得,（a）,（b）,35,在,的條件下，估計,需用拉格朗日乘子法,由,可得,36,對于j1,m將各式相加，得：,由,可得,帶入上式可得,（c）,37,EM Iteration :,設(shè)定一個起始參數(shù)值 （j=1,m（可用K-means方法設(shè)定一個較好的起始參數(shù)值） 使用起始參數(shù)計算 利用公式（a）（b）（c）來計算 令 若 小于某一個極小的容忍值，則停止。否則令 并跳回步驟2。,38,（2） 中的 不能表示為 形式,推導(dǎo)公式類似(1),請自己推導(dǎo)!,39,5 Generalized EM,Assume and function are differentiabl

13、e in .The EM likelihood converges to a point where GEM: Instead of setting (n) = argmax Q (, (n-1) Just find (n) such that Q (, (n) Q (, (n-1) GEM also is guaranteed to converge,40,J.Bilmes, A Gentle Tutorial of the EM algorithm and its Application to Parameter Estimation for Gaussian Mixture and Hi

14、dden Markov Models. TR-CS-Berkeley, 1998 A.Dempster, Laird, Rubin. Maximum Likelihood from Incomplete Data via the EM Algorithm. Journal of the Royal Statistical Society, 1977 Neal, Hinton. A view of the EM Algorithm that Justifies Incremental, Sparse and other Variants. Learning in Graphical Models

15、,1998 A.Moore, Very Fast Mixture Model based Clustering using Multi-resolution k-d trees. NIPS 1999 N.Friedman, The Bayesian Structural EM Algorithm. UAI 1998 Belongie et.al, Color- and Texture-Based Image Segmentation Using EM and Its Application to Content-Based Image Retrieval, ICCV 98,Recommende

16、d Further Readings,41,三、GMM及其應(yīng)用,1 基于GMMs的簡單圖像分割方法,基本思想： 把圖像象素的R、G、B顏色分量分別看作兩個高斯模型的混疊，利用整個圖像顏色信息通過EM算法分別求出對應(yīng)于每一顏色分量的兩個高斯模型的參數(shù)，根據(jù)所得高斯模型，即可將所有象素的每一顏色分量分成兩類，并分別賦以對應(yīng)高斯模型的平均值。由于每個顏色分量都可分成兩類，則所有象素可分成8類。上述過程已將8類象素賦予不同的值，從而將整幅圖分割成8個區(qū)域。,42,43,2 Skin color segmentation,Yang, Ahuja 1999: GMMs for Human Skin Col

17、or ,44,Zhu, Yang, Waibel 2000: Segmenting Hands of Arbitrary Color,45,不同人種皮膚顏色分布圖,感知均衡色彩系統(tǒng)(Perceptually uniform Color System) RGB-UCS：http:/www.wakayama-u.ac.jp/chen/ucs.html,46,Gaussian膚色模型,47,3 自動語言識別 這方面的工作可參見MIT的lincoln實驗室的最新進展，網(wǎng)址是：/,4 人臉識別 人臉識別算法的主要挑戰(zhàn)來自于當被識別者改變姿勢時，臉的特征也相應(yīng)改變，

18、這個問題的一個解決辦法就是預(yù)先建立由所有頭部位置決定的臉部圖象的相關(guān)模型。但是，在一個自由的場合，預(yù)先設(shè)定所有的頭部位置是不太可能的，例如在一個會議室里，可以利用GMM來對人臉進行特征描述, 從而進一步發(fā)展新的算法。,48,作業(yè)： 題目：基于有限混合高斯模型的圖像分割,算法說明、流程請參考本次課講義、參考實驗報告及程序。,要求：用C+ 編程實現(xiàn)該算法?？梢?個同學一組，討論完成作業(yè)。,（在研讀相關(guān)論文基礎(chǔ)上，至少實現(xiàn)一種改進的EM算法。）,49,圖像建模方法統(tǒng)計建模,圖像可以當作二維隨機過程(隨機場)中的一個樣本來分析。在某些場合下，用確定的表示法來描述圖像是很困難的，然而卻可用圖像的平均特性方便地加以描述。圖像的灰度強度函數(shù)F(x,y)可以看作圖像平面上的二維隨機變量。這個隨機變量在一定范圍內(nèi)的分布規(guī)律，就體現(xiàn)了圖像在一定范圍內(nèi)的相對宏觀的平均特性。通常，對于圖像中不同的區(qū)域來說，這個隨機變量具有不同的統(tǒng)計規(guī)律,50,統(tǒng)計建模,時空域統(tǒng)計建模,變換域統(tǒng)計建模,對變換系數(shù)的統(tǒng)計建模：小波系數(shù)的統(tǒng)計建模,（如小波系數(shù)尺度間、尺度內(nèi)、方向間的相關(guān)性等）,51,由于一般正交小波變換不具有平移不變性和方向較少的特點，基于這些不足，現(xiàn)在的發(fā)展是在其他變換域內(nèi)建立模型，如（冗余小波變換，復(fù)小波變換，脊波，曲波等）,5