Sparse Hierarchical Table Ensemble
Authors: Guy Farjon
Aharon Bar HIllel
Venue: ICLR 2022 Submitted (2022)
Keywords: tabular data
DL alternative
architecture

Abstract: Deep learning for tabular data is drawing increasing attention, with recent work attempting to boost the accuracy of neuron-based networks. However, when computational capacity is low as in Internet of Things (IoT), drone, or Natural User Interface (NUI) applications, such deep learning methods are deserted. We offer to enable deep learning capabilities using ferns (oblivious decision trees) instead of neurons, by constructing a Sparse Hierarchical Table Ensemble (S-HTE). S-HTE inference is dense at the beginning of the training process and becomes gradually sparse using an annealing mechanism, leading to an efficient final predictor. Unlike previous work with ferns, S-HTE learns useful internal representations, and it earns from increasing depth. Using a standard classification and regression benchmark, we show its accuracy is comparable to alternatives while having an order of magnitude lower computational complexity. Our PyTorch implementation is available at https://anonymous.4open.science/r/HTE_CTE-60EB/

Under review as a conference paper at ICLR 2022
SPARSE HIERARCHICAL TABLE ENSEMBLE
Anonymous authors
Paper under double-blind review
ABSTRACT
Deep learning for tabular data is drawing increasing attention, with recent work attempting to boost the accuracy of neuron-based networks. However, when com- putational capacity is low as Internet of Things (loT), drone, or Natural User Interface (NUI) application, such deep learning methods are deserted. We offer to enable deep learning capabilities using ferns (oblivious decision trees) instead of neurons, by constructing Sparse Hierarchical Table Ensemble (S-HTE). S-HTE inference is dense at the beginning of the training process and becomes gradu- ally sparse using an annealing mechanism, leading to an efficient final predictor. Unlike previous work with ferns, S-HTE learns useful internal representations, and it earns from increasing depth. Using standard classification and regres- sion benchmark, we show its accuracy is comparable to alternatives, while hav- ing order of magnitude lower computational complexity. Our PyTorch imple- mentation is available at phtttps://anonynnne CTE- 60EB/
4open. wopen.scieeee wwc.enccer//ii
INTRODUCTION
During the last decade, Deep Neural Networks (DNNs) have become dominant for many ma- chine learning tasks in computer vision, natural language processing, speech recognition, and oth- ers (Goodfellow et al. (016). However, when dealing with tabular data, DNNs superiority is in doubt with non-deep models such as Gradient Boosting Decision Tree (GBDT) (Friedman) 2001) being the top choice for many machine learning practitioners. Currently. deep learning and deep neural networks mostly refer to the same thing. Though the tight coupling between these two concepts is natural, given the numerous published studies, these are two different concepts. Deep learning is the learning of hierarchical useful representation, while neural networks are predictors using dot- product based neurons as their basic elements. In this work, we decouple the connection of deep learning to DNNs by introducing a deep learning alternative based on differentiable ferns as the basic computation unit. Ferns (also termed Oblivious Decision Tree (fern) in [Popov et al. (2019); Kohavi (1994); Lou & Obukhov (2017)) are using K simple feature comparisons to choose among 2 possible outputs, and are hence far more expressive than linear neuron with an activation func- tion. In turn, deep predictors based on ferns can enjoy extreme sparsity, and provide accuracy-speed trade off far beyond standard DNNs.
We introduce Sparse Hierarchical Table Ensemble (S-HTE), specifically design to face tabular data tasks when extremely fast inference needed. The basic neuron in S-HTE architecture computes the answer of K simple binary questions, creating a K K-length binary word. This word is then used as index to a table from which the required output is retrieved. The analog of neuron layer (an ensemble of neurons). is an ensemble of M tables, applied with their output summed. The deep S-HTE consists of several layers, constructed hierarchically in order learn deep representations. During training, the architecture enables soft (ambiguous) splits in each fern node, allowing the examples to flow in each of the fern's branches with a certain probability. This enables the S-HTE to be completely differentiable and hence to be fully optimized using SGD. However, since we aim for extremely fast inference, we gradually sharpen the split decisions during the training process, so only one leaf is active in each fern inference time.
S-HTE can be implemented using any of the recent deep learning frameworks (e.g. TensorFlow, Pytorch, etc.), and scales well to large problems. effectively trading speed for memory. While ferns have been used in classification before (Popov et 2019 Krupka et al. 2014), the method of Popov et al. (2019) is not sparse, while the ensembles of Krupka et al. (2014) are not deep. Our method is

---

Under review as a conference paper at ICLR 2022
hence the fern-based method enabling results with accuracy comparable deep MLPs, yet with fraction of the computing power.
The main motivation to deviate from dot-product neurons is the need for fast and efficient CPU inference. Ferns are a good choice since they have a much better relation of representation capac- ity to computational cost than a linear neuron. In representation richness terms, a binary classifier built from a single fern with K queries has a VC-dimension of 0(2*), compared to O(K) for a linear neuron with K inputs. However, computationally they have the same O(K) cost. Consid- ering the index produced the K fern queries as a one-hot vector, this intermediate representation has 2 dimensions, but is nevertheless 2 K -sparse. The table transforming the codeword to the next representation has 2 rows, each containing an output vector for the next level D D-dimensional representation, for total of 2 Dout parameters. Thus, single fern provides a rich transformation family of O(2 Dout) parameters, computed using just O(K + Dout) computations.
We demonstrate that despite the significantly non-linear elements and the extreme sparsity, networks based on S-HTE layers can be successfully trained end-to-end. On a recent benchmark of tabular data tasks (Gorishniy et al. 2021) the method achieves accuracy comparable or slightly lower than state of the art methods while using an order of magnitude lower computational complexity. This trade off is highly valuable for applications on low-end GPU-lacking devices prevalent for example in IOT, embedded or drone upplications. Such low computational complexity capabilities are also required for 'keep-alive' devices, which demands maintaining long battery life.
Our main contribution is hence in introducing fern-based method which is both deep and sparse, while previous similar methods only have one of these qualities. We show that this combination enables gaining order of magnitude in compute power, with small accuracy costs of 2 - 33% at most on a contemporary benchmark. Our Pytorch code is open and available to the community| |
The rest of the paper is organized follows: in section 2 we discuss the most relevant recent work. In section 3 we describe our proposed S-HTE architecture. The computational complexity of the S- HTE and other competitors is analyzed in section The experimental details are detailed in section 5, and section 6 contains some concluding remarks.
RELATED WORK
In recent years gradient-based deep learning models for tabular data getting increasing attention. while our method mainly pinpoints inference speed. the vast majority of the latest work focuses on accuracy improvements (Kadra et al. 2021 Gorishniy et al. 2021 Popov et al. 2019. Katzir et al, 2020 Fiedler 2021 Yang al. 2018). In this section review some of the latest gradient- based models, as well as other dineeiffeeee models which are the most relevant to the proposed method.
Ensemble-based and multi-layered non-differentiable methods. For most tabular data tasks, decision trees based architectures are currently the top-choice for both researchers and practitioners. These architectures are divided into two main groups ensemble of decision trees, and multi-layered models with decision trees being the computational components. Ensemble of decision trees, mostly trained in a boosting like manner, includes several widely used implementations, such as XGBoost Chen Guestrin 2016). LightGBM (Ke et al. 2017), and CatBoost (Prokhorenkova et al. 2017). Though these vary in details, their performance is quite similar. For example, the computational component in XGBoost are Random Decision Trees (RDTs), but in CatBoost these are ferns. Ferns are slightly weaker learners than trees in terms of capacity, but they are faster on modern machines with SIMD (Single Instruction Multiple Data) capabilities (see 3.1 for further discussion). Another line of work is stacking several non non-differenntialee layers into multi- multi-layered architectures (Zhou & Feng 2017 Miller et al., (017)) 7).. For example, /Zou & Feng (2017) presented a deep random forest architecture in which several layers are stacked. Since random forest are not suitable for gradient based learning, each such layer is trained separately, lacking the capability for end-to-end training.
Differentiable decision trees based architectures. The above methods are widely used and achieves state of the art results on tabular datasets, but do not enable gradient flow and end-to-end representation learning. To address this issue, several works enabling gradient based learning with
https://ancnymous.. 4open sci
www.:nsscinnnceeeeeeeeeeeee weweee/ecereeeee 608H/
2

---

Under review as a conference paper at ICLR 2022
decision trees were published in recent years (Yang al. 2018 Kontschieder et al. 2015 Hazimeh (et al. 2020 Popoy et al. 2019). The authors in Kontschieder et al. al. (2015) proposed the deep neural decision forest, in which feature representation learned using CNNs, and the classification is done using differential decision trees. Hazimeh et al. (2020) propose to create differentiable tree routing, by smoothing the decision functions in the internal tree nodes. [Popov et al. (2019) suggested the NODE architecture, in which they smooth ferns into differentiable ferns using the entmax function (Peters al. 2019), but the fern output is dense with all the 2* fern leaves active both train and test time. The output of each layer is logit classification vector, which is concatenated with the input vector and pushed to the next layer in the architecture. The final prediction logit (2 or output neurons in the experiments) is the average across all layer predictions. Flat and deep architectures ({2,4,8) layers) were tested, with 2048 ferns each. Since the output neurons of each layer are direct classification logits (Gorishniy et al.] (02T)) there is no learning of internal representation. In a recent study (Kadra et al. 2021) this method was found non scalable due to memory constraints or run time issues (above 4 days of training), resulting from the unlimited dense output of the ferns involved. The S-HTE method does not suffer from these problems. It learn an internal representation which is not directly class-related, To achieve scalability and efficient inference it structurally limits the number of active fern leaves, and shifts toward sharp ferns as training progresses.
State of the art DNNs for tabular data. There is an extensive research on how to operate standard DNN models on tabular data. For example, Kadra et al.] (2021) reports that using a standard MLP (with or without dropout) achieves inferior results. However, by using several regularization tech- niques, they were able to boost the MLP performance. Gorishniy et al. (202T) showed that using a standard ResNet provides state-of-the-art results on several known datasets. [Shavitt& & Segal (2018) propose to infuse feature importance to standard DNNs by adding a coefficient for each feature weight and solving the task using hyperparameter tuning scheme (resulting with what they termed 'regularization learning networks'). However, in their paper, they do not compare with properly tuned GBDT implementations, which are the most appropriate baselines. Another line of work is to incorporate attention mechanisms to solve tabular datasets tasks(Song et al. [2099; Anik & Pfister, 2020 Gorishniy et al., (222). FT-Transformer (Gorishniy et al.] (2021) is such an example, using a feature tokenizer embed the input features and then applying several stacked attention layer over the embedded features.
3 METHOD
In this section we introduce the core building block in our algorithm, then move on to explain how to train such a model using gradient based learning
3.1 INTRODUCTION TO FERNS
The basic computing element of the S-HTE model accepts a representation vector x E Pi. and outputs a representation vector E R The transformation is a pair of a word calculator (W) and a voting table (V). W is feature extractor applied on the input and returning a K-bit index ie. function W Ri... + {0, 1 The computed code-word is then used to select the output representation form the voting table V E R Pouc:
Bit functions- K simple bit functions are used to compute the code-word W(x; θ), each computing a single bit. Each bit function compares a single feature to a threshold:
w* (z. θ*) = Q(u x th*)
Where x² E P.... is 1-hot vector, addressing single feature from æ. The learned parameters in the bit function are ** juu ,th"]. Notice that the output of the above comparison is scalar, hence an Heaviside function Q(-) is applied to produce the needed output: w² (I, θ*) e {0,
Ferns- ferns are similar to standard decision trees, but with one important difference the queries in each node of the same level are fixed, i.c the choice of w; does not depend on the results of w, for j < i. Fern is a common machine learning algorithm, and is mostly known as the base predictors of the CatBoost model (Prokhorenkova et al. 2017). The computed
is denoted by
W(x; θ) (w" (w"(2,, 00), totk K- 1 (k-1))
3

---

Under review as a conference paper at ICLR 2022
Empurt
w
w²
0
100
output
(a) Single sharp fern
(b) Ensemble of sharp ferns
Figure I: Illustration of the fern sharp graph including the bit functions and the voting tables. a the bit functions operates on single input features. Bits are concatenated into single word, pointing to a row the voting table. The output is Dout dimensional vector. b the voting tables' outputs are summed across ferns.
Since each bit function outputs single bit, the code-word is K-bit word in a binary expression.
Voting table The computed code-wort is then transformed a numeric value and used an index to select the D Dow:-dimensional output representation vector from voting table V:
h(x) = ViW (2, :).:]
(3)
Notice that in the hard version of ferns, W points to a single row in the voting table V and hence the output h(x)) is a vector. The scheme of a complete fern, including W and V is illustrated in Figure la
Fern ensemble- - Instead of using a single fern, the S-HTE layer consists an ensemble of M weak Ferns outputs are summed to get the layers' final output (see Figure 1b
learners (W.. Vn 1M
y ΣM Pim (x)
3.2 DIFFERENTIABLE FERNS
In section 3.1 deseribe the basic layer of the deep S-HTE architecture. However, In order to enable end end-2-end optimization using gradient based learning, we need to softener the hard compo- nents:
Learnable bit functions Instead of forcing bit functions to focus on pre-defined features, we allow them learn which feature relevant. In Popov al. (2019), the entmax (Peters et al., 2019 function was used to choose the features for each bit function. However, as Popov et al. (2019) reported, the entmax function is slow, and though it achieved the best results. it has small margin from the other feature selection options (e.g softmax, and sparsemax (Martins & Astudillo, 2016 Hence, we drop the 1-hot vector u IR Din from Eq. [ and replace with a weights vector as follows:
exp(3 by) Din exp(3 -b))
u = SoSooooaaapp
Uj
(5)
Here, are the learnable parameters that represent the contribution of each input feature. Now, the output is continuous and differentiable. Notice that the output of these bit function are linear com- bination of the input with respect to the weights U. At the beginning of the training process, the weights will be set randomly, allowing multiple features to contribute. but the training progresses, we want the bit function to focus on a specific feature for the decision (for each of the bit functions in each fern). Hence will anneal the temperature parameter 3 from to 3 >> 1.
4

---

Under review as a conference paper at ICLR 2022
Soft ferns- As mentioned, since the output of a bit function (see Eq. D is scalar, the Heaviside function is used. Since Q(x) is not continuous in x = 0 and its gradient equals to zero everywhere else, the use of this function is inappropriate for gradient based learning. Hence, smooth linear sigmoid is used instead:
x>6
g(x; 1)
ztt 20
-t<a<t
x x<-
This function behaves like the Heaviside function for values far from 0 but linear in the section [-t, and hence has gradient in it. When t + 0, g(x,t) approaches the Heaviside function. Thus can be considered as a hyperparameter controlling the smoothness of the linear sigmoid. In addition, this function has the property q(x; 1) + vk-=x;0 1) = 1. g( (a:; ²²);() () can interpret as a 'soft' bit, with g(w²) estimating the probability of the bit to be I and q(-w") the probability to be O. As stated above, the word calculator W maps an example E R: to single code-word, or equivalently into a (row) one-hot vector in R²² Denote the word calculator viewed as a function :RD: possible word a probability- value. For each code-word b E {O...., 2 1}, the activity level is defined by
into IR2 by W, We now extend it to a soft word calculator W : RDD + R²² assigning each
K (x: O) II ((((b,)) w (x;
Where sb,, k)(=1)(++((b)) is the sign of the h bit, with a(b, k) denotes the hhth bit of the code- word b in the standard binary expansion. s(b, k) is 1 if bit k 1, and -1 if bit k 0. The probability-like activity level of a word b is defined as the product of the 'probability" of its single bits. For single hard fern, its output can be written as the product W V. The soft fern is the natural extension W V. Here instead of taking single output from the table V, the Soft-fern outputs a weighted word activation based on the activity levels of the word indices. Furthermore, in our implementation, we may allow only B number of indices to be non-zero for computational complexity considerations.
The sparsity of the soft word calculator is controlled by the parameter / of the linear sigmoid in Eq. 6 that acts as a threshold. When t is large, most of the bit functions are 'aambiguou',, i.c not strictly 0 or I, and the output will be dense. Thus the parameter controls the output sparsity level. In particular, as + the bit functions become hard and W converges toward a hard fern with single active output word. While we need dense flow of information and gradients in the training phase, fast inference requires sparse output. Hence, we use annealing schedule mechanism, such that t is initiated as > 0, set to allow a fraction f of the bit functions values be the 'soft zone' t-t; The value of t is then gradually lowered achieve sharp and sparse classifier towards the end of the training phase.
Annealing mechanism
3.3 MOVING TO DEEP LEARNING S-HTE ARCHITECTURE
The above section describes a single layer of the deep S-HTE architecture. Similar other deep learning schemes, we can stack multiple such layers, where the input of layer j is the output of layer i for j > The number of output features (i.e Dout) is arbitrary and should be tuned similarly to tuning the number of neurons in standard MLP. It is worth mentioning that other similar methods, e.g (Popov et al. 2019 Zhou & Feng 2017) usually use Dout number of classes (for |Popoy et al.) (2019) this is the case due to the computational burden of increasing Dout). By allowing arbitrary Dout size, we enable better representation learning. The final prediction will be the output of the last layer and we train model end-2-end with backpropagation. Our architecture is best presented in figure 2
Adding deep learning machinery In the last several years, different regularization methods were reported to achieve significant improvements for deep networks (Zhang et al. 2017 Kadra et al. 2021). In this paper, since we using deep model, First, We experimented with different models architectures and found that using a ResNet- like struc- ture (i.e the input to layer j will be the sum of the output of layer with the input of layer i, where
exploit these regularization techniques.
5

---

Under review as a conference paper at ICLR 2022
000
000
I
final prediction
000
cuncatenstt
Figure 2: Deep S-HTE architecture multiple layers scheme. Each voting table output is summed to get the layer's i output. This output in then concatenated with the input example (green lines), and the outputs of each layer is summed across layers (red line).
j along with the concatenation of the input example, yields the best results. Second, we add batch normalization layer, weight decay factor and use different learning rate schedulers.
4 COMPUTATIONAL COMPLEXITY COMPARISON
We analyze computational complexity based on the number of expected operations in S-HTE and other relevant models: MLP, Fr-arfffformer (Gorishniy et al.) 202T). NODE (Popov et al., 2019) and decision tree ensembles. For deep methods, we assume for simplicity that all layers have the same internal representation dimension D. For operation count we consider multiply-accumulate as a single operation, and denote by I the number of instructions required for bit function compu- tation. Typically / is 3 operations: comparison to threshold, a shift left operation, and an or operation to store the computed bit.
S-HTE complexity. A standard S-HTE uses single B-bits index for inference in each fern. A single fern inference hence requires the index computation with BI operations and then addition of the relevant table row the output representation with d operations. The total inference cost for layers of M ferns each is
LM + D)
(8)
In this analysis we neglect the cost of bypass additions (LD operations) and classification head computation (DK operations, with C' the number of classes).
When ferns with P split-able bits are considered, the number of active words used in inference is 2". For each such word index computation required / bit operations, and probability computation requires P multiply operations. The total computation of the 2 words is hence 2P operations. Adding the relevant 2" table rows with the corresponding weights requires 2" operations, so the total inference cost is
LM + + 2PP D))
In our multi-word predictors, we consider modest numbers of ferns M S 100 and split-able bits P = 2.3.
NODE. The NODE architecture is similar to our multi-word predictors, but with the crucial differ- ence of using all bits split-able bits, i.e. p= B. Since the dependence on P is exponential, this lead to a dramatic complexity difference.
Standard MLP. The first layer in an MLP with D... input includes D operations and the rest of the layers are with D2 operation count. the total complexity (ignoring bypass and the classification head) hence has quadratic dependency on D)
(T. 1) D D
(10)

---

Under review as a conference paper at ICLR 2022
FT-rraasformer. The architecture suggested in Gorishniy al. (202) includes feature tokenizer, folllowed by L = 3 attention layers and a prediction head. Encoding by the tokenizers requires Din D operations. The attention model in each layer requires 3D;,, D operations for Q, V, K matri- ces creation, D / for computing the Din key-query matrices, and D D for computing the output messages. The MIP following each attention module also requires Da, D2 operations, the total per L layers (ignoring the negligible O D) operations) is
L,3D D2 2D D)
(11)
Shallow ensemble trees. A single tree in such ensembles is extremely fast, requiring BI operations for bit function compute followed by C' additions gather the class votes. However, the total inference cost is (BI++ C') and the number of trees required by such methods is very large due to their shallow architecture and step-wise optimization. Specifically, Thousands of trees are typically required to reach high accuracy, while S-HTE typically uses several hundreds.
In section 5 the speed and accuracy of S-HTE is compared to the above-mentioned methods with their real implementation parameters (see table 2
EXPERIMENTS
Experimental settings. The S-HTE is fully implemented in PyTorch and is publically available" The training code was developed to utilized the GPU, and models were trained on a 1080TI Nvidia- GPU. We used ADAM (Kingma & Ba 2014) optimizer, and enabled different learning rates for the ferns' and the voting tables' parameters voting table parameters may have a high learning rate as opposed word calculators, where each gradient-step can dramatically effect the function's output. We also report how we set tlper-parameters' values in our experiments, as well as the model's s architecture and weights initialization.
Training procedure. Similar to DNNs, the S-HTE architecture is trained end-to-ens with mini- batch SGD. We used batch sizes related the dataset size (following (Gorishniy al.) (02I)) and trained the network for 80 epochs. For classification tasks, we minimize the cross-entropy loss function, and for regression tasks we minimize the mean-square-errot: We save the final trained model (in which all the ferns are sharp and only single word is used for the voting table) and the best model on a held-out validation set. The latter is usually not completely sparse and hence may achieve better results.
weights initialization. Similar to NODE (Popov et al. 2019), we initialize the ferns feature se- lection matrix uniformly Uz UO, 1) for i 1,.., K and 1,..,,.. The thresholds values are initialized with zeros. The weights in the voting table V are initialized with a standard normal distribution V ~ (O; 1). The softmax temperature parameter /3 is initialized towards 30 at the end of training. The smooth step function threshold (t in Eq. is controlled by an additional parameter termed p this parameter controls the percentage of examples with non-zero gradient (see section 3.2 for more details). We set = 0.99 at the beginning of training, and slowly decay it towards 0.
1 and annealed
5.1 COMPARISON TO THE STATE-OF-TIE-ARTT
Dataset. We' ve experimented with six tabular datasets: Adults Income (AD), ALOI (AL), Jannis (JA), Higgs-smal small (HI), California housing (CA), and Year (YE). These datasets were all taken from Gorishniy al. 1 open-source library and were already pre-processed. For multi-class datasets (AL, JA) we report the accuracy on the test set, and for binary classification problems (AD ,H), we report the Area Under the Curve (AUC) of the ROC curve. For regression problems (CA, YE) we report the Moot-Mean-Square-EEE Error. A detailed description of the datasets can be found in the appendices.
Methods. We compare our model to the following baselines:
CatBoost. a GBDT implementation which uses ferns as the computational component.
XGBoost. Similar to CatBoost, with RDTs as the computational component.
https::/ancnymoous. 4open sci wwwiennce//eee..c... 60

---

Under review as a conference paper at ICLR 2022
Table 1: Comparison to the state-of-the-art in terms of accuracy. All comparative results are taken
from the recent research on tabular data (Gorishniy et al. (021). Dataset details can be found at the appendix A Results are reported for S-HTE which has one active word per fern, and 'best S-HTE', which has several active words (1-10, stated in the parenthesis).
AD f
AL f
JA f
HI 1
CA 4
YE L
CatBoosta
0.797
0.946
0.721
0.724
0.430
8,913
XGBoosta
0.775
0.925
0.721
0.705
0.463
9,446
MI.P
0.796
0.954
0.719
0.721
0.494
8.861
TabNet
0.796
0.954
0.724
0.717
0.513
9.032
PT-Transformera
0.799
0.953
0.725
0.723
0.464
8,820
NODE (flat)
N/A
0.918
N/A
N/A
0.464
N/A
NODE (optimized)
0.791
N/A
0.726
0.724
N/A
8,774
S-HTE
0.801
0.948
0.672
0.695
0.518
9.253
best S-HTE
0.817 (4)
0.953 (4)
0.707 (10)
0.708 (6)
0.474 (1)
9.210 (2)
MLP. Simple feed forward network, with several standard Sinear-ReLu-Droppe layers, with dropout regularization.
TabNet. Sequential attention based model, enabling feature selection for each decision step.
FT-Transformer. Transformer based model designed to handle tabular datasets.
NODE. Dense differeniable ensemble of ferns (this method is the closest to the ours).
NODE has two variants a flat model (i.e. single layer of ferns) and a optimized model in which several layers are used. Both variants were used as described in [Popov et al. (0199)
We used the same parameters for each of the datasets (L = 3. M 100, K 7, 40), with the exception of AL dataset which has 1000 output classes (we used L = 4, K = 8, and M, remained
the same).
The results are summarized Table The comparative methods' results were taken from Sromooorshniy et al. (2021), which published comprehensive analysis over several contemporary deep learning models for tabular data. These results advocate the S-HTE model as a competitive method in terms of accuracy, specifically for the AD, AL, and CA datasets. We report the results of the fully-sparse model, which contains completely sharp ferns, and the best trained model on a held-out validation set, which is not necessarily fully sparse. For the latter, the average number of active words fern is reported next to the results on each dataset in parenthesis. In comparison to NODE, NODE works better for JA, HI, CA, and YE datasets, with a small margin compared to the best S-HTE, while H-E is superior on AD and AL.
Table 2: Comparison to the -tate-of-the-art in terms of computational complexity. The equations from section 4 are used to compute the algorithms operation count. The numbers represents thou- sands of operations.
AD
AI
JA
HI
CA
YE
CatBoosta
40
2036
44
40
38
38
XGBoost,
40
2036
44
40
38
38
MLP
602.38
26.21
31.21
34.42
233.68
1155.43
FT-Transformer:
16025.86
82575.36
60466.18
12536.83
5431.3
46033.92
NODE
24147.97
66340.86
2134.017
2202.94
935.94
2002.94
S-HTE
18.3
17.9
18.3
18.3
18.3
18.3
best S-HTE
124.93
4163.58
561.15
159.74
75.77
159.74
As discussed in section we compared the S-HTE the state-of-the-art methods for tabular data by the number of expected operations. Table [ shows the number of operations (in thousands) used by the analyzed methods the examined datasets (Based on hyper parameters taken from the official repository of (Gorishniy et al. 2021 As can be seen, S-HTE has the lowest number of
htttps:// whwb. http::///tttttbb.ooo//nneeerre http://htttttteeeeee///ea//o//ot
8

---

Under review as a conference paper at ICLR 2022
Table Accuracy as a function of S-HTE model depth on the Adult income dataset. As in the other experiments, a 3-layers model works best on this dataset. As can be seen, deep models provide aceuracy gains over shallow ones (for example, the layers model is better than the layers one).
Model Variant
Final Model Results
A
L-Layer
0.754
2-Laysss
0.757
+0.4%
3-1 Bayee
0.772
+2.4%
4-Layers
0.769
+1.9%
Table 4: Ablation study over the annealing components. We test the effect of feature sparsity in bit function (using the 3 parameter) and word sparsity in a fern (using the p parameter). Results are stated on the Jannis dataset, for which the gap between dense and sparse results are significant.
Model Variant
Final Model Results
A
Without annealing
0.667
Annealing of 3 only
0.693
+2.6%
Annealing of p only
0.648
-1.9%
Annealing both p and /3
0.672
+0.5%
operations, often by orders magnitude. Note that these results are obtained without an extensive hyper-parameter tuning study, from which S-HTE can probably gain more.
5.2 ABLATIONS STUDY
From Flat to Deep Models. To examine the benefits of deep representation learning, we compare the results of flat model against L {2, 3, 4]. In this experiment we fixed the of the model's parameters M 50, K = 7, D = 40. The accuracy of the final trained models (i.e. containing only sharp ferns) are presented in Table [3] As the results indicate, using deeper models improved the results by up to 2.4%. Similar experiments with the other datasets show that for all datasets except AL. I. 3 yielded the best results.
Annealing Mechanism Ablation Study. As discussed in section 3.2 there are two annealing mech- anisms the S-HTE architecture- annealing the P parameter for sparse usage of active words, and annealing the 3 parameter for obtaining feature-specific bit functions. We examine the effect of these mechanisms by disabling them. these experiments we used the Jannis dataset, on which large accuracy gap between complete sparse model (our S-HTE), and complete dense model (the optimized version of NODE) was observed. We use a 3-layered model, with 100 ferns in each layer, and 7 bit functions in each fern. Surprisingly, the best result obtained using a partially annealed version of the S-HTE model annealing the / parameter only, keeping p = 0.99. This means using multiple active words is beneficial, but each bit is these words should depend on single feature. Upon reflection, this result has a natural explanation tabular data features are typically heteroge- neous and different nature (i.e. they describe different physical quantities, not similar entities as pixels in different locations). Hence considering each feature in isolation is a reasonable strategy, and enforcing such feature isolation providing useful prior.
CONCLUSION
In this work, we introduced the S-HTE architecture sparse deep learning model for tabular data trained end-to-end with back- propaaropaaatoon.. S-HTE uses ferms as the basic computing component, with single active word for each fern, making is extremely efficient and particularly applicable for low-end CPU-based devices. Using a significantly lower operation count, accuracy results obtained by S-HTE are often comparable to state of the art architectures, as measured on a recent benchmark.
Ablative studies show S-HTE networks earn from depth, and that computing sparse bit functions relying on single features is beneficial to both accuracy and efficiency. In the future we plan to experiment with data-specific hyper-paramesn tuning, and incorporation of recent advances in reg- ularization techniques, which were found to have a significant effect on MLP performance (Kadra)
al. 2021

---

Under review as a conference paper at ICLR 2022
7 ETHICS STATEMENT
As far as we are aware, there are no ethic concerns in this work.
8 REPRODUCIBILITY
Our code is publicly available at |attps://anotymouut 4open. wwwence///eteteee. 6TEB60EB/ All of the datasets used in this paper were taken from a previous published work The datasets were preprocessed in ad- vanced (by the above repository owners), and we kept the same saii-validation-tee splits.
REFERENCES
Sercan O Arrk and Tomas Pfister. Tabnet: Attentive interpretable tabular learning. arXiv, 2020.
Tianqi Chen and Carlos Guestrin. Xgboost: A scalable tree boosting system. In Proceedings of the 22nd acm sigkdd international conference on knowledge discovery and data mining, pp. 785-794, 2016.
James Fiedler. Simple modifications to improve tabular neural networks. arXiv preprint M.Xiv:200..03244 2021.
Jerome H Friedman. Greedy function approximation: gradient boosting machine. Annals of statistics, pp. 1189-1232, 2001.
Ian Goodfellow, Yoshua Bengio, and Aaron Courville. Deep learning. MIT press, 2016.
Yury Gorishniy, Ivan Rubachev, Valentin Khrulkov, and Artem Babenko. Revisiting deep learning models for tabular data. arXiv preprint arXiv:2 19599 2021.
Hussein Hazimeh, Natalia Ponomareva, Petros Mol, Zhenyu Tan, and Rahul Mazumder. The tree ensemble layer: Differentiability meets conditional computation. In International Conference on Machine Learning, pp. 4138-4148. PMLR, 2020.
Arlind Kadra, Marius Lindauer, Frank Hutter, and Josif Grabocka. Regularization all you need: Simple neural nets excel tabular data. arXiv preprint arXiv:2106. / /899, 2021.
Liran Katzir, Gal Flidan, and Ran Ylnvv..v. Net-dnf: Effective deep modeling of tabular data. In International Conference Learning Representations, 2020.
Guolin Ke. Qi Meng. Thomas Finley, Taifeng Wang. Wei Chen, Weidong Ma, Qiwei Ye, and Tic- Yan Liu. Lightgbm: A highly efficient gradient boosting decision tree. Advances in neural information processing systems, 30:3146-3154, 2017.
Diederik Kingma and Jimmy Ba. Adam: A method for stochastic optimization. arXiv preprint arXiv: 141.6690, 2014.
Ron Kohavi. Bottom-up induction of oblivious read-once decision graphs: strengths and limitations. In AAAI, pp. 613-618. Citeseer, 1994.
Peter Kontschieder, Madalina Fiterau. Antonio Criminisi, and Samuel Rota Bulo. Deep neural decision forests. In Proceedings of the IEEE international conference on computer vision, pp- 1467-1475, 2015.
Eyal Krupka, Alon Vinnikov, Ben Klein, Aharon Bar Hillel, Daniel Freedman, and Simon Stachniak. Discriminative ferns ensemble for hand pose recognition. In Proceedings of the IEEE Conference on Computer Vision and Pattern Recognition, pp. 3670-3677, 2014.
Yin Lou and Mikhail Obukhov. Bdt: Gradient boosted decision tables for high accuracy and scoring efficiency. Proceedings of the 23rd ACM SIGKDD international conference on knowledge discovery and data mining, pp. 1893-1901, 2017.
10

---

Under review as a conference paper at ICLR 2022
Andre Martins and Ramon Astudillo. From softmax to sparsemax: A sparse model of attention and multi-label classification. In International conference on machine learning, pp. 1614-1623. PMLR. 2016.
Kevin Miller, Chris Hettinger, Jeffrey Humpherys, Tyler Jarvis, and David Kartchner. Forward thinking: Building deep random forests, arXiv preprini arXiv:1705.07366 2017.
Ben Peters, Vlad Niculae, and André FT Martins. Sparse sequence-to-sequenc models. arXiv preprint arXiv:1905.05770 000000 2019.
Sergei Popov, Stanislav Morozov, and Artem Babenko. Neural oblivious decision ensembles for deep learning tabular data. arXiv preprint
2019.
Liudmila Prokhorenkova, Gleb Gusev, Aleksandr Vorobev, Anna Veronika Dorogush, and Andrey Gulin. Catboost: unbiased boosting with categorical features. arXiv preprint Skdi::1706099166 2017.
Ira Shavitt and Eran Segal. Regularization learning networks: deep learning tabular datasets. arXiv preprint arXiv: 1805.06400, 2018.
Weiping Song, Chence Shi, Zhiping Xiao, Zhijian Duan, Yewen Xu, Ming Zhang, and Jian Tang- Autoint: Automatic feature interaction learning via self-attentive neural networks. In Proceed- ings of the 28th ACM International Conference Information and Knowledge Management, pp- 1161-1170, 2019.
Yongxin Yang, Irene Garcia Morillo, and Timothy M Hospedales. Deep neural decision trees. arXiv preprint arXiv: 860880888, 2018.
Hongyi Zhang, Moustapha Cisse, Yann N Dauphin, and David Lopez-Paz. mixup: Beyond empirical risk minimization. arXiv preprint
2017.
Zhi-Hua Zhou and Ji Feng. Deep forest. arXiv preprint arXiv: 1702.08855. 2017.
A
DATA
Datasets
Table 5: Datasets description
Name
#Train
# Val.
#lest
#Features
Task
#Classes
Batch size
Adults Income
26048
6513
16281
14
Classification
256
Jannis
53588
13398
16747
54
Classification
4
512
Higgs-small
62752
15688
19610
28
Classification
2
512
ALOI
69120
17280
21600
128
Classification
1000
512
California Housing
13209
3303
4128
8
Regression
256
Year
370972
92743
51630
90
Regression
1024


Reviews:
[{"review_id": "h510j9dxecc", "reviewer": "Reviewer_vA5d", "summary": "", "questions": "", "limitations": "", "rating": 1, "confidence": 5, "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": "Overall the paper writing is clear. The related work is also good and comprehensive although there is one similar work they miss (see below). \n\nI have several major concerns. Notably:\n1. The proposed idea of making soft to hard operations has been proposed in [1], although [1] focuses on making NODE as a Generalized Additive Models (GAMs) and not specifically about the lower computational cost. \n2. Although this paper focuses on lowering the computational cost and is suitable for the lower-end CPU, there is no empirical measurement and computing time to support it. Also, in nowadays CPU and GPU with strong parallel processing architecture, the proposed sparsity might not enjoy any speed up in the real world since either dense or sparse vector will require a dot product in PyTorch. \n3. The claimed contribution is also unclear when no experiment of speed up is compared to traditional tree-based packages. They claim that S-HTE enjoys the deep-learning representation and thus only require hundreds of trees while traditional trees require thousands of trees, but this claim needs to be backed up in the experiment. In fact, sklearn GBT default tree number is 100, which is contradictory to what authors claim. \n4. The datasets selected are from Gorishniy et al. 2021. Why don't you experiment on NODE's datasets since NODE is the closest one to your method? This makes readers suspicious of the accuracy of the method.\n5. The ablation study is only conducted on 1 single dataset which is very unconvincing.\n6. Authors should also compare with other sparsification technique for neural network like [2].\n\n[1] NODE-GAM: Neural Generalized Additive Model for Interpretable Deep Learning, https://arxiv.org/abs/2106.01613\n[2] Variational Dropout Sparsifies Deep Neural Networks: https://arxiv.org/abs/1701.05369", "summary_of_the_paper": "This paper modifies from a differential-tree architecture (NODE) for tabular data that has lower theoretical computational complexity to be suited for lower-end CPU devices. Specifically, they gradually anneal the soft operations in NODE to hard operations that sparsify the operations and thus has lower theoretical computation. They find this sparsification, with other modifications like summing across the outputs for each layer before passing to the next layer, can enjoy much smaller operation counts. They show that their performance is somewhat comparable to other commonly used methods like CatBoost, TabNet and NODE. And they do an ablation study to confirm sometimes deeper layers improve the performance and sparsification also leads to higher accuracy.", "summary_of_the_review": "Overall this paper proposes a similar idea to previous work [1] that also sparsifies the NODE without mentioning it. There is no empirical measurement of the claimed speed up, and the selected datasets are not compared to the datasets used in NODE, and no baseline including sparsified neural network like [2]. The accuracy results are somewhat lower than CatBoost in 4 out of 6 datasets. \nTo summarize, there is very little novelty in the architecture, no empirical time measurement to back up its claim, and the datasets selected are not comprehensive, and some missing important baselines. So I recommend rejection for this paper.", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "3: Some of the paper’s claims have minor issues. A few statements are not well-supported, or require small changes to be made correct.", "technical_novelty_and_significance": "1: The contributions are neither significant nor novel.", "empirical_novelty_and_significance": "1: The contributions are neither significant nor novel."}, "extra_text": {}}, {"review_id": "42P7gVfwaFh", "reviewer": "Reviewer_2rMh", "summary": "", "questions": "", "limitations": "", "rating": 5, "confidence": 2, "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": "First of all, I am not an expert of this specific problem (tabular data prediction and differentiable decision tree learning), although I published papers on decision trees before. \n\nStrength: \n- The paper is clearly written. Although I am not working in this field, I am able to follow the paper easily. \n- From the introduction and related work of the paper, technically, this paper seems to have addressed some challenges that previous works have not addressed before (for detailed explanations, see \"Differentiable decision trees based architectures.\" in the related work section).\n\nWeakness:\n- The performance is not so impressive (esp. in comparison to CatBoost which is also quite fast). \n- The results are not reported with an error bar. Without the error bar, some of the designs, such as the ablation of having deep architecture, are not quite convincing given the limited improvement by increasing L from flat to 4. Especially, the performance drops a bit when increasing L from 3 to 4. I wonder whether deep is really necessary for such methods. ", "summary_of_the_paper": "This paper studies the prediction problem on tabular datasets and proposed a differentiable multi-layer fern-based architecture. The training and inference algorithms are provided, and the computational complexity has been analyzed. The selling point is that the approach is computationally efficient on CPUs and can learn sparse representation. The prediction performance is on-par with state-of-the-art methods. ", "summary_of_the_review": "In short, the paper has some merits in comparison to the literature of differentiable decision trees. However, its performance is not so strong and some experiment results are not solidly justified. Nonetheless, I feel the cited papers by this submission are also somewhat incremental to their literature. ", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "3: Some of the paper’s claims have minor issues. A few statements are not well-supported, or require small changes to be made correct.", "technical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work.", "empirical_novelty_and_significance": "2: The contributions are only marginally significant or novel."}, "extra_text": {}}, {"review_id": "2tf4OR2baho", "reviewer": "Reviewer_M9FK", "summary": "", "questions": "", "limitations": "", "rating": 5, "confidence": 3, "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": "STRENGTHS\n\n- The paper is clear about the relation between the proposed method and the previous works. This is very helpful for understanding the paper.\n- The complexity analysis is helpful for understanding the computation efficiency of the proposed method.\n\n\nWEAKNESSES\n\n- The computation cost comparison is in numbers of operations, instead of the wall time on fixed hardware. This may be unfavorable for the dense methods, since the dense operations are usually easier to be accelerated on modern hardware, especially GPU.\n- The comparison on the datasets does not show clearly the proposed method is better. If efficiency is the main advocacy, it may be better to put the accuracies in the context of the computation wall time.\n- The usage of a validation set for parameter tuning may not be unfair for the other methods. Essentially, the validation set is used as a training set for the proposed method. From the paper, it is not clear whether the other methods use the validation set for training as well.\n- The ablation on layer number of the proposed model in Table 3 shows that more layers only add the performance marginally. This is different from the observation in deep convolutional networks that deeper models usually perform much better. The present ablation study is undermining the motivation that we want to go deeper with the proposed method.", "summary_of_the_paper": "The paper constructs Sparse Hierarchical Table Ensemble (S-HTE) based on oblivious decision trees for tabular data processing. The motivation is to benefit from the expressiveness of multi-level processing based on a differentiable framework. The paper dives into how ferns work and the complexity of the new design. The experiments are conducted on the commonly used tabular datasets.", "summary_of_the_review": "Despite the theoretical efficiency advantage of the proposed method, there are still remaining questions as mentioned above. I am leaning towards rejecting given those questions.", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "3: Some of the paper’s claims have minor issues. A few statements are not well-supported, or require small changes to be made correct.", "technical_novelty_and_significance": "2: The contributions are only marginally significant or novel.", "empirical_novelty_and_significance": "2: The contributions are only marginally significant or novel."}, "extra_text": {}}, {"review_id": "-WHMcfyKslX", "reviewer": "Reviewer_dw2A", "summary": "", "questions": "", "limitations": "", "rating": 5, "confidence": 4, "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": "Novelty: the proposed approach can be considered as an extension of the NODE (Popov et al. 2019) with annealing mechanism. From my point of view, this requires a minor modification to the original algorithm: softening of Heaviside function was done differently with annealing hyperparameter taken into account. Furthermore, the annealing mechanism is relatively old trick that is commonly used in literature to get sparsity. Other technical details such as using deep architectures, concatenating inputs/outputs, etc. were already done in the mentioned paper. Therefore, I think that the methodological contribution is not significant.\n\nExperiments: evaluations suggest that the proposed method perform slightly worse than NODE but more efficient and I agree with that. However, by looking at Table 1, I can see that the performance of CatBoost/XGBoost are quite similar. In some cases they even notably outperform S-HTE (e.g. Higgs-small, California Housing) while still being very efficient (asymptotically). Moreover, they are highly optimized for different hardware settings (CPU/GPU) and can benefit from parallel processing. Given all of these, I would suggest to simply use CatBoost or XGBoost rather than the proposed approach. Probably, the proposed method can improve significantly for non-tabular data (e.g. images and texts) where correlation of features matter where representation learning matters (and traditional boosting machines do not perform well).\n\nOther comments/questions:\n- annealing is applied to the Heaviside function but not for the bit functions. Does it mean that each bit function uses a linear combination of all features or they are also sparsified in some way? In any case, the resulting oblivious trees are effectively oblique ferns. They are more powerful class of models rather than traditional axis-aligned trees but they are typically less interpretable.\n- \"the computational component in XGBoost are Random Decision Trees (RDTs)\". What do you mean by random trees? As far as I know, XGBoost use traditional CART style decision trees which are not random.", "summary_of_the_paper": "Authors propose a variant of differentiable multilayer tree ensembles with annealing mechanism. They use a specific types of trees, called ferns, which are constrained to have the same boolean function for all nodes at the same level. Such a tree representation can be useful to effectively reduce a decision tree into a table lookup. The proposed model can be considered as multilayer ferns where the output of the given fern is used as input to the next one and the entire model is trained end-to-end. Additionally, the input from the previous layer is stacked with output as in ResNets. Training is done by softening non-differentiable parts of ferns to allow gradient based optimization. Finally, annealing mechanism is used to obtain sparse connections.", "summary_of_the_review": "Based on major concerns regarding technical novelty and experiments, I am leaning towards rejection of this paper.", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "3: Some of the paper’s claims have minor issues. A few statements are not well-supported, or require small changes to be made correct.", "technical_novelty_and_significance": "2: The contributions are only marginally significant or novel.", "empirical_novelty_and_significance": "2: The contributions are only marginally significant or novel."}, "extra_text": {}}]

Author rebuttal:

Meta-review: The submission introduces the sparse hierarchical table ensemble (S-HTE), based on oblivious decision trees for tabular data. The reviewers acknowledged the clarity of the presentation and the importance of the computational complexity analysis. However, they also raised concerns regarding the novelty of the proposed method and the significance of the results compared to competing methods (e.g., CatBoost). Given the consensus that the submission is not ready for publication at ICLR, I recommend rejection at this point.
Decision: Reject