【文章內(nèi)容簡(jiǎn)介】 ire 證明 : 最大錯(cuò)誤率為 : ? 即訓(xùn)練錯(cuò)誤率隨 γt的增大呈指數(shù)級(jí)的減小 . 2022/2/9 數(shù)據(jù)處理與智能決策 49 AdaBoost Generalization Error(1) ? 最大總誤差 : ? m : 樣本個(gè)數(shù) ? d : VC維 ? T : 訓(xùn)練輪數(shù) ? Pr: 對(duì)訓(xùn)練集的經(jīng)驗(yàn)概率 ? 如果 T值太大 ,Boosting會(huì)導(dǎo)致過適應(yīng)（ overfit） )())(( mTdOyxHp r ?? ??2022/2/9 數(shù)據(jù)處理與智能決策 50 AdaBoost Generalization Error(2) ? 許多的試驗(yàn)表明 : Boosting不會(huì)導(dǎo)致 overfit 2022/2/9 數(shù)據(jù)處理與智能決策 51 AdaBoost Generalization Error(3) ? 解釋以上試驗(yàn)現(xiàn)象 。 ? 樣本 (X,Y)的 margin: margin(x,y)= ? αt=1/2 ln ( (1 Εt)/ Εt ) ? 較大的正邊界表示可信度高的正確的預(yù)測(cè) ? 較大的負(fù)邊界表示可信度高的錯(cuò)誤的預(yù)測(cè) ? ?xhy ttt? ?2022/2/9 數(shù)據(jù)處理與智能決策 52 AdaBoost Generalization Error(4) ? 解釋 : 當(dāng)訓(xùn)練誤差降低后 ,Boosting繼續(xù)提高邊界 ,從而增大了最小邊界 ,使分類的可靠性增加 ,降低總誤差 . ? 總誤差的上界 : ? 該公式與 T無關(guān) )()),(a rg(2??mdOyxinmP r????2022/2/9 數(shù)據(jù)處理與智能決策 53 Boosting其它應(yīng)用 ? Boosting易受到噪音的影響 。 ? AdaBoost 可以用來鑒別異常 。 具有最高權(quán)重的樣本即為異常 . 2022/2/9 數(shù)據(jù)處理與智能決策 54 ???? , ANB是表示變量間連結(jié)關(guān)系的有向無環(huán)圖 ?貝葉斯網(wǎng)絡(luò)的學(xué)習(xí) 結(jié)構(gòu)學(xué)習(xí) 參數(shù)學(xué)習(xí) 基于評(píng)分函數(shù)的結(jié)構(gòu)學(xué)習(xí) 基于條件獨(dú)立性檢驗(yàn)的結(jié)構(gòu)學(xué)習(xí) 構(gòu)建貝葉斯網(wǎng)絡(luò) 2022/2/9 數(shù)據(jù)處理與智能決策 55 構(gòu)建貝葉斯網(wǎng)絡(luò) Bayesian Network Bayesian Network Bayesian Network Problem Domain Problem Domain Problem Domain Expert Knowledge Expert Knowledge Training Data Training Data Probability Elicitor Learning Algorithm Learning Algorithm 2022/2/9 數(shù)據(jù)處理與智能決策 56 3 貝葉斯問題的求解 貝葉斯學(xué)習(xí)理論利用先驗(yàn)信息和樣本數(shù)據(jù)來獲得對(duì)未知樣本的估計(jì)，而概率（聯(lián)合概率和條件概率）是先驗(yàn)信息和樣本數(shù)據(jù)信息在貝葉斯學(xué)習(xí)理論中的表現(xiàn)形式。如何獲得這些概率（也稱之為 密度估計(jì) ）是貝葉斯學(xué)習(xí)理論爭(zhēng)議較多的地方。 研究如何根據(jù)樣本的數(shù)據(jù)信息和人類專家的先驗(yàn)知識(shí)獲得對(duì)未知變量（向量）的分布及其參數(shù)的估計(jì)。它有 兩個(gè)過程 ： 一是 確定未知變量的先驗(yàn)分布； 二是獲得相應(yīng)分布的參數(shù)估計(jì)。 如果以前對(duì)所有信息一無所知，稱這種分布為 無信息先驗(yàn)分布 ； 如果知道其分布求它的分布參數(shù)， 稱之為 有信息先驗(yàn)分布 。 2022/2/9 數(shù)據(jù)處理與智能決策 57 3 貝葉斯問題的求解 選取 貝葉斯先驗(yàn)概率是用貝葉斯模型 求解 的 第一步 ，也是比較關(guān)鍵的一步。常用的選取先驗(yàn)分布的方法有 主觀 和 客觀 兩種。 主觀的方法 是 借助人的經(jīng)驗(yàn)、專家的知識(shí)等來指定其先驗(yàn)概率 。而 客觀的方法 是 通過直接分析數(shù)據(jù)的特點(diǎn)，來觀察數(shù)據(jù)變化的統(tǒng)計(jì)特征 ，它要求有足夠多的數(shù)據(jù)才能真正體現(xiàn)數(shù)據(jù)的真實(shí)分布。 2022/2/9 數(shù)據(jù)處理與智能決策 58 3 貝葉斯問題的求解 ? 共軛分布族 ? 先驗(yàn)與后驗(yàn)屬于同一分布族 ? 預(yù)先給定一個(gè)似然分布形式 ? 對(duì)于變量定義在 01之間的概率分布，存在一個(gè)離散的樣本空間 ? Beta 對(duì)應(yīng)著 2 個(gè)似然狀態(tài) ? 多變量 Dirichlet 分布對(duì)應(yīng) 2個(gè)以上的狀態(tài) 從數(shù)據(jù)中學(xué)習(xí) 3 貝葉斯問題的求解 Raiffa和 Schaifeer提出先驗(yàn)分布應(yīng)選取共軛分布，即要求后驗(yàn)分布與先驗(yàn)分布屬于同一分布類型。它的一般描述為 : 定義 7 設(shè)樣本 X1,X2,… ,Xn 對(duì)參數(shù) θ的條件分布為 p(x1,x2,… ,xn|θ)， 如果先驗(yàn)分布密度函數(shù) π(θ)決定的后驗(yàn)密度 π(θ|x)與 π(θ)同屬于一種類型 ，則稱 π(θ)為 p(x|θ)的 共軛分布 。 3 貝葉斯問題的求解 熵是信息論中描述事物不確定性的程度的一個(gè)概念。如果一個(gè)隨機(jī)變量只取與兩個(gè)不同的值，比較下面兩種情況： (1) p(x=a)=， p(x=a)=； (2) p(x=a)=， p(x=a)=。 很明顯 ， (1)的不確定性要比 (2)的不確定性小得多 ， 而且從直覺上也可以看得出當(dāng)取的兩個(gè)值得概率相等時(shí) ， 不確定性達(dá)到最大 。 3 貝葉斯問題的求解 定義 9 設(shè)隨機(jī)變量 x是離散的，它取 a1,a2,… ,ak,… 可列個(gè)值，且 p(x=ai)=pi(i=1,2,…) ， 則 H(x)= Σpilnpi 稱為 x的熵 。 對(duì)連續(xù)型隨機(jī)變量 x， 它的概率密度函數(shù)為 p(x)， 若積分 H(x)= ∫p(x)lnp(x)dx 有意義，稱它為 連續(xù)型隨機(jī)變量的熵 。 最大熵原則 ： 無信息先驗(yàn)分布應(yīng)取參數(shù) θ的變化范圍內(nèi)熵最大的分布 。 3 貝葉斯問題的求解 杰弗萊對(duì)于先驗(yàn)分布的選取做出了重大的貢獻(xiàn)，它提出一個(gè)不變?cè)?，較好地解決了貝葉斯假設(shè)中的一個(gè)矛盾，并且給出了一個(gè)尋求先驗(yàn)密度的方法。杰弗萊原則由 兩個(gè)部分 組成： 一是 對(duì)先驗(yàn)分布有一合理要求； 二是 給出具體的方法求得適合于要求的先驗(yàn)分布。 3 貝葉斯問題的求解 計(jì)算學(xué)習(xí)機(jī)制 任何系統(tǒng)經(jīng)過運(yùn)行能改善其行為，都是 學(xué)習(xí) 。到底貝葉斯公式求得的后驗(yàn)是否比原來信息有所改善呢？其學(xué)習(xí)機(jī)制是什么？ 現(xiàn)以正態(tài)分布為例進(jìn)行分析，從參數(shù)的變化看先驗(yàn)信息和樣本數(shù)據(jù)在學(xué)習(xí)中所起的作用。（ P170） 3 貝葉斯問題的求解 貝葉斯問題的求解步驟 貝葉斯問題求解的基本步驟可以概括為： (1)定義隨機(jī)變量。將未知參數(shù)看成隨機(jī)變量（或隨機(jī)向量），記為 θ。 將樣本 x1,x2,…, xn的聯(lián)合分布密度p(x1,x2,…, xn 。θ) 看成 x1,x2,…, xn對(duì) θ的條件分布密度，記為p(x1,x2,…, xn|θ) 或 p(D|θ) 。 (2)確定先驗(yàn)分布密度 p(θ) 。采用 共軛分布 先驗(yàn)分布。如果對(duì)先驗(yàn)分布沒有任何信息，就采用無信息先驗(yàn)分布的貝葉斯假設(shè)。 (3)利用貝葉斯定理計(jì)算后驗(yàn)分布密度 。 (4)利用計(jì)算得到的后驗(yàn)分布密度對(duì)所求問題做出判斷。 2022/2/9 數(shù)據(jù)處理與智能決策 65 1) n(n m/n) m(1 variance ? ? ? n m mean ? x) (1 x m) (n (m) (n) n) m, | (x p 1 m n 1 m Beta ? ? ? ? ? ? G G G 1012340 0 . 5 1 1 . 5xp(x|m,n)m =1 , n =2 m =2 , n =4 m =1 0 , n =2 0先驗(yàn)分布的選取－ beta分布 2022/2/9 數(shù)據(jù)處理與智能決策 66 先驗(yàn)分布的選?。囗?xiàng) Dirichlet分布 1) m ( m ) m / m (1 m state i theof variance m m state i theofmean ...x x x ) (m )... (m ) (m ) m ( ) m ,..., m , m | (x p N 1 i i N 1 i i N 1 i i i i th N 1 i i i th 1 m 1 m 1 m N 2 1 N 1 i i N 2 1 Dirichlet N 2 1 ? ? ? ? G G G G ? ? ? ? ? ? ? ? ? ? ? ? ? 2022/2/9 數(shù)據(jù)處理與智能決策 67 不完全數(shù)據(jù)的密度估計(jì) ?期望最大化方法（ Expectation Maximization EM） ?Gibbs抽樣（ Gibbs Sampling GS） ?Bound and Collapse (BC) 2022/2/9 數(shù)據(jù)處理與智能決策 68 期望最大化方法 分為以下幾個(gè)步驟： （ 1）含有不完全數(shù)據(jù)的樣本的缺項(xiàng)用該項(xiàng)的最大似然估計(jì)代替； （ 2）把第一步中的缺項(xiàng)值作為先驗(yàn)信息，計(jì)算每一缺項(xiàng)的最大后驗(yàn)概率，并根據(jù)最大后驗(yàn)概率計(jì)算它的理想值。 （ 3）用理想值替換（ 1）中的缺項(xiàng)。 （ 4）重復(fù)（ 1—3），直到兩次相繼估計(jì)的差在某一固定閥值內(nèi)。 2022/2/9 數(shù)據(jù)處理與智能決策 69 Gibbs抽樣 ? Gibbs抽樣（ Gibbs Sampling GS） GS是最為流行的馬爾科夫、蒙特卡羅方法之一。 GS把含有不完全數(shù)據(jù)樣本的每一缺項(xiàng)當(dāng)作待估參數(shù)，通過對(duì)未知參數(shù)后驗(yàn)分布的一系列隨機(jī)抽樣過程，計(jì)算參數(shù)的后驗(yàn)均值的經(jīng)驗(yàn)估計(jì)。 2022/2/9 數(shù)據(jù)處理與智能決策 70 貝葉斯網(wǎng)絡(luò)的結(jié)構(gòu)學(xué)習(xí) ? 基于搜索評(píng)分的方法 : ? 初始化貝葉斯網(wǎng)絡(luò)為孤立節(jié)點(diǎn) ? 使用啟發(fā)式方法為網(wǎng)絡(luò)加邊 ? 使用評(píng)分函數(shù)評(píng)測(cè)新的結(jié)構(gòu)是否為更好 ? 貝葉斯評(píng)分（ Bayesian Score Metric） ? 基于墑的評(píng)分 ? 最小描述長度 MDL(Minimal Description Length) ? 重復(fù)這個(gè)過程，直到找不到更好的結(jié)構(gòu) ? 基于依賴分析的方法 : ? 通過使用條件獨(dú)立性檢驗(yàn) conditional independence (CI) 找到網(wǎng)絡(luò)的依賴結(jié)構(gòu) 2022/2/9 數(shù)據(jù)處理與智能決策 71 基于 MDL的貝葉斯網(wǎng)結(jié)構(gòu)學(xué)習(xí) ? 計(jì)算每一點(diǎn)對(duì)之間的互信息： ? 建立完全的無向圖，圖中的頂點(diǎn)是變量，邊是變量之間的互信息 ? 建立最大權(quán)張成樹 ? 根據(jù)一定的節(jié)點(diǎn)序關(guān)系，設(shè)置邊的方向 ??yx,P p(x )p(y )y)p(x ,y )l ogP (x ,Y)(X 。I2022/2/9 數(shù)據(jù)處理與智能決策 72 基于條件獨(dú)立性的貝葉斯網(wǎng)絡(luò)學(xué)習(xí) ? 假定：節(jié)點(diǎn)序已知 ? 第一階段 (Drafting) ? 計(jì)算每對(duì)節(jié)點(diǎn)間的互信息，建立完整的無向圖 . ? 第二階段 (Thickening) ? 如果接點(diǎn)對(duì)不可能 d可分的話，把這一點(diǎn)對(duì)加入到邊集中。 ? 第三階段 (Thinning) ? 檢查邊集中的每個(gè)點(diǎn)對(duì)，如果兩個(gè)節(jié)點(diǎn)是 d可分的，那么移走這條邊。 2022/2/9 數(shù)據(jù)處理與智能決策 73 基于條件獨(dú)立性檢驗(yàn) (CI)的 貝葉斯網(wǎng)絡(luò)結(jié)構(gòu)學(xué)習(xí) 1）初始化圖結(jié)構(gòu) B=N,A,?,A=?,R=?,S=?。 2）對(duì)每一節(jié)點(diǎn)對(duì)，計(jì)算它們的互信息，并將互信息大于某一域值的節(jié)點(diǎn)對(duì)按互信息值的大小順序加入到 S中； 3）從 S中取出第一個(gè)點(diǎn)對(duì)，并從 S中刪除這個(gè)元素，把該點(diǎn)對(duì)加入到邊集A中； 4） 從 S中剩余的點(diǎn)對(duì)中，取出第一個(gè)點(diǎn)對(duì)，如果這兩各界點(diǎn)之間不存在開放路徑，再把該點(diǎn)對(duì)加入 A到中，否則加入到 R中； 5）重復(fù) 4),直到 S為空； 6）從 R中取出第一個(gè)點(diǎn)對(duì)； 7）找出該點(diǎn)對(duì)的某一塊集，在該子集上做獨(dú)立性檢驗(yàn)，如果該點(diǎn)對(duì)的兩個(gè)節(jié)點(diǎn)，仍然相互依賴，則加入到 A中； 8） 重復(fù) 6),直到 R為空； 9） 對(duì) A中的每一條邊，如果除這條邊外，仍舊含有開放路徑，則從 A中臨時(shí)移出，并在相應(yīng)的塊集上作獨(dú)立性測(cè)試，如果仍然相關(guān)，則將其返回到 A中，否則從 A中刪除這條邊。 2022/2/9 數(shù)據(jù)處理與智能決策 74 樹增廣的樸素貝葉斯網(wǎng) TAN的結(jié)構(gòu)學(xué)習(xí) 1 ） 計(jì)算各屬性