基于分解的圖模型研究.pdf

1、圖模型是圖論、概率論,統(tǒng)計學等的交叉領域。圖模型利用圖這一比較直觀的工具能夠清晰地表示問題的背景知識及變量間的結構關系,是處理高維問題的有力工具。它廣泛的應用于生物信息學、機器學習、決策論等各個領域。
　　 近些年來,許多學者都利用圖模型處理涉及成千上萬個變量的高維、復雜問題。處理這些問題的十分有效的工具之一是圖分解。利用圖分解可以將這些高維問題化簡為類似的含有較少變量的低維問題,進而提高解決問題的功效。例如,對圖模型的估計、檢

2、驗等統(tǒng)計推斷都可分解為其素塊上的邊緣模型上進行推斷。
　　 本文基于圖分解對圖模型做了進一步研究,包括以下四個方面的工作。第一,基于MCS—M算法改進了Leimer的圖分解算法,無論理論復雜度分析還是模擬實驗結果都顯示新的圖分解算法比Leimer的圖分解算法要略快一些,并且能快速的分解至少含有上萬個頂點的圖模型。第二,基于圖分解改進了概率圖模型的概率傳播算法,提高了概率推斷的效率。我們把概率傳播算法中至關重要的步驟,即求最優(yōu)三角

3、化圖問題(NP-hard),分解成各個小的子圖上的最優(yōu)三角化圖問題,這樣使問題的難度得到大大的降低。進一步給出了基于分解的構建團樹的算法。我們的模擬結果顯示,分解不僅可大大提高尋找最優(yōu)三角化圖和建立團樹的速度,還可得到更高質量的三角化圖。第三,考慮求高斯圖模型極大似然估計,我們利用概率傳播算法共享計算的思想,給出了改進的迭代比例擬合算法(IPSprocedure)和改進的HT算法,并給出了復雜度分析和模擬實驗,兩者均顯示,我們的改進算法

4、大大降低了傳統(tǒng)的迭代比例擬合算法的復雜度,提高了運行速度。第四,我們考慮從道義圖出發(fā)進行Bayes網(wǎng)結構學習.給出了道義圖中道義邊的更精細的刻畫,指出道義邊(α,β)相應的分離子是道義圖中包含α,β的某素塊中α或β的鄰居集的完全子集,這樣便可大大降低搜索分離子的范圍,減少條件獨立檢驗的次數(shù)。進一步提出了結構Structure-Finder(SF)算法基于圖分解進行結構學習,并證明了SF算法的復雜度比Ic算法和Geng等人的方法小得多。同