動(dòng)態(tài)貝葉斯網(wǎng)絡(luò)參數(shù)學(xué)習(xí)算法的一種加速.pdf

第2 8 卷第8 期增刊 2 0 0 7 年8 月 儀器儀表學(xué)報(bào) 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 動(dòng)態(tài)貝葉斯網(wǎng)絡(luò)參數(shù)學(xué)習(xí)算法的一種加速 莫富強(qiáng) 王浩 姚宏亮 合肥工業(yè)大學(xué)計(jì)算機(jī)與信息學(xué)院合肥2 3 0 0 0 9 摘要 針對(duì)動(dòng)態(tài)貝葉斯網(wǎng)絡(luò)E M 參數(shù)學(xué)習(xí)算法中計(jì)算量大和收斂速度慢問(wèn)題 通過(guò)將大規(guī)模時(shí)序數(shù)據(jù)集劃分為較小的數(shù) 據(jù)塊 提出一種基于部分E 步的加速算法 D A E M D A E M 在塊間循環(huán)迭代 每一次迭代執(zhí)行部分E 步 增量式地更新似 然函數(shù)和網(wǎng)絡(luò)參數(shù) 以縮短E 步執(zhí)行時(shí)間 該算法在不損失精度情況下能顯著加快E M 算法的收斂速度 有效地提高E M 算 法的計(jì)算效率 實(shí)驗(yàn)表明 D A E M 算法有較高的計(jì)算效率 關(guān)鍵詞 動(dòng)態(tài)B a y e s i a n 網(wǎng)絡(luò) 參數(shù)學(xué)習(xí) 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 引言 動(dòng)態(tài)貝葉斯網(wǎng)絡(luò) 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 是動(dòng)態(tài)系統(tǒng)概率關(guān)系的一種壓縮表示形式 適 合用于描述非線性關(guān)系和具有隨機(jī)過(guò)程性質(zhì)的不確定 性問(wèn)題 1 D B N s 的學(xué)習(xí)包含結(jié)構(gòu)學(xué)習(xí)和參數(shù)學(xué)習(xí) 2 其中 結(jié)構(gòu)學(xué)習(xí)是尋找與訓(xùn)練樣本擬合得最好的網(wǎng)絡(luò)結(jié)構(gòu) 即確定D B N s 的初始網(wǎng)絡(luò)和轉(zhuǎn)移網(wǎng)絡(luò)結(jié)構(gòu) 參數(shù)學(xué)習(xí) 是在已知D B N s 網(wǎng)絡(luò)結(jié)構(gòu)的情況下 確定網(wǎng)絡(luò)各節(jié)點(diǎn) 的條件概率 文獻(xiàn) 2 3 分別對(duì)D B N s 的結(jié)構(gòu)學(xué)習(xí)和 參數(shù)學(xué)習(xí)進(jìn)行了研究 本文以這些理論為基礎(chǔ) 進(jìn)一步 研究了D B N s 的參數(shù)學(xué)習(xí)算法 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ù)據(jù)情況下參數(shù)學(xué)習(xí)的常用算法 它實(shí)質(zhì)上是一 個(gè)優(yōu)化算法 并且能收斂到局部極值 但是 收斂速度 慢 算法執(zhí)行效率低是其主要缺點(diǎn) 4 目前對(duì)E M 算法的改進(jìn)主要有兩種方法 基于部 分M 步和基于部分E 步方法 部分M 步方法可以提 高E M 算法在M 步的計(jì)算效率 同時(shí)又可以保證算法 的收斂特性 如泛化E M 算法 G E M 4 和期望條件最 大化算法 E C M 5 然而 E M 算法的計(jì)算復(fù)雜度主 要體現(xiàn)在E 步 它的計(jì)算量是隨數(shù)據(jù)集線性增加的 所 以 部分M 步方法不能降低期望充分統(tǒng)計(jì)因子的計(jì)算 量 對(duì)E M 算法的加速也是有限的 M o o r e 等人提出 改進(jìn)E 步的方法 6 但不能保證算法的收斂特性 為 此 針對(duì)D B N s 的時(shí)序數(shù)據(jù)集 本文提出一個(gè)基于部分 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 算法的計(jì)算強(qiáng)度 同時(shí)又能保證E M 算法的收 斂特性 第8 期增刊莫富強(qiáng)等 動(dòng)態(tài)貝葉斯網(wǎng)絡(luò)參數(shù)學(xué)習(xí)算法的一種加速 4 7 1 2 基于E M 算法的D B N s 的參數(shù)學(xué)習(xí) 2 1D B N s 的參數(shù)學(xué)習(xí) 動(dòng)態(tài)貝葉斯網(wǎng)絡(luò)是對(duì)傳統(tǒng)貝葉斯網(wǎng)絡(luò)的擴(kuò)展 是 表示和處理復(fù)雜隨機(jī)過(guò)程問(wèn)題的一種有效方法 對(duì)于初始時(shí)間片t O 時(shí) 結(jié)點(diǎn)之間的邊以及局部 概率函數(shù)和先驗(yàn)網(wǎng)絡(luò)相同 在時(shí)間片t 1 和時(shí)間片t 之間的邊由轉(zhuǎn)移網(wǎng)絡(luò)具體確定 與靜態(tài)貝葉斯網(wǎng)絡(luò)一 樣 動(dòng)態(tài)貝葉斯網(wǎng)絡(luò)的聯(lián)合概率分布是建立在變量的 條件獨(dú)立性假設(shè)的基礎(chǔ)之上 匿藕 圖1 一個(gè)D B N 的初始網(wǎng)和轉(zhuǎn)換網(wǎng) 設(shè)X 一 殄 是D B N 的隨機(jī)變量集 X 表 示變量X 在t 時(shí)對(duì)應(yīng)的隨機(jī)變量 一個(gè)D B N 由一個(gè) 初始網(wǎng)B 0 見(jiàn)圖1 左圖 和一個(gè)轉(zhuǎn)換網(wǎng)B 圖1 的右 圖 組成 初始網(wǎng)B o 給出系統(tǒng)初始狀態(tài)的網(wǎng)絡(luò)結(jié)構(gòu)和 聯(lián)合概率分布 n P X o P 墨lj 缸 磁 1 轉(zhuǎn)換網(wǎng)B 表示t 一1 時(shí)到t 時(shí)狀態(tài)變量集的轉(zhuǎn)移 概率P XI 五一1 D B N s 在X 一 X 1 刀 上的 聯(lián)合概率分布可以表示為 島 r r 一如 X o 崩P B x fK 2 動(dòng)態(tài)B a y e s i a n 網(wǎng)的參數(shù)學(xué)習(xí)就是定義初始網(wǎng)絡(luò)的 參數(shù)和定義轉(zhuǎn)移網(wǎng)絡(luò)的參數(shù) 即給定網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)S 和訓(xùn)練樣本集D 確定D B N s 各節(jié)點(diǎn)的條件概率 記為 p O ID S 用于D B N s 學(xué)習(xí)的數(shù)據(jù)集合是時(shí)序數(shù)據(jù) D f 1 c 2 c 即每個(gè)事例f f 含T 個(gè)時(shí)間片的數(shù) 據(jù) 其中狀態(tài)變量都是缺省的 初始網(wǎng)絡(luò)參數(shù)的學(xué)習(xí) 是基于第一個(gè)時(shí)間片的 轉(zhuǎn)移網(wǎng)絡(luò)參數(shù)的學(xué)習(xí)是基于 2 一T 時(shí)間片的 r i 為結(jié)構(gòu)S 中變量五的父節(jié)點(diǎn)集 則p C v i 一志I 噩一歹 表示給定噩為第j 種可能取值時(shí) 節(jié)點(diǎn)蕾為第k 種取值的概率 記為乳 2 2 基于E M 的D B N s 參數(shù)學(xué)習(xí) E M 算法是一種計(jì)算最大似然函數(shù) M L 的通用 算法 其主要思想是在開(kāi)始設(shè)定一個(gè)初始估計(jì)擴(kuò) 然 后不斷地修正它 從當(dāng)前的估計(jì)儼 到下一個(gè)估計(jì) 伊件n 需要兩個(gè)步驟 期望計(jì)算和最大化 在該算法中 對(duì)于所有的訓(xùn)練樣本集D 和所有的 變量五 計(jì)算條件概率p x i 瑪ID t 給定數(shù)據(jù)集 D 其似然函數(shù)為 z 口ID l n p DI f x j 疵 1 棚馳 3 其中 霹 疵 表示當(dāng)X 一k 且P j 時(shí)在數(shù)據(jù)集 中的取值 最大似然函數(shù)0 可以由下式得到 一券器 期望計(jì)算 E 步 是計(jì)算給定D 時(shí) 當(dāng)前0 的似然 函數(shù)期望 z 口I 伊 一 l n p D z 乃lO p X l B 擴(kuò)o 5 對(duì)于所有的0 應(yīng)滿足 l O I 升 l O l 根據(jù)式 3 有 z 8 伊o 一 f 疊 疤 l n 0 私 6 這里L(fēng) x I r i p x 鞏In 伊o 是通過(guò)平 滑推理機(jī)s m o o t h e r e n g i n e 推理而得 最大化 M 步 是通過(guò)最大化當(dāng)前期望似然函數(shù) 值 選擇下一個(gè)估計(jì) 件 口昝 a g rm a xE P Dl 口 ID 伊o S 一 毒墮車 7 i 廠 蠢 疵 7 式 6 和式 7 分別為E M 算法的期望計(jì)算和最大 化計(jì)算等式 3D A E M 算法 3 1 算法思想 傳統(tǒng)的E M 算法的巨大的時(shí)間復(fù)雜性主要體現(xiàn)在 E 步驟 6 中的期望充分統(tǒng)計(jì)因子工 z 礓 一 p x i l r iD l 儼 的計(jì)算上 算法只有遍歷整個(gè)數(shù) f 據(jù)集后 才能完成一次網(wǎng)絡(luò)參數(shù)的更新 不能快速利用 數(shù)據(jù)中所蘊(yùn)涵的信息 由此導(dǎo)致了似然函數(shù)和網(wǎng)絡(luò)參 數(shù)的更新頻率偏低 進(jìn)而使得算法的收斂速度慢 其所 需要的計(jì)算時(shí)間與數(shù)據(jù)集的數(shù)量成線性關(guān)系 D A E M 算法將數(shù)據(jù)集分塊 然后以塊為單位在數(shù)據(jù)塊之 間循環(huán)迭代 通過(guò)執(zhí)行部分E 步來(lái)減少期望充分統(tǒng)計(jì) 因子的計(jì)算量 從而減少算法計(jì)算強(qiáng)度 加快參數(shù)更新 的頻率和收斂速度 進(jìn)而提高整個(gè)算法的學(xué)習(xí)性能 增 強(qiáng)算法對(duì)時(shí)序數(shù)據(jù)的適應(yīng)能力 4 7 2儀器儀表學(xué)報(bào) 第2 8 卷 D A E M 算法必須解決兩個(gè)關(guān)鍵問(wèn)題 確定數(shù)據(jù)塊 的大小和算法收斂性的判別 3 1 1 數(shù)據(jù)塊的劃分 用y 奠 魏 斂 表示把數(shù)據(jù)集劃分為k 個(gè) 互不相交的數(shù)據(jù)塊的一個(gè)特定劃分 其中Y i 表示第i 個(gè)數(shù)據(jù)塊 D A E M 算法在塊間循環(huán)迭代 每一次迭代 執(zhí)行一個(gè)部分E 步 增量式地更新似然函數(shù)和網(wǎng)絡(luò)參 數(shù) 以縮短E 步執(zhí)行時(shí)間 數(shù)據(jù)塊的大小直接影響了D A E M 算法的執(zhí)行效 率 實(shí)驗(yàn)表明 隨著數(shù)據(jù)集合的變化 精確度和速度相 對(duì)最優(yōu)的數(shù)據(jù)塊的大小相對(duì)穩(wěn)定在一個(gè)區(qū)間 遺憾的 是目前為止還沒(méi)有標(biāo)準(zhǔn)的數(shù)據(jù)塊劃分方法m 本文 給出一個(gè)在實(shí)驗(yàn)中確定數(shù)據(jù)塊劃分方法 令s o 和s 為 兩個(gè)后驗(yàn)分布 分別表示初始化和首次遍歷數(shù)據(jù)塊后 似然函數(shù)的值 用t 表示從分布S O 到分布兩所用的 時(shí)間 通過(guò)執(zhí)行一個(gè)簡(jiǎn)單的搜索來(lái)確定速率r a t i o r a t i o 一 5 那么使得速率r a t i o 最大的所經(jīng)過(guò)的樣 本數(shù)目r 是最優(yōu)的數(shù)據(jù)塊內(nèi)所包含的樣本數(shù)目 3 1 2 算法收斂性判別 在傳統(tǒng)E M 算法中 由于似然函數(shù)值具有單調(diào)性 如果兩次迭代似然函數(shù)的差值小于既定的收斂閥值 則認(rèn)為算法是收斂的 但該方法不適用于D A E M 因 為在D J A E M 算法中 塊間迭代的似然函數(shù)值不滿足 單凋性 因此在本算法中采用一個(gè)近似方式表示似然 函數(shù) 即 L yI 伊o yI 伊o yJ 伊卜1 一L y iJ D L y I 伊 8 N e a l c 8 3 證明對(duì)于所有樣本n k L L 葉 成立 即在數(shù)據(jù)塊的兩次遍歷間的似然函數(shù)值仍然保持單調(diào) r d r t k 不減 因此當(dāng)C 一生1 扣小于收斂閥值s 時(shí) D A b E M 算法收斂 在本文中取S l e 一3 嘩 t t 一誓 岫 一 o 3 2D A E M 算法描述 算法的第n 1 次迭代如下所示 E 步 1 選擇數(shù)據(jù)塊Y i 1 2 k 2 計(jì)算概率 療 多 五 7 r 麓 f Y i 伊 Q 口 礦I Q 口 礦 1l Y J f o rj i 計(jì)算 Q 一 f 六 一瞬 z 弓 f o rj i 3 合并似然函數(shù) o 一 I 口 y Q j 伊 I 曰 Y M 步 更新Q 函數(shù) Q 毋l 礦 y 一Q 穢I 擴(kuò)1 了 Q 參 伊 為 一Q 穢 伊一 弘 選擇礦 1 使得最大化Q 口I 伊 y D A E M 算法中 部分E 步以增量方式構(gòu)造并最大 化似然函數(shù)期望 Q 函數(shù) 每一步迭代過(guò)程中 算法 只是更新Q 函數(shù)的一部分 即只更新當(dāng)前數(shù)據(jù)塊所形 成的似然函數(shù)期望 g 對(duì)于其他的數(shù)據(jù)塊 仍然沿用 上一次迭代中的Q 函數(shù)的值 因此 每次迭代Q 函數(shù) 只需加上當(dāng)前數(shù)據(jù)塊的新舊似然函數(shù)期望的差值 與 標(biāo)準(zhǔn)E M 算法相比 D A E M 算法增加了K 個(gè)存儲(chǔ)開(kāi) 銷 即增加了數(shù)據(jù)塊k 1 i 時(shí)的Q 函數(shù)的 存儲(chǔ) 4 實(shí)驗(yàn)結(jié)果和分析 4 1 實(shí)驗(yàn)環(huán)境和數(shù)據(jù) 本文的工作使用M A T L A B 版本為6 5 運(yùn)行環(huán)境 為操作系統(tǒng)W i n d o w sX P C P Up 41 6G H z 內(nèi)存2 5 6 M 硬盤8 0G 實(shí)驗(yàn)是在系統(tǒng)貝葉斯工具包B N T C 9 3 作者K e v i nM u r p h y 下進(jìn)行的 此軟件可在網(wǎng)上 下載 使用w a t e r 網(wǎng)絡(luò)作為測(cè)試網(wǎng)絡(luò) 該網(wǎng)絡(luò)每個(gè)時(shí)間 片1 2 個(gè)節(jié)點(diǎn) 4 條邊 轉(zhuǎn)移網(wǎng)絡(luò)2 2 條邊 分別用本文 提出的D A E M 算法與標(biāo)準(zhǔn)E M 算法對(duì)網(wǎng)絡(luò)進(jìn)行參數(shù) 學(xué)習(xí) 在學(xué)習(xí)精度和時(shí)間性能上 對(duì)兩個(gè)算法進(jìn)行比 較 利用概率邏輯抽樣算法按4 個(gè)證據(jù)變量和8 個(gè)狀 態(tài)變量分別產(chǎn)生9 個(gè)訓(xùn)練樣本集 分別包括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 個(gè)樣本 4 2 評(píng)價(jià)標(biāo)準(zhǔn) 采用參數(shù)學(xué)習(xí)算法從訓(xùn)練樣本中獲得的條件概率 密度為P 7 V I 丌 口 由于實(shí)際結(jié)點(diǎn)處的條件概率密度 P 7 V Iz r v 是已知的 于是作為結(jié)果的條件概率密度 與真實(shí)的條件概率密度之間的差別可以用來(lái)作為評(píng)價(jià) 參數(shù)學(xué)習(xí)結(jié)果的測(cè)度 這里采用K u l l b a c k L e i b l e r 距 離 1 0 進(jìn)行計(jì)算 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 當(dāng)P 7 y l7 r 口 與p V f 丌 口 越接近時(shí) K u l l b a c k L e i b l e r 距離越小 說(shuō)明參數(shù) 第8 期增刊莫富強(qiáng)等 動(dòng)態(tài)貝葉斯網(wǎng)絡(luò)參數(shù)學(xué)習(xí)算法的一種加速 4 7 3 學(xué)習(xí)的結(jié)果越精確 4 3 實(shí)驗(yàn)結(jié)果分析 采用D A E M 算法與標(biāo)準(zhǔn)的E M 算法對(duì)w a t e r 網(wǎng) 絡(luò)參數(shù)學(xué)習(xí)的K L 距離如圖2 所示 樣本大小 x 1 0 4 圖2 兩種算法學(xué)習(xí)的K L 距離 圖2 中 橫坐標(biāo)表示訓(xùn)練樣本集的大小 所含樣本 的數(shù)目 縱坐標(biāo)表示參數(shù)學(xué)習(xí)結(jié)果與真實(shí)值之間的 K L 距離 從圖可以清楚地看出 對(duì)于相同的訓(xùn)練樣本 集 當(dāng)訓(xùn)練樣本集較小時(shí) 改進(jìn)的E M 算法所得參數(shù)學(xué) 習(xí)結(jié)果與標(biāo)準(zhǔn)E M 算法所得結(jié)果略有差距 但隨著樣 本集的增大 兩種算法所得參數(shù)結(jié)果無(wú)限趨近 這說(shuō) 明改進(jìn)后的算法能夠保證網(wǎng)絡(luò)的精度要求 表1 算法所耗用的C P U 時(shí)間 S 圖3 中 橫坐標(biāo)表示訓(xùn)練樣本集的大小 所含樣本 的數(shù)目 縱坐標(biāo)表示算法所耗用的時(shí)間 從圖3 和表 1 2 中可看出 改進(jìn)后的算法在速度上明顯優(yōu)于原算 法 而且隨著樣本集的增大 這種優(yōu)勢(shì)越來(lái)越明顯 函 f 么 樣本大小 x 1 0 4 圖3 兩種算法學(xué)習(xí)速度比較 5 結(jié)論 E M 算法是動(dòng)態(tài)貝葉斯網(wǎng)絡(luò)參數(shù)學(xué)習(xí)的一種主要 方法 本文通過(guò)將大規(guī)模時(shí)序數(shù)據(jù)集劃分為較小的數(shù) 據(jù)塊 并通過(guò)塊間的循環(huán)迭代 增量式地更新似然函數(shù) 和網(wǎng)絡(luò)參數(shù) 對(duì)傳統(tǒng)的E M 算法進(jìn)行了改進(jìn) 實(shí)驗(yàn)表 明改進(jìn)的D A E M 算法在保證結(jié)果精度的前提下 在 時(shí)間性能上有較大的改進(jìn) 參考文獻(xiàn) 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