Averaging of Decomposable Graphs by Dynamic Programming and Sampling

Juho-Kustaa Wiljami Kangas, Teppo Mikael Niinimäki, Mikko Kalle Henrik Koivisto

Tutkimustuotos: Artikkeli kirjassa/raportissa/konferenssijulkaisussaKonferenssiartikkeliTieteellinenvertaisarvioitu


We give algorithms for Bayesian learning of decomposable graphical models from complete data. We build on a recently proposed dynamic programming algorithm that finds optimal graphs of n nodes in O(4n) time and O(3n) space (Kangas et al., NIPS 2014), and show how it can be turned into accurate averaging algorithms. Specifically, we show that certain marginals of the posterior distribution, like the posterior probability of an edge, can be computed in O(n3 3n) time, provided that the prior over the graphs is of an appropriate form. To overcome some limitations of the exact approach, we also give sampling schemes that—using essentially no extra space—can draw up to 3n independent graphs from the posterior in O(n 4n) time. Through importance sampling, this enables accurate Bayesian inference with a broader class of priors. Using benchmark datasets, we demonstrate the method's performance and the advantage of averaging over optimization when learning from little data.
OtsikkoUncertainty In Artificial Intelligence : Proceedings of the Thirty-First Conference (2015)
ToimittajatMarina Meila, Tom Heskes
JulkaisupaikkaCorvallis, Oregon
KustantajaAUAI Press
ISBN (elektroninen)978-0-9966431-0-8
TilaJulkaistu - 2015
OKM-julkaisutyyppiA4 Artikkeli konferenssijulkaisuussa
TapahtumaConference on uncertainty in artificial intelligence - Amsterdam, Alankomaat
Kesto: 12 heinäkuuta 201516 heinäkuuta 2015
Konferenssinumero: 31 UAI


Proceeding volume:


  • 113 Tietojenkäsittely- ja informaatiotieteet

Siteeraa tätä