Experiments with optimal model trees

Model trees provide an appealing way to perform interpretable machine learning for both classification and regression problems. In contrast to "classic" decision trees with constant values in their leaves, model trees can use linear combinations of predictor variables in their leaf nodes to form predictions, which can help achieve higher accuracy and smaller trees. Typical algorithms for learning model trees from training data work in a greedy fashion, growing the tree in a top-down manner by recursively splitting the data into smaller and smaller subsets. This yields a fast algorithm, but the selected splits are only locally optimal, potentially rendering the tree overly complex and less accurate than a tree whose structure is globally optimal for the training data. In this paper, we empirically investigate the effect of constructing globally optimal model trees for classification and regression. The trees we consider feature linear support vector machines at the leaf nodes and are learned using mixed-integer linear programming (MILP) formulations. We use benchmark datasets to compare them to model trees obtained using greedy and dynamic programming-based algorithms, evaluating both tree size and predictive accuracy. We also compare to classic optimal and greedily grown decision trees, random forests, and support vector machines. Our results show that MILP-based optimal model trees can achieve competitive accuracy with very small trees. We also investigate the effect on the accuracy of replacing axis-parallel splits with multivariate ones, foregoing interpretability while potentially obtaining greater accuracy.