Learning Chordal Markov Networks via Branch and Bound

Forskningsoutput: Kapitel i bok/rapport/konferenshandlingKonferensbidragVetenskapligPeer review

Sammanfattning

We present a new algorithmic approach for the task of finding a chordal Markov network structure that maximizes a given scoring function. The algorithm is based on branch and bound and integrates dynamic programming for both domain pruning and for obtaining strong bounds for search-space pruning. Empirically, we show that the approach dominates in terms of running times a recent integer programming approach (and thereby also a recent constraint optimization approach) for the problem. Furthermore, our algorithm scales at times further with respect to the number of variables than a state-of-the-art dynamic programming algorithm for the problem, with the potential of reaching 20 variables and at the same time circumventing the tight exponential lower bounds on memory consumption of the pure dynamic programming approach.
Originalspråkengelska
Titel på värdpublikationAdvances in Neural Information Processing Systems 30 (NIPS 2017)
RedaktörerI. Guyon
Antal sidor11
FörlagNeural Information Processing Systems Foundation
Utgivningsdatum2017
StatusPublicerad - 2017
MoE-publikationstypA4 Artikel i en konferenspublikation
EvenemangAnnual Conference on Neural Information Processing Systems - Long Beach, Förenta Staterna (USA)
Varaktighet: 4 dec. 20179 dec. 2017
Konferensnummer: 31
http://nips.cc/Conferences/2017

Publikationsserier

NamnAdvances in neural information processing systems
FörlagNeural Information Processing Systems (NIPS)
Volym30
ISSN (tryckt)1049-5258

Vetenskapsgrenar

  • 113 Data- och informationsvetenskap

Citera det här