A quantitative assessment of the effect of different algorithmic schemes to the task of learning the structure of Bayesian Networks

The task of learning a BN can be divided into two subtasks: (1) structural learning, i.e., identification of the topology of the BN, and (2) parametric learning, i.e., estimation of the numerical parameters (conditional probabilities) for a given network topology. In particular, the most challenging task of the two is the one of learning the structure of a BN. Different methods have been proposed to face this problem, and they can be classified into two categories [4, 5]: (1) methods based on detecting conditional independencies, also known as constraint-based methods, and (2) score search methods, also known as score-based approaches. As discussed in [6], the input of the former algorithms is a set of conditional independence relations between subsets of variables, which are used to build a BN that represents a large percentage (and, whenever possible, all) of these relations [7]. However, the number of conditional independence tests that such methods should perform is exponential and, thus, approximation techniques are required.