基于马氏毯的链图模型结构学习

发布时间：2019-03-30 12:48

【摘要】：链图作为一种图模型,是在上世纪八十年代中期被引入的,用来描述条件独立结构.链图是一类更加广泛的图模型,它不仅包括无向图(通常被称为马尔可夫网络),还包括有向无环图(通常被称为贝叶斯网络),而且链图并不仅仅局限于这两类.然而,过去经常被用来表示概率的条件独立结构的却是无向图和有向无环图这两类更为特殊的图模型,链图模型并没有得到广泛的关注.不过,随着人们对链图更加深入的了解,越来越多的研究者对链图产生了浓厚的兴趣,并且链图将继续成为一个令人感兴趣的研究领域.在关于图模型的诸多研究中,结构学习引起了大量讨论,对于链图也不例外.目前主要有两类结构学习的方法：一类是基于约束的方法,一类是基于得分的方法.Lauritzen总结了在上个世纪关于结构学习的最重要的研究,但是大部分研究结果是关于无向图和有向无环图的.就我所知,链图的结构学习算法却少之又少,我认为这也是链图没有得到广泛应用的一个重要原因.因此,我在本文提出链图模型的一个新的结构学习算法.本文主要提出两个算法,一个是寻找链图中所有节点的马氏毯的算法,一个是基于马氏毯进行链图结构学习的算法.马氏毯是这样一个节点集：在忠实性假定下,给定一个节点的马氏毯后,这个节点就与其他节点条件独立.马氏毯可以用来进行因果还原,特征集选择以及链图的结构学习.我们的第一个算法就是为了进行马氏毯的还原,它是基于目标节点的边界和儿子直接从训练集中还原马氏毯,而不用先学习链图的整个结构.这样就为第二个算法做好了基础.在第二个算法中,我们首先通过移除伪边还原链图的骨架,然后确定复型的方向,最后通过迭代应用三个特殊规则得到相应的最大链图.这个算法是一个更加有效率的算法,因为我们只需要在目标节点和它的马氏毯成员之间进行条件独立检验即可.我们在忠实性假定下对两个算法的正确性进行讨论,并给出例子演示算法的运行过程.
[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

【相似文献】