【摘要】：鏈圖作為一種圖模型,是在上世紀(jì)八十年代中期被引入的,用來(lái)描述條件獨(dú)立結(jié)構(gòu).鏈圖是一類更加廣泛的圖模型,它不僅包括無(wú)向圖(通常被稱為馬爾可夫網(wǎng)絡(luò)),還包括有向無(wú)環(huán)圖(通常被稱為貝葉斯網(wǎng)絡(luò)),而且鏈圖并不僅僅局限于這兩類.然而,過去經(jīng)常被用來(lái)表示概率的條件獨(dú)立結(jié)構(gòu)的卻是無(wú)向圖和有向無(wú)環(huán)圖這兩類更為特殊的圖模型,鏈圖模型并沒有得到廣泛的關(guān)注.不過,隨著人們對(duì)鏈圖更加深入的了解,越來(lái)越多的研究者對(duì)鏈圖產(chǎn)生了濃厚的興趣,并且鏈圖將繼續(xù)成為一個(gè)令人感興趣的研究領(lǐng)域.在關(guān)于圖模型的諸多研究中,結(jié)構(gòu)學(xué)習(xí)引起了大量討論,對(duì)于鏈圖也不例外.目前主要有兩類結(jié)構(gòu)學(xué)習(xí)的方法：一類是基于約束的方法,一類是基于得分的方法.Lauritzen總結(jié)了在上個(gè)世紀(jì)關(guān)于結(jié)構(gòu)學(xué)習(xí)的最重要的研究,但是大部分研究結(jié)果是關(guān)于無(wú)向圖和有向無(wú)環(huán)圖的.就我所知,鏈圖的結(jié)構(gòu)學(xué)習(xí)算法卻少之又少,我認(rèn)為這也是鏈圖沒有得到廣泛應(yīng)用的一個(gè)重要原因.因此,我在本文提出鏈圖模型的一個(gè)新的結(jié)構(gòu)學(xué)習(xí)算法.本文主要提出兩個(gè)算法,一個(gè)是尋找鏈圖中所有節(jié)點(diǎn)的馬氏毯的算法,一個(gè)是基于馬氏毯進(jìn)行鏈圖結(jié)構(gòu)學(xué)習(xí)的算法.馬氏毯是這樣一個(gè)節(jié)點(diǎn)集：在忠實(shí)性假定下,給定一個(gè)節(jié)點(diǎn)的馬氏毯后,這個(gè)節(jié)點(diǎn)就與其他節(jié)點(diǎn)條件獨(dú)立.馬氏毯可以用來(lái)進(jìn)行因果還原,特征集選擇以及鏈圖的結(jié)構(gòu)學(xué)習(xí).我們的第一個(gè)算法就是為了進(jìn)行馬氏毯的還原,它是基于目標(biāo)節(jié)點(diǎn)的邊界和兒子直接從訓(xùn)練集中還原馬氏毯,而不用先學(xué)習(xí)鏈圖的整個(gè)結(jié)構(gòu).這樣就為第二個(gè)算法做好了基礎(chǔ).在第二個(gè)算法中,我們首先通過移除偽邊還原鏈圖的骨架,然后確定復(fù)型的方向,最后通過迭代應(yīng)用三個(gè)特殊規(guī)則得到相應(yīng)的最大鏈圖.這個(gè)算法是一個(gè)更加有效率的算法,因?yàn)槲覀冎恍枰谀繕?biāo)節(jié)點(diǎn)和它的馬氏毯成員之間進(jìn)行條件獨(dú)立檢驗(yàn)即可.我們?cè)谥覍?shí)性假定下對(duì)兩個(gè)算法的正確性進(jìn)行討論,并給出例子演示算法的運(yùn)行過程.
[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.
【學(xué)位授予單位】：山東師范大學(xué)
【學(xué)位級(jí)別】：碩士
【學(xué)位授予年份】：2015
【分類號(hào)】：O157.5;TP301.6

【相似文獻(xiàn)】

相關(guān)期刊論文 前10條

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

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

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

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

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

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

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

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

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

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

相關(guān)博士學(xué)位論文 前2條

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

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

相關(guān)碩士學(xué)位論文 前8條

1 蔡倩;基于馬氏毯的鏈圖模型結(jié)構(gòu)學(xué)習(xí)[D];山東師范大學(xué);2015年

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

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

4 羅盼盼;鏈圖模型的結(jié)構(gòu)學(xué)習(xí)研究[D];山東師范大學(xué);2014年

5 李顯勇;一些圖的Hosoya多項(xiàng)式分解與拓?fù)渲笜?biāo)[D];新疆師范大學(xué);2010年

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

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

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

本文編號(hào)：2450093