gbdt.cpp 22.8 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();
Guolin Ke's avatar
Guolin Ke committed
112
113
  }

Guolin Ke's avatar
Guolin Ke committed
114
115
  if ((train_data_ != train_data && train_data != nullptr)
    || (gbdt_config_ != nullptr && gbdt_config_->bagging_fraction != new_config->bagging_fraction)) {
wxchan's avatar
wxchan committed
116
    // if need bagging, create buffer
Guolin Ke's avatar
Guolin Ke committed
117
    if (new_config->bagging_fraction < 1.0 && new_config->bagging_freq > 0) {
118
119
      bag_data_cnt_ =
        static_cast<data_size_t>(new_config->bagging_fraction * num_data_);
120
      bag_data_indices_.resize(num_data_);
121
122
123
124
125
126
      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
127
128
129
    } else {
      bag_data_cnt_ = num_data_;
      bag_data_indices_.clear();
130
      tmp_indices_.clear();
wxchan's avatar
wxchan committed
131
    }
Guolin Ke's avatar
Guolin Ke committed
132
  }
wxchan's avatar
wxchan committed
133
  train_data_ = train_data;
Guolin Ke's avatar
Guolin Ke committed
134
135
  if (train_data_ != nullptr) {
    // reset config for tree learner
136
    tree_learner_->ResetConfig(&new_config->tree_config);
Guolin Ke's avatar
Guolin Ke committed
137
  }
Guolin Ke's avatar
Guolin Ke committed
138
  gbdt_config_.reset(new_config.release());
Guolin Ke's avatar
Guolin Ke committed
139
140
}

wxchan's avatar
wxchan committed
141
void GBDT::AddValidDataset(const Dataset* valid_data,
Guolin Ke's avatar
Guolin Ke committed
142
  const std::vector<const Metric*>& valid_metrics) {
wxchan's avatar
wxchan committed
143
144
  if (!train_data_->CheckAlign(*valid_data)) {
    Log::Fatal("cannot add validation data, since it has different bin mappers with training data");
145
  }
Guolin Ke's avatar
Guolin Ke committed
146
  // for a validation dataset, we need its score and metric
Guolin Ke's avatar
Guolin Ke committed
147
  auto new_score_updater = std::unique_ptr<ScoreUpdater>(new ScoreUpdater(valid_data, num_class_));
wxchan's avatar
wxchan committed
148
149
150
151
152
153
154
  // 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
155
  valid_score_updater_.push_back(std::move(new_score_updater));
Guolin Ke's avatar
Guolin Ke committed
156
  valid_metrics_.emplace_back();
157
158
159
  if (early_stopping_round_ > 0) {
    best_iter_.emplace_back();
    best_score_.emplace_back();
Guolin Ke's avatar
Guolin Ke committed
160
    best_msg_.emplace_back();
161
  }
Guolin Ke's avatar
Guolin Ke committed
162
163
  for (const auto& metric : valid_metrics) {
    valid_metrics_.back().push_back(metric);
164
165
166
    if (early_stopping_round_ > 0) {
      best_iter_.back().push_back(0);
      best_score_.back().push_back(kMinScore);
Guolin Ke's avatar
Guolin Ke committed
167
      best_msg_.back().emplace_back();
168
    }
Guolin Ke's avatar
Guolin Ke committed
169
  }
Guolin Ke's avatar
Guolin Ke committed
170
  valid_metrics_.back().shrink_to_fit();
Guolin Ke's avatar
Guolin Ke committed
171
172
}

173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
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
192

193
void GBDT::Bagging(int iter) {
Guolin Ke's avatar
Guolin Ke committed
194
  // if need bagging
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
  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
227
      }
228
229
230
      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
231
232
      }
    }
Guolin Ke's avatar
Guolin Ke committed
233
    Log::Debug("Re-bagging, using %d data to train", bag_data_cnt_);
Guolin Ke's avatar
Guolin Ke committed
234
    // set bagging data to tree learner
235
    tree_learner_->SetBaggingData(bag_data_indices_.data(), bag_data_cnt_);
Guolin Ke's avatar
Guolin Ke committed
236
237
238
  }
}

239
void GBDT::UpdateScoreOutOfBag(const Tree* tree, const int curr_class) {
Hui Xue's avatar
Hui Xue committed
240
  // we need to predict out-of-bag socres of data for boosting
241
242
  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
243
244
245
  }
}

246
bool GBDT::TrainOneIter(const score_t* gradient, const score_t* hessian, bool is_eval) {
Guolin Ke's avatar
Guolin Ke committed
247
248
249
250
251
252
  // boosting first
  if (gradient == nullptr || hessian == nullptr) {
    Boosting();
    gradient = gradients_.data();
    hessian = hessians_.data();
  }
253
254
  // bagging logic
  Bagging(iter_);
Guolin Ke's avatar
Guolin Ke committed
255
256
257
  for (int curr_class = 0; curr_class < num_class_; ++curr_class) {

    // train a new tree
258
    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
259
260
261
262
    // 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;
263
    }
264

Guolin Ke's avatar
Guolin Ke committed
265
266
267
268
269
    // shrinkage by learning rate
    new_tree->Shrinkage(shrinkage_rate_);
    // update score
    UpdateScore(new_tree.get(), curr_class);
    UpdateScoreOutOfBag(new_tree.get(), curr_class);
270

Guolin Ke's avatar
Guolin Ke committed
271
272
273
274
275
276
277
278
279
    // add model
    models_.push_back(std::move(new_tree));
  }
  ++iter_;
  if (is_eval) {
    return EvalAndCheckEarlyStopping();
  } else {
    return false;
  }
280

Guolin Ke's avatar
Guolin Ke committed
281
}
282

wxchan's avatar
wxchan committed
283
void GBDT::RollbackOneIter() {
284
  if (iter_ <= 0) { return; }
wxchan's avatar
wxchan committed
285
286
287
288
289
290
291
292
293
294
295
296
297
298
299
300
301
  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
302
bool GBDT::EvalAndCheckEarlyStopping() {
303
304
  bool is_met_early_stopping = false;
  // print message for metric
Guolin Ke's avatar
Guolin Ke committed
305
306
  auto best_msg = OutputMetric(iter_);
  is_met_early_stopping = !best_msg.empty();
307
308
309
  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
310
    Log::Info("Output of best iteration round:\n%s", best_msg.c_str());
311
    // pop last early_stopping_round_ models
312
    for (int i = 0; i < early_stopping_round_ * num_class_; ++i) {
313
314
315
316
      models_.pop_back();
    }
  }
  return is_met_early_stopping;
Guolin Ke's avatar
Guolin Ke committed
317
318
}

319
void GBDT::UpdateScore(const Tree* tree, const int curr_class) {
Guolin Ke's avatar
Guolin Ke committed
320
  // update training score
321
  train_score_updater_->AddScore(tree_learner_.get(), curr_class);
Guolin Ke's avatar
Guolin Ke committed
322
  // update validation score
Guolin Ke's avatar
Guolin Ke committed
323
324
  for (auto& score_updater : valid_score_updater_) {
    score_updater->AddScore(tree, curr_class);
Guolin Ke's avatar
Guolin Ke committed
325
326
327
  }
}

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

387
/*! \brief Get eval result */
388
std::vector<double> GBDT::GetEvalAt(int data_idx) const {
Guolin Ke's avatar
Guolin Ke committed
389
  CHECK(data_idx >= 0 && data_idx <= static_cast<int>(valid_score_updater_.size()));
390
391
  std::vector<double> ret;
  if (data_idx == 0) {
392
393
    for (auto& sub_metric : training_metrics_) {
      auto scores = sub_metric->Eval(train_score_updater_->score());
394
395
396
      for (auto score : scores) {
        ret.push_back(score);
      }
397
398
    }
  }
399
400
401
402
403
404
405
  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);
      }
406
407
408
409
410
    }
  }
  return ret;
}

Guolin Ke's avatar
Guolin Ke committed
411
/*! \brief Get training scores result */
412
const double* GBDT::GetTrainingScore(int64_t* out_len) {
413
  *out_len = static_cast<int64_t>(train_score_updater_->num_data()) * num_class_;
Guolin Ke's avatar
Guolin Ke committed
414
  return train_score_updater_->score();
415
416
}

Guolin Ke's avatar
Guolin Ke committed
417
418
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
419

420
  const double* raw_scores = nullptr;
Guolin Ke's avatar
Guolin Ke committed
421
422
  data_size_t num_data = 0;
  if (data_idx == 0) {
wxchan's avatar
wxchan committed
423
    raw_scores = GetTrainingScore(out_len);
Guolin Ke's avatar
Guolin Ke committed
424
425
426
427
428
    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();
429
    *out_len = static_cast<int64_t>(num_data) * num_class_;
Guolin Ke's avatar
Guolin Ke committed
430
431
  }
  if (num_class_ > 1) {
wxchan's avatar
wxchan committed
432
#pragma omp parallel for schedule(static)
Guolin Ke's avatar
Guolin Ke committed
433
    for (data_size_t i = 0; i < num_data; ++i) {
434
      std::vector<double> tmp_result(num_class_);
Guolin Ke's avatar
Guolin Ke committed
435
      for (int j = 0; j < num_class_; ++j) {
436
        tmp_result[j] = raw_scores[j * num_data + i];
Guolin Ke's avatar
Guolin Ke committed
437
438
439
      }
      Common::Softmax(&tmp_result);
      for (int j = 0; j < num_class_; ++j) {
Guolin Ke's avatar
Guolin Ke committed
440
        out_result[j * num_data + i] = static_cast<double>(tmp_result[j]);
Guolin Ke's avatar
Guolin Ke committed
441
442
      }
    }
Guolin Ke's avatar
Guolin Ke committed
443
  } else if(sigmoid_ > 0.0f){
wxchan's avatar
wxchan committed
444
#pragma omp parallel for schedule(static)
Guolin Ke's avatar
Guolin Ke committed
445
    for (data_size_t i = 0; i < num_data; ++i) {
Guolin Ke's avatar
Guolin Ke committed
446
      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
447
448
    }
  } else {
wxchan's avatar
wxchan committed
449
#pragma omp parallel for schedule(static)
Guolin Ke's avatar
Guolin Ke committed
450
    for (data_size_t i = 0; i < num_data; ++i) {
Guolin Ke's avatar
Guolin Ke committed
451
      out_result[i] = static_cast<double>(raw_scores[i]);
Guolin Ke's avatar
Guolin Ke committed
452
453
454
455
456
    }
  }

}

Guolin Ke's avatar
Guolin Ke committed
457
void GBDT::Boosting() {
458
459
460
  if (object_function_ == nullptr) {
    Log::Fatal("No object function provided");
  }
Hui Xue's avatar
Hui Xue committed
461
  // objective function will calculate gradients and hessians
462
  int64_t num_score = 0;
Guolin Ke's avatar
Guolin Ke committed
463
  object_function_->
Guolin Ke's avatar
Guolin Ke committed
464
    GetGradients(GetTrainingScore(&num_score), gradients_.data(), hessians_.data());
Guolin Ke's avatar
Guolin Ke committed
465
466
}

467
std::string GBDT::DumpModel(int num_iteration) const {
Guolin Ke's avatar
Guolin Ke committed
468
  std::stringstream str_buf;
wxchan's avatar
wxchan committed
469

Guolin Ke's avatar
Guolin Ke committed
470
  str_buf << "{";
Guolin Ke's avatar
Guolin Ke committed
471
  str_buf << "\"name\":\"" << SubModelName() << "\"," << std::endl;
Guolin Ke's avatar
Guolin Ke committed
472
473
474
475
  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
476

Guolin Ke's avatar
Guolin Ke committed
477
  str_buf << "\"feature_names\":[\"" 
478
     << Common::Join(feature_names_, "\",\"") << "\"]," 
Guolin Ke's avatar
Guolin Ke committed
479
480
     << std::endl;

Guolin Ke's avatar
Guolin Ke committed
481
  str_buf << "\"tree_info\":[";
482
483
484
485
486
  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
487
    if (i > 0) {
Guolin Ke's avatar
Guolin Ke committed
488
      str_buf << ",";
wxchan's avatar
wxchan committed
489
    }
Guolin Ke's avatar
Guolin Ke committed
490
491
492
493
    str_buf << "{";
    str_buf << "\"tree_index\":" << i << ",";
    str_buf << models_[i]->ToJSON();
    str_buf << "}";
wxchan's avatar
wxchan committed
494
  }
Guolin Ke's avatar
Guolin Ke committed
495
  str_buf << "]" << std::endl;
wxchan's avatar
wxchan committed
496

Guolin Ke's avatar
Guolin Ke committed
497
  str_buf << "}" << std::endl;
wxchan's avatar
wxchan committed
498

Guolin Ke's avatar
Guolin Ke committed
499
  return str_buf.str();
wxchan's avatar
wxchan committed
500
501
502
503
504
505
506
}

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
507
  output_file << SubModelName() << std::endl;
wxchan's avatar
wxchan committed
508
509
510
511
512
513
514
515
516
  // 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;
517
  }
wxchan's avatar
wxchan committed
518
519
  // output sigmoid parameter
  output_file << "sigmoid=" << sigmoid_ << std::endl;
520
521

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

Guolin Ke's avatar
Guolin Ke committed
523
  output_file << std::endl;
524
525
526
  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
527
  }
528
  // output tree models
wxchan's avatar
wxchan committed
529
530
531
  for (int i = 0; i < num_used_model; ++i) {
    output_file << "Tree=" << i << std::endl;
    output_file << models_[i]->ToString() << std::endl;
532
  }
533

wxchan's avatar
wxchan committed
534
535
536
537
  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
538
  }
wxchan's avatar
wxchan committed
539
  output_file.close();
Guolin Ke's avatar
Guolin Ke committed
540
541
}

Guolin Ke's avatar
Guolin Ke committed
542
void GBDT::LoadModelFromString(const std::string& model_str) {
Guolin Ke's avatar
Guolin Ke committed
543
544
545
  // use serialized string to restore this object
  models_.clear();
  std::vector<std::string> lines = Common::Split(model_str.c_str(), '\n');
546
547

  // get number of classes
548
549
550
551
  auto line = Common::FindFromLines(lines, "num_class=");
  if (line.size() > 0) {
    Common::Atoi(Common::Split(line.c_str(), '=')[1].c_str(), &num_class_);
  } else {
552
    Log::Fatal("Model file doesn't specify the number of classes");
553
554
    return;
  }
Guolin Ke's avatar
Guolin Ke committed
555
  // get index of label
556
557
558
559
  line = Common::FindFromLines(lines, "label_index=");
  if (line.size() > 0) {
    Common::Atoi(Common::Split(line.c_str(), '=')[1].c_str(), &label_idx_);
  } else {
560
    Log::Fatal("Model file doesn't specify the label index");
Guolin Ke's avatar
Guolin Ke committed
561
562
    return;
  }
Guolin Ke's avatar
Guolin Ke committed
563
  // get max_feature_idx first
564
565
566
567
  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 {
568
    Log::Fatal("Model file doesn't specify max_feature_idx");
Guolin Ke's avatar
Guolin Ke committed
569
570
571
    return;
  }
  // get sigmoid parameter
572
573
574
575
  line = Common::FindFromLines(lines, "sigmoid=");
  if (line.size() > 0) {
    Common::Atof(Common::Split(line.c_str(), '=')[1].c_str(), &sigmoid_);
  } else {
576
    sigmoid_ = -1.0f;
Guolin Ke's avatar
Guolin Ke committed
577
  }
Guolin Ke's avatar
Guolin Ke committed
578
579
580
  // get feature names
  line = Common::FindFromLines(lines, "feature_names=");
  if (line.size() > 0) {
Guolin Ke's avatar
Guolin Ke committed
581
    feature_names_ = Common::Split(line.substr(std::strlen("feature_names=")).c_str(), " ");
Guolin Ke's avatar
Guolin Ke committed
582
583
584
585
586
587
588
589
590
    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
591
  // get tree models
592
  size_t i = 0;
Guolin Ke's avatar
Guolin Ke committed
593
594
595
596
597
598
599
  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
600
      std::string tree_str = Common::Join<std::string>(lines, start, end, "\n");
Guolin Ke's avatar
Guolin Ke committed
601
602
      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
603
604
605
606
    } else {
      ++i;
    }
  }
607
  Log::Info("Finished loading %d models", models_.size());
wxchan's avatar
wxchan committed
608
609
  num_iteration_for_pred_ = static_cast<int>(models_.size()) / num_class_;
  num_init_iteration_ = num_iteration_for_pred_;
610
  iter_ = 0;
Guolin Ke's avatar
Guolin Ke committed
611
612
}

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

615
  std::vector<size_t> feature_importances(max_feature_idx_ + 1, 0);
616
    for (size_t iter = 0; iter < models_.size(); ++iter) {
617
618
        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
619
620
        }
    }
621
622
623
    // 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
624
      if (feature_importances[i] > 0) {
625
        pairs.emplace_back(feature_importances[i], feature_names_[i]);
Guolin Ke's avatar
Guolin Ke committed
626
      }
627
628
629
630
631
    }
    // 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) {
632
      return lhs.first > rhs.first;
633
    });
wxchan's avatar
wxchan committed
634
    return pairs;
wxchan's avatar
wxchan committed
635
636
}

637
638
std::vector<double> GBDT::PredictRaw(const double* value) const {
  std::vector<double> ret(num_class_, 0.0f);
wxchan's avatar
wxchan committed
639
  for (int i = 0; i < num_iteration_for_pred_; ++i) {
640
641
642
    for (int j = 0; j < num_class_; ++j) {
      ret[j] += models_[i * num_class_ + j]->Predict(value);
    }
Guolin Ke's avatar
Guolin Ke committed
643
644
645
646
  }
  return ret;
}

647
std::vector<double> GBDT::Predict(const double* value) const {
648
  std::vector<double> ret(num_class_, 0.0f);
wxchan's avatar
wxchan committed
649
  for (int i = 0; i < num_iteration_for_pred_; ++i) {
650
651
    for (int j = 0; j < num_class_; ++j) {
      ret[j] += models_[i * num_class_ + j]->Predict(value);
652
653
    }
  }
654
655
656
657
658
659
  // 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);
  }
660
661
662
  return ret;
}

663
std::vector<int> GBDT::PredictLeafIndex(const double* value) const {
wxchan's avatar
wxchan committed
664
  std::vector<int> ret;
wxchan's avatar
wxchan committed
665
  for (int i = 0; i < num_iteration_for_pred_; ++i) {
666
667
668
    for (int j = 0; j < num_class_; ++j) {
      ret.push_back(models_[i * num_class_ + j]->PredictLeafIndex(value));
    }
wxchan's avatar
wxchan committed
669
670
671
672
  }
  return ret;
}

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