xgboost’s New Fast Histogram (tree_method = hist)

Laurae: This post is about the new feature of xgboost: the histogram tree grow method. Currently, it provides error in R but works in Python (?). You can find the pull request #1940 here. I’ll get benchmarks on my customized Bosch data set when the R package works.


Summary from PR author

Add a brand new updater to support histogram-based algorithm, which buckets continuous features into discrete bins to speed up training. To use it, set tree_method=hist to configuration.

Support multiple tree growing strategies. For now, two policies are supported:

  • grow_policy=depthwise (default): favor splitting at nodes closest to the root, i.e. grow depth-wise.
  • grow_policy=lossguide: favor splitting at nodes with highest loss change

Improve single-threaded performance

  • Unroll critical loops
  • Introduce specialized code for dense data (i.e. no missing values)

Additional training parameters: max_leaves, max_bin, grow_policy, verbose


Extra comments by myself

I put this here for more details (could be useful to know what to add exactly for R/Python function descriptions, along with the conditions on the new parameters).

The new/edited fields:

  • Histogram method: must set tree_method to hist (3) - the tree updater becomes grow_fast_histmaker
  • Verbose flag: I guess, for the command line? (it prints timing and some other details, see the end for details) — to ignore for R/Python packages?
  • Maximum leaves: using max_leaves, with no limit (setting to 0 is same as infinite, automatically limited by max_depth)
  • Histogram binning: using max_bin with a value between 2 to 256 (restricted to 256 maximum for a 8-bit representation optimization)
  • Growing policy: using grow_policy, you have the choice between depthwise (split using depth) and lossguide (split using loss), see below for comparison between Depth / Loss:
inline static bool depth_wise(ExpandEntry lhs, ExpandEntry rhs) {
return lhs.depth > rhs.depth;
}
inline static bool loss_guide(ExpandEntry lhs, ExpandEntry rhs) {
return lhs.loss_chg < rhs.loss_chg;
}

Additional designs:

  • max_depth can be unlimited while max_leaves is limited only if not using a depth-wise growing policy
  • max_leaves can be unlimited while max_depth is limited
  • There are performance optimizations depending on 0-indexed dense data, 1-indexed dense data, or sparse data
  • gbtree does a batch of 8 instead of a batch of 1 to make predictions on single instances
  • Pre-initialize some variables
DMLC_DECLARE_FIELD(tree_method).set_default(0)
.add_enum("auto", 0)
.add_enum("approx", 1)
.add_enum("exact", 2)
.add_enum("hist", 3)
.describe("Choice of tree construction method.");
...
    DMLC_DECLARE_FIELD(verbose)
.set_lower_bound(0)
.set_default(0)
.describe(
"Setting verbose flag with a positive value causes the updater "
"to print out *detailed* list of tasks and their runtime");
...
    DMLC_DECLARE_FIELD(max_leaves).set_lower_bound(0).set_default(0).describe(
"Maximum number of leaves; 0 indicates no limit.");
DMLC_DECLARE_FIELD(max_bin).set_lower_bound(2).set_default(256).describe(
"if using histogram-based algorithm, maximum number of bins per feature");
DMLC_DECLARE_FIELD(grow_policy)
.set_default(kDepthWise)
.add_enum("depthwise", kDepthWise)
.add_enum("lossguide", kLossGuide)
.describe(
"Tree growing policy. 0: favor splitting at nodes closest to the node, "
"i.e. grow depth-wise. 1: favor splitting at nodes with highest loss "
"change. (cf. LightGBM)");

Logging details:

  • Initialize data
  • Setup nodes
  • Create histogram
  • Evaluate splits
  • Apply splits
  • Sum of all the time
LOG(INFO) << "\nInitData:          "
<< std::fixed << std::setw(4) << std::setprecision(2) << init_data
<< " (" << std::fixed << std::setw(5) << std::setprecision(2)
<< init_data/total_time*100 << "%)\n"
<< "InitNewNode: "
<< std::fixed << std::setw(4) << std::setprecision(2) << init_new_node
<< " (" << std::fixed << std::setw(5) << std::setprecision(2)
<< init_new_node/total_time*100 << "%)\n"
<< "MakeHist: "
<< std::fixed << std::setw(4) << std::setprecision(2) << make_hist
<< " (" << std::fixed << std::setw(5) << std::setprecision(2)
<< make_hist/total_time*100 << "%)\n"
<< "EvaluateSplit: "
<< std::fixed << std::setw(4) << std::setprecision(2) << evaluate_split
<< " (" << std::fixed << std::setw(5) << std::setprecision(2)
<< evaluate_split/total_time*100 << "%)\n"
<< "ApplySplit: "
<< std::fixed << std::setw(4) << std::setprecision(2) << apply_split
<< " (" << std::fixed << std::setw(5) << std::setprecision(2)
<< apply_split/total_time*100 << "%)\n"
<< "========================================\n"
<< "Total: "
<< std::fixed << std::setw(4) << std::setprecision(2) << total_time;

Does it work in R?

It does not (yet).

> temp_model <- xgb.train(data = data,
+ params = list(nthread = 12,
+ max_depth = 5,
+ eta = 1.0,
+ subsample = 1.0,
+ colsample_bytree = 1.0,
+ tree_method = ‘hist’,
+ grow_policy = ‘lossguide’,
+ booster = “gbtree”,
+ verbose = 1),
+ objective = “binary:logistic”,
+ nrounds = 5,
+ verbose = FALSE,
+ callbacks = list(cb.evaluation.log()))
[13:48:15] Tree method is selected to be ‘hist’, which uses histogram aggregation for faster training. Using default sequence of updaters: grow_fast_histmaker,prune
Error in xgb.iter.update(bst$handle, dtrain, iteration — 1, obj) :
[13:48:15] amalgamation/../src/tree/tree_updater.cc:18: Unknown tree updater grow_fast_histmaker

Does it work in Python?

It currently passes the test (Travis?), so it is supposedly working. See this test:

import xgboost as xgb
import testing as tm
import numpy as np
import unittest
rng = np.random.RandomState(1994)
class TestFastHist(unittest.TestCase):
def test_fast_hist(self):
tm._skip_if_no_sklearn()
from sklearn.datasets import load_digits
from sklearn.cross_validation import train_test_split
digits = load_digits(2)
X = digits[‘data’]
y = digits[‘target’]
X_train, X_test, y_train, y_test = train_test_split(X, y, random_state=0)
dtrain = xgb.DMatrix(X_train, y_train)
dtest = xgb.DMatrix(X_test, y_test)
param = {‘objective’: ‘binary:logistic’,
‘tree_method’: ‘hist’,
‘grow_policy’: ‘depthwise’,
‘max_depth’: 3,
‘eval_metric’: ‘auc’}
res = {}
bst = xgb.train(param, dtrain, 10, [(dtrain, ‘train’), (dtest, ‘test’)],
evals_result=res)
assert self.non_decreasing(res[‘train’][‘auc’])
assert self.non_decreasing(res[‘test’][‘auc’])
param2 = {‘objective’: ‘binary:logistic’,
‘tree_method’: ‘hist’,
‘grow_policy’: ‘lossguide’,
‘max_depth’: 0,
‘max_leaves’: 8,
‘eval_metric’: ‘auc’}
res = {}
bst = xgb.train(param2, dtrain, 10, [(dtrain, ‘train’), (dtest, ‘test’)],
evals_result=res)
assert self.non_decreasing(res[‘train’][‘auc’])
assert self.non_decreasing(res[‘test’][‘auc’])
param3 = {‘objective’: ‘binary:logistic’,
‘tree_method’: ‘hist’,
‘grow_policy’: ‘lossguide’,
‘max_depth’: 0,
‘max_leaves’: 8,
‘max_bin’: 16,
‘eval_metric’: ‘auc’}
res = {}
bst = xgb.train(param3, dtrain, 10, [(dtrain, ‘train’), (dtest, ‘test’)],
evals_result=res)
assert self.non_decreasing(res[‘train’][‘auc’])
assert self.non_decreasing(res[‘test’][‘auc’])

def non_decreasing(self, L):
return all(x<=y for x, y in zip(L, L[1:]))
One clap, two clap, three clap, forty?

By clapping more or less, you can signal to us which stories really stand out.