Generalizing Logic-based Explanations for Machine Learning Classifiers via Optimization

Francisco Mateus Rocha Filho; Ajalmar Rêgo da Rocha Neto; Thiago Alves Rocha

cs.LOMar 2, 2026

Generalizing Logic-based Explanations for Machine Learning Classifiers via Optimization

Authors: Francisco Mateus Rocha Filho, Ajalmar Rêgo da Rocha Neto, Thiago Alves Rocha

Organizations: Instituto Federal de Educa¸c˜ao, Ciˆencia e Tecnologia do Cear´a (IFCE), Fortaleza, Brazil

Abstract

Machine learning models support decision-making, yet the reasons behind their predictions are opaque. Clear and reliable explanations help users make informed decisions and avoid blindly trusting model outputs. However, many existing explanation methods fail to guarantee correctness. Logic-based approaches ensure correctness but often offer overly constrained explanations, limiting coverage. Recent work addresses this by incrementally expanding explanations while maintaining correctness. This process is performed separately for each feature, adjusting both its upper and lower bounds. However, this approach faces a trade-off: smaller increments incur high computational costs, whereas larger ones may lead to explanations covering fewer instances. To overcome this, we propose two novel methods. Onestep builds upon this prior work, generating explanations in a single step for each feature and each bound, eliminating the overhead of an iterative process. Twostep takes a gradual approach, improving coverage. Experimental results show that Twostep significantly increases explanation coverage (by up to 72.60% on average across datasets) compared to Onestep and, consequently, to prior work.

Figures & tables

Figure 1: Example of how the range of a feature $f_{i}$ is computed with an incremental approach.

Figure 2: Example of how the range of a feature $f_{i}$ is computed with Onestep.

Figure 3: Illustration of how a partial range for $f_{i}$ is computed with Twostep.

Dataset	Acronym	Number of Features	Instances
Iris	IRIS	4	150
Blood Transfusion	BLDT	4	748
Banknote Authentication	BANK	4	1372
User Knowledge Modeling	UKMO	5	403
Vertebral Column	VRTC	6	310
Pima	PIMA	8	768

Table 1: Datasets details.

Dataset	Onestep	Twostep
	Onestep	T-Step $0.25$		T-Step $0.50$		T-Step $0.75$
	$\#M$	$\#M$	$\%M$	$\#M$	$\%M$	$\#M$	$\%M$
IRIS	0.017 $\pm$ 0.003	0.022 $\pm$ 0.004	29.41	0.022 $\pm$ 0.004	29.41	0.022 $\pm$ 0.004	29.41
BLDT	0.014 $\pm$ 0.004	0.015 $\pm$ 0.004	7.14	0.015 $\pm$ 0.003	7.14	0.015 $\pm$ 0.004	7.14
BANK	0.017 $\pm$ 0.004	0.023 $\pm$ 0.004	35.29	0.023 $\pm$ 0.004	35.29	0.023 $\pm$ 0.004	35.29
UKMO	0.018 $\pm$ 0.005	0.023 $\pm$ 0.006	27.78	0.023 $\pm$ 0.006	27.78	0.023 $\pm$ 0.006	27.78

Table 2: Average execution time results for SVM.

\#M

demotes the mean execution time along with the standard deviation.

\%M

represents the percentage increase in average execution time of Twostep compared to Onestep.

Dataset	Onestep	Twostep
	Onestep	T-Step $0.25$		T-Step $0.50$		T-Step $0.75$
	$\#M$	$\#M$	$\%M$	$\#M$	$\%M$	$\#M$	$\%M$
IRIS	0.16 $\pm$ 0.02	0.21 $\pm$ 0.04	28.83	0.20 $\pm$ 0.03	21.30	0.21 $\pm$ 0.04	26.51
BLDT	0.14 $\pm$ 0.01	0.16 $\pm$ 0.02	14.71	0.16 $\pm$ 0.02	13.87	0.16 $\pm$ 0.02	14.49
BANK	0.16 $\pm$ 0.02	0.20 $\pm$ 0.03	24.84	0.20 $\pm$ 0.03	26.58	0.20 $\pm$ 0.03	25.48
UKMO	0.18 $\pm$ 0.02	0.23 $\pm$ 0.04	28.25	0.23 $\pm$ 0.04	32.39	0.24 $\pm$ 0.05	33.33

Table 3: Average execution time results for MLP.

\#M

demotes the mean execution time along with the standard deviation.

\%M

represents the percentage increase in average execution time of Twostep compared to Onestep.

Dataset	Onestep	Twostep
	Onestep	T-Step $0.25$		T-Step $0.50$		T-Step $0.75$
	$\#M$	$\#M$	$\%M$	$\#M$	$\%M$	$\#M$	$\%M$
IRIS	30.41 $\pm$ 19.51	35.04 $\pm$ 15.35	15.23	35.56 $\pm$ 14.62	16.94	34.44 $\pm$ 15.87	13.25
BLDT	519.92 $\pm$ 94.91	520.85 $\pm$ 90.60	0.18	521.02 $\pm$ 89.80	0.21	520.89 $\pm$ 90.41	0.19
BANK	36.03 $\pm$ 36.37	49.60 $\pm$ 36.08	37.66	51.00 $\pm$ 36.77	41.55	46.57 $\pm$ 36.92	29.25
UKMO	38.29 $\pm$ 28.95	37.81 $\pm$ 27.69	-1.25	37.76 $\pm$ 27.57	-1.38	38.10 $\pm$ 28.12	-0.50

Table 4: Average coverage results for SVM.

\#M

denotes the mean dataset coverage with standard deviation.

\%M

represents the percentage improvement in mean dataset coverage of Twostep over Onestep.

Dataset	Onestep	Twostep
	Onestep	T-Step $0.25$		T-Step $0.50$		T-Step $0.75$
	$\#M$	$\#M$	$\%M$	$\#M$	$\%M$	$\#M$	$\%M$
IRIS	19.57 $\pm$ 14.48	21.81 $\pm$ 12.21	11.45	22.76 $\pm$ 11.81	16.30	22.65 $\pm$ 12.95	15.74
BLDT	149.55 $\pm$ 113.63	157.78 $\pm$ 122.77	5.50	162.46 $\pm$ 127.68	8.63	157.19 $\pm$ 122.89	5.11
BANK	25.15 $\pm$ 29.50	33.34 $\pm$ 31.56	32.56	33.85 $\pm$ 32.21	34.59	31.05 $\pm$ 31.59	23.46
UKMO	12.85 $\pm$ 10.93	13.91 $\pm$ 10.70	8.25	14.46 $\pm$ 10.99	12.53	14.14 $\pm$ 10.88	10.04

Table 5: Average coverage results for MLP.

\#M

denotes the mean dataset coverage with standard deviation.

\%M

represents the percentage improvement in mean dataset coverage of Twostep over Onestep.

Panel of Figure 4 — Figure 4: Distribution of dataset coverage improvement (%) achieved by Twostep over Onestep for SVM, with Twostep parameter fixed at $p=0.25$ . Red bars represent cases with worsened coverage, gray bars represent cases with same coverage, and the green bars represent cases with improved coverage. The best improvement and the worst deterioration are highlighted.

Panel of Figure 6 — Figure 6: Distribution of dataset coverage improvement (%) achieved by Twostep over Onestep for MLP, with Twostep parameter fixed at $p=0.25$ . Red bars represent cases with worsened coverage, gray bars represent cases with same coverage, and green bars represent cases with improved coverage. The best improvement and the worst deterioration are highlighted.

Panel of Figure 8 — Figure 8: Histogram of coverage improvement (%) achieved by Twostep over Onestep for synthetic data, with the SVM model and Twostep parameter fixed at $p=0.25$ . Red bars represent cases with worsened coverage, gray bars represent cases with same coverage, and green bars represent cases with improved coverage. The best improvement and the worst deterioration are highlighted.

Dataset	Onestep	Twostep
	Onestep	T-Step $0.25$		T-Step $0.50$		T-Step $0.75$
	$\#M$	$\#M$	$\%M$	$\#M$	$\%M$	$\#M$	$\%M$
IRIS	2.55 $\pm$ 0.43	2.52 $\pm$ 0.44	-1.18	2.52 $\pm$ 0.45	-1.18	2.53 $\pm$ 0.44	-0.78
BLDT	3.29 $\pm$ 0.11	3.29 $\pm$ 0.11	0.00	3.29 $\pm$ 0.11	0.00	3.29 $\pm$ 0.11	0.00
BANK	2.47 $\pm$ 0.13	2.48 $\pm$ 0.13	0.40	2.48 $\pm$ 0.13	0.40	2.48 $\pm$ 0.13	0.40
UKMO	3.55 $\pm$ 0.63	3.53 $\pm$ 0.62	-0.56	3.53 $\pm$ 0.62	-0.56	3.54 $\pm$ 0.62	-0.28

Table 6: Explanation range width results for SVM.

\#M

represents the mean range width with standard deviation.

\%M

is the percentage improvement in mean range width of Twostep over Onestep.

Dataset	Onestep	Twostep
	Onestep	T-Step $0.25$		T-Step $0.50$		T-Step $0.75$
	$\#M$	$\#M$	$\%M$	$\#M$	$\%M$	$\#M$	$\%M$
IRIS	2.09 $\pm$ 0.69	2.12 $\pm$ 0.65	1.44	2.14 $\pm$ 0.63	2.39	2.13 $\pm$ 0.65	1.91
BLDT	2.71 $\pm$ 0.27	2.72 $\pm$ 0.27	0.37	2.73 $\pm$ 0.27	0.74	2.72 $\pm$ 0.27	0.37
BANK	2.31 $\pm$ 0.29	2.33 $\pm$ 0.29	0.87	2.33 $\pm$ 0.29	0.87	2.32 $\pm$ 0.29	0.43
UKMO	3.27 $\pm$ 0.65	3.23 $\pm$ 0.64	-1.22	3.23 $\pm$ 0.63	-1.22	3.25 $\pm$ 0.62	-0.61

Table 7: Explanation range width results for MLP.

\#M

represents the mean explanation range width, along with standard deviation.

\%M

is the percentage improvement in mean range widht of Twostep over Onestep.

Explainable Artificial Intelligence

Explainable artificial intelligence develops ways to make AI decisions understandable, testable, and useful to people.

See all 326 papers

Probabilistic Linear Explanations
Sep 16, 2026Frederic Koriche, Jean-Marie Lagniez, Chi TranExplainable Artificial Intelligence Mixed-Integer QP
Computer science Research Institute of Lens (CRIL), UMR CNRS 8188, University of Artois, Rue Jean Souvraz SP 18, Lens, F-62307, France
Beyond Explaining Predictions: Logic-Based Explanations for Confidence in Machine Learning Models
Jun 9, 2026Vinícius Peixoto Chagas, Carlos Henrique Leitão Cavalcante, Thiago Alves RochaExplainable Artificial Intelligence Abductive Reasoning
Bound Propagation meets Constraint Simplification: Improving Logic-based XAI for Neural Networks
Mar 2, 2026Ronaldo Gomes, Jairo Ribeiro, Luiz Queiroz +1Explainable Artificial Intelligence Neural Network Interpretability
Department of Computer Science, Instituto Federal do Ceará (IFCE), Maracanaú, Brazil

Sep 16, 2026J/K move · Enter open · S save

Probabilistic Linear Explanations

Frederic Koriche, Jean-Marie Lagniez, Chi Tran

Computer science Research Institute of Lens (CRIL), UMR CNRS 8188, University of Artois, Rue Jean Souvraz SP 18, Lens, F-62307, France

Explainable Artificial Intelligence Mixed-Integer QP

Open paper AskPDF arXiv

Formal explainability provides mathematically grounded justifications for individual predictions. However, abductive explanations often exceed human cognitive limits by involving too many features, while probabilistic relaxations have remained largely limited to categorical classification. We present a unified framework for probabilistic explainability based on sparse, anchored linear models, applicable to both binary classification and continuous regression. By mapping instances to the Boolean hypercube, our linear explanations strictly generalize subset-based approaches: they capture both the magnitude and direction of feature contributions while enforcing a prescribed sparsity budget

k

. We show that minimizing the relevance error for such explanations is \ClassNPPP-hard when the underlying model is a neural network, and we relate this intractable objective to a tractable surrogate---the fidelity error. For a parameterized family of local distributions, the relevance error of any

k

-sparse explanation is bounded by its fidelity error up to a multiplicative factor that remains small locally. We address the resulting empirical problem using two complementary approaches: a Mixed Integer Programming (MIP) formulation that yields provably optimal empirical solutions while maintaining polynomial sample complexity, and a polynomial-time Iterative Hard Thresholding (IHT) algorithm with provable approximation guarantees. Empirical evaluations show that, unlike state-of-the-art baselines such as LIME and MAPLE, our explanations satisfy both the anchoring and sparsity constraints by construction, while consistently achieving lower relevance error.

Abstract

Explainable Artificial Intelligence

Explore similar work

Probabilistic Linear Explanations

Beyond Explaining Predictions: Logic-Based Explanations for Confidence in Machine Learning Models

Bound Propagation meets Constraint Simplification: Improving Logic-based XAI for Neural Networks