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 = {Vibhav Gogate and Rina Dechter}, booktitle = {Proceedings of the Eleventh International Conference on Artificial Intelligence and Statistics}, pages = {147--154}, year = {2007}, editor = {Marina Meila and Xiaotong Shen}, 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 = {http://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 %J Proceedings of Machine Learning Research %P 147--154 %U http://proceedings.mlr.press %V 2 %W PMLR %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 PY - 2007/03/11 DA - 2007/03/11 ED - Marina Meila ED - Xiaotong Shen ID - pmlr-v2-gogate07a PB - PMLR SP - 147 DP - PMLR EP - 154 L1 - http://proceedings.mlr.press/v2/gogate07a/gogate07a.pdf UR - http://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 PMLR 2:147-154

Related Material