動態(tài)貝葉斯網絡參數(shù)學習算法的一種加速.pdf

第2 8 卷第8 期增刊 2 0 0 7 年8 月 儀器儀表學報 C h i n e s eJ o u r n a lo fS c i e n t i f i cI n s t r u m e n t V o L2 8N o 8 A u g 2 0 0 7 動態(tài)貝葉斯網絡參數(shù)學習算法的一種加速 莫富強 王浩 姚宏亮 合肥工業(yè)大學計算機與信息學院合肥2 3 0 0 0 9 摘要 針對動態(tài)貝葉斯網絡E M 參數(shù)學習算法中計算量大和收斂速度慢問題 通過將大規(guī)模時序數(shù)據集劃分為較小的數(shù) 據塊 提出一種基于部分E 步的加速算法 D A E M D A E M 在塊間循環(huán)迭代 每一次迭代執(zhí)行部分E 步 增量式地更新似 然函數(shù)和網絡參數(shù) 以縮短E 步執(zhí)行時間 該算法在不損失精度情況下能顯著加快E M 算法的收斂速度 有效地提高E M 算 法的計算效率 實驗表明 D A E M 算法有較高的計算效率 關鍵詞 動態(tài)B a y e s i a n 網絡 參數(shù)學習 D A E M M e t h o df o ra c c e l e r a t i n gp a r a m e t e rl e a r n i n go fd y n a m i cb a y e s i a nn e t w o r k s M oF u q i a n g W a n gH a o Y a oH o n g l i a n g S c h o o lo fC o m p u t e ra n dI n f o r m a t i o n H e f e iU n i v e r s i t yo fT e c h n o l o g y H e f e i2 3 0 0 0 9 C h i n a A b s t r a c t T h ea l g o r i t h mb a s e do nE M f o rD B Np a r a m e t e rl e a r n i n go f t e nn e e d sg r e a tc o m p u t a t i o n a lc o s t sa n dt h e c o n v e r g e n c ei Ss l o w T oo v e r c o m et h ed r a w b a c k s l a r g et e m p o r a ld a t as e ti Sd i v i d e di n t os m a l lb l o c k s t h e na n a e c e l e r a t i n gE Ma l g o r i t h m D A E M b a s e do np a r t i a lE s t e pi sp r o p o s e d B yi t e r a t i n gi nt h eb l o c k sc y c l i c a l l y D A E Mu p d a t e sl i k e l i h o o df u n c t i o na n dB a y e s i a np a r a m e t e r si n c r e m e n t a l l y S Ot h ec o m p u t a t i o n a lt i m eo fE s t e pi s s h o r t e n D A E Mc a ng u a r a n t e et h ep r e c i s i o no fE M m a k ei tc o n v e r g ef a s t e ra n dc o m p u t em o r ee f f i c i e n t l y T h ee x p e r i m e n t a lr e s u l t sj u s t i f yt h ec o m p u t a t i o n a le f f i c i e n c yo ft h em e t h o d K e yw o r d s D B N s p a r a m e t e rl e a m i n g D A E M 1 引言 動態(tài)貝葉斯網絡 d y n a m i cb a y e s i a nn e t w o r k s D B N s 是動態(tài)系統(tǒng)概率關系的一種壓縮表示形式 適 合用于描述非線性關系和具有隨機過程性質的不確定 性問題 1 D B N s 的學習包含結構學習和參數(shù)學習 2 其中 結構學習是尋找與訓練樣本擬合得最好的網絡結構 即確定D B N s 的初始網絡和轉移網絡結構 參數(shù)學習 是在已知D B N s 網絡結構的情況下 確定網絡各節(jié)點 的條件概率 文獻 2 3 分別對D B N s 的結構學習和 參數(shù)學習進行了研究 本文以這些理論為基礎 進一步 研究了D B N s 的參數(shù)學習算法 E M 算法 e x p e c t a t i o nm a x i m i z a t i o n 是一種存在 缺失數(shù)據情況下參數(shù)學習的常用算法 它實質上是一 個優(yōu)化算法 并且能收斂到局部極值 但是 收斂速度 慢 算法執(zhí)行效率低是其主要缺點 4 目前對E M 算法的改進主要有兩種方法 基于部 分M 步和基于部分E 步方法 部分M 步方法可以提 高E M 算法在M 步的計算效率 同時又可以保證算法 的收斂特性 如泛化E M 算法 G E M 4 和期望條件最 大化算法 E C M 5 然而 E M 算法的計算復雜度主 要體現(xiàn)在E 步 它的計算量是隨數(shù)據集線性增加的 所 以 部分M 步方法不能降低期望充分統(tǒng)計因子的計算 量 對E M 算法的加速也是有限的 M o o r e 等人提出 改進E 步的方法 6 但不能保證算法的收斂特性 為 此 針對D B N s 的時序數(shù)據集 本文提出一個基于部分 E 步的D B N s 的E M 加速算法 D A E M 算法 d y n a m i c a c c e l e r a t i n ge x p e c t a t i o nm a x i m i z a t i o n 該方法既能減 少E M 算法的計算強度 同時又能保證E M 算法的收 斂特性 第8 期增刊莫富強等 動態(tài)貝葉斯網絡參數(shù)學習算法的一種加速 4 7 1 2 基于E M 算法的D B N s 的參數(shù)學習 2 1D B N s 的參數(shù)學習 動態(tài)貝葉斯網絡是對傳統(tǒng)貝葉斯網絡的擴展 是 表示和處理復雜隨機過程問題的一種有效方法 對于初始時間片t O 時 結點之間的邊以及局部 概率函數(shù)和先驗網絡相同 在時間片t 1 和時間片t 之間的邊由轉移網絡具體確定 與靜態(tài)貝葉斯網絡一 樣 動態(tài)貝葉斯網絡的聯(lián)合概率分布是建立在變量的 條件獨立性假設的基礎之上 匿藕 圖1 一個D B N 的初始網和轉換網 設X 一 殄 是D B N 的隨機變量集 X 表 示變量X 在t 時對應的隨機變量 一個D B N 由一個 初始網B 0 見圖1 左圖 和一個轉換網B 圖1 的右 圖 組成 初始網B o 給出系統(tǒng)初始狀態(tài)的網絡結構和 聯(lián)合概率分布 n P X o P 墨lj 缸 磁 1 轉換網B 表示t 一1 時到t 時狀態(tài)變量集的轉移 概率P XI 五一1 D B N s 在X 一 X 1 刀 上的 聯(lián)合概率分布可以表示為 島 r r 一如 X o 崩P B x fK 2 動態(tài)B a y e s i a n 網的參數(shù)學習就是定義初始網絡的 參數(shù)和定義轉移網絡的參數(shù) 即給定網絡拓撲結構S 和訓練樣本集D 確定D B N s 各節(jié)點的條件概率 記為 p O ID S 用于D B N s 學習的數(shù)據集合是時序數(shù)據 D f 1 c 2 c 即每個事例f f 含T 個時間片的數(shù) 據 其中狀態(tài)變量都是缺省的 初始網絡參數(shù)的學習 是基于第一個時間片的 轉移網絡參數(shù)的學習是基于 2 一T 時間片的 r i 為結構S 中變量五的父節(jié)點集 則p C v i 一志I 噩一歹 表示給定噩為第j 種可能取值時 節(jié)點蕾為第k 種取值的概率 記為乳 2 2 基于E M 的D B N s 參數(shù)學習 E M 算法是一種計算最大似然函數(shù) M L 的通用 算法 其主要思想是在開始設定一個初始估計擴 然 后不斷地修正它 從當前的估計儼 到下一個估計 伊件n 需要兩個步驟 期望計算和最大化 在該算法中 對于所有的訓練樣本集D 和所有的 變量五 計算條件概率p x i 瑪ID t 給定數(shù)據集 D 其似然函數(shù)為 z 口ID l n p DI f x j 疵 1 棚馳 3 其中 霹 疵 表示當X 一k 且P j 時在數(shù)據集 中的取值 最大似然函數(shù)0 可以由下式得到 一券器 期望計算 E 步 是計算給定D 時 當前0 的似然 函數(shù)期望 z 口I 伊 一 l n p D z 乃lO p X l B 擴o 5 對于所有的0 應滿足 l O I 升 l O l 根據式 3 有 z 8 伊o 一 f 疊 疤 l n 0 私 6 這里L x I r i p x 鞏In 伊o 是通過平 滑推理機s m o o t h e r e n g i n e 推理而得 最大化 M 步 是通過最大化當前期望似然函數(shù) 值 選擇下一個估計 件 口昝 a g rm a xE P Dl 口 ID 伊o S 一 毒墮車 7 i 廠 蠢 疵 7 式 6 和式 7 分別為E M 算法的期望計算和最大 化計算等式 3D A E M 算法 3 1 算法思想 傳統(tǒng)的E M 算法的巨大的時間復雜性主要體現(xiàn)在 E 步驟 6 中的期望充分統(tǒng)計因子工 z 礓 一 p x i l r iD l 儼 的計算上 算法只有遍歷整個數(shù) f 據集后 才能完成一次網絡參數(shù)的更新 不能快速利用 數(shù)據中所蘊涵的信息 由此導致了似然函數(shù)和網絡參 數(shù)的更新頻率偏低 進而使得算法的收斂速度慢 其所 需要的計算時間與數(shù)據集的數(shù)量成線性關系 D A E M 算法將數(shù)據集分塊 然后以塊為單位在數(shù)據塊之 間循環(huán)迭代 通過執(zhí)行部分E 步來減少期望充分統(tǒng)計 因子的計算量 從而減少算法計算強度 加快參數(shù)更新 的頻率和收斂速度 進而提高整個算法的學習性能 增 強算法對時序數(shù)據的適應能力 4 7 2儀器儀表學報 第2 8 卷 D A E M 算法必須解決兩個關鍵問題 確定數(shù)據塊 的大小和算法收斂性的判別 3 1 1 數(shù)據塊的劃分 用y 奠 魏 斂 表示把數(shù)據集劃分為k 個 互不相交的數(shù)據塊的一個特定劃分 其中Y i 表示第i 個數(shù)據塊 D A E M 算法在塊間循環(huán)迭代 每一次迭代 執(zhí)行一個部分E 步 增量式地更新似然函數(shù)和網絡參 數(shù) 以縮短E 步執(zhí)行時間 數(shù)據塊的大小直接影響了D A E M 算法的執(zhí)行效 率 實驗表明 隨著數(shù)據集合的變化 精確度和速度相 對最優(yōu)的數(shù)據塊的大小相對穩(wěn)定在一個區(qū)間 遺憾的 是目前為止還沒有標準的數(shù)據塊劃分方法m 本文 給出一個在實驗中確定數(shù)據塊劃分方法 令s o 和s 為 兩個后驗分布 分別表示初始化和首次遍歷數(shù)據塊后 似然函數(shù)的值 用t 表示從分布S O 到分布兩所用的 時間 通過執(zhí)行一個簡單的搜索來確定速率r a t i o r a t i o 一 5 那么使得速率r a t i o 最大的所經過的樣 本數(shù)目r 是最優(yōu)的數(shù)據塊內所包含的樣本數(shù)目 3 1 2 算法收斂性判別 在傳統(tǒng)E M 算法中 由于似然函數(shù)值具有單調性 如果兩次迭代似然函數(shù)的差值小于既定的收斂閥值 則認為算法是收斂的 但該方法不適用于D A E M 因 為在D J A E M 算法中 塊間迭代的似然函數(shù)值不滿足 單凋性 因此在本算法中采用一個近似方式表示似然 函數(shù) 即 L yI 伊o yI 伊o yJ 伊卜1 一L y iJ D L y I 伊 8 N e a l c 8 3 證明對于所有樣本n k L L 葉 成立 即在數(shù)據塊的兩次遍歷間的似然函數(shù)值仍然保持單調 r d r t k 不減 因此當C 一生1 扣小于收斂閥值s 時 D A b E M 算法收斂 在本文中取S l e 一3 嘩 t t 一誓 岫 一 o 3 2D A E M 算法描述 算法的第n 1 次迭代如下所示 E 步 1 選擇數(shù)據塊Y i 1 2 k 2 計算概率 療 多 五 7 r 麓 f Y i 伊 Q 口 礦I Q 口 礦 1l Y J f o rj i 計算 Q 一 f 六 一瞬 z 弓 f o rj i 3 合并似然函數(shù) o 一 I 口 y Q j 伊 I 曰 Y M 步 更新Q 函數(shù) Q 毋l 礦 y 一Q 穢I 擴1 了 Q 參 伊 為 一Q 穢 伊一 弘 選擇礦 1 使得最大化Q 口I 伊 y D A E M 算法中 部分E 步以增量方式構造并最大 化似然函數(shù)期望 Q 函數(shù) 每一步迭代過程中 算法 只是更新Q 函數(shù)的一部分 即只更新當前數(shù)據塊所形 成的似然函數(shù)期望 g 對于其他的數(shù)據塊 仍然沿用 上一次迭代中的Q 函數(shù)的值 因此 每次迭代Q 函數(shù) 只需加上當前數(shù)據塊的新舊似然函數(shù)期望的差值 與 標準E M 算法相比 D A E M 算法增加了K 個存儲開 銷 即增加了數(shù)據塊k 1 i 時的Q 函數(shù)的 存儲 4 實驗結果和分析 4 1 實驗環(huán)境和數(shù)據 本文的工作使用M A T L A B 版本為6 5 運行環(huán)境 為操作系統(tǒng)W i n d o w sX P C P Up 41 6G H z 內存2 5 6 M 硬盤8 0G 實驗是在系統(tǒng)貝葉斯工具包B N T C 9 3 作者K e v i nM u r p h y 下進行的 此軟件可在網上 下載 使用w a t e r 網絡作為測試網絡 該網絡每個時間 片1 2 個節(jié)點 4 條邊 轉移網絡2 2 條邊 分別用本文 提出的D A E M 算法與標準E M 算法對網絡進行參數(shù) 學習 在學習精度和時間性能上 對兩個算法進行比 較 利用概率邏輯抽樣算法按4 個證據變量和8 個狀 態(tài)變量分別產生9 個訓練樣本集 分別包括1 0 0 2 0 0 4 0 0 8 0 0 16 0 0 32 0 0 64 0 0 1 28 0 0 2 56 0 0 個樣本 4 2 評價標準 采用參數(shù)學習算法從訓練樣本中獲得的條件概率 密度為P 7 V I 丌 口 由于實際結點處的條件概率密度 P 7 V Iz r v 是已知的 于是作為結果的條件概率密度 與真實的條件概率密度之間的差別可以用來作為評價 參數(shù)學習結果的測度 這里采用K u l l b a c k L e i b l e r 距 離 1 0 進行計算 K u l l b a c k L e i b l e r 距離定義為 K L p P 7 P V I7 r u l o g p V l 丌 口 P 7 Vl 丌 口 9 這里K L 距離大于等于0 當P 7 y l7 r 口 與p V f 丌 口 越接近時 K u l l b a c k L e i b l e r 距離越小 說明參數(shù) 第8 期增刊莫富強等 動態(tài)貝葉斯網絡參數(shù)學習算法的一種加速 4 7 3 學習的結果越精確 4 3 實驗結果分析 采用D A E M 算法與標準的E M 算法對w a t e r 網 絡參數(shù)學習的K L 距離如圖2 所示 樣本大小 x 1 0 4 圖2 兩種算法學習的K L 距離 圖2 中 橫坐標表示訓練樣本集的大小 所含樣本 的數(shù)目 縱坐標表示參數(shù)學習結果與真實值之間的 K L 距離 從圖可以清楚地看出 對于相同的訓練樣本 集 當訓練樣本集較小時 改進的E M 算法所得參數(shù)學 習結果與標準E M 算法所得結果略有差距 但隨著樣 本集的增大 兩種算法所得參數(shù)結果無限趨近 這說 明改進后的算法能夠保證網絡的精度要求 表1 算法所耗用的C P U 時間 S 圖3 中 橫坐標表示訓練樣本集的大小 所含樣本 的數(shù)目 縱坐標表示算法所耗用的時間 從圖3 和表 1 2 中可看出 改進后的算法在速度上明顯優(yōu)于原算 法 而且隨著樣本集的增大 這種優(yōu)勢越來越明顯 函 f 么 樣本大小 x 1 0 4 圖3 兩種算法學習速度比較 5 結論 E M 算法是動態(tài)貝葉斯網絡參數(shù)學習的一種主要 方法 本文通過將大規(guī)模時序數(shù)據集劃分為較小的數(shù) 據塊 并通過塊間的循環(huán)迭代 增量式地更新似然函數(shù) 和網絡參數(shù) 對傳統(tǒng)的E M 算法進行了改進 實驗表 明改進的D A E M 算法在保證結果精度的前提下 在 時間性能上有較大的改進 參考文獻 1 D E A N T L K A N A z A w A f P r o b a b i l i s t i ct e m p o r a l r e a s o n i n g C 1M i t e h e l lTM S m i t hR GP r o co f7 t h N a t i o n a lC o n f e r e n c eo nA r t i f i c i a lI n t e l l i g e n c e M a d i s o n W i s c o n s i n A A I P r e s s 1 9 8 8 5 2 4 5 2 8 2 F R I E D M A NN M U R P H YK R U S S E L LSL e a r n i n gt h es t r u c t u r eo fd y n a m i cp r o b a b i l i s t i cn e t w o r k s c I n P r o c C o h i o nU n c e r t a i n t yi nA I U A I M a d i s o n W I 1 9 9 8 3 K E NP A T R I c KM u R P H Y D y n a m i cB a y e s i a n N e t w o r k s R e p r e s e n t a t i o n I n f e r e n c ea n dL e a r n i n g z D i s s e r t a t i o nf o rD o c t o rd e g r e eo ft h eu n i v e r s i t y o fC a l i f o r n i a B e r k e l e y F a l l2 0 0 2 4 D E M P S T E R AP L A I R D N R U B I N D B M a x i m u ml i k e l i h o o df r o mi n c o m p l e t ed a t av i at h eE M a l g o r i t h m J J o u r n a lo ft h eR o y a lS t a t i s t i c a lS o c i e t y S e t i e sB 1 9 7 7 3 9 i 3 8 5 砸N G X L R U B I N D 1 3 M a x i m u ml i k e l i h o o d e s t i m a t i o nv i at h eE C Ma l g o r i t h m Ag e n e r a lf r a m e w o r k J B i o m e t r i k a 1 9 9 3 8 0 2 2 6 7 2 7 8 6 S A T O MI S H I I O n l i n eE Ma l g o r i t h mf o rt h e n o r m a l i z e dG a u s s i a nn e t w o r k J N e u r a lC o m p u t a t i o n 2 0 0 0 1 2 2 4 0 7 4 3 2 7 T H I S s 0 N B M E E K C H E c K E R MA N DA c c e l e r a r i n gE M f o rL a r g eD a t a b a s e sE J M a c h i n eL 七a r n i n g 2 0 0 1 4 5 3 2