Learning chordal Markov networks by dynamic programming

Kustaa Kangas, Teppo Mikael Niinimäki, Mikko Koivisto

Tutkimustuotos: Artikkeli kirjassa/raportissa/konferenssijulkaisussaKonferenssiartikkeliTieteellinenvertaisarvioitu

Abstrakti

We present an algorithm for finding a chordal Markov network that maximizes any given decomposable scoring function. The algorithm is based on a recursive characterization of clique trees, and it runs in O(4^n) time for n vertices. On an eight-vertex benchmark instance, our implementation turns out to be about ten million times faster than a recently proposed, constraint satisfaction based algorithm (Corander et al., NIPS 2013). Within a few hours, it is able to solve instances up to 18 vertices, and beyond if we restrict the maximum clique size. We also study the performance of a recent integer linear programming algorithm (Bartlett and Cussens, UAI 2013). Our results suggest that, unless we bound the clique sizes, currently only the dynamic programming algorithm is guaranteed to solve instances with around 15 or more vertices.
Alkuperäiskielienglanti
Otsikko[Proceedings from the conference, "Neural Information Processing Systems 2014"]
ToimittajatZ. Ghahramani, M. Welling, C. Cortes, N.D. Lawrence, K.Q. Weinberger
Sivumäärä9
KustantajaCurran Associates
Julkaisupäivä2014
Sivut2357-2365
TilaJulkaistu - 2014
OKM-julkaisutyyppiA4 Artikkeli konferenssijulkaisuussa
TapahtumaAdvances in neural information processing systems - Montreal, Kanada
Kesto: 8 joulukuuta 201413 joulukuuta 2014
Konferenssinumero: 27

Julkaisusarja

NimiAdvances in Neural Information Processing Systems
Vuosikerta27 (NIPS 2014)
ISSN (painettu)1049-5258

Lisätietoja

Jufo_ID: 50535 ; lyhenne: NIPS.
Volume:
Proceeding volume:

Tieteenalat

  • 113 Tietojenkäsittely- ja informaatiotieteet

Siteeraa tätä