1. 章節(jié)主要內(nèi)容

貝葉斯分類器是機(jī)器學(xué)習(xí)領(lǐng)域應(yīng)用很廣端仰、效果不錯捶惜，且算法相對通俗易懂的分類器，并且章節(jié)中的一些概念和知識在其它的機(jī)器學(xué)習(xí)算法中也經(jīng)常的出現(xiàn)荔烧，所以對貝葉斯分類器很好的理解是很有必要的吱七。

1）貝葉斯分類器的理論框架是什么？

貝葉斯分類器的理論框架基于貝葉斯決策論（Bayesian decision theory）鹤竭，而貝葉斯決策論是概率框架下實施決策的基本方法踊餐。對分類任務(wù)來說，在所有相關(guān)概率都已知的理想情形下臀稚，貝葉斯決策論考慮如何基于這些概率和誤判損失來選擇最優(yōu)的類別標(biāo)記吝岭。

具體來說，若我們決策的目標(biāo)是最小化分類錯誤率吧寺，貝葉斯最優(yōu)分類器要對每個樣本 x窜管，選擇能使后驗概率 P( c | x )最大的類別 c 標(biāo)記≈苫可在現(xiàn)實任務(wù)中后驗概率通常難以直接獲得幕帆，貝葉斯分類器使用的策略是“生成型模型”，即使用貝葉斯定理：

P( c | x ) = P( c, x ) / P( x ) = P( c )P( x | c ) / P( x ) ? ? 式(1)

將求后驗概率P(c|x)的問題轉(zhuǎn)變?yōu)榍笙闰灨怕蔖(c)和條件概率P(x|c)赖条。

2）P( c )和 P( x | c ) 如何求得

［1］P( c )

類先驗概率 P(c) 表達(dá)了樣本空間中各類樣本所占的比例失乾，根據(jù)大數(shù)定律常熙，當(dāng)訓(xùn)練集包含充足的獨立同分布樣本時，P(c) 可通過各類樣本出現(xiàn)的頻率來進(jìn)行估計

［2］P( x | c )

因為對于類條件概率 P( x | c ) 來說仗扬，由于它涉及關(guān)于 x 所有屬性的聯(lián)合概率症概，直接根據(jù)樣本出現(xiàn)的頻率來估計將會遇到嚴(yán)重的困難（想象一下，d 個屬性就會有 2 的 d 次方種可能的取值早芭，在現(xiàn)實中彼城，這個種類數(shù)往往大于訓(xùn)練樣本）。針對這種情況退个，類條件概率的一種常用策略是先假定其具有某種確定的概率分布形式募壕，再基于訓(xùn)練樣本對概率分布的參數(shù)進(jìn)行估計。對于條件概率 P( x | c )语盈，我們可以采用極大似然估計來根據(jù)數(shù)據(jù)采樣來估計概率分布參數(shù)舱馅。對參數(shù) t 進(jìn)行極大似然估計，就是試圖在 t 所有可能的取值中刀荒，找到一個能使數(shù)據(jù)出現(xiàn)的“可能性”最大的值代嗤。

需注意的是，這種參數(shù)化的方法雖然能使類條件概率估計變得相對簡單缠借，但估計結(jié)果的準(zhǔn)確性嚴(yán)重依賴于所假設(shè)的概率分布形式是否符合潛在的真實數(shù)據(jù)分布干毅。

極大似然估計是對類條件概率的分布形式進(jìn)行假設(shè)，然后通過計算來對概率分布參數(shù)進(jìn)行近似的方法泼返，其是在對聯(lián)合概率上的求解硝逢。但是，我們要對數(shù)據(jù)進(jìn)行準(zhǔn)確分類是否真的需要要進(jìn)行這么復(fù)雜的求解過程呢绅喉？本章針對樣本屬性間的獨立性不同介紹了不同的使用貝葉斯決策論構(gòu)建分類器的方法渠鸽，下邊我將一一進(jìn)行介紹。

3）樣本屬性條件獨立時的 P( x | c ) 求解

［1］樸素貝葉斯分類器

樸素貝葉斯分類器（naive Bayes classifier）是采用了“屬性條件獨立性假設(shè)”的一種分類器：其通過對已知類別柴罐，假設(shè)所有屬性相互獨立徽缚，來避開聯(lián)合概率這個障礙。在屬性條件獨立的假設(shè)基礎(chǔ)下革屠，類條件概率可表示為：

P( x | c ) = P( x1 | c ) * P( x2 | c ) * ... * P( xd | c )

其中 d 為屬性數(shù)目凿试，xi 為 x 在第 i 個屬性上的取值。

顯然屠阻，樸素貝葉斯分類器的訓(xùn)練過程就是基于訓(xùn)練集 D 來估計類先驗概率 P(c)红省， 并為每個屬性估計條件概率 P( xi | c )。

令 Dc 表示數(shù)據(jù)集在類別 c 上的樣本數(shù)国觉，Dc,xi 表示 Dc 中在第 i 個屬性上取值為 xi 的樣本組成的集合吧恃，?則條件概率 P( xi | c) 可估計為

P( xi | c ) = |Dc,xi| / |Dc| ? ? ? 式(2)

上式的計算結(jié)果可以通過簡單的統(tǒng)計工作即可得到，這大大的降低了訓(xùn)練的難度麻诀。

［2］概率估計“平滑”處理

在屬性條件獨立假設(shè)下痕寓，類條件概率表示為了每個單獨屬性的概率的乘積傲醉，當(dāng)其中任意一個屬性的概率 P( xi | c ) 為0時，會導(dǎo)致總的類條件概率 P( x | c ) 為0呻率，這顯然不太合理硬毕。為了避免其它屬性攜帶的信息被訓(xùn)練集中未出現(xiàn)的屬性值“抹去”，在估計概率值時通常要進(jìn)行“平滑”處理礼仗，具體來說就是對分子和分母分別加上一個合適的數(shù)值吐咳，使得單獨屬性的類條件概率不為零。比如“拉普拉斯修正”元践，令 Ni 表示第 i 個屬性可能的取值數(shù)韭脊，則式(2)可修正為：

P( xi | c ) = ( |Dc,xi| + 1 ) / ( |Dc| + Ni ) ? ? 式(3)

4）樣本屬性獨依賴時的 P( x | c ) 求解

樸素貝葉斯分類器是建立在屬性條件獨立性假設(shè)的基礎(chǔ)上的，但在現(xiàn)實任務(wù)中這個假設(shè)往往很難成立单旁，所以人們嘗試對屬性條件獨立性假設(shè)進(jìn)行一定程度的放松沪羔，由此產(chǎn)生了一類稱為“半樸素貝葉斯分類器”的學(xué)習(xí)方法。

獨依賴估計（One-Dependent Estimator象浑，簡稱ODE）是半樸素分類器最常用的一種策略蔫饰，顧名思義，所謂“獨依賴”就是假設(shè)每個屬性在類別之外最多僅依賴于一個其它屬性愉豺。這時類條件概率可轉(zhuǎn)化為：

P( x | c ) = P( x1 | c, pa1 ) * P( x2 | c, pa2 ) * ... * P( xd | c, pad )

其中 pai 為屬性 xi 所依賴的屬性篓吁，稱為 xi 的父屬性。對每個屬性粒氧，若其父屬性已知越除，則可采用類似式(3)的辦法來估計概率值 P( xi | c, pai )节腐。

于是外盯，問題的關(guān)鍵就轉(zhuǎn)化為如何確定每個屬性的父屬性，不同的做法產(chǎn)生不同的獨依賴分類器翼雀。

［1］所有屬性都依賴于同一個屬性：SPODE（Super-Parent ODE）

［2］最大帶權(quán)生成樹算法基礎(chǔ)上構(gòu)建依賴：TAN（Tree Augmented naive Bayes）

［3］對每個屬性構(gòu)建SPODE饱苟，并將結(jié)果集成起來作為最終結(jié)果：AODE（Averaged One-Dependent Estimator）

需注意的是，當(dāng)依賴屬性個數(shù)變多時狼渊，需要的訓(xùn)練樣本數(shù)量將以指數(shù)增加箱熬。因此，若訓(xùn)練數(shù)據(jù)非常充分狈邑，泛化性能能有可能提升城须；但在有限樣本條件下，則又會陷入估計高階聯(lián)合概率的泥沼

5）樣本屬性相關(guān)性未知時的 P( x | c ) 求解

在計算 P( x | c ) 時米苹，由于不知道屬性之間的具體相關(guān)性糕伐，所以對于依賴屬性的個數(shù)和依賴關(guān)系很難進(jìn)行選擇。貝葉斯網(wǎng)是一個有效的算法蘸嘶，能對屬性之間的依賴關(guān)系進(jìn)行計算和評估良瞧，以找出一個最佳的分類模型陪汽。

［1］貝葉斯網(wǎng)的介紹

貝葉斯網(wǎng)（Bayesian Network）亦稱“信念網(wǎng)”（belief network），它借助有向圖來刻畫屬性之間的依賴關(guān)系褥蚯，并使用條件概率表來描述屬性的聯(lián)合概率分布挚冤。

具體來說，一個貝葉斯網(wǎng)由結(jié)構(gòu) G 和參數(shù) O 兩部分構(gòu)成赞庶，G 是個有向無環(huán)圖训挡，每個點是一個屬性，每一條邊代表一個直接依賴關(guān)系歧强；參數(shù) O 包含了每個屬性的條件概率表舍哄。

所以一個訓(xùn)練好的貝葉斯網(wǎng)樣知道了樣本屬性的最好依賴關(guān)系，以及不同依賴之間的條件概率誊锭，并能利用這些信息來對我們關(guān)心的屬性進(jìn)行預(yù)測表悬。

［2］貝葉斯網(wǎng)的聯(lián)合概率分布

在一個確定的貝葉斯網(wǎng)中，給定父結(jié)點集丧靡，貝葉斯網(wǎng)假設(shè)每個屬性與它的非后裔屬性獨立蟆沫，則對于屬性x1, x2, ..., xd的聯(lián)合概率分布定義為：

即屬性的聯(lián)合概率分布是每個具體屬性在其父結(jié)點集下的條件概率的乘積

［3］貝葉斯網(wǎng)絡(luò)的學(xué)習(xí)

若網(wǎng)絡(luò)結(jié)構(gòu)已知，即屬性間的依賴關(guān)系已知温治，則貝葉斯網(wǎng)的學(xué)習(xí)過程相對簡單饭庞，只需通過對訓(xùn)練樣本“計數(shù)”，估計出每個結(jié)點的條件概率表即可熬荆。但在現(xiàn)實應(yīng)用中我們往往并不知曉網(wǎng)絡(luò)結(jié)構(gòu)舟山，于是，貝葉斯網(wǎng)學(xué)習(xí)的首要任務(wù)就是根據(jù)訓(xùn)練數(shù)據(jù)集來找出結(jié)構(gòu)最“恰當(dāng)”的貝葉斯網(wǎng)卤恳。具體來說累盗，我們先定義一個評分函數(shù)，以此來評估貝葉斯網(wǎng)與訓(xùn)練數(shù)據(jù)的契合程度突琳，然后基于這個評分函數(shù)來尋找結(jié)構(gòu)最優(yōu)的貝葉斯網(wǎng)若债。

不幸的是，從所有可能的網(wǎng)絡(luò)結(jié)構(gòu)空間搜索最優(yōu)貝葉斯網(wǎng)結(jié)構(gòu)是一個NP難問題拆融，難以快說求解蠢琳。有兩種常用的策略能在有限時間內(nèi)求得近似解：

第一種是貪心法，例如從某個網(wǎng)絡(luò)結(jié)構(gòu)出發(fā)镜豹，每次調(diào)整一條邊傲须，直到評分函數(shù)值不再降低為止

第二種是通過給網(wǎng)絡(luò)結(jié)構(gòu)施加約束來削減搜索空間，例如將網(wǎng)絡(luò)結(jié)構(gòu)限定為樹形結(jié)構(gòu)等趟脂。

［4］貝葉斯網(wǎng)的推斷

在訓(xùn)練好貝葉斯網(wǎng)后就可以用來回答“查詢”泰讽，即通過一些屬性變量的觀測值來推測其它屬性變量的取值。

最理想的是直接根據(jù)貝葉斯網(wǎng)定義的聯(lián)合概率分布來精確計算后驗概率，不幸的是菇绵，這樣的推斷已被證明是NP難的肄渗。此時需借助“近似推斷”，通過降低精度要求咬最，在有限時間內(nèi)求得近似解翎嫡。在現(xiàn)實應(yīng)用中，貝葉斯網(wǎng)的近似推斷常使用吉布斯采樣來完成永乌。

比如惑申，對已知的觀察屬性 E 的取值 e ，我們要判斷在屬性 Q 上會出現(xiàn)取值 q 的概率是多少翅雏，即求 P( q | e ) 的值圈驼，運用貝葉斯網(wǎng) ＋ 吉布斯采樣的推斷過程可以總結(jié)為以下幾步：

a）對 Q 進(jìn)行隨機(jī)取值獲得屬性 Q 上的初始狀態(tài) q0

b）將當(dāng)前的 Q 上的取值與 e 結(jié)合，并使用貝葉斯網(wǎng)去推斷下一時刻的 Q 上取值為多少

c）判斷新生成的 Q 與我們要預(yù)測的 q 是否一致望几，一致則計數(shù)器 n 加一

c）重復(fù)步驟 b）－ c）T次绩脆，通過計算 n / T 我們可以近似得到?P( q | e ) 的值

6）訓(xùn)練樣本不完整時的處理方法

在之前的討論中，我們一直假設(shè)訓(xùn)練樣本所有的屬性值都已被觀測到橄抹，但在現(xiàn)實情況中靴迫，我們往往會遇到“不完整”的訓(xùn)練樣本，這些樣本的不完整性體現(xiàn)在其存在“未觀測”的變量楼誓。因為訓(xùn)練樣本中存在未觀測的變量玉锌，所以之前對概率分布的概率似然估計就無法進(jìn)行計算了。

EM（Expectation-Maximization）算法是常用的估計參數(shù)隱變量的利器疟羹，它是一種迭代式的方法主守，其基本思想就和它的名字一樣分為兩個步驟，第一步（E步）求隱變量的期望榄融；第二步（M步）尋找參數(shù)最大似然估計参淫；不斷重復(fù)第一、第二步直到收斂到局部最優(yōu)解

2. 基本知識

1）“判別式模型”（discriminative models）

直接通過建模P(c|x)來預(yù)測類別c的模型就是判別式模型剃袍，主要算法：決策樹黄刚、BP神經(jīng)網(wǎng)絡(luò)捎谨、支持向量機(jī)等

2）“生成式模型”（generative models）

先對聯(lián)合概率分布P(x,c)建模民效，然后再由此獲得P(c|x)的模型就是生成式模型，主要算法：樸素貝葉斯涛救、貝葉斯網(wǎng)絡(luò)畏邢、馬爾可夫隨機(jī)場

3）大數(shù)定律(law of large numbers)

這是一種描述當(dāng)試驗次數(shù)很大時所呈現(xiàn)的概率性質(zhì)的定律。通俗地說检吆，這個定理就是舒萎，在試驗不變的條件下，重復(fù)試驗多次蹭沛，隨機(jī)事件的頻率近似于它的概率臂寝。偶然中包含著某種必然章鲤。

4）極大似然估計（Maximum Likelihood Estimation）

根據(jù)數(shù)據(jù)采樣來估計概率分布參數(shù)的經(jīng)典方法，比如對參數(shù) t 進(jìn)行極大似然估計咆贬，就是試圖在 t 所有可能的取值中败徊，找到一個能使數(shù)據(jù)出現(xiàn)的“可能性”最大的值。

5）吉布斯采樣（Gibbs sampling）

吉布斯采樣是一種隨機(jī)采樣方法掏缎，首先根據(jù)已知初始值 e 產(chǎn)生一個初始點 q0皱蹦，然后進(jìn)行 T 次采樣，每次根據(jù)第 t-1 次的結(jié)果 q(t-1) 生成一個新的第 t 次的采樣樣本 qt眷蜈，每次采樣后與查詢變量 q 進(jìn)行比對沪哺，一致則計數(shù)器 n 加一。T 次采樣結(jié)束后酌儒， n 除以 T 的值可作為后驗概率 P( q | e ) 的近似估算

6）EM（Expectation-Maximization）算法

EM算法使用兩個步驟交替計算：第一步是期望（E）步辜妓，利用當(dāng)前估計的參數(shù)值來計算對數(shù)似然的期望值；第二步是最大化（M）步忌怎，尋找能使 E 步產(chǎn)生的似然期望最大化的參數(shù)值嫌拣。然后，新得到的參數(shù)值重新被用于 E 步并開始下一輪的計算呆躲，直到收斂到局部最優(yōu)解异逐。

3. 總結(jié)

1）貝葉斯分類器是基于貝葉斯決策論的基礎(chǔ)上構(gòu)建的，目的是對每個樣本 x插掂，選擇能使后驗概率 P( c | x )最大的類別標(biāo)記

2）現(xiàn)實中?P( c | x ) 較難獲得灰瞻，所以將求后驗概率 P( c | x ) 的問題轉(zhuǎn)變?yōu)榍笙闰灨怕?P( c ) 和條件概率 P( x | c )

3）根據(jù)大數(shù)定律，P( c ) 可通過各類樣本出現(xiàn)的頻率來進(jìn)行估計

4）在完全遵守“屬性條件獨立性假設(shè)”時辅甥，類條件概率 P( x | c ) 可通過每個屬性單獨的條件概率的乘積得到

5）在適當(dāng)放松“屬性條件獨立性假設(shè)”時酝润，類條件概率 P( x | c ) 可通過每個屬性在其父結(jié)點下的條件概率的乘積得到

6）在不清楚屬性的條件獨立性情況時，貝葉斯網(wǎng)是一個有效的算法璃弄，能對屬性之間的依賴關(guān)系進(jìn)行計算和評估要销，以找出一個最佳的分類模型

7）貝葉斯網(wǎng)學(xué)習(xí)的首要任務(wù)就是根據(jù)訓(xùn)練數(shù)據(jù)集來找出結(jié)構(gòu)最“恰當(dāng)”的貝葉斯網(wǎng)結(jié)構(gòu)

8）“平滑”處理是解決零這個特殊值對結(jié)果不利影響的一個好策略

9）當(dāng)遇到不完整的訓(xùn)練樣本時，可通過使用EM算法對模型參數(shù)進(jìn)行估計來解決