acceptodds
Under review as a conference paper at ICLR 2027

Optimal all-subsets splits for categorical features in classification tree learning

Abstract

Handling categorical features with many categories adequately in classification trees remains an unsolved problem. Most training algorithms approach a split over a categorical feature via either a one-hot encoding, a label embedding or a multiway split, all of which have significant disadvantages on the resulting tree. The ideal split would choose optimally among all possible category subsets, but this is exponentially costly on the number of categories. We provide a solution to this long-standing problem by 1) using as tree learning not greedy recursive partitioning (as in CART) but tree alternating optimization, and 2) showing that in the latter case the update of a categorical split can be done exactly in time linear on the number of categories. This results in trees that are far smaller (thus more interpretable) and with higher classification accuracy, as demonstrated in our experiments.

Primary area:
other topics in machine learning (i.e., none of the above)
Keywords:
decision trees, supervised learning, categorical features

Reviews

Among:
Shape:
1234this paper, Top 49%
Figure 1. Mean review rating of the reviewed papers at ICLR 2027. This paper averages 2.33 over 3 reviews, above 51% of the others.
Reviewer_tCHCOpenReview ↗
Rating
2
Confidence
3
Informativeness
2
Presentation
2
Soundness
2
Read review
Paper summary

The paper addresses all-subsets splits on unordered categorical features in classification trees, which are exponential in the number of categories under greedy multiclass optimization. Working in Tree Alternating Optimization (TAO), which iteratively re-optimizes the nodes of a given initial tree (here a fully grown one-hot CART tree), the authors note that with the child subtrees fixed, the reduced problem at a decision node is a sum of per-instance losses. Over a lookup table mapping categories to children, this sum separates over categories, so each category is sent to the child with the smaller summed loss (Sec. 5, Eqs. 3–4, Fig. 6 right). The update is claimed to be exact, linear-time, valid for any loss and for binary or multiway nodes, and previously unknown (l.45).

The validation covers 14 datasets comparing against XGBoost, CatBoost, GUIDE, C5.0, CART (scikit-learn one-hot and R rpart) and equality-test TAO. They report:

  • the lowest test error on 13/14 datasets;
  • substantially smaller trees;
  • no high-cardinality selection bias;
  • improved interpretability.

The appendix compares three strategies (Full/Left/Random) for categories that are absent from, or tied at, a node.

Critical strengths
  1. A correct, simple and practical exact node update. I re-derived Eqs. 3–4. No term couples different categories, so the per-category argmin is the global optimum of the node problem. Implemented with per-category accumulation, it costs Θ(N_i + C_d) once the child losses are known. It is also cheap in practice (6.18 s vs. 4.26 s for equality-test TAO on CFEC2, Table 3). This appropriately removes the main practical obstacle to native high-cardinality categorical splits in non-greedy trees.

  2. Mostly smaller trees than equality-test TAO. Tables 1–2 show large reductions in leaf count. This result largely survives fixing the missing-category variant in advance. With Random fixed (Tables 4–5), the tree is smaller than equality-test TAO on 11/14 datasets; it is larger on SF Crime (877 vs. 601) and Chess KRK (2,832 vs. 2,221) and ties on Car. One caveat: sizes are compared at each method's own selected operating point, not at matched accuracy, and only Fig. 5 (Electricity) shows a size–error trade-off. For an interpretability-motivated method, this is the most robust evidence in the paper.

Critical weaknesses
  1. As reported, the results do not allow assessing the accuracy claim (13/14 best).

    • Variant choice. Each "all-subsets TAO" entry in Tables 1–2 equals the lowest test error among the Full/Left/Random variants in Tables 4–5, on all 14 datasets. The paper does not say how the variant was chosen.
    • Fixed variant. With the variant fixed to Random (the rule described in l.322–324), the method is best on 9/14 datasets, showing that the paper may be overclaiming their method's accuracy.
    • Protocol. The data-splitting and validation protocol is not described.
    • Variance. Results come from a single split with no variance estimates, while several highlighted gaps amount to a few test instances.
    • Baselines. Some baseline and dataset results are close to majority-class error (details in Q4–Q5).

    This weakness carries most of my rating. A validation-only selection protocol, fixed-variant results with variance, and explanations of the outlying baselines could change my assessment substantially.

  2. The contribution's novelty is framed more strongly than I think the prior TAO theory allows, and the added split capacity is not controlled.

    • Prior theory. Carreira-Perpiñán & Tavallali (NeurIPS 2018, Thm. 3.2) already reduce a TAO decision node to a binary 0/1 classification on pseudolabels. A lookup table over one feature is a perfectly flexible classifier for that problem, so Eq. 4 appears to follow directly. This sits uneasily with "this fact was not known" (l.45) and "a complete solution" (l.479). This seems like another overclaim, and the paper should clarify what is new beyond the prior theorem.
    • Capacity. An all-subsets node adds up to C_d − 1 free routing bits but pays the same delta penalty λ as a single threshold.
    • Selection bias. The claim that no selection bias occurs (l.128–131) is not tested by any experiment.

    This matters because, with a short algorithmic core, the paper's value rests on its empirical case and on accurate positioning. I would like the authors' view (Q6–Q7) before weighing it.

Questions for authors
  1. [Clarification] Data protocol.

    • How were train/validation/test sets formed? The test sets appear to be the remaining 20%: Car's 1.16% and 2.31% correspond exactly to 4/346 and 8/346 errors, and Contraceptive's 38.64% to 114/295.
    • Where did the validation set used to select λ (l.604–605) come from? The Fig. 2 leaf counts sum to 31,250, the full training size in Table 1.
    • Why do the Table 1–2 sizes equal 80% of the Table 3 sizes for most datasets, but 85% for Bank, 90% for Electricity, and 100% for Chess KRK, Jungle Chess, SF Crime and BeijingAqi?
  2. [Clarification] Choice of the missing-category variant. Was the Full/Left/Random variant chosen per dataset on validation data or on test data? Each entry in Tables 1–2 matches the lowest of the three test errors (e.g. Electricity 11.79/11.56/10.63 → 10.63; Chess KRK 65.88/20.46/21.58 → 20.46; Car 2.60/2.60/1.16 → 1.16).

    • If the choice used validation data, please report which variant was selected per dataset.
    • Otherwise, please report results with one variant fixed in advance, as mean ± std over several splits or seeds, with paired tests against the best baseline. From the current tables, Random alone loses on HBD (14.01 vs. 13.96), CFEC2 (19.21 vs. 18.63), BeijingAqi (24.05 vs. 23.59), SF Crime (72.38 vs. 72.26) and Chess KRK (21.58 vs. 20.56). How would you restate the accuracy claim in that case?
  3. [Clarification] Tie handling: text vs. pseudocode.

    • The text says missing or tied categories go to a random child (l.322–323). Fig. 6 (right), read sequentially, initializes S_min = ∞ and updates only on a strict "<". So a missing category (S = 0 for both children) and any tie always go to the first child, i.e. the "Left" rule. Which rule does the implementation use?
    • How are categories routed at inference when they never appeared in a node's reduced set, or in training at all?
  4. [Clarification] Baseline configurations. Please give the exact single-tree settings for CatBoost (iterations, learning rate) and XGBoost (number of rounds, max_cat_to_onehot, objective), and explain three outlying results:

    • CatBoost on Chess KRK: 73.91% test error and 75.53% training error with 35 leaves. Always predicting the largest UCI class ("fourteen", 4,553 of 28,056) gives ≈83.8%, while CART reaches 21.40%.
    • CatBoost on Car: 20.52% test error and 21.06% training error with 114 leaves, whereas CART fits the training set perfectly with 101 leaves.
    • XGBoost on HBD: 35.99% test error with 12.67% training error, while all other methods reach 13.8–15.6%.

    Also:

    • How are leaves counted for multiclass XGBoost, where each round builds K trees?
    • Why use a custom GUIDE reimplementation rather than Loh's released program? GUIDE's selected depth is exactly 5 on six datasets and 18 on six others, which looks like the edges of the search grid.
    • Appendix A.1 sets use_categorical for C5.0. The R C50 package has no such argument, and C5.0Control(subset = TRUE), the default, evaluates groups of category values. Which setting was used, and does it change C5.0's place in your taxonomy?
  5. [Clarification] Datasets.

    • Please report the majority-class error for every dataset.
    • Please identify HBD and CFEC2. If HBD is Hotel Booking Demand (37% cancellations), the XGBoost result above is near the trivial level. If CFEC2 is Kaggle's Categorical Feature Encoding Challenge II (positive rate ≈18.7% in its training file), the best CFEC2 results (18.59/18.63/18.77) would be close to always predicting the majority class. Is that the case on your 298,042-row subset?
    • Adult is listed with K = 4 classes. What is the target?
  6. [Clarification] Relation to the TAO reduced-problem theorem. Do you agree that Eq. 4 follows from NeurIPS 2018 Thm. 3.2 (and its weighted-loss, multiway generalization) applied to a lookup-table decision function? If not, what does the paper add beyond it? This should be discussed accordingly with previous work:

    • Burshtein et al. (Ann. Statist. 1992), Chou (IEEE TPAMI 1991), Coppersmith, Hong & Hosking (DMKD 1999), and Laber, Molinaro & Mello Pereira (ICML 2018);
    • TAO with an oblique node restricted to the one-hot block of one categorical feature. This node already represents a category-to-weight table, so it can express any subset split, fitted approximately. A comparison would show whether the gains come from exactness or from expressiveness.
  7. [Clarification] Capacity and selection bias. What evidence supports "we find no such bias in our experiments" (l.128–131)? The categorical-node proportion jumps from 0.12 (Full) to 0.72–0.73 (Left/Random) on HBD, and from 0.04 to 0.36–0.39 on SF Crime (Table 4). Please either support the claim with a controlled experiment or remove it. One option: add pure-noise categorical features with C ∈ {10, 100, 1000} and report how often they are selected and how test error changes, compared with GUIDE. Should the delta penalty scale with the number of categories a node uses?

  8. [Clarification] Runtime and initialization.

    • Do the TAO times in Table 3 include building the initial, fully grown one-hot scikit-learn CART tree (l.602–603) and the whole λ path? One-hot CART takes 705.91 s on CFEC2, so the pipeline still appears to depend on one-hot encoding.
    • TAO and categorical TAO have identical times on Contraceptive (0.52 s) and Car (1.18 s); is this correct?
    • The complexity is stated as linear in the number of categories (abstract), in the sample size (l.43–44), Θ(N) (l.279) and Θ(2N_i) (l.311). Which is intended? Fig. 6 read literally is Θ(C_d·N_i).
  9. [Clarification] Tree size at matched accuracy. The size comparisons in Tables 1–2 use each method's own selected tree, so a smaller tree may simply be a more regularized one. Could you report test error vs. number of leaves along the λ path for all-subsets TAO and equality-test TAO on all datasets, as Fig. 5 does for Electricity? In particular, how many leaves does each need to reach the same test error?

Smaller clarifications (lower priority)

  1. [Clarification] Definition of l_{i,n}. Eq. 2 defines it as the 0/1 loss against a pseudolabel, with no care set. Sec. 5 uses each child's actual loss. Which is implemented? Under Eq. 2, instances whose loss is the same in both children incur a spurious cost, and the monotone decrease claimed at l.247–248 may not hold.

  2. [Clarification] Stopping criterion. Training stops when the change in training error falls below 10⁻⁵ (l.605), whereas Fig. 6 stops when E(Θ) stops decreasing. Under the delta penalty these differ. Which is used?

  3. [Clarification] Internal inconsistencies in Tables 4–5. In a binary tree the number of decision nodes is the number of leaves minus 1, but:

    • Car (Full): 10 categorical nodes, 45 leaves (44 decision nodes), proportion 1.00;
    • Contraceptive (Left/Random): 1 categorical node, 13 leaves, proportion 0.40;
    • Bank (all-subsets CART): 41 categorical nodes, 86 leaves, proportion 0.16;
    • Jungle Chess (equality-test TAO): 807 categorical nodes but only 708 leaves.

    Is the proportion defined differently from the caption, or are these typos?

  4. [Clarification] Appendix B baseline. It is called a "baseline identity split" (l.676) but "no cat" or "without proposed categorical decision nodes" in Figs. 3 and 5, and its ≈13% error differs from equality-test TAO's 11.85% in Table 5. What exactly is it? What does "OvO" mean in the Fig. 4 caption?

  5. [Clarification] Choice of comparators in Sec. 6.1. Why compare Election against GUIDE (19.74%, 785 leaves) rather than the best baseline, C5.0 (19.00%, 133 leaves)? Why compare Contraceptive against R CART (44.07%, 85 leaves) rather than GUIDE (40.34%, 21 leaves)?

  6. [Clarification] Interpretability comparison. The Fig. 8–9 trees (depth 12 with 54 and 64 leaves) differ from the Election entries in Table 1 (10/70 and 9/65). How were they selected, and what are their test errors relative to Fig. 2?

Suggestions for future work (not needed for my assessment)

  • A synthetic sweep over C at fixed N to show runtime scaling directly.
  • Interpretability measures beyond leaf count (e.g. rule length, size of the category sets per node) across datasets rather than a single tree.
  • An experiment with multiway nodes, which the paper claims are supported (l.120–121, l.483) but does not test.
2 comments

We thank the reviewer for the detailed assessment. We address the main concerns and clarify the technical details below.

  1. Experimental protocol, variant selection and variance

We used 5-fold cross-validation for hyperparameter selection. After selecting the optimal hyperparameters using the validation set, we performed a separate 80/20 train/test split for the final evaluation. All reported results are averaged over five independent runs. The corresponding standard deviations are provided in our response to Reviewer VjRW and below.

We thank the reviewer for noticing the inconsistencies in dataset sizes across Tables 1–3. These are reporting errors in the dataset-size annotations, not differences in the experimental protocol. The actual data splitting procedure follows the protocol described above. We will correct the table annotations and explicitly document the complete evaluation protocol in the revised manuscript.

Q2) Full/Left/Random differ in absent/tied-category handling (Appendix B). We present the fixed selection based on validation error in the main paper.

Q3) Sec. 5 describes random tie-breaking, while Fig. 6's strict comparison implies first-child selection. We will align the pseudocode with the implementation and specify routing for categories absent from a node or unseen during training.

Q4) Both methods optimize local splitting criteria greedily and are primarily designed for boosting. Restricting them to one round can reduce accuracy. Our custom GUIDE implementation and R C5.0 wrapper enable split-type/count extraction and uniform tuning/reporting.

Q6) Yes, Eq. 4 follows from the prior TAO reduced-problem theorem applied to a categorical lookup table. Our contribution is the exact O(N_i+C_d) all-subsets update: independently minimizing aggregate downstream loss for each category. Unlike one-hot equality tests, it optimizes every partition; unlike approximate one-hot oblique fits, it exactly solves the node subproblem. This enables native high-cardinality multiclass splits.

Q8) With child losses fixed, aggregation costs O(N_i); dense table initialization/output costs O(C_d), yielding O(N_i+C_d) time and O(C_d) space.

Q9) Appendix Fig. 5 already plots error versus node count on Electricity for the three variants and a baseline without the proposed categorical nodes.

Q10) The node update uses the actual loss for each child, not an unweighted 0/1 pseudolabel loss. Instances with equal child losses are indifferent

Q11) Fig. 6 states theoretical objective-based stopping; the implementation caps iterations at 30 and uses a 10⁻⁵ training-error tolerance.

Q15) Fig. 2 is a more regularized illustration (~19% test error; depth 6, 12 leaves). Figs. 8–9 show similar-error equality-test trees (depth 12, 54 and 64 leaves), rather than the Table 1 configurations. We will provide their exact errors and selection criteria.

  1. Addressing critical weakness 1:

In the paper we average the results over 5 runs. Here we include error bars and tree size variation

Dataset (N,D,K)XGBoostCatBoostGUIDEC5.0CART-ETAO-ECART-ATAO-A
Medium/high cardinality
Election 2016 (31250,14,2)19.09±0.63 [9±0.8/77±8.6]19.21±0.45 [15±1.4/623±83]19.74±0.48 [19±2.9/785±156]19.00±0.52 [11±1.9/133±37]19.31±0.61 [9±1.4/65±11]19.21±0.53 [10±1.3/70±16]19.49±0.69 [15±2.4/135±33]18.47±0.57 [10±1.2/43±8.0]
Adult (36177,14,4)45.96±0.69 [9±1.1/33±4.9]44.27±0.50 [12±1.5/378±38]45.11±0.58 [5±1.0/32±4.9]43.05±0.69 [11±1.7/22±4.7]43.25±0.55 [19±1.9/118±19]43.24±0.66 [18±2.2/78±12]–42.83±0.52 [8±0.8/12±1.9]
Albert (52426,31,2)35.77±0.56 [12±1.2/112±17]34.62±0.52 [8±1.2/201±27]34.31±0.56 [5±1.5/31±4.2]34.16±0.51 [18±1.9/969±188]34.55±0.56 [10±1.5/87±26]33.75±0.40 [10±1.1/40±8.1]33.76±0.45 [15±2.3/118±31]33.53±0.38 [7±1.0/21±3.7]
HBD (95508,27,2)35.99±0.43 [20±1.4/387±37]14.96±0.30 [16±2.0/2536±289]15.62±0.31 [18±2.2/2802±639]14.08±0.34 [20±2.3/677±100]14.09±0.30 [48±5.4/3022±740]13.96±0.28 [44±3.6/2282±553]14.77±0.24 [26±2.9/974±155]13.80±0.21 [30±1.8/540±92]
CFEC2 (238436,23,2)24.04±0.25 [25±1.9/1375±204]18.63±0.21 [12±0.9/31±4.1]18.77±0.20 [5±1.3/32±8.2]19.88±0.18 [8±2.2/5296±736]19.79±0.16 [10±1.8/86±18]19.55±0.22 [10±1.5/76±17]24.04±0.26 [10±1.8/115±24]18.59±0.15 [8±1.2/18±2.8]
BeijingAqi (200000,16,6)23.59±0.25 [22±1.8/1535±242]25.70±0.22 [13±2.0/6063±1133]23.95±0.27 [18±2.6/6850±1048]24.33±0.23 [19±2.5/1802±204]24.78±0.26 [21±2.6/1262±336]24.37±0.22 [18±1.5/1215±431]–23.91±0.20 [18±1.4/1149±212]
SF Crime Class. (181931,8,20)73.56±0.31 [26±2.1/1123±214]73.16±0.22 [13±1.6/1990±219]73.75±0.25 [18±3.1/4270±1056]74.77±0.32 [24±3.8/29273±3294]72.49±0.31 [22±2.9/699±191]72.26±0.24 [19±1.7/601±140]–72.15±0.24 [23±2.0/547±93]
Low cardinality
Contraceptive (1178,9,3)47.12±2.93 [3±0.7/4±0.7]47.80±2.70 [8±1.3/26±4.4]40.34±3.90 [5±1.4/21±4.4]44.75±3.25 [10±1.9/40±6.4]45.76±3.60 [14±1.6/118±23]41.02±2.88 [11±1.2/63±12]44.07±3.71 [15±1.7/85±19]38.64±2.81 [4±0.6/7±1.2]
Car eval. (1382,6,4)2.89±0.99 [9±1.1/27±4.3]20.52±2.86 [16±1.2/114±17]4.62±1.37 [11±1.8/39±6.0]6.94±1.58 [6±1.4/76±9.2]3.18±1.30 [14±1.7/101±32]2.89±1.13 [12±1.1/60±6.8]2.31±1.11 [10±1.7/50±15]1.16±0.62 [12±1.5/60±7.3]
Telco (5625,19,2)21.46±1.52 [6±0.6/15±3.0]22.25±1.23 [12±1.6/218±41]20.26±1.50 [5±1.2/32±6.2]19.83±1.62 [10±1.7/51±8.2]20.82±1.21 [11±1.8/63±11]20.75±1.34 [9±1.0/30±5.8]20.04±1.65 [16±1.7/90±27]18.91±0.96 [8±1.1/17±1.8]
Electricity (34626,8,2)12.84±0.35 [22±2.2/1257±138]17.10±0.46 [16±1.6/3329±488]12.86±0.39 [18±2.9/1569±288]10.65±0.40 [28±2.3/1471±287]12.40±0.34 [27±3.6/1466±480]11.85±0.39 [28±2.4/1841±396]12.34±0.40 [25±3.1/935±143]10.63±0.32 [25±2.4/688±90]
Bank Marketing (38429,16,2)9.67±0.39 [15±1.5/89±19]9.48±0.40 [12±1.2/239±56]9.38±0.39 [5±1.2/31±7.5]9.22±0.42 [11±1.5/139±36]9.19±0.41 [17±2.0/164±40]9.20±0.33 [10±0.9/44±7.2]9.10±0.37 [14±2.0/86±22]8.51±0.25 [9±1.1/20±4.4]
Chess KRK (28056,6,18)28.69±0.53 [15±1.4/386±40]73.91±0.91 [10±1.1/35±5.9]35.92±0.92 [18±2.3/1610±244]38.58±0.75 [6±1.8/3027±794]21.40±0.52 [28±2.6/4408±1276]27.23±0.51 [19±1.8/2221±830]20.56±0.50 [21±3.3/5672±1578]20.46±0.22 [28±2.7/1947±243]
Jungle Chess (44819,6,3)13.26±0.32 [16±2.7/733±225]16.21±0.49 [13±1.9/3170±537]16.73±0.48 [18±2.6/1256±207]17.22±0.45 [6±1.2/1043±151]14.44±0.45 [27±2.9/1089±361]15.10±0.34 [17±1.4/708±131]13.49±0.40 [19±2.4/738±216]10.17±0.24 [19±1.4/513±46]
Reviewer_VjRWOpenReview ↗
Rating
3(+1)
Confidence
2
Informativeness
3
Presentation
2
Soundness
2
Read review
Paper summary

This paper proposes a method for handling categorical features in decision trees using Tree Alternating Optimization (TAO). The authors show that by keeping the rest of the tree fixed, the optimal split for a categorical feature can be found by considering each category separately. This avoids the exponential search normally associated with finding the best partition of categorical values. The method is evaluated on 14 datasets against several existing decision-tree algorithms, including CART, C5.0, GUIDE, XGBoost, and CatBoost. The results show that the proposed approach generally produces smaller trees with lower classification error.

Critical strengths
  1. The main strength is the ability to find an optimal categorical split without searching through every possible partition. The derivation is straightforward and appears sound. This is a useful contribution, particularly for features with many categories.
  2. The experimental results are promising across a variety of datasets. The comparison between equality-test TAO and the proposed all-subsets TAO is particularly useful because it helps demonstrate the benefit of the new splitting method.
Critical weaknesses
  1. The results are presented without standard deviations or confidence intervals. Some reported improvements are relatively small, making it difficult to determine how consistent these gains would be across different runs or data splits. This weakens the experimental evidence supporting the method’s superiority.
  2. The paper frequently associates smaller trees with greater interpretability. While smaller trees are generally easier to inspect, categorical splits containing many values may still be difficult to understand. The results clearly support improvements in tree size, but the interpretability claims would benefit from a more careful discussion.
Questions for authors
  1. Were the experiments repeated using different randoms seeds or training/test splits? If so, could the authors provide standard deviations or confidence intervals for the reported results?
  2. Could the authors clarify the linear-time complexity claim, particularly whether the cost of initializing and storing assignments for all possible categories is included?
  3. How is the regularization penalty handled when a categorical split assigns all categories to the same child? Is this treated as an inactive decision node?

It is also important to point out how much work the grammar of the paper needs. I listed some as examples:

-Every mentioned of "time linear" should be changed to "linear time" -Page 1, line 19: "using as tree learning not greedy recursive partitioning" should be "using tree alternating optimization rather than greedy recursive partitioning" -Page 2, Line 75: "and the one with pursue in this paper" should be "and the one we pursue in this paper" -Page 5, line 225: "for each node that uses a featureInstead" (missing punctuation and spacing) -Page 5, line 227: "simplies into a certain reduced problem" should be "simplifies to a reduced problem" -Page 5, line 243: "categoriesIn section 5" (missing punctuation) -Page 7, line 355: "due to the fact that size of the dataset blows up" should be "because the size of the dataset increases substantially" -Page 7, line 357: "due to brute force method of split optimization" should be "due to the brute-force split optimization" -Page 8, line 425: "this list prioritizes the isolation" appears to use "list" where another term was intended, perhaps "split"?

These are only some corrections that stood out to me. There are more in the appendices.

3 comments
  1. Weakness 1 "No standard deviation ..."

In the paper we average the results over 5 runs. Here we include error bars and tree size variation

Dataset (N,D,K)XGBoostCatBoostGUIDEC5.0CART-ETAO-ECART-ATAO-A
Medium/high cardinality
Election 2016 (31250,14,2)19.09±0.63 [9±0.8/77±8.6]19.21±0.45 [15±1.4/623±83]19.74±0.48 [19±2.9/785±156]19.00±0.52 [11±1.9/133±37]19.31±0.61 [9±1.4/65±11]19.21±0.53 [10±1.3/70±16]19.49±0.69 [15±2.4/135±33]18.47±0.57 [10±1.2/43±8.0]
Adult (36177,14,4)45.96±0.69 [9±1.1/33±4.9]44.27±0.50 [12±1.5/378±38]45.11±0.58 [5±1.0/32±4.9]43.05±0.69 [11±1.7/22±4.7]43.25±0.55 [19±1.9/118±19]43.24±0.66 [18±2.2/78±12]–42.83±0.52 [8±0.8/12±1.9]
Albert (52426,31,2)35.77±0.56 [12±1.2/112±17]34.62±0.52 [8±1.2/201±27]34.31±0.56 [5±1.5/31±4.2]34.16±0.51 [18±1.9/969±188]34.55±0.56 [10±1.5/87±26]33.75±0.40 [10±1.1/40±8.1]33.76±0.45 [15±2.3/118±31]33.53±0.38 [7±1.0/21±3.7]
HBD (95508,27,2)35.99±0.43 [20±1.4/387±37]14.96±0.30 [16±2.0/2536±289]15.62±0.31 [18±2.2/2802±639]14.08±0.34 [20±2.3/677±100]14.09±0.30 [48±5.4/3022±740]13.96±0.28 [44±3.6/2282±553]14.77±0.24 [26±2.9/974±155]13.80±0.21 [30±1.8/540±92]
CFEC2 (238436,23,2)24.04±0.25 [25±1.9/1375±204]18.63±0.21 [12±0.9/31±4.1]18.77±0.20 [5±1.3/32±8.2]19.88±0.18 [8±2.2/5296±736]19.79±0.16 [10±1.8/86±18]19.55±0.22 [10±1.5/76±17]24.04±0.26 [10±1.8/115±24]18.59±0.15 [8±1.2/18±2.8]
BeijingAqi (200000,16,6)23.59±0.25 [22±1.8/1535±242]25.70±0.22 [13±2.0/6063±1133]23.95±0.27 [18±2.6/6850±1048]24.33±0.23 [19±2.5/1802±204]24.78±0.26 [21±2.6/1262±336]24.37±0.22 [18±1.5/1215±431]–23.91±0.20 [18±1.4/1149±212]
SF Crime Class. (181931,8,20)73.56±0.31 [26±2.1/1123±214]73.16±0.22 [13±1.6/1990±219]73.75±0.25 [18±3.1/4270±1056]74.77±0.32 [24±3.8/29273±3294]72.49±0.31 [22±2.9/699±191]72.26±0.24 [19±1.7/601±140]–72.15±0.24 [23±2.0/547±93]
Low cardinality
Contraceptive (1178,9,3)47.12±2.93 [3±0.7/4±0.7]47.80±2.70 [8±1.3/26±4.4]40.34±3.90 [5±1.4/21±4.4]44.75±3.25 [10±1.9/40±6.4]45.76±3.60 [14±1.6/118±23]41.02±2.88 [11±1.2/63±12]44.07±3.71 [15±1.7/85±19]38.64±2.81 [4±0.6/7±1.2]
Car eval. (1382,6,4)2.89±0.99 [9±1.1/27±4.3]20.52±2.86 [16±1.2/114±17]4.62±1.37 [11±1.8/39±6.0]6.94±1.58 [6±1.4/76±9.2]3.18±1.30 [14±1.7/101±32]2.89±1.13 [12±1.1/60±6.8]2.31±1.11 [10±1.7/50±15]1.16±0.62 [12±1.5/60±7.3]
Telco (5625,19,2)21.46±1.52 [6±0.6/15±3.0]22.25±1.23 [12±1.6/218±41]20.26±1.50 [5±1.2/32±6.2]19.83±1.62 [10±1.7/51±8.2]20.82±1.21 [11±1.8/63±11]20.75±1.34 [9±1.0/30±5.8]20.04±1.65 [16±1.7/90±27]18.91±0.96 [8±1.1/17±1.8]
Electricity (34626,8,2)12.84±0.35 [22±2.2/1257±138]17.10±0.46 [16±1.6/3329±488]12.86±0.39 [18±2.9/1569±288]10.65±0.40 [28±2.3/1471±287]12.40±0.34 [27±3.6/1466±480]11.85±0.39 [28±2.4/1841±396]12.34±0.40 [25±3.1/935±143]10.63±0.32 [25±2.4/688±90]
Bank Marketing (38429,16,2)9.67±0.39 [15±1.5/89±19]9.48±0.40 [12±1.2/239±56]9.38±0.39 [5±1.2/31±7.5]9.22±0.42 [11±1.5/139±36]9.19±0.41 [17±2.0/164±40]9.20±0.33 [10±0.9/44±7.2]9.10±0.37 [14±2.0/86±22]8.51±0.25 [9±1.1/20±4.4]
Chess KRK (28056,6,18)28.69±0.53 [15±1.4/386±40]73.91±0.91 [10±1.1/35±5.9]35.92±0.92 [18±2.3/1610±244]38.58±0.75 [6±1.8/3027±794]21.40±0.52 [28±2.6/4408±1276]27.23±0.51 [19±1.8/2221±830]20.56±0.50 [21±3.3/5672±1578]20.46±0.22 [28±2.7/1947±243]
Jungle Chess (44819,6,3)13.26±0.32 [16±2.7/733±225]16.21±0.49 [13±1.9/3170±537]16.73±0.48 [18±2.6/1256±207]17.22±0.45 [6±1.2/1043±151]14.44±0.45 [27±2.9/1089±361]15.10±0.34 [17±1.4/708±131]13.49±0.40 [19±2.4/738±216]10.17±0.24 [19±1.4/513±46]

We thank the reviewer for identifying these issues and apologize for the grammatical and typographical errors.

  1. Weakness 2 "The paper frequently associates

Our method improves structural compactness, measured by the number of leaves and tree depth. A single all-subsets node can replace a sequence of equality-test nodes, reducing the number of decisions required to express the same categorical partition.

For example, Figure 2 shows an all-subsets tree with 12 leaves and depth 6, compared with equality-test TAO and CART trees having 54 and 64 leaves, respectively, both with depth 12, at similar test error (Appendix Figs. 8–9).

Moreover, all-subsets nodes explicitly represent groups of categories. In Figure 2, the learned state partition can be visualized geographically, making the grouping easier to inspect than a sequence of individual equality tests.

We acknowledge that high-cardinality category groups may themselves be difficult to interpret. We will distinguish structural compactness from human interpretability and moderate claims that leaf count alone establishes interpretability.

  1. Q2 "Could the authors clarify the linear-time complexity ..."

For a categorical feature with (C_d) categories and (N_i) instances reaching node (i), the algorithm accumulates the loss associated with each child for each category. With the downstream losses already computed and a fixed number of children accumulating category-wise losses requires O((N_i)) time, initializing the category table and selecting assignments requires O((C_d)) time. Therefore, the total complexity is O((N_i+C_d)) time and O((C_d)) auxiliary memory.

Thus, the key result is that optimization is linear in the input representation size rather than exponential in categorical cardinality. We will explicitly state the initialization and storage costs and clarify the complexity claim in Section 5.

  1. Q3 "How is the regularization penalty handled ..."

Equation (2) explicitly includes a "no-feature" option, which sends all instances to one child and incurs zero regularization penalty.

If a categorical split sends every category to the same child, it is functionally equivalent to this inactive-node option. More generally, when all instances reaching a node are routed to the same child, the no-feature option achieves the same training loss without paying the activation penalty (\lambda). Hence, for (\lambda>0), the inactive option is preferred over such a redundant categorical split.

This is consistent with TAO's pruning mechanism: inactive nodes and their redundant subtrees can be removed. We will clarify the treatment of constant categorical mappings, including tie cases and unobserved categories, in the algorithm description.

Thank you for addressing my questions, providing the results with standard deviations, and clarifying the other points. Based on your responses, I have increased my score. However, I still have concerns about the amount of grammatical editing the paper requires.

Reviewer_yUeqOpenReview ↗
Rating
2
Confidence
2
Informativeness
1
Presentation
2
Soundness
2
Read review
Paper summary

The paper aims to deal with categorical features that contain many categories for classification tasks. One apparently may not feel satisfied with those traditional methods such as using one-hot encoding, label embedding or multiway split for the categorical-feature representation. The classification trees are the focused model in this study. The node splitting is based on a trade-off between the label prediction error and the maximum margin criterion for the considered categorical features.

Critical strengths

The paper has a clear goal and the experiment results more or less support the proposed method.

Critical weaknesses

The proposed mechanism is considered straightforward and lack enough novelty. Moreover, one must convince others that the tree-based methods are still competitive, such as sacrificing a little performance but gaining transparency over other black-box models.

Questions for authors

• How to interpret the comparison to other methods in terms of test error and tree size? We prefer a small tree with low test error. How to explain the benefit of having a TAO-generated tree to another tree when both producing similar performance but the TAO tree is a bit bigger (also with more leaves) than the other tree? For instance, C5.0 and TAO have similar test error on the Adult dataset but the C5.0 tree is much smaller. Should we decide a good set of parameters such that TAO and other compared method can produce two trees with similar size and we can focus on the test performance comparison?

• How to choose the datasets for the experiments in this study? What could be the criteria?

• What is the detail setting of C5.0 modeling in this study? I wonder C5.0 instead of C4.5 was used but no boosting was chosen for C5.0, any reasons for the choice?

• Moreover, should we discuss the effect of boosting separately since the mechanism of tree generation and performance are done quite differently?

• While categorical features could have certain ordering information included, should we separate the categorical features into different kinds or simply focus on only the categorical features without clear ordering information? For instance, grades A, B, C may not be appropriate to be considered as categorical and be included in this study. The label embedding method could be the main focused compared candidate in this case.

• When given both categorical features and numerical features, should we need to worry about the balance between choosing the features fairly from the both when generating the TAO tree?

• The TAO tree shown in Figure 2 looks a bit skew (most nodes have only one branch with continuous splitting), any reasons? Is it a defect for the proposed method?

• While providing clear transparency from tree modeling is interesting, one may also like to see what could be the performance from deep learning methods, at least for some baseline or comparison.

2 comments

We thank the reviewer for the review.

  1. Addressing critical weaknesses:

Our main contribution is an exact, linear-time algorithm for optimizing all-subsets categorical splits within TAO, not simply a new splitting heuristic. For a categorical feature with CC categories, the search space contains exponentially many partitions. Our key result (Sec. 5, Eq. 3–4) shows that, because TAO fixes the downstream subtrees during node optimization, the objective decomposes independently across categories. Thus, the globally optimal categorical partition for the node subproblem can be computed without enumerating subsets, in time linear in the node's data size.

This result applies to multiclass classification, arbitrary losses, and binary or multiway splits. Unlike classical greedy tree learning, our approach provides the downstream losses needed for this decomposition. The contribution is recognizing and proving this exact optimization property for an otherwise combinatorial problem.

We also clarify that our objective is classification loss plus a sparsity penalty on active decision nodes (Eq. 1), not a maximum-margin criterion, as suggested in the review summary.

Our goal is not to outperform every black-box model, but to obtain accurate, compact, directly interpretable single trees. Our method achieves the lowest test error on 13/14 datasets. More importantly, compared with equality-test TAO, it improves both test error and leaf count on all seven medium/high-cardinality datasets (Table 1), isolating the benefit of the proposed categorical optimization.

  1. Q1 "How to interpret the comparison ..."

We agree that both should be considered. However, we would like to clarify the Adult example:

  • C5.0: 43.05% test error, 22 leaves, depth 11.
  • Proposed all-subsets TAO: 42.83% test error, 12 leaves, depth 8.
  • Equality-test TAO: 43.24% test error, 78 leaves, depth 18.

Thus, our proposed method is both smaller and more accurate than C5.0 on Adult. Additionally, on CFEC2, our method reduces test error from 19.55% to 18.59% while reducing leaves from 76 to 18 compared with equality-test TAO.

We agree that size-matched comparisons and error-versus-leaf-count curves are useful complementary evaluations. Our regularization path already allows examining this trade-off (Appendix Figs. 3 and 5).

  1. Q2 "How to choose the datasets ..."

We evaluate 14 datasets: four categorical-only and ten mixed, binary/multiclass classification, different sample sizes, and categorical cardinalities ranging from low to 2,217. Low-cardinality datasets are good for comparison with other tree based models (as most of them struggle with high cardinality one). The high-cardinality datasets are highly practical (as real world dataset often include many categories like ZIP codes, etc.) and directly test the computational and representational challenges motivating our method. Mixed datasets test categorical and numerical features jointly.

  1. Q3–Q4 about C5.0 configuration and boosting

We use the R implementation of C5.0, tune its pruning confidence factor (CF) using validation data, and set trials = 1 to obtain a single tree. C5.0 was chosen as a practical successor to C4.5 with native categorical-feature support.

We deliberately evaluate single-tree configurations of C5.0, XGBoost, and CatBoost to maintain apple-to-apple comparison. Boosting creates ensembles with substantially different model complexity and lack of interpretability. We agree that full boosting results would be useful as a separate predictive-performance reference, rather than a directly size-comparable baseline.

  1. Q5 "While categorical features could ..."

We already distinguish these cases in Sec. 4. Our method targets unordered (nominal) categorical features. Ordered features are usually split using thresholds between consecutive values. Our approach avoids imposing artificial ordering on nominal features and searches the complete category-partition space, unlike fixed label embeddings.

  1. Q6 "When given both categorical features and numerical features ..."

Both feature types are evaluated using the same TAO reduced objective, and the candidate minimizing the loss is selected. Thus, there is no explicit preference for either feature type in the objective. Regularization and validation-based model selection mitigate overfitting.

  1. Q7 " The TAO tree shown in Figure 2 looks a bit skew ..."

The asymmetry is not a defect. TAO does not enforce balanced trees; it minimizes classification loss while penalizing active nodes. Consequently, easy-to-classify subsets can terminate early, while harder subsets require further splitting.

Figure 2 intentionally shows a more regularized tree for interpretability. At approximately 19% test error, our tree has 12 leaves and depth 6, compared with 54 leaves/depth 12 for equality-test TAO and 64 leaves/depth 12 for CART at similar error (Appendix Figs. 8–9). Thus, despite its asymmetric appearance, our tree is substantially more compact and shallower.

  1. Q8 about deep learning comparisons

We agree that neural-network baselines could provide additional predictive-performance context. However, our primary research question concerns the accuracy and compactness of directly interpretable single decision trees, not unrestricted black-box prediction.

From OpenReview, CC BY 4.0. Authors as signed there; shown unedited.

Related papers

Loading the map…

Discussion (0)

Sign in to comment.