Backward Responsibility in Transition Systems Using General Power Indices
Research output: Contribution to journal › Conference article › Contributed › peer-review
Contributors
Abstract
To improve reliability and the understanding of AI systems, there is increasing interest in the use of formal methods, e.g. model checking. Model checking tools produce a counterexample when a model does not satisfy a property. Understanding these counterexamples is critical for efficient debugging, as it allows the developer to focus on the parts of the program that caused the issue. To this end, we present a new technique that ascribes a responsibility value to each state in a transition system that does not satisfy a given safety property. The value is higher if the non-deterministic choices in a state have more power to change the outcome, given the behaviour observed in the counterexample. For this, we employ a concept from cooperative game theory – namely general power indices, such as the Shapley value – to compute the responsibility of the states. We present an optimistic and pessimistic version of responsibility that differ in how they treat the states that do not lie on the counterexample. We give a characterisation of optimistic responsibility that leads to an efficient algorithm for it and show computational hardness of the pessimistic version. We also present a tool to compute responsibility and show how a stochastic algorithm can be used to approximate responsibility in larger models. These methods can be deployed in the design phase, at runtime and at inspection time to gain insights on causal relations within the behavior of AI systems.
Details
Original language | English |
---|---|
Pages (from-to) | 20320-20327 |
Number of pages | 8 |
Journal | Proceedings of the AAAI Conference on Artificial Intelligence |
Volume | 38 |
Issue number | 18 |
Publication status | Published - 25 Mar 2024 |
Peer-reviewed | Yes |
Conference
Title | 38th AAAI Conference on Artificial Intelligence |
---|---|
Abbreviated title | AAAI-24 |
Conference number | 38 |
Duration | 20 - 27 February 2024 |
Website | |
Degree of recognition | International event |
Location | Vancouver Convention Centre |
City | Vancouver |
Country | Canada |
External IDs
ORCID | /0000-0002-5321-9343/work/160951234 |
---|---|
ORCID | /0000-0001-7047-3813/work/161890923 |
ORCID | /0000-0003-1724-2586/work/165453615 |
ORCID | /0000-0003-4829-0476/work/165453943 |
Keywords
ASJC Scopus subject areas
Keywords
- causality, Cooperative Game Theory