GBDT-MO: Gradient Boosted Decision Trees for Multiple Outputs

In plain words

Gradient-boosted trees are built one after another, each new tree correcting the mistakes left by the ones before it. When a prediction has several parts, the usual libraries build a separate set of trees for each part and never let them share anything. That wastes effort, because the parts are often related.

This paper changes the tree so that one tree predicts all the parts together. Each leaf holds a small vector, and a split is chosen by how much it helps all parts combined. A second option lets each leaf use only a few of the parts, so unrelated outputs can be left out. A speed trick from earlier libraries, which groups values into histogram bins, is extended to the vector case. The authors report better accuracy on most of their test sets and faster training when there are many parts, but they say the model converges more slowly.

TL;DR

GBDT-MO is a gradient-boosting method in which each tree is shared across all outputs. Its split score adds up the gains over outputs, and an optional top-k restriction keeps only a few outputs per leaf. Its tree construction uses a diagonal Hessian approximation and histograms. The paper reports the best result on five of six datasets; the 10-run averaging is stated only for the three randomly split ones. The code is public under MIT. Treat the numbers as author-reported and check the code differences in the Paper vs code section before relying on them.

Problem

Common GBDT libraries grow one tree per output and concatenate the results, so correlations between outputs are ignored and the learned tree structures can be redundant §1. Earlier multi-output GBDTs have limits. One kernelizes the output space, which needs an n-by-n kernel matrix and works only with the square loss §4. Another (GBDT-sparse) uses sparse outputs and first-order gradients only, so it does not use the second-order gradient or histograms §4. The paper assumes a second-order differentiable loss §2.2, §3.1.

Method

Notation. Input x in R^m, output y in R^d. A tree maps x to a leaf index q(x) and returns a leaf vector W[q(x)] in R^d §3.1 eq. 10. The prediction after t trees is the sum of their leaf vectors §3.1.

Objective per leaf. The loss is second-order differentiable. Its Taylor expansion around the current prediction gives a gradient vector g_i and a Hessian matrix H_i for each sample §3.1 eq. 12. The optimal leaf vector is w* = -(sum_i H_i + lambda I)^(-1) (sum_i g_i) §3.1 eq. 13, and the optimal leaf objective is the matching quadratic form §3.1 eq. 14.

Diagonal approximation (used in practice). Inverting a d-by-d matrix per candidate split is too costly, so the method keeps only the diagonal of H. The per-output leaf value is -G_j / (H_j + lambda), and the objective is the sum over outputs of G_j^2 / (H_j + lambda) §3.1 eq. 15 eq. 16. The paper argues this is a good approximation when H is dominated by its diagonal, with a bound given in app. A. Better approximations are left to future work §3.1.

Split gain (non-sparse). For a candidate split, the gain is the parent objective minus the sum of the two children's objectives, summed over all outputs. Samples go left when the feature value is at most the threshold §2.3 eq. 8 §3.3. Histograms are built per feature, with one gradient and one Hessian value per bin and output alg. 1. The best bin is found by scanning the cumulative bin sums alg. 2.

Sparse variants. To use only k outputs in a leaf, the method keeps the k outputs with the largest score G_j^2 / (H_j + lambda). All other outputs get zero §3.2 eq. 17 eq. 18 eq. 19 eq. 20. Two split-gain variants follow §3.4:

• Unrestricted: left and right children each keep their own top-k outputs eq. 21.
• Restricted: both children share one top-k set, chosen by the sum of their two scores eq. 22 alg. 4. The paper reports that this is slightly better and cheaper §5.3.

Tree growth. Nodes are expanded best-first: the pending node with the largest gain is split next §3.5 alg. 5. The histogram of the smaller child is computed from samples, and the larger child's histogram is the parent histogram minus the smaller one §2.3 booster.cpp.

One boosting round. Compute per-output gradients and diagonal Hessians from the current predictions, grow one tree, scale its leaves by the learning rate, add it to the predictions booster.cpp booster.cpp.

# Gain of one non-sparse split over all d outputs  [§3.3] [eq. 16] [alg. 2]
# Input:  G_l, H_l, G, H: (d,) gradient and diagonal Hessian sums,
#         left side (l) and parent (no suffix); lam: L2 regulariser
# Output: gain (scalar), averaged over outputs

def split_gain(G_l, H_l, G, H, lam):
    # Right side is the parent minus the left side
    G_r = G - G_l
    H_r = H - H_l
    # Objective score of each side, summed over outputs  [eq. 16]
    score_l = sum(G_l ** 2 / (H_l + lam))
    score_r = sum(G_r ** 2 / (H_r + lam))
    score_p = sum(G ** 2 / (H + lam))
    # Halve, then divide by d so the threshold compares the mean gain
    # [code: src/booster.cpp#L494] [app. B]
    return 0.5 * (score_l + score_r - score_p) / len(G)

# Restricted sparse split gain: one shared top-k set  [§3.4] [eq. 22] [alg. 4]
# Input:  G_l, H_l, G, H: (d,) sums; k: number of outputs kept
# Output: gain (scalar)

def restricted_sparse_gain(G_l, H_l, G, H, lam, k):
    G_r = G - G_l
    H_r = H - H_l
    # Parent term: its own best k per-output scores  [eq. 20]
    score_p = sum(top_k(G ** 2 / (H + lam), k))
    # Shared scores: left and right side for each output  [eq. 22]
    shared = G_l ** 2 / (H_l + lam) + G_r ** 2 / (H_r + lam)
    # Keep only the k outputs with the largest shared score
    score_s = sum(top_k(shared, k))
    # Halve, then divide by k  [code: src/booster.cpp#L576]
    return 0.5 * (score_s - score_p) / k

# Leaf value once a leaf is fixed  [§3.1] [eq. 15] [code: src/mathFunc.h#L26]
# Input:  G, H: (d,) gradient and diagonal Hessian sums in the leaf
# Output: W: (d,) leaf vector, before the learning-rate scaling

def leaf_value(G, H, lam):
    # One value per output; lambda is added to the Hessian sum
    return -G / (H + lam)

Hyperparameters

Values come from the paper unless marked as code. Per-dataset values are in the appendix tables.

Learning rate and depth per method tab. IX:

Cells are learning rate / maximum depth.

Gain threshold, minimum samples, maximum bins tab. XI:

Trees in the best model tab. X: the count for GBDT-SO is the sum over outputs.

Results

Author-reported. Yeast, Caltech101 and Student-por were split 70/30 at random, repeated 10 times and averaged §5.2. MNIST, MNIST-inpainting and NUS-WIDE use their official splits; the number of runs for those is not stated §5.2. Synthetic runs use 10,000 training and 10,000 test samples, averaged over 5 seeds §5.1.

Real-world performance tab. V. Higher is better for accuracy; lower is better for RMSE.

Best in each column: GBDT-MO on five of six datasets; XGBoost on Yeast tab. V. For Yeast, Caltech101 and Student-por the paper reports a confidence that GBDT-MO beats each baseline, estimated from the 10 random trials app. C tab. XII. For Yeast against XGBoost that value is 0.067, well below 0.5.

Synthetic data tab. III, RMSE on test data:

Sparse split finding, training time per configuration tab. VI. Cells are restricted / unrestricted, in seconds, as stated in the text §5.3. The table caption gives no unit.

Sparse split finding, performance tab. VII. Cells are restricted / unrestricted.

Exact Hessian versus diagonal tab. VIII (MNIST and Yeast, one round):

Complexity tab. I tab. II. Split finding costs O(b m d) for GBDT-SO and non-sparse GBDT-MO, O(b m d log k) for sparse GBDT-MO, and O(b m d^3) with the exact Hessian. Inference costs O(t h) comparisons for GBDT-MO against O(t d h) for GBDT-SO, where t is the number of rounds and h the depth §3.6.

Speed fig. 5. Figure 5 plots average seconds per boosting round on four larger datasets, log scale. The text says GBDT-MO is much faster than GBDT-SO and XGBoost, especially with many outputs, and slightly faster than LightGBM. The figure gives no table of numbers.

Figures. fig. 1 shows the trees learned on Yeast with 10 outputs: per-output trees for GBDT-SO and one shared tree for GBDT-MO, with depth limited to 3. fig. 2 illustrates the three split variants on four samples and three outputs with a sparse constraint of 2. fig. 3 shows RMSE curves on the synthetic data. fig. 4 shows cross-entropy and accuracy curves on MNIST and Caltech101.

Datasets tab. IV. Samples and features are as listed; * marks features that were pre-processed.

Data preparation §5.2: MNIST pixels are flattened. Yeast uses its 8 attributes. Caltech101 images are resized to 64 by 64 and given HOG features, 324 values. For MNIST-inpainting the central 20 by 20 patch is cut, the upper half is the input and a 4 by 6 patch at the top centre of the lower half is the target. Student-por scores are linearly mapped to [-1, 1] and categorical fields are one-hot coded. NUS-WIDE uses 128-D cVLAD+ features and a label subset selected by Tsoumakas et al.

Paper vs code

Repository: https://github.com/zzd1992/GBDTMO at commit 639615f98522cb33fa0af9e0e3fadf76fc5f2b25, MIT licence, copyright Zhendong Zhang. The paper links it from the implementation section §3.5, and its LICENSE names Zhendong Zhang, an author. Code is C++ with a Python wrapper; the file names used below are from that commit.

• Split gain is averaged over outputs in code. The paper's gain has no 1/d factor §3.3 eq. 16. The code halves the gain and divides by d for the full split and by k for the sparse splits booster.cpp booster.cpp booster.cpp. The appendix does say the gain threshold uses the average gain app. B, so the two agree on the threshold and differ only in the scale of the raw score.
• Hessian. The paper derives the exact leaf value but uses the diagonal in practice §3.1. The code has only the diagonal path mathFunc.h. The exact-Hessian comparison of tab. VIII cannot be reproduced from this repository (search found no inverse or exact code path).
• Cross-entropy Hessian. Code uses p(1 - p) for the diagonal of softmax cross-entropy, with gradient p minus the one-hot label loss.cpp. The paper names cross-entropy but does not give the formula §5.2.
• Squared error. Code sets the gradient to prediction minus label and the Hessian to 1 for every output, which corresponds to half the squared error loss.cpp loss.h. The paper does not state the scaling.
• Multi-label loss. The paper says MSE is used for regression and multi-label tasks §5.2. The code offers a sigmoid cross-entropy objective named bce, with top-1 accuracy as its metric loss.h. The repository has no experiment configuration, so which loss produced the NUS-WIDE result is not determinable from the code.
• Maximum leaves. The paper sets it to 0.75 times 2^d app. B. The code defaults to 32 and has no such rule lib_utils.py.
• Node cache. The paper says up to 48 nodes are kept in memory §3.5. The code default is 16 lib_utils.py.
• Learning rate. The paper selects from a grid of 0.05 to 0.5 app. B. The code default is 0.2 lib_utils.py, which is not in that grid.
• Early stopping. The paper stops after 25 rounds without improvement §5. The code default is 0, meaning off lib_utils.py parameters.rst. The 25-round setting is not in the repository.
• Restricted vs unrestricted. The parameter named one_side defaults to true, and that selects the single shared top-k queue, i.e. the paper's restricted variant booster.cpp booster.cpp. The name does not describe what it does; the unrestricted path is the other branch.
• Bins. The paper does not say how bin edges are chosen beyond "from the column distribution" §2.3. The code builds bins from the training column with roughly equal counts, and uses midpoints when there are few distinct values histogram.py. Bins are fixed after the first construction.
• Experiments. The paper's experiments are not in the repository. The examples use random data and 20 rounds test.py.

Pitfalls

• Missing children predict zero. A new node's child pointers default to 0, and prediction treats leaf index 0 as "no value", adding nothing tree.h tree.cpp. In build_tree_best, when the leaf budget is reached the function returns before handling the remaining sibling and the frontier nodes are not turned into leaves booster.cpp booster.cpp. Each child whose sample count is below the minimum is also never added booster.cpp booster.cpp. The same happens when a node cannot enter the bounded cache, because push then discards it dataStruct.h booster.cpp. By reading the code, samples routed into such a branch get zero from that tree. This was not run, and the paper does not describe it. Check before relying on deep trees.
• Node cache cap. The cache holds hist_cache entries, default 16, sorted by gain booster.h dataStruct.h. Raise it for large max_leaves, and remember the paper's 48-node value §3.5.
• Gain scale. The gain threshold is compared with the averaged gain, not the sum app. B booster.cpp. Using the paper's raw sum with the listed thresholds would change which splits are accepted.
• Diagonal approximation. The approximation is exact only when the Hessian is diagonal. The paper's bound carries a factor gamma that the code does not have app. A. Appendix A says gamma can be absorbed into the learning rate and lambda; if you port the paper's form with gamma, rescale the gain threshold to match. Table VIII shows the diagonal can lose accuracy on one dataset (Yeast: 62.29 against 62.89) and win on another (MNIST: 98.30 against 98.17).
• Sparse cost. Unrestricted sparse split finding needs two priority queues; the restricted one needs one §3.4. In the timing table, restricted is faster in every row except MNIST at k=2 (0.619 against 0.599) tab. VI.
• Convergence. The paper says the method converges more slowly, especially at the start of training §6. Compare against a fixed round count, not only the best round.
• Significance. The statistical test assumes Student's t on 10 random trials app. C. Some confidence values are close to 0.5 (for example GBDT-SO on Student-por: 0.561), and the Yeast value against XGBoost is 0.067 tab. XII.
• Tuning data. The paper does not say which data the grid search used, and says the fixed hyperparameters may not be optimal app. B. Treat the comparisons as tuned by the authors, not as untuned baselines.
• Labels. The Python examples pass classification labels as int32 and regression targets as float64 2-D arrays test.py.

Lineage

• Builds on: second-order gradient boosting as in XGBoost §2.2 §4; histogram split finding as in LightGBM §2.3 §4; the L0-constrained output selection of GBDT-sparse, changed to use second-order gradients and histograms §3.2 §4.
• Compared against: XGBoost, LightGBM, GBDT-sparse, and the paper's own single-output GBDT (GBDT-SO) §5.
• Superseded by: not known from content on this wiki.