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

Structural Learning Bayesian Network Equivalence Classes Based on a Hybrid Method

作　　者：朱明敏[1] 刘三阳[1,2] 杨有龙[1] 

机构地区：[1]西安电子科技大学理学院数学系,陕西西安710071 [2]西安电子科技大学综合业务网国家重点实验室,陕西西安710071

出　　处：《电子学报》2013年第1期98-104,共7页Acta Electronica Sinica

基　　金：国家自然科学基金(No.60974082;No.61075055);国家杰出青年科学基金(No.11001214);西安电子科技大学基本科研业务基金(No.K5051270013)

摘　　要：贝叶斯网络(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.

关 键 词：贝叶斯网络 最大主分解 Markov边界 有向无环图 条件独立 

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