in src/treelearner/feature_histogram.hpp [278:516]
void FindBestThresholdCategoricalInner(double sum_gradient,
double sum_hessian,
data_size_t num_data,
const FeatureConstraint* constraints,
double parent_output,
SplitInfo* output) {
is_splittable_ = false;
output->default_left = false;
double best_gain = kMinScore;
data_size_t best_left_count = 0;
double best_sum_left_gradient = 0;
double best_sum_left_hessian = 0;
double gain_shift;
if (USE_MC) {
constraints->InitCumulativeConstraints(true);
}
if (USE_SMOOTHING) {
gain_shift = GetLeafGainGivenOutput<USE_L1>(
sum_gradient, sum_hessian, meta_->config->lambda_l1, meta_->config->lambda_l2, parent_output);
} else {
// Need special case for no smoothing to preserve existing behaviour. If no smoothing, the parent output is calculated
// with the larger categorical l2, whereas min_split_gain uses the original l2.
gain_shift = GetLeafGain<USE_L1, USE_MAX_OUTPUT, false>(sum_gradient, sum_hessian,
meta_->config->lambda_l1, meta_->config->lambda_l2, meta_->config->max_delta_step, 0,
num_data, 0);
}
double min_gain_shift = gain_shift + meta_->config->min_gain_to_split;
const int8_t offset = meta_->offset;
const int bin_start = 1 - offset;
const int bin_end = meta_->num_bin - offset;
int used_bin = -1;
std::vector<int> sorted_idx;
double l2 = meta_->config->lambda_l2;
bool use_onehot = meta_->num_bin <= meta_->config->max_cat_to_onehot;
int best_threshold = -1;
int best_dir = 1;
const double cnt_factor = num_data / sum_hessian;
int rand_threshold = 0;
if (use_onehot) {
if (USE_RAND) {
if (bin_end - bin_start > 0) {
rand_threshold = meta_->rand.NextInt(bin_start, bin_end);
}
}
for (int t = bin_start; t < bin_end; ++t) {
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));
// if data not enough, or sum hessian too small
if (cnt < meta_->config->min_data_in_leaf ||
hess < meta_->config->min_sum_hessian_in_leaf) {
continue;
}
data_size_t other_count = num_data - cnt;
// if data not enough
if (other_count < meta_->config->min_data_in_leaf) {
continue;
}
double sum_other_hessian = sum_hessian - hess - kEpsilon;
// if sum hessian too small
if (sum_other_hessian < meta_->config->min_sum_hessian_in_leaf) {
continue;
}
double sum_other_gradient = sum_gradient - grad;
if (USE_RAND) {
if (t != rand_threshold) {
continue;
}
}
// current split gain
double current_gain = GetSplitGains<USE_MC, USE_L1, USE_MAX_OUTPUT, USE_SMOOTHING>(
sum_other_gradient, sum_other_hessian, grad, hess + kEpsilon,
meta_->config->lambda_l1, l2, meta_->config->max_delta_step,
constraints, 0, meta_->config->path_smooth, other_count, cnt, 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) {
best_threshold = t;
best_sum_left_gradient = grad;
best_sum_left_hessian = hess + kEpsilon;
best_left_count = cnt;
best_gain = current_gain;
}
}
} else {
for (int i = bin_start; i < bin_end; ++i) {
if (Common::RoundInt(GET_HESS(data_, i) * cnt_factor) >=
meta_->config->cat_smooth) {
sorted_idx.push_back(i);
}
}
used_bin = static_cast<int>(sorted_idx.size());
l2 += meta_->config->cat_l2;
auto ctr_fun = [this](double sum_grad, double sum_hess) {
return (sum_grad) / (sum_hess + meta_->config->cat_smooth);
};
std::stable_sort(
sorted_idx.begin(), sorted_idx.end(), [this, &ctr_fun](int i, int j) {
return ctr_fun(GET_GRAD(data_, i), GET_HESS(data_, i)) <
ctr_fun(GET_GRAD(data_, j), GET_HESS(data_, j));
});
std::vector<int> find_direction(1, 1);
std::vector<int> start_position(1, 0);
find_direction.push_back(-1);
start_position.push_back(used_bin - 1);
const int max_num_cat =
std::min(meta_->config->max_cat_threshold, (used_bin + 1) / 2);
int max_threshold = std::max(std::min(max_num_cat, used_bin) - 1, 0);
if (USE_RAND) {
if (max_threshold > 0) {
rand_threshold = meta_->rand.NextInt(0, max_threshold);
}
}
is_splittable_ = false;
for (size_t out_i = 0; out_i < find_direction.size(); ++out_i) {
auto dir = find_direction[out_i];
auto start_pos = start_position[out_i];
data_size_t min_data_per_group = meta_->config->min_data_per_group;
data_size_t cnt_cur_group = 0;
double sum_left_gradient = 0.0f;
double sum_left_hessian = kEpsilon;
data_size_t left_count = 0;
for (int i = 0; i < used_bin && i < max_num_cat; ++i) {
auto t = sorted_idx[start_pos];
start_pos += dir;
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_left_gradient += grad;
sum_left_hessian += hess;
left_count += cnt;
cnt_cur_group += cnt;
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 (right_count < meta_->config->min_data_in_leaf ||
right_count < min_data_per_group) {
break;
}
double sum_right_hessian = sum_hessian - sum_left_hessian;
if (sum_right_hessian < meta_->config->min_sum_hessian_in_leaf) {
break;
}
if (cnt_cur_group < min_data_per_group) {
continue;
}
cnt_cur_group = 0;
double sum_right_gradient = sum_gradient - sum_left_gradient;
if (USE_RAND) {
if (i != rand_threshold) {
continue;
}
}
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, l2,
meta_->config->max_delta_step, constraints, 0, meta_->config->path_smooth,
left_count, right_count, parent_output);
if (current_gain <= min_gain_shift) {
continue;
}
is_splittable_ = true;
if (current_gain > best_gain) {
best_left_count = left_count;
best_sum_left_gradient = sum_left_gradient;
best_sum_left_hessian = sum_left_hessian;
best_threshold = i;
best_gain = current_gain;
best_dir = dir;
}
}
}
}
if (is_splittable_) {
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, l2, meta_->config->max_delta_step,
constraints->LeftToBasicConstraint(), 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, l2,
meta_->config->max_delta_step, constraints->RightToBasicConstraint(), 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;
if (use_onehot) {
output->num_cat_threshold = 1;
output->cat_threshold =
std::vector<uint32_t>(1, static_cast<uint32_t>(best_threshold + offset));
} else {
output->num_cat_threshold = best_threshold + 1;
output->cat_threshold =
std::vector<uint32_t>(output->num_cat_threshold);
if (best_dir == 1) {
for (int i = 0; i < output->num_cat_threshold; ++i) {
auto t = sorted_idx[i] + offset;
output->cat_threshold[i] = t;
}
} else {
for (int i = 0; i < output->num_cat_threshold; ++i) {
auto t = sorted_idx[used_bin - 1 - i] + offset;
output->cat_threshold[i] = t;
}
}
}
output->monotone_type = 0;
}
}