Document Open Access Logo

Counterfactual Explanations via Inverse Constraint Programming

Authors Anton Korikov, J. Christopher Beck

PDF
Thumbnail PDF

File

LIPIcs.CP.2021.35.pdf
  • Filesize: 1.18 MB
  • 16 pages

Document Identifiers

Author Details

Anton Korikov
  • Department of Mechanical & Industrial Engineering, University of Toronto, Canada
J. Christopher Beck
  • Department of Mechanical & Industrial Engineering, University of Toronto, Canada

Funding

This research was supported by the Natural Sciences and Engineering Research Council of Canada.

Cite As Get BibTex

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) https://doi.org/10.4230/LIPIcs.CP.2021.35

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.

Subject Classification

ACM Subject Classification
  • Computing methodologies → Planning and scheduling
Keywords
  • Explanation
  • Inverse Optimization
  • Scheduling

Metrics

  • Access Statistics
  • Total Accesses (updated on a weekly basis)
    0
    PDF Downloads
    0
    Metadata Views

References

  1. B. Bogaerts, E. Gamba, J. Claes, and T. Guns. Step-wise explanations of constraint satisfaction problems. In 24th European Conference on Artificial Intelligence (ECAI), 2020. Google Scholar
  2. M. Brandao and D. Magazzeni. Explaining plans at scale: scalable path planning explanations in navigation meshes using inverse optimization. In Workshop on XAI, IJCAI-PRICAI, 2020. Google Scholar
  3. J. Burrell. How the machine ‘thinks’: Understanding opacity in machine learning algorithms. Big Data & Society, 3(1), 2016. Google Scholar
  4. T. C. Y. Chan and N. Kaw. Inverse optimization for the recovery of constraint parameters. European Journal of Operational Research, 282(2):415-427, 2020. Google Scholar
  5. J. W. Chinneck. Feasibility and Infeasibility in Optimization: Algorithms and Computational Methods. Number 118 in International Series in Operations Research and Management Sciences. Springer, 2008. Google Scholar
  6. M. Demange and J. Monnot. An introduction to inverse combinatorial problems. Paradigms of Combinatorial Optimization: Problems and New Approaches, pages 547-586, 2014. Google Scholar
  7. R. Eiffer, M. Cashmore, J. Hoffmann, D. Magazzeni, and M. Steinmetz. A New Approach to Plan-Space Explanation: Analyzing Plan-Property Dependencies in Oversubscription Planning. In AAAI. AAAI, 2020. Google Scholar
  8. K. Epstude and N. J. Roese. The functional theory of counterfactual thinking. Personality and social psychology review, 12(2):168-192, 2008. Google Scholar
  9. V. Eubanks. Automating inequality: How high-tech tools profile, police, and punish the poor. St. Martin’s Press, 2018. Google Scholar
  10. M. Fox, D. Long, and D. Magazzeni. Explainable Planning. CoRR, abs/1709.10256, 2017. URL: http://arxiv.org/abs/1709.10256.
  11. E. Freuder. Explaining ourselves: human-aware constraint reasoning. In AAAI, 2017. Google Scholar
  12. Global Constraint Catalogue. https://sofdem.github.io/gccat/. Accessed: 2021-08-5.
  13. C. Heuberger. Inverse combinatorial optimization: A survey on problems, methods, and results. Journal of combinatorial optimization, 8(3):329-361, 2004. Google Scholar
  14. U. Junker. Preferred explanations and relaxations for over-constrained problems. In AAAI, 2004. Google Scholar
  15. A. B Keha, K. Khowala, and J. W. Fowler. Mixed integer programming formulations for single machine scheduling problems. Computers & Industrial Engineering, 56(1):357-367, 2009. Google Scholar
  16. A. Korikov, A. Shleyfman, and C. Beck. Counterfactual explanations for optimization-based decisions in the context of the GDPR. In International Joint Conferences on Artificial Intelligence (IJCAI), 2021. Google Scholar
  17. J. K. Lenstra, A. R. Kan, and P. Brucker. Complexity of machine scheduling problems. In Annals of discrete mathematics, volume 1, pages 343-362. Elsevier, 1977. Google Scholar
  18. T. Miller. Explanation in artificial intelligence: Insights from the social sciences. Artificial Intelligence, 267:1-38, 2019. Google Scholar
  19. Parliament and Council of the European Union. Regulation (EU) 2016/679 of the European Parliament and of the Council of 27 April 2016 on the protection of natural persons with regard to the processing of personal data and on the free movement of such data, and repealing Directive 95/46/EC (General Data Protection Regulation), 2016. Google Scholar
  20. D. Pisinger, H. Kellerer, and U. Pferschy. Knapsack problems. Handbook of Combinatorial Optimization, page 299, 2013. Google Scholar
  21. C. Russell. Efficient search for diverse coherent explanations. In Proceedings of the Conference on Fairness, Accountability, and Transparency, pages 20-28, 2019. Google Scholar
  22. A. Sinha, P. Malo, and K. Deb. A review on bilevel optimization: from classical to evolutionary approaches and applications. IEEE Transactions on Evolutionary Computation, 22(2):276-295, 2017. Google Scholar
  23. M. H. Sqalli and E. C. Freuder. Inference-based constraint satisfaction supports explanation. In AAAI/IAAI, Vol. 1, pages 318-325, 1996. Google Scholar
  24. S. Verma, J. Dickerson, and K. Hines. Counterfactual explanations for machine learning: A review. arXiv preprint, 2020. URL: http://arxiv.org/abs/2010.10596.
  25. S. Wachter, B. Mittelstadt, and C. Russell. Counterfactual explanations without opening the black box: Automated decisions and the GDPR. Harv. JL & Tech., 31:841, 2017. Google Scholar
  26. L. Wang. Cutting plane algorithms for the inverse mixed integer linear programming problem. Operations Research Letters, 37(2):114-116, 2009. Google Scholar
  27. C. Yang, J. Zhang, and Z. Ma. Inverse maximum flow and minimum cut problems. Optimization, 40(2):147-170, 1997. Google Scholar
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
© 2023-2024 Schloss Dagstuhl – LZI GmbH About DROPS Imprint Privacy Contact