Source-linked AI summary
CO2 Forest: Improved Random Forest by Continuous Optimization of Oblique Splits
Mohammad Norouzi, Maxwell D. Collins, David J. Fleet, Pushmeet Kohli
TL;DR
Oblique splits offer more expressive feature combinations than univariate splits, but their discontinuous stump loss is difficult to optimize. CO2 uses a continuous upper bound to optimize oblique stumps, and the paper reports improvements over random forests and prior oblique-tree methods on classification benchmarks.
Problem
Oblique split parameters are difficult to optimize because stump empirical loss is discontinuous, and multiclass stumps require jointly assigning labels to leaves and choosing hyperplane parameters.
Source: §4 · p. 3Method
Results
CO2 forests achieve large improvements on classification benchmarks over random forests and previous oblique-tree methods.
Source: §7 · p. 7Takeaways & Limitations
The upper-bound framework scales to high-dimensional inputs and large training sets and can be generalized to regression or structured prediction losses.
Source: §7 · p. 7On LFW, the models use only raw pixels and the comparison targets forest baselines, while other tree-like structures and specialized vision systems achieve better segmentation accuracy.
Source: §6.2 · p. 7
Abstract
from arXiv · showhide
We propose a novel algorithm for optimizing multivariate linear threshold functions as split functions of decision trees to create improved Random Forest classifiers. Standard tree induction methods resort to sampling and exhaustive search to find good univariate split functions. In contrast, our method computes a linear combination of the features at each node, and optimizes the parameters of the linear combination (oblique) split functions by adopting a variant of latent variable SVM formulation. We develop a convex-concave upper bound on the classification loss for a one-level decision tree, and optimize the bound by stochastic gradient descent at each internal node of the tree. Forests of up to 1000 Continuously Optimized Oblique (CO2) decision trees are created, which significantly outperform Random Forest with univariate splits and previous techniques for constructing oblique trees. Experimental results are reported on multi-class classification benchmarks and on Labeled Faces in the Wild (LFW) dataset.
1 INTRODUCTION
The introduction motivates oblique splits as more expressive than univariate splits but difficult to optimize, then proposes a continuous loss bound for optimizing them. It reports that CO2 forests outperform the stated forest baselines while mitigating diversity loss.
1 INTRODUCTION
- Oblique splits combine features in a linear projection, but exhaustive hyperplane search is infeasible and preliminary random sampling performs poorly.Unlike univariate splits, their parameters are not readily amenable to numerical optimization because typical stump criteria are discontinuous.Source: §1 · p. 1
- A continuous, ramp-loss-like upper bound on stump empirical loss makes oblique-split optimization possible with convex losses.The bound is a difference of two convex terms, optimized using the Convex-Concave Procedure.Source: §1 · p. 1
- Random-forest split initialization yields non-correlated optimized trees, mitigating diversity loss; performance gains increase as the ensemble grows.The non-convex optimization allows diverse initial states to produce different split functions.Source: §1 · pp. 1–2
- CO2 forest outperforms random forest on all nine classification benchmarks and also outperforms OC1 trees; on LFW, it outperforms the other forest baselines.The experiments generate up to 1000 trees; the LFW comparison is against forest baselines.Source: §1 · p. 2
2 RELATED WORK
Related work includes coordinate-descent oblique trees, soft-split experts, and random forests. CO2 instead optimizes all split weights together and uses latent-variable-SVM regularization, with stated trade-offs in training, inference, and task scope.
2 RELATED WORK
- Earlier CART-LC and OC1 methods optimize oblique-split weights one dimension at a time, whereas CO2 updates all weights simultaneously using gradient descent.OC1 adds random restarts and perturbations to escape local minima.Source: §2 · p. 2
- Latent-variable-SVM regularization is presented as a means to improve oblique stumps’ generalization, beyond optimizing splitting criteria for smaller trees.The authors contrast this with prior algorithms focused mainly on minimizing tree size.Source: §2 · p. 2
- Hierarchical mixture-of-experts models permit smooth optimization through soft splits, but inference must explore multiple tree paths, reducing classifier efficiency.Source: §2 · p. 2
- Random forests train faster and often classify faster at equal tree counts, while CO2 can achieve similar accuracy with fewer trees and sometimes higher performance at computational cost.Random forests’ trees can be trained in parallel; the authors usually train 30 trees in parallel.Source: §2 · p. 2
- Unlike a cited oblique-forest approach limited to convenient binary-classification use, CO2 supports optimization of multiclass-classification and regression losses.The cited method faces a combinatorial label-assignment problem for multiclass splits.Source: §2 · p. 2
- Neural-net split functions can be powerful but lose decision trees’ computational simplicity; the paper positions linear multivariate splits as a middle ground.The authors also note their upper-bound formulation can extend to nonlinear split functions, including neural nets.Source: §2 · p. 2
3 PRELIMINARIES
The preliminaries describe a binary tree whose internal nodes route inputs using linear threshold tests and whose leaves provide class-label distributions. The paper frames training as minimizing misclassification loss over split and leaf parameters, while optimizing nodes greedily from root to depth or another stopping condition.
3 PRELIMINARIES
- The setup uses binary classification trees with m internal nodes and m + 1 leaves, routing each input to a leaf that specifies a distribution over k labels.A binary tree has one more leaf than internal node.Source: §3 · p. 2
- Each internal node sends an input left or right according to the sign of a node-specific linear threshold function.An offset is incorporated by appending a constant −1 to the feature vector.Source: §3 · p. 2
- Leaf class distributions are parameterized by unnormalized log-probabilities and a softmax function.Source: §3 · pp. 2–3
- The tree parameters comprise internal split-weight vectors and one vector of unnormalized log-probabilities per leaf.Source: §3 · p. 3
- Training seeks split and leaf parameters that minimize training misclassification loss, but joint optimization is challenging because tree decisions are discrete and sequential.The method optimizes internal nodes one at a time in breadth-first order, stopping at a target depth or another stopping criterion.Source: §3 · p. 3
4 CONTINUOUS OPTIMIZATION OF OBLIQUE (CO2) DECISION STUMPS
CO2 optimizes an oblique stump’s feature weights and leaf parameters by replacing discontinuous empirical loss with a continuous upper bound. The bound’s convex-concave structure supports CCCP and stochastic subgradient optimization.
4 CONTINUOUS OPTIMIZATION OF OBLIQUE (CO2) DECISION STUMPS
- A stump uses a weight vector to gate examples to two leaves, whose parameters define the selected loss; minimizing log loss maximizes information gain.The leaf parameters that minimize log loss for a fixed split are the empirical class log-probabilities at the leaves.Source: §4 · p. 3
- The framework also accommodates other losses convex in the leaf parameters, including squared loss for regression with y ∈ R^k.Source: §4 · p. 3
- Because stump empirical loss is discontinuous in the split weights, CO2 optimizes a continuous upper bound while jointly learning leaf assignments and hyperplane parameters.Unlike binary classification, the multi-label stump does not pre-specify which labels go to each side of the hyperplane.Source: §4 · p. 3
4.1 Upper Bound on Empirical Loss
- The surrogate objective upper-bounds empirical loss for every ν; its bound tightens as ∥w∥ increases, but large norms make optimization less smooth, so CO2 constrains ∥w∥.The authors report that constraining ∥w∥ yields better solutions with better generalization, and select ν by cross-validation.Source: §4.1 · pp. 3–4
4.2 Convex-Concave Optimization
- The surrogate is piecewise smooth, convex-concave in w, and convex in the leaf parameters; CCCP linearizes its concave term to form a convex subproblem.CO2 uses stochastic subgradient descent on that subproblem, projecting w back into the feasible region and updating the CCCP estimate after a fixed number of epochs.Source: §4.2 · p. 4
- In practice, gradients use mini-batches of 100 with momentum 0.9, and the learning rate is reduced when the surrogate objective oscillates.Source: §4.2 · p. 4
5 IMPLEMENTATION AND EXPERIMENTAL DETAILS
The experiments grow trees to pure leaves and use bagging; validation and grid search set the Random Forest and CO2 hyperparameters, while OC1 is modified for comparison.
5 IMPLEMENTATION AND EXPERIMENTAL DETAILS
- Trees in all methods grow until pure leaves, and bagging builds each forest from datasets sampled uniformly with replacement.For Random Forest, q is selected from five powers of p using a 20% training-set hold-out; validation uses a 1000-tree forest.Source: §5 · p. 5
- The OC1 implementation removes tree-depth and minimum-example limits and adopts CO2’s split initialization; the authors report both changes improve OC1 Forest performance.OC1 hyperparameters otherwise retain the authors’ defaults.Source: §5 · p. 5
- CO2 uses ν, initial learning rate η, and candidate-set size q; q comes from Random Forest validation, while ν and η are selected by grid search.The same regularizer and learning rate are used at every node to keep tuning simple.Source: §5 · p. 5
6 EXPERIMENTS
Across nine multi-class benchmarks, CO2 Forest outperforms Random Forest and OC1 Forest, and on LFW it also beats the forest baselines for face-part segmentation. The experiments examine CO2 tree depth and ν, with results evaluated using test error on the benchmarks and class-average Jaccard score on LFW.
6 EXPERIMENTS
- On MNIST, training error falls with tree depth, while validation error saturates around depth 10; ν = 10 appears best, balancing bound tightness and objective smoothness.CO2 trees reach the baseline’s training error at a smaller depth and achieve better generalization.Source: §6 · p. 5
6.1 UCI multi-class benchmarks
- The benchmarks comprise nine UCI multi-class datasets, with training and test splits generally following prior work.Connect4 and Covertype use the authors’ own splits.Source: §6.1 · p. 5
- On every benchmark CO2 Forest outperforms Random Forest and OC1 Forest; on four datasets, 10 CO2 trees outperform 1,000 Random Forest trees.The improvement is small on Covertype and SatImage.Source: §6.1 · p. 5, Table 1 · p. 6
6.2 Labeled Faces in the Wild (LFW)
- The LFW task predicts one of eight face-part or background labels for each center pixel from a 31 × 31 RGB image window.A 15-pixel border is excluded at training and test time.Source: §6.2 · pp. 5–6
6.1 UCI multi-class benchmarks
- Across tree counts, CO2 Forest outperforms Random Forest and OC1 Forest by a large margin, with gains that usually persist as forests grow.All methods gain substantially from 10 to 30 trees; gains from 30 to 1,000 are smaller but still notable.Source: §6.1 · p. 5, Figure 2 · p. 7
6.2 Labeled Faces in the Wild (LFW)
- CO2 Forest considerably outperforms both Two-probe Forest and Random Forest on LFW face-part segmentation by class-average Jaccard score.The test set comprises 250 randomly chosen images.Source: §6.2 · p. 6, Table 2 · p. 7
- On LFW, other tree-like structures and more sophisticated computer-vision systems achieve better segmentation accuracy; this experiment uses raw pixels to compare forest baselines.Source: §6.2 · p. 7
7 CONCLUSION
CO2 Forest uses oblique splits and a continuous upper bound to optimize decision-tree ensembles, with large improvements over random forests and prior oblique-tree methods on classification benchmarks. The conclusion also highlights its scalability and potential application to other tasks.
7 CONCLUSION
- CO2 Forest uses oblique splits and a continuous upper bound on the information gain objective to optimize decision-tree ensembles.Source: §7 · p. 7
- Fig. 4 plots LFW test Jaccard scores by tree depth and tree count, while Fig. 3 compares Random Forest, Two-probe Forest, and CO2 Forest segmentations with inputs and ground truth.Source: Figure 4 · p. 7, Figure 3 · p. 8
- CO2 Forest achieves large improvements on classification benchmarks over random forests and previous methods for constructing oblique trees.Source: §7 · p. 7
- Unlike OC1 trees, CO2 Forest scales to high-dimensional inputs and large training sets.Source: §7 · p. 7
- The upper bound applies to convex losses, supporting extensions to regression and structured prediction.Source: §7 · p. 7