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

SerialTreeLearner::~SerialTreeLearner() {
}

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

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

wxchan's avatar
wxchan committed
57
  // initialize splits for leaf
Guolin Ke's avatar
Guolin Ke committed
58
59
  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
60
61

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

  GetMultiValBin(train_data_, true);

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

79
80
81
82
83
84
85
86
87
88
89
90
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
91
92
93
void SerialTreeLearner::ResetTrainingData(const Dataset* train_data) {
  train_data_ = train_data;
  num_data_ = train_data_->num_data();
Guolin Ke's avatar
Guolin Ke committed
94
  CHECK(num_features_ == train_data_->num_features());
Guolin Ke's avatar
Guolin Ke committed
95
96
97
98
99
100
101
102

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

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

103
104
  GetMultiValBin(train_data_, false);

Guolin Ke's avatar
Guolin Ke committed
105
106
107
  // initialize ordered gradients and hessians
  ordered_gradients_.resize(num_data_);
  ordered_hessians_.resize(num_data_);
108

109
110
111
  if (cegb_ != nullptr) {
    cegb_->Init();
  }
Guolin Ke's avatar
Guolin Ke committed
112
}
Guolin Ke's avatar
Guolin Ke committed
113

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

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

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

Guolin Ke's avatar
Guolin Ke committed
152
153
  // some initial works before training
  BeforeTrain();
Guolin Ke's avatar
Guolin Ke committed
154

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

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

Guolin Ke's avatar
Guolin Ke committed
178
179
180
181
182
183
    // 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
184
      Log::Warning("No further splits with positive gain, best gain: %f", best_leaf_SplitInfo.gain);
Guolin Ke's avatar
Guolin Ke committed
185
186
187
      break;
    }
    // split tree with best leaf
Guolin Ke's avatar
Guolin Ke committed
188
    Split(tree.get(), best_leaf, &left_leaf, &right_leaf);
189
    cur_depth = std::max(cur_depth, tree->leaf_depth(left_leaf));
Guolin Ke's avatar
Guolin Ke committed
190
  }
191
  Log::Debug("Trained a tree with leaves = %d and max_depth = %d", tree->num_leaves(), cur_depth);
Guolin Ke's avatar
Guolin Ke committed
192
  return tree.release();
Guolin Ke's avatar
Guolin Ke committed
193
194
}

195
Tree* SerialTreeLearner::FitByExistingTree(const Tree* old_tree, const score_t* gradients, const score_t *hessians) const {
Guolin Ke's avatar
Guolin Ke committed
196
197
  auto tree = std::unique_ptr<Tree>(new Tree(*old_tree));
  CHECK(data_partition_->num_leaves() >= tree->num_leaves());
198
  OMP_INIT_EX();
Guolin Ke's avatar
Guolin Ke committed
199
  #pragma omp parallel for schedule(static)
200
  for (int i = 0; i < tree->num_leaves(); ++i) {
201
    OMP_LOOP_EX_BEGIN();
Guolin Ke's avatar
Guolin Ke committed
202
203
204
    data_size_t cnt_leaf_data = 0;
    auto tmp_idx = data_partition_->GetIndexOnLeaf(i, &cnt_leaf_data);
    double sum_grad = 0.0f;
205
    double sum_hess = kEpsilon;
Guolin Ke's avatar
Guolin Ke committed
206
207
208
209
210
211
    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
212
                                                                  config_->lambda_l1, config_->lambda_l2, config_->max_delta_step);
Guolin Ke's avatar
Guolin Ke committed
213
214
215
    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);
216
    OMP_LOOP_EX_END();
Guolin Ke's avatar
Guolin Ke committed
217
  }
218
  OMP_THROW_EX();
Guolin Ke's avatar
Guolin Ke committed
219
220
221
  return tree.release();
}

222
223
224
225
226
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);
}

227
std::vector<int8_t> SerialTreeLearner::GetUsedFeatures(bool is_tree_level) {
228
  std::vector<int8_t> ret(num_features_, 1);
229
230
231
232
  if (config_->feature_fraction >= 1.0f && is_tree_level) {
    return ret;
  }
  if (config_->feature_fraction_bynode >= 1.0f && !is_tree_level) {
233
234
235
    return ret;
  }
  std::memset(ret.data(), 0, sizeof(int8_t) * num_features_);
236
  const int min_used_features = std::min(2, static_cast<int>(valid_feature_indices_.size()));
237
  if (is_tree_level) {
238
239
    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);
240
241
242
243
244
245
246
247
248
    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
249
  } else if (used_feature_indices_.size() <= 0) {
250
251
    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);
252
253
254
255
256
257
258
259
260
261
    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 {
262
263
    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);
264
265
266
267
268
269
270
271
272
    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;
    }
273
274
275
276
  }
  return ret;
}

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

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

Guolin Ke's avatar
Guolin Ke committed
291
292
293
294
  // initialize data partition
  data_partition_->Init();

  // reset the splits for leaves
Guolin Ke's avatar
Guolin Ke committed
295
  for (int i = 0; i < config_->num_leaves; ++i) {
Guolin Ke's avatar
Guolin Ke committed
296
297
298
299
300
301
302
    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
303

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

  larger_leaf_splits_->Init();
}

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

Guolin Ke's avatar
Guolin Ke committed
354
355
void SerialTreeLearner::FindBestSplits() {
  std::vector<int8_t> is_feature_used(num_features_, 0);
356
  #pragma omp parallel for schedule(static, 1024) if (num_features_ >= 2048)
Guolin Ke's avatar
Guolin Ke committed
357
358
359
360
361
362
363
364
365
366
367
368
369
370
  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);
}

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

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

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

Guolin Ke's avatar
Guolin Ke committed
433
    if (use_subtract) {
434
435
      larger_leaf_histogram_array_[feature_index].Subtract(smaller_leaf_histogram_array_[feature_index]);
    } else {
Guolin Ke's avatar
Guolin Ke committed
436
      train_data_->FixHistogram(feature_index, larger_leaf_splits_->sum_gradients(), larger_leaf_splits_->sum_hessians(),
Guolin Ke's avatar
Guolin Ke committed
437
                                larger_leaf_histogram_array_[feature_index].RawData());
438
    }
Guolin Ke's avatar
Guolin Ke committed
439
    SplitInfo larger_split;
Guolin Ke's avatar
Guolin Ke committed
440
    // find best threshold for larger child
Guolin Ke's avatar
Guolin Ke committed
441
442
443
444
    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
445
446
      larger_leaf_splits_->min_constraint(),
      larger_leaf_splits_->max_constraint(),
Guolin Ke's avatar
Guolin Ke committed
447
      &larger_split);
448
    larger_split.feature = real_fidx;
449
450
    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);
451
    }
452
    if (larger_split > larger_best[tid] && larger_node_used_features[feature_index]) {
Guolin Ke's avatar
Guolin Ke committed
453
      larger_best[tid] = larger_split;
Guolin Ke's avatar
Guolin Ke committed
454
    }
455
    OMP_LOOP_EX_END();
Guolin Ke's avatar
Guolin Ke committed
456
  }
457
  OMP_THROW_EX();
Guolin Ke's avatar
Guolin Ke committed
458
459
460
461
462
463
464
465
466
467
468
  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
469
int32_t SerialTreeLearner::ForceSplits(Tree* tree, const Json& forced_split_json, int* left_leaf,
470
                                       int* right_leaf, int *cur_depth,
471
472
473
474
475
476
477
478
479
480
                                       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));
481
  while (!q.empty()) {
482
483
484
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
    // 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),
559
560
                                static_cast<double>(current_split_info.left_sum_hessian),
                                static_cast<double>(current_split_info.right_sum_hessian),
561
562
563
564
565
566
567
568
569
570
571
572
573
574
575
576
577
578
579
580
581
582
583
584
585
586
587
                                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),
588
589
                                           static_cast<double>(current_split_info.left_sum_hessian),
                                           static_cast<double>(current_split_info.right_sum_hessian),
590
591
592
593
594
595
596
597
598
599
600
601
602
603
604
605
606
607
608
609
610
611
612
613
614
615
616
                                           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"];
617
618
619
      if (left.object_items().count("feature") > 0 && left.object_items().count("threshold") > 0) {
        q.push(std::make_pair(left, *left_leaf));
      }
620
621
622
    }
    if ((pair.first).object_items().count("right") > 0) {
      right = (pair.first)["right"];
623
624
625
      if (right.object_items().count("feature") > 0 && right.object_items().count("threshold") > 0) {
        q.push(std::make_pair(right, *right_leaf));
      }
626
627
628
629
630
631
    }
    result_count++;
    *(cur_depth) = std::max(*(cur_depth), tree->leaf_depth(*left_leaf));
  }
  return result_count;
}
Guolin Ke's avatar
Guolin Ke committed
632

633
void SerialTreeLearner::Split(Tree* tree, int best_leaf, int* left_leaf, int* right_leaf) {
634
635
  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
636
  const int inner_feature_index = train_data_->InnerFeatureIndex(best_split_info.feature);
637
638
  if (cegb_ != nullptr) {
    cegb_->UpdateLeafBestSplits(tree, best_leaf, &best_split_info, &best_split_per_leaf_);
639
  }
640
  *left_leaf = best_leaf;
641
642
  auto next_leaf_id = tree->NextLeafId();

Guolin Ke's avatar
Guolin Ke committed
643
644
  bool is_numerical_split = train_data_->FeatureBinMapper(inner_feature_index)->bin_type() == BinType::NumericalBin;
  if (is_numerical_split) {
645
    auto threshold_double = train_data_->RealThreshold(inner_feature_index, best_split_info.threshold);
646
647
648
649
    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);
650
651
    // split tree, will return right leaf
    *right_leaf = tree->Split(best_leaf,
652
653
654
655
656
657
658
659
660
661
662
663
664
      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);
665
  } else {
666
667
668
669
670
671
    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);
672

673
    data_partition_->Split(best_leaf, train_data_, inner_feature_index,
674
675
676
677
678
679
680
681
682
683
684
685
686
687
688
689
690
691
692
693
694
695
      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);
696

Guolin Ke's avatar
Guolin Ke committed
697
698
  auto p_left = smaller_leaf_splits_.get();
  auto p_right = larger_leaf_splits_.get();
Guolin Ke's avatar
Guolin Ke committed
699
700
  // init the leaves that used on next iteration
  if (best_split_info.left_count < best_split_info.right_count) {
701
    CHECK(best_split_info.left_count > 0);
Guolin Ke's avatar
Guolin Ke committed
702
703
    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
704
  } else {
705
    CHECK(best_split_info.right_count > 0);
Guolin Ke's avatar
Guolin Ke committed
706
707
    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
708
709
710
711
712
713
714
715
716
717
718
719
720
721
    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
722
723
724
  }
}

Guolin Ke's avatar
Guolin Ke committed
725

726
void SerialTreeLearner::RenewTreeOutput(Tree* tree, const ObjectiveFunction* obj, std::function<double(const label_t*, int)> residual_getter,
727
728
729
730
731
732
733
734
                                        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
735
    std::vector<int> n_nozeroworker_perleaf(tree->num_leaves(), 1);
736
    int num_machines = Network::num_machines();
737
738
739
740
741
    #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
742
743
      if (cnt_leaf_data > 0) {
        // bag_mapper[index_mapper[i]]
744
        const double new_output = obj->RenewTreeOutput(output, residual_getter, index_mapper, bag_mapper, cnt_leaf_data);
Guolin Ke's avatar
Guolin Ke committed
745
746
747
748
749
750
751
752
753
754
755
756
        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
757
758
      outputs = Network::GlobalSum(&outputs);
      n_nozeroworker_perleaf = Network::GlobalSum(&n_nozeroworker_perleaf);
Guolin Ke's avatar
Guolin Ke committed
759
760
761
762
763
764
765
      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
766
}  // namespace LightGBM