本文關(guān)鍵詞：基于團(tuán)分劃改進(jìn)的IPS算法，由筆耕文化傳播整理發(fā)布。

【摘要】：圖模型用圖直觀地、清晰地表達(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首次提出之后,陸續(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)系,這樣即使圖結(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)有利用圖的結(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ì)算效率,本文稱(chēng)之為UPSP-JT算法。然后,本文模擬比較了IPS、IPSP、UPS-JT、UPSP-JT這幾種算法的算法效率,我們發(fā)現(xiàn)使用連接樹(shù)的UPS-JT算法和UPSP-JT算法優(yōu)于沒(méi)使用連接樹(shù)的IPS算法和IPSP算法,并且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ù)情形下圖模型的模型選擇問(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é)果和算法(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ù)情形下圖模型的模型選擇的模擬研究。第五章中,給出了全文總結(jié),并且展望了在貝葉斯估計(jì)中,IPS算法基于局部計(jì)算策略的改進(jìn)。
【關(guān)鍵詞】：圖模型 IPS算法 局部計(jì)算 團(tuán)分劃 E-MS算法
【學(xué)位授予單位】：長(zhǎng)春工業(yè)大學(xué)
【學(xué)位級(jí)別】：碩士
【學(xué)位授予年份】：2016
【分類(lèi)號(hào)】：O212.1;F224
【目錄】：

• 摘要3-5
• Abstract5-8
• 第一章 緒論8-12
• 1.1 研究背景8
• 1.2 圖模型的分類(lèi)及研究方向8-9
• 1.3 IPS算法發(fā)展的歷史和現(xiàn)狀9-10
• 1.4 本文的一些工作10
• 1.5 文章的組織結(jié)構(gòu)10-12
• 第二章 預(yù)備知識(shí)及記號(hào)12-15
• 2.1 圖的相關(guān)概念及圖分解12-13
• 2.2 馬爾科夫性及圖模型13-15
• 第三章 基于團(tuán)分劃改進(jìn)IPS算法15-26
• 3.1 多項(xiàng)分布圖模型及IPS算法簡(jiǎn)介15-17
• 3.1.1 列聯(lián)表15-16
• 3.1.2 極大似然估計(jì)的IPS算法16-17
• 3.2 基于團(tuán)分劃改進(jìn)的IPS算法17-20
• 3.2.1 基于團(tuán)分劃的局部計(jì)算的理論17-18
• 3.2.2 基于團(tuán)分劃的IPSP算法18-20
• 3.3 團(tuán)集的近似最優(yōu)分劃20-22
• 3.4 n元圈圖模型的最優(yōu)分劃22-23
• 3.5 基于團(tuán)分劃改進(jìn)UPS-JT算法及模擬比較23-26
• 3.5.1 UPS-JT算法簡(jiǎn)介及基于團(tuán)分劃的改進(jìn)23-24
• 3.5.2 算法效率的模擬比較24-26
• 第四章E-MS算法在不完全數(shù)據(jù)圖模型選擇中的模擬研究26-29
• 4.1 E-MS算法及復(fù)雜度分析26-27
• 4.2 模擬研究27-29
• 第五章 結(jié)論29-31
• 致謝31-32
• 參考文獻(xiàn)32-35
• 作者簡(jiǎn)介35
• 攻讀碩士學(xué)位期間研究成果35

【相似文獻(xiàn)】

中國(guó)碩士學(xué)位論文全文數(shù)據(jù)庫(kù) 前1條

1 孫聚波;基于團(tuán)分劃改進(jìn)的IPS算法[D];長(zhǎng)春工業(yè)大學(xué);2016年

  本文關(guān)鍵詞：基于團(tuán)分劃改進(jìn)的IPS算法，，由筆耕文化傳播整理發(fā)布。

本文編號(hào)：486397