Abstract
In artificial intelligence and decision support systems, experts often express uncertainty through probability intervals rather than point estimates. This paper, originally presented at AAAI-91, investigates the conditions under which a set of probability intervals on individual events can be represented as a formal Dempster-Shafer belief function. We present the necessary and sufficient mathematical conditions for such a representation and introduce an efficient $O(n)$ algorithm for constructing a valid mass function or proving its non-existence.
Introduction
The Dempster-Shafer theory of evidence provides a robust framework for handling uncertainty by explicitly modeling "uncommitted" belief. However, a significant challenge arises when integrating expert intuition: human experts are typically more comfortable providing intervals (e.g., "the probability is between 0.3 and 0.5") than precise values. While a set of intervals might be probabilistically consistent—meaning a standard probability distribution exists within those bounds—it may not be "belief function consistent."
Lemmer and Kyburg demonstrate that in a three-event scenario, only about one-fifth of probabilistically consistent intervals can be mapped to a valid belief function. This discrepancy necessitates a rigorous method for checking consistency to prevent system failures in AI applications.
Mathematical Framework
The authors define a frame of discernment $\Theta$ consisting of mutually exclusive possibilities. For each possibility $e_i$, an expert provides an interval $[l_i, u_i]$. The core of the analysis rests on three variables:
- Interval Width ($s_i$): Defined as $s_i = u_i - l_i$, representing the degree of uncertainty for a specific event.
- Uncommitted Belief ($U$): The portion of total probability not assigned to any single event, calculated as $U = 1.0 - \sum l_i$.
- Total Uncertainty ($S$): The sum of all interval widths, $S = \sum s_i$.
The Existence of Belief Functions
The primary contribution of the paper is Theorem 1, which establishes the necessary and sufficient conditions for the existence of a belief function corresponding to a set of intervals. A belief function exists if and only if:
- $U \ge 0$: The sum of the lower bounds does not exceed 100%.
- $s_i \le U$ for all $i$: No single event's uncertainty exceeds the total uncommitted belief.
- $S \ge 2U$: The sum of all interval widths must be at least twice the uncommitted belief.
These conditions highlight the restrictive nature of belief functions compared to classical probability. The 'Region of Existence' shown in Figure 1 illustrates how these constraints carve out a specific volume within the geometric simplex of possible probability assignments. The labels $S=U$ and $S=2U$ in the figure correspond directly to the boundaries defined by the theorem.
The $O(n)$ Algorithm
To operationalize these findings, the authors provide a constructive proof in the form of a four-phase algorithm:
- Phase I: Assigns the lower bounds of belief ($l_i$) to each atomic event.
- Phases II & III: Iteratively adjusts mass assignments to satisfy upper probability constraints ($u_i$).
- Phase IV: Redistributes any remaining "improper" mass (initially assigned to the empty set) into subsets of size two, ensuring a proper basic probability assignment.
The algorithm's linear complexity, $O(n)$, where $n$ is the number of atoms, makes it suitable for real-time consistency checking in large-scale systems.
Key Insights and Discussion
The most striking takeaway is the "gap" between probability and belief. Many expert-provided intervals that seem reasonable under classical probability theory are mathematically impossible within the Dempster-Shafer framework. The uncommitted belief $U$ acts as a critical resource; if intervals are too wide or too narrow relative to $U$, the system becomes inconsistent.
Conclusion and Future Work
While this work provides a definitive solution for intervals placed on individual atoms, several avenues for future research remain. Currently, the framework does not account for intervals placed on subsets of events (e.g., "the probability of A or B is 0.6-0.8"). Extending the algorithm to handle such complex constraints and characterizing the entire set of consistent belief functions—rather than just finding one—are identified as key next steps.
Summary updated