Exact Maximum Margin Structure Learning of Bayesian Networks
This addresses the challenge of discriminative structure learning in Bayesian networks for classification tasks, offering an incremental improvement over existing generative methods.
The paper tackles the problem of learning globally optimal Bayesian network structures for classification by proposing an exact method to maximize the probabilistic soft margin, a discriminative score, using branch-and-bound and linear programming. In experiments, this method outperforms generatively trained networks and competes with support vector machines.
Recently, there has been much interest in finding globally optimal Bayesian network structures. These techniques were developed for generative scores and can not be directly extended to discriminative scores, as desired for classification. In this paper, we propose an exact method for finding network structures maximizing the probabilistic soft margin, a successfully applied discriminative score. Our method is based on branch-and-bound techniques within a linear programming framework and maintains an any-time solution, together with worst-case sub-optimality bounds. We apply a set of order constraints for enforcing the network structure to be acyclic, which allows a compact problem representation and the use of general-purpose optimization techniques. In classification experiments, our methods clearly outperform generatively trained network structures and compete with support vector machines.