  In this paper, we describe a scheme for propagating belief functions in
certain kinds of trees using only local computations. This scheme generalizes
the computational scheme proposed by Shafer and Logan1 for diagnostic trees of
the type studied by Gordon and Shortliffe, and the slightly more general scheme
given by Shafer for hierarchical evidence. It also generalizes the scheme
proposed by Pearl for Bayesian causal trees (see Shenoy and Shafer). Pearl's
causal trees and Gordon and Shortliffe's diagnostic trees are both ways of
breaking the evidence that bears on a large problem down into smaller items of
evidence that bear on smaller parts of the problem so that these smaller
problems can be dealt with one at a time. This localization of effort is often
essential in order to make the process of probability judgment feasible, both
for the person who is making probability judgments and for the machine that is
combining them. The basic structure for our scheme is a type of tree that
generalizes both Pearl's and Gordon and Shortliffe's trees. Trees of this
general type permit localized computation in Pearl's sense. They are based on
qualitative judgments of conditional independence. We believe that the scheme
we describe here will prove useful in expert systems. It is now clear that the
successful propagation of probabilities or certainty factors in expert systems
requires much more structure than can be provided in a pure production-system
framework. Bayesian schemes, on the other hand, often make unrealistic demands
for structure. The propagation of belief functions in trees and more general
networks stands on a middle ground where some sensible and useful things can be
done. We would like to emphasize that the basic idea of local computation for
propagating probabilities is due to Judea Pearl. It is a very innovative idea;
we do not believe that it can be found in the Bayesian literature prior to
Pearl's work. We see our contribution as extending the usefulness of Pearl's
idea by generalizing it from Bayesian probabilities to belief functions. In the
next section, we give a brief introduction to belief functions. The notions of
qualitative independence for partitions and a qualitative Markov tree are
introduced in Section III. Finally, in Section IV, we describe a scheme for
propagating belief functions in qualitative Markov trees.
