基于混合方式的贝叶斯网络等价类学习算法

Structural Learning Bayesian Network Equivalence Classes Based on a Hybrid Method

贝叶斯网络(BN)是不确定知识表示和推理的主要方法之一,是人工智能中重要的理论模型.针对现有混合方法学习BN结构不稳定、容易陷入局部最优等问题,本文将图论中的最大主子图分解理论与条件独立(CI)测试相结合,同时引入少量的局部评分搜索,提出一种新的基于混合方式的BN等价类学习算法.新算法通过确定所有变量的Markov边界构造网络的无向独立图,并对无向图进行最大主子图分解,从而将高维的结构学习问题转化为低维问题,然后利用低阶CI测试和局部评分搜索识别子图中的V结构.理论证明以及实验分析显示了新算法的正确性和有效性.

Bayesian Network（BN）is one of the most important methods for representing and inferring with uncertainty knowledge,and also a powerful theory model within the community of artificial intelligence.To solve the drawbacks of hybrid methods for learning BNs which are easy to fall into local optimum and unreliable for learning large data set,we propose a novel hybrid algorithm for learning BN equivalence classes which combines ideas from maximal prime decomposition（MPD）of graph theory,conditional independence（CI）tests,and local search-and-score techniques in an effective way.It first reconstructs the undirected independence graph of a BN and then performs MPD to transform the undirected graph into its subgraphs.Finally,the new algorithm uses only lower-order CI tests and local BDeu score to check the v-structure of each subgraph.Theoretical and experimental results show that the proposed algorithm is correctness and effective.