This issue is to document a series of recent improvements in the tree grower. Related: #1673.

Faster training via feature binning

Histogram aggregation is a major computational bottleneck in tree growing. We introduce a new tree growing method hist where only a subset of possible split values are considered. As in FastBDT and LightGBM, continuous features are bucketed into discrete bins. The histogram accumulation becomes faster due to less index manipulations

How does the new method differ from tree_method=approx? The existing approximate splitting method in xgboost also buckets continuous features into discrete bins to speed up training. The approx method generates a new set of bins for each iteration, whereas the hist method re-uses the bins over multiple iterations.

The latter approach enables additional optimizations that are not possible for the former, as follows:

• Cache of the bins : replace continuous feature values in the training data with bin IDs and cache the data structure
• Histogram subtraction trick: to compute the histogram for a node, we simply take the difference between the histograms for its parent and sibling.

Besides the above improvements, some highlights

• Efficient representation of sparse matrices as in xgboost, sparse matrices is supported naturally, with effective speedup for mixed sparse+dense matrices
• Extensible to other existing features in xgboost such as monotonic constraints, language bindings.

How to use

Simply set tree_method to hist. You may also want to set max_bin, which represents the (maximum) number of discrete bins to bucket continuous features. By default, max_bin is set to 256. Increasing this number improves the optimality of splits at the cost of higher computation time.

Flexible tree growing policies

The existing tree grower in xgboost grows a tree in a depth-wise fashion, executing splits in first level before splits in second and so forth. The new grower lets you control the way new nodes are added to the tree:

• grow_policy=depthwise (default): split at nodes closest to the root, i.e. grow depth-wise.
• grow_policy=lossguide: split at nodes with highest loss change. This behavior mimics that of LightGBM.

It has been reported that the lossguide policy often results in faster convergence in loss, though there is also risk of over-fitting(see the preliminary results).

How to use

For now, only the hist grower supports multiple growing policies; we may extend the support to other growers in the future. So you should set tree_method to hist. The grow_policy parameters lets you select the growing policy. If unspecified, grow_policy will be set to depthwise by default. Here are two parameters that are relevant:

• max_leaves: maximum number of nodes to be added. Only relevant for the lossguide policy.
• max_depth: maximum depth. Behaves as usual when grow_policy is set to depthwise. If grow_policy is lossguide, max_depth can be set to zero, indicating the lack of limit on depth.

Benchmark

Configurations

• CPU: Intel(R) Core(TM) i7-6850K CPU @ 3.60GHz, 6 physical cores
• Memory: 48 GB
• Training parameters: Evaluation metric is turn on during the benchmark, since that is how users commonly use the code
  • exact: tree_method=exact, eta=0.1, gamma=1.0, max_depth=8, min_child_weight=100
  • approx: tree_method=approx, eta=0.1, gamma=1.0, max_depth=8, min_child_weight=100
  • hist + depthwise: tree_method=hist, grow_policy=depthwise, eta=0.1, gamma=1.0, max_depth=8, min_child_weight=100
  • hist + lossguide: tree_method=hist, grow_policy=lossguide, eta=0.1, gamma=1.0, max_depth=0, max_leaves=255, min_child_weight=100
  • LightGBM: learning_rate=0.1, max_bin=255, num_leaves=255, min_sum_hessian_in_leaf=100, min_data_in_leaf=0

Model accuracy

For allstate and higgs, we plot AUC (Area Under Curve) on the validation set. For yahoo, we plot NDCG (Normalized Discounted Cumulative Gain) at 10.

Notice that favoring splits with highest change leads to overfitting in the case of allstate, which is more like a real world insurance dataset. While the validation training curve is more consistent on higgs, which is simulated data points.
We tried different options such as min_child_weight didn't move the curve much. This seems to suggest that depthwise is more conservative and more robust to overfitting and should be used when the training validation distribution might not be very identical, or overfitting is a problem in the dataset

Single-threaded performance

Keep in mind that the tree growing policy of LightGBM is equivalent to setting grow_policy=lossguide in xgboost, so LightGBM column should be compared with hist + lossguide column.

Per-iteration runtime (seconds)
The average was taken over 300 iterations.

Cumulative runtime over 300 iterations

Multi-threaded performance, not yet fully optimized,

Parallel implementation of tree_method=hist needs more work, for the time being.

Per-iteration runtime (seconds)

Cumulative runtime over 300 iterations