gbdt.cpp 23.3 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
16
#include <LightGBM/utils/common.h>

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

#include <ctime>

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

namespace LightGBM {

21
GBDT::GBDT()
22
  :iter_(0),
23
24
25
26
27
28
  train_data_(nullptr),
  object_function_(nullptr),
  early_stopping_round_(0),
  max_feature_idx_(0),
  num_class_(1),
  sigmoid_(1.0f),
29
  num_iteration_for_pred_(0),
30
  shrinkage_rate_(0.1f),
wxchan's avatar
wxchan committed
31
  num_init_iteration_(0) {
32
33
34
35
36
#pragma omp parallel
#pragma omp master
    {
      num_threads_ = omp_get_num_threads();
    }
Guolin Ke's avatar
Guolin Ke committed
37
38
39
}

GBDT::~GBDT() {
Guolin Ke's avatar
Guolin Ke committed
40

Guolin Ke's avatar
Guolin Ke committed
41
42
}

43
44
45
void GBDT::Init(const BoostingConfig* config, const Dataset* train_data, const ObjectiveFunction* object_function,
     const std::vector<const Metric*>& training_metrics) {
  iter_ = 0;
wxchan's avatar
wxchan committed
46
  num_iteration_for_pred_ = 0;
47
  max_feature_idx_ = 0;
wxchan's avatar
wxchan committed
48
  num_class_ = config->num_class;
49
50
51
  for (int i = 0; i < num_threads_; ++i) {
    random_.emplace_back(config->bagging_seed + i);
  }
wxchan's avatar
wxchan committed
52
  train_data_ = nullptr;
Guolin Ke's avatar
Guolin Ke committed
53
  gbdt_config_ = nullptr;
54
  tree_learner_ = nullptr;
wxchan's avatar
wxchan committed
55
56
57
58
59
  ResetTrainingData(config, train_data, object_function, training_metrics);
}

void GBDT::ResetTrainingData(const BoostingConfig* config, const Dataset* train_data, const ObjectiveFunction* object_function,
  const std::vector<const Metric*>& training_metrics) {
Guolin Ke's avatar
Guolin Ke committed
60
  auto new_config = std::unique_ptr<BoostingConfig>(new BoostingConfig(*config));
wxchan's avatar
wxchan committed
61
62
63
  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
64
65
66
  early_stopping_round_ = new_config->early_stopping_round;
  shrinkage_rate_ = new_config->learning_rate;

Guolin Ke's avatar
Guolin Ke committed
67
  object_function_ = object_function;
Guolin Ke's avatar
Guolin Ke committed
68

Guolin Ke's avatar
Guolin Ke committed
69
  sigmoid_ = -1.0f;
wxchan's avatar
wxchan committed
70
  if (object_function_ != nullptr
Guolin Ke's avatar
Guolin Ke committed
71
72
    && std::string(object_function_->GetName()) == std::string("binary")) {
    // only binary classification need sigmoid transform
Guolin Ke's avatar
Guolin Ke committed
73
    sigmoid_ = new_config->sigmoid;
74
  }
Guolin Ke's avatar
Guolin Ke committed
75

Guolin Ke's avatar
Guolin Ke committed
76
  if (train_data_ != train_data && train_data != nullptr) {
77
78
    if (tree_learner_ == nullptr) {
      tree_learner_ = std::unique_ptr<TreeLearner>(TreeLearner::CreateTreeLearner(new_config->tree_learner_type, &new_config->tree_config));
Guolin Ke's avatar
Guolin Ke committed
79
80
    }
    // init tree learner
81
    tree_learner_->Init(train_data);
Guolin Ke's avatar
Guolin Ke committed
82

Guolin Ke's avatar
Guolin Ke committed
83
84
85
86
87
88
    // 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
89
90
91
92
93
94
95
96
97
98
99
100
101
    // not same training data, need reset score and others
    // create score tracker
    train_score_updater_.reset(new ScoreUpdater(train_data, num_class_));
    // update score
    for (int i = 0; i < iter_; ++i) {
      for (int curr_class = 0; curr_class < num_class_; ++curr_class) {
        auto curr_tree = (i + num_init_iteration_) * num_class_ + curr_class;
        train_score_updater_->AddScore(models_[curr_tree].get(), curr_class);
      }
    }
    num_data_ = train_data->num_data();
    // create buffer for gradients and hessians
    if (object_function_ != nullptr) {
102
103
104
      size_t total_size = static_cast<size_t>(num_data_) * num_class_;
      gradients_.resize(total_size);
      hessians_.resize(total_size);
wxchan's avatar
wxchan committed
105
106
107
108
109
    }
    // get max feature index
    max_feature_idx_ = train_data->num_total_features() - 1;
    // get label index
    label_idx_ = train_data->label_idx();
110
111
    // get feature names
    feature_names_ = train_data->feature_names();
112
113
114
115
116
117
118
119
120
121
    // get feature infos
    feature_infos_.clear();
    for (int i = 0; i < max_feature_idx_ + 1; ++i) {
      int feature_idx = train_data->GetInnerFeatureIndex(i);
      if (feature_idx < 0) { 
        feature_infos_.push_back("trival feature"); 
      } else {
        feature_infos_.push_back(train_data->FeatureAt(feature_idx)->bin_mapper()->bin_info());
      }
    }
Guolin Ke's avatar
Guolin Ke committed
122
123
  }

Guolin Ke's avatar
Guolin Ke committed
124
125
  if ((train_data_ != train_data && train_data != nullptr)
    || (gbdt_config_ != nullptr && gbdt_config_->bagging_fraction != new_config->bagging_fraction)) {
wxchan's avatar
wxchan committed
126
    // if need bagging, create buffer
Guolin Ke's avatar
Guolin Ke committed
127
    if (new_config->bagging_fraction < 1.0 && new_config->bagging_freq > 0) {
128
129
      bag_data_cnt_ =
        static_cast<data_size_t>(new_config->bagging_fraction * num_data_);
130
      bag_data_indices_.resize(num_data_);
131
132
133
134
135
136
      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_);
wxchan's avatar
wxchan committed
137
138
139
    } else {
      bag_data_cnt_ = num_data_;
      bag_data_indices_.clear();
140
      tmp_indices_.clear();
wxchan's avatar
wxchan committed
141
    }
Guolin Ke's avatar
Guolin Ke committed
142
  }
wxchan's avatar
wxchan committed
143
  train_data_ = train_data;
Guolin Ke's avatar
Guolin Ke committed
144
145
  if (train_data_ != nullptr) {
    // reset config for tree learner
146
    tree_learner_->ResetConfig(&new_config->tree_config);
Guolin Ke's avatar
Guolin Ke committed
147
  }
Guolin Ke's avatar
Guolin Ke committed
148
  gbdt_config_.reset(new_config.release());
Guolin Ke's avatar
Guolin Ke committed
149
150
}

wxchan's avatar
wxchan committed
151
void GBDT::AddValidDataset(const Dataset* valid_data,
Guolin Ke's avatar
Guolin Ke committed
152
  const std::vector<const Metric*>& valid_metrics) {
wxchan's avatar
wxchan committed
153
154
  if (!train_data_->CheckAlign(*valid_data)) {
    Log::Fatal("cannot add validation data, since it has different bin mappers with training data");
155
  }
Guolin Ke's avatar
Guolin Ke committed
156
  // for a validation dataset, we need its score and metric
Guolin Ke's avatar
Guolin Ke committed
157
  auto new_score_updater = std::unique_ptr<ScoreUpdater>(new ScoreUpdater(valid_data, num_class_));
wxchan's avatar
wxchan committed
158
159
160
161
162
163
164
  // update score
  for (int i = 0; i < iter_; ++i) {
    for (int curr_class = 0; curr_class < num_class_; ++curr_class) {
      auto curr_tree = (i + num_init_iteration_) * num_class_ + curr_class;
      new_score_updater->AddScore(models_[curr_tree].get(), curr_class);
    }
  }
Guolin Ke's avatar
Guolin Ke committed
165
  valid_score_updater_.push_back(std::move(new_score_updater));
Guolin Ke's avatar
Guolin Ke committed
166
  valid_metrics_.emplace_back();
167
168
169
  if (early_stopping_round_ > 0) {
    best_iter_.emplace_back();
    best_score_.emplace_back();
Guolin Ke's avatar
Guolin Ke committed
170
    best_msg_.emplace_back();
171
  }
Guolin Ke's avatar
Guolin Ke committed
172
173
  for (const auto& metric : valid_metrics) {
    valid_metrics_.back().push_back(metric);
174
175
176
    if (early_stopping_round_ > 0) {
      best_iter_.back().push_back(0);
      best_score_.back().push_back(kMinScore);
Guolin Ke's avatar
Guolin Ke committed
177
      best_msg_.back().emplace_back();
178
    }
Guolin Ke's avatar
Guolin Ke committed
179
  }
Guolin Ke's avatar
Guolin Ke committed
180
  valid_metrics_.back().shrink_to_fit();
Guolin Ke's avatar
Guolin Ke committed
181
182
}

183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
data_size_t GBDT::BaggingHelper(data_size_t start, data_size_t cnt, data_size_t* buffer){
  const int tid = omp_get_thread_num();
  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;
  // random bagging, minimal unit is one record
  for (data_size_t i = 0; i < cnt; ++i) {
    double prob =
      (bag_data_cnt - cur_left_cnt) / static_cast<double>(cnt - i);
    if (random_[tid].NextDouble() < prob) {
      buffer[cur_left_cnt++] = start + i;
    } else {
      buffer[bag_data_cnt + cur_right_cnt++] = start + i;
    }
  }
  CHECK(cur_left_cnt == bag_data_cnt);
  return cur_left_cnt;
}
Guolin Ke's avatar
Guolin Ke committed
202

203
void GBDT::Bagging(int iter) {
Guolin Ke's avatar
Guolin Ke committed
204
  // if need bagging
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
  if (bag_data_cnt_ < num_data_ && iter % gbdt_config_->bagging_freq == 0) {
    const data_size_t min_inner_size = 10000;
    data_size_t inner_size = (num_data_ + num_threads_ - 1) / num_threads_;
    if (inner_size < min_inner_size) { inner_size = min_inner_size; }

#pragma omp parallel for schedule(static, 1)
    for (int i = 0; i < num_threads_; ++i) {
      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; }
      data_size_t cur_left_count = BaggingHelper(cur_start, cur_cnt, tmp_indices_.data() + cur_start);
      offsets_buf_[i] = cur_start;
      left_cnts_buf_[i] = cur_left_count;
      right_cnts_buf_[i] = cur_cnt - cur_left_count;
    }
    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];

#pragma omp parallel for schedule(static, 1)
    for (int i = 0; i < num_threads_; ++i) {
      if (left_cnts_buf_[i] > 0) {
        std::memcpy(bag_data_indices_.data() + left_write_pos_buf_[i],
          tmp_indices_.data() + offsets_buf_[i], left_cnts_buf_[i] * sizeof(data_size_t));
Guolin Ke's avatar
Guolin Ke committed
237
      }
238
239
240
      if (right_cnts_buf_[i] > 0) {
        std::memcpy(bag_data_indices_.data() + left_cnt + right_write_pos_buf_[i],
          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
241
242
      }
    }
Guolin Ke's avatar
Guolin Ke committed
243
    Log::Debug("Re-bagging, using %d data to train", bag_data_cnt_);
Guolin Ke's avatar
Guolin Ke committed
244
    // set bagging data to tree learner
245
    tree_learner_->SetBaggingData(bag_data_indices_.data(), bag_data_cnt_);
Guolin Ke's avatar
Guolin Ke committed
246
247
248
  }
}

249
void GBDT::UpdateScoreOutOfBag(const Tree* tree, const int curr_class) {
Hui Xue's avatar
Hui Xue committed
250
  // we need to predict out-of-bag socres of data for boosting
251
252
  if (num_data_ - bag_data_cnt_ > 0) {
    train_score_updater_->AddScore(tree, bag_data_indices_.data() + bag_data_cnt_, num_data_ - bag_data_cnt_, curr_class);
Guolin Ke's avatar
Guolin Ke committed
253
254
255
  }
}

256
bool GBDT::TrainOneIter(const score_t* gradient, const score_t* hessian, bool is_eval) {
Guolin Ke's avatar
Guolin Ke committed
257
258
259
260
261
262
  // boosting first
  if (gradient == nullptr || hessian == nullptr) {
    Boosting();
    gradient = gradients_.data();
    hessian = hessians_.data();
  }
263
264
  // bagging logic
  Bagging(iter_);
Guolin Ke's avatar
Guolin Ke committed
265
266
267
  for (int curr_class = 0; curr_class < num_class_; ++curr_class) {

    // train a new tree
268
    std::unique_ptr<Tree> new_tree(tree_learner_->Train(gradient + curr_class * num_data_, hessian + curr_class * num_data_));
Guolin Ke's avatar
Guolin Ke committed
269
270
271
272
    // if cannot learn a new tree, then stop
    if (new_tree->num_leaves() <= 1) {
      Log::Info("Stopped training because there are no more leafs that meet the split requirements.");
      return true;
273
    }
274

Guolin Ke's avatar
Guolin Ke committed
275
276
277
278
279
    // shrinkage by learning rate
    new_tree->Shrinkage(shrinkage_rate_);
    // update score
    UpdateScore(new_tree.get(), curr_class);
    UpdateScoreOutOfBag(new_tree.get(), curr_class);
280

Guolin Ke's avatar
Guolin Ke committed
281
282
283
284
285
286
287
288
289
    // add model
    models_.push_back(std::move(new_tree));
  }
  ++iter_;
  if (is_eval) {
    return EvalAndCheckEarlyStopping();
  } else {
    return false;
  }
290

Guolin Ke's avatar
Guolin Ke committed
291
}
292

wxchan's avatar
wxchan committed
293
void GBDT::RollbackOneIter() {
294
  if (iter_ <= 0) { return; }
wxchan's avatar
wxchan committed
295
296
297
298
299
300
301
302
303
304
305
306
307
308
309
310
311
  int cur_iter = iter_ + num_init_iteration_ - 1;
  // reset score
  for (int curr_class = 0; curr_class < num_class_; ++curr_class) {
    auto curr_tree = cur_iter * num_class_ + curr_class;
    models_[curr_tree]->Shrinkage(-1.0);
    train_score_updater_->AddScore(models_[curr_tree].get(), curr_class);
    for (auto& score_updater : valid_score_updater_) {
      score_updater->AddScore(models_[curr_tree].get(), curr_class);
    }
  }
  // remove model
  for (int curr_class = 0; curr_class < num_class_; ++curr_class) {
    models_.pop_back();
  }
  --iter_;
}

Guolin Ke's avatar
Guolin Ke committed
312
bool GBDT::EvalAndCheckEarlyStopping() {
313
314
  bool is_met_early_stopping = false;
  // print message for metric
Guolin Ke's avatar
Guolin Ke committed
315
316
  auto best_msg = OutputMetric(iter_);
  is_met_early_stopping = !best_msg.empty();
317
318
319
  if (is_met_early_stopping) {
    Log::Info("Early stopping at iteration %d, the best iteration round is %d",
      iter_, iter_ - early_stopping_round_);
Guolin Ke's avatar
Guolin Ke committed
320
    Log::Info("Output of best iteration round:\n%s", best_msg.c_str());
321
    // pop last early_stopping_round_ models
322
    for (int i = 0; i < early_stopping_round_ * num_class_; ++i) {
323
324
325
326
      models_.pop_back();
    }
  }
  return is_met_early_stopping;
Guolin Ke's avatar
Guolin Ke committed
327
328
}

329
void GBDT::UpdateScore(const Tree* tree, const int curr_class) {
Guolin Ke's avatar
Guolin Ke committed
330
  // update training score
331
  train_score_updater_->AddScore(tree_learner_.get(), curr_class);
Guolin Ke's avatar
Guolin Ke committed
332
  // update validation score
Guolin Ke's avatar
Guolin Ke committed
333
334
  for (auto& score_updater : valid_score_updater_) {
    score_updater->AddScore(tree, curr_class);
Guolin Ke's avatar
Guolin Ke committed
335
336
337
  }
}

Guolin Ke's avatar
Guolin Ke committed
338
339
340
341
std::string GBDT::OutputMetric(int iter) {
  bool need_output = (iter % gbdt_config_->output_freq) == 0;
  std::string ret = "";
  std::stringstream msg_buf;
342
  std::vector<std::pair<size_t, size_t>> meet_early_stopping_pairs;
Guolin Ke's avatar
Guolin Ke committed
343
  // print training metric
Guolin Ke's avatar
Guolin Ke committed
344
  if (need_output) {
345
346
347
    for (auto& sub_metric : training_metrics_) {
      auto name = sub_metric->GetName();
      auto scores = sub_metric->Eval(train_score_updater_->score());
Guolin Ke's avatar
Guolin Ke committed
348
      for (size_t k = 0; k < name.size(); ++k) {
Guolin Ke's avatar
Guolin Ke committed
349
350
351
352
353
354
355
356
        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;
        }
357
      }
358
    }
Guolin Ke's avatar
Guolin Ke committed
359
360
  }
  // print validation metric
Guolin Ke's avatar
Guolin Ke committed
361
  if (need_output || early_stopping_round_ > 0) {
362
363
364
    for (size_t i = 0; i < valid_metrics_.size(); ++i) {
      for (size_t j = 0; j < valid_metrics_[i].size(); ++j) {
        auto test_scores = valid_metrics_[i][j]->Eval(valid_score_updater_[i]->score());
Guolin Ke's avatar
Guolin Ke committed
365
366
367
368
369
370
371
372
373
374
375
        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;
376
          }
wxchan's avatar
wxchan committed
377
        }
Guolin Ke's avatar
Guolin Ke committed
378
        if (ret.empty() && early_stopping_round_ > 0) {
379
380
381
          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;
382
            best_iter_[i][j] = iter;
Guolin Ke's avatar
Guolin Ke committed
383
            meet_early_stopping_pairs.emplace_back(i, j);
384
          } else {
Guolin Ke's avatar
Guolin Ke committed
385
            if (iter - best_iter_[i][j] >= early_stopping_round_) { ret = best_msg_[i][j]; }
386
          }
wxchan's avatar
wxchan committed
387
388
        }
      }
Guolin Ke's avatar
Guolin Ke committed
389
390
    }
  }
Guolin Ke's avatar
Guolin Ke committed
391
392
393
  for (auto& pair : meet_early_stopping_pairs) {
    best_msg_[pair.first][pair.second] = msg_buf.str();
  }
wxchan's avatar
wxchan committed
394
  return ret;
Guolin Ke's avatar
Guolin Ke committed
395
396
}

397
/*! \brief Get eval result */
398
std::vector<double> GBDT::GetEvalAt(int data_idx) const {
Guolin Ke's avatar
Guolin Ke committed
399
  CHECK(data_idx >= 0 && data_idx <= static_cast<int>(valid_score_updater_.size()));
400
401
  std::vector<double> ret;
  if (data_idx == 0) {
402
403
    for (auto& sub_metric : training_metrics_) {
      auto scores = sub_metric->Eval(train_score_updater_->score());
404
405
406
      for (auto score : scores) {
        ret.push_back(score);
      }
407
408
    }
  }
409
410
411
412
413
414
415
  else {
    auto used_idx = data_idx - 1;
    for (size_t j = 0; j < valid_metrics_[used_idx].size(); ++j) {
      auto test_scores = valid_metrics_[used_idx][j]->Eval(valid_score_updater_[used_idx]->score());
      for (auto score : test_scores) {
        ret.push_back(score);
      }
416
417
418
419
420
    }
  }
  return ret;
}

Guolin Ke's avatar
Guolin Ke committed
421
/*! \brief Get training scores result */
422
const double* GBDT::GetTrainingScore(int64_t* out_len) {
423
  *out_len = static_cast<int64_t>(train_score_updater_->num_data()) * num_class_;
Guolin Ke's avatar
Guolin Ke committed
424
  return train_score_updater_->score();
425
426
}

Guolin Ke's avatar
Guolin Ke committed
427
428
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
429

430
  const double* raw_scores = nullptr;
Guolin Ke's avatar
Guolin Ke committed
431
432
  data_size_t num_data = 0;
  if (data_idx == 0) {
wxchan's avatar
wxchan committed
433
    raw_scores = GetTrainingScore(out_len);
Guolin Ke's avatar
Guolin Ke committed
434
435
436
437
438
    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();
439
    *out_len = static_cast<int64_t>(num_data) * num_class_;
Guolin Ke's avatar
Guolin Ke committed
440
441
  }
  if (num_class_ > 1) {
wxchan's avatar
wxchan committed
442
#pragma omp parallel for schedule(static)
Guolin Ke's avatar
Guolin Ke committed
443
    for (data_size_t i = 0; i < num_data; ++i) {
444
      std::vector<double> tmp_result(num_class_);
Guolin Ke's avatar
Guolin Ke committed
445
      for (int j = 0; j < num_class_; ++j) {
446
        tmp_result[j] = raw_scores[j * num_data + i];
Guolin Ke's avatar
Guolin Ke committed
447
448
449
      }
      Common::Softmax(&tmp_result);
      for (int j = 0; j < num_class_; ++j) {
Guolin Ke's avatar
Guolin Ke committed
450
        out_result[j * num_data + i] = static_cast<double>(tmp_result[j]);
Guolin Ke's avatar
Guolin Ke committed
451
452
      }
    }
Guolin Ke's avatar
Guolin Ke committed
453
  } else if(sigmoid_ > 0.0f){
wxchan's avatar
wxchan committed
454
#pragma omp parallel for schedule(static)
Guolin Ke's avatar
Guolin Ke committed
455
    for (data_size_t i = 0; i < num_data; ++i) {
Guolin Ke's avatar
Guolin Ke committed
456
      out_result[i] = static_cast<double>(1.0f / (1.0f + std::exp(-2.0f * sigmoid_ * raw_scores[i])));
Guolin Ke's avatar
Guolin Ke committed
457
458
    }
  } else {
wxchan's avatar
wxchan committed
459
#pragma omp parallel for schedule(static)
Guolin Ke's avatar
Guolin Ke committed
460
    for (data_size_t i = 0; i < num_data; ++i) {
Guolin Ke's avatar
Guolin Ke committed
461
      out_result[i] = static_cast<double>(raw_scores[i]);
Guolin Ke's avatar
Guolin Ke committed
462
463
464
465
466
    }
  }

}

Guolin Ke's avatar
Guolin Ke committed
467
void GBDT::Boosting() {
468
469
470
  if (object_function_ == nullptr) {
    Log::Fatal("No object function provided");
  }
Hui Xue's avatar
Hui Xue committed
471
  // objective function will calculate gradients and hessians
472
  int64_t num_score = 0;
Guolin Ke's avatar
Guolin Ke committed
473
  object_function_->
Guolin Ke's avatar
Guolin Ke committed
474
    GetGradients(GetTrainingScore(&num_score), gradients_.data(), hessians_.data());
Guolin Ke's avatar
Guolin Ke committed
475
476
}

477
std::string GBDT::DumpModel(int num_iteration) const {
Guolin Ke's avatar
Guolin Ke committed
478
  std::stringstream str_buf;
wxchan's avatar
wxchan committed
479

Guolin Ke's avatar
Guolin Ke committed
480
  str_buf << "{";
Guolin Ke's avatar
Guolin Ke committed
481
  str_buf << "\"name\":\"" << SubModelName() << "\"," << std::endl;
Guolin Ke's avatar
Guolin Ke committed
482
483
484
485
  str_buf << "\"num_class\":" << num_class_ << "," << std::endl;
  str_buf << "\"label_index\":" << label_idx_ << "," << std::endl;
  str_buf << "\"max_feature_idx\":" << max_feature_idx_ << "," << std::endl;
  str_buf << "\"sigmoid\":" << sigmoid_ << "," << std::endl;
wxchan's avatar
wxchan committed
486

Guolin Ke's avatar
Guolin Ke committed
487
  str_buf << "\"feature_names\":[\"" 
488
     << Common::Join(feature_names_, "\",\"") << "\"]," 
Guolin Ke's avatar
Guolin Ke committed
489
490
     << std::endl;

Guolin Ke's avatar
Guolin Ke committed
491
  str_buf << "\"tree_info\":[";
492
493
494
495
496
  int num_used_model = static_cast<int>(models_.size());
  if (num_iteration > 0) {
    num_used_model = std::min(num_iteration * num_class_, num_used_model);
  } 
  for (int i = 0; i < num_used_model; ++i) {
wxchan's avatar
wxchan committed
497
    if (i > 0) {
Guolin Ke's avatar
Guolin Ke committed
498
      str_buf << ",";
wxchan's avatar
wxchan committed
499
    }
Guolin Ke's avatar
Guolin Ke committed
500
501
502
503
    str_buf << "{";
    str_buf << "\"tree_index\":" << i << ",";
    str_buf << models_[i]->ToJSON();
    str_buf << "}";
wxchan's avatar
wxchan committed
504
  }
Guolin Ke's avatar
Guolin Ke committed
505
  str_buf << "]" << std::endl;
wxchan's avatar
wxchan committed
506

Guolin Ke's avatar
Guolin Ke committed
507
  str_buf << "}" << std::endl;
wxchan's avatar
wxchan committed
508

Guolin Ke's avatar
Guolin Ke committed
509
  return str_buf.str();
wxchan's avatar
wxchan committed
510
511
512
513
514
515
516
}

void GBDT::SaveModelToFile(int num_iteration, const char* filename) const {
  /*! \brief File to write models */
  std::ofstream output_file;
  output_file.open(filename);
  // output model type
Guolin Ke's avatar
Guolin Ke committed
517
  output_file << SubModelName() << std::endl;
wxchan's avatar
wxchan committed
518
519
520
521
522
523
524
525
526
  // output number of class
  output_file << "num_class=" << num_class_ << std::endl;
  // output label index
  output_file << "label_index=" << label_idx_ << std::endl;
  // output max_feature_idx
  output_file << "max_feature_idx=" << max_feature_idx_ << std::endl;
  // output objective name
  if (object_function_ != nullptr) {
    output_file << "objective=" << object_function_->GetName() << std::endl;
527
  }
wxchan's avatar
wxchan committed
528
529
  // output sigmoid parameter
  output_file << "sigmoid=" << sigmoid_ << std::endl;
530
531

  output_file << "feature_names=" << Common::Join(feature_names_, " ") << std::endl;
wxchan's avatar
wxchan committed
532

Guolin Ke's avatar
Guolin Ke committed
533
  output_file << std::endl;
534
535
536
  int num_used_model = static_cast<int>(models_.size());
  if (num_iteration > 0) {
    num_used_model = std::min(num_iteration * num_class_, num_used_model);
Guolin Ke's avatar
Guolin Ke committed
537
  }
538
  // output tree models
wxchan's avatar
wxchan committed
539
540
541
  for (int i = 0; i < num_used_model; ++i) {
    output_file << "Tree=" << i << std::endl;
    output_file << models_[i]->ToString() << std::endl;
542
  }
543

wxchan's avatar
wxchan committed
544
545
546
547
  std::vector<std::pair<size_t, std::string>> pairs = FeatureImportance();
  output_file << std::endl << "feature importances:" << std::endl;
  for (size_t i = 0; i < pairs.size(); ++i) {
    output_file << pairs[i].second << "=" << std::to_string(pairs[i].first) << std::endl;
Guolin Ke's avatar
Guolin Ke committed
548
  }
549
550
551
552
553
554

  output_file << std::endl << "feature information:" << std::endl;
  for (size_t i = 0; i < max_feature_idx_ + 1; ++i) {
    output_file << feature_names_[i] << "=" << feature_infos_[i] << std::endl;
  }

wxchan's avatar
wxchan committed
555
  output_file.close();
Guolin Ke's avatar
Guolin Ke committed
556
557
}

Guolin Ke's avatar
Guolin Ke committed
558
void GBDT::LoadModelFromString(const std::string& model_str) {
Guolin Ke's avatar
Guolin Ke committed
559
560
561
  // use serialized string to restore this object
  models_.clear();
  std::vector<std::string> lines = Common::Split(model_str.c_str(), '\n');
562
563

  // get number of classes
564
565
566
567
  auto line = Common::FindFromLines(lines, "num_class=");
  if (line.size() > 0) {
    Common::Atoi(Common::Split(line.c_str(), '=')[1].c_str(), &num_class_);
  } else {
568
    Log::Fatal("Model file doesn't specify the number of classes");
569
570
    return;
  }
Guolin Ke's avatar
Guolin Ke committed
571
  // get index of label
572
573
574
575
  line = Common::FindFromLines(lines, "label_index=");
  if (line.size() > 0) {
    Common::Atoi(Common::Split(line.c_str(), '=')[1].c_str(), &label_idx_);
  } else {
576
    Log::Fatal("Model file doesn't specify the label index");
Guolin Ke's avatar
Guolin Ke committed
577
578
    return;
  }
Guolin Ke's avatar
Guolin Ke committed
579
  // get max_feature_idx first
580
581
582
583
  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 {
584
    Log::Fatal("Model file doesn't specify max_feature_idx");
Guolin Ke's avatar
Guolin Ke committed
585
586
587
    return;
  }
  // get sigmoid parameter
588
589
590
591
  line = Common::FindFromLines(lines, "sigmoid=");
  if (line.size() > 0) {
    Common::Atof(Common::Split(line.c_str(), '=')[1].c_str(), &sigmoid_);
  } else {
592
    sigmoid_ = -1.0f;
Guolin Ke's avatar
Guolin Ke committed
593
  }
Guolin Ke's avatar
Guolin Ke committed
594
595
596
  // get feature names
  line = Common::FindFromLines(lines, "feature_names=");
  if (line.size() > 0) {
Guolin Ke's avatar
Guolin Ke committed
597
    feature_names_ = Common::Split(line.substr(std::strlen("feature_names=")).c_str(), " ");
Guolin Ke's avatar
Guolin Ke committed
598
599
600
601
602
603
604
605
606
    if (feature_names_.size() != static_cast<size_t>(max_feature_idx_ + 1)) {
      Log::Fatal("Wrong size of feature_names");
      return;
    }
  } else {
    Log::Fatal("Model file doesn't contain feature names");
    return;
  }

Guolin Ke's avatar
Guolin Ke committed
607
  // get tree models
608
  size_t i = 0;
Guolin Ke's avatar
Guolin Ke committed
609
610
611
612
613
614
615
  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
616
      std::string tree_str = Common::Join<std::string>(lines, start, end, "\n");
Guolin Ke's avatar
Guolin Ke committed
617
618
      auto new_tree = std::unique_ptr<Tree>(new Tree(tree_str));
      models_.push_back(std::move(new_tree));
Guolin Ke's avatar
Guolin Ke committed
619
620
621
622
    } else {
      ++i;
    }
  }
623
  Log::Info("Finished loading %d models", models_.size());
wxchan's avatar
wxchan committed
624
625
  num_iteration_for_pred_ = static_cast<int>(models_.size()) / num_class_;
  num_init_iteration_ = num_iteration_for_pred_;
626
  iter_ = 0;
Guolin Ke's avatar
Guolin Ke committed
627
628
}

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

631
  std::vector<size_t> feature_importances(max_feature_idx_ + 1, 0);
632
    for (size_t iter = 0; iter < models_.size(); ++iter) {
633
634
        for (int split_idx = 0; split_idx < models_[iter]->num_leaves() - 1; ++split_idx) {
            ++feature_importances[models_[iter]->split_feature_real(split_idx)];
wxchan's avatar
wxchan committed
635
636
        }
    }
637
638
639
    // store the importance first
    std::vector<std::pair<size_t, std::string>> pairs;
    for (size_t i = 0; i < feature_importances.size(); ++i) {
Guolin Ke's avatar
Guolin Ke committed
640
      if (feature_importances[i] > 0) {
641
        pairs.emplace_back(feature_importances[i], feature_names_[i]);
Guolin Ke's avatar
Guolin Ke committed
642
      }
643
644
645
646
647
    }
    // sort the importance
    std::sort(pairs.begin(), pairs.end(),
      [](const std::pair<size_t, std::string>& lhs,
        const std::pair<size_t, std::string>& rhs) {
648
      return lhs.first > rhs.first;
649
    });
wxchan's avatar
wxchan committed
650
    return pairs;
wxchan's avatar
wxchan committed
651
652
}

653
654
std::vector<double> GBDT::PredictRaw(const double* value) const {
  std::vector<double> ret(num_class_, 0.0f);
wxchan's avatar
wxchan committed
655
  for (int i = 0; i < num_iteration_for_pred_; ++i) {
656
657
658
    for (int j = 0; j < num_class_; ++j) {
      ret[j] += models_[i * num_class_ + j]->Predict(value);
    }
Guolin Ke's avatar
Guolin Ke committed
659
660
661
662
  }
  return ret;
}

663
std::vector<double> GBDT::Predict(const double* value) const {
664
  std::vector<double> ret(num_class_, 0.0f);
wxchan's avatar
wxchan committed
665
  for (int i = 0; i < num_iteration_for_pred_; ++i) {
666
667
    for (int j = 0; j < num_class_; ++j) {
      ret[j] += models_[i * num_class_ + j]->Predict(value);
668
669
    }
  }
670
671
672
673
674
675
  // if need sigmoid transform
  if (sigmoid_ > 0 && num_class_ == 1) {
    ret[0] = 1.0f / (1.0f + std::exp(- 2.0f * sigmoid_ * ret[0]));
  } else if (num_class_ > 1) {
    Common::Softmax(&ret);
  }
676
677
678
  return ret;
}

679
std::vector<int> GBDT::PredictLeafIndex(const double* value) const {
wxchan's avatar
wxchan committed
680
  std::vector<int> ret;
wxchan's avatar
wxchan committed
681
  for (int i = 0; i < num_iteration_for_pred_; ++i) {
682
683
684
    for (int j = 0; j < num_class_; ++j) {
      ret.push_back(models_[i * num_class_ + j]->PredictLeafIndex(value));
    }
wxchan's avatar
wxchan committed
685
686
687
688
  }
  return ret;
}

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