Efficiently Explaining CSPs with Unsatisfiable Subset Optimization

Emilio Gamba; Bart Bogaerts; Tias Guns

doi:10.24963/ijcai.2021/191

Efficiently Explaining CSPs with Unsatisfiable Subset Optimization

Emilio Gamba, Bart Bogaerts, Tias Guns

Research output: Chapter in Book/Report/Conference proceeding › Conference paper

1 Citation (Scopus)

63 Downloads (Pure)

Abstract

Recently, a novel method for explaining solutions of constraint satisfaction problems was proposed.
An explanation in that method is a sequence of simple inference steps, where the simplicity of an inference step depends on the number and types of constraints used, eventually explaining all logical consequences of the problem.
The current paper tackles two questions left in builds on these formal foundations and tackles two trailing questions: namely how to generate explanations that are provably optimal (with respect to the given cost metric) and how to generate them efficiently.
To answer these questions, we develop 1) an implicit hitting set algorithm for finding optimal unsatisfiable subsets; 2) a method to reduce multiple calls for (optimal) unsatisfiable subsets to a single call that takes constraints on the subset into account, and 3) a method for re-using relevant information over multiple calls to these algorithms.

Original language	English
Title of host publication	Efficiently Explaining CSPs with Unsatisfiable Subset Optimization
Editors	Zhi-Hua Zhou
Publisher	IJCAI
Chapter	Main Track
Pages	1381-1388
Number of pages	8
ISBN (Electronic)	978-0-9992411-9-6
DOIs	https://doi.org/10.24963/ijcai.2021/191
Publication status	Published - 2021
Event	30th International Joint Conference on Artificial Intelligence (IJCAI-21): IJCAI-21 - Canada, Montreal, Canada Duration: 21 Aug 2021 → 26 Aug 2021 https://ijcai-21.org/

Publication series

Name	IJCAI International Joint Conference on Artificial Intelligence
ISSN (Print)	1045-0823

Conference

Conference	30th International Joint Conference on Artificial Intelligence (IJCAI-21)
Abbreviated title	IJCAI 2021
Country	Canada
City	Montreal
Period	21/08/21 → 26/08/21
Internet address	https://ijcai-21.org/

Keywords

Weighted Unsatisfiable Subsets
constraint satisfaction
Algorithm
Explainable AI
Artificial intelligence

Access to Document

10.24963/ijcai.2021/191Licence: Unspecified

0191Final published version, 197 KBLicence: Unspecified

2 Active

FWOAL1002: FRESCO: A FRamework for Explainable Solving and Constraint Optimization
Bogaerts, B. & Guns, T.
1/01/21 → 31/12/24
Project: Fundamental
VLAAI1: Subsidie: Onderzoeksprogramma Artificiële Intelligentie (AI) Vlaanderen
Nowe, A. & Vanderborght, B.
1/07/19 → 31/12/23
Project: Applied

1 Citations
1 Conference paper
1 Article

A framework for step-wise explaining how to solve constraint satisfaction problems
Bogaerts, B., Gamba, E. & Guns, T., Nov 2021, In: Artificial Intelligence. 300, 103550.
Research output: Contribution to journal › Article › peer-review

Open Access
File
2 Citations (Scopus)

39 Downloads (Pure)
Step-wise Explanations of Constraint Satisfaction Problems
Bogaerts, B., Gamba, E., Guns, T. & Claes, J., 24 Aug 2020, ECAI 2020 - 24th European Conference on Artificial Intelligence, including 10th Conference on Prestigious Applications of Artificial Intelligence, PAIS 2020 - Proceedings. De Giacomo, G., Catala, A., Dilkina, B., Milano, M., Barro, S., Bugarin, A. & Lang, J. (eds.). IOS Press, Vol. 325. p. 640-647 8 p. (Frontiers in Artificial Intelligence and Applications; vol. 325).
Research output: Chapter in Book/Report/Conference proceeding › Conference paper

Open Access
File
5 Citations (Scopus)

78 Downloads (Pure)

Cite this

@inproceedings{f1b08ae67d094ca8b2c3c0aa940c38eb,

title = "Efficiently Explaining CSPs with Unsatisfiable Subset Optimization",

abstract = "Recently, a novel method for explaining solutions of constraint satisfaction problems was proposed.An explanation in that method is a sequence of simple inference steps, where the simplicity of an inference step depends on the number and types of constraints used, eventually explaining all logical consequences of the problem.The current paper tackles two questions left in builds on these formal foundations and tackles two trailing questions: namely how to generate explanations that are provably optimal (with respect to the given cost metric) and how to generate them efficiently.To answer these questions, we develop 1) an implicit hitting set algorithm for finding optimal unsatisfiable subsets; 2) a method to reduce multiple calls for (optimal) unsatisfiable subsets to a single call that takes constraints on the subset into account, and 3) a method for re-using relevant information over multiple calls to these algorithms. ",

keywords = "Weighted Unsatisfiable Subsets, constraint satisfaction, Algorithm, Explainable AI, Artificial intelligence",

author = "Emilio Gamba and Bart Bogaerts and Tias Guns",

year = "2021",

doi = "10.24963/ijcai.2021/191",

language = "English",

series = "IJCAI International Joint Conference on Artificial Intelligence",

publisher = "IJCAI",

pages = "1381--1388",

editor = "Zhi-Hua Zhou",

booktitle = "Efficiently Explaining CSPs with Unsatisfiable Subset Optimization",

note = "30th International Joint Conference on Artificial Intelligence (IJCAI-21) : IJCAI-21, IJCAI 2021 ; Conference date: 21-08-2021 Through 26-08-2021",

url = "https://ijcai-21.org/",

}

Gamba, E , Bogaerts, B & Guns, T 2021, Efficiently Explaining CSPs with Unsatisfiable Subset Optimization. in Z-H Zhou (ed.), Efficiently Explaining CSPs with Unsatisfiable Subset Optimization ., 191, IJCAI International Joint Conference on Artificial Intelligence, IJCAI, pp. 1381-1388, 30th International Joint Conference on Artificial Intelligence (IJCAI-21), Montreal, Canada, 21/08/21. https://doi.org/10.24963/ijcai.2021/191

Efficiently Explaining CSPs with Unsatisfiable Subset Optimization. / Gamba, Emilio ; Bogaerts, Bart ; Guns, Tias.

Efficiently Explaining CSPs with Unsatisfiable Subset Optimization . ed. / Zhi-Hua Zhou. IJCAI, 2021. p. 1381-1388 191 (IJCAI International Joint Conference on Artificial Intelligence).

Research output: Chapter in Book/Report/Conference proceeding › Conference paper

TY - GEN

T1 - Efficiently Explaining CSPs with Unsatisfiable Subset Optimization

AU - Gamba, Emilio

AU - Bogaerts, Bart

AU - Guns, Tias

PY - 2021

Y1 - 2021

N2 - Recently, a novel method for explaining solutions of constraint satisfaction problems was proposed.An explanation in that method is a sequence of simple inference steps, where the simplicity of an inference step depends on the number and types of constraints used, eventually explaining all logical consequences of the problem.The current paper tackles two questions left in builds on these formal foundations and tackles two trailing questions: namely how to generate explanations that are provably optimal (with respect to the given cost metric) and how to generate them efficiently.To answer these questions, we develop 1) an implicit hitting set algorithm for finding optimal unsatisfiable subsets; 2) a method to reduce multiple calls for (optimal) unsatisfiable subsets to a single call that takes constraints on the subset into account, and 3) a method for re-using relevant information over multiple calls to these algorithms.

AB - Recently, a novel method for explaining solutions of constraint satisfaction problems was proposed.An explanation in that method is a sequence of simple inference steps, where the simplicity of an inference step depends on the number and types of constraints used, eventually explaining all logical consequences of the problem.The current paper tackles two questions left in builds on these formal foundations and tackles two trailing questions: namely how to generate explanations that are provably optimal (with respect to the given cost metric) and how to generate them efficiently.To answer these questions, we develop 1) an implicit hitting set algorithm for finding optimal unsatisfiable subsets; 2) a method to reduce multiple calls for (optimal) unsatisfiable subsets to a single call that takes constraints on the subset into account, and 3) a method for re-using relevant information over multiple calls to these algorithms.

KW - Weighted Unsatisfiable Subsets

KW - constraint satisfaction

KW - Algorithm

KW - Explainable AI

KW - Artificial intelligence

UR - https://github.com/ML-KULeuven/ocus-explain

UR - http://www.scopus.com/inward/record.url?scp=85111208290&partnerID=8YFLogxK

U2 - 10.24963/ijcai.2021/191

DO - 10.24963/ijcai.2021/191

M3 - Conference paper

T3 - IJCAI International Joint Conference on Artificial Intelligence

SP - 1381

EP - 1388

BT - Efficiently Explaining CSPs with Unsatisfiable Subset Optimization

A2 - Zhou, Zhi-Hua

PB - IJCAI

T2 - 30th International Joint Conference on Artificial Intelligence (IJCAI-21)

Y2 - 21 August 2021 through 26 August 2021

ER -

Efficiently Explaining CSPs with Unsatisfiable Subset Optimization

Abstract

Publication series

Conference

Keywords

Access to Document

Fingerprint

Projects

FWOAL1002: FRESCO: A FRamework for Explainable Solving and Constraint Optimization

VLAAI1: Subsidie: Onderzoeksprogramma Artificiële Intelligentie (AI) Vlaanderen

Research output

A framework for step-wise explaining how to solve constraint satisfaction problems

Step-wise Explanations of Constraint Satisfaction Problems

Cite this