On Validating, Repairing and Refining Heuristic ML Explanations

Alexey Ignatiev; Joao Marques-Silva; Nina Narodytska

arxiv: 1907.02509 · v1 · pith:HOE3P6CDnew · submitted 2019-07-04 · 💻 cs.LG · cs.AI· cs.LO

On Validating, Repairing and Refining Heuristic ML Explanations

Alexey Ignatiev , Nina Narodytska , Joao Marques-Silva This is my paper

Pith reviewed 2026-05-25 09:06 UTC · model grok-4.3

classification 💻 cs.LG cs.AIcs.LO

keywords machine learning explanationsheuristic explanationsboosted treesrigorous explanationsinstance spaceexplanation validationexplanation repair

0 comments

The pith

Heuristic explanations for boosted-tree predictions are inadequate for most instances when checked over the full instance space.

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

The paper extends rigorous explanation methods to boosted trees and uses them to test common heuristic approaches on multiple datasets. It finds that heuristic explanations fail to remain valid for the vast majority of instances once the entire space of possible inputs is taken into account. This result matters because heuristic methods are the default choice for explaining non-interpretable models, yet their outputs can be unreliable without exhaustive verification. The work also outlines steps for validating, repairing, and refining those heuristic outputs using the rigorous methods as reference.

Core claim

When rigorous methods are applied as ground truth, state-of-the-art heuristic explanations for boosted trees prove inadequate on most datasets and for the vast majority of instances once validity is required across the complete instance space.

What carries the argument

Rigorous explanation computation for boosted trees, serving as an exact reference to measure whether heuristic explanations hold everywhere.

If this is right

Heuristic explanations require post-processing or repair to restore validity over the full instance space.
Rigorous methods can be used to detect and correct failures in heuristic outputs for boosted trees.
Explanation quality must be assessed against the complete input space rather than local approximations alone.
Many current heuristic tools produce outputs that cannot be trusted without additional validation.

Where Pith is reading between the lines

These are editorial extensions of the paper, not claims the author makes directly.

Practical explanation pipelines may need to combine heuristic speed with periodic rigorous checks rather than relying on heuristics alone.
The gap between heuristic and rigorous outputs could motivate new hybrid algorithms that start heuristic and finish with targeted rigorous repair.
If the inadequacy pattern holds beyond the tested datasets, explanation reliability becomes a property of the method rather than the model.

Load-bearing premise

The rigorous methods correctly identify every valid and invalid explanation over the entire instance space.

What would settle it

A dataset and boosted-tree model where a standard heuristic explanation remains valid for every possible input instance, contrary to the reported failure rates on most datasets.

Figures

Figures reproduced from arXiv: 1907.02509 by Alexey Ignatiev, Joao Marques-Silva, Nina Narodytska.

read the original abstract

Recent years have witnessed a fast-growing interest in computing explanations for Machine Learning (ML) models predictions. For non-interpretable ML models, the most commonly used approaches for computing explanations are heuristic in nature. In contrast, recent work proposed rigorous approaches for computing explanations, which hold for a given ML model and prediction over the entire instance space. This paper extends earlier work to the case of boosted trees and assesses the quality of explanations obtained with state-of-the-art heuristic approaches. On most of the datasets considered, and for the vast majority of instances, the explanations obtained with heuristic approaches are shown to be inadequate when the entire instance space is (implicitly) considered.

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, simulated authors' rebuttal, and a circularity audit. Tearing a paper down is the easy half of reading it; the pith above is the substance, this is the friction.

Desk Editor's Note private letter to a colleague

This extends rigorous explanation methods to boosted trees and reports that heuristics fail for most instances on most datasets when checked over the full space.

read the letter

The main thing to know is that the paper takes prior rigorous explanation procedures, adapts them to boosted trees, and then measures how often common heuristic explanations hold up. The empirical finding is that on most datasets the heuristics are inadequate for the vast majority of instances once the entire input space is considered. That extension and the concrete comparison are the actual new pieces. The work is useful because it gives a direct, testable warning about relying on heuristics without further checks, and the model class is one that sees real use. The datasets and protocol are not described in the abstract, but the overall setup follows from the earlier rigorous line of work. The soft spot is exactly the one in the stress-test note: the result treats the rigorous outputs as ground truth. If those procedures have any gap in handling tree ensembles or counter-example enumeration, the reported inadequacy rates are not reliable. The paper does not appear to include an independent sanity check on the rigorous side, which leaves the central claim resting on that assumption. This is for readers already working on formal or explanation methods in ML, not for a general audience. A serious referee should see it because the claim is falsifiable, the extension is legitimate, and the empirical angle is worth checking even if revisions are needed on the validation side. I would send it to review.

Referee Report

1 major / 2 minor

Summary. The manuscript extends prior rigorous explanation techniques to boosted trees and compares them against state-of-the-art heuristic methods. It reports that, on most of the datasets examined, heuristic explanations are inadequate for the vast majority of instances when validity is assessed over the entire instance space.

Significance. If the rigorous procedures are sound, the empirical comparison would demonstrate concrete limitations of heuristic explanations for tree ensembles and motivate the use of validation/repair steps. The extension of rigorous methods to boosted trees is a useful technical step for the XAI literature.

major comments (1)

[Abstract and methodology description of rigorous methods] The headline claim (heuristics inadequate on most datasets for the vast majority of instances) treats the rigorous explanation procedures as a complete and correct oracle over the full instance space. No independent soundness argument, enumeration check, or verification experiment for these rigorous procedures on boosted trees is supplied, which is load-bearing for the measured inadequacy rates.

minor comments (2)

[Abstract] The abstract supplies no quantitative details on the number of datasets, models, or exact inadequacy percentages, making it difficult to assess the strength of the empirical claim.
[Introduction] Notation for the instance space and the precise definition of 'inadequate' should be introduced earlier and used consistently.

Simulated Author's Rebuttal

1 responses · 0 unresolved

Thank you for the careful review and for highlighting the importance of the soundness of the rigorous procedures. We address the major comment below and will revise the manuscript to strengthen the justification.

read point-by-point responses

Referee: The headline claim (heuristics inadequate on most datasets for the vast majority of instances) treats the rigorous explanation procedures as a complete and correct oracle over the full instance space. No independent soundness argument, enumeration check, or verification experiment for these rigorous procedures on boosted trees is supplied, which is load-bearing for the measured inadequacy rates.

Authors: We agree that the soundness of the rigorous methods is foundational to the empirical claims. These procedures extend the constraint-based exact explanation methods from prior work on single decision trees, where formal soundness was established. For boosted trees the extension adapts the encoding to the additive model output while preserving exact equivalence to the model's decision over the full instance space; the validity guarantees therefore carry over by construction. We acknowledge that the manuscript did not include an explicit soundness subsection or small-scale verification experiment for the boosted-tree case. In revision we will add a dedicated subsection detailing the soundness argument (including how base-case properties are preserved) and a limited verification experiment on synthetic data where full enumeration is feasible. revision: yes

Circularity Check

0 steps flagged

No circularity; empirical comparison to external rigorous methods

full rationale

The paper performs an empirical assessment of heuristic explanations against rigorous methods extended to boosted trees. No equations, derivations, fitted parameters, or self-referential definitions appear in the abstract or described claims. The central result (inadequacy of heuristics) is obtained by direct comparison rather than any reduction to inputs by construction. Prior work on rigorous methods is cited but functions as independent support for the ground truth, with no load-bearing self-citation chain or ansatz smuggling exhibited. The derivation chain is self-contained as a validation study.

Axiom & Free-Parameter Ledger

0 free parameters · 0 axioms · 0 invented entities

Abstract-only review; no methods, parameters, or assumptions are detailed enough to populate the ledger.

pith-pipeline@v0.9.0 · 5647 in / 1032 out tokens · 34060 ms · 2026-05-25T09:06:41.114986+00:00 · methodology

discussion (0)

Reference graph

Works this paper leans on

52 extracted references · 52 canonical work pages

[1]

In: NeurIPS

Adebayo, J., Gilmer, J., Muelly, M., Goodfellow, I.J., Hardt, M., Kim, B.: Sanity checks for saliency maps. In: NeurIPS. pp. 9525–9536 (2018)

work page 2018
[2]

In: NeurIPS

Alvarez-Melis, D., Jaakkola, T.S.: Towards robust interpretability with self-explaining neural networks. In: NeurIPS. pp. 7786–7795 (2018)

work page 2018
[3]

Angelino, E., Larus-Stone, N., Alabi, D., Seltzer, M., Rudin, C.: Learning certiﬁably optimal rule lists. In: KDD. pp. 35–44 (2017)

work page 2017
[4]

Journal of Machine Learning Research11, 1803– 1831 (2010)

Baehrens, D., Schroeter, T., Harmeling, S., Kawanabe, M., Hansen, K., M ¨uller, K.: How to explain individual classiﬁcation decisions. Journal of Machine Learning Research11, 1803– 1831 (2010)

work page 2010
[5]

In: Handbook of Model Checking., pp

Barrett, C., Tinelli, C.: Satisﬁability modulo theories. In: Handbook of Model Checking., pp. 305–343 (2018)

work page 2018
[6]

In: Biere, A., Heule, M., van Maaren, H., Walsh, T

Barrett, C.W., Sebastiani, R., Seshia, S.A., Tinelli, C.: Satisﬁability modulo theories. In: Biere, A., Heule, M., van Maaren, H., Walsh, T. (eds.) Handbook of Satisﬁability, Frontiers in Artiﬁcial Intelligence and Applications, vol. 185, pp. 825–885. IOS Press (2009)

work page 2009
[7]

Boutilier, C., Brafman, R.I., Domshlak, C., Hoos, H.H., Poole, D.: Cp-nets: A tool for repre- senting and reasoning with conditional ceteris paribus preference statements. J. Artif. Intell. Res. 21, 135–191 (2004)

work page 2004
[8]

In: SODA

Chandrasekaran, K., Karp, R.M., Moreno-Centeno, E., Vempala, S.: Algorithms for implicit hitting set problems. In: SODA. pp. 614–629 (2011)

work page 2011
[9]

Chen, T., Guestrin, C.: XGBoost: A scalable tree boosting system. In: KDD. pp. 785–794. ACM (2016)

work page 2016
[10]

In: NIPS

Craven, M., Shavlik, J.W.: Extracting tree-structured representations of trained networks. In: NIPS. pp. 24–30 (1995)

work page 1995
[11]

DARPA: DARPA explainable Artiﬁcial Intelligence (XAI) program (2016)

work page 2016
[12]

In: CA V

Dillig, I., Dillig, T., McMillan, K.L., Aiken, A.: Minimum satisfying assignments for SMT. In: CA V . pp. 394–409 (2012)

work page 2012
[13]

Eiter, T., Gottlob, G.: The complexity of logic-based abduction. J. ACM 42(1), 3–42 (1995)

work page 1995
[14]

EU Data Protection Regulation: Regulation (EU) 2016/679 of the European Parliament and of the Council (2016)

work page 2016
[15]

https://blog.fastforwardlabs.com/2017/ 03/09/fairml-auditing-black-box-predictive-models.html (2016)

Auditing black-box predictive models. https://blog.fastforwardlabs.com/2017/ 03/09/fairml-auditing-black-box-predictive-models.html (2016)

work page 2017
[16]

Feldman, M., Friedler, S.A., Moeller, J., Scheidegger, C., Venkatasubramanian, S.: Certify- ing and removing disparate impact. In: KDD. pp. 259–268. ACM (2015)

work page 2015
[17]

Constraints 23(3), 296–309 (2018)

Fischetti, M., Jo, J.: Deep neural networks and mixed integer linear optimization. Constraints 23(3), 296–309 (2018)

work page 2018
[18]

Friedler, S., Scheidegger, C., Venkatasubramanian, S.: On algorithmic fairness, discrimina- tion and disparate impact (2015)

work page 2015
[19]

In: CExAIIA (2017)

Frosst, N., Hinton, G.E.: Distilling a neural network into a soft decision tree. In: CExAIIA (2017)

work page 2017
[20]

Dover (2003)

Gallier, J.H.: Logic For Computer Science. Dover (2003)

work page 2003
[21]

AI Magazine 38(3), 50–57 (2017)

Goodman, B., Flaxman, S.R.: European Union regulations on algorithmic decision-making and a ”right to explanation”. AI Magazine 38(3), 50–57 (2017)

work page 2017
[22]

In: CA V

Huang, X., Kwiatkowska, M., Wang, S., Wu, M.: Safety veriﬁcation of deep neural networks. In: CA V . pp. 3–29 (2017)

work page 2017
[23]

In: ECAI

Ignatiev, A., Morgado, A., Marques-Silva, J.: Propositional abduction with implicit hitting sets. In: ECAI. pp. 1327–1335 (2016)

work page 2016
[24]

In: AAAI (2019) On Validating, Repairing and Reﬁning Heuristic ML Explanations 17

Ignatiev, A., Narodytska, N., Marques-Silva, J.: Abduction-based explanations for machine learning models. In: AAAI (2019) On Validating, Repairing and Reﬁning Heuristic ML Explanations 17

work page 2019
[25]

In: IJCAR

Ignatiev, A., Pereira, F., Narodytska, N., Marques-Silva, J.: A SAT-based approach to learn explainable decision sets. In: IJCAR. pp. 627–645 (2018)

work page 2018
[26]

In: CA V

Katz, G., Barrett, C.W., Dill, D.L., Julian, K., Kochenderfer, M.J.: Reluplex: An efﬁcient SMT solver for verifying deep neural networks. In: CA V . pp. 97–117 (2017)

work page 2017
[27]

In: NIPS

Kim, B., Shah, J.A., Doshi-Velez, F.: Mind the gap: A generative approach to interpretable feature selection and extraction. In: NIPS. pp. 2260–2268 (2015)

work page 2015
[28]

Kohavi, R.: Scaling up the accuracy of naive-bayes classiﬁers: A decision-tree hybrid. In: KDD. pp. 202–207 (1996)

work page 1996
[29]

Lakkaraju, H., Bach, S.H., Leskovec, J.: Interpretable decision sets: A joint framework for description and prediction. In: KDD. pp. 1675–1684 (2016)

work page 2016
[30]

In: AAAI

Li, O., Liu, H., Chen, C., Rudin, C.: Deep learning for case-based reasoning through proto- types: A neural network that explains its predictions. In: AAAI. pp. 3530–3537 (2018)

work page 2018
[31]

In: NIPS

Lundberg, S.M., Lee, S.: A uniﬁed approach to interpreting model predictions. In: NIPS. pp. 4768–4777 (2017)

work page 2017
[32]

Marques-Silva, J., Previti, A.: On computing preferred muses and mcses. In: SAT. pp. 58–74 (2014)

work page 2014
[33]

In: FAIR

Marquis, P.: Extending abduction from propositional to ﬁrst-order logic. In: FAIR. pp. 141– 155 (1991)

work page 1991
[34]

In: Handbook of Defeasible Reasoning and Uncertainty Management Systems, pp

Marquis, P.: Consequence ﬁnding algorithms. In: Handbook of Defeasible Reasoning and Uncertainty Management Systems, pp. 41–145 (2000)

work page 2000
[35]

Digital Signal Processing 73, 1–15 (2018)

Montavon, G., Samek, W., M ¨uller, K.: Methods for interpreting and understanding deep neural networks. Digital Signal Processing 73, 1–15 (2018)

work page 2018
[36]

In: TACAS

de Moura, L.M., Bjørner, N.: Z3: an efﬁcient SMT solver. In: TACAS. pp. 337–340 (2008)

work page 2008
[37]

In: IJCAI

Narodytska, N., Ignatiev, A., Pereira, F., Marques-Silva, J.: Learning optimal decision trees with SAT. In: IJCAI. pp. 1362–1368 (2018)

work page 2018
[38]

Ribeiro, M.T., Singh, S., Guestrin, C.: ”Why should I trust you?”: Explaining the predictions of any classiﬁer. In: KDD. pp. 1135–1144 (2016)

work page 2016
[39]

In: AAAI (2018)

Ribeiro, M.T., Singh, S., Guestrin, C.: Anchors: High-precision model-agnostic explana- tions. In: AAAI (2018)

work page 2018
[40]

AI Commun

Rosa, E.D., Giunchiglia, E.: Combining approaches for solving satisﬁability problems with qualitative preferences. AI Commun. 26(4), 395–408 (2013)

work page 2013
[41]

In: AAAI

Ross, A.S., Doshi-Velez, F.: Improving the adversarial robustness and interpretability of deep neural networks by regularizing their input gradients. In: AAAI. pp. 1660–1669 (2018)

work page 2018
[42]

In: IJCAI

Ross, A.S., Hughes, M.C., Doshi-Velez, F.: Right for the right reasons: Training differen- tiable models by constraining their explanations. In: IJCAI. pp. 2662–2670 (2017)

work page 2017
[43]

In: IJCAI

Ruan, W., Huang, X., Kwiatkowska, M.: Reachability analysis of deep neural networks with provable guarantees. In: IJCAI. pp. 2651–2659 (2018)

work page 2018
[44]

Saikko, P., Wallner, J.P., J ¨arvisalo, M.: Implicit hitting set algorithms for reasoning beyond NP. In: KR. pp. 104–113 (2016)

work page 2016
[45]

Inter- University Consortium for Political and Social Research (1988)

Schmidt, P., Witte, A.D.: Predicting recidivism in north carolina, 1978 and 1980. Inter- University Consortium for Political and Social Research (1988)

work page 1978
[46]

In: IJCAI

Shih, A., Choi, A., Darwiche, A.: A symbolic approach to explaining bayesian network clas- siﬁers. In: IJCAI. pp. 5103–5111 (2018)

work page 2018
[47]

Journal of Machine Learning Research 11, 1–18 (2010)

Strumbelj, E., Kononenko, I.: An efﬁcient explanation of individual classiﬁcations using game theory. Journal of Machine Learning Research 11, 1–18 (2010)

work page 2010
[48]

Data Knowl

Strumbelj, E., Kononenko, I., Robnik-Sikonja, M.: Explaining instance classiﬁcations with interactions of subsets of feature values. Data Knowl. Eng. 68(10), 886–904 (2009)

work page 2009
[49]

In: ASRU

Tan, S., Sim, K.C., Gales, M.J.F.: Improving the interpretability of deep neural networks with stimulated learning. In: ASRU. pp. 617–623. IEEE (2015) 18 Ignatiev et al

work page 2015
[50]

IEEE Trans

Umans, C., Villa, T., Sangiovanni-Vincentelli, A.L.: Complexity of two-level logic mini- mization. IEEE Trans. on CAD of Integrated Circuits and Systems25(7), 1230–1246 (2006)

work page 2006
[51]

In: ICDM

Wang, T., Rudin, C., Doshi-Velez, F., Liu, Y ., Klampﬂ, E., MacNeille, P.: Bayesian rule sets for interpretable classiﬁcation. In: ICDM. pp. 1269–1274 (2016)

work page 2016
[52]

In: AAAI

Wu, M., Hughes, M.C., Parbhoo, S., Zazzi, M., Roth, V ., Doshi-Velez, F.: Beyond sparsity: Tree regularization of deep models for interpretability. In: AAAI. pp. 1670–1678 (2018)

work page 2018

[1] [1]

In: NeurIPS

Adebayo, J., Gilmer, J., Muelly, M., Goodfellow, I.J., Hardt, M., Kim, B.: Sanity checks for saliency maps. In: NeurIPS. pp. 9525–9536 (2018)

work page 2018

[2] [2]

In: NeurIPS

Alvarez-Melis, D., Jaakkola, T.S.: Towards robust interpretability with self-explaining neural networks. In: NeurIPS. pp. 7786–7795 (2018)

work page 2018

[3] [3]

Angelino, E., Larus-Stone, N., Alabi, D., Seltzer, M., Rudin, C.: Learning certiﬁably optimal rule lists. In: KDD. pp. 35–44 (2017)

work page 2017

[4] [4]

Journal of Machine Learning Research11, 1803– 1831 (2010)

Baehrens, D., Schroeter, T., Harmeling, S., Kawanabe, M., Hansen, K., M ¨uller, K.: How to explain individual classiﬁcation decisions. Journal of Machine Learning Research11, 1803– 1831 (2010)

work page 2010

[5] [5]

In: Handbook of Model Checking., pp

Barrett, C., Tinelli, C.: Satisﬁability modulo theories. In: Handbook of Model Checking., pp. 305–343 (2018)

work page 2018

[6] [6]

In: Biere, A., Heule, M., van Maaren, H., Walsh, T

Barrett, C.W., Sebastiani, R., Seshia, S.A., Tinelli, C.: Satisﬁability modulo theories. In: Biere, A., Heule, M., van Maaren, H., Walsh, T. (eds.) Handbook of Satisﬁability, Frontiers in Artiﬁcial Intelligence and Applications, vol. 185, pp. 825–885. IOS Press (2009)

work page 2009

[7] [7]

Boutilier, C., Brafman, R.I., Domshlak, C., Hoos, H.H., Poole, D.: Cp-nets: A tool for repre- senting and reasoning with conditional ceteris paribus preference statements. J. Artif. Intell. Res. 21, 135–191 (2004)

work page 2004

[8] [8]

In: SODA

Chandrasekaran, K., Karp, R.M., Moreno-Centeno, E., Vempala, S.: Algorithms for implicit hitting set problems. In: SODA. pp. 614–629 (2011)

work page 2011

[9] [9]

Chen, T., Guestrin, C.: XGBoost: A scalable tree boosting system. In: KDD. pp. 785–794. ACM (2016)

work page 2016

[10] [10]

In: NIPS

Craven, M., Shavlik, J.W.: Extracting tree-structured representations of trained networks. In: NIPS. pp. 24–30 (1995)

work page 1995

[11] [11]

DARPA: DARPA explainable Artiﬁcial Intelligence (XAI) program (2016)

work page 2016

[12] [12]

In: CA V

Dillig, I., Dillig, T., McMillan, K.L., Aiken, A.: Minimum satisfying assignments for SMT. In: CA V . pp. 394–409 (2012)

work page 2012

[13] [13]

Eiter, T., Gottlob, G.: The complexity of logic-based abduction. J. ACM 42(1), 3–42 (1995)

work page 1995

[14] [14]

EU Data Protection Regulation: Regulation (EU) 2016/679 of the European Parliament and of the Council (2016)

work page 2016

[15] [15]

https://blog.fastforwardlabs.com/2017/ 03/09/fairml-auditing-black-box-predictive-models.html (2016)

Auditing black-box predictive models. https://blog.fastforwardlabs.com/2017/ 03/09/fairml-auditing-black-box-predictive-models.html (2016)

work page 2017

[16] [16]

Feldman, M., Friedler, S.A., Moeller, J., Scheidegger, C., Venkatasubramanian, S.: Certify- ing and removing disparate impact. In: KDD. pp. 259–268. ACM (2015)

work page 2015

[17] [17]

Constraints 23(3), 296–309 (2018)

Fischetti, M., Jo, J.: Deep neural networks and mixed integer linear optimization. Constraints 23(3), 296–309 (2018)

work page 2018

[18] [18]

Friedler, S., Scheidegger, C., Venkatasubramanian, S.: On algorithmic fairness, discrimina- tion and disparate impact (2015)

work page 2015

[19] [19]

In: CExAIIA (2017)

Frosst, N., Hinton, G.E.: Distilling a neural network into a soft decision tree. In: CExAIIA (2017)

work page 2017

[20] [20]

Dover (2003)

Gallier, J.H.: Logic For Computer Science. Dover (2003)

work page 2003

[21] [21]

AI Magazine 38(3), 50–57 (2017)

Goodman, B., Flaxman, S.R.: European Union regulations on algorithmic decision-making and a ”right to explanation”. AI Magazine 38(3), 50–57 (2017)

work page 2017

[22] [22]

In: CA V

Huang, X., Kwiatkowska, M., Wang, S., Wu, M.: Safety veriﬁcation of deep neural networks. In: CA V . pp. 3–29 (2017)

work page 2017

[23] [23]

In: ECAI

Ignatiev, A., Morgado, A., Marques-Silva, J.: Propositional abduction with implicit hitting sets. In: ECAI. pp. 1327–1335 (2016)

work page 2016

[24] [24]

In: AAAI (2019) On Validating, Repairing and Reﬁning Heuristic ML Explanations 17

Ignatiev, A., Narodytska, N., Marques-Silva, J.: Abduction-based explanations for machine learning models. In: AAAI (2019) On Validating, Repairing and Reﬁning Heuristic ML Explanations 17

work page 2019

[25] [25]

In: IJCAR

Ignatiev, A., Pereira, F., Narodytska, N., Marques-Silva, J.: A SAT-based approach to learn explainable decision sets. In: IJCAR. pp. 627–645 (2018)

work page 2018

[26] [26]

In: CA V

Katz, G., Barrett, C.W., Dill, D.L., Julian, K., Kochenderfer, M.J.: Reluplex: An efﬁcient SMT solver for verifying deep neural networks. In: CA V . pp. 97–117 (2017)

work page 2017

[27] [27]

In: NIPS

Kim, B., Shah, J.A., Doshi-Velez, F.: Mind the gap: A generative approach to interpretable feature selection and extraction. In: NIPS. pp. 2260–2268 (2015)

work page 2015

[28] [28]

Kohavi, R.: Scaling up the accuracy of naive-bayes classiﬁers: A decision-tree hybrid. In: KDD. pp. 202–207 (1996)

work page 1996

[29] [29]

Lakkaraju, H., Bach, S.H., Leskovec, J.: Interpretable decision sets: A joint framework for description and prediction. In: KDD. pp. 1675–1684 (2016)

work page 2016

[30] [30]

In: AAAI

Li, O., Liu, H., Chen, C., Rudin, C.: Deep learning for case-based reasoning through proto- types: A neural network that explains its predictions. In: AAAI. pp. 3530–3537 (2018)

work page 2018

[31] [31]

In: NIPS

Lundberg, S.M., Lee, S.: A uniﬁed approach to interpreting model predictions. In: NIPS. pp. 4768–4777 (2017)

work page 2017

[32] [32]

Marques-Silva, J., Previti, A.: On computing preferred muses and mcses. In: SAT. pp. 58–74 (2014)

work page 2014

[33] [33]

In: FAIR

Marquis, P.: Extending abduction from propositional to ﬁrst-order logic. In: FAIR. pp. 141– 155 (1991)

work page 1991

[34] [34]

In: Handbook of Defeasible Reasoning and Uncertainty Management Systems, pp

Marquis, P.: Consequence ﬁnding algorithms. In: Handbook of Defeasible Reasoning and Uncertainty Management Systems, pp. 41–145 (2000)

work page 2000

[35] [35]

Digital Signal Processing 73, 1–15 (2018)

Montavon, G., Samek, W., M ¨uller, K.: Methods for interpreting and understanding deep neural networks. Digital Signal Processing 73, 1–15 (2018)

work page 2018

[36] [36]

In: TACAS

de Moura, L.M., Bjørner, N.: Z3: an efﬁcient SMT solver. In: TACAS. pp. 337–340 (2008)

work page 2008

[37] [37]

In: IJCAI

Narodytska, N., Ignatiev, A., Pereira, F., Marques-Silva, J.: Learning optimal decision trees with SAT. In: IJCAI. pp. 1362–1368 (2018)

work page 2018

[38] [38]

Ribeiro, M.T., Singh, S., Guestrin, C.: ”Why should I trust you?”: Explaining the predictions of any classiﬁer. In: KDD. pp. 1135–1144 (2016)

work page 2016

[39] [39]

In: AAAI (2018)

Ribeiro, M.T., Singh, S., Guestrin, C.: Anchors: High-precision model-agnostic explana- tions. In: AAAI (2018)

work page 2018

[40] [40]

AI Commun

Rosa, E.D., Giunchiglia, E.: Combining approaches for solving satisﬁability problems with qualitative preferences. AI Commun. 26(4), 395–408 (2013)

work page 2013

[41] [41]

In: AAAI

Ross, A.S., Doshi-Velez, F.: Improving the adversarial robustness and interpretability of deep neural networks by regularizing their input gradients. In: AAAI. pp. 1660–1669 (2018)

work page 2018

[42] [42]

In: IJCAI

Ross, A.S., Hughes, M.C., Doshi-Velez, F.: Right for the right reasons: Training differen- tiable models by constraining their explanations. In: IJCAI. pp. 2662–2670 (2017)

work page 2017

[43] [43]

In: IJCAI

Ruan, W., Huang, X., Kwiatkowska, M.: Reachability analysis of deep neural networks with provable guarantees. In: IJCAI. pp. 2651–2659 (2018)

work page 2018

[44] [44]

Saikko, P., Wallner, J.P., J ¨arvisalo, M.: Implicit hitting set algorithms for reasoning beyond NP. In: KR. pp. 104–113 (2016)

work page 2016

[45] [45]

Inter- University Consortium for Political and Social Research (1988)

Schmidt, P., Witte, A.D.: Predicting recidivism in north carolina, 1978 and 1980. Inter- University Consortium for Political and Social Research (1988)

work page 1978

[46] [46]

In: IJCAI

Shih, A., Choi, A., Darwiche, A.: A symbolic approach to explaining bayesian network clas- siﬁers. In: IJCAI. pp. 5103–5111 (2018)

work page 2018

[47] [47]

Journal of Machine Learning Research 11, 1–18 (2010)

Strumbelj, E., Kononenko, I.: An efﬁcient explanation of individual classiﬁcations using game theory. Journal of Machine Learning Research 11, 1–18 (2010)

work page 2010

[48] [48]

Data Knowl

Strumbelj, E., Kononenko, I., Robnik-Sikonja, M.: Explaining instance classiﬁcations with interactions of subsets of feature values. Data Knowl. Eng. 68(10), 886–904 (2009)

work page 2009

[49] [49]

In: ASRU

Tan, S., Sim, K.C., Gales, M.J.F.: Improving the interpretability of deep neural networks with stimulated learning. In: ASRU. pp. 617–623. IEEE (2015) 18 Ignatiev et al

work page 2015

[50] [50]

IEEE Trans

Umans, C., Villa, T., Sangiovanni-Vincentelli, A.L.: Complexity of two-level logic mini- mization. IEEE Trans. on CAD of Integrated Circuits and Systems25(7), 1230–1246 (2006)

work page 2006

[51] [51]

In: ICDM

Wang, T., Rudin, C., Doshi-Velez, F., Liu, Y ., Klampﬂ, E., MacNeille, P.: Bayesian rule sets for interpretable classiﬁcation. In: ICDM. pp. 1269–1274 (2016)

work page 2016

[52] [52]

In: AAAI

Wu, M., Hughes, M.C., Parbhoo, S., Zazzi, M., Roth, V ., Doshi-Velez, F.: Beyond sparsity: Tree regularization of deep models for interpretability. In: AAAI. pp. 1670–1678 (2018)

work page 2018