A Modification to Evidential Probability

Bülent Murtezaoglu, Henry E. Kyburg Jr.UAI 1991

TL;DR

This paper proposes a modification to Kyburg's Evidential Probability system to address the problem of selecting the most appropriate reference class when faced with conflicting probabilistic information. The new method aims to produce stronger statistical assertions by avoiding the undue weakening of conclusions caused by conflicting, but ultimately less informative, evidence.

What Problem Does This Paper Address?

When an agent needs to make a decision based on uncertain information, it often relies on probabilistic reasoning. Kyburg's Evidential Probability system provides a framework for this, but it struggles when multiple "reference classes" (sets of data) offer conflicting probabilities for the same event. For example, if you're deciding whether to eat a berry, you might have information about the edibility of red berries, soft berries, and berries from a specific region. If these statistics conflict, and you don't know how these categories relate (e.g., if all red berries are also soft), it's hard to pick the best piece of evidence. The paper tackles this "subset style dominance" problem, where the system might be forced to return a very weak, broad probability interval (like [0, 1]) because of conflicting evidence, even if some of the individual pieces of evidence are quite strong.

Methods

The authors propose a modified algorithm that refines Kyburg's approach. Kyburg's original method (Algorithm 1 in the paper) involves constructing "interval covers" of conflicting pairs of intervals. These covers represent the combined uncertainty from two conflicting sources. However, this can lead to wider, weaker intervals if one of the original intervals is very broad. The proposed solution (Algorithm 2) aims to mitigate this by "marking" and effectively disregarding intervals that are superseded by a narrower cover derived from conflicting evidence. This allows stronger conclusions to emerge without being unduly weakened by less informative, conflicting data. The core idea is to find the narrowest interval cover whose constituent intervals are not "challenged" by any other interval outside the cover.

Datasets

Not discussed in the paper. The paper uses a hypothetical "berries example" to illustrate its concepts.

Key Insights and Ideas

  • Conflicting evidence can unduly weaken conclusions: The paper highlights that simply taking the broadest possible interval cover of all conflicting evidence can lead to overly conservative and uninformative results, even when some individual pieces of evidence are strong.
  • Focus on "strongest consistent" evidence: The modified algorithm prioritizes finding a narrow interval that is consistent with a subset of the available evidence, rather than being forced to accommodate all conflicting evidence.
  • Semantics of interval covers: The authors suggest that interval covers can intuitively represent the combined uncertainty of conflicting evidence, and their modification aims to preserve the strength of strong evidence within these covers.
  • Computational efficiency: While not the primary focus, the proposed method is described as computationally cheap, making it practical for agents.

Key Results

The paper demonstrates that its modified algorithm (Algorithm 2) returns an interval that is "never in conflict with the one returned by the original and is at least as narrow." This means the new method produces results that are either the same or stronger (narrower intervals) than the original Kyburg approach. It specifically performs better in cases with:

  • No conflict between candidate intervals.
  • No nesting intervals (where one interval is completely contained within another).
  • Cases where narrowest intervals are at the extreme ends of wider intervals.

Limitations and Future Work

  • Computational complexity of Algorithm 1: The paper notes that Kyburg's original method (Algorithm 1) can be inefficient due to the need to repeatedly construct covers and mark intervals. While Algorithm 2 is presented as an improvement, a more efficient version (Algorithm 2') is also suggested.
  • "Marked" intervals interfering: A limitation of Algorithm 1 is that "marked" intervals (those that have been used to form a cover) can still interfere with the selection of narrower covers. The proposed Algorithm 2 addresses this by deleting marked elements.
  • Future work: The paper implies that further exploration of efficient algorithms for computing these interval covers and understanding their practical implications in agent decision-making would be valuable. The authors also acknowledge that their method is for a "restricted case" and more complex scenarios might require further development.

Summary updated

BibTeX
@inproceedings{murtezaoglu1991modification,
  author = {Bülent Murtezaoglu and Henry E. Kyburg Jr.},
  title = {{A Modification to Evidential Probability}},
  booktitle = {Conference on Uncertainty in Artificial Intelligence},
  year = {1991},
}
Figure