gbdt.h 13.8 KB
Newer Older
Guolin Ke's avatar
Guolin Ke committed
1
2
3
4
#ifndef LIGHTGBM_BOOSTING_GBDT_H_
#define LIGHTGBM_BOOSTING_GBDT_H_

#include <LightGBM/boosting.h>
5
#include <LightGBM/objective_function.h>
Guolin Ke's avatar
Guolin Ke committed
6
#include <LightGBM/prediction_early_stop.h>
7

Guolin Ke's avatar
Guolin Ke committed
8
9
10
11
12
#include "score_updater.hpp"

#include <cstdio>
#include <vector>
#include <string>
13
#include <fstream>
Guolin Ke's avatar
Guolin Ke committed
14
#include <memory>
15
#include <mutex>
Guolin Ke's avatar
Guolin Ke committed
16
17
18
19
20
21
22
23
24
25

namespace LightGBM {
/*!
* \brief GBDT algorithm implementation. including Training, prediction, bagging.
*/
class GBDT: public Boosting {
public:
  /*!
  * \brief Constructor
  */
26
  GBDT();
Guolin Ke's avatar
Guolin Ke committed
27
28
29
30
31
  /*!
  * \brief Destructor
  */
  ~GBDT();
  /*!
Qiwei Ye's avatar
Qiwei Ye committed
32
  * \brief Initialization logic
zhangyafeikimi's avatar
zhangyafeikimi committed
33
  * \param gbdt_config Config for boosting
Guolin Ke's avatar
Guolin Ke committed
34
  * \param train_data Training data
35
  * \param objective_function Training objective function
Guolin Ke's avatar
Guolin Ke committed
36
37
  * \param training_metrics Training metrics
  */
38
39
40
  void Init(const BoostingConfig* gbdt_config, const Dataset* train_data, const ObjectiveFunction* objective_function,
            const std::vector<const Metric*>& training_metrics)
    override;
wxchan's avatar
wxchan committed
41
42
43

  /*!
  * \brief Merge model from other boosting object
44
  Will insert to the front of current boosting object
wxchan's avatar
wxchan committed
45
46
47
48
49
50
51
52
53
54
55
56
  * \param other
  */
  void MergeFrom(const Boosting* other) override {
    auto other_gbdt = reinterpret_cast<const GBDT*>(other);
    // tmp move to other vector
    auto original_models = std::move(models_);
    models_ = std::vector<std::unique_ptr<Tree>>();
    // push model from other first
    for (const auto& tree : other_gbdt->models_) {
      auto new_tree = std::unique_ptr<Tree>(new Tree(*(tree.get())));
      models_.push_back(std::move(new_tree));
    }
Guolin Ke's avatar
Guolin Ke committed
57
    num_init_iteration_ = static_cast<int>(models_.size()) / num_tree_per_iteration_;
wxchan's avatar
wxchan committed
58
59
60
61
62
    // push model in current object
    for (const auto& tree : original_models) {
      auto new_tree = std::unique_ptr<Tree>(new Tree(*(tree.get())));
      models_.push_back(std::move(new_tree));
    }
Guolin Ke's avatar
Guolin Ke committed
63
    num_iteration_for_pred_ = static_cast<int>(models_.size()) / num_tree_per_iteration_;
wxchan's avatar
wxchan committed
64
65
  }

66
67
  void ResetTrainingData(const Dataset* train_data, const ObjectiveFunction* objective_function,
                         const std::vector<const Metric*>& training_metrics) override;
wxchan's avatar
wxchan committed
68

69
  void ResetConfig(const BoostingConfig* config) override;
Guolin Ke's avatar
Guolin Ke committed
70
  /*!
Qiwei Ye's avatar
Qiwei Ye committed
71
72
73
  * \brief Adding a validation dataset
  * \param valid_data Validation dataset
  * \param valid_metrics Metrics for validation dataset
Guolin Ke's avatar
Guolin Ke committed
74
  */
wxchan's avatar
wxchan committed
75
  void AddValidDataset(const Dataset* valid_data,
76
                       const std::vector<const Metric*>& valid_metrics) override;
Guolin Ke's avatar
Guolin Ke committed
77
78
79

  void Train(int snapshot_freq, const std::string& model_output_path) override;

Guolin Ke's avatar
Guolin Ke committed
80
  /*!
Guolin Ke's avatar
Guolin Ke committed
81
82
83
  * \brief Training logic
  * \param gradient nullptr for using default objective, otherwise use self-defined boosting
  * \param hessian nullptr for using default objective, otherwise use self-defined boosting
Guolin Ke's avatar
Guolin Ke committed
84
  * \param is_eval true if need evaluation or early stop
Guolin Ke's avatar
Guolin Ke committed
85
  * \return True if meet early stopping or cannot boosting
Guolin Ke's avatar
Guolin Ke committed
86
  */
87
  virtual bool TrainOneIter(const score_t* gradient, const score_t* hessian, bool is_eval) override;
88

wxchan's avatar
wxchan committed
89
90
91
92
93
  /*!
  * \brief Rollback one iteration
  */
  void RollbackOneIter() override;

Guolin Ke's avatar
Guolin Ke committed
94
  int GetCurrentIteration() const override { return static_cast<int>(models_.size()) / num_tree_per_iteration_; }
wxchan's avatar
wxchan committed
95

Guolin Ke's avatar
Guolin Ke committed
96
97
  bool EvalAndCheckEarlyStopping() override;

98
  bool NeedAccuratePrediction() const override {
99
100
101
102
103
104
105
    if (objective_function_ == nullptr) {
      return true;
    } else {
      return objective_function_->NeedAccuratePrediction();
    }
  }

Guolin Ke's avatar
Guolin Ke committed
106
107
108
109
110
  /*!
  * \brief Get evaluation result at data_idx data
  * \param data_idx 0: training data, 1: 1st validation data
  * \return evaluation result
  */
111
  std::vector<double> GetEvalAt(int data_idx) const override;
112

Guolin Ke's avatar
Guolin Ke committed
113
114
  /*!
  * \brief Get current training score
Guolin Ke's avatar
Guolin Ke committed
115
  * \param out_len length of returned score
Guolin Ke's avatar
Guolin Ke committed
116
117
  * \return training score
  */
118
  virtual const double* GetTrainingScore(int64_t* out_len) override;
119

Guolin Ke's avatar
Guolin Ke committed
120
121
122
123
124
125
126
127
  virtual int64_t GetNumPredictAt(int data_idx) const override {
    CHECK(data_idx >= 0 && data_idx <= static_cast<int>(valid_score_updater_.size()));
    data_size_t num_data = train_data_->num_data();
    if (data_idx > 0) {
      num_data = valid_score_updater_[data_idx - 1]->num_data();
    }
    return num_data * num_class_;
  }
Guolin Ke's avatar
Guolin Ke committed
128
129
130
131
  /*!
  * \brief Get prediction result at data_idx data
  * \param data_idx 0: training data, 1: 1st validation data
  * \param result used to store prediction result, should allocate memory before call this function
132
  * \param out_len length of returned score
Guolin Ke's avatar
Guolin Ke committed
133
  */
Guolin Ke's avatar
Guolin Ke committed
134
  void GetPredictAt(int data_idx, double* out_result, int64_t* out_len) override;
Guolin Ke's avatar
Guolin Ke committed
135

136
  inline int NumPredictOneRow(int num_iteration, bool is_pred_leaf, bool is_pred_contrib) const override {
Guolin Ke's avatar
Guolin Ke committed
137
138
139
140
141
142
143
144
    int num_preb_in_one_row = num_class_;
    if (is_pred_leaf) {
      int max_iteration = GetCurrentIteration();
      if (num_iteration > 0) {
        num_preb_in_one_row *= static_cast<int>(std::min(max_iteration, num_iteration));
      } else {
        num_preb_in_one_row *= max_iteration;
      }
145
146
    } else if (is_pred_contrib) {
      num_preb_in_one_row = max_feature_idx_ + 2; // +1 for 0-based indexing, +1 for baseline
Guolin Ke's avatar
Guolin Ke committed
147
148
149
    }
    return num_preb_in_one_row;
  }
Guolin Ke's avatar
Guolin Ke committed
150

cbecker's avatar
cbecker committed
151
  void PredictRaw(const double* features, double* output,
152
                  const PredictionEarlyStopInstance* earlyStop) const override;
wxchan's avatar
wxchan committed
153

cbecker's avatar
cbecker committed
154
155
  void Predict(const double* features, double* output,
               const PredictionEarlyStopInstance* earlyStop) const override;
Guolin Ke's avatar
Guolin Ke committed
156

157
  void PredictLeafIndex(const double* features, double* output) const override;
wxchan's avatar
wxchan committed
158

159
160
161
  void PredictContrib(const double* features, double* output,
                      const PredictionEarlyStopInstance* earlyStop) const override;

Guolin Ke's avatar
Guolin Ke committed
162
  /*!
wxchan's avatar
wxchan committed
163
  * \brief Dump model to json format string
164
  * \param num_iteration Number of iterations that want to dump, -1 means dump all
wxchan's avatar
wxchan committed
165
  * \return Json format string of model
Guolin Ke's avatar
Guolin Ke committed
166
  */
167
  std::string DumpModel(int num_iteration) const override;
wxchan's avatar
wxchan committed
168

169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
  /*!
  * \brief Translate model to if-else statement
  * \param num_iteration Number of iterations that want to translate, -1 means translate all
  * \return if-else format codes of model
  */
  std::string ModelToIfElse(int num_iteration) const override;

  /*!
  * \brief Translate model to if-else statement
  * \param num_iteration Number of iterations that want to translate, -1 means translate all
  * \param filename Filename that want to save to
  * \return is_finish Is training finished or not
  */
  bool SaveModelToIfElse(int num_iteration, const char* filename) const override;

wxchan's avatar
wxchan committed
184
185
  /*!
  * \brief Save model to file
wxchan's avatar
wxchan committed
186
  * \param num_iterations Number of model that want to save, -1 means save all
wxchan's avatar
wxchan committed
187
  * \param filename Filename that want to save to
188
  * \return is_finish Is training finished or not
wxchan's avatar
wxchan committed
189
  */
190
  virtual bool SaveModelToFile(int num_iterations, const char* filename) const override;
wxchan's avatar
wxchan committed
191

192
193
  /*!
  * \brief Save model to string
wxchan's avatar
wxchan committed
194
  * \param num_iterations Number of model that want to save, -1 means save all
195
196
  * \return Non-empty string if succeeded
  */
197
  virtual std::string SaveModelToString(int num_iterations) const override;
198

Guolin Ke's avatar
Guolin Ke committed
199
200
201
  /*!
  * \brief Restore from a serialized string
  */
202
  bool LoadModelFromString(const std::string& model_str) override;
wxchan's avatar
wxchan committed
203

204
205
206
207
208
209
210
211
  /*!
  * \brief Calculate feature importances
  * \param num_iteration Number of model that want to use for feature importance, -1 means use all
  * \param importance_type: 0 for split, 1 for gain
  * \return vector of feature_importance
  */
  std::vector<double> FeatureImportance(int num_iteration, int importance_type) const override;

Guolin Ke's avatar
Guolin Ke committed
212
213
214
215
216
  /*!
  * \brief Get max feature index of this model
  * \return Max feature index of this model
  */
  inline int MaxFeatureIdx() const override { return max_feature_idx_; }
Guolin Ke's avatar
Guolin Ke committed
217

wxchan's avatar
wxchan committed
218
219
220
221
222
223
  /*!
  * \brief Get feature names of this model
  * \return Feature names of this model
  */
  inline std::vector<std::string> FeatureNames() const override { return feature_names_; }

Guolin Ke's avatar
Guolin Ke committed
224
225
226
227
228
229
  /*!
  * \brief Get index of label column
  * \return index of label column
  */
  inline int LabelIdx() const override { return label_idx_; }

Guolin Ke's avatar
Guolin Ke committed
230
231
232
233
  /*!
  * \brief Get number of weak sub-models
  * \return Number of weak sub-models
  */
wxchan's avatar
wxchan committed
234
  inline int NumberOfTotalModel() const override { return static_cast<int>(models_.size()); }
Guolin Ke's avatar
Guolin Ke committed
235

Guolin Ke's avatar
Guolin Ke committed
236
237
238
239
240
241
  /*!
  * \brief Get number of tree per iteration
  * \return number of tree per iteration
  */
  inline int NumTreePerIteration() const override { return num_tree_per_iteration_; }

242
243
244
245
  /*!
  * \brief Get number of classes
  * \return Number of classes
  */
Guolin Ke's avatar
Guolin Ke committed
246
  inline int NumberOfClasses() const override { return num_class_; }
247

248
  inline void InitPredict(int num_iteration) override {
Guolin Ke's avatar
Guolin Ke committed
249
    num_iteration_for_pred_ = static_cast<int>(models_.size()) / num_tree_per_iteration_;
wxchan's avatar
wxchan committed
250
    if (num_iteration > 0) {
251
      num_iteration_for_pred_ = std::min(num_iteration + (boost_from_average_ ? 1 : 0), num_iteration_for_pred_);
252
253
    }
  }
wxchan's avatar
wxchan committed
254

Guolin Ke's avatar
Guolin Ke committed
255
256
257
258
259
260
261
262
263
264
265
266
  inline double GetLeafValue(int tree_idx, int leaf_idx) const {
    CHECK(tree_idx >= 0 && static_cast<size_t>(tree_idx) < models_.size());
    CHECK(leaf_idx >= 0 && leaf_idx < models_[tree_idx]->num_leaves());
    return models_[tree_idx]->LeafOutput(leaf_idx);
  }

  inline void SetLeafValue(int tree_idx, int leaf_idx, double val) {
    CHECK(tree_idx >= 0 && static_cast<size_t>(tree_idx) < models_.size());
    CHECK(leaf_idx >= 0 && leaf_idx < models_[tree_idx]->num_leaves());
    models_[tree_idx]->SetLeafOutput(leaf_idx, val);
  }

267
268
269
  /*!
  * \brief Get Type name of this boosting object
  */
Guolin Ke's avatar
Guolin Ke committed
270
  virtual const char* SubModelName() const override { return "tree"; }
271

272
protected:
Guolin Ke's avatar
Guolin Ke committed
273
  void ResetBaggingConfig(const BoostingConfig* config, bool is_change_dataset);
Guolin Ke's avatar
Guolin Ke committed
274
275
276
277
  /*!
  * \brief Implement bagging logic
  * \param iter Current interation
  */
278
279
280
281
282
283
284
285
286
  virtual void Bagging(int iter);

  /*!
  * \brief Helper function for bagging, used for multi-threading optimization
  * \param start start indice of bagging
  * \param cnt count
  * \param buffer output buffer
  * \return count of left size
  */
Guolin Ke's avatar
Guolin Ke committed
287
  data_size_t BaggingHelper(Random& cur_rand, data_size_t start, data_size_t cnt, data_size_t* buffer);
Guolin Ke's avatar
Guolin Ke committed
288
  /*!
Qiwei Ye's avatar
Qiwei Ye committed
289
290
  * \brief updating score for out-of-bag data.
  *        Data should be update since we may re-bagging data on training
Guolin Ke's avatar
Guolin Ke committed
291
  * \param tree Trained tree of this iteration
292
  * \param cur_tree_id Current tree for multiclass training
Guolin Ke's avatar
Guolin Ke committed
293
  */
Guolin Ke's avatar
Guolin Ke committed
294
  virtual void UpdateScoreOutOfBag(const Tree* tree, const int cur_tree_id);
Guolin Ke's avatar
Guolin Ke committed
295
296
297
  /*!
  * \brief calculate the object function
  */
Guolin Ke's avatar
Guolin Ke committed
298
  virtual void Boosting();
Guolin Ke's avatar
Guolin Ke committed
299
  /*!
Qiwei Ye's avatar
Qiwei Ye committed
300
  * \brief updating score after tree was trained
Guolin Ke's avatar
Guolin Ke committed
301
  * \param tree Trained tree of this iteration
302
  * \param cur_tree_id Current tree for multiclass training
Guolin Ke's avatar
Guolin Ke committed
303
  */
304
  virtual void UpdateScore(const Tree* tree, const int cur_tree_id);
Guolin Ke's avatar
Guolin Ke committed
305
306

  virtual std::vector<double> EvalOneMetric(const Metric* metric, const double* score) const;
Guolin Ke's avatar
Guolin Ke committed
307
  /*!
Hui Xue's avatar
Hui Xue committed
308
  * \brief Print metric result of current iteration
Guolin Ke's avatar
Guolin Ke committed
309
  * \param iter Current interation
Guolin Ke's avatar
Guolin Ke committed
310
  * \return best_msg if met early_stopping
Guolin Ke's avatar
Guolin Ke committed
311
  */
Guolin Ke's avatar
Guolin Ke committed
312
  std::string OutputMetric(int iter);
313

314
315
  /*! \brief current iteration */
  int iter_;
Guolin Ke's avatar
Guolin Ke committed
316
317
318
  /*! \brief Pointer to training data */
  const Dataset* train_data_;
  /*! \brief Config of gbdt */
Guolin Ke's avatar
Guolin Ke committed
319
  std::unique_ptr<BoostingConfig> gbdt_config_;
Hui Xue's avatar
Hui Xue committed
320
  /*! \brief Tree learner, will use this class to learn trees */
321
  std::unique_ptr<TreeLearner> tree_learner_;
Guolin Ke's avatar
Guolin Ke committed
322
  /*! \brief Objective function */
323
  const ObjectiveFunction* objective_function_;
Hui Xue's avatar
Hui Xue committed
324
  /*! \brief Store and update training data's score */
Guolin Ke's avatar
Guolin Ke committed
325
  std::unique_ptr<ScoreUpdater> train_score_updater_;
Guolin Ke's avatar
Guolin Ke committed
326
327
328
  /*! \brief Metrics for training data */
  std::vector<const Metric*> training_metrics_;
  /*! \brief Store and update validation data's scores */
Guolin Ke's avatar
Guolin Ke committed
329
  std::vector<std::unique_ptr<ScoreUpdater>> valid_score_updater_;
Guolin Ke's avatar
Guolin Ke committed
330
331
  /*! \brief Metric for validation data */
  std::vector<std::vector<const Metric*>> valid_metrics_;
wxchan's avatar
wxchan committed
332
333
  /*! \brief Number of rounds for early stopping */
  int early_stopping_round_;
Guolin Ke's avatar
Guolin Ke committed
334
  /*! \brief Best iteration(s) for early stopping */
wxchan's avatar
wxchan committed
335
  std::vector<std::vector<int>> best_iter_;
Guolin Ke's avatar
Guolin Ke committed
336
  /*! \brief Best score(s) for early stopping */
337
  std::vector<std::vector<double>> best_score_;
Guolin Ke's avatar
Guolin Ke committed
338
339
  /*! \brief output message of best iteration */
  std::vector<std::vector<std::string>> best_msg_;
Guolin Ke's avatar
Guolin Ke committed
340
  /*! \brief Trained models(trees) */
Guolin Ke's avatar
Guolin Ke committed
341
  std::vector<std::unique_ptr<Tree>> models_;
Guolin Ke's avatar
Guolin Ke committed
342
343
344
  /*! \brief Max feature index of training data*/
  int max_feature_idx_;
  /*! \brief First order derivative of training data */
345
  std::vector<score_t> gradients_;
Guolin Ke's avatar
Guolin Ke committed
346
  /*! \brief Secend order derivative of training data */
347
  std::vector<score_t> hessians_;
Guolin Ke's avatar
Guolin Ke committed
348
  /*! \brief Store the indices of in-bag data */
Guolin Ke's avatar
Guolin Ke committed
349
  std::vector<data_size_t> bag_data_indices_;
Guolin Ke's avatar
Guolin Ke committed
350
351
  /*! \brief Number of in-bag data */
  data_size_t bag_data_cnt_;
352
353
  /*! \brief Store the indices of in-bag data */
  std::vector<data_size_t> tmp_indices_;
wxchan's avatar
wxchan committed
354
  /*! \brief Number of training data */
Guolin Ke's avatar
Guolin Ke committed
355
  data_size_t num_data_;
356
357
358
  /*! \brief Number of trees per iterations */
  int num_tree_per_iteration_;
  /*! \brief Number of class */
359
  int num_class_;
Guolin Ke's avatar
Guolin Ke committed
360
361
  /*! \brief Index of label column */
  data_size_t label_idx_;
362
  /*! \brief number of used model */
wxchan's avatar
wxchan committed
363
  int num_iteration_for_pred_;
Guolin Ke's avatar
Guolin Ke committed
364
365
  /*! \brief Shrinkage rate for one iteration */
  double shrinkage_rate_;
wxchan's avatar
wxchan committed
366
367
  /*! \brief Number of loaded initial models */
  int num_init_iteration_;
Guolin Ke's avatar
Guolin Ke committed
368
369
  /*! \brief Feature names */
  std::vector<std::string> feature_names_;
Guolin Ke's avatar
Guolin Ke committed
370
  std::vector<std::string> feature_infos_;
371
372
373
374
375
376
377
378
379
380
381
382
  /*! \brief number of threads */
  int num_threads_;
  /*! \brief Buffer for multi-threading bagging */
  std::vector<data_size_t> offsets_buf_;
  /*! \brief Buffer for multi-threading bagging */
  std::vector<data_size_t> left_cnts_buf_;
  /*! \brief Buffer for multi-threading bagging */
  std::vector<data_size_t> right_cnts_buf_;
  /*! \brief Buffer for multi-threading bagging */
  std::vector<data_size_t> left_write_pos_buf_;
  /*! \brief Buffer for multi-threading bagging */
  std::vector<data_size_t> right_write_pos_buf_;
Guolin Ke's avatar
Guolin Ke committed
383
384
  std::unique_ptr<Dataset> tmp_subset_;
  bool is_use_subset_;
385
  bool boost_from_average_;
386
387
  std::vector<bool> class_need_train_;
  std::vector<double> class_default_output_;
388
  bool is_constant_hessian_;
389
  std::unique_ptr<ObjectiveFunction> loaded_objective_;
Guolin Ke's avatar
Guolin Ke committed
390
  bool average_output_;
Guolin Ke's avatar
Guolin Ke committed
391
  bool need_re_bagging_ = false;
Guolin Ke's avatar
Guolin Ke committed
392
393
394
};

}  // namespace LightGBM
Guolin Ke's avatar
Guolin Ke committed
395
#endif   // LightGBM_BOOSTING_GBDT_H_