革新知能統合研究センター

Title: Learning Binary Decision Trees by Argmin Differentiation

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 .

Bio: Matt Kusner is an associate professor in machine learning at
University College London. His work aims to design simple
machine learning models tailored to the constraints of the
problem at hand, particularly in causal inference, algorithmic
fairness, private learning, and molecular/materials design.
After getting his PhD in Computer Science from Washington
University in St. Louis in 2016, Matt was part of the first
cohort of research fellows at The Alan Turing Institute in
London, UK’s National Institute for Data Science and Artificial
Intelligence. His work was given the Turner Dissertation
Award for best Computer Science & Engineering doctoral
dissertation. Before joining UCL, he was an associate
professor at the University of Oxford and tutorial fellow at
Jesus College.