Bayesian Error-Bars for Belief Net Inference

Russell Greiner


  A Bayesian Belief Network (BN) models a joint distribution over a set of n variables, using a DAG structure to represent the immediate dependencies between the variables, and a set of parameters (aka "CPTables") to represent the local conditional probabilities of a node, given each assignment to its parents. In many situations, these parameters are themselves random variables --- this may reflect the uncertainty of the domain expert, or may come from a training sample used to estimate the parameter values. The distribution over these "CPtable variables" induces a distribution over the response the BN will return to any "What is Pr(Q=q | E=e)?" query. This paper investigates properties of this response: showing first that it is asymptotically normal, then providing, in closed form, its mean and asymptotic variance. We then present an effective general algorithm for computing this variance, which has the same complexity as simply computing (the mean value of) the response itself --- ie, O(n 2^w), where w is the effective tree width. Finally, we provide empirical evidence that a Beta approximation works much better than the normal distribution, especially for small sample sizes, and that our algorithm works effectively in practice, over a range of belief net structures, sample sizes and queries. This is joint work with Tim Van Allen, Ajit Singh and Peter Hooper.

Back to the Main Page

Pradeep Ravikumar
Last modified: Tue Feb 17 15:50:59 EST 2004