段宏英　姜威　于帥

[摘要]貝葉斯網(wǎng)將概率論和圖論相結(jié)合，是一種描述隨機(jī)變量間依賴關(guān)系，并能緊湊高效的表示聯(lián)合概率分布的概率圖模型，近年來已成為人工智能理論中處理不確定性問題的重要工具，面向大數(shù)據(jù)的貝葉斯網(wǎng)學(xué)習(xí)方法一個(gè)重要問題。論文給出了基于分治算法的高維貝葉斯網(wǎng)學(xué)習(xí)新思路，并給出了其在圖像分割領(lǐng)域中的應(yīng)用策略。

[關(guān)鍵詞]貝葉斯網(wǎng)；圖像分割；分治算法

1 引言

隨著大數(shù)據(jù)時(shí)代的到來，人類所獲得的數(shù)據(jù)往往存在海量、高維等特點(diǎn)。貝葉斯網(wǎng)學(xué)習(xí)是NP問題，其計(jì)算量隨貝葉斯網(wǎng)變量數(shù)目的增加呈指數(shù)級(jí)增長。雖然面向常規(guī)數(shù)據(jù)的貝葉斯網(wǎng)學(xué)習(xí)技術(shù)已取得很大進(jìn)展，但當(dāng)用于學(xué)習(xí)的數(shù)據(jù)維度很高、即目標(biāo)貝葉斯網(wǎng)的變量數(shù)目龐大時(shí)，貝葉斯網(wǎng)學(xué)習(xí)算法的計(jì)算復(fù)雜度很高，學(xué)習(xí)十分困難，如何從高維數(shù)據(jù)中高效的學(xué)習(xí)貝葉斯網(wǎng)是一個(gè)挑戰(zhàn)性問題。

為此，本文提出針對(duì)高維數(shù)據(jù)的復(fù)雜貝葉斯網(wǎng)的高效學(xué)習(xí)新思路，并給出將研究結(jié)果應(yīng)用于圖像分割領(lǐng)域的實(shí)施方案。

2 基于分治策略的高維貝葉斯網(wǎng)學(xué)習(xí)思路

基于“分而治之”的思想，研究對(duì)高維數(shù)據(jù)的變量進(jìn)行高效分組的新方法，使每組內(nèi)部的變量有著極強(qiáng)的依賴關(guān)系，而各個(gè)組之間的關(guān)聯(lián)關(guān)系較弱。進(jìn)而可獨(dú)立分別學(xué)習(xí)各組結(jié)點(diǎn)對(duì)應(yīng)的單元貝葉斯網(wǎng)，最后將學(xué)得的各單元貝葉斯網(wǎng)合并以得到最終貝葉斯網(wǎng)。

首先使用已有研究成果從數(shù)據(jù)中求得貝葉斯網(wǎng)中每個(gè)變量的可能父結(jié)點(diǎn)集合，并對(duì)每個(gè)變量可能的父結(jié)點(diǎn)排序（比如基于條件互信息的值排序）；然后基于上述結(jié)果，借鑒前人提出的“父結(jié)點(diǎn)關(guān)系圖”的思想，生成一個(gè)有向有環(huán)的草圖，將可能存在父子結(jié)點(diǎn)關(guān)系結(jié)點(diǎn)對(duì)都用有向邊連接，該圖并不是真正的貝葉斯網(wǎng)。只是最大程度反映貝葉斯網(wǎng)結(jié)點(diǎn)間可能的父子關(guān)系，可能存在眾多環(huán)結(jié)構(gòu)，X可能是Y的父結(jié)點(diǎn)、Y也可能是X的父結(jié)點(diǎn)。

按下面原則對(duì)結(jié)點(diǎn)進(jìn)行分組：如果一個(gè)結(jié)點(diǎn)集U中的結(jié)點(diǎn)可能是另一結(jié)點(diǎn)集V中結(jié)點(diǎn)的祖先，但V中結(jié)點(diǎn)并不可能是U中結(jié)點(diǎn)的祖先，即這兩個(gè)集合間不存在環(huán)（各自集合內(nèi)可以存在環(huán)），則將這兩個(gè)結(jié)點(diǎn)集分進(jìn)不同的組。一個(gè)例子如圖1所示。圖1中將結(jié)點(diǎn)分為4組，每組結(jié)點(diǎn)間不存在環(huán)，組內(nèi)存在環(huán)。這意味著每組內(nèi)部的結(jié)點(diǎn)有著極強(qiáng)的依賴關(guān)系，而各個(gè)組之間的關(guān)聯(lián)關(guān)系較弱。

基于“分而治之”的思想，獨(dú)立處理每組結(jié)點(diǎn)集合，可大幅提高貝葉斯網(wǎng)學(xué)習(xí)效率。研究處理組間連接的方法，即每組結(jié)點(diǎn)對(duì)應(yīng)的小貝葉斯網(wǎng)學(xué)完之后如何合并成最終的貝葉斯網(wǎng)。例如對(duì)于圖1，X₄可能是X₂的父結(jié)點(diǎn)，如果只是單獨(dú)學(xué)習(xí)結(jié)點(diǎn)集（X₁，X₂，X₃）對(duì)應(yīng)的貝葉斯網(wǎng)，則學(xué)習(xí)完之后就較難和其他組結(jié)點(diǎn)集對(duì)應(yīng)的貝葉斯網(wǎng)合并。我們試采用如下策略：第一組結(jié)點(diǎn)結(jié)點(diǎn)集（X₁，X₂，X₃）的學(xué)習(xí)考慮將X₄作為X₂的可能父結(jié)點(diǎn)之一，但不學(xué)習(xí)X的父結(jié)點(diǎn)，X₄的父結(jié)點(diǎn)放在第二組中學(xué)習(xí)。即針對(duì)每組結(jié)點(diǎn)集的學(xué)習(xí)過程中，也考慮在其他組中的可能父結(jié)點(diǎn)。這樣，最終將圖1分為下面的4組結(jié)點(diǎn)集，可分別獨(dú)立學(xué)習(xí)這4組結(jié)點(diǎn)對(duì)應(yīng)的貝葉斯網(wǎng)，如圖2所示。

獨(dú)立學(xué)習(xí)按上述策略得到的各組結(jié)點(diǎn)對(duì)應(yīng)的貝葉斯網(wǎng)，一共分為n組，則學(xué)得n個(gè)貝葉斯網(wǎng)，我們稱之為單元貝葉斯網(wǎng)，最后將這n個(gè)單元貝葉斯網(wǎng)的重復(fù)結(jié)點(diǎn)合并，即可得到最終的貝葉斯網(wǎng)。研究控制分組數(shù)目的方法，如當(dāng)上圖中有向邊很稠密時(shí)，利用結(jié)點(diǎn)與其父結(jié)點(diǎn)的互信息，對(duì)邊進(jìn)行精簡，以增加分組數(shù)目。

3 基于貝葉斯網(wǎng)的高效圖像分割策略

針對(duì)當(dāng)前圖像分割基于多分辨率算法中低分辨率圖像的優(yōu)點(diǎn)全局性強(qiáng)利用不夠充分，可使用貝葉斯網(wǎng)在不同分辨率之間信息傳遞來消除或減少圖像分割中由于受到噪點(diǎn)等而產(chǎn)生的過分割現(xiàn)象。針對(duì)多分辨率圖像輔助決策方法存在各級(jí)分辨率的決策結(jié)果效果不一的問題，可使用信息融合算法合理總和這些結(jié)果進(jìn)行決策，使最終邊界認(rèn)定更準(zhǔn)確。整體流程如圖3所示。

4 結(jié)束語

針對(duì)高維復(fù)雜數(shù)據(jù)下貝葉斯網(wǎng)學(xué)習(xí)問題，本文給出了基于分治算法的高維貝葉斯網(wǎng)學(xué)習(xí)新思路，并給出了其在圖像分割領(lǐng)域中的應(yīng)用策略，對(duì)拓展貝葉斯網(wǎng)的理論與應(yīng)用具有重要意義。