《貝葉斯學(xué)習(xí)轉(zhuǎn)》word版

1、.貝葉斯學(xué)習(xí) 轉(zhuǎn)機(jī)器學(xué)習(xí)-貝葉斯學(xué)習(xí) Mitchell譯者：曾華軍等講者：陶曉鵬機(jī)器學(xué)習(xí)第6章貝葉斯學(xué)習(xí)概述貝葉斯推理提供了一種概率手段,基于如下的假定：待考察的量遵循某概率分布,且可根據(jù)這些概率及已觀察到的數(shù)據(jù)進(jìn)展推理,以作出最優(yōu)的決策.貝葉斯推理為衡量多個(gè)假設(shè)的置信度提供了定量的方法貝葉斯推理為直接操作概率的學(xué)習(xí)算法提供了根底,也為其他算法的分析提供了理論框架簡介貝葉斯學(xué)習(xí)算法與機(jī)器學(xué)習(xí)相關(guān)的兩個(gè)原因：貝葉斯學(xué)習(xí)算法可以計(jì)算顯示的假設(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í)方法的特性觀察到的每個(gè)訓(xùn)練樣例可以增量地降低或升高某假設(shè)的估計(jì)概率.而其他算法會(huì)在某個(gè)假設(shè)與任一樣例不一致時(shí)完全去掉該假設(shè)先驗(yàn)知識可以與觀察數(shù)據(jù)一起決定假設(shè)的最終概率,先驗(yàn)知識的形式是：1每個(gè)候選假設(shè)的先驗(yàn)概率；2每個(gè)可能假設(shè)在可觀察數(shù)據(jù)上的概率分布貝葉斯方法可允許假設(shè)做出不確定性的預(yù)測新的實(shí)例分類可由多個(gè)假設(shè)一起做出預(yù)測,用它們的概率來加權(quán)即使在貝葉斯方法計(jì)算復(fù)雜度較高時(shí),它們?nèi)钥勺鳛橐粋€(gè)最優(yōu)的決策標(biāo)準(zhǔn)衡量其他方法貝葉斯方法的難度難度之一：需要概率的初始知識,當(dāng)概率預(yù)先未知時(shí),可以基于

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

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

5、能性越大,那么D對h的支持度越小極大后驗(yàn)假設(shè)學(xué)習(xí)器在候選假設(shè)集合H中尋找給定數(shù)據(jù)D時(shí)可能性最大的假設(shè)h,h被稱為極大后驗(yàn)假設(shè)MAP確定MAP的方法是用貝葉斯公式計(jì)算每個(gè)候選假設(shè)的后驗(yàn)概率,計(jì)算式如下最后一步,去掉了PD,因?yàn)樗遣灰蕾囉趆的常量極大似然假設(shè)在某些情況下,可假定H中每個(gè)假設(shè)有一樣的先驗(yàn)概率,這款式子6.2可以進(jìn)一步簡化,只需考慮PD|h來尋找極大可能假設(shè).PD|h常被稱為給定h時(shí)數(shù)據(jù)D的似然度,而使PD|h最大的假設(shè)被稱為極大似然假設(shè)假設(shè)空間H可擴(kuò)展為任意的互斥命題集合,只要這些命題的概率之和為1舉例：一個(gè)醫(yī)療診斷問題有兩個(gè)可選的假設(shè)：病人有癌癥,病人無癌癥可用數(shù)據(jù)來自化驗(yàn)結(jié)果：

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

7、驗(yàn)概率可將上面的結(jié)果歸一化以使它們的和為1 Pcanner|+=0.0078/0.0078+0.0298=0.21 Pcancer|-=0.79貝葉斯推理的結(jié)果很大程度上依賴于先驗(yàn)概率,另外不是完全承受或回絕假設(shè),只是在觀察到較多的數(shù)據(jù)后增大或減小了假設(shè)的可能性根本概率公式表乘法規(guī)那么：PA B=PA|BPB=PB|APA加法規(guī)那么：PA B=PA+PB-PA B貝葉斯法那么：Ph|D=PD|hPh/PD全概率法那么：假設(shè)事件A1.An互斥,且滿足,那么貝葉斯法那么和概念學(xué)習(xí)貝葉斯法那么為計(jì)算給定訓(xùn)練數(shù)據(jù)下任一假設(shè)的后驗(yàn)概率提供了原那么性方法,因此可以直接將其作為一個(gè)根本的學(xué)習(xí)方法：計(jì)算每個(gè)假

8、設(shè)的概率,再輸出其中概率最大的.這個(gè)方法稱為Brute-Force貝葉斯概念學(xué)習(xí)算法.將上面方法與第2章介紹的概念學(xué)習(xí)算法比較,可以看到：在特定條件下,它們學(xué)習(xí)得到一樣的假設(shè),不同的是第2章的方法不明確計(jì)算概率,而且效率更高.Brute-Force貝葉斯概念學(xué)習(xí)概念學(xué)習(xí)問題：有限假設(shè)空間H定義在實(shí)例空間X上,任務(wù)是學(xué)習(xí)某個(gè)目的概念c.Brute-Force MAP學(xué)習(xí)算法對于H中每個(gè)假設(shè)h,計(jì)算后驗(yàn)概率輸出有最高后驗(yàn)概率的假設(shè)上面算法需要較大計(jì)算量,因?yàn)樗?jì)算每個(gè)假設(shè)的后驗(yàn)概率,對于大的假設(shè)空間顯得不實(shí)在際,但是它提供了一個(gè)標(biāo)準(zhǔn)以判斷其他概念學(xué)習(xí)算法的性能特定情況下的MAP假設(shè)假定訓(xùn)練數(shù)據(jù)D

9、是無噪聲的,即di=cxi目的概念c包含在假設(shè)空間H中每個(gè)假設(shè)的概率一樣求得由于所有假設(shè)的概率之和是1,因此由于訓(xùn)練數(shù)據(jù)無噪聲,那么給定假設(shè)h時(shí),與h一致的D的概率為1,不一致的概率為0,因此特定情況下的MAP假設(shè)2考慮Brute-Force MAP算法的第一步h與D不一致,h與D一致,VSH,D是關(guān)于D的變型空間見第2章,即與D一致的假設(shè)集特定情況下的MAP假設(shè)3PD的推導(dǎo)PD假設(shè)的概率演化情況如圖6-1所示,初始時(shí)所有假設(shè)具有一樣的概率,當(dāng)訓(xùn)練數(shù)據(jù)逐步出現(xiàn)后,不一致假設(shè)的概率變?yōu)?,而整個(gè)概率的和為1,它們均勻分布到剩余的一致假設(shè)中每個(gè)一致的假設(shè)都是MAP假設(shè)MAP假設(shè)和一致學(xué)習(xí)器一致學(xué)習(xí)

10、器：假設(shè)某個(gè)學(xué)習(xí)器輸出的假設(shè)在訓(xùn)練樣例上為0錯(cuò)誤率,那么稱為一致學(xué)習(xí)器假設(shè)H上有均勻的先驗(yàn)概率,且訓(xùn)練數(shù)據(jù)是確定性和無噪聲的,任意一致學(xué)習(xí)器將輸出一個(gè)MAP假設(shè)Find-S算法按照特殊到一般的順序搜索架設(shè)空間H,并輸出一個(gè)極大特殊的一致假設(shè),因此可知在上面定義的Ph和PD|h概率分布下,它輸出MAP假設(shè)更一般地,對于先驗(yàn)概率偏袒于更特殊假設(shè)的任何概率分布,Find-S輸出的假設(shè)都是MAP假設(shè)MAP假設(shè)和一致學(xué)習(xí)器2貝葉斯框架提出了一種刻畫學(xué)習(xí)算法行為的方法,即便該學(xué)習(xí)算法不進(jìn)展概率操作,通過確定算法輸出最優(yōu)假設(shè)時(shí)使用的概率分布Ph和PD|h,可以刻畫出算法具有最優(yōu)行為時(shí)的隱含假定使用貝葉斯方法

11、刻畫學(xué)習(xí)算法,與提醒學(xué)習(xí)器中的歸納偏置在思想上是類似的在第2章,將學(xué)習(xí)算法的歸納偏置定義為斷言集合B,通過它可充分地演繹推斷出學(xué)習(xí)器所執(zhí)行的歸納推理結(jié)果,即學(xué)習(xí)器的輸出是由其輸入和隱含的歸納偏置所演繹得出的MAP假設(shè)和一致學(xué)習(xí)器3貝葉斯解釋對于描繪學(xué)習(xí)算法中的隱含假定提供了另一種方法,用基于貝葉斯理論的一個(gè)等效的概率推理系統(tǒng)來建模貝葉斯解釋隱含的假定形式為：H上的先驗(yàn)概率由Ph分布給出,數(shù)據(jù)回絕或承受假設(shè)的強(qiáng)度由PD|h給出在這些假定的概率分布后,一個(gè)基于貝葉斯理論的概率推理系統(tǒng)將產(chǎn)生等效于Find-S,候選消除等算法的輸入-輸出行為極大似然和最小誤差平方假設(shè)前面分析說明：某些學(xué)習(xí)算法即使沒有

12、顯示地使用貝葉斯規(guī)那么,或以某種形式計(jì)算概率,但它們輸出的結(jié)果符合貝葉斯原理,是一個(gè)MAP假設(shè)通過簡單的貝葉斯分析,可以說明在特定前提下,任一學(xué)習(xí)算法假設(shè)使輸出的假設(shè)預(yù)測和訓(xùn)練數(shù)據(jù)之間的誤差平方和最小化,它將輸出一極大似然假設(shè)上面結(jié)論的意義是,對于許多神經(jīng)網(wǎng)絡(luò)和曲線擬合的方法,假設(shè)它們試圖在訓(xùn)練數(shù)據(jù)上使誤差平方和最小化,此結(jié)論提供了基于貝葉斯的理論根據(jù)極大似然和最小誤差平方假設(shè)2問題框架：學(xué)習(xí)器L工作在實(shí)例空間X和假設(shè)空間H上,H中的假設(shè)為X上定義的某種實(shí)數(shù)值函數(shù).L面臨的問題是學(xué)習(xí)一個(gè)從H中抽取出的未知目的函數(shù)f,給定m個(gè)訓(xùn)練樣例的集合,每個(gè)樣例的目的值被某隨機(jī)噪聲干擾,此隨機(jī)噪聲服從正態(tài)分

13、布更準(zhǔn)確地講,每個(gè)訓(xùn)練樣例是序偶,di=fxi+ei,ei是代表噪聲的隨機(jī)變量,假定ei的值是獨(dú)立抽取的,并且它們的分布服從0均值的正態(tài)分布學(xué)習(xí)器的任務(wù)是在所有假設(shè)有相等的先驗(yàn)概率前提下,輸出極大似然假設(shè)即MAP假設(shè)極大似然和最小誤差平方假設(shè)3用一個(gè)簡單情況,即線性函數(shù)來說明問題.如圖6-2所示,實(shí)線表示線性目的函數(shù)f,實(shí)點(diǎn)表示有噪聲的訓(xùn)練樣例集,虛線對應(yīng)有最小平方訓(xùn)練誤差的假設(shè)hML,即極大似然假設(shè).對于e這樣的連續(xù)變量上的概率,使用概率密度表示概率分布,它在所有值上的積分為1,用小寫的p表示.有限概率P有時(shí)又稱為概率質(zhì)量概率密度函數(shù)：極大似然和最小誤差平方假設(shè)4假定有一固定的訓(xùn)練實(shí)例集合,

14、因此只考慮相應(yīng)的目的值序列D=,這里di=fxi+ei.假定訓(xùn)練樣例是互相獨(dú)立的,給定h時(shí),可將PD|h寫成各pdi|h的積假設(shè)誤差ei服從0均值和未知方差2的正態(tài)分布,那么每個(gè)di服從均值為fxi,方差不變的正態(tài)分布.因此,pdi|h可寫為方差2,均值fxi的正態(tài)分布使用表5-4中的正態(tài)分布公式并將相應(yīng)的參數(shù)代入,由于概率di的表達(dá)式是在h為目的函數(shù)f的正確描繪條件下的,所以交換=fxi=hxi極大似然和最小誤差平方假設(shè)5hML上式說明了極大似然假設(shè)等價(jià)于使訓(xùn)練值和假設(shè)預(yù)測值之間的誤差的平方和最小的那個(gè)假設(shè)這個(gè)結(jié)論的前提是：訓(xùn)練值等于真實(shí)目的值加上隨機(jī)噪聲,其中隨機(jī)噪聲從一個(gè)均值為0的正態(tài)分

15、布中獨(dú)立抽取采用正態(tài)分布的合理性數(shù)學(xué)計(jì)算的簡潔性對許多物理系統(tǒng)的噪聲都有良好的近似第5章中心極限定律顯示,足夠多的獨(dú)立同分布隨機(jī)變量的和服從正態(tài)分布由許多獨(dú)立同分布的因素的和所生成的噪聲將成為正態(tài)分布當(dāng)然,現(xiàn)實(shí)中不同的分量對噪聲的奉獻(xiàn)也許不是同分布的使誤差平方最小化的方法經(jīng)常被用于神經(jīng)網(wǎng)絡(luò),曲線擬合及其他許多實(shí)函數(shù)逼近的算法中上面的分析只考慮了訓(xùn)練樣例的目的值中的噪聲,而沒有考慮實(shí)例屬性值的噪聲用于預(yù)測概率的極大似然假設(shè)問題框架：學(xué)習(xí)一個(gè)不確定性函數(shù)f：X0,1,它有兩個(gè)離散的值輸出這種不可預(yù)測性來源于未能觀察到的因素,導(dǎo)致目的函數(shù)的輸出是輸入的概率函數(shù)學(xué)習(xí)得到的神經(jīng)網(wǎng)絡(luò)或其他實(shí)函數(shù)學(xué)習(xí)器的輸

16、出是fx=1的概率,表示為f'：X0,1,即f'=Pfx=1用于預(yù)測概率的極大似然假設(shè)2Brute-Force法首先搜集對x的每個(gè)可能值觀察到的1和0的頻率,然后訓(xùn)練神經(jīng)網(wǎng)絡(luò),對每個(gè)x輸出目的頻率可以直接從f的訓(xùn)練樣例中訓(xùn)練神經(jīng)網(wǎng)絡(luò),然后推導(dǎo)出f'的極大似然假設(shè)D=.用于預(yù)測概率的極大似然假設(shè)3hML式子6.13與熵函數(shù)的一般式相似,因此它的負(fù)值常稱為穿插熵在神經(jīng)網(wǎng)絡(luò)中梯度搜索以到達(dá)似然最大化前面討論了利用式子6.13求極大似然假設(shè),現(xiàn)用Gh,D表示,為神經(jīng)網(wǎng)絡(luò)學(xué)習(xí)推導(dǎo)一個(gè)權(quán)值訓(xùn)練法那么,使用梯度上升法使Gh,D最大化考慮簡單的情況,假定神經(jīng)網(wǎng)絡(luò)從一個(gè)單層的sigmoi

17、d單元建立,那么在神經(jīng)網(wǎng)絡(luò)中梯度搜索以到達(dá)似然最大化2因?yàn)橐筆D|h最大化而不是最小化,因此執(zhí)行梯度上升搜索,而不是梯度下降搜索.與反向傳播更新法那么比照使誤差平方最小化的法那么尋找到極大似然假設(shè)的前提是：訓(xùn)練數(shù)據(jù)可以由目的函數(shù)值加上正態(tài)分布噪聲來模擬使穿插熵最小化的法那么尋找極大似然假設(shè)基于的前提是：觀察到的布爾值為輸入實(shí)例的概率函數(shù)最小描繪長度準(zhǔn)那么奧坎姆剃刀可以概括為：為觀察到的數(shù)據(jù)選擇最短的解釋此處給出一個(gè)貝葉斯分析,提出最小描繪長度準(zhǔn)那么,根據(jù)信息論中的根本概念來解釋hMAP的定義上式可以解釋為在特定的假設(shè)編碼表示方案上"優(yōu)先選擇短的假設(shè)"最小描繪長度準(zhǔn)那么2信

18、息論中的編碼理論設(shè)想要為隨機(jī)傳送的消息設(shè)計(jì)一個(gè)編碼,其中遇到消息i的概率是pi感興趣的是,使得傳輸隨機(jī)信息所需的最小期望傳送位數(shù)的編碼直觀上,為使期望的編碼長度最小,可能性大的消息應(yīng)該賦予較短的編碼Shannon&Weaver證明了最優(yōu)編碼對消息i的編碼長度為-log2pi使用代碼C來編碼消息i所需的位數(shù)被稱為消息i關(guān)于C的描繪長度,記為LCi最小描繪長度準(zhǔn)那么3使用編碼理論的結(jié)論來解釋等式6.16-log2Ph是在假設(shè)空間H的最優(yōu)編碼下h的描繪長度.換言之,這是假設(shè)h使用其最優(yōu)表示時(shí)的大小,CH為假設(shè)空間H的最優(yōu)編碼-log2PD|h是在給定假設(shè)h時(shí),訓(xùn)練數(shù)據(jù)D的描繪長度,CD|h是

19、假定發(fā)送者和接送者都知道假設(shè)h時(shí)描繪數(shù)據(jù)D的最優(yōu)編碼因此式子6.16顯示,hMAP是使假設(shè)描繪長度和給定假設(shè)下數(shù)據(jù)描繪長度之和最小化的假設(shè)最小描繪長度準(zhǔn)那么：最小描繪長度準(zhǔn)那么4假設(shè)選擇C1為假設(shè)的最優(yōu)編碼CH,C2為最優(yōu)編碼CD|h,那么hMDL=hMAP可將MDL準(zhǔn)那么想象為選擇最短的方法來重新編碼訓(xùn)練數(shù)據(jù),其中不僅計(jì)算假設(shè)的大小,并且計(jì)算給定假設(shè)時(shí)編碼數(shù)據(jù)的附加開銷將MDL準(zhǔn)那么應(yīng)用于決策樹,如何選擇假設(shè)和數(shù)據(jù)的表示C1和C2對于C1,很自然地選擇某種明確的決策樹編碼方法,其中描繪長度隨著樹中節(jié)點(diǎn)和邊的增長而增加對于C2,假設(shè)訓(xùn)練分類fxi與假設(shè)的預(yù)計(jì)一樣,那么就不需要傳輸有關(guān)這些樣例的

20、任何信息；假設(shè)不同,那么要傳輸更正消息最小描繪長度準(zhǔn)那么5MDL準(zhǔn)那么提供了一種方法在假設(shè)的復(fù)雜性和假設(shè)產(chǎn)生錯(cuò)誤的數(shù)量之間進(jìn)展折中,它有可能選擇一個(gè)較短的產(chǎn)生少量錯(cuò)誤的假設(shè),而不是完美地分類訓(xùn)練數(shù)據(jù)的較長的假設(shè)上面討論自然給出了一種處理數(shù)據(jù)過度擬合的方法Quinlan&Rivest描繪了應(yīng)用MDL準(zhǔn)那么選擇決策樹大小的幾個(gè)實(shí)驗(yàn),報(bào)告指出,基于MDL的方法產(chǎn)生的決策樹的精度相當(dāng)于第3章中討論的標(biāo)準(zhǔn)樹修剪方法第125頁,6.6節(jié)最后一段的含義貝葉斯最優(yōu)分類器前面我們討論的問題是：給定訓(xùn)練數(shù)據(jù),最可能的假設(shè)是什么另一個(gè)相關(guān)的更有意義的問題是：給定訓(xùn)練數(shù)據(jù),對新實(shí)例的最可能的分類是什么顯然,第

21、二個(gè)問題的解決可以將第一個(gè)問題的結(jié)果MAP應(yīng)用到新實(shí)例上得到,還存在更好的算法貝葉斯最優(yōu)分類器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è)一新實(shí)例x被h1分類為正,被h2和h3分類為反計(jì)算所有假設(shè),x為正例的概率為0.4,為反例的概率為0.6因此,這時(shí)最可能的分類與MAP假設(shè)生成的分類不同貝葉斯最優(yōu)分類器3一般而言,新實(shí)例的最可能分類可通過合并所有假設(shè)的預(yù)測得到,用后驗(yàn)概率來加權(quán).假設(shè)新實(shí)例的可能分類可取某集合V中的任一值vj,那么概率Pvj|D表示新實(shí)例分類為vj的概率新實(shí)例的最優(yōu)分類為使Pvj

22、|D最大的vj值,貝葉斯最優(yōu)分類器為：貝葉斯最優(yōu)分類器4例子：新實(shí)例的可能分類集合為V=+,-Ph1|D=0.4,P-|h1=0,P+|h1=1 Ph2|D=0.3,P-|h2=1,P+|h2=0 Ph3|D=0.3,P-|h3=1,P+|h2=0因此：貝葉斯最優(yōu)分類器5貝葉斯最優(yōu)分類器在給定可用數(shù)據(jù),假設(shè)空間及這些假設(shè)的先驗(yàn)概率下使新實(shí)例被正確分類的可能性到達(dá)最大貝葉斯最優(yōu)分類器的一個(gè)屬性：它所做的分類可以對應(yīng)于H中不存在的假設(shè)使用式子6.18來分類X中的每個(gè)實(shí)例,按此定義的實(shí)例標(biāo)注不一定對應(yīng)于H中的任一單個(gè)假設(shè)h對實(shí)例的標(biāo)注將貝葉斯分類器看成是不同于假設(shè)空間H的另一空間H',在其上

23、應(yīng)用貝葉斯公式.H'有效地包含了一組假設(shè),它能在H中多個(gè)假設(shè)的線性組合所作的預(yù)言中進(jìn)展比較Gibbs算法貝葉斯最優(yōu)分類器能從給定訓(xùn)練數(shù)據(jù)中獲得最好的性能,但算法的開銷很大一個(gè)替代的,非最優(yōu)的方法是Gibbs算法,定義如下：按照H上的后驗(yàn)概率分布,從H中隨機(jī)選擇假設(shè)h使用h來預(yù)言下一個(gè)實(shí)例x的分類在一定條件下,Gibbs算法的誤分類率的期望值最多為貝葉斯最優(yōu)分類器的兩倍.確切地講,期望值是在隨機(jī)抽取的目的概念上作出的,抽取過程按照學(xué)習(xí)器假定的先驗(yàn)概率對概念學(xué)習(xí)問題的一個(gè)啟示：假設(shè)學(xué)習(xí)器假定H上有均勻的先驗(yàn)概率,而且假設(shè)目的概念實(shí)際上也按該分布抽取,那么當(dāng)前變型空間中隨機(jī)抽取的假設(shè)對下一實(shí)

24、例分類的期望誤差最多為貝葉斯分類器的兩倍樸素貝葉斯分類器應(yīng)用的學(xué)習(xí)任務(wù)：每個(gè)實(shí)例x可由屬性值的合取描繪,而目的函數(shù)fx從某有限集合V中取值貝葉斯方法的新實(shí)例分類目的是在給定描繪實(shí)例的屬性值下,得到最可能的目的值vMAP使用貝葉斯公式變化上式樸素貝葉斯分類器2基于訓(xùn)練數(shù)據(jù)估計(jì)式子6.19中的兩個(gè)數(shù)據(jù)項(xiàng)的值估計(jì)Pvj很容易：計(jì)算每個(gè)目的值vj出如今訓(xùn)練數(shù)據(jù)中的頻率估計(jì)Pa1,.an|vj遇到數(shù)據(jù)稀疏問題,除非有一個(gè)非常大的訓(xùn)練數(shù)據(jù)集,否那么無法獲得可靠的估計(jì)樸素貝葉斯分類器引入一個(gè)簡單的假定防止數(shù)據(jù)稀疏問題：在給定目的值時(shí),屬性值之間互相條件獨(dú)立,即樸素貝葉斯分類器3樸素貝葉斯分類器的定義：從訓(xùn)練

25、數(shù)據(jù)中估計(jì)不同Pai|vj項(xiàng)的數(shù)量比要估計(jì)Pa1,.,an|vj項(xiàng)所需的量小得多只要條件獨(dú)立性得到滿足,樸素貝葉斯分類vNB等于MAP分類,否那么是近似樸素貝葉斯分類器與其他已介紹的學(xué)習(xí)方法的一個(gè)區(qū)別：沒有明確地搜索可能假設(shè)空間的過程假設(shè)的形成不需要搜索,只是簡單地計(jì)算訓(xùn)練樣例中不同數(shù)據(jù)組合的出現(xiàn)頻率樸素貝葉斯分類器4舉例表3-2提供了目的概念PlayTennis的14個(gè)訓(xùn)練樣例,給新實(shí)例分類根據(jù)表3-2,可以計(jì)算出上式需要的概率值Pyes=9/14=0.64 Pno=5/14=0.36 Pstrong|yes=3/9=0.33 Pstrong|no=3/5=0.60.求vNB PyesPsu

26、nny|yesPcool|yesPhigh|yesPstrong|yes=0.0053 PnoPsunny|noPcool|noPhigh|noPstrong|no=0.0206 vNB=no樸素貝葉斯分類器5估計(jì)概率我們通過在全部事件根底上觀察某事件出現(xiàn)的比例來估計(jì)概率當(dāng)樣本很小時(shí),采用平滑技術(shù),m-估計(jì)p是將要確定的概率的先驗(yàn)估計(jì),而m是一稱為等效樣本大小的常量在缺少其他信息時(shí),選擇p的一種典型的方法是均勻概率,比方某屬性有k個(gè)可能值,那么p=1/k m被稱為等效樣本大小的原因是：式子6.22可被解釋為將n個(gè)實(shí)際的觀察擴(kuò)大,加上m個(gè)按p分布的虛擬樣本舉例：學(xué)習(xí)分類文本利用貝葉斯方法學(xué)習(xí)目的

27、概念,然后用于文本自動(dòng)過濾,比方我感興趣的電子新聞稿討論機(jī)器學(xué)習(xí)的萬維網(wǎng)頁本節(jié)描繪一個(gè)基于樸素貝葉斯分類器的文本分類的通用算法,它是目前所知的文本分類的最有效方法之一問題框架：實(shí)例空間X包含了所有的文本文檔,給定某未知目的函數(shù)fx的一組訓(xùn)練樣例,fx的值來自某有限集合V作為例如,此處令V=like,dislike舉例：學(xué)習(xí)分類文本2應(yīng)用樸素貝葉斯分類器的兩個(gè)主要設(shè)計(jì)問題：怎樣將任意文檔表示為屬性值的形式如何估計(jì)樸素貝葉斯分類器所需的概率表示文檔的方法給定一個(gè)文本文檔,對每個(gè)單詞的位置定義一個(gè)屬性,該屬性的值為在此位置上找到的英文單詞假定我們共有1000個(gè)訓(xùn)練文檔,其中700個(gè)分類為dislik

28、e,300個(gè)分類為like,如今要對下面的新文檔進(jìn)展分類：This is an example document for the naive Bayes classifier.This document contains only one paragraph,or two sentences.舉例：學(xué)習(xí)分類文本3計(jì)算式注意此處貝葉斯分類器隱含的獨(dú)立性假設(shè)并不成立.通常,某個(gè)位置上出現(xiàn)某個(gè)單詞的概率與前后位置上出現(xiàn)的單詞是相關(guān)的雖然此處獨(dú)立性假設(shè)不準(zhǔn)確,但別無選擇,否那么要計(jì)算的概率項(xiàng)極為龐大.另外理論中,樸素貝葉斯學(xué)習(xí)器在許多文本分類問題中性能非常好舉例：學(xué)習(xí)分類文本4需要估計(jì)概率項(xiàng)Pvi和P

29、ai=wk|vi.前一項(xiàng)可基于每一類在訓(xùn)練數(shù)據(jù)中的比例很容易得到,后一項(xiàng)含三個(gè)參數(shù),出現(xiàn)數(shù)據(jù)稀疏問題再引入一個(gè)假定以減少需要估計(jì)的概率項(xiàng)的數(shù)量：假定單詞wk出現(xiàn)的概率獨(dú)立于單詞所在的位置,即Pai=wk|vi=Pwk|vj作此假定的一個(gè)主要優(yōu)點(diǎn)在于：使可用于估計(jì)每個(gè)所需概率的樣例數(shù)增加了,因此增加了估計(jì)的可靠程度采納m-估計(jì)方法,即有統(tǒng)一的先驗(yàn)概率并且m等于詞匯表的大小,因此表6-2用于學(xué)習(xí)和分類文本的樸素貝葉斯算法Learn_Naive_Bayes_TextExamples,VExamples為一組文本文檔以及它們的目的值.V為所有可能目的值的集合.此函數(shù)作用是學(xué)習(xí)概率項(xiàng)Pwk|vj和Pvj

30、.搜集Examples中所有的單詞,標(biāo)點(diǎn)符號以及其他記號Vocabulary在Examples中任意文本文檔中出現(xiàn)的所有單詞及記號的集合計(jì)算所需要的概率項(xiàng)Pvj和Pwk|vj對V中每個(gè)目的值vj docsj Examples中目的值為vj的文檔子集Pvj|docsj|/|Examples|Textj將docsj中所有成員連接起來建立的單個(gè)文檔n在Textj中不同單詞位置的總數(shù)對Vocabulary中每個(gè)單詞wk nk單詞wk出如今Textj中的次數(shù)Pwk|vjnk+1/n+|Vocabulary|表6-2用于學(xué)習(xí)和分類文本的樸素貝葉斯算法2Classify_Naive_Bayes_TextDo

31、c對文檔Doc返回其估計(jì)的目的值,ai代表在Doc中的第i個(gè)位置上出現(xiàn)的單詞positions在Doc中的所有單詞位置,它包含能在Vocabulary中找到的記號返回vNB,實(shí)驗(yàn)結(jié)果Joachims將此算法用于新聞組文章的分類每一篇文章的分類是該文章所屬的新聞組名稱20個(gè)新聞組,每個(gè)新聞組有1000篇文章,共2萬個(gè)文檔2/3作為訓(xùn)練樣例,1/3進(jìn)展性能測量詞匯表不包含最常用詞比方the,of和罕見詞數(shù)據(jù)集中出現(xiàn)次數(shù)少于3Lang用此算法學(xué)習(xí)目的概念"我感興趣的新聞組文章"NewsWeeder系統(tǒng),讓用戶閱讀新聞組文章并為其評分,然后使用這些評分的文章作為訓(xùn)練樣例,來預(yù)測后續(xù)

32、文章哪些是用戶感興趣的每天向用戶展示前10%的自動(dòng)評分文章,它建立的文章序列中包含的用戶感興趣的文章比通常高34倍貝葉斯信念網(wǎng)樸素貝葉斯分類器假定各個(gè)屬性取值在給定目的值v下是條件獨(dú)立的,從而化簡了最優(yōu)貝葉斯分類的計(jì)算復(fù)雜度.但在多數(shù)情況下,這一條件獨(dú)立假定過于嚴(yán)厲了.貝葉斯信念網(wǎng)描繪的是一組變量所遵從的概率分布,它通過一組條件概率來指定一組條件獨(dú)立性假設(shè)貝葉斯信念網(wǎng)中可表述變量的一個(gè)子集上的條件獨(dú)立性假定,因此,貝葉斯信念網(wǎng)提供了一種中間的方法,它比樸素貝葉斯分類器的限制更少,又比在所有變量中計(jì)算條件依賴更可行貝葉斯信念網(wǎng)2貝葉斯信念網(wǎng)描繪了一組變量上的概率分布考慮一任意的隨機(jī)變量集合Y1.

33、Yn,其中每個(gè)Yi可取的值集合為VYi變量集合Y的結(jié)合空間為叉乘VY1.VYn在此結(jié)合空間上的概率分布稱為結(jié)合概率分布,結(jié)合概率分布指定了元組的每個(gè)可能的變量約束的概率貝葉斯信念網(wǎng)那么對一組變量描繪了結(jié)合概率分布條件獨(dú)立性準(zhǔn)確定義條件獨(dú)立性令X,Y和Z為3個(gè)離散值隨機(jī)變量,當(dāng)給定Z值時(shí)X服從的概率分布獨(dú)立于Y的值,稱X在給定Z時(shí)條件獨(dú)立于Y,即上式通常簡寫成PX|Y,Z=PX|Z擴(kuò)展到變量集合下面等式成立時(shí),稱變量集合X1.Xl在給定變量集合Z1.Zn時(shí)條件獨(dú)立于變量集合Y1.Ym條件獨(dú)立性與樸素貝葉斯分類器的之間的關(guān)系貝葉斯信念網(wǎng)的表示貝葉斯信念網(wǎng)簡稱貝葉斯網(wǎng)表示一組變量的結(jié)合概率分布一般地

34、說,貝葉斯網(wǎng)表示結(jié)合概率分布的方法是指定一組條件獨(dú)立性假定有向無環(huán)圖以及一組部分條件概率集合圖6-3,結(jié)合空間中每個(gè)變量在貝葉斯網(wǎng)中表示為一個(gè)節(jié)點(diǎn),每個(gè)變量需要兩種類型的信息網(wǎng)絡(luò)弧表示斷言"此變量在給定其直接前驅(qū)時(shí)條件獨(dú)立于其非后繼"每個(gè)變量有一個(gè)條件概率表,描繪了該變量在給定其立即前驅(qū)時(shí)的概率分布貝葉斯信念網(wǎng)的表示2對網(wǎng)絡(luò)變量的元組賦以所希望的值y1.yn的結(jié)合概率計(jì)算公式如下：所有變量的部分條件概率表以及由網(wǎng)絡(luò)所描繪的一組條件獨(dú)立假定,描繪了該網(wǎng)絡(luò)的整個(gè)結(jié)合概率分布貝葉斯信念網(wǎng)的推理可以用貝葉斯網(wǎng)在給定其他變量的觀察值時(shí)推理出某些目的變量的值由于所處理的是隨機(jī)變量,所以

35、一般不會(huì)賦予目的變量一個(gè)確切的值真正需要推理的是目的變量的概率分布,它指定了在給予其他變量的觀察值條件下,目的變量取每一個(gè)可能值的概率在網(wǎng)絡(luò)中所有其他變量都確切知道的情況下,這一推理步驟很簡單一般來說,貝葉斯網(wǎng)絡(luò)可用于在知道某些變量的值或分布時(shí)計(jì)算網(wǎng)絡(luò)中另一部分變量的概率分布貝葉斯信念網(wǎng)的推理2對任意貝葉斯網(wǎng)絡(luò)的概率確實(shí)切推理已經(jīng)知道是一個(gè)NP難題Monte Carlo方法提供了一種近似的結(jié)果,通過對未觀察到的變量進(jìn)展隨機(jī)采樣理論上,即使是貝葉斯網(wǎng)絡(luò)中的近似推理也可能是NP難題理論中許多情況下近似的方法被證明是有效的學(xué)習(xí)貝葉斯信念網(wǎng)從訓(xùn)練數(shù)據(jù)中學(xué)到貝葉斯信念網(wǎng),有多種討論的框架：網(wǎng)絡(luò)構(gòu)造可以預(yù)

36、先給出,或由訓(xùn)練數(shù)據(jù)中得到所有的網(wǎng)絡(luò)變量可以直接從每個(gè)訓(xùn)練樣例中觀察到,或某些變量不能觀察到假設(shè)網(wǎng)絡(luò)構(gòu)造且變量可以從訓(xùn)練樣例中完全獲得,那么得到條件概率表就比較簡單假設(shè)網(wǎng)絡(luò)構(gòu)造,但只有一部分變量值能在數(shù)據(jù)中觀察到,學(xué)習(xí)問題就困難多了.這類似于在人工神經(jīng)網(wǎng)絡(luò)中學(xué)習(xí)隱藏單元的權(quán)值Russtll1995提出了一個(gè)簡單的梯度上升過程以學(xué)習(xí)條件概率表中的項(xiàng),相當(dāng)于對表項(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)的元組,yij=T

37、rue,且uik=貝葉斯網(wǎng)的梯度上升訓(xùn)練2lnPD|h的梯度由對每個(gè)wijk求導(dǎo)數(shù)得到例如,為計(jì)算圖6-3中表左上方的表項(xiàng)的lnPD|h的導(dǎo)數(shù),需要對D中每個(gè)訓(xùn)練樣例d計(jì)算PCampfire=True,Storm=False,BusTourGroup=False|d當(dāng)訓(xùn)練樣例中無法觀察到這些變量時(shí),這些概率可用標(biāo)準(zhǔn)的貝葉斯網(wǎng)從d中觀察到的變量中推理得到這些量可以很容易地從貝葉斯網(wǎng)推理過程中得到,幾乎不需要附加的開銷貝葉斯網(wǎng)的梯度上升訓(xùn)練3式子6.25的推導(dǎo)用PhD來表示PD|h假定在數(shù)據(jù)集D中的各樣例d都是獨(dú)立抽取的貝葉斯網(wǎng)的梯度上升訓(xùn)練4更新權(quán)值歸一化處理,保持在區(qū)間0,1之間,且jwijk

38、對所有i,k保持為1這個(gè)算法只保證找到部分最優(yōu)解,替代梯度上升的一個(gè)算法是EM算法學(xué)習(xí)貝葉斯網(wǎng)的構(gòu)造假設(shè)貝葉斯網(wǎng)的構(gòu)造未知,那么需要學(xué)習(xí)貝葉斯網(wǎng)的構(gòu)造Cooper&Herskovits提出了一個(gè)貝葉斯評分尺度,以便從不同網(wǎng)絡(luò)中進(jìn)展選擇Cooper&Herskovits提出了算法K2,啟發(fā)式算法,用于在數(shù)據(jù)完全可觀察時(shí)學(xué)習(xí)網(wǎng)絡(luò)構(gòu)造基于約束的學(xué)習(xí)貝葉斯網(wǎng)絡(luò)構(gòu)造：從數(shù)據(jù)中推導(dǎo)出獨(dú)立和相關(guān)的關(guān)系,然后用這些關(guān)系來構(gòu)造貝葉斯網(wǎng)EM算法在許多實(shí)際的學(xué)習(xí)問題框架中,相關(guān)實(shí)例特征中只有一部分可觀察到已有許多方法被提出來處理存在未觀察到變量的問題比方,假設(shè)某些變量有時(shí)能觀察到,有時(shí)不能,那么可以

39、用觀察到該變量的實(shí)例去預(yù)測未觀察到的實(shí)例中的變量的值EM算法是存在隱含變量時(shí)廣泛使用的一種學(xué)習(xí)方法,可用于變量的值從來沒有被直接觀察到的情形,只要這些變量所遵循的概率分布的一般形式用于貝葉斯網(wǎng)的訓(xùn)練用于馬爾可夫模型的訓(xùn)練估計(jì)k個(gè)高斯分布的均值考慮D是一個(gè)實(shí)例集合,它由k個(gè)不同正態(tài)分布的混合所得分布生成每個(gè)實(shí)例使用一個(gè)兩步驟的過程形成：首先,隨機(jī)選擇k個(gè)正態(tài)分布中的一個(gè)其次,隨機(jī)變量xi按照此選擇的分布生成考慮一個(gè)簡單情形：單個(gè)正態(tài)分布的選擇基于均勻的概率進(jìn)展,且k個(gè)正態(tài)分布有一樣的方差學(xué)習(xí)任務(wù)：輸出一個(gè)假設(shè)h=,描繪k個(gè)分布中每個(gè)分布的均值,找到極大似然假設(shè),即使得pD|h最大化的假設(shè)估計(jì)k個(gè)

40、高斯分布的均值2當(dāng)給定從一個(gè)正態(tài)分布中抽取的數(shù)據(jù)實(shí)例x1,.,xm時(shí),很容易計(jì)算該分布的均值的極大似然假設(shè),它是6.4節(jié)中式子6.6的一個(gè)特例,表示如下然而,如今的問題涉及k個(gè)不同正態(tài)分布,而且不知道哪個(gè)實(shí)例是哪個(gè)分布產(chǎn)生的.這是一個(gè)涉及隱藏變量的典型例子對于圖6-4的例子,每個(gè)實(shí)例的完好描繪是三元組,其中xi是第i個(gè)實(shí)例的觀測值,zi1和zi2表示哪個(gè)正態(tài)分布被用來產(chǎn)生xi,是隱藏變量估計(jì)k個(gè)高斯分布的均值3假設(shè)zi1和zi2的值可知,就可用式子6.27來解決,否那么使用EM算法EM算法根據(jù)當(dāng)前假設(shè),不斷地再估計(jì)隱藏變量zij的期望值,然后用這些隱藏變量的期望值重新計(jì)算極大似然假設(shè)以圖6-4

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