1 Search Results for "Korikov, Anton"


Document
Counterfactual Explanations via Inverse Constraint Programming

Authors: Anton Korikov and J. Christopher Beck

Published in: LIPIcs, Volume 210, 27th International Conference on Principles and Practice of Constraint Programming (CP 2021)


Abstract
It is increasingly recognized that automated decision making systems cannot be black boxes: users require insight into the reasons that decisions are made. Explainable AI (XAI) has developed a number of approaches to this challenge, including the framework of counterfactual explanations where an explanation takes the form of the minimal change to the world required for a user’s desired decisions to be made. Building on recent work, we show that for a user query specifying an assignment to a subset of variables, a counterfactual explanation can be found using inverse optimization. Thus, we develop inverse constraint programming (CP): to our knowledge, the first definition and treatment of inverse optimization in constraint programming. We modify a cutting plane algorithm for inverse mixed-integer programming (MIP), resulting in both pure and hybrid inverse CP algorithms. We evaluate the performance of these algorithms in generating counterfactual explanations for two combinatorial optimization problems: the 0-1 knapsack problem and single machine scheduling with release dates. Our numerical experiments show that a MIP-CP hybrid approach extended with a novel early stopping criteria can substantially out-perform a MIP approach particularly when CP is the state of the art for the underlying optimization problem.

Cite as

Anton Korikov and J. Christopher Beck. Counterfactual Explanations via Inverse Constraint Programming. In 27th International Conference on Principles and Practice of Constraint Programming (CP 2021). Leibniz International Proceedings in Informatics (LIPIcs), Volume 210, pp. 35:1-35:16, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2021)


Copy BibTex To Clipboard

@InProceedings{korikov_et_al:LIPIcs.CP.2021.35,
  author =	{Korikov, Anton and Beck, J. Christopher},
  title =	{{Counterfactual Explanations via Inverse Constraint Programming}},
  booktitle =	{27th International Conference on Principles and Practice of Constraint Programming (CP 2021)},
  pages =	{35:1--35:16},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-211-2},
  ISSN =	{1868-8969},
  year =	{2021},
  volume =	{210},
  editor =	{Michel, Laurent D.},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.CP.2021.35},
  URN =		{urn:nbn:de:0030-drops-153261},
  doi =		{10.4230/LIPIcs.CP.2021.35},
  annote =	{Keywords: Explanation, Inverse Optimization, Scheduling}
}
  • Refine by Author
  • 1 Beck, J. Christopher
  • 1 Korikov, Anton

  • Refine by Classification
  • 1 Computing methodologies → Planning and scheduling

  • Refine by Keyword
  • 1 Explanation
  • 1 Inverse Optimization
  • 1 Scheduling

  • Refine by Type
  • 1 document

  • Refine by Publication Year
  • 1 2021

Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail