Source-linked AI summary
Learning Nonlinear Functions Using Regularized Greedy Forest
Rie Johnson, Tong Zhang
TL;DR
The paper addresses nonlinear-function learning with decision forests and general loss functions, where boosted tree methods treat the tree learner as a black box. It proposes RGF, which directly learns the forest using tree-structured regularization and fully-corrective regularized greedy search. Across the tested datasets, the authors report more accurate predictions than existing methods, including GBDT and AdaBoost, while also obtaining smaller models.
Problem
Existing boosted-tree methods learn forests through a wrapper around a black-box tree learner, motivating a direct method that exploits forest structure and supports general loss functions.
Method
RGF directly learns additive nonlinear decision rules using tree-structured regularization and fully-corrective regularized greedy search.
Results
The authors report that RGF achieves more accurate predictions than tested existing methods, including GBDT and AdaBoost, with smaller models on many datasets.
Takeaways & Limitations
Using the forest's structure directly provides an effective and principled alternative to wrapper-based boosted decision trees across the evaluated datasets.
Abstract
from arXiv · showhide
We consider the problem of learning a forest of nonlinear decision rules with general loss functions. The standard methods employ boosted decision trees such as Adaboost for exponential loss and Friedman's gradient boosting for general loss. In contrast to these traditional boosting algorithms that treat a tree learner as a black box, the method we propose directly learns decision forests via fully-corrective regularized greedy search using the underlying forest structure. Our method achieves higher accuracy and smaller models than gradient boosting (and Adaboost with exponential loss) on many datasets.
I. INTRODUCTION
The paper studies learning nonlinear functions with decision forests and proposes directly exploiting forest structure rather than treating decision-tree learning as a black-box component. RGF is designed for general loss functions and aims to improve accuracy through structured greedy search.
- Decision trees handle heterogeneous data readily and require less tuning than neural networks, but generally deliver lower prediction accuracy.
- Boosting forms an additive decision forest, but its wrapper treats the tree learner as a black box and may not optimally aggregate tree structure.
- The paper proposes directly learning decision forests by exploiting their underlying tree structure rather than using a black-box tree learner.
- RGF supports general loss functions, unlike Adaboost's loss-specific formulation, and achieves better results than GBDT on tested datasets.
- The learning problem covers nonlinear prediction functions for regression, binary classification, and pair-wise preference learning with task-specific loss functions.
- RGF uses additive nonlinear decision rules as its function class and searches the large rule space with a structured greedy algorithm.
III. GRADIENT BOOSTED DECISION TREE
Gradient boosting minimizes a general loss using an additive model and a regression-tree base learner. Its shrinkage and early stopping provide implicit regularization, but small step sizes can produce unnecessarily large forests and their regularization effects are unclear.
- Gradient boosting minimizes the loss with an additive model by repeatedly applying a nonlinear base learner that approximately solves a regression problem.
- For decision trees, GBDT uses a J-leaf tree and partially corrects all J associated coefficients before applying shrinkage.
- Gradient boosting is a functional generalization of gradient descent, with shrinkage acting as the step size.
- Small shrinkage can improve prediction performance but generally requires more trees, creating a potentially huge model and higher computational cost.
- GBDT has no explicit regularization; shrinkage, early stopping, and tree size interact as implicit regularizers whose combined effect is unclear.
IV. FULLY-CORRECTIVE GREEDY UPDATE AND STRUCTURED SPARSITY REGULARIZATION
The paper combines fully corrective updates with explicit structured regularization to learn compact decision forests while avoiding the small-step requirement of traditional gradient boosting. This framework is motivated by convergence benefits of correcting all coefficients and by the need to control overfitting from aggressive greedy search.
- Fully-corrective updates: Fully-corrective gradient boosting re-optimizes all coefficients obtained so far at each iteration, unlike partial corrective boosting.The paper reports that this can accelerate convergence and has a theoretical convergence rate under suitable conditions.
- Fully-corrective updates: The fully-corrective update, combined with regularization, removes the need for the small step s used in traditional gradient boosting.The comparison states that no analogous convergence rate is possible with only partial corrective optimization.
- Structured sparsity regularization: Explicit regularization is required because aggressive greedy search can quickly overfit without the implicit regularization provided by a small boosting step.The paper frames regularization as necessary for controlling overfitting while using larger corrective updates.
- Structured sparsity regularization: The method seeks sparse combinations of decision rules and exploits the forest’s graph-like structure as a structured sparsity pattern.This supports compact models while using the organization of rules within decision forests.
V. REGULARIZED GREEDY FOREST
Regularized Greedy Forest directly learns a decision forest through fully corrective regularized greedy search over its underlying node structure. Its formulation uses explicit tree-structured regularization and represents the forest as an additive model over decision-rule basis functions.
- Method overview: RGF directly learns a decision forest via fully-corrective regularized greedy search rather than treating a tree learner as a wrapper component.The method is presented as addressing the issues of standard gradient-boosted decision trees.
- Method overview: The method introduces explicit regularization that takes advantage of individual tree structures.The regularized objective replaces the unregularized formulation and is designed around forest topology.
- Method overview: RGF repeatedly re-optimizes all decision-rule coefficients while adding rules through greedy search.This fully corrective procedure is paired with explicit regularization to avoid overfitting and excessively large models.
- Forest representation: The nonlinear function is defined as an additive model over forest nodes, enabling structured search and potentially simultaneous growth of multiple trees.The forest structure is treated as a graph sparsity structure.
- Forest representation: Each forest node represents a nonlinear decision rule that serves as a basis function, while the model assigns weights to nodes with internal-node weights set to zero.Equivalent leaf-only representations follow from the parent-child relationship between node basis functions.
B. Algorithmic framework
The RGF framework alternates between changing forest structure and optimizing weights, using greedy structural operations that split leaves or add trees. Candidate operations are evaluated by their loss reduction, with practical search restricted to recent trees when exhaustive search is too expensive.
- Algorithmic framework: RGF alternates between reducing Q(F) by changing forest structure and minimizing Q(F) by changing weights.These are the framework’s two main algorithmic components.
- Structure search: The practical search uses two operations: splitting an existing leaf node or starting a new tree by adding a stump.New leaf nodes receive weights and the split node is assigned zero weight.
- Structure search: For each structural operation, the method evaluates the loss reduction and selects the optimum forest obtainable from one permitted structure change.The procedure repeatedly searches for the best candidate before optimizing leaf weights.
- Structure search: When searching the entire forest is prohibitively expensive, RGF restricts candidates to the most recently created t trees, with t = 1 as the default.This restriction still permits choosing between splitting a recent leaf and growing a new tree.
- Structure search: RGF automatically determines tree sizes through minimization of the regularized loss, so it does not require the tree-size parameter used in GBDT.
- Structure search: Splitting a leaf removes its parent contribution and replaces it with child contributions, then optimizes the resulting forest over the child weight changes.The split optimization considers forests generated by splitting one current leaf node.
- Structure search: The split subproblem may use one Newton step as a more accurate inexpensive approximation when analytic optimization is unavailable.The computation is repeated frequently, motivating an efficient approximation.
2) Weight optimization/correction (Line 3):
With forest structure fixed, RGF optimizes leaf weights using coordinate descent and Newton updates, while periodically applying fully corrective weight updates as new leaves are added.
- Weight optimization: With basis functions fixed, the implementation optimizes weights by coordinate descent, updating each weight with a Newton step using a small step size.The procedure iteratively visits the basis functions and changes their coefficients.
- Weight optimization: Fully corrective weight updates need not occur after every iteration because newly initialized leaf weights are approximately optimal when created.The implementation instead corrects weights after every k new leaf nodes, with extreme k values discouraged.
D. Tree-structured regularization
Tree-structured regularization assigns penalties through a unique representation of equivalent models on a tree, using leaf weights, node structure, and depth. The section presents leaf-only L2, min-penalty, and computational procedures for these regularizers.
- Regularization framework: Equivalent models on the same tree topology receive the same penalty through a selected unique representation.The representation is defined over all nodes, with penalties depending on node weights and attributes such as depth.
- L2 regularization: The leaf-only model uses standard L2 regularization and is often, but not always, the sparsest equivalent representation.Its sparsity refers to using the smallest number of basis functions among equivalent models.
- Min-penalty regularization: The min-penalty regularizer selects the equivalent model minimizing a penalty that explicitly accounts for node depth.Deeper nodes are penalized more when γ > 1, reflecting their association with more complex decision rules.
- Computation: The min-penalty computation introduces recursively defined auxiliary variables and solves for each variable as a weighted average of neighboring values.This recursive optimization leads to an iterative algorithm.
3) Min-penalty regularization with sum-to-zero sibling constraints:
The sum-to-zero sibling regularizer constrains sibling weights to cancel, selecting a unique equivalent model that reduces redundancy between opposing branches.
- Sum-to-zero sibling constraints: Sibling constraints require the weights of every sibling pair to sum to zero.The constraint is imposed alongside the regularization framework described for tree models.
- Sum-to-zero sibling constraints: The constraint favors less redundant models by making sibling branches take completely opposite actions.The paper illustrates this as one branch adding x and the other subtracting x from the output.
- Unique representation: Every set of equivalent models contains exactly one model satisfying the sum-to-zero sibling constraints.That representative is obtained through recursive computation on auxiliary variables.
E. Extension of regularized greedy forest
The paper extends RGF by separating regularization parameters for forest growing and fully corrective weight updates, then evaluates RGF against GBDT and other ensembles on regression and binary classification tasks. Experiments report stronger accuracy and, in several comparisons, smaller models.
- Extension: RGF allows forest growing and weight correction to use different regularization parameters because the two processes are greedy-local and fully corrective-global, respectively.The paper also notes, but does not pursue, changing regularization strength as the forest grows.
- Experimental scope: The experiments focus on regression and binary classification, although the general-loss formulation also applies to other tasks such as multiclass classification.Multiclass prediction can be constructed through schemes such as one-vs-others, and similar extensions exist for related methods.
- Synthesized datasets: Synthesized datasets vary target-function complexity by generating ensembles of q-leaf regression trees, with larger q indicating more complex targets.The study evaluates performance using randomly generated features, splits, leaf weights, and data points.
- Synthesized datasets: 0.0315, 0.0210, and 0.0033 RMSE improvements over RGF-L2 occur with min-penalty regularization and sibling constraints on 5-, 10-, and 20-leaf datasets, respectively.The improvements are larger on the simpler synthesized targets.
- Model-size comparisons: RGF achieves better RMSE than GBDT at all model sizes in the synthesized-data comparison, requiring a smaller model for similar RMSE.The comparison uses model size measured by basis functions or leaf nodes.
B. Regression and 2-way classification tasks on the real-world datasets
On real-world regression and binary-classification tasks, RGF generally outperformed the compared tree ensembles while often using smaller models. Its advantage was strongest over GBDT and poorly regularized or stump-based AdaBoost.
- Regression results: RGF achieved lower RMSE than all other methods on the regression datasets.
- Binary classification results: RGF achieved the best binary-classification performance on three datasets, whereas GBDT was best on only one.
- AdaBoost comparison: Explicit regularization mattered for AdaBoost: stump restrictions degraded accuracy by 1%, 6%, and 12% relative to RGF on Letter, Musk, and Nursery.
- Model size: RGF reached comparable accuracy with smaller models than GBDT and AdaBoost, while BART models exceeded 400K leaf nodes versus 20K or fewer for RGF.
C. GBDT with post processing of fully-corrective updates
The paper compares RGF with a two-stage GBDT-plus-L1 approach and evaluates both methods in competitions. RGF’s interleaved learning and direct forest optimization were associated with smaller or more accurate models across these comparisons.
- Two-stage post-processing: RGF interleaves basis-function generation with weight optimization, allowing fully corrected weights to influence subsequent basis functions.
- Two-stage post-processing: L1 post-processing made GBDT models smaller but noticeably degraded accuracy on all but one dataset.
- Competition results: RGF produced more accurate models than GBDT in all three competitions.
- Competition results: In bond-price prediction, RGF produced smaller error than GBDT on both public and private leaderboard portions using the same features for single runs.
- Competition results: RGF achieved lower error than GBDT in both leaderboard and five-fold cross-validation comparisons for hospital-stay prediction.
- Competition results: Across 53 datasets, RGF produced lower error than GBDT, with an average error difference of 0.0005.
VII. RUNNING TIME
RGF grows forests and repeatedly corrects leaf weights, adding computational work beyond GBDT while retaining linear dependence on the number of training points. Parameter-selection design can nevertheless make total tuning time competitive.
- Complexity: RGF training has additional complexity from fully-corrective weight updates, but its running time is linear in the number of training data points.
- Implementation assumptions: Pre-sorting costs O(nd log(n)), although its observed runtime was practically negligible relative to other training operations at n up to 100,000.
- Complexity: Forest growth costs O(ndℓ), while coordinate-descent weight optimization costs O(nℓcz) excluding regularization.
- Regularization overhead: The extra running time from min-penalty regularizers and weight optimization depends on implementation and includes an O(ℓcz) optimization term.
- Empirical timing: On Letter, parameter selection took 128 seconds for RGF-L2 versus 191 seconds for GBDT despite RGF taking longer per training run.