Research map / Learning theory and algorithms / Prediction and decision losses
MEPSI: An MDL-Based Ensemble Pruning Approach with Structural Information
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 MEPSI, an MDL/Kolmogorov-complexity-based ensemble pruning method that trades off empirical error against algorithmic mutual information (approximated by tree edit similarity) among decision trees, with generalization bounds and experiments on 11 classification datasets.
Problem
Ensemble pruning typically relies only on the external behavior of learners on samples (empirical error or diversity), which may overfit; the paper asks whether the internal structure of individual learners should also guide pruning for better generalization.
Approach
Formulate ensemble pruning as a two-objective MDL problem that combines empirical error with the algorithmic mutual information among selected learners (structural information), approximated for decision trees by an edit similarity measure based on tree edit distance over internal nodes.
Key results
- MEPSI achieves top-three accuracy on 8 of 11 datasets among 14 methods (Table 1).
- MEPSI ranks first on average and significantly outperforms the other methods per the Friedman/Nemenyi test (Figure 2).
- Generalization bounds (Theorems 4.1 and 4.2) are given for the general and tree-based MEPSI, matching the proposed optimization objectives.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| Use MEPSI instead of Disagree pruning | CART decision tree ensemble pruning · Sklearn-digits | accuracy: 81.4±1.5 -> 82.1±1.7 | Helped |
| Use MEPSI instead of Disagree pruning | CART decision tree ensemble pruning · USPS | accuracy: 59.0±2.6 -> 59.1±2.2 | Helped |
| Use MEPSI instead of QStat pruning | CART decision tree ensemble pruning · Breast-cancer | accuracy: 79.5±0.4 vs 79.1±3.2 | Hurt |
| Use MEPSI instead of InAgree pruning | CART decision tree ensemble pruning · Breast-w | accuracy: 95.8±0.5 vs 95.6±0.9 | Hurt |
| Use MEPSI instead of TreeMat pruning | CART decision tree ensemble pruning · Vowel | accuracy: 44.6±4.0 vs 43.7±3.4 | Hurt |
| Use MEPSI instead of Kappa pruning | CART decision tree ensemble pruning · Mfeat-factors | accuracy: 79.1±3.9 -> 87.1±1.1 | Helped |
| Use MEPSI instead of TreeMat pruning | CART decision tree ensemble pruning · Splice | accuracy: 78.5±4.2 vs 68.9±4.7 | Hurt |
| Use MEPSI instead of QStat pruning | CART decision tree ensemble pruning · Credit-a | accuracy: 89.6±0.4 -> 89.8±0.0 | Helped |
| Use MEPSI instead of TreeMat pruning | CART decision tree ensemble pruning · Tic-tac-toe | accuracy: 83.6±1.9 vs 78.3±7.8 | Hurt |
| Use MEPSI instead of Disagree pruning | CART decision tree ensemble pruning · Vehicle | accuracy: 62.0±0.8 vs 61.9±0.9 | No clear effect |
| Use MEPSI instead of Boost pruning | CART decision tree ensemble pruning · Sick | accuracy: 96.8±1.2 vs 96.4±0.6 | No clear effect |
| Replace the competing pruning objectives with MEPSI's structural-information objective | CART decision tree ensemble pruning · 11 classification data sets | average rank | Helped |
Surprising findings
- MEPSI selects quite different sets of trees from other pruning methods, as indicated by low Jaccard indexes.
Limitations
- Method is practical for homogeneous ensembles only; hard to apply to heterogeneous ensembles due to lack of structural information metrics.
- Kolmogorov complexity is uncomputable, so the tree implementation relies on node counts and edit distance as approximations.
- Tree-based implementation depends on the assumption that node number approximates Kolmogorov complexity.
Experimental setup
Datasets: scikit-learn digits USPS Breast-cancer Breast-w Vowel Mfeat-factors Splice Credit-a Tic-tac-toe Vehicle Sick
Benchmarks: scikit-learn digits USPS Breast-cancer Breast-w Vowel Mfeat-factors Splice Credit-a Tic-tac-toe Vehicle Sick
Metrics: test accuracy average rank Friedman test with Nemenyi test Jaccard index
Baselines: Kappa pruning Orientation pruning Boosting-based pruning SDP-Relaxation HAC pruning Tree Match diversity pruning Q-Statistic pruning Disagreement pruning Entropy pruning KWVar pruning InAgree pruning Random selection
Builds on: Kappa pruning MDL principle Sun and Zhou 2018 tree edit distance diversity random forest
Closest papers by meaning
- Free Lunch in the Forest: Functionally-Identical Pruning of Boosted Tree Ensembles (AAAI 2025 · similarity 0.88)
- Data Pruning by Information Maximization (ICLR 2025 · similarity 0.85)
- Compressing tree ensembles through Level-wise Optimization and Pruning (ICML 2025 · similarity 0.85)
- Generalization Performance of Ensemble Clustering: From Theory to Algorithm (ICML 2025 · similarity 0.84)
- Ensemble Pruning for Out-of-distribution Generalization (ICML 2024 · similarity 0.84)
- Structure-informed Risk Minimization for Robust Ensemble Learning (ICML 2025 · similarity 0.83)
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.