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