Uncertainty in Artificial Intelligence
First Name   Last Name   Password   Forgot Password   Log in!
    Proceedings   Proceeding details   Article details         Authors         Search    
Treedy: A Heuristic for Counting and Sampling Subsets
Teppo Niinimaki, Mikko Koivisto
Abstract:
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.
Keywords:
Pages: 469-477
PS Link:
PDF Link: /papers/13/p469-niinimaki.pdf
BibTex:
@INPROCEEDINGS{Niinimaki13,
AUTHOR = "Teppo Niinimaki and Mikko Koivisto",
TITLE = "Treedy: A Heuristic for Counting and Sampling Subsets",
BOOKTITLE = "Proceedings of the Twenty-Ninth Conference Annual Conference on Uncertainty in Artificial Intelligence (UAI-13)",
PUBLISHER = "AUAI Press",
ADDRESS = "Corvallis, Oregon",
YEAR = "2013",
PAGES = "469--477"
}


hosted by DSL   •   site info   •   help