Research map / Learning theory and algorithms / Prediction and decision losses
Complete Search for Feature Selection in Decision Trees
Salvatore Ruggieri
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 |
|---|---|---|---|
| replace black-box sequential backward elimination with DTsbe (enumeration of distinct trees) | SBE · 20 UCI datasets (m=2) | elapsed time ratio: speedup in the range 2x - 100x | Improved |
| use DTsbe instead of SBE on high-dimensional datasets | SBE · Madelon, Isolet, Gisette, P53mutants, Arcene, Dexter | completes within 1h time-out: SBE >1h vs DTsbe 9.79 s on Madelon | Improved |
| use DTdistinct to avoid building duplicate trees | SBE enumeration · benchmark datasets | duplicate trees built: at most 0.035% duplicate trees | Improved |
| add heuristic feature selection (DTsbe) to decision trees | decision tree on all features · Adult, 10-fold CV | generalization error: 15.76 -> 14.45 | Improved |
| add complete search (DTaccept0, best subsets) instead of DTsbe | DTsbe · Adult | generalization error: 14.45 -> 14.30 | Improved |
| use complete search (DTaccept0) instead of heuristic DTsbe | DTsbe · Ionosphere and Anneal | generalization error: Ionosphere 9.77 -> 11.29 | Hurt |
| oversearching with complete search (ablation) | feature selection · Sonar | gap between estimated and generalization error: DTaccept0 estimated 2.12 vs generalization 26.40 | Hurt |
| add DTsbe feature selection before random forest | RF · Dexter | generalization error: 48.95 -> 43.59 | Improved |
| add DTsbe feature selection before random forest | RF · Madelon | generalization error: 36.25 -> 20.93 | Improved |
| add DTsbe feature selection before random forest | RF · Sonar | generalization error: 18.42 -> 23.26 | Hurt |
| use random forest instead of single decision tree with feature selection | DTsbe · 20 UCI datasets | generalization error: RF worse only on Hypo and Madelon | Improved |
| use all instances for training instead of splitting into build and search sets (ablation) | feature selection · Ionosphere, large m | generalization error: baseline best, then SBE, then best subsets | Improved |
Closest papers by meaning
- Enumerating Distinct Decision Trees (ICML 2017 · similarity 0.92)
- Optimal Decision Tree Pruning Revisited: Algorithms and Complexity (ICML 2025 · similarity 0.88)
- Improving Decision Trees through the Lens of Parameterized Local Search (NeurIPS 2025 · similarity 0.87)
- Learning Small Decision Trees with Few Outliers: A Parameterized Perspective (AAAI 2024 · similarity 0.87)
- Near-Optimal Decision Trees in a SPLIT Second (ICML 2025 · similarity 0.87)
- SORTeD Rashomon Sets of Sparse Decision Trees: Anytime Enumeration (NeurIPS 2025 · similarity 0.87)
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.
