Implementing Dempster's rule for hierarchical evidence (Q1096411)

This article deals with Dempster-Shafer theory and gives an algorithm for an exact implementation of Dempster's rule when hypotheses can be arranged in a hierarchical or tree-like structure. Let \(\theta\) be a set of possible answers to some question, \(S_ 1\) and \(S_ 2\) random non- empty subsets of \(\theta\), \(Bel_ 1\) and \(Bel_ 2\) the belief functions corresponding to \(S_ 1\) and \(S_ 2\). The rule for forming \(Bel_ 1 \oplus Bel_ 2\) is Dempster's rule of combination. The amount of computation increases exponentially with the number of possible answers in a diagnostic problem, while in Gordon and Shortliffe's algorithm (1985) it is linear in its computational complexity. Here, an computationally efficient algorithm is suggested, which makes the approximation suggested by Gordon and Shortliffe unnecessary. In section 1, a survey of the mathematical aspects of the theory of belief functions is provided which is relevant for the algorithm. Dempster's principle, focal elements, simple support functions, dichotomous belief functions, and Bayesian belief functions are discussed. Barnett's technique is explained in terms of commonality functions. Barnett has shown that the number of computations of Dempster's rule increases only linearly. In section 2, the procedure of Gordon and Shortliffe is discussed. Their approximation is usually good when the degrees of support for the simple support functions are drawn at random from a uniform distribution. Examples for bad approximations are given. The procedure only assigns degrees of belief to subsets of \(\theta\), which correspond to tree nodes. The complements of these nodes are not assigned, thus plausibilities cannot be assigned to the nodes. In section 3, a generalization to a broader class of hypotheses is given (hierarchical evidence). Four lemmas are concerned with the position of \(\theta\). In section 4, the results of section 3 are used for the formulation of the new algorithm. The formulas for the numerical calculations of the algorithm are grouped into 6 subroutines. A comparison with Barnett's technique is given, a complexity analysis hints to the non-dependency on the size of the tree but only on the number of daughter nodes. Finally, in section 5 some hints concerning the generalization of diagnostic trees with general trees of partitions are provided.