由Markov网到Bayesian网  

LEARNING BAYESIAN NETWORK BY FIRST LEARNING MARKOV NETWORK

作　　者：何盈捷[1] 刘惟一[1] 

机构地区：[1]云南大学计算机科学系,昆明650091

出　　处：《计算机研究与发展》2002年第1期87-99,共13页Journal of Computer Research and Development

基　　金：国家自然科学基金资助 (69763 0 0 3 )

摘　　要：Markov网 (马尔可夫网 )是类似于 Bayesian网 (贝叶斯网 )的另一种进行不确定性推理的有力工具 .Markov网是一个无向图 ,而 Bayesian网是一个有向无环图 .发现 Markov网不需要发现边的方向 ,因此要比发现Bayesian网容易得多 .提出了一种通过发现 Markov网得到等价的 Bayesian网的方法 .首先利用信息论中验证信息独立的一个重要结论 ,提出了一个基于依赖分析的边删除算法发现 Markov网 .该算法需 O(n2 )次 CI(条件独立 )测试 ,CI测试的时间复杂度取决于由样本数据得到的联合概率函数表的大小 .经证明 ,假如由样本数据得到的联合概率函数严格为正 ,则该算法发现的 Markov网一定是样本的最小 I图 .由发现的 Markov网 ,根据表示的联合概率函数相等 ,得到与其等价的Markov network is an another powerful tool besides Bayesian network, which can be used to do uncertain inference. Markov network is an undirected graph, while Bayesian network is a directed acyclic graph. Learning Markov network is easier than learning Bayesian network because it doesn't need to find the direction of an edge. A method of learning Bayesian network by first learning Markov network is given. Taking advantage of an important conclusion in information theory to test conditional independence, a dependency analysis based Markov network learning algorithm (edge deleting algorithm) is presented. The algorithm requires O(n 2) times CI(conditional independence) test, while the time complexity of a CI test depends on the size of the joint probability table which is obtained from the sample data. It has been proved that if the joint probability obtained from the sample data is strictly positive, the found Markov network must be the minimal I map of the sample. After finding a Markov network, an equivalent Bayesian network can be by representing the same joint probability.

关 键 词：MARKOV网 BAYESIAN网 联合概率函数 不确定推理 人工智能 

分 类 号：TP18[自动化与计算机技术—控制理论与控制工程]