【正文】 Gibbs Sampling GS） ?Bound and Collapse (BC) 2022/2/9 數(shù)據(jù)處理與智能決策 68 期望最大化方法 分為以下幾個步驟： （ 1）含有不完全數(shù)據(jù)的樣本的缺項用該項的最大似然估計代替； （ 2）把第一步中的缺項值作為先驗信息，計算每一缺項的最大后驗概率，并根據(jù)最大后驗概率計算它的理想值。 （ 4）重復（ 1—3），直到兩次相繼估計的差在某一固定閥值內(nèi)。 GS把含有不完全數(shù)據(jù)樣本的每一缺項當作待估參數(shù)，通過對未知參數(shù)后驗分布的一系列隨機抽樣過程，計算參數(shù)的后驗均值的經(jīng)驗估計。I2022/2/9 數(shù)據(jù)處理與智能決策 72 基于條件獨立性的貝葉斯網(wǎng)絡學習 ? 假定：節(jié)點序已知 ? 第一階段 (Drafting) ? 計算每對節(jié)點間的互信息，建立完整的無向圖 . ? 第二階段 (Thickening) ? 如果接點對不可能 d可分的話，把這一點對加入到邊集中。 2022/2/9 數(shù)據(jù)處理與智能決策 73 基于條件獨立性檢驗 (CI)的 貝葉斯網(wǎng)絡結(jié)構(gòu)學習 1）初始化圖結(jié)構(gòu) B=N,A,?,A=?,R=?,S=?。 2022/2/9 數(shù)據(jù)處理與智能決策 74 樹增廣的樸素貝葉斯網(wǎng) TAN的結(jié)構(gòu)學習 1 ） 計算各屬性節(jié)點間的條件互信息 。 ??CAA jijijijijiCAPCAPCAAPCAAPCAAI, )|()|()|。()|,(2022/2/9 數(shù)據(jù)處理與智能決策 75 主動貝葉斯網(wǎng)絡分類器 ?主動學習： 主動在候選樣本集中選擇測試例子，并將這些實例以一定的方式加入到訓練集中。 //用當前的分類器 C標注 S中的元素，并把它加入到 L中。 //從 UL中移走 S. CheckStop(amp。 //根據(jù)當前狀態(tài)設置退出條件 } Return C。類條件熵最大的樣本的加入，使得分類器能夠?qū)哂刑厥庑畔⒌臉颖镜募霸缰匾?；而類條件熵最小的樣本是分類器較為確定的樣本，對它的分類也更加準確，從而部分地抑制了由于不確定性樣本的加入而產(chǎn)生的誤差傳播問題 ???? || 1 ))|(l n()|()|( Ci ii xcpxcpxCH2022/2/9 數(shù)據(jù)處理與智能決策 78 主動貝葉斯網(wǎng)絡分類器 ?基于分類損失與不確定抽樣相結(jié)合的主動學習 ?? x DD dxxpxcpxcpLL )()|(),|(( ^分類損失： 選擇過程： 從測試樣本中選擇個熵較大的樣本，組成集合 maxS，然后對此集合中每個元素計算相對于該集合的分類損失和，選擇分類損失和最小的樣本做標注并加入到訓練樣本集中。合理地組織這些信息，以便從茫茫的數(shù)據(jù)世界中，檢索到期望的目標；有效地分析這些信息，以便從浩如煙海的信息海洋中，挖掘出新穎的、潛在有用的模式，正在成為網(wǎng)上信息處理的研究熱點。 2022/2/9 數(shù)據(jù)處理與智能決策 81 6 貝葉斯?jié)撛谡Z義模型 聚類分析是文本挖掘的主要手段之一。 K均值聚類是比較典型的聚類算法，另外自組織映射（ SOM） 神經(jīng)網(wǎng)絡聚類和基于概率分布的貝葉斯層次聚類（ HBC） 等新的聚類算法也正在不斷的研制與應用中。而 網(wǎng)頁分類是一種監(jiān)督學習，它通過一系列訓練樣本的分析，來預測未知網(wǎng)頁的類別歸屬 。遺憾的是獲得大量的、帶有類別標注的樣本的代價是相當昂貴的，而這些方法只有通過大規(guī)模的訓練集才能獲得較高精度的分類效果。 通過引入貝葉斯?jié)撛谡Z義模型，首先將含有潛在類別主題變量的文檔分配到相應的類主題中。針對這兩階段的特點，我們定義了兩種似然函數(shù)，并利用 EM算法獲得最大似然估計的局部最優(yōu)解。為了與純粹的監(jiān)督與非監(jiān)督學習相區(qū)別，稱這種方法為 半監(jiān)督學習算法 。這個映射是通過對項 /文檔矩陣 Nm n的奇異值分解（ SVD）來實現(xiàn)的。潛在語義分析通過取 k個最大的奇異值，而將剩余的值設為零來近似 (42) 2022/2/9 數(shù)據(jù)處理與智能決策 84 ~~ TTU V U V NN ?????LSA 的應用： 信息濾波、文檔索引、視頻檢索 文檔的相似性 TTT UUNNNN ~ 2~~ ???特征的相似性 6 貝葉斯?jié)撛谡Z義模型 ~???(43) 2022/2/9 數(shù)據(jù)處理與智能決策 85 以一定的概率選擇文檔 d )|( ?dp以一定的概率選擇一潛在變量 z ),|( ?dzp以一定的概率產(chǎn)生特征 w ),|( ?zwp產(chǎn)生如下的聯(lián)合概率模型 ???Zzzdpzwpzpwdp ),|(),|()|()|,( ????6 貝葉斯?jié)撛谡Z義模型 設文檔集合為 D={d1, d2,… , dn}， 詞匯集為 W={w1, w2,… , wm }，則 文檔 d∈ D的產(chǎn)生模型可表述為： 2022/2/9 數(shù)據(jù)處理與智能決策 86 d1 d2 d3 dn ... w1 w2 w3 wm ... z1 z2 zk ... 圖 3 貝葉斯?jié)撛谡Z義模型 6 貝葉斯?jié)撛谡Z義模型 圖 3 表明了該模型各分量間的關(guān)聯(lián)。1jiDDDD jikjj ???????7 半監(jiān)督文本挖掘算法 D ? { d1, d2,…, dn } 詞匯集 先驗信息 潛在內(nèi)部變量 網(wǎng)頁聚類 W ? { w1, w2,…, wm } Z ? { z1, z2,…, zk } Θ ? { ?1, ?2,…, ?k } 2022/2/9 數(shù)據(jù)處理與智能決策 89 解決策略： 1. 劃分 D為兩個集合： D = DL∪ DU ，滿足： ]}1[,|{ kjdzjdD jL ?????]}1[,|{ kjdzjdD jU ?????3. 使用 Naive Bayesian標注 DU 2. 使用 BLSA 標注 DL 7 半監(jiān)督文本挖掘算法 網(wǎng)頁聚類 2022/2/9 數(shù)據(jù)處理與智能決策 90 1) 使用 BLSA估計分布參數(shù) 2) 使用最大后驗概率標注文檔 )}|({m a x)( iij zdpzdl ??1. 使用 BLSA 標注 LD7 半監(jiān)督 文本 挖掘算法 網(wǎng)頁聚類 (51) 2022/2/9 數(shù)據(jù)處理與智能決策 91 EM算法是稀疏數(shù)據(jù)參數(shù)估計的主要方法之一。它的一般過程可描述為： ⑴ E步，基于當前的參數(shù)估計，計算它的期望值； ⑵ M步，基于 E步參數(shù)的期望值，最大化當前的參數(shù)估計； ⑶ 對修正后的參數(shù)估計，計算似然函數(shù)值，若似然函數(shù)值達到事前制定的閾值或者指定的迭代次數(shù)，則停止，否則轉(zhuǎn)步驟⑴ 。 )。|()|()。|()|()。39。z zwpzdpzpzwpzdpzpwdzP???????⑴ 在 E步，通過下面的貝葉斯公式來獲得期望值： ⑵ 在 M步中，利用上一步的期望值，來重新估計參數(shù)的分布密度： ??? 39。39。,|(),()。|(wddwdzpwdnwdzpwdnzwp?????? wd w wdzpwdnwdzpwdnzdp,39。39。,|(),()。|(?????? wdwd wdnwdzpwdnzp,),()。 6500006000005500005000004500004000001 2 3 4 5 6 7 8 9 10 11n u m be r of i t e r a t i onloglikelihood7 半監(jiān)督文本挖掘算法 對含有潛在類別主題詞文檔的類別標注 2022/2/9 數(shù)據(jù)處理與智能決策 94 2. 使用 Naive Bayesian標注 UD? ?? ???||1||1)。1 ijzz kjki ???M步： ||||1))((|| 1ZDcdcIDi iic j ???? ? ??? ??? ???????mkDi jikiDi jitijcw cdcIwdncdcIwdnjt1||10||1| ))((),())((),(???E步 : 似然 函數(shù) 7 半監(jiān)督 文本 挖掘算法 (61a) 2022/2/9 數(shù)據(jù)處理與智能決策 95 試驗結(jié)果 1000 足球類文檔 876 特征詞 050100150200250300350AodongBeijingg...TaishanXiamenxi...HaishiWuhaiTsingdaoShenzhen...JiaANational...JiaBYijiaYingchaoDejiaWorldcup14 Latent variables7 Latent variables 7 半監(jiān)督 文本 挖掘算法 2022/2/9 數(shù)據(jù)處理與智能決策 96 貝葉斯網(wǎng)中的證據(jù)推理 目的：通過聯(lián)合概率分布公式，在給定的網(wǎng)絡結(jié)構(gòu) 和已知證據(jù)下，計算某一事件的發(fā)生的概率。ve Bayesian ? 圖約簡算法 ? Polytree算法 ? 近似推理 ? 前向模擬推理 ? 隨機模擬推理 The algorithm’s purpose is “… fusing and propagating the impact of new evidence and beliefs through Bayesian works so that each proposition eventually will be assigned a certainty measure consistent with the axioms of probability theory.” (Pearl, 1988, p 143) 2022/2/9 數(shù)據(jù)處理與智能決策 103 精確推理－計算聯(lián)合概率 任何查詢都可以通過聯(lián)合概率回答 步驟： ?計算聯(lián)合概率 P(AB)=P(A)*P(B|A) ?邊界化不在查詢中的變量 P(B)=ΣAP(AB) ?效率低 A B 2022/2/9 數(shù)據(jù)處理與智能決策 104 圖約簡算法－一般原理 ? 基本觀點 任何概率查詢可以表示成網(wǎng)絡的子網(wǎng)，推理的目的是把網(wǎng)絡分解成幾個子網(wǎng) ? 三個基本操作 ? 擬轉(zhuǎn)弧操作（ Arc Reversal）－ 貝葉斯公式 ? 孤寡點移出 (Barren node removal)－ 求和公式 ? 值節(jié)點歸并 (Merge with Value node)－ 期望最大化 2022/2/9 數(shù)據(jù)處理與智能決策 105 約簡算法－擬轉(zhuǎn)弧操作 X1 X3 X2 X1 X3 X2 X1 X3 X2 X1 X3 X2 p(x1, x2, x3) = p(x3 | x1) p(x2 | x1) p(x1) p(x1, x2, x3) = p(x3 | x2, x1) p(x2) p( x1) p(x1, x2, x3) = p(x3 | x1) p(x2 , x1) = p(x3 | x1) p(x1 | x2) p( x2) p(x1, x2, x3) = p(x3, x2 | x1) p( x1) = p(x2 | x3, x1) p(x3 | x1) p( x1) 2022/2/9 數(shù)據(jù)處理與智能決策 106 約簡算法－孤寡點移出 孤寡點－沒有孩子的節(jié)點 2022/2/9 數(shù)據(jù)處理與智能決策 107 約簡算法－值節(jié)點歸并 值節(jié)點－證據(jù)節(jié)點或賦值節(jié)點 2022/2/9 數(shù)據(jù)處理與智能決策 108 Polytree算法－介紹 ? 該算法由 Pearl 于 1982年首次提出 ? 基本觀點 計算邊界后驗的消息傳遞機制 Lambda 算子：消息向上傳向父親 pi 算子：消息向下傳向孩子 2022/2/9 數(shù)據(jù)處理與智能決策 109 Polytree算法－單連通網(wǎng) 定義： 在任何兩個節(jié)點之間存在且僅存在一條路徑（忽略方向） X Multiple parents and/or multiple children 2022/2/9 數(shù)據(jù)處理與智能決策 110 單連通網(wǎng)的表示 X 表示 m維隨機向量 。 Bel(A) = ? ?(A) ?(A) ?(A) Bel(A) ?(A) A1 A2 (2) ?(B) = ?(A)