【正文】 | p(E E) | p(A ? ? p(B) A)p(A) | p(B p(B) B) p(A, B) | p(A A1 A2 A3 A4 A5 A6 E 2022/2/9 數(shù)據(jù)處理與智能決策 25 貝葉斯網(wǎng)絡(luò)的概率解釋 ? 任何完整的概率模型必須具有表示（直接或間接）該領(lǐng)域變量聯(lián)合分布的能力。完全的枚舉需要指數(shù)級(jí)的規(guī)模（相對(duì)于領(lǐng)域變量個(gè)數(shù)） ? 貝葉斯網(wǎng)絡(luò)提供了這種聯(lián)合概率分布的緊湊表示：分解聯(lián)合分布為幾個(gè)局部分布的乘積： ? 從公式可以看出，需要的參數(shù)個(gè)數(shù)隨網(wǎng)絡(luò)中節(jié)點(diǎn)個(gè)數(shù)呈線性增長(zhǎng)，而聯(lián)合分布的計(jì)算呈指數(shù)增長(zhǎng)。 ? 網(wǎng)絡(luò)中變量間獨(dú)立性的指定是實(shí)現(xiàn)緊湊表示的關(guān)鍵。這種獨(dú)立性關(guān)系在通過人類專家構(gòu)造貝葉斯網(wǎng)中特別有效。 ?? i iin paxPxxxP )|(),( 21 ?2022/2/9 數(shù)據(jù)處理與智能決策 26 4 簡(jiǎn)單貝葉斯學(xué)習(xí)模型 簡(jiǎn)單貝葉斯 （ na239。ve Bayes或 simple Bayes） 學(xué)習(xí)模型將訓(xùn)練實(shí)例 I分解成特征向量 X和決策類別變量 C。 簡(jiǎn)單貝葉斯模型假定特征向量的各分量間相對(duì)于決策變量是相對(duì)獨(dú)立的，也就是說 各分量獨(dú)立地作用于決策變量 。盡管這一假定一定程度上限制了簡(jiǎn)單貝葉斯模型的適用范圍，然而在實(shí)際應(yīng)用中，不僅以指數(shù)級(jí)降低了貝葉斯網(wǎng)絡(luò)構(gòu)建的復(fù)雜性，而且在許多領(lǐng)域，在違背這種假定的條件下，簡(jiǎn)單貝葉斯也表現(xiàn)出相當(dāng)?shù)慕研院透咝?[111]，它已經(jīng)成功地應(yīng)用到分類、聚類及模型選擇等數(shù)據(jù)挖掘的任務(wù)中。目前，許多研究人員正致力于改善特征變量間獨(dú)立性的限制 [54]，以使它適用于更大的范圍。 2022/2/9 數(shù)據(jù)處理與智能決策 27 簡(jiǎn)單貝葉斯 Na239。ve Bayesian ?結(jié)構(gòu)簡(jiǎn)單－只有兩層結(jié)構(gòu) ?推理復(fù)雜性與網(wǎng)絡(luò)節(jié)點(diǎn)個(gè)數(shù)呈線性關(guān)系 2022/2/9 數(shù)據(jù)處理與智能決策 28 設(shè)樣本 A表示成屬性向量，如果屬性對(duì)于給定的類別獨(dú)立，那么 P(A|Ci)可以分解成幾個(gè)分量的積： )|(*)|(*)|( 21 imii CaPCaPCaP ? ai是樣本 A的第 i個(gè)屬性 4 簡(jiǎn)單貝葉斯學(xué)習(xí)模型 2022/2/9 數(shù)據(jù)處理與智能決策 29 簡(jiǎn)單貝葉斯分類模型 )|()( )()|(1???mjijii CaPAPCPACP)|( ij CaP)( iCP這個(gè)過程稱之為 簡(jiǎn)單貝葉斯分類 (SBC: Simple Bayesian Classifier)。 一般認(rèn)為，只有在獨(dú)立性假定成立的時(shí)候，SBC才能獲得精度最優(yōu)的分類效率；或者在屬性相關(guān)性較小的情況下，能獲得近似最優(yōu)的分類效果。 4 簡(jiǎn)單貝葉斯學(xué)習(xí)模型 簡(jiǎn)單貝葉斯學(xué)習(xí)模型的介紹 2022/2/9 數(shù)據(jù)處理與智能決策 30 簡(jiǎn)單貝葉斯模型的提升 提升方法（ Boosting） 總的思想是學(xué)習(xí)一系列分類器，在這個(gè)序列中每一個(gè)分類器對(duì)它前一個(gè)分類器導(dǎo)致的錯(cuò)誤分類例子給與更大的重視。尤其是在學(xué)習(xí)完分類器 Hk之后，增加了由 Hk導(dǎo)致分類錯(cuò)誤的訓(xùn)練例子的權(quán)值，并且通過重新對(duì)訓(xùn)練例子計(jì)算權(quán)值，再學(xué)習(xí)下一個(gè)分類器 Hk+1。 這個(gè)過程重復(fù) T次。最終的分類器從這一系列的分類器中綜合得出。 4 簡(jiǎn)單貝葉斯學(xué)習(xí)模型 2022/2/9 數(shù)據(jù)處理與智能決策 31 5 貝葉斯網(wǎng)絡(luò)的建造 貝葉斯網(wǎng)絡(luò)的建構(gòu)及建立方法 貝葉斯網(wǎng)絡(luò)是表示變量間概率依賴關(guān)系的有向無環(huán)圖，這里每個(gè)節(jié)點(diǎn)表示領(lǐng)域變量，每條邊表示變量間的概率依賴關(guān)系，同時(shí)對(duì)每個(gè)節(jié)點(diǎn)都對(duì)應(yīng)著一個(gè)條件概率分布表 (CPT) ， 指明了該變量與父節(jié)點(diǎn)之間概率依賴的數(shù)量關(guān)系。 2022/2/9 數(shù)據(jù)處理與智能決策 32 貝葉斯網(wǎng)的表示方法 = P(A) P(S) P(T|A) P(L|S) P(B|S) P(C|T,L) P(D|T,L,B) P(A, S, T, L, B, C, D) 條件獨(dú)立性假設(shè) 有效的表示 CPT: T L B D=0 D=1 0 0 0 0 0 1 0 1 0 0 1 1 ... Lung Cancer Smoking Chest Xray Bronchitis Dyspnoea Tuberculosis Visit to Asia P(D|T,L,B) P(B|S) P(S) P(C|T,L) P(L|S) P(A) P(T|A) 貝葉斯網(wǎng)絡(luò)是表示變量間概率依賴關(guān)系的有向無環(huán)圖 2022/2/9 數(shù)據(jù)處理與智能決策 33 Boosting背景 ?來源于 :PACLearning Model Valiant 1984 11 ?提出問題 : ?強(qiáng)學(xué)習(xí)算法 : 準(zhǔn)確率很高的學(xué)習(xí)算法 ?弱學(xué)習(xí)算法 : 準(zhǔn)確率不高 ,僅比隨機(jī)猜測(cè)略好 ?是否可以將弱學(xué)習(xí)算法提升為強(qiáng)學(xué)習(xí)算法 2022/2/9 數(shù)據(jù)處理與智能決策 34 Boosting背景 ?最初的 boosting算法 Schapire 1989 ?AdaBoost算法 Freund and Schapire 1995 2022/2/9 數(shù)據(jù)處理與智能決策 35 Boosting— concepts(3) Boosting ?弱學(xué)習(xí)機(jī)（ weak learner): 對(duì)一定分布的訓(xùn)練樣本給出假設(shè)（僅僅強(qiáng)于隨機(jī)猜測(cè)） 根據(jù)有云猜測(cè)可能會(huì)下雨 ?強(qiáng)學(xué)習(xí)機(jī)（ strong learner): 根據(jù)得到的弱學(xué)習(xí)機(jī)和相應(yīng)的權(quán)重給出假設(shè)（最大程度上符合實(shí)際情況： almost perfect expert) 根據(jù) CNN,ABC,CBS以往的預(yù)測(cè)表現(xiàn)及實(shí)際天氣情況作出綜合準(zhǔn)確的天氣預(yù)測(cè) ?弱學(xué)習(xí)機(jī) 強(qiáng)學(xué)習(xí)機(jī) 2022/2/9 數(shù)據(jù)處理與智能決策 36 Boosting流程 (loop1) 強(qiáng)學(xué)習(xí)機(jī) 弱學(xué)習(xí)機(jī) 原始訓(xùn)練集 加權(quán)后的訓(xùn)練集 加權(quán)后的假設(shè) X1?1:1 弱假設(shè) 2022/2/9 數(shù)據(jù)處理與智能決策 37 Boosting流程 (loop2) 強(qiáng)學(xué)習(xí)機(jī) 弱學(xué)習(xí)機(jī) 原始訓(xùn)練集 加權(quán)后的訓(xùn)練集 加權(quán)后的假設(shè) Y3?1:1 弱假設(shè) 2022/2/9 數(shù)據(jù)處理與智能決策 38 Boosting流程 (loop3) 強(qiáng)學(xué)習(xí)機(jī) 弱學(xué)習(xí)機(jī) 原始訓(xùn)練集 加權(quán)后的訓(xùn)練集 加權(quán)后的假設(shè) Z7?1:1 弱假設(shè) 2022/2/9 數(shù)據(jù)處理與智能決策 39 Boosting ? 過程 : ? 在一定的權(quán)重條件下訓(xùn)練數(shù)據(jù)，得出分類法 Ct ? 根據(jù) Ct的錯(cuò)誤率調(diào)整權(quán)重 Set of weighted instances Classifier Ct train classifier adjust weights 2022/2/9 數(shù)據(jù)處理與智能決策 40 流程描述 ? Step1: 原始訓(xùn)練集輸入，帶有原始分布 ? Step2: 給出訓(xùn)練集中各樣本的權(quán)重 ? Step3: 將改變分布后的訓(xùn)練集輸入已知的弱學(xué)習(xí)機(jī)，弱學(xué)習(xí)機(jī)對(duì)每個(gè)樣本給出假設(shè) ? Step4: 對(duì)此次的弱學(xué)習(xí)機(jī)給出權(quán)重 ? Step5: 轉(zhuǎn)到 Step2, 直到循環(huán)到達(dá)一定次數(shù)或者某度量標(biāo)準(zhǔn)符合要求 ? Step6: 將弱學(xué)習(xí)機(jī)按其相應(yīng)的權(quán)重加權(quán)組合形成強(qiáng)學(xué)習(xí)機(jī) 2022/2/9 數(shù)據(jù)處理與智能決策 41 核心思想 ? 樣本的權(quán)重 ? 沒有先驗(yàn)知識(shí)的情況下，初始的分布應(yīng)為等概分布，也就是訓(xùn)練集如果有 N個(gè)樣本，每個(gè)樣本的分布概率為 1/N ? 每次循環(huán)一后提高錯(cuò)誤樣本的分布概率，分錯(cuò)樣本在訓(xùn)練集中所占權(quán)重增大， 使得下一次循環(huán)的弱學(xué)習(xí)機(jī)能夠集中力量對(duì)這些錯(cuò)誤樣本進(jìn)行判斷。 ? 弱學(xué)習(xí)機(jī)的權(quán)重 ? 準(zhǔn)確率越高的弱學(xué)習(xí)機(jī)權(quán)重越高 ? 循環(huán)控制：損失函數(shù)達(dá)到最小 ? 在強(qiáng)學(xué)習(xí)機(jī)的組合中增加一個(gè)加權(quán)的弱學(xué)習(xí)機(jī)，使準(zhǔn)確率提高，損失函數(shù)值減小。 2022/2/9 數(shù)據(jù)處理與智能決策 42 簡(jiǎn)單問題演示（ Boosting訓(xùn)練過程） ++++++++++++loop1Weak learner1(y=)loop2Weak learner2(x=)loop3Weak learner3(y=)loop4Weak learner4(x=)training set等概分布strong learnerw1*(y?1:1) + w2*(x?1:1) + w3*(y?1:1) + w4*(x?1:1)2022/2/9 數(shù)據(jù)處理與智能決策 43 算法 — 問題描述 ? 訓(xùn)練集 { (x1,y1), (x2,y2),… , (xN,yN) } ? xi ?Rm, yi? {1,+1} ? Dt 為第 t次循環(huán)時(shí)的訓(xùn)練樣本分布（每個(gè)樣本在訓(xùn)練集中所占的概率， Dt總和應(yīng)該為 1） ? ht:X?{1,+1} 為第 t次循環(huán)時(shí)的 Weak learner，對(duì)每個(gè)樣本給出相應(yīng)的假設(shè)，應(yīng)該滿足強(qiáng)于隨機(jī)猜測(cè)： ? wt為 ht的權(quán)重 ? 為 t次循環(huán)得到的 Strong learner ????? 21),( )]([ xhyP tDyx t?????? tiitiit hws i gnH1))(()(2022/2/9 數(shù)據(jù)處理與智能決策 44 算法 — 樣本權(quán)重 ? 思想：提高分錯(cuò)樣本的權(quán)重 ? 反映了 strong learner對(duì)樣本的假設(shè)是否正確 ? 采用什么樣的函數(shù)形式？ )( iti Hy ?????????w r ongr i ghtHyiti 00)(? ?)(e x p iti Hy ???2022/2/9 數(shù)據(jù)處理與智能決策 45 算法 — 弱學(xué)習(xí)機(jī)權(quán)重 ? 思想：錯(cuò)誤率越低，該學(xué)習(xí)機(jī)的權(quán)重應(yīng)該越大 ? 為學(xué)習(xí)機(jī)的錯(cuò)誤概率 ? 采用什么樣的函數(shù)形式？ 和指數(shù)函數(shù)遙相呼應(yīng)： )]([),( xhyP tDyxt t ?? ?????????? ??tttw ??1ln212022/2/9 數(shù)據(jù)處理與智能決策 46 算法 Adaboost ????????? ????????????TtttttittitttttiiNNxhws i g nxHZZxhwyiDiDwRhDTtNiDyxyxyx11111))(()(:l e a r n e r ) ( s t r o n gc l a s s i f i e r f i n a l O u t p u t t h ef a c t o ri o n n o r m a l i z a t a is ))(e x p ()()( U p d a t e C o m p u t e:l e a r n e r G e t we a k u s i n gl e a r n e r T r a i n we a k:,1F o r 1)( I n i t i a l i z e}1,1{, w h e r e),(,),( :G i v e n??2022/2/9 數(shù)據(jù)處理與智能決策 47 ? 初始賦予每個(gè)樣本相等的權(quán)重 1/N ； ? For t = 1, 2, …, T Do ? 學(xué)習(xí)得到分類法 Ct； ? 計(jì)算該分類法的錯(cuò)誤率 Et Et=所有被錯(cuò)誤分類的樣本的權(quán)重和； ? βt= Et/（ 1 Et） ? 根據(jù)錯(cuò)誤率更新樣本的權(quán)重； 正確分類的樣本： Wnew= Wold* βt 錯(cuò)誤分類的樣本： Wnew= Wold ? 調(diào)整使得權(quán)重和為 1； ? 每個(gè)分類法 Ct的投票價(jià)值為 log [ 1 / βt ] 2022/2/9 數(shù)據(jù)處理與智能決策 48 AdaBoost Training Error ? ?? ? 24112 ttt ??? ?????? ????tt22e xp ?? 將 γt=1/2Et 。 ? Freund and Schap