基于分治策略的貝葉斯網學習方法及在圖像分割中的應用

段宏英　姜威　于帥

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

[關鍵詞]貝葉斯網；圖像分割；分治算法

1 引言

隨著大數據時代的到來，人類所獲得的數據往往存在海量、高維等特點。貝葉斯網學習是NP問題，其計算量隨貝葉斯網變量數目的增加呈指數級增長。雖然面向常規數據的貝葉斯網學習技術已取得很大進展，但當用于學習的數據維度很高、即目標貝葉斯網的變量數目龐大時，貝葉斯網學習算法的計算復雜度很高，學習十分困難，如何從高維數據中高效的學習貝葉斯網是一個挑戰性問題。

為此，本文提出針對高維數據的復雜貝葉斯網的高效學習新思路，并給出將研究結果應用于圖像分割領域的實施方案。

2 基于分治策略的高維貝葉斯網學習思路

基于“分而治之”的思想，研究對高維數據的變量進行高效分組的新方法，使每組內部的變量有著極強的依賴關系，而各個組之間的關聯關系較弱。進而可獨立分別學習各組結點對應的單元貝葉斯網，最后將學得的各單元貝葉斯網合并以得到最終貝葉斯網。

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

按下面原則對結點進行分組：如果一個結點集U中的結點可能是另一結點集V中結點的祖先，但V中結點并不可能是U中結點的祖先，即這兩個集合間不存在環（各自集合內可以存在環），則將這兩個結點集分進不同的組。一個例子如圖1所示。圖1中將結點分為4組，每組結點間不存在環，組內存在環。這意味著每組內部的結點有著極強的依賴關系，而各個組之間的關聯關系較弱。

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

獨立學習按上述策略得到的各組結點對應的貝葉斯網，一共分為n組，則學得n個貝葉斯網，我們稱之為單元貝葉斯網，最后將這n個單元貝葉斯網的重復結點合并，即可得到最終的貝葉斯網。研究控制分組數目的方法，如當上圖中有向邊很稠密時，利用結點與其父結點的互信息，對邊進行精簡，以增加分組數目。

3 基于貝葉斯網的高效圖像分割策略

針對當前圖像分割基于多分辨率算法中低分辨率圖像的優點全局性強利用不夠充分，可使用貝葉斯網在不同分辨率之間信息傳遞來消除或減少圖像分割中由于受到噪點等而產生的過分割現象。針對多分辨率圖像輔助決策方法存在各級分辨率的決策結果效果不一的問題，可使用信息融合算法合理總和這些結果進行決策，使最終邊界認定更準確。整體流程如圖3所示。

4 結束語

針對高維復雜數據下貝葉斯網學習問題，本文給出了基于分治算法的高維貝葉斯網學習新思路，并給出了其在圖像分割領域中的應用策略，對拓展貝葉斯網的理論與應用具有重要意義。