gbdt.cpp 28.6 KB
Newer Older
Guolin Ke's avatar
Guolin Ke committed
1
2
#include "gbdt.h"

3
#include <LightGBM/utils/openmp_wrapper.h>
4

Guolin Ke's avatar
Guolin Ke committed
5
6
7
8
#include <LightGBM/utils/common.h>

#include <LightGBM/objective_function.h>
#include <LightGBM/metric.h>
cbecker's avatar
cbecker committed
9
#include <LightGBM/prediction_early_stop.h>
Guolin Ke's avatar
Guolin Ke committed
10
#include <LightGBM/network.h>
Guolin Ke's avatar
Guolin Ke committed
11
12
13
14
15
16
17

#include <ctime>

#include <sstream>
#include <chrono>
#include <string>
#include <vector>
18
#include <utility>
Guolin Ke's avatar
Guolin Ke committed
19
20
21

namespace LightGBM {

Guolin Ke's avatar
Guolin Ke committed
22
23
24
#ifdef TIMETAG
std::chrono::duration<double, std::milli> boosting_time;
std::chrono::duration<double, std::milli> train_score_time;
Guolin Ke's avatar
Guolin Ke committed
25
std::chrono::duration<double, std::milli> out_of_bag_score_time;
Guolin Ke's avatar
Guolin Ke committed
26
27
28
29
30
31
std::chrono::duration<double, std::milli> valid_score_time;
std::chrono::duration<double, std::milli> metric_time;
std::chrono::duration<double, std::milli> bagging_time;
std::chrono::duration<double, std::milli> tree_time;
#endif // TIMETAG

Guolin Ke's avatar
Guolin Ke committed
32
GBDT::GBDT() : iter_(0),
Guolin Ke's avatar
Guolin Ke committed
33
34
35
36
37
38
39
40
41
42
train_data_(nullptr),
objective_function_(nullptr),
early_stopping_round_(0),
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) {
Guolin Ke's avatar
Guolin Ke committed
43

Guolin Ke's avatar
Guolin Ke committed
44
45
  #pragma omp parallel
  #pragma omp master
Guolin Ke's avatar
Guolin Ke committed
46
47
48
49
  {
    num_threads_ = omp_get_num_threads();
  }
  average_output_ = false;
Guolin Ke's avatar
Guolin Ke committed
50
  tree_learner_ = nullptr;
Guolin Ke's avatar
Guolin Ke committed
51
52
53
}

GBDT::~GBDT() {
Guolin Ke's avatar
Guolin Ke committed
54
  #ifdef TIMETAG
Guolin Ke's avatar
Guolin Ke committed
55
56
  Log::Info("GBDT::boosting costs %f", boosting_time * 1e-3);
  Log::Info("GBDT::train_score costs %f", train_score_time * 1e-3);
Guolin Ke's avatar
Guolin Ke committed
57
  Log::Info("GBDT::out_of_bag_score costs %f", out_of_bag_score_time * 1e-3);
Guolin Ke's avatar
Guolin Ke committed
58
59
60
61
  Log::Info("GBDT::valid_score costs %f", valid_score_time * 1e-3);
  Log::Info("GBDT::metric costs %f", metric_time * 1e-3);
  Log::Info("GBDT::bagging costs %f", bagging_time * 1e-3);
  Log::Info("GBDT::tree costs %f", tree_time * 1e-3);
Guolin Ke's avatar
Guolin Ke committed
62
  #endif
Guolin Ke's avatar
Guolin Ke committed
63
64
}

65
void GBDT::Init(const BoostingConfig* config, const Dataset* train_data, const ObjectiveFunction* objective_function,
66
                const std::vector<const Metric*>& training_metrics) {
Guolin Ke's avatar
Guolin Ke committed
67
  CHECK(train_data != nullptr);
Guolin Ke's avatar
Guolin Ke committed
68
  CHECK(train_data->num_features() > 0);
69
  train_data_ = train_data;
70
  iter_ = 0;
wxchan's avatar
wxchan committed
71
  num_iteration_for_pred_ = 0;
72
  max_feature_idx_ = 0;
wxchan's avatar
wxchan committed
73
  num_class_ = config->num_class;
74
75
76
77
78
79
80
81
  gbdt_config_ = std::unique_ptr<BoostingConfig>(new BoostingConfig(*config));
  early_stopping_round_ = gbdt_config_->early_stopping_round;
  shrinkage_rate_ = gbdt_config_->learning_rate;

  objective_function_ = objective_function;
  num_tree_per_iteration_ = num_class_;
  if (objective_function_ != nullptr) {
    is_constant_hessian_ = objective_function_->IsConstantHessian();
Guolin Ke's avatar
Guolin Ke committed
82
    num_tree_per_iteration_ = objective_function_->NumModelPerIteration();
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
  } else {
    is_constant_hessian_ = false;
  }

  tree_learner_ = std::unique_ptr<TreeLearner>(TreeLearner::CreateTreeLearner(gbdt_config_->tree_learner_type, gbdt_config_->device_type, &gbdt_config_->tree_config));

  // init tree learner
  tree_learner_->Init(train_data_, is_constant_hessian_);

  // 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();

  // if need bagging, create buffer
Guolin Ke's avatar
Guolin Ke committed
117
  ResetBaggingConfig(gbdt_config_.get(), true);
118
119
120
121
122

  // reset config for tree learner
  class_need_train_ = std::vector<bool>(num_tree_per_iteration_, true);
  if (objective_function_ != nullptr && objective_function_->SkipEmptyClass()) {
    CHECK(num_tree_per_iteration_ == num_class_);
Guolin Ke's avatar
Guolin Ke committed
123

124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
    class_default_output_ = std::vector<double>(num_tree_per_iteration_, 0.0f);
    auto label = train_data_->metadata().label();
    if (num_tree_per_iteration_ > 1) {
      // multi-class
      std::vector<data_size_t> cnt_per_class(num_tree_per_iteration_, 0);
      for (data_size_t i = 0; i < num_data_; ++i) {
        int index = static_cast<int>(label[i]);
        CHECK(index < num_tree_per_iteration_);
        ++cnt_per_class[index];
      }
      for (int i = 0; i < num_tree_per_iteration_; ++i) {
        if (cnt_per_class[i] == num_data_) {
          class_need_train_[i] = false;
          class_default_output_[i] = -std::log(kEpsilon);
        } else if (cnt_per_class[i] == 0) {
          class_need_train_[i] = false;
          class_default_output_[i] = -std::log(1.0f / kEpsilon - 1.0f);
        }
      }
    } else {
      // binary class
      data_size_t cnt_pos = 0;
      for (data_size_t i = 0; i < num_data_; ++i) {
        if (label[i] > 0) {
          ++cnt_pos;
        }
      }
      if (cnt_pos == 0) {
        class_need_train_[0] = false;
        class_default_output_[0] = -std::log(1.0f / kEpsilon - 1.0f);
      } else if (cnt_pos == num_data_) {
        class_need_train_[0] = false;
        class_default_output_[0] = -std::log(kEpsilon);
      }
    }
  }
wxchan's avatar
wxchan committed
160
161
162
}

void GBDT::AddValidDataset(const Dataset* valid_data,
163
                           const std::vector<const Metric*>& valid_metrics) {
wxchan's avatar
wxchan committed
164
165
  if (!train_data_->CheckAlign(*valid_data)) {
    Log::Fatal("cannot add validation data, since it has different bin mappers with training data");
166
  }
Guolin Ke's avatar
Guolin Ke committed
167
  // for a validation dataset, we need its score and metric
168
  auto new_score_updater = std::unique_ptr<ScoreUpdater>(new ScoreUpdater(valid_data, num_tree_per_iteration_));
wxchan's avatar
wxchan committed
169
170
  // update score
  for (int i = 0; i < iter_; ++i) {
171
172
173
    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
174
175
    }
  }
Guolin Ke's avatar
Guolin Ke committed
176
  valid_score_updater_.push_back(std::move(new_score_updater));
Guolin Ke's avatar
Guolin Ke committed
177
  valid_metrics_.emplace_back();
178
179
180
  if (early_stopping_round_ > 0) {
    best_iter_.emplace_back();
    best_score_.emplace_back();
Guolin Ke's avatar
Guolin Ke committed
181
    best_msg_.emplace_back();
182
  }
Guolin Ke's avatar
Guolin Ke committed
183
184
  for (const auto& metric : valid_metrics) {
    valid_metrics_.back().push_back(metric);
185
186
187
    if (early_stopping_round_ > 0) {
      best_iter_.back().push_back(0);
      best_score_.back().push_back(kMinScore);
Guolin Ke's avatar
Guolin Ke committed
188
      best_msg_.back().emplace_back();
189
    }
Guolin Ke's avatar
Guolin Ke committed
190
  }
Guolin Ke's avatar
Guolin Ke committed
191
  valid_metrics_.back().shrink_to_fit();
Guolin Ke's avatar
Guolin Ke committed
192
193
}

Guolin Ke's avatar
Guolin Ke committed
194
195
196
197
198
199
200
201
202
203
void GBDT::Boosting() {
  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());
}

204
data_size_t GBDT::BaggingHelper(Random& cur_rand, data_size_t start, data_size_t cnt, data_size_t* buffer) {
205
206
207
  if (cnt <= 0) {
    return 0;
  }
Guolin Ke's avatar
Guolin Ke committed
208
  data_size_t bag_data_cnt = static_cast<data_size_t>(gbdt_config_->bagging_fraction * cnt);
209
210
  data_size_t cur_left_cnt = 0;
  data_size_t cur_right_cnt = 0;
Guolin Ke's avatar
Guolin Ke committed
211
  auto right_buffer = buffer + bag_data_cnt;
212
213
  // random bagging, minimal unit is one record
  for (data_size_t i = 0; i < cnt; ++i) {
Guolin Ke's avatar
Guolin Ke committed
214
    float prob = (bag_data_cnt - cur_left_cnt) / static_cast<float>(cnt - i);
Guolin Ke's avatar
Guolin Ke committed
215
    if (cur_rand.NextFloat() < prob) {
216
217
      buffer[cur_left_cnt++] = start + i;
    } else {
Guolin Ke's avatar
Guolin Ke committed
218
      right_buffer[cur_right_cnt++] = start + i;
219
220
221
222
223
    }
  }
  CHECK(cur_left_cnt == bag_data_cnt);
  return cur_left_cnt;
}
Guolin Ke's avatar
Guolin Ke committed
224

225
void GBDT::Bagging(int iter) {
Guolin Ke's avatar
Guolin Ke committed
226
  // if need bagging
Guolin Ke's avatar
Guolin Ke committed
227
  if ((bag_data_cnt_ < num_data_ && iter % gbdt_config_->bagging_freq == 0)
Guolin Ke's avatar
Guolin Ke committed
228
      || need_re_bagging_) {
Guolin Ke's avatar
Guolin Ke committed
229
    need_re_bagging_ = false;
Guolin Ke's avatar
Guolin Ke committed
230
    const data_size_t min_inner_size = 1000;
231
232
    data_size_t inner_size = (num_data_ + num_threads_ - 1) / num_threads_;
    if (inner_size < min_inner_size) { inner_size = min_inner_size; }
233
    OMP_INIT_EX();
Guolin Ke's avatar
Guolin Ke committed
234
    #pragma omp parallel for schedule(static,1)
235
    for (int i = 0; i < num_threads_; ++i) {
236
      OMP_LOOP_EX_BEGIN();
237
238
239
240
241
242
      left_cnts_buf_[i] = 0;
      right_cnts_buf_[i] = 0;
      data_size_t cur_start = i * inner_size;
      if (cur_start > num_data_) { continue; }
      data_size_t cur_cnt = inner_size;
      if (cur_start + cur_cnt > num_data_) { cur_cnt = num_data_ - cur_start; }
Guolin Ke's avatar
Guolin Ke committed
243
244
      Random cur_rand(gbdt_config_->bagging_seed + iter * num_threads_ + i);
      data_size_t cur_left_count = BaggingHelper(cur_rand, cur_start, cur_cnt, tmp_indices_.data() + cur_start);
245
246
247
      offsets_buf_[i] = cur_start;
      left_cnts_buf_[i] = cur_left_count;
      right_cnts_buf_[i] = cur_cnt - cur_left_count;
248
      OMP_LOOP_EX_END();
249
    }
250
    OMP_THROW_EX();
251
252
253
254
255
256
257
258
259
    data_size_t left_cnt = 0;
    left_write_pos_buf_[0] = 0;
    right_write_pos_buf_[0] = 0;
    for (int i = 1; i < num_threads_; ++i) {
      left_write_pos_buf_[i] = left_write_pos_buf_[i - 1] + left_cnts_buf_[i - 1];
      right_write_pos_buf_[i] = right_write_pos_buf_[i - 1] + right_cnts_buf_[i - 1];
    }
    left_cnt = left_write_pos_buf_[num_threads_ - 1] + left_cnts_buf_[num_threads_ - 1];

Guolin Ke's avatar
Guolin Ke committed
260
    #pragma omp parallel for schedule(static, 1)
261
    for (int i = 0; i < num_threads_; ++i) {
262
      OMP_LOOP_EX_BEGIN();
263
264
      if (left_cnts_buf_[i] > 0) {
        std::memcpy(bag_data_indices_.data() + left_write_pos_buf_[i],
265
                    tmp_indices_.data() + offsets_buf_[i], left_cnts_buf_[i] * sizeof(data_size_t));
Guolin Ke's avatar
Guolin Ke committed
266
      }
267
268
      if (right_cnts_buf_[i] > 0) {
        std::memcpy(bag_data_indices_.data() + left_cnt + right_write_pos_buf_[i],
269
                    tmp_indices_.data() + offsets_buf_[i] + left_cnts_buf_[i], right_cnts_buf_[i] * sizeof(data_size_t));
Guolin Ke's avatar
Guolin Ke committed
270
      }
271
      OMP_LOOP_EX_END();
Guolin Ke's avatar
Guolin Ke committed
272
    }
273
    OMP_THROW_EX();
Guolin Ke's avatar
Guolin Ke committed
274
    bag_data_cnt_ = left_cnt;
Guolin Ke's avatar
Guolin Ke committed
275
    Log::Debug("Re-bagging, using %d data to train", bag_data_cnt_);
Guolin Ke's avatar
Guolin Ke committed
276
    // set bagging data to tree learner
Guolin Ke's avatar
Guolin Ke committed
277
278
279
280
    if (!is_use_subset_) {
      tree_learner_->SetBaggingData(bag_data_indices_.data(), bag_data_cnt_);
    } else {
      // get subset
Guolin Ke's avatar
Guolin Ke committed
281
282
      tmp_subset_->ReSize(bag_data_cnt_);
      tmp_subset_->CopySubset(train_data_, bag_data_indices_.data(), bag_data_cnt_, false);
Guolin Ke's avatar
Guolin Ke committed
283
284
      tree_learner_->ResetTrainingData(tmp_subset_.get());
    }
Guolin Ke's avatar
Guolin Ke committed
285
286
287
  }
}

288
/* If the custom "average" is implemented it will be used inplace of the label average (if enabled)
Guolin Ke's avatar
Guolin Ke committed
289
290
291
292
293
294
295
296
297
298
*
* 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, const float* label, data_size_t num_data) {
299
300
  double init_score = 0.0f;
  bool got_custom = false;
Guolin Ke's avatar
Guolin Ke committed
301
302
  if (fobj != nullptr) {
    got_custom = fobj->GetCustomAverage(&init_score);
303
304
305
306
307
308
309
310
  }
  if (!got_custom) {
    double sum_label = 0.0f;
    #pragma omp parallel for schedule(static) reduction(+:sum_label)
    for (data_size_t i = 0; i < num_data; ++i) {
      sum_label += label[i];
    }
    init_score = sum_label / num_data;
Guolin Ke's avatar
Guolin Ke committed
311
312
313
314
315
316
  }
  if (Network::num_machines() > 1) {
    double global_init_score = 0.0f;
    Network::Allreduce(reinterpret_cast<char*>(&init_score),
                       sizeof(init_score), sizeof(init_score),
                       reinterpret_cast<char*>(&global_init_score),
Guolin Ke's avatar
Guolin Ke committed
317
318
                       [](const char* src, char* dst, int type_size, comm_size_t len) {
      comm_size_t used_size = 0;
Guolin Ke's avatar
Guolin Ke committed
319
320
321
322
323
324
325
326
327
328
329
330
331
332
333
334
335
      const double *p1;
      double *p2;
      while (used_size < len) {
        p1 = reinterpret_cast<const double *>(src);
        p2 = reinterpret_cast<double *>(dst);
        *p2 += *p1;
        src += type_size;
        dst += type_size;
        used_size += type_size;
      }
    });
    return global_init_score / Network::num_machines();
  } else {
    return init_score;
  }
}

Guolin Ke's avatar
Guolin Ke committed
336
337
338
339
void GBDT::Train(int snapshot_freq, const std::string& model_output_path) {
  bool is_finished = false;
  auto start_time = std::chrono::steady_clock::now();
  for (int iter = 0; iter < gbdt_config_->num_iterations && !is_finished; ++iter) {
Guolin Ke's avatar
Guolin Ke committed
340
341
342
343
    is_finished = TrainOneIter(nullptr, nullptr);
    if (!is_finished) {
      is_finished = EvalAndCheckEarlyStopping();
    }
Guolin Ke's avatar
Guolin Ke committed
344
345
346
347
348
349
350
351
352
353
354
355
    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);
      SaveModelToFile(-1, snapshot_out.c_str());
    }
  }
}

Guolin Ke's avatar
Guolin Ke committed
356
double GBDT::BoostFromAverage() {
357
  // boosting from average label; or customized "average" if implemented for the current objective
Guolin Ke's avatar
Guolin Ke committed
358
359
  if (models_.empty()
      && gbdt_config_->boost_from_average
360
      && !train_score_updater_->has_init_score()
361
362
363
      && num_class_ <= 1
      && objective_function_ != nullptr
      && objective_function_->BoostFromAverage()) {
Guolin Ke's avatar
Guolin Ke committed
364

365
366
    auto label = train_data_->metadata().label();
    double init_score = ObtainAutomaticInitialScore(objective_function_, label, num_data_);
Guolin Ke's avatar
Guolin Ke committed
367
368
369
370
371
372
    if (std::fabs(init_score) > kEpsilon) {
      train_score_updater_->AddScore(init_score, 0);
      for (auto& score_updater : valid_score_updater_) {
        score_updater->AddScore(init_score, 0);
      }
      return init_score;
373
    }
374
  }
Guolin Ke's avatar
Guolin Ke committed
375
376
  return 0.0f;
}
Guolin Ke's avatar
Guolin Ke committed
377

Guolin Ke's avatar
Guolin Ke committed
378
379
bool GBDT::TrainOneIter(const score_t* gradients, const score_t* hessians) {
  auto init_score = BoostFromAverage();
Guolin Ke's avatar
Guolin Ke committed
380
  // boosting first
Guolin Ke's avatar
Guolin Ke committed
381
382
  if (gradients == nullptr || hessians == nullptr) {

Guolin Ke's avatar
Guolin Ke committed
383
    #ifdef TIMETAG
Guolin Ke's avatar
Guolin Ke committed
384
    auto start_time = std::chrono::steady_clock::now();
Guolin Ke's avatar
Guolin Ke committed
385
    #endif
Guolin Ke's avatar
Guolin Ke committed
386

Guolin Ke's avatar
Guolin Ke committed
387
    Boosting();
Guolin Ke's avatar
Guolin Ke committed
388
389
390
    gradients = gradients_.data();
    hessians = hessians_.data();

Guolin Ke's avatar
Guolin Ke committed
391
    #ifdef TIMETAG
Guolin Ke's avatar
Guolin Ke committed
392
    boosting_time += std::chrono::steady_clock::now() - start_time;
Guolin Ke's avatar
Guolin Ke committed
393
    #endif
Guolin Ke's avatar
Guolin Ke committed
394
  }
Guolin Ke's avatar
Guolin Ke committed
395

Guolin Ke's avatar
Guolin Ke committed
396
  #ifdef TIMETAG
Guolin Ke's avatar
Guolin Ke committed
397
  auto start_time = std::chrono::steady_clock::now();
Guolin Ke's avatar
Guolin Ke committed
398
  #endif
Guolin Ke's avatar
Guolin Ke committed
399

400
401
  // bagging logic
  Bagging(iter_);
Guolin Ke's avatar
Guolin Ke committed
402

Guolin Ke's avatar
Guolin Ke committed
403
  #ifdef TIMETAG
Guolin Ke's avatar
Guolin Ke committed
404
  bagging_time += std::chrono::steady_clock::now() - start_time;
Guolin Ke's avatar
Guolin Ke committed
405
  #endif
Guolin Ke's avatar
Guolin Ke committed
406

Guolin Ke's avatar
Guolin Ke committed
407
  bool should_continue = false;
408
  for (int cur_tree_id = 0; cur_tree_id < num_tree_per_iteration_; ++cur_tree_id) {
Guolin Ke's avatar
Guolin Ke committed
409

Guolin Ke's avatar
Guolin Ke committed
410
    #ifdef TIMETAG
Guolin Ke's avatar
Guolin Ke committed
411
    start_time = std::chrono::steady_clock::now();
Guolin Ke's avatar
Guolin Ke committed
412
    #endif
Guolin Ke's avatar
Guolin Ke committed
413

414
    std::unique_ptr<Tree> new_tree(new Tree(2));
415
    if (class_need_train_[cur_tree_id]) {
416
      size_t bias = static_cast<size_t>(cur_tree_id)* num_data_;
Guolin Ke's avatar
Guolin Ke committed
417
418
419
420
421
422
423
424
425
426
427
428
429
430
      auto grad = gradients + bias;
      auto hess = hessians + bias;

      // 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) {
          gradients_[bias + i] = grad[bag_data_indices_[i]];
          hessians_[bias + i] = hess[bag_data_indices_[i]];
        }
        grad = gradients_.data() + bias;
        hess = hessians_.data() + bias;
      }

      new_tree.reset(tree_learner_->Train(grad, hess, is_constant_hessian_));
431
    }
Guolin Ke's avatar
Guolin Ke committed
432

Guolin Ke's avatar
Guolin Ke committed
433
    #ifdef TIMETAG
Guolin Ke's avatar
Guolin Ke committed
434
    tree_time += std::chrono::steady_clock::now() - start_time;
Guolin Ke's avatar
Guolin Ke committed
435
    #endif
Guolin Ke's avatar
Guolin Ke committed
436
437

    if (new_tree->num_leaves() > 1) {
Guolin Ke's avatar
Guolin Ke committed
438
439
440
441
      should_continue = true;
      // shrinkage by learning rate
      new_tree->Shrinkage(shrinkage_rate_);
      // update score
442
      UpdateScore(new_tree.get(), cur_tree_id);
Guolin Ke's avatar
Guolin Ke committed
443
444
445
      if (std::fabs(init_score) > kEpsilon) {
        new_tree->AddBias(init_score);
      }
446
447
    } else {
      // only add default score one-time
448
449
      if (!class_need_train_[cur_tree_id] && models_.size() < static_cast<size_t>(num_tree_per_iteration_)) {
        auto output = class_default_output_[cur_tree_id];
450
        new_tree->AsConstantTree(output);
Guolin Ke's avatar
Guolin Ke committed
451
        // updates scores
452
        train_score_updater_->AddScore(output, cur_tree_id);
453
        for (auto& score_updater : valid_score_updater_) {
454
          score_updater->AddScore(output, cur_tree_id);
455
456
457
        }
      }
    }
Guolin Ke's avatar
Guolin Ke committed
458
459
460
    // add model
    models_.push_back(std::move(new_tree));
  }
Guolin Ke's avatar
Guolin Ke committed
461

Guolin Ke's avatar
Guolin Ke committed
462
  if (!should_continue) {
Guolin Ke's avatar
Guolin Ke committed
463
    Log::Warning("Stopped training because there are no more leaves that meet the split requirements.");
464
    for (int cur_tree_id = 0; cur_tree_id < num_tree_per_iteration_; ++cur_tree_id) {
Guolin Ke's avatar
Guolin Ke committed
465
466
467
468
      models_.pop_back();
    }
    return true;
  }
469

Guolin Ke's avatar
Guolin Ke committed
470
471
  ++iter_;
  return false;
Guolin Ke's avatar
Guolin Ke committed
472
}
473

wxchan's avatar
wxchan committed
474
void GBDT::RollbackOneIter() {
475
  if (iter_ <= 0) { return; }
wxchan's avatar
wxchan committed
476
  // reset score
477
  for (int cur_tree_id = 0; cur_tree_id < num_tree_per_iteration_; ++cur_tree_id) {
Guolin Ke's avatar
Guolin Ke committed
478
    auto curr_tree = models_.size() - num_tree_per_iteration_ + cur_tree_id;
wxchan's avatar
wxchan committed
479
    models_[curr_tree]->Shrinkage(-1.0);
480
    train_score_updater_->AddScore(models_[curr_tree].get(), cur_tree_id);
wxchan's avatar
wxchan committed
481
    for (auto& score_updater : valid_score_updater_) {
482
      score_updater->AddScore(models_[curr_tree].get(), cur_tree_id);
wxchan's avatar
wxchan committed
483
484
485
    }
  }
  // remove model
486
  for (int cur_tree_id = 0; cur_tree_id < num_tree_per_iteration_; ++cur_tree_id) {
wxchan's avatar
wxchan committed
487
488
489
490
491
    models_.pop_back();
  }
  --iter_;
}

Guolin Ke's avatar
Guolin Ke committed
492
bool GBDT::EvalAndCheckEarlyStopping() {
493
  bool is_met_early_stopping = false;
Guolin Ke's avatar
Guolin Ke committed
494

Guolin Ke's avatar
Guolin Ke committed
495
  #ifdef TIMETAG
Guolin Ke's avatar
Guolin Ke committed
496
  auto start_time = std::chrono::steady_clock::now();
Guolin Ke's avatar
Guolin Ke committed
497
  #endif
Guolin Ke's avatar
Guolin Ke committed
498

499
  // print message for metric
Guolin Ke's avatar
Guolin Ke committed
500
  auto best_msg = OutputMetric(iter_);
Guolin Ke's avatar
Guolin Ke committed
501

Guolin Ke's avatar
Guolin Ke committed
502
  #ifdef TIMETAG
Guolin Ke's avatar
Guolin Ke committed
503
  metric_time += std::chrono::steady_clock::now() - start_time;
Guolin Ke's avatar
Guolin Ke committed
504
  #endif
Guolin Ke's avatar
Guolin Ke committed
505

Guolin Ke's avatar
Guolin Ke committed
506
  is_met_early_stopping = !best_msg.empty();
507
508
  if (is_met_early_stopping) {
    Log::Info("Early stopping at iteration %d, the best iteration round is %d",
509
              iter_, iter_ - early_stopping_round_);
Guolin Ke's avatar
Guolin Ke committed
510
    Log::Info("Output of best iteration round:\n%s", best_msg.c_str());
511
    // pop last early_stopping_round_ models
512
    for (int i = 0; i < early_stopping_round_ * num_tree_per_iteration_; ++i) {
513
514
515
516
      models_.pop_back();
    }
  }
  return is_met_early_stopping;
Guolin Ke's avatar
Guolin Ke committed
517
518
}

519
void GBDT::UpdateScore(const Tree* tree, const int cur_tree_id) {
Guolin Ke's avatar
Guolin Ke committed
520

Guolin Ke's avatar
Guolin Ke committed
521
  #ifdef TIMETAG
Guolin Ke's avatar
Guolin Ke committed
522
  auto start_time = std::chrono::steady_clock::now();
Guolin Ke's avatar
Guolin Ke committed
523
  #endif
Guolin Ke's avatar
Guolin Ke committed
524

Guolin Ke's avatar
Guolin Ke committed
525
  // update training score
Guolin Ke's avatar
Guolin Ke committed
526
  if (!is_use_subset_) {
527
    train_score_updater_->AddScore(tree_learner_.get(), tree, cur_tree_id);
Guolin Ke's avatar
Guolin Ke committed
528
529
530
531
532
533
534
535
536
537
538
539
540
541
542
543
544
545

    #ifdef TIMETAG
    train_score_time += std::chrono::steady_clock::now() - start_time;
    #endif

    #ifdef TIMETAG
    start_time = std::chrono::steady_clock::now();
    #endif

    // 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);
    }

    #ifdef TIMETAG
    out_of_bag_score_time += std::chrono::steady_clock::now() - start_time;
    #endif

Guolin Ke's avatar
Guolin Ke committed
546
  } else {
547
    train_score_updater_->AddScore(tree, cur_tree_id);
Guolin Ke's avatar
Guolin Ke committed
548
549
550
551

    #ifdef TIMETAG
    train_score_time += std::chrono::steady_clock::now() - start_time;
    #endif
Guolin Ke's avatar
Guolin Ke committed
552
  }
Guolin Ke's avatar
Guolin Ke committed
553
554


Guolin Ke's avatar
Guolin Ke committed
555
  #ifdef TIMETAG
Guolin Ke's avatar
Guolin Ke committed
556
  start_time = std::chrono::steady_clock::now();
Guolin Ke's avatar
Guolin Ke committed
557
  #endif
Guolin Ke's avatar
Guolin Ke committed
558

Guolin Ke's avatar
Guolin Ke committed
559
  // update validation score
Guolin Ke's avatar
Guolin Ke committed
560
  for (auto& score_updater : valid_score_updater_) {
561
    score_updater->AddScore(tree, cur_tree_id);
Guolin Ke's avatar
Guolin Ke committed
562
  }
Guolin Ke's avatar
Guolin Ke committed
563

Guolin Ke's avatar
Guolin Ke committed
564
  #ifdef TIMETAG
Guolin Ke's avatar
Guolin Ke committed
565
  valid_score_time += std::chrono::steady_clock::now() - start_time;
Guolin Ke's avatar
Guolin Ke committed
566
  #endif
Guolin Ke's avatar
Guolin Ke committed
567
568
}

Guolin Ke's avatar
Guolin Ke committed
569
570
571
572
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
573
574
575
576
std::string GBDT::OutputMetric(int iter) {
  bool need_output = (iter % gbdt_config_->output_freq) == 0;
  std::string ret = "";
  std::stringstream msg_buf;
577
  std::vector<std::pair<size_t, size_t>> meet_early_stopping_pairs;
Guolin Ke's avatar
Guolin Ke committed
578
  // print training metric
Guolin Ke's avatar
Guolin Ke committed
579
  if (need_output) {
580
581
    for (auto& sub_metric : training_metrics_) {
      auto name = sub_metric->GetName();
Guolin Ke's avatar
Guolin Ke committed
582
      auto scores = EvalOneMetric(sub_metric, train_score_updater_->score());
Guolin Ke's avatar
Guolin Ke committed
583
      for (size_t k = 0; k < name.size(); ++k) {
Guolin Ke's avatar
Guolin Ke committed
584
585
586
587
588
589
        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) {
590
          msg_buf << tmp_buf.str() << '\n';
Guolin Ke's avatar
Guolin Ke committed
591
        }
592
      }
593
    }
Guolin Ke's avatar
Guolin Ke committed
594
595
  }
  // print validation metric
Guolin Ke's avatar
Guolin Ke committed
596
  if (need_output || early_stopping_round_ > 0) {
597
598
    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
599
        auto test_scores = EvalOneMetric(valid_metrics_[i][j], valid_score_updater_[i]->score());
Guolin Ke's avatar
Guolin Ke committed
600
601
602
603
604
605
606
607
608
609
        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) {
610
            msg_buf << tmp_buf.str() << '\n';
611
          }
wxchan's avatar
wxchan committed
612
        }
Guolin Ke's avatar
Guolin Ke committed
613
        if (ret.empty() && early_stopping_round_ > 0) {
614
615
616
          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;
617
            best_iter_[i][j] = iter;
Guolin Ke's avatar
Guolin Ke committed
618
            meet_early_stopping_pairs.emplace_back(i, j);
619
          } else {
Guolin Ke's avatar
Guolin Ke committed
620
            if (iter - best_iter_[i][j] >= early_stopping_round_) { ret = best_msg_[i][j]; }
621
          }
wxchan's avatar
wxchan committed
622
623
        }
      }
Guolin Ke's avatar
Guolin Ke committed
624
625
    }
  }
Guolin Ke's avatar
Guolin Ke committed
626
627
628
  for (auto& pair : meet_early_stopping_pairs) {
    best_msg_[pair.first][pair.second] = msg_buf.str();
  }
wxchan's avatar
wxchan committed
629
  return ret;
Guolin Ke's avatar
Guolin Ke committed
630
631
}

632
/*! \brief Get eval result */
633
std::vector<double> GBDT::GetEvalAt(int data_idx) const {
Guolin Ke's avatar
Guolin Ke committed
634
  CHECK(data_idx >= 0 && data_idx <= static_cast<int>(valid_score_updater_.size()));
635
636
  std::vector<double> ret;
  if (data_idx == 0) {
637
    for (auto& sub_metric : training_metrics_) {
Guolin Ke's avatar
Guolin Ke committed
638
      auto scores = EvalOneMetric(sub_metric, train_score_updater_->score());
639
640
641
      for (auto score : scores) {
        ret.push_back(score);
      }
642
    }
643
  } else {
644
645
    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
646
      auto test_scores = EvalOneMetric(valid_metrics_[used_idx][j], valid_score_updater_[used_idx]->score());
647
648
649
      for (auto score : test_scores) {
        ret.push_back(score);
      }
650
651
652
653
654
    }
  }
  return ret;
}

Guolin Ke's avatar
Guolin Ke committed
655
/*! \brief Get training scores result */
656
const double* GBDT::GetTrainingScore(int64_t* out_len) {
657
  *out_len = static_cast<int64_t>(train_score_updater_->num_data()) * num_class_;
Guolin Ke's avatar
Guolin Ke committed
658
  return train_score_updater_->score();
659
660
}

661
662
663
void GBDT::PredictContrib(const double* features, double* output, const PredictionEarlyStopInstance* early_stop) const {
  int early_stop_round_counter = 0;
  // set zero
Guolin Ke's avatar
Guolin Ke committed
664
665
  const int num_features = max_feature_idx_ + 1;
  std::memset(output, 0, sizeof(double) * num_tree_per_iteration_ * (num_features + 1));
666
667
668
  for (int i = 0; i < num_iteration_for_pred_; ++i) {
    // predict all the trees for one iteration
    for (int k = 0; k < num_tree_per_iteration_; ++k) {
Guolin Ke's avatar
Guolin Ke committed
669
      models_[i * num_tree_per_iteration_ + k]->PredictContrib(features, num_features, output + k*(num_features + 1));
670
671
672
673
674
675
676
677
678
679
680
681
    }
    // check early stopping
    ++early_stop_round_counter;
    if (early_stop->round_period == early_stop_round_counter) {
      if (early_stop->callback_function(output, num_tree_per_iteration_)) {
        return;
      }
      early_stop_round_counter = 0;
    }
  }
}

Guolin Ke's avatar
Guolin Ke committed
682
683
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
684

685
  const double* raw_scores = nullptr;
Guolin Ke's avatar
Guolin Ke committed
686
687
  data_size_t num_data = 0;
  if (data_idx == 0) {
wxchan's avatar
wxchan committed
688
    raw_scores = GetTrainingScore(out_len);
Guolin Ke's avatar
Guolin Ke committed
689
690
691
692
693
    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();
694
    *out_len = static_cast<int64_t>(num_data) * num_class_;
Guolin Ke's avatar
Guolin Ke committed
695
  }
Guolin Ke's avatar
Guolin Ke committed
696
  if (objective_function_ != nullptr && !average_output_) {
Guolin Ke's avatar
Guolin Ke committed
697
698
    #pragma omp parallel for schedule(static)
    for (data_size_t i = 0; i < num_data; ++i) {
Guolin Ke's avatar
Guolin Ke committed
699
      std::vector<double> tree_pred(num_tree_per_iteration_);
700
      for (int j = 0; j < num_tree_per_iteration_; ++j) {
Guolin Ke's avatar
Guolin Ke committed
701
        tree_pred[j] = raw_scores[j * num_data + i];
702
      }
Guolin Ke's avatar
Guolin Ke committed
703
704
      std::vector<double> tmp_result(num_class_);
      objective_function_->ConvertOutput(tree_pred.data(), tmp_result.data());
Guolin Ke's avatar
Guolin Ke committed
705
      for (int j = 0; j < num_class_; ++j) {
706
        out_result[j * num_data + i] = static_cast<double>(tmp_result[j]);
Guolin Ke's avatar
Guolin Ke committed
707
708
      }
    }
709
  } else {
Guolin Ke's avatar
Guolin Ke committed
710
    #pragma omp parallel for schedule(static)
Guolin Ke's avatar
Guolin Ke committed
711
    for (data_size_t i = 0; i < num_data; ++i) {
Guolin Ke's avatar
Guolin Ke committed
712
      std::vector<double> tmp_result(num_tree_per_iteration_);
713
      for (int j = 0; j < num_tree_per_iteration_; ++j) {
Guolin Ke's avatar
Guolin Ke committed
714
        out_result[j * num_data + i] = static_cast<double>(raw_scores[j * num_data + i]);
Guolin Ke's avatar
Guolin Ke committed
715
716
717
718
719
      }
    }
  }
}

Guolin Ke's avatar
Guolin Ke committed
720
721
void GBDT::ResetTrainingData(const Dataset* train_data, const ObjectiveFunction* objective_function,
                             const std::vector<const Metric*>& training_metrics) {
Guolin Ke's avatar
Guolin Ke committed
722

Guolin Ke's avatar
Guolin Ke committed
723
724
  if (train_data != train_data_ && !train_data_->CheckAlign(*train_data)) {
    Log::Fatal("cannot reset training data, since new training data has different bin mappers");
wxchan's avatar
wxchan committed
725
726
  }

Guolin Ke's avatar
Guolin Ke committed
727
728
729
730
731
732
  objective_function_ = objective_function;
  if (objective_function_ != nullptr) {
    is_constant_hessian_ = objective_function_->IsConstantHessian();
    CHECK(num_tree_per_iteration_ == objective_function_->NumModelPerIteration());
  } else {
    is_constant_hessian_ = false;
733
734
  }

Guolin Ke's avatar
Guolin Ke committed
735
736
737
738
  // push training metrics
  training_metrics_.clear();
  for (const auto& metric : training_metrics) {
    training_metrics_.push_back(metric);
739
  }
Guolin Ke's avatar
Guolin Ke committed
740
  training_metrics_.shrink_to_fit();
741

Guolin Ke's avatar
Guolin Ke committed
742
743
744
745
746
  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_));
747

Guolin Ke's avatar
Guolin Ke committed
748
749
750
751
752
753
    // 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);
      }
754
755
    }

Guolin Ke's avatar
Guolin Ke committed
756
    num_data_ = train_data_->num_data();
757

Guolin Ke's avatar
Guolin Ke committed
758
759
760
761
762
763
    // 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);
    }
764

Guolin Ke's avatar
Guolin Ke committed
765
766
767
768
    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();
769

Guolin Ke's avatar
Guolin Ke committed
770
771
    tree_learner_->ResetTrainingData(train_data);
    ResetBaggingConfig(gbdt_config_.get(), true);
772
  }
773
774
}

Guolin Ke's avatar
Guolin Ke committed
775
776
777
778
779
780
void GBDT::ResetConfig(const BoostingConfig* config) {
  auto new_config = std::unique_ptr<BoostingConfig>(new BoostingConfig(*config));
  early_stopping_round_ = new_config->early_stopping_round;
  shrinkage_rate_ = new_config->learning_rate;
  if (tree_learner_ != nullptr) {
    tree_learner_->ResetConfig(&new_config->tree_config);
781
  }
Guolin Ke's avatar
Guolin Ke committed
782
783
  if (train_data_ != nullptr) {
    ResetBaggingConfig(new_config.get(), false);
784
  }
Guolin Ke's avatar
Guolin Ke committed
785
  gbdt_config_.reset(new_config.release());
Guolin Ke's avatar
Guolin Ke committed
786
787
}

Guolin Ke's avatar
Guolin Ke committed
788
789
790
791
792
793
794
void GBDT::ResetBaggingConfig(const BoostingConfig* config, bool is_change_dataset) {
  // if need bagging, create buffer
  if (config->bagging_fraction < 1.0 && config->bagging_freq > 0) {
    bag_data_cnt_ =
      static_cast<data_size_t>(config->bagging_fraction * num_data_);
    bag_data_indices_.resize(num_data_);
    tmp_indices_.resize(num_data_);
795

Guolin Ke's avatar
Guolin Ke committed
796
797
798
799
800
    offsets_buf_.resize(num_threads_);
    left_cnts_buf_.resize(num_threads_);
    right_cnts_buf_.resize(num_threads_);
    left_write_pos_buf_.resize(num_threads_);
    right_write_pos_buf_.resize(num_threads_);
801

Guolin Ke's avatar
Guolin Ke committed
802
803
804
805
806
807
    double average_bag_rate = config->bagging_fraction / config->bagging_freq;
    int sparse_group = 0;
    for (int i = 0; i < train_data_->num_feature_groups(); ++i) {
      if (train_data_->FeatureGroupIsSparse(i)) {
        ++sparse_group;
      }
Guolin Ke's avatar
Guolin Ke committed
808
    }
Guolin Ke's avatar
Guolin Ke committed
809
810
811
812
813
814
815
816
817
818
819
    is_use_subset_ = false;
    const int group_threshold_usesubset = 100;
    const int sparse_group_threshold_usesubset = train_data_->num_feature_groups() / 4;
    if (average_bag_rate <= 0.5
        && (train_data_->num_feature_groups() < group_threshold_usesubset || sparse_group < sparse_group_threshold_usesubset)) {
      if (tmp_subset_ == nullptr || is_change_dataset) {
        tmp_subset_.reset(new Dataset(bag_data_cnt_));
        tmp_subset_->CopyFeatureMapperFrom(train_data_);
      }
      is_use_subset_ = true;
      Log::Debug("use subset for bagging");
Guolin Ke's avatar
Guolin Ke committed
820
821
    }

Guolin Ke's avatar
Guolin Ke committed
822
823
    if (is_change_dataset) {
      need_re_bagging_ = true;
Guolin Ke's avatar
Guolin Ke committed
824
    }
825

Guolin Ke's avatar
Guolin Ke committed
826
827
828
829
830
    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);
831
      }
832
    }
833
  } else {
Guolin Ke's avatar
Guolin Ke committed
834
835
836
837
    bag_data_cnt_ = num_data_;
    bag_data_indices_.clear();
    tmp_indices_.clear();
    is_use_subset_ = false;
838
  }
wxchan's avatar
wxchan committed
839
840
}

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