Constraint-driven explanations for black box ML models

Aditya A. Shrotri, Nina Narodytska, Alexey Ignatiev, Kuldeep S. Meel, Joao Marques-Silva, Moshe Y. Vardi

Research output: Chapter in Book/Report/Conference proceedingConference PaperResearchpeer-review

10 Citations (Scopus)


The need to understand the inner workings of opaque Machine Learning models has prompted researchers to devise various types of post-hoc explanations. A large class of such explainers proceed in two phases: first perturb an input instance whose explanation is sought, and then generate an interpretable artifact to explain the prediction of the opaque model on that instance. Recently, Deutch and Frost proposed to use an additional input from the user: a set of constraints over the input space to guide the perturbation phase. While this approach affords the user the ability to tailor the explanation to their needs, striking a balance between flexibility, theoretical rigor and computational cost has remained an open challenge. We propose a novel constraint-driven explanation generation approach which simultaneously addresses these issues in a modular fashion. Our framework supports the use of expressive Boolean constraints giving the user more flexibility to specify the subspace to generate perturbations from. Leveraging advances in Formal Methods, we can theoretically guarantee strict adherence of the samples to the desired distribution. This also allows us to compute fidelity in a rigorous way, while scaling much better in practice. Our empirical study demonstrates concrete uses of our tool CLIME in obtaining more meaningful explanations with high fidelity.

Original languageEnglish
Title of host publication36th AAAI Conference on Artificial Intelligence (AAAI-22)
EditorsVasant Honavar, Matthijs Spaan
Place of PublicationPalo Alto CA USA
PublisherAssociation for the Advancement of Artificial Intelligence (AAAI)
Number of pages11
ISBN (Electronic)1577358767, 9781577358763
Publication statusPublished - 2022
EventAAAI Conference on Artificial Intelligence 2022 - Online, United States of America
Duration: 22 Feb 20221 Mar 2022
Conference number: 36th (Website) (Proceedings)

Publication series

NameProceedings of the 36th AAAI Conference on Artificial Intelligence, AAAI 2022
PublisherAssociation for the Advancement of Artificial Intelligence (AAAI)
ISSN (Print)2159-5399
ISSN (Electronic)2374-3468


ConferenceAAAI Conference on Artificial Intelligence 2022
Abbreviated titleAAAI 2022
Country/TerritoryUnited States of America
Internet address


  • Machine Learning (ML)
  • Constraint Satisfaction And Optimization (CSO)
  • Reasoning Under Uncertainty (RU)
  • Humans And AI (HAI)

Cite this