gbdt.h 13 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
zhangyafeikimi's avatar
zhangyafeikimi committed
29
  * \param gbdt_config Config for boosting
Guolin Ke's avatar
Guolin Ke committed
30
  * \param train_data Training data
31
  * \param objective_function Training objective function
Guolin Ke's avatar
Guolin Ke committed
32
33
  * \param training_metrics Training metrics
  */
34
35
36
  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
37
38
39

  /*!
  * \brief Merge model from other boosting object
40
  Will insert to the front of current boosting object
wxchan's avatar
wxchan committed
41
42
43
44
45
46
47
48
49
50
51
52
  * \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
53
    num_init_iteration_ = static_cast<int>(models_.size()) / num_tree_per_iteration_;
wxchan's avatar
wxchan committed
54
55
56
57
58
    // 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
59
    num_iteration_for_pred_ = static_cast<int>(models_.size()) / num_tree_per_iteration_;
wxchan's avatar
wxchan committed
60
61
62
63
64
  }

  /*!
  * \brief Reset training data for current boosting
  * \param train_data Training data
65
  * \param objective_function Training objective function
wxchan's avatar
wxchan committed
66
67
  * \param training_metrics Training metric
  */
68
  void ResetTrainingData(const BoostingConfig* config, const Dataset* train_data, const ObjectiveFunction* objective_function, const std::vector<const Metric*>& training_metrics) override;
wxchan's avatar
wxchan committed
69

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;

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

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

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

Guolin Ke's avatar
Guolin Ke committed
125
126
127
128
129
130
131
132
133
134
135
136
  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
137

Guolin Ke's avatar
Guolin Ke committed
138
  void PredictRaw(const double* feature_values, double* output) const override;
wxchan's avatar
wxchan committed
139

Guolin Ke's avatar
Guolin Ke committed
140
141
142
  void Predict(const double* feature_values, double* output) const override;

  void PredictLeafIndex(const double* value, double* output) const override;
wxchan's avatar
wxchan committed
143

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

  /*!
  * \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
  */
156
  virtual bool SaveModelToFile(int num_iterations, const char* filename) const override;
wxchan's avatar
wxchan committed
157

158
159
160
161
162
  /*!
  * \brief Save model to string
  * \param num_used_model Number of model that want to save, -1 means save all
  * \return Non-empty string if succeeded
  */
163
  virtual std::string SaveModelToString(int num_iterations) const override;
164

Guolin Ke's avatar
Guolin Ke committed
165
166
167
  /*!
  * \brief Restore from a serialized string
  */
168
  bool LoadModelFromString(const std::string& model_str) override;
wxchan's avatar
wxchan committed
169

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

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

Guolin Ke's avatar
Guolin Ke committed
194
195
196
197
198
199
  /*!
  * \brief Get number of tree per iteration
  * \return number of tree per iteration
  */
  inline int NumTreePerIteration() const override { return num_tree_per_iteration_; }

200
201
202
203
  /*!
  * \brief Get number of classes
  * \return Number of classes
  */
Guolin Ke's avatar
Guolin Ke committed
204
  inline int NumberOfClasses() const override { return num_class_; }
205

Guolin Ke's avatar
Guolin Ke committed
206
207
  inline std::vector<int> InitPredict(int num_iteration) override {
    num_iteration_for_pred_ = static_cast<int>(models_.size()) / num_tree_per_iteration_;
wxchan's avatar
wxchan committed
208
    if (num_iteration > 0) {
209
      num_iteration_for_pred_ = std::min(num_iteration + (boost_from_average_ ? 1 : 0), num_iteration_for_pred_);
210
    }
Guolin Ke's avatar
Guolin Ke committed
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
237
238
    int used_fidx = 0;
    // Construct used feature mapper
    std::vector<int> feature_mapper(max_feature_idx_ + 1, -1);
    int total_tree = num_iteration_for_pred_ * num_tree_per_iteration_;

    #pragma omp parallel for schedule(static, 64) if (total_tree >= 128)
    for (int i = 0; i < total_tree; ++i) {
      int num_leaves = models_[i]->num_leaves();
      for (int j = 0; j < num_leaves - 1; ++j) {
        int fidx = models_[i]->split_feature(j);
        if (feature_mapper[fidx] == -1) {
          #pragma omp critical
          {
            if (feature_mapper[fidx] == -1) {
              feature_mapper[fidx] = used_fidx;
              ++used_fidx;
            }
          }
        }
      }
    }

    #pragma omp parallel for schedule(static, 64) if (total_tree >= 128)
    for (int i = 0; i < total_tree; ++i) {
      models_[i]->ReMapFeature(feature_mapper);
    }

    return feature_mapper;
239
  }
wxchan's avatar
wxchan committed
240

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

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

258
protected:
Guolin Ke's avatar
Guolin Ke committed
259
260
261
262
  /*!
  * \brief Implement bagging logic
  * \param iter Current interation
  */
263
264
265
266
267
268
269
270
271
  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
272
  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
273
  /*!
Qiwei Ye's avatar
Qiwei Ye committed
274
275
  * \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
276
  * \param tree Trained tree of this iteration
277
  * \param cur_tree_id Current tree for multiclass training
Guolin Ke's avatar
Guolin Ke committed
278
  */
279
  void UpdateScoreOutOfBag(const Tree* tree, const int cur_tree_id);
Guolin Ke's avatar
Guolin Ke committed
280
281
282
283
284
  /*!
  * \brief calculate the object function
  */
  void Boosting();
  /*!
Qiwei Ye's avatar
Qiwei Ye committed
285
  * \brief updating score after tree was trained
Guolin Ke's avatar
Guolin Ke committed
286
  * \param tree Trained tree of this iteration
287
  * \param cur_tree_id Current tree for multiclass training
Guolin Ke's avatar
Guolin Ke committed
288
  */
289
  virtual void UpdateScore(const Tree* tree, const int cur_tree_id);
Guolin Ke's avatar
Guolin Ke committed
290
  /*!
Hui Xue's avatar
Hui Xue committed
291
  * \brief Print metric result of current iteration
Guolin Ke's avatar
Guolin Ke committed
292
  * \param iter Current interation
Guolin Ke's avatar
Guolin Ke committed
293
  * \return best_msg if met early_stopping
Guolin Ke's avatar
Guolin Ke committed
294
  */
Guolin Ke's avatar
Guolin Ke committed
295
  std::string OutputMetric(int iter);
wxchan's avatar
wxchan committed
296
297
298
  /*!
  * \brief Calculate feature importances
  */
wxchan's avatar
wxchan committed
299
  std::vector<std::pair<size_t, std::string>> FeatureImportance() const;
300
301
  /*! \brief current iteration */
  int iter_;
Guolin Ke's avatar
Guolin Ke committed
302
303
304
  /*! \brief Pointer to training data */
  const Dataset* train_data_;
  /*! \brief Config of gbdt */
Guolin Ke's avatar
Guolin Ke committed
305
  std::unique_ptr<BoostingConfig> gbdt_config_;
Hui Xue's avatar
Hui Xue committed
306
  /*! \brief Tree learner, will use this class to learn trees */
307
  std::unique_ptr<TreeLearner> tree_learner_;
Guolin Ke's avatar
Guolin Ke committed
308
  /*! \brief Objective function */
309
  const ObjectiveFunction* objective_function_;
Hui Xue's avatar
Hui Xue committed
310
  /*! \brief Store and update training data's score */
Guolin Ke's avatar
Guolin Ke committed
311
  std::unique_ptr<ScoreUpdater> train_score_updater_;
Guolin Ke's avatar
Guolin Ke committed
312
313
314
  /*! \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
315
  std::vector<std::unique_ptr<ScoreUpdater>> valid_score_updater_;
Guolin Ke's avatar
Guolin Ke committed
316
317
  /*! \brief Metric for validation data */
  std::vector<std::vector<const Metric*>> valid_metrics_;
wxchan's avatar
wxchan committed
318
319
  /*! \brief Number of rounds for early stopping */
  int early_stopping_round_;
Guolin Ke's avatar
Guolin Ke committed
320
  /*! \brief Best iteration(s) for early stopping */
wxchan's avatar
wxchan committed
321
  std::vector<std::vector<int>> best_iter_;
Guolin Ke's avatar
Guolin Ke committed
322
  /*! \brief Best score(s) for early stopping */
323
  std::vector<std::vector<double>> best_score_;
Guolin Ke's avatar
Guolin Ke committed
324
325
  /*! \brief output message of best iteration */
  std::vector<std::vector<std::string>> best_msg_;
Guolin Ke's avatar
Guolin Ke committed
326
  /*! \brief Trained models(trees) */
Guolin Ke's avatar
Guolin Ke committed
327
  std::vector<std::unique_ptr<Tree>> models_;
Guolin Ke's avatar
Guolin Ke committed
328
329
330
  /*! \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
331
  std::vector<score_t> gradients_;
Guolin Ke's avatar
Guolin Ke committed
332
  /*! \brief Secend order derivative of training data */
Guolin Ke's avatar
Guolin Ke committed
333
  std::vector<score_t> hessians_;
Guolin Ke's avatar
Guolin Ke committed
334
  /*! \brief Store the indices of in-bag data */
Guolin Ke's avatar
Guolin Ke committed
335
  std::vector<data_size_t> bag_data_indices_;
Guolin Ke's avatar
Guolin Ke committed
336
337
  /*! \brief Number of in-bag data */
  data_size_t bag_data_cnt_;
338
339
  /*! \brief Store the indices of in-bag data */
  std::vector<data_size_t> tmp_indices_;
wxchan's avatar
wxchan committed
340
  /*! \brief Number of training data */
Guolin Ke's avatar
Guolin Ke committed
341
  data_size_t num_data_;
342
343
344
  /*! \brief Number of trees per iterations */
  int num_tree_per_iteration_;
  /*! \brief Number of class */
345
  int num_class_;
Guolin Ke's avatar
Guolin Ke committed
346
347
  /*! \brief Index of label column */
  data_size_t label_idx_;
348
  /*! \brief number of used model */
wxchan's avatar
wxchan committed
349
  int num_iteration_for_pred_;
Guolin Ke's avatar
Guolin Ke committed
350
351
  /*! \brief Shrinkage rate for one iteration */
  double shrinkage_rate_;
wxchan's avatar
wxchan committed
352
353
  /*! \brief Number of loaded initial models */
  int num_init_iteration_;
Guolin Ke's avatar
Guolin Ke committed
354
355
  /*! \brief Feature names */
  std::vector<std::string> feature_names_;
Guolin Ke's avatar
Guolin Ke committed
356
  std::vector<std::string> feature_infos_;
357
358
359
360
361
362
363
364
365
366
367
368
  /*! \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
369
370
  std::unique_ptr<Dataset> tmp_subset_;
  bool is_use_subset_;
371
  bool boost_from_average_;
372
373
  std::vector<bool> class_need_train_;
  std::vector<double> class_default_output_;
374
  bool is_constant_hessian_;
375
  std::unique_ptr<ObjectiveFunction> loaded_objective_;
Guolin Ke's avatar
Guolin Ke committed
376
377
378
};

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