Hierarchical evidence and belief functions

Paul K. Black, Kathryn B. LaskeyUAI 1988

TL;DR

This paper tackles the challenge of representing and propagating uncertainty in rule-based AI systems using Dempster-Shafer (D/S) theory. It proposes and compares three methods for transforming conditional belief functions (derived from rules) into joint belief functions, which are necessary for propagation algorithms, highlighting that different methods can lead to different conclusions.

What Problem Does This Paper Address?

Automated reasoning systems often rely on rule-based knowledge representation, where rules assert a conclusion based on a set of conditions. To make these systems more robust, it's crucial to associate degrees of belief or certainty with these rules. While probabilistic models have been used, Dempster-Shafer (D/S) theory offers a compelling alternative for representing incomplete evidence – situations where evidence supports a hypothesis but doesn't definitively prove or disprove it.

A key challenge in applying D/S theory to rule-based systems is how to combine the individual beliefs associated with each rule into a coherent overall belief structure for the entire system. Specifically, propagation algorithms in D/S theory require a joint belief function over all variables. However, eliciting this full joint function directly is often impractical. The paper focuses on the problem of how to derive this joint belief function from simpler, more intuitive conditional belief functions that naturally arise from rule specifications.

Methods

The paper proposes and analyzes three distinct methods for extending conditional belief functions (representing the belief in a consequent given antecedents) and marginal belief functions (representing beliefs in root nodes) to a joint belief function over the cross-product space of variables. These methods are:

  • Conditional Embedding: This method treats each conditional belief function as an independent source of evidence. It's akin to applying Dempster's Rule to combine belief functions derived from each rule separately. This approach assumes independence between the evidential links.
  • Consonant Extension: This method assumes that the focal elements of the belief function form a nested chain of subsets. In the context of rules, it implies that the evidential links tend to be "valid together." This method is unique when given consonant conditional belief functions and results in a vacuous marginal belief function on the antecedents.
  • Dissonant Extension: This method represents an extreme of non-independence, where the validity of one evidential link is assumed to be inversely related to the validity of another.

The paper then demonstrates how these different methods of constructing the joint belief function lead to different marginal beliefs on the consequent variable when combined with incoming beliefs on the antecedents.

Datasets

Not discussed in the paper. The paper uses a hypothetical example of a company's decision to pay for a trip to a workshop.

Key Insights and Ideas

  • Rule-based systems and D/S theory: D/S theory is a promising framework for handling incomplete evidence in rule-based AI, but requires careful handling of how individual rule beliefs combine.
  • The ambiguity of joint belief function construction: Simply specifying conditional belief functions from rules is not sufficient to uniquely determine the joint belief function. Different methods of construction yield different results.
  • Independence assumptions matter: The choice of method (conditional embedding vs. consonant extension vs. dissonant extension) implicitly encodes assumptions about the independence or dependence of the evidential links within a rule.
  • Consonant extension's intuition: For simple cases with consonant conditional beliefs, the consonant extension method aligns well with intuitive reasoning about combined evidence.
  • Conditional embedding's generality: Conditional embedding is more general and can be applied regardless of the structure of the conditional belief functions, but its independence assumption can lead to "leaking" of belief to the universal set.
  • Need for "canonical stories": For D/S theory to be widely applicable in rule-based systems, knowledge engineers and experts need better frameworks ("canonical stories") for understanding and assessing the relationships (independence, dependence) between evidential links.

Key Results

The paper demonstrates through an example (a company's decision to pay for a trip based on paper acceptance) that the three proposed methods for constructing a joint belief function yield different marginal beliefs on the consequent variable (whether the company pays).

  • The consonant extension method, in the example, produced results that the authors believe most people's intuition would favor. It also aligns with the natural interval probability model.
  • Conditional embedding resulted in a different set of marginal beliefs, with a wider range of permissible belief on the consequent, due to its independence assumption.
  • Dissonant extension represented another extreme, leading to yet different belief distributions.

The paper shows that the range of permissible belief on the consequent variable varies across the methods, with consonant extension yielding a narrower range and conditional embedding a wider one.

Limitations and Future Work

  • Consonant extension limitation: The consonant extension method is limited to cases where the input conditional belief functions are consonant. This may restrict its applicability in more complex scenarios.
  • Understanding independence: The authors acknowledge a lack of clear understanding of what "independent" or "valid together" truly means in the context of evidential links, suggesting this is a fundamental issue for future research.
  • Need for generalizable methods: While consonant extension is intuitive for specific cases, a more general and compelling method for constructing joint belief functions is needed for broader application.
  • Developing "canonical stories": The authors emphasize the need for better frameworks to help experts and knowledge engineers assess the relationships between hypotheses in rule-based systems.
  • Assessing belief functions: The paper notes that assessing general belief functions is complex, requiring specification for each member of the power set, which sacrifices the simplicity of rule-based assessment.

The paper concludes by suggesting that, based on their analysis, the company in their example is likely to pay for the trip, encouraging readers to apply their own numbers to reach their conclusions.

Summary updated

BibTeX
@inproceedings{black1988hierarchical,
  author = {Paul K. Black and Kathryn B. Laskey},
  title = {{Hierarchical evidence and belief functions}},
  booktitle = {Conference on Uncertainty in Artificial Intelligence},
  year = {1988},
}
Figure