Timezone: »
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.
Author Information
Valentina Zantedeschi (INRIA, UCL)
Matt J. Kusner (University College London)
Vlad Niculae (Instituto de Telecomunicações // NIF 502854200)
Related Events (a corresponding poster, oral, or spotlight)
-
2021 Poster: Learning Binary Decision Trees by Argmin Differentiation »
Thu. Jul 22nd 04:00 -- 06:00 PM Room
More from the Same Authors
-
2023 : Causal Discovery with Language Models as Imperfect Experts »
Stephanie Long · Alex Piche · Valentina Zantedeschi · Tibor Schuster · Alexandre Drouin -
2023 Poster: Regions of Reliability in the Evaluation of Multivariate Probabilistic Forecasts »
Étienne Marcotte · Valentina Zantedeschi · Alexandre Drouin · Nicolas Chapados -
2022 Poster: Modeling Structure with Undirected Neural Networks »
Tsvetomila Mihaylova · Vlad Niculae · Andre Filipe Torres Martins -
2022 Spotlight: Modeling Structure with Undirected Neural Networks »
Tsvetomila Mihaylova · Vlad Niculae · Andre Filipe Torres Martins -
2021 Poster: Operationalizing Complex Causes: A Pragmatic View of Mediation »
Limor Gultchin · David Watson · Matt J. Kusner · Ricardo Silva -
2021 Spotlight: Operationalizing Complex Causes: A Pragmatic View of Mediation »
Limor Gultchin · David Watson · Matt J. Kusner · Ricardo Silva -
2021 Poster: Proximal Causal Learning with Kernels: Two-Stage Estimation and Moment Restriction »
Afsaneh Mastouri · Yuchen Zhu · Limor Gultchin · Anna Korba · Ricardo Silva · Matt J. Kusner · Arthur Gretton · Krikamol Muandet -
2021 Spotlight: Proximal Causal Learning with Kernels: Two-Stage Estimation and Moment Restriction »
Afsaneh Mastouri · Yuchen Zhu · Limor Gultchin · Anna Korba · Ricardo Silva · Matt J. Kusner · Arthur Gretton · Krikamol Muandet -
2020 Poster: LP-SparseMAP: Differentiable Relaxed Optimization for Sparse Structured Prediction »
Vlad Niculae · Andre Filipe Torres Martins -
2019 Poster: Making Decisions that Reduce Discriminatory Impacts »
Matt J. Kusner · Chris Russell · Joshua Loftus · Ricardo Silva -
2019 Oral: Making Decisions that Reduce Discriminatory Impacts »
Matt J. Kusner · Chris Russell · Joshua Loftus · Ricardo Silva -
2018 Poster: Blind Justice: Fairness with Encrypted Sensitive Attributes »
Niki Kilbertus · Adria Gascon · Matt Kusner · Michael Veale · Krishna Gummadi · Adrian Weller -
2018 Oral: Blind Justice: Fairness with Encrypted Sensitive Attributes »
Niki Kilbertus · Adria Gascon · Matt Kusner · Michael Veale · Krishna Gummadi · Adrian Weller -
2018 Poster: TAPAS: Tricks to Accelerate (encrypted) Prediction As a Service »
Amartya Sanyal · Matt Kusner · Adria Gascon · Varun Kanade -
2018 Oral: TAPAS: Tricks to Accelerate (encrypted) Prediction As a Service »
Amartya Sanyal · Matt Kusner · Adria Gascon · Varun Kanade -
2018 Poster: SparseMAP: Differentiable Sparse Structured Inference »
Vlad Niculae · Andre Filipe Torres Martins · Mathieu Blondel · Claire Cardie -
2018 Oral: SparseMAP: Differentiable Sparse Structured Inference »
Vlad Niculae · Andre Filipe Torres Martins · Mathieu Blondel · Claire Cardie -
2017 Poster: Grammar Variational Autoencoder »
Matt J. Kusner · Brooks Paige · Jose Miguel Hernandez-Lobato -
2017 Talk: Grammar Variational Autoencoder »
Matt J. Kusner · Brooks Paige · Jose Miguel Hernandez-Lobato