  Neural networks and tree ensembles are state-of-the-art learners, each with
its unique statistical and computational advantages. We aim to combine these
advantages by introducing a new layer for neural networks, composed of an
ensemble of differentiable decision trees (a.k.a. soft trees). While
differentiable trees demonstrate promising results in the literature, they are
typically slow in training and inference as they do not support conditional
computation. We mitigate this issue by introducing a new sparse activation
function for sample routing, and implement true conditional computation by
developing specialized forward and backward propagation algorithms that exploit
sparsity. Our efficient algorithms pave the way for jointly training over deep
and wide tree ensembles using first-order methods (e.g., SGD). Experiments on
23 classification datasets indicate over 10x speed-ups compared to the
differentiable trees used in the literature and over 20x reduction in the
number of parameters compared to gradient boosted trees, while maintaining
competitive performance. Moreover, experiments on CIFAR, MNIST, and Fashion
MNIST indicate that replacing dense layers in CNNs with our tree layer reduces
the test loss by 7-53% and the number of parameters by 8x. We provide an
open-source TensorFlow implementation with a Keras API.
