Abstract
Decision trees are widely used in machine learning due to their simplicity and interpretability, but they often lack robustness to adversarial attacks and data perturbations. The paper proposes a novel island-based coevolutionary algorithm (ICoEvoRDF) for constructing robust decision tree ensembles. The algorithm operates on multiple islands, each containing populations of decision trees and adversarial perturbations. The populations on each island evolve independently, with periodic migration of top-performing decision trees between islands. This approach fosters diversity and enhances the exploration of the solution space, leading to more robust and accurate decision tree ensembles. ICoEvoRDF utilizes a popular game theory concept of mixed Nash equilibrium for ensemble weighting, which further leads to improvement in results. ICoEvoRDF is evaluated on 20 benchmark datasets, demonstrating its superior performance compared to state-of-the-art methods in optimizing both adversarial accuracy and minimax regret. The flexibility of ICoEvoRDF allows for the integration of decision trees from various existing methods, providing a unified framework for combining diverse solutions. Our approach offers a promising direction for developing robust and interpretable machine learning models.
Introduction
Decision Trees (DTs) are a cornerstone of interpretable machine learning. However, their sensitivity to small data perturbations and adversarial attacks—often referred to as a "glass jaw"—limits their deployment in security-critical applications. While ensemble methods like Random Forests improve general predictive power, they do not inherently address the underlying vulnerability to adversarial manipulation.
Existing Robust Decision Tree (RDT) methods frequently rely on greedy heuristics or optimize for narrow metrics, which can result in a lack of diversity within the final ensemble. If all trees in a forest share the same vulnerabilities, an adversary only needs to exploit a single weakness to compromise the entire system. This research introduces ICoEvoRDF (Island-based CoEvolutionary Robust Decision Forests), a framework designed to cultivate a diverse and resilient archipelago of decision trees.
Methodology
ICoEvoRDF integrates three core concepts to enhance robustness: island models, coevolution, and game-theoretic weighting.
The Island Model and Coevolution
Instead of evolving a single global population, the algorithm maintains several isolated "islands" or subpopulations that evolve in parallel. This structure prevents premature convergence by allowing different islands to explore distinct regions of the solution space. On each island, a "cat-and-mouse" coevolutionary process occurs between two distinct populations:
- Decision Trees: These individuals evolve to maximize classification accuracy on perturbed data.
- Adversarial Perturbations: These individuals evolve to identify and exploit the weaknesses of the current tree population.
Periodically, islands share their most successful individuals through a migration process (typically using a ring topology), allowing beneficial traits to spread across the archipelago without sacrificing the diversity maintained by isolation.
Mixed Nash Equilibrium (MNE) Weighting
To construct the final forest, ICoEvoRDF moves beyond uniform weighting. By treating the interaction between trees and perturbations as a zero-sum game, the algorithm calculates a Mixed Nash Equilibrium. This assigns optimal weights to each tree, ensuring the ensemble is strategically prepared for the full spectrum of adversarial scenarios encountered during the evolutionary process.
Experimental Evaluation
The framework was evaluated across 20 benchmark datasets, ranging from standard UCI tasks (e.g., ionos, diabetes, wine) to complex image-based tasks (e.g., mnist, cifar10). The performance of ICoEvoRDF was benchmarked against state-of-the-art (SOTA) methods including GROOT, FPRDT, and PRAdaBoost.
Results and Discussion
ICoEvoRDF demonstrated significant improvements in both robustness and accuracy. Key findings include:
- Superior Adversarial Accuracy: The model achieved the highest adversarial accuracy on 17 out of 20 benchmarks. As shown in the results table, the integrated approach (ICoEvoRDF + FPRDT) consistently outperformed standalone SOTA methods.
- Minimax Regret Dominance: In terms of minimax regret—a comprehensive metric measuring performance across all possible perturbations—ICoEvoRDF outperformed all competing methods on every dataset with statistical significance.
- Computational Efficiency: Despite the complexity of evolutionary algorithms, the island model's parallel nature allowed for a 9x speedup on multi-core systems, making its training time competitive with non-evolutionary boosting techniques.
One of the most powerful aspects of ICoEvoRDF is its synergy with existing tools. The framework can be "seeded" with trees from other SOTA algorithms like FPRDT, which the evolutionary process then refines and diversifies further.
Conclusion
ICoEvoRDF provides a robust framework for evolving decision tree ensembles that are resilient to adversarial attacks. While there is an inherent trade-off between the simplicity of a single tree and the complexity of a weighted ensemble, the gains in resilience are substantial. Future work will explore applying this coevolutionary framework to other non-differentiable models and integrating fairness metrics to ensure that evolved models are not only robust but also unbiased and equitable.
Summary updated