serial_tree_learner.cpp 35.1 KB
Newer Older
1
2
3
4
/*!
 * Copyright (c) 2016 Microsoft Corporation. All rights reserved.
 * Licensed under the MIT License. See LICENSE file in the project root for license information.
 */
Guolin Ke's avatar
Guolin Ke committed
5
6
#include "serial_tree_learner.h"

7
8
#include <LightGBM/network.h>
#include <LightGBM/objective_function.h>
Guolin Ke's avatar
Guolin Ke committed
9
#include <LightGBM/utils/array_args.h>
10
#include <LightGBM/utils/common.h>
Guolin Ke's avatar
Guolin Ke committed
11

Guolin Ke's avatar
Guolin Ke committed
12
#include <algorithm>
13
#include <queue>
14
15
#include <unordered_map>
#include <utility>
Guolin Ke's avatar
Guolin Ke committed
16

17
18
#include "cost_effective_gradient_boosting.hpp"

Guolin Ke's avatar
Guolin Ke committed
19
20
namespace LightGBM {

Guolin Ke's avatar
Guolin Ke committed
21

Guolin Ke's avatar
Guolin Ke committed
22
23
24
SerialTreeLearner::SerialTreeLearner(const Config* config)
  :config_(config) {
  random_ = Random(config_->feature_fraction_seed);
25
26
  #pragma omp parallel
  #pragma omp master
Guolin Ke's avatar
Guolin Ke committed
27
28
29
  {
    num_threads_ = omp_get_num_threads();
  }
Guolin Ke's avatar
Guolin Ke committed
30
31
32
}

SerialTreeLearner::~SerialTreeLearner() {
33

Guolin Ke's avatar
Guolin Ke committed
34
35
}

36
void SerialTreeLearner::Init(const Dataset* train_data, bool is_constant_hessian) {
Guolin Ke's avatar
Guolin Ke committed
37
38
39
  train_data_ = train_data;
  num_data_ = train_data_->num_data();
  num_features_ = train_data_->num_features();
40
  is_constant_hessian_ = is_constant_hessian;
41
42
  int max_cache_size = 0;
  // Get the max size of pool
Guolin Ke's avatar
Guolin Ke committed
43
44
  if (config_->histogram_pool_size <= 0) {
    max_cache_size = config_->num_leaves;
45
46
47
  } else {
    size_t total_histogram_size = 0;
    for (int i = 0; i < train_data_->num_features(); ++i) {
48
      total_histogram_size += KHistEntrySize * train_data_->FeatureNumBin(i);
49
    }
Guolin Ke's avatar
Guolin Ke committed
50
    max_cache_size = static_cast<int>(config_->histogram_pool_size * 1024 * 1024 / total_histogram_size);
51
52
  }
  // at least need 2 leaves
Guolin Ke's avatar
Guolin Ke committed
53
  max_cache_size = std::max(2, max_cache_size);
Guolin Ke's avatar
Guolin Ke committed
54
  max_cache_size = std::min(max_cache_size, config_->num_leaves);
Guolin Ke's avatar
Guolin Ke committed
55

56
  
Guolin Ke's avatar
Guolin Ke committed
57
  // push split information for all leaves
Guolin Ke's avatar
Guolin Ke committed
58
  best_split_per_leaf_.resize(config_->num_leaves);
Guolin Ke's avatar
Guolin Ke committed
59

wxchan's avatar
wxchan committed
60
  // initialize splits for leaf
Guolin Ke's avatar
Guolin Ke committed
61
62
  smaller_leaf_splits_.reset(new LeafSplits(train_data_->num_data()));
  larger_leaf_splits_.reset(new LeafSplits(train_data_->num_data()));
Guolin Ke's avatar
Guolin Ke committed
63
64

  // initialize data partition
Guolin Ke's avatar
Guolin Ke committed
65
  data_partition_.reset(new DataPartition(num_data_, config_->num_leaves));
Guolin Ke's avatar
Guolin Ke committed
66
  is_feature_used_.resize(num_features_);
67
  valid_feature_indices_ = train_data_->ValidFeatureIndices();
Guolin Ke's avatar
Guolin Ke committed
68
  // initialize ordered gradients and hessians
Guolin Ke's avatar
Guolin Ke committed
69
70
  ordered_gradients_.resize(num_data_);
  ordered_hessians_.resize(num_data_);
71
72
73
74

  GetMultiValBin(train_data_, true);

  histogram_pool_.DynamicChangeSize(train_data_, is_hist_colwise_, config_, max_cache_size, config_->num_leaves);
75
  Log::Info("Number of data points in the train set: %d, number of used features: %d", num_data_, num_features_);
76
77
78
  if (CostEfficientGradientBoosting::IsEnable(config_)) {
    cegb_.reset(new CostEfficientGradientBoosting(this));
    cegb_->Init();
79
  }
Guolin Ke's avatar
Guolin Ke committed
80
81
}

82
83
84
85
86
87
88
89
90
91
92
93
void SerialTreeLearner::GetMultiValBin(const Dataset* dataset, bool is_first_time) {
  if (is_first_time) {
    auto used_feature = GetUsedFeatures(true);
    multi_val_bin_.reset(dataset->TestMultiThreadingMethod(ordered_gradients_.data(), ordered_hessians_.data(), used_feature,
      is_constant_hessian_, config_->force_col_wise, config_->force_row_wise, &is_hist_colwise_));
  } else {
    // cannot change is_hist_col_wise during training
    multi_val_bin_.reset(dataset->TestMultiThreadingMethod(ordered_gradients_.data(), ordered_hessians_.data(), is_feature_used_,
      is_constant_hessian_, is_hist_colwise_, !is_hist_colwise_, &is_hist_colwise_));
  }
}

Guolin Ke's avatar
Guolin Ke committed
94
95
96
void SerialTreeLearner::ResetTrainingData(const Dataset* train_data) {
  train_data_ = train_data;
  num_data_ = train_data_->num_data();
Guolin Ke's avatar
Guolin Ke committed
97
  CHECK(num_features_ == train_data_->num_features());
Guolin Ke's avatar
Guolin Ke committed
98
99
100
101
102
103
104
105

  // initialize splits for leaf
  smaller_leaf_splits_->ResetNumData(num_data_);
  larger_leaf_splits_->ResetNumData(num_data_);

  // initialize data partition
  data_partition_->ResetNumData(num_data_);

106
107
  GetMultiValBin(train_data_, false);

Guolin Ke's avatar
Guolin Ke committed
108
109
110
  // initialize ordered gradients and hessians
  ordered_gradients_.resize(num_data_);
  ordered_hessians_.resize(num_data_);
111

112
113
114
  if (cegb_ != nullptr) {
    cegb_->Init();
  }
Guolin Ke's avatar
Guolin Ke committed
115
}
Guolin Ke's avatar
Guolin Ke committed
116

Guolin Ke's avatar
Guolin Ke committed
117
118
119
void SerialTreeLearner::ResetConfig(const Config* config) {
  if (config_->num_leaves != config->num_leaves) {
    config_ = config;
Guolin Ke's avatar
Guolin Ke committed
120
121
    int max_cache_size = 0;
    // Get the max size of pool
Guolin Ke's avatar
Guolin Ke committed
122
123
    if (config->histogram_pool_size <= 0) {
      max_cache_size = config_->num_leaves;
Guolin Ke's avatar
Guolin Ke committed
124
125
126
    } else {
      size_t total_histogram_size = 0;
      for (int i = 0; i < train_data_->num_features(); ++i) {
127
        total_histogram_size += KHistEntrySize * train_data_->FeatureNumBin(i);
Guolin Ke's avatar
Guolin Ke committed
128
      }
Guolin Ke's avatar
Guolin Ke committed
129
      max_cache_size = static_cast<int>(config_->histogram_pool_size * 1024 * 1024 / total_histogram_size);
Guolin Ke's avatar
Guolin Ke committed
130
131
132
    }
    // at least need 2 leaves
    max_cache_size = std::max(2, max_cache_size);
Guolin Ke's avatar
Guolin Ke committed
133
    max_cache_size = std::min(max_cache_size, config_->num_leaves);
134
    histogram_pool_.DynamicChangeSize(train_data_, is_hist_colwise_, config_, max_cache_size, config_->num_leaves);
Guolin Ke's avatar
Guolin Ke committed
135
136

    // push split information for all leaves
Guolin Ke's avatar
Guolin Ke committed
137
138
    best_split_per_leaf_.resize(config_->num_leaves);
    data_partition_->ResetLeaves(config_->num_leaves);
Guolin Ke's avatar
Guolin Ke committed
139
  } else {
Guolin Ke's avatar
Guolin Ke committed
140
    config_ = config;
Guolin Ke's avatar
Guolin Ke committed
141
  }
Guolin Ke's avatar
Guolin Ke committed
142
  histogram_pool_.ResetConfig(config_);
143
144
145
146
  if (CostEfficientGradientBoosting::IsEnable(config_)) {
    cegb_.reset(new CostEfficientGradientBoosting(this));
    cegb_->Init();
  }
Guolin Ke's avatar
Guolin Ke committed
147
148
}

Guolin Ke's avatar
Guolin Ke committed
149
Tree* SerialTreeLearner::Train(const score_t* gradients, const score_t *hessians, bool is_constant_hessian, const Json& forced_split_json) {
150
  Common::FunctionTimer fun_timer("SerialTreeLearner::Train", global_timer);
Guolin Ke's avatar
Guolin Ke committed
151
152
  gradients_ = gradients;
  hessians_ = hessians;
153
  is_constant_hessian_ = is_constant_hessian;
154

Guolin Ke's avatar
Guolin Ke committed
155
156
  // some initial works before training
  BeforeTrain();
Guolin Ke's avatar
Guolin Ke committed
157

Guolin Ke's avatar
Guolin Ke committed
158
  auto tree = std::unique_ptr<Tree>(new Tree(config_->num_leaves));
Guolin Ke's avatar
Guolin Ke committed
159
160
  // root leaf
  int left_leaf = 0;
161
  int cur_depth = 1;
Guolin Ke's avatar
Guolin Ke committed
162
163
  // only root leaf can be splitted on first time
  int right_leaf = -1;
164
165
166
167
168
169
170
171

  int init_splits = 0;
  bool aborted_last_force_split = false;
  if (!forced_split_json.is_null()) {
    init_splits = ForceSplits(tree.get(), forced_split_json, &left_leaf,
                              &right_leaf, &cur_depth, &aborted_last_force_split);
  }

Guolin Ke's avatar
Guolin Ke committed
172
  for (int split = init_splits; split < config_->num_leaves - 1; ++split) {
Guolin Ke's avatar
Guolin Ke committed
173
    // some initial works before finding best split
174
    if (!aborted_last_force_split && BeforeFindBestSplit(tree.get(), left_leaf, right_leaf)) {
Guolin Ke's avatar
Guolin Ke committed
175
      // find best threshold for every feature
Guolin Ke's avatar
Guolin Ke committed
176
      FindBestSplits();
177
178
    } else if (aborted_last_force_split) {
      aborted_last_force_split = false;
Guolin Ke's avatar
Guolin Ke committed
179
    }
180

Guolin Ke's avatar
Guolin Ke committed
181
182
183
184
185
186
    // Get a leaf with max split gain
    int best_leaf = static_cast<int>(ArrayArgs<SplitInfo>::ArgMax(best_split_per_leaf_));
    // Get split information for best leaf
    const SplitInfo& best_leaf_SplitInfo = best_split_per_leaf_[best_leaf];
    // cannot split, quit
    if (best_leaf_SplitInfo.gain <= 0.0) {
Guolin Ke's avatar
Guolin Ke committed
187
      Log::Warning("No further splits with positive gain, best gain: %f", best_leaf_SplitInfo.gain);
Guolin Ke's avatar
Guolin Ke committed
188
189
190
      break;
    }
    // split tree with best leaf
Guolin Ke's avatar
Guolin Ke committed
191
    Split(tree.get(), best_leaf, &left_leaf, &right_leaf);
192
    cur_depth = std::max(cur_depth, tree->leaf_depth(left_leaf));
Guolin Ke's avatar
Guolin Ke committed
193
  }
194
  Log::Debug("Trained a tree with leaves = %d and max_depth = %d", tree->num_leaves(), cur_depth);
Guolin Ke's avatar
Guolin Ke committed
195
  return tree.release();
Guolin Ke's avatar
Guolin Ke committed
196
197
}

198
Tree* SerialTreeLearner::FitByExistingTree(const Tree* old_tree, const score_t* gradients, const score_t *hessians) const {
Guolin Ke's avatar
Guolin Ke committed
199
200
  auto tree = std::unique_ptr<Tree>(new Tree(*old_tree));
  CHECK(data_partition_->num_leaves() >= tree->num_leaves());
201
  OMP_INIT_EX();
Guolin Ke's avatar
Guolin Ke committed
202
  #pragma omp parallel for schedule(static)
203
  for (int i = 0; i < tree->num_leaves(); ++i) {
204
    OMP_LOOP_EX_BEGIN();
Guolin Ke's avatar
Guolin Ke committed
205
206
207
    data_size_t cnt_leaf_data = 0;
    auto tmp_idx = data_partition_->GetIndexOnLeaf(i, &cnt_leaf_data);
    double sum_grad = 0.0f;
208
    double sum_hess = kEpsilon;
Guolin Ke's avatar
Guolin Ke committed
209
210
211
212
213
214
    for (data_size_t j = 0; j < cnt_leaf_data; ++j) {
      auto idx = tmp_idx[j];
      sum_grad += gradients[idx];
      sum_hess += hessians[idx];
    }
    double output = FeatureHistogram::CalculateSplittedLeafOutput(sum_grad, sum_hess,
Guolin Ke's avatar
Guolin Ke committed
215
                                                                  config_->lambda_l1, config_->lambda_l2, config_->max_delta_step);
Guolin Ke's avatar
Guolin Ke committed
216
217
218
    auto old_leaf_output = tree->LeafOutput(i);
    auto new_leaf_output = output * tree->shrinkage();
    tree->SetLeafOutput(i, config_->refit_decay_rate * old_leaf_output + (1.0 - config_->refit_decay_rate) * new_leaf_output);
219
    OMP_LOOP_EX_END();
Guolin Ke's avatar
Guolin Ke committed
220
  }
221
  OMP_THROW_EX();
Guolin Ke's avatar
Guolin Ke committed
222
223
224
  return tree.release();
}

225
226
227
228
229
Tree* SerialTreeLearner::FitByExistingTree(const Tree* old_tree, const std::vector<int>& leaf_pred, const score_t* gradients, const score_t *hessians) {
  data_partition_->ResetByLeafPred(leaf_pred, old_tree->num_leaves());
  return FitByExistingTree(old_tree, gradients, hessians);
}

230
std::vector<int8_t> SerialTreeLearner::GetUsedFeatures(bool is_tree_level) {
231
  std::vector<int8_t> ret(num_features_, 1);
232
233
234
235
  if (config_->feature_fraction >= 1.0f && is_tree_level) {
    return ret;
  }
  if (config_->feature_fraction_bynode >= 1.0f && !is_tree_level) {
236
237
238
    return ret;
  }
  std::memset(ret.data(), 0, sizeof(int8_t) * num_features_);
239
  const int min_used_features = std::min(2, static_cast<int>(valid_feature_indices_.size()));
240
  if (is_tree_level) {
241
242
    int used_feature_cnt = static_cast<int>(std::round(valid_feature_indices_.size() * config_->feature_fraction));
    used_feature_cnt = std::max(used_feature_cnt, min_used_features);
243
244
245
246
247
248
249
250
251
    used_feature_indices_ = random_.Sample(static_cast<int>(valid_feature_indices_.size()), used_feature_cnt);
    int omp_loop_size = static_cast<int>(used_feature_indices_.size());
    #pragma omp parallel for schedule(static, 512) if (omp_loop_size >= 1024)
    for (int i = 0; i < omp_loop_size; ++i) {
      int used_feature = valid_feature_indices_[used_feature_indices_[i]];
      int inner_feature_index = train_data_->InnerFeatureIndex(used_feature);
      CHECK(inner_feature_index >= 0);
      ret[inner_feature_index] = 1;
    }
Guolin Ke's avatar
Guolin Ke committed
252
  } else if (used_feature_indices_.size() <= 0) {
253
254
    int used_feature_cnt = static_cast<int>(std::round(valid_feature_indices_.size() * config_->feature_fraction_bynode));
    used_feature_cnt = std::max(used_feature_cnt, min_used_features);
255
256
257
258
259
260
261
262
263
264
    auto sampled_indices = random_.Sample(static_cast<int>(valid_feature_indices_.size()), used_feature_cnt);
    int omp_loop_size = static_cast<int>(sampled_indices.size());
    #pragma omp parallel for schedule(static, 512) if (omp_loop_size >= 1024)
    for (int i = 0; i < omp_loop_size; ++i) {
      int used_feature = valid_feature_indices_[sampled_indices[i]];
      int inner_feature_index = train_data_->InnerFeatureIndex(used_feature);
      CHECK(inner_feature_index >= 0);
      ret[inner_feature_index] = 1;
    }
  } else {
265
266
    int used_feature_cnt = static_cast<int>(std::round(used_feature_indices_.size() * config_->feature_fraction_bynode));
    used_feature_cnt = std::max(used_feature_cnt, min_used_features);
267
268
269
270
271
272
273
274
275
    auto sampled_indices = random_.Sample(static_cast<int>(used_feature_indices_.size()), used_feature_cnt);
    int omp_loop_size = static_cast<int>(sampled_indices.size());
    #pragma omp parallel for schedule(static, 512) if (omp_loop_size >= 1024)
    for (int i = 0; i < omp_loop_size; ++i) {
      int used_feature = valid_feature_indices_[used_feature_indices_[sampled_indices[i]]];
      int inner_feature_index = train_data_->InnerFeatureIndex(used_feature);
      CHECK(inner_feature_index >= 0);
      ret[inner_feature_index] = 1;
    }
276
277
278
279
  }
  return ret;
}

Guolin Ke's avatar
Guolin Ke committed
280
void SerialTreeLearner::BeforeTrain() {
281
  Common::FunctionTimer fun_timer("SerialTreeLearner::BeforeTrain", global_timer);
282
283
  // reset histogram pool
  histogram_pool_.ResetMap();
Guolin Ke's avatar
Guolin Ke committed
284

285
286
  if (config_->feature_fraction < 1.0f) {
    is_feature_used_ = GetUsedFeatures(true);
Guolin Ke's avatar
Guolin Ke committed
287
  } else {
Guolin Ke's avatar
Guolin Ke committed
288
    #pragma omp parallel for schedule(static, 512) if (num_features_ >= 1024)
Guolin Ke's avatar
Guolin Ke committed
289
290
291
    for (int i = 0; i < num_features_; ++i) {
      is_feature_used_[i] = 1;
    }
Guolin Ke's avatar
Guolin Ke committed
292
  }
293

Guolin Ke's avatar
Guolin Ke committed
294
295
296
297
  // initialize data partition
  data_partition_->Init();

  // reset the splits for leaves
Guolin Ke's avatar
Guolin Ke committed
298
  for (int i = 0; i < config_->num_leaves; ++i) {
Guolin Ke's avatar
Guolin Ke committed
299
300
301
302
303
304
305
    best_split_per_leaf_[i].Reset();
  }

  // Sumup for root
  if (data_partition_->leaf_count(0) == num_data_) {
    // use all data
    smaller_leaf_splits_->Init(gradients_, hessians_);
Guolin Ke's avatar
Guolin Ke committed
306

Guolin Ke's avatar
Guolin Ke committed
307
308
  } else {
    // use bagging, only use part of data
Guolin Ke's avatar
Guolin Ke committed
309
    smaller_leaf_splits_->Init(0, data_partition_.get(), gradients_, hessians_);
Guolin Ke's avatar
Guolin Ke committed
310
311
312
313
314
  }

  larger_leaf_splits_->Init();
}

Guolin Ke's avatar
Guolin Ke committed
315
bool SerialTreeLearner::BeforeFindBestSplit(const Tree* tree, int left_leaf, int right_leaf) {
316
  Common::FunctionTimer fun_timer("SerialTreeLearner::BeforeFindBestSplit", global_timer);
Guolin Ke's avatar
Guolin Ke committed
317
  // check depth of current leaf
Guolin Ke's avatar
Guolin Ke committed
318
  if (config_->max_depth > 0) {
Guolin Ke's avatar
Guolin Ke committed
319
    // only need to check left leaf, since right leaf is in same level of left leaf
Guolin Ke's avatar
Guolin Ke committed
320
    if (tree->leaf_depth(left_leaf) >= config_->max_depth) {
Guolin Ke's avatar
Guolin Ke committed
321
322
323
324
325
326
327
      best_split_per_leaf_[left_leaf].gain = kMinScore;
      if (right_leaf >= 0) {
        best_split_per_leaf_[right_leaf].gain = kMinScore;
      }
      return false;
    }
  }
Guolin Ke's avatar
Guolin Ke committed
328
329
330
  data_size_t num_data_in_left_child = GetGlobalDataCountInLeaf(left_leaf);
  data_size_t num_data_in_right_child = GetGlobalDataCountInLeaf(right_leaf);
  // no enough data to continue
Guolin Ke's avatar
Guolin Ke committed
331
332
  if (num_data_in_right_child < static_cast<data_size_t>(config_->min_data_in_leaf * 2)
      && num_data_in_left_child < static_cast<data_size_t>(config_->min_data_in_leaf * 2)) {
Guolin Ke's avatar
Guolin Ke committed
333
334
335
336
337
338
    best_split_per_leaf_[left_leaf].gain = kMinScore;
    if (right_leaf >= 0) {
      best_split_per_leaf_[right_leaf].gain = kMinScore;
    }
    return false;
  }
339
  parent_leaf_histogram_array_ = nullptr;
Guolin Ke's avatar
Guolin Ke committed
340
341
  // only have root
  if (right_leaf < 0) {
342
    histogram_pool_.Get(left_leaf, &smaller_leaf_histogram_array_);
Guolin Ke's avatar
Guolin Ke committed
343
344
    larger_leaf_histogram_array_ = nullptr;
  } else if (num_data_in_left_child < num_data_in_right_child) {
Hui Xue's avatar
Hui Xue committed
345
    // put parent(left) leaf's histograms into larger leaf's histograms
346
347
348
    if (histogram_pool_.Get(left_leaf, &larger_leaf_histogram_array_)) { parent_leaf_histogram_array_ = larger_leaf_histogram_array_; }
    histogram_pool_.Move(left_leaf, right_leaf);
    histogram_pool_.Get(left_leaf, &smaller_leaf_histogram_array_);
Guolin Ke's avatar
Guolin Ke committed
349
  } else {
Hui Xue's avatar
Hui Xue committed
350
    // put parent(left) leaf's histograms to larger leaf's histograms
351
352
    if (histogram_pool_.Get(left_leaf, &larger_leaf_histogram_array_)) { parent_leaf_histogram_array_ = larger_leaf_histogram_array_; }
    histogram_pool_.Get(right_leaf, &smaller_leaf_histogram_array_);
Guolin Ke's avatar
Guolin Ke committed
353
354
355
356
  }
  return true;
}

Guolin Ke's avatar
Guolin Ke committed
357
358
void SerialTreeLearner::FindBestSplits() {
  std::vector<int8_t> is_feature_used(num_features_, 0);
359
  #pragma omp parallel for schedule(static, 1024) if (num_features_ >= 2048)
Guolin Ke's avatar
Guolin Ke committed
360
361
362
363
364
365
366
367
368
369
370
371
372
373
  for (int feature_index = 0; feature_index < num_features_; ++feature_index) {
    if (!is_feature_used_[feature_index]) continue;
    if (parent_leaf_histogram_array_ != nullptr
        && !parent_leaf_histogram_array_[feature_index].is_splittable()) {
      smaller_leaf_histogram_array_[feature_index].set_is_splittable(false);
      continue;
    }
    is_feature_used[feature_index] = 1;
  }
  bool use_subtract = parent_leaf_histogram_array_ != nullptr;
  ConstructHistograms(is_feature_used, use_subtract);
  FindBestSplitsFromHistograms(is_feature_used, use_subtract);
}

374
void SerialTreeLearner::ConstructHistograms(const std::vector<int8_t>& is_feature_used, bool use_subtract) {
375
  Common::FunctionTimer fun_timer("SerialTreeLearner::ConstructHistograms", global_timer);
Guolin Ke's avatar
Guolin Ke committed
376
  // construct smaller leaf
377
  hist_t* ptr_smaller_leaf_hist_data = smaller_leaf_histogram_array_[0].RawData() - KHistOffset;
Guolin Ke's avatar
Guolin Ke committed
378
  train_data_->ConstructHistograms(is_feature_used,
Guolin Ke's avatar
Guolin Ke committed
379
                                   smaller_leaf_splits_->data_indices(), smaller_leaf_splits_->num_data_in_leaf(),
380
                                   gradients_, hessians_,
381
                                   ordered_gradients_.data(), ordered_hessians_.data(), is_constant_hessian_,
382
                                   multi_val_bin_.get(), is_hist_colwise_,
Guolin Ke's avatar
Guolin Ke committed
383
                                   ptr_smaller_leaf_hist_data);
Guolin Ke's avatar
Guolin Ke committed
384
385
386

  if (larger_leaf_histogram_array_ != nullptr && !use_subtract) {
    // construct larger leaf
387
    hist_t* ptr_larger_leaf_hist_data = larger_leaf_histogram_array_[0].RawData() - KHistOffset;
Guolin Ke's avatar
Guolin Ke committed
388
    train_data_->ConstructHistograms(is_feature_used,
Guolin Ke's avatar
Guolin Ke committed
389
                                     larger_leaf_splits_->data_indices(), larger_leaf_splits_->num_data_in_leaf(),
390
                                     gradients_, hessians_,
391
                                     ordered_gradients_.data(), ordered_hessians_.data(), is_constant_hessian_,
392
                                     multi_val_bin_.get(), is_hist_colwise_,
Guolin Ke's avatar
Guolin Ke committed
393
                                     ptr_larger_leaf_hist_data);
Guolin Ke's avatar
Guolin Ke committed
394
  }
395
396
}

Guolin Ke's avatar
Guolin Ke committed
397
void SerialTreeLearner::FindBestSplitsFromHistograms(const std::vector<int8_t>& is_feature_used, bool use_subtract) {
398
  Common::FunctionTimer fun_timer("SerialTreeLearner::FindBestSplitsFromHistograms", global_timer);
Guolin Ke's avatar
Guolin Ke committed
399
400
  std::vector<SplitInfo> smaller_best(num_threads_);
  std::vector<SplitInfo> larger_best(num_threads_);
401
402
  std::vector<int8_t> smaller_node_used_features(num_features_, 1);
  std::vector<int8_t> larger_node_used_features(num_features_, 1);
403
404
405
  if (config_->feature_fraction_bynode < 1.0f) {
    smaller_node_used_features = GetUsedFeatures(false);
    larger_node_used_features = GetUsedFeatures(false);
406
  }
407
  OMP_INIT_EX();
408
  // find splits	
409
  #pragma omp parallel for schedule(static)
Guolin Ke's avatar
Guolin Ke committed
410
  for (int feature_index = 0; feature_index < num_features_; ++feature_index) {
411
    OMP_LOOP_EX_BEGIN();
Guolin Ke's avatar
Guolin Ke committed
412
413
414
    if (!is_feature_used[feature_index]) { continue; }
    const int tid = omp_get_thread_num();
    SplitInfo smaller_split;
Guolin Ke's avatar
Guolin Ke committed
415
416
417
    train_data_->FixHistogram(feature_index,
                              smaller_leaf_splits_->sum_gradients(), smaller_leaf_splits_->sum_hessians(),
                              smaller_leaf_histogram_array_[feature_index].RawData());
418
    int real_fidx = train_data_->RealFeatureIndex(feature_index);
Guolin Ke's avatar
Guolin Ke committed
419
420
421
422
    smaller_leaf_histogram_array_[feature_index].FindBestThreshold(
      smaller_leaf_splits_->sum_gradients(),
      smaller_leaf_splits_->sum_hessians(),
      smaller_leaf_splits_->num_data_in_leaf(),
Guolin Ke's avatar
Guolin Ke committed
423
424
      smaller_leaf_splits_->min_constraint(),
      smaller_leaf_splits_->max_constraint(),
Guolin Ke's avatar
Guolin Ke committed
425
      &smaller_split);
426
    smaller_split.feature = real_fidx;
427
428
    if (cegb_ != nullptr) {
      smaller_split.gain -= cegb_->DetlaGain(feature_index, real_fidx, smaller_leaf_splits_->LeafIndex(), smaller_leaf_splits_->num_data_in_leaf(), smaller_split);
429
    }
430
    if (smaller_split > smaller_best[tid] && smaller_node_used_features[feature_index]) {
Guolin Ke's avatar
Guolin Ke committed
431
432
      smaller_best[tid] = smaller_split;
    }
Guolin Ke's avatar
Guolin Ke committed
433
    // only has root leaf
Guolin Ke's avatar
Guolin Ke committed
434
    if (larger_leaf_splits_ == nullptr || larger_leaf_splits_->LeafIndex() < 0) { continue; }
Guolin Ke's avatar
Guolin Ke committed
435

Guolin Ke's avatar
Guolin Ke committed
436
    if (use_subtract) {
437
438
      larger_leaf_histogram_array_[feature_index].Subtract(smaller_leaf_histogram_array_[feature_index]);
    } else {
Guolin Ke's avatar
Guolin Ke committed
439
      train_data_->FixHistogram(feature_index, larger_leaf_splits_->sum_gradients(), larger_leaf_splits_->sum_hessians(),
Guolin Ke's avatar
Guolin Ke committed
440
                                larger_leaf_histogram_array_[feature_index].RawData());
441
    }
Guolin Ke's avatar
Guolin Ke committed
442
    SplitInfo larger_split;
Guolin Ke's avatar
Guolin Ke committed
443
    // find best threshold for larger child
Guolin Ke's avatar
Guolin Ke committed
444
445
446
447
    larger_leaf_histogram_array_[feature_index].FindBestThreshold(
      larger_leaf_splits_->sum_gradients(),
      larger_leaf_splits_->sum_hessians(),
      larger_leaf_splits_->num_data_in_leaf(),
Guolin Ke's avatar
Guolin Ke committed
448
449
      larger_leaf_splits_->min_constraint(),
      larger_leaf_splits_->max_constraint(),
Guolin Ke's avatar
Guolin Ke committed
450
      &larger_split);
451
    larger_split.feature = real_fidx;
452
453
    if (cegb_ != nullptr) {
      larger_split.gain -= cegb_->DetlaGain(feature_index, real_fidx, larger_leaf_splits_->LeafIndex(), larger_leaf_splits_->num_data_in_leaf(), larger_split);
454
    }
455
    if (larger_split > larger_best[tid] && larger_node_used_features[feature_index]) {
Guolin Ke's avatar
Guolin Ke committed
456
      larger_best[tid] = larger_split;
Guolin Ke's avatar
Guolin Ke committed
457
    }
458
    OMP_LOOP_EX_END();
Guolin Ke's avatar
Guolin Ke committed
459
  }
460
  OMP_THROW_EX();
Guolin Ke's avatar
Guolin Ke committed
461
462
463
464
465
466
467
468
469
470
471
  auto smaller_best_idx = ArrayArgs<SplitInfo>::ArgMax(smaller_best);
  int leaf = smaller_leaf_splits_->LeafIndex();
  best_split_per_leaf_[leaf] = smaller_best[smaller_best_idx];

  if (larger_leaf_splits_ != nullptr && larger_leaf_splits_->LeafIndex() >= 0) {
    leaf = larger_leaf_splits_->LeafIndex();
    auto larger_best_idx = ArrayArgs<SplitInfo>::ArgMax(larger_best);
    best_split_per_leaf_[leaf] = larger_best[larger_best_idx];
  }
}

Guolin Ke's avatar
Guolin Ke committed
472
int32_t SerialTreeLearner::ForceSplits(Tree* tree, const Json& forced_split_json, int* left_leaf,
473
                                       int* right_leaf, int *cur_depth,
474
475
476
477
478
479
480
481
482
483
                                       bool *aborted_last_force_split) {
  int32_t result_count = 0;
  // start at root leaf
  *left_leaf = 0;
  std::queue<std::pair<Json, int>> q;
  Json left = forced_split_json;
  Json right;
  bool left_smaller = true;
  std::unordered_map<int, SplitInfo> forceSplitMap;
  q.push(std::make_pair(forced_split_json, *left_leaf));
484
  while (!q.empty()) {
485
486
487
488
489
490
491
492
493
494
495
496
497
498
499
500
501
502
503
504
505
506
507
508
509
510
511
512
513
514
515
516
517
518
519
520
521
522
523
524
525
526
527
528
529
530
531
532
533
534
535
536
537
538
539
540
541
542
543
544
545
546
547
548
549
550
551
552
553
554
555
556
557
558
559
560
561
    // before processing next node from queue, store info for current left/right leaf
    // store "best split" for left and right, even if they might be overwritten by forced split
    if (BeforeFindBestSplit(tree, *left_leaf, *right_leaf)) {
      FindBestSplits();
    }
    // then, compute own splits
    SplitInfo left_split;
    SplitInfo right_split;

    if (!left.is_null()) {
      const int left_feature = left["feature"].int_value();
      const double left_threshold_double = left["threshold"].number_value();
      const int left_inner_feature_index = train_data_->InnerFeatureIndex(left_feature);
      const uint32_t left_threshold = train_data_->BinThreshold(
              left_inner_feature_index, left_threshold_double);
      auto leaf_histogram_array = (left_smaller) ? smaller_leaf_histogram_array_ : larger_leaf_histogram_array_;
      auto left_leaf_splits = (left_smaller) ? smaller_leaf_splits_.get() : larger_leaf_splits_.get();
      leaf_histogram_array[left_inner_feature_index].GatherInfoForThreshold(
              left_leaf_splits->sum_gradients(),
              left_leaf_splits->sum_hessians(),
              left_threshold,
              left_leaf_splits->num_data_in_leaf(),
              &left_split);
      left_split.feature = left_feature;
      forceSplitMap[*left_leaf] = left_split;
      if (left_split.gain < 0) {
        forceSplitMap.erase(*left_leaf);
      }
    }

    if (!right.is_null()) {
      const int right_feature = right["feature"].int_value();
      const double right_threshold_double = right["threshold"].number_value();
      const int right_inner_feature_index = train_data_->InnerFeatureIndex(right_feature);
      const uint32_t right_threshold = train_data_->BinThreshold(
              right_inner_feature_index, right_threshold_double);
      auto leaf_histogram_array = (left_smaller) ? larger_leaf_histogram_array_ : smaller_leaf_histogram_array_;
      auto right_leaf_splits = (left_smaller) ? larger_leaf_splits_.get() : smaller_leaf_splits_.get();
      leaf_histogram_array[right_inner_feature_index].GatherInfoForThreshold(
        right_leaf_splits->sum_gradients(),
        right_leaf_splits->sum_hessians(),
        right_threshold,
        right_leaf_splits->num_data_in_leaf(),
        &right_split);
      right_split.feature = right_feature;
      forceSplitMap[*right_leaf] = right_split;
      if (right_split.gain < 0) {
        forceSplitMap.erase(*right_leaf);
      }
    }

    std::pair<Json, int> pair = q.front();
    q.pop();
    int current_leaf = pair.second;
    // split info should exist because searching in bfs fashion - should have added from parent
    if (forceSplitMap.find(current_leaf) == forceSplitMap.end()) {
        *aborted_last_force_split = true;
        break;
    }
    SplitInfo current_split_info = forceSplitMap[current_leaf];
    const int inner_feature_index = train_data_->InnerFeatureIndex(
            current_split_info.feature);
    auto threshold_double = train_data_->RealThreshold(
            inner_feature_index, current_split_info.threshold);

    // split tree, will return right leaf
    *left_leaf = current_leaf;
    if (train_data_->FeatureBinMapper(inner_feature_index)->bin_type() == BinType::NumericalBin) {
      *right_leaf = tree->Split(current_leaf,
                                inner_feature_index,
                                current_split_info.feature,
                                current_split_info.threshold,
                                threshold_double,
                                static_cast<double>(current_split_info.left_output),
                                static_cast<double>(current_split_info.right_output),
                                static_cast<data_size_t>(current_split_info.left_count),
                                static_cast<data_size_t>(current_split_info.right_count),
562
563
                                static_cast<double>(current_split_info.left_sum_hessian),
                                static_cast<double>(current_split_info.right_sum_hessian),
564
565
566
567
568
569
570
571
572
573
574
575
576
577
578
579
580
581
582
583
584
585
586
587
588
589
590
                                static_cast<float>(current_split_info.gain),
                                train_data_->FeatureBinMapper(inner_feature_index)->missing_type(),
                                current_split_info.default_left);
      data_partition_->Split(current_leaf, train_data_, inner_feature_index,
                             &current_split_info.threshold, 1,
                             current_split_info.default_left, *right_leaf);
    } else {
      std::vector<uint32_t> cat_bitset_inner = Common::ConstructBitset(
              current_split_info.cat_threshold.data(), current_split_info.num_cat_threshold);
      std::vector<int> threshold_int(current_split_info.num_cat_threshold);
      for (int i = 0; i < current_split_info.num_cat_threshold; ++i) {
        threshold_int[i] = static_cast<int>(train_data_->RealThreshold(
                    inner_feature_index, current_split_info.cat_threshold[i]));
      }
      std::vector<uint32_t> cat_bitset = Common::ConstructBitset(
              threshold_int.data(), current_split_info.num_cat_threshold);
      *right_leaf = tree->SplitCategorical(current_leaf,
                                           inner_feature_index,
                                           current_split_info.feature,
                                           cat_bitset_inner.data(),
                                           static_cast<int>(cat_bitset_inner.size()),
                                           cat_bitset.data(),
                                           static_cast<int>(cat_bitset.size()),
                                           static_cast<double>(current_split_info.left_output),
                                           static_cast<double>(current_split_info.right_output),
                                           static_cast<data_size_t>(current_split_info.left_count),
                                           static_cast<data_size_t>(current_split_info.right_count),
591
592
                                           static_cast<double>(current_split_info.left_sum_hessian),
                                           static_cast<double>(current_split_info.right_sum_hessian),
593
594
595
596
597
598
599
600
601
602
603
604
605
606
607
608
609
610
611
612
613
614
615
616
617
618
619
                                           static_cast<float>(current_split_info.gain),
                                           train_data_->FeatureBinMapper(inner_feature_index)->missing_type());
      data_partition_->Split(current_leaf, train_data_, inner_feature_index,
                             cat_bitset_inner.data(), static_cast<int>(cat_bitset_inner.size()),
                             current_split_info.default_left, *right_leaf);
    }

    if (current_split_info.left_count < current_split_info.right_count) {
      left_smaller = true;
      smaller_leaf_splits_->Init(*left_leaf, data_partition_.get(),
                                 current_split_info.left_sum_gradient,
                                 current_split_info.left_sum_hessian);
      larger_leaf_splits_->Init(*right_leaf, data_partition_.get(),
                                current_split_info.right_sum_gradient,
                                current_split_info.right_sum_hessian);
    } else {
      left_smaller = false;
      smaller_leaf_splits_->Init(*right_leaf, data_partition_.get(),
                                 current_split_info.right_sum_gradient, current_split_info.right_sum_hessian);
      larger_leaf_splits_->Init(*left_leaf, data_partition_.get(),
                                current_split_info.left_sum_gradient, current_split_info.left_sum_hessian);
    }

    left = Json();
    right = Json();
    if ((pair.first).object_items().count("left") > 0) {
      left = (pair.first)["left"];
620
621
622
      if (left.object_items().count("feature") > 0 && left.object_items().count("threshold") > 0) {
        q.push(std::make_pair(left, *left_leaf));
      }
623
624
625
    }
    if ((pair.first).object_items().count("right") > 0) {
      right = (pair.first)["right"];
626
627
628
      if (right.object_items().count("feature") > 0 && right.object_items().count("threshold") > 0) {
        q.push(std::make_pair(right, *right_leaf));
      }
629
630
631
632
633
634
    }
    result_count++;
    *(cur_depth) = std::max(*(cur_depth), tree->leaf_depth(*left_leaf));
  }
  return result_count;
}
Guolin Ke's avatar
Guolin Ke committed
635

636
void SerialTreeLearner::Split(Tree* tree, int best_leaf, int* left_leaf, int* right_leaf) {
637
638
  Common::FunctionTimer fun_timer("SerialTreeLearner::Split", global_timer);
  SplitInfo& best_split_info = best_split_per_leaf_[best_leaf];
Guolin Ke's avatar
Guolin Ke committed
639
  const int inner_feature_index = train_data_->InnerFeatureIndex(best_split_info.feature);
640
641
  if (cegb_ != nullptr) {
    cegb_->UpdateLeafBestSplits(tree, best_leaf, &best_split_info, &best_split_per_leaf_);
642
  }
643
  *left_leaf = best_leaf;
644
645
  auto next_leaf_id = tree->NextLeafId();

Guolin Ke's avatar
Guolin Ke committed
646
647
  bool is_numerical_split = train_data_->FeatureBinMapper(inner_feature_index)->bin_type() == BinType::NumericalBin;
  if (is_numerical_split) {
648
    auto threshold_double = train_data_->RealThreshold(inner_feature_index, best_split_info.threshold);
649
650
651
652
    data_partition_->Split(best_leaf, train_data_, inner_feature_index,
      &best_split_info.threshold, 1, best_split_info.default_left, next_leaf_id);
    best_split_info.left_count = data_partition_->leaf_count(*left_leaf);
    best_split_info.right_count = data_partition_->leaf_count(next_leaf_id);
653
654
    // split tree, will return right leaf
    *right_leaf = tree->Split(best_leaf,
655
656
657
658
659
660
661
662
663
664
665
666
667
668
      inner_feature_index,
      best_split_info.feature,
      best_split_info.threshold,
      threshold_double,
      static_cast<double>(best_split_info.left_output),
      static_cast<double>(best_split_info.right_output),
      static_cast<data_size_t>(best_split_info.left_count),
      static_cast<data_size_t>(best_split_info.right_count),
      static_cast<double>(best_split_info.left_sum_hessian),
      static_cast<double>(best_split_info.right_sum_hessian),
      static_cast<float>(best_split_info.gain),
      train_data_->FeatureBinMapper(inner_feature_index)->missing_type(),
      best_split_info.default_left);

669
  } else {
670

671
672
673
674
675
676
    std::vector<uint32_t> cat_bitset_inner = Common::ConstructBitset(best_split_info.cat_threshold.data(), best_split_info.num_cat_threshold);
    std::vector<int> threshold_int(best_split_info.num_cat_threshold);
    for (int i = 0; i < best_split_info.num_cat_threshold; ++i) {
      threshold_int[i] = static_cast<int>(train_data_->RealThreshold(inner_feature_index, best_split_info.cat_threshold[i]));
    }
    std::vector<uint32_t> cat_bitset = Common::ConstructBitset(threshold_int.data(), best_split_info.num_cat_threshold);
677

678
    data_partition_->Split(best_leaf, train_data_, inner_feature_index,
679
680
681
682
683
684
685
686
687
688
689
690
691
692
693
694
695
696
697
698
699
700
      cat_bitset_inner.data(), static_cast<int>(cat_bitset_inner.size()), best_split_info.default_left, next_leaf_id);

    best_split_info.left_count = data_partition_->leaf_count(*left_leaf);
    best_split_info.right_count = data_partition_->leaf_count(next_leaf_id);

    *right_leaf = tree->SplitCategorical(best_leaf,
      inner_feature_index,
      best_split_info.feature,
      cat_bitset_inner.data(),
      static_cast<int>(cat_bitset_inner.size()),
      cat_bitset.data(),
      static_cast<int>(cat_bitset.size()),
      static_cast<double>(best_split_info.left_output),
      static_cast<double>(best_split_info.right_output),
      static_cast<data_size_t>(best_split_info.left_count),
      static_cast<data_size_t>(best_split_info.right_count),
      static_cast<double>(best_split_info.left_sum_hessian),
      static_cast<double>(best_split_info.right_sum_hessian),
      static_cast<float>(best_split_info.gain),
      train_data_->FeatureBinMapper(inner_feature_index)->missing_type());
  }
  CHECK(*right_leaf == next_leaf_id);
701

Guolin Ke's avatar
Guolin Ke committed
702
703
  auto p_left = smaller_leaf_splits_.get();
  auto p_right = larger_leaf_splits_.get();
Guolin Ke's avatar
Guolin Ke committed
704
705
  // init the leaves that used on next iteration
  if (best_split_info.left_count < best_split_info.right_count) {
706
    CHECK(best_split_info.left_count > 0);
Guolin Ke's avatar
Guolin Ke committed
707
708
    smaller_leaf_splits_->Init(*left_leaf, data_partition_.get(), best_split_info.left_sum_gradient, best_split_info.left_sum_hessian);
    larger_leaf_splits_->Init(*right_leaf, data_partition_.get(), best_split_info.right_sum_gradient, best_split_info.right_sum_hessian);
Guolin Ke's avatar
Guolin Ke committed
709
  } else {
710
    CHECK(best_split_info.right_count > 0);
Guolin Ke's avatar
Guolin Ke committed
711
712
    smaller_leaf_splits_->Init(*right_leaf, data_partition_.get(), best_split_info.right_sum_gradient, best_split_info.right_sum_hessian);
    larger_leaf_splits_->Init(*left_leaf, data_partition_.get(), best_split_info.left_sum_gradient, best_split_info.left_sum_hessian);
Guolin Ke's avatar
Guolin Ke committed
713
714
715
716
717
718
719
720
721
722
723
724
725
726
    p_right = smaller_leaf_splits_.get();
    p_left = larger_leaf_splits_.get();
  }
  p_left->SetValueConstraint(best_split_info.min_constraint, best_split_info.max_constraint);
  p_right->SetValueConstraint(best_split_info.min_constraint, best_split_info.max_constraint);
  if (is_numerical_split) {
    double mid = (best_split_info.left_output + best_split_info.right_output) / 2.0f;
    if (best_split_info.monotone_type < 0) {
      p_left->SetValueConstraint(mid, best_split_info.max_constraint);
      p_right->SetValueConstraint(best_split_info.min_constraint, mid);
    } else if (best_split_info.monotone_type > 0) {
      p_left->SetValueConstraint(best_split_info.min_constraint, mid);
      p_right->SetValueConstraint(mid, best_split_info.max_constraint);
    }
Guolin Ke's avatar
Guolin Ke committed
727
728
729
  }
}

Guolin Ke's avatar
Guolin Ke committed
730

731
void SerialTreeLearner::RenewTreeOutput(Tree* tree, const ObjectiveFunction* obj, std::function<double(const label_t*, int)> residual_getter,
732
733
734
735
736
737
738
739
                                        data_size_t total_num_data, const data_size_t* bag_indices, data_size_t bag_cnt) const {
  if (obj != nullptr && obj->IsRenewTreeOutput()) {
    CHECK(tree->num_leaves() <= data_partition_->num_leaves());
    const data_size_t* bag_mapper = nullptr;
    if (total_num_data != num_data_) {
      CHECK(bag_cnt == num_data_);
      bag_mapper = bag_indices;
    }
Guolin Ke's avatar
Guolin Ke committed
740
    std::vector<int> n_nozeroworker_perleaf(tree->num_leaves(), 1);
741
    int num_machines = Network::num_machines();
742
743
744
745
746
    #pragma omp parallel for schedule(static)
    for (int i = 0; i < tree->num_leaves(); ++i) {
      const double output = static_cast<double>(tree->LeafOutput(i));
      data_size_t cnt_leaf_data = 0;
      auto index_mapper = data_partition_->GetIndexOnLeaf(i, &cnt_leaf_data);
Guolin Ke's avatar
Guolin Ke committed
747
748
      if (cnt_leaf_data > 0) {
        // bag_mapper[index_mapper[i]]
749
        const double new_output = obj->RenewTreeOutput(output, residual_getter, index_mapper, bag_mapper, cnt_leaf_data);
Guolin Ke's avatar
Guolin Ke committed
750
751
752
753
754
755
756
757
758
759
760
761
        tree->SetLeafOutput(i, new_output);
      } else {
        CHECK(num_machines > 1);
        tree->SetLeafOutput(i, 0.0);
        n_nozeroworker_perleaf[i] = 0;
      }
    }
    if (num_machines > 1) {
      std::vector<double> outputs(tree->num_leaves());
      for (int i = 0; i < tree->num_leaves(); ++i) {
        outputs[i] = static_cast<double>(tree->LeafOutput(i));
      }
Guolin Ke's avatar
Guolin Ke committed
762
763
      outputs = Network::GlobalSum(&outputs);
      n_nozeroworker_perleaf = Network::GlobalSum(&n_nozeroworker_perleaf);
Guolin Ke's avatar
Guolin Ke committed
764
765
766
767
768
769
770
      for (int i = 0; i < tree->num_leaves(); ++i) {
        tree->SetLeafOutput(i, outputs[i] / n_nozeroworker_perleaf[i]);
      }
    }
  }
}

Guolin Ke's avatar
Guolin Ke committed
771
}  // namespace LightGBM