Submitted by bmmalone on September 11, 2013 - 15:51
Lecturer :
Teppo Niinimäki
Event type:
HIIT seminar
Event time:
2013-09-20 10:15 to 11:00
Place:
Exactum, B119
Description:
Title
Treedy: A Heuristic for Counting and Sampling Subsets
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.
About the presenter
Teppo Niinimäki is a doctoral student at the University of Helsinki, Department of Computer Science.
Last updated on 11 Sep 2013 by Brandon Malone - Page created on 11 Sep 2013 by Brandon Malone