We show how neural models can be used to realize piece-wise constant functions such as decision trees. Our approach builds on ReLU networks that are piece-wise linear and hence their associated gradients with respect to the inputs are locally constant. We formally establish the equivalence between the classes of locally constant networks and decision trees. Moreover, we highlight several advantageous properties of locally constant networks, including how they realize decision trees with parameter sharing across branching / leaves. Indeed, only M neurons suffice to implicitly model an oblique decision tree with 2 M leaf nodes. The neural representation also enables us to adopt many tools developed for deep networks (e.g., DropConnect (Wan et al., 2013)) while implicitly training decision trees. We demonstrate that our method outperforms alternative techniques for training oblique decision trees in the context of molecular property classification and regression tasks.
*Summary*
This paper leverages the piecewise linearity of predictions in ReLU neural networks to encode and learn piecewise constant predictors akin to oblique decision trees (trees with splits made on linear combinations of features instead of axis-aligned splits). The core observation is that the Jacobian of a ReLU network is piecewise constant w.r.t to the input. This Jacobian is chosen to encode the hard splits of a decision tree. The paper establishes an exact equivalence between decision trees and a slightly modified form of the locally constant networks (LCN). The LCN used for experiments is slightly relaxed to allow for training, including "annealing" from a the softplus nonlinearity to ReLU during training, adding one or more output layers to perform the final prediction, and training with connection dropout. Experiments show LCN models outperform existing methods for oblique decision trees, but ensembles are often matched or outperformed by random forests.
*Rating*
Perhaps the greatest attribute of decision trees is utter simplicity. (The second best attribute the out-of-the-box competitive accuracy of tree ensembles on a wide variety of problems.) An argument to be made for this paper is that it leverages the machinery of learning DNNs to learn more powerful, oblique tree-like models. The counterpoint is that despite the added complication, it's still often beaten by ensembles of CART trees. Overall, the idea is clever, the presentation could be improved slightly, and the experiments raise existential questions for this kind of work. My current rating is weak reject.
(1) It's difficult to know how LCNs should be compared to traditional decision trees, with accuracy, number of parameters, prediction speed, and training time/parallelism as viable components. The paper focuses almost exclusively on accuracy, while cross-validating over model sizes and other hyperparameters. This is a reasonable choice, though a discussion of model size and prediction speed would be welcome. I do have two significant questions about the experiments:
(2) It seems unfair that LCN has access to one or more hidden layers between the splits and the final output, denoted g_\phi. Would competing decision tree models improve with such a layer learned and appended to the final tree? Would LCN suffer from using a tabular representation like the others?
(3) Despite the assertion that these are datasets that necessitate tree-like predictors, the LLN method outperforms LCN and the trees on 4/5 datasets and is competitive with ensemble methods. While not explicitly stated, am I correct that LLN is essentially a traditional ReLU-network? If high accuracy is the goal, then why should I go to the trouble of training LCN when a traditional DNN is better. And if a tree is needed, then LCNs should be evaluated on more than just accuracy.
(4) LCNs seem to present a less bulky alternative to e.g. Deep Neural Decision Trees (https://arxiv.org/abs/1806.06988), but that work should be cited and discussed
(5) The proof sketch in Section 3.6 of the equivalence between the "standard architecture" and decision trees is difficult to understand and not convincing. (On second reading I noticed the subtle vector "\mathbf 0" indicating that all entries of "\grad_x a^i_1" are zero. Some further exposition and enumeration of steps would clear up confusion.)
(6) Overall the presentation is reasonable, other than the notes below. I did find myself searching back over the (dense) notation section and following sections looking for definitions of variables and terms used later. Consider better formatting (e.g. more definitions in standalone equations), strategic pruning of some material to make it less dense, and repeating some definitions in line (e.g. see below for "p7:... remind the reader").
*Notes*
(Spelling typos throughout; most are noted below)
p3: clarify in 3.1/3.3 that L is the number of outputs
p4: "interpred"
p5: "aother"
p5: Theorem 2 proof: note that the T/T' notation is capturing left/right splits
p5: "netwoworks"
p5: "Remark 5 is important for learning shallow...": should "shallow" be "narrow" instead?
p7: in the first paragraph, remind the reader of the definitions of õ^M and J_x ã^M
p7: "Here we provide a sketch of [the] proof"
p7: "unconstraint" should be "unconstrained"
p7: "...can construct a [sufficiently expressive] network g_\theta"
p7: "simlify"
p9: Table 2: instead of "2nd row", ..., use "1st section", ...; also consider noting which methods are introduced in this paper
p9: Figure 2: text is too small