A new method for efficient symbolic propagation in discrete Bayesian networks

This paper presents a new efficient method for uncertainty propagation in discrete Bayesian networks in symbolic, as opposed to numeric, form, when considering some of the probabilities of the Bayesian network as parameters. The algebraic structure of the conditional probabilities of any set of nodes, given some evidence, is characterized as ratios of linear polynomials in the parameters. We use this result to carry out these symbolic expressions efficiently by calculating the coefficients of the polynomials involved, using standard numerical algorithms. The numeric canonical components method is proposed as an alternative to symbolic computations, gaining in speed and simplicity. It is also shown how to avoid redundancy when calculating the numeric canonical components probabilities using standard message-passing methods. The canonical components can also be used to obtain lower and upper bounds for the symbolic expression associated with the probabilities. Finally, we analyze the problem of symbolic evidence, which allows answering multiple queries regarding a given set of evidential nodes. In this case, the algebraic structure of the symbolic expressions obtained for the probabilities are shown to be ratios of nonlinear polynomial expressions. Then, we can perform symbolic inference with only a small set of symbolic evidential nodes. The methodology is illustrated by examples.