Research map / Learning theory and algorithms / Prediction and decision losses
Optimizing Binary Decision Diagrams with MaxSAT for Classification
Read the paperCheck your idea against 108,967 papers
AI-extracted summary. Written by AI from the paper's title only (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 |
|---|---|---|---|
| Replace BDD1's classification constraints with BDD2's per-example feature-value variables and truth-table constraints (ablation) | SAT-based BDD learning · audiology, hold-out test, ratio=0.25 | encoding size (E_Size): 23.53 -> 6.81 | Helped |
| Replace BDD1's classification constraints with BDD2's per-example feature-value variables and truth-table constraints (ablation) | SAT-based BDD learning · audiology, hold-out test, ratio=0.25 | testing accuracy: 92.94 -> 92.45 | No clear effect |
| Use an ordered, reduced BDD representation instead of a decision tree | MaxSAT classification, mushroom, H=4 · mushroom, 5-fold cross-validation, H=4 | model size: 19.80 -> 9 | Helped |
| Use an ordered, reduced BDD representation instead of a decision tree | MaxSAT classification, car, H=2 · car, 5-fold cross-validation, H=2 | test accuracy: 85.53 -> 85.53 | No clear effect |
| Use the CART-selected feature subset to restrict the MaxSAT-BDD search (ablation) | MaxSAT-BDD · datasets with many features, cross-validation | testing accuracy | Mixed |
| Merge compatible subtrees to determine predictions at unobserved truth-table assignments (ablation) | MaxSAT-BDD · datasets, cross-validation | testing accuracy | No clear effect |
| Increase the depth limit (ablation) | MaxSAT-BDD · datasets, cross-validation | testing accuracy | Helped |
Closest papers by meaning
- Learning Minimum-Size BDDs: Towards Efficient Exact Algorithms (ICML 2025 · similarity 0.86)
- A Scalable Two Stage Approach to Computing Optimal Decision Sets (AAAI 2021 · similarity 0.86)
- Can Graph Neural Networks Learn to Solve the MaxSAT Problem? (Student Abstract) (AAAI 2023 · similarity 0.85)
- A General Theoretical Framework for Learning Smallest Interpretable Models (AAAI 2024 · similarity 0.83)
- Learning How to Cube (NeurIPS 2026 · similarity 0.82)
- BoolXAI: Explainable AI Using Expressive Boolean Formulas (AAAI 2025 · 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.