Learning Chordal Markov Networks via Branch and Bound

Tutkimustuotos: Artikkeli kirjassa/raportissa/konferenssijulkaisussaKonferenssiartikkeliTieteellinenvertaisarvioitu


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.
OtsikkoAdvances in Neural Information Processing Systems 30 (NIPS 2017)
ToimittajatI. Guyon
KustantajaNeural Information Processing Systems Foundation
TilaJulkaistu - 2017
OKM-julkaisutyyppiA4 Artikkeli konferenssijulkaisuussa
TapahtumaAnnual Conference on Neural Information Processing Systems - Long Beach, Yhdysvallat (USA)
Kesto: 4 joulukuuta 20179 joulukuuta 2017
Konferenssinumero: 31


NimiAdvances in neural information processing systems
KustantajaNeural Information Processing Systems (NIPS)
ISSN (painettu)1049-5258


Proceeding volume:


  • 113 Tietojenkäsittely- ja informaatiotieteet

Siteeraa tätä