gbdt.cpp 30.5 KB
Newer Older
1
2
3
4
/*!
 * Copyright (c) 2016 Microsoft Corporation. All rights reserved.
 * Licensed under the MIT License. See LICENSE file in the project root for license information.
 */
Guolin Ke's avatar
Guolin Ke committed
5
6
7
#include "gbdt.h"

#include <LightGBM/metric.h>
Guolin Ke's avatar
Guolin Ke committed
8
#include <LightGBM/network.h>
9
10
11
12
#include <LightGBM/objective_function.h>
#include <LightGBM/prediction_early_stop.h>
#include <LightGBM/utils/common.h>
#include <LightGBM/utils/openmp_wrapper.h>
Guolin Ke's avatar
Guolin Ke committed
13

14
15
16
17
#include <chrono>
#include <ctime>
#include <sstream>

Guolin Ke's avatar
Guolin Ke committed
18
19
namespace LightGBM {

20
21
Common::Timer global_timer;

22
23
24
int LGBM_config_::current_device = lgbm_device_cpu;
int LGBM_config_::current_learner = use_cpu_learner;

25
26
27
GBDT::GBDT()
    : iter_(0),
      train_data_(nullptr),
28
      config_(nullptr),
29
30
31
32
33
34
35
36
37
38
39
40
      objective_function_(nullptr),
      early_stopping_round_(0),
      es_first_metric_only_(false),
      max_feature_idx_(0),
      num_tree_per_iteration_(1),
      num_class_(1),
      num_iteration_for_pred_(0),
      shrinkage_rate_(0.1f),
      num_init_iteration_(0),
      need_re_bagging_(false),
      balanced_bagging_(false),
      bagging_runner_(0, bagging_rand_block_) {
Guolin Ke's avatar
Guolin Ke committed
41
  average_output_ = false;
Guolin Ke's avatar
Guolin Ke committed
42
  tree_learner_ = nullptr;
Guolin Ke's avatar
Guolin Ke committed
43
44
45
46
47
}

GBDT::~GBDT() {
}

Guolin Ke's avatar
Guolin Ke committed
48
void GBDT::Init(const Config* config, const Dataset* train_data, const ObjectiveFunction* objective_function,
49
                const std::vector<const Metric*>& training_metrics) {
Nikita Titov's avatar
Nikita Titov committed
50
  CHECK_NOTNULL(train_data);
51
  train_data_ = train_data;
52
  if (!config->monotone_constraints.empty()) {
Nikita Titov's avatar
Nikita Titov committed
53
    CHECK_EQ(static_cast<size_t>(train_data_->num_total_features()), config->monotone_constraints.size());
Nikita Titov's avatar
Nikita Titov committed
54
  }
55
  if (!config->feature_contri.empty()) {
Nikita Titov's avatar
Nikita Titov committed
56
    CHECK_EQ(static_cast<size_t>(train_data_->num_total_features()), config->feature_contri.size());
57
  }
58
  iter_ = 0;
wxchan's avatar
wxchan committed
59
  num_iteration_for_pred_ = 0;
60
  max_feature_idx_ = 0;
wxchan's avatar
wxchan committed
61
  num_class_ = config->num_class;
Guolin Ke's avatar
Guolin Ke committed
62
63
  config_ = std::unique_ptr<Config>(new Config(*config));
  early_stopping_round_ = config_->early_stopping_round;
64
  es_first_metric_only_ = config_->first_metric_only;
Guolin Ke's avatar
Guolin Ke committed
65
  shrinkage_rate_ = config_->learning_rate;
66

67
68
69
70
  if (config_->device_type == std::string("cuda")) {
    LGBM_config_::current_learner = use_cuda_learner;
  }

71
  // load forced_splits file
72
73
74
75
76
  if (!config->forcedsplits_filename.empty()) {
    std::ifstream forced_splits_file(config->forcedsplits_filename.c_str());
    std::stringstream buffer;
    buffer << forced_splits_file.rdbuf();
    std::string err;
Guolin Ke's avatar
Guolin Ke committed
77
    forced_splits_json_ = Json::parse(buffer.str(), &err);
78
79
  }

80
81
82
  objective_function_ = objective_function;
  num_tree_per_iteration_ = num_class_;
  if (objective_function_ != nullptr) {
Guolin Ke's avatar
Guolin Ke committed
83
    num_tree_per_iteration_ = objective_function_->NumModelPerIteration();
84
85
86
    if (objective_function_->IsRenewTreeOutput() && !config->monotone_constraints.empty()) {
      Log::Fatal("Cannot use ``monotone_constraints`` in %s objective, please disable it.", objective_function_->GetName());
    }
87
88
  }

89
90
  is_constant_hessian_ = GetIsConstHessian(objective_function);

Guolin Ke's avatar
Guolin Ke committed
91
  tree_learner_ = std::unique_ptr<TreeLearner>(TreeLearner::CreateTreeLearner(config_->tree_learner, config_->device_type, config_.get()));
92
93
94

  // init tree learner
  tree_learner_->Init(train_data_, is_constant_hessian_);
95
  tree_learner_->SetForcedSplit(&forced_splits_json_);
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119

  // push training metrics
  training_metrics_.clear();
  for (const auto& metric : training_metrics) {
    training_metrics_.push_back(metric);
  }
  training_metrics_.shrink_to_fit();

  train_score_updater_.reset(new ScoreUpdater(train_data_, num_tree_per_iteration_));

  num_data_ = train_data_->num_data();
  // create buffer for gradients and hessians
  if (objective_function_ != nullptr) {
    size_t total_size = static_cast<size_t>(num_data_) * num_tree_per_iteration_;
    gradients_.resize(total_size);
    hessians_.resize(total_size);
  }
  // get max feature index
  max_feature_idx_ = train_data_->num_total_features() - 1;
  // get label index
  label_idx_ = train_data_->label_idx();
  // get feature names
  feature_names_ = train_data_->feature_names();
  feature_infos_ = train_data_->feature_infos();
120
  monotone_constraints_ = config->monotone_constraints;
121
122

  // if need bagging, create buffer
Guolin Ke's avatar
Guolin Ke committed
123
  ResetBaggingConfig(config_.get(), true);
124
125
126

  class_need_train_ = std::vector<bool>(num_tree_per_iteration_, true);
  if (objective_function_ != nullptr && objective_function_->SkipEmptyClass()) {
Nikita Titov's avatar
Nikita Titov committed
127
    CHECK_EQ(num_tree_per_iteration_, num_class_);
128
129
    for (int i = 0; i < num_class_; ++i) {
      class_need_train_[i] = objective_function_->ClassNeedTrain(i);
130
131
    }
  }
wxchan's avatar
wxchan committed
132
133
134
}

void GBDT::AddValidDataset(const Dataset* valid_data,
135
                           const std::vector<const Metric*>& valid_metrics) {
wxchan's avatar
wxchan committed
136
  if (!train_data_->CheckAlign(*valid_data)) {
137
    Log::Fatal("Cannot add validation data, since it has different bin mappers with training data");
138
  }
Guolin Ke's avatar
Guolin Ke committed
139
  // for a validation dataset, we need its score and metric
140
  auto new_score_updater = std::unique_ptr<ScoreUpdater>(new ScoreUpdater(valid_data, num_tree_per_iteration_));
wxchan's avatar
wxchan committed
141
142
  // update score
  for (int i = 0; i < iter_; ++i) {
143
144
145
    for (int cur_tree_id = 0; cur_tree_id < num_tree_per_iteration_; ++cur_tree_id) {
      auto curr_tree = (i + num_init_iteration_) * num_tree_per_iteration_ + cur_tree_id;
      new_score_updater->AddScore(models_[curr_tree].get(), cur_tree_id);
wxchan's avatar
wxchan committed
146
147
    }
  }
Guolin Ke's avatar
Guolin Ke committed
148
  valid_score_updater_.push_back(std::move(new_score_updater));
Guolin Ke's avatar
Guolin Ke committed
149
150
151
152
  valid_metrics_.emplace_back();
  for (const auto& metric : valid_metrics) {
    valid_metrics_.back().push_back(metric);
  }
Guolin Ke's avatar
Guolin Ke committed
153
  valid_metrics_.back().shrink_to_fit();
154

155
156
157
158
159
160
161
  if (early_stopping_round_ > 0) {
    auto num_metrics = valid_metrics.size();
    if (es_first_metric_only_) { num_metrics = 1; }
    best_iter_.emplace_back(num_metrics, 0);
    best_score_.emplace_back(num_metrics, kMinScore);
    best_msg_.emplace_back(num_metrics);
  }
Guolin Ke's avatar
Guolin Ke committed
162
163
}

Guolin Ke's avatar
Guolin Ke committed
164
void GBDT::Boosting() {
165
  Common::FunctionTimer fun_timer("GBDT::Boosting", global_timer);
Guolin Ke's avatar
Guolin Ke committed
166
167
168
169
170
171
172
173
174
  if (objective_function_ == nullptr) {
    Log::Fatal("No object function provided");
  }
  // objective function will calculate gradients and hessians
  int64_t num_score = 0;
  objective_function_->
    GetGradients(GetTrainingScore(&num_score), gradients_.data(), hessians_.data());
}

175
data_size_t GBDT::BaggingHelper(data_size_t start, data_size_t cnt, data_size_t* buffer) {
176
177
178
  if (cnt <= 0) {
    return 0;
  }
179
  data_size_t cur_left_cnt = 0;
180
  data_size_t cur_right_pos = cnt;
181
182
  // random bagging, minimal unit is one record
  for (data_size_t i = 0; i < cnt; ++i) {
183
184
185
    auto cur_idx = start + i;
    if (bagging_rands_[cur_idx / bagging_rand_block_].NextFloat() < config_->bagging_fraction) {
      buffer[cur_left_cnt++] = cur_idx;
186
    } else {
187
      buffer[--cur_right_pos] = cur_idx;
188
189
190
191
    }
  }
  return cur_left_cnt;
}
Guolin Ke's avatar
Guolin Ke committed
192

193
194
data_size_t GBDT::BalancedBaggingHelper(data_size_t start, data_size_t cnt,
                                        data_size_t* buffer) {
Guolin Ke's avatar
Guolin Ke committed
195
196
197
198
199
  if (cnt <= 0) {
    return 0;
  }
  auto label_ptr = train_data_->metadata().label();
  data_size_t cur_left_cnt = 0;
200
  data_size_t cur_right_pos = cnt;
Guolin Ke's avatar
Guolin Ke committed
201
202
  // random bagging, minimal unit is one record
  for (data_size_t i = 0; i < cnt; ++i) {
203
    auto cur_idx = start + i;
Guolin Ke's avatar
Guolin Ke committed
204
205
206
    bool is_pos = label_ptr[start + i] > 0;
    bool is_in_bag = false;
    if (is_pos) {
207
208
      is_in_bag = bagging_rands_[cur_idx / bagging_rand_block_].NextFloat() <
                  config_->pos_bagging_fraction;
Guolin Ke's avatar
Guolin Ke committed
209
    } else {
210
211
      is_in_bag = bagging_rands_[cur_idx / bagging_rand_block_].NextFloat() <
                  config_->neg_bagging_fraction;
Guolin Ke's avatar
Guolin Ke committed
212
213
    }
    if (is_in_bag) {
214
      buffer[cur_left_cnt++] = cur_idx;
Guolin Ke's avatar
Guolin Ke committed
215
    } else {
216
      buffer[--cur_right_pos] = cur_idx;
Guolin Ke's avatar
Guolin Ke committed
217
218
219
220
221
    }
  }
  return cur_left_cnt;
}

222
void GBDT::Bagging(int iter) {
223
  Common::FunctionTimer fun_timer("GBDT::Bagging", global_timer);
Guolin Ke's avatar
Guolin Ke committed
224
  // if need bagging
Guolin Ke's avatar
Guolin Ke committed
225
226
  if ((bag_data_cnt_ < num_data_ && iter % config_->bagging_freq == 0) ||
      need_re_bagging_) {
Guolin Ke's avatar
Guolin Ke committed
227
    need_re_bagging_ = false;
228
229
230
231
232
233
234
235
    auto left_cnt = bagging_runner_.Run<true>(
        num_data_,
        [=](int, data_size_t cur_start, data_size_t cur_cnt, data_size_t* left,
            data_size_t*) {
          data_size_t cur_left_count = 0;
          if (balanced_bagging_) {
            cur_left_count =
                BalancedBaggingHelper(cur_start, cur_cnt, left);
Guolin Ke's avatar
Guolin Ke committed
236
          } else {
237
            cur_left_count = BaggingHelper(cur_start, cur_cnt, left);
Guolin Ke's avatar
Guolin Ke committed
238
          }
239
240
241
          return cur_left_count;
        },
        bag_data_indices_.data());
Guolin Ke's avatar
Guolin Ke committed
242
    bag_data_cnt_ = left_cnt;
Guolin Ke's avatar
Guolin Ke committed
243
    Log::Debug("Re-bagging, using %d data to train", bag_data_cnt_);
Guolin Ke's avatar
Guolin Ke committed
244
    // set bagging data to tree learner
Guolin Ke's avatar
Guolin Ke committed
245
    if (!is_use_subset_) {
246
      tree_learner_->SetBaggingData(nullptr, bag_data_indices_.data(), bag_data_cnt_);
Guolin Ke's avatar
Guolin Ke committed
247
248
    } else {
      // get subset
Guolin Ke's avatar
Guolin Ke committed
249
      tmp_subset_->ReSize(bag_data_cnt_);
250
      tmp_subset_->CopySubrow(train_data_, bag_data_indices_.data(),
Guolin Ke's avatar
Guolin Ke committed
251
                              bag_data_cnt_, false);
252
253
      tree_learner_->SetBaggingData(tmp_subset_.get(), bag_data_indices_.data(),
                                    bag_data_cnt_);
Guolin Ke's avatar
Guolin Ke committed
254
    }
Guolin Ke's avatar
Guolin Ke committed
255
256
257
  }
}

Guolin Ke's avatar
Guolin Ke committed
258
void GBDT::Train(int snapshot_freq, const std::string& model_output_path) {
259
  Common::FunctionTimer fun_timer("GBDT::Train", global_timer);
Guolin Ke's avatar
Guolin Ke committed
260
261
  bool is_finished = false;
  auto start_time = std::chrono::steady_clock::now();
Guolin Ke's avatar
Guolin Ke committed
262
  for (int iter = 0; iter < config_->num_iterations && !is_finished; ++iter) {
Guolin Ke's avatar
Guolin Ke committed
263
264
265
266
    is_finished = TrainOneIter(nullptr, nullptr);
    if (!is_finished) {
      is_finished = EvalAndCheckEarlyStopping();
    }
Guolin Ke's avatar
Guolin Ke committed
267
268
269
270
271
272
273
    auto end_time = std::chrono::steady_clock::now();
    // output used time per iteration
    Log::Info("%f seconds elapsed, finished iteration %d", std::chrono::duration<double,
              std::milli>(end_time - start_time) * 1e-3, iter + 1);
    if (snapshot_freq > 0
        && (iter + 1) % snapshot_freq == 0) {
      std::string snapshot_out = model_output_path + ".snapshot_iter_" + std::to_string(iter + 1);
274
      SaveModelToFile(0, -1, config_->saved_feature_importance_type, snapshot_out.c_str());
Guolin Ke's avatar
Guolin Ke committed
275
276
277
278
    }
  }
}

279
void GBDT::RefitTree(const std::vector<std::vector<int>>& tree_leaf_prediction) {
280
281
282
  CHECK_GT(tree_leaf_prediction.size(), 0);
  CHECK_EQ(static_cast<size_t>(num_data_), tree_leaf_prediction.size());
  CHECK_EQ(static_cast<size_t>(models_.size()), tree_leaf_prediction[0].size());
283
284
285
286
287
288
289
290
291
  int num_iterations = static_cast<int>(models_.size() / num_tree_per_iteration_);
  std::vector<int> leaf_pred(num_data_);
  for (int iter = 0; iter < num_iterations; ++iter) {
    Boosting();
    for (int tree_id = 0; tree_id < num_tree_per_iteration_; ++tree_id) {
      int model_index = iter * num_tree_per_iteration_ + tree_id;
      #pragma omp parallel for schedule(static)
      for (int i = 0; i < num_data_; ++i) {
        leaf_pred[i] = tree_leaf_prediction[i][model_index];
Nikita Titov's avatar
Nikita Titov committed
292
        CHECK_LT(leaf_pred[i], models_[model_index]->num_leaves());
293
      }
294
295
296
      size_t offset = static_cast<size_t>(tree_id) * num_data_;
      auto grad = gradients_.data() + offset;
      auto hess = hessians_.data() + offset;
297
298
299
300
301
302
303
      auto new_tree = tree_learner_->FitByExistingTree(models_[model_index].get(), leaf_pred, grad, hess);
      train_score_updater_->AddScore(tree_learner_.get(), new_tree, tree_id);
      models_[model_index].reset(new_tree);
    }
  }
}

304
305
306
307
308
309
310
311
312
313
314
315
316
317
318
319
320
321
322
323
324
/* If the custom "average" is implemented it will be used inplace of the label average (if enabled)
*
* An improvement to this is to have options to explicitly choose
* (i) standard average
* (ii) custom average if available
* (iii) any user defined scalar bias (e.g. using a new option "init_score" that overrides (i) and (ii) )
*
* (i) and (ii) could be selected as say "auto_init_score" = 0 or 1 etc..
*
*/
double ObtainAutomaticInitialScore(const ObjectiveFunction* fobj, int class_id) {
  double init_score = 0.0;
  if (fobj != nullptr) {
    init_score = fobj->BoostFromScore(class_id);
  }
  if (Network::num_machines() > 1) {
    init_score = Network::GlobalSyncUpByMean(init_score);
  }
  return init_score;
}

Guolin Ke's avatar
Guolin Ke committed
325
double GBDT::BoostFromAverage(int class_id, bool update_scorer) {
326
  Common::FunctionTimer fun_timer("GBDT::BoostFromAverage", global_timer);
327
  // boosting from average label; or customized "average" if implemented for the current objective
328
329
330
  if (models_.empty() && !train_score_updater_->has_init_score() && objective_function_ != nullptr) {
    if (config_->boost_from_average || (train_data_ != nullptr && train_data_->num_features() == 0)) {
      double init_score = ObtainAutomaticInitialScore(objective_function_, class_id);
331
      if (std::fabs(init_score) > kEpsilon) {
Guolin Ke's avatar
Guolin Ke committed
332
333
334
335
336
        if (update_scorer) {
          train_score_updater_->AddScore(init_score, class_id);
          for (auto& score_updater : valid_score_updater_) {
            score_updater->AddScore(init_score, class_id);
          }
337
338
339
        }
        Log::Info("Start training from score %lf", init_score);
        return init_score;
Guolin Ke's avatar
Guolin Ke committed
340
      }
341
342
343
    } else if (std::string(objective_function_->GetName()) == std::string("regression_l1")
               || std::string(objective_function_->GetName()) == std::string("quantile")
               || std::string(objective_function_->GetName()) == std::string("mape")) {
344
      Log::Warning("Disabling boost_from_average in %s may cause the slow convergence", objective_function_->GetName());
345
    }
346
  }
Guolin Ke's avatar
Guolin Ke committed
347
348
  return 0.0f;
}
Guolin Ke's avatar
Guolin Ke committed
349

Guolin Ke's avatar
Guolin Ke committed
350
bool GBDT::TrainOneIter(const score_t* gradients, const score_t* hessians) {
351
  Common::FunctionTimer fun_timer("GBDT::TrainOneIter", global_timer);
352
  std::vector<double> init_scores(num_tree_per_iteration_, 0.0);
Guolin Ke's avatar
Guolin Ke committed
353
  // boosting first
Guolin Ke's avatar
Guolin Ke committed
354
  if (gradients == nullptr || hessians == nullptr) {
355
    for (int cur_tree_id = 0; cur_tree_id < num_tree_per_iteration_; ++cur_tree_id) {
Guolin Ke's avatar
Guolin Ke committed
356
      init_scores[cur_tree_id] = BoostFromAverage(cur_tree_id, true);
357
    }
Guolin Ke's avatar
Guolin Ke committed
358
    Boosting();
Guolin Ke's avatar
Guolin Ke committed
359
360
    gradients = gradients_.data();
    hessians = hessians_.data();
Guolin Ke's avatar
Guolin Ke committed
361
  }
362
363
  // bagging logic
  Bagging(iter_);
Guolin Ke's avatar
Guolin Ke committed
364

Guolin Ke's avatar
Guolin Ke committed
365
  bool should_continue = false;
366
  for (int cur_tree_id = 0; cur_tree_id < num_tree_per_iteration_; ++cur_tree_id) {
367
    const size_t offset = static_cast<size_t>(cur_tree_id) * num_data_;
368
    std::unique_ptr<Tree> new_tree(new Tree(2, false));
369
    if (class_need_train_[cur_tree_id] && train_data_->num_features() > 0) {
370
371
      auto grad = gradients + offset;
      auto hess = hessians + offset;
Guolin Ke's avatar
Guolin Ke committed
372
373
374
      // need to copy gradients for bagging subset.
      if (is_use_subset_ && bag_data_cnt_ < num_data_) {
        for (int i = 0; i < bag_data_cnt_; ++i) {
375
376
          gradients_[offset + i] = grad[bag_data_indices_[i]];
          hessians_[offset + i] = hess[bag_data_indices_[i]];
Guolin Ke's avatar
Guolin Ke committed
377
        }
378
379
        grad = gradients_.data() + offset;
        hess = hessians_.data() + offset;
Guolin Ke's avatar
Guolin Ke committed
380
      }
381
      new_tree.reset(tree_learner_->Train(grad, hess));
382
    }
Guolin Ke's avatar
Guolin Ke committed
383

Guolin Ke's avatar
Guolin Ke committed
384
    if (new_tree->num_leaves() > 1) {
Guolin Ke's avatar
Guolin Ke committed
385
      should_continue = true;
386
      auto score_ptr = train_score_updater_->score() + offset;
387
388
      auto residual_getter = [score_ptr](const label_t* label, int i) {return static_cast<double>(label[i]) - score_ptr[i]; };
      tree_learner_->RenewTreeOutput(new_tree.get(), objective_function_, residual_getter,
389
                                     num_data_, bag_data_indices_.data(), bag_data_cnt_);
Guolin Ke's avatar
Guolin Ke committed
390
391
392
      // shrinkage by learning rate
      new_tree->Shrinkage(shrinkage_rate_);
      // update score
393
      UpdateScore(new_tree.get(), cur_tree_id);
394
395
      if (std::fabs(init_scores[cur_tree_id]) > kEpsilon) {
        new_tree->AddBias(init_scores[cur_tree_id]);
Guolin Ke's avatar
Guolin Ke committed
396
      }
397
398
    } else {
      // only add default score one-time
399
400
401
402
403
404
405
406
407
      if (models_.size() < static_cast<size_t>(num_tree_per_iteration_)) {
        double output = 0.0;
        if (!class_need_train_[cur_tree_id]) {
          if (objective_function_ != nullptr) {
            output = objective_function_->BoostFromScore(cur_tree_id);
          }
        } else {
          output = init_scores[cur_tree_id];
        }
408
        new_tree->AsConstantTree(output);
Guolin Ke's avatar
Guolin Ke committed
409
        // updates scores
410
        train_score_updater_->AddScore(output, cur_tree_id);
411
        for (auto& score_updater : valid_score_updater_) {
412
          score_updater->AddScore(output, cur_tree_id);
413
414
415
        }
      }
    }
Guolin Ke's avatar
Guolin Ke committed
416
417
418
    // add model
    models_.push_back(std::move(new_tree));
  }
Guolin Ke's avatar
Guolin Ke committed
419

Guolin Ke's avatar
Guolin Ke committed
420
  if (!should_continue) {
421
    Log::Warning("Stopped training because there are no more leaves that meet the split requirements");
422
423
424
425
    if (models_.size() > static_cast<size_t>(num_tree_per_iteration_)) {
      for (int cur_tree_id = 0; cur_tree_id < num_tree_per_iteration_; ++cur_tree_id) {
        models_.pop_back();
      }
Guolin Ke's avatar
Guolin Ke committed
426
427
428
    }
    return true;
  }
429

Guolin Ke's avatar
Guolin Ke committed
430
431
  ++iter_;
  return false;
Guolin Ke's avatar
Guolin Ke committed
432
}
433

wxchan's avatar
wxchan committed
434
void GBDT::RollbackOneIter() {
435
  if (iter_ <= 0) { return; }
wxchan's avatar
wxchan committed
436
  // reset score
437
  for (int cur_tree_id = 0; cur_tree_id < num_tree_per_iteration_; ++cur_tree_id) {
Guolin Ke's avatar
Guolin Ke committed
438
    auto curr_tree = models_.size() - num_tree_per_iteration_ + cur_tree_id;
wxchan's avatar
wxchan committed
439
    models_[curr_tree]->Shrinkage(-1.0);
440
    train_score_updater_->AddScore(models_[curr_tree].get(), cur_tree_id);
wxchan's avatar
wxchan committed
441
    for (auto& score_updater : valid_score_updater_) {
442
      score_updater->AddScore(models_[curr_tree].get(), cur_tree_id);
wxchan's avatar
wxchan committed
443
444
445
    }
  }
  // remove model
446
  for (int cur_tree_id = 0; cur_tree_id < num_tree_per_iteration_; ++cur_tree_id) {
wxchan's avatar
wxchan committed
447
448
449
450
451
    models_.pop_back();
  }
  --iter_;
}

Guolin Ke's avatar
Guolin Ke committed
452
bool GBDT::EvalAndCheckEarlyStopping() {
453
454
  bool is_met_early_stopping = false;
  // print message for metric
Guolin Ke's avatar
Guolin Ke committed
455
  auto best_msg = OutputMetric(iter_);
Guolin Ke's avatar
Guolin Ke committed
456
457


Guolin Ke's avatar
Guolin Ke committed
458
  is_met_early_stopping = !best_msg.empty();
459
460
  if (is_met_early_stopping) {
    Log::Info("Early stopping at iteration %d, the best iteration round is %d",
461
              iter_, iter_ - early_stopping_round_);
Guolin Ke's avatar
Guolin Ke committed
462
    Log::Info("Output of best iteration round:\n%s", best_msg.c_str());
463
    // pop last early_stopping_round_ models
464
    for (int i = 0; i < early_stopping_round_ * num_tree_per_iteration_; ++i) {
465
466
467
468
      models_.pop_back();
    }
  }
  return is_met_early_stopping;
Guolin Ke's avatar
Guolin Ke committed
469
470
}

471
void GBDT::UpdateScore(const Tree* tree, const int cur_tree_id) {
472
  Common::FunctionTimer fun_timer("GBDT::UpdateScore", global_timer);
Guolin Ke's avatar
Guolin Ke committed
473
  // update training score
Guolin Ke's avatar
Guolin Ke committed
474
  if (!is_use_subset_) {
475
    train_score_updater_->AddScore(tree_learner_.get(), tree, cur_tree_id);
Guolin Ke's avatar
Guolin Ke committed
476
477
478
479
480
481

    // we need to predict out-of-bag scores of data for boosting
    if (num_data_ - bag_data_cnt_ > 0) {
      train_score_updater_->AddScore(tree, bag_data_indices_.data() + bag_data_cnt_, num_data_ - bag_data_cnt_, cur_tree_id);
    }

Guolin Ke's avatar
Guolin Ke committed
482
  } else {
483
    train_score_updater_->AddScore(tree, cur_tree_id);
Guolin Ke's avatar
Guolin Ke committed
484
  }
Guolin Ke's avatar
Guolin Ke committed
485
486


Guolin Ke's avatar
Guolin Ke committed
487
  // update validation score
Guolin Ke's avatar
Guolin Ke committed
488
  for (auto& score_updater : valid_score_updater_) {
489
    score_updater->AddScore(tree, cur_tree_id);
Guolin Ke's avatar
Guolin Ke committed
490
491
492
  }
}

Guolin Ke's avatar
Guolin Ke committed
493
494
495
496
std::vector<double> GBDT::EvalOneMetric(const Metric* metric, const double* score) const {
  return metric->Eval(score, objective_function_);
}

Guolin Ke's avatar
Guolin Ke committed
497
std::string GBDT::OutputMetric(int iter) {
Guolin Ke's avatar
Guolin Ke committed
498
  bool need_output = (iter % config_->metric_freq) == 0;
Guolin Ke's avatar
Guolin Ke committed
499
500
  std::string ret = "";
  std::stringstream msg_buf;
501
  std::vector<std::pair<size_t, size_t>> meet_early_stopping_pairs;
Guolin Ke's avatar
Guolin Ke committed
502
  // print training metric
Guolin Ke's avatar
Guolin Ke committed
503
  if (need_output) {
504
505
    for (auto& sub_metric : training_metrics_) {
      auto name = sub_metric->GetName();
Guolin Ke's avatar
Guolin Ke committed
506
      auto scores = EvalOneMetric(sub_metric, train_score_updater_->score());
Guolin Ke's avatar
Guolin Ke committed
507
      for (size_t k = 0; k < name.size(); ++k) {
Guolin Ke's avatar
Guolin Ke committed
508
509
510
511
512
513
        std::stringstream tmp_buf;
        tmp_buf << "Iteration:" << iter
          << ", training " << name[k]
          << " : " << scores[k];
        Log::Info(tmp_buf.str().c_str());
        if (early_stopping_round_ > 0) {
514
          msg_buf << tmp_buf.str() << '\n';
Guolin Ke's avatar
Guolin Ke committed
515
        }
516
      }
517
    }
Guolin Ke's avatar
Guolin Ke committed
518
519
  }
  // print validation metric
Guolin Ke's avatar
Guolin Ke committed
520
  if (need_output || early_stopping_round_ > 0) {
521
522
    for (size_t i = 0; i < valid_metrics_.size(); ++i) {
      for (size_t j = 0; j < valid_metrics_[i].size(); ++j) {
Guolin Ke's avatar
Guolin Ke committed
523
        auto test_scores = EvalOneMetric(valid_metrics_[i][j], valid_score_updater_[i]->score());
Guolin Ke's avatar
Guolin Ke committed
524
525
526
527
528
529
530
531
532
533
        auto name = valid_metrics_[i][j]->GetName();
        for (size_t k = 0; k < name.size(); ++k) {
          std::stringstream tmp_buf;
          tmp_buf << "Iteration:" << iter
            << ", valid_" << i + 1 << " " << name[k]
            << " : " << test_scores[k];
          if (need_output) {
            Log::Info(tmp_buf.str().c_str());
          }
          if (early_stopping_round_ > 0) {
534
            msg_buf << tmp_buf.str() << '\n';
535
          }
wxchan's avatar
wxchan committed
536
        }
537
        if (es_first_metric_only_ && j > 0) { continue; }
Guolin Ke's avatar
Guolin Ke committed
538
        if (ret.empty() && early_stopping_round_ > 0) {
539
540
541
          auto cur_score = valid_metrics_[i][j]->factor_to_bigger_better() * test_scores.back();
          if (cur_score > best_score_[i][j]) {
            best_score_[i][j] = cur_score;
542
            best_iter_[i][j] = iter;
Guolin Ke's avatar
Guolin Ke committed
543
            meet_early_stopping_pairs.emplace_back(i, j);
544
          } else {
Guolin Ke's avatar
Guolin Ke committed
545
            if (iter - best_iter_[i][j] >= early_stopping_round_) { ret = best_msg_[i][j]; }
546
          }
wxchan's avatar
wxchan committed
547
548
        }
      }
Guolin Ke's avatar
Guolin Ke committed
549
550
    }
  }
Guolin Ke's avatar
Guolin Ke committed
551
552
553
  for (auto& pair : meet_early_stopping_pairs) {
    best_msg_[pair.first][pair.second] = msg_buf.str();
  }
wxchan's avatar
wxchan committed
554
  return ret;
Guolin Ke's avatar
Guolin Ke committed
555
556
}

557
/*! \brief Get eval result */
558
std::vector<double> GBDT::GetEvalAt(int data_idx) const {
Guolin Ke's avatar
Guolin Ke committed
559
  CHECK(data_idx >= 0 && data_idx <= static_cast<int>(valid_score_updater_.size()));
560
561
  std::vector<double> ret;
  if (data_idx == 0) {
562
    for (auto& sub_metric : training_metrics_) {
Guolin Ke's avatar
Guolin Ke committed
563
      auto scores = EvalOneMetric(sub_metric, train_score_updater_->score());
564
565
566
      for (auto score : scores) {
        ret.push_back(score);
      }
567
    }
568
  } else {
569
570
    auto used_idx = data_idx - 1;
    for (size_t j = 0; j < valid_metrics_[used_idx].size(); ++j) {
Guolin Ke's avatar
Guolin Ke committed
571
      auto test_scores = EvalOneMetric(valid_metrics_[used_idx][j], valid_score_updater_[used_idx]->score());
572
573
574
      for (auto score : test_scores) {
        ret.push_back(score);
      }
575
576
577
578
579
    }
  }
  return ret;
}

Guolin Ke's avatar
Guolin Ke committed
580
/*! \brief Get training scores result */
581
const double* GBDT::GetTrainingScore(int64_t* out_len) {
582
  *out_len = static_cast<int64_t>(train_score_updater_->num_data()) * num_class_;
Guolin Ke's avatar
Guolin Ke committed
583
  return train_score_updater_->score();
584
585
}

586
void GBDT::PredictContrib(const double* features, double* output) const {
587
  // set zero
Guolin Ke's avatar
Guolin Ke committed
588
589
  const int num_features = max_feature_idx_ + 1;
  std::memset(output, 0, sizeof(double) * num_tree_per_iteration_ * (num_features + 1));
590
591
  const int end_iteration_for_pred = start_iteration_for_pred_ + num_iteration_for_pred_;
  for (int i = start_iteration_for_pred_; i < end_iteration_for_pred; ++i) {
592
593
    // predict all the trees for one iteration
    for (int k = 0; k < num_tree_per_iteration_; ++k) {
Guolin Ke's avatar
Guolin Ke committed
594
      models_[i * num_tree_per_iteration_ + k]->PredictContrib(features, num_features, output + k*(num_features + 1));
595
    }
596
597
598
599
600
601
  }
}

void GBDT::PredictContribByMap(const std::unordered_map<int, double>& features,
                               std::vector<std::unordered_map<int, double>>* output) const {
  const int num_features = max_feature_idx_ + 1;
602
603
  const int end_iteration_for_pred = start_iteration_for_pred_ + num_iteration_for_pred_;
  for (int i = start_iteration_for_pred_; i < end_iteration_for_pred; ++i) {
604
605
606
    // predict all the trees for one iteration
    for (int k = 0; k < num_tree_per_iteration_; ++k) {
      models_[i * num_tree_per_iteration_ + k]->PredictContribByMap(features, num_features, &((*output)[k]));
607
608
609
610
    }
  }
}

Guolin Ke's avatar
Guolin Ke committed
611
612
void GBDT::GetPredictAt(int data_idx, double* out_result, int64_t* out_len) {
  CHECK(data_idx >= 0 && data_idx <= static_cast<int>(valid_score_updater_.size()));
Guolin Ke's avatar
Guolin Ke committed
613

614
  const double* raw_scores = nullptr;
Guolin Ke's avatar
Guolin Ke committed
615
616
  data_size_t num_data = 0;
  if (data_idx == 0) {
wxchan's avatar
wxchan committed
617
    raw_scores = GetTrainingScore(out_len);
Guolin Ke's avatar
Guolin Ke committed
618
619
620
621
622
    num_data = train_score_updater_->num_data();
  } else {
    auto used_idx = data_idx - 1;
    raw_scores = valid_score_updater_[used_idx]->score();
    num_data = valid_score_updater_[used_idx]->num_data();
623
    *out_len = static_cast<int64_t>(num_data) * num_class_;
Guolin Ke's avatar
Guolin Ke committed
624
  }
Guolin Ke's avatar
Guolin Ke committed
625
  if (objective_function_ != nullptr) {
Guolin Ke's avatar
Guolin Ke committed
626
627
    #pragma omp parallel for schedule(static)
    for (data_size_t i = 0; i < num_data; ++i) {
Guolin Ke's avatar
Guolin Ke committed
628
      std::vector<double> tree_pred(num_tree_per_iteration_);
629
      for (int j = 0; j < num_tree_per_iteration_; ++j) {
Guolin Ke's avatar
Guolin Ke committed
630
        tree_pred[j] = raw_scores[j * num_data + i];
631
      }
Guolin Ke's avatar
Guolin Ke committed
632
633
      std::vector<double> tmp_result(num_class_);
      objective_function_->ConvertOutput(tree_pred.data(), tmp_result.data());
Guolin Ke's avatar
Guolin Ke committed
634
      for (int j = 0; j < num_class_; ++j) {
635
        out_result[j * num_data + i] = static_cast<double>(tmp_result[j]);
Guolin Ke's avatar
Guolin Ke committed
636
637
      }
    }
638
  } else {
Guolin Ke's avatar
Guolin Ke committed
639
    #pragma omp parallel for schedule(static)
Guolin Ke's avatar
Guolin Ke committed
640
    for (data_size_t i = 0; i < num_data; ++i) {
641
      for (int j = 0; j < num_tree_per_iteration_; ++j) {
Guolin Ke's avatar
Guolin Ke committed
642
        out_result[j * num_data + i] = static_cast<double>(raw_scores[j * num_data + i]);
Guolin Ke's avatar
Guolin Ke committed
643
644
645
646
647
      }
    }
  }
}

648
649
double GBDT::GetUpperBoundValue() const {
  double max_value = 0.0;
Nikita Titov's avatar
Nikita Titov committed
650
  for (const auto &tree : models_) {
651
652
653
654
655
656
657
    max_value += tree->GetUpperBoundValue();
  }
  return max_value;
}

double GBDT::GetLowerBoundValue() const {
  double min_value = 0.0;
Nikita Titov's avatar
Nikita Titov committed
658
  for (const auto &tree : models_) {
659
660
661
662
663
    min_value += tree->GetLowerBoundValue();
  }
  return min_value;
}

Guolin Ke's avatar
Guolin Ke committed
664
665
666
void GBDT::ResetTrainingData(const Dataset* train_data, const ObjectiveFunction* objective_function,
                             const std::vector<const Metric*>& training_metrics) {
  if (train_data != train_data_ && !train_data_->CheckAlign(*train_data)) {
667
    Log::Fatal("Cannot reset training data, since new training data has different bin mappers");
wxchan's avatar
wxchan committed
668
669
  }

Guolin Ke's avatar
Guolin Ke committed
670
671
  objective_function_ = objective_function;
  if (objective_function_ != nullptr) {
Nikita Titov's avatar
Nikita Titov committed
672
    CHECK_EQ(num_tree_per_iteration_, objective_function_->NumModelPerIteration());
673
674
675
    if (objective_function_->IsRenewTreeOutput() && !config_->monotone_constraints.empty()) {
      Log::Fatal("Cannot use ``monotone_constraints`` in %s objective, please disable it.", objective_function_->GetName());
    }
676
  }
677
  is_constant_hessian_ = GetIsConstHessian(objective_function);
678

Guolin Ke's avatar
Guolin Ke committed
679
680
681
682
  // push training metrics
  training_metrics_.clear();
  for (const auto& metric : training_metrics) {
    training_metrics_.push_back(metric);
683
  }
Guolin Ke's avatar
Guolin Ke committed
684
  training_metrics_.shrink_to_fit();
685

Guolin Ke's avatar
Guolin Ke committed
686
687
688
689
690
  if (train_data != train_data_) {
    train_data_ = train_data;
    // not same training data, need reset score and others
    // create score tracker
    train_score_updater_.reset(new ScoreUpdater(train_data_, num_tree_per_iteration_));
691

Guolin Ke's avatar
Guolin Ke committed
692
693
694
695
696
697
    // update score
    for (int i = 0; i < iter_; ++i) {
      for (int cur_tree_id = 0; cur_tree_id < num_tree_per_iteration_; ++cur_tree_id) {
        auto curr_tree = (i + num_init_iteration_) * num_tree_per_iteration_ + cur_tree_id;
        train_score_updater_->AddScore(models_[curr_tree].get(), cur_tree_id);
      }
698
699
    }

Guolin Ke's avatar
Guolin Ke committed
700
    num_data_ = train_data_->num_data();
701

Guolin Ke's avatar
Guolin Ke committed
702
703
704
705
706
707
    // create buffer for gradients and hessians
    if (objective_function_ != nullptr) {
      size_t total_size = static_cast<size_t>(num_data_) * num_tree_per_iteration_;
      gradients_.resize(total_size);
      hessians_.resize(total_size);
    }
708

Guolin Ke's avatar
Guolin Ke committed
709
710
711
712
    max_feature_idx_ = train_data_->num_total_features() - 1;
    label_idx_ = train_data_->label_idx();
    feature_names_ = train_data_->feature_names();
    feature_infos_ = train_data_->feature_infos();
713

714
    tree_learner_->ResetTrainingData(train_data, is_constant_hessian_);
Guolin Ke's avatar
Guolin Ke committed
715
    ResetBaggingConfig(config_.get(), true);
716
717
  } else {
    tree_learner_->ResetIsConstantHessian(is_constant_hessian_);
718
  }
719
720
}

Guolin Ke's avatar
Guolin Ke committed
721
722
void GBDT::ResetConfig(const Config* config) {
  auto new_config = std::unique_ptr<Config>(new Config(*config));
723
  if (!config->monotone_constraints.empty()) {
Nikita Titov's avatar
Nikita Titov committed
724
    CHECK_EQ(static_cast<size_t>(train_data_->num_total_features()), config->monotone_constraints.size());
725
726
  }
  if (!config->feature_contri.empty()) {
Nikita Titov's avatar
Nikita Titov committed
727
    CHECK_EQ(static_cast<size_t>(train_data_->num_total_features()), config->feature_contri.size());
728
  }
729
730
731
  if (objective_function_ != nullptr && objective_function_->IsRenewTreeOutput() && !config->monotone_constraints.empty()) {
    Log::Fatal("Cannot use ``monotone_constraints`` in %s objective, please disable it.", objective_function_->GetName());
  }
Guolin Ke's avatar
Guolin Ke committed
732
733
734
  early_stopping_round_ = new_config->early_stopping_round;
  shrinkage_rate_ = new_config->learning_rate;
  if (tree_learner_ != nullptr) {
Guolin Ke's avatar
Guolin Ke committed
735
    tree_learner_->ResetConfig(new_config.get());
736
  }
Guolin Ke's avatar
Guolin Ke committed
737
738
  if (train_data_ != nullptr) {
    ResetBaggingConfig(new_config.get(), false);
739
  }
740
  if (config_.get() != nullptr && config_->forcedsplits_filename != new_config->forcedsplits_filename) {
741
742
743
744
745
746
747
    // load forced_splits file
    if (!new_config->forcedsplits_filename.empty()) {
      std::ifstream forced_splits_file(
          new_config->forcedsplits_filename.c_str());
      std::stringstream buffer;
      buffer << forced_splits_file.rdbuf();
      std::string err;
Guolin Ke's avatar
Guolin Ke committed
748
      forced_splits_json_ = Json::parse(buffer.str(), &err);
749
750
751
752
753
754
      tree_learner_->SetForcedSplit(&forced_splits_json_);
    } else {
      forced_splits_json_ = Json();
      tree_learner_->SetForcedSplit(nullptr);
    }
  }
Guolin Ke's avatar
Guolin Ke committed
755
  config_.reset(new_config.release());
Guolin Ke's avatar
Guolin Ke committed
756
757
}

Guolin Ke's avatar
Guolin Ke committed
758
void GBDT::ResetBaggingConfig(const Config* config, bool is_change_dataset) {
Guolin Ke's avatar
Guolin Ke committed
759
  // if need bagging, create buffer
Guolin Ke's avatar
Guolin Ke committed
760
761
762
763
764
765
  data_size_t num_pos_data = 0;
  if (objective_function_ != nullptr) {
    num_pos_data = objective_function_->NumPositiveData();
  }
  bool balance_bagging_cond = (config->pos_bagging_fraction < 1.0 || config->neg_bagging_fraction < 1.0) && (num_pos_data > 0);
  if ((config->bagging_fraction < 1.0 || balance_bagging_cond) && config->bagging_freq > 0) {
766
767
    need_re_bagging_ = false;
    if (!is_change_dataset &&
Guolin Ke's avatar
Guolin Ke committed
768
769
      config_.get() != nullptr && config_->bagging_fraction == config->bagging_fraction && config_->bagging_freq == config->bagging_freq
      && config_->pos_bagging_fraction == config->pos_bagging_fraction && config_->neg_bagging_fraction == config->neg_bagging_fraction) {
770
771
      return;
    }
Guolin Ke's avatar
Guolin Ke committed
772
773
    if (balance_bagging_cond) {
      balanced_bagging_ = true;
774
      bag_data_cnt_ = static_cast<data_size_t>(num_pos_data * config->pos_bagging_fraction)
Guolin Ke's avatar
Guolin Ke committed
775
776
777
778
                      + static_cast<data_size_t>((num_data_ - num_pos_data) * config->neg_bagging_fraction);
    } else {
      bag_data_cnt_ = static_cast<data_size_t>(config->bagging_fraction * num_data_);
    }
Guolin Ke's avatar
Guolin Ke committed
779
    bag_data_indices_.resize(num_data_);
780
781
782
783
784
785
    bagging_runner_.ReSize(num_data_);
    bagging_rands_.clear();
    for (int i = 0;
         i < (num_data_ + bagging_rand_block_ - 1) / bagging_rand_block_; ++i) {
      bagging_rands_.emplace_back(config_->bagging_seed + i);
    }
786

787
788
    double average_bag_rate =
        (static_cast<double>(bag_data_cnt_) / num_data_) / config->bagging_freq;
Guolin Ke's avatar
Guolin Ke committed
789
790
    is_use_subset_ = false;
    const int group_threshold_usesubset = 100;
791
    if (average_bag_rate <= 0.5
792
        && (train_data_->num_feature_groups() < group_threshold_usesubset)) {
Guolin Ke's avatar
Guolin Ke committed
793
794
795
796
797
      if (tmp_subset_ == nullptr || is_change_dataset) {
        tmp_subset_.reset(new Dataset(bag_data_cnt_));
        tmp_subset_->CopyFeatureMapperFrom(train_data_);
      }
      is_use_subset_ = true;
798
      Log::Debug("Use subset for bagging");
Guolin Ke's avatar
Guolin Ke committed
799
800
    }

801
    need_re_bagging_ = true;
802

Guolin Ke's avatar
Guolin Ke committed
803
804
805
806
807
    if (is_use_subset_ && bag_data_cnt_ < num_data_) {
      if (objective_function_ == nullptr) {
        size_t total_size = static_cast<size_t>(num_data_) * num_tree_per_iteration_;
        gradients_.resize(total_size);
        hessians_.resize(total_size);
808
      }
809
    }
810
  } else {
Guolin Ke's avatar
Guolin Ke committed
811
812
    bag_data_cnt_ = num_data_;
    bag_data_indices_.clear();
813
    bagging_runner_.ReSize(0);
Guolin Ke's avatar
Guolin Ke committed
814
    is_use_subset_ = false;
815
  }
wxchan's avatar
wxchan committed
816
817
}

Guolin Ke's avatar
Guolin Ke committed
818
}  // namespace LightGBM