构建贝叶斯网络本质图的新方法

New method for constructing essential graph of Bayesian network structures

等价类学习是贝叶斯网络结构学习的一个重要分支,而本质图是贝叶斯网络等价类的图形表示,是进行等价类学习的有力工具。针对求解贝叶斯网络结构本质图存在的繁琐问题,提出了一种构建贝叶斯网络本质图的组合算法。该算法从初始非循环有向图开始,对所有有向边进行排序,保持V-结构中的边不变,将不参与V-结构的有向边转化为无向边,依次根据三条规则判定各条无向边在本质图中的方向。给出了算法的理论证明,通过具体案例分析验证了算法的有效性。

Learning equivalence class is an important branch in Bayesian network structure learning,and essential graph is a graphical representation and powerful tool for equivalence classes of Bayesian network.Finding the essential graph of a Bayesian network structure is troublesome,a combined algorithm is presented for constructing the essential graph of Bayesian network.The algorithm starts from the initial directed acyclic graph,firstly sorts all the directed edges,and then keeps the edges participating in V-structures unchanged and transforms all the others into undirected edges,finally determines the orientation of all the undirected edges in essential graph with respect to the three rules successively.The correctness of the method is proved and the validity of the algorithm is analyzed in the case at last.