第6章-貝葉斯學(xué)習(xí)與EM算法

第6章貝葉斯學(xué)習(xí)與EM算法(BayesianLearningandEMAlgorithm

)概述貝葉斯推理提供了一種概率手段，基于如下的假定：待考察的量遵循某概率分布，且可根據(jù)這些概率及已觀察到的數(shù)據(jù)進(jìn)行推理，以作出最優(yōu)的決策。貝葉斯推理為衡量多個(gè)假設(shè)的置信度提供了定量的方法。貝葉斯推理為直接操作概率的學(xué)習(xí)算法提供了基礎(chǔ)，也為其它算法的分析提供了理論框架。簡(jiǎn)介貝葉斯學(xué)習(xí)算法與機(jī)器學(xué)習(xí)相關(guān)的兩個(gè)原因：貝葉斯學(xué)習(xí)算法能夠計(jì)算顯示的假設(shè)概率，比如樸素貝葉斯分類(lèi)器；貝葉斯方法為理解多數(shù)學(xué)習(xí)算法提供了一種有效的手段，而這些算法不一定直接操縱概率數(shù)據(jù)，比如：Find-S候選消除算法神經(jīng)網(wǎng)絡(luò)學(xué)習(xí)：選擇使誤差平方和最小化的神經(jīng)網(wǎng)絡(luò)推導(dǎo)出另一種誤差函數(shù)：交叉熵可分析決策樹(shù)的歸納偏置可考察最小描述長(zhǎng)度原則貝葉斯學(xué)習(xí)方法的特性觀察到的每個(gè)訓(xùn)練樣例可以增量地降低或升高某假設(shè)的估計(jì)概率。而其它算法會(huì)在某個(gè)假設(shè)與任一樣例不一致時(shí)完全去掉該假設(shè)；（最大優(yōu)點(diǎn)）先驗(yàn)知識(shí)可以與觀察數(shù)據(jù)一起決定假設(shè)的最終概率，先驗(yàn)知識(shí)的形式是：1）每個(gè)候選假設(shè)的先驗(yàn)概率；2）每個(gè)可能假設(shè)在可觀察數(shù)據(jù)上的概率分布；貝葉斯方法可允許假設(shè)做出不確定性的預(yù)測(cè)；新的實(shí)例分類(lèi)可由多個(gè)假設(shè)一起做出預(yù)測(cè)，用它們的概率來(lái)加權(quán)；即使在貝葉斯方法計(jì)算復(fù)雜度較高時(shí)，它們?nèi)钥勺鳛橐粋€(gè)最優(yōu)的決策標(biāo)準(zhǔn)衡量其它方法；貝葉斯方法的難度難度之一：需要概率的初始知識(shí)，當(dāng)概率預(yù)先未知時(shí)，可以基于背景知識(shí)、預(yù)先準(zhǔn)備好的數(shù)據(jù)以及基準(zhǔn)分布的假定來(lái)估計(jì)這些概率；難度之二：一般情況下，確定貝葉斯最優(yōu)假設(shè)的計(jì)算代價(jià)比較大（在某些特定情形下，這種計(jì)算代價(jià)可以大大降低）。內(nèi)容安排介紹貝葉斯理論；定義極大似然假設(shè)（ML）和極大后驗(yàn)概率假設(shè)（MAP）；將此概率框架應(yīng)用于分析前面章節(jié)的相關(guān)問(wèn)題和學(xué)習(xí)算法；介紹幾種直接操作概率的學(xué)習(xí)算法；貝葉斯最優(yōu)分類(lèi)器Gibbs算法樸素貝葉斯分類(lèi)器討論EM算法，一類(lèi)參數(shù)估計(jì)的方法。統(tǒng)計(jì)推斷中可用的三種信息

美籍波蘭統(tǒng)計(jì)學(xué)家耐曼(E.L.Lehmann1894－1981)高度概括了在統(tǒng)計(jì)推斷中可用的三種信息：

1．總體信息，即總體分布或所屬分布族給我們的信息。譬如“總體視察指數(shù)分布”或“總體是正態(tài)分布”在統(tǒng)計(jì)推斷中都發(fā)揮重要作用，只要有總體信息，就要想方設(shè)法在統(tǒng)計(jì)推斷中使用2．樣本信息，即樣本提供我們的信息，這是任一種統(tǒng)計(jì)推斷中都需要

3．先驗(yàn)信息，即在抽樣之前有關(guān)統(tǒng)計(jì)推斷的一些信息。譬如，在估計(jì)某產(chǎn)品的不合格率時(shí)，假如工廠保存了過(guò)去抽檢這種產(chǎn)品質(zhì)量的資料，這些資料（包括歷史數(shù)據(jù)）有時(shí)估計(jì)該產(chǎn)品的不合格率是有好處的。這些資料所提供的信息就是一種先驗(yàn)信息。又如某工程師根據(jù)自己多年積累的經(jīng)驗(yàn)對(duì)正在設(shè)計(jì)的某種彩電的平均壽命所提供的估計(jì)也是一種先驗(yàn)信息。由于這種信息是在“試驗(yàn)之前”就已有的，故稱(chēng)為先驗(yàn)信息。假設(shè)Ⅰ

隨機(jī)變量X有一個(gè)密度函數(shù)p（x；θ），其中θ是一個(gè)參數(shù)，不同的θ對(duì)應(yīng)不同的密度函數(shù)，故從貝葉斯觀點(diǎn)看，p（x；θ）是在給定后θ是個(gè)條件密度函數(shù)，因此記為p（x│θ）更恰當(dāng)一些。這個(gè)條件密度能提供我們的有關(guān)的θ信息就是總體信息。假設(shè)Ⅱ

當(dāng)給定θ后，從總體p（x│θ）中隨機(jī)抽取一個(gè)樣本,該樣本中含有θ的有關(guān)信息。這種信息就是樣本信息。貝葉斯公式的密度函數(shù)形式

假設(shè)Ⅲ

對(duì)參數(shù)θ已經(jīng)積累了很多資料，經(jīng)過(guò)分析、整理和加工，可以獲得一些有關(guān)θ的有用信息，這種信息就是先驗(yàn)信息。參數(shù)θ不是永遠(yuǎn)固定在一個(gè)值上，而是一個(gè)事先不能確定的量。從貝葉斯觀點(diǎn)來(lái)看，未知參數(shù)θ是一個(gè)隨機(jī)變量。而描述這個(gè)隨機(jī)變量的分布可從先驗(yàn)信息中歸納出來(lái)，這個(gè)分布稱(chēng)為先驗(yàn)分布，其密度函數(shù)用π（θ）表示。前面的分析總結(jié)如下：人們根據(jù)先驗(yàn)信息對(duì)參數(shù)θ已有一個(gè)認(rèn)識(shí)，這個(gè)認(rèn)識(shí)就是先驗(yàn)分布π（θ）。通過(guò)試驗(yàn)，獲得樣本。從而對(duì)θ的先驗(yàn)分布進(jìn)行調(diào)整，調(diào)整的方法就是使用上面的貝葉斯公式，調(diào)整的結(jié)果就是后驗(yàn)分布。后驗(yàn)分布是三種信息的綜合。獲得后驗(yàn)分布使人們對(duì)θ的認(rèn)識(shí)又前進(jìn)一步，可看出，獲得樣本的的效果是把我們對(duì)θ的認(rèn)識(shí)由π（θ）調(diào)整到

。所以對(duì)θ的統(tǒng)計(jì)推斷就應(yīng)建立在后驗(yàn)分布

的基礎(chǔ)上。貝葉斯法則機(jī)器學(xué)習(xí)的任務(wù)：在給定訓(xùn)練數(shù)據(jù)D時(shí)，確定假設(shè)空間H中的最佳假設(shè)。最佳假設(shè)：一種方法是把它定義為在給定數(shù)據(jù)D以及H中不同假設(shè)的先驗(yàn)概率的有關(guān)知識(shí)下的最可能假設(shè)。貝葉斯理論提供了一種計(jì)算假設(shè)概率的方法，基于假設(shè)的先驗(yàn)概率、給定假設(shè)下觀察到不同數(shù)據(jù)的概率以及觀察到的數(shù)據(jù)本身。先驗(yàn)概率和后驗(yàn)概率用P(h)表示在沒(méi)有訓(xùn)練數(shù)據(jù)前假設(shè)h擁有的初始概率。P(h)被稱(chēng)為h的先驗(yàn)概率；先驗(yàn)概率反映了關(guān)于h是一正確假設(shè)的機(jī)會(huì)的背景知識(shí)；如果沒(méi)有這一先驗(yàn)知識(shí)，可以簡(jiǎn)單地將每一候選假設(shè)賦予相同的先驗(yàn)概率；類(lèi)似地，P(D)表示訓(xùn)練數(shù)據(jù)D的先驗(yàn)概率，P(D|h)表示假設(shè)h成立時(shí)D的概率；機(jī)器學(xué)習(xí)中，我們關(guān)心的是P(h|D)，即給定D時(shí)h的成立的概率，稱(chēng)為h的后驗(yàn)概率。貝葉斯公式貝葉斯公式提供了從先驗(yàn)概率P(h)、P(D)和P(D|h)計(jì)算后驗(yàn)概率P(h|D)的方法；

(6.1)P(h|D)隨著P(h)和P(D|h)的增長(zhǎng)而增長(zhǎng)，隨著P(D)的增長(zhǎng)而減少，即如果D獨(dú)立于h時(shí)被觀察到的可能性越大，那么D對(duì)h的支持度越小。極大后驗(yàn)假設(shè)學(xué)習(xí)器在候選假設(shè)集合H中尋找給定數(shù)據(jù)D時(shí)可能性最大的假設(shè)h，h被稱(chēng)為極大后驗(yàn)假設(shè)（MAP）；確定MAP的方法是用貝葉斯公式計(jì)算每個(gè)候選假設(shè)的后驗(yàn)概率，計(jì)算式如下：

(6.2)

最后一步，去掉了P(D)，因?yàn)樗遣灰蕾?lài)于h的常量。極大似然假設(shè)在某些情況下，可假定H中每個(gè)假設(shè)有相同的先驗(yàn)概率，這樣式子6.2可以進(jìn)一步簡(jiǎn)化，只需考慮P(D|h)來(lái)尋找極大可能假設(shè)。P(D|h)常被稱(chēng)為給定h時(shí)數(shù)據(jù)D的似然度，而使P(D|h)最大的假設(shè)被稱(chēng)為極大似然假設(shè)：假設(shè)空間H可擴(kuò)展為任意的互斥命題集合，只要這些命題的概率之和為1。舉例：一個(gè)醫(yī)療診斷問(wèn)題有兩個(gè)可選的假設(shè)：病人有癌癥、病人無(wú)癌癥可用數(shù)據(jù)來(lái)自化驗(yàn)結(jié)果：正+和負(fù)-有先驗(yàn)知識(shí)：在所有人口中，患病率是0.008對(duì)確實(shí)有病的患者的化驗(yàn)準(zhǔn)確率為98%，對(duì)確實(shí)無(wú)病的患者的化驗(yàn)準(zhǔn)確率為97%總結(jié)如下P(cancer)=0.008,P(cancer)=0.992P(+|cancer)=0.98,P(-|cancer)=0.02P(+|cancer)=0.03,P(-|cancer)=0.97舉例：一個(gè)醫(yī)療診斷問(wèn)題（2）問(wèn)題：假定有一個(gè)新病人，化驗(yàn)結(jié)果為正，是否應(yīng)將病人斷定為有癌癥？求后驗(yàn)概率P(cancer|+)和P(cancer|+)利用式子6.2找到極大后驗(yàn)假設(shè)P(+|cancer)P(cancer)=0.0078P(+|cancer)P(cancer)=0.0298hMAP=cancer確切的后驗(yàn)概率可將上面的結(jié)果歸一化以使它們的和為1P(canner|+)=0.0078/(0.0078+0.0298)=0.21P(cancer|+)=0.79貝葉斯推理的結(jié)果很大程度上依賴(lài)于先驗(yàn)概率，另外不是完全接受或拒絕假設(shè)，只是在觀察到較多的數(shù)據(jù)后增大或減小了假設(shè)的可能性基本概率公式表乘法規(guī)則：P(AB)=P(A|B)P(B)=P(B|A)P(A)加法規(guī)則：P(AB)=P(A)+P(B)-P(AB)貝葉斯法則：P(h|D)=P(D|h)P(h)/P(D)全概率法則：如果事件A1...An互斥，且滿足，

則貝葉斯法則和概念學(xué)習(xí)貝葉斯法則為計(jì)算給定訓(xùn)練數(shù)據(jù)下任一假設(shè)的后驗(yàn)概率提供了原則性方法，因此可以直接將其作為一個(gè)基本的學(xué)習(xí)方法：計(jì)算每個(gè)假設(shè)的概率，再輸出其中概率最大的。這個(gè)方法稱(chēng)為Brute-Force貝葉斯概念學(xué)習(xí)算法。將上面方法與第2章介紹的概念學(xué)習(xí)算法比較，可以看到：在特定條件下，它們學(xué)習(xí)得到相同的假設(shè)，不同的是第2章的方法不明確計(jì)算概率，而且效率更高。Brute-Force貝葉斯概念學(xué)習(xí)概念學(xué)習(xí)問(wèn)題：有限假設(shè)空間H定義在實(shí)例空間X上，任務(wù)是學(xué)習(xí)某個(gè)目標(biāo)概念c。Brute-ForceMAP學(xué)習(xí)算法對(duì)于H中每個(gè)假設(shè)h，計(jì)算后驗(yàn)概率輸出有最高后驗(yàn)概率的假設(shè)上面算法需要較大計(jì)算量，因?yàn)樗?jì)算每個(gè)假設(shè)的后驗(yàn)概率，對(duì)于大的假設(shè)空間顯得不切實(shí)際，但是它提供了一個(gè)標(biāo)準(zhǔn)以判斷其它概念學(xué)習(xí)算法的性能特定情況下的MAP假設(shè)假定訓(xùn)練數(shù)據(jù)D是無(wú)噪聲的，即di=c(xi)目標(biāo)概念c包含在假設(shè)空間H中每個(gè)假設(shè)的先驗(yàn)概率相同求得由于所有假設(shè)的概率之和是1，因此由于訓(xùn)練數(shù)據(jù)無(wú)噪聲，那么給定假設(shè)h時(shí)，與h一致的D的概率為1，不一致的概率為0，因此特定情況下的MAP假設(shè)（2）考慮Brute-ForceMAP算法的第一步h與D不一致，h與D一致，，

VSH,D是關(guān)于D的變型空間（見(jiàn)第2章，即與D一致的假設(shè)集）特定情況下的MAP假設(shè)（3）P(D)的推導(dǎo)

P(D)

圖6-1假設(shè)的概率演化情況如圖6-1所示，初始時(shí)所有假設(shè)具有相同的概率，當(dāng)訓(xùn)練數(shù)據(jù)逐步出現(xiàn)后，不一致假設(shè)的概率變?yōu)?，而整個(gè)概率的和為1，它們均勻分布到剩余的一致假設(shè)中每個(gè)與D一致的假設(shè)都是MAP假設(shè)hP(h|D1,D2)P(h)P(h|D1)hhMAP假設(shè)和一致學(xué)習(xí)器一致學(xué)習(xí)器：如果某個(gè)學(xué)習(xí)器輸出的假設(shè)在訓(xùn)練樣例上為0錯(cuò)誤率，則稱(chēng)為一致學(xué)習(xí)器；如果H上有均勻的先驗(yàn)概率，且訓(xùn)練數(shù)據(jù)是確定性和無(wú)噪聲的，任意一致學(xué)習(xí)器將輸出一個(gè)MAP假設(shè)；Find-S算法按照特殊到一般的順序搜索假設(shè)空間H，并輸出一個(gè)極大特殊的一致假設(shè)，因此可知在上面定義的P(h)和P(D|h)概率分布下，它輸出MAP假設(shè)；更一般地，對(duì)于先驗(yàn)概率偏袒于更特殊假設(shè)的任何概率分布，F(xiàn)ind-S輸出的假設(shè)都是MAP假設(shè)。MAP假設(shè)和一致學(xué)習(xí)器（2）貝葉斯框架提出了一種刻畫(huà)學(xué)習(xí)算法行為的方法，即便該學(xué)習(xí)算法不進(jìn)行概率操作，通過(guò)確定算法輸出最優(yōu)假設(shè)時(shí)使用的概率分布P(h)和P(D|h)，可以刻畫(huà)出算法具有最優(yōu)行為時(shí)的隱含假定；使用貝葉斯方法刻畫(huà)學(xué)習(xí)算法，與揭示學(xué)習(xí)器中的歸納偏置在思想上是類(lèi)似的；在第2章，將學(xué)習(xí)算法的歸納偏置定義為斷言集合B，通過(guò)它可充分地演繹推斷出學(xué)習(xí)器所執(zhí)行的歸納推理結(jié)果，即學(xué)習(xí)器的輸出是由其輸入和隱含的歸納偏置所演繹得出的。MAP假設(shè)和一致學(xué)習(xí)器（3）貝葉斯解釋對(duì)于描述學(xué)習(xí)算法中的隱含假定提供了另一種方法，用基于貝葉斯理論的一個(gè)等效的概率推理系統(tǒng)來(lái)建模；貝葉斯解釋隱含的假定形式為：H上的先驗(yàn)概率由P(h)分布給出，數(shù)據(jù)拒絕或接受假設(shè)的強(qiáng)度由P(D|h)給出；在已知這些假定的概率分布后，一個(gè)基于貝葉斯理論的概率推理系統(tǒng)將產(chǎn)生等效于Find-S、候選消除等算法的輸入-輸出行為；極大似然和最小誤差平方假設(shè)（1）前面分析表明：某些學(xué)習(xí)算法即使沒(méi)有顯示地使用貝葉斯規(guī)則，或以某種形式計(jì)算概率，但它們輸出的結(jié)果符合貝葉斯原理，是一個(gè)MAP假設(shè)；通過(guò)簡(jiǎn)單的貝葉斯分析，可以表明在特定前提下，任一學(xué)習(xí)算法如果使輸出的假設(shè)預(yù)測(cè)和訓(xùn)練數(shù)據(jù)之間的誤差平方和最小化，它將輸出一極大似然假設(shè)；上面結(jié)論的意義是，對(duì)于許多神經(jīng)網(wǎng)絡(luò)和曲線擬合的方法，如果它們?cè)噲D在訓(xùn)練數(shù)據(jù)上使誤差平方和最小化，此結(jié)論提供了基于貝葉斯的理論依據(jù)。極大似然和最小誤差平方假設(shè)（2）問(wèn)題框架：學(xué)習(xí)器L工作在實(shí)例空間X和假設(shè)空間H上，H中的假設(shè)為X上定義的某種實(shí)數(shù)值函數(shù)；L面臨的問(wèn)題是學(xué)習(xí)一個(gè)從H中抽取出的未知目標(biāo)函數(shù)f，給定m個(gè)訓(xùn)練樣例的集合，每個(gè)樣例的目標(biāo)值被某隨機(jī)噪聲干擾，此隨機(jī)噪聲服從正態(tài)分布；更精確地講，每個(gè)訓(xùn)練樣例是序偶<xi,di>，di=f(xi)+ei，ei是代表噪聲的隨機(jī)變量，假定ei的值是獨(dú)立抽取的，并且它們的分布服從0均值的正態(tài)分布；學(xué)習(xí)器的任務(wù)是在所有假設(shè)有相等的先驗(yàn)概率前提下，輸出極大似然假設(shè)（即ML假設(shè)）；極大似然和最小誤差平方假設(shè)（3）用一個(gè)簡(jiǎn)單情況，即線性函數(shù)來(lái)說(shuō)明問(wèn)題。如圖所示，實(shí)線表示線性目標(biāo)函數(shù)f，實(shí)點(diǎn)表示有噪聲的訓(xùn)練樣例集，虛線對(duì)應(yīng)有最小平方訓(xùn)練誤差的假設(shè)hML，即極大似然假設(shè)。對(duì)于e這樣的連續(xù)變量上的概率，使用概率密度表示概率分布，它在所有值上的積分為1，用小寫(xiě)的p表示。有限概率P有時(shí)又稱(chēng)為概率質(zhì)量；概率密度函數(shù)：極大似然和最小誤差平方假設(shè)（4）假定有一固定的訓(xùn)練實(shí)例集合，因此只考慮相應(yīng)的目標(biāo)值序列D=<d1...dm>，這里di=f(xi)+ei。假定訓(xùn)練樣例是相互獨(dú)立的，給定h時(shí)，可將P(D|h)寫(xiě)成各p(di|h)的積如果誤差ei服從0均值和未知方差2的正態(tài)分布，那么每個(gè)di服從均值為f(xi)，方差不變的正態(tài)分布。因此，p(di|h)可寫(xiě)為方差2、均值f(xi)的正態(tài)分布；使用第5章中的正態(tài)分布公式并將相應(yīng)的參數(shù)代入，由于概率di的表達(dá)式是在h為目標(biāo)函數(shù)f的正確描述條件下的，所以替換=f(xi)=h(xi)極大似然和最小誤差平方假設(shè)（5）hML上式說(shuō)明了極大似然假設(shè)等價(jià)于使訓(xùn)練值和假設(shè)預(yù)測(cè)值之間的誤差的平方和最小的那個(gè)假設(shè)；這個(gè)結(jié)論的前提是：訓(xùn)練值等于真實(shí)目標(biāo)值加上隨機(jī)噪聲，其中隨機(jī)噪聲從一個(gè)均值為0的正態(tài)分布中獨(dú)立抽取。采用正態(tài)分布的合理性數(shù)學(xué)計(jì)算的簡(jiǎn)潔性；對(duì)許多物理系統(tǒng)的噪聲都有良好的近似；第5章中心極限定理顯示，足夠多的獨(dú)立同分布隨機(jī)變量的和服從正態(tài)分布；由許多獨(dú)立同分布的因素的和所生成的噪聲將成為正態(tài)分布（當(dāng)然，現(xiàn)實(shí)中不同的分量對(duì)噪聲的貢獻(xiàn)也許不是同分布的）；使誤差平方最小化的方法經(jīng)常被用于神經(jīng)網(wǎng)絡(luò)、曲線擬合及其他許多實(shí)函數(shù)逼近的算法中；上面的分析只考慮了訓(xùn)練樣例的目標(biāo)值中的噪聲，而沒(méi)有考慮實(shí)例屬性值的噪聲。用于預(yù)測(cè)概率的極大似然假設(shè)問(wèn)題框架：學(xué)習(xí)一個(gè)不確定性函數(shù)f:X{0,1}，它有兩個(gè)離散的值輸出；這種不可預(yù)測(cè)性來(lái)源于未能觀察到的因素，導(dǎo)致目標(biāo)函數(shù)的輸出是輸入的概率函數(shù)。學(xué)習(xí)得到的神經(jīng)網(wǎng)絡(luò)（或其它實(shí)函數(shù)學(xué)習(xí)器）的輸出是f(x)=1的概率，表示為：

f’:X[0,1]，即f’=P(f(x)=1)用于預(yù)測(cè)概率的極大似然假設(shè)（2）Brute-Force法首先收集對(duì)x的每個(gè)可能值觀察到的1和0的頻率，然后訓(xùn)練神經(jīng)網(wǎng)絡(luò)，對(duì)每個(gè)x輸出目標(biāo)頻率可以直接從f的訓(xùn)練樣例中訓(xùn)練神經(jīng)網(wǎng)絡(luò)，而且能推導(dǎo)出f’的極大似然假設(shè)D={<x1,d1>...<xm,dm>}

用于預(yù)測(cè)概率的極大似然假設(shè)（3）

hML

（6.13）式子6.13與熵函數(shù)的一般式相似，因此它的負(fù)值常稱(chēng)為交叉熵在神經(jīng)網(wǎng)絡(luò)中梯度搜索以達(dá)到似然最大化前面討論了利用式子6.13求極大似然假設(shè)，現(xiàn)用G(h,D)表示，為神經(jīng)網(wǎng)絡(luò)學(xué)習(xí)推導(dǎo)一個(gè)權(quán)值訓(xùn)練法則，使用梯度上升法使G(h,D)最大化考慮簡(jiǎn)單的情況，假定神經(jīng)網(wǎng)絡(luò)從一個(gè)單層的sigmoid單元建立，則在神經(jīng)網(wǎng)絡(luò)中梯度搜索以達(dá)到似然最大化（2）因?yàn)橐筆(D|h)最大化而不是最小化，因此執(zhí)行梯度上升搜索，而不是梯度下降搜索。與反向傳播更新法則對(duì)比使誤差平方最小化的法則尋找到極大似然假設(shè)的前提是：訓(xùn)練數(shù)據(jù)可以由目標(biāo)函數(shù)值加上正態(tài)分布噪聲來(lái)模擬使交叉熵最小化的法則尋找極大似然假設(shè)基于的前提是：觀察到的布爾值為輸入實(shí)例的概率函數(shù)最小描述長(zhǎng)度準(zhǔn)則奧坎姆剃刀可以概括為：為觀察到的數(shù)據(jù)選擇最短的解釋?zhuān)淮颂幗o出一個(gè)貝葉斯分析，提出最小描述長(zhǎng)度準(zhǔn)則，根據(jù)信息論中的基本概念來(lái)解釋hMAP的定義

(6.16)上式可以解釋為在特定的假設(shè)編碼表示方案上“優(yōu)先選擇短的假設(shè)”最小描述長(zhǎng)度準(zhǔn)則（2）信息論中的編碼理論設(shè)想要為隨機(jī)傳送的消息設(shè)計(jì)一個(gè)編碼，其中遇到消息i的概率是pi感興趣的是，使得傳輸隨機(jī)信息所需的最小期望傳送位數(shù)的編碼直觀上，為使期望的編碼長(zhǎng)度最小，可能性大的消息應(yīng)該賦予較短的編碼Shannon&Weaver證明了最優(yōu)編碼對(duì)消息i的編碼長(zhǎng)度為-log2pi使用代碼C來(lái)編碼消息i所需的位數(shù)被稱(chēng)為消息i關(guān)于C的描述長(zhǎng)度，記為L(zhǎng)C(i)最小描述長(zhǎng)度準(zhǔn)則（3）使用編碼理論的結(jié)論來(lái)解釋等式6.16-log2P(h)是在假設(shè)空間H的最優(yōu)編碼下h的描述長(zhǎng)度。換言之，這是假設(shè)h使用其最優(yōu)表示時(shí)的大小，CH為假設(shè)空間H的最優(yōu)編碼-log2P(D|h)是在給定假設(shè)h時(shí)，訓(xùn)練數(shù)據(jù)D的描述長(zhǎng)度，，CD|h是假定發(fā)送者和接送者都知道假設(shè)h時(shí)描述數(shù)據(jù)D的最優(yōu)編碼因此式子6.16顯示，hMAP是使假設(shè)描述長(zhǎng)度和給定假設(shè)下數(shù)據(jù)描述長(zhǎng)度之和最小化的假設(shè)最小描述長(zhǎng)度準(zhǔn)則：最小描述長(zhǎng)度準(zhǔn)則（4）如果選擇C1為假設(shè)的最優(yōu)編碼CH，C2為最優(yōu)編碼CD|h，那么hMDL=hMAP可將MDL準(zhǔn)則想象為選擇最短的方法來(lái)重新編碼訓(xùn)練數(shù)據(jù)，其中不僅計(jì)算假設(shè)的大小，并且計(jì)算給定假設(shè)時(shí)編碼數(shù)據(jù)的附加開(kāi)銷(xiāo)將MDL準(zhǔn)則應(yīng)用于決策樹(shù)，如何選擇假設(shè)和數(shù)據(jù)的表示C1和C2?對(duì)于C1，很自然地選擇某種明確的決策樹(shù)編碼方法，其中描述長(zhǎng)度隨著樹(shù)中節(jié)點(diǎn)和邊的增長(zhǎng)而增加對(duì)于C2，如果訓(xùn)練分類(lèi)f(xi)與假設(shè)的預(yù)計(jì)相同，那么就不需要傳輸有關(guān)這些樣例的任何信息；如果不同，則要傳輸更正消息最小描述長(zhǎng)度準(zhǔn)則（5）MDL準(zhǔn)則提供了一種方法在假設(shè)的復(fù)雜性和假設(shè)產(chǎn)生錯(cuò)誤的數(shù)量之間進(jìn)行折中，它有可能選擇一個(gè)較短的產(chǎn)生少量錯(cuò)誤的假設(shè)，而不是完美地分類(lèi)訓(xùn)練數(shù)據(jù)的較長(zhǎng)的假設(shè)上面討論自然給出了一種處理數(shù)據(jù)過(guò)度擬合的方法Quinlan&Rivest描述了應(yīng)用MDL準(zhǔn)則選擇決策樹(shù)大小的幾個(gè)實(shí)驗(yàn)，報(bào)告指出，基于MDL的方法產(chǎn)生的決策樹(shù)的精度相當(dāng)于第3章中討論的標(biāo)準(zhǔn)樹(shù)修剪方法分類(lèi)問(wèn)題？能否利用MAP解決分類(lèi)問(wèn)題？假設(shè)類(lèi)別為Ci，其后驗(yàn)概率公式如何表述？如何選取判別函數(shù)？假設(shè)p(x|Ci)為高斯分布，其參數(shù)如何求??？先驗(yàn)概率P（Ci）如何求取？貝葉斯最優(yōu)分類(lèi)器前面我們討論的問(wèn)題是：給定訓(xùn)練數(shù)據(jù)，最可能的假設(shè)是什么？另一個(gè)相關(guān)的更有意義的問(wèn)題是：給定訓(xùn)練數(shù)據(jù)，對(duì)新實(shí)例的最可能的分類(lèi)是什么？顯然，第二個(gè)問(wèn)題的解決可以將第一個(gè)問(wèn)題的結(jié)果（MAP）應(yīng)用到新實(shí)例上得到，還存在更好的算法？貝葉斯最優(yōu)分類(lèi)器（2）例子考慮一個(gè)包含三個(gè)假設(shè)h1,h2,h3的假設(shè)空間。假定已知訓(xùn)練數(shù)據(jù)時(shí)三個(gè)假設(shè)的后驗(yàn)概率分別是0.4,0.3,0.3，因此h1為MAP假設(shè)。若一新實(shí)例x被h1分類(lèi)為正，被h2和h3分類(lèi)為反計(jì)算所有假設(shè)，x為正例的概率為0.4，為反例的概率為0.6因此，這時(shí)最可能的分類(lèi)與MAP假設(shè)生成的分類(lèi)不同——矛盾！貝葉斯最優(yōu)分類(lèi)器（3）一般而言，新實(shí)例的最可能分類(lèi)可通過(guò)合并所有假設(shè)的預(yù)測(cè)得到，用后驗(yàn)概率來(lái)加權(quán)。如果新實(shí)例的可能分類(lèi)可取某集合V中的任一值vj，那么概率P(vj|D)表示新實(shí)例分類(lèi)為vj的概率新實(shí)例的最優(yōu)分類(lèi)為使P(vj|D)最大的vj值，貝葉斯最優(yōu)分類(lèi)器為：（6.18)貝葉斯最優(yōu)分類(lèi)器（4）例子已知：新實(shí)例的可能分類(lèi)集合為V={+,-}P(h1|D)=0.4,P(-|h1)=0,P(+|h1)=1P(h2|D)=0.3,P(-|h2)=1,P(+|h2)=0P(h3|D)=0.3,P(-|h3)=1,P(+|h2)=0因此：

貝葉斯最優(yōu)分類(lèi)器（5）貝葉斯最優(yōu)分類(lèi)器在給定可用數(shù)據(jù)、假設(shè)空間及這些假設(shè)的先驗(yàn)概率下使新實(shí)例被正確分類(lèi)的可能性達(dá)到最大；貝葉斯最優(yōu)分類(lèi)器的一個(gè)屬性：它所做的分類(lèi)可以對(duì)應(yīng)于H中不存在的假設(shè)；使用式子6.18來(lái)分類(lèi)X中的每個(gè)實(shí)例，按此定義的實(shí)例標(biāo)注不一定對(duì)應(yīng)于H中的任一單個(gè)假設(shè)h對(duì)實(shí)例的標(biāo)注；將貝葉斯分類(lèi)器看成是不同于假設(shè)空間H的另一空間H’，在其上應(yīng)用貝葉斯公式。H’有效地包含了一組假設(shè)，它能在H中多個(gè)假設(shè)的線性組合所作的預(yù)言中進(jìn)行比較。Gibbs算法貝葉斯最優(yōu)分類(lèi)器能從給定訓(xùn)練數(shù)據(jù)中獲得最好的性能，但算法的開(kāi)銷(xiāo)很大；一個(gè)替代的、非最優(yōu)的方法是Gibbs算法，定義如下：按照H上的后驗(yàn)概率分布，從H中隨機(jī)選擇假設(shè)h使用h來(lái)預(yù)言下一個(gè)實(shí)例x的分類(lèi)在一定條件下，Gibbs算法的誤分類(lèi)率的期望值最多為貝葉斯最優(yōu)分類(lèi)器的兩倍。確切地講，期望值是在隨機(jī)抽取的目標(biāo)概念上作出的，抽取過(guò)程按照學(xué)習(xí)器假定的先驗(yàn)概率對(duì)概念學(xué)習(xí)問(wèn)題的一個(gè)啟示：如果學(xué)習(xí)器假定H上有均勻的先驗(yàn)概率，而且如果目標(biāo)概念實(shí)際上也按該分布抽取，那么當(dāng)前變型空間中隨機(jī)抽取的假設(shè)對(duì)下一實(shí)例分類(lèi)的期望誤差最多為貝葉斯分類(lèi)器的兩倍樸素貝葉斯分類(lèi)器應(yīng)用的學(xué)習(xí)任務(wù)：每個(gè)實(shí)例x可由屬性值的合取描述，而目標(biāo)函數(shù)f(x)從某有限集合V中取值;貝葉斯方法的新實(shí)例分類(lèi)目標(biāo)是在給定描述實(shí)例的屬性值<a1,...,an>下，得到最可能的目標(biāo)值vMAP使用貝葉斯公式變化上式(6.19)樸素貝葉斯分類(lèi)器（2）基于訓(xùn)練數(shù)據(jù)估計(jì)式(6.19)中的兩個(gè)數(shù)據(jù)項(xiàng)的值估計(jì)P(vj)很容易：計(jì)算每個(gè)目標(biāo)值vj出現(xiàn)在訓(xùn)練數(shù)據(jù)中的頻率；估計(jì)P(a1,..,an|vj)遇到數(shù)據(jù)稀疏問(wèn)題，除非有一個(gè)非常大的訓(xùn)練數(shù)據(jù)集，否則無(wú)法獲得可靠的估計(jì)樸素貝葉斯分類(lèi)器引入一個(gè)簡(jiǎn)單的假定避免數(shù)據(jù)稀疏問(wèn)題：在給定目標(biāo)值時(shí)，屬性值之間相互條件獨(dú)立，即(6.20)樸素貝葉斯分類(lèi)器（3）樸素貝葉斯分類(lèi)器的定義：從訓(xùn)練數(shù)據(jù)中估計(jì)不同P(ai|vj)項(xiàng)的數(shù)量比要估計(jì)P(a1,...,an|vj)項(xiàng)所需的量小得多；只要條件獨(dú)立性得到滿足，樸素貝葉斯分類(lèi)vNB等于MAP分類(lèi)，否則是近似；樸素貝葉斯分類(lèi)器與前面已介紹的學(xué)習(xí)方法的一個(gè)區(qū)別：沒(méi)有明確地搜索可能假設(shè)空間的過(guò)程（假設(shè)的形成不需要搜索，只是簡(jiǎn)單地計(jì)算訓(xùn)練樣例中不同數(shù)據(jù)組合的出現(xiàn)頻率）樸素貝葉斯分類(lèi)器（4）舉例表3-2提供了目標(biāo)概念PlayTennis的14個(gè)訓(xùn)練樣例，給新實(shí)例<sunny,cool,high,strong>分類(lèi)

根據(jù)表3-2，可以計(jì)算出上式需要的概率值P(yes)=9/14=0.64P(no)=5/14=0.36P(strong|yes)=3/9=0.33P(strong|no)=3/5=0.60...求vNBP(yes)P(sunny|yes)P(cool|yes)P(high|yes)P(strong|yes)=0.0053P(no)P(sunny|no)P(cool|no)P(high|no)P(strong|no)=0.0206vNB=no樸素貝葉斯分類(lèi)器（5）估計(jì)概率通過(guò)在全部事件基礎(chǔ)上觀察某事件出現(xiàn)的比例來(lái)估計(jì)概率當(dāng)樣本很小時(shí)，采用平滑技術(shù)，m-估計(jì)p是將要確定的概率的先驗(yàn)估計(jì)，而m是一稱(chēng)為等效樣本大小的常量；在缺少其它信息時(shí)，選擇p的一種典型的方法是均勻概率，比如某屬性有k個(gè)可能值，那么p=1/k；m被稱(chēng)為等效樣本大小的原因是：式子6.22可被解釋為將n個(gè)實(shí)際的觀察擴(kuò)大，加上m個(gè)按p分布的虛擬樣本。(6.22)舉例：學(xué)習(xí)分類(lèi)文本利用貝葉斯方法學(xué)習(xí)目標(biāo)概念，然后用于文本自動(dòng)過(guò)濾，比如：我感興趣的電子新聞稿討論機(jī)器學(xué)習(xí)的因特網(wǎng)頁(yè)問(wèn)題框架：實(shí)例空間X包含了所有的文本文檔，給定某未知目標(biāo)函數(shù)f(x)的一組訓(xùn)練樣例，f(x)的值來(lái)自某有限集合V（作為示例，此處令V={like,dislike}）基于樸素貝葉斯的分類(lèi)方法是文本分類(lèi)最有效方法。舉例：學(xué)習(xí)分類(lèi)文本（2）應(yīng)用樸素貝葉斯分類(lèi)器的兩個(gè)主要設(shè)計(jì)問(wèn)題：怎樣將任意文檔表示為屬性值的形式如何估計(jì)樸素貝葉斯分類(lèi)器所需的概率表示文檔的方法給定一個(gè)文本文檔，對(duì)每個(gè)單詞的位置定義一個(gè)屬性，該屬性的值為在此位置上找到的英文單詞假定我們共有1000個(gè)訓(xùn)練文檔，其中700個(gè)分類(lèi)為dislike，300個(gè)分類(lèi)為like，現(xiàn)在要對(duì)下面的新文檔進(jìn)行分類(lèi)：ThisisanexampledocumentforthenaiveBayesclassifier.Thisdocumentcontainsonlyoneparagraph,ortwosentences.舉例：學(xué)習(xí)分類(lèi)文本（3）計(jì)算式注意此處貝葉斯分類(lèi)器隱含的獨(dú)立性假設(shè)并不成立。通常，某個(gè)位置上出現(xiàn)某個(gè)單詞的概率與前后位置上出現(xiàn)的單詞是相關(guān)的雖然此處獨(dú)立性假設(shè)不精確，但別無(wú)選擇，否則要計(jì)算的概率項(xiàng)極為龐大。實(shí)踐中，樸素貝葉斯學(xué)習(xí)器在許多文本分類(lèi)問(wèn)題中性能非常好。舉例：學(xué)習(xí)分類(lèi)文本（4）需要估計(jì)概率項(xiàng)P(vi)和P(ai=wk|vi)。前一項(xiàng)可基于每一類(lèi)在訓(xùn)練數(shù)據(jù)中的比例很容易得到，后一項(xiàng)含三個(gè)參數(shù)，出現(xiàn)數(shù)據(jù)稀疏問(wèn)題再引入一個(gè)假定以減少需要估計(jì)的概率項(xiàng)的數(shù)量：假定單詞wk出現(xiàn)的概率獨(dú)立于單詞所在的位置，即P(ai=wk|vi)=P(wk|vj)作此假定的一個(gè)主要優(yōu)點(diǎn)在于：使可用于估計(jì)每個(gè)所需概率的樣例數(shù)增加了，因此增加了估計(jì)的可靠程度采納m-估計(jì)方法，即有統(tǒng)一的先驗(yàn)概率并且m等于詞匯表的大小，因此表6-2用于學(xué)習(xí)和分類(lèi)文本的樸素貝葉斯算法Learn_Naive_Bayes_Text(Examples,V) Examples為一組文本文檔以及它們的目標(biāo)值。V為所有可能目標(biāo)值的集合。此函數(shù)作用是學(xué)習(xí)概率項(xiàng)P(wk|vj)和P(vj)。收集Examples中所有的單詞、標(biāo)點(diǎn)符號(hào)以及其他記號(hào)Vocabulary在Examples中任意文本文檔中出現(xiàn)的所有單詞及記號(hào)的集合計(jì)算所需要的概率項(xiàng)P(vj)和P(wk|vj)對(duì)V中每個(gè)目標(biāo)值vjdocsjExamples中目標(biāo)值為vj的文檔子集P(vj)|docsj|/|Examples|Textj將docsj中所有成員連接起來(lái)建立的單個(gè)文檔n在Textj中不同單詞位置的總數(shù)對(duì)Vocabulary中每個(gè)單詞wknk單詞wk出現(xiàn)在Textj中的次數(shù)P(wk|vj)(nk+1)/(n+|Vocabulary|)用于學(xué)習(xí)和分類(lèi)文本的樸素貝葉斯算法（2）Classify_Naive_Bayes_Text(Doc)

對(duì)文檔Doc返回其估計(jì)的目標(biāo)值，ai代表在Doc中的第i個(gè)位置上出現(xiàn)的單詞positions在Doc中的所有單詞位置，它包含能在Vocabulary中找到的記號(hào)返回vNB，應(yīng)用樣例Joachims將此算法用于新聞組文章的分類(lèi)每一篇文章的分類(lèi)是該文章所屬的新聞組名稱(chēng)；20個(gè)新聞組，每個(gè)新聞組有1000篇文章，共2萬(wàn)個(gè)文檔；2/3作為訓(xùn)練樣例，1/3進(jìn)行性能測(cè)量；詞匯表不包含最常用詞（比如the、of）和罕見(jiàn)詞（數(shù)據(jù)集中出現(xiàn)次數(shù)少于3）；分類(lèi)精度由隨機(jī)分類(lèi)5％提高到89％。Lang用此算法學(xué)習(xí)目標(biāo)概念“我感興趣的新聞組文章”NewsWeeder系統(tǒng)，讓用戶閱讀新聞組文章并為其評(píng)分，然后使用這些評(píng)分的文章作為訓(xùn)練樣例，來(lái)預(yù)測(cè)后續(xù)文章哪些是用戶感興趣的；每天向用戶展示前10%的自動(dòng)評(píng)分文章，它建立的文章序列中包含的用戶感興趣的文章比通常高3~4倍。貝葉斯信念網(wǎng)樸素貝葉斯分類(lèi)器假定各個(gè)屬性取值在給定目標(biāo)值v下是條件獨(dú)立的，從而化簡(jiǎn)了最優(yōu)貝葉斯分類(lèi)的計(jì)算復(fù)雜度。但在多數(shù)情況下，這一條件獨(dú)立假定過(guò)于嚴(yán)格；貝葉斯信念網(wǎng)描述的是一組變量所遵從的概率分布，它通過(guò)一組條件概率來(lái)指定一組條件獨(dú)立性假設(shè)；貝葉斯信念網(wǎng)采用聯(lián)合概率分布，它允許在變量的子集間定義類(lèi)條件獨(dú)立性，它提供因果關(guān)系圖形。因此，貝葉斯信念網(wǎng)提供了一種中間的方法，它比樸素貝葉斯分類(lèi)器的限制更少，又比在所有變量中計(jì)算條件依賴(lài)更可行。貝葉斯信念網(wǎng)（2）貝葉斯信念網(wǎng)描述了一組變量上的概率分布；考慮一任意的隨機(jī)變量集合Y1...Yn，其中每個(gè)Yi可取的值集合為V(Yi)；變量集合Y的聯(lián)合空間為叉乘V(Y1)...V(Yn)；在此聯(lián)合空間上的概率分布稱(chēng)為聯(lián)合概率分布，聯(lián)合概率分布指定了元組的每個(gè)可能的變量約束的概率；貝葉斯信念網(wǎng)則對(duì)一組變量描述了聯(lián)合概率分布。條件獨(dú)立性精確定義條件獨(dú)立性令X,Y和Z為3個(gè)離散值隨機(jī)變量，當(dāng)給定Z值時(shí)X服從的概率分布獨(dú)立于Y的值，稱(chēng)X在給定Z時(shí)條件獨(dú)立于Y，即上式通常簡(jiǎn)寫(xiě)成P(X|Y,Z)=P(X|Z)擴(kuò)展到變量集合下面等式成立時(shí)，稱(chēng)變量集合X1...Xl在給定變量集合Z1...Zn時(shí)條件獨(dú)立于變量集合Y1...Ym條件獨(dú)立性與樸素貝葉斯分類(lèi)器的之間的關(guān)系貝葉斯信念網(wǎng)的表示貝葉斯信念網(wǎng)（簡(jiǎn)稱(chēng)貝葉斯網(wǎng)）表示一組變量的聯(lián)合概率分布一般地說(shuō)，貝葉斯網(wǎng)表示聯(lián)合概率分布的方法是指定一組條件獨(dú)立性假定（有向無(wú)環(huán)圖）以及一組局部條件概率集合下頁(yè)圖，聯(lián)合空間中每個(gè)變量在貝葉斯網(wǎng)中表示為一個(gè)節(jié)點(diǎn)，每個(gè)變量需要兩種類(lèi)型的信息網(wǎng)絡(luò)弧表示斷言“此變量在給定其直接前驅(qū)時(shí)條件獨(dú)立于其非后繼”每個(gè)變量有一個(gè)條件概率表，描述了該變量在給定其立即前驅(qū)時(shí)的概率分布StormBusTourGroupLightningThunderForestFireCampfire S,B S,┐B ┐S,B ┐S,┐BC 0.4 0.1 0.8 0.2┐C 0.6 0.9 0.2 0.8Campfire貝葉斯信念網(wǎng)的表示（2）對(duì)網(wǎng)絡(luò)變量的元組<Y1...Yn>賦以所希望的值(y1...yn)的聯(lián)合概率計(jì)算公式如下：所有變量的局部條件概率表以及由網(wǎng)絡(luò)所描述的一組條件獨(dú)立假定，描述了該網(wǎng)絡(luò)的整個(gè)聯(lián)合概率分布貝葉斯信念網(wǎng)的推理可以用貝葉斯網(wǎng)在給定其它變量的觀察值時(shí)推理出某些目標(biāo)變量的值由于所處理的是隨機(jī)變量，所以一般不會(huì)賦予目標(biāo)變量一個(gè)確切的值真正需要推理的是目標(biāo)變量的概率分布，它指定了在給予其他變量的觀察值條件下，目標(biāo)變量取每一個(gè)可能值的概率在網(wǎng)絡(luò)中所有其它變量都確切知道的情況下，這一推理步驟很簡(jiǎn)單一般來(lái)說(shuō)，貝葉斯網(wǎng)絡(luò)可用于在知道某些變量的值或分布時(shí)計(jì)算網(wǎng)絡(luò)中另一部分變量的概率分布學(xué)習(xí)貝葉斯信念網(wǎng)從訓(xùn)練數(shù)據(jù)中學(xué)到貝葉斯信念網(wǎng)，有多種討論的框架：網(wǎng)絡(luò)結(jié)構(gòu)可以預(yù)先給出，或由訓(xùn)練數(shù)據(jù)中得到所有的網(wǎng)絡(luò)變量可以直接從每個(gè)訓(xùn)練樣例中觀察到，或某些變量不能觀察到如果網(wǎng)絡(luò)結(jié)構(gòu)已知且變量可以從訓(xùn)練樣例中完全獲得，那么得到條件概率表就比較簡(jiǎn)單；如果網(wǎng)絡(luò)結(jié)構(gòu)已知，但只有一部分變量值能在數(shù)據(jù)中觀察到，學(xué)習(xí)問(wèn)題就困難多了。這類(lèi)似于在人工神經(jīng)網(wǎng)絡(luò)中學(xué)習(xí)隱層單元的權(quán)值；Russell（1995）提出了一個(gè)簡(jiǎn)單的梯度上升過(guò)程以學(xué)習(xí)條件概率表中的項(xiàng)，相當(dāng)于對(duì)表項(xiàng)搜索極大似然假設(shè)。貝葉斯網(wǎng)的梯度上升訓(xùn)練令wijk代表?xiàng)l件概率表的一個(gè)表項(xiàng)，即在給定父節(jié)點(diǎn)Ui取值uik時(shí)，網(wǎng)絡(luò)變量Yi值為yij的概率例如圖6-3，wijk為最右上方的表項(xiàng)，那么Yi為變量Campfire，Ui是其父節(jié)點(diǎn)的元組<Storm,BusTourGroup>，yij=True，且uik=<False,False> S,B S,┐B ┐S,B ┐S,┐BC 0.4 0.1 0.8 0.2┐C 0.6 0.9 0.2 0.8Campfire貝葉斯網(wǎng)的梯度上升訓(xùn)練（2）lnP(D|h)的梯度由對(duì)每個(gè)wijk求導(dǎo)數(shù)得到例如，為計(jì)算圖6-3中表右上方的表項(xiàng)的lnP(D|h)的導(dǎo)數(shù)，需要對(duì)D中每個(gè)訓(xùn)練樣例d計(jì)算P(Campfire=True,Storm=False,BusTourGroup=False|d)當(dāng)訓(xùn)練樣例中無(wú)法觀察到這些變量時(shí)，這些概率可用標(biāo)準(zhǔn)的貝葉斯網(wǎng)從d中觀察到的變量中推理得到這些量能夠很容易地從貝葉斯網(wǎng)推理過(guò)程中得到，幾乎不需要附加的開(kāi)銷(xiāo)(6.25)貝葉斯網(wǎng)的梯度上升訓(xùn)練（3）式子6.25的推導(dǎo)用Ph(D)來(lái)表示P(D|h)假定在數(shù)據(jù)集D中的各樣例d都是獨(dú)立抽取的貝葉斯網(wǎng)的梯度上升訓(xùn)練（4）更新權(quán)值歸一化處理，保持在區(qū)間[0,1]之間，且jwijk對(duì)所有i,k保持為1這個(gè)算法只保證找到局部最優(yōu)解，替代梯度上升的一個(gè)算法是EM算法學(xué)習(xí)貝葉斯網(wǎng)的結(jié)構(gòu)如果貝葉斯網(wǎng)的結(jié)構(gòu)未知，那么需要學(xué)習(xí)貝葉斯網(wǎng)的結(jié)構(gòu)Cooper&Herskovits提出了一個(gè)貝葉斯評(píng)分尺度，以便從不同網(wǎng)絡(luò)中進(jìn)行選擇Cooper&Herskovits提出了算法K2，啟發(fā)式算法，用于在數(shù)據(jù)完全可觀察時(shí)學(xué)習(xí)網(wǎng)絡(luò)結(jié)構(gòu)基于約束的學(xué)習(xí)貝葉斯網(wǎng)絡(luò)結(jié)構(gòu)：從數(shù)據(jù)中推導(dǎo)出獨(dú)立和相關(guān)的關(guān)系，然后用這些關(guān)系來(lái)構(gòu)造貝葉斯網(wǎng)EM算法EM（ExpectationMaximizationalgorithm）期望最大化算法；處理存在未觀察到變量的問(wèn)題比如，如果某些變量有時(shí)能觀察到，有時(shí)不能，那么可以用觀察到該變量的實(shí)例去預(yù)測(cè)未觀察到的實(shí)例中的變量的值EM算法可用于變量的值從來(lái)沒(méi)有被直接觀察到的情形，只要這些變量所遵循的概率分布的形式已知用于馬爾可夫模型的訓(xùn)練，估計(jì)HMM的參數(shù)；可用于混合模型的參數(shù)估計(jì)（如GMM）用于貝葉斯網(wǎng)的訓(xùn)練聚類(lèi)分析方法單變量數(shù)據(jù)樣本Sampling極大似然（ML）Sampling給定

x,它是

和

2

函數(shù)目的是

將其最大化.取對(duì)數(shù)的極大似然函數(shù)將該最大化變換為對(duì)數(shù)形式只需使且對(duì)數(shù)似然函數(shù)求極大值對(duì)數(shù)似然函數(shù)求極大值數(shù)據(jù)缺失SamplingMissingdataE-Step令為tth迭代的估計(jì)值E-Step令為tth迭代的估計(jì)值M-Step令為tth迭代的估計(jì)值混合模型如果采集的數(shù)據(jù)是屬于混合模型情況；可描述成以下形式：且混合模型令

yi{1,…,M

}

代表數(shù)據(jù)源于那個(gè)模型.

混合模型其中

yi{1,…,M}代表數(shù)據(jù)源于那個(gè)模型.

混合模型混合模型混合模型給定

x

和

,y

的條件概率可被計(jì)算.完整數(shù)據(jù)的似然函數(shù)期望g:估計(jì)期望g:估計(jì)期望當(dāng)yi

l

為0期望期望期望1最大化給定初始估計(jì)值

g,需要找到合適參數(shù)

,使得期望最大化實(shí)際上,就是反復(fù)迭代.混合高斯模型高斯模型為

d

維，第

j個(gè)模型

可表示為:該GMM有

M

個(gè)模型:目標(biāo)混合模型其中，最大化:目標(biāo)混合模型其中最大化:僅與

l

相關(guān).僅與

l

相關(guān).求

l

由于有

l的約束,為典型求條件極值問(wèn)題，故引入拉格朗日乘子

,并構(gòu)成以下等式.求l

1N1求

l

求

l

Onlyneedtomaximizethisterm考慮

GMMunrelated求

l

Onlyneedtomaximizethisterm因此,需最大化:unrelated為什么?主要是基于矩陣代數(shù)知識(shí).求

l

因此,需最大化:小結(jié)針對(duì)高斯混合模型

GMM的EM算法給定初始估計(jì)值

g,尋找新的參數(shù)

new

如下：不收斂

估計(jì)k個(gè)高斯分布的均值考慮D是一個(gè)實(shí)例集合，它由k個(gè)不同正態(tài)分布的混合所得分布生成每個(gè)實(shí)例使用一個(gè)兩步驟的過(guò)程形成：首先，隨機(jī)選擇k個(gè)正態(tài)分布中的一個(gè)其次，隨機(jī)變量xi按照此選擇的分布生成考慮一個(gè)簡(jiǎn)單情形：?jiǎn)蝹€(gè)正態(tài)分布的選擇基于均勻的概率進(jìn)行，且k個(gè)正態(tài)分布有相同的方差學(xué)習(xí)任務(wù)：輸出一個(gè)假設(shè)h=<1...k>，描述k個(gè)分布中每個(gè)分布的均值，找到極大似然假設(shè)，即使得p(D|h)最大化的假設(shè)估計(jì)k個(gè)高斯分布的均值（2）當(dāng)給定從一個(gè)正態(tài)分布中抽取的數(shù)據(jù)實(shí)例x1,...,xm時(shí)，很容易計(jì)算該分布的均值的極大似然假設(shè)，它是前面介紹的最小誤差平方假設(shè)的一個(gè)特例，表示如下然而，現(xiàn)在的問(wèn)題涉及k個(gè)不同正態(tài)分布，而且不知道哪個(gè)實(shí)例是哪個(gè)分布產(chǎn)生的。這是一個(gè)涉及隱藏變量的典型例子；對(duì)于圖6-4的例子，每個(gè)實(shí)例的完整描述是三元組<xi,zi1,zi2>，其中xi是第i個(gè)實(shí)例的觀測(cè)值，zi1和zi2表示哪個(gè)正態(tài)分布被用來(lái)產(chǎn)生xi，是隱藏變量(6.27,28)圖6-4由兩個(gè)具有相等方差的正態(tài)分布混合生成的例子估計(jì)k個(gè)高斯分布的均值（3）如果zi1和zi2的值可知，就可用式子6.27來(lái)解決，否則使用EM算法EM算法根據(jù)當(dāng)前假設(shè)<1...k>，不斷地再估計(jì)隱藏變量zij的期望值，然后用這些隱藏變量的期望值重新計(jì)算極大似然假設(shè)以圖6-4為例，先將假設(shè)初始化為h=<1,2>計(jì)算每個(gè)隱藏變量zij的期望值E[zij]，假定當(dāng)前假設(shè)h=<1,2>成立計(jì)算一個(gè)新的極大似然假設(shè)h’=<’1,’2>，假定每個(gè)隱藏變量zij所取值是第一步得到的期望值E[zij]。將假設(shè)替換為h’=<’1,’2>，然后循環(huán)兩個(gè)步驟的計(jì)算式E[zij]正是實(shí)例xi由第j個(gè)正態(tài)分布生成的概率第二步，使用第一步得到的E[zij]來(lái)導(dǎo)出一新的極大似然假設(shè)兩個(gè)步驟的計(jì)算式（2）第二步中的表達(dá)式類(lèi)似于式6.28，只是變成了加權(quán)樣本均值EM算法的要點(diǎn)：當(dāng)前的假設(shè)用于估計(jì)未知變量，而這些變量的期望值再被用于改進(jìn)假設(shè)可以證明：算法的每一次循環(huán)中，EM算法能使似然P(D|h)增加，除非P(D|h)達(dá)到局部最大，因此算法收斂到一個(gè)局部最大似然假設(shè)EM算法的一般表