Learning Binary Decision Trees by Argmin Differentiation
Preprint
Abstract
We address the problem of learning binary decision trees that partition data for some downstream task. We propose to learn discrete parameters (i.e., for tree traversals and node pruning) and continuous parameters (i.e., for tree split functions and prediction functions) simultaneously using argmin differentiation. We do so by sparsely relaxing a mixed-integer program for the discrete parameters, to allow gradients to pass through the program to continuous parameters. We derive customized algorithms to efficiently compute the forward and backward passes. This means that our tree learning procedure can be used as an (implicit) layer in arbitrary deep networks, and can be optimized with arbitrary loss functions. We demonstrate that our approach produces binary trees that are competitive with existing single tree and ensemble approaches, in both supervised and unsupervised settings. Further, apart from greedy approaches (which do not have competitive accuracies), our method is faster to train than all other tree-learning baselines we compare with. The code for reproducing the results is available at https://github.com/vzantedeschi/LatentTrees.Keywords
All Related Versions
This publication has 16 references indexed in Scilit:
- Optimal decision trees for categorical data via integer programmingJournal of Global Optimization, 2021
- Jointly learning sentence embeddings and syntax with unsupervised Tree-LSTMsNatural Language Engineering, 2019
- Gradient-based Hierarchical Clustering using Continuous Representations of Trees in Hyperbolic Space2019
- Learning customized and optimized lists of rules with mathematical programmingMathematical Programming Computation, 2018
- A rewriting system for convex optimization problemsJournal of Control and Decision, 2017
- Exact Algorithms for Isotonic Regression and RelatedJournal of Physics: Conference Series, 2016
- Searching for exotic particles in high-energy physics with deep learningNature Communications, 2014
- Learning Graphical Model Parameters with Approximate Marginal InferenceIEEE Transactions on Pattern Analysis and Machine Intelligence, 2013
- BIRCH: A New Data Clustering Algorithm and Its ApplicationsData Mining and Knowledge Discovery, 1997
- An Algorithm for Constructing Optimal Binary Decision TreesIEEE Transactions on Computers, 1977