Oblique Decision Trees from Derivatives of ReLU Networks
Authors: Guang-He Lee
Tommi S. Jaakkola
Venue:  (2020)
Keywords: oblique decision trees
ReLU networks

Abstract: We show how neural models can be used to realize piece-wise constant functions such as decision trees. The proposed architecture, which we call locally constant networks, 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. 

Published as a conference paper at ICLR 2020
OBLIQUE DECISION TREES FROM DERIVATIVES OF RELU NETWORKS
Guang-He Lee & Tommi S. Jaakkola Computer Science and Artificial Intelligence Lab MIT {guanghe, tommi Bettgieettttmmeessestseeee Pecsail. meteaall.it... .mit.edd edu
ABSTRACT
We show how neural models can be used to realize piece-wise constant functions such as decision trees. The proposed architecture, which we call locally con- stant networks, builds ReLU networks that their associated gradients with respect to the inputs are locally constant. We for- mally establish the equivalence between the classes of locally constant networks and decision trees. Moreover, we highlight several advantageous properties of lo- cally 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 2M Icaf nodes. The neural representation also enables us to adopt many tools developed for deep networks (e.g., DropCon- nect (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 molecular property classification and regression tasks)
piece-wise linear and hence
INTRODUCTION
Decision trees (Breiman et al. 1984) employ series of simple decision nodes, arranged in a tree, to transparently capture how the predicted outcome reached. Functionally, such tree-based models, including random forest (Breiman 2001), realize piece-wise constant functions. Beyond their status as de facto interpretable models, they have also persisted as the state of the models in some tab- ular (Sandulescu & Chiru 2016) and chemical datasets (Wu et al. 2018). Deep neural models, in contrast, are highly flexible and continuous, demonstrably effective practice, though lack trans- parency. We merge these two contrasting views by introducing new family of neural models that implicitly learn and represent oblique decision trees.
Prior work has attempted to generalize classic decision trees by extending coordinate-wise cuts to be weighted, linear classifications. The resulting family of models is known as oblique decision trees (Murthy et al. 1993). However, the generalization accompanies challenging combinatorial, non-differentiable optimization problem over the linear parameters at each decision point. Simple sorting procedures used for successively finding branch-wise optimal coordinate cuts available, making these models considerably harder to train. While finding the optimal oblique decision tree can be cast as mixed integer linear program (Bertsimas & Dunn 2017). scaling remains a challenge.
longer
In this work, provide effective, implicit representation of piece-wise constant mappings, termed locally constant networks. Our approach exploits piece-wise linear models such as ReLU networks basic building blocks. Linearity of the mapping each region in such models means that the gradient with respect to the input coordinates is locally constant. We therefore implicitly represent piece-wise -ise constant networks through gradients evaluated from ReLU networks. We prove the equivalence between the class of oblique decision trees and these proposed locally constant neu- ral models. However, the sizes required for equivalent representations can be substantially different. For example, a locally constant network with M neurons can implicitly realize an oblique decision tree whose explicit form requires 2 oblique decision nodes. The exponential complexity reduc-
Our implementation and data available https: http://gtgtuuu.ooogggeeeeaeseeee weeigghhheeeeeeeeeee r20-1 en

---

Published as a conference paper at ICLR 2020
tion in the corresponding neural representation illustrates the degree to which parameters are shared across the locally constant regions.
Our locally constant networks can be learned via gradient descent, and they can be explicitly verted back to oblique decision trees for interpretability. For learning via gradient descent, however, it is necessary to employ some smooth annealing of piece-wisd wisee linear activation functions keep the gradients themselves continuous. Moreover, we need to evaluate the gradients of all the neurons with respect the inputs. To address this bottleneck, we devise a dynamic programming algorithm which computes all the necessary gradient information in a single forward pass. A number of extensions are possible. For instance, we can construct approximately locally constant networks by switching activation functions, or apply helpful techniques used with normal deep learning mod- els (e.g., DropConnect (Wan et al. 2013)) while implicitly training tree models.
to
We empirically test our model in the context of molecular property classification and regression tasks (Wu et al., 2018), where tree-based models remain state-of-the-art. We compare our approach against recent methods for training oblique decision trees and classic ensemble methods such as gradient boosting (Friedman) 2001) and random forest. Empirically, a locally constant network always outperforms alternative methods for training oblique decision trees by large margin, and the ensemble of locally constant networks is competitive with classic ensemble methods.
2 RELATED WORK
Locally constant networks are built on mixed integer linear representation of piece- wise linear networks, defined as any feed-forward network with wiiee linear activation function such as ReLU (Nair& & Hinton 2010). One can specify a set of integers encoding the active linear piece of each neuron, which is called activation pattern (Raghu et al. 2017). The feasible set of an activation pattern forms a convex polyhedron in the input space (Lee et al. 2019). where the net- linear model. The framework motivates
leverage the locally invariant derivatives of the networks to construct a locally constant network. The activation pattern is also exploited in literature for other purposes such deriving robustness certificates (Weng al. 2018) We refer the readers to the recent work (Lee et al.) 2019) and the references therein.
work degenerates
Locally constant networks use the gradients of deep networks with respect to inputs as the repre- sentations to build discriminative models. Such gradients have been used in literature for different purposes. They have been widely used for local sensitivity analysis of trained networks (Simonyan et al. 2013 Smilkov et al., (017)). When the deep networks model an energy function (LeCun et al., 2006), the gradients can be used draw samples from the distribution specified by the normalized energy function (Du & Mordatch] 2019 [Song & Ermon, 2019). The gradients can also be used to train generative models (Goodfellow al. 2014) or perform knowledge distillation (Srinivas &
Fleuret 2018).
The class of locally constant networks equivalent to the class of oblique decision trees. There are some classic methods that also construct neural networks that reproduce decision trees (Sethi 1990, Brent 1991 Cios & Liu 1992), by utilizing step functions and logic gates (e.g., AND/NEGATION CON) as the activation function. The methods were developed when back- propppppagn was yet practically useful, and the motivation is to exploit effective learning procedures of decision trees to train neural networks. Instead, our goal is leverage the successful deep models to train oblique decision trees. Recently, Yang et al. (2018) proposed a network architecture with arg max activations to represent classic decision trees with coordinate cuts, but their parameterization scales exponentially with input dimension. In stark contrast, our parameterization only scales linearly with input dimension (see our complexity analyses in (3.7)
Learning oblique decision trees is challenging, even for a greedy algorithm; for a single oblique split, Einn (N) different ways to separate N data points in D-dimensional space (Vapnik & Chervonenkis, 1971) (cf. ND possibilities for coordinate-cuts) Existing learning algorithms for oblique decision trees include greedy induction, global optimization, and iterative refinements on
there can be Σp
initial tree. We review some representative works, and refer the readers to the references therein.
Optimizing each oblique split in greedy induction can be realized by coordinate descent (Murthy ct al. 1994) or a coordinate-cut search in some linear projection space (Menze et al.) 2011]: Wickra- marachchi et al. 2016). However, the greedy constructions tend get stuck in poor local optimum.
2

---

Published as a conference paper at ICLR 2020
There are some works which attempt find the global optimum given a fixed tree structure by for- mulating a linear program (Bennett 1994) or a mixed integer linear program (Bertsimas & Dunn. 2017), but the methods are not scalable to ordinary tree sizes (c.g.. depth more than 4). The itera- tive refinements are more scalable than global optimization, where CART (Breiman et al. 1984) is the typical initialization. Saareira-Perpiniae & 'aaaalaaii (2018) develop an alternating optimization method via iteratively training a linear classifier on each decision node, which yield the state-of-the- art empirical performance, but the approach only applicable classification problems. Norouzi et al. (2015) proposed to do gradient descent on sub ribbdifferentialle upperbound of tree prediction errors, but the gradients with respect to oblique decision nodes are unavailable whenever the up- perbound is tight. In contrast, our method conducts gradient descent on a differentiable relaxation, which is gradually annealed a locally constant network.
METHODOLOGY
In this section, we introduce the notation and basics in |3.1 construct the locally constant networks in 43.2
3.3 analyze the networks in 33.4 and develop practical formulations and algorithms in Note that we will propose two (equivalent) architectures of locally constant networks in 3.3 and 336 which are useful for theoretical analyses and practical purposes, respectively.
3.1
NOTATION AND BASICS
The proposed approach built on feed-forward networks that yield piece-wise linear mappings. Here we first introduce canonical example of such networks, and elaborate its piece-wise wise linearity. We consider the densely connected architecture (Huang et al. (017), where each hidden layer takes as input all the previous layers; it subsumes other existing fecd-forwart architectures such as residual networks (He et al., 2016). For such a network fo IDD - R& with the set of parameters 0, we denote the number of hidden layers M and the number of neurons in the 5th layer as N₁; we denote the neurons in the zt layer, before and after activation, as x' E N. and a' E RN, respectively, where we sometimes interchangeably denote the input instance x as a E RoNo with No - D. To simplify exposition, we denote the concatenation of (a", aa....,.a' a') as a' E R with Ñ; & Σj= Nr, Vi E {0, M.) The neurons are defined via the weight matrix W RNNNN, and the bias vector b' E R. in each layer [M] A (1.2.....AA Concretely, a é w'aa-ai- b', a' a0(2)), Vi E [M],
(I) where (.) a point-wise activation function. Note that both a and are functions of the specific instance denoted by æ, where we drop the functional dependency to simplify notation. We use the
set I to denote the set of all the neuron indices in this network {(i.j)li E [Nt]. [M]]. In this work, will use ReLU (Nair & Hinton 2010) as canonical example for the activation function
a =z=); A max(0, zj), V(i,j) II,
but the results naturally generalize to other piece-wise linear activation functions such as leaky ReLU (Maas et al. 2013). The output of the entire network fo(x)) is the affine transformation from all the hidden layers MM with the weight matrix W+++ E RRL. LRLNN and bias vector b M+1 I.."..
3.2 LOCAL LINEARITY
It is widely known that the class of networks fo(-) yields piece-wiss linear function. The results are typically proved via associating the end-to-end behavior of the network with its activation pattern which linear piece in each neuron is activated; once activation pattern is fixed across the entire network, the network degenerates to linear model and the feasible set with respect to an activation pattern is a natural characterization of locally linear region of the network.
Formally, we define the activation pattern as the collection of activation indicator functions for each neuron 0f : : > {0, 1). V(. I (or, equivalently, the derivatives of ReLU units; see below
dag A [2z > (i. EI,
of
Note that each of is again function of æ, where we omit the dependency for brevity.
3

---

Published as a conference paper at ICLR 2020
Define
z
X1
X2
1; z²
4x + X2 4a
+
- x + 1.5a 0.3a² 4; z
M
2
Fille
True
M 2
A
D0D,9,10
Falle
1.00 1
M 3
272
$01.0000
2
2
1...
Locally constant networks
Maps
Decision trees
Toy examples for the equivalent representations of the same mappings for different M. Here the locally constant networks have neuron per layer. We show the locally constant networks on the LHS, the raw mappings in the middle, and the equivalent oblique decision trees on the RHS.
Figure I:
where I[-) is the indicator function. Note that, for mathematical correctness, we define /aj/ 23 0; this choice is arbitrary, and
change da, /0z) at 2) 0 without affecting most of the derivations. Given a fixed activation pattern oj E {0, (0.1], vi.jj), we can specify feasible set in RD that corresponds to this activation pattern {a E IR PR 03 = oj. Vi,j) E I (note that each of is function of æ:). Due to the fixed activation pattern, the non-linear ReLU can be re-written linear function for all the inputs in the feasible ser. For example, for an oj can re-write at = 0 z5. As a result, the network has a consistent end-to-end linear behavior across the entire feasible set. One can prove that all the feasible sets partition the space RD into disjoint convex polyhedra which realize natural representation of the locally linear regions. Since we will only use the result to motivate the construction of locally constant networks, we refer the readers to Lee al. (2019) for detailed justification of the piece-wise linearity of such networks.
3.3 CANONICAL LOCALLY CONSTANT NETWORKS
Since the ReLU network fo (x) is piece-wise wise linear, immediately implies that its derivatives with respect to the input æ is a piece-wise constant function. Here we use Ja. fe (x) E IR LXD to denote the Jacobian matrix (i.e., fo (ax)]..; ; = (=)x2)) and we assume the Jacobian consistent with Eq. at the boundary of the locally linear regions. Since any function taking the piece- wise constant Jacobian as input will remain itself piece-wise constant, we can construct variety of locally constant networks by composition.
However, in order to simplify the derivation, we first make a trivial observation that the activation pattern in each locally linear region is also locally invariant. More broadly, any invariant quantity in each locally linear region can be utilized so as to build locally constant networks. We thus define the locally constant networks any composite function that leverage the local invariance of piece- piece-wise linear networks. For the theoretical analyses, we consider the below architecture.
Canonical architecture. We denote σM E 10 as the concatenation of (o',..., o M). We will the composite function g(ōh) M) as the canonical architecture of locally constant networks for theoretical analyses, where g {0, 1 MM + R is simply a table.
Before elucidating the representational equivalence oblique decision trees, first show some toy examples of the canonical locally constant networks and their equivalent mappings in Fig. [
'The boundary of the polyhedron depends on the specific definition of the activation pattern, under some definition in literature, the resulting convex polyhedra may not be disjoint the boundary.

---

Published as a conference paper at ICLR 2020
which illustrates their constructions when there is only 1 neuron per layer (i.e., x' zi. and simi- larly for o' and a'). When M = 1, = + 21 32 + 1 2 O, thus the locally constant network is equivalent to linear model shown in the middle, which can also be represented an oblique decision tree with depth = 1. When M > 1, the activations in the previous layers control different linear behaviors of neuron with respect the input, thus realizing hierarchical structure as an oblique decision tree. For example, for M = 2, o² 0 + z² <0= + z² -4x1 + 22 + 4 and o² + 21 2 0 = z² = -3x2 8; hence, can also be interpreted as the decision tree on the RHS, where the concrete realization of z² depends on the previous decision variable 2' 2 0. Afterwards, we can map either the activation patterns on the LHS or the decision patterns on the RHS to an output value, which leads to the mapping in the middle.
3.4 REPRESENTATIONAL EQUIVALENCE
In this section, prove the equivalence between the class of oblique decision trees and the class of locally constant networks. We first make an observation that any unbalanced oblique decision tree can be re-written to be balanced by adding dummy decision nodes 0 x 2-1 Hence, we can define the class of oblique decision trees with the balance constraint:
Definition 1. The class of oblique decision trees contains any functions that can be procedurally defined (with some depth for x E R
1. T1 - 1[ + AB 2 0J. where wz E Rº and 3g E R. denote the weight and bias of the root decision node,
2. For E (2,3,...,T). - T( Pi:-1 3 0), where Wry RDD and Br E TR. denote the weight and bias for the decision node after the decision pattern 71--1-
3. (0, +R R outputs the leaf value v(riTT) associated with the decision pattern TI.T-
The class of locally constant networks is defined by the canonical architecture with finite M and Ni, E [M. We first prove that we can represent any oblique decision tree as a locally constant network. Since typical oblique decision tree can produce arbitrary weight in each decision node (cf. the structurally dependent weights in the oblique decision trees in Fig. []. the idea is to utilize a network with only hidden layer such that the neurons do not constrain one another. Concretely,
Theorem 2. The class of locally constant networks 2 the class of oblique decision trees.
Proof. For any oblique decision tree with depth T, it contains 2 - 1 weights and biases. We thus construct locally constant network with M = 1 and N₁ 2 such that each pair of (wo, B) in the oblique decision tree is equal to some W k,: and by in the constructed locally constant network.
For each leaf node in the decision tree, it is associated with output value y R and T decisions; the decisions can be written as W i.x b. [dx[j] 2 0 for j E (1,2...., Th} and W icx[s], +
b1 idxls for j E {T" + 1, ..,... T} for some index function idx : [T] + [2 and some T" E 10.1...... T3. We can set the table g()) of the locally constant network as
اxرl = 1( W1
idx(f).: x + b1 idxijl 2 0), for E (1, T"), and
if
[dxlo] 0(*+ W Wixls). [dxis] < 0), [T" 1, + ,....
As a result, the constructed locally constant network yields the same output as the given oblique decision tree for all the inputs that are routed to each leaf node, which concludes the proof. O
Then we prove that the class of locally constant networks is subset of the class of oblique decision trees, which simply follows the construction of the toy examples in Fig. []]
Theorem 3. The class of locally constant networks C the class of oblique decision trees.
Proof. For any locally constant network, it can be re-written to have 1 neuron per layer, by ex- panding any layer with N; > 1 neurons to be N, different layers such that they do not have effective intra-connections. Below the notation refers to the converted locally constant network with 1 neuron per layer. We define the following oblique decision tree with T M for E IR.;
1. A of = Ia + +B0 2 0] with Wg W and B3 = b/.
5

---

Published as a conference paper at ICLR 2020
2. For i .., - IW + Pri. 0], where Wri - = - (Vozi) æ. Note that T; = l| 2 0] = 0j.
V V and
3. U= g.
Note that, in order to be valid decision tree, Wi:;; and B have to be unique for all that yield the same decision pattern T1--1- To see this, for i E (2,3,..., M), as T1s-1 = (o),... of we know each z is a fixed affine function given an activation pattern for the pre- ceding neurons, so V and z x ~VV V are fixed quantities given a decision pattern Ti:--1-
Since F1:M = ØM and g. conclude that they yield the same mapping.
Despite the simplicity of the proof, it has some practical implications:
Remark 4.
The proof of Theorem 3 implies that we can train locally constant network with M neurons, and convert it to an oblique decision tree with depth M (for interpretability).
establishes that, given a fixed number of neurons, it suffices (representationally) to only consider the locally constant networks with neuron per layer.
Remark 5. The proof of Theorem 3
Remark [5] is important for learning small locally constant networks (which can be converted to shallow decision trees for interpretability), since representation capacity is critical for low capacity models. In the remainder of the paper, we will only consider the setting with N; 1, E [M]-
3.5 STRUCTURALLY SHARED PARAMETERIZATION
Although we have established the exact class-level equivalence between locally constant networks and oblique decision trees, once we restrict the depth of the locally constant networks M, it can no longer re-produce all the decision trees with depth M. The result can be intuitively understood by the following reason: we effectively using M pairs of (weight, bias) in the locally constant network to implicitly realize 2 - pairs (weight, bias) in the corresponding oblique decision tree. Such exponential reduction the effective parameters in the representation of oblique decision trees yields "dimension reduction" the model capacity. This section aims to reveal the implied shared parameterization embedded in the oblique decision trees derived from locally constant networks.
In this section, the oblique decision trees and the associated parameters refer to the decision trees obtained via the proof of Theorem We start the analysis by decomposition of Wry among the preceding weights was Wr11 Wei To simplify notation, we denote Wre. A Wa. Since Wri.. = = 2+ and z1
an affine transformation of the vector (aa, a!.....a)).
dat dz
Wri. V i+1 wit1 =
Σ I.D+& I,I:D
V
Wi-1 I,ED
with L.D42 XT4 Wrik-1'
where we simply re-write the derivatives in terms of tree parameters. Since With Wri.. the above decomposition implies that, in the induced tree, all the weights Wr... in the same depth i are restricted to be a linear combination of the fixed basis With and the corresponding preceding weights Wriorr-... Wris We can extend this analysis to compare weights in same layer, and we begin the analysis by comparing weights whose tn distance in decision pattern is 1. To help interpret the statement, note that Wr1s-1 is the weight that leads to the decision T, (or r'J see below).
1,1:D is fixed for all the
Lemma 6. For an oblique decision tree with depth T >> 1, Vi E [T - 1) and any T rhis such that Ty = ry for all ls [0] except that T # r for some j E [i], we have Wr for some R.
Wri
Wri
The proof involves some algebraic manipulation, and is deferred Appendix A.I L terizes an interesting structural constraint embedded in the oblique decision trees realized by locally constant networks, where the structural discrepancy ry in decision patterns (ris versus r'()) is re- flected on the discrepancy of the corresponding weights (up be generalized for all the weights in the same layer, but the message is similar.
scaling factor a). The analysis can
Proposition 7. For the oblique decision tree with depth T > 1, Vi [T 1] and any Pi. T'x such that T = r' for all E [i] except for n E coordinates ji...., In E [t]. we have
Whin - Wry, =
Σ Ogk x Wrish 11 for some ag E R, Vk E [n]]
(4)

---

Published as a conference paper at ICLR 2020
The statement can be proved by applying Lemma 6
multiple times.
Discussion. Here we summarize this section and provide some discussion. Locally constant net- works implicitly represent oblique decision trees with the same depth and structurally shared pa- rameterization. In the implied oblique decision trees, the weight of each decision node a linear combination of shared weight across the whole layer and all the preceding weights. The analysis explains how locally constant networks use only M weights to model a decision tree with 2 decision nodes; it yields a strong regularization effect to avoid overfitting, and helps computation by exponentially reducing the memory consumption on the weights.
3.6 STANDARD LOCALLY CONSTANT NETWORKS AND EXTENSIONS
The simple structure of the canonical locally constant networks is beneficial for theoretical analysis, but the structure is not practical for learning since the discrete activation pattern does not exhibit gra- dients for learning the networks. Indeed, V ((²M) is undefined, which implies that V V g(O²) also undefined. Here we present another architecture that equivalent to the canonical architec- ture, but exhibits aab-gradients with respect to model parameters and is flexible for model extension.
Standard architecture. We assume N;- 1, Vi E [M]. We denote the Jacobian of all the neurons after activation M as J=a' M E CRMD and denote Jæa M as the vectorized version. We then define the standard architecture as go (Jzaa,,, where O IR (M D)) + R is a fully-connected network.
We abbreviate the standard locally constant networks as LCN. Note that each aj is locally linear and thus the Jacobian J= is locally constant. We replace 8M with J M as the invariant rep- resentation for each locally linear region and replace the table g with a differentiable function Jo that takes as input real vectors. The gradients of LCN with respect to parameters is thus established through the derivatives of go and the mixed partial derivatives of the neurons (derivatives of J)
Fortunately, all the previous analyses also apply to the standard architecture, due to a fine-grained equivalence between the two architectures.
Theorem 8. Given any fixed fe. any canonical locally constant network g(ōM) ) can be equivalently represented by a standard locally constant network go ( M), and vice versa.
Since fo and g control the decision nodes and leaf nodes in the associated oblique decision tree, respectively (see Theorem 3). Theorem @essentially states that both architectures are equally com- petent for assigning leaf nodes. Combining T the analyses in $3.4, we have class-level cquivalence among the two architectures of locally constant networks and oblique decision trees. The analyses in (3.5 are also inherited since the analyses only depend on decision nodes (i.e., fe).
X
The core ideas for proving Theorem 8 are two-fold: 1) we find a bijection between the activation pattern TM and the Jacobian J_ M and 2) feed-forward networks De can map the (finitely many) Jacobian J_ as flexibly as a table g. The complete proof is deferred to Appendix A.2
Discussion. The standard architecture yields a new property that is only partially exhibited in the canonical architecture. For all the decision and leaf nodes which no training data is routed to, there is no way to obtain learning signals in classic oblique decision trees. However, due to shared pa- rameterization (see (3.5). locally constant networks can "learn" all the decision nodes in the implied oblique decision trees (if there is a way to optimize the networks), and the standard architecture can even "learn" all the leaf nodes due to the parameterized output function Iø-
The construction of (standard) locally constant networks enables several natural exten- sions due to the flexibility of the neural architecture and the interpretation of decision trees. The original locally linear networks (LLNN) fo, which outputs linear function instead of a constant function for each region, can be regarded as one extension. Here we discuss two examples.
Extensions.
Approximately locally constant networks (ALCN): we can change the activation function while keeping the model architecture of LCN. For example, we can replace ReLU max(0, x) with softplus log(1 + exp(x)), which will lead to an approximately locally constant network, as the softplus function has approximately locally constant derivative for inputs with large absolute value. Note that the canonical architecture (tabular g) is not compatible with such extension.
"In practice, we also include each bias ai (V.ai) T a. which omitted here simplify exposition.
7

---

Published as a conference paper at ICLR 2020
Ensemble locally constant networks (ELCN): since each LCN can only output 2 different val- ues, it is limited for complex tasks like regression (akin to decision trees). We can instead use an additive ensemble of LCN or ALCN to increase the capacity. We use g |el (JaāaMlle) to denote base model in the ensemble, and denote the ensemble with E models as Ee= (J
3.7 COMPUTATION AND LEARNING
In this section, we discuss computation and learning algorithms for the proposed models. In the following complexity analyses, assume 96 be linear model.
Space complexity.
The space complexity of LCN is (M for representing decision nodes and (MMDL) for representing leaf nodes. In contrast, the space complexity of classic oblique decision trees ((2M - D)D) for decision nodes and ((2 L) for leaf nodes. Hence, our representation improves the space complexity over classic oblique decision trees exponentially.
Computation and time complexity. LCN and ALCN are built on the gradients of all the neurons Ja = -[ a ..... Vaajj, which can be computationally challenging to obtain. Existing auto- matic differentiation (e.g., back-propagation) only computes the gradient of scalar output. Instead, here we propose an efficient dynamic programming procedure which only requires forward pass:
1. Vaai o x W
2. E (2...., M), Vaai= of (Wi.I. EEE Wi.D+
The complexity of the dynamic programming is (M2)) due to the inner-summation inside each iteration. Straightforward back-propagation re-computes the partial solutions a for each z so the complexity is O(M)). We can parallelize the sumem-summaiion of the dynamic programming and straightforward back-propageal will become O ((M) and ((²²), respectively. Note that the complexity of forward pass of typical network is also ( on GPU. The time complexity of learning LCN by (stochastic) gradient descent is thus (MMT), where r denotes the number of iterations. contrast, the computation of existing oblique decision tree training algorithms is typically data-dependent and thus the complexity is hard to characterize.
GPU, and the complexity
Training LCN and ALCN. Even though LCN is sub-differentiable, whenever of O, the network does not exhibit useful gradient information for learning each locally constant representation V (note that J_a' [V a. :........ V V since, operationally, of implies af <- and there v = O with respect to model parameters. To alleviate the
is no useful gradient of a problem, we propose to leverage softplus an infinitely differentiable approximation of ReLU to obtain meaningful learning signals for V aj Concretely, we conduct the annealing during training:
A max(0, (0, >) + (1 xx) log(1 + exp(z1)), Vi E [M], E [0,
(5)
where Aa is an iteration-dependes a special case of Eq. (5). We train LCN with X₂ equal to the ratio between the current epoch and the total epochs, and ALCN with A 0. Both models are optimized via stochastic gradient descent.
annealing parameter. Both LCN and AL.CN can be constructed as
We also include DropConnect (Wan et al. 2013) to the weight matrices W f- drop W during training. Despite the simple structure of DropConnect in the locally constant networks, it entails a structural dropout on the weights in the corresponding oblique decision trees (see (3.5). which is challenging to reproduce in typical oblique decision trees. In addition, it also encourages the exploration of parameter space, which is easy to see for the raw LCN: the randomization enables the exploration that flips of 0 o 1 to establish effective learning signal. Note that the standard DropOut (Srivastava et al. 2014 is not ideal for the low capacity models that we consider here.
Training ELCN. Since each ensemble component is sub-differentiable, we can directly learn the whole ensemble through gradient descent. However, the approach is not scalable due to memory constraints in practice. Instead, we propose to train the ensemble in boosting fashion:
1. We first train an initial locally constant network g
[1] (.1).
2. For each iteration e' E 32, 1,3....,E,,, E). we incrementally optimize 1 (Jg Note that, in the second step, only the latest model is optimized, and thus we can simply store the predictions of the preceding models without loading them into the memory. Each partial ensemble can be directly learned through gradient descent, without resorting to complex meta-algorithms such as adaptive boosting (Freund & Schapire 1997) or gradient boosting (Friedman) (001).
8

---

Published as a conference paper at ICLR 2020
Table 1: Dataset statistics
Dataset
Bace
HTV
SIDER
Tox21
PDBhind
Task
-Multi-label) binary classification
Regression
Number of labels
1
27
12
Number of data
1,513
41,127
1,427
7,831
11,908
Table Main results. The 1st section refers to (oblique) decision tree methods, the 2nd section refers to single model extensions of LCN, the 3rd section refers to ensemble methods, and the last section is GCN. The results of GCN are copied from (Wu et al. 2018), where the results SIDER and Tox21 are not directly comparable due to lack of standard splittings. The best result in each section is in bold letters.
Dataset
Bace (AUC)
HIV (AUC)
SIDER (AUC)
Tox21 (AUC)
PDBhind (RMSE)
CART
0,652 + 0.024
0.544 + 0.009
0,570 + 0.010
0.651 + 0.005
1.573 + 0.000
HHCART
0.545 = 0.016
0.636 + 0.000
0.570 0.009
0.638 0.007
1.530 + 0.000
TAO
0.734 + 0.000
0.627 + 0.000
0.577 + 0.004
0.676 + 0.003
Not applicable
LCN
0.839 + 0.013
0.728 + 0.013
0.624 0.044
0.781 0.017
1.508 + 0.017
LLN
0.818 0.007
0.737 + 0.009
0.677
0.014
0.813 0.009
1.627 + 0.008
ALCN
0.854 + 0.007
0.738 + 0.009
0.653 + 0.044
0.814 + 0.009
1.369 + 0.007
RF
0.869 = 0.003
0.796 + 0.007
0.685
0.011
0.839 + 0.007
1.256 = 0.002
GBDT
0,859 1 0.005
0.748 1 0.001
0.668 1 0.014
0.812 1 0.011
1.247 1 0.002
ELCN
0.874 + 0.005
0.757 1 0.011
0.685 0.010
0.822 0.006
1.219 1 0.007
GCN
0.783 0.014
0.763 1 0.016
*0.638 + 0.012
*0.829 + 0.006
1.44 + 0.12
4
EXPERIMENT
Here we evaluate the efficacy of our models (LCN, ALCN, and ELCN) using the chemical prop- erty prediction datasets from MoleculeNet (Wu et al. 2018). where random forest performs com- petitively. We include (multi-label) binary classification datasets and regression dataset. The statistics are available in Table ! We follow the literature to construct the feature (Wu et al. (018)). Specifically, we use the standard Morgan fingerprint (Rogers Hahn 2010). 2,048 binary indi- cators of chemical substructures, for the classification datasets, and 'grid features' (fingerprints of pairs between ligand and protein, see Ww et al. (2018)) for the regression dataset. Each dataset splitted into (train, validation, test) sets under the criterion specified in MoleculeNet.
We compare LCN and its extensions (LLN, ALCN, and ELCN) with the following baselines:
(Oblique) decision trees: CART (Breiman et al. (1984)). HHCART (Wickramarachchi et al. (206)); oblique decision trees induced greedily linear projections). and TAo (Carreira-
Perpinán & Tavallali 2018); oblique decision trees trained via alternating optimization).
Tree ensembles: RF (Breiman (200T); random forest) and GBDT (Friedman (200T); gradient
boosting decision trees).
Graph networks: GcN (Duvenaud et al. (215);; graph convolutional networks on molecules).
For decision trees, LCN, LLN, and ALCN, tune the tree depth in f2, ... 12). For LCN, LLN, and ALCN, we also tune the DropConnect probability in {0, 0.25, 0.5, 0.75). Since regression tasks require precise estimations of the prediction values while classification tasks do not, tune the number hidden layers of 9o in (0, 1, 2, 3, 4} (each with 256 neurons) for the regression task, and simply use linear model ga for the classification tasks. For ELCC,, we ALCN the base model, tune the ensemble size E {2". [2 ... 28) for the classification tasks, and E {2", 22....,." ,22 for the regression task. To train our models, we use the cross entropy loss for the classification tasks, and mean squared error for the regression task. Other minor details available in Appendix B
We follow the chemistry literature (Wu et al. 2018) to measure the performance by AUC for classi- fication, and not-mean-squared error (RMSE) for regression. For each dataset, train model for

---

Published as a conference paper at ICLR 2020
JATTHE
10 mee
2.0
1.00
055
850
15.
05
bpocs
Teee
(a) Learning curve of LCN
(b) Training performance
(c) Testing performance
Figure 2: Empirical analysis for oblique decision trees on the HIV dataset. Fig. 2a is ablation
study for LCN and Fig. 2c compare different training methods.
each label, compute the mean and standard deviation of the performance across different random seeds, and report their average across all the labels within the dataset. The results are in Table 2
Among the (oblique) decision tree training algorithms, our LCN achieves the toate-of-theaan per- formance. The continuous extension (ALCN) always improves the empirical performance of LCN, which expected since LCN is limited for the number of possible outputs (leaf nodes). Among the ensemble methods, the proposed ELCN always outperforms the classic counterpart, GBDT, and sometimes outperforms RF. Overall, LCN the state-of-the method for learning oblique deci- sion trees, and ELCN performs competitively against other alternatives for training tree ensembles.
Empirical analysis. Here we analyze the proposed LCN in terms of the optimization and general- ization performance in the large HIV dataset. We conduct ablation study on the proposed method for training LCN in Figure 2a Direct training (without annealing) does not suffice to learn LCN, while the proposed annealing succeed in optimization; even better optimization and generalization performance can be achieved by introducing DropConnect, which corroborates our hypothesis on the exploration effect during training in $3.7 and its well-known regularization effect. Compared to other methods (Fig. 2b). only TAO has a comparable training performance. In terms of generaliza- tion (Fig. 2c), all of the competitors do not perform well and overfit fairly quickly. In stark contrast, LCN outperforms the competitors by large margin and gets even more accurate as the depth in- creases. This is expected due to the strong regularization of LCN that uses a linear number of effective weights to construct exponential number of decision nodes, as discussed in (3.5) Some additional analysis and the visualization of the tree converted from LCN are included in Appendix
5 DISCUSSION AND CONCLUSION
We create a novel neural architecture by casting the derivatives of deep networks as the representa- tion, which realizes new class of neural models that is equivalent to oblique decision trees. The induced oblique decision trees embed rich structures and are compatible with deep learning meth- ods. This work can be used to interpret methods that utilize derivatives of a network, such as training generator through the gradient of discriminator (Goodfellow et al.) 2014). The work opens up many avenues for future work, from building representations from the derivatives of neural models to the incorporation of more structures, such the inner randomization of random forest.
ACKNOWLEDGMENTS
GH and TJ were in part supported by grant from Siemens Corporation. The authors thank Shub- hendu Trivedi and Menghua Wu for proofreading, and thank the anonymous reviewers for their helpful comments.
REFERENCES
Kristin Bennett. Global tree optimization: non- non-greedy decision tree algorithm. Science and Statistics, pp. 156-156, 1994.
Computing
Dimitris Bertsimas and Jack Dunn. Optimal classification trees. Machine Learning, 106(7):1039- 1082, 2017.
10

---

Published as a conference paper at ICLR 2020
L. Breiman, J. Friedman, R. Olshen, and C. Stone. Classification and Regression Trees. Wadsworth and Brooks, Monterey, CA, 1984.
Leo Breiman. Random forests. Machine Learning, 45(1):5-32, 2001.
Richard Brent. Fast training algorithms for multilayer neural nets. IEEE Transactions on Neural Networks, 2(3):346-354, 1991.
Miguel A Carreira- Perpinán and Pooya Tavallali. Alternttnng optimization of decision trees, with application to learning sparse oblique trees. In Advances in Neural Information Processing Sys- tems, pp. 121 1211-1221, 2018.
Krzysztof J Cios and Ning Liu. A machine learning method for generation of a neural network architecture: A continuous id3 algorithm. JEEE Transactions Neural Networks, 3 322:2800-91, 1992.
Yilun Du and Igor Mordatch. Implicit generation and modeling with energy based models. In Advances in Neural Information Processing Systems, pp. 3603-3613, 2019.
David K Duvenaud, Dougal Maclaurin, Jorge Iparraguirre, Rafael Bombarell, Timothy Hirzel, Alán Aspuru-Guzza and Ryan Adams. Convolutional networks on graphs for learning molecular fingerprints. In Advances in Neural Information Processing Systems, pp. 2224-2232, 2015.
Yoav Freund and Robert E Schapire. A Recision-theoretiic generalization on-line learning and an application to boosting. Journal of Computer and System Sciences, 55(1): 19-139, 1997.
Jerome H Friedman. Greedy function approximation: gradient boosting machine. Annals of
Statistics, pp. 1189-1232, 2001.
Ian Goodfellow, Jean Pouget-Abadie, Mchdi Mirza, Bing Xu, David Warde-Farley, Sherjil Ozair, Aaron Courville, and Yoshua Bengio. Generative adversarial nets. In Advances in Neural Infor- mation Processing Systems, pp. 2672-2680, 2014.
Kaiming He, Xiangyu Zhang, Shaoqing Ren, and Jian Sun. Deep residual learning for image recog- nition. In IEEE Conference Computer Vision and Pattern Recognition, pp. 770-778, 2016.
Kurt Hornik, Maxwell Stinchcombe, and Halbert White. Multilayer feedforward networks are uni- versal approximators. Neural Networks, 2(5):359-366, 1989.
Gao Huang. Zhuang Liu, Laurens Van Der Maaten, and Kilian Weinherger. Densely connected convolutional networks. In IEEE Conference on Computer Vision and Pattern Recognition, pp. 4700-4708, 2017..
Yann LeCun, Sumit Chopra, Raia Hadsell, M Ranzato, and Huang. tutorial on energy-based learning. Predicting Structured Data, 100), 2006.
Guang-He Lee, David Alvarez-Melis, and Tommi S. Jaakkola. Towards robust, locally linear deep networks. In International Conference Learning Representations, 2019.
Andrew Maas, Awni Y Hannun, and Andrew Y Ng. Rectifier nonlinearities improve neural net- work acoustic models. In International Conference on Machine Learning, volume 30, pp. 3, 2013.
Bjoern H Menze, B Michael Kelm, Daniel N Splitthoff, Ultrich Koethe, and Fred A Hamprecht. On oblique random forests. In Joint European Conference on Machine Learning and Knowledge Discovery in Databases, pp. 453-469. Springer, 2011.
Sreerama K Murthy, Simon Kasif, Steven Salzberg, and Richard Beigel. Ocl: randomized al- gorithm for building oblique decision trees. In AAAI Conference on Artificial Intelligence, vol- ume 93, pp. 322-327. Citeseer, 1993.
Sreerama K Murthy, Simon Kasif, and Steven Salzberg. A system for induction of oblique decision trees, Journal of Artificial Intelligence Research, 2:1-32, 1994.

---

Published as a conference paper at ICLR 2020
Vinod Nair and Geoffrey E Hinton. Rectified linear units improve restricted boltzmann machines. In Interaational Conference on Machine Learning, pp. 807-814, 2010.
Mohammad Norouzi, Maxwell Collins, Matthew A Johnson, David Fleet, and Pushmeet Kohli. Ef- ficient non-greedy optimization of decision trees. In Advances in Neural Information Processing Systems, pp. 1729-1737, 2015.
Fabian Pedregosa, Gaël Varoquaux, Alexandre Gramfort, Vincent Michel, Bertrand Thirion, Olivier Grisel, Mathieu Blondel, Peter Prettenhofer, Ron Weiss, Vincent Dubourg, et al. Scikit-learn: Machine learning in python. Journal of Machine Learning Research, 12(0ct):2225-2830, 2011.
Maithra Raghu, Ben Poole, Jon Kleinberg, Surya Ganguli, and Jascha Sohl Dickstein. On the expressive power of deep neural networks. In International Conference on Machine Learning, pp. 2847-2854. JMLR. org, 2017.
Sashank J. Reddi, Satyen Kale, and Sanjiv Kumar. On the convergence of adam and beyond. In International Conference on Learning Representations, 2018.
David Rogers and Mathew Hahn. commeeit fingerprints. Journal of Chemical Infor- mation and Modeling, 50(5):742-754, 2010.
Vlad Sandulescu and Mihai Chiru. Predicting the future relevance of research institutions-the win- ning solution of the kdd cup 2016. arXiv preprint arXiv:1609.02728, 2016.
Ishwar Krishnan Sethi. Entropy nets: from decision trees to neural networks. IEEE, 78(10):1605- 1613, 1990.
Karen Simonyan, Andrea Vedaldi, and Andrew Zisserman. Deep inside convolutional networks: networss Vi- sualising image classification models and saliency maps. arXiv preprint arXiv:1112.6034, 2013.
Daniel Smilkov, Nikhil Thorat, Been Kim, Fernanda Viégas, and Martin Wattenberg. Smoothgrad: removing noise by adding noise. arXiv preprint /70iv:/706.00 1706003825 2017.
Yang Song and Stefano Ermon. Generative modeling by estimating gradients of the data distribution. In Advances in Neural Information Processing Systems, pp. 11895-11907, 2019.
Suraj Srinivas and Francois Fleuret. Knowledge transfer with Jacobian matching. In International Conference on Machine Learning, pp. 4723-4731, 2018.
Nitish Srivastava, Geoffrey Hinton, Alex Krizhevsky, Ilya Sutskever, and Ruslan Salakhutdinov. Dropout: a simple way to prevent neural networks from overfitting. Journal of Machine Learning Research, 15(1 ((1):1929-1958 2014.
V. N. Vapnik and A. Ya. Chervonenkis. On the uniform convergence of relative frequencies of events to their probabilities. Theory of Probability & Its Applications, (6(2):264-280) 1971. doi: 10.1 10.1137/1110055, URL //c::////cc.. httt:p:://cc..rr/o.........
Li Wan, Matthew Zeiler, Sixin Zhang, Yann Le Cun, and Rob Fergus. Regularization of neural networks using dropconnect. In International Conference on Machine Learning, pp. 1058-1066, 2013.
Tsui- Weng, Huan Zhang, Hongge Chen, Zhao Song, Cho-Jui Hsich, Duane Boning, Inderjit Dhillon, and Luca Daniel. Towards fast computation of certified robustness for relu networks. International Conference on Machine Learning, 2018
DC Wickramarachchi, BL Robertson, Marco Reale, CJ Price, and J Brown. Hhcart: An oblique decision tree. Computational Statistics & Data Analysis, 96:12-23, 2016.
Zhenqin Wu, Bharath Ramsundar, Evan N Feinherg, Joseph Gomes, Caleb Geniesse, Aneesh Pappu, Karl Leswing, and Vijay Pande. Moleculenet: benchmark for molecular machine learn- ing. Chemical Science, 92):5133-530, 2018
Yongxin Yang, Irene Garcia Morillo, and Timothy M Hospedales. Deep neural decision trees. arXiv preprint arxiv: / 00988, 2018.
12

---

Published as a conference paper at ICLR 2020
Chiyuan Zhang, Samy Bengio, Moritz Hardt, Benjamin Recht, and Oriol Vinyals. Understanding deep learning requires rethinking generalization. In International Conference on Learning Rep- resentations, 2017.
13

---

Published as a conference paper at ICLR 2020
A PROOFS
A.1 PROOF OF LEMMA 6
Proof. We fix j and do induction i. Without loss of generality, we assume = r/ 0.
If j. since ryj O, we have
Wrin W
1,1 + E
kk=
W
1,44 Tk Wrek-1
Wr = W k=
W
1,D4 Tkk x Wrik-1'
Hence, we have Wi... Wrin = (WiD+ 1,D+ x r;) x Wri = a x Wris 19
We assume the statement holds for up to some integer 2 j:
Wris Wri Wris for some R.
For + 1, we have
i11
-W(+2
W
WriHt
1,1:D
1,D+k X Tk Wria-1
-W4+2
1,1:D
1,D+k X Tk Wrin-1 + W,D+s x ry x Wri-1
Σ
W
1.D+k rx Wrin
k=/+1
=W442
Σ
WH+
1. x r Wri W 1.D+j ry Wrig-1
1,1:
k=1
(1
+
Σ
W
1,D+ r x (Wrim-r an Wris ,), for some an
k=/+1
-Wi+2
W 1, r/ Wrin-1
it
+ (Wi+2
1,04j
x rg +
Σ
Wi+2
WiD+* x X x an) x Wris-1
k=j+1
+ x wry-s for some R
The proof follows by induction.
A.2 PROOF OF THEOREM g
Proof. We first prove that we can represent any go (s as g(o Note that for any x mapping to the activation pattern @M the Jacobian JaaM is constant. Hence, may re-write the go( (J((M) where J( is the Jacobian corresponding the activation pattern G.M Then we can set g(.) _ (J.)), which concludes the first part of the proof.
standard architecture ges (
To prove the other direction, first prove that also write the activation pattern function of the Jacobian. We prove this by layer-wise induction (note that MM (ol...., ..,,, oM1 and J.ä [V V.......,
VaaiM M
The induction hypothesis 662 2) is that [ot...., of - is a function [V.a V
2. l (zero vector). z|, a. and of are constant (thus being function V a)). Otherwise,
V a 0 of and V W1 of 1, of can be written function of V.
14

---

Published as a conference paper at ICLR 2020
3. Assume that given [V aa........
Voaj-1] and the corresponding [o], of.....,,,''1.
If either oj = 0 or of is infeasible (but not both), by induction hypothesis, [o]..... ojl can be written a function of [ [ Væaj].
oj = for some x' and oj = 0 for some x", we claim that of = + Va + 0:
If of = -1 and Vadj = 0, we have 0f l = af
= > 0 and
a v which
implies that the bias (of z', given [o]................ 1.......
o
x =1) x 2 O. Note that both = and of regardless of oj. Hence, given [o] ......., 0 ".
<v~ == x1) TT constant given [o]
we have z z (V==1) x 2 and of
is infeasible (=x-).
Note that, given fixed l of V a
+ 0 has unique value in Rd. Combining the result
n 0, there a bijection between of and a in this case, which implies that [o], ... of can be written as a function of [V.aa,..... Vaajj.
of = 1 = a * with of =
The derivation implies that we may re-write the canonical architecture g( as g(
where "(JaaM) is the activation pattern corresponding to the Jacobian J M Hence, it suffices to establish that there exists feed-forward network ge such that most 2 distinct J_ā which can be found by the Theorem 2.5 of Hornik et al. (1989) or the Theorem of Zfang et al. (2017).
g J_aaM for
B IMPLEMENTATION DETAILS
Here provide the full version of the implementation details.
For the baseline methods:
CART, HHCART, and TAo: we tune the tree depth in (2,3, 12).
RF: we use the scikit-learn (Pedregosa et al. 2011 implementation of random forest. We
set the number of estimators as 500.
GBDT: we use the scikit-lears PPedregssa et al.
2011 implementation of gradient boost-
ing trees. We tune the number of estimators in (2", 2 2 200
For LCN, LLN, and ALCN, we run the same training procedure. For all the datasets, we tune the depth in (2.3.... 12] and the DropConnect probability in {0, 0.25, 0.5, 0.75]. The models are optimized with mini-batch stochastic gradient descent with batch size set to 64. For all the classifi- cation tasks, we set the learning rate as 0.1, which is annealed by factor of 10 for every 10 epochs (30 epochs in total). For the regression task, we set the learning rate as 0.0001, which is annealed by a factor of 10 for every epochs (60 epochs in total).
Both LCN and ALCN have an extra fully-connected network 9a. which transforms the derivatives J Mf the final outputs. Since regression tasks require precise estimation of prediction values while classification tasks do not, we tune the number of hidden layers of in {0, 1, 2, 3, 4} (cach with 256 neurons) for the regression dataset, and simply use linear Jo for the classification datasets.
For ELCN, we fix the depth to 12 and tune the number of base models F E {20, 21 .., 26) for the
classification tasks, and E E {20 21 24,,...... .?....," 29} for the regression task. We set the DropConnect prob- ability as 0.75 to encourage strong regularization for the classification tasks, and as 0.25 to impose mild regularization for the regression task (because regression is hard to fit). We found stochastic gradient descent does not suffice incrementally learn the ELCN, we use the AMSGrad opti- mizer (Reddi et al. 2018) instead. We set the batch size as 256 and train each partial ensemble for 30 epochs. The learning rate is 0.01 for the classification tasks, and 0.0001 for the regression task.
To train our models, we use the cross entropy loss for the classification tasks, and mean squared error for the regression task.
15

---

Published as a conference paper at ICLR 2020
Table Analysis for "unobserved decision patterns" of LCN in the Bace dataset.
Depth
8
10
11
12
of possible patterns
256
512
1024
2048
4096
of training patterns
72
103
86
of testing patterns
32
31
48
49
40
of testing patterns training patterns
5
11
Ratio of testing points w/ unobserved patterns
0.040
0.013
0.072
0.059
0.079
Testing performance observed patterns
0.8505
0.8184
0.8270
0.8429
0,8390
Testing performance -unobserved patterns
0.8596
0.9145
0.8303
0.7732
0.8894
C
SUPPLEMENTARY EMPIRICAL ANALYSIS AND VISUALIZATION
C.
SUPPLEMENTARY EMPIRICAL ANALYSIS
In this section, we investigate the learning of "unobserved branching / leaves" discussed in 3.6 The "unobserved branching leaves" refer to the decision and leaf nodes of the oblique decision tree converted from LCN, such that there is training data that are routed the nodes. It impossible for traditional (oblique) decision tree training algorithms to learn the values of such nodes (e.g,, the output value of leaf node in the traditional framework is based on the training data that are routed to the leaf node). However, the shared parameterization in our oblique decision tree provides a means to update such unobserved nodes during training (see the discussion in (3.6).
Since the above scenario in general happens more frequently in small datasets than in large datasets, we evaluate the scenario on the small Bace dataset (binary classification task). Here we empirically analyze few things pertaining to the unobserved nodes:
# of training patterns: the number of distinet end-to-end activation decision patterns T1:M en- countered in the training data.
# of testing patterns: the number of distinct end-to-end activation / decision patterns F1:1r en- countered ib the testing data.
# of testing patterns training patterns: the number of distinet end-to-end activation / decision
patterns FI:M that is only encountered in the testing data but not in the training data.
Ratio of testing points w/ unobserved patterns: the number of testing points that yield unobserved patterns divided by the total number of testing points.
Testing performance observed patterns: here we denote the number of testing data as n, the prediction and label of the 1th as ÿ, E [0, 1] and y/s E {0, 1}, respectively. We collect the subset of indices I of the testing data such that their activation decision patterns T1:M are observed the training data, and then compute the performance of their predictions. Since the original performance is measured by AUC, here we generalize AUC to measure subset of points / as:
EiEl Σラ=1
[Tu vil (T ú5] 0.5TT úsl) + Mye < Usl (Tlū: < úz} 0.5T ú;}
EiEl Ej=1
1[y > Bsl + 1/24 < 4y])
(6)
When / [n]. the above measure recovers AUC.
Testing performance unobserved patterns: the same as above, but use / for the testing data such that their activation decision patterns T1:M are unobserved in the training data.
The results are in Table 3 There are some interesting findings. For example, there is an exponential number possible patterns, but the number of patterns that appear in the dataset quite small. The ratio of testing points with unobserved patterns is also small, but these unobserved branching leaves seem to be controlled properly. They do not lead to completely different performance compared to those that are observed during training.
C.2 VISUALIZATION
Here we visualize the learned locally constant network on the HIV dataset the representation of its equivalent oblique decision tree in Fig. Since the dimension of Morgan fingerprint (Rogers &
16

---

Published as a conference paper at ICLR 2020
Hahn 2010 is quite high (2,048), here only visualize the top-K weights (in terms of the absolute value) for each decision node. We also normalize each weight such that the & norm of each weight 1. Since the task is evaluated by ranking (AUC), we visualize the leaf nodes in terms of the ranking of output probability among the leaf nodes (the higher the more likely).
Note that complete visualization requires some engineering efforts. Our main contribution here the algorithm that transforms an LCN to an oblique decision tree, rather than the visualization of oblique decision trees, only provide the initial visualization as a proof of concept.
17

---

Published as a conference paper at ICLR 2020
~
0
-00031 J.
2
-0000
0008 X
4
20
<0
Cince "x" .c00e 1 -.000
8
<0
2
J
00000 usee X
13000 X
11
4000 1.
.00003 -
9
>
10
<0
000000 T 10033
0000
14
000000
Y
20
0037
13
12
0000 J vaase
15
Figure 3: Visualization of learned locally constant network in the representation of oblique decision
trees using the proof of Theorem 3 The number the leaves indicates the ranking of output proba- bility among the 16 leaves (the exact value is not important). See the descriptions in Appendix C.2
18


Reviews:
[{"review_id": "rkgFDc0HcB", "reviewer": "AnonReviewer1", "summary": "", "questions": "", "limitations": "", "rating": 6, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "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. \n\nThe detailed comments are as follows:\n\n1) 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. \n\n2) 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. \n\n3) One weakness is that the performance of ELCN seems to be very close to RF, as shown in Table 2. \n\nI 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.\n", "extra_scores": {"experience_assessment": "I do not know much about this area.", "review_assessment:_thoroughness_in_paper_reading": "I read the paper at least twice and used my best judgement in assessing the paper.", "review_assessment:_checking_correctness_of_experiments": "I assessed the sensibility of the experiments.", "review_assessment:_checking_correctness_of_derivations_and_theory": "I carefully checked the derivations and theory."}, "extra_text": {}}, {"review_id": "HJlLZg0dqH", "reviewer": "AnonReviewer3", "summary": "", "questions": "", "limitations": "", "rating": 3, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "*Summary*\nThis 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.\n\n*Rating*\nPerhaps 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.\n\n(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:\n\n(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?\n\n(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.\n\n(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\n\n(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.)\n\n(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\").\n\n*Notes*\n(Spelling typos throughout; most are noted below)\np3: clarify in 3.1/3.3 that L is the number of outputs\np4: \"interpred\"\np5: \"aother\"\np5: Theorem 2 proof: note that the T/T' notation is capturing left/right splits\np5: \"netwoworks\"\np5: \"Remark 5 is important for learning shallow...\": should \"shallow\" be \"narrow\" instead?\np7: in the first paragraph, remind the reader of the definitions of õ^M and J_x ã^M\np7: \"Here we provide a sketch of [the] proof\"\np7: \"unconstraint\" should be \"unconstrained\"\np7: \"...can construct a [sufficiently expressive] network g_\\theta\"\np7: \"simlify\"\np9: Table 2: instead of \"2nd row\", ..., use \"1st section\", ...; also consider noting which methods are introduced in this paper\np9: Figure 2: text is too small\n", "extra_scores": {"experience_assessment": "I have read many papers in this area.", "review_assessment:_checking_correctness_of_experiments": "I carefully checked the experiments.", "review_assessment:_thoroughness_in_paper_reading": "I read the paper thoroughly.", "review_assessment:_checking_correctness_of_derivations_and_theory": "I carefully checked the derivations and theory."}, "extra_text": {}}, {"review_id": "BJg0mfZ2tr", "reviewer": "AnonReviewer2", "summary": "", "questions": "", "limitations": "", "rating": 6, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "In this paper, the authors proposed an approach to fit locally constant functions using deep neural networks (DNNs).\nThe idea is based on the fact that DNN consisting of only linear transformations and ReLU activations is piecewise linear.\nThus, the derivative of such a network with respect to the input is locally constant.\n\nIn the paper, the authors focused on connecting the locally constant network with oblique decision trees.\nSpecifically, they proved that these two models are in some sense equivalent, and one can transform one model to another.\nThis connection enables us to train the oblique decision trees by training the locally constant network instead.\nBecause the locally constant network can be trained using the gradient-based methods, it would be much easier to train than the oblique decision trees.\n\nI think the paper is well-written and the idea is clear.\nConnecting the locally constant network with oblique decision trees looks interesting.\n\nI have one concern, however.\nThe authors mention that the training of oblique decision trees is difficult, and the use of the locally constant network is helpful.\nIf I understand correctly, oblique decision tree is one specific instance of the hierarchical mixtures of experts.\nAnd, [Ref1] pointed out that the hierarchical mixtures of experts can be trained using EM algorithm, which is another type of the gradient-based training.\nThe current paper misses such a prior study.\nI 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.\n\n[Ref1] Hierarchical mixtures of experts and the EM algorithm\n\n\n### Updated after author response ###\nThe authors have successfully demonstrated that the proposed approach is better than the EM-like classical approaches. I therefore keep my score.", "extra_scores": {"experience_assessment": "I have read many papers in this area.", "review_assessment:_checking_correctness_of_experiments": "I assessed the sensibility of the experiments.", "review_assessment:_thoroughness_in_paper_reading": "I made a quick assessment of this paper.", "review_assessment:_checking_correctness_of_derivations_and_theory": "I did not assess the derivations or theory."}, "extra_text": {}}]

Author rebuttal:

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)