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

摘要

Approximate Bayesian inference is NP-hard. Dagum and Luby defined the Local Vari ance Bound (LVB) to measure the approx imation hardness of Bayesian inference on Bayesian networks, assuming the networks model strictly positive joint probability dis tributions, i.e. zero probabilities are not per mitted. This paper introduces the k-test to measure the approximation hardness of in ference on Bayesian networks with determin istic causalities in the probability distribu tion, 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.