in src/treelearner/feature_histogram.hpp [858:1083]
void FindBestThresholdSequentially(double sum_gradient, double sum_hessian,
data_size_t num_data,
const FeatureConstraint* constraints,
double min_gain_shift, SplitInfo* output,
int rand_threshold, double parent_output) {
const int8_t offset = meta_->offset;
double best_sum_left_gradient = NAN;
double best_sum_left_hessian = NAN;
double best_gain = kMinScore;
data_size_t best_left_count = 0;
uint32_t best_threshold = static_cast<uint32_t>(meta_->num_bin);
const double cnt_factor = num_data / sum_hessian;
BasicConstraint best_right_constraints;
BasicConstraint best_left_constraints;
bool constraint_update_necessary =
USE_MC && constraints->ConstraintDifferentDependingOnThreshold();
if (USE_MC) {
constraints->InitCumulativeConstraints(REVERSE);
}
if (REVERSE) {
double sum_right_gradient = 0.0f;
double sum_right_hessian = kEpsilon;
data_size_t right_count = 0;
int t = meta_->num_bin - 1 - offset - NA_AS_MISSING;
const int t_end = 1 - offset;
// from right to left, and we don't need data in bin0
for (; t >= t_end; --t) {
// need to skip default bin
if (SKIP_DEFAULT_BIN) {
if ((t + offset) == static_cast<int>(meta_->default_bin)) {
continue;
}
}
const auto grad = GET_GRAD(data_, t);
const auto hess = GET_HESS(data_, t);
data_size_t cnt =
static_cast<data_size_t>(Common::RoundInt(hess * cnt_factor));
sum_right_gradient += grad;
sum_right_hessian += hess;
right_count += cnt;
// if data not enough, or sum hessian too small
if (right_count < meta_->config->min_data_in_leaf ||
sum_right_hessian < meta_->config->min_sum_hessian_in_leaf) {
continue;
}
data_size_t left_count = num_data - right_count;
// if data not enough
if (left_count < meta_->config->min_data_in_leaf) {
break;
}
double sum_left_hessian = sum_hessian - sum_right_hessian;
// if sum hessian too small
if (sum_left_hessian < meta_->config->min_sum_hessian_in_leaf) {
break;
}
double sum_left_gradient = sum_gradient - sum_right_gradient;
if (USE_RAND) {
if (t - 1 + offset != rand_threshold) {
continue;
}
}
if (USE_MC && constraint_update_necessary) {
constraints->Update(t + offset);
}
// current split gain
double current_gain = GetSplitGains<USE_MC, USE_L1, USE_MAX_OUTPUT, USE_SMOOTHING>(
sum_left_gradient, sum_left_hessian, sum_right_gradient,
sum_right_hessian, meta_->config->lambda_l1,
meta_->config->lambda_l2, meta_->config->max_delta_step,
constraints, meta_->monotone_type, meta_->config->path_smooth,
left_count, right_count, parent_output);
// gain with split is worse than without split
if (current_gain <= min_gain_shift) {
continue;
}
// mark as able to be split
is_splittable_ = true;
// better split point
if (current_gain > best_gain) {
if (USE_MC) {
best_right_constraints = constraints->RightToBasicConstraint();
best_left_constraints = constraints->LeftToBasicConstraint();
if (best_right_constraints.min > best_right_constraints.max ||
best_left_constraints.min > best_left_constraints.max) {
continue;
}
}
best_left_count = left_count;
best_sum_left_gradient = sum_left_gradient;
best_sum_left_hessian = sum_left_hessian;
// left is <= threshold, right is > threshold. so this is t-1
best_threshold = static_cast<uint32_t>(t - 1 + offset);
best_gain = current_gain;
}
}
} else {
double sum_left_gradient = 0.0f;
double sum_left_hessian = kEpsilon;
data_size_t left_count = 0;
int t = 0;
const int t_end = meta_->num_bin - 2 - offset;
if (NA_AS_MISSING) {
if (offset == 1) {
sum_left_gradient = sum_gradient;
sum_left_hessian = sum_hessian - kEpsilon;
left_count = num_data;
for (int i = 0; i < meta_->num_bin - offset; ++i) {
const auto grad = GET_GRAD(data_, i);
const auto hess = GET_HESS(data_, i);
data_size_t cnt =
static_cast<data_size_t>(Common::RoundInt(hess * cnt_factor));
sum_left_gradient -= grad;
sum_left_hessian -= hess;
left_count -= cnt;
}
t = -1;
}
}
for (; t <= t_end; ++t) {
if (SKIP_DEFAULT_BIN) {
if ((t + offset) == static_cast<int>(meta_->default_bin)) {
continue;
}
}
if (t >= 0) {
sum_left_gradient += GET_GRAD(data_, t);
sum_left_hessian += GET_HESS(data_, t);
left_count += static_cast<data_size_t>(
Common::RoundInt(GET_HESS(data_, t) * cnt_factor));
}
// if data not enough, or sum hessian too small
if (left_count < meta_->config->min_data_in_leaf ||
sum_left_hessian < meta_->config->min_sum_hessian_in_leaf) {
continue;
}
data_size_t right_count = num_data - left_count;
// if data not enough
if (right_count < meta_->config->min_data_in_leaf) {
break;
}
double sum_right_hessian = sum_hessian - sum_left_hessian;
// if sum Hessian too small
if (sum_right_hessian < meta_->config->min_sum_hessian_in_leaf) {
break;
}
double sum_right_gradient = sum_gradient - sum_left_gradient;
if (USE_RAND) {
if (t + offset != rand_threshold) {
continue;
}
}
// current split gain
double current_gain = GetSplitGains<USE_MC, USE_L1, USE_MAX_OUTPUT, USE_SMOOTHING>(
sum_left_gradient, sum_left_hessian, sum_right_gradient,
sum_right_hessian, meta_->config->lambda_l1,
meta_->config->lambda_l2, meta_->config->max_delta_step,
constraints, meta_->monotone_type, meta_->config->path_smooth, left_count,
right_count, parent_output);
// gain with split is worse than without split
if (current_gain <= min_gain_shift) {
continue;
}
// mark as able to be split
is_splittable_ = true;
// better split point
if (current_gain > best_gain) {
if (USE_MC) {
best_right_constraints = constraints->RightToBasicConstraint();
best_left_constraints = constraints->LeftToBasicConstraint();
if (best_right_constraints.min > best_right_constraints.max ||
best_left_constraints.min > best_left_constraints.max) {
continue;
}
}
best_left_count = left_count;
best_sum_left_gradient = sum_left_gradient;
best_sum_left_hessian = sum_left_hessian;
best_threshold = static_cast<uint32_t>(t + offset);
best_gain = current_gain;
}
}
}
if (is_splittable_ && best_gain > output->gain + min_gain_shift) {
// update split information
output->threshold = best_threshold;
output->left_output =
CalculateSplittedLeafOutput<USE_MC, USE_L1, USE_MAX_OUTPUT, USE_SMOOTHING>(
best_sum_left_gradient, best_sum_left_hessian,
meta_->config->lambda_l1, meta_->config->lambda_l2,
meta_->config->max_delta_step, best_left_constraints, meta_->config->path_smooth,
best_left_count, parent_output);
output->left_count = best_left_count;
output->left_sum_gradient = best_sum_left_gradient;
output->left_sum_hessian = best_sum_left_hessian - kEpsilon;
output->right_output =
CalculateSplittedLeafOutput<USE_MC, USE_L1, USE_MAX_OUTPUT, USE_SMOOTHING>(
sum_gradient - best_sum_left_gradient,
sum_hessian - best_sum_left_hessian, meta_->config->lambda_l1,
meta_->config->lambda_l2, meta_->config->max_delta_step,
best_right_constraints, meta_->config->path_smooth, num_data - best_left_count,
parent_output);
output->right_count = num_data - best_left_count;
output->right_sum_gradient = sum_gradient - best_sum_left_gradient;
output->right_sum_hessian =
sum_hessian - best_sum_left_hessian - kEpsilon;
output->gain = best_gain - min_gain_shift;
output->default_left = REVERSE;
}
}