P4 貝葉斯學(xué)習(xí)(2016)

1、第四部分第四部分 貝葉斯學(xué)習(xí)貝葉斯學(xué)習(xí) 參考書目參考書目 lTom M.Mitchell 機(jī)器學(xué)習(xí)機(jī)器學(xué)習(xí) 機(jī)械工業(yè)出版社機(jī)械工業(yè)出版社 l李連文李連文 郭海鵬郭海鵬 貝葉斯網(wǎng)絡(luò)引論貝葉斯網(wǎng)絡(luò)引論 科學(xué)出版社科學(xué)出版社 0 兩個(gè)示例兩個(gè)示例 樹后有幾只箱子？樹后有幾只箱子？ 可能的情況可能的情況 自然語言的二義性自然語言的二義性 lThe girl saw the boy with a telescope. lThe girl saw-with-a-telescope the boy. lThe girl saw the-boy-with-a-telescope. 1 貝葉斯公式貝葉斯公式 )

2、( )()|( )|( DP hPhDP DhP 先驗(yàn)概率和后驗(yàn)概率先驗(yàn)概率和后驗(yàn)概率 lP(h)：h的的先驗(yàn)概率先驗(yàn)概率。 表示在沒有訓(xùn)練數(shù)據(jù)前表示在沒有訓(xùn)練數(shù)據(jù)前 假設(shè)假設(shè)h擁有的擁有的初始概率初始概率； l先驗(yàn)概率反映了關(guān)于先驗(yàn)概率反映了關(guān)于h是一正確假設(shè)的機(jī)會(huì)的是一正確假設(shè)的機(jī)會(huì)的 背景知識(shí)。如果沒有這一先驗(yàn)知識(shí)，可以簡(jiǎn)單背景知識(shí)。如果沒有這一先驗(yàn)知識(shí)，可以簡(jiǎn)單 地將地將每一候選假設(shè)賦予相同的先驗(yàn)概率每一候選假設(shè)賦予相同的先驗(yàn)概率； lP(D)：訓(xùn)練數(shù)據(jù)：訓(xùn)練數(shù)據(jù)D的先驗(yàn)概率，的先驗(yàn)概率，P(D|h)表示假表示假 設(shè)設(shè)h成立時(shí)成立時(shí)D的概率；的概率； lP(h|D)： h的的后驗(yàn)概率后

3、驗(yàn)概率。表示給定。表示給定D時(shí)時(shí)h的成的成 立的概率。立的概率。 貝葉斯公式貝葉斯公式 l提供了從先驗(yàn)概率提供了從先驗(yàn)概率P(h)、P(D)和和P(D|h)計(jì)算后計(jì)算后 驗(yàn)概率驗(yàn)概率P(h|D)的方法，的方法， lP(h|D)隨著隨著P(h)和和P(D|h)的增長而增長，隨著的增長而增長，隨著 P(D)的增長而減少的增長而減少。 l即如果即如果D獨(dú)立于獨(dú)立于h時(shí)被觀察到的可能性越大，時(shí)被觀察到的可能性越大， 那么那么D對(duì)對(duì)h的支持度越小。的支持度越小。 極大后驗(yàn)假設(shè)（極大后驗(yàn)假設(shè)（MAP） l在候選假設(shè)集合在候選假設(shè)集合H中尋找給定數(shù)據(jù)中尋找給定數(shù)據(jù)D時(shí)，可時(shí)，可 能性最大的假設(shè)能性最大的假設(shè)

4、h； l確定確定MAP的方法是用貝葉斯公式計(jì)算每個(gè)的方法是用貝葉斯公式計(jì)算每個(gè) 候選假設(shè)的后驗(yàn)概率。候選假設(shè)的后驗(yàn)概率。 )()|(maxarg )( )()|( maxarg)|(maxarghPhDP DP hPhDP DhPh HhHhHh MAP 極大似然假設(shè)（極大似然假設(shè)（ML） l在某些情況下，可在某些情況下，可假定假定H中每個(gè)假設(shè)有相同中每個(gè)假設(shè)有相同 的先驗(yàn)概率的先驗(yàn)概率。 lP(D|h)常被稱為給定常被稱為給定h時(shí)數(shù)據(jù)時(shí)數(shù)據(jù)D的的似然度似然度， 而使而使P(D|h)最大的假設(shè)被稱為極大似然假最大的假設(shè)被稱為極大似然假 設(shè)；設(shè)； l假設(shè)空間假設(shè)空間H可擴(kuò)展為任意的互斥命題集合，

5、可擴(kuò)展為任意的互斥命題集合， 只要這些命題的概率之和為只要這些命題的概率之和為1。 )|(maxarghDPh Hh ML 示例示例- -醫(yī)療診斷醫(yī)療診斷 l有兩個(gè)可選的假設(shè)：病人有癌癥、病人無癌癥 l可用數(shù)據(jù)來自化驗(yàn)結(jié)果：正+和負(fù)- l先驗(yàn)知識(shí)： l在所有人口中，患病率是0.008 l對(duì)確實(shí)有病的患者的化驗(yàn)準(zhǔn)確率為98%， l對(duì)確實(shí)無病的患者的化驗(yàn)準(zhǔn)確率為97% 先驗(yàn)知識(shí)的概率表示先驗(yàn)知識(shí)的概率表示 P(cancer) = 0.008, P(cancer) = 0.992 P(+|cancer) = 0.98, P(-|cancer) =0.02 P(+|cancer) = 0.03, P(

6、-|cancer) = 0.97 示例示例 l假定有一個(gè)病人，化驗(yàn)結(jié)果為正，是否應(yīng)將病人斷定 為有癌癥？ l求后驗(yàn)概率P(cancer|+)和P(cancer|+) l極大后驗(yàn)假設(shè) lP(+|cancer)P(cancer)=0.0078 lP(+|cancer)P(cancer)=0.0298 lhMAP=cancer l確切的后驗(yàn)概率：上面結(jié)果的歸一化 P(canner|+)=0.0078/(0.0078+0.0298)=0.21 lP(cancer|-)=0.79 貝葉斯推理貝葉斯推理 貝葉斯推理的結(jié)果很大程度上依賴于先驗(yàn)概率貝葉斯推理的結(jié)果很大程度上依賴于先驗(yàn)概率 ，同時(shí)不是完全接受或

7、拒絕假設(shè)，只是在觀察，同時(shí)不是完全接受或拒絕假設(shè)，只是在觀察 到較多的數(shù)據(jù)后增大或減小了假設(shè)的可能性。到較多的數(shù)據(jù)后增大或減小了假設(shè)的可能性。 基本概率公式表基本概率公式表 乘法規(guī)則：乘法規(guī)則：(A B)=P(A|B)P(B)=P(B|A)P(A) 加法規(guī)則：加法規(guī)則：P(A B)=P(A)+P(B)-P(A B) 貝葉斯法則：貝葉斯法則：P(h|D)=P(D|h)P(h)/P(D) 全概率法則：如果事件全概率法則：如果事件A1.An互斥，且滿足互斥，且滿足 則則 n i ii APABPBP 1 )()|()( 1 1 n i i AP)( 貝葉斯法則貝葉斯法則 l貝葉斯法則為計(jì)算給定訓(xùn)練數(shù)

8、據(jù)下任一假設(shè)的 后驗(yàn)概率提供了原則性方法，因此可以直接將 其作為一個(gè)基本的學(xué)習(xí)方法：計(jì)算每個(gè)假設(shè)的 概率，再輸出其中概率最大的。 2 極大似然與最小誤差平方假設(shè)極大似然與最小誤差平方假設(shè) 某些學(xué)習(xí)算法即使沒有顯式地使用貝葉斯規(guī)則，某些學(xué)習(xí)算法即使沒有顯式地使用貝葉斯規(guī)則， 或以某種形式計(jì)算概率，但它們或以某種形式計(jì)算概率，但它們輸出的結(jié)果符合輸出的結(jié)果符合 貝葉斯原理貝葉斯原理，是一個(gè)，是一個(gè)MAP假設(shè)；假設(shè)； 在特定前提下，任一學(xué)習(xí)算法如果使輸出的假設(shè)在特定前提下，任一學(xué)習(xí)算法如果使輸出的假設(shè) 預(yù)測(cè)和訓(xùn)練數(shù)據(jù)之間的誤差平方和最小化，它將預(yù)測(cè)和訓(xùn)練數(shù)據(jù)之間的誤差平方和最小化，它將 輸出一極大似

9、然假設(shè)輸出一極大似然假設(shè)； 對(duì)于許多神經(jīng)網(wǎng)絡(luò)和曲線擬合的方法，如果它們對(duì)于許多神經(jīng)網(wǎng)絡(luò)和曲線擬合的方法，如果它們 試圖在訓(xùn)練數(shù)據(jù)上使誤差平方和最小化，此結(jié)論試圖在訓(xùn)練數(shù)據(jù)上使誤差平方和最小化，此結(jié)論 提供了提供了基于貝葉斯的理論依據(jù)基于貝葉斯的理論依據(jù)。 最小誤差平方假設(shè)最小誤差平方假設(shè) 學(xué)習(xí)器學(xué)習(xí)器L工作在工作在實(shí)例空間實(shí)例空間X和和假設(shè)空間假設(shè)空間H上上 ，H中的假設(shè)為中的假設(shè)為X上定義的某種實(shí)數(shù)值函上定義的某種實(shí)數(shù)值函 數(shù)；數(shù)； L面臨的問題是學(xué)習(xí)一個(gè)從面臨的問題是學(xué)習(xí)一個(gè)從H中抽取出的中抽取出的 未知目標(biāo)函數(shù)未知目標(biāo)函數(shù)f，給定，給定m個(gè)訓(xùn)練樣例的集個(gè)訓(xùn)練樣例的集 合，每個(gè)樣例的目標(biāo)值

10、被某隨機(jī)噪聲干擾合，每個(gè)樣例的目標(biāo)值被某隨機(jī)噪聲干擾 ，此隨機(jī)噪聲服從正態(tài)分布；，此隨機(jī)噪聲服從正態(tài)分布； 最小誤差平方假設(shè)最小誤差平方假設(shè) 每個(gè)訓(xùn)練樣例是序偶每個(gè)訓(xùn)練樣例是序偶 ，di=f(xi)+ei， ei是代表噪聲的隨機(jī)變量，假定是代表噪聲的隨機(jī)變量，假定ei的值是的值是 獨(dú)立抽取的，并且它們的分布服從獨(dú)立抽取的，并且它們的分布服從0均值均值 的正態(tài)分布；的正態(tài)分布； 學(xué)習(xí)器的任務(wù)是在所有假設(shè)有相等的先驗(yàn)學(xué)習(xí)器的任務(wù)是在所有假設(shè)有相等的先驗(yàn) 概率前提下，輸出極大似然假設(shè)（即概率前提下，輸出極大似然假設(shè)（即 MAP假設(shè)）。假設(shè)）。 最小誤差平方假設(shè)最小誤差平方假設(shè) 最小誤差平方假設(shè)最小誤

11、差平方假設(shè) l假定有一固定的訓(xùn)練實(shí)例集合，因此只考假定有一固定的訓(xùn)練實(shí)例集合，因此只考 慮相應(yīng)的目標(biāo)值序列慮相應(yīng)的目標(biāo)值序列D=，且，且 di=f(xi)+ei。 l假定訓(xùn)練樣例是相互獨(dú)立的，給定假定訓(xùn)練樣例是相互獨(dú)立的，給定h時(shí)，時(shí)， 可將可將P(D|h)寫成各寫成各p(di|h)的積：的積： m i i Hh ML hdph 1 )|(maxarg 最小誤差平方假設(shè)最小誤差平方假設(shè) l如果誤差如果誤差ei服從服從0均值和未知方差均值和未知方差 2的正態(tài)的正態(tài) 分布，那么每個(gè)分布，那么每個(gè)di服從均值為服從均值為f(xi)，方差不，方差不 變的正態(tài)分布。因此，變的正態(tài)分布。因此，p(di|h

12、)可寫為方差可寫為方差 2、均值、均值f(xi)的正態(tài)分布的正態(tài)分布； l概率概率di的表達(dá)式是在的表達(dá)式是在h為目標(biāo)函數(shù)為目標(biāo)函數(shù)f的正確描的正確描 述條件下的，所以述條件下的，所以替換替換 =f(xi)=h(xi)。 最小誤差平方假設(shè)最小誤差平方假設(shè) m i ii Hh m i ii Hh m i ii Hh )x(hd( m i Hh m i )d( Hh ML )x(hd(minarg )x(hd(maxarg )x(hd(lnmaxarg emaxarg emaxargh ii i 1 2 1 2 2 1 2 22 2 1 1 2 1 2 1 2 2 1 2 1 2 1 2 1 2

13、1 2 2 2 2 最小誤差平方假設(shè)最小誤差平方假設(shè) 上式說明了極大似然假設(shè)等價(jià)于使訓(xùn)練值上式說明了極大似然假設(shè)等價(jià)于使訓(xùn)練值 和假設(shè)預(yù)測(cè)值之間誤差的平方和最小的那和假設(shè)預(yù)測(cè)值之間誤差的平方和最小的那 個(gè)假設(shè)。個(gè)假設(shè)。 這個(gè)結(jié)論的前提是：訓(xùn)練值等于真實(shí)目標(biāo)這個(gè)結(jié)論的前提是：訓(xùn)練值等于真實(shí)目標(biāo) 值加上隨機(jī)噪聲，其中隨機(jī)噪聲從一個(gè)均值加上隨機(jī)噪聲，其中隨機(jī)噪聲從一個(gè)均 值為值為0的正態(tài)分布中獨(dú)立抽取。的正態(tài)分布中獨(dú)立抽取。 采用正態(tài)分布的合理性采用正態(tài)分布的合理性 p數(shù)學(xué)計(jì)算的簡(jiǎn)潔性；數(shù)學(xué)計(jì)算的簡(jiǎn)潔性； p對(duì)許多物理系統(tǒng)的噪聲都有良好的近似；對(duì)許多物理系統(tǒng)的噪聲都有良好的近似； p中心極限定理顯示

14、，足夠多的獨(dú)立同分布隨機(jī)中心極限定理顯示，足夠多的獨(dú)立同分布隨機(jī) 變量的和服從正態(tài)分布；變量的和服從正態(tài)分布； p由許多獨(dú)立同分布的因素的和所生成的噪聲將由許多獨(dú)立同分布的因素的和所生成的噪聲將 成為正態(tài)分布。成為正態(tài)分布。 3 貝葉斯最優(yōu)分類器貝葉斯最優(yōu)分類器 l給定訓(xùn)練數(shù)據(jù)，最可能的假設(shè)是什么？給定訓(xùn)練數(shù)據(jù)，最可能的假設(shè)是什么？ l給定訓(xùn)練數(shù)據(jù)，對(duì)新實(shí)例的最可能的分類是什給定訓(xùn)練數(shù)據(jù)，對(duì)新實(shí)例的最可能的分類是什 么？么？ l第二個(gè)問題的解決可以將第一個(gè)問題的結(jié)果（第二個(gè)問題的解決可以將第一個(gè)問題的結(jié)果（ MAP）應(yīng)用到新實(shí)例上得到；）應(yīng)用到新實(shí)例上得到； l還存在更好的算法還存在更好的算法

15、. 一個(gè)例子一個(gè)例子 l一個(gè)包含三個(gè)假設(shè)一個(gè)包含三個(gè)假設(shè)h1, h2, h3的假設(shè)空間；的假設(shè)空間； l假定已知訓(xùn)練數(shù)據(jù)時(shí)三個(gè)假設(shè)的后驗(yàn)概率分別是假定已知訓(xùn)練數(shù)據(jù)時(shí)三個(gè)假設(shè)的后驗(yàn)概率分別是 0.4, 0.3, 0.3，因此，因此h1為為MAP假設(shè)。假設(shè)。 l若一新實(shí)例若一新實(shí)例x被被h1分類為正，被分類為正，被h2和和h3分類為反；分類為反； l計(jì)算所有假設(shè)，計(jì)算所有假設(shè)，x為正例的概率為為正例的概率為0.4，為反例的，為反例的 概率為概率為0.6； l這時(shí)最可能的分類與這時(shí)最可能的分類與MAP假設(shè)生成的分類不同假設(shè)生成的分類不同。 貝葉斯最優(yōu)分類器貝葉斯最優(yōu)分類器 l一般而言，一般而言，新實(shí)

16、例的最可能分類可通過合新實(shí)例的最可能分類可通過合 并所有假設(shè)的預(yù)測(cè)得到，權(quán)重為其后驗(yàn)概并所有假設(shè)的預(yù)測(cè)得到，權(quán)重為其后驗(yàn)概 率。率。 l如果新實(shí)例的可能分類可取某集合如果新實(shí)例的可能分類可取某集合V中的中的 任一值任一值vj，那么概率，那么概率P(vj|D)為新實(shí)例分類為新實(shí)例分類 為為vj的概率的概率 Hh iijj i DhPhvPDvP)|()|()|( 貝葉斯最優(yōu)分類器貝葉斯最優(yōu)分類器 u新實(shí)例的最優(yōu)分類為使P(vj|D)最大的vj值 Hh iij Vv i j DhPhvP)|()|(maxarg 貝葉斯最優(yōu)分類器貝葉斯最優(yōu)分類器-示例示例 u新實(shí)例的可能分類集合為新實(shí)例的可能分類集

17、合為V=+,- uP(h1|D)=0.4, P(-|h1)=0, P(+|h1)=1 uP(h2|D)=0.3, P(-|h2)=1, P(+|h2)=0 uP(h3|D)=0.3, P(-|h3)=1, P(+|h2)=0 40.)|()|( Hh ii i DhPhP Hh iij Hhv i ij DhPhvP)|()|(maxarg , 60.)|()|( Hh ii i DhPhP 貝葉斯最優(yōu)分類器貝葉斯最優(yōu)分類器 使用相同的假設(shè)空間和相同的先驗(yàn)概率，使用相同的假設(shè)空間和相同的先驗(yàn)概率， 沒有其他方法能比其平均性能更好。貝葉沒有其他方法能比其平均性能更好。貝葉 斯最優(yōu)分類器在給定可用

18、數(shù)據(jù)、假設(shè)空間斯最優(yōu)分類器在給定可用數(shù)據(jù)、假設(shè)空間 及這些假設(shè)的先驗(yàn)概率下使新實(shí)例被正確及這些假設(shè)的先驗(yàn)概率下使新實(shí)例被正確 分類的可能性達(dá)到最大分類的可能性達(dá)到最大 Gibbs算法算法 貝葉斯最優(yōu)分類器能從給定訓(xùn)練數(shù)據(jù)中獲貝葉斯最優(yōu)分類器能從給定訓(xùn)練數(shù)據(jù)中獲 得最好的性能，但算法的開銷很大。得最好的性能，但算法的開銷很大。 一個(gè)替代的、非最優(yōu)的方法是一個(gè)替代的、非最優(yōu)的方法是Gibbs算法：算法： p按照按照H上的后驗(yàn)概率分布，從上的后驗(yàn)概率分布，從H中隨機(jī)選擇中隨機(jī)選擇 假設(shè)假設(shè)h； p使用使用h來預(yù)言下一個(gè)實(shí)例來預(yù)言下一個(gè)實(shí)例x的分類。的分類。 Gibbs算法算法 l在一定條件下，在一定

19、條件下，Gibbs算法的誤分類率的期算法的誤分類率的期 望值最多為貝葉斯最優(yōu)分類器的望值最多為貝葉斯最優(yōu)分類器的兩倍兩倍。確。確 切地講，期望值是在隨機(jī)抽取的目標(biāo)概念切地講，期望值是在隨機(jī)抽取的目標(biāo)概念 上作出的，抽取過程按照學(xué)習(xí)器假定的先上作出的，抽取過程按照學(xué)習(xí)器假定的先 驗(yàn)概率。驗(yàn)概率。 樸素貝葉斯分類器樸素貝葉斯分類器(Naive Bayes Classifier) l學(xué)習(xí)任務(wù)：學(xué)習(xí)任務(wù)：每個(gè)實(shí)例每個(gè)實(shí)例x可由可由屬性值的合取屬性值的合取描述描述 ，而目標(biāo)函數(shù)，而目標(biāo)函數(shù)f(x)從某有限集合從某有限集合V中取值。中取值。 l貝葉斯方法的新實(shí)例分類目標(biāo)是在給定描述貝葉斯方法的新實(shí)例分類目

20、標(biāo)是在給定描述 實(shí)例的屬性值實(shí)例的屬性值下，得到最可能的目下，得到最可能的目 標(biāo)值標(biāo)值vMAP： ),.,|(maxarg nj v MAP aavPv j 1 樸素貝葉斯分類器樸素貝葉斯分類器 )()|,.,(maxarg ),.,( )()|,.,( maxarg jjn Vv n jjn Vv MAP vPvaaP aaP vPvaaP v j j 1 1 1 樸素貝葉斯分類器樸素貝葉斯分類器 l基于訓(xùn)練數(shù)據(jù)估計(jì)兩個(gè)數(shù)據(jù)項(xiàng)的值基于訓(xùn)練數(shù)據(jù)估計(jì)兩個(gè)數(shù)據(jù)項(xiàng)的值 估計(jì)估計(jì)P(vj)很容易：計(jì)算每個(gè)目標(biāo)值很容易：計(jì)算每個(gè)目標(biāo)值vj出現(xiàn)在訓(xùn)出現(xiàn)在訓(xùn) 練數(shù)據(jù)中的頻率。練數(shù)據(jù)中的頻率。 u估計(jì)估計(jì)P(

21、a1,.an|vj)遇到數(shù)據(jù)稀疏問題，除非有一遇到數(shù)據(jù)稀疏問題，除非有一 個(gè)非常大的訓(xùn)練數(shù)據(jù)集，否則無法獲得可靠的個(gè)非常大的訓(xùn)練數(shù)據(jù)集，否則無法獲得可靠的 估計(jì)。估計(jì)。 樸素貝葉斯分類器樸素貝葉斯分類器 u樸素貝葉斯分類器引入一個(gè)簡(jiǎn)單的假定避免樸素貝葉斯分類器引入一個(gè)簡(jiǎn)單的假定避免 數(shù)據(jù)稀疏問題，數(shù)據(jù)稀疏問題，在給定目標(biāo)值時(shí)，屬性值之在給定目標(biāo)值時(shí)，屬性值之 間相互條件獨(dú)立間相互條件獨(dú)立 u樸素貝葉斯分類器的定義：樸素貝葉斯分類器的定義： i jij Vv NB vaPvPv j )|()(maxarg i jijn vaPvaaP)|()|,.,( 1 樸素貝葉斯分類器樸素貝葉斯分類器 l從

22、訓(xùn)練數(shù)據(jù)中估計(jì)不同從訓(xùn)練數(shù)據(jù)中估計(jì)不同P(ai|vj)項(xiàng)的數(shù)量比要估項(xiàng)的數(shù)量比要估 計(jì)計(jì)P(a1,.,an|vj)項(xiàng)所需的量小得多；項(xiàng)所需的量小得多； l只要條件獨(dú)立性得到滿足，樸素貝葉斯分類只要條件獨(dú)立性得到滿足，樸素貝葉斯分類 vNB等于等于MAP分類，否則是近似；分類，否則是近似； l樸素貝葉斯分類器與其他已介紹的學(xué)習(xí)方法的樸素貝葉斯分類器與其他已介紹的學(xué)習(xí)方法的 一個(gè)區(qū)別：沒有明確地搜索可能假設(shè)空間的過一個(gè)區(qū)別：沒有明確地搜索可能假設(shè)空間的過 程（假設(shè)的形成不需要搜索，只是簡(jiǎn)單地計(jì)算程（假設(shè)的形成不需要搜索，只是簡(jiǎn)單地計(jì)算 訓(xùn)練樣例中不同數(shù)據(jù)組合的出現(xiàn)頻率）。訓(xùn)練樣例中不同數(shù)據(jù)組合的出

23、現(xiàn)頻率）。 示例示例 DayOutlookTemperatureHumidityWindPlay Tennis D1SunnyHotHighWeakNo D2SunnyHotHighStrongNo D3OvercastHotHighWeakYes D4RainMildHighWeakYes D5RainCoolNormalWeakNo D6RainCoolNormalStrongYes D7OvercastCoolNormalStrongYes D8SunnyMildHighWeakNo D9SunnyCoolNormalWeakYes D10RainMildNormalWeakYes D1

24、1SunnyMildNormalStrongYes D12OvercastMildHighStrongYes D13OvercastHotNormalWeakYes D14RainMildHighStrongNo 示例示例 )|()|()|()|()(maxarg)|()(maxarg , jjjjj noyesv i jij noyesv NB vstrongPvhighPvcoolPvsunnyPvPvaPvPv jj u表中提供了目標(biāo)概念表中提供了目標(biāo)概念Play Tennis的的14個(gè)訓(xùn)練樣例，給新個(gè)訓(xùn)練樣例，給新 實(shí)例實(shí)例分類分類 u計(jì)算出上式需要的概率值計(jì)算出上式需要的概率值 lP

25、(yes)=9/14=0.64 lP(no)=5/14=0.36 lP(strong|yes)=3/9=0.33 lP(strong|no)=3/5=0.60 l. )|()|()|()|()(maxarg )|()(maxarg , , jjjjj noyesv i jij noyesv NB vstrongPvhighPvcoolPvsunnyPvP vaPvPv j j 示例示例 uvNB lP(yes) P(sunny|yes) P(cool|yes) P(high|yes) P(strong|yes)=0.0053 lP(no) P(sunny|no) P(cool|no) P(hi

26、gh|no) P(strong|no)=0.0206 lvNB =no u歸一化歸一化 0.0206/(0.0206+0.0053)=0.795 4 EM算法算法 在許多實(shí)際的學(xué)習(xí)問題框架中，相關(guān)實(shí)例特征在許多實(shí)際的學(xué)習(xí)問題框架中，相關(guān)實(shí)例特征 中只有一部分可觀察到中只有一部分可觀察到 已有許多方法被提出來處理存在未觀察到變量已有許多方法被提出來處理存在未觀察到變量 的問題的問題 l如果某些變量有時(shí)能觀察到，有時(shí)不能，那么可以如果某些變量有時(shí)能觀察到，有時(shí)不能，那么可以 用觀察到該變量的實(shí)例去預(yù)測(cè)未觀察到的實(shí)例中的用觀察到該變量的實(shí)例去預(yù)測(cè)未觀察到的實(shí)例中的 變量的值變量的值 EM算法算法 u

27、EM算法是存在隱含變量時(shí)廣泛使用的一種學(xué)算法是存在隱含變量時(shí)廣泛使用的一種學(xué) 習(xí)方法，可用于變量的值從來沒有被直接觀察習(xí)方法，可用于變量的值從來沒有被直接觀察 到的情形，只要這些變量所遵循的概率分布的到的情形，只要這些變量所遵循的概率分布的 一般形式已知一般形式已知 用于貝葉斯網(wǎng)的訓(xùn)練用于貝葉斯網(wǎng)的訓(xùn)練 用于馬爾可夫模型的訓(xùn)練用于馬爾可夫模型的訓(xùn)練 示例：估計(jì)示例：估計(jì)k k個(gè)高斯分布的均值個(gè)高斯分布的均值 n考慮考慮D是一個(gè)實(shí)例集合，它由是一個(gè)實(shí)例集合，它由k個(gè)不同正態(tài)個(gè)不同正態(tài) 分布的混合所得分布生成分布的混合所得分布生成 n每個(gè)實(shí)例使用一個(gè)兩步驟的過程形成：每個(gè)實(shí)例使用一個(gè)兩步驟的過程形

28、成： 首先，隨機(jī)選擇首先，隨機(jī)選擇k個(gè)正態(tài)分布中的一個(gè)個(gè)正態(tài)分布中的一個(gè) 其次，隨機(jī)變量其次，隨機(jī)變量xi按照此選擇的分布生成按照此選擇的分布生成 示例示例 u考慮一個(gè)簡(jiǎn)單情形：考慮一個(gè)簡(jiǎn)單情形： 單個(gè)正態(tài)分布的選擇基于均勻的概率進(jìn)行，且單個(gè)正態(tài)分布的選擇基于均勻的概率進(jìn)行，且k 個(gè)正態(tài)分布有相同的方差；個(gè)正態(tài)分布有相同的方差； 學(xué)習(xí)任務(wù)：輸出一個(gè)假設(shè)學(xué)習(xí)任務(wù)：輸出一個(gè)假設(shè)h=，描述，描述k 個(gè)分布中每個(gè)分布的均值，找到極大似然假設(shè)個(gè)分布中每個(gè)分布的均值，找到極大似然假設(shè) ，即使得，即使得p(D|h)最大化的假設(shè)。最大化的假設(shè)。 隱藏變量隱藏變量 u當(dāng)給定從一個(gè)正態(tài)分布中抽取的數(shù)據(jù)實(shí)例當(dāng)給定從

29、一個(gè)正態(tài)分布中抽取的數(shù)據(jù)實(shí)例 x1,.,xm時(shí)，很容易計(jì)算該分布的均值的時(shí)，很容易計(jì)算該分布的均值的 極大似然假設(shè)：極大似然假設(shè)： u涉及涉及k個(gè)不同正態(tài)分布，而且不知道哪個(gè)實(shí)個(gè)不同正態(tài)分布，而且不知道哪個(gè)實(shí) 例是哪個(gè)分布產(chǎn)生的例是哪個(gè)分布產(chǎn)生的。這是一個(gè)涉及。這是一個(gè)涉及隱藏隱藏 變量變量的典型例子。的典型例子。 m i i m i iML x m x 11 2 1 )(minarg 兩個(gè)正態(tài)分布的混合兩個(gè)正態(tài)分布的混合 示例示例 u每個(gè)實(shí)例的完整描述是三元組每個(gè)實(shí)例的完整描述是三元組， 其中其中xi是第是第i個(gè)實(shí)例的觀測(cè)值，個(gè)實(shí)例的觀測(cè)值，zi1和和zi2表示表示 哪個(gè)正態(tài)分布被用來產(chǎn)生哪

30、個(gè)正態(tài)分布被用來產(chǎn)生xi，是隱藏變量。，是隱藏變量。 uEM算法根據(jù)當(dāng)前假設(shè)算法根據(jù)當(dāng)前假設(shè)，不斷地再，不斷地再 估計(jì)隱藏變量估計(jì)隱藏變量zij的期望值，然后用這些隱藏的期望值，然后用這些隱藏 變量的期望值重新計(jì)算極大似然假設(shè)。變量的期望值重新計(jì)算極大似然假設(shè)。 示例示例 n先將假設(shè)初始化為先將假設(shè)初始化為h= n計(jì)算每個(gè)隱藏變量計(jì)算每個(gè)隱藏變量zij的期望值的期望值Ezij，假定當(dāng)前，假定當(dāng)前 假設(shè)假設(shè)h=成立；成立； n計(jì)算一個(gè)新的極大似然假設(shè)計(jì)算一個(gè)新的極大似然假設(shè)h= ，假，假 定每個(gè)隱藏變量定每個(gè)隱藏變量zij所取值是第一步得到的期望所取值是第一步得到的期望 值值E zij。將假設(shè)替

31、換為。將假設(shè)替換為h= ，然后循，然后循 環(huán)。環(huán)。 示例：示例：步驟步驟1 Ezij正是實(shí)例正是實(shí)例xi由第由第j個(gè)正態(tài)分布生成的概個(gè)正態(tài)分布生成的概 率率 2 1 2 1 2 1 2 1 2 2 2 2 n x x n ni ji ij ni ji e e xxp xxp zE )( )( )|( )|( 示例：示例：步驟步驟2 使用第一步得到的使用第一步得到的Ezij來導(dǎo)出一新的極大來導(dǎo)出一新的極大 似然假設(shè)似然假設(shè) m i ij m i iij j zE xzE 1 1 示例示例 n第二步中的表達(dá)式類似于單一正態(tài)分布均第二步中的表達(dá)式類似于單一正態(tài)分布均 值的計(jì)算，只是變成了加權(quán)樣本均值

32、。值的計(jì)算，只是變成了加權(quán)樣本均值。 nEM算法的要點(diǎn)：算法的要點(diǎn)：當(dāng)前的假設(shè)用于估計(jì)未知當(dāng)前的假設(shè)用于估計(jì)未知 變量，而這些變量的期望值再被用于改進(jìn)變量，而這些變量的期望值再被用于改進(jìn) 假設(shè)。假設(shè)。 n可以證明：算法的每一次循環(huán)中，可以證明：算法的每一次循環(huán)中，EM算法算法 能使似然能使似然P(D|h)增加，除非增加，除非P(D|h)達(dá)到局部達(dá)到局部 最大。因此算法收斂到一個(gè)局部最大似然最大。因此算法收斂到一個(gè)局部最大似然 假設(shè)。假設(shè)。 EM算法的一般表述算法的一般表述 l一般地，令待估計(jì)參數(shù)是一般地，令待估計(jì)參數(shù)是 ，全部數(shù)據(jù)，全部數(shù)據(jù) Y=X Z，其中，其中X是可觀察數(shù)據(jù)，是可觀察數(shù)據(jù)，

33、Z是未觀察是未觀察 數(shù)據(jù)。數(shù)據(jù)。 lZ可看作一個(gè)隨機(jī)變量，它的概率分布依賴可看作一個(gè)隨機(jī)變量，它的概率分布依賴 于參數(shù)于參數(shù) 和已知數(shù)據(jù)和已知數(shù)據(jù)X。 lY也是一個(gè)隨機(jī)變量，因?yàn)樗呻S機(jī)變量也是一個(gè)隨機(jī)變量，因?yàn)樗呻S機(jī)變量Z 定義。定義。 EM算法的一般表述算法的一般表述 nEM算法通過搜尋使算法通過搜尋使ElnP(Y|h)最大的最大的h來尋找來尋找 極大似然假設(shè)極大似然假設(shè)h，其合理性是：，其合理性是： lP(Y|h)是給定假設(shè)是給定假設(shè)h下全部數(shù)據(jù)下全部數(shù)據(jù)Y的似然度，因此找到的似然度，因此找到 使得這個(gè)值最大的使得這個(gè)值最大的h是合理的；是合理的； l對(duì)數(shù)對(duì)數(shù)lnP(Y|h)最大化也使

34、最大化也使P(Y|h)最大化；最大化； l由于由于Y是一個(gè)隨機(jī)變量，因此是一個(gè)隨機(jī)變量，因此P(Y|h)無法計(jì)算，轉(zhuǎn)而計(jì)無法計(jì)算，轉(zhuǎn)而計(jì) 算它的期望值算它的期望值ElnP(Y|h)； nY的概率分布由待估計(jì)的參數(shù)決定，的概率分布由待估計(jì)的參數(shù)決定，EM算法使用算法使用 當(dāng)前假設(shè)當(dāng)前假設(shè)h代替實(shí)際參數(shù)，來估計(jì)代替實(shí)際參數(shù)，來估計(jì)Y的概率分布。的概率分布。 EM算法的一般形式算法的一般形式 u定義函數(shù)定義函數(shù) Q(h|h)=ElnP(Y|h)|h,X EM算法的一般形式算法的一般形式 u重復(fù)下面的步驟，直至收斂重復(fù)下面的步驟，直至收斂 l估計(jì)估計(jì)(Expectation)步驟：使用當(dāng)前假設(shè)步驟：使

35、用當(dāng)前假設(shè)h和觀和觀 察到的數(shù)據(jù)察到的數(shù)據(jù)X來估計(jì)來估計(jì)Y上的概率分布以計(jì)算上的概率分布以計(jì)算 Q(h|h): Q(h|h)ElnP(Y|h)|h,X l最大化最大化(Maximization)步驟：將假設(shè)步驟：將假設(shè)h替換為使替換為使 Q函數(shù)最大化的假設(shè)函數(shù)最大化的假設(shè)h: hargmaxhQ(h|h) n當(dāng)函數(shù)當(dāng)函數(shù)Q連續(xù)時(shí)，連續(xù)時(shí)，EM算法收斂到似然函數(shù)算法收斂到似然函數(shù) P(Y|h)的一個(gè)不動(dòng)點(diǎn)，它保證收斂到一個(gè)局的一個(gè)不動(dòng)點(diǎn)，它保證收斂到一個(gè)局 部最大值。部最大值。 K均值算法推導(dǎo)均值算法推導(dǎo) u問題框架問題框架 要估計(jì)要估計(jì)k個(gè)正態(tài)分布的均值個(gè)正態(tài)分布的均值 = 觀察到的數(shù)據(jù)是觀察

36、到的數(shù)據(jù)是X= 隱藏變量隱藏變量Z=表示表示k個(gè)正態(tài)分布中哪個(gè)正態(tài)分布中哪 一個(gè)生成一個(gè)生成xi K均值算法推導(dǎo)均值算法推導(dǎo) u單個(gè)實(shí)例的概率單個(gè)實(shí)例的概率 k j jiij xz ikiii ehzzxphyp 1 2 2 2 1 2 1 2 1 )( ) |,.,() |( K均值算法推導(dǎo)均值算法推導(dǎo) u所有實(shí)例的概率的對(duì)數(shù)所有實(shí)例的概率的對(duì)數(shù) m i k j jiij m i i m i i xz hyp hyphYP 11 2 2 2 1 1 2 1 2 1 )(ln ) |(ln ) |(ln) |(ln K均值算法推導(dǎo)均值算法推導(dǎo) u計(jì)算期望值計(jì)算期望值 m i k j jiij

37、m i k j jiij xzE xzEhYPE 11 2 2 2 11 2 2 2 2 1 2 1 2 1 2 1 )(ln )(ln)|(ln K均值算法推導(dǎo)均值算法推導(dǎo) u求使求使Q函數(shù)最大的假設(shè)函數(shù)最大的假設(shè) m i k j j iij h m i k j j iij h h xzEminarg xzElnmaxarg)h| h(Qmaxarg 11 2 11 2 22 2 1 2 1 K均值算法推導(dǎo)均值算法推導(dǎo) u解上式得到解上式得到 u其中其中 m i ij m i iij j zE xzE 1 1 k n )x( )x( ij ji ji e e zE 1 2 1 2 2 1 2

38、 2 2 5 Bayes網(wǎng)與網(wǎng)與Markov鏈鏈 n條件獨(dú)立性條件獨(dú)立性 令令X, Y和和Z為為3個(gè)離散值隨機(jī)變量，當(dāng)給定個(gè)離散值隨機(jī)變量，當(dāng)給定Z 值時(shí)值時(shí)X服從的概率分布獨(dú)立于服從的概率分布獨(dú)立于Y的值，稱的值，稱X在在 給定給定Z時(shí)條件獨(dú)立于時(shí)條件獨(dú)立于Y，即，即 簡(jiǎn)寫：簡(jiǎn)寫：P(X|Y,Z)=P(X|Z) )|(),|(, kikjikji zZxXPzZyYxXPzyx 條件獨(dú)立性條件獨(dú)立性 u變量集合的條件獨(dú)立性變量集合的條件獨(dú)立性 下面等式成立時(shí)，稱變量集合下面等式成立時(shí)，稱變量集合X1.Xl在給定變量集在給定變量集 合合Z1.Zn時(shí)條件獨(dú)立于變量集合時(shí)條件獨(dú)立于變量集合Y1.Ym ).|.().,