Inverse Problems for Gradual Semantics

Nir Oren, Bruno Yun, Srdjan Vesic, Murilo S. BaptistaIJCAI 2022 · DOI

TL;DR

This paper tackles the "inverse problem" in argumentation theory: given a desired ranking of arguments, can we find the initial weights that would produce this ranking using specific gradual semantics? The authors propose an algorithm to solve this for several weighted semantics and empirically evaluate its effectiveness, showing it can efficiently find valid weightings.

What Problem Does This Paper Address?

Abstract argumentation theory models reasoning as a system of arguments and their interactions (like attacks). "Gradual semantics" go beyond simply identifying "justified" arguments by assigning a numerical score (acceptability degree) to each argument, leading to a ranked order. Many such semantics exist, each with its own logic. Some advanced semantics, called "weighted semantics," require not only the argument structure but also initial "weights" assigned to each argument. These initial weights influence the final acceptability scores.

The problem this paper addresses is the inverse of the usual process. Instead of starting with weights and seeing what ranking emerges, the authors want to start with a desired ranking and figure out what initial weights would lead to it. This is crucial for applications like persuasion (finding arguments to emphasize to achieve a specific outcome) or preference elicitation (understanding what underlying beliefs would lead to a stated preference). The challenge lies in finding a systematic way to determine these weights, especially since the relationship between initial weights and final rankings can be complex and non-linear, depending heavily on the specific gradual semantics used.

Methods

The core of the paper is a two-phase algorithm designed to solve the inverse problem.

Phase 1: Computing Acceptability Degrees This phase focuses on determining achievable ranges for argument acceptability degrees based on the desired ranking and the properties of the chosen semantics. Arguments are grouped into sets where arguments within a set should have the same acceptability degree in the final ranking, and arguments in earlier sets should be ranked higher than those in later sets. For each set, the algorithm calculates a "minimal upper bound" – the lowest possible acceptability degree an argument in that set can achieve, given the worst-case scenario from its attackers. This helps establish a target range for each argument.

Phase 2: Finding the Initial Weights This phase uses the calculated acceptability degree ranges to find the actual initial weights. The authors employ a bisection method (a standard numerical technique for finding roots of equations) to iteratively adjust the initial weight of an argument until its computed acceptability degree (using the gradual semantics) matches its target value (derived from Phase 1). This process is repeated for all arguments. The paper also explores various strategies for selecting which argument to adjust at each step, aiming to minimize perturbations and ensure convergence.

The algorithm is designed to work with specific gradual semantics (σMB, σCB, σHC) that satisfy certain properties like continuity and strong monotonicity, which are crucial for the bisection method to guarantee a unique solution.

Datasets

Not discussed in the paper. The evaluation uses synthetically generated argumentation graphs (directed scale-free, small world (Erdos-Renyi), and complete graphs) of varying sizes.

Key Insights and Ideas

  • The Inverse Problem is Solvable (for some semantics): The paper demonstrates that for a class of weighted gradual semantics (σMB, σCB, σHC), it's possible to find initial weights that produce a desired argument ranking. This opens up new avenues for applying argumentation theory in practical scenarios.
  • Bisection Method is Key: The bisection method, a robust numerical technique, is effectively adapted to find the specific initial weights needed to achieve target acceptability degrees. Its efficiency is a significant advantage.
  • Semantic Properties Matter: The success of the inverse problem approach hinges on properties of the gradual semantics, such as continuity and strong monotonicity. The paper identifies these as necessary conditions for a unique solution.
  • Strategic Argument Selection is Important: The choice of which argument's weight to adjust at each step in Phase 2 significantly impacts the algorithm's performance and success rate. Selecting arguments based on the largest error (difference between current and target acceptability) proved to be the most effective strategy in their evaluation.

Key Results

  • The proposed algorithm successfully found weightings for all tested graph topologies and semantics (σMB, σCB, σHC).
  • Empirical evaluation showed that, when using the "largest error first" strategy, each argument's weight was typically adjusted at most twice by the bisection method before convergence. This indicates the algorithm is efficient and scalable.
  • The runtime of the algorithm grows super-linearly with graph size, which is attributed to the increased cost of evaluating the semantics themselves on larger graphs.
  • Optimizing the bounds for the bisection method had minimal impact on runtime, highlighting the inherent speed of the bisection convergence.
  • The paper provides theoretical properties (continuity, uniqueness) for the studied semantics and conjectures strong monotonicity and bounded continuity, which are crucial for guaranteeing a unique solution to the inverse problem.

Limitations and Future Work

  • Analytical Proofs: While empirical results strongly suggest that σMB, σHC, and σCB satisfy the necessary properties (strong monotonicity and bounded continuity), analytical proofs are still missing and are identified as a critical avenue for future work.
  • Total Rankings: The current approach assumes a total desired ranking. Extending it to handle partial rankings is mentioned as a trivial extension in terms of input but would lead to a combinatorial explosion in the number of possibilities to consider.
  • Other Semantics: The algorithm and analysis are focused on a specific set of semantics. Investigating its applicability to other weighted semantics, including probabilistic or bipolar ones, is a natural next step.
  • Argument Selection Strategies: While a successful strategy was identified, exploring other argument selection heuristics could further optimize performance.
  • Applications: The paper acknowledges potential applications in persuasion and preference elicitation but does not delve into specific use cases, leaving this for future research.

Summary updated

BibTeX
@inproceedings{oren2022inverse,
  author = {Nir Oren and Bruno Yun and Srdjan Vesic and Murilo S. Baptista},
  title = {{Inverse Problems for Gradual Semantics}},
  booktitle = {International Joint Conference on Artificial Intelligence},
  year = {2022},
  doi = {10.24963/ijcai.2022/377},
}
Figure