基于最大主子图分解的贝叶斯网络等价类学习算法

针对基于约束方法学习贝叶斯网络(BN)结构的不足,以及随着条件集的增大,利用统计方法进行条件独立(CI)测试不稳定等问题,提出一种基于最大主子图分解(MPD)的BN等价类学习算法.该算法首先通过MPD分解技术对BN的道德图进行分解；然后利用0阶和1阶CI测试识别部分子图中的V结构,对于初步未定的V结构利用局部评分搜索确定,从而避免了冗余检验,有效地减小了条件集的维数,并且提高了算法的效率.理论证明和实验结果均表明了所提出算法的有效性和合理性.

Structural Learning Bayesian Network Equivalence Classes via Maximal Prime Decomposition

To solve the drawbacks of constraint-based method for learning Bayesian networks(BN) and the unreliability of the conditional independence(CI) tests as the conditioning sets become too large,this paper proposes a structural learning algorithm based on maximal prime decomposition(MPD).Firstly,MPD technique is used to transform the moral graph of BN into its sub-graphs.Then,only zero order and first order CI tests are used to identify V-structures in part of sub-graphs and takes scoring function searches to optimize local structure,so that the number of conditional independence tests can be decreased.Redundancy tests can be avoided and the time performance can be greatly enhanced.Finally,theoretical and experimental results show that the new algorithm is effective and reasonable.