Fusion, propagation, and structuring in belief networks.

*(English)*Zbl 0624.68081Belief networks are directed acyclic graphs in which the nodes represent propositions (or variables), the arcs signify direct dependencies between the linked propositions, and the strengths of these dependencies are quantified by conditional probabilities. A network of this sort can be used to represent the generic knowledge of a domain expert, and it turns into a computational architecture if the links are used not merely for storing factual knowledge but also for directing and activating the data flow in the computations which manipulate this knowledge.

The first part of the paper deals with the task of fusing and propagating the impacts of new information through the networks in such a way that, when equilibrium is reached, each proposition will be assigned a measure of belief consistent with the axioms of probability theory. It is shown that if the network is singly connected (e.g. tree-structured), then probabilities can be updated by local propagation in an isomorphic network of parallel and autonomous processors and that the impact of new information can be imparted to all propositions in time proportional to the longest path in the network.

The second part of the paper deals with the problem of finding a tree- structured representation for a collection of probabilistically coupled propositions using auxiliary (dummy) variables, colloquially called “hidden causes”. It is shown that if such a tree-structured representation exists, then it is possible to uniquely uncover the topology of the tree by observing pairwise dependencies among the available propositions (i.e., the leaves of the tree). The entire tree structure, including the strengths of all internal relationships, can be reconstructed in time proportional to n log n, where n is the number of leaves.

The first part of the paper deals with the task of fusing and propagating the impacts of new information through the networks in such a way that, when equilibrium is reached, each proposition will be assigned a measure of belief consistent with the axioms of probability theory. It is shown that if the network is singly connected (e.g. tree-structured), then probabilities can be updated by local propagation in an isomorphic network of parallel and autonomous processors and that the impact of new information can be imparted to all propositions in time proportional to the longest path in the network.

The second part of the paper deals with the problem of finding a tree- structured representation for a collection of probabilistically coupled propositions using auxiliary (dummy) variables, colloquially called “hidden causes”. It is shown that if such a tree-structured representation exists, then it is possible to uniquely uncover the topology of the tree by observing pairwise dependencies among the available propositions (i.e., the leaves of the tree). The entire tree structure, including the strengths of all internal relationships, can be reconstructed in time proportional to n log n, where n is the number of leaves.

##### MSC:

68T99 | Artificial intelligence |

##### Keywords:

computational model for humans’ inferential reasoning; Belief networks; directed acyclic graphs; generic knowledge of a domain expert
Full Text:
DOI

##### References:

[1] | Anderson, J.R., () |

[2] | Chow, C.K.; Liu, C.N., Approximating discrete probability distributions with dependence trees, IEEE trans. inf. theory, 14, 462-467, (1968) · Zbl 0165.22305 |

[3] | Dechter, R.; Pearl, J., The anatomy of easy problems: A constraint-satisfaction formulation, (), 1066-1072 |

[4] | Dell, G.S., Positive feedback in hierarchical connectionist models: applications to language production, Cognitive sci., 9, 1, 3-24, (1985) |

[5] | Doyle, J., A truth maintenance system, Artificial intelligence, 12, 231-272, (1979) |

[6] | Duda, R.O.; Hart, P.E.; Nilsson, N.J., Subjective Bayesian methods for rule-based inference systems, (), 1075-1082 |

[7] | Freuder, E.C., A sufficient condition of backtrack-free search, J. ACM, 29, 1, 24-32, (1982) · Zbl 0477.68063 |

[8] | Geman, S.; Geman, D., Stochastic relaxations, Gibbs distributions, and the Bayesian restoration of images, IEEE trans. pattern anal. machine intelligence, 6, 6, 721-742, (1984) · Zbl 0573.62030 |

[9] | Hinton, G.E.; Sejnowski, T.J.; Ackley, D.H., Boltzman machines: constraint satisfaction networks that learn, () |

[10] | Howard, R.A.; Matheson, J.E., Influence diagrams, () |

[11] | Jeffrey, R., () |

[12] | Kemeny, J.G.; Snell, J.L.; Knapp, A.W., () |

[13] | Kim, J., CONVINCE: A conversational inference consolidation engine, () |

[14] | Kim, J.; Pearl, J., A computational model for combined causal and diagnostic reasoning in inference systems, (), 190-193 |

[15] | Lauritzen, S.L., () |

[16] | Lazarfeld, P.F., Latent structure analysis, () |

[17] | Lesser, V.R.; Erman, L.D., A retrospective view of HEARSAY II architecture, (), 790-800 |

[18] | Levy, H.; Low, D.W., A new algorithm for finding small cycle cutsets, () · Zbl 0662.68070 |

[19] | Lowrance, J.D., Dependency-graph models of evidential support, () |

[20] | McAllester, D., An outlook on truth maintenance, () |

[21] | Pearl, J., Reverend Bayes on inference engines: A distributed hierarchical approach, (), 133-136 |

[22] | Pearl, J., A constraint-propagation approach to probabilistic reasoning, (), 357-370, also |

[23] | Pearl, J., Distributed diagnosis in causal models with continuous variables, () |

[24] | Pearl, J.; Paz, A., Graphoids: A graph-based logic for reasoning about relevancy relations, () |

[25] | Pearl, J., On evidential reasoning in a hierarchy of hypotheses, Artificial intelligence, 28, 9-15, (1986) |

[26] | Pearl, J.; Tarsi, M., Structuring causal trees, J. complexity, 2, 1, 60-77, (1986) · Zbl 0589.68060 |

[27] | Rosenfeld, A.; Hummel, A.; Zucker, S., Scene labelling by relaxation operations, IEEE trans. syst. man cybern., 6, 420-433, (1976) · Zbl 0335.68070 |

[28] | Rumelhart, D.E., Toward an interactive model of Reading, () |

[29] | Rumelhart, D.E.; McClelland, J.L., An interactive activation model of context effects in letter perception: part 2. the contextual enhancement effect and some tests and extensions of the model, Psychol. rev., 89, 60-94, (1982) |

[30] | Shastri, L.; Feldman, J.A., Semantic networks and neural nets, () |

[31] | Simon, H.A., Spurious correlations: A causal interpretation, J. am. stat. assoc., 49, 469-492, (1954) |

[32] | Spiegelhalter, D.J., Probabilistic reasoning in predictive expert systems, (), 47-68 |

[33] | Suppes, P., () |

[34] | Tverski, A.; Kahneman, D., Causal schemata in judgments under uncertainty, () |

[35] | Waltz, D.G., Generating semantic descriptions from drawings of scenes with shadows, () |

This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.