Dempster's Rule for Evidence Ordered in a Directed Acyclic Graph

摘要

Dempster-Shafer theory, which is a way to manage uncertain information, is basedupon the fact that one has evidences for and/or against one or more different propositions. Dempster-Shafer theory contains a rule for the fusion of these evidences, Dempster's rule. The report presents a new algorithm with lower computational complexity for Dempster's rule in the case of evidence ordered in a directed acyclic graph than for the classic step by step application of Dempster's rule. This is the problem when for every pair of evidences, one has an evidence against the simultaneous belief in both propositions. The original evidences are situated on the vertices and the new ones are situated on the intermediate edges. The new algorithm which reasons about complete paths through the graph is O(nx(4 sup n)), compared to O(2 sup n squared) of the classic algorithm. After having made a detailed presentation of the reasoning behind the new algorithm the authors conclude that it is feasible to reason without any approximation about complete paths through a directed acyclic graph not only for the smallest problems. The new algorithm was developed for an anti-submarine intelligence analysis system.