- 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
-
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.
-
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
-
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.
-
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
-
[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?
-
[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?
-
[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?
-
[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_categoricalfor C5.0. The RC50package has no such argument, andC5.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?
-
[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?
-
[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.
-
[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?
-
[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).
-
[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)
-
[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.
-
[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?
-
[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?
-
[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?
-
[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)?
-
[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
- 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) | XGBoost | CatBoost | GUIDE | C5.0 | CART-E | TAO-E | CART-A | TAO-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 the detailed assessment. We address the main concerns and clarify the technical details below.
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.