<div class="csl-bib-body">
<div class="csl-entry">Ordyniak, S., Paesani, G., & Szeider, S. (2023). The Parameterized Complexity of Finding Concise Local Explanations. In <i>Proceedings of the Thirty-Second International Joint Conference on Artificial Intelligence (IJCAI-23)</i> (pp. 3312–3320). International Joint Conferences on Artificial Intelligence. https://doi.org/10.24963/ijcai.2023/369</div>
</div>
-
dc.identifier.uri
http://hdl.handle.net/20.500.12708/190647
-
dc.description.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
dc.language.iso
en
-
dc.relation.ispartofseries
IJCAI
-
dc.subject
Knowledge Representation and Reasoning
en
dc.subject
Computational complexity of reasoning
en
dc.subject
Explainable/Interpretable machine learning
en
dc.title
The Parameterized Complexity of Finding Concise Local Explanations
en
dc.type
Inproceedings
en
dc.type
Konferenzbeitrag
de
dc.contributor.affiliation
University of Leeds, United Kingdom of Great Britain and Northern Ireland (the)
-
dc.contributor.affiliation
University of Leeds, United Kingdom of Great Britain and Northern Ireland (the)
-
dc.relation.isbn
978-1-956792-03-4
-
dc.relation.issn
1045-0823
-
dc.description.startpage
3312
-
dc.description.endpage
3320
-
dc.type.category
Full-Paper Contribution
-
tuw.booktitle
Proceedings of the Thirty-Second International Joint Conference on Artificial Intelligence (IJCAI-23)
-
tuw.book.ispartofseries
IJCAI
-
tuw.relation.publisher
International Joint Conferences on Artificial Intelligence
-
tuw.researchTopic.id
I1
-
tuw.researchTopic.name
Logic and Computation
-
tuw.researchTopic.value
100
-
tuw.publication.orgunit
E192-01 - Forschungsbereich Algorithms and Complexity
-
tuw.publisher.doi
10.24963/ijcai.2023/369
-
dc.description.numberOfPages
9
-
tuw.author.orcid
0000-0002-2383-1339
-
tuw.author.orcid
0000-0001-8994-1656
-
tuw.event.name
32nd International Joint Conference on Artificial Intelligence (IJCAI 2023)
en
tuw.event.startdate
19-08-2023
-
tuw.event.enddate
25-08-2023
-
tuw.event.online
On Site
-
tuw.event.type
Event for scientific audience
-
tuw.event.place
Macao
-
tuw.event.country
CN
-
tuw.event.presenter
Ordyniak, Sebastian
-
wb.sciencebranch
Informatik
-
wb.sciencebranch
Mathematik
-
wb.sciencebranch.oefos
1020
-
wb.sciencebranch.oefos
1010
-
wb.sciencebranch.value
80
-
wb.sciencebranch.value
20
-
item.languageiso639-1
en
-
item.openairetype
conference paper
-
item.grantfulltext
restricted
-
item.fulltext
no Fulltext
-
item.cerifentitytype
Publications
-
item.openairecristype
http://purl.org/coar/resource_type/c_5794
-
crisitem.author.dept
E192-01 - Forschungsbereich Algorithms and Complexity
-
crisitem.author.dept
University of Leeds
-
crisitem.author.dept
E192-01 - Forschungsbereich Algorithms and Complexity
