Structuring Bodies of Evidence

Sandra A. SandriUAI 1991

TL;DR

This paper introduces two novel structures, "partitioning by cardinality" and "Hierarchical Trees," to organize bodies of evidence in Dempster-Shafer theory. These structures significantly reduce the computational complexity of calculating belief measures and combining evidence, without sacrificing expressiveness or imposing restrictions on the data.

What Problem Does This Paper Address?

Dempster-Shafer (DS) theory is a powerful framework for representing and reasoning with uncertainty, particularly useful in knowledge-based systems. However, its practical application is often hindered by the significant computational complexity involved in its operations. The most notorious example is Dempster's rule of combination, which can have a worst-case complexity of $2^{2^n}$ (where $n$ is the size of the frame of discernment), making it intractable for even moderately sized problems. While existing algorithms aim to reduce this complexity, they often impose restrictive assumptions on the nature of the evidence or the frame of discernment. This paper addresses the need for efficient DS theory algorithms that work without these limitations, leveraging inherent set-theoretical properties of the evidence itself.

Methods

The paper proposes two main structuring methods:

  1. Partitioning by Cardinality: This approach organizes the focal elements (the specific pieces of evidence) within a body of evidence based on their size (cardinality). This allows for a more structured calculation of belief functions (Bel, Pl, Q) by processing elements in a specific order, reducing redundant computations.
  2. Hierarchical Trees: This more sophisticated structure represents the relationships between focal elements as a tree. Each node in the tree corresponds to a focal element, and its parent represents a superset, while its children represent subsets. This hierarchical organization allows for efficient calculation of belief measures and, crucially, Dempster's rule of combination. The construction of these trees leverages the lattice structure of the power set of the frame of discernment.

The paper also presents algorithms for:

  • Calculating belief measures (Bel, Pl, Q) using both partitioning and hierarchical trees.
  • Implementing Dempster's rule of combination using Hierarchical Trees, dividing the process into a pre-processing phase and a combination phase.

Datasets

Not discussed in the paper. The paper focuses on theoretical frameworks and algorithmic development rather than empirical evaluation on specific datasets.

Key Insights and Ideas

  • Leveraging Set-Theoretic Properties: The core idea is that the inherent set relationships between focal elements can be exploited to build efficient algorithms, rather than relying on external restrictions.
  • Hierarchical Trees as a Unified Structure: Hierarchical Trees are presented as a powerful structure that can simplify the calculation of belief measures and Dempster's rule, offering a more integrated approach.
  • Reducing Complexity Without Loss of Expressiveness: The proposed structures and algorithms avoid generating the entire power set of the frame of discernment, making them applicable even when the frame is not enumerable.
  • Pre-processing for Dempster's Rule: The introduction of a pre-processing step for Dempster's rule helps to reduce the size of the evidence sets before the main combination, further improving efficiency.

Key Results

The paper demonstrates that the proposed structuring methods significantly reduce computational complexity compared to brute-force approaches. While specific quantitative results are presented in terms of operations or node visits for various scenarios (e.g., calculating Q for $P(\Omega)$ with $|\Omega|=5$ is reduced from 961 to 211 operations using Hierarchical Trees), the primary takeaway is the potential for substantial speedups and the feasibility of applying DS theory to larger or more complex problems. The algorithms are shown to be more efficient as the size of the input bodies of evidence ($|F_1| \times |F_2|$) increases.

Limitations and Future Work

  • Complexity of Tree Construction: While the resulting algorithms are efficient, the construction of the Hierarchical Tree itself can still be computationally intensive, especially for large frames of discernment. The paper provides formulas for the cost of tree construction.
  • Comparison of Strategies: The paper suggests that the choice between brute-force and the Q-strategy (which uses commonality functions) should be guided by the relationship between $|P(\Omega)|$ and $|F_1| \times |F_2|$. If $|P(\Omega)|$ is enumerable and $|F_1| \times |F_2|$ is large, structuring the evidence is recommended.
  • Future Work: The paper mentions the use of Hierarchical Trees in "Local Propagation of Information" as a direction for future research, indicating that these structures have broader applicability within DS theory. The paper also notes that the effectiveness of the normalization step in Dempster's rule is a point of ongoing discussion.

Summary updated

BibTeX
@inproceedings{sandri1991structuring,
  author = {Sandra A. Sandri},
  title = {{Structuring Bodies of Evidence}},
  booktitle = {Conference on Uncertainty in Artificial Intelligence},
  year = {1991},
}
Figure