1、北京 第七章 貝葉斯分類(lèi)器機(jī)器學(xué)習(xí).09.02第1頁(yè)圖形繪制圖片處理圖表設(shè)計(jì)經(jīng)典案例* 貝葉斯決議論1346Contents目 錄* 25極大似然預(yù)計(jì)樸素貝葉斯分類(lèi)器半樸素貝葉斯分類(lèi)器貝葉斯網(wǎng)EM算法機(jī)器學(xué)習(xí) 貝葉斯分類(lèi)器第2頁(yè)圖形繪制圖片處理圖表設(shè)計(jì)經(jīng)典案例* 貝葉斯決議論1346Chapter 7* 25極大似然預(yù)計(jì)樸素貝葉斯分類(lèi)器半樸素貝葉斯分類(lèi)器貝葉斯網(wǎng)EM算法機(jī)器學(xué)習(xí) 貝葉斯分類(lèi)器第3頁(yè)圖形繪制判別式 vs.生成式 貝葉斯定理* 貝葉斯準(zhǔn)則7.1 貝葉斯決議論貝葉斯決議論（Bayesian decision theory）概率框架下實(shí)施決議基本理論。對(duì)于分類(lèi)任務(wù)：基于已知相關(guān)概率和誤

2、判損失選擇最優(yōu)類(lèi)別標(biāo)識(shí)后驗(yàn)概率尋找一個(gè)判定準(zhǔn)則 h 以最小化總體風(fēng)險(xiǎn)：第4頁(yè)圖形繪制判別式 vs.生成式 貝葉斯定理* 貝葉斯準(zhǔn)則7.1 貝葉斯決議論貝葉斯判定準(zhǔn)則（Bayes decision rule）h* 稱(chēng)為貝葉斯最優(yōu)分類(lèi)器(Bayes optimal classifier)，其總體風(fēng)險(xiǎn)稱(chēng)為貝葉斯風(fēng)險(xiǎn) (Bayes risk)反應(yīng)了學(xué)習(xí)性能理論上限第5頁(yè)判別式 vs.生成式 貝葉斯定理* 貝葉斯準(zhǔn)則7.1 貝葉斯決議論判別式 vs. 生成式生成式 (generative) 模型決議樹(shù)BP 神經(jīng)網(wǎng)絡(luò)SVM代表：貝葉斯分類(lèi)器第6頁(yè)判別式 vs.生成式 貝葉斯定理* 貝葉斯準(zhǔn)則7.1 貝葉斯

3、決議論貝葉斯定理Thomas Bayes (1701?-1761)依據(jù)貝葉斯定理，有證據(jù) (evidence)因子，與類(lèi)別無(wú)關(guān)主要困難在于預(yù)計(jì)似然樣本相對(duì)于類(lèi)標(biāo)識(shí)類(lèi)條 件概率 (class-conditional probability), 亦稱(chēng) 似然 (likelihood)類(lèi)先驗(yàn)概率（prior） 樣本空間中各類(lèi)樣本所占 百分比，可經(jīng)過(guò)各類(lèi)樣本出現(xiàn) 頻率預(yù)計(jì)（大數(shù)定律）第7頁(yè)圖形繪制圖片處理圖表設(shè)計(jì)經(jīng)典案例* 貝葉斯決議論1346Chapter 7* 25極大似然預(yù)計(jì)樸素貝葉斯分類(lèi)器半樸素貝葉斯分類(lèi)器貝葉斯網(wǎng)EM算法機(jī)器學(xué)習(xí)第8頁(yè)先假設(shè)類(lèi)條件概率某種概率分布形式，再基于訓(xùn)練樣樣本對(duì)參數(shù)進(jìn)行

4、預(yù)計(jì)* 7.2 極大似然預(yù)計(jì)極大似然預(yù)計(jì)（Maximum Likelihood Estimation, MLE）使用對(duì)數(shù)似然 (log-likelihood)預(yù)計(jì)結(jié)果準(zhǔn)確性嚴(yán)重依賴(lài)于所假設(shè)概率分布形式是否符合潛在真實(shí)分布第9頁(yè)* 7.2 極大似然預(yù)計(jì)極大似然預(yù)計(jì)（Maximum Likelihood Estimation, MLE）第10頁(yè)圖形繪制圖片處理圖表設(shè)計(jì)經(jīng)典案例* 貝葉斯決議論1346Chapter 7* 25極大似然預(yù)計(jì)樸素貝葉斯分類(lèi)器半樸素貝葉斯分類(lèi)器貝葉斯網(wǎng)EM算法機(jī)器學(xué)習(xí)第11頁(yè)拉普拉斯修正 * 樸素貝葉斯分類(lèi)器7.3 樸素貝葉斯分類(lèi)器樸素貝葉斯分類(lèi)器（nave Bayes

5、classifiers）基本思緒：假定屬性相互獨(dú)立d 為屬性數(shù)，xi 為 x 在第 i 個(gè)屬性上取值對(duì)全部類(lèi)別相同，于是分類(lèi)器使用 第12頁(yè)對(duì)離散屬性，令 表示 Dc 中在第 i 個(gè)屬性上取值為xi 樣本組成集合，則拉普拉斯修正 * 樸素貝葉斯分類(lèi)器7.3 樸素貝葉斯分類(lèi)器分類(lèi)器使用 預(yù)計(jì) P(c): 預(yù)計(jì) P(x|c):對(duì)連續(xù)屬性，考慮概率密度函數(shù)，假定樸素貝葉斯分類(lèi)器（nave Bayes classifiers）第13頁(yè)拉普拉斯修正 * 樸素貝葉斯分類(lèi)器7.3 樸素貝葉斯分類(lèi)器分類(lèi)器使用 比如：樸素貝葉斯分類(lèi)器（nave Bayes classifiers）首先預(yù)計(jì)類(lèi)先驗(yàn)概率 P(c):

6、第14頁(yè)拉普拉斯修正 * 樸素貝葉斯分類(lèi)器7.3 樸素貝葉斯分類(lèi)器分類(lèi)器使用 比如：樸素貝葉斯分類(lèi)器（nave Bayes classifiers）第15頁(yè)拉普拉斯修正 * 樸素貝葉斯分類(lèi)器7.3 樸素貝葉斯分類(lèi)器分類(lèi)器使用 比如：樸素貝葉斯分類(lèi)器（nave Bayes classifiers）第16頁(yè)拉普拉斯修正 * 樸素貝葉斯分類(lèi)器7.3 樸素貝葉斯分類(lèi)器分類(lèi)器使用 比如：樸素貝葉斯分類(lèi)器（nave Bayes classifiers）第17頁(yè)拉普拉斯修正 * 樸素貝葉斯分類(lèi)器7.3 樸素貝葉斯分類(lèi)器分類(lèi)器使用 拉普拉斯修正（Laplacian correction）若某個(gè)屬性值在訓(xùn)練集中

7、沒(méi)有與某個(gè)類(lèi)同時(shí)出現(xiàn)過(guò)，則直接計(jì)算會(huì)出現(xiàn) 問(wèn)題，因?yàn)楦怕蔬B乘將“抹去”其它屬性提供信息比如，若訓(xùn)練集中未出現(xiàn)“敲聲=清脆”好瓜， 則模型在碰到“敲聲=清脆”測(cè)試樣本時(shí) 令 N 表示訓(xùn)練集 D 中可能類(lèi)別數(shù)，Ni 表示第 i 個(gè)屬性可能取值數(shù)第18頁(yè)拉普拉斯修正 * 樸素貝葉斯分類(lèi)器7.3 樸素貝葉斯分類(lèi)器分類(lèi)器使用 樸素貝葉斯分類(lèi)器使用 若對(duì)預(yù)測(cè)速度要求高，則對(duì)給定數(shù)據(jù)集， 預(yù)計(jì)算全部概率估值，使用時(shí)“查表” 若數(shù)據(jù)更替頻繁 不進(jìn)行任何訓(xùn)練，收到預(yù)測(cè)請(qǐng)求時(shí)再根據(jù)當(dāng)前數(shù)據(jù)集進(jìn)行估值(懶惰學(xué)習(xí), lazy learning) 若數(shù)據(jù)不停增加 基于現(xiàn)有估值，對(duì)新樣本屬性值包括概率估值進(jìn)行修正(增量學(xué)

8、習(xí), incremental learning)第19頁(yè)圖形繪制圖片處理圖表設(shè)計(jì)經(jīng)典案例* 貝葉斯決議論1346Chapter 7* 25極大似然預(yù)計(jì)樸素貝葉斯分類(lèi)器半樸素貝葉斯分類(lèi)器貝葉斯網(wǎng)EM算法機(jī)器學(xué)習(xí)第20頁(yè)SPODE & TAN * 半樸素貝葉斯分類(lèi)器7.4 半樸素貝葉斯分類(lèi)器AODE 半樸素貝葉斯分類(lèi)器（semi-nave Bayes classifiers）樸素貝葉斯分類(lèi)器“屬性獨(dú)立性假設(shè)”在現(xiàn)實(shí)中往往難以成立半樸素貝葉斯分類(lèi)器 (semi-nave Bayes classifier)基本思緒：適當(dāng)考慮一部分屬性間相互依賴(lài)信息最慣用策略：獨(dú)依賴(lài)預(yù)計(jì) (One-Dependent

9、Estimator, ODE) 假設(shè)每個(gè)屬性在類(lèi)別之外最多僅依賴(lài)一個(gè)其他屬性假如確定了父屬性，那么 關(guān)鍵是怎樣確定每個(gè)節(jié)點(diǎn)父屬性?第21頁(yè)SPODE & TAN * 半樸素貝葉斯分類(lèi)器7.4 半樸素貝葉斯分類(lèi)器AODE 兩種慣用方法SPODE (Super-Parent ODE)： 假設(shè)全部屬性都依賴(lài)于同一屬性，稱(chēng)為“超父” (Super-Parent)，然后經(jīng)過(guò)交叉驗(yàn)證等模型選擇方法來(lái)確定超父屬性TAN (Tree Augmented nave Bayes)： 以屬性間條件”互信息”(mutual information)為邊權(quán)重，構(gòu)建完全圖，再利用最大帶權(quán)生成樹(shù)算法，僅保留強(qiáng)相關(guān)屬性間依賴(lài)

10、性第22頁(yè)SPODE & TAN * 半樸素貝葉斯分類(lèi)器7.4 半樸素貝葉斯分類(lèi)器AODE AODE (Averaged One-Dependent Estimator)嘗試將每個(gè)屬性作為超父構(gòu)建 SPODE將擁有足夠訓(xùn)練數(shù)據(jù)支撐 SPODE 集成起來(lái)作為最終止果其中是在第 i 個(gè)屬性上取值為 xi 樣本集合，m 為閾值常數(shù)(默認(rèn)為30)表示類(lèi)別為 c 且在第 i 和第 j 個(gè)屬性上取值分別為 xi 和 xj 樣本集合Geoff Webb 澳大利亞 Monash大學(xué)第23頁(yè)SPODE & TAN * 半樸素貝葉斯分類(lèi)器7.4 半樸素貝葉斯分類(lèi)器AODE 高階依賴(lài) 訓(xùn)練樣本非常充分 性能可能提升

11、 有限訓(xùn)練樣本 高階聯(lián)合概率預(yù)計(jì)困難 考慮屬性間高階依賴(lài)，需要其它方法能否經(jīng)過(guò)考慮屬性間高階依賴(lài)來(lái)深入提升泛化性能？比如最簡(jiǎn)單做法：ODE kDE將父屬性 pai 替換為包含 k 個(gè)屬性集合障礙：伴隨 k 增加，準(zhǔn)確預(yù)計(jì) 所需樣本數(shù)量將以指數(shù)增加第24頁(yè)圖形繪制圖片處理圖表設(shè)計(jì)經(jīng)典案例* 貝葉斯決議論1346Chapter 7* 25極大似然預(yù)計(jì)樸素貝葉斯分類(lèi)器半樸素貝葉斯分類(lèi)器貝葉斯網(wǎng)EM算法機(jī)器學(xué)習(xí)第25頁(yè)學(xué)習(xí) * 結(jié)構(gòu)7.5 貝葉斯網(wǎng)推斷 貝葉斯網(wǎng)（Bayesian network）貝葉斯網(wǎng)亦稱(chēng)“信念網(wǎng)”(belief network)有向無(wú)環(huán)圖(Directed Acyclic Gra

12、ph) &條件概率表(CPT, Conditional Probability Table)Judea Pearl (1936 - ) 圖靈獎(jiǎng)貝葉斯網(wǎng)結(jié)構(gòu)參數(shù)西瓜問(wèn)題一個(gè)貝葉斯網(wǎng)結(jié)構(gòu)以及屬性“根蒂”條件概率表1985年 J. Pearl 命名為貝葉斯網(wǎng)， 為了強(qiáng)調(diào)：輸入信息主觀本質(zhì)對(duì)貝葉斯條件依賴(lài)性因果與證據(jù)推理區(qū)分第26頁(yè)學(xué)習(xí) * 結(jié)構(gòu)7.5 貝葉斯網(wǎng)推斷 結(jié)構(gòu)貝葉斯網(wǎng)比如：第27頁(yè)學(xué)習(xí) * 結(jié)構(gòu)7.5 貝葉斯網(wǎng)推斷 結(jié)構(gòu)貝葉斯網(wǎng)第28頁(yè)學(xué)習(xí) * 結(jié)構(gòu)7.5 貝葉斯網(wǎng)推斷 結(jié)構(gòu)貝葉斯網(wǎng)條件獨(dú)立性條件獨(dú)立性邊際獨(dú)立性給定 x4, x1 與 x2 必不獨(dú)立若 x4 未知，則 x1 與 x2 獨(dú)立

13、貝葉斯網(wǎng)中三變量間經(jīng)典依賴(lài)關(guān)系對(duì)于三個(gè)隨機(jī)變量a,b,c若a值完全未知，而b,c此時(shí)獨(dú)立，則稱(chēng)之為邊際獨(dú)立第29頁(yè)學(xué)習(xí) * 結(jié)構(gòu)7.5 貝葉斯網(wǎng)推斷 結(jié)構(gòu)貝葉斯網(wǎng)分析條件獨(dú)立性“有向分離”(D-separation)先將有向圖轉(zhuǎn)變?yōu)闊o(wú)向圖V 型結(jié)構(gòu)父結(jié)點(diǎn)相連有向邊變成無(wú)向邊道德圖(moral graph)由圖可得：若 x 和 y 能在圖上被 z 分入 兩個(gè)連通分支，則有得到條件獨(dú)立性關(guān)系之后，預(yù)計(jì)出條件 概率表，就得到了最終網(wǎng)絡(luò)第30頁(yè)比如 最小描述長(zhǎng)度 (MDL, Minimal Description Length)給定數(shù)據(jù)集 D，貝葉斯網(wǎng) 在 D 上評(píng)分函數(shù)：越小越好學(xué)習(xí) * 結(jié)構(gòu)7.5

14、 貝葉斯網(wǎng)推斷 學(xué)習(xí)貝葉斯網(wǎng)評(píng)分函數(shù)(score function)評(píng)定貝葉斯網(wǎng)與訓(xùn)練數(shù)據(jù)契合程度慣用評(píng)分函數(shù)通常基于信息論準(zhǔn)則第31頁(yè)學(xué)習(xí) * 結(jié)構(gòu)7.5 貝葉斯網(wǎng)推斷 學(xué)習(xí)貝葉斯網(wǎng)AIC:BIC:搜索最優(yōu)貝葉斯網(wǎng)絡(luò)結(jié)構(gòu)是NP難問(wèn)題第32頁(yè)學(xué)習(xí) * 結(jié)構(gòu)7.5 貝葉斯網(wǎng)推斷 推斷貝葉斯網(wǎng)推斷(inference)：基于已知屬性變量觀察值，推測(cè)其它屬性變量取值已知屬性變量觀察值稱(chēng)為“證據(jù)”(evidence) 準(zhǔn)確推斷：直接依據(jù)貝葉斯網(wǎng)定義聯(lián)合概率分 布來(lái)準(zhǔn)確計(jì)算后驗(yàn)概率NP難 近似推斷：降低精度要求，在有限時(shí)間內(nèi)求得近似解常見(jiàn)做法：吉布斯采樣 (Gibbs sampling)變分推斷 (va

15、riational inference)第33頁(yè)學(xué)習(xí) * 結(jié)構(gòu)7.5 貝葉斯網(wǎng)推斷 推斷 吉布斯采樣思想貝葉斯網(wǎng)隨機(jī)產(chǎn)生一個(gè)與證據(jù) E = e 一致樣本 q0 作為初始點(diǎn)比如： 證據(jù) E = e：(色澤; 敲聲;根蒂) = (青綠; 濁響; 蜷縮) 查詢(xún)目標(biāo) Q = q: (好瓜;甜度)= (是;高) 隨機(jī)產(chǎn)生 q0: (否; 高)進(jìn)行 T 次采樣，每次采樣中逐一考查每個(gè)非證據(jù)變量：假定全部其他屬性取當(dāng)前值，推斷出采樣概率，然后依據(jù)該概率采樣取值假定經(jīng)過(guò) T 次采樣得到與“查詢(xún)目標(biāo)”q 一致樣本共有 nq 個(gè)，則可近似估算出后驗(yàn)概率第34頁(yè)學(xué)習(xí) * 結(jié)構(gòu)7.5 貝葉斯網(wǎng)推斷 貝葉斯網(wǎng)推斷 吉布斯采樣算法比如：先假定 色澤=青綠; 敲聲=濁響; 根蒂=蜷縮; 甜度=高，推斷出“好瓜”采樣概率，然后采樣；假設(shè)采樣結(jié)果為“好瓜=是”;然后依據(jù) 色澤=青綠; 敲聲=濁響; 根蒂=蜷縮;好瓜=是，推斷出 “甜度” 采樣概率，然后采樣；假設(shè)采樣結(jié)果為“甜度=高”; 證據(jù) E = e：(色澤; 敲聲;根蒂) = (青綠; 濁響; 蜷縮) 查詢(xún)目標(biāo) Q = q: (好瓜;甜度)= (是;高)第35頁(yè)圖形繪制圖片處理圖表設(shè)計(jì)經(jīng)典案例* 貝葉斯決議論1346Chapter 7* 25極大似然預(yù)計(jì)樸素貝葉斯分類(lèi)器半樸素貝葉斯分類(lèi)器貝葉斯網(wǎng)EM算法機(jī)器學(xué)習(xí)第36頁(yè)* 7.6 EM算法Z 是隱