Learning Chordal Markov Networks via Branch and Bound

Tutkimustuotos: Artikkeli kirjassa/raportissa/konferenssijulkaisussaKonferenssiartikkeliTieteellinenvertaisarvioitu

Abstrakti

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.
Alkuperäiskielienglanti
OtsikkoAdvances in Neural Information Processing Systems 30 (NIPS 2017)
ToimittajatI. Guyon
Sivumäärä11
KustantajaNeural Information Processing Systems Foundation
Julkaisupäivä2017
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
http://nips.cc/Conferences/2017

Julkaisusarja

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

Lisätietoja


Volume:
Proceeding volume:

Tieteenalat

  • 113 Tietojenkäsittely- ja informaatiotieteet

Siteeraa tätä