七、貝葉斯分類器

機器學習7周志華貝葉斯決策論(Bayesiandecisiontheory)概率框架下實施決策的基本理論給定N個類別，令λij代表將第j類樣本誤分類為第i類所產生的損失，則基于后驗概率將樣本x分到第i類的條件風險為：貝葉斯判定準則(Bayesdecisionrule)：?h*稱為貝葉斯最優分類器(Bayesoptimalclassifier)，其總體風險稱為貝葉斯

風險(Bayesrisk)?反映了學習性能的理論上限機器學習7周志華判別式(discriminative)模型生成式(generative)模型建模思路：直接對代表：

?決策樹

?BP神經網絡

?SVM判別式vs.生成式

在現實中通常難以直接獲得

從這個角度來看，機器學習所要實現的是基于有限的訓練樣本 盡可能準確地估計出后驗概率

兩種基本策略：思路：先對聯合概率分布建模，再由此獲得代表：貝葉斯分類器

注意：貝葉斯分類器≠貝葉斯學習

(Bayesianlearning)機器學習7周志華貝葉斯定理根據貝葉斯定理，有

先驗概率（prior）

樣本空間中各類樣本所占的

比例，可通過各類樣本出現

的頻率估計（大數定律）證據(evidence)因子，與類別無關

ThomasBayes (1701?-1761)樣本相對于類標記的類條件概率(class-conditionalprobability),亦稱似然(likelihood)主要困難在于估計似然機器學習7周志華極大似然估計

先假設某種概率分布形式，再基于訓練樣例對參數進行估計假定具有確定的概率分布形式，且被參數唯一確定，則任務就是利用訓練集D來估計參數 對于訓練集D中第c類樣本組成的集合Dc的似然(likelihood)為連乘易造成下溢，因此通常使用對數似然(log-likelihood)于是，的極大似然估計為估計結果的準確性嚴重依賴于所假設的概率分布形式是否符合潛在的真實分布機器學習7周志華樸素貝葉斯分類器(na?ve

Bayesclassifier)

主要障礙：所有屬性上的聯合概率 難以從有限訓練樣本估計獲得

組合爆炸；樣本稀疏基本思路：假定屬性相互獨立？

d為屬性數，xi為x在第i個屬性上的取值

對所有類別相同，于是機器學習7周志華樸素貝葉斯分類器

估計P(c):

估計P(x|c):?對離散屬性，令表示Dc中在第i個屬性上取值為

xi的樣本組成的集合，則?對連續屬性，考慮概率密度函數，假定機器學習7周志華拉普拉斯修正(Laplaciancorrection)若某個屬性值在訓練集中沒有與某個類同時出現過，則直接計算會出現問題，因為概率連乘將“抹去”其他屬性提供的信息

例如，若訓練集中未出現“敲聲=清脆”的好瓜， 則模型在遇到“敲聲=清脆”的測試樣本時……

令N表示訓練集D中可能的類別數，Ni表示第i個屬性可能的取值數

假設了屬性值與類別的均勻分布，這是額外引入的bias機器學習7周志華樸素貝葉斯分類器的使用

若對預測速度要求高

預計算所有概率估值，使用時“查表”

若數據更替頻繁

不進行任何訓練，收到預測請求時再估值(懶惰學習,lazylearning)

若數據不斷增加

基于現有估值，對新樣本涉及的概率估值進行修正(增量學習,incrementallearning)機器學習7周志華半樸素貝葉斯分類器

樸素貝葉斯分類器的“屬性獨立性假設”在現實中往往難以成立

半樸素貝葉斯分類器(semi-na?veBayesclassifier)

基本思路：適當考慮一部分屬性間的相互依賴信息最常用策略：獨依賴估計(One-DependentEstimator,ODE)假設每個屬性在類別之外最多僅依賴一個其他屬性

xi的“父屬性”

關鍵是如何確定父屬性機器學習7周志華兩種常見方法

SPODE(Super-ParentODE)：假設所有屬性都依賴于同一屬性，稱為“超父”(Super-Parent)，然后通過交叉驗證等模型選擇方法來確定超父屬性

TAN(TreeAugmentedna?veBayes)：以屬性間的條件”互信息”(mutualinformation)為邊的權重，構建完全圖，再利用最大帶權生成樹算法，僅保留強相關屬性間的依賴性機器學習7周志華AODE(AveragedOne-DependentEstimator)其中是在第i個屬性上取值為xi的樣本的集合，m’為閾值常數表示類別為c且在第i和第j個屬性上取值分別為xi和xj的樣本集合?嘗試將每個屬性作為超父構建SPODE?將擁有足夠訓練數據支撐的SPODE集成起來作為最終結果

GeoffWebb

澳大利亞

Monash大學機器學習7周志華高階依賴

能否通過考慮屬性間的高階依賴來進一步提升泛化性能？

例如最簡單的做法：ODE

kDE

將父屬性pai替換為包含k個屬性的集合pai明顯障礙：隨著k的增加，估計所需的樣本數將以指數級增加

訓練樣本非常充分

性能可能提升

有限訓練樣本

高階聯合概率估計困難

考慮屬性間的高階依賴，需要其他辦法機器學習7周志華貝葉斯網（Bayesiannetwork;Bayesnetwork） 亦稱“信念網”(briefnetwork)JudeaPearl (1936-)2011圖靈獎

有向無環圖(DAG,

DirectedAcyclicGraph)貝葉斯網結構參數概率圖模型(Probabilisticgraphicalmodel)?有向圖模型

貝葉斯網?無向圖模型

馬爾可夫網

第14章

條件概率表(CPT, ConditionalProbabilityTable)1985年J.Pearl命名為貝葉斯網，為了強調：?輸入信息的主觀本質??對貝葉斯條件的依賴性因果與證據推理的區別機器學習7周志華貝葉斯網（Bayesiannetwork）

條件概率表(CPT,ConditionalProbabilityTable)

有向無環圖(DAG,DirectedAcyclicGraph)給定父結點集，貝葉斯網假設每個屬性與其非后裔屬性獨立

父結點集機器學習7周志華三變量間的典型依賴關系條件獨立性條件獨立性

邊際獨立性?給定x4,x1與x2必不獨立?若x4未知，則x1與x2獨立機器學習7周志華分析條件獨立性“有向分離”(D-separation)先將有向圖轉變為無向圖?V型結構父結點相連?有向邊變成無向邊(根蒂)x1(好瓜)x2(甜度)x3(敲聲)x4(色澤)x5

道德圖(moralgraph)由圖可得：若x和y能在圖上被z分入兩個連通分支，則有

得到條件獨立性關系之后，估計出條件 概率表，就得到了最終網絡機器學習7周志華結構學習

評分函數(scorefunction)評估貝葉斯網與訓練數據的契合程度常用評分函數通常基于信息論準則例如最小描述長度(MDL,MinimalDescriptionLength)給定數據集D，貝葉斯網

?AIC: ?BIC:?……

搜索最優貝葉斯網絡結構是NP難問題回憶“模型選擇”

在D上的評分函數：

越小越好是貝葉斯網的參數個數

表示描述每個參數所需的字節數機器學習7周志華推斷

推斷(inference)：基于已知屬性變量的觀測值， 推測其他屬性變量的取值

已知屬性變量的觀測值稱為“證據”(evidence)

精確推斷：直接根據貝葉斯網定義的聯合概率分 布來精確計算后驗概率NP難

近似推斷：降低精度要求，在有限時間內求得近似解

常見做法：

?吉布斯采樣(Gibbssampling)

?變分推斷(variationalinference)機器學習7周志華吉布斯采樣

隨機產生一個與證據E=e一致的樣本q0作為初始點例如證據E=e：(色澤;敲聲;根蒂)=(青綠;濁響;蜷縮)查詢目標Q=q:(好瓜;甜度)=(是;高)隨機產生q0:(否;高)

進行T次采樣，每次采樣中逐個考察每個非證據變量：假定所有其他屬性取當前值，推斷出采樣概率，然后根據該概率采樣

例如：先假定{色澤=青綠;敲聲=濁響;根蒂=蜷縮;甜度=高}，推斷出“好 瓜”的采樣概率，然后采樣；假設采樣結果為“好瓜=是”;

然后根據{色澤=青綠;敲聲=濁響;根蒂=蜷縮;好瓜=是}，推斷出“甜度”的采樣概率，然后采樣；假設采樣結果為“甜度=高”;……

假定經過T次采樣的得到與“查詢目標”q一致的樣本共有nq個，則可近似估算出后驗概率機器學習7周志華EM算法

如何處理“未觀測到的”變量？

例如，西瓜已經脫落的根蒂，無法看出是“蜷縮”還是“堅挺”,

則訓練樣本的“根蒂”屬性變量值未知未觀測變量

隱變量(latentvariable)EM(Expectation-Maximization)算法是估計隱變量的利器做令X表示已觀測變量集，Z表示隱變量集，欲對模型參數極大似然估計，則應最大化對數似然函數

Z是隱變量，無法直接求解。怎么辦？機器學習7周志華以初始值

?基于為起點，迭