A Novel Structure Learning Algorithm for Optimal Bayesian Network: Best Parents

We present a novel algorithm for learning structure of a Bayesian Network. Best Parents is a greedy construction method which performs structure learning without preconditioned knowledge or preprocessing. Unlike the well-known methods such as K2, TAN Hill Climbing or Simulated Annealing, we use no feature ordering, DAG validity or structure metrics. We provide a new greedy algorithm for optimal structure learning using conditional entropy. Also we perform a running time and performance comparison with other methods in the field. Our results indicate substantial optimality of our proposed algorithm in terms of running time and AUC combination.