Towards Efficient Sampling: Exploiting Random Walk Strategies
Abstract
From a computational perspective, there is a close connec-tion between various probabilistic reasoning tasks and the problem of counting or sampling satisfying assignments of a propositional theory. We consider the question of whether state-of-the-art satisfiability procedures, based on random walk strategies, can be used to sample uniformly or near-uniformly from the space of satisfying assignments. We first show that random walk SAT procedures often do reach the full set of solutions of complex logical theories. Moreover, by interleaving random walk steps with Metropolis transitions, we also show how the sampling becomes near-uniform.
Cite
Text
Wei et al. "Towards Efficient Sampling: Exploiting Random Walk Strategies." AAAI Conference on Artificial Intelligence, 2004. doi:10.1042/bj0180809Markdown
[Wei et al. "Towards Efficient Sampling: Exploiting Random Walk Strategies." AAAI Conference on Artificial Intelligence, 2004.](https://mlanthology.org/aaai/2004/wei2004aaai-efficient/) doi:10.1042/bj0180809BibTeX
@inproceedings{wei2004aaai-efficient,
title = {{Towards Efficient Sampling: Exploiting Random Walk Strategies}},
author = {Wei, Wei and Erenrich, Jordan and Selman, Bart},
booktitle = {AAAI Conference on Artificial Intelligence},
year = {2004},
pages = {670-676},
doi = {10.1042/bj0180809},
url = {https://mlanthology.org/aaai/2004/wei2004aaai-efficient/}
}