Efficient Search for Diverse Coherent Explanations
Abstract
This paper proposes new search algorithms for counterfactual explanations based upon mixed integer programming. We are concerned with complex data in which variables may take any value from a contiguous range or an additional set of discrete states. We propose a novel set of constraints that we refer to as a "mixed polytope" and show how this can be used with an integer programming solver to efficiently find coherent counterfactual explanations i.e. solutions that are guaranteed to map back onto the underlying data structure, while avoiding the need for brute-force enumeration. We also look at the problem of diverse explanations and show how these can be generated within our framework.
Integrity signals
Registry
Cites
Statistics
Claims the paper makes
Claims other papers make about this one
Each is checked against this paper’s own text: does it say what the citing paper says it does?
Counterfactual reasoning is claimed to be a key mechanism for explaining adaptive behavior in a changing environment.
“In addition, counterfactual reasoning is claimed to be a key mechanism for explaining adaptive behavior in a changing environment [25], [26].”
From A Survey of Contrastive and Counterfactual Explanation Generation Methods for Explainable Artificial Intelligence (2021) · cites this paper as [26]
Cites
"Why Should I Trust You?": Explaining the Predictions of Any Classifier
Ribeiro, M. T., Singh, S., & Guestrin, C. (2016) · Proceedings of the 22nd ACM SIGKDD International Conference on Knowledge Discovery and Data Mining · doi:10.1145/2939672.2939778 · Cited by 17,555 · see citing works
Braun, W. J., & Murdoch, D. J. (2021) · Cambridge University Press eBooks · doi:10.1017/9781108993456.011 · Cited by 14,099 · see citing works
Nocedal, J., & Wright, S. J. (1999) · Springer eBooks · doi:10.1007/b98874 · Cited by 9,563 · see citing works
An Automatic Method for Finding the Greatest or Least Value of a Function
Rosenbrock, H. H. (1960) · The Computer Journal · doi:10.1093/comjnl/3.3.175 · Cited by 2,981 · see citing works
Methods for interpreting and understanding deep neural networks
Montavon, G., Samek, W., & Müller, K.-R. (2018) · Digital Signal Processing · doi:10.1016/j.dsp.2017.10.011 · Cited by 2,665 · see citing works
Rule-Based Expert Systems: The MYCIN Experiments of the Stanford Heuristic Programming Project
(1986) · Telematics and Informatics · doi:10.1016/s0736-5853(86)80073-9 · Cited by 1,701 · see citing works
(2021) · doi:10.26226/morressier.60c8d83cbea1445efd9a1905 · Cited by 1,230 · see citing works
Mittelstadt, B., Russell, C., & Wachter, S. (2019) · Proceedings of the Conference on Fairness, Accountability, and Transparency · doi:10.1145/3287560.3287574 · Cited by 794 · see citing works
Self-citationNot Just a Black Box: Learning Important Features Through Propagating Activation DifferencesPreprint
Shrikumar, A., Greenside, P., Shcherbina, A., & Kundaje, A. B. (2016) · arXiv (Cornell University) · doi:10.48550/arxiv.1605.01713 · Cited by 704 · see citing works
'It's Reducing a Human Being to a Percentage': Perceptions of Justice in Algorithmic Decisions
Binns, R., Van Kleek, M., Veale, M., Lyngs, U., Zhao, J., & Shadbolt, N. (2018) · Proceedings of the 2018 CHI Conference on Human Factors in Computing Systems · doi:10.1145/3173574.3173951 · Cited by 691 · cited 6× · see citing works
“Binns et al. (2018) found evidence that users prefer counterfactual explanations over case-based reasoning.”
BackgroundInfluentialProceedings of the AMIA Symposium
Schulz, S., Daumke, P., Smith, B., & Hahn, U. (2005) · Cited by 606 · see citing works
Extracting Tree-Structured Representations of Trained Networks
Craven, M. W., & SHAVLIK, J. W. (1995) · Neural Information Processing Systems · Cited by 583 · see citing works
Actionable Recourse in Linear Classification
Ustun, B., Spangher, A., & Liu, Y. (2019) · Proceedings of the Conference on Fairness, Accountability, and Transparency · doi:10.1145/3287560.3287566 · Cited by 501 · see citing works
Assessing demand for intelligibility in context-aware applications
Lim, B. Y., & Dey, A. K. (2009) · Proceedings of the 11th international conference on Ubiquitous computing · doi:10.1145/1620545.1620576 · Cited by 246 · see citing works
The Bayesian Case Model: A Generative Approach for Case-Based Reasoning and Prototype Classification
Kim, B., Rudin, C. D., & Shah, J. (2014) · Cited by 185 · see citing works
Counterfactuals and Explanation
Kment, B. (2006) · Mind · doi:10.1093/mind/fzl261 · Cited by 111 · see citing works
Case-based explanation of non-case-based learning methods.
Caruana, R., Kangarloo, H., Dionisio, J. D. N., Sinha, U., & Johnson, D. (1999) · PubMed Central · Cited by 92 · see citing works
Ruben, D. (2015) · Routledge eBooks · doi:10.4324/9781315634739 · Cited by 34 · see citing works
Towards Extracting Faithful and Descriptive Representations of Latent Variable Models
Rockt, T., Riedel, S., & Singh, S. K. (2015) · National Conference on Artificial Intelligence · Cited by 28 · see citing works
Explaining Data-Driven Document Classifications
Martens, D., & Provost, F. J. (2013) · Faculty Digital Archive (New York University Florence) · Cited by 11 · see citing works
Flagged first, then by citations
Cited by
Sorted by citations
Explaining machine learning classifiers through diverse counterfactual explanations
Mothilal, R. K., Sharma, A., & Tan, C. (2020) · Proceedings of the 2020 Conference on Fairness, Accountability, and Transparency · doi:10.1145/3351095.3372850 · Cited by 1,233 · see citing works
A Survey on the Explainability of Supervised Machine Learning
Burkart, N., & Huber, M. F. (2021) · Journal of Artificial Intelligence Research · doi:10.1613/jair.1.12228 · Cited by 1,008 · see citing works
Manipulating and Measuring Model Interpretability
Poursabzi-Sangdeh, F., Goldstein, D. G., Hofman, J. M., Wortman Vaughan, J. W., & Wallach, H. (2021) · Proceedings of the 2021 CHI Conference on Human Factors in Computing Systems · doi:10.1145/3411764.3445315 · Cited by 728 · see citing works
Stepin, I., Alonso, J. M., Catala, A., & Pereira-Farina, M. (2021) · IEEE Access · doi:10.1109/access.2021.3051315 · Cited by 376 · see citing works
FACE: Feasible and Actionable Counterfactual Explanations
Poyiadzi, R., Sokol, K., Santos-Rodriguez, R., De Bie, T., & Flach, P. (2020) · Proceedings of the AAAI/ACM Conference on AI, Ethics, and Society · doi:10.1145/3375627.3375850 · Cited by 317 · see citing works
Chou, Y.-L., Moreira, C., Bruza, P., Ouyang, C., & Jorge, J. (2022) · Information Fusion · doi:10.1016/j.inffus.2021.11.003 · Cited by 302 · see citing works
Counterfactual Explanations and Algorithmic Recourses for Machine Learning: A Review
Verma, S., Boonsanong, V., Hoang, M., Hines, K. E., Dickerson, J. P., & Shah, C. (2020) · arXiv · doi:10.48550/arxiv.2010.10596 · Cited by 267 · see citing works
Amann, J., Vetter, D., Blomberg, S. N., Christensen, H. C., Coffee, M., Gerke, S., Gilbert, T. K., Hagendorff, T., Holm, S., Livne, M., et al. (2022) · PLOS Digital Health · doi:10.1371/journal.pdig.0000016 · Cited by 251 · see citing works
Sharma, S., Henderson, J., & Ghosh, J. (2020) · Proceedings of the AAAI/ACM Conference on AI, Ethics, and Society · doi:10.1145/3375627.3375812 · Cited by 226 · see citing works
Learning Model-Agnostic Counterfactual Explanations for Tabular Data
Pawelczyk, M., Broelemann, K., & Kasneci, G. (2020) · Proceedings of The Web Conference 2020 · doi:10.1145/3366423.3380087 · Cited by 167 · see citing works
Explainable Artificial Intelligence for Tabular Data: A Survey
Sahakyan, M., Aung, Z., & Rahwan, T. (2021) · IEEE Access · doi:10.1109/access.2021.3116481 · Cited by 135 · see citing works
“Russell [71] proposes a search algorithm and a set of constraints for counterfactuals based on mixed-integer programming.”
Background"Why is 'Chicago' deceptive?" Towards Building Model-Driven Tutorials for Humans
Lai, V., Liu, H., & Tan, C. (2020) · Proceedings of the 2020 CHI Conference on Human Factors in Computing Systems · doi:10.1145/3313831.3376873 · Cited by 123 · see citing works
Getting a CLUE: A Method for Explaining Uncertainty Estimates
Antorán, J., Bhatt, U., Adel, T., Weller, A., & Hernández-Lobato, J. M. (2021) · Apollo - University of Cambridge Repository · doi:10.17863/cam.69929 · Cited by 49 · see citing works
Unjustified Classification Regions and Counterfactual Explanations in Machine Learning
Laugel, T., Lesot, M.-J., Marsala, C., Renard, X., & Detyniecki, M. (2020) · Lecture Notes in Computer Science · doi:10.1007/978-3-030-46147-8_3 · Cited by 28 · see citing works
Algorithmic monoculture and social welfare
(2023) · The Societal Impacts of Algorithmic Decision-Making · doi:10.1145/3603195.3603202
- Authors
- Russell, C.
- Affiliations
- University of Surrey (GB)
- Corresponding author
- Russell, Chris
- ORCID
- Russell, Chris
- Venue
- Proceedings of the Conference on Fairness, Accountability, and Transparency
- Publisher
- ACM
- Published
- 2019-01-29
- Pages
- 20-28
- OpenAlex
- W2909392392
- Cited by
- 218
- References
- 21
- Citations by year
- 2026: 14 · 2025: 23 · 2024: 25 · 2023: 50 · 2022: 36 · 2021: 40 · 2020: 28 · 2019: 2
- FWCI
- 10.14
- Type
- conference paper
- Language
- en
- Open access
- closed
- Locations
- ACM Conference on Fairness, Accountability, and Transparency (FAccT) (publishedVersion)
- Topics
- Physical Sciences › Computer Science › Artificial Intelligence › Explainable Artificial Intelligence (XAI)
- Physical Sciences › Computer Science › Software › Software Testing and Debugging Techniques
- Physical Sciences › Computer Science › Artificial Intelligence › Privacy-Preserving Technologies in Data
- Keywords
- counterfactual explanations, mixed integer programming, explainable AI, search algorithms
About these checks
Registry, retraction, Cites and statistics results are computed, not judged, with one exception: a printed reference that no index lists is read once by a model before it counts as a citation error. Claims are extracted by a model and kept only when their quote appears verbatim in the text; each cited source is then checked, with a model’s help, for whether it says what the claim relies on. Those verdicts can be wrong — read the claim’s quote and the cited source before relying on one.
Statistics and arithmetic are recomputed, not judged.
Confidence bands are shown only for fields calibrated on our annotated test set. None is calibrated yet, so no band is shown.
What counts as a claim ›How we measure confidence ›How we check this ›
Are you an author, or do you see a problem with this page? Request a review
