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

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

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

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

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