XGBoost (5) C++ 命令行训练源码分析
回顾与本文目标
前一篇文章（第 4 篇）中，我们在命令行接口模式下运行 XGBoost 成功。在第 3 篇中，我们在 Python 接口下运行了 XGBoost，并且分析了其中的 PredictRaw 函数。但这里的代码读得有点乱。所以我会想到打算从头开始，一个一个函数解释代码是如何运行的。但事后发现，这件事情是不是特别容易的一件事情，如果强行这样做会让整篇文章显得异常冗长，从而丧失了写文章的意义。
所以，我打算把自己理解下来的部分先贴在前面。分割线之后的是细节部分。如果需要用到再去查阅即可。
小结
整个训练的过程的 大致逻辑 如下：
- 首先需要定义问题：训练数据集是什么？测试数据集是什么？中间评判的准则是什么？训练时的目标函数是什么？迭代更新的参数是什么？（这两个问题决定了迭代法求解优化问题的具体格式。）这些设置都存于配置文件中，程序第一步是读取 配置 (conf)，然后转存为 参数 (param)
- 根据参数，把该读的数据文件载入 学习器 (leaner)，然后初始化模型，开始准备训练。
- 由于模型是生长模式的，生长的次数是
num_round。生长出的模型可以是线性模型（GBLinear）也可以是决策树（GBTree）无论如何，外层循环是使得模型不断生长的循环，在CLITrain()函数中调用。 - 每一个循环的实现者是
UpdateOneIter()。这里的一个循环执行完之后，模型数量就会 +1 （对一个输出的情形，如有 N 个输出，模型数量会 +N，to be verified, 没有试过，欢迎批评指正）。主要做三步，第一步：求模型当前的函数值。第二步，求一阶导数、二阶导数。第三步，生长模型。注: 这里容易让人费解的是代码中的函数名：
grad和hess看上去像梯度和 Hessian。第一反应很有可能是：诶，这两个东西，一个是向量一个是矩阵？对 个数据点和 个输出，莫非这两个变量是三阶、四阶张量？但实际上，是目标函数关于第二个变量 的一阶导数和二阶导数，都是标量，结合上数据点和输出的维度，两个量都是矩阵。 - 对树模型，第三步主要是找最适当的分割点。实践中，算法主要实现了 Algorithm 3 的算法（而非）
注: 这里容易让人不解的是分割 Algorithm 2。默认情况下没有执行这个算法。
一些实现时的一开始不太让人理解的技巧：
- 分割点存于
sindex_中。这个变量有点变态，定义在RegTree里，是一个unsigned类型的变量。这个变量实际上复合了两个信息。第一是分割的输入向量（或者叫特征向量）的序号。由于unsigned是 32 位的，这里实际上用了后面 31 位，保存这个序号。而第一位是用来保存 左分割 还是 右分割。 - 在树模型中，每一棵树的叶片最终算出一个得分。所有得分累加，得出总得分。如果是回归问题，那就可以直接和真实结果进行比对。如果是二元分类问题，那还要在最外层作用 sigmoid 函数，最后再计算交叉熵得到目标函数（误差）。（这实际上应该是 logistic 回归的基础知识，但放在这个语境下，有时候会忘掉目标函数是怎么被求出来的）。
下面还能看看的，可能只有两张图了，请看官随意翻阅。
谢谢观赏！
起点 main() @ src/cli_main.cc
int main(int argc, char *argv[]) {
return xgboost::CLIRunTask(argc, argv);
}
这是程序的入口。作为我们的例子，argc 显然是 2，argv 是两个字符串：xgboost 文件的路径全称和配置文件 mushroom.conf。这个函数会调用 CLIRunTask() 就在主函数上方。
通过命令行接口执行任务 CLIRunTask() @ src/cli_main.cc
int CLIRunTask(int argc, char *argv[]) {
if (argc < 2) {
printf("Usage: <config>\n");
return 0;
}
rabit::Init(argc, argv);
std::vector<std::pair<std::string, std::string> > cfg;
cfg.emplace_back("seed", "0");
common::ConfigIterator itr(argv[1]);
while (itr.Next()) {
cfg.emplace_back(std::string(itr.Name()), std::string(itr.Val()));
}
for (int i = 2; i < argc; ++i) {
char name[256], val[256];
if (sscanf(argv[i], "%[^=]=%s", name, val) == 2) {
cfg.emplace_back(std::string(name), std::string(val));
}
}
CLIParam param;
param.Configure(cfg);
switch (param.task) {
case kTrain: CLITrain(param); break;
case kDumpModel: CLIDumpModel(param); break;
case kPredict: CLIPredict(param); break;
}
rabit::Finalize();
return 0;
}
这个函数甚至于可以直接和主函数合并。如果写出它的中文伪代码，可以是：
- 如果输入没有参数，那么就打印一句提示，并且直接返回。
- 调用并行环境的构造函数
- 定义 配置变量，类似于一个字典
- 第一个成员：
{种子:零}1。 - 再定义一个 配置循环体，以 配置文件名 初始化。
- 做循环，直到配置循环体没有下一个，把信息（名字、值）都传入配置变量
- 然后把文件外配置存入配置变量中。
- 第一个成员：
- 定义 参数变量
- 把配置变量存入参数变量
- 根据参数中的任务值执行任务，有三种选择：训练
0[TODO]、导出1、预测2 - 最后调用并行环境的析构函数
在默认的情况下，param的task是零，因此对应训练。
命令行训练任务 CLITrain() @ src/cli_main.cc
void CLITrain(const CLIParam& param) {
const double tstart_data_load = dmlc::GetTime();
if (rabit::IsDistributed()) {
std::string pname = rabit::GetProcessorName();
LOG(CONSOLE) << "start " << pname << ":" << rabit::GetRank();
}
// load in data.
std::shared_ptr<DMatrix> dtrain(
DMatrix::Load(
param.train_path,
ConsoleLogger::GlobalVerbosity() > ConsoleLogger::DefaultVerbosity(),
param.dsplit == 2));
std::vector<std::shared_ptr<DMatrix> > deval;
std::vector<std::shared_ptr<DMatrix> > cache_mats;
std::vector<DMatrix*> eval_datasets;
cache_mats.push_back(dtrain);
for (size_t i = 0; i < param.eval_data_names.size(); ++i) {
deval.emplace_back(
std::shared_ptr<DMatrix>(DMatrix::Load(
param.eval_data_paths[i],
ConsoleLogger::GlobalVerbosity() > ConsoleLogger::DefaultVerbosity(),
param.dsplit == 2)));
eval_datasets.push_back(deval.back().get());
cache_mats.push_back(deval.back());
}
std::vector<std::string> eval_data_names = param.eval_data_names;
if (param.eval_train) {
eval_datasets.push_back(dtrain.get());
eval_data_names.emplace_back("train");
}
// initialize the learner.
std::unique_ptr<Learner> learner(Learner::Create(cache_mats));
int version = rabit::LoadCheckPoint(learner.get());
if (version == 0) {
// initialize the model if needed.
if (param.model_in != "NULL") {
std::unique_ptr<dmlc::Stream> fi(
dmlc::Stream::Create(param.model_in.c_str(), "r"));
learner->Load(fi.get());
learner->Configure(param.cfg);
} else {
learner->Configure(param.cfg);
learner->InitModel();
}
}
LOG(INFO) << "Loading data: " << dmlc::GetTime() - tstart_data_load << " sec";
// start training.
const double start = dmlc::GetTime();
for (int i = version / 2; i < param.num_round; ++i) {
double elapsed = dmlc::GetTime() - start;
if (version % 2 == 0) {
LOG(INFO) << "boosting round " << i << ", " << elapsed << " sec elapsed";
learner->UpdateOneIter(i, dtrain.get());
if (learner->AllowLazyCheckPoint()) {
rabit::LazyCheckPoint(learner.get());
} else {
rabit::CheckPoint(learner.get());
}
version += 1;
}
CHECK_EQ(version, rabit::VersionNumber());
std::string res = learner->EvalOneIter(i, eval_datasets, eval_data_names);
if (rabit::IsDistributed()) {
if (rabit::GetRank() == 0) {
LOG(TRACKER) << res;
}
} else {
LOG(CONSOLE) << res;
}
if (param.save_period != 0 &&
(i + 1) % param.save_period == 0 &&
rabit::GetRank() == 0) {
std::ostringstream os;
os << param.model_dir << '/'
<< std::setfill('0') << std::setw(4)
<< i + 1 << ".model";
std::unique_ptr<dmlc::Stream> fo(
dmlc::Stream::Create(os.str().c_str(), "w"));
learner->Save(fo.get());
}
if (learner->AllowLazyCheckPoint()) {
rabit::LazyCheckPoint(learner.get());
} else {
rabit::CheckPoint(learner.get());
}
version += 1;
CHECK_EQ(version, rabit::VersionNumber());
}
// always save final round
if ((param.save_period == 0 || param.num_round % param.save_period != 0) &&
param.model_out != "NONE" &&
rabit::GetRank() == 0) {
std::ostringstream os;
if (param.model_out == "NULL") {
os << param.model_dir << '/'
<< std::setfill('0') << std::setw(4)
<< param.num_round << ".model";
} else {
os << param.model_out;
}
std::unique_ptr<dmlc::Stream> fo(
dmlc::Stream::Create(os.str().c_str(), "w"));
learner->Save(fo.get());
}
double elapsed = dmlc::GetTime() - start;
LOG(INFO) << "update end, " << elapsed << " sec in all";
}
代码挺长的。伪代码如下：
- 读取数据部分
- 记录时间起点
- 如果分布式运行，那记录进程名和进程编号
- 定义 训练集 、 验证集类 、 缓冲集类 变量、 评价集类 变量
- 在缓冲集类中加入训练集
- 根据参数中的数据集名称读取数据集，并保存到验证、缓冲、和评价集类中
- 定义 评价数据集的所有名称 从参数中拿取
- 如果需要评价训练集，则在评价集类的最后加上训练集，
- 根据缓冲集类，定义 学习器
- 根据学习器，读取存档点，返回 版本值。
- 如果版本值为零，则查看是否有输入模型
- 如果有输入模型，则读取之，并且载入学习器。
- 如果没有，则把配置存入学习器，并且初始化模型。
- 打印日志，读取数据完成。
- 训练部分
- 获取起始时间
- 从 版本值的一半 开始循环，直到 训练最大轮数。
- 获取逝去时间
- 如果版本值是偶数
- 打印日志：“第 轮生长 Boosting，已经过去了多少时间”
- 更新一次迭代 [
TODO] - 进入存档点
- 版本值加一
- 检查版本值和并行环境版本值是否一致
- 评价一个迭代
- 分别讨论分布式和单机情形，输出日志：评价结果
- 如果有周期性保存指标，则保存模型，格式是
[四维迭代数].model，如0002.model。 - 进入存档点
- 版本值加一
- 检查版本值和并行环境版本值是否一致
- 保存最后一轮模型，
model_out是自定义的模型输出名称。 - 打印日志，更新完成
小结一下：
- 这段代码就是建立了一个循环，然后调用了更新一次迭代。
- 函数支持 “断点续传功能”，“保存中间结果功能”
更新一次迭代 LearnerImpl::UpdateOneIter() @ src/learner.cc
void UpdateOneIter(int iter, DMatrix* train) override {
monitor_.Start("UpdateOneIter");
CHECK(ModelInitialized())
<< "Always call InitModel or LoadModel before update";
if (tparam_.seed_per_iteration || rabit::IsDistributed()) {
common::GlobalRandom().seed(tparam_.seed * kRandSeedMagic + iter);
}
this->PerformTreeMethodHeuristic(train);
monitor_.Start("PredictRaw");
this->PredictRaw(train, &preds_);
monitor_.Stop("PredictRaw");
monitor_.Start("GetGradient");
obj_->GetGradient(preds_, train->Info(), iter, &gpair_);
monitor_.Stop("GetGradient");
gbm_->DoBoost(train, &gpair_, obj_.get());
monitor_.Stop("UpdateOneIter");
}
我们直接写代码小结：
- 检查模型是否初始化
- 根据迭代数随机化随机数种子
- 执行树方法的启发式步骤 [HOLD]
- 求预测值 [
TODO] - 求梯度 [
TODO] - 进行生长 [
TODO]
求预测值 LearnerImpl::PredictRaw() @ src/learner.cc
inline void PredictRaw(DMatrix* data, HostDeviceVector<bst_float>* out_preds,
unsigned ntree_limit = 0) const {
CHECK(gbm_ != nullptr)
<< "Predict must happen after Load or InitModel";
gbm_->PredictBatch(data, out_preds, ntree_limit);
}
这个函数很简单
- 检查模型是否已经初始化
- 调用 模型的批量预测函数 [
TODO]
模型的批量预测函数 GBTree::PredictBatch() @ src/gbm/gbtree.cc
void PredictBatch(DMatrix* p_fmat,
HostDeviceVector<bst_float>* out_preds,
unsigned ntree_limit) override {
predictor_->PredictBatch(p_fmat, out_preds, model_, 0, ntree_limit);
}
这个函数更简单
- 调用 预测子的批量预测函数 [
TODO]
预测子的批量预测函数 CPUPredictor::PredictBatch() @ src/predictor/predictor.cc
void PredictBatch(DMatrix* dmat, HostDeviceVector<bst_float>* out_preds,
const gbm::GBTreeModel& model, int tree_begin,
unsigned ntree_limit = 0) override {
if (this->PredictFromCache(dmat, out_preds, model, ntree_limit)) {
return;
}
this->InitOutPredictions(dmat->Info(), out_preds, model);
ntree_limit *= model.param.num_output_group;
if (ntree_limit == 0 || ntree_limit > model.trees.size()) {
ntree_limit = static_cast<unsigned>(model.trees.size());
}
this->PredLoopInternal(dmat, &out_preds->HostVector(), model,
tree_begin, ntree_limit);
}
- 如果已经有了缓存，那直接读取
-
预测子的初始化预测值 [
TODO] - 树的极限数量 放大 输出组数 倍
- 如果树的极限数量为零，或者大于模型的树的棵数，则把极限数量设为模型中树的棵数
-
预测子的预测循环内部 [
TODO]
预测子的初始化预测值 CPUPredictor::InitOutPredictions() @ src/predictor/predictor.cc
void InitOutPredictions(const MetaInfo& info,
HostDeviceVector<bst_float>* out_preds,
const gbm::GBTreeModel& model) const {
size_t n = model.param.num_output_group * info.num_row_;
const auto& base_margin = info.base_margin_.HostVector();
out_preds->Resize(n);
std::vector<bst_float>& out_preds_h = out_preds->HostVector();
if (base_margin.size() == n) {
CHECK_EQ(out_preds->Size(), n);
std::copy(base_margin.begin(), base_margin.end(), out_preds_h.begin());
} else {
if (!base_margin.empty()) {
std::ostringstream oss;
oss << "Warning: Ignoring the base margin, since it has incorrect length. "
<< "The base margin must be an array of length ";
if (model.param.num_output_group > 1) {
oss << "[num_class] * [number of data points], i.e. "
<< model.param.num_output_group << " * " << info.num_row_
<< " = " << n << ". ";
} else {
oss << "[number of data points], i.e. " << info.num_row_ << ". ";
}
oss << "Instead, all data points will use "
<< "base_score = " << model.base_margin;
LOG(INFO) << oss.str();
}
std::fill(out_preds_h.begin(), out_preds_h.end(), model.base_margin);
}
}
- 预测值数组大小是：数据集行数 乘以 输出组数。
- 如果数据集有基础偏移，则将其填充到输出中。
预测子的预测循环内部 CPUPredictor::PredLoopInternal() @ src/predictor/predictor.cc
void PredLoopInternal(DMatrix* dmat, std::vector<bst_float>* out_preds,
const gbm::GBTreeModel& model, int tree_begin,
unsigned ntree_limit) {
// TODO(Rory): Check if this specialisation actually improves performance
PredLoopSpecalize(dmat, out_preds, model, model.param.num_output_group,
tree_begin, ntree_limit);
}
这个代码也没有办法更简单了
-
预测子的预测特殊循环 [
TODO]
预测子的预测特殊循环 CPUPredictor::PredLoopSpecalize() @ src/predictor/predictor.cc
inline void PredLoopSpecalize(DMatrix* p_fmat,
std::vector<bst_float>* out_preds,
const gbm::GBTreeModel& model, int num_group,
unsigned tree_begin, unsigned tree_end) {
const MetaInfo& info = p_fmat->Info();
const int nthread = omp_get_max_threads();
InitThreadTemp(nthread, model.param.num_feature);
std::vector<bst_float>& preds = *out_preds;
CHECK_EQ(model.param.size_leaf_vector, 0)
<< "size_leaf_vector is enforced to 0 so far";
CHECK_EQ(preds.size(), p_fmat->Info().num_row_ * num_group);
// start collecting the prediction
for (const auto &batch : p_fmat->GetRowBatches()) {
// parallel over local batch
constexpr int kUnroll = 8;
const auto nsize = static_cast<bst_omp_uint>(batch.Size());
const bst_omp_uint rest = nsize % kUnroll;
#pragma omp parallel for schedule(static)
for (bst_omp_uint i = 0; i < nsize - rest; i += kUnroll) {
const int tid = omp_get_thread_num();
RegTree::FVec& feats = thread_temp[tid];
int64_t ridx[kUnroll];
SparsePage::Inst inst[kUnroll];
for (int k = 0; k < kUnroll; ++k) {
ridx[k] = static_cast<int64_t>(batch.base_rowid + i + k);
}
for (int k = 0; k < kUnroll; ++k) {
inst[k] = batch[i + k];
}
for (int k = 0; k < kUnroll; ++k) {
for (int gid = 0; gid < num_group; ++gid) {
const size_t offset = ridx[k] * num_group + gid;
preds[offset] += this->PredValue(
inst[k], model.trees, model.tree_info, gid,
info.GetRoot(ridx[k]), &feats, tree_begin, tree_end);
}
}
}
for (bst_omp_uint i = nsize - rest; i < nsize; ++i) {
RegTree::FVec& feats = thread_temp[0];
const auto ridx = static_cast<int64_t>(batch.base_rowid + i);
auto inst = batch[i];
for (int gid = 0; gid < num_group; ++gid) {
const size_t offset = ridx * num_group + gid;
preds[offset] +=
this->PredValue(inst, model.trees, model.tree_info, gid,
info.GetRoot(ridx), &feats, tree_begin, tree_end);
}
}
}
}
- 循环每一个行批次
- 对每一行批次，每八个一组，用 OpenMP，求预测值 [
TODO] - 批次中多余的行，单线程进行操作
- 对每一行批次，每八个一组，用 OpenMP，求预测值 [
预测值的输入是：
- 实例 :: 这里的实例源于批次，批次源于训练数据，可以理解成是 训练数据中的某一个样本点。这里的实例源于批次，批次源于训练数据，可以理解成是训练数据中的某一个样本点。
-
模型中的所有树 :: 模型是一片森林。森林是分组的，由一片一片 小森林 组成，分组标准根据输出决定（因为输出可以是向量的），每一片小森林对应输出的一个分量。（在输出为标量时，自然只有一片小森林。）每一片小森林里都有若干棵决策树。 如下图所示：
- 模型的树信息 :: 存放着每一棵树的分组信息。
- 组编号 :: 小森林的序号。
- 根节点 :: 训练数据中，每一个样本可以有一个预先定义好的 起始根节点。如果没有指定，那就从根节点出发。
- 回归树的特征向量 :: 把实例特征向量化的容器，用于取出决策树的节点值。这里的想法是把稀疏的输入向量稠密化。
- 树起始编号
- 树结束编号
预测子的预测特殊循环 CPUPredictor::PredValue() @ src/predictor/predictor.cc
static bst_float PredValue(const SparsePage::Inst& inst,
const std::vector<std::unique_ptr<RegTree>>& trees,
const std::vector<int>& tree_info, int bst_group,
unsigned root_index, RegTree::FVec* p_feats,
unsigned tree_begin, unsigned tree_end) {
bst_float psum = 0.0f;
p_feats->Fill(inst);
for (size_t i = tree_begin; i < tree_end; ++i) {
if (tree_info[i] == bst_group) {
int tid = trees[i]->GetLeafIndex(*p_feats, root_index);
psum += (*trees[i])[tid].LeafValue();
}
}
p_feats->Drop(inst);
return psum;
}
- 调用 回归树特征向量的填充方法，把数据填入特征向量
- 遍历所有树符合要求的树
- 获取叶片指标
- 累加叶片值
- 调用 回归树特征向量的丢弃方法，清空特征向量
特征向量与树直接的相互作用过程如下图所示：
求导数 GetGradient() @ src/objective/regression_obj.cu
void GetGradient(const HostDeviceVector<bst_float>& preds,
const MetaInfo &info,
int iter,
HostDeviceVector<GradientPair>* out_gpair) override {
CHECK_NE(info.labels_.Size(), 0U) << "label set cannot be empty";
CHECK_EQ(preds.Size(), info.labels_.Size())
<< "labels are not correctly provided"
<< "preds.size=" << preds.Size() << ", label.size=" << info.labels_.Size();
size_t ndata = preds.Size();
out_gpair->Resize(ndata);
label_correct_.Fill(1);
bool is_null_weight = info.weights_.Size() == 0;
auto scale_pos_weight = param_.scale_pos_weight;
common::Transform<>::Init(
[=] XGBOOST_DEVICE(size_t _idx,
common::Span<int> _label_correct,
common::Span<GradientPair> _out_gpair,
common::Span<const bst_float> _preds,
common::Span<const bst_float> _labels,
common::Span<const bst_float> _weights) {
bst_float p = Loss::PredTransform(_preds[_idx]);
bst_float w = is_null_weight ? 1.0f : _weights[_idx];
bst_float label = _labels[_idx];
if (label == 1.0f) {
w *= scale_pos_weight;
}
if (!Loss::CheckLabel(label)) {
// If there is an incorrect label, the host code will know.
_label_correct[0] = 0;
}
_out_gpair[_idx] = GradientPair(Loss::FirstOrderGradient(p, label) * w,
Loss::SecondOrderGradient(p, label) * w);
},
common::Range{0, static_cast<int64_t>(ndata)}, devices_).Eval(
&label_correct_, out_gpair, &preds, &info.labels_, &info.weights_);
// copy "label correct" flags back to host
std::vector<int>& label_correct_h = label_correct_.HostVector();
for (auto const flag : label_correct_h) {
if (flag == 0) {
LOG(FATAL) << Loss::LabelErrorMsg();
}
}
}
- 初始化梯度对数组
- 循环，求梯度和 Hessian
- 求预测值的“概率”，以供下面两个函数使用 [
TODO] - 求梯度 [
TODO] - 求 Hessian
- 求预测值的“概率”，以供下面两个函数使用 [
求预测值的“概率” Loss::PredTransform() @ src/objective/regression_loss.h
template <typename T>
static T PredTransform(T x) { return common::Sigmoid(x); }
这里比较容易搞糊涂的地方在于, 调用的时候，输入的是叶片值的总和，变量名叫 preds。而输出是 p，这是属于某一个类别的概率，而不是预测值。更容易与下面的函数变量名混淆：
一阶导数 Loss::FirstOrderGradient() @ src/objective/regression_loss.h
template <typename T>
static T FirstOrderGradient(T predt, T label) { return predt - label; }
这里其实输入是的概率，所以变量名是 predt。它不是 predict 的缩写，而是 predict transformed` 的缩写。为什么“一阶导数”是预测概率和标签之间的差呢？更要命的是，一阶导数为什么是一个标量呢？参考此文 就会发现，其实这里保存了一阶导数和 Hessian 的 “系数”。那么既然是系数，那就有原始向量（或矩阵）。这时分别为： 和 。
这里的实现方式真是 fancy，一定要放到头文件里去。还请高手指点我一下为什么一定要这么绕？
进行生长 GBTree::DoBoost() @ src/gbm/gbtree.cc
void DoBoost(DMatrix* p_fmat,
HostDeviceVector<GradientPair>* in_gpair,
ObjFunction* obj) override {
std::vector<std::vector<std::unique_ptr<RegTree> > > new_trees;
const int ngroup = model_.param.num_output_group;
monitor_.Start("BoostNewTrees");
if (ngroup == 1) {
std::vector<std::unique_ptr<RegTree> > ret;
BoostNewTrees(in_gpair, p_fmat, 0, &ret);
new_trees.push_back(std::move(ret));
} else {
CHECK_EQ(in_gpair->Size() % ngroup, 0U)
<< "must have exactly ngroup*nrow gpairs";
// TODO(canonizer): perform this on GPU if HostDeviceVector has device set.
HostDeviceVector<GradientPair> tmp
(in_gpair->Size() / ngroup, GradientPair(),
GPUDistribution::Block(in_gpair->Distribution().Devices()));
const auto& gpair_h = in_gpair->ConstHostVector();
auto nsize = static_cast<bst_omp_uint>(tmp.Size());
for (int gid = 0; gid < ngroup; ++gid) {
std::vector<GradientPair>& tmp_h = tmp.HostVector();
#pragma omp parallel for schedule(static)
for (bst_omp_uint i = 0; i < nsize; ++i) {
tmp_h[i] = gpair_h[i * ngroup + gid];
}
std::vector<std::unique_ptr<RegTree> > ret;
BoostNewTrees(&tmp, p_fmat, gid, &ret);
new_trees.push_back(std::move(ret));
}
}
monitor_.Stop("BoostNewTrees");
monitor_.Start("CommitModel");
this->CommitModel(std::move(new_trees));
monitor_.Stop("CommitModel");
}
- 首先申请新的树
- 如果输出是标量，则调用 生长新树林 [
TODO] - 否则并行调用生长新树
- 最后保存模型
生长新树林 GBTree::BoostNewTrees() @ src/gbm/gbtree.cc
inline void BoostNewTrees(HostDeviceVector<GradientPair>* gpair,
DMatrix *p_fmat,
int bst_group,
std::vector<std::unique_ptr<RegTree> >* ret) {
this->InitUpdater();
std::vector<RegTree*> new_trees;
ret->clear();
// create the trees
for (int i = 0; i < tparam_.num_parallel_tree; ++i) {
if (tparam_.process_type == kDefault) {
// create new tree
std::unique_ptr<RegTree> ptr(new RegTree());
ptr->param.InitAllowUnknown(this->cfg_);
new_trees.push_back(ptr.get());
ret->push_back(std::move(ptr));
} else if (tparam_.process_type == kUpdate) {
CHECK_LT(model_.trees.size(), model_.trees_to_update.size());
// move an existing tree from trees_to_update
auto t = std::move(model_.trees_to_update[model_.trees.size() +
bst_group * tparam_.num_parallel_tree + i]);
new_trees.push_back(t.get());
ret->push_back(std::move(t));
}
}
// update the trees
for (auto& up : updaters_) {
up->Update(gpair, p_fmat, new_trees);
}
}
- 初始化更新器
- 循环所有并行树：
- 如果是默认执行模式，则新建一棵树
- 如果是更新执行模型，则读取需要更新的树
- 调用 按列生成的更新函数 [
TODO]
按列生成的更新函数 ColMaker::Update @ src/tree/updater_colmaker.cc
void Update(HostDeviceVector<GradientPair> *gpair,
DMatrix* dmat,
const std::vector<RegTree*> &trees) override {
// rescale learning rate according to size of trees
float lr = param_.learning_rate;
param_.learning_rate = lr / trees.size();
// build tree
for (auto tree : trees) {
Builder builder(
param_,
std::unique_ptr<SplitEvaluator>(spliteval_->GetHostClone()));
builder.Update(gpair->ConstHostVector(), dmat, tree);
}
param_.learning_rate = lr;
}
- 修改参数中的学习率
- 对每一棵树定义一个建造器 [TODO]
- 调用建造器的更新函数 [
TODO] - 复原参数中的学习率
建造器的更新函数 Builder::Update @ src/tree/updater_colmaker.cc
virtual void Update(const std::vector<GradientPair>& gpair,
DMatrix* p_fmat,
RegTree* p_tree) {
std::vector<int> newnodes;
this->InitData(gpair, *p_fmat, *p_tree);
this->InitNewNode(qexpand_, gpair, *p_fmat, *p_tree);
for (int depth = 0; depth < param_.max_depth; ++depth) {
this->FindSplit(depth, qexpand_, gpair, p_fmat, p_tree);
this->ResetPosition(qexpand_, p_fmat, *p_tree);
this->UpdateQueueExpand(*p_tree, qexpand_, &newnodes);
this->InitNewNode(newnodes, gpair, *p_fmat, *p_tree);
for (auto nid : qexpand_) {
if ((*p_tree)[nid].IsLeaf()) {
continue;
}
int cleft = (*p_tree)[nid].LeftChild();
int cright = (*p_tree)[nid].RightChild();
spliteval_->AddSplit(nid,
cleft,
cright,
snode_[nid].best.SplitIndex(),
snode_[cleft].weight,
snode_[cright].weight);
}
qexpand_ = newnodes;
// if nothing left to be expand, break
if (qexpand_.size() == 0) break;
}
// set all the rest expanding nodes to leaf
for (const int nid : qexpand_) {
(*p_tree)[nid].SetLeaf(snode_[nid].weight * param_.learning_rate);
}
// remember auxiliary statistics in the tree node
for (int nid = 0; nid < p_tree->param.num_nodes; ++nid) {
p_tree->Stat(nid).loss_chg = snode_[nid].best.loss_chg;
p_tree->Stat(nid).base_weight = snode_[nid].weight;
p_tree->Stat(nid).sum_hess = static_cast<float>(snode_[nid].stats.sum_hess);
}
}
- 初始化数据 [TODO]
- 初始化新节点 [TODO]
- 对每一个深度循环
- 找出分割点 [TODO]
- 重置位置 [TODO]
- 更新节点扩张队列 [TODO]
- 初始化新节点
- 对所有队列中的元素
- 如果是叶片，则跳过
- 增加分割 [TODO]
- 扩张队列设为新节点
- 如果扩张队列为空，则结束循环
- 对每一个扩张队列的元素，设置叶片 [TODO]
- 对树中所有节点
- 更新损失变更
- 更新基础权重
- 更新 Hessian 和
总体上来说，就是一层一层把树长起来。
初始化数据 Builder::InitData @ src/tree/updater_colmaker.cc
inline void InitData(const std::vector<GradientPair>& gpair,
const DMatrix& fmat,
const RegTree& tree) {
CHECK_EQ(tree.param.num_nodes, tree.param.num_roots)
<< "ColMaker: can only grow new tree";
const std::vector<unsigned>& root_index = fmat.Info().root_index_;
{
// setup position
position_.resize(gpair.size());
CHECK_EQ(fmat.Info().num_row_, position_.size());
if (root_index.size() == 0) {
std::fill(position_.begin(), position_.end(), 0);
} else {
for (size_t ridx = 0; ridx < position_.size(); ++ridx) {
position_[ridx] = root_index[ridx];
CHECK_LT(root_index[ridx], (unsigned)tree.param.num_roots);
}
}
// mark delete for the deleted datas
for (size_t ridx = 0; ridx < position_.size(); ++ridx) {
if (gpair[ridx].GetHess() < 0.0f) position_[ridx] = ~position_[ridx];
}
// mark subsample
if (param_.subsample < 1.0f) {
std::bernoulli_distribution coin_flip(param_.subsample);
auto& rnd = common::GlobalRandom();
for (size_t ridx = 0; ridx < position_.size(); ++ridx) {
if (gpair[ridx].GetHess() < 0.0f) continue;
if (!coin_flip(rnd)) position_[ridx] = ~position_[ridx];
}
}
}
{
column_sampler_.Init(fmat.Info().num_col_, param_.colsample_bynode,
param_.colsample_bylevel, param_.colsample_bytree);
}
{
// setup temp space for each thread
// reserve a small space
stemp_.clear();
stemp_.resize(this->nthread_, std::vector<ThreadEntry>());
for (auto& i : stemp_) {
i.clear(); i.reserve(256);
}
snode_.reserve(256);
}
{
// expand query
qexpand_.reserve(256); qexpand_.clear();
for (int i = 0; i < tree.param.num_roots; ++i) {
qexpand_.push_back(i);
}
}
}