Abstract
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.

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