Sub-Local Constraint-Based Learning of Bayesian Networks Using A Joint Dependence Criterion

摘要

Constraint-based learning of Bayesian networks (BN) from limiteddata can lead to multiple testing problems when recovering denseareas of the skeleton and to conflicting results in theorientation of edges. In this paper, we present a newconstraint-based algorithm, light mutual min (LMM) for improvedaccuracy of BN learning from small sample data. LMM improves theassessment of candidate edges by using a ranking criterion thatconsiders conditional independence on neighboring variables atboth sides of an edge simultaneously. The algorithm also employsan adaptive relaxation of constraints that, selectively, allowssome nodes not to condition on some neighbors. This relaxationaims at reducing the incorrect rejection of true edgesconnecting high degree nodes due to multiple testing. LMMadditionally incorporates a new criterion for rankingv-structures that is used to recover the completed partiallydirected acyclic graph (CPDAG) and to resolve conflictingv-structures, a common problem in small sample constraint-basedlearning. Using simulated data, each of these components of LMMis shown to significantly improve network inference compared tocommonly applied methods when learning from limited data,including more accurate recovery of skeletons and CPDAGscompared to the PC, MaxMin, and MaxMin hill climbing algorithms.A proof of asymptotic correctness is also provided for LMM forrecovering the correct skeleton and CPDAG. color="gray">