Record link: 
http://hdl.handle.net/20.500.12708/190647
-
Title: 
The Parameterized Complexity of Finding Concise Local Explanations
en
Citation: 
Ordyniak, S., Paesani, G., & Szeider, S. (2023). The Parameterized Complexity of Finding Concise Local Explanations. In Proceedings of the Thirty-Second International Joint Conference on Artificial Intelligence (IJCAI-23) (pp. 3312–3320). International Joint Conferences on Artificial Intelligence. https://doi.org/10.24963/ijcai.2023/369
-
Publisher DOI: 
10.24963/ijcai.2023/369
-
Publication Type: 
Inproceedings - Full-Paper Contribution
en
Language: 
English
-
Authors: 
Ordyniak, Sebastian 
Paesani, Giacomo 
Szeider, Stefan 
-
Organisational Unit: 
E192-01 - Forschungsbereich Algorithms and Complexity 
-
Published in: 
Proceedings of the Thirty-Second International Joint Conference on Artificial Intelligence (IJCAI-23) 
-
ISBN: 
978-1-956792-03-4
-
Date (published): 
2023
-
Event name: 
32nd International Joint Conference on Artificial Intelligence (IJCAI 2023) 
en
Event date: 
19-Aug-2023 - 25-Aug-2023
-
Event place: 
Macao, China
-
Number of Pages: 
9
-
Publisher: 
International Joint Conferences on Artificial Intelligence
-
Peer reviewed: 
Yes
-
Keywords: 
Knowledge Representation and Reasoning; Computational complexity of reasoning; Explainable/Interpretable machine learning
en
Abstract: 
We consider the computational problem of finding a smallest local explanation (anchor) for classifying a given feature vector (example) by a black-box model. After showing that the problem is NP-hard in general, we study various natural restrictions of the problem in terms of problem parameters to see whether these restrictions make the problem fixedparameter tractable or not. We draw a detailed and systematic complexity landscape for combinations of parameters, including the size of the anchor, the size of the anchor’s coverage, and parameters that capture structural aspects of the problem instance, including rank-width, twin-width, and maximum difference.
en
Research Areas: 
Logic and Computation: 100%
-
Science Branch: 
1020 - Informatik: 80%
1010 - Mathematik: 20%
-
Appears in Collections:
Conference Paper

Show full item record

Page view(s)

111
checked on Dec 22, 2023

Google ScholarTM

Check