Pareto-optimal trees and Pareto forest: a bi-objective optimization model for binary classification

Abstract As inherently transparent models, classification trees play a central role in interpretable machine learning by providing easily traceable decision paths that allow users to understand how input features contribute to specific predictions. In this work, we introduce a new class of interpretable binary classification models, named Pareto-optimal trees, which aim at combining the complementary strengths of Optimal Classification Trees with Hyperplane-based splits (OCT-H) and Support Vector Machines (SVM). We formulate a bi-objective mixed-integer quadratic optimization problem, whose nondominated solutions represent trade-offs between these two different classification techniques. To further enhance robustness and performance, we propose the Pareto forest, an ensemble method based on the Pareto-optimal trees, aggregated through majority voting. Extensive experiments on benchmark datasets demonstrate that our models can outperform standard methods such as CART and OCT, underscoring the improvements gained through the bi-objective perspective. In particular, Pareto-optimal trees unify the ability of OCT-H and SVM within a single framework, resulting in enhanced classification performance relative to either method alone. Embracing a multiobjective perspective allows the construction of multiple “high quality" trees. Our comparison between Pareto forests and random forests shows that building shallow ensembles from a small number of such optimized trees outperforms relying on a large set of random trees with variable depth.