Evidential Reasoning Using DELIEF

AAAI 1988

TL;DR

This paper introduces DELIEF, an interactive system that simplifies the creation and analysis of belief function models for evidential reasoning. By allowing users to build graphical knowledge schemas and input evidence intuitively, DELIEF makes complex uncertainty management more accessible, bridging the gap between traditional Bayesian approaches and the flexibility of Dempster-Shafer theory.

What Problem Does This Paper Address?

Reasoning under uncertainty is a fundamental challenge in artificial intelligence and expert systems. Traditional logical formalisms struggle with incomplete, ambiguous, or contradictory information. While classical probability offers a framework, it often requires extensive statistical data that may not be available. The Dempster-Shafer theory of belief functions provides a powerful alternative, allowing for more nuanced representation of uncertainty and the combination of evidence from various sources. However, the computational complexity of Dempster's rule has historically limited its practical application. This paper addresses this by presenting DELIEF, a system designed to overcome these computational hurdles and provide a user-friendly interface for building and reasoning with belief function models.

Methods

DELIEF employs a graphical interface for users to construct knowledge schemas as networks of variables and joint variables. These schemas serve as the underlying structure for reasoning. The core of DELIEF's methodology lies in its implementation of the Dempster-Shafer theory of belief functions.

Key techniques include:

  • Graphical Knowledge Schemas: Users build models by creating nodes representing variables (with defined frames of possible answers) and edges representing relationships between them. Joint variables combine multiple individual variables.
  • Belief Functions: Evidence is represented as belief functions, which assign degrees of belief to subsets of a variable's frame. DELIEF allows for the input of m-values (basic probability assignments) for focal elements.
  • Markov Tree Propagation: To manage computational complexity, DELIEF embeds the graphical model into a Markov tree. This allows for efficient local combination of belief functions and propagation of results through the tree, inspired by recent advancements in Markov tree propagation schemes.
  • Unified Formalism: DELIEF implements both belief function analysis and Bayesian analysis within a single framework. Bayesian analysis is treated as a special case where probability transition matrices are converted into belief functions.

Datasets

Not discussed in the paper. The paper uses a hypothetical example from Lauritzen and Spiegelhalter (1988) to illustrate the system's functionality.

Key Insights and Ideas

  • Bridging the Gap: DELIEF effectively bridges the gap between the rigid structure of Bayesian networks and the flexible, yet computationally intensive, Dempster-Shafer theory.
  • User-Centric Design: The interactive graphical interface significantly lowers the barrier to entry for using belief functions, making complex uncertainty reasoning more accessible to domain experts.
  • Flexibility in Schema Design: Unlike traditional Bayesian approaches where schemas are data-driven and fixed, DELIEF allows users to start with educated guesses and iteratively refine both the schema structure and the evidence.
  • Handling Incomplete Evidence: The system is designed to provide meaningful answers even with partial evidence, a key advantage of belief functions over methods requiring complete probability distributions.
  • Bayesian as a Special Case: Unifying Bayesian and belief function analysis under one formalism simplifies implementation and allows users to choose the approach best suited to their data availability.

Key Results

The paper demonstrates DELIEF's capability through a hypothetical example involving medical diagnosis (dyspnoea, tuberculosis, lung cancer, bronchitis, smoking, Asia visit, X-ray results). The system successfully:

  • Allows users to create complex graphical models representing relationships between variables.
  • Enables the input of evidence as belief functions for individual variables.
  • Performs belief propagation efficiently using Markov trees.
  • Generates results for both belief function and Bayesian analyses, showing comparable outputs when appropriate.
  • The paper includes figures illustrating the Markov trees generated for propagation and the resulting belief distributions for variables, showcasing the system's output.

Limitations and Future Work

  • Computational Complexity: While DELIEF uses Markov trees to manage complexity, the paper acknowledges that Dempster's rule can still be computationally expensive, especially with large frames or complex dependencies. The efficiency is highly dependent on the structure of the embedded Markov tree.
  • User Interface Refinement: The paper focuses on the core functionality. Further enhancements to the user interface for more complex operations or visualizations could be beneficial.
  • Learning and Adaptation: The current system focuses on reasoning with a predefined schema and evidence. Future work could explore automated learning of schema structures or belief functions from data.
  • Handling Contradictory Evidence: While belief functions can handle conflicting evidence, the paper doesn't deeply explore advanced strategies for resolving or interpreting highly contradictory inputs beyond the standard Dempster-Shafer combination.

Summary updated

BibTeX
@inproceedings{1988evidential,
  title = {{Evidential Reasoning Using DELIEF}},
  booktitle = {AAAI Conference on Artificial Intelligence},
  year = {1988},
}
Figure