一般贝叶斯网络分类器及其学习算法

Algorithm for exact recovery of Bayesian network for classification

贝叶斯网络(BN)应用于分类应用时对目标变量预测有直接贡献的局部模型称做一般贝叶斯网络分类器(GBNC)。推导GBNC的传统途径是先学习完整的BN,而现有推导BN结构的算法限制了应用规模。为了避免学习全局BN,提出仅执行局部搜索的结构学习算法IPC-GBNC,它以目标变量节点为中心执行广度优先搜索,且将搜索深度控制在不超过两层。理论上可证明算法IPC-GBNC是正确的,而基于仿真和真实数据的实验进一步验证了其学习效果和效率的优势:a)可输出和执行全局搜索的PC算法相同甚至更高质量的结构;b)较全局搜索消耗少得多的计算量;c)同时实现了降维(类似决策树学习算法)。相比于绝大多数经典分类器,GBNC的分类性能相当,但兼具直观、紧凑表达和强大推理的能力(且支持不完整观测值)。

General Bayesian network classifier（ GBNC） was the effective local section of the Bayesian network（ BN） facing classification problem. Conventionally,it had to learn the global BN first,and existing structure learning algorithm imposed restriction on possible problem scale. The paper developed an algorithm called IPC-GBNC for the exact recovery of GBNC with only local search. It conducted a breadth-first search with depth no more than 2 given the class node as the center. It proved its soundness,and experiments on synthetic and UCI real-world datasets demonstrate the merits of IPC-GBNC over classical PC algorithm which conducted global search： a） it produces same as or even higher quality of structure than PC,b） it saves considerable computation over PC,and c） effective dimension reduction is realized. As compared with state-of-the-art classifiers,GBNC not only performs as well on prediction,but inherits merits from being graphical model,like compact representation and powerful inference ability.