Research map / Learning theory and algorithms / Prediction and decision losses
BoolXAI: Explainable AI Using Expressive Boolean Formulas
Read the paperCheck your idea against 108,967 papers
AI-extracted summary. Written by AI from the paper's full text. Numbers and claims can be wrong or missing context, so check the paper before you cite or build on it.
Proposes an interpretable classifier based on expressive Boolean formulas (with operators like AtLeast, AtMost, Choose) trained by simulated-annealing native local search with ILP/QUBO-powered non-local subtree moves.
Problem
Interpretable classification where rules are restricted to rigid rule lists, CNF/DNF or decision trees, which can become overly complex for simple rules such as AtLeast3 over features.
Approach
Searches directly over expressive Boolean formulas containing parameterized operators (AtLeast, AtMost, Choose) using a native simulated-annealing local solver, augmented with non-local moves that re-optimize subtrees via depth-one ILP or QUBO formulations that could run on specialized or quantum hardware.
Key results
- The native local rule classifier is generally competitive with the other classifiers evaluated on nine public datasets.
- Adding non-local ILP-powered moves achieves similar results with fewer iterations than local-only search.
- For max_num_literals around 10, the QUBO search space exceeds the ILP feasible space by more than 400 orders of magnitude.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| Use expressive Boolean formulas instead of a decision tree or CNF encoding for the AtLeast3 rule | AtLeast3 rule with five binary features · Synthetic five-feature rule example | complexity | Helped |
| Add parameterized operators such as AtLeast, AtMost, and Choose | Depth-one Boolean rule classifier · Breast Cancer | balanced accuracy | Helped |
| Add ILP-powered non-local subtree moves | SA native local rule classifier · Benchmark datasets | iterations to achieve similar results | Helped |
| Use the native local rule classifier rather than the considered alternative classifiers | SA native local rule classifier · Benchmark datasets | balanced accuracy | No clear effect |
Surprising findings
- QUBO-based depth-one classifiers generally underperformed the ILP classifier, since single bit-flip simulated annealing struggles with constrained QUBO landscapes.
- Dropping error variables from QUBO formulations gave similar or better accuracy-complexity curves and much shorter runtimes, potentially by orders of magnitude.
Limitations
- Hyperparameter optimization was minimal, so results may improve with tuning.
- Rows with missing values were removed, including 44% of Home Equity Default data.
- Speedup from quantum or specialized hardware is hypothesized rather than demonstrated; time-to-solution comparison left for future work.
Experimental setup
Datasets: Airline Customer Satisfaction Breast Cancer Credit Card Default Credit Risk Customer Churn Direct Marketing Home Equity Default Online Shoppers Intention Parkinsons
Benchmarks: Airline Customer Satisfaction Breast Cancer Credit Card Default Credit Risk Customer Churn Direct Marketing Home Equity Default Online Shoppers Intention Parkinsons
Metrics: balanced accuracy complexity time to solution
Baselines: Decision tree Single feature rule ILP rule SA native local rule
Builds on: simulated annealing CNF/DNF rule learning via ILP sequential counter encoding
Closest papers by meaning
- Navigating the Maze of Explainable AI: A Systematic Approach to Evaluating Methods and Metrics (NeurIPS 2024 · similarity 0.86)
- On Computing Probabilistic Explanations for Decision Trees (NeurIPS 2022 · similarity 0.85)
- Learning for Highly Faithful Explainability (ICLR 2026 · similarity 0.85)
- F-Fidelity: A Robust Framework for Faithfulness Evaluation of Explainable AI (ICLR 2025 · similarity 0.84)
- Even-if Explanations: Formal Foundations, Priorities and Complexity (AAAI 2025 · similarity 0.84)
- Everything, Everywhere, All at Once: Is Mechanistic Interpretability Identifiable? (ICLR 2025 · similarity 0.84)
Writing a paper in this area? scime draft is a free LaTeX editor with AI included, real-time co-authors and a check of your references and venue rules before you submit. It also imports OpenAI Prism projects.