serial_tree_learner.cpp 35.3 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);
Guolin Ke's avatar
Guolin Ke committed
24
25
26
27
28
}

SerialTreeLearner::~SerialTreeLearner() {
}

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

Guolin Ke's avatar
Guolin Ke committed
48
  // push split information for all leaves
Guolin Ke's avatar
Guolin Ke committed
49
  best_split_per_leaf_.resize(config_->num_leaves);
50
  constraints_.reset(new LeafConstraints<ConstraintEntry>(config_->num_leaves));
Guolin Ke's avatar
Guolin Ke committed
51

wxchan's avatar
wxchan committed
52
  // initialize splits for leaf
Guolin Ke's avatar
Guolin Ke committed
53
54
  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
55
56

  // initialize data partition
Guolin Ke's avatar
Guolin Ke committed
57
  data_partition_.reset(new DataPartition(num_data_, config_->num_leaves));
Guolin Ke's avatar
Guolin Ke committed
58
  is_feature_used_.resize(num_features_);
59
  valid_feature_indices_ = train_data_->ValidFeatureIndices();
Guolin Ke's avatar
Guolin Ke committed
60
  // initialize ordered gradients and hessians
Guolin Ke's avatar
Guolin Ke committed
61
62
  ordered_gradients_.resize(num_data_);
  ordered_hessians_.resize(num_data_);
63

64
65
  GetShareStates(train_data_, is_constant_hessian, true);
  histogram_pool_.DynamicChangeSize(train_data_, share_state_->is_colwise, config_, max_cache_size, config_->num_leaves);
66
  Log::Info("Number of data points in the train set: %d, number of used features: %d", num_data_, num_features_);
67
68
69
  if (CostEfficientGradientBoosting::IsEnable(config_)) {
    cegb_.reset(new CostEfficientGradientBoosting(this));
    cegb_->Init();
70
  }
Guolin Ke's avatar
Guolin Ke committed
71
72
}

73
74
75
void SerialTreeLearner::GetShareStates(const Dataset* dataset,
                                       bool is_constant_hessian,
                                       bool is_first_time) {
76
77
  if (is_first_time) {
    auto used_feature = GetUsedFeatures(true);
78
79
80
    share_state_.reset(dataset->GetShareStates(
        ordered_gradients_.data(), ordered_hessians_.data(), used_feature,
        is_constant_hessian, config_->force_col_wise, config_->force_row_wise));
81
  } else {
82
    CHECK(share_state_ != nullptr);
83
    // cannot change is_hist_col_wise during training
84
85
86
87
    share_state_.reset(dataset->GetShareStates(
        ordered_gradients_.data(), ordered_hessians_.data(), is_feature_used_,
        is_constant_hessian, share_state_->is_colwise,
        !share_state_->is_colwise));
88
  }
89
  CHECK(share_state_ != nullptr);
90
91
}

92
93
94
void SerialTreeLearner::ResetTrainingDataInner(const Dataset* train_data,
                                               bool is_constant_hessian,
                                               bool reset_multi_val_bin) {
Guolin Ke's avatar
Guolin Ke committed
95
96
  train_data_ = train_data;
  num_data_ = train_data_->num_data();
97
  CHECK_EQ(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
108
  if (reset_multi_val_bin) {
    GetShareStates(train_data_, is_constant_hessian, false);
  }
109

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

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

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

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

151
Tree* SerialTreeLearner::Train(const score_t* gradients, const score_t *hessians, const Json& forced_split_json) {
152
  Common::FunctionTimer fun_timer("SerialTreeLearner::Train", global_timer);
Guolin Ke's avatar
Guolin Ke committed
153
154
  gradients_ = gradients;
  hessians_ = hessians;
155
156
157
158
159
160
161
162
163
  int num_threads = OMP_NUM_THREADS();
  if (share_state_->num_threads != num_threads && share_state_->num_threads > 0){
    Log::Warning(
        "Detect num_threads changed durning traing (from %d to %d), may cause "
        "unexpected errors.",
        share_state_->num_threads, num_threads);
  }
  share_state_->num_threads = num_threads;
  
Guolin Ke's avatar
Guolin Ke committed
164
165
  // some initial works before training
  BeforeTrain();
Guolin Ke's avatar
Guolin Ke committed
166

Guolin Ke's avatar
Guolin Ke committed
167
  auto tree = std::unique_ptr<Tree>(new Tree(config_->num_leaves));
Guolin Ke's avatar
Guolin Ke committed
168
169
  // root leaf
  int left_leaf = 0;
170
  int cur_depth = 1;
Guolin Ke's avatar
Guolin Ke committed
171
172
  // only root leaf can be splitted on first time
  int right_leaf = -1;
173
174
175
176
177
178
179
180

  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
181
  for (int split = init_splits; split < config_->num_leaves - 1; ++split) {
Guolin Ke's avatar
Guolin Ke committed
182
    // some initial works before finding best split
183
    if (!aborted_last_force_split && BeforeFindBestSplit(tree.get(), left_leaf, right_leaf)) {
Guolin Ke's avatar
Guolin Ke committed
184
      // find best threshold for every feature
Guolin Ke's avatar
Guolin Ke committed
185
      FindBestSplits();
186
187
    } else if (aborted_last_force_split) {
      aborted_last_force_split = false;
Guolin Ke's avatar
Guolin Ke committed
188
    }
189

Guolin Ke's avatar
Guolin Ke committed
190
191
192
193
194
195
    // 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
196
      Log::Warning("No further splits with positive gain, best gain: %f", best_leaf_SplitInfo.gain);
Guolin Ke's avatar
Guolin Ke committed
197
198
199
      break;
    }
    // split tree with best leaf
Guolin Ke's avatar
Guolin Ke committed
200
    Split(tree.get(), best_leaf, &left_leaf, &right_leaf);
201
    cur_depth = std::max(cur_depth, tree->leaf_depth(left_leaf));
Guolin Ke's avatar
Guolin Ke committed
202
  }
203
  Log::Debug("Trained a tree with leaves = %d and max_depth = %d", tree->num_leaves(), cur_depth);
Guolin Ke's avatar
Guolin Ke committed
204
  return tree.release();
Guolin Ke's avatar
Guolin Ke committed
205
206
}

207
Tree* SerialTreeLearner::FitByExistingTree(const Tree* old_tree, const score_t* gradients, const score_t *hessians) const {
Guolin Ke's avatar
Guolin Ke committed
208
209
  auto tree = std::unique_ptr<Tree>(new Tree(*old_tree));
  CHECK(data_partition_->num_leaves() >= tree->num_leaves());
210
  OMP_INIT_EX();
Guolin Ke's avatar
Guolin Ke committed
211
  #pragma omp parallel for schedule(static)
212
  for (int i = 0; i < tree->num_leaves(); ++i) {
213
    OMP_LOOP_EX_BEGIN();
Guolin Ke's avatar
Guolin Ke committed
214
215
216
    data_size_t cnt_leaf_data = 0;
    auto tmp_idx = data_partition_->GetIndexOnLeaf(i, &cnt_leaf_data);
    double sum_grad = 0.0f;
217
    double sum_hess = kEpsilon;
Guolin Ke's avatar
Guolin Ke committed
218
219
220
221
222
223
    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
224
                                                                  config_->lambda_l1, config_->lambda_l2, config_->max_delta_step);
Guolin Ke's avatar
Guolin Ke committed
225
226
227
    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);
228
    OMP_LOOP_EX_END();
Guolin Ke's avatar
Guolin Ke committed
229
  }
230
  OMP_THROW_EX();
Guolin Ke's avatar
Guolin Ke committed
231
232
233
  return tree.release();
}

234
235
236
237
238
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);
}

239
std::vector<int8_t> SerialTreeLearner::GetUsedFeatures(bool is_tree_level) {
240
  std::vector<int8_t> ret(num_features_, 1);
241
242
243
244
  if (config_->feature_fraction >= 1.0f && is_tree_level) {
    return ret;
  }
  if (config_->feature_fraction_bynode >= 1.0f && !is_tree_level) {
245
246
247
    return ret;
  }
  std::memset(ret.data(), 0, sizeof(int8_t) * num_features_);
248
  const int min_used_features = std::min(2, static_cast<int>(valid_feature_indices_.size()));
249
  if (is_tree_level) {
250
251
    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);
252
253
254
255
256
257
    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);
258
      CHECK_GE(inner_feature_index, 0);
259
260
      ret[inner_feature_index] = 1;
    }
Guolin Ke's avatar
Guolin Ke committed
261
  } else if (used_feature_indices_.size() <= 0) {
262
263
    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);
264
265
266
267
268
269
    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);
270
      CHECK_GE(inner_feature_index, 0);
271
272
273
      ret[inner_feature_index] = 1;
    }
  } else {
274
275
    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);
276
277
278
279
280
281
    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);
282
      CHECK_GE(inner_feature_index, 0);
283
284
      ret[inner_feature_index] = 1;
    }
285
286
287
288
  }
  return ret;
}

Guolin Ke's avatar
Guolin Ke committed
289
void SerialTreeLearner::BeforeTrain() {
290
  Common::FunctionTimer fun_timer("SerialTreeLearner::BeforeTrain", global_timer);
291
292
  // reset histogram pool
  histogram_pool_.ResetMap();
Guolin Ke's avatar
Guolin Ke committed
293

294
295
  if (config_->feature_fraction < 1.0f) {
    is_feature_used_ = GetUsedFeatures(true);
Guolin Ke's avatar
Guolin Ke committed
296
  } else {
Guolin Ke's avatar
Guolin Ke committed
297
    #pragma omp parallel for schedule(static, 512) if (num_features_ >= 1024)
Guolin Ke's avatar
Guolin Ke committed
298
299
300
    for (int i = 0; i < num_features_; ++i) {
      is_feature_used_[i] = 1;
    }
Guolin Ke's avatar
Guolin Ke committed
301
  }
302
  train_data_->InitTrain(is_feature_used_, share_state_.get());
Guolin Ke's avatar
Guolin Ke committed
303
304
305
  // initialize data partition
  data_partition_->Init();

306
307
  constraints_->Reset();

Guolin Ke's avatar
Guolin Ke committed
308
  // reset the splits for leaves
Guolin Ke's avatar
Guolin Ke committed
309
  for (int i = 0; i < config_->num_leaves; ++i) {
Guolin Ke's avatar
Guolin Ke committed
310
311
312
313
314
315
316
    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
317

Guolin Ke's avatar
Guolin Ke committed
318
319
  } else {
    // use bagging, only use part of data
Guolin Ke's avatar
Guolin Ke committed
320
    smaller_leaf_splits_->Init(0, data_partition_.get(), gradients_, hessians_);
Guolin Ke's avatar
Guolin Ke committed
321
322
323
324
325
  }

  larger_leaf_splits_->Init();
}

Guolin Ke's avatar
Guolin Ke committed
326
bool SerialTreeLearner::BeforeFindBestSplit(const Tree* tree, int left_leaf, int right_leaf) {
327
  Common::FunctionTimer fun_timer("SerialTreeLearner::BeforeFindBestSplit", global_timer);
Guolin Ke's avatar
Guolin Ke committed
328
  // check depth of current leaf
Guolin Ke's avatar
Guolin Ke committed
329
  if (config_->max_depth > 0) {
Guolin Ke's avatar
Guolin Ke committed
330
    // only need to check left leaf, since right leaf is in same level of left leaf
Guolin Ke's avatar
Guolin Ke committed
331
    if (tree->leaf_depth(left_leaf) >= config_->max_depth) {
Guolin Ke's avatar
Guolin Ke committed
332
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;
    }
  }
Guolin Ke's avatar
Guolin Ke committed
339
340
341
  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
342
343
  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
344
345
346
347
348
349
    best_split_per_leaf_[left_leaf].gain = kMinScore;
    if (right_leaf >= 0) {
      best_split_per_leaf_[right_leaf].gain = kMinScore;
    }
    return false;
  }
350
  parent_leaf_histogram_array_ = nullptr;
Guolin Ke's avatar
Guolin Ke committed
351
352
  // only have root
  if (right_leaf < 0) {
353
    histogram_pool_.Get(left_leaf, &smaller_leaf_histogram_array_);
Guolin Ke's avatar
Guolin Ke committed
354
355
    larger_leaf_histogram_array_ = nullptr;
  } else if (num_data_in_left_child < num_data_in_right_child) {
Hui Xue's avatar
Hui Xue committed
356
    // put parent(left) leaf's histograms into larger leaf's histograms
357
358
359
    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
360
  } else {
Hui Xue's avatar
Hui Xue committed
361
    // put parent(left) leaf's histograms to larger leaf's histograms
362
363
    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
364
365
366
367
  }
  return true;
}

Guolin Ke's avatar
Guolin Ke committed
368
369
void SerialTreeLearner::FindBestSplits() {
  std::vector<int8_t> is_feature_used(num_features_, 0);
370
  #pragma omp parallel for schedule(static, 1024) if (num_features_ >= 2048)
Guolin Ke's avatar
Guolin Ke committed
371
372
373
374
375
376
377
378
379
380
381
382
383
384
  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);
}

385
386
387
388
void SerialTreeLearner::ConstructHistograms(
    const std::vector<int8_t>& is_feature_used, bool use_subtract) {
  Common::FunctionTimer fun_timer("SerialTreeLearner::ConstructHistograms",
                                  global_timer);
Guolin Ke's avatar
Guolin Ke committed
389
  // construct smaller leaf
390
391
  hist_t* ptr_smaller_leaf_hist_data =
      smaller_leaf_histogram_array_[0].RawData() - kHistOffset;
392
393
394
  train_data_->ConstructHistograms(
      is_feature_used, smaller_leaf_splits_->data_indices(),
      smaller_leaf_splits_->num_data_in_leaf(), gradients_, hessians_,
395
396
      ordered_gradients_.data(), ordered_hessians_.data(), share_state_.get(),
      ptr_smaller_leaf_hist_data);
Guolin Ke's avatar
Guolin Ke committed
397
398
399

  if (larger_leaf_histogram_array_ != nullptr && !use_subtract) {
    // construct larger leaf
400
401
    hist_t* ptr_larger_leaf_hist_data =
        larger_leaf_histogram_array_[0].RawData() - kHistOffset;
402
403
404
    train_data_->ConstructHistograms(
        is_feature_used, larger_leaf_splits_->data_indices(),
        larger_leaf_splits_->num_data_in_leaf(), gradients_, hessians_,
405
        ordered_gradients_.data(), ordered_hessians_.data(), share_state_.get(),
406
        ptr_larger_leaf_hist_data);
Guolin Ke's avatar
Guolin Ke committed
407
  }
408
409
}

Guolin Ke's avatar
Guolin Ke committed
410
411
412
413
void SerialTreeLearner::FindBestSplitsFromHistograms(
    const std::vector<int8_t>& is_feature_used, bool use_subtract) {
  Common::FunctionTimer fun_timer(
      "SerialTreeLearner::FindBestSplitsFromHistograms", global_timer);
414
415
  std::vector<SplitInfo> smaller_best(share_state_->num_threads);
  std::vector<SplitInfo> larger_best(share_state_->num_threads);
416
417
  std::vector<int8_t> smaller_node_used_features(num_features_, 1);
  std::vector<int8_t> larger_node_used_features(num_features_, 1);
418
419
420
  if (config_->feature_fraction_bynode < 1.0f) {
    smaller_node_used_features = GetUsedFeatures(false);
    larger_node_used_features = GetUsedFeatures(false);
421
  }
422
  OMP_INIT_EX();
Guolin Ke's avatar
Guolin Ke committed
423
424
// find splits
#pragma omp parallel for schedule(static)
Guolin Ke's avatar
Guolin Ke committed
425
  for (int feature_index = 0; feature_index < num_features_; ++feature_index) {
426
    OMP_LOOP_EX_BEGIN();
Guolin Ke's avatar
Guolin Ke committed
427
428
429
    if (!is_feature_used[feature_index]) {
      continue;
    }
Guolin Ke's avatar
Guolin Ke committed
430
    const int tid = omp_get_thread_num();
Guolin Ke's avatar
Guolin Ke committed
431
432
433
434
    train_data_->FixHistogram(
        feature_index, smaller_leaf_splits_->sum_gradients(),
        smaller_leaf_splits_->sum_hessians(),
        smaller_leaf_histogram_array_[feature_index].RawData());
435
    int real_fidx = train_data_->RealFeatureIndex(feature_index);
436
437
438
439
440
441
442

    ComputeBestSplitForFeature(smaller_leaf_histogram_array_, feature_index,
                               real_fidx,
                               smaller_node_used_features[feature_index],
                               smaller_leaf_splits_->num_data_in_leaf(),
                               smaller_leaf_splits_.get(), &smaller_best[tid]);

Guolin Ke's avatar
Guolin Ke committed
443
    // only has root leaf
Guolin Ke's avatar
Guolin Ke committed
444
445
446
447
    if (larger_leaf_splits_ == nullptr ||
        larger_leaf_splits_->leaf_index() < 0) {
      continue;
    }
Guolin Ke's avatar
Guolin Ke committed
448

Guolin Ke's avatar
Guolin Ke committed
449
    if (use_subtract) {
Guolin Ke's avatar
Guolin Ke committed
450
451
      larger_leaf_histogram_array_[feature_index].Subtract(
          smaller_leaf_histogram_array_[feature_index]);
452
    } else {
Guolin Ke's avatar
Guolin Ke committed
453
454
455
456
      train_data_->FixHistogram(
          feature_index, larger_leaf_splits_->sum_gradients(),
          larger_leaf_splits_->sum_hessians(),
          larger_leaf_histogram_array_[feature_index].RawData());
457
    }
458
459
460
461
462

    ComputeBestSplitForFeature(larger_leaf_histogram_array_, feature_index,
                               real_fidx,
                               larger_node_used_features[feature_index],
                               larger_leaf_splits_->num_data_in_leaf(),
Guolin Ke's avatar
Guolin Ke committed
463
                               larger_leaf_splits_.get(), &larger_best[tid]);
464

465
    OMP_LOOP_EX_END();
Guolin Ke's avatar
Guolin Ke committed
466
  }
467
  OMP_THROW_EX();
Guolin Ke's avatar
Guolin Ke committed
468
  auto smaller_best_idx = ArrayArgs<SplitInfo>::ArgMax(smaller_best);
469
  int leaf = smaller_leaf_splits_->leaf_index();
Guolin Ke's avatar
Guolin Ke committed
470
471
  best_split_per_leaf_[leaf] = smaller_best[smaller_best_idx];

Guolin Ke's avatar
Guolin Ke committed
472
473
  if (larger_leaf_splits_ != nullptr &&
      larger_leaf_splits_->leaf_index() >= 0) {
474
    leaf = larger_leaf_splits_->leaf_index();
Guolin Ke's avatar
Guolin Ke committed
475
476
477
478
479
    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
480
int32_t SerialTreeLearner::ForceSplits(Tree* tree, const Json& forced_split_json, int* left_leaf,
481
                                       int* right_leaf, int *cur_depth,
482
483
484
485
486
487
488
489
490
491
                                       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));
492
  while (!q.empty()) {
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
    // 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;
Guolin Ke's avatar
Guolin Ke committed
560
    auto next_leaf_id = tree->NextLeafId();
561
    if (train_data_->FeatureBinMapper(inner_feature_index)->bin_type() == BinType::NumericalBin) {
Guolin Ke's avatar
Guolin Ke committed
562
563
564
565
566
      data_partition_->Split(current_leaf, train_data_, inner_feature_index,
                             &current_split_info.threshold, 1,
                             current_split_info.default_left, next_leaf_id);
      current_split_info.left_count = data_partition_->leaf_count(*left_leaf);
      current_split_info.right_count = data_partition_->leaf_count(next_leaf_id);
567
568
569
570
571
572
573
574
575
      *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),
576
577
                                static_cast<double>(current_split_info.left_sum_hessian),
                                static_cast<double>(current_split_info.right_sum_hessian),
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);
    } 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);
Guolin Ke's avatar
Guolin Ke committed
591
592
593
594
595
      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, next_leaf_id);
      current_split_info.left_count = data_partition_->leaf_count(*left_leaf);
      current_split_info.right_count = data_partition_->leaf_count(next_leaf_id);
596
597
598
599
600
601
602
603
604
605
606
      *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),
607
608
                                           static_cast<double>(current_split_info.left_sum_hessian),
                                           static_cast<double>(current_split_info.right_sum_hessian),
609
610
611
                                           static_cast<float>(current_split_info.gain),
                                           train_data_->FeatureBinMapper(inner_feature_index)->missing_type());
    }
Guolin Ke's avatar
Guolin Ke committed
612
613
614
    #ifdef DEBUG
    CHECK(*right_leaf == next_leaf_id);
    #endif
615
616
617
618
619
620
621
622
623
624
625
626
627
628
629
630
631
632
633
634
    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"];
635
636
637
      if (left.object_items().count("feature") > 0 && left.object_items().count("threshold") > 0) {
        q.push(std::make_pair(left, *left_leaf));
      }
638
639
640
    }
    if ((pair.first).object_items().count("right") > 0) {
      right = (pair.first)["right"];
641
642
643
      if (right.object_items().count("feature") > 0 && right.object_items().count("threshold") > 0) {
        q.push(std::make_pair(right, *right_leaf));
      }
644
645
646
647
648
649
    }
    result_count++;
    *(cur_depth) = std::max(*(cur_depth), tree->leaf_depth(*left_leaf));
  }
  return result_count;
}
Guolin Ke's avatar
Guolin Ke committed
650

651
void SerialTreeLearner::Split(Tree* tree, int best_leaf, int* left_leaf, int* right_leaf) {
652
653
  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
654
  const int inner_feature_index = train_data_->InnerFeatureIndex(best_split_info.feature);
655
656
  if (cegb_ != nullptr) {
    cegb_->UpdateLeafBestSplits(tree, best_leaf, &best_split_info, &best_split_per_leaf_);
657
  }
658
  *left_leaf = best_leaf;
659
660
  auto next_leaf_id = tree->NextLeafId();

Guolin Ke's avatar
Guolin Ke committed
661
662
  bool is_numerical_split = train_data_->FeatureBinMapper(inner_feature_index)->bin_type() == BinType::NumericalBin;
  if (is_numerical_split) {
663
    auto threshold_double = train_data_->RealThreshold(inner_feature_index, best_split_info.threshold);
664
665
666
667
    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);
668
669
    // split tree, will return right leaf
    *right_leaf = tree->Split(best_leaf,
670
671
672
673
674
675
676
677
678
679
680
681
682
      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);
683
  } else {
684
685
686
687
688
689
    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);
690

691
    data_partition_->Split(best_leaf, train_data_, inner_feature_index,
692
693
694
695
696
697
698
699
700
701
702
703
704
705
706
707
708
709
710
711
712
      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());
  }
713
714

  #ifdef DEBUG
715
  CHECK(*right_leaf == next_leaf_id);
716
  #endif
717

Guolin Ke's avatar
Guolin Ke committed
718
719
  // init the leaves that used on next iteration
  if (best_split_info.left_count < best_split_info.right_count) {
720
    CHECK_GT(best_split_info.left_count, 0);
Guolin Ke's avatar
Guolin Ke committed
721
722
    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
723
  } else {
724
    CHECK_GT(best_split_info.right_count, 0);
Guolin Ke's avatar
Guolin Ke committed
725
726
    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
727
  }
728
729
730
731
  constraints_->UpdateConstraints(
      is_numerical_split, *left_leaf, *right_leaf,
      best_split_info.monotone_type, best_split_info.right_output,
      best_split_info.left_output);
Guolin Ke's avatar
Guolin Ke committed
732
733
}

Guolin Ke's avatar
Guolin Ke committed
734

735
void SerialTreeLearner::RenewTreeOutput(Tree* tree, const ObjectiveFunction* obj, std::function<double(const label_t*, int)> residual_getter,
736
737
738
739
740
                                        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_) {
741
      CHECK_EQ(bag_cnt, num_data_);
742
743
      bag_mapper = bag_indices;
    }
Guolin Ke's avatar
Guolin Ke committed
744
    std::vector<int> n_nozeroworker_perleaf(tree->num_leaves(), 1);
745
    int num_machines = Network::num_machines();
746
747
748
749
750
    #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
751
752
      if (cnt_leaf_data > 0) {
        // bag_mapper[index_mapper[i]]
753
        const double new_output = obj->RenewTreeOutput(output, residual_getter, index_mapper, bag_mapper, cnt_leaf_data);
Guolin Ke's avatar
Guolin Ke committed
754
755
        tree->SetLeafOutput(i, new_output);
      } else {
756
        CHECK_GT(num_machines, 1);
Guolin Ke's avatar
Guolin Ke committed
757
758
759
760
761
762
763
764
765
        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
766
767
      outputs = Network::GlobalSum(&outputs);
      n_nozeroworker_perleaf = Network::GlobalSum(&n_nozeroworker_perleaf);
Guolin Ke's avatar
Guolin Ke committed
768
769
770
771
772
773
774
      for (int i = 0; i < tree->num_leaves(); ++i) {
        tree->SetLeafOutput(i, outputs[i] / n_nozeroworker_perleaf[i]);
      }
    }
  }
}

775
776
777
778
779
780
781
782
783
784
785
786
787
788
789
790
791
792
793
794
795
796
void SerialTreeLearner::ComputeBestSplitForFeature(
    FeatureHistogram* histogram_array_, int feature_index, int real_fidx,
    bool is_feature_used, int num_data, const LeafSplits* leaf_splits,
    SplitInfo* best_split) {
  if (!is_feature_used) {
    return;
  }
  SplitInfo new_split;
  histogram_array_[feature_index].FindBestThreshold(
      leaf_splits->sum_gradients(), leaf_splits->sum_hessians(), num_data,
      constraints_->Get(leaf_splits->leaf_index()), &new_split);
  new_split.feature = real_fidx;
  if (cegb_ != nullptr) {
    new_split.gain -=
        cegb_->DetlaGain(feature_index, real_fidx, leaf_splits->leaf_index(),
                         num_data, new_split);
  }
  if (new_split > *best_split) {
    *best_split = new_split;
  }
}

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