【摘要】：鏈圖作為一種圖模型,是在上世紀八十年代中期被引入的,用來描述條件獨立結構.鏈圖是一類更加廣泛的圖模型,它不僅包括無向圖(通常被稱為馬爾可夫網(wǎng)絡),還包括有向無環(huán)圖(通常被稱為貝葉斯網(wǎng)絡),而且鏈圖并不僅僅局限于這兩類.然而,過去經(jīng)常被用來表示概率的條件獨立結構的卻是無向圖和有向無環(huán)圖這兩類更為特殊的圖模型,鏈圖模型并沒有得到廣泛的關注.不過,隨著人們對鏈圖更加深入的了解,越來越多的研究者對鏈圖產(chǎn)生了濃厚的興趣,并且鏈圖將繼續(xù)成為一個令人感興趣的研究領域.在關于圖模型的諸多研究中,結構學習引起了大量討論,對于鏈圖也不例外.目前主要有兩類結構學習的方法：一類是基于約束的方法,一類是基于得分的方法.Lauritzen總結了在上個世紀關于結構學習的最重要的研究,但是大部分研究結果是關于無向圖和有向無環(huán)圖的.就我所知,鏈圖的結構學習算法卻少之又少,我認為這也是鏈圖沒有得到廣泛應用的一個重要原因.因此,我在本文提出鏈圖模型的一個新的結構學習算法.本文主要提出兩個算法,一個是尋找鏈圖中所有節(jié)點的馬氏毯的算法,一個是基于馬氏毯進行鏈圖結構學習的算法.馬氏毯是這樣一個節(jié)點集：在忠實性假定下,給定一個節(jié)點的馬氏毯后,這個節(jié)點就與其他節(jié)點條件獨立.馬氏毯可以用來進行因果還原,特征集選擇以及鏈圖的結構學習.我們的第一個算法就是為了進行馬氏毯的還原,它是基于目標節(jié)點的邊界和兒子直接從訓練集中還原馬氏毯,而不用先學習鏈圖的整個結構.這樣就為第二個算法做好了基礎.在第二個算法中,我們首先通過移除偽邊還原鏈圖的骨架,然后確定復型的方向,最后通過迭代應用三個特殊規(guī)則得到相應的最大鏈圖.這個算法是一個更加有效率的算法,因為我們只需要在目標節(jié)點和它的馬氏毯成員之間進行條件獨立檢驗即可.我們在忠實性假定下對兩個算法的正確性進行討論,并給出例子演示算法的運行過程.
[Abstract]:As a graph model, chain graph was introduced in the mid-1980s to describe conditional independent structure. Chain graph is a kind of more extensive graph model, which includes not only undirected graph (usually called Markov network), but also directed acyclic graph (usually called Bayesian network), and chain graph is not limited to these two classes. However, in the past, the conditional independent structures used to represent probability are two more special graph models, namely, undirected graph and directed acyclic graph, and the chain graph model has not been paid much attention. However, with the deeper understanding of chain graph, more and more researchers are interested in chain graph, and chain graph will continue to be an interesting research field. In many studies on graph model, structural learning has caused a lot of discussion, and chain graph is no exception. At present, there are two main methods of structural learning: one is constraint-based method, the other is score-based method. Lauritzen summarized the most important research on structural learning in the last century. But most of the results are about undirected graphs and directed acyclic graphs. As far as I know, there are few structural learning algorithms for chain graphs, which I think is one of the important reasons why chain graphs are not widely used. Therefore, I propose a new structure learning algorithm for chain graph model in this paper. In this paper, two algorithms are proposed, one is to find the Markov blanket of all nodes in the chain graph, and the other is to learn the structure of the chain graph based on the Markov carpet. Markov blanket is a set of nodes: given the Markov blanket of one node, the node is independent of other node conditions under the assumption of fidelity. Markov blankets can be used for causal reduction, feature set selection, and chain graph structure learning. Our first algorithm is to restore the Markov carpet, which is based on the boundary of the target node and the son directly from the training set without having to learn the whole structure of the chain graph. This lays the foundation for the second algorithm. In the second algorithm, we first remove the skeleton of the pseudo-edge reduction chain graph, then determine the direction of the complex type. Finally, we obtain the corresponding maximum chain graph by iterative application of three special rules. This algorithm is a more efficient algorithm because we only need to perform conditional independent test between the target node and its Markov carpet members. Under the assumption of fidelity, we discuss the correctness of the two algorithms, and give an example to demonstrate the running process of the algorithm.
【學位授予單位】：山東師范大學
【學位級別】：碩士
【學位授予年份】：2015
【分類號】：O157.5;TP301.6

【相似文獻】

相關期刊論文 前10條

1 單而芳，竇榮啟，康麗英;φ－容忍鏈圖與樹[J];河北大學學報(自然科學版);1996年02期

2 蘇敏邦,錢建國;多邊形鏈圖中的完美匹配數(shù)(英文)[J];數(shù)學研究;2000年01期

3 劉佰軍,鄭忠國,趙慧;根據(jù)已知鏈圖找出最大鏈圖的有效的算法[J];中國科學(A輯:數(shù)學);2005年10期

4 柳柏濂;關于二連通唯一最短鏈圖[J];華中師范大學學報(自然科學版);1986年01期

5 陳儀朝;;項鏈圖在曲面上的嵌入[J];數(shù)學學報;2012年01期

6 盧建立;馬美琳;任鳳霞;;一類新鏈圖的優(yōu)美性[J];河北師范大學學報(自然科學版);2012年04期

7 任秋萍;顧娟;;利用多項式不變量α_K對內(nèi)在3-鏈圖中紐結分支的研究[J];齊齊哈爾大學學報(自然科學版);2013年02期

8 任秋萍;;帶有紐結分支的內(nèi)在鏈圖和內(nèi)在紐結與3-鏈圖[J];黑龍江科技學院學報;2007年04期

9 任秋萍;王光輝;;一種帶有紐結分支的內(nèi)在鏈圖[J];佳木斯大學學報(自然科學版);2009年05期

10 任秋萍;王光輝;;一類帶有紐結分支的內(nèi)在鏈圖[J];科技導報;2009年22期

相關博士學位論文 前2條

1 孟憲勇;圖模型基礎理論研究[D];東北師范大學;2012年

2 陳學文;WS中γ，，Z_0，W~±混合圈鏈圖傳播子的解析計算及其在粒子反應中的應用[D];重慶大學;2012年

相關碩士學位論文 前8條

1 蔡倩;基于馬氏毯的鏈圖模型結構學習[D];山東師范大學;2015年

2 襲慶;鏈圖的可壓縮性[D];山東師范大學;2015年

3 任秋萍;內(nèi)在鏈圖和內(nèi)在紐結圖[D];哈爾濱工業(yè)大學;2006年

4 羅盼盼;鏈圖模型的結構學習研究[D];山東師范大學;2014年

5 李顯勇;一些圖的Hosoya多項式分解與拓撲指標[D];新疆師范大學;2010年

6 田靜;在光子重整化混合圈鏈圖傳播下的高能電子對碰撞生成重輕子對的微分截面[D];重慶大學;2010年

7 史成業(yè);在電弱統(tǒng)一標準模型中研究Bhabha散射截面的重整化圈鏈圖效應[D];重慶大學;2013年

8 潘宇;精確計算中子—反中子重整化鏈圖傳播下中子—反中子湮沒產(chǎn)生雙中性介子反應截面[D];重慶大學;2008年

本文編號：2450093