贝叶斯网等价类学习算法

An Algorithm for Learning the Markov Equivalence Classes of the Bayesian Network

贝叶斯网用一种紧凑的形式表示联合概率分布,具有完备的语义和坚实的理论基础,目前已成为人工智能领域处理不确定性问题的最佳方法之一。贝叶斯网学习是其关键问题,传统学习方法存在如下不足:(1)随节点数增多非法结构以指数级增加,影响学习效率;(2)在等价结构之间进行打分搜索,影响收敛速度;(3)假设每个结构具有相同的先验概率,造成等价类中包含结构越多则先验概率越高。本文提出一种学习马尔科夫等价类算法,该算法基于骨架空间进行状态转换,利用从骨架空间到等价类空间的映射关系实现学习贝叶斯网等价类。实验数据证明,该方法可有效缩小搜索空间规模,相对于在有向图空间搜索的算法加快了算法的收敛速度,提高了执行效率。

Bayesian networks （BNs） is a compact representation of complex joint probability distribution. BNs have sound probabilistic semantics, explicit encoding of relevance relationships which led BNs to be one of the best methods for dealing with uncertainty in the AI domain. Learning BNs from data has become an important problem, and there are some problems in the existing learning algorithms： （1） The number of illegal structures is exponential, which infects the efficiency of structural learning ; （2） Comparing the structures in the same equivalent class slows down the speed of convergence; （3） If the prior distribution of each structure is equal, the more the structures contained in the equivalent class, the higher the probability of the class. This paper presents an algorithm for learning the Markov equivalence class of the Bayesian Network, which maps the search space from the skeleton space to the Markov equivalent class space. Experiments show that the searching space is decreased, compared with the algorithm searching in the Directed Acyclic Graph space, the convergence speed and the efficiency are improved