Learning a Decision Tree Algorithm with Transformers
Authors: Yufan Zhuang
Liyuan Liu
Chandan Singh
Jingbo Shang
Jianfeng Gao
Venue: Accepted by TMLR ()

Abstract: Decision trees are renowned for their ability to achieve high predictive performance while remaining interpretable, especially on tabular data. Traditionally, they are constructed through recursive algorithms, where they partition the data at every node in a tree. However, identifying a good partition is challenging, as decision trees optimized for local segments may not yield global generalization. To address this, we introduce MetaTree, a transformer-based model trained via meta-learning to directly produce strong decision trees. Specifically, we fit both greedy decision trees and globally optimized decision trees on a large number of datasets, and train MetaTree to produce only the trees that achieve strong generalization performance. This training enables MetaTree to emulate these algorithms and intelligently adapt its strategy according to the context, thereby achieving superior generalization performance.

Published in Transactions on Machine Learning Research (08/2024)
Learning a Decision Tree Algorithm with Transformers
Yufan Zhuang
yhzhoanng@uussdccoomm edu
UC San Diego Microsoft Research
Liyuan Liu Microsoft Research
lucliu@microsoft.comm com
Chandan Singh Microsoft Research
chansinggl@mmicrroofttooom
Jingbo Shang UC' San Diego
jshang edu
Jianfeng Gao
itgao@mierosoft.com
Microsoft Research
Reviewed on OpenReview: https: // openreview. net/ forum? id- 1kzzm22us
Abstract
Decision trees renowned for their ability to achieve high predictive performance while remaining interpretable, especially tabular data. Traditionally, they constructed through recursive algorithms,, where they partition the data at every node in a tree. However, identifying a good partition is challenging, as decision trees optimized for local segments may not yield global generalization. To address this, we introduce MetaTree, a transformer-based model trained via meta-learning to directly produce strong decision trees. Specifically, we fit both greedy decision trees and globally optimized decision trees on a large number of datasets, and train Meta'Tree to produce only the trees that achieve strong generalization performance. This training enables Mrta to emulate these algorithms and intelligently adapt its strategy according to the context, thereby achieving superior generalization performance.
1 Introduction
Transformers (Vaswani et al. 2017) have demonstrated the capacity to generate accurate predictions on tasks previously deemed impossible (OpenAl 2023 Betker et al.) 2023). Despite this success, it remains unclear if they can directly produce models rather than predictions. In this work, we investigate whether transformers can generate binary decision trees and explore the mechanisms by which they do so. We select decision trees as they are foundational building blocks of modern machine learning and hierarchical reasoning. They achieve state-of-the-art performance across a wide range of practical applications (Grinsztajn al., 2022
and additionally offer interpretability, often critical consideration in high-stakes situations (Rudin Murdoch et al. 2019).
2018
Decision trees are traditionally constructed using algorithms based on greedy heuristics (Brimman et al. 1984 Quinlan 1986). To overcome the bias imposed by greedy algorithms, recent work has proposed global. discrete optimization methods for fitting decision trees (Lin al. 2020 Hu et al., 2019 Bertsimas Dunn 2017). While these approaches have been effective in tabular contexts, a significant challenge lics in their non-diiferentiabillt, which raises difficulties when integrating them into deep learning models. Moreover, full
Code available httpp://gt: httpps//gStthb. ccm///raazZhaanggHeetrreee

---

Published in Transactions on Machine Learning Research (08/2024)
Table 1: Comparing each algorithm's single-tree performance over the 91 held-out datasets (91D) and the 13 Treo-of-prompts datasets (ToP), among tree depth 2, 3, and MetaTree generalizes well, despite only being trained on depth-2 trees. Listed are the average rank with standard deviation over the datascts. We also report the number of times algorithm in the first place (champion). TGODDT encounters out-of-memory (OOM) errors for tree depths greater than 2 due to the NP-hard complexity of solving for the optimal tree. We report the memory usage for GOSDT in Table
Config
MetaTree
GOSDT
CART
ID3
C4.5
avg. rank champion
1.34 + 0.84
2.68 + 1.20
3.30 + 0.90
3.30 + 0.92
4.36 + 1.15
91D, depth-2
72
13
2
2
avg. rank champion
1.08 + 0.27
2.77 = 1.48
3.00 + 1.18
2.77 + 1.25
3.38 + 1.60
ToP, 2epth-2
7
3
1
2
avg. rank champion
1.25 + 0.64
OOM
2.65 + 0.78
2.57 = 0.80
3.53 + 0.84
91D, depth-3
76
5
2
avg. rank champion
1.31 + 0.82
OOM
2.54 + 1.15
2.46
= 1.08
2.69 + 0.99
ToP, depth-3
9
2
avg. rank champion
1.25 + 0.67
OOM*
2.79 + 0.79
2.51 + 0.76
3.44 + 0.92
91D, depth-4
76
avg. rank champion
1.15 + 0.36
OOM*
2.46 + 0.93
2.46
1.01
2.69 + 1.14
ToP, depth-4
9
decision tree optimization is NP-hard (Laurent & Rivest 1976). rendering it practically infeasible to compute optimal trees with large tree depths.
In this work, we introduce MetaTree, a transformer-basol model designed to construct a decision tree on tabular dataset. MetaTTree recursively performs inference decide the splitting feature and value for each decision node (Fig. [p). We train MetaTTee to produce high-performing decision trees. Specifically, we fit both greedy decision trees and optimized decision trees on a large number of datasets. We then train Meta Tree to generate the trees that demonstrated superior generalization performance (Fig, [e]. This training strategy endows MetaTree with a unique advantage: it learns not just to emulate the underlying decision tree algorithm, but also to implicitly select which algorithmic approach is more effective for a particular dataset. This adaptability adds significant flexibility traditional methods that are bound to a single algorithmic framework. MetaTree's architecture leverages an alternating row and column attention mechanism along with learnable absolute positional bias for the tabular representations (Fig D
MetaTree produces highly accurate trees on large set of real-world datasets that it did not see during training, consistently outperforming traditional decision tree algorithms (Table J and more in Sec. 5 Further analysis shows that. Meta Tree's performance improvement comes from its ability to dynamically switch between a greedy or global approach depending on the context of the split (Sec. 6.1). Finally, a bias-variance analysis shows that Mcta successfully achieves lower empirical variance than traditional decision-tree algorithms (Sec. 6.2
2 Related work
Decision trees There is a long history of greedy methods for fitting decision trees, c.g., CART Breiman
el al. 1984), ID3 QQuinlan 1986 or C4.5 QQuinlan 2014). Recent work has explored fitting trees overcoming
the limitations of greedy methods by using global optimization methods (Lin et al., 2020 Hu et al. 2019 2023). These methods can improve performance given a fixed tree
Bertsimas & Dunn] 2017 Jo al.
size, but often incur prohibitively high computational cost. Other recent studies have improved trees
through regularization (Agarwal et al. 2022 Chipman & McCulloch, 2000 Yildız & Alpaydın 2013). iterative
2

---

Published in Transactions on Machine Learning Research (08/2024)
(a) Decision Generation
(b) MetaTree Architecture
(c) Two-Phase Learning Curriculum
GOSDT
Node
Input
Input
m
Node
X E Rm .Y.YYE E
MeteTree COHO
MetaTree
Learn to Generate
COSDT
COSOT
COSOT
GOSDT
Inpul Represeriation
Phase 1: Learning to Generate GOSDT Trees
Emb R
Node
Node
CART
Node
Tebular Altention
Node
Input
Validation
Meta Tree
MetaTree Tree
HiddenStates é R
GOSDT
Node
Sigmold Activation
Node
SnpHot E Ru
MelaTree
Learn to Generate
CART
GOSDT
GOSDT
CART
Loaf
Loaf
Loaf Node
Leaf
Node
Node
Node
Phase 2: Learming to Generate Strong Generalizable Trees
Figure 1: MetaTrec Methodology. The creation of a decision tree, depicted in (a), entails recursive MetaTTre calls. MelaTree only assesses the current stale for its decision-making. (b) shows Mree's architecture, which the tabular input (n data points of m features) is embedded representation space, processed with row and column attention at each layer, and the output is one-hot mask indicating the splitting feature j and threshold X,.- (c) illustrates MetaTree's two-phase learning curriculum: in the first phase, the focus is exclusively on learning from the optimized GOSDT trees, to closely emulate the behavior of GOSDT algorithm. Then in the second phase, the training process incorporates data from both the GOSDT and CART trees, gencrating the ones that have better generalization capabilities.
updates Caareira-Perpinaae & Tavallali 2018 Hada et al. 2023 or increased flexibility Grossmann 2004
Valdes et al.
2016 Tan et al. 2022 Sorokina et al. 2007
Hiabu et al. 2020
Tree- based models maintain state-of-the-an prediction performance across most tabular applications (Grinsz
tajn et al. 2022 Kornblith et al., 2022), especially when used ensembles such as Random Forest (Breiman
2001 boosted trees (Freund et al.) 1996. Chen & Guestrin 2016). and BART (Chipman al,,
2010 Some works have sought combine these tree-based models with deep-learning based models to
improve predictive performance when fitting single dataset (Frosst & Hinton 2017 Zantedeschi al. 2021
Tanno et al. 2019 Lee & Jaakkola,
2019 Biau et al. 2019
Recent research has increasingly focused on exploring the synergy between tree-based models and large language models (LLMs). One area of investigation involves leveraging trees to guide and improve the generation processos of LLMss Using tree structure in scarching for prompts provides a hicrarchical framework that structures the prompt space more effectively. can enhance the coherence and logical flow of generated text (Yao et al.] 2023), and improve task performance without needing to finetune the LLM (Morris al. 2023 LLMs can also be used to build stronger decision trees. Aug-imodels (Singh et al. 2023 has demonstrated that integrating LLMs during the training phase of decision trees can significantly enhance their performance and interpretability.
Learning models/algorithms Some learning- based methods have focused improving algorithuss, largely based combining transformers with deep reinforcement learning, e.g. faster matrix multiplication (Fawzi et al. 2022) or faster sorting algorithms (Mankowitz et al.) 2023). One new work studies using LLMs to iteratively generate and refine code to discover improved solutions to problems in computer science and mathematics Kkomera-Paredee et al. 2023
Other works focus on transformers' ability to learn in context. Zhou et al. (2023) probe simple tasks for length generalization and find that transformers can generalize to certain class problems easily. One very related work studies whether Transformers can successfully learn to generate predictions from linear
3

---

Published in Transactions on Machine Learning Research (08/2024)
functions, and even decision trees and small MLPs in context [Garg et al. 2022). Despite these successes, recent, works also find limitations in transformers' ability to generalize in certain contexts, e.g. to distribution shifts Yadlowsky et al. 2023 or to arithmetic changes (Dziri et al. 2023).
Meta-learning Often referred to as "learning-to-leam" meta-learning has gained incrcasing attention in
cent years (Finn et al. 2017 Nichol et al.
2018: Hospedales el al. 2021p. p. Meta-learning algorithms are designed
to learn model that works well on unseen dataset/task given many instances of datasets/tast (Vilalta & Drissi 2002). Particularly related to MetaTTre are works that apply meta-learning with transformers to
tabular data (Hollmann et al.) 2022 Feuer et al.
2023
Onishi et al., 2023 Hegselmann et al., 2023 Gorishniy
jt al. 2023 Manikandan et al. 2023: Zhu et al.
2023 Our work follows the direction of meta-learning with
a focus on directly outputting a model informed by the insights of established algorithms.
3 Methods: MetaTree
Problem definition When generating a decision tree, we are given a dataset D (xi, yt) where at E R represents the input features and yi (L...., K} corresponds to the label for each instance. At each node, decision tree identifies split consisting of feature j E (1....,m) m) and threshold value u E R, such that D can be partitioned into two subsets by thresholding the value of the jth feature. The dataset is partitioned recursively until meeting a pre-specified stopping criterion, here a maximum tree depth. To generate a prediction from the tree, a point is passed through the tree until reaching a leaf node, where the predicted label is the majority label of training points falling into that leaf node. We illustrate MetaTree's generation pipeline, architecture design and its two-phase learning curriculum in Fig. 1
3.1 Generating a decision tree model: representation and model design
Decision trees are typically fit using a top-down greody algorithm such CART (Breiman et al. 1984p These algorithms greedily select the split at each node based on criterion such as the Gini impurity. This class of methods, while efficient, often results in sub-optimal solutions. More recent work has studied the generation of "optimal" decision trees seeking a solution that maximizes predictive performance subject to minimizing the total number of splits in a trec. This can be formulated as a tree search, in which recursive revisions on the tree happen when all children of search node are proven to be non-optimal (Lin al., 2020). However, finding optimal trees is intractable for even modest tree depths, and can also quickly overfit to noisy data.
Model design: divide and conquer with learned speculative planning Our approach, MetaTree, aims to bridge the gap between existing methods by generating highly predictive decision trees, as illustrated in Fig. [a). To construct single tree, MetaTTree is recursively called at each node. The process begins by presenting the entire dataset to the model, in which Meta'Tree creates the first split (i.e. a threshold value on feature dimension). The dataset is then filtered into two subsets by the root node's split, and each subset (i.c., left child and right child) is individually passed through the model, while masking out the opposite subset. This recursive process continues until a predetermined maximum depth for the tree is reached. Although MetaTree only outputs one split at a time, its ability to consider the entire dataset when making the initial split and utilize multiple Transformer layers enables it to make adaptive, non- non-greedy splits. We show experimental results supporting this claim in Sec. 6.1 and we include related case studics in Appendix A.2
Representing numerical inputs: learnable projection and positional bias MetaTTee takes matrices of real-valued numbers as input. We use multiplicative embodding to project all the numerical features into embedding space and add the class embedding onto it. The aggregated embedding is then transformed via a two-layer MLP. Specifically, given n-row m-column input X E Ram and its k-class label Y E (1,...,k)"'
4

---

The main task of our model is to select a feature and value to split the input data. This process involves selecting a specific element from the input matrix X E R.... Suppose the choice is made for X is equivalent to docision that splits the data along the 5th feature with value X Our design for the model's Published in Transactions on Machine Learning Research (08/2024)
with You denotes Y in one-hot format, the embedding is computed as follows:
(Feature Embedding)
Embx (X) X @ Wa E ER Wa e Rd
(1)
(Label Embedding)
Emby (Y) You Wy Rdd Wy E R
(2)
(Position Embedding)
B(...R) bi(jA) b2(1,))
(Final Representation)
Emb = MLP(Embx(X) Emby (Y) + B) Emb E R..... B pnm.d bj R"... b2 R.d
For each number in the matrix X, is transformed into I2 space via multiplication with W2: then added to the class embedding of Y. The final embedding obtained by putting the aggregatod embodding plus the positional bias terms b1, b2 through an MLP.
We normalize each feature dimension per batch to have mean of 0 and variance of 1. Prior to inference, we also add truncated Gaussian noise to categorical fealures; this improves performance on discrete features since the model is mostly trained on continuous data.
Tabular self-attention: row and column- wise information processing Since our tabular input shares information across rows and columns, we apply attention to both the row dimension and column dimension in each Transformer layer. For 1th layer, given input in hidden space x²=1 E Ru,m,d the output of the tabular attention y E gn.m.d computed as:
ColAttn(X (1)) = Softmax (o00
K(0)
col
vil)
(5)
RowAttt (x = Softmax (Q!!T K-()) (1) row zow
V-(1)
(6)
y-(1) (x + RowAttn(XX, x((
(7)
where ( Emb(X, Y) for the first layer, x MI.((y for the rest the layers; for the column/row
query Q, key K, value V projections, xx( E Ra.m, is first reshaped to (I) E Ru.m, and hooww E m.,dd where the Softmax is conducted on the corresponding column/rov /row dimension, i.e. second last dimension. The Q K, are constructed in the following manner, we will explain this for column attention only where the row attention follows the same design: Q!i) = w-ll x where the linear projections w-ll) Q.col: !!! v(( E d.d are all learnable parameters. The dimension orders will be shuffled back after column/row attention such that ColAttn(X,), (")"), RowAttn(X Rm.m.d
Q.col x h.col: K( = w( x(() Xx h.col v(O = w x-I) Keeol
Viaa hi
Attention is being applied in the row and column dimensions individually, it will first gather information over n rows and then over m columns with an O(n2 + m²) complexity. This alleviates the computing cost. compared to reshaping the table as a long sequence, which would require an O (n²m²) complexity, while effectively gathering and propagating information for the entire table.
3.2 Training objective: cross entropy with Gaussian smoothing
output and the correspouding loss function is based on this fundamental principle of split selection. The model's output is passed through linear projection to scale down from gn.md to p...,. and the final output is obtained after Sigmoid activation.
We train our model with supervised learning. In the ground truth tree, each node contains the feature index and the splitting value. This equivalent to a one-hot mask over the input table where the optimal choice of feature and value marked as one and the rest marked as zero. However, directly taking this mask as the training signal raises issues: some data points might have similar or exactly the same values along the same feature the optimal split, and masking out these data points would deeply confuse the model. Hence
5

---

Published in Transactions on Machine Learning Research (08/2024)
use Gaussian smoothing over this mask our loss target based on the value distance over the chosen feature. We denote the ground truth splitting feature and value as j' and v², the training target M:
M
exp
(X 1
20
j= jド
(8)
0,
where is hyperparameter, controlling the smoothing radius. We use Binary Cross Entropy (BCE) to calculate the loss between our model output and the training larget M.
Learning curriculum: learning from optimized trees to best generalizing trees Our training approach is tailored to accommodate the mixed learning signals derived from the two distinct algorithms,, each with its unique objectives and behaviors. The task difficult. Mimicking the optimization- based decision tree algorithm is already challenging (i.e. approximating solutions for NP-hard problem), but Tree must also learn to generate the split that has the better generalization potential out of the two (CART v.s. GOSDT).
To effectively train our model, we use learning curriculum in our experiments (as illustrated in Fig. D In the first phase, the focus is exclusively on learning from the optimization- GOSDT trees. The goal during this stage to closely emulate the behavior of GOSDT algorithm. Then in the second phase, the training process incorporates data from both the GOSDT and CART trees (see details in Sec. [.1 train Meta Tree. This two-stage approach enables our model to assimilate the characteristies of both algorithms, facilitating better generalization capabilities. (See Appendix A.6 for ablation studies the training curriculum.)
We selected CART and GOSDT as they are representative and effective algorithms in the classes of greedy and optimized decision tree algorithms. As shown in our experiments (Fig, 2 they are consistently first and second amongst classical algorithms. Training with the best tree out an algorithm ensemble could potentially further improve performance, but for the simplicity of our analyses we leave that for future explorations.
MetaTree in inference: generating decision tree models Note that MetaTTee is equivalent to algorithm, the inference process is slightly different from typical deep learning models. When deploying Meta- Tree on an unseen dataset (Xtrain: Ytrain Nest Yust), we will first generate decision trees from the train set (Xtrain Yurain, then use the generated trees to make predictions Ypred on Xtest:
Decision'TreeMoode MeteTreeeaaaaaeea (train Yersin)
Ypred DeeisionTreeMMddell
where DocisionTTreeModo is constructed by recursively calling MelaTTre, as shown in Fig. Ia).
4 Experimental setup
4.1 Datasets
We use 632 classification datasets from OpenML. (Vanschoren al. 2013). Penn Machine Learning Bench- marks (Romano al. 2021). along with synthetic XOR datasct. We require cach datasct to have at least 1000 data points, at most 256 features, at most. 10 classes, and less than 100 categorical feat with no missing data. We randomly select 91 datasets as the left-out test set for evaluating our model's generalization capability while making sure they and their variants do not appear in the training set.
We generate our decision-tree training dataset in the following manner: for each datasel, we first divide it into train and test sets with a 70:30 split; then we sample 256 data points with 10 randomly selected feature dimensions from the training set and fit GOSDT tree (Lin et al.] (020)) and a CART tree (Breiman al., 1984) of depth 2 both; we later record the accuracy of the two trees on the test set; We repeat this process and generate 10k trees for each dataset. In total, we have 10,820,000 trees generated for training.

---

Published in Transactions on Machine Learning Research (08/2024)
We have both GOSDT and CART trees generated for all these datasets; for clarity, we refer to the GOSDT trees the GOSDT dalaset, the CART trees as the CART dalaset, and the trees that have the best evaluation accuracy on their respective test set between CART and GOSDT as the GOSDT+CART dataset.
We generate a synthetic XOR dataset with the following algorithm: we first randomly sample 256 data points in the 2-dimensional bounding box {a/ar ε []); then randomly generate the ground truth XOR splits inside the bounding box depending on the pre-specified level (for example, level XOR has 3 splits, level 2 XOR has 15 splits, and the root node split can take place randomly [-1. while the rest of the split is sampled randomly inside the dissected bounding boxes, see examples in Fig. A1l and assign the class labels according to the splits; at the final step, we add in label flipping noise and additional noisy feature dimensions consisting of uniform noise within [_],
We additionally test MetaTree on the 13 Tree-of prompt datasets from Morris et al. (2023) They are tabular datascts constructed from text classification tasks; the input X the LLM's response to set of prompts accompanying the text (yes or no); and the output Y is the class label. Successfully building trees on these datasets shows the potential for MetaTree to help in steering large language models. Moreover, since Meta is differentiable, it could be integrated into the training process of some LLMs.
4.2 Baselines
We use GOSDT Lin et al. 2020). CART (Beiima et al. 1984). ID3 QQiinaan 1986) and C4.5 Quinlan 2014) as our baselines, as representative optimal and greedy decision tree algorithms. For GOSDT, we utilize the official implementation, using gradient-boosted decision trees for the initial label warm-up with the number of estimators equal to 128, a regularization factor of 1e-3. For CART and ID3, we use the sklearn implementation (Pedregosa et al., 2011)) ; setting the splitting critcrion Gini impurity and entropy respectively. For C4.5, use the imodels implementation (Singh et al. 2021 with the default setting.
4.3 Model configurations
We use the LLaMA [Touvron et al. 2023) architecture as the base Transformer. For Meta'Tree, we set the number of layers as 12, the number of heads as 12, the embedding dimension as 768, MLP dimension as 3072. We can use a maximum of 256 data points and 10 features for producing a single tree, as Transformers' memory usage and runtime would grow quadratically with the sequence length, see our discussion on this in Sec. 7
We pretrain our model from scratch on the GOSDT datasel, and after training converges, we finetune it on the GOSDT+CART dataset. This curriculum improves performance compared to direct training on the GOSDT+CART dataset (as shown in Appendix A.6). We also show an ablation with RL training objective in Appendix A.8 Detailed hyperparameters are shown in Appendix A.5.
5 Results: On the Generalization Ability of MetaTree
In this section, we present Meta/ree's performance on real-world datasets previously unseen by the model (in Table aadd Fig. 2) We compare it with established algorithms, GOSDT, CART, ID3, C4.5, and find that it performs favorably when used a single tree and an ensemble. We focus on three questions: (1) Can MetaTree effectively generalize to real-world data it has not encountered before? (2) Is Mela capable of generating decision trees deeper than those it was trained on?, and (3) Can Mete be used in an LLM setting to accurately steer model outputs?
Generalizing to new datasets: Fig. 2 across 91 datasets that were excluded from its training. For each dataset, we adopt the standard 70/30 split create the train and test sets, then repeatedly sample from the train set and run the decision tree algorithms (MetaTree, GOSDT, CART, ID3, or C4.5) to form tree ensembles with specified number of trees from {1, 5, 10, 20, 30, 40, 50, 60, 70, 80, 90, 100]. The majority prediction across trees is taken the
To address the first question, we rigorously evaluate Meta Tree
7

---

Published in Transactions on Machine Learning Research (08/2024)
72.5
74
76-
Demenlirtionn Aucuracy
70.0
Gonccllzzaiion Accuracy
Gerecniization Accuracy
72
74-
67.5
-0-
72-
65.0-
MotaTree
70
GOSDT
Meta
68-
62.5
CART
66-
CART
CART
IDI
ID3
66-
ID3
60.0-
C4.5
64-
C4.5
C4.5
64
30 10 50 do to so so 100
10 30 40 50 60 do so 90 100
10 20 30 40
50
60 do
160
Number of Trees
Number ofTTree
Number of Trees
(A) 91 Datascts, Depth-2 trers
(H) 91 Datasets, Depth-3 trees
(C) 91 Datasets, Depth-4 troes
76-
80-
Geneniiration Accurccy
Genoreliizatonn.ooo Accursey
Generelizations Accurcy
74
78
79
77
78
72-
MetalTee
76-
GOSDT
MetaTree
77-
MotaThee
CART
75-
CART
CART
70-
1D3
ID3
74-
76-
10 20
30
40
50
60
70 Trees
80 90 100
10
20
30
40
50
60 70
80 90 100
10
20 30 40 50
60 70 s0 90 100 Number of Trees
Number
Number of Trees
(D) Tre-of-prompt Datasets, Depth-2 trees
(E) Tree-of-prompt Datasets, Depth-3 trees
(F) Tree-ofprompp Datasets, Depth-l trees
Figure 2: MetaTree demonstrates strong generalization on real-world datasets. MetaTree generalizes
well to 91 held-out datasets for (A) depth-2 trees (B) depth-3 trees and (C) depth-4 trees, despite only being trained produce depth-2 trees. MotaTree also generalizes well to the 13 Troo-of-prompts datasots for (D) depth-2 trees (E) depth-3 3 trees (F) depth-4 trees, which requires constructing a tree steer large language model (Morris et al. 2023 Each plot shows the average test accuracy for tree ensembles of size {1, 5, 10, 20, 30, 40, 50, 60, 70, 80, 90, 100}, with error bars indicating the standard deviation.
ensemble prediction and accuracy is averaged across all datasets. The entire evaluation process is replicated across 5 independent runs and the standard deviation is shown as error bars in the plot.
The result shows that MetaTree demonstrates a consistent and significant performance advantage over the baseline algorithms. GOSDT outperforms CART and the other greedy algorithms when the number of trees is small; this corresponds well to GOSDT's tendency to overfit on training data as it is designed to optimally solve for the train set. It also brings a higher variance in GOSDT's generalization performance. CART and ID3 exhibit similar performance due to their algorithmic similarities. In contrast, C4.5 underperforms, likely due excessive node pruning which hampers performance when model complexity is not high enough.
In addition to the above results, we provide the average single-tree fitting accuracy of the algorithms in Appendix A.4 for a more comprehensive view of their performance.
Generalizing to deeper trees: Fig. BBC Going beyond MetaTree capability to generalize to new data, we now study whether MetaTree can generate deeper trees. To answer this question, we ask MetaTTre to generate trees with depth and 4, and compare its generalization performance with the baseline algorithms, similar to the aforementioned evaluation process.
The result is shown in Fig. B3. It can be observed that MetaTTree still consistently outperforms the baseline algorithms at depth 3. At depth 4, Meta Tree putperforms the baselines in the single-tree scenario or when the number of trees is small, and the greedy algorithms (CART, ID3) catch up with the growing ensemble size.
Note that GOSDT can not stably generate trees with depth greater than 2 without incurring errors on machines with up 125G memory (see Sec. for memory usage analysis). Hence GOSDT excluded from this study.
Out-of-Time
8

---

Published in Transactions on Machine Learning Research (08/2024)
MetiTiee's bahavior when CART generalizes better
MetaTree's behavioc when GUSDT generalizes better
p-1e05
High
High
CARD OcSDTAA
0.5
High
0.5
1aw
liiht
Low
Modiun
59 15%
0.2
52,05%
Medium
40.35%
47 91%
99%%
27.4%%
39,53
Median
42%5
15.11%
0W5
011
0.8
Ouguut with CART
8.5
13
on
Outyut Condetia with GOSDT
0.0
Octput Coucleiio
02
Oriput Couriition GOSDT
D.5
1.0
-0.35
CART Commbiiio GOSDT Comdation
-6.0
-0.5
0/6
0:50
0.75
1.0
(a)
(b)
(c)
Figure 3: We show that Mete learns to adapt its splitting strategy for better generalization.
(a), (b) The figures demonstrate Heeta'rre's tendency to select the more effective generalization strategy: opting for the greedy algorithm CART when CART performs better and the optimal algorithm GOSDT when GOSDT is the better choice, (c) We also conduct regression analysis showing that MetalTree's algorithmic preference positively correlates with the better generalizing algorithm's 's performance.
One reason MetaTree can generalize to deeper trees is that it is designed to generate splitting decisions at each node, hence the generated tree not dependent on the tree depth. Besides, the model has trained on depth 2 trees, Lee the root node split and two children split, we believe Meta Tree might have learned behave as an induction algorithm, thereby generating deeper trees with high quality.
Tree of prompts dataset: Fig. ED We evaluate Tree on the 13 Tree-of- pee-opt-rroptt datasets, that consist of purely categorical features, with the input being LLM's answer to a set of prompts (yes or no) and output being the classification label of the text. Fig. 2D.E again compares MetaTree to GOSDT, CART, ID3, and C4.5. Meta maintains a higher level of generalization accuracy across almost all tree counts when compared to GOSDT, CART, ID3 and C4.5.
GOSDT, CART, and ID3 show lower generalization accuracies, with GOSDT performing slightly better than CART and TD3. Notably, C4.5's performance jumps at depth-4 and surpasses CART and ID3, potentially due its node pruning being effective deeper tree depth.
This evaluation demonstrates MetaTree's great performance Tree-of-promps datasets, highlighting its capability to process categorical features and produce differentiable trees for LLM--geerated inputs and user-queried outputs.
6 Analysis
After benchmarking the performance of Meta'Tree, we conduct an in-depth analysis of its behavior and splitting strategy. Our analysis of MetaTTee begins by examining MetaTrec's tendency between choosing greedy split and an optimized split (Sec. 6.1 We measure the similarity of the generated splits between Meta Tree and CART CART/GOSDT and evaluate all the splits' generalization performance. Turns out MetaTree would opt in for the better algorithm at the right circumstance. We then take a closer look at MetaTTee'' empirical bias-variance (Sec. 6.2). MetaTree illustrates a possibility to reduce empirical variance while not trading off empirical bias. We have included further analysis of evaluating MetaTTree on synthetic XOR problems, considering the effects of noise and feature interactions (Appendix A..p.. And a look into MetaTree's internal mecision-making process (Appendix A.2 reveals MetaTree sometimes gets the right split early on, within the first 9 transformer layers.
6.1 Can MetaTres be less greedy when needed?
Our model is trained on mixed learning signals from GOSDT and CART, selected using generalization performance as the criterion. Our objective is decipher whether MetaTree can strategically adapt its splitting approach between GOSDT and CART. To answer this question, we randomly take 100 samples (each of 256 data points) per dataset from the 91 left-out datasets and instruct MetaTree, GOSDT, and
9

---

Published in Transactions on Machine Learning Research (08/2024)
CART to generate splits for each sample. This approach ensures that all three algorithms are provided with the same data when making the splitting decision, allowing for a meaningful comparison.
We assess the similarity between the splits generated by MetaTTree and those produced by GOSDT and CART. To measure it, we calculate the correlation coefficient between the label assignments following the splits. Additionally, we evaluate the generalization performance by examining the accuracy of the splits on its respective test set. We exclude samples where GOSDT and CART yield highly similar splits (correlation coefficient > 0.7).
We plot the output correlation between MetaTree and CART PORT/GGOTTTT in Fig. 3a for when CART is the better generalizing algorithm among the two. Similarly, we plot the output correlation between Meta and CART CART/GOSD" /OODD in Fig. 3b for when GOSDT is better generalizing. We divide the output correlation values into three categories (low, medium, and high correlation), and it can be observed that MetaTree tends to favor the algorithm that exhibits better generalization performance.
Furthermore, we visualize the relationship between the correlation difference (CART correlation minus GOSDT correlation) and the generalization performance difference (CART's test accuracy minus GOSDT's test accuracy) in Fig. 3e noting that we exclude samples with marginal performance differences (gencralization accuracy difference < 0.08). A medium correlation (Pearson correlation = 0.64, p-value = 0.00003) is observed, suggesting a tendency in MetaTree'ss splitting strategy to align with generalization performance.
To better explain why MetaTree can learn to be non-greedy, at a high level, the model makes one decision at each node: shall make the greedy split now? or is it better to plan for a split one step later? Due to our training strategy, Tree is optimized towards making these choices.
6.2 Breaking through the bias-variance frontier
Finally, we conduct comprehensive bias-variance analysis to evaluate MetaTTree along with GOSDT and CART, the 91 left-out datasets. This analysis shows how each algorithm navigates the trade-off between bias (the error due to insufficient learning power of the algorithm or incorrect model assumptions) and variance (the error due to scnsitivity to small fluctuations in the training set). We use the empirical bias and variance as the measures in our evaluation; we perform 100 repetitions (N=100) for each dataset, therefore we have 100 decision tree models per algorithm per dataset. The empirical bias of an algorithm is calculated as the & difference between its produced models' average output and the ground truth labels, whereas the empirical variance calculated as the mean l difference between its produced models' average output and each model's output.
The result is presented in Fig. 4a Each point in the plot corresponds to the bias-variance coordinates derived from the performance of one algorithm on single dataset. The x-axis represents empirical bias, indicating the algorithm's 's average error from the true function, while the y-axis corresponds to empirical variance, reflecting the sensitivity of the algorithm to different training sets. It can be observed that MetaTTre demonstrates lower empirical variance, suggesting its robustuess in diverse data distribution scenarios.
We accompany the bias-variance analysis with dataset-level performance comparison for single trees of depth 2 in Fig. 4b Each vertical axis represents datasct. We first take the average generalization accuracy of CART and GOSDT as the base accuracy, then calculate the delta. difference between each algorithm's 'ss accuracy and the base accuracy, Fig, 4b further illustrates MetaTree's advantage when comparing against GOSDT and CART.
6.3 Memory Usage and Runtime Analysis
We conduct an analysis to show the memory usage and runtime difference among CART an efficient algorithm with greedy heuristics and GOSDT a mathematically guaranteed optimized algorithm and algorithm that learns from both worlds.
MetaTree- an transformer-
Meta enjoys the benefit of a non-reeursive greedy algorithm constant memory usage and fast inference speed, while having the superior performance among them all.
10

---

Published in Transactions on Machine Learning Research (08/2024)
Generalization Aecuracy Delta
0.10
Meta Tree
0.1
GOSDT CART
0.08
Empirical Variance
0.0
0.04
-0.1-
MetaTree
0.02
GOSDT
-0.2-
CART
0.000
0.025
0,050
0.075
0.100
Empirical Bias
Datasets
(a) Empirical bias-variance analysis.
(b) Dataset level comparisous for single trees.
Figure 4: Empirical bias-variance decomposition for MetaTree, GOSDT, and CART on 91 left-out datasets with 100 repetitions is shown in (a). Meta has significantly lower variance and slightly smaller bias as compared to GOSDT and CART. (b) We compare accuracy delta (y-axis) for each dataset (x-axis) when fitting single tree. The delta is the change compared to the mean accuracy of CART and GOSDT.
Table We show the memory usage of CART, GOSDT and MetaTTree when fitting decision trees with depth & 3, using the memory profiler tool (Pedregosa & Gervais 2021). GOSDT takes a significant amount of memory since it is solving for the full decision tree solution on the data. *We report successfully terminated runs' stats, the experiments conducted workstation with 125G memories and 128 cores.
CART
GOSDT
MetaTree (GPU)
Mean Memory
0.82
146.82 MB*
2420.48 MB
Depth=2 Max Memory
1.41 MB
228.98 MB*
2461.87 MB
Fail Rate
0%
1.1%
0%
Mean Memory
0.79 MB
15,615.69 MB*
2423.96 MB
Depth=3
Max Memory
1.34 MB
87,721.02 MB*
2466.87 MB
Fail Rate
0%
86.81%
0%
Table 3: We show the inference wall time for CART, GOSDT and MetaTreo when fitting decision trees with
depth 2. GOSDT takes a significant amount of time since it solving for the full decision tree solution on the data. *We report successfully terminated runs' stats only.
CART
GOSDT
MetaTree (GPU)
Mean Time
0.047s
26.44s*
0.090s
Depth=2
Max Time
0.15s
74.42s*
0.102s
6.4 Ablation studies
We conduct ablation studics on our learning curriculum (two-phase v.s. single-phase, Appendix A.6), learning signals (noisy real-world labels v.s. relabelled perfect synthetic labels, Appendix A.7), training methodology (supervised training v.s. reinforcement. learning, Appendix A.8), positional bias (with positional bias v.s.
11

---

Published in Transactions on Machine Learning Research (08/2024)
Table 4: We conducted ablation studies on various important design choices, including training curriculum (two-phase versus single-phase, Appendix AA.6). learning signals (noisy real-world labels versus relabelled perfect synthetic labels, Appendix A.7). training methodology (supervised training versus reinforcement learning, Appendix A.8), positional bias (with positional bias versus without, Appendix AA.9 and our choice of Gaussian smoothing ayper-parammtte. We summarize the mean and std of the test accuracy changes for evaluation on the 91 left-out datasets with 100 trees.
Ablation Setting
Performance Change
Curriculum: two-phase single-phase
test acc. + -0.79 + 0.14
Labels: noisy real-world + perfect synthetic
test acc 4 -2.78 0.23 training destabilized
Training: supervised -+ RL
Positional bias: with - without
test acc 4 00.876 0.04
Larger Ganssian radius: o 0.05 + a 0.1
test acc 4 -0.19 + 0.06
Smaller Gaussian radius: 0.05 + a = 0.01 test acc 4 -0.33 + 0.10
without, Appendix A.9 and our choice of Gaussian smoothing Ayper-parameter in Appendix A.10 The summary of our ablation studies is put into Table 4 and the details for each ablation experiment can be found in the corresponding section.
7 Discussion
Limitations and future directions MetaTree is constrained by the inherent architectural limitations of transformers. Specifically, the maximum number of data points and features that MetaTTee can process is boundod by the transformer model's max sequence length (refer to Table A2 for detailed specifications). However, these constraints can be alleviated by training a larger model. transformers' capacity for handling long sequences is constantly improving, with state-of-the-ar LLMs (Reid et al. 2024) now able to take in sequences with up to 10M tokens. While MetaTTree remains limited to small datasets, this work shows important first step in learning to adaptively produce machine-learning models, and we leave training a large-scale LLM for future work.
Conclusion We introduce MetaTree,, a novel transformer-basee decision tree algorithm. It diverges from traditional heuristic- based or optimization-baset decision tree algorithms, leveraging the learning capabilities of transformers to generate strong decision tree models. MetaTTree is trained using data from classical decision tree algorithms and exhibits a unique ability to adapt its strategy to the dataset context, thus achieving superior generalization performance. The model demonstrates its elficacy on unseen real-world datasets and can generalize to generate deeper trees. We conducted a thorough analysis of Meta'Tree's behavior and its bias-variance characteristics. More exploratory analysis and ablation studies are included in the appendix.
This work showcases the potential of deep learning models in algorithm generation, broadening their scope beyond predicting labels and into the realm of automated model creation. Its ability to learn from and improve upon established algorithms opens new avenues for research in the field of machine learning.
Acknowledgement
Our work is sponsored in part by NSF CAREER Award 2239440, NSF Proto-OKN Award 2333790, as well as generous gifts from Google, Adobe, and Teradata. Any opinions, findings, and conclusions or recommendations expressod herein are those the authors and should not be interpretod as necessarily representing the views, either expressed or implied, of the U.S. Government. The U.S. Government is authorized to reproduce and distribute reprints for government purposes not withstanding any copyright annotation hereon.
12

---

Published in Transactions on Machine Learning Research (08/2024)
References
Abhinect Agarwal, Yan Shuo Tan, Omer Ronen, Chandan Singh, and Bin Yu. Hierarchical shrinkage: improving the accuracy and interpretability of tree-based methods. arXiv:2202.008: 00858 fea, statj, 2022. URL httpp://axxw..orggbbbbst. 00858 arXiv: 2202.00858.
Dimitris Bertsimas and Jack Dunn. Optimal classification trees. Machine Learning, 106(():1039-1085 2017.
James Betker, Gabricl Goh, Li Jing, Tim Brooks, Jianfeng Wang, Linjie Li, Long Ouyang, Juntang Zhuang, Joyce Lee, Yufei Guo, et al. Improving image generation with better captions. Computer Science. https://cdn. openoi. com/papers/ httppppppp///lleeeee// dall-e--. pdf, 2:3, 2023.
Gérard Bian, Erwan Scornet, and Johannes Welbl. Neural random forests. Sankhya A, 81(2):347-38, 2019.
L. Breiman, J. H. Friedman, R. A. Olshen, and C. J. Stone. Classification and Regression Tress. Wadsworth and Brooks, Monterey, CA, 1984 UBLAtttpe//ww...oottldeg....e book/ #ook//978041204818
wwtp:/..otledee.comm http:e/ee///ccaasaaaaaaaaaaaaaaa http://wwww..eeeeeee////aaaaaaaa and hrtr///nnn-rreeee///iieeeeeaa Friedman Sereieeddan--toeeeeee -tone--tsoenn p/
Leo Breiman. Random forests. Machine Tearning, 45(1):5-322 32, 10 2001. ISSN 1573-0565. doi: (0.1023/A:101093888
Miguel A Parreira-Prrináán and Pooya Tavallali. Alternating optimization decision trees, with application to learning sparse oblique trees. Advances newrol information processing systems, 31, 2018.
Tianqi Chen and Carlos Guestrin. Xgboost: A scalable tree boosting system. In Proceedings of the 22nd aem sigkdd international conference on knowledge discovery and data mining, pp. 785-794, 2016.
Hugh Chipman and Robert F. McCulloch. Hierarchical priors for bayesian cart. shrinkage. Statistics and Computing, 10:17-24, 2000.
Hugh A Chipman, Edward I George, and Robert E McCulloch. Bart: Bayesian additive regression trees. The Annals of Applicd Statistics, (1))2666-29; 2010.
Janez Demsar. Statistical comparisons of classifiers over multiple data sets The Journal of Machine learning research, 7:1-30, 2006.
Nouha Dziri, Ximing Lu, Melanie Sclar, Xiang Lorraine Li, Liwei Jian, Bill Yuchen Lin, Peter West, Chandra Bhagavatula, Ronan Le Bras, Jena D Hwang, et al. Faith and fate: Limits of transformers on compositionality. arXiv preprint arXiv:2905. 18654, 2023.
Alhussein Fawzi, Matej Balog, Aja Huang, Thomas Hubert, Bernardino Romera- Paredes, Mohammadamin Barekatain, Alexander Novikov, Francisco J R Ruiz, Julian Schrittwieser, Grzegorz Swirszez, et al. Discovering faster matrix multiplication algorithms with reinforcement learning. Nature, 610(7930):47-636 2022.
Benjamin Feuer, Chinmay Hegde, and Niv Cohen. Sealing tabpfn: Sketching and feature selection for tabular prior-data fitted networks. Xiv preprint arxio:2311 10609, 2023.
Chelsea Finn, Picter Abbeel, and Sergey Levine. Model-agnostic meta-learuing for fast adaptation of deep networks. International conference on machine learning, pp. 1126 1135. PMLR, 2017.
Yoav Freund, Robert E Schapire, al. Experiments with a new boosting algorithm. In teml, volume 96, pp. 148-156. Citeseer, 1996.
Nicholas Frosst and Geoffrey Hinton. Distilling neural network into soft decision tree. anXiv preprint arXiv:1711. 115101971,,974,, 2017.
Shivam Garg, Dimitris Tsipras, Percy S Liang, and Gregory Valiant. What can transformers learn in-context? case study of simple function classes. Advances in Neural Information Processing Systems, 35:30583 35:30583-30598, 2022.
Yury Gorishnly, Tvan Rubachev, Nikolay Kartashev, Daniil Shlenskii, Akim Kotelnikov, and Artem Babenko. Tabr: Unlocking the power of retrieval-augmented tabular deep learning, arXiv preprint arXiw:2307. 14338, 2023.
Lóo Crinsztajn, Edouard Oyallon, and Gaël Varoquaux. Why do tree-based models still outperform deep learning on typical tabular data? Advances in Newral Information Processing Systems, 33:507 520, 2022.
Etienne Grossmann. Adatree: boosting a weak classifier into a decision tree. 2004 Conference on Computer Vision and Pattern Recognition Workshop, pp. 105-105. IEEE, 2004.
Suryabhan Singh Hada, Miguel Á Carreira-Perpiiánn, understand and manipulate neural net features. Data Mining and Knowledge Discovery, pp. 1-40, 2023.
Arman Zharmagambetov. Sparse oblique decision trees: A tool
Michael Hanna, Ollie Lin, and Alexandre Variengien. How does gpt-2 compute greater-than?: Interpreting mathematical abilities in a pre-trained language model. Xr preprint ar XrXn:2305500554 005886 2023.
13

---

Published in Transactions on Machine Learning Research (08/2024)
Stefan Hegselmann, Alejandro Buendia, Hunter Lang, Monica Agrawal, Xiaoyi Jiang, and David Sontag. Tablim: Few-shot classification of tabular data with large language models. In International Conference Artificial Intelligence and Statistics, pp. 5549-5581. PMLR, 2023.
Munir Hiabu, Enno Mammen, and Joseph T Meyer. Random planted forest: directly interpretable ensemble. arXiv preprint arXiv:2012.14663 2020.
Noah Hollmann, Samuel Müller, Katharina Eggensperger, and Frank Hutter. Tabpfn: A transformer that solves small tabular classification problems in second. arXiv preprint arXie:2207.01845 2022.
Timothy Hospedales, Autreas Antoniou, Paul Micaelli, and Amos Storkey. Meta-learning in neural networks: A survey, IEEE transactions on pattern analysis and machine intelligence, 44(9):5149- (199),514--116, 2021.
Xiyang Hu, Cynthia Rudin, and Margo Seltzer. Optimal sparse decision trees. Advances in Neural Information Processing Systems (NeurIPS), 2019.
Nathanacl Jo, Sina Aghaci, Jack Benson, Andres Gomez, and Phebe Vayanos. Learning optimal fair decision trees: Trade-offs between interpretabilityy fairness, and accuracy. In Proceedings of the 2023 AAAT/ACM Conference on AI, Ethics, and Society, pp. 181-192, 2023.
Aaron E Korublith, Chandan Singh, Cabriel Devlin, Newton Addo, Christian J Streek, James F Holmes, Nathan Kuppermann, Jacqueline Grupp-Phelan, Jeffrey Fineman, Atul J Butte, and Bin Yu. Predictabilityy and stability testing to assess clinical decision instrument performance for children after blunt torso trauma. medRaio, 2022. dot: 10.1101 10.1101/2022.00 020.//20......22222.22.. URL httpp::/wwwt wttp:///wwwwwwwwi////m//////m. mwdrxiv.ddvv... pttg//oonentt/erll///22 00002/003/0//022.222 03. 03.08. 22270944
Hyafil Laurent and Ronald L Rivest. Constructing optimal binary decision trees is np-complete. Information processing letters, 5(1):15-17, 1976.
Guang-He He Lee and Tommi S Jankkola. Oblique decision trees from derivatives of relu networks. arXiv preprint 1909: 2019.
Jimmy Lin, Chudi Zhong, Diane Hu, Cynthia Rudin, and Margo Seltzer. Generalized and scalable optimal sparse decision trees.
In International Conference on Machine Learning, pp. 6150-6660 6160. PMLR, 2020.
Hariharan Manikandan, Yiding Jiang, and Zico Kolter. Language models are weak learners. arXiv preprint ar Xrv: 14101, 2023.
Daniel J Mankowitz, Andrea Michi, Anton Zhernov, Marco Gelmi, Marco Selvi, Cosmin Paduraru, Edouard Leurent, Shariq Iqbal, Jean-Baptiste Lespiau, Alex Ahern, et al. Faster sorting algorithms discovered using deep reinforcement learning. Nature, 618(7964):2577 263,, 2023.
John X Morris, Chandan Singh, Alexander M Rush, Jaanfeng Gao, and Vuntian Deng. Tree prompting: efficient task adaptation ion without fine-tuning, arXiv preprint ar 100:22010.14030 2023.
W. James Murdoch, Chandan Singh, Karl Kumbier, Reza Abbasi-Asl, and Bin Yu. Definitions, methods, and applications in interpretable machine learning. Proceedings of the National Academy of Sciences of the United States of America, 116(44): 22071 120080, 2019. doi: 10. 10.1073/pnas. 19006541 16.
Alex Nichol, Joshua Achiam, and John Schulman. On first-order meta-learning algorithms. arxio preprint arXiv: 029999 2018.
Soma Onishi, Kenta Oono, and Kohei Hayashi. Tabret: Pre-training traneformer-based tabular models for unseen columns. Xix preprint arXie:2308.15747, 2023.
OpenAL. Gpt-4 technical report, 2023.
F. Pedregosa, G. Varoquaux, A. Gramfort, V. Michel, Thirion, O. Grisel, M. Blondel, P. Prettenhofer, R. Weiss, V. Dubourg,
J. Vanderplas, A. Passos, D. Cournapeau, M. Brucher, M. Perrot, and E. Duchesnay. Seikit-learn: Machine learning in Pythou. Journal of Machine Learning Research, 12:2825 2830, 2011.
Fabian Pedregosa and Philippe Gervais. memory-profile: module for monitoring memory usage of a python program. 2021.
J. Ross Quiulan. Induction decision trees. Machine learning, 1(1):81-100 1986.
Ross Quinlan. Cz. 5: programs for machine learning. Elsevier, 2014.
Machel Reid, Nikolay Savinov, Denis Teplyashin, Dmitry Lepikhin, Timothy Lillicrap, Jean-baptistc Alayrac, Radu Soricut, Angeliki Lazaridon, Orhan Firat, Julian Schrittwieser, al. Gemini 1.5: Unlocking multimodal understanding across millions of tokens of context. ar Xau preprint arXs::2003.055. 05530, 2024.
14

---

Published in Transactions on Machine Learning Research (08/2024)
Joseph D Romano, Trang T Le, William La Cava, John T Gregg, Daniel Goldberg, Praneel Chakraborty, Natasha L Ray, Daniel Himmelstein, Weixuan Fu, and Jason H Moore. Pmlb v1.0: an open source dataset collection for benchmarking machine learning methods. arXiv preprint AXN::2012.0005800 2021.
Bernardino Pareea- Mohammadamin Barekatain, Alexander Novikov, Matej Balog, M Pawan Kumar, Emilien Dupont, Francisco JR. Ruiz, Jordan S Ellenberg, Pengming Wang, Omar Fawzi, et al. Msthematical discoveries from program search with large language models. Nature, pp. 1-3, 2023.
Cynthia Rudin. Please stop explaining black box models for high stakes decisions. arXiv preprint arXiv: 1811. 10155, 2018.
Chandan Singh, Keyan Nasseri, Yan Shuo Tan, Tiffany Tang, and Bin Vu. imodels: a python package for fitting interpretable models. Journal of Open Souree Software, 6(61) 2021. doi: 10.21105//jss.03199 URL httpp:://doi.oooo orro org/10.21105/ [088.03192
Chandan Singh, Armin Askari, Rich Caruana, and Jianfeng Gao. Augmenting interpretable models with large language models during training. Nature Communications, 14(1):7913, 2023.
Daria Sorokina, Rich Caruana, and Mirek Riedewald. Additive groves of regression trees. In Mochine Learning: ECML 2007: 18th European Conference on Machine Learning, Worsam; Poland, September 17-21, 2007. Proceedings 18, pp. 323-334. Springer, 2007.
Yan Shno Tan, Chandan Singh, Keyan Nasseri, Abhineet Agarwal, and Bin Yu. Fast interpretable greedy-tree sums (figs). arxf::2001.1 11931 fes, statj, 2022.
11931 arXiv: 2201.11931.
Ryutaro Tamno, Kai Arulkumaran, Daniel Alesander, Antonio Criminisi, and Aditya Nori. Adaptive neural trees. In Intornational Conference on Machine Learning, pp. 6166-6175. PMLR, 2019.
Hugo Touvron, Louis Martin, Kevin Stone, Peter Albert, Amjad Almahairi, Yosmine Babaei, Nikolay Bashlykov, Soumya Batra, Prajjwal Bhargava, Shruti Bhosale, et al. Llama 2: Open foundation and fine-tuned chat models. arXiv prepriut Xix:22000 09288, 2023.
Gilmer Valdes, José Marcio Luna, Eric Eaton, Charles B Simone, Lyle H Ungar, and Timothy D Solberg. Mediboust: a patient stratification tool for interpretable decision making in the cra of precision medicine. Scientific reports, 6(1):37854, 2016.
Joaquin Vanschoren, Jan N. van Rijn, Bernd Bischl, and Lais Torgo. Openml: networked science in machine learning. SIGKDD Explovations, 15(2):49-60 60, 2013. doi: (0.1145/664119022611188 URL http:///oi. acm. 111///..114////411900 264119
Ashish Vaswani, Noam Shazeer, Niki Parmar, Jakob Uszkoreit, Llion Jones, Aidan N Gomez, Lukasz Kaiser, and Illia Polosukhin. Attention is all you need. Advances in neural information processing systems, 30, 2017.
Ricardo Vilalta and Youssef Drissi. A perspoctive view and survey of meta-learning. Artificial intelligence review, 18:77-00 95, 2002.
Steve Yadlowsky, Lyric Doshi, and Nilesh Tripuraneni. Can transformer models generalize via in-context learning beyond protraining data? NewrIPS 2023 Workshop on Distribution Shifts; New Prontiers with Foundation Models, 2023.
Shunyu Yau, Dian Yu, Jeffrey Zhao, Izhak Shafran, Thomas L. Griffiths, Yuan Cao, and Karthik Narasinhan. Tree of thoughts: Deliberate problem solving with large language models, 2023.
Olcay Taner Vildz and Fthem Alpaydın. Regularizing soft decision trees. In Information Sciences and Systems 2013: Procendings of the 28th International Symposium on Computer and Information Sciences, pp. 15-21. Springer, 2013.
Valentina Zantodeschi, Matt Kusner, and Vlad Niculac. Learning binary decision trees by argmin differentiation. International Conference on Machine Learning, pp. 12298-12306 PMT.R, 2021.
Hattic Zhou, Arwen Bradley, Etai Littwin, Noam Razin, Omid Saremi, Josh Susskind, Sany Bengio, and Prectum Nakkiran. What algorithms can transformers learn? study length generalization. arXie preprint Xix: 16098,, 2023.
Wangchuushu Zhou, Canwen Xu, Tao Ge, Julian McAuley, Ke Xu, and Furu Wei. Bert loses patience: Fast and robust inference with carly exit. Advances in Newral Information Processing Systems, 33:18330- 18341, 2020.
Bingzhao Zhu, Xingjian Shi, Nick Erickson, Mu Li, George Karypis, and Mahsa Shoaran. Xtab: Cross-table pretraining for tabular transformers. Xio preprint arXio:2305. 06090, 2023.
15

---

Published in Transactions on Machine Learning Research (08/2024)
A Appendix
A.1 Controlled setting: noisy XOR
We evaluate the MetaTree model in a controlled setting, on XOR datasets with 1e,el=(1,2), label flipping noise=(0%, 5%, 10%, 15%, 20%, 25%),, and dataset size 10k for each XOR level/noise ratio configuration. To assess performance, we employ the relative error metric, defined as the gap between the achieved accuracy and the maximum possible accuracy achievable (= 100% labee noise ratc). Note that we have only trained our model 10k trees generated with XOR Level 1 and 15% label noise. This specific training scenario was chosen to evaluate the model's robustness towards noise and adaptability to harder problems.
As indicated in Table Alb MetaTrec demonstrates a remarkable capacity for noise resistance and generalization. Once MetaTTee learns to solve the XOR Level problem, it can withstand much stronger data noise (while Meta has only seen 15% noise); and generalize to significantly harder XOR Level 2 problems (while MetaTree has only trained on XOR Level 1).
We further conduct qualitative analysis, asking CART and MetaTree to generate decision trees for XOR Level 1&:2 problems. The resulting trees, as depicted in Figure A1 offer insightful comparisons into the decision-making processes of both models under varying complexity levels.
A.2 Probing MetaTree's decision-making process
Our study is partially inspired by the logit-lens behavior analysis on GPT-2 (Hanna al. 2023). Their findings suggest that GPT-2 often forms initial guess about the next token in its middle layers, with subsequent layers refining this guess for the final generation distribution. Building on this concept, we aim to investigate whether a similar guessing-refinnng pattern exists in our model and explore the feasibility of implementing an early exiting strategy as outlined in Zhou et al. (2020).
To this end, we analyze the decision-making process of our model at each Transformer layer. We can scrutinize how the model's decisions evolve by feeding the intermediate representation from each layer into the output module. One qualitative example is shown in Fig. Alc. where we ask Meta'Tree to generate the root node split an XOR Level 1 problem. We observe that the model gets reasonable split right after the first layer. At layer 9, the model reaches the split that is close to its final output, and layer 10's output is alternative revision with close to ground truth split (the ground truth can be vertical or horizontal split).
We proceed with a quantitative analysis to investigale the correlation between the model's final split and the splits occurring in its intermediate layers. We take samples from the 91 left-out datasets following the same procedure as dotailed in Sec. 6.11 and we ask MetaTres generate splits on them. The correlation between splits is determined by calculating the correlation coefficient between the label assignments after applying the splits. This metric essentially measures how closely aligned the splits are in dissecting the input regions.
The results of our quantitative analysis are presented in Fig. Aid Notably, the correlation shows gradual increase from layer 1 to 8, nearly reaching I at layer 9. However, it then drops significantly to approximately 0.2 at layers 10 and 11. This pattern suggests that the model consistently improves its ability to make accurate predictions in the initial 1 to 9 layers, while layers 10 and 11 may introduce some divergence or revision in its dicision-making process.
This finding provides valuable insights into the internal decision-making process of Mete It raises the possibility of considering early exit strategies at intermediate layers, particularly around layer 9, to enhance overall efficiency.
A.3 Statistical Comparisons for Single-trees
We conduct Frodman-Holm test Demšar (2006) to compare the single-tree level performance of Mrta/Tree. Results are shown in Table A1 The statistical tests confirm MetaTroe's performance advantage when compared against the baseline algorithms.
16

---

Published in Transactions on Machine Learning Research (08/2024)
Hidden Layer
Hidden Layer 10
Acca66.07
Acce 98.04
Hidden Layer 9
Hidden Layer 12
(4) Gready Algorithm (feft. whereas MetaTree solves (1gh))
Aoc=67.19
Acc=89.45
(c) Logit-lens probing MetaTree on an XOR Level problem.
Gradd XOR (jeft),
generalizes (rigt).
1.0
(a) Greedy algorithms such as CART cannot solve prob-
lems that require planning, such as Level 1&2 XOR. We show Meta'Tree can learn to solve Level 1 XOR and generalize solving Level XOR.
0.8
Label Corelation
0.4
0.2
Noise
0%
5%
10%
15%
20%
25%
XOR L1
3.59
3.26
2.94
2.64
2.37
2.04
0.0
XOR L2
12.78
11.06
9.34
7.32
4.99
2.05
10
11
12
Layer
(b) Relative error of Meta (trained XOR Level with 15% noise) on XOR datasets with level=(1,2) and label flipping noise rate from 0% to 25%.
(d) The output correlation analysis between the final split and each layer's splits of Meta across 91 left- out datasets.
Figure A1: Exploratory analysis of MetaTree. (a), (b) We examined MetaTree's performance a controlled XOR setting with various noise levels and problem difficully. We show illustration of Meta solving Level XOR and generalizing to Level 2 XOR while greedy algorithms like CART are unable to solve these. (c), (d) We probe the decision-making process of Mrea over the Transformer layers, found out that MetaTree can very often generate the final split early on.
A.4 Single-tree fitting accuracy
We show the fitting accuracy of the algorithms in Fig. A2 when gencrating single depth-2 docision trees over the datasets.
A.5 Model Hyperparameters
We list Mrec's hyperparameters in Table A2 We note that in the following ablation studics, the basc and ablation models are trained with fewer steps (2M steps instead of 4M steps) due to the compute resource limit.
17

---

Published in Transactions on Machine Learning Research (08/2024)
Table Al: Single-tree statistical comparison over the datasets with Fredman-Holle test Demsšr (2006
We are showing the p-values of the ranked tests. They are all of statistical significance (i.c. 0.05), demonstrating MetaTree's advantage over the baseline algorithms.
MetaTree v.s.
MetaTree
GOSDT
CART
ID3
C4.5
91D, depth=2
2.71e-08
8.88e-16
8.88e- 16
0.00
ToP, depth=2
0.025
0.017
0.022
0.004
91D, depth=3
0OM
9.42e-12
4.19e-11
0.00
ToP, depth=3
0OM
0.014
0.011
0.028
91D, depth=4
OOM
2.86e-14
3. 131--10
0.00
ToP, depth=1
OOM
0.006
0.006
0.006
Tree of Prompts Datasets, Depth
91 Datasets, Depth-2
Single Tree Fitting Aecuracy
Single Tree Fitting Accuracy
70-
80
78-
65
76
74-
60
MetaTree
GOSDT
CART
ID3
C4.5
MetaTree
GOSDT
CART
ID3
C4.5
(b) Mean fitting accuracy the 13 Tree-of-prompis datasets.
(a) Mean fitting accuracy over the 91 left-out datasets.
Figure A2: Average fitting accuracy for algorithms when generating single depth-2 trees.
A.6 Ablation Study: Training Curriculum
We devise a two-phase learning curriculum for MetaTree's training, as described in Sec. 3.2 Here we conduct an ablation study comparing our curriculum with a curriculum that only uses the GOSDT+CAA CART datasct with otherwise same configurations.
The evaluation process is the same the one used in Sec. 5 we compute their average test accuracy on 91 left-out datasets and for the number of trees from {1, 10, 20, 30, 40, 50, 60, 70, 80, 90, 100).
As shown in Fig. A5 the learning curriculum has significant impact on the model at the end of training.
A.7 Ablation Study: Training Signal
We explore training with noise-free data, by relabeling the datasets with the generated trees' prediction. By relabeling the dataset, we can guarantee optimal decision splits are being fed into the model's training procedure.
We evaluate model trained in such a manner on the left-out datasets, for the number of trees from {1, 5, 10, 20, 30, 40, 50, 60, 70, 80, 90, 100).
18

---

Published in Transactions on Machine Learning Research (08/2024)
Table A2: Hyperparameters for MetaTTee training.
Hyperparameter
Value
Number of Hidden Layers
12
Number of Attention Heads
12
Hidden Size
768
Number of Parameters
149M
Learning Rate
5e-5
Learning Rate Schedule
Linear Decay
Optimizer
AdamW
81
0.9
82
0.999
Training dtype
bf16
Number of Features
10
Number of Classes
10
Block Size
256
Tree Depth
2
5e-2
Number of Warmup Steps
1000
Number of Training Steps
4,000,000
Steps in Phase 1 (GOSDT)
1,000,000
Steps Phase 2 (GOSDT+CART)
3,000,000
Batch Size
128
We show the results in Fig. on unseen datasets.
A3 learning from the original noisy labels brings better generalization capacity
72-
Generalization Accuracy
70-
68
66
64-
MetaTree
MetaTree Synthetic Trees
62
10
20
30 40 50 60 70 80 100
Number of Trees
Figure A3: Average generalization accuracy for training with different labels. Meta trains directly from the noisy ground truth label. Meta'Tree Synthetic Trees is trained from the synthetic labels derived from the ground truth decision trees.
A.8 Ablation Study: Reinforcement Learning
In the early phase of our study, We experimented with training a model directly using reinforcement learning (specifically with proximal policy optimization), where the model can explore the space of decision tree splits and get rewards as function of the final generalization accuracy. This approach is plausible, however, we found that the training process is unstable with the sparse reward and large search space. We plot 30 runs of
19

---

Published in Transactions on Machine Learning Research (08/2024)
such RL training in Fig. A4 where the task is to classify XOR L1 with only 2 dimensions and without any
noise.
RL Training on Simple Level XOR
1.0
0.9
Eval Eval Accuracy
0.8
0.7-
250
500
750
1000
Step
Figure A4: 30 runs of model training using reinforcement learning. It can be observed that the process is highly unstable.
As can be seen, the training process is highly unstable and rarcly reaches above 95% eval accuracy, whereas the regular approach could quickly get to 97-98 eval acc. Therefore, we leave reinforcement learning for MelaTrea as future research.
72-
Generalization Accuracy
70-
68
MetaTree Curriculum
66
Single Curriculum
10 20 30 40 50 60 70 80 90 100 Number of Trees
Figure A5: Average generalization accuracy for two different learning curricula. Meta Tree's learning curriculum involves first-phase training on GOSDT trees only, and a socond-phase training on GOSDT+CART trees. The other curriculum is trained directly from GOSDT+CART datasets.
A.9 Ablation Study: Positional Bias
As introduced in Sec. 3 MotaTTree uses two positional bias by, by at the input layer anchor the row and column positions. We apply sequential and dimensional shuffling during training make the model learn the positional invariance.
20

---

Published in Transactions on Machine Learning Research (08/2024)
72
Generalization Accuracy
70
68
66-
MetaTree
Without Positional Bias
10 20 30 40 50 60 70 80 90 100 Number of Trees
Figure A6: Average generalization accuracy for models trained with or without positional bias.
Alternatively, we can have a design that provides zero positional information to the model and becomes naturally invariant input permutations. However, this design may have difficulties identifying the split, the information will be mixed altogether over the Transformer layers.
We train a model with such design, keeping all other training configurations the same, and compare its performance on the 91 left-out datasets using their average test accuracy for the mumber of trees from {1, 5, 10, 20, 30, 40, 50, 60, 70, 80, 90, 100).
As shown in Fig. A6 having such positional bias empirically beneficial compared to a design that provides no positional information to the model.
A.10 Ablation Study: Gaussian Smoothing Loss
We conduct an ablation study on the radius of the Gaussian smoothing loss (a). It controls how much noise and signal the model receives during training. When a too large, every split may seem like a target split, but when a is too small, the model may fail to learn from some equally good splits.
Following the evaluation pipeline as described in Sec. we conduct our ablation study comparing model trained using a=5c-1 with models trained with larger 0=le-1 and smaller 0=1c-2, on 91 left-out datasets and compute their average test accuracy for number of trees from f1, 5, 10, 20, 30, 40, 50, 60, 70, 80, 90, 100)
As shown in Fig. A7 the smoothing radius does have an impact on the trained model, and choosing an appropriate radius is essential training an effective model.
21

---

Published in Transactions on Machine Learning Research (08/2024)
72
72
Generalization Accuracy
Generalization Aecuracy
70-
70-
68-
Sigma=5e-2 5e-2
Sigma=5e-2
66
Sigma=1e-1
66
Sigma=1e-2
10 20 30 40
50 60 70 80 90 100
10 20
70 80 90 100 Number Trees
40
50
60
Number of Trees
(a) Training with larger o=le-1
(b) Training with smaller o=
Figure A7: Average generalization accuracy for models trained with different Gaussian Smoothing radius.
A.11 Datasets
Table A3: List of 91 datasets used MetaTrec's evaluation.
Dataset
Entries
Dim.
Class
mfeat fourier
2000
76
10
mfeat zernike
2000
47
10
mfeat morphological
2000
6
10
mfeat karhunen
2000
64
10
page blocks
5473
10
5
opidigits
5620
64
10
pendigits
10992
16
10
waveform 5000
5000
40
3
Hyperplane 1E 3
1000000
10
Hyperplane 10 1E 4
1000000
10
2
pokerhand
829201
10
RandomRBF 0 0
1000000
10
5
RandomRBF 1E 3
1000000
10
RandomRBF 50 1E 3
1000000
10
5
RandomRBF 1E 4
1000000
10
RandomRBF 50 1E 4
1000000
10
5
SEA 50
1000000
SEA 50000
1000000
3
2
satimage
6430
36
BNG labor
1000000
BNG breast
39366
9
2
BNG mfeat karhunen
1000000
64
10
BNG bridges version1
1000000
3
6
BNG mfeat zernike
1000000
47
10
BNG eme
55296
2
3
BNG colic ORIG
1000000
BNG colic
1000000
7
2
BNG credit
1000000
BNG page blocks
295245
10
5
BNG credit
1000000
2
22

---

Published in Transactions on Machine Learning Research (08/2024)
BNG pendigits
1000000
16
10
BNG cylinder bands
1000000
18
2
BNG dermatology
1000000
BNG sonar
1000000
60
2
BNG glass
137781
BNG heart
1000000
5
BNG heart statlog
1000000
13
2
BNG vehicle
1000000
18
4
BNG hepatitis
1000000
2
BNG waveform 5000
1000000
10
3
BNG 2oo
1000000
1
7
vehicle sensIT
98528
100
UNIX user data
9100
1
9
fri c3
1000
25
rmftsa sleepdata JapaneseVowels fri c4 1000 100 abalone
1024
2
4
9961
14
1000
100
2
4177
2
fri c4 1000 25 bank8FM
1000
25
2
8192
2
analcatdata supreme ailerons
4052
7
2
13750
40
2
epu small
8192
12
space ga
3107
2
fri cl 1000
1000
puma32H
8192
32
2
c3 1000 10
1000
10
epu act
8192
21
2
fri c4 1000 10 quake
1000
10
2178
3
2
fri c4 1000 50
1000
50
fri c0 1000 5 delta ailerons fri c3 1000 50 kin8nm
1000
5
2
7129
2
1000
50
8192
2
fri c3 1000
1000
puma8NH
8192
8
2
delta elevators
9517
houses
20640
8
2
bank32nh
8192
32
fri cl 1000 50 house 8L.
1000
50
2
22784
fri c0 1000 10 elevators wind
1000
10
2
16599
18
2
6574
14
fri c0 1000 25 fri c2 1000 50 pollen mv
1000
25
2
1000
50
3848
5
2
40768
fried
40768
10
2
fri c2 1000
1000
25
fri c0 1000 50
1000
50
2
cl 1000 10
1000
10
fri c2 1000 5
1000
5
2
fri c2 1000 10
1000
10
fri cl 1000 25
1000
25
2
visualizing soil
8641
3
2
23

---

Published in Transactions on Machine Learning Research (08/2024)
socmob mozilla1
1156
15545
5
2
pe3 pel
1563
37
1109
21
2
24


Reviews:
[{"review_id": "9GjtSYQzAB", "reviewer": "Reviewer_j58L", "summary": "", "questions": "", "limitations": "", "rating": null, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "*Strengths* - generating decision trees (DT) in a non-greedy fashion could have a major impact on ML. As DTs are very interpretable and are extensively used for commercial tabular data this could have vast implications on data regimes where leading methods such as deep-learning are less effective. \n\n\n*Weaknesses* - I have several concerns regarding the validity of the proposed method:\n\nThe technical parts of the paper are not well written. For example, the authors should make it clear what happens during inference time of (a) a new dataset (using the transformer), and (b) a new sample (using a DT generated by the transformer). Moreover, parts like the curriculum, data generation, and weighting of the two data-sources are not well-explained. A re-writing of Section 3 entirely could greatly improve the quality of the paper.\n\nNo analysis of the proposed features (the representation and self attention, the smoothing, the curriculum, etc’). Each feature could have been replaced with a simpler option, and understanding the contribution of each is crucial. \n\nEmpirical evidence - maybe because the curriculum and optimization processes are not well defined, it is not clear to me what creates the gap between the baselines and MetaTree given that it is trained via supervised learning. Another aspect I find confusing, is that the authors claim that the trees are closer to optimal (or less greedy), however without the information over the budget (size of the sub-tree) I can’t see how the decisions are not greedy by nature. For instance, given a fixed dataset, if we have one split vs. multiple splits can drastically change the decision in the root node. However, MetaTree is unaware of this budget. Finally, it would help if the authors explain why the datasets generated in the paper to create the MetaTree algorithm are a good representation of most of the datasets out there.", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "No", "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": "", "paper_topic_and_main_contributions": "", "excitement": null, "reproducibility": null, "ethical_concerns": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "summary_of_contributions": "This work proposes a new supervised learning algorithm for generating decision trees. They designed a specific architecture based on a Transformer model that predicts the attribute and threshold from the data to split upon. Finally they demonstrate the model performance by predicting decision trees for several datasets.", "claims_and_evidence_yn": "No", "claims_explanation": "", "audience_yn": "Yes", "audience_explanation": "", "requested_changes": "Besides addressing the weaknesses above, there are some minor corrections and clarifications: \n\nIn eq.3 you add b1, b2 and the first term which is mathematically invalid. Please clarify.\n\nIn Fig. 2 what are the number of trees?", "broader_impact_concerns": "NA", "additional_comments": "", "extra_scores": {}, "extra_text": {}}, {"review_id": "K5oWKZLJ0w", "reviewer": "Reviewer_Dizq", "summary": "", "questions": "", "limitations": "", "rating": null, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "*Strengths* The work combines a nowadays very popular architecture, i.e., transformers, with a classical classification strategy, i.e., decision trees, hoping that the elsewhere observed generalization ability of transformers leads to better performances in the tree generation. The idea is, in particular, to benefit from the context sensitivity of the attention mechanism. Moreover, the differentiability of the architectural action with respect to its weight is another advantage. From this point of view, the paper is interesting as it might lead to a further step in the modern design of decision trees.\n\n*Weaknesses* The paper is not well written, in my opinion, and some parts are kind of sketchy making it overll not clear. One weakness of the contribution is that it appears as a purely numerical experiment without discussion of a number of choices (for example, the size of the parameter sets or the impact of the embedding dimension) and without a theory-oriented analysis (e.g., the possible scaling of the accuracy with the size of the datasets, or the dimension, the number of hidden layers of the MLP, the number of transformers layers, etc). From what I understand, the training of the transformers relies on trees generated by different algorithms: the (expectedly relevant) impact of the nature of the training set is only marginally discussed. In this sense, the paper seems more of a (not very detailed) technical report without offering particular insights into *why* the proposed strategy is successful or how it is possible to extract optimal performances from the proposed algorithmic strategy.", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "No", "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": "", "paper_topic_and_main_contributions": "", "excitement": null, "reproducibility": null, "ethical_concerns": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "summary_of_contributions": "The paper proposes a strategy to generate decision trees by using a transformer architecture: the architecture produces a splitting of the input learning after trees which are generated by using CART and the optimal GOSDT algorithm by a learning curriculum strategy. The authors perform subsequently numerical experiments on real datasets showing that the strategy generates trees that can perform a classification task with good accuracy even beyond the depth of the tree actually used for the training phase. The work is of experimental/numerical nature, as it relies on the substitution of the application of some explicit splitting criterion in each decision tree level by the action of a transformer.", "claims_and_evidence_yn": "No", "claims_explanation": "", "audience_yn": "Yes", "audience_explanation": "", "requested_changes": "I list a brief collection of questions aside from some points raised in the *Weaknesses* paragraph that might be further clarified.\n- The central paragraph on page 4 is, I think, too sketchy and relies on a standardization of the nomenclature in attention papers which needs nevertheless to be improved. For example, the authors never clarify what MPL means, nor how the query, key and value matrices are related to the input. Also, what is $X_h$ in the line before 4? (I expect $\\mathrm{Emb}(X)$ although I do not understand if/why the notation has been changed). Finally, it is not clear what is happening in the only non-numbered equation after Eq 2: it appears that the MLP takes as input a sum of objects that have different dimensions...! Why do the authors need two biases in the expression that generates $\\mathrm{Emb}$?\n- In Eq. 6, how does the relative contribution of rows and columns for the generation of $Y_h$ have been decided? (Eg, it appears that the relative contribution of the two parts is not important in the efficacy of the algorithm).\n- It would be useful to add some comments on the nature of the OpenML datasets (i.e., their content).  As a side note, what is the adopted criterion to sort datasets in Fig 4b?\n- The authors claim that ```MetaTree's performance improvement comes from its ability to dynamically switch between a greedy or optimal approach depending on the context of the dataset```. It is not clear what *dynamically* means and I would advise further clarification on this point. Also related to this, have the authors observed any decay of accuracy for deep trees and, if this is the case, is this related to the adopted number of transformers layers?", "broader_impact_concerns": "There are no broader impact concerns on ethical implications requiring an explicit statement.", "additional_comments": "", "extra_scores": {}, "extra_text": {}}, {"review_id": "OiNhdwK5TX", "reviewer": "Reviewer_YdWW", "summary": "", "questions": "", "limitations": "", "rating": null, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Strengths:  \n1. The paper is well-written. I like that the authors presented the method in Section 3 in a clear  and concise way.  \n\n\n2. Machine learning on tabular data is a practical yet understudied area in machine learning. I think studying how Transformers that have been shown effective in NLP and Vision generalize to other modality is an interesting and important direction.\n\n\n3. The experiment and analysis conducted in the paper is thorough. I think the additional analysis in Section 6 provide a deep insight into why and how MetaTree works for generating decision trees.\n\n\n\n\nWeaknesses:  \n1. In Figure 1c, the first stage of the training process is to emulate the GOSDT decision trees while the second stage incorporates the CART trees. Have the authors tried other training curriculum with other decision tree algorithm, e.g., ID3 and C4.5?  \n\n\n2. It seems not clear to me the reason for using a two-stage learning curriculum. What is the benefit of learning from the GOSDT trees in the first stage? I think this paper lacks discussion on this front which might make this part confusing to potential readers.\n\n\n3. The authors mentioned in section 4.3 that the LLaMA architecture is used as the base architecture for MetaTree. However, I am not sure if the architecture designed for language is also fit for other modalities. Given that the dataset used in this paper is smaller compared to the data that LLaMA is trained on, I wonder if the authors have experimented with smaller Transformers. \n\n\n4. I think it would be good to also show how architecture not based on self-attention would work for this task. What about the traditional 1d convolution, other attention formulation [1] or the recent SSM based module, e.g., Mamba [2]?  \n\n[1] Axial Attention in Multidimensional Transformers. Ho et al, 2019.  \n[2] Mamba: Linear-Time Sequence Modeling with Selective State Spaces. Gu et al, 2023.", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "Yes", "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": "", "paper_topic_and_main_contributions": "", "excitement": null, "reproducibility": null, "ethical_concerns": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "summary_of_contributions": "This paper propose a method to learn a Transformer based neural network MetaTree to automatically generate decision trees from a new tabular dataset. The authors develop a two-stage training curriculum to learn a highly capable and generalizable MetaTree Transformers for generating a decision tree. The authors have conducted extensive experimental evaluation to demonstrate the effectiveness of the proposed approach MetaTree.", "claims_and_evidence_yn": "Yes", "claims_explanation": "", "audience_yn": "Yes", "audience_explanation": "", "requested_changes": "I would like to see more discussions on the design of the learning curriculum. It would be better to add some ablation analysis on why the proposed learning curriculum is superior.", "broader_impact_concerns": "I do not have concerns regarding the broader impacts of this paper.", "additional_comments": "", "extra_scores": {}, "extra_text": {}}, {"review_id": "ig69920p3E", "reviewer": "Reviewer_2q7w", "summary": "", "questions": "", "limitations": "", "rating": null, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "### Strengths ###\n- The work is well motivated and the problem is important. Decision trees are in wide practical use today but many scalable methods are heuristic in nature. Meta-learning decision trees seems like a promising alternative approach.\n- The proposed algorithm and experimental setup seems to be sound.\n- Experiments are done on both synthetic and real datasets, and ablations are carried out on certain aspects of the algorithm, such as curriculum and training loss.\n- Experimental results show that MetaTree outperforms both heuristics and optimal methods in terms of generalization accuracy for trees of depth 2 (trees of depth 2 were used for training).\n\n### Weaknesses ###\n- The architecture (section 3.0) is not explained very clearly. It would be helpful to add a figure.\n- No discussion of the computational burden is included in the paper, although it could be one of the main advantages of MetaTree. Appendix A.11 discusses the memory usage of GOSDT and CART; I think it would be helpful to also include MetaTree and computation time.\n- Once the trees get to depth 4, the generalization accuracy of MetaTree is comparable to those of other algorithms. This negatively affects the potential generalizability of the model and makes a more detailed discussion of the computational burden more important.", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "No", "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": "", "paper_topic_and_main_contributions": "", "excitement": null, "reproducibility": null, "ethical_concerns": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "summary_of_contributions": "This paper considers the problem of automatically learning decision trees. It takes a meta-learning approach, learning a Transformer model that, at each step, takes in a dataset and outputs a feature to split and the splitting value. The model is trained using cross entropy after discretizing the features' values, and a curriculum of optimal trees and then optimal trees + CART trees. Experiments are done on synthetic and real datasets, showing that the proposed algorithm MetaTree scales to deeper trees (unlike algorithms that compute the optimal tree) and outperforms heuristics like CART when trees have depth 2.", "claims_and_evidence_yn": "No", "claims_explanation": "", "audience_yn": "Yes", "audience_explanation": "", "requested_changes": "### Critical ###\n- Discussion of computational burden (time, GPUs used, etc.) for all algorithms in the experiments and the trade-offs to be made between MetaTree and the other algorithms. \n\n### Others ###\n- A figure illustrating the model architecture.", "broader_impact_concerns": "No broader impact statement is included, and I think that this is fine since the paper proposes a general approach for learning decision trees and thus does not have direct societal impacts.", "additional_comments": "", "extra_scores": {}, "extra_text": {}}]

Author rebuttal:

Meta-review: Overall the paper appears to have proposed a novel method with solid performance. One strength of this paper in my opinion is that the adaptation of transformers to this problem (meta-learning decision trees) seems to be non-trivial, e.g. in the ways that attention, positional encoding, etc are used.

On the other hand, I agree with the concerns of several reviewers that the presentation of the main algorithm (even after rebuttal) is not ideal and could be further improved. For example, the authors may consider further polishing Section 3.1 & 3.2 to make the description of the main algorithm clearer. The related work (in particular related to ICL and meta-learning) could also be more comprehensive. In my opinion this paper could serve as a first work in the direction of learning decision trees by attention-based architectures, and an adequate literature review could make the paper stand stronger in such a position. For example, the difference with the works in the Section "Some recent works have studied the intersection of trees and Transformers" could be discussed in more detail.

After rebuttal, most reviewers are supportive of the paper. Therefore, I recommend acceptance with minor revision, and encourage the authors to revise the paper according to the reviewers' and the above suggestions.
Decision: Accept (poster)