PaperlayerView exact revision on arXiv

Source-linked AI summary

GBDT-MO: Gradient Boosted Decision Trees for Multiple Outputs

Zhendong Zhang, Cheolkon Jung

arXiv:1909.04373v2cs.CVcs.LG

TL;DR

Existing GBDT implementations learn separate trees for multiple outputs, ignoring correlations and introducing redundant structures. GBDT-MO jointly predicts outputs in each tree, optionally selects correlated subsets, and extends histogram approximation; experiments report better generalization and faster training.

  • Problem

    Existing GBDT implementations treat multiple output variables independently, ignoring their correlations and producing redundant learned tree structures.

  • Method

    GBDT-MO jointly fits multiple outputs in each tree by summing objective gains across variables, optionally selecting output subsets with an L0 constraint and using histogram approximation.

  • Results

    Experiments on synthetic and real-world multi-output tasks report better generalization ability and faster training than standard single-output GBDT, especially for many outputs.

  • Takeaways & Limitations

    Capturing output-variable correlations in shared tree structures provides the paper's reported accuracy and training-speed advantages over single-output GBDT.

Abstract

from arXiv · show

Gradient boosted decision trees (GBDTs) are widely used in machine learning, and the output of current GBDT implementations is a single variable. When there are multiple outputs, GBDT constructs multiple trees corresponding to the output variables. The correlations between variables are ignored by such a strategy causing redundancy of the learned tree structures. In this paper, we propose a general method to learn GBDT for multiple outputs, called GBDT-MO. Each leaf of GBDT-MO constructs predictions of all variables or a subset of automatically selected variables. This is achieved by considering the summation of objective gains over all output variables. Moreover, we extend histogram approximation into multiple output case to speed up the training process. Various experiments on synthetic and real-world datasets verify that GBDT-MO achieves outstanding performance in terms of both accuracy and training speed. Our codes are available on-line.

I. INTRODUCTION

Current GBDT implementations handle multiple outputs with separate trees, ignoring output correlations and creating redundant structures. GBDT-MO jointly learns outputs in single trees, using shared gains, sparse selection, and histogram approximation.

  • Motivation: Current GBDT implementations construct one tree per output variable, treating outputs independently during training.
  • Motivation: Ignoring correlations between output variables can produce redundant learned tree structures and motivates a joint multiple-output strategy.
  • GBDT-MO: GBDT-MO jointly fits all output variables in a single tree, with each leaf predicting multiple outputs.
  • GBDT-MO: The split-finding objective maximizes the summed objective gains across output variables, while an L0 constraint enables automatic selection of correlated output subsets.
  • GBDT-MO: The method extends histogram approximation to multiple outputs and uses second-order gradients to improve training efficiency.
  • Results: Experiments on synthetic and real-world datasets report better generalization ability and faster training than standard single-output GBDT, especially with many outputs.

C. Split Finding

Single-output split finding maximizes gain by comparing objectives before and after candidate splits. The paper extends this process through histogram buckets to make multiple-output training more efficient.

  • Split definition: A candidate split divides samples into left and right parts using an input column and threshold.
  • Split objective: The best split maximizes the gain between the optimal objective before splitting and the summed optimal objectives of the two resulting parts.
  • Split objective: A split with gain below a threshold stops tree growth to help avoid over-fitting.
  • Approximation: Exact split finding enumerates possible splits across columns, whereas approximate methods enumerate histogram buckets instead of individual samples.

III. GBDT FOR MULTIPLE OUTPUTS

GBDT-MO generalizes gradient-boosted trees to multiple outputs by assigning vector predictions to leaves and jointly optimizing output objectives. The method uses second-order loss information, with diagonal Hessian approximations when exact non-separable objectives are impractical.

  • Multiple-output formulation: GBDT-MO maps each input to a leaf whose value is a d-dimensional output vector.The tree function selects a leaf and returns that leaf’s d-dimensional vector.
  • Joint objective: The multiple-output objective is derived from a second-order Taylor expansion with quadratic leaf regularization.The resulting optimal leaf values and objective naturally generalize the single-output formulation.
  • Joint objective: Each leaf jointly fits all output variables by maximizing the summed objective gains across outputs.This differs from fitting independent trees even when the Hessian is diagonal.
  • Approximation and scope: When the loss Hessian is non-diagonal, exact optimization is impractical because it requires storing d × d matrices and repeatedly computing their inverses.These costs become problematic as the output dimension grows.
  • Approximation and scope: GBDT-MO therefore uses diagonal Hessian approximations, which are reported as good when diagonal elements dominate and are derived from an upper bound on the loss.Better loss-specific approximations are left for future work.

B. Sparse Objective

The sparse objective lets each leaf predict only a selected subset of output variables, reflecting that correlations may be limited to subsets. An L0 constraint yields a top-k selection rule, while multiple-output histograms support efficient split evaluation.

  • Sparse objective: The sparse objective adds an L0 constraint so a leaf selects at most k output variables.All variables can still be covered across different leaves, while the leaf stores fewer parameters.
  • Motivation: The sparse formulation addresses settings where only a subset of output variables is correlated in practice.It replaces the all-output leaf objective with a suitable subset-selection objective.
  • Sparse objective: The selected variables are those with the k largest objective contributions, while all remaining leaf values are set to zero.The solution ranks columns and retains only the top-k values.
  • Histogram implementation: Multiple-output histograms accumulate gradient and second-order statistics for every bin and output dimension.For each used sample, the algorithm increments the bin count and updates gradient and Hessian sums across outputs.
  • Histogram implementation: Approximate split finding scans input columns and histogram bins to select the split with maximum gain.The procedure maintains cumulative left statistics while deriving right statistics from the current-node totals.

C. Split Finding

For multiple outputs, split finding must aggregate objective gains across output variables, making exhaustive enumeration inefficient. GBDT-MO uses histogram-based approximate split finding and sparse priority-queue algorithms for this setting.

  • Split-finding objective: Multiple-output split finding defines gain over all output variables and requires scanning output columns for each candidate split.The exact algorithm is inefficient because it enumerates all possible splits.
  • Approximate split finding: Histogram approximation speeds training by evaluating bucket boundaries instead of every possible sample-level split.The multiple-output histogram extends the single-output construction to store statistics across outputs.
  • Sparse split finding: The sparse split algorithms compute each candidate split’s gain using top-k priority queues over output variables.The unrestricted and restricted variants are specified as separate gain-computation procedures.

D. Sparse Split Finding

Sparse split finding selects output columns separately or jointly for the two child nodes while evaluating candidate gains. The restricted variant shares selected columns across children, reducing computation and imposing a smoothness prior.

  • Sparse split algorithms: Sparse split finding evaluates objective gains while selecting only a constrained number of output columns for child nodes.The paper contrasts non-sparse, sparse, and restricted sparse split finding using a four-sample, three-output example with constraint 2.
  • Sparse split algorithms: The unrestricted sparse method maintains top-k columns for both child parts based on their objective contributions.A top-k priority queue supports scanning columns efficiently.
  • Restricted sparse split: The restricted sparse method forces the selected column sets of the left and right children to completely overlap.This shared selection changes the gain calculation and yields the restricted algorithm.
  • Restricted sparse split: A single top-k priority queue gives the restricted method lower computational complexity than the non-restricted sparse method.The restriction reduces the number of maintained queues from two to one.
  • Restricted sparse split: Sharing selected columns makes sibling nodes with the same parent more similar, introducing a smoothness prior in function space.This is presented as a second advantage of the restricted method.

E. Implementation Details

The implementation builds GBDT-MO in C++ by extending a LightGBM-like single-output core, with Python access, multicore parallelism, and best-first tree growth.

  • Implementation Details: GBDT-MO is implemented in C++ by integrating multiple-output learning into a self-developed LightGBM core called GBDT-SO.A Python interface is also provided.
  • Implementation Details: OpenMP multicore parallelism is used to speed up GBDT-MO training.
  • Implementation Details: The tree grows best-first by storing unsplit nodes and selecting a node when another split is added.
  • Implementation Details: The paper provides Algorithm 5 for the tree-growth procedure.

F. Complexity Analysis

The split-finding analysis compares GBDT-SO and GBDT-MO across output-aware costs, while related work distinguishes GBDT-MO from sparse and non-GBDT alternatives.

  • Complexity Analysis: For non-sparse split finding, both GBDT-SO and GBDT-MO have complexity O(bmd), while sparse split finding adds a log k factor.Using the exact Hessian changes the complexity to O(bmd^3) because it requires inverting a d × d matrix.
  • Complexity Analysis: Despite equal split-finding complexity, GBDT-SO can train more slowly because it divides samples d times, whereas GBDT-MO divides them once.
  • Related Work: The kernelized alternative requires an n×n kernel matrix and works only for square loss, making it non-scalable.
  • Related Work: GBDT-sparse requires output-separable loss and sparse gradients, with the condition ∂l/∂ŷ = 0 when ŷ = y limiting supported losses.
  • Related Work: GBDT-sparse does not use second-order gradients or histogram approximation, while GBDT-MO incorporates both.
  • Related Work: GBDT-sparse targets extreme multi-label classification, whereas GBDT-MO targets general multiple-output problems.

V. EXPERIMENTS

Experiments cover multi-output regression, multi-class classification, and multi-label classification on synthetic and real-world datasets. GBDT-MO shows stronger generalization than GBDT-SO, although synthetic experiments report slower convergence.

  • Experiments: The evaluation covers multi-output regression, multi-class classification, and multi-label classification using synthetic and real-world datasets.Real-world comparisons include GBDT-SO, XGBoost, LightGBM, and GBDT-sparse.
  • Synthetic Datasets: The friedman1 synthetic problem extends a scalar target to y ∈R5 by adding independent noise to the shared underlying function.
  • Synthetic Datasets: The synthetic experiments use 10,000 training samples and 10,000 test samples for each dataset, with five random-seed repetitions averaged by test RMSE.
  • Synthetic Datasets: GBDT-MO has lower test RMSE and a smaller train–unseen performance gap than GBDT-SO on both synthetic datasets.The paper uses the performance gap as a measure of generalization ability.
  • Synthetic Datasets: The synthetic outputs are correlated, and the authors connect GBDT-MO’s stronger generalization to a learning mechanism that captures variable correlations.GBDT-MO nevertheless suffers from slow convergence speed.

B. Real-world Datasets

The real-world evaluation spans diverse datasets and compares GBDT-MO with related methods on predictive performance and training speed. GBDT-MO achieves better overall performance and is especially faster than competing methods as output dimensionality grows.

  • Dataset setup: The evaluation covers six real-world datasets with varied scale and complexity, using official or repeated random train-test splits.For datasets without standard splits, results are averaged over 10 trials; losses include cross-entropy for multi-class classification and MSE for regression and multi-label classification.
  • Predictive performance: GBDT-MO has better overall RMSE and accuracy than the compared methods on real-world datasets.The paper also reports better generalization ability than GBDT-SO, despite higher training loss.
  • Training speed: GBDT-MO is remarkably faster than GBDT-SO and XGBoost, especially when the number of outputs is large.It is slightly faster than LightGBM; training time is averaged over three repetitions of 10 boost rounds.

C. Sparse Split Finding

The sparse split-finding experiments compare unrestricted and restricted algorithms across several datasets and sparse factors. The restricted algorithm is faster and slightly more accurate, while diagonal Hessian approximation offers a favorable accuracy-speed trade-off.

  • Experimental setup: The sparse split-finding evaluation compares unrestricted and restricted algorithms on MNIST, MNIST-inpainting, Caltech101, and NUS-WIDE across different sparse factors.The same hyper-parameters as the corresponding non-sparse methods are used.
  • Sparse split speed: The restricted sparse split-finding algorithm is faster than the unrestricted algorithm, with larger speed differences at larger k.Training times are reported in seconds in Table VI.
  • Sparse split performance: The restricted algorithm is slightly better than the unrestricted algorithm on test performance.The paper also reports that sparse methods can outperform the non-sparse version for a suitable k, such as k = 64 on Caltech101.
  • Hessian approximation: Replacing the exact Hessian with a diagonal Hessian produces similar accuracy but much faster single-round training.The comparison is conducted on MNIST and Yeast, whose output dimensions are relatively small.
  • Hessian approximation: The diagonal Hessian approximation provides a favorable trade-off between accuracy and computational speed.This approximation reduces computational complexity while preserving similar accuracy in the reported comparison.

APPENDIX A APPROXIMATED OBJECTIVE

The appendix develops approximations for the multi-output learning objective using assumptions about the Hessian and second-order Taylor expansion. It also documents implementation settings and statistical testing used to assess reported superiority.

  • Approximated objective: The approximation assumes that the Hessian H is dominated by its diagonal elements.This assumption supports replacing the full Hessian structure with diagonal terms in the objective derivation.
  • Approximated objective: The derivation ignores the remainder term of the Taylor expansion and substitutes an upper bound to obtain the optimal leaf weight.The resulting solution matches the diagonal-Hessian form apart from the coefficient γ.
  • Implementation consequence: The learning rate can cancel the effect of γ, so its exact value need not be considered in practice.The paper states that α and λ can be adjusted to absorb γ's effect.
  • Hyper-parameters: Maximum depth and learning rate are selected by grid search, while L2 regularization is fixed at λ = 1.0 across experiments.Depth is searched from {4, 5, 6, 7, 8, 9, 10}, and learning rate from {0.05, 0.1, 0.25, 0.5}.
  • Statistical testing: For datasets without standard splits, superiority is assessed from 10 random trials using confidence probabilities based on estimated performance differences.Most confidence scores are significantly higher than 0.5.
Loading 1909.04373v2…