An Improved Admissible Heuristic for Finding Optimal Bayesian Networks

Changhe Yuan, Brandon Michael Malone

Forskningsoutput: Kapitel i bok/rapport/konferenshandlingKonferensbidragVetenskapligPeer review


Recently two search algorithms, A* and breadth-first branch and bound (BFBnB), were developed based on a simple admissible heuristic for learning Bayesian network structures that optimize a scoring function. The heuristic represents a relaxation of the learning problem such that each variable chooses optimal parents independently. As a result, the heuristic may contain many directed cycles and result in a loose bound. This paper introduces an improved admissible heuristic that tries to avoid directed cycles within small groups of variables. A sparse representation is also introduced to store only the unique optimal parent choices. Empirical results show that the new techniques significantly improved the efficiency and scalability of A* and BFBnB on most of datasets tested in this paper.
Titel på gästpublikationProceedings of the 28th Conference of Uncertainty in Artificial Intelligence
Antal sidor10
StatusPublicerad - 2012
MoE-publikationstypA4 Artikel i en konferenspublikation
EvenemangConference on Uncertainty in Artificial Intelligence - Catalina Island, Förenta Staterna (USA)
Varaktighet: 15 aug 201217 aug 2012
Konferensnummer: 28


  • 113 Data- och informationsvetenskap

Citera det här