Venue: ICLR 2020 Conference

Reviews:

final_score: rating: 3: Weak Reject
review_content: *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

review_title: Official Blind Review #3

final_score: rating: 6: Weak Accept
review_content: This paper proposes locally constant network (LCN), which is implemented via the gradient of piece-wise linear networks such as ReLU networks. The authors built the equivalence between LCN and decision trees, and also demonstrated that LCN with M neurons has the same representation capability as decision trees with 2^M leaf nodes. The experiments conducted in the paper disclose that training LCN outperforms other methods using decision trees. 

The detailed comments are as follows:

1) The idea of LCN is very interesting, and the equivalence to decision trees is also very valuable, as it provides interpretability and shines light on new training algorithms. 

2) The derivation of LCN and the equivalence is clear. The analysis based on the shared parameterization in Section 3.5 is helpful to understand why LCN with M neurons could be of equal capability to decision trees with 2^M leaf nodes. 

3) One weakness is that the performance of ELCN seems to be very close to RF, as shown in Table 2. 

I am not sure whether some similar ideas to LCN have been explored in the literature. But the topic studied in this work is very valuable, which connects deep neural networks and decision trees.

review_title: Official Blind Review #1

final_score: rating: 6: Weak Accept
review_content: In this paper, the authors proposed an approach to fit locally constant functions using deep neural networks (DNNs).
The idea is based on the fact that DNN consisting of only linear transformations and ReLU activations is piecewise linear.
Thus, the derivative of such a network with respect to the input is locally constant.

In the paper, the authors focused on connecting the locally constant network with oblique decision trees.
Specifically, they proved that these two models are in some sense equivalent, and one can transform one model to another.
This connection enables us to train the oblique decision trees by training the locally constant network instead.
Because the locally constant network can be trained using the gradient-based methods, it would be much easier to train than the oblique decision trees.

I think the paper is well-written and the idea is clear.
Connecting the locally constant network with oblique decision trees looks interesting.

I have one concern, however.
The authors mention that the training of oblique decision trees is difficult, and the use of the locally constant network is helpful.
If I understand correctly, oblique decision tree is one specific instance of the hierarchical mixtures of experts.
And, [Ref1] pointed out that the hierarchical mixtures of experts can be trained using EM algorithm, which is another type of the gradient-based training.
The current paper misses such a prior study.
I am interested in to see if the use of locally constant network is truly effective for training oblique decision trees over the algorithms considered in the literatures of hierarchical mixtures of experts.

[Ref1] Hierarchical mixtures of experts and the EM algorithm


### Updated after author response ###
The authors have successfully demonstrated that the proposed approach is better than the EM-like classical approaches. I therefore keep my score.
review_title: Official Blind Review #2

Meta-review: This paper leverages the piecewise linearity of predictions in ReLU neural networks to encode and learn piecewise constant predictors akin to oblique decision trees. The reviewers think the paper is interesting, and the idea is clever. The paper can be further improved in experiments. This includes comparison to ensembles of traditional trees or (in some cases) simple ReLU networks. Also  the tradeoffs other than accuracy between the method and baselines are also interesting. 
Decision: Accept (Poster)