gbdt.h 11.7 KB
Newer Older
Guolin Ke's avatar
Guolin Ke committed
1
2
3
4
5
6
7
8
9
#ifndef LIGHTGBM_BOOSTING_GBDT_H_
#define LIGHTGBM_BOOSTING_GBDT_H_

#include <LightGBM/boosting.h>
#include "score_updater.hpp"

#include <cstdio>
#include <vector>
#include <string>
10
#include <fstream>
Guolin Ke's avatar
Guolin Ke committed
11
#include <memory>
Guolin Ke's avatar
Guolin Ke committed
12
13
14
15
16
17
18
19
20
21

namespace LightGBM {
/*!
* \brief GBDT algorithm implementation. including Training, prediction, bagging.
*/
class GBDT: public Boosting {
public:
  /*!
  * \brief Constructor
  */
22
  GBDT();
Guolin Ke's avatar
Guolin Ke committed
23
24
25
26
27
  /*!
  * \brief Destructor
  */
  ~GBDT();
  /*!
Qiwei Ye's avatar
Qiwei Ye committed
28
  * \brief Initialization logic
Guolin Ke's avatar
Guolin Ke committed
29
30
31
32
33
34
  * \param config Config for boosting
  * \param train_data Training data
  * \param object_function Training objective function
  * \param training_metrics Training metrics
  * \param output_model_filename Filename of output model
  */
35
36
  void Init(const BoostingConfig* gbdt_config, const Dataset* train_data, const ObjectiveFunction* object_function,
                             const std::vector<const Metric*>& training_metrics)
Guolin Ke's avatar
Guolin Ke committed
37
                                                                       override;
wxchan's avatar
wxchan committed
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70

  /*!
  * \brief Merge model from other boosting object
           Will insert to the front of current boosting object
  * \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));
    }
    num_init_iteration_ = static_cast<int>(models_.size()) / num_class_;
    // 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));
    }
    num_iteration_for_pred_ = static_cast<int>(models_.size()) / num_class_;
  }

  /*!
  * \brief Reset training data for current boosting
  * \param train_data Training data
  * \param object_function Training objective function
  * \param training_metrics Training metric
  */
  void ResetTrainingData(const BoostingConfig* config, const Dataset* train_data, const ObjectiveFunction* object_function, const std::vector<const Metric*>& training_metrics) override;

Guolin Ke's avatar
Guolin Ke committed
71
  /*!
Qiwei Ye's avatar
Qiwei Ye committed
72
73
74
  * \brief Adding a validation dataset
  * \param valid_data Validation dataset
  * \param valid_metrics Metrics for validation dataset
Guolin Ke's avatar
Guolin Ke committed
75
  */
wxchan's avatar
wxchan committed
76
  void AddValidDataset(const Dataset* valid_data,
Guolin Ke's avatar
Guolin Ke committed
77
78
       const std::vector<const Metric*>& valid_metrics) override;
  /*!
Guolin Ke's avatar
Guolin Ke committed
79
80
81
  * \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
82
  * \param is_eval true if need evaluation or early stop
Guolin Ke's avatar
Guolin Ke committed
83
  * \return True if meet early stopping or cannot boosting
Guolin Ke's avatar
Guolin Ke committed
84
  */
85
  virtual bool TrainOneIter(const score_t* gradient, const score_t* hessian, bool is_eval) override;
86

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

  int GetCurrentIteration() const override { return iter_ + num_init_iteration_; }

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

Guolin Ke's avatar
Guolin Ke committed
96
97
98
99
100
  /*!
  * \brief Get evaluation result at data_idx data
  * \param data_idx 0: training data, 1: 1st validation data
  * \return evaluation result
  */
101
  std::vector<double> GetEvalAt(int data_idx) const override;
102

Guolin Ke's avatar
Guolin Ke committed
103
104
  /*!
  * \brief Get current training score
Guolin Ke's avatar
Guolin Ke committed
105
  * \param out_len length of returned score
Guolin Ke's avatar
Guolin Ke committed
106
107
  * \return training score
  */
108
  virtual const double* GetTrainingScore(int64_t* out_len) override;
109

Guolin Ke's avatar
Guolin Ke committed
110
111
112
113
114
115
116
117
  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
118
119
120
121
122
123
  /*!
  * \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
  * \param out_len lenght of returned score
  */
Guolin Ke's avatar
Guolin Ke committed
124
  void GetPredictAt(int data_idx, double* out_result, int64_t* out_len) override;
Guolin Ke's avatar
Guolin Ke committed
125

Guolin Ke's avatar
Guolin Ke committed
126
  /*!
wxchan's avatar
wxchan committed
127
  * \brief Prediction for one record without sigmoid transformation
Guolin Ke's avatar
Guolin Ke committed
128
129
130
  * \param feature_values Feature value on this record
  * \return Prediction result for this record
  */
131
  std::vector<double> PredictRaw(const double* feature_values) const override;
Guolin Ke's avatar
Guolin Ke committed
132
133

  /*!
wxchan's avatar
wxchan committed
134
  * \brief Prediction for one record with sigmoid transformation if enabled
Guolin Ke's avatar
Guolin Ke committed
135
136
137
  * \param feature_values Feature value on this record
  * \return Prediction result for this record
  */
138
  std::vector<double> Predict(const double* feature_values) const override;
wxchan's avatar
wxchan committed
139

wxchan's avatar
wxchan committed
140
  /*!
wxchan's avatar
wxchan committed
141
  * \brief Prediction for one record with leaf index
wxchan's avatar
wxchan committed
142
143
144
  * \param feature_values Feature value on this record
  * \return Predicted leaf index for this record
  */
145
  std::vector<int> PredictLeafIndex(const double* value) const override;
wxchan's avatar
wxchan committed
146

Guolin Ke's avatar
Guolin Ke committed
147
  /*!
wxchan's avatar
wxchan committed
148
149
  * \brief Dump model to json format string
  * \return Json format string of model
Guolin Ke's avatar
Guolin Ke committed
150
  */
151
  std::string DumpModel(int num_iteration) const override;
wxchan's avatar
wxchan committed
152
153
154
155
156
157
158

  /*!
  * \brief Save model to file
  * \param num_used_model Number of model that want to save, -1 means save all
  * \param is_finish Is training finished or not
  * \param filename Filename that want to save to
  */
159
  virtual bool SaveModelToFile(int num_iterations, const char* filename) const override ;
wxchan's avatar
wxchan committed
160

Guolin Ke's avatar
Guolin Ke committed
161
162
163
  /*!
  * \brief Restore from a serialized string
  */
164
  bool LoadModelFromString(const std::string& model_str) override;
wxchan's avatar
wxchan committed
165

Guolin Ke's avatar
Guolin Ke committed
166
167
168
169
170
  /*!
  * \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
171
172
173
174
175
176
177

  /*!
  * \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
178
179
180
181
  /*!
  * \brief Get number of weak sub-models
  * \return Number of weak sub-models
  */
wxchan's avatar
wxchan committed
182
  inline int NumberOfTotalModel() const override { return static_cast<int>(models_.size()); }
Guolin Ke's avatar
Guolin Ke committed
183

184
185
186
187
  /*!
  * \brief Get number of classes
  * \return Number of classes
  */
Guolin Ke's avatar
Guolin Ke committed
188
  inline int NumberOfClasses() const override { return num_class_; }
189
190

  /*!
wxchan's avatar
wxchan committed
191
  * \brief Set number of iterations for prediction
192
  */
wxchan's avatar
wxchan committed
193
  inline void SetNumIterationForPred(int num_iteration) override {
194
    num_iteration_for_pred_ = static_cast<int>(models_.size()) / num_class_;
wxchan's avatar
wxchan committed
195
    if (num_iteration > 0) {
196
      num_iteration_for_pred_ = std::min(num_iteration, num_iteration_for_pred_);
197
198
    }
  }
wxchan's avatar
wxchan committed
199

Guolin Ke's avatar
Guolin Ke committed
200
201
202
203
204
205
206
207
208
209
210
211
  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);
  }

212
213
214
  /*!
  * \brief Get Type name of this boosting object
  */
Guolin Ke's avatar
Guolin Ke committed
215
  virtual const char* SubModelName() const override { return "tree"; }
216

217
protected:
Guolin Ke's avatar
Guolin Ke committed
218
219
220
221
  /*!
  * \brief Implement bagging logic
  * \param iter Current interation
  */
222
223
224
225
226
227
228
229
230
231
  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
  */
  virtual data_size_t BaggingHelper(data_size_t start, data_size_t cnt, data_size_t* buffer);
Guolin Ke's avatar
Guolin Ke committed
232
  /*!
Qiwei Ye's avatar
Qiwei Ye committed
233
234
  * \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
235
  * \param tree Trained tree of this iteration
236
  * \param curr_class Current class for multiclass training
Guolin Ke's avatar
Guolin Ke committed
237
  */
238
  void UpdateScoreOutOfBag(const Tree* tree, const int curr_class);
Guolin Ke's avatar
Guolin Ke committed
239
240
241
242
243
  /*!
  * \brief calculate the object function
  */
  void Boosting();
  /*!
Qiwei Ye's avatar
Qiwei Ye committed
244
  * \brief updating score after tree was trained
Guolin Ke's avatar
Guolin Ke committed
245
  * \param tree Trained tree of this iteration
246
  * \param curr_class Current class for multiclass training
Guolin Ke's avatar
Guolin Ke committed
247
  */
248
  virtual void UpdateScore(const Tree* tree, const int curr_class);
Guolin Ke's avatar
Guolin Ke committed
249
  /*!
Hui Xue's avatar
Hui Xue committed
250
  * \brief Print metric result of current iteration
Guolin Ke's avatar
Guolin Ke committed
251
  * \param iter Current interation
Guolin Ke's avatar
Guolin Ke committed
252
  * \return best_msg if met early_stopping
Guolin Ke's avatar
Guolin Ke committed
253
  */
Guolin Ke's avatar
Guolin Ke committed
254
  std::string OutputMetric(int iter);
wxchan's avatar
wxchan committed
255
256
257
258
  /*!
  * \brief Calculate feature importances
  * \param last_iter Last tree use to calculate
  */
wxchan's avatar
wxchan committed
259
  std::vector<std::pair<size_t, std::string>> FeatureImportance() const;
260
261
  /*! \brief current iteration */
  int iter_;
Guolin Ke's avatar
Guolin Ke committed
262
263
264
  /*! \brief Pointer to training data */
  const Dataset* train_data_;
  /*! \brief Config of gbdt */
Guolin Ke's avatar
Guolin Ke committed
265
  std::unique_ptr<BoostingConfig> gbdt_config_;
Hui Xue's avatar
Hui Xue committed
266
  /*! \brief Tree learner, will use this class to learn trees */
267
  std::unique_ptr<TreeLearner> tree_learner_;
Guolin Ke's avatar
Guolin Ke committed
268
269
  /*! \brief Objective function */
  const ObjectiveFunction* object_function_;
Hui Xue's avatar
Hui Xue committed
270
  /*! \brief Store and update training data's score */
Guolin Ke's avatar
Guolin Ke committed
271
  std::unique_ptr<ScoreUpdater> train_score_updater_;
Guolin Ke's avatar
Guolin Ke committed
272
273
274
  /*! \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
275
  std::vector<std::unique_ptr<ScoreUpdater>> valid_score_updater_;
Guolin Ke's avatar
Guolin Ke committed
276
277
  /*! \brief Metric for validation data */
  std::vector<std::vector<const Metric*>> valid_metrics_;
wxchan's avatar
wxchan committed
278
279
  /*! \brief Number of rounds for early stopping */
  int early_stopping_round_;
Guolin Ke's avatar
Guolin Ke committed
280
  /*! \brief Best iteration(s) for early stopping */
wxchan's avatar
wxchan committed
281
  std::vector<std::vector<int>> best_iter_;
Guolin Ke's avatar
Guolin Ke committed
282
  /*! \brief Best score(s) for early stopping */
283
  std::vector<std::vector<double>> best_score_;
Guolin Ke's avatar
Guolin Ke committed
284
285
  /*! \brief output message of best iteration */
  std::vector<std::vector<std::string>> best_msg_;
Guolin Ke's avatar
Guolin Ke committed
286
  /*! \brief Trained models(trees) */
Guolin Ke's avatar
Guolin Ke committed
287
  std::vector<std::unique_ptr<Tree>> models_;
Guolin Ke's avatar
Guolin Ke committed
288
289
290
  /*! \brief Max feature index of training data*/
  int max_feature_idx_;
  /*! \brief First order derivative of training data */
Guolin Ke's avatar
Guolin Ke committed
291
  std::vector<score_t> gradients_;
Guolin Ke's avatar
Guolin Ke committed
292
  /*! \brief Secend order derivative of training data */
Guolin Ke's avatar
Guolin Ke committed
293
  std::vector<score_t> hessians_;
Guolin Ke's avatar
Guolin Ke committed
294
  /*! \brief Store the indices of in-bag data */
Guolin Ke's avatar
Guolin Ke committed
295
  std::vector<data_size_t> bag_data_indices_;
Guolin Ke's avatar
Guolin Ke committed
296
297
  /*! \brief Number of in-bag data */
  data_size_t bag_data_cnt_;
298
299
  /*! \brief Store the indices of in-bag data */
  std::vector<data_size_t> tmp_indices_;
wxchan's avatar
wxchan committed
300
  /*! \brief Number of training data */
Guolin Ke's avatar
Guolin Ke committed
301
  data_size_t num_data_;
302
303
  /*! \brief Number of classes */
  int num_class_;
Guolin Ke's avatar
Guolin Ke committed
304
  /*! \brief Random generator, used for bagging */
305
  std::vector<Random> random_;
Guolin Ke's avatar
Guolin Ke committed
306
307
  /*!
  *   \brief Sigmoid parameter, used for prediction.
wxchan's avatar
wxchan committed
308
  *          if > 0 means output score will transform by sigmoid function
Guolin Ke's avatar
Guolin Ke committed
309
  */
310
  double sigmoid_;
Guolin Ke's avatar
Guolin Ke committed
311
312
  /*! \brief Index of label column */
  data_size_t label_idx_;
313
  /*! \brief number of used model */
wxchan's avatar
wxchan committed
314
  int num_iteration_for_pred_;
Guolin Ke's avatar
Guolin Ke committed
315
316
  /*! \brief Shrinkage rate for one iteration */
  double shrinkage_rate_;
wxchan's avatar
wxchan committed
317
318
  /*! \brief Number of loaded initial models */
  int num_init_iteration_;
Guolin Ke's avatar
Guolin Ke committed
319
320
  /*! \brief Feature names */
  std::vector<std::string> feature_names_;
321
322
  /*! \brief Feature informations */
  std::vector<std::string> feature_infos_;
323
324
325
326
327
328
329
330
331
332
333
334
  /*! \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
335
336
337
};

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