feature_histogram.hpp 26.6 KB
Newer Older
Guolin Ke's avatar
Guolin Ke committed
1
2
3
4
#ifndef LIGHTGBM_TREELEARNER_FEATURE_HISTOGRAM_HPP_
#define LIGHTGBM_TREELEARNER_FEATURE_HISTOGRAM_HPP_

#include "split_info.hpp"
Guolin Ke's avatar
Guolin Ke committed
5
6
7

#include <LightGBM/utils/array_args.h>
#include <LightGBM/dataset.h>
Guolin Ke's avatar
Guolin Ke committed
8
9
10

#include <cstring>

Guolin Ke's avatar
Guolin Ke committed
11
namespace LightGBM
Guolin Ke's avatar
Guolin Ke committed
12
{
Guolin Ke's avatar
Guolin Ke committed
13

Guolin Ke's avatar
Guolin Ke committed
14
15
16
class FeatureMetainfo {
public:
  int num_bin;
Guolin Ke's avatar
Guolin Ke committed
17
  MissingType missing_type;
18
  int8_t bias = 0;
Guolin Ke's avatar
Guolin Ke committed
19
  uint32_t default_bin;
Guolin Ke's avatar
Guolin Ke committed
20
  int8_t monotone_type;
Guolin Ke's avatar
Guolin Ke committed
21
22
23
  /*! \brief pointer of tree config */
  const TreeConfig* tree_config;
};
Guolin Ke's avatar
Guolin Ke committed
24
25
26
27
28
/*!
* \brief FeatureHistogram is used to construct and store a histogram for a feature.
*/
class FeatureHistogram {
public:
Guolin Ke's avatar
Guolin Ke committed
29
  FeatureHistogram() {
Guolin Ke's avatar
Guolin Ke committed
30
    data_ = nullptr;
Guolin Ke's avatar
Guolin Ke committed
31
  }
Guolin Ke's avatar
Guolin Ke committed
32

Guolin Ke's avatar
Guolin Ke committed
33
34
35
  ~FeatureHistogram() {
  }

Guolin Ke's avatar
Guolin Ke committed
36
37
38
39
40
  /*! \brief Disable copy */
  FeatureHistogram& operator=(const FeatureHistogram&) = delete;
  /*! \brief Disable copy */
  FeatureHistogram(const FeatureHistogram&) = delete;

Guolin Ke's avatar
Guolin Ke committed
41
42
43
44
45
  /*!
  * \brief Init the feature histogram
  * \param feature the feature data for this histogram
  * \param min_num_data_one_leaf minimal number of data in one leaf
  */
46
  void Init(HistogramBinEntry* data, const FeatureMetainfo* meta, BinType bin_type) {
Guolin Ke's avatar
Guolin Ke committed
47
48
    meta_ = meta;
    data_ = data;
49
50
    if (bin_type == BinType::NumericalBin) {
      find_best_threshold_fun_ = std::bind(&FeatureHistogram::FindBestThresholdNumerical, this, std::placeholders::_1
Guolin Ke's avatar
Guolin Ke committed
51
                                           , std::placeholders::_2, std::placeholders::_3, std::placeholders::_4, std::placeholders::_5, std::placeholders::_6);
52
53
    } else {
      find_best_threshold_fun_ = std::bind(&FeatureHistogram::FindBestThresholdCategorical, this, std::placeholders::_1
Guolin Ke's avatar
Guolin Ke committed
54
                                           , std::placeholders::_2, std::placeholders::_3, std::placeholders::_4, std::placeholders::_5, std::placeholders::_6);
55
    }
Guolin Ke's avatar
Guolin Ke committed
56
57
  }

Guolin Ke's avatar
Guolin Ke committed
58
59
  HistogramBinEntry* RawData() {
    return data_;
Guolin Ke's avatar
Guolin Ke committed
60
61
62
63
64
65
  }
  /*!
  * \brief Subtract current histograms with other
  * \param other The histogram that want to subtract
  */
  void Subtract(const FeatureHistogram& other) {
Guolin Ke's avatar
Guolin Ke committed
66
    for (int i = 0; i < meta_->num_bin - meta_->bias; ++i) {
Guolin Ke's avatar
Guolin Ke committed
67
68
69
70
71
      data_[i].cnt -= other.data_[i].cnt;
      data_[i].sum_gradients -= other.data_[i].sum_gradients;
      data_[i].sum_hessians -= other.data_[i].sum_hessians;
    }
  }
72

Guolin Ke's avatar
Guolin Ke committed
73
  void FindBestThreshold(double sum_gradient, double sum_hessian, data_size_t num_data, double min_constraint, double max_constraint,
Guolin Ke's avatar
Guolin Ke committed
74
                         SplitInfo* output) {
Guolin Ke's avatar
Guolin Ke committed
75
    output->default_left = true;
Guolin Ke's avatar
Guolin Ke committed
76
    output->gain = kMinScore;
Guolin Ke's avatar
Guolin Ke committed
77
    find_best_threshold_fun_(sum_gradient, sum_hessian + 2 * kEpsilon, num_data, min_constraint, max_constraint, output);
78
79
  }

Guolin Ke's avatar
Guolin Ke committed
80
  void FindBestThresholdNumerical(double sum_gradient, double sum_hessian, data_size_t num_data, double min_constraint, double max_constraint,
Guolin Ke's avatar
Guolin Ke committed
81
                                  SplitInfo* output) {
Guolin Ke's avatar
Guolin Ke committed
82
83

    is_splittable_ = false;
Guolin Ke's avatar
Guolin Ke committed
84
85
    double gain_shift = GetLeafSplitGain(sum_gradient, sum_hessian,
                                         meta_->tree_config->lambda_l1, meta_->tree_config->lambda_l2);
Guolin Ke's avatar
Guolin Ke committed
86
    double min_gain_shift = gain_shift + meta_->tree_config->min_gain_to_split;
Guolin Ke's avatar
Guolin Ke committed
87
88
    if (meta_->num_bin > 2 && meta_->missing_type != MissingType::None) {
      if (meta_->missing_type == MissingType::Zero) {
Guolin Ke's avatar
Guolin Ke committed
89
90
        FindBestThresholdSequence(sum_gradient, sum_hessian, num_data, min_constraint, max_constraint, min_gain_shift, output, -1, true, false);
        FindBestThresholdSequence(sum_gradient, sum_hessian, num_data, min_constraint, max_constraint, min_gain_shift, output, 1, true, false);
Guolin Ke's avatar
Guolin Ke committed
91
      } else {
Guolin Ke's avatar
Guolin Ke committed
92
93
        FindBestThresholdSequence(sum_gradient, sum_hessian, num_data, min_constraint, max_constraint, min_gain_shift, output, -1, false, true);
        FindBestThresholdSequence(sum_gradient, sum_hessian, num_data, min_constraint, max_constraint, min_gain_shift, output, 1, false, true);
Guolin Ke's avatar
Guolin Ke committed
94
      }
95
    } else {
Guolin Ke's avatar
Guolin Ke committed
96
      FindBestThresholdSequence(sum_gradient, sum_hessian, num_data, min_constraint, max_constraint, min_gain_shift, output, -1, false, false);
Guolin Ke's avatar
Guolin Ke committed
97
98
99
100
      // fix the direction error when only have 2 bins
      if (meta_->missing_type == MissingType::NaN) {
        output->default_left = false;
      }
Guolin Ke's avatar
Guolin Ke committed
101
    }
Guolin Ke's avatar
Guolin Ke committed
102
    output->gain -= min_gain_shift;
Guolin Ke's avatar
Guolin Ke committed
103
104
105
    output->monotone_type = meta_->monotone_type;
    output->min_constraint = min_constraint;
    output->max_constraint = max_constraint;
Guolin Ke's avatar
Guolin Ke committed
106
  }
107

Guolin Ke's avatar
Guolin Ke committed
108
  void FindBestThresholdCategorical(double sum_gradient, double sum_hessian, data_size_t num_data, double min_constraint, double max_constraint,
Guolin Ke's avatar
Guolin Ke committed
109
                                    SplitInfo* output) {
Guolin Ke's avatar
Guolin Ke committed
110
    output->default_left = false;
111
    double best_gain = kMinScore;
112
    data_size_t best_left_count = 0;
ChenZhiyong's avatar
ChenZhiyong committed
113
114
115
    double best_sum_left_gradient = 0;
    double best_sum_left_hessian = 0;
    double gain_shift = GetLeafSplitGain(sum_gradient, sum_hessian, meta_->tree_config->lambda_l1, meta_->tree_config->lambda_l2);
Guolin Ke's avatar
Guolin Ke committed
116
    
117
    double min_gain_shift = gain_shift + meta_->tree_config->min_gain_to_split;
ChenZhiyong's avatar
ChenZhiyong committed
118
    bool is_full_categorical = meta_->missing_type == MissingType::None;
119
    int used_bin = meta_->num_bin - 1 + is_full_categorical;
ChenZhiyong's avatar
ChenZhiyong committed
120

Guolin Ke's avatar
Guolin Ke committed
121
    std::vector<int> sorted_idx;
122
123
124
125
    double l2 = meta_->tree_config->lambda_l2;
    bool use_onehot = meta_->num_bin <= meta_->tree_config->max_cat_to_onehot;
    int best_threshold = -1;
    int best_dir = 1;
Guolin Ke's avatar
Guolin Ke committed
126

127
128
129
130
131
132
133
134
    if (use_onehot) {
      for (int t = 0; t < used_bin; ++t) {
        // if data not enough, or sum hessian too small
        if (data_[t].cnt < meta_->tree_config->min_data_in_leaf
            || data_[t].sum_hessians < meta_->tree_config->min_sum_hessian_in_leaf) continue;
        data_size_t other_count = num_data - data_[t].cnt;
        // if data not enough
        if (other_count < meta_->tree_config->min_data_in_leaf) continue;
ChenZhiyong's avatar
ChenZhiyong committed
135

136
137
138
        double sum_other_hessian = sum_hessian - data_[t].sum_hessians - kEpsilon;
        // if sum hessian too small
        if (sum_other_hessian < meta_->tree_config->min_sum_hessian_in_leaf) continue;
ChenZhiyong's avatar
ChenZhiyong committed
139

140
141
        double sum_other_gradient = sum_gradient - data_[t].sum_gradients;
        // current split gain
Guolin Ke's avatar
Guolin Ke committed
142
143
144
        double current_gain = GetSplitGains(sum_other_gradient, sum_other_hessian, data_[t].sum_gradients, data_[t].sum_hessians + kEpsilon,
                                            meta_->tree_config->lambda_l1, l2,
                                            min_constraint, max_constraint, 0);
145
        // gain with split is worse than without split
ChenZhiyong's avatar
ChenZhiyong committed
146
        if (current_gain <= min_gain_shift) continue;
147
148

        // mark to is splittable
ChenZhiyong's avatar
ChenZhiyong committed
149
        is_splittable_ = true;
150
        // better split point
ChenZhiyong's avatar
ChenZhiyong committed
151
        if (current_gain > best_gain) {
152
153
154
155
          best_threshold = t;
          best_sum_left_gradient = data_[t].sum_gradients;
          best_sum_left_hessian = data_[t].sum_hessians + kEpsilon;
          best_left_count = data_[t].cnt;
ChenZhiyong's avatar
ChenZhiyong committed
156
          best_gain = current_gain;
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
        }
      }
    } else {
      for (int i = 0; i < used_bin; ++i) {
        if (data_[i].cnt >= meta_->tree_config->cat_smooth) {
          sorted_idx.push_back(i);
        }
      }
      used_bin = static_cast<int>(sorted_idx.size());

      l2 += meta_->tree_config->cat_l2;

      auto ctr_fun = [this](double sum_grad, double sum_hess) {
        return (sum_grad) / (sum_hess + meta_->tree_config->cat_smooth);
      };
      std::sort(sorted_idx.begin(), sorted_idx.end(),
                [this, &ctr_fun](int i, int j) {
        return ctr_fun(data_[i].sum_gradients, data_[i].sum_hessians) < ctr_fun(data_[j].sum_gradients, data_[j].sum_hessians);
      });

      std::vector<int> find_direction(1, 1);
      std::vector<int> start_position(1, 0);
      find_direction.push_back(-1);
      start_position.push_back(used_bin - 1);
      const int max_num_cat = std::min(meta_->tree_config->max_cat_threshold, (used_bin + 1) / 2);

      is_splittable_ = false;
      for (size_t out_i = 0; out_i < find_direction.size(); ++out_i) {
        auto dir = find_direction[out_i];
        auto start_pos = start_position[out_i];
        data_size_t min_data_per_group = meta_->tree_config->min_data_per_group;
        data_size_t cnt_cur_group = 0;
        double sum_left_gradient = 0.0f;
        double sum_left_hessian = kEpsilon;
        data_size_t left_count = 0;
        for (int i = 0; i < used_bin && i < max_num_cat; ++i) {
          auto t = sorted_idx[start_pos];
          start_pos += dir;

          sum_left_gradient += data_[t].sum_gradients;
          sum_left_hessian += data_[t].sum_hessians;
          left_count += data_[t].cnt;
          cnt_cur_group += data_[t].cnt;

          if (left_count < meta_->tree_config->min_data_in_leaf
              || sum_left_hessian < meta_->tree_config->min_sum_hessian_in_leaf) continue;
          data_size_t right_count = num_data - left_count;
          if (right_count < meta_->tree_config->min_data_in_leaf || right_count < min_data_per_group) break;

          double sum_right_hessian = sum_hessian - sum_left_hessian;
          if (sum_right_hessian < meta_->tree_config->min_sum_hessian_in_leaf) break;

          if (cnt_cur_group < min_data_per_group) continue;

          cnt_cur_group = 0;

          double sum_right_gradient = sum_gradient - sum_left_gradient;
Guolin Ke's avatar
Guolin Ke committed
214
215
216
          double current_gain = GetSplitGains(sum_left_gradient, sum_left_hessian, sum_right_gradient, sum_right_hessian,
                                              meta_->tree_config->lambda_l1, l2,
                                              min_constraint, max_constraint, 0);
217
218
219
220
221
222
223
224
225
226
          if (current_gain <= min_gain_shift) continue;
          is_splittable_ = true;
          if (current_gain > best_gain) {
            best_left_count = left_count;
            best_sum_left_gradient = sum_left_gradient;
            best_sum_left_hessian = sum_left_hessian;
            best_threshold = i;
            best_gain = current_gain;
            best_dir = dir;
          }
ChenZhiyong's avatar
ChenZhiyong committed
227
        }
228
229
      }
    }
230

231
    if (is_splittable_) {
Guolin Ke's avatar
Guolin Ke committed
232
      output->left_output = CalculateSplittedLeafOutput(best_sum_left_gradient, best_sum_left_hessian,
Guolin Ke's avatar
Guolin Ke committed
233
                                                        meta_->tree_config->lambda_l1, l2, min_constraint, max_constraint);
234
235
236
237
      output->left_count = best_left_count;
      output->left_sum_gradient = best_sum_left_gradient;
      output->left_sum_hessian = best_sum_left_hessian - kEpsilon;
      output->right_output = CalculateSplittedLeafOutput(sum_gradient - best_sum_left_gradient,
Guolin Ke's avatar
Guolin Ke committed
238
                                                         sum_hessian - best_sum_left_hessian,
Guolin Ke's avatar
Guolin Ke committed
239
                                                         meta_->tree_config->lambda_l1, l2, min_constraint, max_constraint);
240
241
242
      output->right_count = num_data - best_left_count;
      output->right_sum_gradient = sum_gradient - best_sum_left_gradient;
      output->right_sum_hessian = sum_hessian - best_sum_left_hessian - kEpsilon;
Guolin Ke's avatar
Guolin Ke committed
243
      output->gain = best_gain - min_gain_shift;
244
245
246
      if (use_onehot) {
        output->num_cat_threshold = 1;
        output->cat_threshold = std::vector<uint32_t>(1, static_cast<uint32_t>(best_threshold));
ChenZhiyong's avatar
ChenZhiyong committed
247
      } else {
248
249
250
251
252
253
254
255
256
257
258
259
        output->num_cat_threshold = best_threshold + 1;
        output->cat_threshold = std::vector<uint32_t>(output->num_cat_threshold);
        if (best_dir == 1) {
          for (int i = 0; i < output->num_cat_threshold; ++i) {
            auto t = sorted_idx[i];
            output->cat_threshold[i] = t;
          }
        } else {
          for (int i = 0; i < output->num_cat_threshold; ++i) {
            auto t = sorted_idx[used_bin - 1 - i];
            output->cat_threshold[i] = t;
          }
ChenZhiyong's avatar
ChenZhiyong committed
260
261
        }
      }
Guolin Ke's avatar
Guolin Ke committed
262
263
264
      output->monotone_type = 0;
      output->min_constraint = min_constraint;
      output->max_constraint = max_constraint;
265
    }
266
267
  }

Guolin Ke's avatar
Guolin Ke committed
268
269
270
271
  /*!
  * \brief Binary size of this histogram
  */
  int SizeOfHistgram() const {
Guolin Ke's avatar
Guolin Ke committed
272
    return (meta_->num_bin - meta_->bias) * sizeof(HistogramBinEntry);
Guolin Ke's avatar
Guolin Ke committed
273
274
275
276
277
  }

  /*!
  * \brief Restore histogram from memory
  */
Guolin Ke's avatar
Guolin Ke committed
278
279
  void FromMemory(char* memory_data) {
    std::memcpy(data_, memory_data, (meta_->num_bin - meta_->bias) * sizeof(HistogramBinEntry));
Guolin Ke's avatar
Guolin Ke committed
280
281
282
283
284
285
286
287
288
289
290
291
292
  }

  /*!
  * \brief True if this histogram can be splitted
  */
  bool is_splittable() { return is_splittable_; }

  /*!
  * \brief Set splittable to this histogram
  */
  void set_is_splittable(bool val) { is_splittable_ = val; }

  /*!
Guolin Ke's avatar
Guolin Ke committed
293
  * \brief Calculate the output of a leaf based on regularized sum_gradients and sum_hessians
Guolin Ke's avatar
Guolin Ke committed
294
295
  * \param sum_gradients
  * \param sum_hessians
Guolin Ke's avatar
Guolin Ke committed
296
  * \return leaf output
Guolin Ke's avatar
Guolin Ke committed
297
  */
Guolin Ke's avatar
Guolin Ke committed
298
299
300
301
302
303
  static double CalculateSplittedLeafOutput(double sum_gradients, double sum_hessians, double l1, double l2) {
    const double reg_abs_sum_gradients = std::max(0.0, std::fabs(sum_gradients) - l1);
    return -(Common::Sign(sum_gradients) * reg_abs_sum_gradients) / (sum_hessians + l2);
  }

private:
Guolin Ke's avatar
Guolin Ke committed
304

Guolin Ke's avatar
Guolin Ke committed
305
306
307
308
309
310
311
312
313
314
315
316
317
318
319
320
321
  static double GetSplitGains(double sum_left_gradients, double sum_left_hessians,
                              double sum_right_gradients, double sum_right_hessians,
                              double l1, double l2,
                              double min_constraint, double max_constraint, int8_t monotone_constraint) {
    double left_output = CalculateSplittedLeafOutput(sum_left_gradients, sum_left_hessians, l1, l2, min_constraint, max_constraint);
    double right_output = CalculateSplittedLeafOutput(sum_right_gradients, sum_right_hessians, l1, l2, min_constraint, max_constraint);
    if (((monotone_constraint > 0) && (left_output > right_output)) ||
      ((monotone_constraint < 0) && (left_output < right_output))) {
      return 0;
    }
    return GetLeafSplitGainGivenOutput(sum_left_gradients, sum_left_hessians, l1, l2, left_output)
      + GetLeafSplitGainGivenOutput(sum_right_gradients, sum_right_hessians, l1, l2, right_output);
  }

  static double ThresholdL1(double s, double l1) {
    const double reg_s = std::max(0.0, std::fabs(s) - l1);
    return Common::Sign(s) * reg_s;
Guolin Ke's avatar
Guolin Ke committed
322
323
324
  }

  /*!
325
  * \brief Calculate the output of a leaf based on regularized sum_gradients and sum_hessians
Guolin Ke's avatar
Guolin Ke committed
326
327
328
329
  * \param sum_gradients
  * \param sum_hessians
  * \return leaf output
  */
Guolin Ke's avatar
Guolin Ke committed
330
331
332
333
334
335
336
337
338
  static double CalculateSplittedLeafOutput(double sum_gradients, double sum_hessians, double l1, double l2, 
                                            double min_constraint, double max_constraint) {
    double ret = -ThresholdL1(sum_gradients, l1) / (sum_hessians + l2);
    if (ret < min_constraint) {
      ret = min_constraint;
    } else if (ret > max_constraint) {
      ret = max_constraint;
    }
    return ret;
Guolin Ke's avatar
Guolin Ke committed
339
  }
Guolin Ke's avatar
Guolin Ke committed
340

Guolin Ke's avatar
Guolin Ke committed
341
342
343
344
345
346
347
348
349
350
351
352
353
354
355
356
357
  /*!
  * \brief Calculate the split gain based on regularized sum_gradients and sum_hessians
  * \param sum_gradients
  * \param sum_hessians
  * \return split gain
  */
  static double GetLeafSplitGain(double sum_gradients, double sum_hessians, double l1, double l2) {
    double abs_sum_gradients = std::fabs(sum_gradients);
    double reg_abs_sum_gradients = std::max(0.0, abs_sum_gradients - l1);
    return (reg_abs_sum_gradients * reg_abs_sum_gradients)
      / (sum_hessians + l2);
  }

  static double GetLeafSplitGainGivenOutput(double sum_gradients, double sum_hessians, double l1, double l2, double output) {
    const double sg_l1 = ThresholdL1(sum_gradients, l1);
    return -(2.0 * sg_l1 * output + (sum_hessians + l2) * output * output);
  }
Guolin Ke's avatar
Guolin Ke committed
358

Guolin Ke's avatar
Guolin Ke committed
359
360
  void FindBestThresholdSequence(double sum_gradient, double sum_hessian, data_size_t num_data, double min_constraint, double max_constraint,
                                 double min_gain_shift, SplitInfo* output, int dir, bool skip_default_bin, bool use_na_as_missing) {
Guolin Ke's avatar
Guolin Ke committed
361

362
    const int8_t bias = meta_->bias;
Guolin Ke's avatar
Guolin Ke committed
363
364
365
366
367
368
369
370
371
372
373
374
375

    double best_sum_left_gradient = NAN;
    double best_sum_left_hessian = NAN;
    double best_gain = kMinScore;
    data_size_t best_left_count = 0;
    uint32_t best_threshold = static_cast<uint32_t>(meta_->num_bin);

    if (dir == -1) {

      double sum_right_gradient = 0.0f;
      double sum_right_hessian = kEpsilon;
      data_size_t right_count = 0;

Guolin Ke's avatar
Guolin Ke committed
376
      int t = meta_->num_bin - 1 - bias - use_na_as_missing;
Guolin Ke's avatar
Guolin Ke committed
377
378
379
380
381
382
383
384
385
386
387
388
389
390
391
392
393
394
395
396
397
398
399
400
      const int t_end = 1 - bias;

      // from right to left, and we don't need data in bin0
      for (; t >= t_end; --t) {

        // need to skip default bin
        if (skip_default_bin && (t + bias) == static_cast<int>(meta_->default_bin)) { continue; }

        sum_right_gradient += data_[t].sum_gradients;
        sum_right_hessian += data_[t].sum_hessians;
        right_count += data_[t].cnt;
        // if data not enough, or sum hessian too small
        if (right_count < meta_->tree_config->min_data_in_leaf
            || sum_right_hessian < meta_->tree_config->min_sum_hessian_in_leaf) continue;
        data_size_t left_count = num_data - right_count;
        // if data not enough
        if (left_count < meta_->tree_config->min_data_in_leaf) break;

        double sum_left_hessian = sum_hessian - sum_right_hessian;
        // if sum hessian too small
        if (sum_left_hessian < meta_->tree_config->min_sum_hessian_in_leaf) break;

        double sum_left_gradient = sum_gradient - sum_right_gradient;
        // current split gain
Guolin Ke's avatar
Guolin Ke committed
401
402
403
        double current_gain = GetSplitGains(sum_left_gradient, sum_left_hessian, sum_right_gradient, sum_right_hessian,
                                            meta_->tree_config->lambda_l1, meta_->tree_config->lambda_l2,
                                            min_constraint, max_constraint, meta_->monotone_type);
Guolin Ke's avatar
Guolin Ke committed
404
405
406
407
408
409
410
411
412
413
414
415
416
417
418
        // gain with split is worse than without split
        if (current_gain <= min_gain_shift) continue;

        // mark to is splittable
        is_splittable_ = true;
        // better split point
        if (current_gain > best_gain) {
          best_left_count = left_count;
          best_sum_left_gradient = sum_left_gradient;
          best_sum_left_hessian = sum_left_hessian;
          // left is <= threshold, right is > threshold.  so this is t-1
          best_threshold = static_cast<uint32_t>(t - 1 + bias);
          best_gain = current_gain;
        }
      }
ChenZhiyong's avatar
ChenZhiyong committed
419
    } else {
Guolin Ke's avatar
Guolin Ke committed
420
421
422
423
424
425
426
      double sum_left_gradient = 0.0f;
      double sum_left_hessian = kEpsilon;
      data_size_t left_count = 0;

      int t = 0;
      const int t_end = meta_->num_bin - 2 - bias;

Guolin Ke's avatar
Guolin Ke committed
427
428
429
430
431
432
433
434
435
436
437
438
      if (use_na_as_missing && bias == 1) {
        sum_left_gradient = sum_gradient;
        sum_left_hessian = sum_hessian - kEpsilon;
        left_count = num_data;
        for (int i = 0; i < meta_->num_bin - bias; ++i) {
          sum_left_gradient -= data_[i].sum_gradients;
          sum_left_hessian -= data_[i].sum_hessians;
          left_count -= data_[i].cnt;
        }
        t = -1;
      }

Guolin Ke's avatar
Guolin Ke committed
439
440
441
442
      for (; t <= t_end; ++t) {

        // need to skip default bin
        if (skip_default_bin && (t + bias) == static_cast<int>(meta_->default_bin)) { continue; }
Guolin Ke's avatar
Guolin Ke committed
443
444
445
446
447
        if (t >= 0) {
          sum_left_gradient += data_[t].sum_gradients;
          sum_left_hessian += data_[t].sum_hessians;
          left_count += data_[t].cnt;
        }
Guolin Ke's avatar
Guolin Ke committed
448
449
450
451
452
453
454
455
456
457
458
459
460
        // if data not enough, or sum hessian too small
        if (left_count < meta_->tree_config->min_data_in_leaf
            || sum_left_hessian < meta_->tree_config->min_sum_hessian_in_leaf) continue;
        data_size_t right_count = num_data - left_count;
        // if data not enough
        if (right_count < meta_->tree_config->min_data_in_leaf) break;

        double sum_right_hessian = sum_hessian - sum_left_hessian;
        // if sum hessian too small
        if (sum_right_hessian < meta_->tree_config->min_sum_hessian_in_leaf) break;

        double sum_right_gradient = sum_gradient - sum_left_gradient;
        // current split gain
Guolin Ke's avatar
Guolin Ke committed
461
462
463
        double current_gain = GetSplitGains(sum_left_gradient, sum_left_hessian, sum_right_gradient, sum_right_hessian,
                                            meta_->tree_config->lambda_l1, meta_->tree_config->lambda_l2, 
                                            min_constraint, max_constraint, meta_->monotone_type);
Guolin Ke's avatar
Guolin Ke committed
464
465
466
467
468
469
470
471
472
473
474
475
476
477
478
479
480
481
482
483
        // gain with split is worse than without split
        if (current_gain <= min_gain_shift) continue;

        // mark to is splittable
        is_splittable_ = true;
        // better split point
        if (current_gain > best_gain) {
          best_left_count = left_count;
          best_sum_left_gradient = sum_left_gradient;
          best_sum_left_hessian = sum_left_hessian;
          best_threshold = static_cast<uint32_t>(t + bias);
          best_gain = current_gain;
        }
      }
    }

    if (is_splittable_ && best_gain > output->gain) {
      // update split information
      output->threshold = best_threshold;
      output->left_output = CalculateSplittedLeafOutput(best_sum_left_gradient, best_sum_left_hessian,
Guolin Ke's avatar
Guolin Ke committed
484
                                                        meta_->tree_config->lambda_l1, meta_->tree_config->lambda_l2, min_constraint, max_constraint);
Guolin Ke's avatar
Guolin Ke committed
485
486
487
488
489
      output->left_count = best_left_count;
      output->left_sum_gradient = best_sum_left_gradient;
      output->left_sum_hessian = best_sum_left_hessian - kEpsilon;
      output->right_output = CalculateSplittedLeafOutput(sum_gradient - best_sum_left_gradient,
                                                         sum_hessian - best_sum_left_hessian,
Guolin Ke's avatar
Guolin Ke committed
490
                                                         meta_->tree_config->lambda_l1, meta_->tree_config->lambda_l2, min_constraint, max_constraint);
Guolin Ke's avatar
Guolin Ke committed
491
492
493
494
      output->right_count = num_data - best_left_count;
      output->right_sum_gradient = sum_gradient - best_sum_left_gradient;
      output->right_sum_hessian = sum_hessian - best_sum_left_hessian - kEpsilon;
      output->gain = best_gain;
Guolin Ke's avatar
Guolin Ke committed
495
      output->default_left = dir == -1;
Guolin Ke's avatar
Guolin Ke committed
496
497
498
    }
  }

Guolin Ke's avatar
Guolin Ke committed
499
  const FeatureMetainfo* meta_;
Guolin Ke's avatar
Guolin Ke committed
500
  /*! \brief sum of gradient of each bin */
Guolin Ke's avatar
Guolin Ke committed
501
502
  HistogramBinEntry* data_;
  //std::vector<HistogramBinEntry> data_;
Guolin Ke's avatar
Guolin Ke committed
503
504
  /*! \brief False if this histogram cannot split */
  bool is_splittable_ = true;
505

Guolin Ke's avatar
Guolin Ke committed
506
  std::function<void(double, double, data_size_t, double, double, SplitInfo*)> find_best_threshold_fun_;
Guolin Ke's avatar
Guolin Ke committed
507
};
Guolin Ke's avatar
Guolin Ke committed
508
509
510
511
512
513
class HistogramPool {
public:
  /*!
  * \brief Constructor
  */
  HistogramPool() {
Guolin Ke's avatar
Guolin Ke committed
514
515
    cache_size_ = 0;
    total_size_ = 0;
Guolin Ke's avatar
Guolin Ke committed
516
517
518
519
520
521
522
523
524
525
526
  }
  /*!
  * \brief Destructor
  */
  ~HistogramPool() {
  }
  /*!
  * \brief Reset pool size
  * \param cache_size Max cache size
  * \param total_size Total size will be used
  */
Guolin Ke's avatar
Guolin Ke committed
527
  void Reset(int cache_size, int total_size) {
Guolin Ke's avatar
Guolin Ke committed
528
529
530
531
532
533
534
535
536
    cache_size_ = cache_size;
    // at least need 2 bucket to store smaller leaf and larger leaf
    CHECK(cache_size_ >= 2);
    total_size_ = total_size;
    if (cache_size_ > total_size_) {
      cache_size_ = total_size_;
    }
    is_enough_ = (cache_size_ == total_size_);
    if (!is_enough_) {
537
538
539
      mapper_.resize(total_size_);
      inverse_mapper_.resize(cache_size_);
      last_used_time_.resize(cache_size_);
Guolin Ke's avatar
Guolin Ke committed
540
541
542
543
544
545
546
547
548
549
550
551
552
553
554
      ResetMap();
    }
  }
  /*!
  * \brief Reset mapper
  */
  void ResetMap() {
    if (!is_enough_) {
      cur_time_ = 0;
      std::fill(mapper_.begin(), mapper_.end(), -1);
      std::fill(inverse_mapper_.begin(), inverse_mapper_.end(), -1);
      std::fill(last_used_time_.begin(), last_used_time_.end(), 0);
    }
  }

Guolin Ke's avatar
Guolin Ke committed
555
556
  void DynamicChangeSize(const Dataset* train_data, const TreeConfig* tree_config, int cache_size, int total_size) {
    if (feature_metas_.empty()) {
Guolin Ke's avatar
Guolin Ke committed
557
558
559
560
      int num_feature = train_data->num_features();
      feature_metas_.resize(num_feature);
      #pragma omp parallel for schedule(static, 512) if(num_feature >= 1024)
      for (int i = 0; i < num_feature; ++i) {
Guolin Ke's avatar
Guolin Ke committed
561
        feature_metas_[i].num_bin = train_data->FeatureNumBin(i);
Guolin Ke's avatar
Guolin Ke committed
562
        feature_metas_[i].default_bin = train_data->FeatureBinMapper(i)->GetDefaultBin();
Guolin Ke's avatar
Guolin Ke committed
563
        feature_metas_[i].missing_type = train_data->FeatureBinMapper(i)->missing_type();
Guolin Ke's avatar
Guolin Ke committed
564
        feature_metas_[i].monotone_type = train_data->FeatureMonotone(i);
Guolin Ke's avatar
Guolin Ke committed
565
566
567
568
569
570
571
        if (train_data->FeatureBinMapper(i)->GetDefaultBin() == 0) {
          feature_metas_[i].bias = 1;
        } else {
          feature_metas_[i].bias = 0;
        }
        feature_metas_[i].tree_config = tree_config;
      }
Guolin Ke's avatar
Guolin Ke committed
572
    }
Guolin Ke's avatar
Guolin Ke committed
573
574
    uint64_t num_total_bin = train_data->NumTotalBin();
    Log::Info("Total Bins %d", num_total_bin);
Guolin Ke's avatar
Guolin Ke committed
575
    int old_cache_size = static_cast<int>(pool_.size());
Guolin Ke's avatar
Guolin Ke committed
576
    Reset(cache_size, total_size);
Guolin Ke's avatar
Guolin Ke committed
577
578
579
580
581
582

    if (cache_size > old_cache_size) {
      pool_.resize(cache_size);
      data_.resize(cache_size);
    }

583
    OMP_INIT_EX();
Guolin Ke's avatar
Guolin Ke committed
584
    #pragma omp parallel for schedule(static)
Guolin Ke's avatar
Guolin Ke committed
585
    for (int i = old_cache_size; i < cache_size; ++i) {
586
      OMP_LOOP_EX_BEGIN();
Guolin Ke's avatar
Guolin Ke committed
587
588
589
590
591
      pool_[i].reset(new FeatureHistogram[train_data->num_features()]);
      data_[i].resize(num_total_bin);
      uint64_t offset = 0;
      for (int j = 0; j < train_data->num_features(); ++j) {
        offset += static_cast<uint64_t>(train_data->SubFeatureBinOffset(j));
592
        pool_[i][j].Init(data_[i].data() + offset, &feature_metas_[j], train_data->FeatureBinMapper(j)->bin_type());
Guolin Ke's avatar
Guolin Ke committed
593
594
595
596
597
598
599
        auto num_bin = train_data->FeatureNumBin(j);
        if (train_data->FeatureBinMapper(j)->GetDefaultBin() == 0) {
          num_bin -= 1;
        }
        offset += static_cast<uint64_t>(num_bin);
      }
      CHECK(offset == num_total_bin);
600
      OMP_LOOP_EX_END();
Guolin Ke's avatar
Guolin Ke committed
601
    }
602
    OMP_THROW_EX();
Guolin Ke's avatar
Guolin Ke committed
603
604
  }

Guolin Ke's avatar
Guolin Ke committed
605
  void ResetConfig(const TreeConfig* tree_config) {
Guolin Ke's avatar
Guolin Ke committed
606
607
608
    int size = static_cast<int>(feature_metas_.size());
    #pragma omp parallel for schedule(static, 512) if(size >= 1024)
    for (int i = 0; i < size; ++i) {
Guolin Ke's avatar
Guolin Ke committed
609
      feature_metas_[i].tree_config = tree_config;
Guolin Ke's avatar
Guolin Ke committed
610
611
    }
  }
Guolin Ke's avatar
Guolin Ke committed
612
613
614
615
616
617
618
619
620
621
622
623
624
625
626
627
628
629
630
631
632
633
634
635
636
637
638
639
640
641
642
643
644
645
646
647
648
649
650
651
652
653
654
655
656
657
658
659
660
661
662
663
664
665
666
667
  /*!
  * \brief Get data for the specific index
  * \param idx which index want to get
  * \param out output data will store into this
  * \return True if this index is in the pool, False if this index is not in the pool
  */
  bool Get(int idx, FeatureHistogram** out) {
    if (is_enough_) {
      *out = pool_[idx].get();
      return true;
    } else if (mapper_[idx] >= 0) {
      int slot = mapper_[idx];
      *out = pool_[slot].get();
      last_used_time_[slot] = ++cur_time_;
      return true;
    } else {
      // choose the least used slot 
      int slot = static_cast<int>(ArrayArgs<int>::ArgMin(last_used_time_));
      *out = pool_[slot].get();
      last_used_time_[slot] = ++cur_time_;

      // reset previous mapper
      if (inverse_mapper_[slot] >= 0) mapper_[inverse_mapper_[slot]] = -1;

      // update current mapper
      mapper_[idx] = slot;
      inverse_mapper_[slot] = idx;
      return false;
    }
  }

  /*!
  * \brief Move data from one index to another index
  * \param src_idx
  * \param dst_idx
  */
  void Move(int src_idx, int dst_idx) {
    if (is_enough_) {
      std::swap(pool_[src_idx], pool_[dst_idx]);
      return;
    }
    if (mapper_[src_idx] < 0) {
      return;
    }
    // get slot of src idx
    int slot = mapper_[src_idx];
    // reset src_idx
    mapper_[src_idx] = -1;

    // move to dst idx
    mapper_[dst_idx] = slot;
    last_used_time_[slot] = ++cur_time_;
    inverse_mapper_[slot] = dst_idx;
  }
private:
  std::vector<std::unique_ptr<FeatureHistogram[]>> pool_;
Guolin Ke's avatar
Guolin Ke committed
668
669
  std::vector<std::vector<HistogramBinEntry>> data_;
  std::vector<FeatureMetainfo> feature_metas_;
Guolin Ke's avatar
Guolin Ke committed
670
671
672
673
674
675
676
677
678
  int cache_size_;
  int total_size_;
  bool is_enough_ = false;
  std::vector<int> mapper_;
  std::vector<int> inverse_mapper_;
  std::vector<int> last_used_time_;
  int cur_time_ = 0;
};

Guolin Ke's avatar
Guolin Ke committed
679
}  // namespace LightGBM
Guolin Ke's avatar
Guolin Ke committed
680
#endif   // LightGBM_TREELEARNER_FEATURE_HISTOGRAM_HPP_