Coevolutionary Algorithm for Building Robust Decision Trees under
  Minimax Regret
Adam Żychowski Andrew Perrault Jacek Mańdziuk
In recent years, there has been growing interest in developing robust machine
learning (ML) models that can withstand adversarial attacks, including one of
the most widely adopted, efficient, and interpretable ML algorithms-decision
trees (DTs). This paper proposes a novel coevolutionary algorithm (CoEvoRDT)
designed to create robust DTs capable of handling noisy high-dimensional data
in adversarial contexts. Motivated by the limitations of traditional DT
algorithms, we leverage adaptive coevolution to allow DTs to evolve and learn
from interactions with perturbed input data. CoEvoRDT alternately evolves
competing populations of DTs and perturbed features, enabling construction of
DTs with desired properties. CoEvoRDT is easily adaptable to various target
metrics, allowing the use of tailored robustness criteria such as minimax
regret. Furthermore, CoEvoRDT has potential to improve the results of other
state-of-the-art methods by incorporating their outcomes (DTs they produce)
into the initial population and optimize them in the process of coevolution.
Inspired by the game theory, CoEvoRDT utilizes mixed Nash equilibrium to
enhance convergence. The method is tested on 20 popular datasets and shows
superior performance compared to 4 state-of-the-art algorithms. It outperformed
all competing methods on 13 datasets with adversarial accuracy metrics, and on
all 20 considered datasets with minimax regret. Strong experimental results and
flexibility in choosing the error measure make CoEvoRDT a promising approach
for constructing robust DTs in real-world applications.