Decision trees are a widely used tool for interpretable machine learning. Multivariate decision trees employ hyperplanes at the branch nodes to route datapoints throughout the tree and yield more compact models than univariate trees. Recently, mixed-integer programming (MIP) has been applied to formulate the optimal decision tree problem. To strengthen MIP formulations, it is crucial to introduce polyhedral characterizations of multivariate decision trees. A key component of most MIP formulations is a specification of how to route datapoints in the tree from the root to the leaves.
Our goal is to characterize the set of realizable routings, i.e., routings that can be realized using multivariate branching rules. We first focus on shattering inequalities, a class of valid inequalities that can be used to strengthen almost any MIP formulation and that have been shown to be computationally effective. We prove that if all the feature vectors are in general position, then the shattering inequalities defined for the root of the tree are facet-defining for the convex hull of the realizable routings. We then show that every facet-defining inequality of a depth one tree involving at least two variables is also facet-defining for trees of arbitrary depth. Finally, we show that facet-defining inequalities characterizing realizable routings are also facet-defining for a complete MIP formulation.
Citation
Carla Michini and Zachary Zhou, A polyhedral study of multivariate decision trees, University of Wisconsin-Madison, November 2022