Treedy: A Heuristic for Counting and Sampling Subset

Teppo Mikael Niinimäki, Mikko Koivisto

Tutkimustuotos: Artikkeli kirjassa/raportissa/konferenssijulkaisussaKonferenssiartikkeliTieteellinenvertaisarvioitu

Abstrakti

Consider a collection of weighted subsets of a ground set N. Given a query subset Q of N, how fast can one (1) find the weighted sum over all subsets of Q, and (2) sample a subset of Q proportionally to the weights? We present a tree-based greedy heuristic, Treedy, that for a given positive tolerance d answers such counting and sampling queries to within a guaranteed relative error d and total variation distance d, respectively. Experimental results on artificial instances and in application to Bayesian structure discovery in Bayesian networks show that approximations yield dramatic savings in running time compared to exact computation, and that Treedy typically outperforms a previously proposed sorting-based heuristic.
Alkuperäiskielienglanti
OtsikkoProceedings of the Twenty-Ninth Conference Conference on Uncertainty in Artificial Intelligence (UAI-13)
Sivumäärä8
Julkaisupäivä2013
Sivut469-477
TilaJulkaistu - 2013
OKM-julkaisutyyppiA4 Artikkeli konferenssijulkaisuussa
TapahtumaConference on Uncertainty in Artificial Intelligence - Bellevue, Yhdysvallat (USA)
Kesto: 12 heinäkuuta 201315 heinäkuuta 2013
Konferenssinumero: 29 (UAI)

Lisätietoja


Volume:
Proceeding volume:

Tieteenalat

  • 113 Tietojenkäsittely- ja informaatiotieteet

Siteeraa tätä