TL;DR
This paper introduces novel methods for updating knowledge bases represented in Possibilistic Answer Set Programming (ASP), a framework that handles uncertainty. They propose two revision operators that incorporate new, certain information while minimizing changes to existing beliefs, offering both syntactic and semantic characterizations and analyzing their logical properties and complexity.
What Problem Does This Paper Address?
Reasoning with information from sources like the web often involves incomplete, imprecise, and uncertain data. Traditional belief revision methods, while well-established for classical logic, struggle with non-monotonic formalisms like Answer Set Programming (ASP), which are better suited for representing complex knowledge and handling uncertainty. This paper tackles the challenge of belief revision within Possibilistic ASP, specifically when new information is certain but the existing knowledge base has varying degrees of certainty. The goal is to update the knowledge base by incorporating the new information while minimally altering the existing beliefs, especially those with higher certainty, and ensuring the resulting knowledge base is consistent.
Methods
The paper proposes two main approaches to possibilistic ASP base revision:
- Standard Possibilistic ASP Base Revision ($\circledR_n$): This operator, inspired by existing work, restores consistency by removing rules with lower certainty degrees than those causing the inconsistency. It essentially "cuts" the knowledge base at a certain level of certainty.
- RSR Possibilistic ASP Base Revision ($\circledR_{RSR}$): This approach extends the "Removed Sets Revision" (RSR) strategy. It aims to remove the minimum number of the least certain rules from the original knowledge base that are involved in the inconsistency. This is a more fine-grained approach than the standard method, aiming to preserve more of the original, higher-certainty rules.
Both operators are given semantic characterizations in terms of possibilistic distributions, which represent the certainty of different interpretations of the knowledge base. The paper also analyzes the logical properties of these operators by adapting classical belief revision postulates (like Success, Inclusion, Consistency, Vacuity, Relevance, and Uniformity) to the possibilistic ASP context.
Datasets
Not discussed in the paper. The paper focuses on theoretical framework development and uses illustrative examples rather than empirical evaluation on datasets.
Key Insights and Ideas
- Bridging Uncertainty and Non-Monotonicity: The paper effectively combines the handling of uncertainty (via possibility theory) with the expressive power of non-monotonic ASP for belief revision. This is crucial for real-world applications where information is inherently uncertain.
- Two Flavors of Revision: The distinction between the "standard" approach (cutting at a certainty level) and the "RSR" approach (minimal removal of least certain rules) highlights different trade-offs between preserving certainty and minimizing structural change. The RSR approach is particularly interesting for its focus on preserving higher-certainty beliefs.
- Semantic Characterization is Key: Providing semantic characterizations of the revision operators allows for a deeper understanding of their behavior and equivalency to syntactic operations. This connects the abstract rules to the actual meaning (interpretations) of the knowledge base.
- Postulates for Possibilistic ASP: Adapting classical belief revision postulates to the possibilistic ASP setting provides a formal framework for evaluating the desirable properties of revision operators in this new context.
Key Results
- The paper defines two novel possibilistic ASP base revision operators: $\circledR_n$ and $\circledR_{RSR}(f)$.
- Semantic characterizations for both operators are provided, linking them to possibilistic distributions and consistency.
- The $\circledR_n$ operator is shown to be equivalent to a "cut" operation on the possibilistic distribution.
- The $\circledR_{RSR}(f)$ operator is shown to have a semantic counterpart based on "preferred models" and "preferred falsified rules," which aligns with minimizing the removal of rules involved in inconsistency.
- The $\circledR_n$ operator satisfies Inclusion, Consistency, and Vacuity but not Success, Relevance, or Uniformity.
- The $\circledR_{RSR}(f)$ operator, when defined, satisfies Success, Inclusion, Consistency, Vacuity, Relevance, and Uniformity.
- The complexity of checking for the existence of a removed set $R$ that leads to a consistent revised program is shown to be in DP and DP-complete.
Limitations and Future Work
- Complexity of $\circledR_n$: The paper acknowledges that the computational complexity of the $\circledR_n$ operator is an open question and a direction for future work.
- Certain Input Assumption: The current work assumes the input (new information) is certain ($n(r)=1$). Future work should extend these operators to handle uncertain input, leading to "semi-revision" operators.
- Exploring Other Revision Strategies: The authors suggest investigating other revision strategies from both possibility theory and ASP base revision literature.
- Other Possibilistic ASP Extensions: Extending the revision framework to other variants of possibilistic ASP is also proposed as future research.
Summary updated