Derivation from first principles of belief values generated in networks by message passing

ABSTRACT

Some basic assumptions about the propagation of belief in the normal mode operation of system components in an arithmetic network are identified. They lead naturally to a message passing paradigm that propagates local computations throughout the system, and they are applicable to the quantification of reasoning in the presence of uncertainty in other contexts.

REFERENCES

• 1: deKleer, J., An assumption-based truth maintenance system, Artificial Intelligence 29 (1986a) 241-288.
• 2: Johan de Kleer, Extending the ATMS, Artificial Intelligence, v.28 n.2, p.163-196, March 1986 [doi>10.1016/0004-3702(86)90081-0]
• 3: J de Kleer , B C Williams, Diagnosing multiple faults, Artificial Intelligence, v.32 n.1, p.97-130, April 1987 [doi>10.1016/0004-3702(87)90063-4]
• 4: Dempster, A.P., Upper and lower probabilities induced by a multivalued mapping, Annals of Mathematical Statistics s88 (1967) 325-339.
• 5: Doyle, J., A truth maintenance system, Artificial Intelligence 12 (1979)231-272.
• 6: D. Dubois , H. Prade, Default reasoning and possibility theory, Artificial Intelligence, v.35 n.2, p.243-257, June 1988 [doi>10.1016/0004-3702(88)90014-8]
• 7: R. Fagin , J. Y. Halpern, Belief, awareness, and limited reasoning, Artificial Intelligence, v.34 n.1, p.39-76, Dec. 1987 [doi>10.1016/0004-3702(87)90003-8]
• 8: Geffner,H. and J. Pearl, Distributed diagnosis of systems with multiple faults, Proceedings of the third conference on Artificial Intelligence Applications, (1987) 156-162.
• 9: Matthew L. Ginsberg, Readings in nonmonotonic reasoning, Morgan Kaufmann Publishers Inc., San Francisco, CA, 1987
• 10: Laskey, K.B., and P.E. Lehner, Assumptions, beliefs and probabilities, submitted for publication, 1987.
• 11: J. P. Martins , S. C. Shapiro, A model for belief revision, Artificial Intelligence, v.35 n.1, p.25-79, May 1988 [doi>10.1016/0004-3702(88)90031-8]
• 12: McDermott, D. and J. Doyle, Non-monotonic logic I, Artificial Intelligence IS (1980) 41-72.
• 13: J Pearl, Fusion, propagation, and structuring in belief networks, Artificial Intelligence, v.29 n.3, p.241-288, Sept. 1986 [doi>10.1016/0004-3702(86)90072-X]
• 14: J Pearl, Evidential reasoning using stochastic simulation of causal models, Artificial Intelligence, v.32 n.2, p.245-257, May 1987 [doi>10.1016/0004-3702(87)90012-9]
• 15: Judea Pearl, Probabilistic reasoning in intelligent systems: networks of plausible inference, Morgan Kaufmann Publishers Inc., San Francisco, CA, 1988
• 16: Poole, D., A logical framework for default resoning, Artificial Intelligence 86
• 17: Reiter, R., A theory of evidence Pricncples, Artificial Intelligence 82
• 18: Sharer, G., A mathematical evidence Pricncn University Press, Princeton,
• 19: Zadeh, L.A., Fuzzy sets as a bnafor theory of possibility, Fuzzy Sets and Symptoms 1(1978) 3-28

INDEX TERMS

Primary Classification:
  G. Mathematics of Computing
  G.2 DISCRETE MATHEMATICS
      G.2.2 Graph Theory
          Subjects: Graph algorithms

Additional Classification:
  F. Theory of Computation
  F.2 ANALYSIS OF ALGORITHMS AND PROBLEM COMPLEXITY
      F.2.2 Nonnumerical Algorithms and Problems
          Subjects: Computations on discrete structures

  I. Computing Methodologies
  I.2 ARTIFICIAL INTELLIGENCE
      I.2.3 Deduction and Theorem Proving
          Subjects: Uncertainty, "fuzzy," and probabilistic reasoning

General Terms:
Algorithms, Theory