Year: 2020

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 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.1

heading: 1 INTRODUCTION
text: Decision trees (Breiman et al., 1984) employ a series of simple decision nodes, arranged in a tree, to transparently capture how the predicted outcome is 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 art models in some tabular (Sandulescu & Chiru, 2016) and chemical datasets (Wu et al., 2018). Deep neural models, in contrast, are highly flexible and continuous, demonstrably effective in practice, though lack transparency. We merge these two contrasting views by introducing a 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 a 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 are no longer available, making these models considerably harder to train. While finding the optimal oblique decision tree can be cast as a mixed integer linear program (Bertsimas & Dunn, 2017), scaling remains a challenge.
In this work, we provide an effective, implicit representation of piece-wise constant mappings, termed locally constant networks. Our approach exploits piece-wise linear models such as ReLU networks as basic building blocks. Linearity of the mapping in each region in such models means that the gradient with respect to the input coordinates is locally constant. We therefore implicitly represent piece-wise constant networks through gradients evaluated from ReLU networks. We prove the equivalence between the class of oblique decision trees and these proposed locally constant neural 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 2M−1 oblique decision nodes. The exponential complexity reduc-
1Our implementation and data are available at https://github.com/guanghelee/iclr20-lcn.
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 converted back to oblique decision trees for interpretability. For learning via gradient descent, however, it is necessary to employ some smooth annealing of piece-wise linear activation functions so as to keep the gradients themselves continuous. Moreover, we need to evaluate the gradients of all the neurons with respect to 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 models (e.g., DropConnect (Wan et al., 2013)) while implicitly training tree models.
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 a large margin, and the ensemble of locally constant networks is competitive with classic ensemble methods.

heading: 2 RELATED WORK
text: Locally constant networks are built on a mixed integer linear representation of piece-wise linear networks, defined as any feed-forward network with a piece-wise 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 an 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 network degenerates to a linear model. The framework motivates us to 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 as deriving robustness certificates (Weng et al., 2018). We refer the readers to the recent work (Lee et al., 2019) and the references therein.
Locally constant networks use the gradients of deep networks with respect to inputs as the representations 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., 2017). When the deep networks model an energy function (LeCun et al., 2006), the gradients can be used to 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 et al., 2014) or perform knowledge distillation (Srinivas & Fleuret, 2018).
The class of locally constant networks is 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) as the activation function. The methods were developed when back-propagation was not yet practically useful, and the motivation is to exploit effective learning procedures of decision trees to train neural networks. Instead, our goal is to 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, there can be ∑D k=0 ( N k ) 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 an 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 et al., 1994) or a coordinate-cut search in some linear projection space (Menze et al., 2011; Wickramarachchi et al., 2016). However, the greedy constructions tend to get stuck in poor local optimum.
There are some works which attempt to find the global optimum given a fixed tree structure by formulating a linear program (Bennett, 1994) or a mixed integer linear program (Bertsimas & Dunn, 2017), but the methods are not scalable to ordinary tree sizes (e.g., depth more than 4). The iterative refinements are more scalable than global optimization, where CART (Breiman et al., 1984) is the typical initialization. Carreira-Perpinán & Tavallali (2018) develop an alternating optimization method via iteratively training a linear classifier on each decision node, which yield the state-of-theart empirical performance, but the approach is only applicable to classification problems. Norouzi et al. (2015) proposed to do gradient descent on a sub-differentiable upperbound of tree prediction errors, but the gradients with respect to oblique decision nodes are unavailable whenever the upperbound is tight. In contrast, our method conducts gradient descent on a differentiable relaxation, which is gradually annealed to a locally constant network.

heading: 3 METHODOLOGY
text: In this section, we introduce the notation and basics in §3.1, construct the locally constant networks in §3.2-3.3, analyze the networks in §3.4-3.5, and develop practical formulations and algorithms in §3.6-3.7. Note that we will propose two (equivalent) architectures of locally constant networks in §3.3 and §3.6, which are useful for theoretical analyses and practical purposes, respectively.

heading: 3.1 NOTATION AND BASICS
text: The proposed approach is built on feed-forward networks that yield piece-wise linear mappings. Here we first introduce a canonical example of such networks, and elaborate its piece-wise linearity. We consider the densely connected architecture (Huang et al., 2017), where each hidden layer takes as input all the previous layers; it subsumes other existing feed-forward architectures such as residual networks (He et al., 2016). For such a network fθ : RD → RL with the set of parameters θ, we denote the number of hidden layers asM and the number of neurons in the ith layer asNi; we denote the neurons in the ith layer, before and after activation, as zi ∈ RNi and ai ∈ RNi , respectively, where we sometimes interchangeably denote the input instance x as a0 ∈ RN0 with N0 , D. To simplify exposition, we denote the concatenation of (a0,a1, . . . ,ai) as ãi ∈ RÑi with Ñi ,∑i j=0Ni, ∀i ∈ {0, 1, . . . ,M}. The neurons are defined via the weight matrix W i ∈ RNi×Ñi−1 and the bias vector bi ∈ RNi in each layer i ∈ [M ] , {1, 2, . . . ,M}. Concretely,
a0 , x, zi , W iãi−1 + bi, ai , σ(zi),∀i ∈ [M ], (1) where σ(·) is a point-wise activation function. Note that both a and z are functions of the specific instance denoted by x, 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)|j ∈ [Ni], i ∈ [M ]}. In this work, we will use ReLU (Nair & Hinton, 2010) as a canonical example for the activation function
aij = σ(z i)j , max(0, z i j),∀(i, j) ∈ I, (2)
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 fθ(x) is the affine transformation from all the hidden layers ãM with the weight matrix WM+1 ∈ RL×ÑM and bias vector bM+1 ∈ RL.

heading: 3.2 LOCAL LINEARITY
text: It is widely known that the class of networks fθ(·) yields a piece-wise 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 an activation pattern is fixed across the entire network, the network degenerates to a linear model and the feasible set with respect to an activation pattern is a natural characterization of a locally linear region of the network.
Formally, we define the activation pattern as the collection of activation indicator functions for each neuron oij : RD → {0, 1},∀(i, j) ∈ I (or, equivalently, the derivatives of ReLU units; see below)2:
oij = ∂aij ∂zij , I[zij ≥ 0],∀(i, j) ∈ I, (3)
2Note that each oij is again a function of x, where we omit the dependency for brevity.
𝐷𝑒𝑓𝑖𝑛𝑒
𝑧# = 𝑥# − 𝑥& + 1; 𝑧& = −4𝑥# + 𝑥& + 4𝑎# + 4; 𝑧' = −𝑥# + 𝑥& + 1.5𝑎# − 0.3𝑎& − 3.
where I[·] is the indicator function. Note that, for mathematical correctness, we define ∂aij/∂zij = 1 at zij = 0; this choice is arbitrary, and one can change it to ∂a i j/∂z i j = 0 at z i j = 0 without affecting most of the derivations. Given a fixed activation pattern ōij ∈ {0, 1},∀(i, j), we can specify a feasible set in RD that corresponds to this activation pattern {x ∈ RD|oij = ōij ,∀(i, j) ∈ I} (note that each oij is a function of x). Due to the fixed activation pattern, the non-linear ReLU can be re-written as a linear function for all the inputs in the feasible set. For example, for an ōij = 0, we can re-write aij = 0×zij . 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 polyhedra3, which realize a 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 et al. (2019) for a detailed justification of the piece-wise linearity of such networks.

heading: 3.3 CANONICAL LOCALLY CONSTANT NETWORKS
text: Since the ReLU network fθ(x) is piece-wise linear, it immediately implies that its derivatives with respect to the input x is a piece-wise constant function. Here we use Jxfθ(x) ∈ RL×D to denote the Jacobian matrix (i.e., [Jxfθ(x)]i,j = ∂fθ(x)i/∂xj), and we assume the Jacobian is consistent with Eq. (3) at the boundary of the locally linear regions. Since any function taking the piecewise constant Jacobian as input will remain itself piece-wise constant, we can construct a 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 as any composite function that leverage the local invariance of piece-wise linear networks. For the theoretical analyses, we consider the below architecture.
Canonical architecture. We denote õM ∈ {0, 1}ÑM as the concatenation of (o1, . . . ,oM ). We will use the composite function g(õM ) as the canonical architecture of locally constant networks for theoretical analyses, where g : {0, 1}ÑM → RL is simply a table. Before elucidating on the representational equivalence to oblique decision trees, we first show some toy examples of the canonical locally constant networks and their equivalent mappings in Fig. 1,
3The boundary of the polyhedron depends on the specific definition of the activation pattern, so, under some definition in literature, the resulting convex polyhedra may not be disjoint in the boundary.
which illustrates their constructions when there is only 1 neuron per layer (i.e., zi = zi1, and similarly for oi and ai). When M = 1, o1 = 1⇔ x1 − x2 + 1 ≥ 0, thus the locally constant network is equivalent to a linear model shown in the middle, which can also be represented as an oblique decision tree with depth = 1. When M > 1, the activations in the previous layers control different linear behaviors of a neuron with respect to the input, thus realizing a hierarchical structure as an oblique decision tree. For example, for M = 2, o1 = 0 ⇔ z1 < 0 ⇒ z2 = −4x1 + x2 + 4 and o1 = 1 ⇔ z1 ≥ 0 ⇒ z2 = −3x2 + 8; hence, it can also be interpreted as the decision tree on the RHS, where the concrete realization of z2 depends on the previous decision variable z1 ≥ 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.

heading: 3.4 REPRESENTATIONAL EQUIVALENCE
text: In this section, we 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 ≥ −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 T ∈ Z>0) for x ∈ RD:
1. r1 , I[ω>∅x + β∅ ≥ 0], where ω∅ ∈ RD and β∅ ∈ R denote the weight and bias of the root decision node.
2. For i ∈ (2, 3, . . . , T ), ri , I[ω>r1:i−1x+βr1:i−1 ≥ 0], where ωr1:i−1 ∈ R D and βr1:i−1 ∈ R
denote the weight and bias for the decision node after the decision pattern r1:i−1.
3. v : {0, 1}T → RL outputs the leaf value v(r1:T ) associated with the decision pattern r1:T . The class of locally constant networks is defined by the canonical architecture with finite M and Ni,∀i ∈ [M ]. We first prove that we can represent any oblique decision tree as a locally constant network. Since a typical oblique decision tree can produce an arbitrary weight in each decision node (cf. the structurally dependent weights in the oblique decision trees in Fig. 1), the idea is to utilize a network with only 1 hidden layer such that the neurons do not constrain one another. Concretely,
Theorem 2. The class of locally constant networks ⊇ the class of oblique decision trees.
Proof. For any oblique decision tree with depth T , it contains 2T − 1 weights and biases. We thus construct a locally constant network with M = 1 and N1 = 2T − 1 such that each pair of (ω, β) in the oblique decision tree is equal to some W 1k,: and b 1 k in the constructed locally constant network.
For each leaf node in the decision tree, it is associated with an output value y ∈ RL and T decisions; the decisions can be written as W 1idx[j],:x + b 1 idx[j] ≥ 0 for j ∈ {1, 2, . . . , T
′} and W 1idx[j],:x + b1idx[j] < 0 for j ∈ {T
′ + 1, T ′ + 2, . . . , T} for some index function idx : [T ] → [2T − 1] and some T ′ ∈ {0, 1, . . . , T}. We can set the table g(·) of the locally constant network as
y, if
{ o1idx[j] = 1(⇔W 1 idx[j],:x + b 1 idx[j] ≥ 0), for j ∈ {1, 2, . . . , T
′}, and o1idx[j] = 0(⇔W 1 idx[j],:x + b 1 idx[j] < 0), for j ∈ {T ′ + 1, T ′ + 2, . . . , T}.
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.
Then we prove that the class of locally constant networks is a subset of the class of oblique decision trees, which simply follows the construction of the toy examples in Fig. 1.
Theorem 3. The class of locally constant networks ⊆ the class of oblique decision trees.
Proof. For any locally constant network, it can be re-written to have 1 neuron per layer, by expanding any layer with Ni > 1 neurons to be Ni 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 x ∈ RD:
1. r1 , o11 = I[ω>∅x + β∅ ≥ 0] with ω∅ = W 11,: and β∅ = b11.
2. For i ∈ (2, 3, . . . ,M), ri , I[ω>r1:i−1x + βr1:i−1 ≥ 0], where ωr1:i−1 = ∇xz i 1 and
βr1:i−1 = z i 1 − (∇xzi1)>x. Note that ri = I[zi1 ≥ 0] = oi1.
3. v = g.
Note that, in order to be a valid decision tree, ω1:ri−1 and β1:ri−1 have to be unique for all x that yield the same decision pattern r1:i−1. To see this, for i ∈ (2, 3, . . . ,M), as r1:i−1 = (o11, . . . ,o i−1 1 ), we know each z i 1 is a fixed affine function given an activation pattern for the preceding neurons, so∇xzi1 and zi1 − x>∇xzi1 are fixed quantities given a decision pattern r1:i−1. Since r1:M = õM and v = g, we 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 a locally constant network with M neurons, and convert it to an oblique decision tree with depth M (for interpretability). Remark 5. The proof of Theorem 3 establishes that, given a fixed number of neurons, it suffices (representationally) to only consider the locally constant networks with one neuron per layer.
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 Ni = 1,∀i ∈ [M ].

heading: 3.5 STRUCTURALLY SHARED PARAMETERIZATION
text: 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 depthM . The result can be intuitively understood by the following reason: we are effectively using M pairs of (weight, bias) in the locally constant network to implicitly realize 2M − 1 pairs of (weight, bias) in the corresponding oblique decision tree. Such exponential reduction on the effective parameters in the representation of oblique decision trees yields “dimension reduction” of 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 3. We start the analysis by a decomposition of ωr1:i among the preceding weights ω∅,ωr1:1 , . . . ,ωr1:r−1 . To simplify notation, we denote ωr1:0 , ω∅. Since ωr1:i = ∇xzi+11 and z i+1 1 is an affine transformation of the vector (a0,a 1 1, . . . ,a i 1),
ωr1:i =∇xzi+11 =W i+1 1,1:D+ i∑ k=1 W i+11,D+k× ∂ak1 ∂zk1 ×∇xzk1 =W i+11,1:D+ i∑ k=1 W i+11,D+k×rk×ωr1:k−1 ,
where we simply re-write the derivatives in terms of tree parameters. Since W i+11,1:D is fixed for all the ωr1:i , the above decomposition implies that, in the induced tree, all the weights ωr1:i in the same depth i are restricted to be a linear combination of the fixed basis W i+11,1:D and the corresponding preceding weights ωr1:0 , . . . ,ωr1:i−1 . We can extend this analysis to compare weights in same layer, and we begin the analysis by comparing weights whose `0 distance in decision pattern is 1. To help interpret the statement, note that ωr1:j−1 is the weight that leads to the decision rj (or r ′ j ; see below). Lemma 6. For an oblique decision tree with depth T > 1, ∀i ∈ [T − 1] and any r1:i, r′1:i such that rk = r ′ k for all k ∈ [i] except that rj 6= r′j for some j ∈ [i], we have
ωr1:i − ωr′1:i = α× ωr1:j−1 , for some α ∈ R.
The proof involves some algebraic manipulation, and is deferred to Appendix A.1. Lemma 6 characterizes an interesting structural constraint embedded in the oblique decision trees realized by locally constant networks, where the structural discrepancy rj in decision patterns (r1:i versus r′1:i) is reflected on the discrepancy of the corresponding weights (up to a scaling factor α). The analysis can be generalized for all the weights in the same layer, but the message is similar. Proposition 7. For the oblique decision tree with depth T > 1, ∀i ∈ [T − 1] and any r1:i, r′1:i such that rk = r′k for all k ∈ [i] except for n ∈ [i] coordinates j1, . . . , jn ∈ [i], we have
ωr1:i − ωr′1:i = n∑ k=1 αk × ωr1:jk−1 , for some αk ∈ R,∀k ∈ [n]. (4)
The statement can be proved by applying Lemma 6 multiple times.
Discussion. Here we summarize this section and provide some discussion. Locally constant networks implicitly represent oblique decision trees with the same depth and structurally shared parameterization. In the implied oblique decision trees, the weight of each decision node is a linear combination of a 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 2M − 1 decision nodes; it yields a strong regularization effect to avoid overfitting, and helps computation by exponentially reducing the memory consumption on the weights.

heading: 3.6 STANDARD LOCALLY CONSTANT NETWORKS AND EXTENSIONS
text: 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 gradients for learning the networks. Indeed, ∇õM g(õM ) is undefined, which implies that ∇W ig(õM ) is also undefined. Here we present another architecture that is equivalent to the canonical architecture, but exhibits sub-gradients with respect to model parameters and is flexible for model extension.
Standard architecture. We assume Ni = 1,∀i ∈ [M ]. We denote the Jacobian of all the neurons after activation ãM as JxãM ∈ RM×D, and denote ~JxãM as the vectorized version. We then define the standard architecture as gφ( ~JxãM ), where gφ : R(M×D) → RL is a fully-connected network.
We abbreviate the standard locally constant networks as LCN. Note that each ai1 is locally linear and thus the Jacobian JxãM is locally constant. We replace õM with JxãM as the invariant representation for each locally linear region4, and replace the table g with a differentiable function gφ that takes as input real vectors. The gradients of LCN with respect to parameters is thus established through the derivatives of gφ and the mixed partial derivatives of the neurons (derivatives of ~JxãM ).
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 fθ, any canonical locally constant network g(õM ) can be equivalently represented by a standard locally constant network gφ( ~JxãM ), and vice versa.
Since fθ and g control the decision nodes and leaf nodes in the associated oblique decision tree, respectively (see Theorem 3), Theorem 8 essentially states that both architectures are equally competent for assigning leaf nodes. Combining Theorem 8 with the analyses in §3.4, we have class-level equivalence 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., fθ). The core ideas for proving Theorem 8 are two-fold: 1) we find a bijection between the activation pattern õM and the Jacobian ~JxãM , and 2) feed-forward networks gφ can map the (finitely many) Jacobian ~JxãM 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 parameterization (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 gφ.
Extensions. The construction of (standard) locally constant networks enables several natural extensions due to the flexibility of the neural architecture and the interpretation of decision trees. The original locally linear networks (LLN) fθ, which outputs a linear function instead of a constant function for each region, can be regarded as one extension. Here we discuss two examples.
• 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 an approximately locally constant derivative for inputs with large absolute value. Note that the canonical architecture (tabular g) is not compatible with such extension. 4In practice, we also include each bias ai1 − (∇xai1)>x, which is omitted here to simplify exposition.
• Ensemble locally constant networks (ELCN): since each LCN can only output 2M different values, 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[e]φ ( ~Jxã M,[e]) to denote a
base model in the ensemble, and denote the ensemble with E models as ∑E e=1 g [e] φ ( ~Jxã M,[e]).

heading: 3.7 COMPUTATION AND LEARNING
text: In this section, we discuss computation and learning algorithms for the proposed models. In the following complexity analyses, we assume gφ to be a linear model.
Space complexity. The space complexity of LCN is Θ(MD) for representing decision nodes and Θ(MDL) for representing leaf nodes. In contrast, the space complexity of classic oblique decision trees is Θ((2M − 1)D) for decision nodes and Θ(2ML) 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 ~Jxã
M = [∇xaM1 , . . . , ∇xa11], which can be computationally challenging to obtain. Existing automatic differentiation (e.g., back-propagation) only computes the gradient of a scalar output. Instead, here we propose an efficient dynamic programming procedure which only requires a forward pass:
1. ∇xa11 = o11 ×W 1. 2. ∀i ∈ {2, . . . ,M},∇xai1 = oi1 × (W i1,1:D + ∑i−1 k=1 W i 1,D+k∇xak1),
The complexity of the dynamic programming is Θ(M2) due to the inner-summation inside each iteration. Straightforward back-propagation re-computes the partial solutions∇xak1 for each∇xai1, so the complexity is Θ(M3). We can parallelize the inner-summation on a GPU, and the complexity of the dynamic programming and straightforward back-propagation will become Θ(M) and Θ(M2), respectively. Note that the complexity of a forward pass of a typical network is also Θ(M) on a GPU. The time complexity of learning LCN by (stochastic) gradient descent is thus Θ(Mτ), where τ denotes the number of iterations. In contrast, the computation of existing oblique decision tree training algorithms is typically data-dependent and thus the complexity is hard to characterize.
Training LCN and ALCN. Even though LCN is sub-differentiable, whenever oi1 = 0, the network does not exhibit useful gradient information for learning each locally constant representation∇xai1 (note that ~JxãM = [∇xa11, . . . ,∇xaM1 ]), since, operationally, oi1 = 0 implies ai1 ← 0 and there is no useful gradient of ∇xai1 = ∇x0 = 0 with respect to model parameters. To alleviate the problem, we propose to leverage softplus as an infinitely differentiable approximation of ReLU to obtain meaningful learning signals for∇xai1. Concretely, we conduct the annealing during training:
ai1 = λt max(0, z i 1) + (1− λt) log(1 + exp(zi1)),∀i ∈ [M ], λt ∈ [0, 1], (5)
where λt is an iteration-dependent annealing parameter. Both LCN and ALCN can be constructed as a special case of Eq. (5). We train LCN with λt equal to the ratio between the current epoch and the total epochs, and ALCN with λt = 0. Both models are optimized via stochastic gradient descent.
We also include DropConnect (Wan et al., 2013) to the weight matrices W i ← drop(W i) 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 oi1 = 0 to o i 1 = 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 a boosting fashion:
1. We first train an initial locally constant network g[1]φ ( ~Jxã M,[1]). 2. For each iteration e′ ∈ {2, 3, . . . , E}, we incrementally optimize ∑e′ e=1 g [e] φ ( ~Jxã M,[e]).
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, 2001).

heading: 4 EXPERIMENT
text: Here we evaluate the efficacy of our models (LCN, ALCN, and ELCN) using the chemical property prediction datasets from MoleculeNet (Wu et al., 2018), where random forest performs competitively. We include 4 (multi-label) binary classification datasets and 1 regression dataset. The statistics are available in Table 1. We follow the literature to construct the feature (Wu et al., 2018). Specifically, we use the standard Morgan fingerprint (Rogers & Hahn, 2010), 2,048 binary indicators of chemical substructures, for the classification datasets, and ‘grid features’ (fingerprints of pairs between ligand and protein, see Wu et al. (2018)) for the regression dataset. Each dataset is 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. (2016); oblique decision trees induced greedily on linear projections), and TAO (CarreiraPerpinán & Tavallali (2018); oblique decision trees trained via alternating optimization).
• Tree ensembles: RF (Breiman (2001); random forest) and GBDT (Friedman (2001); gradient boosting decision trees).
• Graph networks: GCN (Duvenaud et al. (2015); graph convolutional networks on molecules). For decision trees, LCN, LLN, and ALCN, we tune the tree depth in {2, 3, . . . , 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, we tune the number of hidden layers of gφ in {0, 1, 2, 3, 4} (each with 256 neurons) for the regression task, and simply use a linear model gφ for the classification tasks. For ELCN, we use ALCN as the base model, tune the ensemble size E ∈ {20, 21, . . . , 26} for the classification tasks, and E ∈ {20, 21, . . . , 29} 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 are available in Appendix B.
We follow the chemistry literature (Wu et al., 2018) to measure the performance by AUC for classification, and root-mean-squared error (RMSE) for regression. For each dataset, we train a model for
each label, compute the mean and standard deviation of the performance across 10 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 state-of-the-art performance. The continuous extension (ALCN) always improves the empirical performance of LCN, which is 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 is the state-of-the-art method for learning oblique decision 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 generalization performance in the large HIV dataset. We conduct an 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 generalization (Fig. 2c), all of the competitors do not perform well and overfit fairly quickly. In stark contrast, LCN outperforms the competitors by a large margin and gets even more accurate as the depth increases. This is expected due to the strong regularization of LCN that uses a linear number of effective weights to construct an 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 C.

heading: 5 DISCUSSION AND CONCLUSION
text: We create a novel neural architecture by casting the derivatives of deep networks as the representation, which realizes a 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 methods. This work can be used to interpret methods that utilize derivatives of a network, such as training a generator through the gradient of a 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 as the inner randomization of random forest.

heading: ACKNOWLEDGMENTS
text: GH and TJ were in part supported by a grant from Siemens Corporation. The authors thank Shubhendu Trivedi and Menghua Wu for proofreading, and thank the anonymous reviewers for their helpful comments.

heading: A PROOFS
text: A.1 PROOF OF LEMMA 6
Proof. We fix j and do induction on i. Without loss of generality, we assume 1 = rj 6= r′j = 0.
If i = j, since r′j = 0, we have{ ωr1:i = W i+1 1,1:D + ∑i k=1 W i+1 1,D+k × rk × ωr1:k−1 ,
ωr′1:1 = W i+1 1,1:D + ∑i−1 k=1 W i+1 1,D+k × rk × ωr1:k−1 .
Hence, we have ωr1:i − ωr′1:1 = (W i+1 1,D+i × ri)× ωr1:i−1 = α× ωr1:j−1 .
We assume the statement holds for up to some integer i ≥ j:
ωr1:i − ωr′1:i = α× ωr1:j−1 , for some α ∈ R.
For i+ 1, we have
ωr1:i+1 =W i+2 1,1:D + i+1∑ k=1 W i+21,D+k × rk × ωr1:k−1
=W i+21,1:D + j−1∑ k=1 W i+21,D+k × rk × ωr1:k−1 + W i+2 1,D+j × rj × ωr1:j−1
+ i+1∑ k=j+1 W i+21,D+k × rk × ωr1:k−1
=W i+21,1:D + j−1∑ k=1 W i+21,D+k × r ′ k × ωr′1:k−1 + W i+2 1,D+j × rj × ωr1:j−1
+ i+1∑ k=j+1 W i+21,D+k × r ′ k × (ωr′1:k−1 + αk × ωr1:j−1), for some αk ∈ R
=W i+21,1:D + i+1∑ k=1 W i+21,D+k × r ′ k × ωr′1:k−1
+ (W i+21,D+j × rj + i+1∑
k=j+1
W i+21,D+k × rk × αk)× ωr1:j−1
=ωr′1:i+1 + α× ωr1:j−1 , for some α ∈ R
The proof follows by induction.
A.2 PROOF OF THEOREM 8
Proof. We first prove that we can represent any gφ( ~JxãM ) as g(õM ). Note that for any x mapping to the same activation pattern õM , the Jacobian ~JxãM is constant. Hence, we may re-write the standard architecture gφ( ~JxãM ) as gφ( ~J(õM )), where ~J(õM ) is the Jacobian corresponding to the activation pattern õM . Then we can set g(·) , gφ( ~J(·)), which concludes the first part of the proof. To prove the other direction, we first prove that we can also write the activation pattern as a function of the Jacobian. We prove this by layer-wise induction (note that õM = [o11, . . . ,o M 1 ] and ~Jxã
M = [∇xa11, . . . ,∇xaM1 ]):
1. The induction hypothesis (i ≥ 2) is that [o11, . . . ,oi−11 ] is a function of [∇xa11, . . . ,∇xa i−1 1 ].
2. If W 1 = 0 (zero vector), z11 , a11, and o11 are constant (thus being a function of∇xa11). Otherwise, ∇xa11 = 0⇔ o11 = 0 and ∇xa11 = W 1 ⇔ o11 = 1, so o11 can be written as a function of∇xa11.
3. Assume that we are given [∇xa11, . . . ,∇xai−11 ] and the corresponding [o11, . . . ,o i−1 1 ].
If either oi1 = 0 or o i 1 = 1 is infeasible (but not both), by induction hypothesis, [o 1 1, . . . ,o i 1] can be written as a function of [∇xa11, . . . ,∇xai1]. If oi1 = 1 for some x ′ and oi1 = 0 for some x ′′, we claim that oi1 = 1⇒ ∇xai1 6= 0:
If oi1 = 1 and ∇xai1 = 0, we have oi1 = 1 ⇒ ai1 = zi1 ≥ 0 and 0 = ∇xai1 = ∇xzi1, which implies that the bias (of zi, given [o11, . . . ,o i−1 1 ]) z i 1− (∇xzi1)>x ≥ 0. Note that both∇xzi1 and zi1−(∇xzi1)>x are constant given [o11, . . . ,oi−11 ], regardless of oi1. Hence, given [o11, . . . ,o i−1 1 ], we have zi1 = z i 1 − (∇xzi1)>x ≥ 0 and oi1 = 0 is infeasible (⇒⇐).
Note that, given fixed [o11, . . . ,o i−1 1 ], ∇xai1 6= 0 has a unique value in Rd. Combining the result oi1 = 1 ⇒ ∇xai1 6= 0 with oi1 = 0 ⇒ ∇xai1 = 0, there is a bijection between oi1 and ∇xai1 in this case, which implies that [o11, . . . ,o i 1] can be written as a function of [∇xa11, . . . ,∇xai1].
The derivation implies that we may re-write the canonical architecture g(õM ) as g(õ( ~JxãM )), where õ( ~JxãM ) is the activation pattern corresponding to the Jacobian ~JxãM . Hence, it suffices to establish that there exists a feed-forward network gφ such that gφ( ~JxãM ) = g(õ( ~JxãM )) for at most 2M distinct ~JxãM , which can be found by the Theorem 2.5 of Hornik et al. (1989) or the Theorem 1 of Zhang et al. (2017).
B IMPLEMENTATION DETAILS
Here we 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-learn (Pedregosa et al., 2011) implementation of gradient boosting trees. We tune the number of estimators in {23, 24, . . . , 210}.
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 classification tasks, we set the learning rate as 0.1, which is annealed by a 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 30 epochs (60 epochs in total).
Both LCN and ALCN have an extra fully-connected network gφ, which transforms the derivatives ~Jxã
M to 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 gφ in {0, 1, 2, 3, 4} (each with 256 neurons) for the regression dataset, and simply use a linear gφ for the classification datasets.
For ELCN, we fix the depth to 12 and tune the number of base models E ∈ {20, 21, . . . , 26} for the classification tasks, and E ∈ {20, 21, . . . , 29} for the regression task. We set the DropConnect probability 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 to incrementally learn the ELCN, so we use the AMSGrad optimizer (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.

heading: C SUPPLEMENTARY EMPIRICAL ANALYSIS AND VISUALIZATION
text: C.1 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 no training data that are routed to the nodes. It is impossible for traditional (oblique) decision tree training algorithms to learn the values of such nodes (e.g., the output value of a 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 a few things pertaining to the unobserved nodes:
• # of training patterns: the number of distinct end-to-end activation / decision patterns r1:M encountered in the training data. • # of testing patterns: the number of distinct end-to-end activation / decision patterns r1:M encountered ib the testing data. • # of testing patterns - training patterns: the number of distinct end-to-end activation / decision patterns r1: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 ith as ŷi ∈ [0, 1] and yi ∈ {0, 1}, respectively. We collect the subset of indices I of the testing data such that their activation / decision patterns r1:M are observed in 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 a subset of points I as:∑
i∈I ∑n j=1 ( I[yi > yj ] ( I[ŷi > ŷj ] + 0.5I[ŷi = ŷj ] ) + I[yi < yj ] ( I[ŷi < ŷj ] + 0.5I[ŷi = ŷj ] )) ∑ i∈I ∑n j=1 ( I[yi > yj ] + I[yi < yj ])
) . (6)
When I = [n], the above measure recovers AUC. • Testing performance - unobserved patterns: the same as above, but use I for the testing data such
that their activation / decision patterns r1: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 of possible patterns, but the number of patterns that appear in the dataset is 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 in the representation of its equivalent oblique decision tree in Fig. 3. Since the dimension of Morgan fingerprint (Rogers &
Hahn, 2010) is quite high (2,048), here we only visualize the top-K weights (in terms of the absolute value) for each decision node. We also normalize each weight such that the `1 norm of each weight is 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 a complete visualization requires some engineering efforts. Our main contribution here is the algorithm that transforms an LCN to an oblique decision tree, rather than the visualization of oblique decision trees, so we only provide the initial visualization as a proof of concept.

Review summaries:
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.

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.