Research map / Learning theory and algorithms / Prediction and decision losses
Explaining Naive Bayes and Other Linear Classifiers with Polynomial Time and Delay
Joao Marques-Silva, Thomas Gerspacher, Martin Cooper, Alexey Ignatiev, Nina Narodytska
Read the paperCheck your idea against 137,217 papers
AI-extracted. The measured effects below were read by AI from the paper's full text (no summary yet). Numbers and claims can be wrong or missing context, so check the paper before you cite or build on it.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| Use XPXLC's direct PI-explanation enumeration instead of STEP's SDD enumeration | Naive Bayes Classifiers · NBC classifiers compilable within 2 hours | PI-explanation enumeration runtime: between 4 and 20 times slower than XPXLC | Improved |
| Use XPXLC instead of Anchor for instance-level explanation generation | Naive Bayes Classifiers · Instance-level explanation generation | runtime: Anchor takes 1.55 seconds; XPXLC never exceeds a few tens of μsec | Improved |
| Use XPXLC instead of SHAP for instance-level explanation generation | Naive Bayes Classifiers · Instance-level explanation generation | runtime: SHAP takes 99.58 seconds; XPXLC never exceeds a few tens of μsec | Improved |
| Use heuristic feature explanations rather than the most common features in enumerated PI-explanations | Anchor and SHAP · Adult and Spambase | overlap with common PI-explanation features: Anchor has zero overlap in more than 2000 instances | Mixed |
Closest papers by meaning
- Learning Global Probabilistic Explanations (NeurIPS 2026 · similarity 0.85)
- On the Tractability of SHAP Explanations (AAAI 2021 · similarity 0.85)
- Consistent Sufficient Explanations and Minimal Local Rules for explaining the decision of any classifier or regressor (NeurIPS 2022 · similarity 0.85)
- Data-centric Prediction Explanation via Kernelized Stein Discrepancy (ICLR 2025 · similarity 0.83)
- Position: Rethinking Explainable Machine Learning as Applied Statistics (ICML 2025 · similarity 0.83)
- Naive Bayes Classifiers over Missing Data: Decision and Poisoning (ICML 2024 · similarity 0.82)
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.
