TL;DR
This paper explores the concept of "forgetting" in abstract argumentation frameworks (AFs), a crucial aspect for efficient reasoning. The authors demonstrate that existing forgetting methods from logic programming don't directly translate to AFs and introduce a systematic study of desiderata and operations tailored for AFs, revealing both the limitations and potential of forgetting in this domain.
What Problem Does This Paper Address?
In knowledge representation and reasoning, "forgetting" refers to the process of removing certain elements (like variables or arguments) from a system while preserving as much of the relevant reasoning as possible. This is particularly useful for improving computational efficiency. While forgetting has been well-studied in formalisms like classical logic and logic programming, its application to abstract argumentation frameworks (AFs) is relatively new. Existing work in AFs has often overlooked key properties like "strong persistence" and "strong invariance." Furthermore, it's unclear if forgetting in AFs can be simply reduced to forgetting in logic programming. This paper aims to bridge this gap by providing a comprehensive analysis of forgetting in AFs, defining desiderata, and exploring the inherent limits and possibilities.
Methods
The paper proposes a systematic study of forgetting in abstract argumentation by:
- Defining Desiderata: A comprehensive set of desiderata for forgetting in AFs is introduced, generalizing concepts from logic programming and adapting them to the specifics of argumentation. These desiderata cover aspects like how extensions should be adjusted (e.g., removing forgotten arguments from them), how reasoning (skeptical and credulous) should be affected, and syntactic properties of the resulting framework.
- Analyzing Satisfiability: The authors investigate which of these desiderata can be satisfied, both individually and in combination, under various argumentation semantics (e.g., stable, grounded, preferred). This analysis reveals inherent limitations, particularly highlighting the unique behavior of stable semantics.
- Proposing Forgetting Operators: Two specific forgetting operators are presented: one that enforces the removal of forgotten arguments from extensions (e4) and another that aims to preserve adjusted extensions (e1), along with relaxations for the latter. These operators are designed to be compatible with specific desiderata.
- Investigating Dependencies: The paper maps out the relationships and implications between different desiderata, providing a clear picture of their interdependencies and identifying which combinations are satisfiable.
Datasets
Not discussed in the paper. The paper focuses on theoretical analysis and formal definitions rather than empirical evaluation on specific datasets.
Key Insights and Ideas
- Forgetting in AFs is Not Trivial: Forgetting in abstract argumentation cannot be directly reduced to forgetting in logic programming. Simple syntactic removal of arguments can lead to unintended consequences, such as making previously unaccepted arguments acceptable.
- Stable Semantics is Special: Stable semantics exhibits unique properties regarding forgetting. While many desiderata are unsatisfiable under other semantics, stable semantics allows for more flexibility and promising combinations, particularly when dealing with the removal of extensions.
- Iterative Forgetting Can Be Problematic: Applying forgetting operators for single arguments iteratively to forget a set of arguments might not yield an informationally economic or desirable result and can be sensitive to the order of forgetting.
- Desiderata Reveal Limits: The systematic study of desiderata highlights fundamental limitations. For instance, achieving "X-adjusted extensions" (e1) under stable semantics is challenging due to realizability constraints, forcing a consideration of relaxations.
- Syntactic vs. Semantic Forgetting: The paper distinguishes between syntactic approaches (e.g., directly manipulating the graph structure) and semantic approaches (e.g., adjusting extensions). Different desiderata capture these distinct philosophies.
Key Results
- Unsatisfiability of Key Combinations: Several combinations of desiderata, particularly those aiming for both adjusted extensions and compatibility with other reasoning modes, are shown to be unsatisfiable for most semantics.
- Satisfiability under Stable Semantics: The paper demonstrates that certain desirable combinations of desiderata, like {lo, esc} and {l1, esc}, are satisfiable under stable semantics, underscoring its unique role.
- Formal Dependencies: Proposition 1 and 2 provide a detailed map of the logical dependencies between various forgetting desiderata for different argumentation semantics.
- Proposed Operators: Algorithms are presented for two forgetting operators, one focusing on removing extensions containing forgotten arguments (e4) and another that aims to preserve adjusted extensions (e1) with relaxations.
Limitations and Future Work
- Focus on Stable Semantics: While the paper explores various semantics, the detailed analysis of forgetting operators is primarily focused on stable semantics. Future work could extend this to other semantics.
- Comparison of Iterative vs. One-Shot Forgetting: The paper notes that a detailed comparison between iteratively applying single-argument forgetting operators and a "one-shot" approach for forgetting sets of arguments is left for future work.
- Relaxations of e1: The paper suggests exploring relaxations of the e1 desideratum (preserving adjusted extensions) when it's not fully satisfiable, such as considering e3, e32, or esc. Further research is needed to determine the best relaxation strategy based on application context.
- Robustness Principles: The authors suggest that incorporating insights from robustness principles in argumentation (e.g., how structural changes affect labellings) could be fruitful for developing concrete forgetting operators.
Summary updated