gbdt.h 13.4 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
  /*!
Guolin Ke's avatar
Guolin Ke committed
78
79
80
  * \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
81
  * \param is_eval true if need evaluation or early stop
Guolin Ke's avatar
Guolin Ke committed
82
  * \return True if meet early stopping or cannot boosting
Guolin Ke's avatar
Guolin Ke committed
83
  */
84
  virtual bool TrainOneIter(const score_t* gradient, const score_t* hessian, bool is_eval) override;
85

wxchan's avatar
wxchan committed
86
87
88
89
90
  /*!
  * \brief Rollback one iteration
  */
  void RollbackOneIter() override;

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

Guolin Ke's avatar
Guolin Ke committed
93
94
  bool EvalAndCheckEarlyStopping() override;

95
96
97
98
99
100
101
102
  bool NeedAccuratePrediction() const override { 
    if (objective_function_ == nullptr) {
      return true;
    } else {
      return objective_function_->NeedAccuratePrediction();
    }
  }

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

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

Guolin Ke's avatar
Guolin Ke committed
117
118
119
120
121
122
123
124
  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
125
126
127
128
  /*!
  * \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
129
  * \param out_len length of returned score
Guolin Ke's avatar
Guolin Ke committed
130
  */
Guolin Ke's avatar
Guolin Ke committed
131
  void GetPredictAt(int data_idx, double* out_result, int64_t* out_len) override;
Guolin Ke's avatar
Guolin Ke committed
132

Guolin Ke's avatar
Guolin Ke committed
133
134
135
136
137
138
139
140
141
142
143
144
  inline int NumPredictOneRow(int num_iteration, int is_pred_leaf) const override {
    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;
      }
    }
    return num_preb_in_one_row;
  }
Guolin Ke's avatar
Guolin Ke committed
145

cbecker's avatar
cbecker committed
146
  void PredictRaw(const double* features, double* output,
147
                  const PredictionEarlyStopInstance* earlyStop) const override;
wxchan's avatar
wxchan committed
148

cbecker's avatar
cbecker committed
149
150
  void Predict(const double* features, double* output,
               const PredictionEarlyStopInstance* earlyStop) const override;
Guolin Ke's avatar
Guolin Ke committed
151

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

Guolin Ke's avatar
Guolin Ke committed
154
  /*!
wxchan's avatar
wxchan committed
155
  * \brief Dump model to json format string
156
  * \param num_iteration Number of iterations that want to dump, -1 means dump all
wxchan's avatar
wxchan committed
157
  * \return Json format string of model
Guolin Ke's avatar
Guolin Ke committed
158
  */
159
  std::string DumpModel(int num_iteration) const override;
wxchan's avatar
wxchan committed
160

161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
  /*!
  * \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
176
177
  /*!
  * \brief Save model to file
wxchan's avatar
wxchan committed
178
  * \param num_iterations Number of model that want to save, -1 means save all
wxchan's avatar
wxchan committed
179
  * \param filename Filename that want to save to
180
  * \return is_finish Is training finished or not
wxchan's avatar
wxchan committed
181
  */
182
  virtual bool SaveModelToFile(int num_iterations, const char* filename) const override;
wxchan's avatar
wxchan committed
183

184
185
  /*!
  * \brief Save model to string
wxchan's avatar
wxchan committed
186
  * \param num_iterations Number of model that want to save, -1 means save all
187
188
  * \return Non-empty string if succeeded
  */
189
  virtual std::string SaveModelToString(int num_iterations) const override;
190

Guolin Ke's avatar
Guolin Ke committed
191
192
193
  /*!
  * \brief Restore from a serialized string
  */
194
  bool LoadModelFromString(const std::string& model_str) override;
wxchan's avatar
wxchan committed
195

Guolin Ke's avatar
Guolin Ke committed
196
197
198
199
200
  /*!
  * \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
201

wxchan's avatar
wxchan committed
202
203
204
205
206
207
  /*!
  * \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
208
209
210
211
212
213
  /*!
  * \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
214
215
216
217
  /*!
  * \brief Get number of weak sub-models
  * \return Number of weak sub-models
  */
wxchan's avatar
wxchan committed
218
  inline int NumberOfTotalModel() const override { return static_cast<int>(models_.size()); }
Guolin Ke's avatar
Guolin Ke committed
219

Guolin Ke's avatar
Guolin Ke committed
220
221
222
223
224
225
  /*!
  * \brief Get number of tree per iteration
  * \return number of tree per iteration
  */
  inline int NumTreePerIteration() const override { return num_tree_per_iteration_; }

226
227
228
229
  /*!
  * \brief Get number of classes
  * \return Number of classes
  */
Guolin Ke's avatar
Guolin Ke committed
230
  inline int NumberOfClasses() const override { return num_class_; }
231

232
  inline void InitPredict(int num_iteration) override {
Guolin Ke's avatar
Guolin Ke committed
233
    num_iteration_for_pred_ = static_cast<int>(models_.size()) / num_tree_per_iteration_;
wxchan's avatar
wxchan committed
234
    if (num_iteration > 0) {
235
      num_iteration_for_pred_ = std::min(num_iteration + (boost_from_average_ ? 1 : 0), num_iteration_for_pred_);
236
237
    }
  }
wxchan's avatar
wxchan committed
238

Guolin Ke's avatar
Guolin Ke committed
239
240
241
242
243
244
245
246
247
248
249
250
  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);
  }

251
252
253
  /*!
  * \brief Get Type name of this boosting object
  */
Guolin Ke's avatar
Guolin Ke committed
254
  virtual const char* SubModelName() const override { return "tree"; }
255

256
protected:
257
  void ResetBaggingConfig(const BoostingConfig* config);
Guolin Ke's avatar
Guolin Ke committed
258
259
260
261
  /*!
  * \brief Implement bagging logic
  * \param iter Current interation
  */
262
263
264
265
266
267
268
269
270
  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
271
  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
272
  /*!
Qiwei Ye's avatar
Qiwei Ye committed
273
274
  * \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
275
  * \param tree Trained tree of this iteration
276
  * \param cur_tree_id Current tree for multiclass training
Guolin Ke's avatar
Guolin Ke committed
277
  */
Guolin Ke's avatar
Guolin Ke committed
278
  virtual void UpdateScoreOutOfBag(const Tree* tree, const int cur_tree_id);
Guolin Ke's avatar
Guolin Ke committed
279
280
281
  /*!
  * \brief calculate the object function
  */
Guolin Ke's avatar
Guolin Ke committed
282
  virtual void Boosting();
Guolin Ke's avatar
Guolin Ke committed
283
  /*!
Qiwei Ye's avatar
Qiwei Ye committed
284
  * \brief updating score after tree was trained
Guolin Ke's avatar
Guolin Ke committed
285
  * \param tree Trained tree of this iteration
286
  * \param cur_tree_id Current tree for multiclass training
Guolin Ke's avatar
Guolin Ke committed
287
  */
288
  virtual void UpdateScore(const Tree* tree, const int cur_tree_id);
Guolin Ke's avatar
Guolin Ke committed
289
290

  virtual std::vector<double> EvalOneMetric(const Metric* metric, const double* score) const;
Guolin Ke's avatar
Guolin Ke committed
291
  /*!
Hui Xue's avatar
Hui Xue committed
292
  * \brief Print metric result of current iteration
Guolin Ke's avatar
Guolin Ke committed
293
  * \param iter Current interation
Guolin Ke's avatar
Guolin Ke committed
294
  * \return best_msg if met early_stopping
Guolin Ke's avatar
Guolin Ke committed
295
  */
Guolin Ke's avatar
Guolin Ke committed
296
  std::string OutputMetric(int iter);
wxchan's avatar
wxchan committed
297
298
  /*!
  * \brief Calculate feature importances
wxchan's avatar
wxchan committed
299
300
  * \param num_used_model Number of model that want to use for feature importance, -1 means use all 
  * \return sorted pairs of (feature_importance, feature_name)
wxchan's avatar
wxchan committed
301
  */
wxchan's avatar
wxchan committed
302
  std::vector<std::pair<size_t, std::string>> FeatureImportance(int num_used_model) const;
303

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

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