Learning Optimal Classification Trees: Strong Max-Flow Formulations

By Sina Aghaei, Andres Gomez, Phebe Vayanos. 2020

28 citations recorded by the source corpus.

We consider the problem of learning optimal binary classification trees. Literature on the topic has burgeoned in recent years, motivated both by the empirical suboptimality of heuristic approaches and the tremendous improvements in mixed-integer programming (MIP) technology. Yet, existing approaches from the literature do not leverage the power of MIP to its full extent. Indeed, they rely on weak formulations, resulting in slow convergence and large optimality gaps. To fill this gap in the literature, we propose a flow-based MIP formulation for optimal binary classification trees that has a stronger linear programming relaxation. Our formulation presents an attractive decomposable structure. We exploit this structure and max-flow/min-cut duality to derive a Benders' decomposition method, which scales to larger instances. We conduct extensive computational experiments on standard benchmark datasets on which we show that our proposed approaches are 50 times faster than state-of-the art MIP-based techniques and improve out of sample performance up to 13.8%.

Subfields: Artificial Intelligence, Algorithms & Complexity

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

In Artificial Intelligence

In Algorithms & Complexity

Citations in the corpus

Interpretable Machine Learning: Fundamental Principles and 10 Grand Challenges (2021, background): “MIP solvers can be used directly when the problem is not too large and when the loss function is discrete or linear (e.g., classification error is discrete, as it takes values either 0 or 1).”
Mathematical optimization in classification and regression trees (2021, background): “In Aghaei et al. (2020), a flow-based MILO formulation is proposed for binary predictor variables.”
MurTree: Optimal Decision Trees via Dynamic Programming and Search (2020, background): “Recently, Zhu et al. (2020) proposed a novel mixed-integer programming formulation based on support vector machines and a cutting plane technique for optimal multi-variate decision trees, and a ﬂow-based encoding has been developed Aghaei et al. (2020).”
A Scalable MIP-based Method for Learning Optimal Multivariate Decision Trees (2020, methodology): “[2] propose a strong max-flow based MIP formulation to train univariate ODT for binary classification.”
Decision Trees for Decision-Making under the Predict-then-Optimize Framework (2020, unknown): “There have been several frameworks proposed in the literature for encoding decision trees using integer and linear constraints (Bertsimas & Dunn, 2017; Günlük et al., 2018; Verwer & Zhang, 2019; Aghaei et al., 2020).”
Learning Binary Trees via Sparse Relaxation (2020, result): “This resulted in a line of recent follow-up works (Günlük et al., 2018; Aghaei et al., 2019; Verwer & Zhang, 2019; Hu et al., 2019; Aghaei et al., 2020; Lin et al., 2020).”