Measuring the Hardness of Stochastic Sampling on Bayesian Networks with Deterministic Causalities: the k-Test

Haohai Yu, Robert A. van Engelen
Proceedings of the 27th Conference on Uncertainty in Artificial Intelligence, PMLR R9:867-876, 2011.

Abstract

Approximate Bayesian inference is NP-hard. Dagum and Luby defined the Local Variance Bound (LVB) to measure the approximation hardness of Bayesian inference on Bayesian networks, assuming the networks model strictly positive joint probability distributions, i.e. zero probabilities are not permitted. This paper introduces the k-test to measure the approximation hardness of inference on Bayesian networks with deterministic causalities in the probability distribution, i.e. when zero conditional probabilities are permitted. Approximation by stochastic sampling is a widely-used inference method that is known to suffer from inefficiencies due to sample rejection. The k-test predicts when rejection rates of stochastic sampling a Bayesian network will be low, modest, high, or when sampling is intractable.

Cite this Paper

BibTeX
@InProceedings{pmlr-vR9-yu11b, title = {Measuring the Hardness of Stochastic Sampling on {B}ayesian Networks with Deterministic Causalities: the k-Test}, author = {Yu, Haohai and van Engelen, Robert A.}, booktitle = {Proceedings of the 27th Conference on Uncertainty in Artificial Intelligence}, pages = {867--876}, year = {2011}, editor = {Cozman, Fabio and Pfeffer, Avi}, volume = {R9}, series = {Proceedings of Machine Learning Research}, month = {14--17 Jul}, publisher = {PMLR}, pdf = {https://raw.githubusercontent.com/mlresearch/r9/main/assets/yu11b/yu11b.pdf}, url = {https://proceedings.mlr.press/r9/yu11b.html}, abstract = {Approximate Bayesian inference is NP-hard. Dagum and Luby defined the Local Variance Bound (LVB) to measure the approximation hardness of Bayesian inference on Bayesian networks, assuming the networks model strictly positive joint probability distributions, i.e. zero probabilities are not permitted. This paper introduces the k-test to measure the approximation hardness of inference on Bayesian networks with deterministic causalities in the probability distribution, i.e. when zero conditional probabilities are permitted. Approximation by stochastic sampling is a widely-used inference method that is known to suffer from inefficiencies due to sample rejection. The k-test predicts when rejection rates of stochastic sampling a Bayesian network will be low, modest, high, or when sampling is intractable.}, note = {Reissued by PMLR on 04 October 2026.} }
Endnote
%0 Conference Paper %T Measuring the Hardness of Stochastic Sampling on Bayesian Networks with Deterministic Causalities: the k-Test %A Haohai Yu %A Robert A. van Engelen %B Proceedings of the 27th Conference on Uncertainty in Artificial Intelligence %C Proceedings of Machine Learning Research %D 2011 %E Fabio Cozman %E Avi Pfeffer %F pmlr-vR9-yu11b %I PMLR %P 867--876 %U https://proceedings.mlr.press/r9/yu11b.html %V R9 %X Approximate Bayesian inference is NP-hard. Dagum and Luby defined the Local Variance Bound (LVB) to measure the approximation hardness of Bayesian inference on Bayesian networks, assuming the networks model strictly positive joint probability distributions, i.e. zero probabilities are not permitted. This paper introduces the k-test to measure the approximation hardness of inference on Bayesian networks with deterministic causalities in the probability distribution, i.e. when zero conditional probabilities are permitted. Approximation by stochastic sampling is a widely-used inference method that is known to suffer from inefficiencies due to sample rejection. The k-test predicts when rejection rates of stochastic sampling a Bayesian network will be low, modest, high, or when sampling is intractable. %Z Reissued by PMLR on 04 October 2026.
APA
Yu, H. & van Engelen, R.A.. (2011). Measuring the Hardness of Stochastic Sampling on Bayesian Networks with Deterministic Causalities: the k-Test. Proceedings of the 27th Conference on Uncertainty in Artificial Intelligence, in Proceedings of Machine Learning Research R9:867-876 Available from https://proceedings.mlr.press/r9/yu11b.html. Reissued by PMLR on 04 October 2026.

Related Material