機(jī)器學(xué)習(xí)7周志華

七、貝葉斯分類器貝葉斯決策論(Bayesian decision theory)概率框架下實(shí)施決策的基本理論給定 N 個(gè)類別，令 ij 代表將第 j 類樣本誤分類為第 i 類所產(chǎn)生的損失，則基于后驗(yàn)概率將樣本 x 分到第 i 類的條件風(fēng)險(xiǎn)為：貝葉斯判定準(zhǔn)則(Bayes decision rule)： h* 稱為 貝葉斯最優(yōu)分類器(Bayes optimal classifier)，其總體風(fēng)險(xiǎn)稱為 貝葉斯風(fēng)險(xiǎn) (Bayes risk) 反映了 學(xué)習(xí)性能的理論上限判別式(discriminative)模型生成式(generative)模型建模思路：直接對(duì)代表： 決策樹 BP 神經(jīng)網(wǎng)絡(luò) SVM判別式 vs. 生成式在現(xiàn)實(shí)中通常難以直接獲得從這個(gè)角度來看，機(jī)器學(xué)習(xí)所要實(shí)現(xiàn)的是基于有限的訓(xùn)練樣本盡可能準(zhǔn)確地估計(jì)出后驗(yàn)概率兩種基本策略：思路：先對(duì)聯(lián)合概率分布建模，再由此獲得代表：貝葉斯分類器注意：貝葉斯分類器 貝葉斯學(xué)習(xí)(Bayesian learning)貝葉斯定理根據(jù)貝葉斯定理，有先驗(yàn)概率（prior ）樣本空間中各類樣本所占的比例，可通過各類樣本出現(xiàn)的頻率估計(jì)（大數(shù)定律）證據(jù) (evidence)因子，與類別無關(guān)Thomas Bayes(1701?-1761)樣本相對(duì)于類標(biāo)記的 類條件概率 (class-conditionalprobability), 亦稱 似然(likelihood)主要困難在于估計(jì)似然極大似然估計(jì)先假設(shè)某種概率分布形式，再基于訓(xùn)練樣例對(duì)參數(shù)進(jìn)行估計(jì)假定具有確定的概率分布形式，且被參數(shù)唯一確定，則任務(wù)就是利用訓(xùn)練集 D 來估計(jì)參數(shù)對(duì)于訓(xùn)練集 D 中第 c 類樣本組成的集合 Dc 的似然(likelihood)為連乘易造成下溢，因此通常使用對(duì)數(shù)似然(log-likelihood)于是，的極大似然估計(jì)為估計(jì)結(jié)果的準(zhǔn)確性嚴(yán)重依賴于所假設(shè)的概率分布形式是否符合潛在的真實(shí)分布樸素貝葉斯分類器(nave Bayes classifier)主要障礙：所有屬性上的聯(lián)合概率難以從有限訓(xùn)練樣本估計(jì)獲得組合爆炸；樣本稀疏基本思路：假定屬性相互獨(dú)立？d 為屬性數(shù)， xi 為 x 在第 i 個(gè)屬性上的取值對(duì)所有類別相同，于是樸素貝葉斯分類器 估計(jì) P(c): 估計(jì) P(x|c): 對(duì)離散屬性，令表示 Dc 中在第 i 個(gè)屬性上取值為xi 的樣本組成的集合，則 對(duì)連續(xù)屬性，考慮概率密度函數(shù)，假定拉普拉斯修正(Laplacian correction)若某個(gè)屬性值在訓(xùn)練集中沒有與某個(gè)類同時(shí)出現(xiàn)過，則直接計(jì)算會(huì)出現(xiàn)問題，因?yàn)楦怕蔬B乘將“抹去”其他屬性提供的信息例如，若訓(xùn)練集中未出現(xiàn)“敲聲=清脆”的好瓜，則模型在遇到“敲聲 =清脆”的測試樣本時(shí) 令 N 表示訓(xùn)練集 D 中可能的類別數(shù)，Ni 表示第 i 個(gè)屬性可能的取值數(shù)假設(shè)了屬性值與類別的均勻分布，這是額外引入的 bias樸素貝葉斯分類器的使用 若對(duì)預(yù)測速度要求高 預(yù)計(jì)算所有概率估值，使用時(shí)“查表” 若數(shù)據(jù)更替頻繁 不進(jìn)行任何訓(xùn)練，收到預(yù)測請(qǐng)求時(shí)再估值(懶惰學(xué)習(xí) , lazy learning) 若數(shù)據(jù)不斷增加 基于現(xiàn)有估值，對(duì)新樣本涉及的概率估值進(jìn)行修正(增量學(xué)習(xí) , incremental learning)半樸素貝葉斯分類器樸素貝葉斯分類器的“屬性獨(dú)立性假設(shè)”在現(xiàn)實(shí)中往往難以成立半樸素貝葉斯分類器 (semi-nave Bayes classifier)基本思路：適當(dāng)考慮一部分屬性間的相互依賴信息最常用策略： 獨(dú)依賴估計(jì)(One-Dependent Estimator, ODE)假設(shè)每個(gè)屬性在類別之外最多僅依賴一個(gè)其他屬性xi 的“父屬性”關(guān)鍵是如何確定父屬性兩種常見方法 SPODE (Super-Parent ODE)：假設(shè)所有屬性都依賴于同一屬性，稱為“超父” (Super-Parent)，然后通過交叉驗(yàn)證等模型選擇方法來確定超父屬性 TAN (Tree Augmented nave Bayes)：以屬性間的條件 ”互信息 ”(mutual information)為邊的權(quán)重，構(gòu)建完全圖，再利用最大帶權(quán)生成樹算法，僅保留強(qiáng)相關(guān)屬性間的依賴性AODE(Averaged One-Dependent Estimator)其中是在第 i 個(gè)屬性上取值為 xi 的樣本的集合，m 為閾值常數(shù)表示類別為 c 且在第 i 和第 j 個(gè)屬性上取值分別為 xi 和 xj 的樣本集合 嘗試將每個(gè)屬性作為超父構(gòu)建 SPODE 將擁有足夠訓(xùn)練數(shù)據(jù)支撐的 SPODE 集成起來作為最終結(jié)果Geoff Webb澳大利亞Monash大學(xué)高階依賴能否通過考慮屬性間的高階依賴來進(jìn)一步提升泛化性能？例如最簡單的做法： ODE kDE將父屬性 pai 替換為包含 k 個(gè)屬性的集合 pai明顯障礙：隨著 k 的增加，估計(jì)所 需 的 樣 本數(shù)將以指數(shù)級(jí)增加 訓(xùn)練樣本非常充分 性能可能提升 有限訓(xùn)練樣本 高階聯(lián)合概率估計(jì)困難考慮屬性間的高階依賴，需要其他辦法貝葉斯網(wǎng) （Bayesian network; Bayes network）亦稱“信念網(wǎng)” (brief network)Judea Pearl(1936 - )2011 圖靈獎(jiǎng)有向無環(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ì)對(duì)貝葉斯條件的依賴性因果與證據(jù)推理的區(qū)別貝葉斯網(wǎng) （Bayesian network）條件概率表 ( CPT,Conditional Probability Table)有向無環(huán)圖( DAG,Directed Acyclic Graph)給定父結(jié)點(diǎn)集，貝葉斯網(wǎng)假設(shè)每個(gè)屬性與其非后裔屬性 獨(dú)立父結(jié)點(diǎn)集三變量間的典型依賴關(guān)系條件獨(dú)立性條件獨(dú)立性邊際獨(dú)立性 給定 x4, 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 graph)由圖可得：若 x 和 y 能在圖上被 z 分入兩個(gè)連通分支，則有得到條件獨(dú)立性關(guān)系之后，估計(jì)出條件概率表，就得到了最終網(wǎng)絡(luò)結(jié)構(gòu)學(xué)習(xí)評(píng)分函數(shù)(score function)評(píng)估貝葉斯網(wǎng)與訓(xùn)練數(shù)據(jù)的契合程度常用評(píng)分函數(shù)通?；谛畔⒄摐?zhǔn)則例如 最小描述長度(MDL, Minimal Description Length)給定數(shù)據(jù)集 D，貝葉斯網(wǎng) AIC: BIC: 搜索最優(yōu)貝葉斯網(wǎng)絡(luò)結(jié)構(gòu)是 NP難問題回憶“模型選擇”在 D 上的評(píng)分函數(shù)：越小越好是貝葉斯網(wǎng)的參數(shù)個(gè)數(shù)表示描述每個(gè)參數(shù) 所需的字節(jié)數(shù)推斷推斷(inference)：基于已知屬性變量的觀測值，推測其他屬性變量的取值已知屬性變量的觀測值稱為“證據(jù)” (evidence) 精確推斷：直接根據(jù)貝葉斯網(wǎng)定義的聯(lián)合概率分布來精確計(jì)算后驗(yàn)概率NP 難 近似推斷：降低精度要求，在有限時(shí)間內(nèi)求得近似解常見做法： 吉布斯采樣 (Gibbs sampling) 變分推斷 (variational inference)吉布斯采樣 隨機(jī)產(chǎn)生一個(gè)與證據(jù) E = e 一致的樣本 q0 作為初始點(diǎn)例如 證據(jù) E = e：(色澤; 敲聲 ;根蒂) = (青綠 ; 濁響; 蜷縮)查詢目標(biāo) Q = q: (好瓜 ;甜度)= (是;高)隨機(jī)產(chǎn)生 q0: (否; 高) 進(jìn)行 T 次采樣，每次采樣中逐個(gè)考察每個(gè)非證據(jù)變量：假定所有其他屬性取當(dāng)前值，推斷出采樣概率，然后根據(jù)該概率采樣例如：先假定 色澤=青綠; 敲聲=濁響; 根蒂=蜷縮; 甜度=高，推斷出“好瓜”的采樣概率，然后采樣；假設(shè)采樣結(jié)果為“ 好瓜=是”;然后根據(jù) 色澤=青綠 ; 敲聲=濁響; 根蒂 =蜷縮;好瓜 =是，推斷出“甜度” 的采樣概率，然后采樣；假設(shè)采樣結(jié)果為“ 甜度=高”; 假定經(jīng)過 T 次采樣的得到與“查詢目標(biāo)” q 一致的樣本共有 nq個(gè)，則可近似估算出后驗(yàn)概率EM算法如何處理“未觀測到的”變量？例如，西瓜已經(jīng)脫落的根蒂，無法看出是“蜷縮”還是“堅(jiān)挺”,則訓(xùn)練樣本的“根蒂”屬性變量值未知未觀測變量 隱變量(latent variable)EM(Expectation-Maximization) 算法是估計(jì)隱變量的利器做令 X 表示已觀測變量集， Z 表示隱變量集，欲對(duì)模型參數(shù)極大似然估計(jì)，則應(yīng)最大化對(duì)數(shù)似然函數(shù)Z 是隱變量，無法直接求解。怎么辦？以初始值 基于為起點(diǎn)，迭代執(zhí)行以下步驟直至收斂 :推斷隱變量 Z 的期望，記為 基于已觀測變量 X 和對(duì)參數(shù)做極大似然估計(jì)，記為E步 : 當(dāng)已知 根據(jù)訓(xùn)練數(shù)據(jù)推斷出最優(yōu)隱變量 ZM步 : 當(dāng) Z 已知 對(duì)做極大似然估計(jì)EM算法 (續(xù) )對(duì)隱變量 Z 計(jì)算期望，最大化已觀測數(shù)據(jù)的對(duì)數(shù)“邊際似然”(marginal likelihood)前往第八站