1、貝葉斯學(xué)習(xí) 轉(zhuǎn)機器學(xué)習(xí)-貝葉斯學(xué)習(xí)作者：Mitchell譯者：曾華軍等講者：陶曉鵬機器學(xué)習(xí)第6章貝葉斯學(xué)習(xí)概述貝葉斯推理提供了一種概率手段,基于如下的假定：待考察的量遵循某概率分布,且可根據(jù)這些概率及已觀察到的數(shù)據(jù)進(jìn)行推理,以作出最優(yōu)的決策.貝葉斯推理為衡量多個假設(shè)的置信度提供了定量的方法貝葉斯推理為直接操作概率的學(xué)習(xí)算法提供了基礎(chǔ),也為其他算法的分析提供了理論框架簡介貝葉斯學(xué)習(xí)算法與機器學(xué)習(xí)相關(guān)的兩個原因：貝葉斯學(xué)習(xí)算法能夠計算顯示的假設(shè)概率,比如樸素貝葉斯分類貝葉斯方法為理解多數(shù)學(xué)習(xí)算法提供了一種有效的手段,而這些算法不一定直接操縱概率數(shù)據(jù),比如Find-S候選消除算法神經(jīng)網(wǎng)絡(luò)學(xué)習(xí)：選擇使

2、誤差平方和最小化的神經(jīng)網(wǎng)絡(luò)推導(dǎo)出另一種誤差函數(shù)：交叉熵分析了決策樹的歸納偏置考察了最小描述長度原則貝葉斯學(xué)習(xí)方法的特性觀察到的每個訓(xùn)練樣例可以增量地降低或升高某假設(shè)的估計概率.而其他算法會在某個假設(shè)與任一樣例不一致時完全去掉該假設(shè)先驗知識可以與觀察數(shù)據(jù)一起決定假設(shè)的最終概率,先驗知識的形式是：1)每個候選假設(shè)的先驗概率；2)每個可能假設(shè)在可觀察數(shù)據(jù)上的概率分布貝葉斯方法可允許假設(shè)做出不確定性的預(yù)測新的實例分類可由多個假設(shè)一起做出預(yù)測,用它們的概率來加權(quán)即使在貝葉斯方法計算復(fù)雜度較高時,它們?nèi)钥勺鳛橐粋€最優(yōu)的決策標(biāo)準(zhǔn)衡量其他方法貝葉斯方法的難度難度之一：需要概率的初始知識,當(dāng)概率預(yù)先未知時,可以

3、基于背景知識,預(yù)先準(zhǔn)備好的數(shù)據(jù)以及基準(zhǔn)分布的假定來估計這些概率難度之二：一般情況下,確定貝葉斯最優(yōu)假設(shè)的計算代價比較大(在某些特定情形下,這種計算代價可以大大降低).內(nèi)容安排介紹貝葉斯理論定義極大似然假設(shè)和極大后驗概率假設(shè)將此概率框架應(yīng)用于分析前面章節(jié)的相關(guān)問題和學(xué)習(xí)算法介紹幾種直接操作概率的學(xué)習(xí)算法貝葉斯最優(yōu)分類器Gibbs算法樸素貝葉斯分類器討論貝葉斯信念網(wǎng),這是存在未知變量時被廣泛使用的學(xué)習(xí)算法貝葉斯法則機器學(xué)習(xí)的任務(wù)：在給定訓(xùn)練數(shù)據(jù)D時,確定假設(shè)空間H中的最佳假設(shè).最佳假設(shè)：一種方法是把它定義為在給定數(shù)據(jù)D以及H中不同假設(shè)的先驗概率的有關(guān)知識下的最可能假設(shè)貝葉斯理論提供了一種計算假設(shè)概

4、率的方法,基于假設(shè)的先驗概率,給定假設(shè)下觀察到不同數(shù)據(jù)的概率以及觀察到的數(shù)據(jù)本身先驗概率和后驗概率用P(h)表示在沒有訓(xùn)練數(shù)據(jù)前假設(shè)h擁有的初始概率.P(h)被稱為h的先驗概率.先驗概率反映了關(guān)于h是一正確假設(shè)的機會的背景知識如果沒有這一先驗知識,可以簡單地將每一候選假設(shè)賦予相同的先驗概率類似地,P(D)表示訓(xùn)練數(shù)據(jù)D的先驗概率,P(D|h)表示假設(shè)h成立時D的概率機器學(xué)習(xí)中,我們關(guān)心的是P(h|D),即給定D時h的成立的概率,稱為h的后驗概率貝葉斯公式貝葉斯公式提供了從先驗概率P(h),P(D)和P(D|h)計算后驗概率P(h|D)的方法P(h|D)隨著P(h)和P(D|h)的增長而增長,隨

5、著P(D)的增長而減少,即如果D獨立于h時被觀察到的可能性越大,那么D對h的支持度越小極大后驗假設(shè)學(xué)習(xí)器在候選假設(shè)集合H中尋找給定數(shù)據(jù)D時可能性最大的假設(shè)h,h被稱為極大后驗假設(shè)(MAP)確定MAP的方法是用貝葉斯公式計算每個候選假設(shè)的后驗概率,計算式如下最后一步,去掉了P(D),因為它是不依賴于h的常量極大似然假設(shè)在某些情況下,可假定H中每個假設(shè)有相同的先驗概率,這樣式子6.2可以進(jìn)一步簡化,只需考慮P(D|h)來尋找極大可能假設(shè).P(D|h)常被稱為給定h時數(shù)據(jù)D的似然度,而使P(D|h)最大的假設(shè)被稱為極大似然假設(shè)假設(shè)空間H可擴展為任意的互斥命題集合,只要這些命題的概率之和為1舉例：一個

6、醫(yī)療診斷問題有兩個可選的假設(shè)：病人有癌癥,病人無癌癥可用數(shù)據(jù)來自化驗結(jié)果：正+和負(fù)-有先驗知識：在所有人口中,患病率是0.008對確實有病的患者的化驗準(zhǔn)確率為98%,對確實無病的患者的化驗準(zhǔn)確率為97%總結(jié)如下P(cancer)=0.008,P(cancer)=0.992 P(+|cancer)=0.98,P(-|cancer)=0.02 P(+|cancer)=0.03,P(-|cancer)=0.97舉例：一個醫(yī)療診斷問題(2)問題：假定有一個新病人,化驗結(jié)果為正,是否應(yīng)將病人斷定為有癌癥求后驗概率P(cancer|+)和P(cancer|+)利用式子6.2找到極大后驗假設(shè)P(+|canc

7、er)P(cancer)=0.0078 P(+|cancer)P(cancer)=0.0298 hMAP=cancer確切的后驗概率可將上面的結(jié)果歸一化以使它們的和為1 P(canner|+)=0.0078/(0.0078+0.0298)=0.21 P(cancer|-)=0.79貝葉斯推理的結(jié)果很大程度上依賴于先驗概率,另外不是完全接受或拒絕假設(shè),只是在觀察到較多的數(shù)據(jù)后增大或減小了假設(shè)的可能性基本概率公式表乘法規(guī)則：P(A B)=P(A|B)P(B)=P(B|A)P(A)加法規(guī)則：P(A B)=P(A)+P(B)-P(A B)貝葉斯法則：P(h|D)=P(D|h)P(h)/P(D)全概率法

8、則：如果事件A1.An互斥,且滿足,則貝葉斯法則和概念學(xué)習(xí)貝葉斯法則為計算給定訓(xùn)練數(shù)據(jù)下任一假設(shè)的后驗概率提供了原則性方法,因此可以直接將其作為一個基本的學(xué)習(xí)方法：計算每個假設(shè)的概率,再輸出其中概率最大的.這個方法稱為Brute-Force貝葉斯概念學(xué)習(xí)算法.將上面方法與第2章介紹的概念學(xué)習(xí)算法比較,可以看到：在特定條件下,它們學(xué)習(xí)得到相同的假設(shè),不同的是第2章的方法不明確計算概率,而且效率更高.Brute-Force貝葉斯概念學(xué)習(xí)概念學(xué)習(xí)問題：有限假設(shè)空間H定義在實例空間X上,任務(wù)是學(xué)習(xí)某個目標(biāo)概念c.Brute-Force MAP學(xué)習(xí)算法對于H中每個假設(shè)h,計算后驗概率輸出有最高后驗概率的

9、假設(shè)上面算法需要較大計算量,因為它要計算每個假設(shè)的后驗概率,對于大的假設(shè)空間顯得不切實際,但是它提供了一個標(biāo)準(zhǔn)以判斷其他概念學(xué)習(xí)算法的性能特定情況下的MAP假設(shè)假定訓(xùn)練數(shù)據(jù)D是無噪聲的,即di=c(xi)目標(biāo)概念c包含在假設(shè)空間H中每個假設(shè)的概率相同求得由于所有假設(shè)的概率之和是1,因此由于訓(xùn)練數(shù)據(jù)無噪聲,那么給定假設(shè)h時,與h一致的D的概率為1,不一致的概率為0,因此特定情況下的MAP假設(shè)(2)考慮Brute-Force MAP算法的第一步h與D不一致,h與D一致,VSH,D是關(guān)于D的變型空間(見第2章,即與D一致的假設(shè)集)特定情況下的MAP假設(shè)(3)P(D)的推導(dǎo)P(D)假設(shè)的概率演化情況如

10、圖6-1所示,初始時所有假設(shè)具有相同的概率,當(dāng)訓(xùn)練數(shù)據(jù)逐步出現(xiàn)后,不一致假設(shè)的概率變?yōu)?,而整個概率的和為1,它們均勻分布到剩余的一致假設(shè)中每個一致的假設(shè)都是MAP假設(shè)MAP假設(shè)和一致學(xué)習(xí)器一致學(xué)習(xí)器：如果某個學(xué)習(xí)器輸出的假設(shè)在訓(xùn)練樣例上為0錯誤率,則稱為一致學(xué)習(xí)器如果H上有均勻的先驗概率,且訓(xùn)練數(shù)據(jù)是確定性和無噪聲的,任意一致學(xué)習(xí)器將輸出一個MAP假設(shè)Find-S算法按照特殊到一般的順序搜索架設(shè)空間H,并輸出一個極大特殊的一致假設(shè),因此可知在上面定義的P(h)和P(D|h)概率分布下,它輸出MAP假設(shè)更一般地,對于先驗概率偏袒于更特殊假設(shè)的任何概率分布,Find-S輸出的假設(shè)都是MAP假設(shè)M

11、AP假設(shè)和一致學(xué)習(xí)器(2)貝葉斯框架提出了一種刻畫學(xué)習(xí)算法行為的方法,即便該學(xué)習(xí)算法不進(jìn)行概率操作,通過確定算法輸出最優(yōu)假設(shè)時使用的概率分布P(h)和P(D|h),可以刻畫出算法具有最優(yōu)行為時的隱含假定使用貝葉斯方法刻畫學(xué)習(xí)算法,與揭示學(xué)習(xí)器中的歸納偏置在思想上是類似的在第2章,將學(xué)習(xí)算法的歸納偏置定義為斷言集合B,通過它可充分地演繹推斷出學(xué)習(xí)器所執(zhí)行的歸納推理結(jié)果,即學(xué)習(xí)器的輸出是由其輸入和隱含的歸納偏置所演繹得出的MAP假設(shè)和一致學(xué)習(xí)器(3)貝葉斯解釋對于描述學(xué)習(xí)算法中的隱含假定提供了另一種方法,用基于貝葉斯理論的一個等效的概率推理系統(tǒng)來建模貝葉斯解釋隱含的假定形式為：H上的先驗概率由P(

12、h)分布給出,數(shù)據(jù)拒絕或接受假設(shè)的強度由P(D|h)給出在已知這些假定的概率分布后,一個基于貝葉斯理論的概率推理系統(tǒng)將產(chǎn)生等效于Find-S,候選消除等算法的輸入-輸出行為極大似然和最小誤差平方假設(shè)前面分析表明：某些學(xué)習(xí)算法即使沒有顯示地使用貝葉斯規(guī)則,或以某種形式計算概率,但它們輸出的結(jié)果符合貝葉斯原理,是一個MAP假設(shè)通過簡單的貝葉斯分析,可以表明在特定前提下,任一學(xué)習(xí)算法如果使輸出的假設(shè)預(yù)測和訓(xùn)練數(shù)據(jù)之間的誤差平方和最小化,它將輸出一極大似然假設(shè)上面結(jié)論的意義是,對于許多神經(jīng)網(wǎng)絡(luò)和曲線擬合的方法,如果它們試圖在訓(xùn)練數(shù)據(jù)上使誤差平方和最小化,此結(jié)論提供了基于貝葉斯的理論依據(jù)極大似然和最小誤

13、差平方假設(shè)(2)問題框架：學(xué)習(xí)器L工作在實例空間X和假設(shè)空間H上,H中的假設(shè)為X上定義的某種實數(shù)值函數(shù).L面臨的問題是學(xué)習(xí)一個從H中抽取出的未知目標(biāo)函數(shù)f,給定m個訓(xùn)練樣例的集合,每個樣例的目標(biāo)值被某隨機噪聲干擾,此隨機噪聲服從正態(tài)分布更精確地講,每個訓(xùn)練樣例是序偶,di=f(xi)+ei,ei是代表噪聲的隨機變量,假定ei的值是獨立抽取的,并且它們的分布服從0均值的正態(tài)分布學(xué)習(xí)器的任務(wù)是在所有假設(shè)有相等的先驗概率前提下,輸出極大似然假設(shè)(即MAP假設(shè))極大似然和最小誤差平方假設(shè)(3)用一個簡單情況,即線性函數(shù)來說明問題.如圖6-2所示,實線表示線性目標(biāo)函數(shù)f,實點表示有噪聲的訓(xùn)練樣例集,虛線

14、對應(yīng)有最小平方訓(xùn)練誤差的假設(shè)hML,即極大似然假設(shè).對于e這樣的連續(xù)變量上的概率,使用概率密度表示概率分布,它在所有值上的積分為1,用小寫的p表示.有限概率P有時又稱為概率質(zhì)量概率密度函數(shù)：極大似然和最小誤差平方假設(shè)(4)假定有一固定的訓(xùn)練實例集合,因此只考慮相應(yīng)的目標(biāo)值序列D=,這里di=f(xi)+ei.假定訓(xùn)練樣例是相互獨立的,給定h時,可將P(D|h)寫成各p(di|h)的積如果誤差ei服從0均值和未知方差2的正態(tài)分布,那么每個di服從均值為f(xi),方差不變的正態(tài)分布.因此,p(di|h)可寫為方差2,均值f(xi)的正態(tài)分布使用表5-4中的正態(tài)分布公式并將相應(yīng)的參數(shù)代入,由于概率

15、di的表達(dá)式是在h為目標(biāo)函數(shù)f的正確描述條件下的,所以替換=f(xi)=h(xi)極大似然和最小誤差平方假設(shè)(5)hML上式說明了極大似然假設(shè)等價于使訓(xùn)練值和假設(shè)預(yù)測值之間的誤差的平方和最小的那個假設(shè)這個結(jié)論的前提是：訓(xùn)練值等于真實目標(biāo)值加上隨機噪聲,其中隨機噪聲從一個均值為0的正態(tài)分布中獨立抽取采用正態(tài)分布的合理性數(shù)學(xué)計算的簡潔性對許多物理系統(tǒng)的噪聲都有良好的近似第5章中心極限定律顯示,足夠多的獨立同分布隨機變量的和服從正態(tài)分布由許多獨立同分布的因素的和所生成的噪聲將成為正態(tài)分布(當(dāng)然,現(xiàn)實中不同的分量對噪聲的貢獻(xiàn)也許不是同分布的)使誤差平方最小化的方法經(jīng)常被用于神經(jīng)網(wǎng)絡(luò),曲線擬合及其他許多

16、實函數(shù)逼近的算法中上面的分析只考慮了訓(xùn)練樣例的目標(biāo)值中的噪聲,而沒有考慮實例屬性值的噪聲用于預(yù)測概率的極大似然假設(shè)問題框架：學(xué)習(xí)一個不確定性函數(shù)f：X0,1,它有兩個離散的值輸出這種不可預(yù)測性來源于未能觀察到的因素,導(dǎo)致目標(biāo)函數(shù)的輸出是輸入的概率函數(shù)學(xué)習(xí)得到的神經(jīng)網(wǎng)絡(luò)(或其他實函數(shù)學(xué)習(xí)器)的輸出是f(x)=1的概率,表示為f：X0,1,即f=P(f(x)=1)用于預(yù)測概率的極大似然假設(shè)(2)Brute-Force法首先收集對x的每個可能值觀察到的1和0的頻率,然后訓(xùn)練神經(jīng)網(wǎng)絡(luò),對每個x輸出目標(biāo)頻率可以直接從f的訓(xùn)練樣例中訓(xùn)練神經(jīng)網(wǎng)絡(luò),然后推導(dǎo)出f的極大似然假設(shè)D=.用于預(yù)測概率的極大似然假設(shè)(

17、3)hML式子6.13與熵函數(shù)的一般式相似,因此它的負(fù)值常稱為交叉熵在神經(jīng)網(wǎng)絡(luò)中梯度搜索以達(dá)到似然最大化前面討論了利用式子6.13求極大似然假設(shè),現(xiàn)用G(h,D)表示,為神經(jīng)網(wǎng)絡(luò)學(xué)習(xí)推導(dǎo)一個權(quán)值訓(xùn)練法則,使用梯度上升法使G(h,D)最大化考慮簡單的情況,假定神經(jīng)網(wǎng)絡(luò)從一個單層的sigmoid單元建立,則在神經(jīng)網(wǎng)絡(luò)中梯度搜索以達(dá)到似然最大化(2)因為要使P(D|h)最大化而不是最小化,因此執(zhí)行梯度上升搜索,而不是梯度下降搜索.與反向傳播更新法則對比使誤差平方最小化的法則尋找到極大似然假設(shè)的前提是：訓(xùn)練數(shù)據(jù)可以由目標(biāo)函數(shù)值加上正態(tài)分布噪聲來模擬使交叉熵最小化的法則尋找極大似然假設(shè)基于的前提是：觀察

18、到的布爾值為輸入實例的概率函數(shù)最小描述長度準(zhǔn)則奧坎姆剃刀可以概括為：為觀察到的數(shù)據(jù)選擇最短的解釋此處給出一個貝葉斯分析,提出最小描述長度準(zhǔn)則,根據(jù)信息論中的基本概念來解釋hMAP的定義上式可以解釋為在特定的假設(shè)編碼表示方案上優(yōu)先選擇短的假設(shè)最小描述長度準(zhǔn)則(2)信息論中的編碼理論設(shè)想要為隨機傳送的消息設(shè)計一個編碼,其中遇到消息i的概率是pi感興趣的是,使得傳輸隨機信息所需的最小期望傳送位數(shù)的編碼直觀上,為使期望的編碼長度最小,可能性大的消息應(yīng)該賦予較短的編碼Shannon&Weaver證明了最優(yōu)編碼對消息i的編碼長度為-log2pi使用代碼C來編碼消息i所需的位數(shù)被稱為消息i關(guān)于C的描述長度,

19、記為LC(i)最小描述長度準(zhǔn)則(3)使用編碼理論的結(jié)論來解釋等式6.16-log2P(h)是在假設(shè)空間H的最優(yōu)編碼下h的描述長度.換言之,這是假設(shè)h使用其最優(yōu)表示時的大小,CH為假設(shè)空間H的最優(yōu)編碼-log2P(D|h)是在給定假設(shè)h時,訓(xùn)練數(shù)據(jù)D的描述長度,CD|h是假定發(fā)送者和接送者都知道假設(shè)h時描述數(shù)據(jù)D的最優(yōu)編碼因此式子6.16顯示,hMAP是使假設(shè)描述長度和給定假設(shè)下數(shù)據(jù)描述長度之和最小化的假設(shè)最小描述長度準(zhǔn)則：最小描述長度準(zhǔn)則(4)如果選擇C1為假設(shè)的最優(yōu)編碼CH,C2為最優(yōu)編碼CD|h,那么hMDL=hMAP可將MDL準(zhǔn)則想象為選擇最短的方法來重新編碼訓(xùn)練數(shù)據(jù),其中不僅計算假設(shè)的

20、大小,并且計算給定假設(shè)時編碼數(shù)據(jù)的附加開銷將MDL準(zhǔn)則應(yīng)用于決策樹,如何選擇假設(shè)和數(shù)據(jù)的表示C1和C2對于C1,很自然地選擇某種明確的決策樹編碼方法,其中描述長度隨著樹中節(jié)點和邊的增長而增加對于C2,如果訓(xùn)練分類f(xi)與假設(shè)的預(yù)計相同,那么就不需要傳輸有關(guān)這些樣例的任何信息；如果不同,則要傳輸更正消息最小描述長度準(zhǔn)則(5)MDL準(zhǔn)則提供了一種方法在假設(shè)的復(fù)雜性和假設(shè)產(chǎn)生錯誤的數(shù)量之間進(jìn)行折中,它有可能選擇一個較短的產(chǎn)生少量錯誤的假設(shè),而不是完美地分類訓(xùn)練數(shù)據(jù)的較長的假設(shè)上面討論自然給出了一種處理數(shù)據(jù)過度擬合的方法Quinlan&Rivest描述了應(yīng)用MDL準(zhǔn)則選擇決策樹大小的幾個實驗,報告

21、指出,基于MDL的方法產(chǎn)生的決策樹的精度相當(dāng)于第3章中討論的標(biāo)準(zhǔn)樹修剪方法第125頁,6.6節(jié)最后一段的含義貝葉斯最優(yōu)分類器前面我們討論的問題是：給定訓(xùn)練數(shù)據(jù),最可能的假設(shè)是什么另一個相關(guān)的更有意義的問題是：給定訓(xùn)練數(shù)據(jù),對新實例的最可能的分類是什么顯然,第二個問題的解決可以將第一個問題的結(jié)果(MAP)應(yīng)用到新實例上得到,還存在更好的算法貝葉斯最優(yōu)分類器(2)例子考慮一個包含三個假設(shè)h1,h2,h3的假設(shè)空間.假定已知訓(xùn)練數(shù)據(jù)時三個假設(shè)的后驗概率分別是0.4,0.3,0.3,因此h1為MAP假設(shè).若一新實例x被h1分類為正,被h2和h3分類為反計算所有假設(shè),x為正例的概率為0.4,為反例的概率

22、為0.6因此,這時最可能的分類與MAP假設(shè)生成的分類不同貝葉斯最優(yōu)分類器(3)一般而言,新實例的最可能分類可通過合并所有假設(shè)的預(yù)測得到,用后驗概率來加權(quán).如果新實例的可能分類可取某集合V中的任一值vj,那么概率P(vj|D)表示新實例分類為vj的概率新實例的最優(yōu)分類為使P(vj|D)最大的vj值,貝葉斯最優(yōu)分類器為：貝葉斯最優(yōu)分類器(4)例子已知：新實例的可能分類集合為V=+,-P(h1|D)=0.4,P(-|h1)=0,P(+|h1)=1 P(h2|D)=0.3,P(-|h2)=1,P(+|h2)=0 P(h3|D)=0.3,P(-|h3)=1,P(+|h2)=0因此：貝葉斯最優(yōu)分類器(5)

23、貝葉斯最優(yōu)分類器在給定可用數(shù)據(jù),假設(shè)空間及這些假設(shè)的先驗概率下使新實例被正確分類的可能性達(dá)到最大貝葉斯最優(yōu)分類器的一個屬性：它所做的分類可以對應(yīng)于H中不存在的假設(shè)使用式子6.18來分類X中的每個實例,按此定義的實例標(biāo)注不一定對應(yīng)于H中的任一單個假設(shè)h對實例的標(biāo)注將貝葉斯分類器看成是不同于假設(shè)空間H的另一空間H,在其上應(yīng)用貝葉斯公式.H有效地包含了一組假設(shè),它能在H中多個假設(shè)的線性組合所作的預(yù)言中進(jìn)行比較Gibbs算法貝葉斯最優(yōu)分類器能從給定訓(xùn)練數(shù)據(jù)中獲得最好的性能,但算法的開銷很大一個替代的,非最優(yōu)的方法是Gibbs算法,定義如下：按照H上的后驗概率分布,從H中隨機選擇假設(shè)h使用h來預(yù)言下一個

24、實例x的分類在一定條件下,Gibbs算法的誤分類率的期望值最多為貝葉斯最優(yōu)分類器的兩倍.確切地講,期望值是在隨機抽取的目標(biāo)概念上作出的,抽取過程按照學(xué)習(xí)器假定的先驗概率對概念學(xué)習(xí)問題的一個啟示：如果學(xué)習(xí)器假定H上有均勻的先驗概率,而且如果目標(biāo)概念實際上也按該分布抽取,那么當(dāng)前變型空間中隨機抽取的假設(shè)對下一實例分類的期望誤差最多為貝葉斯分類器的兩倍()樸素貝葉斯分類器應(yīng)用的學(xué)習(xí)任務(wù)：每個實例x可由屬性值的合取描述,而目標(biāo)函數(shù)f(x)從某有限集合V中取值貝葉斯方法的新實例分類目標(biāo)是在給定描述實例的屬性值下,得到最可能的目標(biāo)值vMAP使用貝葉斯公式變化上式樸素貝葉斯分類器(2)基于訓(xùn)練數(shù)據(jù)估計式子6

25、.19中的兩個數(shù)據(jù)項的值估計P(vj)很容易：計算每個目標(biāo)值vj出現(xiàn)在訓(xùn)練數(shù)據(jù)中的頻率估計P(a1,.an|vj)遇到數(shù)據(jù)稀疏問題,除非有一個非常大的訓(xùn)練數(shù)據(jù)集,否則無法獲得可靠的估計樸素貝葉斯分類器引入一個簡單的假定避免數(shù)據(jù)稀疏問題：在給定目標(biāo)值時,屬性值之間相互條件獨立,即樸素貝葉斯分類器(3)樸素貝葉斯分類器的定義：從訓(xùn)練數(shù)據(jù)中估計不同P(ai|vj)項的數(shù)量比要估計P(a1,.,an|vj)項所需的量小得多只要條件獨立性得到滿足,樸素貝葉斯分類vNB等于MAP分類,否則是近似樸素貝葉斯分類器與其他已介紹的學(xué)習(xí)方法的一個區(qū)別：沒有明確地搜索可能假設(shè)空間的過程(假設(shè)的形成不需要搜索,只是簡

26、單地計算訓(xùn)練樣例中不同數(shù)據(jù)組合的出現(xiàn)頻率)樸素貝葉斯分類器(4)舉例表3-2提供了目標(biāo)概念PlayTennis的14個訓(xùn)練樣例,給新實例分類根據(jù)表3-2,可以計算出上式需要的概率值P(yes)=9/14=0.64 P(no)=5/14=0.36 P(strong|yes)=3/9=0.33 P(strong|no)=3/5=0.60.求vNB P(yes)P(sunny|yes)P(cool|yes)P(high|yes)P(strong|yes)=0.0053 P(no)P(sunny|no)P(cool|no)P(high|no)P(strong|no)=0.0206 vNB=no樸素貝葉

27、斯分類器(5)估計概率我們通過在全部事件基礎(chǔ)上觀察某事件出現(xiàn)的比例來估計概率當(dāng)樣本很小時,采用平滑技術(shù),m-估計p是將要確定的概率的先驗估計,而m是一稱為等效樣本大小的常量在缺少其他信息時,選擇p的一種典型的方法是均勻概率,比如某屬性有k個可能值,那么p=1/k m被稱為等效樣本大小的原因是：式子6.22可被解釋為將n個實際的觀察擴大,加上m個按p分布的虛擬樣本舉例：學(xué)習(xí)分類文本利用貝葉斯方法學(xué)習(xí)目標(biāo)概念,然后用于文本自動過濾,比如我感興趣的電子新聞稿討論機器學(xué)習(xí)的萬維網(wǎng)頁本節(jié)描述一個基于樸素貝葉斯分類器的文本分類的通用算法,它是目前所知的文本分類的最有效方法之一問題框架：實例空間X包含了所有

28、的文本文檔,給定某未知目標(biāo)函數(shù)f(x)的一組訓(xùn)練樣例,f(x)的值來自某有限集合V(作為示例,此處令V=like,dislike)舉例：學(xué)習(xí)分類文本(2)應(yīng)用樸素貝葉斯分類器的兩個主要設(shè)計問題：怎樣將任意文檔表示為屬性值的形式如何估計樸素貝葉斯分類器所需的概率表示文檔的方法給定一個文本文檔,對每個單詞的位置定義一個屬性,該屬性的值為在此位置上找到的英文單詞假定我們共有1000個訓(xùn)練文檔,其中700個分類為dislike,300個分類為like,現(xiàn)在要對下面的新文檔進(jìn)行分類：This is an example document for the naive Bayes classifier.Th

29、is document contains only one paragraph,or two sentences.舉例：學(xué)習(xí)分類文本(3)計算式注意此處貝葉斯分類器隱含的獨立性假設(shè)并不成立.通常,某個位置上出現(xiàn)某個單詞的概率與前后位置上出現(xiàn)的單詞是相關(guān)的雖然此處獨立性假設(shè)不精確,但別無選擇,否則要計算的概率項極為龐大.另外實踐中,樸素貝葉斯學(xué)習(xí)器在許多文本分類問題中性能非常好舉例：學(xué)習(xí)分類文本(4)需要估計概率項P(vi)和P(ai=wk|vi).前一項可基于每一類在訓(xùn)練數(shù)據(jù)中的比例很容易得到,后一項含三個參數(shù),出現(xiàn)數(shù)據(jù)稀疏問題再引入一個假定以減少需要估計的概率項的數(shù)量：假定單詞wk出現(xiàn)的概率

30、獨立于單詞所在的位置,即P(ai=wk|vi)=P(wk|vj)作此假定的一個主要優(yōu)點在于：使可用于估計每個所需概率的樣例數(shù)增加了,因此增加了估計的可靠程度采納m-估計方法,即有統(tǒng)一的先驗概率并且m等于詞匯表的大小,因此表6-2用于學(xué)習(xí)和分類文本的樸素貝葉斯算法Learn_Naive_Bayes_Text(Examples,V)Examples為一組文本文檔以及它們的目標(biāo)值.V為所有可能目標(biāo)值的集合.此函數(shù)作用是學(xué)習(xí)概率項P(wk|vj)和P(vj).收集Examples中所有的單詞,標(biāo)點符號以及其他記號Vocabulary在Examples中任意文本文檔中出現(xiàn)的所有單詞及記號的集合計算所需要

31、的概率項P(vj)和P(wk|vj)對V中每個目標(biāo)值vj docsj Examples中目標(biāo)值為vj的文檔子集P(vj)|docsj|/|Examples|Textj將docsj中所有成員連接起來建立的單個文檔n在Textj中不同單詞位置的總數(shù)對Vocabulary中每個單詞wk nk單詞wk出現(xiàn)在Textj中的次數(shù)P(wk|vj)(nk+1)/(n+|Vocabulary|)表6-2用于學(xué)習(xí)和分類文本的樸素貝葉斯算法(2)Classify_Naive_Bayes_Text(Doc)對文檔Doc返回其估計的目標(biāo)值,ai代表在Doc中的第i個位置上出現(xiàn)的單詞positions在Doc中的所有單詞

32、位置,它包含能在Vocabulary中找到的記號返回vNB,實驗結(jié)果Joachims將此算法用于新聞組文章的分類每一篇文章的分類是該文章所屬的新聞組名稱20個新聞組,每個新聞組有1000篇文章,共2萬個文檔2/3作為訓(xùn)練樣例,1/3進(jìn)行性能測量詞匯表不包含最常用詞(比如the,of)和罕見詞(數(shù)據(jù)集中出現(xiàn)次數(shù)少于3)Lang用此算法學(xué)習(xí)目標(biāo)概念我感興趣的新聞組文章NewsWeeder系統(tǒng),讓用戶閱讀新聞組文章并為其評分,然后使用這些評分的文章作為訓(xùn)練樣例,來預(yù)測后續(xù)文章哪些是用戶感興趣的每天向用戶展示前10%的自動評分文章,它建立的文章序列中包含的用戶感興趣的文章比通常高34倍貝葉斯信念網(wǎng)樸素

33、貝葉斯分類器假定各個屬性取值在給定目標(biāo)值v下是條件獨立的,從而化簡了最優(yōu)貝葉斯分類的計算復(fù)雜度.但在多數(shù)情況下,這一條件獨立假定過于嚴(yán)厲了.貝葉斯信念網(wǎng)描述的是一組變量所遵從的概率分布,它通過一組條件概率來指定一組條件獨立性假設(shè)貝葉斯信念網(wǎng)中可表述變量的一個子集上的條件獨立性假定,因此,貝葉斯信念網(wǎng)提供了一種中間的方法,它比樸素貝葉斯分類器的限制更少,又比在所有變量中計算條件依賴更可行貝葉斯信念網(wǎng)(2)貝葉斯信念網(wǎng)描述了一組變量上的概率分布考慮一任意的隨機變量集合Y1.Yn,其中每個Yi可取的值集合為V(Yi)變量集合Y的聯(lián)合空間為叉乘V(Y1).V(Yn)在此聯(lián)合空間上的概率分布稱為聯(lián)合概率

34、分布,聯(lián)合概率分布指定了元組的每個可能的變量約束的概率貝葉斯信念網(wǎng)則對一組變量描述了聯(lián)合概率分布條件獨立性精確定義條件獨立性令X,Y和Z為3個離散值隨機變量,當(dāng)給定Z值時X服從的概率分布獨立于Y的值,稱X在給定Z時條件獨立于Y,即上式通常簡寫成P(X|Y,Z)=P(X|Z)擴展到變量集合下面等式成立時,稱變量集合X1.Xl在給定變量集合Z1.Zn時條件獨立于變量集合Y1.Ym條件獨立性與樸素貝葉斯分類器的之間的關(guān)系貝葉斯信念網(wǎng)的表示貝葉斯信念網(wǎng)(簡稱貝葉斯網(wǎng))表示一組變量的聯(lián)合概率分布一般地說,貝葉斯網(wǎng)表示聯(lián)合概率分布的方法是指定一組條件獨立性假定(有向無環(huán)圖)以及一組局部條件概率集合圖6-3

35、,聯(lián)合空間中每個變量在貝葉斯網(wǎng)中表示為一個節(jié)點,每個變量需要兩種類型的信息網(wǎng)絡(luò)弧表示斷言此變量在給定其直接前驅(qū)時條件獨立于其非后繼每個變量有一個條件概率表,描述了該變量在給定其立即前驅(qū)時的概率分布貝葉斯信念網(wǎng)的表示(2)對網(wǎng)絡(luò)變量的元組賦以所希望的值(y1.yn)的聯(lián)合概率計算公式如下：所有變量的局部條件概率表以及由網(wǎng)絡(luò)所描述的一組條件獨立假定,描述了該網(wǎng)絡(luò)的整個聯(lián)合概率分布貝葉斯信念網(wǎng)的推理可以用貝葉斯網(wǎng)在給定其他變量的觀察值時推理出某些目標(biāo)變量的值由于所處理的是隨機變量,所以一般不會賦予目標(biāo)變量一個確切的值真正需要推理的是目標(biāo)變量的概率分布,它指定了在給予其他變量的觀察值條件下,目標(biāo)變量取

36、每一個可能值的概率在網(wǎng)絡(luò)中所有其他變量都確切知道的情況下,這一推理步驟很簡單一般來說,貝葉斯網(wǎng)絡(luò)可用于在知道某些變量的值或分布時計算網(wǎng)絡(luò)中另一部分變量的概率分布貝葉斯信念網(wǎng)的推理(2)對任意貝葉斯網(wǎng)絡(luò)的概率的確切推理已經(jīng)知道是一個NP難題Monte Carlo方法提供了一種近似的結(jié)果,通過對未觀察到的變量進(jìn)行隨機采樣理論上,即使是貝葉斯網(wǎng)絡(luò)中的近似推理也可能是NP難題實踐中許多情況下近似的方法被證明是有效的學(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ò)變量可以直接從每個訓(xùn)練樣例中觀察到,或某些變量不能觀察到如果網(wǎng)絡(luò)結(jié)構(gòu)已知且變

37、量可以從訓(xùn)練樣例中完全獲得,那么得到條件概率表就比較簡單如果網(wǎng)絡(luò)結(jié)構(gòu)已知,但只有一部分變量值能在數(shù)據(jù)中觀察到,學(xué)習(xí)問題就困難多了.這類似于在人工神經(jīng)網(wǎng)絡(luò)中學(xué)習(xí)隱藏單元的權(quán)值Russtll(1995)提出了一個簡單的梯度上升過程以學(xué)習(xí)條件概率表中的項,相當(dāng)于對表項搜索極大似然假設(shè)貝葉斯網(wǎng)的梯度上升訓(xùn)練令wijk代表條件概率表的一個表項,即在給定父節(jié)點Ui取值uik時,網(wǎng)絡(luò)變量Yi值為yij的概率例如圖6-3,wijk為最右上方的表項,那么Yi為變量Campfire,Ui是其父節(jié)點的元組,yij=True,且uik=貝葉斯網(wǎng)的梯度上升訓(xùn)練(2)lnP(D|h)的梯度由對每個wijk求導(dǎo)數(shù)得到例如,

38、為計算圖6-3中表左上方的表項的lnP(D|h)的導(dǎo)數(shù),需要對D中每個訓(xùn)練樣例d計算P(Campfire=True,Storm=False,BusTourGroup=False|d)當(dāng)訓(xùn)練樣例中無法觀察到這些變量時,這些概率可用標(biāo)準(zhǔn)的貝葉斯網(wǎng)從d中觀察到的變量中推理得到這些量能夠很容易地從貝葉斯網(wǎng)推理過程中得到,幾乎不需要附加的開銷貝葉斯網(wǎng)的梯度上升訓(xùn)練(3)式子6.25的推導(dǎo)用Ph(D)來表示P(D|h)假定在數(shù)據(jù)集D中的各樣例d都是獨立抽取的貝葉斯網(wǎng)的梯度上升訓(xùn)練(4)更新權(quán)值歸一化處理,保持在區(qū)間0,1之間,且jwijk對所有i,k保持為1這個算法只保證找到局部最優(yōu)解,替代梯度上升的一個

39、算法是EM算法學(xué)習(xí)貝葉斯網(wǎng)的結(jié)構(gòu)如果貝葉斯網(wǎng)的結(jié)構(gòu)未知,那么需要學(xué)習(xí)貝葉斯網(wǎng)的結(jié)構(gòu)Cooper&Herskovits提出了一個貝葉斯評分尺度,以便從不同網(wǎng)絡(luò)中進(jìn)行選擇Cooper&Herskovits提出了算法K2,啟發(fā)式算法,用于在數(shù)據(jù)完全可觀察時學(xué)習(xí)網(wǎng)絡(luò)結(jié)構(gòu)基于約束的學(xué)習(xí)貝葉斯網(wǎng)絡(luò)結(jié)構(gòu)：從數(shù)據(jù)中推導(dǎo)出獨立和相關(guān)的關(guān)系,然后用這些關(guān)系來構(gòu)造貝葉斯網(wǎng)EM算法在許多實際的學(xué)習(xí)問題框架中,相關(guān)實例特征中只有一部分可觀察到已有許多方法被提出來處理存在未觀察到變量的問題比如,如果某些變量有時能觀察到,有時不能,那么可以用觀察到該變量的實例去預(yù)測未觀察到的實例中的變量的值EM算法是存在隱含變量時廣泛使用

40、的一種學(xué)習(xí)方法,可用于變量的值從來沒有被直接觀察到的情形,只要這些變量所遵循的概率分布的一般形式已知用于貝葉斯網(wǎng)的訓(xùn)練用于馬爾可夫模型的訓(xùn)練估計k個高斯分布的均值考慮D是一個實例集合,它由k個不同正態(tài)分布的混合所得分布生成每個實例使用一個兩步驟的過程形成：首先,隨機選擇k個正態(tài)分布中的一個其次,隨機變量xi按照此選擇的分布生成考慮一個簡單情形：單個正態(tài)分布的選擇基于均勻的概率進(jìn)行,且k個正態(tài)分布有相同的方差學(xué)習(xí)任務(wù)：輸出一個假設(shè)h=,描述k個分布中每個分布的均值,找到極大似然假設(shè),即使得p(D|h)最大化的假設(shè)估計k個高斯分布的均值(2)當(dāng)給定從一個正態(tài)分布中抽取的數(shù)據(jù)實例x1,.,xm時,很

41、容易計算該分布的均值的極大似然假設(shè),它是6.4節(jié)中式子6.6的一個特例,表示如下然而,現(xiàn)在的問題涉及k個不同正態(tài)分布,而且不知道哪個實例是哪個分布產(chǎn)生的.這是一個涉及隱藏變量的典型例子對于圖6-4的例子,每個實例的完整描述是三元組,其中xi是第i個實例的觀測值,zi1和zi2表示哪個正態(tài)分布被用來產(chǎn)生xi,是隱藏變量估計k個高斯分布的均值(3)如果zi1和zi2的值可知,就可用式子6.27來解決,否則使用EM算法EM算法根據(jù)當(dāng)前假設(shè),不斷地再估計隱藏變量zij的期望值,然后用這些隱藏變量的期望值重新計算極大似然假設(shè)以圖6-4為例,先將假設(shè)初始化為h=計算每個隱藏變量zij的期望值Ezij,假定

42、當(dāng)前假設(shè)h=成立計算一個新的極大似然假設(shè)h=,假定每個隱藏變量zij所取值是第一步得到的期望值Ezij.將假設(shè)替換為h=,然后循環(huán)兩個步驟的計算式Ezij正是實例xi由第j個正態(tài)分布生成的概率第二步,使用第一步得到的Ezij來導(dǎo)出一新的極大似然假設(shè)兩個步驟的計算式(2)第二步中的表達(dá)式類似于式6.28,只是變成了加權(quán)樣本均值EM算法的要點：當(dāng)前的假設(shè)用于估計未知變量,而這些變量的期望值再被用于改進(jìn)假設(shè)可以證明：算法的每一次循環(huán)中,EM算法能使似然P(D|h)增加,除非P(D|h)達(dá)到局部最大,因此算法收斂到一個局部最大似然假設(shè)EM算法的一般表述EM算法可用于許多問題框架：其中需要估計一組描述基準(zhǔn)概率分布的參數(shù),只給定了由此分布產(chǎn)生的全部數(shù)據(jù)中能觀察到的一部分.上面的二均值問題中,感興趣的參數(shù)是=,全部數(shù)據(jù)是三元組,而只能觀察到xi一般地,令待估計參數(shù)是,全部數(shù)據(jù)Y=X Z,其