gbdt.cpp 36.7 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
9
10
11
12
13
14
15
#include <LightGBM/utils/common.h>

#include <LightGBM/objective_function.h>
#include <LightGBM/metric.h>

#include <ctime>

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

namespace LightGBM {

Guolin Ke's avatar
Guolin Ke committed
20
21
22
#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
23
std::chrono::duration<double, std::milli> out_of_bag_score_time;
Guolin Ke's avatar
Guolin Ke committed
24
25
26
27
28
29
30
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> sub_gradient_time;
std::chrono::duration<double, std::milli> tree_time;
#endif // TIMETAG

31
GBDT::GBDT()
32
  :iter_(0),
33
  train_data_(nullptr),
34
  objective_function_(nullptr),
35
36
  early_stopping_round_(0),
  max_feature_idx_(0),
37
  num_tree_per_iteration_(1),
38
  num_class_(1),
39
  num_iteration_for_pred_(0),
40
  shrinkage_rate_(0.1f),
41
42
  num_init_iteration_(0),
  boost_from_average_(false) {
Guolin Ke's avatar
Guolin Ke committed
43
44
  #pragma omp parallel
  #pragma omp master
45
46
47
    {
      num_threads_ = omp_get_num_threads();
    }
Guolin Ke's avatar
Guolin Ke committed
48
49
50
}

GBDT::~GBDT() {
Guolin Ke's avatar
Guolin Ke committed
51
  #ifdef TIMETAG
Guolin Ke's avatar
Guolin Ke committed
52
53
  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
54
  Log::Info("GBDT::out_of_bag_score costs %f", out_of_bag_score_time * 1e-3);
Guolin Ke's avatar
Guolin Ke committed
55
56
57
58
59
  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::sub_gradient costs %f", sub_gradient_time * 1e-3);
  Log::Info("GBDT::tree costs %f", tree_time * 1e-3);
Guolin Ke's avatar
Guolin Ke committed
60
  #endif
Guolin Ke's avatar
Guolin Ke committed
61
62
}

63
void GBDT::Init(const BoostingConfig* config, const Dataset* train_data, const ObjectiveFunction* objective_function,
64
                const std::vector<const Metric*>& training_metrics) {
65
  iter_ = 0;
wxchan's avatar
wxchan committed
66
  num_iteration_for_pred_ = 0;
67
  max_feature_idx_ = 0;
wxchan's avatar
wxchan committed
68
69
  num_class_ = config->num_class;
  train_data_ = nullptr;
Guolin Ke's avatar
Guolin Ke committed
70
  gbdt_config_ = nullptr;
71
  tree_learner_ = nullptr;
72
  ResetTrainingData(config, train_data, objective_function, training_metrics);
wxchan's avatar
wxchan committed
73
74
}

75
void GBDT::ResetTrainingData(const BoostingConfig* config, const Dataset* train_data, const ObjectiveFunction* objective_function,
76
                             const std::vector<const Metric*>& training_metrics) {
Guolin Ke's avatar
Guolin Ke committed
77
  auto new_config = std::unique_ptr<BoostingConfig>(new BoostingConfig(*config));
wxchan's avatar
wxchan committed
78
79
80
  if (train_data_ != nullptr && !train_data_->CheckAlign(*train_data)) {
    Log::Fatal("cannot reset training data, since new training data has different bin mappers");
  }
Guolin Ke's avatar
Guolin Ke committed
81
82
83
  early_stopping_round_ = new_config->early_stopping_round;
  shrinkage_rate_ = new_config->learning_rate;

84
85
86
87
  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
88
    num_tree_per_iteration_ = objective_function_->NumTreePerIteration();
89
90
91
  } else {
    is_constant_hessian_ = false;
  }
Guolin Ke's avatar
Guolin Ke committed
92

Guolin Ke's avatar
Guolin Ke committed
93
  if (train_data_ != train_data && train_data != nullptr) {
94
    if (tree_learner_ == nullptr) {
95
      tree_learner_ = std::unique_ptr<TreeLearner>(TreeLearner::CreateTreeLearner(new_config->tree_learner_type, new_config->device_type, &new_config->tree_config));
Guolin Ke's avatar
Guolin Ke committed
96
97
    }
    // init tree learner
98
    tree_learner_->Init(train_data, is_constant_hessian_);
Guolin Ke's avatar
Guolin Ke committed
99

Guolin Ke's avatar
Guolin Ke committed
100
101
102
103
104
105
    // push training metrics
    training_metrics_.clear();
    for (const auto& metric : training_metrics) {
      training_metrics_.push_back(metric);
    }
    training_metrics_.shrink_to_fit();
wxchan's avatar
wxchan committed
106
107
    // not same training data, need reset score and others
    // create score tracker
108
    train_score_updater_.reset(new ScoreUpdater(train_data, num_tree_per_iteration_));
wxchan's avatar
wxchan committed
109
110
    // update score
    for (int i = 0; i < iter_; ++i) {
111
112
113
      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);
wxchan's avatar
wxchan committed
114
115
116
117
      }
    }
    num_data_ = train_data->num_data();
    // create buffer for gradients and hessians
118
119
120
121
122
    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);
    }
wxchan's avatar
wxchan committed
123
124
125
126
    // get max feature index
    max_feature_idx_ = train_data->num_total_features() - 1;
    // get label index
    label_idx_ = train_data->label_idx();
127
128
    // get feature names
    feature_names_ = train_data->feature_names();
Guolin Ke's avatar
Guolin Ke committed
129
130

    feature_infos_ = train_data->feature_infos();
Guolin Ke's avatar
Guolin Ke committed
131
132
  }

Guolin Ke's avatar
Guolin Ke committed
133
  if ((train_data_ != train_data && train_data != nullptr)
134
      || (gbdt_config_ != nullptr && gbdt_config_->bagging_fraction != new_config->bagging_fraction)) {
wxchan's avatar
wxchan committed
135
    // if need bagging, create buffer
Guolin Ke's avatar
Guolin Ke committed
136
    if (new_config->bagging_fraction < 1.0 && new_config->bagging_freq > 0) {
137
138
      bag_data_cnt_ =
        static_cast<data_size_t>(new_config->bagging_fraction * num_data_);
139
      bag_data_indices_.resize(num_data_);
140
141
142
143
144
145
      tmp_indices_.resize(num_data_);
      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_);
Guolin Ke's avatar
Guolin Ke committed
146
147
      double average_bag_rate = new_config->bagging_fraction / new_config->bagging_freq;
      is_use_subset_ = false;
148
      if (average_bag_rate <= 0.5) {
Guolin Ke's avatar
Guolin Ke committed
149
        tmp_subset_.reset(new Dataset(bag_data_cnt_));
150
        tmp_subset_->CopyFeatureMapperFrom(train_data);
Guolin Ke's avatar
Guolin Ke committed
151
152
153
        is_use_subset_ = true;
        Log::Debug("use subset for bagging");
      }
wxchan's avatar
wxchan committed
154
155
156
    } else {
      bag_data_cnt_ = num_data_;
      bag_data_indices_.clear();
157
      tmp_indices_.clear();
Guolin Ke's avatar
Guolin Ke committed
158
      is_use_subset_ = false;
wxchan's avatar
wxchan committed
159
    }
Guolin Ke's avatar
Guolin Ke committed
160
  }
wxchan's avatar
wxchan committed
161
  train_data_ = train_data;
Guolin Ke's avatar
Guolin Ke committed
162
163
  if (train_data_ != nullptr) {
    // reset config for tree learner
164
    tree_learner_->ResetConfig(&new_config->tree_config);
165
166
167
    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_);
168
      // + 1 here for the binary classification
Guolin Ke's avatar
Guolin Ke committed
169
      class_default_output_ = std::vector<double>(num_tree_per_iteration_, 0.0f);
170
      auto label = train_data_->metadata().label();
171
      if (num_tree_per_iteration_ > 1) {
Guolin Ke's avatar
Guolin Ke committed
172
173
174
        // 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) {
175
176
177
          int index = static_cast<int>(label[i]);
          CHECK(index < num_tree_per_iteration_);
          ++cnt_per_class[index];
Guolin Ke's avatar
Guolin Ke committed
178
        }
179
        for (int i = 0; i < num_tree_per_iteration_; ++i) {
180
181
182
183
184
          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;
185
            class_default_output_[i] = -std::log(1.0f / kEpsilon - 1.0f);
186
187
188
          }
        }
      } else {
Guolin Ke's avatar
Guolin Ke committed
189
190
191
192
193
194
195
196
        // 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) {
197
198
          class_need_train_[0] = false;
          class_default_output_[0] = -std::log(1.0f / kEpsilon - 1.0f);
Guolin Ke's avatar
Guolin Ke committed
199
        } else if (cnt_pos == num_data_) {
200
201
202
203
204
          class_need_train_[0] = false;
          class_default_output_[0] = -std::log(kEpsilon);
        }
      }
    }
Guolin Ke's avatar
Guolin Ke committed
205
  }
Guolin Ke's avatar
Guolin Ke committed
206
  gbdt_config_.reset(new_config.release());
Guolin Ke's avatar
Guolin Ke committed
207
208
}

wxchan's avatar
wxchan committed
209
void GBDT::AddValidDataset(const Dataset* valid_data,
210
                           const std::vector<const Metric*>& valid_metrics) {
wxchan's avatar
wxchan committed
211
212
  if (!train_data_->CheckAlign(*valid_data)) {
    Log::Fatal("cannot add validation data, since it has different bin mappers with training data");
213
  }
Guolin Ke's avatar
Guolin Ke committed
214
  // for a validation dataset, we need its score and metric
215
  auto new_score_updater = std::unique_ptr<ScoreUpdater>(new ScoreUpdater(valid_data, num_tree_per_iteration_));
wxchan's avatar
wxchan committed
216
217
  // update score
  for (int i = 0; i < iter_; ++i) {
218
219
220
    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
221
222
    }
  }
Guolin Ke's avatar
Guolin Ke committed
223
  valid_score_updater_.push_back(std::move(new_score_updater));
Guolin Ke's avatar
Guolin Ke committed
224
  valid_metrics_.emplace_back();
225
226
227
  if (early_stopping_round_ > 0) {
    best_iter_.emplace_back();
    best_score_.emplace_back();
Guolin Ke's avatar
Guolin Ke committed
228
    best_msg_.emplace_back();
229
  }
Guolin Ke's avatar
Guolin Ke committed
230
231
  for (const auto& metric : valid_metrics) {
    valid_metrics_.back().push_back(metric);
232
233
234
    if (early_stopping_round_ > 0) {
      best_iter_.back().push_back(0);
      best_score_.back().push_back(kMinScore);
Guolin Ke's avatar
Guolin Ke committed
235
      best_msg_.back().emplace_back();
236
    }
Guolin Ke's avatar
Guolin Ke committed
237
  }
Guolin Ke's avatar
Guolin Ke committed
238
  valid_metrics_.back().shrink_to_fit();
Guolin Ke's avatar
Guolin Ke committed
239
240
}

241
data_size_t GBDT::BaggingHelper(Random& cur_rand, data_size_t start, data_size_t cnt, data_size_t* buffer) {
242
243
244
  if (cnt <= 0) {
    return 0;
  }
245
246
247
248
  data_size_t bag_data_cnt =
    static_cast<data_size_t>(gbdt_config_->bagging_fraction * cnt);
  data_size_t cur_left_cnt = 0;
  data_size_t cur_right_cnt = 0;
Guolin Ke's avatar
Guolin Ke committed
249
  auto right_buffer = buffer + bag_data_cnt;
250
251
  // random bagging, minimal unit is one record
  for (data_size_t i = 0; i < cnt; ++i) {
Guolin Ke's avatar
Guolin Ke committed
252
253
254
    float prob =
      (bag_data_cnt - cur_left_cnt) / static_cast<float>(cnt - i);
    if (cur_rand.NextFloat() < prob) {
255
256
      buffer[cur_left_cnt++] = start + i;
    } else {
Guolin Ke's avatar
Guolin Ke committed
257
      right_buffer[cur_right_cnt++] = start + i;
258
259
260
261
262
    }
  }
  CHECK(cur_left_cnt == bag_data_cnt);
  return cur_left_cnt;
}
Guolin Ke's avatar
Guolin Ke committed
263

Guolin Ke's avatar
Guolin Ke committed
264
265


266
void GBDT::Bagging(int iter) {
Guolin Ke's avatar
Guolin Ke committed
267
  // if need bagging
268
  if (bag_data_cnt_ < num_data_ && iter % gbdt_config_->bagging_freq == 0) {
Guolin Ke's avatar
Guolin Ke committed
269
    const data_size_t min_inner_size = 1000;
270
271
    data_size_t inner_size = (num_data_ + num_threads_ - 1) / num_threads_;
    if (inner_size < min_inner_size) { inner_size = min_inner_size; }
272
    OMP_INIT_EX();
Guolin Ke's avatar
Guolin Ke committed
273
    #pragma omp parallel for schedule(static,1)
274
    for (int i = 0; i < num_threads_; ++i) {
275
      OMP_LOOP_EX_BEGIN();
276
277
278
279
280
281
      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
282
283
      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);
284
285
286
      offsets_buf_[i] = cur_start;
      left_cnts_buf_[i] = cur_left_count;
      right_cnts_buf_[i] = cur_cnt - cur_left_count;
287
      OMP_LOOP_EX_END();
288
    }
289
    OMP_THROW_EX();
290
291
292
293
294
295
296
297
298
    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
299
    #pragma omp parallel for schedule(static, 1)
300
    for (int i = 0; i < num_threads_; ++i) {
301
      OMP_LOOP_EX_BEGIN();
302
303
      if (left_cnts_buf_[i] > 0) {
        std::memcpy(bag_data_indices_.data() + left_write_pos_buf_[i],
304
                    tmp_indices_.data() + offsets_buf_[i], left_cnts_buf_[i] * sizeof(data_size_t));
Guolin Ke's avatar
Guolin Ke committed
305
      }
306
307
      if (right_cnts_buf_[i] > 0) {
        std::memcpy(bag_data_indices_.data() + left_cnt + right_write_pos_buf_[i],
308
                    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
309
      }
310
      OMP_LOOP_EX_END();
Guolin Ke's avatar
Guolin Ke committed
311
    }
312
    OMP_THROW_EX();
Guolin Ke's avatar
Guolin Ke committed
313
314
    bag_data_cnt_ = left_cnt;
    CHECK(bag_data_indices_[bag_data_cnt_ - 1] > bag_data_indices_[bag_data_cnt_]);
Guolin Ke's avatar
Guolin Ke committed
315
    Log::Debug("Re-bagging, using %d data to train", bag_data_cnt_);
Guolin Ke's avatar
Guolin Ke committed
316
    // set bagging data to tree learner
Guolin Ke's avatar
Guolin Ke committed
317
318
319
320
    if (!is_use_subset_) {
      tree_learner_->SetBaggingData(bag_data_indices_.data(), bag_data_cnt_);
    } else {
      // get subset
Guolin Ke's avatar
Guolin Ke committed
321
322
      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
323
324
      tree_learner_->ResetTrainingData(tmp_subset_.get());
    }
Guolin Ke's avatar
Guolin Ke committed
325
326
327
  }
}

328
void GBDT::UpdateScoreOutOfBag(const Tree* tree, const int cur_tree_id) {
Guolin Ke's avatar
Guolin Ke committed
329
  #ifdef TIMETAG
Guolin Ke's avatar
Guolin Ke committed
330
  auto start_time = std::chrono::steady_clock::now();
Guolin Ke's avatar
Guolin Ke committed
331
  #endif
332
  // we need to predict out-of-bag scores of data for boosting
Guolin Ke's avatar
Guolin Ke committed
333
  if (num_data_ - bag_data_cnt_ > 0 && !is_use_subset_) {
334
    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
335
  }
Guolin Ke's avatar
Guolin Ke committed
336
  #ifdef TIMETAG
Guolin Ke's avatar
Guolin Ke committed
337
  out_of_bag_score_time += std::chrono::steady_clock::now() - start_time;
Guolin Ke's avatar
Guolin Ke committed
338
  #endif
Guolin Ke's avatar
Guolin Ke committed
339
340
}

341
bool GBDT::TrainOneIter(const score_t* gradient, const score_t* hessian, bool is_eval) {
342
  // boosting from average prediction. It doesn't work well for classification, remove it for now.
Guolin Ke's avatar
Guolin Ke committed
343
344
  if (models_.empty()
      && gbdt_config_->boost_from_average
345
      && !train_score_updater_->has_init_score()
346
347
348
      && num_class_ <= 1
      && objective_function_ != nullptr
      && objective_function_->BoostFromAverage()) {
349
    double init_score = 0.0f;
350
    auto label = train_data_->metadata().label();
351
352
353
    #pragma omp parallel for schedule(static) reduction(+:init_score)
    for (data_size_t i = 0; i < num_data_; ++i) {
      init_score += label[i];
354
    }
355
356
    init_score /= num_data_;
    std::unique_ptr<Tree> new_tree(new Tree(2));
Guolin Ke's avatar
Guolin Ke committed
357
    new_tree->Split(0, 0, BinType::NumericalBin, 0, 0, 0, init_score, init_score, 0, num_data_, -1);
358
359
360
361
362
    train_score_updater_->AddScore(init_score, 0);
    for (auto& score_updater : valid_score_updater_) {
      score_updater->AddScore(init_score, 0);
    }
    models_.push_back(std::move(new_tree));
363
364
    boost_from_average_ = true;
  }
Guolin Ke's avatar
Guolin Ke committed
365
366
  // boosting first
  if (gradient == nullptr || hessian == nullptr) {
Guolin Ke's avatar
Guolin Ke committed
367
    #ifdef TIMETAG
Guolin Ke's avatar
Guolin Ke committed
368
    auto start_time = std::chrono::steady_clock::now();
Guolin Ke's avatar
Guolin Ke committed
369
    #endif
Guolin Ke's avatar
Guolin Ke committed
370
    Boosting();
371
372
    gradient = gradients_.data();
    hessian = hessians_.data();
Guolin Ke's avatar
Guolin Ke committed
373
    #ifdef TIMETAG
Guolin Ke's avatar
Guolin Ke committed
374
    boosting_time += std::chrono::steady_clock::now() - start_time;
Guolin Ke's avatar
Guolin Ke committed
375
    #endif
Guolin Ke's avatar
Guolin Ke committed
376
  }
Guolin Ke's avatar
Guolin Ke committed
377
  #ifdef TIMETAG
Guolin Ke's avatar
Guolin Ke committed
378
  auto start_time = std::chrono::steady_clock::now();
Guolin Ke's avatar
Guolin Ke committed
379
  #endif
380
381
  // bagging logic
  Bagging(iter_);
Guolin Ke's avatar
Guolin Ke committed
382
  #ifdef TIMETAG
Guolin Ke's avatar
Guolin Ke committed
383
  bagging_time += std::chrono::steady_clock::now() - start_time;
Guolin Ke's avatar
Guolin Ke committed
384
  #endif
Guolin Ke's avatar
Guolin Ke committed
385
  if (is_use_subset_ && bag_data_cnt_ < num_data_) {
Guolin Ke's avatar
Guolin Ke committed
386
    #ifdef TIMETAG
Guolin Ke's avatar
Guolin Ke committed
387
    start_time = std::chrono::steady_clock::now();
Guolin Ke's avatar
Guolin Ke committed
388
    #endif
389
390
391
392
393
    if (gradients_.empty()) {
      size_t total_size = static_cast<size_t>(num_data_) * num_tree_per_iteration_;
      gradients_.resize(total_size);
      hessians_.resize(total_size);
    }
Guolin Ke's avatar
Guolin Ke committed
394
    // get sub gradients
395
    for (int cur_tree_id = 0; cur_tree_id < num_tree_per_iteration_; ++cur_tree_id) {
396
      size_t bias = static_cast<size_t>(cur_tree_id)* num_data_;
397
      // cannot multi-threading here.
Guolin Ke's avatar
Guolin Ke committed
398
      for (int i = 0; i < bag_data_cnt_; ++i) {
399
400
        gradients_[bias + i] = gradient[bias + bag_data_indices_[i]];
        hessians_[bias + i] = hessian[bias + bag_data_indices_[i]];
Guolin Ke's avatar
Guolin Ke committed
401
402
      }
    }
403
404
    gradient = gradients_.data();
    hessian = hessians_.data();
Guolin Ke's avatar
Guolin Ke committed
405
    #ifdef TIMETAG
Guolin Ke's avatar
Guolin Ke committed
406
    sub_gradient_time += std::chrono::steady_clock::now() - start_time;
Guolin Ke's avatar
Guolin Ke committed
407
    #endif
Guolin Ke's avatar
Guolin Ke committed
408
  }
Guolin Ke's avatar
Guolin Ke committed
409
  bool should_continue = false;
410
  for (int cur_tree_id = 0; cur_tree_id < num_tree_per_iteration_; ++cur_tree_id) {
Guolin Ke's avatar
Guolin Ke committed
411
    #ifdef TIMETAG
Guolin Ke's avatar
Guolin Ke committed
412
    start_time = std::chrono::steady_clock::now();
Guolin Ke's avatar
Guolin Ke committed
413
    #endif
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_;
417
      new_tree.reset(
418
        tree_learner_->Train(gradient + bias, hessian + bias, is_constant_hessian_));
419
    }
Guolin Ke's avatar
Guolin Ke committed
420
    #ifdef TIMETAG
Guolin Ke's avatar
Guolin Ke committed
421
    tree_time += std::chrono::steady_clock::now() - start_time;
Guolin Ke's avatar
Guolin Ke committed
422
    #endif
Guolin Ke's avatar
Guolin Ke committed
423
424

    if (new_tree->num_leaves() > 1) {
Guolin Ke's avatar
Guolin Ke committed
425
426
427
428
      should_continue = true;
      // shrinkage by learning rate
      new_tree->Shrinkage(shrinkage_rate_);
      // update score
429
430
      UpdateScore(new_tree.get(), cur_tree_id);
      UpdateScoreOutOfBag(new_tree.get(), cur_tree_id);
431
432
    } else {
      // only add default score one-time
433
434
      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];
Guolin Ke's avatar
Guolin Ke committed
435
        new_tree->Split(0, 0, BinType::NumericalBin, 0, 0, 0,
Guolin Ke's avatar
Guolin Ke committed
436
                        output, output, 0, num_data_, -1);
437
        train_score_updater_->AddScore(output, cur_tree_id);
438
        for (auto& score_updater : valid_score_updater_) {
439
          score_updater->AddScore(output, cur_tree_id);
440
441
442
        }
      }
    }
Guolin Ke's avatar
Guolin Ke committed
443
444
445
    // add model
    models_.push_back(std::move(new_tree));
  }
Guolin Ke's avatar
Guolin Ke committed
446
  if (!should_continue) {
Guolin Ke's avatar
Guolin Ke committed
447
    Log::Warning("Stopped training because there are no more leaves that meet the split requirements.");
448
    for (int cur_tree_id = 0; cur_tree_id < num_tree_per_iteration_; ++cur_tree_id) {
Guolin Ke's avatar
Guolin Ke committed
449
450
451
452
      models_.pop_back();
    }
    return true;
  }
Guolin Ke's avatar
Guolin Ke committed
453
454
455
456
457
458
  ++iter_;
  if (is_eval) {
    return EvalAndCheckEarlyStopping();
  } else {
    return false;
  }
459

Guolin Ke's avatar
Guolin Ke committed
460
}
461

wxchan's avatar
wxchan committed
462
void GBDT::RollbackOneIter() {
463
  if (iter_ <= 0) { return; }
wxchan's avatar
wxchan committed
464
465
  int cur_iter = iter_ + num_init_iteration_ - 1;
  // reset score
466
467
  for (int cur_tree_id = 0; cur_tree_id < num_tree_per_iteration_; ++cur_tree_id) {
    auto curr_tree = cur_iter * num_tree_per_iteration_ + cur_tree_id;
wxchan's avatar
wxchan committed
468
    models_[curr_tree]->Shrinkage(-1.0);
469
    train_score_updater_->AddScore(models_[curr_tree].get(), cur_tree_id);
wxchan's avatar
wxchan committed
470
    for (auto& score_updater : valid_score_updater_) {
471
      score_updater->AddScore(models_[curr_tree].get(), cur_tree_id);
wxchan's avatar
wxchan committed
472
473
474
    }
  }
  // remove model
475
  for (int cur_tree_id = 0; cur_tree_id < num_tree_per_iteration_; ++cur_tree_id) {
wxchan's avatar
wxchan committed
476
477
478
479
480
    models_.pop_back();
  }
  --iter_;
}

Guolin Ke's avatar
Guolin Ke committed
481
bool GBDT::EvalAndCheckEarlyStopping() {
482
  bool is_met_early_stopping = false;
Guolin Ke's avatar
Guolin Ke committed
483
  #ifdef TIMETAG
Guolin Ke's avatar
Guolin Ke committed
484
  auto start_time = std::chrono::steady_clock::now();
Guolin Ke's avatar
Guolin Ke committed
485
  #endif
486
  // print message for metric
Guolin Ke's avatar
Guolin Ke committed
487
  auto best_msg = OutputMetric(iter_);
Guolin Ke's avatar
Guolin Ke committed
488
  #ifdef TIMETAG
Guolin Ke's avatar
Guolin Ke committed
489
  metric_time += std::chrono::steady_clock::now() - start_time;
Guolin Ke's avatar
Guolin Ke committed
490
  #endif
Guolin Ke's avatar
Guolin Ke committed
491
  is_met_early_stopping = !best_msg.empty();
492
493
  if (is_met_early_stopping) {
    Log::Info("Early stopping at iteration %d, the best iteration round is %d",
494
              iter_, iter_ - early_stopping_round_);
Guolin Ke's avatar
Guolin Ke committed
495
    Log::Info("Output of best iteration round:\n%s", best_msg.c_str());
496
    // pop last early_stopping_round_ models
497
    for (int i = 0; i < early_stopping_round_ * num_tree_per_iteration_; ++i) {
498
499
500
501
      models_.pop_back();
    }
  }
  return is_met_early_stopping;
Guolin Ke's avatar
Guolin Ke committed
502
503
}

504
void GBDT::UpdateScore(const Tree* tree, const int cur_tree_id) {
Guolin Ke's avatar
Guolin Ke committed
505
  #ifdef TIMETAG
Guolin Ke's avatar
Guolin Ke committed
506
  auto start_time = std::chrono::steady_clock::now();
Guolin Ke's avatar
Guolin Ke committed
507
  #endif
Guolin Ke's avatar
Guolin Ke committed
508
  // update training score
Guolin Ke's avatar
Guolin Ke committed
509
  if (!is_use_subset_) {
510
    train_score_updater_->AddScore(tree_learner_.get(), tree, cur_tree_id);
Guolin Ke's avatar
Guolin Ke committed
511
  } else {
512
    train_score_updater_->AddScore(tree, cur_tree_id);
Guolin Ke's avatar
Guolin Ke committed
513
  }
Guolin Ke's avatar
Guolin Ke committed
514
  #ifdef TIMETAG
Guolin Ke's avatar
Guolin Ke committed
515
  train_score_time += std::chrono::steady_clock::now() - start_time;
Guolin Ke's avatar
Guolin Ke committed
516
517
  #endif
  #ifdef TIMETAG
Guolin Ke's avatar
Guolin Ke committed
518
  start_time = std::chrono::steady_clock::now();
Guolin Ke's avatar
Guolin Ke committed
519
  #endif
Guolin Ke's avatar
Guolin Ke committed
520
  // update validation score
Guolin Ke's avatar
Guolin Ke committed
521
  for (auto& score_updater : valid_score_updater_) {
522
    score_updater->AddScore(tree, cur_tree_id);
Guolin Ke's avatar
Guolin Ke committed
523
  }
Guolin Ke's avatar
Guolin Ke committed
524
  #ifdef TIMETAG
Guolin Ke's avatar
Guolin Ke committed
525
  valid_score_time += std::chrono::steady_clock::now() - start_time;
Guolin Ke's avatar
Guolin Ke committed
526
  #endif
Guolin Ke's avatar
Guolin Ke committed
527
528
}

Guolin Ke's avatar
Guolin Ke committed
529
530
531
532
std::string GBDT::OutputMetric(int iter) {
  bool need_output = (iter % gbdt_config_->output_freq) == 0;
  std::string ret = "";
  std::stringstream msg_buf;
533
  std::vector<std::pair<size_t, size_t>> meet_early_stopping_pairs;
Guolin Ke's avatar
Guolin Ke committed
534
  // print training metric
Guolin Ke's avatar
Guolin Ke committed
535
  if (need_output) {
536
537
    for (auto& sub_metric : training_metrics_) {
      auto name = sub_metric->GetName();
Guolin Ke's avatar
Guolin Ke committed
538
      auto scores = sub_metric->Eval(train_score_updater_->score(), objective_function_);
Guolin Ke's avatar
Guolin Ke committed
539
      for (size_t k = 0; k < name.size(); ++k) {
Guolin Ke's avatar
Guolin Ke committed
540
541
542
543
544
545
546
547
        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) {
          msg_buf << tmp_buf.str() << std::endl;
        }
548
      }
549
    }
Guolin Ke's avatar
Guolin Ke committed
550
551
  }
  // print validation metric
Guolin Ke's avatar
Guolin Ke committed
552
  if (need_output || early_stopping_round_ > 0) {
553
554
    for (size_t i = 0; i < valid_metrics_.size(); ++i) {
      for (size_t j = 0; j < valid_metrics_[i].size(); ++j) {
555
        auto test_scores = valid_metrics_[i][j]->Eval(valid_score_updater_[i]->score(),
Guolin Ke's avatar
Guolin Ke committed
556
                                                      objective_function_);
Guolin Ke's avatar
Guolin Ke committed
557
558
559
560
561
562
563
564
565
566
567
        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) {
            msg_buf << tmp_buf.str() << std::endl;
568
          }
wxchan's avatar
wxchan committed
569
        }
Guolin Ke's avatar
Guolin Ke committed
570
        if (ret.empty() && early_stopping_round_ > 0) {
571
572
573
          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;
574
            best_iter_[i][j] = iter;
Guolin Ke's avatar
Guolin Ke committed
575
            meet_early_stopping_pairs.emplace_back(i, j);
576
          } else {
Guolin Ke's avatar
Guolin Ke committed
577
            if (iter - best_iter_[i][j] >= early_stopping_round_) { ret = best_msg_[i][j]; }
578
          }
wxchan's avatar
wxchan committed
579
580
        }
      }
Guolin Ke's avatar
Guolin Ke committed
581
582
    }
  }
Guolin Ke's avatar
Guolin Ke committed
583
584
585
  for (auto& pair : meet_early_stopping_pairs) {
    best_msg_[pair.first][pair.second] = msg_buf.str();
  }
wxchan's avatar
wxchan committed
586
  return ret;
Guolin Ke's avatar
Guolin Ke committed
587
588
}

589
/*! \brief Get eval result */
590
std::vector<double> GBDT::GetEvalAt(int data_idx) const {
Guolin Ke's avatar
Guolin Ke committed
591
  CHECK(data_idx >= 0 && data_idx <= static_cast<int>(valid_score_updater_.size()));
592
593
  std::vector<double> ret;
  if (data_idx == 0) {
594
    for (auto& sub_metric : training_metrics_) {
Guolin Ke's avatar
Guolin Ke committed
595
      auto scores = sub_metric->Eval(train_score_updater_->score(), objective_function_);
596
597
598
      for (auto score : scores) {
        ret.push_back(score);
      }
599
    }
600
  } else {
601
602
    auto used_idx = data_idx - 1;
    for (size_t j = 0; j < valid_metrics_[used_idx].size(); ++j) {
603
      auto test_scores = valid_metrics_[used_idx][j]->Eval(valid_score_updater_[used_idx]->score(),
Guolin Ke's avatar
Guolin Ke committed
604
                                                           objective_function_);
605
606
607
      for (auto score : test_scores) {
        ret.push_back(score);
      }
608
609
610
611
612
    }
  }
  return ret;
}

Guolin Ke's avatar
Guolin Ke committed
613
/*! \brief Get training scores result */
614
const double* GBDT::GetTrainingScore(int64_t* out_len) {
615
  *out_len = static_cast<int64_t>(train_score_updater_->num_data()) * num_class_;
Guolin Ke's avatar
Guolin Ke committed
616
  return train_score_updater_->score();
617
618
}

Guolin Ke's avatar
Guolin Ke committed
619
620
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
621

622
  const double* raw_scores = nullptr;
Guolin Ke's avatar
Guolin Ke committed
623
624
  data_size_t num_data = 0;
  if (data_idx == 0) {
wxchan's avatar
wxchan committed
625
    raw_scores = GetTrainingScore(out_len);
Guolin Ke's avatar
Guolin Ke committed
626
627
628
629
630
    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();
631
    *out_len = static_cast<int64_t>(num_data) * num_class_;
Guolin Ke's avatar
Guolin Ke committed
632
  }
633
  if (objective_function_ != nullptr) {
Guolin Ke's avatar
Guolin Ke committed
634
635
    #pragma omp parallel for schedule(static)
    for (data_size_t i = 0; i < num_data; ++i) {
Guolin Ke's avatar
Guolin Ke committed
636
      std::vector<double> tree_pred(num_tree_per_iteration_);
637
      for (int j = 0; j < num_tree_per_iteration_; ++j) {
Guolin Ke's avatar
Guolin Ke committed
638
        tree_pred[j] = raw_scores[j * num_data + i];
639
      }
Guolin Ke's avatar
Guolin Ke committed
640
641
      std::vector<double> tmp_result(num_class_);
      objective_function_->ConvertOutput(tree_pred.data(), tmp_result.data());
Guolin Ke's avatar
Guolin Ke committed
642
      for (int j = 0; j < num_class_; ++j) {
643
        out_result[j * num_data + i] = static_cast<double>(tmp_result[j]);
Guolin Ke's avatar
Guolin Ke committed
644
645
      }
    }
646
  } else {
Guolin Ke's avatar
Guolin Ke committed
647
    #pragma omp parallel for schedule(static)
Guolin Ke's avatar
Guolin Ke committed
648
    for (data_size_t i = 0; i < num_data; ++i) {
Guolin Ke's avatar
Guolin Ke committed
649
      std::vector<double> tmp_result(num_tree_per_iteration_);
650
      for (int j = 0; j < num_tree_per_iteration_; ++j) {
Guolin Ke's avatar
Guolin Ke committed
651
        out_result[j * num_data + i] = static_cast<double>(raw_scores[j * num_data + i]);
Guolin Ke's avatar
Guolin Ke committed
652
653
654
655
656
      }
    }
  }
}

Guolin Ke's avatar
Guolin Ke committed
657
void GBDT::Boosting() {
658
  if (objective_function_ == nullptr) {
659
660
    Log::Fatal("No object function provided");
  }
Hui Xue's avatar
Hui Xue committed
661
  // objective function will calculate gradients and hessians
662
  int64_t num_score = 0;
663
  objective_function_->
Guolin Ke's avatar
Guolin Ke committed
664
    GetGradients(GetTrainingScore(&num_score), gradients_.data(), hessians_.data());
Guolin Ke's avatar
Guolin Ke committed
665
666
}

667
std::string GBDT::DumpModel(int num_iteration) const {
Guolin Ke's avatar
Guolin Ke committed
668
  std::stringstream str_buf;
wxchan's avatar
wxchan committed
669

Guolin Ke's avatar
Guolin Ke committed
670
  str_buf << "{";
Guolin Ke's avatar
Guolin Ke committed
671
  str_buf << "\"name\":\"" << SubModelName() << "\"," << std::endl;
Guolin Ke's avatar
Guolin Ke committed
672
  str_buf << "\"num_class\":" << num_class_ << "," << std::endl;
673
  str_buf << "\"num_tree_per_iteration\":" << num_tree_per_iteration_ << "," << std::endl;
Guolin Ke's avatar
Guolin Ke committed
674
675
  str_buf << "\"label_index\":" << label_idx_ << "," << std::endl;
  str_buf << "\"max_feature_idx\":" << max_feature_idx_ << "," << std::endl;
wxchan's avatar
wxchan committed
676

677
678
679
  str_buf << "\"feature_names\":[\""
    << Common::Join(feature_names_, "\",\"") << "\"],"
    << std::endl;
Guolin Ke's avatar
Guolin Ke committed
680

Guolin Ke's avatar
Guolin Ke committed
681
  str_buf << "\"tree_info\":[";
682
683
  int num_used_model = static_cast<int>(models_.size());
  if (num_iteration > 0) {
Guolin Ke's avatar
Guolin Ke committed
684
    num_iteration += boost_from_average_ ? 1 : 0;
685
    num_used_model = std::min(num_iteration * num_tree_per_iteration_, num_used_model);
686
  }
687
  for (int i = 0; i < num_used_model; ++i) {
wxchan's avatar
wxchan committed
688
    if (i > 0) {
Guolin Ke's avatar
Guolin Ke committed
689
      str_buf << ",";
wxchan's avatar
wxchan committed
690
    }
Guolin Ke's avatar
Guolin Ke committed
691
692
693
694
    str_buf << "{";
    str_buf << "\"tree_index\":" << i << ",";
    str_buf << models_[i]->ToJSON();
    str_buf << "}";
wxchan's avatar
wxchan committed
695
  }
Guolin Ke's avatar
Guolin Ke committed
696
  str_buf << "]" << std::endl;
wxchan's avatar
wxchan committed
697

Guolin Ke's avatar
Guolin Ke committed
698
  str_buf << "}" << std::endl;
wxchan's avatar
wxchan committed
699

Guolin Ke's avatar
Guolin Ke committed
700
  return str_buf.str();
wxchan's avatar
wxchan committed
701
702
}

703
704
705
706
707
708
709
710
711
712
713
714
715
716
717
718
719
720
721
722
723
724
725
726
727
728
729
730
731
732
733
734
735
736
737
738
739
740
741
742
743
744
745
746
747
748
749
750
751
752
753
754
755
756
757
758
759
760
761
762
763
764
765
766
767
768
769
770
771
772
773
774
775
776
777
778
779
780
781
782
783
784
785
786
787
788
789
790
791
792
793
794
795
std::string GBDT::ModelToIfElse(int num_iteration) const {
  std::stringstream str_buf;

  int num_used_model = static_cast<int>(models_.size());
  if (num_iteration > 0) {
    num_iteration += boost_from_average_ ? 1 : 0;
    num_used_model = std::min(num_iteration * num_tree_per_iteration_, num_used_model);
  }

  // PredictRaw
  for (int i = 0; i < num_used_model; ++i) {
    str_buf << models_[i]->ToIfElse(i, false) << std::endl;
  }

  str_buf << "double (*PredictTreePtr[])(const double*) = { ";
  for (int i = 0; i < num_used_model; ++i) {
    if (i > 0) {
      str_buf << " , ";
    }
    str_buf << "PredictTree" << i;
  }
  str_buf << " };" << std::endl << std::endl;

  std::stringstream pred_str_buf;

  pred_str_buf << "\t" << "if (num_threads_ <= num_tree_per_iteration_) {" << std::endl;
  pred_str_buf << "\t\t" << "#pragma omp parallel for schedule(static)" << std::endl;
  pred_str_buf << "\t\t" << "for (int k = 0; k < num_tree_per_iteration_; ++k) {" << std::endl;
  pred_str_buf << "\t\t\t" << "for (int i = 0; i < num_iteration_for_pred_; ++i) {" << std::endl;
  pred_str_buf << "\t\t\t\t" << "output[k] += (*PredictTreePtr[i * num_tree_per_iteration_ + k])(features);" << std::endl;
  pred_str_buf << "\t\t\t" << "}" << std::endl;
  pred_str_buf << "\t\t" << "}" << std::endl;
  pred_str_buf << "\t" << "} else {" << std::endl;
  pred_str_buf << "\t\t" << "for (int k = 0; k < num_tree_per_iteration_; ++k) {" << std::endl;
  pred_str_buf << "\t\t\t" << "double t = 0.0f;" << std::endl;
  pred_str_buf << "\t\t\t" << "#pragma omp parallel for schedule(static) reduction(+:t)" << std::endl;
  pred_str_buf << "\t\t\t" << "for (int i = 0; i < num_iteration_for_pred_; ++i) {" << std::endl;
  pred_str_buf << "\t\t\t\t" << "t += (*PredictTreePtr[i * num_tree_per_iteration_ + k])(features);" << std::endl;
  pred_str_buf << "\t\t\t" << "}" << std::endl;
  pred_str_buf << "\t\t\t" << "output[k] = t;" << std::endl;
  pred_str_buf << "\t\t" << "}" << std::endl;
  pred_str_buf << "\t" << "}" << std::endl;

  str_buf << "void GBDT::PredictRaw(const double* features, double *output) const {" << std::endl;
  str_buf << pred_str_buf.str();
  str_buf << "}" << std::endl;
  str_buf << std::endl;

  // Predict
  str_buf << "void GBDT::Predict(const double* features, double *output) const {" << std::endl;
  str_buf << pred_str_buf.str();
  str_buf << "\t" << "if (objective_function_ != nullptr) {" << std::endl;
  str_buf << "\t\t" << "objective_function_->ConvertOutput(output, output);" << std::endl;
  str_buf << "\t" << "}" << std::endl;
  str_buf << "}" << std::endl;
  str_buf << std::endl;

  // PredictLeafIndex
  for (int i = 0; i < num_used_model; ++i) {
    str_buf << models_[i]->ToIfElse(i, true) << std::endl;
  }

  str_buf << "double (*PredictTreeLeafPtr[])(const double*) = { ";
  for (int i = 0; i < num_used_model; ++i) {
    if (i > 0) {
      str_buf << " , ";
    }
    str_buf << "PredictTree" << i << "Leaf";
  }
  str_buf << " };" << std::endl << std::endl;

  str_buf << "void GBDT::PredictLeafIndex(const double* features, double *output) const {" << std::endl;
  str_buf << "\t" << "int total_tree = num_iteration_for_pred_ * num_tree_per_iteration_;" << std::endl;
  str_buf << "\t" << "#pragma omp parallel for schedule(static)" << std::endl;
  str_buf << "\t" << "for (int i = 0; i < total_tree; ++i) {" << std::endl;
  str_buf << "\t\t" << "output[i] = (*PredictTreeLeafPtr[i])(features);" << std::endl;
  str_buf << "\t" << "}" << std::endl;
  str_buf << "}" << std::endl;
  return str_buf.str();
}

bool GBDT::SaveModelToIfElse(int num_iteration, const char* filename) const {
  /*! \brief File to write models */
  std::ofstream output_file;
  output_file.open(filename);

  output_file << ModelToIfElse(num_iteration);

  output_file.close();

  return (bool)output_file;
}

Guolin Ke's avatar
Guolin Ke committed
796
std::string GBDT::SaveModelToString(int num_iteration) const {
797
  std::stringstream ss;
798

799
800
801
802
  // output model type
  ss << SubModelName() << std::endl;
  // output number of class
  ss << "num_class=" << num_class_ << std::endl;
803
  ss << "num_tree_per_iteration=" << num_tree_per_iteration_ << std::endl;
804
805
806
807
  // output label index
  ss << "label_index=" << label_idx_ << std::endl;
  // output max_feature_idx
  ss << "max_feature_idx=" << max_feature_idx_ << std::endl;
808
809
810
  // output objective
  if (objective_function_ != nullptr) {
    ss << "objective=" << objective_function_->ToString() << std::endl;
811
  }
812

813
814
815
  if (boost_from_average_) {
    ss << "boost_from_average" << std::endl;
  }
Guolin Ke's avatar
Guolin Ke committed
816

817
  ss << "feature_names=" << Common::Join(feature_names_, " ") << std::endl;
818

819
  ss << "feature_infos=" << Common::Join(feature_infos_, " ") << std::endl;
820

821
822
  ss << std::endl;
  int num_used_model = static_cast<int>(models_.size());
Guolin Ke's avatar
Guolin Ke committed
823
824
  if (num_iteration > 0) {
    num_iteration += boost_from_average_ ? 1 : 0;
825
    num_used_model = std::min(num_iteration * num_tree_per_iteration_, num_used_model);
826
827
828
829
830
831
832
833
834
835
836
837
838
839
  }
  // output tree models
  for (int i = 0; i < num_used_model; ++i) {
    ss << "Tree=" << i << std::endl;
    ss << models_[i]->ToString() << std::endl;
  }

  std::vector<std::pair<size_t, std::string>> pairs = FeatureImportance();
  ss << std::endl << "feature importances:" << std::endl;
  for (size_t i = 0; i < pairs.size(); ++i) {
    ss << pairs[i].second << "=" << std::to_string(pairs[i].first) << std::endl;
  }

  return ss.str();
840
841
}

842
bool GBDT::SaveModelToFile(int num_iteration, const char* filename) const {
wxchan's avatar
wxchan committed
843
844
845
  /*! \brief File to write models */
  std::ofstream output_file;
  output_file.open(filename);
846

847
  output_file << SaveModelToString(num_iteration);
848

wxchan's avatar
wxchan committed
849
  output_file.close();
850
851

  return (bool)output_file;
Guolin Ke's avatar
Guolin Ke committed
852
853
}

854
bool GBDT::LoadModelFromString(const std::string& model_str) {
Guolin Ke's avatar
Guolin Ke committed
855
856
857
  // use serialized string to restore this object
  models_.clear();
  std::vector<std::string> lines = Common::Split(model_str.c_str(), '\n');
858
859

  // get number of classes
860
861
862
863
  auto line = Common::FindFromLines(lines, "num_class=");
  if (line.size() > 0) {
    Common::Atoi(Common::Split(line.c_str(), '=')[1].c_str(), &num_class_);
  } else {
864
    Log::Fatal("Model file doesn't specify the number of classes");
865
    return false;
866
  }
867
868
869
870
871
872
873
874

  line = Common::FindFromLines(lines, "num_tree_per_iteration=");
  if (line.size() > 0) {
    Common::Atoi(Common::Split(line.c_str(), '=')[1].c_str(), &num_tree_per_iteration_);
  } else {
    num_tree_per_iteration_ = num_class_;
  }

Guolin Ke's avatar
Guolin Ke committed
875
  // get index of label
876
877
878
879
  line = Common::FindFromLines(lines, "label_index=");
  if (line.size() > 0) {
    Common::Atoi(Common::Split(line.c_str(), '=')[1].c_str(), &label_idx_);
  } else {
880
    Log::Fatal("Model file doesn't specify the label index");
881
    return false;
Guolin Ke's avatar
Guolin Ke committed
882
  }
Guolin Ke's avatar
Guolin Ke committed
883
  // get max_feature_idx first
884
885
886
887
  line = Common::FindFromLines(lines, "max_feature_idx=");
  if (line.size() > 0) {
    Common::Atoi(Common::Split(line.c_str(), '=')[1].c_str(), &max_feature_idx_);
  } else {
888
    Log::Fatal("Model file doesn't specify max_feature_idx");
889
    return false;
Guolin Ke's avatar
Guolin Ke committed
890
  }
891
892
893
894
895
  // get boost_from_average_
  line = Common::FindFromLines(lines, "boost_from_average");
  if (line.size() > 0) {
    boost_from_average_ = true;
  }
Guolin Ke's avatar
Guolin Ke committed
896
897
898
  // get feature names
  line = Common::FindFromLines(lines, "feature_names=");
  if (line.size() > 0) {
Guolin Ke's avatar
Guolin Ke committed
899
    feature_names_ = Common::Split(line.substr(std::strlen("feature_names=")).c_str(), " ");
Guolin Ke's avatar
Guolin Ke committed
900
901
    if (feature_names_.size() != static_cast<size_t>(max_feature_idx_ + 1)) {
      Log::Fatal("Wrong size of feature_names");
902
      return false;
Guolin Ke's avatar
Guolin Ke committed
903
    }
904
  } else {
Guolin Ke's avatar
Guolin Ke committed
905
    Log::Fatal("Model file doesn't contain feature names");
906
    return false;
Guolin Ke's avatar
Guolin Ke committed
907
908
  }

Guolin Ke's avatar
Guolin Ke committed
909
910
911
912
913
914
915
916
917
918
919
920
  line = Common::FindFromLines(lines, "feature_infos=");
  if (line.size() > 0) {
    feature_infos_ = Common::Split(line.substr(std::strlen("feature_infos=")).c_str(), " ");
    if (feature_infos_.size() != static_cast<size_t>(max_feature_idx_ + 1)) {
      Log::Fatal("Wrong size of feature_infos");
      return false;
    }
  } else {
    Log::Fatal("Model file doesn't contain feature infos");
    return false;
  }

921
922
923
924
925
926
927
928
  line = Common::FindFromLines(lines, "objective=");

  if (line.size() > 0) {
    auto str = Common::Split(line.c_str(), '=')[1];
    loaded_objective_.reset(ObjectiveFunction::CreateObjectiveFunction(str));
    objective_function_ = loaded_objective_.get();
  }

Guolin Ke's avatar
Guolin Ke committed
929
  // get tree models
930
  size_t i = 0;
Guolin Ke's avatar
Guolin Ke committed
931
932
933
934
935
936
937
  while (i < lines.size()) {
    size_t find_pos = lines[i].find("Tree=");
    if (find_pos != std::string::npos) {
      ++i;
      int start = static_cast<int>(i);
      while (i < lines.size() && lines[i].find("Tree=") == std::string::npos) { ++i; }
      int end = static_cast<int>(i);
Guolin Ke's avatar
Guolin Ke committed
938
      std::string tree_str = Common::Join<std::string>(lines, start, end, "\n");
939
      models_.emplace_back(new Tree(tree_str));
Guolin Ke's avatar
Guolin Ke committed
940
941
942
943
    } else {
      ++i;
    }
  }
944
  Log::Info("Finished loading %d models", models_.size());
945
  num_iteration_for_pred_ = static_cast<int>(models_.size()) / num_tree_per_iteration_;
wxchan's avatar
wxchan committed
946
  num_init_iteration_ = num_iteration_for_pred_;
947
  iter_ = 0;
948
949

  return true;
Guolin Ke's avatar
Guolin Ke committed
950
951
}

wxchan's avatar
wxchan committed
952
std::vector<std::pair<size_t, std::string>> GBDT::FeatureImportance() const {
953

954
  std::vector<size_t> feature_importances(max_feature_idx_ + 1, 0);
955
956
  for (size_t iter = 0; iter < models_.size(); ++iter) {
    for (int split_idx = 0; split_idx < models_[iter]->num_leaves() - 1; ++split_idx) {
Guolin Ke's avatar
Guolin Ke committed
957
958
959
      if (models_[iter]->split_gain(split_idx) > 0) {
        ++feature_importances[models_[iter]->split_feature(split_idx)];
      }
wxchan's avatar
wxchan committed
960
    }
961
962
963
964
965
966
  }
  // store the importance first
  std::vector<std::pair<size_t, std::string>> pairs;
  for (size_t i = 0; i < feature_importances.size(); ++i) {
    if (feature_importances[i] > 0) {
      pairs.emplace_back(feature_importances[i], feature_names_[i]);
967
    }
968
969
970
  }
  // sort the importance
  std::sort(pairs.begin(), pairs.end(),
Guolin Ke's avatar
Guolin Ke committed
971
972
            [](const std::pair<size_t, std::string>& lhs,
               const std::pair<size_t, std::string>& rhs) {
973
974
975
    return lhs.first > rhs.first;
  });
  return pairs;
wxchan's avatar
wxchan committed
976
977
}

978
void GBDT::PredictRaw(const double* features, double* output) const {
Guolin Ke's avatar
Guolin Ke committed
979
980
981
982
  if (num_threads_ <= num_tree_per_iteration_) {
    #pragma omp parallel for schedule(static)
    for (int k = 0; k < num_tree_per_iteration_; ++k) {
      for (int i = 0; i < num_iteration_for_pred_; ++i) {
983
        output[k] += models_[i * num_tree_per_iteration_ + k]->Predict(features);
Guolin Ke's avatar
Guolin Ke committed
984
985
986
987
988
989
990
      }
    }
  } else {
    for (int k = 0; k < num_tree_per_iteration_; ++k) {
      double t = 0.0f;
      #pragma omp parallel for schedule(static) reduction(+:t)
      for (int i = 0; i < num_iteration_for_pred_; ++i) {
991
        t += models_[i * num_tree_per_iteration_ + k]->Predict(features);
Guolin Ke's avatar
Guolin Ke committed
992
993
      }
      output[k] = t;
994
    }
Guolin Ke's avatar
Guolin Ke committed
995
996
997
  }
}

998
void GBDT::Predict(const double* features, double* output) const {
Guolin Ke's avatar
Guolin Ke committed
999
1000
1001
1002
  if (num_threads_ <= num_tree_per_iteration_) {
    #pragma omp parallel for schedule(static)
    for (int k = 0; k < num_tree_per_iteration_; ++k) {
      for (int i = 0; i < num_iteration_for_pred_; ++i) {
1003
        output[k] += models_[i * num_tree_per_iteration_ + k]->Predict(features);
Guolin Ke's avatar
Guolin Ke committed
1004
1005
1006
1007
1008
1009
1010
      }
    }
  } else {
    for (int k = 0; k < num_tree_per_iteration_; ++k) {
      double t = 0.0f;
      #pragma omp parallel for schedule(static) reduction(+:t)
      for (int i = 0; i < num_iteration_for_pred_; ++i) {
1011
        t += models_[i * num_tree_per_iteration_ + k]->Predict(features);
Guolin Ke's avatar
Guolin Ke committed
1012
1013
      }
      output[k] = t;
1014
1015
    }
  }
1016
  if (objective_function_ != nullptr) {
Guolin Ke's avatar
Guolin Ke committed
1017
    objective_function_->ConvertOutput(output, output);
1018
  }
1019
1020
}

1021
void GBDT::PredictLeafIndex(const double* features, double* output) const {
Guolin Ke's avatar
Guolin Ke committed
1022
1023
1024
  int total_tree = num_iteration_for_pred_ * num_tree_per_iteration_;
  #pragma omp parallel for schedule(static)
  for (int i = 0; i < total_tree; ++i) {
1025
    output[i] = models_[i]->PredictLeafIndex(features);
wxchan's avatar
wxchan committed
1026
1027
1028
  }
}

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