Counting and Sampling Subsets Using Block Covers

Elias Lehtinen, Mikko Koivisto
Proceedings of the 42nd Conference on Uncertainty in Artificial Intelligence, PMLR 337:3477-3486, 2026.

Abstract

We present a new data structure, *block cover*, for approximate weighted counting and sampling of subsets of a given query set. Such queries are the main computational bottleneck, e.g., in advanced {Markov} chain Monte Carlo algorithms for {Bayesian} learning of {Bayesian} networks. Given a collection of weighted subsets of a ground set $N$, our key idea is to select a few moderate-size subsets $B$ of $N$, called blocks, so as to cover all or most of the input collection by the power sets $2^B$. An approximate sum over the subsets of a query set $Q$ is obtained by adding up the contributions within each block, which contibutions we precompute. We also give a similar, efficient algorithm for generating a subset of $Q$ with probability proportional to its weight. Our empirical results suggest that block covers are superior to previous approaches, which consider the subsets of interest one by one.

Cite this Paper

BibTeX
@InProceedings{pmlr-v337-lehtinen26a, title = {Counting and Sampling Subsets Using Block Covers}, author = {Lehtinen, Elias and Koivisto, Mikko}, booktitle = {Proceedings of the 42nd Conference on Uncertainty in Artificial Intelligence}, pages = {3477--3486}, year = {2026}, editor = {Perković, Emilija and Malinsky, Daniel}, volume = {337}, series = {Proceedings of Machine Learning Research}, month = {17--21 Aug}, publisher = {PMLR}, pdf = {https://raw.githubusercontent.com/mlresearch/v337/main/assets/lehtinen26a/lehtinen26a.pdf}, url = {https://proceedings.mlr.press/v337/lehtinen26a.html}, abstract = {We present a new data structure, *block cover*, for approximate weighted counting and sampling of subsets of a given query set. Such queries are the main computational bottleneck, e.g., in advanced {Markov} chain Monte Carlo algorithms for {Bayesian} learning of {Bayesian} networks. Given a collection of weighted subsets of a ground set $N$, our key idea is to select a few moderate-size subsets $B$ of $N$, called blocks, so as to cover all or most of the input collection by the power sets $2^B$. An approximate sum over the subsets of a query set $Q$ is obtained by adding up the contributions within each block, which contibutions we precompute. We also give a similar, efficient algorithm for generating a subset of $Q$ with probability proportional to its weight. Our empirical results suggest that block covers are superior to previous approaches, which consider the subsets of interest one by one.} }
Endnote
%0 Conference Paper %T Counting and Sampling Subsets Using Block Covers %A Elias Lehtinen %A Mikko Koivisto %B Proceedings of the 42nd Conference on Uncertainty in Artificial Intelligence %C Proceedings of Machine Learning Research %D 2026 %E Emilija Perković %E Daniel Malinsky %F pmlr-v337-lehtinen26a %I PMLR %P 3477--3486 %U https://proceedings.mlr.press/v337/lehtinen26a.html %V 337 %X We present a new data structure, *block cover*, for approximate weighted counting and sampling of subsets of a given query set. Such queries are the main computational bottleneck, e.g., in advanced {Markov} chain Monte Carlo algorithms for {Bayesian} learning of {Bayesian} networks. Given a collection of weighted subsets of a ground set $N$, our key idea is to select a few moderate-size subsets $B$ of $N$, called blocks, so as to cover all or most of the input collection by the power sets $2^B$. An approximate sum over the subsets of a query set $Q$ is obtained by adding up the contributions within each block, which contibutions we precompute. We also give a similar, efficient algorithm for generating a subset of $Q$ with probability proportional to its weight. Our empirical results suggest that block covers are superior to previous approaches, which consider the subsets of interest one by one.
APA
Lehtinen, E. & Koivisto, M.. (2026). Counting and Sampling Subsets Using Block Covers. Proceedings of the 42nd Conference on Uncertainty in Artificial Intelligence, in Proceedings of Machine Learning Research 337:3477-3486 Available from https://proceedings.mlr.press/v337/lehtinen26a.html.

Related Material