Research map / Adversarial robustness and security / Certified and empirical robustness
Cultivating Archipelago of Forests: Evolving Robust Decision Trees Through Island Coevolution
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 ICoEvoRDF, an island-based coevolutionary algorithm that evolves robust decision tree forests with migration between islands and Nash-equilibrium-based voting weights, outperforming prior robust tree/forest methods on adversarial accuracy and minimax regret across 20 datasets.
Problem
Decision trees and tree ensembles lack robustness to adversarial perturbations; existing robust tree construction methods rely on single-population evolution or single robustness metrics and struggle to maintain ensemble diversity.
Approach
Runs multiple islands, each coevolving a population of decision trees and a population of input perturbations, with periodic migration of top trees between neighboring islands, and weights the final forest by a mixed Nash equilibrium computed between island representative trees and perturbations.
Key results
- ICoEvoRDF (with Nash voting and distinct per-island inputs) achieves average adversarial accuracy 0.784 vs 0.775 for PRAdaBoost and 0.782 for CoEvoRDT boosting; ICoEvoRDF+FPRDT reaches 0.785.
- On max regret, ICoEvoRDF averages 0.082 vs 0.086 for CoEvoRDT boosting and 0.127 for CoEvoRDT forest, outperforming all methods across all 20 datasets (with statistical significance).
- As a single-tree variant (ICoEvoRDT), average adversarial accuracy 0.779 and max regret 0.113, beating CoEvoRDT (0.767, 0.131) and N CoEvoRDT (0.776, 0.122).
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| Use the island-based ICoEvoRDF ensemble instead of CoEvoRDT boosting | Decision tree ensembles · 20 benchmark datasets (average) | adversarial accuracy: 0.782 -> 0.784 | Helped |
| Use the island-based ICoEvoRDF ensemble instead of CoEvoRDT boosting | Decision tree ensembles · 20 benchmark datasets (average) | minimax regret: 0.086 -> 0.082 | Helped |
| Add FPRDT initialization to one island | ICoEvoRDF · 20 benchmark datasets (average) | adversarial accuracy: 0.784 -> 0.785 | Helped |
| Add FPRDT initialization to one island | ICoEvoRDF · 20 benchmark datasets (average) | minimax regret: 0.082 -> 0.082 | No clear effect |
| Add Nash voting rather than equal voting (ablation) | ICoEvoRDF with distinct island inputs · 20 benchmark datasets (average) | adversarial accuracy: 0.779 -> 0.784 | Helped |
| Add Nash voting rather than equal voting (ablation) | ICoEvoRDF with distinct island inputs · 20 benchmark datasets (average) | minimax regret: 0.098 -> 0.082 | Helped |
| Give each island a distinct training set rather than the same inputs (ablation) | ICoEvoRDF with equal voting · 20 benchmark datasets (average) | adversarial accuracy: 0.777 -> 0.779 | Helped |
| Give each island a distinct training set rather than the same inputs (ablation) | ICoEvoRDF with equal voting · 20 benchmark datasets (average) | minimax regret: 0.102 -> 0.098 | Helped |
| Add Nash voting and distinct island inputs rather than using both equal voting and the same inputs (ablation) | ICoEvoRDF · 20 benchmark datasets (average) | adversarial accuracy: 0.777 -> 0.784 | Helped |
| Add Nash voting and distinct island inputs rather than using both equal voting and the same inputs (ablation) | ICoEvoRDF · 20 benchmark datasets (average) | minimax regret: 0.102 -> 0.082 | Helped |
| Add migration between islands instead of independent runs without migration (ablation) | ICoEvoRDT · 20 benchmark datasets (average) | adversarial accuracy: 0.776 -> 0.779 | Helped |
| Add migration between islands instead of independent runs without migration (ablation) | ICoEvoRDT · 20 benchmark datasets (average) | minimax regret: 0.122 -> 0.113 | Helped |
Surprising findings
- Equal voting with same training set for each island (ICoEvoRDF with EV and SI) already outperforms CoEvoRDT forest, with the island structure itself contributing gains.
- Parallelization via shared memory is reported to reduce computation time by a factor of 8-10 without impacting results.
Limitations
- Non-boosting ensemble results are reported without parallelization; computation time comparable to SOTA only at 10 islands.
- Trade-off between robustness and interpretability: more trees improve robustness but reduce interpretability.
- Adversarial accuracy standard deviations are relatively high (ICoEvoRDF family average 0.0100).
Experimental setup
Datasets: ionos breast diabetes bank Japan3v4 spam GesDvP har1v2 wine collision-det mnist-1-5 mnist-2-6
Benchmarks: ionos breast diabetes bank Japan3v4 spam GesDvP har1v2 wine collision-det mnist-1-5 mnist-2-6
Metrics: adversarial accuracy max regret minimax regret diversity computation time
Baselines: Random forests GROOT FPRDT CoEvoRDT PRAdaBoost CoEvoRDT boosting N CoEvoRDT Meta-Silvae
Builds on: CoEvoRDT PRAdaBoost FPRDT GROOT island model
Closest papers by meaning
- Coevolutionary Algorithm for Building Robust Decision Trees under Minimax Regret (AAAI 2024 · similarity 0.90)
- Learning Decision Trees and Forests with Algorithmic Recourse (ICML 2024 · similarity 0.84)
- Invariant Random Forest: Tree-Based Model Solution for OOD Generalization (AAAI 2024 · similarity 0.83)
- Towards Runtime Analysis of Population-Based Co-evolutionary Algorithms on Sparse Binary Zero-Sum Game (AAAI 2025 · similarity 0.82)
- Generative Adversarial Equilibrium Solvers (ICLR 2024 · similarity 0.82)
- No-Regret Bandit Exploration based on Soft Tree Ensemble Model (NeurIPS 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.