## Probabilistic Reasoning and Bayesian Networks

Expert systems and uncertainty in artificial intelligence have seen a great surge of research activity during the last decade.

Bayesian networksare powerful tools both for graphically representing the relationships among a set of variables and for dealing with uncertainties in expert systems (see Pearl (1988) or Castillo, Gutiérrez, and Hadi (1997) for an introduction to this field). A key problem in Bayesian networks isevidence propagation, that is, obtaining the posterior distributions of variables when some evidence is observed. Several efficient methods for propagation of evidence in Bayesian networks have been proposed in recent years.Exact methodsexploit the independence structure contained in the network to efficiently propagate uncertainty (see, for example, Kim and Pearl (1983), Lauritzen and Spiegelhalter (1988), Jensen, Olesen, and Andersen (1990), Pearl (1988), and Shachter, Andersen, and Szolovits (1994)).Stochastic simulationconstitute an interesting alternative in highly connected networks, where exact algorithms may become inefficient (Pearl (1986), Henrion (1988), Shachter and Peot (1990a), Fung and Chang (1990), Bouckaert, Castillo, and Gutiérrez (1996)). Recently,search-based approximation algorithms, which search for high probability configurations through a space of possible values, have emerged as an alternative to the above methods in special cases as, for example, in Bayesian networks with extreme probabilities (Poole (1993)).However, all exact and approximate methods require that the joint probabilities of the nodes be specified numerically, that is, all the parameters must be assigned numeric values. In practice, exact numeric specification of these parameters may not be available or it may happens that the subject matter specialists can specify only ranges of values for the parameters rather than their exact values. In such cases, there is a need for symbolic methods which are able to deal with the parameters themselves, without assigning them numeric values.

Symbolic propagationleads to solutions which are expressed as functions of the parameters in symbolic form. Thus, the answers to general queries can be given symbolically in terms of the parameters and the answers to specific queries can then be obtained by plugging the values of the parameters in the solution which is given in symbolic form, without need to redo the propagation. Furthermore, symbolic propagation allows one to study the sensitivity of the results to changes in parameter values with little additional computational effort.Recently, two main approaches have been proposed for symbolic inference in Bayesian networks. The symbolic probabilistic inference algorithm (SPI) (Shachter, D'Ambrosio, and DelFabero (1990), Li and D'Ambrosio (1994)) is a goal directed method which performs only those calculations that are required to respond to queries. Symbolic expressions can be obtained by postponing evaluation of expressions, maintaining them in symbolic form. On the other hand, Castillo, Gutiérrez and Hadi (1996) perform symbolic calculations using slightly modified versions of standard numerical propagation algorithms by first replacing the values of the initial probabilities by symbolic parameters, then using computer packages with symbolic computational capabilities (such as, Mathematica and Maple) to propagate uncertainty. As opposed to SPI algorithm, this method is not goal oriented, but allows us to obtain symbolic expressions for all the nodes in the network.

However, both methods suffer from the same problem: they need to use special programs, or extra computational efforts implementing the necessary code, to carry out the symbolic computations. Furthermore, computing and simplifying symbolic expressions is a computationally expensive task, and it becomes increasingly inefficient when dealing with large networks, or large numbers of symbolic parameters. Castillo, Gutiérrez and Hadi (1996) present an efficient approach to symbolic propagation that takes advantage of the polynomial structure of the probabilities of the nodes to avoid symbolic computations. The main idea of the method is obtaining the symbolic expressions through a numerical algorithm to compute the coefficients of the associated polynomials. Then, all the computations are carried out numerically, avoiding the use of the computationally expensive symbolic manipulations.

For example, consider the following Bayesian network defined using some symbolic parameters:

The symbolic marginal probabilities of the nodes obtained by using the above symbolic method are

## References:

- Bouckaert, R. R., Castillo, E. and Gutiérrez, J. M. (1996) , "A Modified Simulation Scheme for Inference in Bayesian Networks," International Journal of Approximate Reasoning,
- Castillo, E., Gutiérrez, J. M., and Hadi, A. S. (1997), Expert Systems and Probabilistic Network Models, Springer-Verlag, New York.
- Castillo, E., Gutiérrez, J. M., and Hadi, A. S. (1996), A New Method for Symbolic Inference in Bayesian Networks, Networks, Vol. 28, 31-43.
- Fung, R. and Chang, K-C. (1990), "Weighing and Integrating Evidence
for Stochastic Simulation in Bayesian Networks," in
*Uncertainty in Artificial Intelligence 5*, Machine Intelligence and Pattern Recognition Series, 10, (Henrion et al. Eds.), North Holland, Amsterdam, 209-219. - Henrion, M. (1988), "Propagating Uncertainty in Bayesian Networks
by Probabilistic Logic Sampling," in
*Uncertainty in Artificial Intelligence 2*, (J.F. Lemmer and L. N. Kanal, Eds.), North Holland, Amsterdam, 317-324. - Kim, J. H. and Pearl, J. (1983), "A Computation Model for Causal
and Diagnostic Reasoning in Inference Systems," in
*Proceedings of the 8th International Joint Conference on AI*, Los Angeles, 190-193. - Lauritzen, S. L. and Spiegelhalter, D. J. (1988), "Local Computations with Probabilities on Graphical Structures and Their Application to Expert Systems," Journal of the Royal Statistical Society (B), 50, 157-224.
- Li, Z., and D'Ambrosio, B. (1995), "A Framework for Ordering Composite Beliefs in Belief Networks," IEEE Transactions on Systems, Man, and Cybernetics, 25, 2, 243-255.
- Pearl, J. (1988), Probabilistic Reasoning in Intelligent Systems: Networks of Plausible Inference, Morgan Kaufmann, San Mateo, CA.
- Pool, D. (1993), "Average-case Analysis of a Search Algorithm
for Estimating Prior and Posterior Probabilities in Bayesian Networks with
Extreme Probabilities",In
*Proceedings of the 13th International Joint Conference on Artificial Intelligence*, 13, 1, 606-612. - Santos, E., and Shimony S. E. (1994), "Belief Updating by Enumerating
High-Probability Independence-Based Assignments," in
*Proceedings of the Tenth Conference on Uncertainty in Artificial Intelligence*, 506-513. Morgan Kaufmann Publishers, San Francisco. - Shachter, R. D. and Peot, M. A. (1990a), "Simulation Approaches
to General Probabilistic Inference on Belief Networks," in
*Uncertainty in Artificial Intelligence 5*, Machine Intelligence and Pattern Recognition Series, 10 (Henrion et al. Eds.), North Holland, Amsterdam, 221-231. - Shachter, R. D., D'Ambrosio, B., and DelFabero, B. (1990b), "Symbolic
Probabilistic Inference in Belief Networks," in
*Proceedings Eighth National Conference on AI*, 126-131. - Shachter, R. D., Andersen, S. K. and Szolovits, P. (1994), "Global
Conditioning for Probabilistic Inference in Belief Networks," in
*Proceedings of the Tenth Conference on Uncertainty in Artificial Intelligence*, 514-522. Morgan Kaufmann Publishers, San Francisco. - Fung, R. and Chang, K-C. (1990), "Weighing and Integrating Evidence
for Stochastic Simulation in Bayesian Networks," in
*Uncertainty in Artificial Intelligence 5*, Machine Intelligence and Pattern Recognition Series, 10, (Henrion et al. Eds.), North Holland, Amsterdam, 209-219. - Henrion, M. (1988), "Propagating Uncertainty in Bayesian Networks
by Probabilistic Logic Sampling," in
*Uncertainty in Artificial Intelligence 2*, (J.F. Lemmer and L. N. Kanal, Eds.), North Holland, Amsterdam, 317-324. - Jensen, F. V., Olesen, K. G., and Andersen, S. K. (1990), "An Algebra of Bayesian Belief Universes for Knowledge-Based Systems," Networks, 20, 637-659.
- Kim, J. H. and Pearl, J. (1983), "A Computation Model for Causal
and Diagnostic Reasoning in Inference Systems," in
*Proceedings of the 8th International Joint Conference on AI*, Los Angeles, 190-193. - Lauritzen, S. L. and Spiegelhalter, D. J. (1988), "Local Computations with Probabilities on Graphical Structures and Their Application to Expert Systems," Journal of the Royal Statistical Society (B), 50, 157-224.
- Li, Z., and D'Ambrosio, B. (1994), "Efficient Inference in Bayes Nets as a Combinatorial Optimization Problem," International Journal of Approximate Reasoning, 11, 1, 55-81.
- Pearl, J. (1986), "Evidential Reasoning Using Stochastic Simulation of Causal Models," Artificial Intelligence, 32, 245-287.
- Pearl, J. (1988), Probabilistic Reasoning in Intelligent Systems: Networks of Plausible Inference, Morgan Kaufmann, San Mateo, CA.
- Pool, D. (1993), "Average-case Analysis of a Search Algorithm
for Estimating Prior and Posterior Probabilities in Bayesian Networks with
Extreme Probabilities",In
*Proceedings of the 13th International Joint Conference on Artificial Intelligence*, 13, 1, 606-612. - Shachter, R. D. and Peot, M. A. (1990a), "Simulation Approaches
to General Probabilistic Inference on Belief Networks," in
*Uncertainty in Artificial Intelligence 5*, Machine Intelligence and Pattern Recognition Series, 10 (Henrion et al. Eds.), North Holland, Amsterdam, 221-231. - Shachter, R. D., D'Ambrosio, B., and DelFabero, B. (1990b), "Symbolic
Probabilistic Inference in Belief Networks," in
*Proceedings Eighth National Conference on AI*, 126-131. - Shachter, R. D., Andersen, S. K. and Szolovits, P. (1994), "Global
Conditioning for Probabilistic Inference in Belief Networks," in
*Proceedings of the Tenth Conference on Uncertainty in Artificial Intelligence*, 514-522. Morgan Kaufmann Publishers, San Francisco.