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

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

2003-05-16

arxiv.org/abs/cs/0305014v1

International Journal of Approximate Reasoning 9(1) (1993) 37-73

Computer Science

Artificial Intelligence

37 pages, 12 figures

Scientific paper

For the case of evidence ordered in a complete directed acyclic graph this paper presents a new algorithm with lower computational complexity for Dempster's rule than that of step-by-step application of Dempster's rule. In this problem, every original pair of evidences, has a corresponding evidence against the simultaneous belief in both propositions. In this case, it is uncertain whether the propositions of any two evidences are in logical conflict. The original evidences are associated with the vertices and the additional evidences are associated with the edges. The original evidences are ordered, i.e., for every pair of evidences it is determinable which of the two evidences is the earlier one. We are interested in finding the most probable completely specified path through the graph, where transitions are possible only from lower- to higher-ranked vertices. The path is here a representation for a sequence of states, for instance a sequence of snapshots of a physical object's track. A completely specified path means that the path includes no other vertices than those stated in the path representation, as opposed to an incompletely specified path that may also include other vertices than those stated. In a hierarchical network of all subsets of the frame, i.e., of all incompletely specified paths, the original and additional evidences support subsets that are not disjoint, thus it is not possible to prune the network to a tree. Instead of propagating belief, the new algorithm reasons about the logical conditions of a completely specified path through the graph. The new algorithm is O(|THETA| log |THETA|), compared to O(|THETA| ** log |THETA|) of the classic brute force algorithm.

Affiliated with

Also associated with

No associations

Rating

Dempster's Rule for Evidence Ordered in a Complete Directed Acyclic Graph does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.

If you have personal experience with Dempster's Rule for Evidence Ordered in a Complete Directed Acyclic Graph, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Dempster's Rule for Evidence Ordered in a Complete Directed Acyclic Graph will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-545254