《機(jī)器學(xué)習(xí)7周志華.ppt》由會員分享，可在線閱讀，更多相關(guān)《機(jī)器學(xué)習(xí)7周志華.ppt（23頁珍藏版）》請在裝配圖網(wǎng)上搜索。

1、七、貝葉斯分類器 貝葉斯決策論(Bayesian decision theory)概率框架下實施決策的基本理論給定 N 個類別，令 ij 代表將第 j 類樣本誤分類為第 i 類所產(chǎn)生的損失，則基于后驗概率將樣本 x 分到第 i 類的條件風(fēng)險為：貝葉斯判定準(zhǔn)則(Bayes decision rule)： h* 稱為 貝葉斯最優(yōu)分類器(Bayes optimal classifier)，其總體風(fēng)險稱為 貝葉斯風(fēng)險 (Bayes risk) 反映了 學(xué)習(xí)性能的理論上限 判別式(discriminative)模型生成式(generative)模型建模思路：直接對代表： 決策樹 BP 神經(jīng)網(wǎng)絡(luò) SVM判

2、別式 vs. 生成式在現(xiàn)實中通常難以直接獲得從這個角度來看，機(jī)器學(xué)習(xí)所要實現(xiàn)的是基于有限的訓(xùn)練樣本盡可能準(zhǔn)確地估計出后驗概率兩種基本策略：思路：先對聯(lián)合概率分布建模，再由此獲得代表：貝葉斯分類器注意：貝葉斯分類器 貝葉斯學(xué)習(xí)(Bayesian learning) 貝葉斯定理根據(jù)貝葉斯定理，有先驗概率（prior ） 樣本空間中各類樣本所占的比例，可通過各類樣本出現(xiàn)的頻率估計（大數(shù)定律）證據(jù) (evidence)因子，與類別無關(guān)Thomas Bayes(1701?-1761)樣本相對于類標(biāo)記的 類條件概率 (class-conditionalprobability), 亦稱 似然(likelih

3、ood)主要困難在于估計似然 極大似然估計先假設(shè)某種概率分布形式，再基于訓(xùn)練樣例對參數(shù)進(jìn)行估計假定具有確定的概率分布形式，且被參數(shù)唯一確定，則任務(wù)就是利用訓(xùn)練集 D 來估計參數(shù)對于訓(xùn)練集 D 中第 c 類樣本組成的集合 Dc 的似然(likelihood)為連乘易造成下溢，因此通常使用對數(shù)似然 (log-likelihood)于是，的極大似然估計為估計結(jié)果的準(zhǔn)確性嚴(yán)重依賴于所假設(shè)的概率分布形式是否符合潛在的真實分布 樸素貝葉斯分類器(nave Bayes classifier)主要障礙：所有屬性上的聯(lián)合概率難以從有限訓(xùn)練樣本估計獲得組合爆炸；樣本稀疏基本思路：假定屬性相互獨(dú)立？d 為屬性數(shù)，

4、x i 為 x 在第 i 個屬性上的取值對所有類別相同，于是 樸素貝葉斯分類器 估計 P(c): 估計 P(x|c): 對離散屬性，令表示 Dc 中在第 i 個屬性上取值為xi 的樣本組成的集合，則 對連續(xù)屬性，考慮概率密度函數(shù)，假定 拉普拉斯修正(Laplacian correction)若某個屬性值在訓(xùn)練集中沒有與某個類同時出現(xiàn)過，則直接計算會出現(xiàn)問題，因為概率連乘將“抹去”其他屬性提供的信息例如，若訓(xùn)練集中未出現(xiàn)“敲聲=清脆”的好瓜，則模型在遇到“敲聲 =清脆”的測試樣本時 令 N 表示訓(xùn)練集 D 中可能的類別數(shù)，Ni 表示第 i 個屬性可能的取值數(shù) 假設(shè)了屬性值與類別的均勻分布，這是額

5、外引入的 bias 樸素貝葉斯分類器的使用 若對預(yù)測速度要求高 預(yù)計算所有概率估值，使用時“查表” 若數(shù)據(jù)更替頻繁 不進(jìn)行任何訓(xùn)練，收到預(yù)測請求時再估值(懶惰學(xué)習(xí) , lazy learning) 若數(shù)據(jù)不斷增加 基于現(xiàn)有估值，對新樣本涉及的概率估值進(jìn)行修正 (增量學(xué)習(xí) , incremental learning) 半樸素貝葉斯分類器樸素貝葉斯分類器的“屬性獨(dú)立性假設(shè)”在現(xiàn)實中往往難以成立半樸素貝葉斯分類器 (semi-nave Bayes classifier)基本思路：適當(dāng)考慮一部分屬性間的相互依賴信息最常用策略： 獨(dú)依賴估計(One-Dependent Estimator, ODE)假

6、設(shè)每個屬性在類別之外最多僅依賴一個其他屬性 xi 的“父屬性”關(guān)鍵是如何確定父屬性 兩種常見方法 SPODE (Super-Parent ODE)：假設(shè)所有屬性都依賴于同一屬性，稱為“超父” (Super-Parent)，然后通過交叉驗證等模型選擇方法來確定超父屬性 TAN (Tree Augmented nave Bayes)：以屬性間的條件 ”互信息 ”(mutual information)為邊的權(quán)重，構(gòu)建完全圖，再利用最大帶權(quán)生成樹算法，僅保留強(qiáng)相關(guān)屬性間的依賴性 AODE (Averaged One-Dependent Estimator)其中是在第 i 個屬性上取值為 x i 的樣

7、本的集合，m 為閾值常數(shù)表示類別為 c 且在第 i 和第 j 個屬性上取值分別為 xi 和 xj 的樣本集合 嘗試將每個屬性作為超父構(gòu)建 SPODE 將擁有足夠訓(xùn)練數(shù)據(jù)支撐的 SPODE 集成起來作為最終結(jié)果Geoff Webb澳大利亞Monash大學(xué) 高階依賴能否通過考慮屬性間的高階依賴來進(jìn)一步提升泛化性能？例如最簡單的做法： ODE kDE將父屬性 pai 替換為包含 k 個屬性的集合 pai明顯障礙：隨著 k 的增加，估計所 需 的 樣 本數(shù)將以指數(shù)級增加 訓(xùn)練樣本非常充分 性能可能提升 有限訓(xùn)練樣本 高階聯(lián)合概率估計困難考慮屬性間的高階依賴，需要其他辦法 貝葉斯網(wǎng) （Bayesian

8、network; Bayes network）亦稱“信念網(wǎng)” (brief network) Judea Pearl(1936 - )2011 圖靈獎 有向無環(huán)圖( DAG,Directed Acyclic Graph)貝葉斯網(wǎng)結(jié)構(gòu)參數(shù)概率圖模型 (Probabilistic graphical model) 有向圖模型 貝葉斯網(wǎng) 無向圖模型 馬爾可夫網(wǎng) 第 14章 條件概率表 ( CPT,Conditional Probability Table)1985年 J. Pearl 命名為貝葉斯網(wǎng)，為了強(qiáng)調(diào)：輸入信息的主觀本質(zhì)對貝葉斯條件的依賴性因果與證據(jù)推理的區(qū)別 貝葉斯網(wǎng) （Bayesian

9、network）條件概率表 ( CPT,Conditional Probability Table)有向無環(huán)圖( DAG,Directed Acyclic Graph)給定父結(jié)點(diǎn)集，貝葉斯網(wǎng)假設(shè)每個屬性與其非后裔屬性 獨(dú)立 父結(jié)點(diǎn)集 三變量間的典型依賴關(guān)系條件獨(dú)立性條件獨(dú)立性邊際獨(dú)立性 給定 x 4, x1 與 x2 必不獨(dú)立 若 x4 未知，則 x1 與 x2 獨(dú)立 分析條件獨(dú)立性“有向分離”( D-separation)先將有向圖轉(zhuǎn)變?yōu)闊o向圖 V 型結(jié)構(gòu)父結(jié)點(diǎn)相連 有向邊變成無向邊(根蒂)x 1 (好瓜) x 2 (甜度)x 3 (敲聲) x 4 (色澤) x5道德圖(moral grap

10、h)由圖可得：若 x 和 y 能在圖上被 z 分入兩個連通分支，則有 得到條件獨(dú)立性關(guān)系之后，估計出條件概率表，就得到了最終網(wǎng)絡(luò) 結(jié)構(gòu)學(xué)習(xí)評分函數(shù)(score function)評估貝葉斯網(wǎng)與訓(xùn)練數(shù)據(jù)的契合程度常用評分函數(shù)通?；谛畔⒄摐?zhǔn)則例如 最小描述長度(MDL, Minimal Description Length)給定數(shù)據(jù)集 D，貝葉斯網(wǎng) AIC: BIC: 搜索最優(yōu)貝葉斯網(wǎng)絡(luò)結(jié)構(gòu)是 NP難問題回憶“模型選擇”在 D 上的評分函數(shù)：越小越好是貝葉斯網(wǎng)的參數(shù)個數(shù)表示描述每個參數(shù) 所需的字節(jié)數(shù) 推斷推斷(inference)：基于已知屬性變量的觀測值，推測其他屬性變量的取值已知屬性變量的觀

11、測值稱為“證據(jù)” (evidence) 精確推斷：直接根據(jù)貝葉斯網(wǎng)定義的聯(lián)合概率分布來精確計算后驗概率NP 難 近似推斷：降低精度要求，在有限時間內(nèi)求得近似解常見做法： 吉布斯采樣 (Gibbs sampling) 變分推斷 (variational inference) 吉布斯采樣 隨機(jī)產(chǎn)生一個與證據(jù) E = e 一致的樣本 q0 作為初始點(diǎn)例如 證據(jù) E = e：(色澤; 敲聲 ;根蒂) = (青綠 ; 濁響; 蜷縮)查詢目標(biāo) Q = q: (好瓜 ;甜度)= (是;高)隨機(jī)產(chǎn)生 q0: (否; 高) 進(jìn)行 T 次采樣，每次采樣中逐個考察每個非證據(jù)變量：假定所有其他屬性取當(dāng)前值，推斷出采樣

12、概率，然后根據(jù)該概率采樣例如：先假定 色澤=青綠; 敲聲=濁響; 根蒂=蜷縮; 甜度=高，推斷出“好瓜”的采樣概率，然后采樣；假設(shè)采樣結(jié)果為“ 好瓜=是”;然后根據(jù) 色澤=青綠 ; 敲聲=濁響; 根蒂 =蜷縮;好瓜 =是，推斷出“甜度” 的采樣概率，然后采樣；假設(shè)采樣結(jié)果為“ 甜度=高”; 假定經(jīng)過 T 次采樣的得到與“查詢目標(biāo)” q 一致的樣本共有 n q個，則可近似估算出后驗概率 EM算法如何處理“未觀測到的”變量？例如，西瓜已經(jīng)脫落的根蒂，無法看出是“蜷縮”還是“堅挺”,則訓(xùn)練樣本的“根蒂”屬性變量值未知未觀測變量 隱變量(latent variable)EM(Expectation-Maximization) 算法是估計隱變量的利器做令 X 表示已觀測變量集， Z 表示隱變量集，欲對模型參數(shù)極大似然估計，則應(yīng)最大化對數(shù)似然函數(shù) Z 是隱變量，無法直接求解。怎么辦？ 以初始值 基于為起點(diǎn)，迭代執(zhí)行以下步驟直至收斂 :推斷隱變量 Z 的期望，記為 基于已觀測變量 X 和對參數(shù)做極大似然估計，記為E步 : 當(dāng)已知 根據(jù)訓(xùn)練數(shù)據(jù)推斷出最優(yōu)隱變量 ZM步 : 當(dāng) Z 已知 對做極大似然估計EM算法 (續(xù) )對隱變量 Z 計算期望，最大化已觀測數(shù)據(jù)的對數(shù)“邊際似然”(marginal likelihood) 前往第八站