基于團(tuán)分劃改進(jìn)的IPS算法.pdf

1、圖模型用圖直觀地、清晰地表達(dá)變量間的結(jié)構(gòu)關(guān)系，并將復(fù)雜的大型全局問(wèn)題分解為相對(duì)簡(jiǎn)單局部問(wèn)題，這樣不僅極大地減少推理計(jì)算時(shí)的計(jì)算量，而且也將提高推理的功效。在圖模型的各種推理計(jì)算中，參數(shù)估計(jì)和模型選擇是最核心的兩個(gè)問(wèn)題。本文將研究完全數(shù)據(jù)時(shí)的極大似然估計(jì)和不完全數(shù)據(jù)情形下的模型選擇。
　　圖模型的極大似然估計(jì)一般采用迭代比例擬合（IPS）算法。由于IPS算法的穩(wěn)定性和易于執(zhí)行性，自從Deming and Stephan首次提出之后，

2、陸續(xù)有許多學(xué)者從幾何解釋、收斂性、空間復(fù)雜度、時(shí)間復(fù)雜度等許多方面進(jìn)行了深入研究和改進(jìn)。然而，許多實(shí)際問(wèn)題往往結(jié)構(gòu)復(fù)雜、涉及的變量眾多，此時(shí)IPS算法復(fù)雜度較高。
　　本文從計(jì)算局部化的角度對(duì)IPS算法作了進(jìn)一步研究。受Xu等人發(fā)表在JCGS的關(guān)于高斯圖模型中利用團(tuán)分劃進(jìn)行局部計(jì)算的啟發(fā)，我們給出了在多項(xiàng)分布圖模型中基于團(tuán)分劃進(jìn)行局部計(jì)算的理論。由構(gòu)成該理論的2個(gè)定理知，基于團(tuán)分劃的局部計(jì)算沒(méi)有利用變量間的條件獨(dú)立關(guān)系，這樣即使圖

3、結(jié)構(gòu)非常復(fù)雜，團(tuán)分劃策略仍然有效，這是前輩學(xué)者的諸多算法所不具備的優(yōu)點(diǎn)。進(jìn)一步，提出了基于團(tuán)分劃進(jìn)行局部計(jì)算的算法，即IPSP算法。在該算法中，先將團(tuán)集分劃為幾個(gè)非重疊和非空的塊，然后在每個(gè)塊中局部地、逐次地調(diào)整團(tuán)邊緣。找到使IPSP算法勝過(guò)IPS算法的團(tuán)分劃不難，但是整體最優(yōu)的分劃是很難確定地找到。本文采用模擬退火（SA）算法來(lái)尋找到一個(gè)近似最優(yōu)分劃。此外，我們還證明了n元圈圖模型的最優(yōu)分劃為連續(xù)二等分劃。由于團(tuán)分劃的策略沒(méi)有利用圖的

4、結(jié)構(gòu)和模型的條件獨(dú)立關(guān)系，而Teh and Welling提出的UPS-JT算法中利用連接樹(shù)進(jìn)行局部計(jì)算的策略不具備此特性，因此團(tuán)分劃能提高UPS-JT算法中的擬合步的計(jì)算速度，進(jìn)而提高UPS-JT算法的整體計(jì)算效率，本文稱之為UPSP-JT算法。然后，本文模擬比較了IPS、IPSP、UPS-JT、UPSP-JT這幾種算法的算法效率，我們發(fā)現(xiàn)使用連接樹(shù)的UPS-JT算法和UPSP-JT算法優(yōu)于沒(méi)使用連接樹(shù)的IPS算法和IPSP算法，并且

5、IPSP算法和UPSP-JT算法運(yùn)行的分別比IPS算法和UPS-JT算法更快，所以基于團(tuán)分劃的局部計(jì)算能有效地提高計(jì)算效率。
　　含不完全數(shù)據(jù)的模型選擇問(wèn)題，傳統(tǒng)的方法是先在備選模型下求極大似然估計(jì)，而后采用信息準(zhǔn)則（例如BIC等）選擇模型。但Jiang等人的JASA論文指出，傳統(tǒng)的方法可能不會(huì)收斂，甚至可能選錯(cuò)模型，并提出了在一定條件下具有收斂性的E-MS算法。本文將利用Jiang等人提出的E-MS算法，考慮不完全數(shù)據(jù)情形下圖模

6、型的模型選擇問(wèn)題。但由于E-MS其嵌套計(jì)算的特性，計(jì)算量隨變量個(gè)數(shù)的增加迅速的增大，因而本文在最大化Q函數(shù)中將采用IPSP算法提高計(jì)算速度，同時(shí)進(jìn)行了模擬研究。
　　本文結(jié)構(gòu)安排如下。第一章中，簡(jiǎn)要介紹了研究背景和IPS算法發(fā)展的歷史和現(xiàn)狀，以及本文的組織結(jié)構(gòu)安排。第二章中，簡(jiǎn)要介紹了一些預(yù)備知識(shí)，即圖模型的一些定義、概念和記號(hào)。第三章中，首先簡(jiǎn)介了屬性數(shù)據(jù)的列聯(lián)表和經(jīng)典的IPS算法。其次給出了基于團(tuán)分劃進(jìn)行局部計(jì)算的理論結(jié)果和算

7、法（IPSP算法），以及利用模擬退火算法求團(tuán)集的近似最優(yōu)分劃中進(jìn)行MH抽樣的算法（MHDP算法），并證明了圖模型的一種基礎(chǔ)結(jié)構(gòu)n元圈的最優(yōu)分劃為連續(xù)二等分劃。然后利用團(tuán)分劃策略改進(jìn)了UPS-JT算法，并通過(guò)模擬實(shí)驗(yàn)比較了IPS、IPSP、UPS-JT和UPSP-JT這四種算法的計(jì)算效率。第四章中，簡(jiǎn)介了不完全數(shù)據(jù)情形下模型選擇的較新理論成果，即E-MS算法，并分析了其復(fù)雜度，同時(shí)還進(jìn)行了不完全數(shù)據(jù)情形下圖模型的模型選擇的模擬研究。第五章