Source-linked AI summary
Efficient non-greedy optimization of decision trees
Mohammad Norouzi, Maxwell D. Collins, Matthew Johnson, David J. Fleet, Pushmeet Kohli
TL;DR
Greedy decision-tree induction optimizes one split at a time, whereas jointly optimizing splits and leaf parameters under a global objective is challenging. This paper uses a latent-variable formulation and an upper bound on empirical loss for non-greedy optimization. Across multiple datasets and tree depths, the authors report the best test performance for their non-greedy trees among the compared methods.
Problem
Method
Results
Across multiple datasets and tree depths, non-greedy trees achieve the best test performance among the compared methods.
Source: §7 · p. 8Takeaways & Limitations
The global training framework can be extended to sparse splits or kernelized split parameters, according to the paper’s proposed future directions.
Source: §8 · p. 8Larger split-weight norms tighten the upper bound but can make it nearly piecewise constant and difficult to optimize.
Source: §5 · p. 5
Abstract
from arXiv · showhide
Decision trees and randomized forests are widely used in computer vision and machine learning. Standard algorithms for decision tree induction optimize the split functions one node at a time according to some splitting criteria. This greedy procedure often leads to suboptimal trees. In this paper, we present an algorithm for optimizing the split functions at all levels of the tree jointly with the leaf parameters, based on a global objective. We show that the problem of finding optimal linear-combination (oblique) splits for decision trees is related to structured prediction with latent variables, and we formulate a convex-concave upper bound on the tree's empirical loss. The run-time of computing the gradient of the proposed surrogate objective with respect to each training exemplar is quadratic in the the tree depth, and thus training deep trees is feasible. The use of stochastic gradient descent for optimization enables effective training with large datasets. Experiments on several classification benchmarks demonstrate that the resulting non-greedy decision trees outperform greedy decision tree baselines.
1 Introduction
Decision trees are valued for their computational efficiency and use in large-scale tasks, but conventional induction remains greedy. This paper jointly optimizes split functions across tree levels under a global objective, connecting the problem to latent-variable structured prediction.
1 Introduction
- Decision trees and forests remain popular partly because they are computationally efficient and apply to large-scale classification and regression.The introduction cites Kinect pose estimation from depth images, using trees trained on millions of exemplars.Source: §1 · p. 1
- Jointly optimizing split functions across tree levels under a global objective is the paper’s proposed alternative to greedy induction.The authors state that joint optimization can promote cooperation among split nodes and improve generalization.Source: §1 · p. 1
- The method links decision-tree optimization to structured prediction with latent variables and uses a convex-concave upper bound on empirical loss.The bound is optimized by stochastic gradient descent; modifying it reduces gradient complexity from O(2^d p) to O(d^2 p).Source: §1 · p. 2
2 Related work
Prior non-greedy approaches faced challenges in computational cost, scope, or overfitting, while soft-split models can lose some of trees’ computational advantage. The paper presents a latent-variable formulation intended to support efficient learning, general losses, and regularized joint optimization.
2 Related work
- Jointly optimizing splits is difficult because tree decisions are discrete and sequential, a problem the paper frames as NP-complete.Earlier non-greedy approaches faced limitations including high computation for few-node trees or susceptibility to overfitting without regularization.Source: §2 · p. 2
- Soft splits in Hierarchical Mixture of Experts capture gradual transitions, but evaluating all or most experts can erode trees’ computational advantage.The soft splits yield a probabilistic model with a smooth log-likelihood that can be optimized using methods such as EM.Source: §2 · p. 2
- The paper’s formulation is presented as handling general loss functions while retaining O(dp) inference and providing a surrogate objective for regularizing joint optimization.The cited prior approaches include online tree extension with Mondrian Processes [15] and global multi-linear programming limited to binary classification with 0-1 loss.Source: §2 · p. 2
3 Problem formulation
The paper formulates binary decision-tree learning as joint optimization of oblique split parameters and leaf parameters against empirical loss. Because tree navigation depends on sequential binary tests, direct optimization is challenging; the formulation represents split decisions as latent variables that select a leaf.
3 Problem formulation
- Each internal node uses a linear threshold split, sgn(w_i^T x − b_i), with the offset represented by appending a constant −1 to the input.This section focuses on binary classification trees.Source: §3 · pp. 2–3
- Jointly choosing oblique splits and leaf parameters to minimize training-set misclassification loss is challenging because tree decisions are discrete and sequential.The setup uses a binary tree with m internal nodes and m + 1 leaves; each leaf specifies a distribution over class labels.Source: §3 · pp. 2–3
- The split outputs can be represented as a binary vector h, and the navigation function f(h) selects a one-hot leaf indicator.The selected leaf parameters are Θ^T f(h); Figure 1 illustrates this for three internal nodes.Source: §3 · p. 3, Figure 1 · p. 3
- For each input, the selected leaf’s parameters determine the prediction loss; classification uses log loss, while regression can use squared loss.The framework allows other loss forms; the stated regression setting has y and θ in R^q.Source: §3 · pp. 3–4
- Direct optimization over W is difficult because empirical loss is discontinuous and piecewise constant, while early binary tests determine which later tests occur.The learning objective is to find W and Θ that minimize empirical loss on the training set.Source: §3 · pp. 3–4
4 Decision trees and structured prediction
The paper connects decision-tree learning to structured prediction by treating split decisions as latent variables. It uses this perspective to formulate a piecewise-smooth upper bound on empirical loss.
4 Decision trees and structured prediction
- To address intractable empirical-loss optimization, the paper develops a piecewise-smooth upper bound inspired by latent-variable structured prediction.The bound is proposed as a surrogate for empirical loss.Source: §4 · p. 4
- The split functions can be represented through a latent binary vector h, which determines the selected leaf and its loss.The split vector can be viewed as maximizing a score, and the loss is re-expressed in a joint feature space over h and x.Source: §4 · p. 4
- Because the ground-truth split decisions are unavailable, the resulting objective is a form of structured prediction with latent variables.The objective resembles those used in structured prediction.Source: §4 · p. 4
5 Upper bound on empirical loss
The section upper-bounds empirical loss with a surrogate that supports loss-augmented inference and regularizes split parameters. Increasing split-weight norms tightens the bound, but can make it difficult to optimize.
5 Upper bound on empirical loss
- Loss-augmented inference adds a loss term to standard inference and can be solved exactly for this tree formulation.The bound is tight when the latent decisions match the standard inference result.Source: §5 · p. 4
- Because empirical loss is invariant to W's scale but the upper bound is not, the method regularizes W's norm during bound optimization.The bound tightens as W is scaled up, but an excessively large norm can make it nearly piecewise constant and hard to optimize.Source: §5 · pp. 4–5
- The surrogate objective sums the per-example bounds and constrains each split row's norm independently.The row constraints use the regularization parameter ν.Source: §5 · p. 5
- For every ν, the empirical loss is bounded above by the surrogate objective, which uses hard row-norm constraints on W.The constraints also support sparse gradient updates because most rows of W have zero gradients at each step.Source: §5 · p. 5
6 Optimizing the surrogate objective
The optimization section describes how to minimize the surrogate through tree-structured inference and stochastic gradient methods. A fast inference variant reduces the depth-dependent cost, while Stable SGD updates leaf assignments conservatively.
6 Optimizing the surrogate objective
- Although the surrogate remains non-convex to minimize, it is piecewise linear and convex-concave in W, with convex constraints on W.Source: §6 · p. 5
- Inference can be organized by leaf: path decisions determine the leaf, while off-path bits follow sgn(Wx), enabling a depth-first search over candidate leaves.The method selects the leaf maximizing the loss-augmented objective.Source: §6 · pp. 5–6
- Fast loss-augmented inference considers at most d + 1 leaf outcomes and yields gradient updates with complexity O(d^2p + k).The original algorithm has complexity O(mp), with m internal nodes and tree depth d.Source: §6 · pp. 6–7
- SGD samples training pairs to update split parameters and leaf parameters, then projects W back into its feasible region.The implementation also uses momentum and mini-batches.Source: §6 · p. 6
- Stable SGD fixes data-point-to-leaf assignments for several updates, refreshing them when improvement in the bound becomes negligible.This conservative assignment schedule is intended to discourage abrupt changes in the number of inactive leaves.Source: §6 · p. 6
- Non-greedy trees achieve better test accuracy across depths and are less vulnerable to overfitting than the compared methods.Figure 2 plots test and training accuracy as a function of depth.Source: Figure 2 · p. 7
7 Experiments
Across the reported datasets and tree depths, non-greedy trees achieve the best test performance and appear less susceptible to overfitting. The experiments also examine regularization-driven pruning and the runtime of fast inference.
7 Experiments
- Experiments use SensIT, Connect4, Protein, and MNIST, comparing against axis-aligned, OC1, random oblique, and CO2 trees.For single-tree comparisons, the maximum tree depth is varied.Source: §7 · p. 7
- Small ν values can prune MNIST trees to far fewer leaves than the axis-aligned initialization, and ν is selected using validation error.The study tests ν values from 0.1 to 100 and then trains on the combined training and validation sets for test evaluation.Source: Figure 3 · p. 8, §7 · p. 8
- Non-greedy trees achieve the best test performance across depths and datasets, appear less susceptible to overfitting, and improve on CO2 in most cases.CO2 is the simpler greedy variant of the proposed approach.Source: §7 · p. 8
- Non-greedy trees are initialized from an axis-aligned information-gain tree, with the greedy CO2 procedure providing initial W and Θ.Source: §7 · p. 8
- On Connect4, standard loss-augmented inference runtime grows exponentially with tree depth, whereas the fast variant is more scalable.The comparison measures total time for 1,000 SGD epochs; Connect4 has 55,000 training points.Source: §7 · p. 8, Figure 4 · p. 8
8 Conclusion
The paper presents non-greedy decision-tree learning as stochastic-gradient optimization of an upper bound on training empirical loss, with a framework that admits sparse and kernelized extensions.
8 Conclusion
- Stochastic gradient descent optimizes an upper bound on the training dataset’s empirical loss for non-greedy decision-tree learning.The framework poses global tree training as an optimization problem.Source: §8 · p. 8
- Sparsity-inducing regularization on W is proposed as a way to learn sparse split functions.The paper identifies this as a possible route to efficiency gains.Source: §8 · p. 8
- Applying the kernel trick to linear split parameters W makes the model applicable to higher-order splits and examples in arbitrary reproducing kernel Hilbert spaces.Source: §8 · p. 8
A Proofs
The proof section states an upper bound on split loss and establishes that it tightens as a constant multiple of W increases.
A Proofs
- The loss ℓ(Θ^T f(sgn(Wx)), y) is upper bounded by the expression introduced in the proof.Source: A Proofs · p. 10
- For any α > β > 0, the upper bound becomes tighter as a constant multiple of W increases.Source: A Proofs · p. 10
- The proof concludes by summing the two sides of (17) and (19) and using (18).Source: A Proofs · p. 10