On state-space abstraction for anytime evaluation of Bayesian networks

ABSTRACT

Despite the increasing popularity of Bayesian networks for representing and reasoning about uncertain situations, the complexity of inference in this formalism remains a significant concern. A viable approach to relieving the problem is trading off accuracy for computational efficiency. To this end, varying the granularity of state space of state variables appears to be a feasible strategy for controlling the evaluation process. We consider an anytime procedure for approximate evaluation of Bayesian networks based on this idea. On application to some simple networks, the procedure exhibits a smooth improvement in approximation quality as computation time increases. With the aim of developing principled control techniques, we also conduct a theoretical analysis of the quality of approximation. Our main result demonstrates that the error induced by state-space abstraction deceases with the distance from the abstracted nodes, where "distance" is defined in terms of d-separation. While the empirical results suggest that incremental state-space abstraction offers a viable performance profile, the theoretical results represent a starting point for the deliberation scheduling of our anytime approximation method.

REFERENCES

• 1: Mark Boddy , Thomas L. Dean, Deliberation scheduling for problem solving in time-constrained environments, Artificial Intelligence, v.67 n.2, p.245-285, June 1994 [doi>10.1016/0004-3702(94)90054-X]
• 2: Breese, J. S. Construction of belief and decision networks. <i>Computational Intelligence</i> <b>8</b>(4): 624--647, 1992.
• 3: Breese, J. S., R. P. Goldman, and M. P. Wellman. Special Section on Knowledge-Based Construction of Probabilistic and Decision Models. <i>IEEE Transactions on Systems, Man, and Cybernetics</i> <b>24</b>(11), 1994.
• 4: Jack S. Breese , Eric Horvitz, Ideal reformulation of belief networks, Proceedings of the Sixth Annual Conference on Uncertainty in Artificial Intelligence, p.129-144, July 27-29, 1990
• 5: Kuo-Chu Chang , Robert M. Fung, Refinement and coarsening of Bayesian networks, Proceedings of the Sixth Annual Conference on Uncertainty in Artificial Intelligence, p.435-446, July 27-29, 1990
• 6: Eugene Charniak, Bayesian networks without tears: making Bayesian networks more accessible to the probabilistically unsophisticated, AI Magazine, v.12 n.4, p.50-63, Winter 1991
• 7: Ch&aacute;vez, T., and M. Henrion. Efficient estimation of the value of information in Monte Carlo models. <i>Proceedings of the Tenth Conference on Uncertainty in Artificial Intelligence,</i> Seattle, WA, Morgan Kaufmann, pp. 119--127, 1994.
• 8: Gregory F. Cooper, The computational complexity of probabilistic inference using Bayesian belief networks (research note), Artificial Intelligence, v.42 n.2-3, p.393-405, March 1990 [doi>10.1016/0004-3702(90)90060-D]
• 9: D'Ambrosio, B. Incremental probabilistic inference. <i>Proceedings of the Ninth Conference on Uncertainty in Artificial Intelligence,</i> Washington, DC, Morgan Kaufmann, pp. 301--308, 1993.
• 10: Paul Dagum , Michael Luby, Approximating probabilistic inference in Bayesian belief networks is NP-hard, Artificial Intelligence, v.60 n.1, p.141-153, March 1993 [doi>10.1016/0004-3702(93)90036-B]
• 11: Draper, D. L., and S. Hanks. Localized partial evaluation of belief networks. <i>Proceedings of the Tenth Conference on Uncertainty in Artificial Intelligence,</i> Seattle, WA, Morgan Kaufmann, pp. 170--177, 1994.
• 12: Ezawa, K. J. <i>Efficient Evaluation of Influence Diagrams.</i> PhD Thesis, Stanford University, 1986.
• 13: R. P. Goldman , E. Cherniak, A Language for Construction of Belief Networks, IEEE Transactions on Pattern Analysis and Machine Intelligence, v.15 n.3, p.196-208, March 1993 [doi>10.1109/34.204902]
• 14: Hoebel L. J. and M. Pittarelli. (Eds.) <i>Working Notes of the IJCAI-95 Workshop on Anytime Algorithms and Deliberation Scheduling.</i> Montr&eacute;al, Qu&eacute;bec, Canada, 1995.
• 15: Horvitz, E. J., and A. C. Klein. Utility-based abstraction and categorization. <i>Proceedings of the Ninth Conference on Uncertainty in Artificial Intelligence,</i> Washington, DC, Morgan Kaufmann, pp. 128--135, 1993.
• 16: Horvitz, E. J., H. J. Suermondt, and G. F. Cooper. Bounded conditioning: Flexible inference for decisions under scarce resources. <i>Proceedings of the Fifth Workshop on Uncertainty in Artificial Intelligence,</i> Windsor, Ontario, Canada, Morgan Kaufmann, pp. 182--193, 1989.
• 17: Jensen, F., and S. K. Andersen. Approximations in Bayesian belief universes for knowledge-based systems. <i>Proceedings of the Sixth Conference on Uncertainty in Artificial Intelligence,</i> Cambridge, MA, pp. 162--169, 1990.
• 18: Kj&aelig;rulff, U. Reduction of computational complexity in Bayesian networks through removal of weak dependences. <i>Proceedings of the Tenth Conference on Uncertainty in Artificial Intelligence,</i> Seattle, WA, Morgan Kaufmann, pp. 374--382, 1994.
• 19: Liu, C.-L., and M. P. Wellman. Control strategies for state-space abstraction in Bayesian networks, in preparation.
• 20: Richard E. Neapolitan, Probabilistic reasoning in expert systems: theory and algorithms, John Wiley & Sons, Inc., New York, NY, 1990
• 21: Nicholson, A. E., and J. M. Brady. Dynamic belief networks for discrete monitoring. <i>IEEE Transactions on Systems, Man, and Cybernetics</i> <b>24</b>(11), 1994.
• 22: Poh, K. L. and E. J. Horvitz. Topological proximity and relevance in graphical decision models. Technical Report. Microsoft Technical Report MSR-TR-95-15, Microsoft Research, Microsoft, 1995.
• 23: Judea Pearl, Probabilistic reasoning in intelligent systems: networks of plausible inference, Morgan Kaufmann Publishers Inc., San Francisco, CA, 1988
• 24: Provan, G. M. Tradeoffs in knowledge-based construction of probabilistic models. <i>IEEE Transactions on Systems, Man, and Cybernetics</i> <b>24</b>(11), 1994.
• 25: Provan, G. M. Abstraction in Belief Networks: The Role of Intermediate Sates in Diagnostic Reasoning. <i>Proceedings of the Eleventh Conference on Uncertainty in Artificial Intelligence,</i> Montr&eacute;al, Qu&eacute;bec, Canada, Morgan Kaufmann, pp. 464--471, 1995.
• 26: Saffiotti, A., and E. Umkehrer. Inference-driven construction of valuation systems from first-order clauses. <i>IEEE Transactions on Systems, Man, and Cybernetics</i> <b>24,</b> 1994.
• 27: Wellman, M. P., J. S. Breese, and R. P. Goldman. From knowledge bases to decision models. <i>Knowledge Engineering Review</i> <b>7</b>(1): 35--53, 1992.
• 28: Wellman, M. P., and C.-L. Liu. State-space abstraction for anytime evaluation of probabilistic networks. <i>Proceedings of the Tenth Conference on Uncertainty in Artificial Intelligence,</i> Seattle, WA, Morgan Kaufmann, pp. 567--574, 1994.
• 29: Whittaker, J. <i>Graphical Models in Applied Multivariate Statistics,</i> New York, NY, John Wiley &amp; Sons, 1990.

INDEX TERMS

Primary Classification:
  I. Computing Methodologies
  I.2 ARTIFICIAL INTELLIGENCE
      I.2.8 Problem Solving, Control Methods, and Search

Additional Classification:
  G. Mathematics of Computing
  G.2 DISCRETE MATHEMATICS
      G.2.2 Graph Theory
          Subjects: Network problems

  I. Computing Methodologies
  I.2 ARTIFICIAL INTELLIGENCE
        I.2.10 Vision and Scene Understanding
      I.2.3 Deduction and Theorem Proving

General Terms:
Design, Measurement, Performance, Theory