- Rating
- 2
- Confidence
- 4
- Informativeness
- 1
- Presentation
- 2
- Soundness
- 1
Read review
Paper summary
The paper grows a single classification tree by stochastic search instead of greedy induction. The search has 3 parts:
- Sample many complete trees, with each node using either a random split or a greedy split under a randomly chosen criterion, and score each root by the mean loss of its best sampled continuations.
- Fix a prefix in stages and resample the subtrees below it.
- Refine with a beam, where each split replacement regrows subtrees under four criteria.
The loss combines prediction performance with a leaf penalty on a held-out split, and the input is augmented with PCA and ridge directions, so splits can be oblique. The authors find that on 22 small UCI datasets the tree mostly beats single-tree baselines.
Critical strengths
- The method is intuitive and understandable, although the authors could do a better job to make it clear by describing it at a high level before diving into a technical explanation
- The problem of improving the performance of a decision tree with a reasonable search time is well-motivated
- The evaluation is well-done overall
Critical weaknesses
- Oblique trees are compared with axis-aligned ones. Every single-tree baseline uses axis-aligned splits, while the proposed tree splits on PCA/ridge projections. The paper needs its own method without learned directions, plus oblique baselines (e.g. HHCART, TAO, DTSemNet, or ReLU+Argmin). Without that it's unclear where the gains come from.
- The paper makes some overclaims. Stage 3 is chosen because it has the best mean test Macro-F1 in Table 1, even though Sec. 4.2 says the stage should be picked on validation. Against single trees, only ExtraTree is beaten significantly.
- Interpretability is the reason to want a single tree, and it isn't measured. It would be nice to have some measurement of the number of tree nodes and some visualizations of whether the oblique trees can me interpreted at all.
Smaller note: random restarts + lookahead + refinement over complete trees is close to older stochastic tree search that isn't discussed: Bayesian CART (Chipman et al. 1998), evtree (Grubinger et al. 2014), lookahead induction (Murthy & Salzberg 1995), and MCTS for decision trees (Nunes et al. 2018). Born-again tree ensembles (Vidal & Schiffer 2020) target the same "close the gap with one tree" goal.
Questions for authors
- Can you report results for the method with learned directions disabled, against the same axis-aligned baselines, with the stage selected on validation?
- Can you show Macro-F1 vs number of leaves for all single-tree methods, and the fraction of oblique splits in the final trees?
- What is the wall-clock training time per dataset vs baselines?]