dart.hpp 6.68 KB
Newer Older
Guolin Ke's avatar
Guolin Ke committed
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
#ifndef LIGHTGBM_BOOSTING_DART_H_
#define LIGHTGBM_BOOSTING_DART_H_

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

#include <cstdio>
#include <vector>
#include <string>
#include <fstream>

namespace LightGBM {
/*!
* \brief DART algorithm implementation. including Training, prediction, bagging.
*/
class DART: public GBDT {
public:
  /*!
  * \brief Constructor
  */
22
  DART() : GBDT() { }
Guolin Ke's avatar
Guolin Ke committed
23
24
25
26
27
28
29
30
  /*!
  * \brief Destructor
  */
  ~DART() { }
  /*!
  * \brief Initialization logic
  * \param config Config for boosting
  * \param train_data Training data
31
  * \param objective_function Training objective function
Guolin Ke's avatar
Guolin Ke committed
32
33
34
  * \param training_metrics Training metrics
  * \param output_model_filename Filename of output model
  */
35
36
37
  void Init(const BoostingConfig* config, const Dataset* train_data, const ObjectiveFunction* objective_function,
            const std::vector<const Metric*>& training_metrics) override {
    GBDT::Init(config, train_data, objective_function, training_metrics);
Guolin Ke's avatar
Guolin Ke committed
38
    random_for_drop_ = Random(gbdt_config_->drop_seed);
39
    sum_weight_ = 0.0f;
Guolin Ke's avatar
Guolin Ke committed
40
  }
Guolin Ke's avatar
Guolin Ke committed
41

Guolin Ke's avatar
Guolin Ke committed
42
43
44
45
46
47
  void ResetConfig(const BoostingConfig* config) override {
    GBDT::ResetConfig(config);
    random_for_drop_ = Random(gbdt_config_->drop_seed);
    sum_weight_ = 0.0f;
  }

Guolin Ke's avatar
Guolin Ke committed
48
49
50
  /*!
  * \brief one training iteration
  */
Guolin Ke's avatar
Guolin Ke committed
51
  bool TrainOneIter(const score_t* gradient, const score_t* hessian) override {
Guolin Ke's avatar
Guolin Ke committed
52
    is_update_score_cur_iter_ = false;
Guolin Ke's avatar
Guolin Ke committed
53
54
55
56
    bool ret = GBDT::TrainOneIter(gradient, hessian);
    if (ret) {
      return ret;
    }
Guolin Ke's avatar
Guolin Ke committed
57
58
    // normalize
    Normalize();
59
60
61
62
    if (!gbdt_config_->uniform_drop) {
      tree_weight_.push_back(shrinkage_rate_);
      sum_weight_ += shrinkage_rate_;
    }
Guolin Ke's avatar
Guolin Ke committed
63
    return false;
Guolin Ke's avatar
Guolin Ke committed
64
  }
Guolin Ke's avatar
Guolin Ke committed
65

Guolin Ke's avatar
Guolin Ke committed
66
67
68
69
70
  /*!
  * \brief Get current training score
  * \param out_len length of returned score
  * \return training score
  */
71
  const double* GetTrainingScore(int64_t* out_len) override {
Guolin Ke's avatar
Guolin Ke committed
72
73
74
75
76
    if (!is_update_score_cur_iter_) {
      // only drop one time in one iteration
      DroppingTrees();
      is_update_score_cur_iter_ = true;
    }
77
    *out_len = static_cast<int64_t>(train_score_updater_->num_data()) * num_class_;
Guolin Ke's avatar
Guolin Ke committed
78
79
    return train_score_updater_->score();
  }
Guolin Ke's avatar
Guolin Ke committed
80

Guolin Ke's avatar
Guolin Ke committed
81
82
83
84
85
86
private:
  /*!
  * \brief drop trees based on drop_rate
  */
  void DroppingTrees() {
    drop_index_.clear();
Guolin Ke's avatar
Guolin Ke committed
87
    bool is_skip = random_for_drop_.NextFloat() < gbdt_config_->skip_drop;
zhangyafeikimi's avatar
zhangyafeikimi committed
88
    // select dropping tree indices based on drop_rate and tree weights
89
90
91
92
93
94
95
96
    if (!is_skip) {
      double drop_rate = gbdt_config_->drop_rate;
      if (!gbdt_config_->uniform_drop) {
        double inv_average_weight = static_cast<double>(tree_weight_.size()) / sum_weight_;
        if (gbdt_config_->max_drop > 0) {
          drop_rate = std::min(drop_rate, gbdt_config_->max_drop * inv_average_weight / sum_weight_);
        }
        for (int i = 0; i < iter_; ++i) {
Guolin Ke's avatar
Guolin Ke committed
97
          if (random_for_drop_.NextFloat() < drop_rate * tree_weight_[i] * inv_average_weight) {
98
99
100
101
102
103
104
105
            drop_index_.push_back(i);
          }
        }
      } else {
        if (gbdt_config_->max_drop > 0) {
          drop_rate = std::min(drop_rate, gbdt_config_->max_drop / static_cast<double>(iter_));
        }
        for (int i = 0; i < iter_; ++i) {
Guolin Ke's avatar
Guolin Ke committed
106
          if (random_for_drop_.NextFloat() < drop_rate) {
107
108
            drop_index_.push_back(i);
          }
Guolin Ke's avatar
Guolin Ke committed
109
110
111
112
113
        }
      }
    }
    // drop trees
    for (auto i : drop_index_) {
114
115
      for (int cur_tree_id = 0; cur_tree_id < num_tree_per_iteration_; ++cur_tree_id) {
        auto curr_tree = i * num_tree_per_iteration_ + cur_tree_id;
Guolin Ke's avatar
Guolin Ke committed
116
        models_[curr_tree]->Shrinkage(-1.0);
117
        train_score_updater_->AddScore(models_[curr_tree].get(), cur_tree_id);
Guolin Ke's avatar
Guolin Ke committed
118
119
      }
    }
120
121
122
123
124
125
126
127
128
    if (!gbdt_config_->xgboost_dart_mode) {
      shrinkage_rate_ = gbdt_config_->learning_rate / (1.0f + static_cast<double>(drop_index_.size()));
    } else {
      if (drop_index_.empty()) {
        shrinkage_rate_ = gbdt_config_->learning_rate;
      } else {
        shrinkage_rate_ = gbdt_config_->learning_rate / (gbdt_config_->learning_rate + static_cast<double>(drop_index_.size()));
      }
    }
Guolin Ke's avatar
Guolin Ke committed
129
130
131
  }
  /*!
  * \brief normalize dropped trees
132
  * NOTE: num_drop_tree(k), learning_rate(lr), shrinkage_rate_ = lr / (k + 1)
wxchan's avatar
wxchan committed
133
  *       step 1: shrink tree to -1 -> drop tree
134
  *       step 2: shrink tree to k / (k + 1) - 1 from -1, by 1/(k+1)
wxchan's avatar
wxchan committed
135
  *               -> normalize for valid data
136
  *       step 3: shrink tree to k / (k + 1) from k / (k + 1) - 1, by -k
wxchan's avatar
wxchan committed
137
  *               -> normalize for train data
138
  *       end with tree weight = (k / (k + 1)) * old_weight
Guolin Ke's avatar
Guolin Ke committed
139
140
141
  */
  void Normalize() {
    double k = static_cast<double>(drop_index_.size());
142
143
    if (!gbdt_config_->xgboost_dart_mode) {
      for (auto i : drop_index_) {
144
145
        for (int cur_tree_id = 0; cur_tree_id < num_tree_per_iteration_; ++cur_tree_id) {
          auto curr_tree = i * num_tree_per_iteration_ + cur_tree_id;
146
147
148
          // update validation score
          models_[curr_tree]->Shrinkage(1.0f / (k + 1.0f));
          for (auto& score_updater : valid_score_updater_) {
149
            score_updater->AddScore(models_[curr_tree].get(), cur_tree_id);
150
151
152
          }
          // update training score
          models_[curr_tree]->Shrinkage(-k);
153
          train_score_updater_->AddScore(models_[curr_tree].get(), cur_tree_id);
154
155
156
157
158
159
160
161
        }
        if (!gbdt_config_->uniform_drop) {
          sum_weight_ -= tree_weight_[i] * (1.0f / (k + 1.0f));
          tree_weight_[i] *= (k / (k + 1.0f));
        }
      }
    } else {
      for (auto i : drop_index_) {
162
163
        for (int cur_tree_id = 0; cur_tree_id < num_tree_per_iteration_; ++cur_tree_id) {
          auto curr_tree = i * num_tree_per_iteration_ + cur_tree_id;
164
165
166
          // update validation score
          models_[curr_tree]->Shrinkage(shrinkage_rate_);
          for (auto& score_updater : valid_score_updater_) {
167
            score_updater->AddScore(models_[curr_tree].get(), cur_tree_id);
168
169
170
          }
          // update training score
          models_[curr_tree]->Shrinkage(-k / gbdt_config_->learning_rate);
171
          train_score_updater_->AddScore(models_[curr_tree].get(), cur_tree_id);
172
173
174
175
        }
        if (!gbdt_config_->uniform_drop) {
          sum_weight_ -= tree_weight_[i] * (1.0f / (k + gbdt_config_->learning_rate));;
          tree_weight_[i] *= (k / (k + gbdt_config_->learning_rate));
Guolin Ke's avatar
Guolin Ke committed
176
177
178
179
        }
      }
    }
  }
180
181
182
183
  /*! \brief The weights of all trees, used to choose drop trees */
  std::vector<double> tree_weight_;
  /*! \brief sum weights of all trees */
  double sum_weight_;
zhangyafeikimi's avatar
zhangyafeikimi committed
184
  /*! \brief The indices of dropping trees */
185
  std::vector<int> drop_index_;
Guolin Ke's avatar
Guolin Ke committed
186
187
  /*! \brief Random generator, used to select dropping trees */
  Random random_for_drop_;
Guolin Ke's avatar
Guolin Ke committed
188
189
  /*! \brief Flag that the score is update on current iter or not*/
  bool is_update_score_cur_iter_;
Guolin Ke's avatar
Guolin Ke committed
190
191
192
193
};

}  // namespace LightGBM
#endif   // LightGBM_BOOSTING_DART_H_