基于團分劃改進的IPS算法.pdf

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

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

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

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

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

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

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