Treedy: A Heuristic for Counting and Sampling Subsets

Teppo Niinimäki, Mikko Koivisto
Proceedings of the 29th Conference on Uncertainty in Artificial Intelligence, PMLR R11:184-192, 2013.

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 sub-set 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.

Cite this Paper

BibTeX
@InProceedings{pmlr-vR11-niinimaki13a, title = {Treedy: A Heuristic for Counting and Sampling Subsets}, author = {Niinim{\"a}ki, Teppo and Koivisto, Mikko}, booktitle = {Proceedings of the 29th Conference on Uncertainty in Artificial Intelligence}, pages = {184--192}, year = {2013}, editor = {Nicholson, Ann and Smyth, Padhraic}, volume = {R11}, series = {Proceedings of Machine Learning Research}, month = {12--14 Jul}, publisher = {PMLR}, pdf = {https://raw.githubusercontent.com/mlresearch/r11/main/assets/niinimaki13a/niinimaki13a.pdf}, url = {https://proceedings.mlr.press/r11/niinimaki13a.html}, 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 sub-set 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.}, note = {Reissued by PMLR on 04 October 2026.} }
Endnote
%0 Conference Paper %T Treedy: A Heuristic for Counting and Sampling Subsets %A Teppo Niinimäki %A Mikko Koivisto %B Proceedings of the 29th Conference on Uncertainty in Artificial Intelligence %C Proceedings of Machine Learning Research %D 2013 %E Ann Nicholson %E Padhraic Smyth %F pmlr-vR11-niinimaki13a %I PMLR %P 184--192 %U https://proceedings.mlr.press/r11/niinimaki13a.html %V R11 %X 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 sub-set 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. %Z Reissued by PMLR on 04 October 2026.
APA
Niinimäki, T. & Koivisto, M.. (2013). Treedy: A Heuristic for Counting and Sampling Subsets. Proceedings of the 29th Conference on Uncertainty in Artificial Intelligence, in Proceedings of Machine Learning Research R11:184-192 Available from https://proceedings.mlr.press/r11/niinimaki13a.html. Reissued by PMLR on 04 October 2026.

Related Material