SampleSearch: A Scheme that Searches for Consistent Samples

Vibhav Gogate, Rina Dechter
Proceedings of the Eleventh International Conference on Artificial Intelligence and Statistics, PMLR 2:147-154, 2007.

Abstract

Sampling from belief networks which have a substantial number of zero probabilities is problematic. MCMC algorithms like Gibbs sampling do not converge and importance sampling schemes generate many zero weight samples that are rejected, yielding an inefficient sampling process (the rejection problem). In this paper, we propose to augment importance sampling with systematic constraint-satisfaction search in order to overcome the rejection problem. The resulting SampleSearch scheme can be made unbiased by using a computationally expensive weighting scheme. To overcome this an approximation is proposed such that the resulting estimator is asymptotically unbiased. Our empirical results demonstrate the potential of our new scheme.

Cite this Paper

BibTeX
@InProceedings{pmlr-v2-gogate07a, title = {SampleSearch: A Scheme that Searches for Consistent Samples}, author = {Gogate, Vibhav and Dechter, Rina}, booktitle = {Proceedings of the Eleventh International Conference on Artificial Intelligence and Statistics}, pages = {147--154}, year = {2007}, editor = {Meila, Marina and Shen, Xiaotong}, volume = {2}, series = {Proceedings of Machine Learning Research}, address = {San Juan, Puerto Rico}, month = {21--24 Mar}, publisher = {PMLR}, pdf = {http://proceedings.mlr.press/v2/gogate07a/gogate07a.pdf}, url = {https://proceedings.mlr.press/v2/gogate07a.html}, abstract = {Sampling from belief networks which have a substantial number of zero probabilities is problematic. MCMC algorithms like Gibbs sampling do not converge and importance sampling schemes generate many zero weight samples that are rejected, yielding an inefficient sampling process (the rejection problem). In this paper, we propose to augment importance sampling with systematic constraint-satisfaction search in order to overcome the rejection problem. The resulting SampleSearch scheme can be made unbiased by using a computationally expensive weighting scheme. To overcome this an approximation is proposed such that the resulting estimator is asymptotically unbiased. Our empirical results demonstrate the potential of our new scheme.} }
Endnote
%0 Conference Paper %T SampleSearch: A Scheme that Searches for Consistent Samples %A Vibhav Gogate %A Rina Dechter %B Proceedings of the Eleventh International Conference on Artificial Intelligence and Statistics %C Proceedings of Machine Learning Research %D 2007 %E Marina Meila %E Xiaotong Shen %F pmlr-v2-gogate07a %I PMLR %P 147--154 %U https://proceedings.mlr.press/v2/gogate07a.html %V 2 %X Sampling from belief networks which have a substantial number of zero probabilities is problematic. MCMC algorithms like Gibbs sampling do not converge and importance sampling schemes generate many zero weight samples that are rejected, yielding an inefficient sampling process (the rejection problem). In this paper, we propose to augment importance sampling with systematic constraint-satisfaction search in order to overcome the rejection problem. The resulting SampleSearch scheme can be made unbiased by using a computationally expensive weighting scheme. To overcome this an approximation is proposed such that the resulting estimator is asymptotically unbiased. Our empirical results demonstrate the potential of our new scheme.
RIS
TY - CPAPER TI - SampleSearch: A Scheme that Searches for Consistent Samples AU - Vibhav Gogate AU - Rina Dechter BT - Proceedings of the Eleventh International Conference on Artificial Intelligence and Statistics DA - 2007/03/11 ED - Marina Meila ED - Xiaotong Shen ID - pmlr-v2-gogate07a PB - PMLR DP - Proceedings of Machine Learning Research VL - 2 SP - 147 EP - 154 L1 - http://proceedings.mlr.press/v2/gogate07a/gogate07a.pdf UR - https://proceedings.mlr.press/v2/gogate07a.html AB - Sampling from belief networks which have a substantial number of zero probabilities is problematic. MCMC algorithms like Gibbs sampling do not converge and importance sampling schemes generate many zero weight samples that are rejected, yielding an inefficient sampling process (the rejection problem). In this paper, we propose to augment importance sampling with systematic constraint-satisfaction search in order to overcome the rejection problem. The resulting SampleSearch scheme can be made unbiased by using a computationally expensive weighting scheme. To overcome this an approximation is proposed such that the resulting estimator is asymptotically unbiased. Our empirical results demonstrate the potential of our new scheme. ER -
APA
Gogate, V. & Dechter, R.. (2007). SampleSearch: A Scheme that Searches for Consistent Samples. Proceedings of the Eleventh International Conference on Artificial Intelligence and Statistics, in Proceedings of Machine Learning Research 2:147-154 Available from https://proceedings.mlr.press/v2/gogate07a.html.

Related Material