TL;DR
This paper proposes a novel framework for integrating Dempster-Shafer (DS) theory of evidence with knowledge representation (KR) systems. It defines "Dempster-Shafer Belief Bases" as abstract data types that leverage DS theory for representing belief strength and KR languages for representing knowledge itself, preserving the properties of both.
What Problem Does This Paper Address?
Traditional knowledge representation (KR) systems excel at representing factual knowledge but often struggle with uncertainty. While Dempster-Shafer (DS) theory provides a robust mathematical framework for handling uncertainty and combining evidence, it lacks the expressive power to represent the nuances of knowledge itself. For instance, DS theory might represent "normally, birds fly" and "smoke suggests fire" in a similar way, failing to capture the qualitative differences in these knowledge statements. This paper bridges this gap by proposing a way to represent knowledge using existing KR languages while using DS theory to quantify belief about that knowledge.
Methods
The core contribution is the definition of "Dempster-Shafer Belief Bases" (DS Belief Bases) as abstract data types. These bases are characterized by three primitive operations: Ask, Tell, and Empty.
- Propositions as the Bridge: The paper first defines "propositions" as abstract objects that form a Boolean algebra. These propositions serve as the common ground between the KR system and DS theory.
- KR System's Role: A KR system is used to provide a "meaning function" that maps sentences from its language to these abstract propositions. This function is crucial for translating linguistic knowledge into a form that DS theory can operate on.
- DS Theory for Belief: DS theory is then applied to these propositions. Belief masses are assigned to propositions, and DS theory's combination rules are used to update these beliefs when new evidence arrives.
- Two Modeling Approaches: The paper presents two ways to model propositions:
- Model-Theoretic: Propositions are represented as sets of possible worlds.
- Proof-Theoretic: Propositions are represented as sets of possible arguments (sets of sentences from which a proposition can be deduced).
- Abstract Data Type Operations:
Empty(): Initializes an empty belief base, assigning full belief to the tautology.
Ask(α, KB): Queries the belief in a proposition corresponding to sentenceαwithin a belief baseKB. It returns the belief and disbelief values.Tell(α, <x, xf>, KB): Updates the belief baseKBwith new evidence about sentenceα.xandxfrepresent the belief mass assigned toαbeing true and false, respectively. This operation uses Dempster's rule of combination.
Datasets
Not discussed in the paper. The paper focuses on a theoretical framework and provides examples using formal logic systems rather than specific datasets.
Key Insights and Ideas
- Decoupling Knowledge and Belief: The most significant insight is the clear separation between the representation of knowledge (handled by KR languages) and the representation of belief about that knowledge (handled by DS theory). This allows for richer knowledge representation without sacrificing the power of DS theory.
- Propositions as a Universal Language: By abstracting knowledge into propositions, the framework becomes independent of the specific KR system used. This promotes modularity and extensibility.
- Preservation of Properties: A key formal result is that DS Belief Bases preserve the properties of both the underlying KR system and DS theory, ensuring a sound integration.
- Bridging Syntax and Semantics: The framework effectively bridges the syntactic level of KR languages with the semantic level of propositions and the uncertainty quantification of DS theory.
- Flexibility in Proposition Modeling: The ability to model propositions using either possible worlds or proof-theoretic approaches makes the framework adaptable to different KR system formalizations.
Key Results
- Formal Definition of DS Belief Bases: The paper provides a formal definition of DS Belief Bases as abstract data types with well-defined operations (
Ask,Tell,Empty). - Lemma 3.1 and Theorem 3.1: These results demonstrate that DS Belief Bases "behave well," meaning they preserve the logical properties of the KR system and the combination properties of DS theory.
- Examples with FOL and M-KRYPTON: The paper illustrates the framework's practical application by showing how it can be instantiated with First-Order Logic (FOL) and M-KRYPTON, a hybrid KR system. These examples showcase how complex knowledge, including epistemic attitudes of multiple agents, can be represented and reasoned about under uncertainty.
Limitations and Future Work
- Computational Complexity: The paper acknowledges that the computational complexity of
Askoperations can be exponential in the number ofTelloperations performed, particularly when dealing with a large number of assumptions or possible arguments. This is inherent to Dempster's combination rule. - Practical Implementation: While the paper sketches an architecture for a modular system, the full implementation details and efficiency optimizations are left for future work. The paper suggests strategies like focusing on "reasonable" arguments and using ATMS for fragment reconstruction to mitigate complexity.
- Extensibility to Other Calculi: The authors note that the presented framework is extensible to other uncertainty calculi beyond DS theory, suggesting a general approach for integrating various reasoning mechanisms with KR systems.
- Further Exploration of KR Systems: The paper hints at the potential for integrating DS theory with a wider range of KR systems, including those with different semantic formalisms.
Summary updated