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.
|Title of host publication||Proceedings of the 29th International Conference on Machine Learning, ICML 2012|
|Number of pages||8|
|Publication status||Published - 10 Oct 2012|
|Event||29th International Conference on Machine Learning, ICML 2012 - Edinburgh, United Kingdom|
Duration: 26 Jun 2012 → 1 Jul 2012
|Conference||29th International Conference on Machine Learning, ICML 2012|
|Period||26/06/12 → 1/07/12|