use super::binary_log_loss::BinaryLogLoss;
use super::link::Link;
use super::objective::Objective;
use super::squared_error::SquaredError;
use crate::numeric::sum_in_order;
pub(crate) trait BoostingObjective: Objective {
const ARTIFACT_OBJECTIVE_TAG: u32;
fn node_hessian_total(weight: f64, hessian_sum: f64) -> f64;
fn negative_gradient_and_curvature(raw: f64, target: f64) -> (f64, f64) {
(
Self::negative_gradient(raw, target),
Self::gradient_and_curvature(raw, target).1,
)
}
}
impl BoostingObjective for SquaredError {
const ARTIFACT_OBJECTIVE_TAG: u32 = 1;
fn node_hessian_total(weight: f64, _hessian_sum: f64) -> f64 {
constant_hessian_total::<Self>(weight)
}
}
impl BoostingObjective for BinaryLogLoss {
const ARTIFACT_OBJECTIVE_TAG: u32 = 2;
fn node_hessian_total(_weight: f64, hessian_sum: f64) -> f64 {
hessian_sum
}
fn negative_gradient_and_curvature(raw: f64, target: f64) -> (f64, f64) {
let probability = <Self as Objective>::Link::inverse(raw);
(
target - probability,
(probability * (1.0 - probability)).max(Self::CURVATURE_FLOOR),
)
}
}
#[inline]
pub(crate) fn negative_gradient_sum(
samples: &[usize],
negative_gradients: &[f32],
sample_weights: Option<&[f32]>,
) -> f64 {
weighted_sample_sum(samples, negative_gradients, sample_weights)
}
#[inline]
pub(crate) fn hessian_sum(
samples: &[usize],
hessians: &[f32],
sample_weights: Option<&[f32]>,
) -> f64 {
weighted_sample_sum(samples, hessians, sample_weights)
}
#[inline]
fn weighted_sample_sum(samples: &[usize], values: &[f32], sample_weights: Option<&[f32]>) -> f64 {
match sample_weights {
None => sum_in_order(samples.iter().map(|&sample| f64::from(values[sample]))),
Some(weights) => sum_in_order(
samples
.iter()
.map(|&sample| f64::from(weights[sample]) * f64::from(values[sample])),
),
}
}
pub(crate) fn constant_hessian_total<O: Objective>(weight: f64) -> f64 {
const {
assert!(
O::CONSTANT_HESSIAN,
"a per-sample hessian cannot be recovered from a weight total"
);
}
weight * O::hessian(0.0, 0.0)
}
#[inline]
pub(crate) fn newton_leaf_value(
negative_gradient_sum: f64,
hessian_total: f64,
l2_regularization: f32,
) -> f32 {
(negative_gradient_sum / (hessian_total + f64::from(l2_regularization))) as f32
}
#[inline]
pub(crate) fn newton_split_score(
negative_gradient_sum: f64,
hessian_total: f64,
l2_regularization: f32,
) -> f64 {
negative_gradient_sum * negative_gradient_sum / (hessian_total + f64::from(l2_regularization))
}
#[cfg(test)]
mod tests {
use super::*;
use crate::loss::{BinaryLogLoss, SquaredError};
use crate::numeric::sigmoid_f64;
#[test]
fn a_constant_hessian_total_is_the_weight_total_for_squared_error() {
for weight in [0.0_f64, 1.0, 7.0, 1_000_000.0, 2.5] {
assert_eq!(
constant_hessian_total::<SquaredError>(weight).to_bits(),
weight.to_bits()
);
}
}
#[test]
fn the_leaf_value_is_the_regularized_mean_of_the_negative_gradients() {
let negative_gradients = [2.0_f32, 4.0, -3.0, 9.0];
let samples = [0_usize, 1, 2];
let sum = negative_gradient_sum(&samples, &negative_gradients, None);
assert_eq!(sum, 3.0);
let total = constant_hessian_total::<SquaredError>(samples.len() as f64);
assert_eq!(newton_leaf_value(sum, total, 0.0), 1.0);
assert_eq!(newton_leaf_value(sum, total, 3.0), 0.5);
}
#[test]
fn an_exactly_balanced_leaf_keeps_a_positively_signed_zero() {
let negative_gradients = [1.5_f32, -1.5];
let samples = [0_usize, 1];
let sum = negative_gradient_sum(&samples, &negative_gradients, None);
let value = newton_leaf_value(sum, constant_hessian_total::<SquaredError>(2.0), 0.0);
assert_eq!(value, 0.0);
assert!(value.is_sign_positive());
}
#[test]
fn a_split_that_separates_the_gradients_scores_above_its_parent() {
let negative_gradients = [-2.0_f32, -2.0, 3.0, 3.0];
let all = [0_usize, 1, 2, 3];
let left = [0_usize, 1];
let right = [2_usize, 3];
let score = |samples: &[usize]| {
newton_split_score(
negative_gradient_sum(samples, &negative_gradients, None),
constant_hessian_total::<SquaredError>(samples.len() as f64),
0.0,
)
};
assert!(score(&left) + score(&right) > score(&all));
let uniform = [1.0_f32, 1.0, 1.0, 1.0];
let flat = |samples: &[usize]| {
newton_split_score(
negative_gradient_sum(samples, &uniform, None),
constant_hessian_total::<SquaredError>(samples.len() as f64),
0.0,
)
};
assert_eq!(flat(&left) + flat(&right), flat(&all));
}
#[test]
fn a_sample_weight_scales_a_gradient_like_repeating_its_row() {
let negative_gradients = [2.0_f32, 4.0, -3.0];
let samples = [0_usize, 1, 2];
let unweighted = negative_gradient_sum(&samples, &negative_gradients, None);
assert_eq!(
negative_gradient_sum(&samples, &negative_gradients, Some(&[1.0, 1.0, 1.0])).to_bits(),
unweighted.to_bits()
);
let repeated = [0_usize, 1, 1, 1, 2];
assert_eq!(
negative_gradient_sum(&samples, &negative_gradients, Some(&[1.0, 3.0, 1.0])),
negative_gradient_sum(&repeated, &negative_gradients, None)
);
assert_eq!(
negative_gradient_sum(&samples, &negative_gradients, Some(&[1.0, 0.0, 1.0])),
negative_gradient_sum(&[0_usize, 2], &negative_gradients, None)
);
}
#[test]
fn every_objective_has_its_own_permanent_artifact_name() {
assert_eq!(SquaredError::ARTIFACT_OBJECTIVE_TAG, 1);
assert_ne!(
SquaredError::ARTIFACT_OBJECTIVE_TAG,
BinaryLogLoss::ARTIFACT_OBJECTIVE_TAG
);
assert_ne!(SquaredError::ARTIFACT_OBJECTIVE_TAG, 0);
assert_ne!(BinaryLogLoss::ARTIFACT_OBJECTIVE_TAG, 0);
}
#[test]
fn each_objective_forms_its_denominator_from_the_statistic_it_declares() {
for weight in [0.0_f64, 1.0, 7.5, 4096.0] {
for hessian in [0.0_f64, 0.25, 3.5] {
assert_eq!(
SquaredError::node_hessian_total(weight, hessian).to_bits(),
weight.to_bits(),
"squared error must ignore a hessian sum"
);
assert_eq!(
BinaryLogLoss::node_hessian_total(weight, hessian).to_bits(),
hessian.to_bits(),
"log loss must ignore a weight total"
);
}
}
}
#[test]
fn a_log_loss_leaf_divides_by_the_accumulated_curvature() {
let raws = [-2.0_f64, 0.0, 1.5, 3.0];
let targets = [1.0_f64, 0.0, 1.0, 1.0];
let negative_gradients = raws
.iter()
.zip(targets)
.map(|(&raw, target)| BinaryLogLoss::negative_gradient(raw, target) as f32)
.collect::<Vec<_>>();
let hessians = raws
.iter()
.map(|&raw| BinaryLogLoss::hessian(raw, 0.0) as f32)
.collect::<Vec<_>>();
let samples = [0_usize, 1, 2, 3];
let gradient = negative_gradient_sum(&samples, &negative_gradients, None);
let curvature = hessian_sum(&samples, &hessians, None);
assert_eq!(
BinaryLogLoss::node_hessian_total(samples.len() as f64, curvature),
curvature
);
let expected_gradient = raws
.iter()
.zip(targets)
.map(|(&raw, target)| target - sigmoid_f64(raw))
.fold(-0.0_f64, |sum, term| sum + f64::from(term as f32));
let expected_curvature = raws
.iter()
.map(|&raw| sigmoid_f64(raw) * (1.0 - sigmoid_f64(raw)))
.fold(-0.0_f64, |sum, term| sum + f64::from(term as f32));
assert_eq!(gradient.to_bits(), expected_gradient.to_bits());
assert_eq!(curvature.to_bits(), expected_curvature.to_bits());
assert_eq!(
newton_leaf_value(gradient, curvature, 0.0),
(expected_gradient / expected_curvature) as f32
);
}
#[test]
fn a_sample_weight_scales_a_hessian_like_repeating_its_row() {
let hessians = [0.25_f32, 0.1875, 0.09];
let samples = [0_usize, 1, 2];
assert_eq!(
hessian_sum(&samples, &hessians, Some(&[1.0, 1.0, 1.0])).to_bits(),
hessian_sum(&samples, &hessians, None).to_bits()
);
assert_eq!(
hessian_sum(&samples, &hessians, Some(&[1.0, 3.0, 1.0])),
hessian_sum(&[0_usize, 1, 1, 1, 2], &hessians, None)
);
assert_eq!(
hessian_sum(&samples, &hessians, Some(&[1.0, 0.0, 1.0])),
hessian_sum(&[0_usize, 2], &hessians, None)
);
}
#[test]
fn regularization_shrinks_a_leaf_toward_zero_without_changing_its_sign() {
let negative_gradients = [-6.0_f32, -6.0];
let samples = [0_usize, 1];
let sum = negative_gradient_sum(&samples, &negative_gradients, None);
let total = constant_hessian_total::<SquaredError>(samples.len() as f64);
let plain = newton_leaf_value(sum, total, 0.0);
let shrunk = newton_leaf_value(sum, total, 2.0);
assert!(shrunk > plain && shrunk < 0.0);
}
}