use crate::api::{Capabilities, Estimator, HasCapabilities, HasParams, ModelError, Regressor};
use crate::data::{BinaryTargets, MatrixView, RegressionTargets};
use super::Calibrator;
#[derive(Clone, Copy, Debug, Default, Eq, PartialEq)]
pub struct IsotonicRegressionParams;
#[derive(Clone, Debug, PartialEq)]
pub struct IsotonicRegression {
thresholds: Vec<f32>,
values: Vec<f32>,
params: IsotonicRegressionParams,
}
impl IsotonicRegression {
pub fn fit(
data: &MatrixView<'_>,
targets: &RegressionTargets,
params: IsotonicRegressionParams,
) -> Result<Self, ModelError> {
validate_univariate(data, targets.len())?;
let scores: Vec<f32> = data.iter_rows().map(|row| row[0]).collect();
Ok(Self::fit_pairs(&scores, targets.as_slice(), params))
}
pub fn fit_calibration(
scores: &[f32],
targets: &BinaryTargets,
params: IsotonicRegressionParams,
) -> Result<Self, ModelError> {
super::validate_calibration_sample(scores, targets)?;
Ok(Self::fit_pairs(scores, targets.as_slice(), params))
}
fn fit_pairs<T: Copy + Into<f64>>(
scores: &[f32],
targets: &[T],
params: IsotonicRegressionParams,
) -> Self {
let mut order: Vec<u32> = (0..scores.len() as u32).collect();
order.sort_by(|&left, &right| scores[left as usize].total_cmp(&scores[right as usize]));
let mut inputs: Vec<Block> = Vec::new();
for &index in &order {
let score = scores[index as usize];
let target: f64 = targets[index as usize].into();
match inputs.last_mut() {
Some(last) if last.score == score => {
last.count += 1.0;
last.total += target;
}
_ => inputs.push(Block {
score,
count: 1.0,
total: target,
}),
}
}
let thresholds: Vec<f32> = inputs.iter().map(|block| block.score).collect();
let mut pooled: Vec<(Block, usize)> = Vec::with_capacity(inputs.len());
for block in inputs {
let mut merged = block;
let mut span = 1;
while let Some((previous, _)) = pooled.last() {
if previous.mean() <= merged.mean() {
break;
}
let (previous, previous_span) = pooled.pop().expect("the block was just inspected");
span += previous_span;
merged = Block {
score: previous.score,
count: previous.count + merged.count,
total: previous.total + merged.total,
};
}
pooled.push((merged, span));
}
let mut values = Vec::with_capacity(thresholds.len());
for (block, span) in pooled {
let value = block.mean() as f32;
values.extend(std::iter::repeat_n(value, span));
}
debug_assert_eq!(values.len(), thresholds.len());
Self {
thresholds,
values,
params,
}
}
pub const fn n_features_in(&self) -> usize {
1
}
pub const fn get_params(&self) -> &IsotonicRegressionParams {
&self.params
}
pub fn thresholds(&self) -> &[f32] {
&self.thresholds
}
pub fn values(&self) -> &[f32] {
&self.values
}
pub fn map(&self, score: f32) -> f32 {
let thresholds = &self.thresholds;
let last = thresholds.len() - 1;
if score.is_nan() || score <= thresholds[0] {
return self.values[0];
}
if score >= thresholds[last] {
return self.values[last];
}
let index = thresholds.partition_point(|&threshold| threshold <= score);
let (low, high) = (index - 1, index);
let span = f64::from(thresholds[high]) - f64::from(thresholds[low]);
let offset = f64::from(score) - f64::from(thresholds[low]);
let rise = f64::from(self.values[high]) - f64::from(self.values[low]);
let interpolated = f64::from(self.values[low]) + rise * (offset / span);
(interpolated as f32).clamp(self.values[low], self.values[high])
}
pub fn predict_one(&self, row: &[f32]) -> Result<f32, ModelError> {
if row.len() != 1 {
return Err(ModelError::FeatureDimension {
expected: 1,
actual: row.len(),
});
}
if !row[0].is_finite() {
return Err(ModelError::NonFiniteFeature { row: 0, column: 0 });
}
Ok(self.map(row[0]))
}
pub fn predict(&self, data: &MatrixView<'_>) -> Result<Vec<f32>, ModelError> {
<Self as Regressor>::predict(self, data)
}
pub fn predict_into(
&self,
data: &MatrixView<'_>,
output: &mut [f32],
) -> Result<(), ModelError> {
<Self as Regressor>::predict_into(self, data, output)
}
}
#[derive(Clone, Copy, Debug)]
struct Block {
score: f32,
count: f64,
total: f64,
}
impl Block {
fn mean(&self) -> f64 {
self.total / self.count
}
}
fn validate_univariate(data: &MatrixView<'_>, targets: usize) -> Result<(), ModelError> {
if data.rows() == 0 || data.columns() == 0 {
return Err(ModelError::EmptyData);
}
if data.columns() != 1 {
return Err(ModelError::FeatureDimension {
expected: 1,
actual: data.columns(),
});
}
if data.rows() != targets {
return Err(ModelError::TargetLength {
rows: data.rows(),
targets,
});
}
Ok(())
}
impl Estimator for IsotonicRegression {
fn n_features_in(&self) -> usize {
self.n_features_in()
}
}
impl HasParams for IsotonicRegression {
type Params = IsotonicRegressionParams;
fn get_params(&self) -> &Self::Params {
&self.params
}
}
impl HasCapabilities for IsotonicRegression {
const CAPABILITIES: Capabilities = Capabilities::NONE;
}
impl Regressor for IsotonicRegression {
fn predict_into(&self, data: &MatrixView<'_>, output: &mut [f32]) -> Result<(), ModelError> {
if data.columns() != 1 {
return Err(ModelError::FeatureDimension {
expected: 1,
actual: data.columns(),
});
}
if output.len() != data.rows() {
return Err(ModelError::OutputLength {
expected: data.rows(),
actual: output.len(),
});
}
for (slot, row) in output.iter_mut().zip(data.iter_rows()) {
*slot = self.map(row[0]);
}
Ok(())
}
}
impl Calibrator for IsotonicRegression {
fn calibrate(&self, score: f32) -> f32 {
self.map(score)
}
}
#[cfg(test)]
mod tests {
use super::*;
use crate::data::DenseMatrix;
fn fit(x: &[f32], y: &[f32]) -> IsotonicRegression {
let data = DenseMatrix::new(x.to_vec(), x.len(), 1).unwrap();
let targets = RegressionTargets::new(y.to_vec()).unwrap();
IsotonicRegression::fit(&data.as_view(), &targets, IsotonicRegressionParams).unwrap()
}
#[test]
fn an_already_monotone_sample_is_reproduced_exactly() {
let fitted = fit(&[0.0, 1.0, 2.0, 3.0], &[0.0, 0.0, 1.0, 1.0]);
assert_eq!(fitted.thresholds(), &[0.0, 1.0, 2.0, 3.0]);
assert_eq!(fitted.values(), &[0.0, 0.0, 1.0, 1.0]);
}
#[test]
fn violating_pairs_are_pooled_into_their_mean() {
let fitted = fit(&[0.0, 1.0, 2.0, 3.0, 4.0], &[0.0, 1.0, 0.0, 1.0, 1.0]);
assert_eq!(fitted.values(), &[0.0, 0.5, 0.5, 1.0, 1.0]);
let fitted = fit(&[0.0, 1.0, 2.0, 3.0], &[1.0, 1.0, 0.0, 0.0]);
assert_eq!(fitted.values(), &[0.5, 0.5, 0.5, 0.5]);
}
#[test]
fn tied_inputs_pool_first_and_the_fit_ignores_observation_order() {
let scores = [0.0_f32, 1.0, 1.0, 1.0, 2.0];
let values = [0.0_f32, 1.0, 0.0, 0.0, 1.0];
let sorted = fit(&scores, &values);
assert_eq!(sorted.thresholds(), &[0.0, 1.0, 2.0]);
assert_eq!(sorted.values(), &[0.0, 1.0 / 3.0, 1.0]);
for permutation in [[2, 0, 4, 3, 1], [4, 3, 2, 1, 0], [1, 3, 0, 2, 4]] {
let permuted_scores: Vec<f32> = permutation.iter().map(|&i| scores[i]).collect();
let permuted_values: Vec<f32> = permutation.iter().map(|&i| values[i]).collect();
let permuted = fit(&permuted_scores, &permuted_values);
assert_eq!(permuted, sorted, "permutation {permutation:?}");
}
}
#[test]
fn signed_zeros_are_one_input() {
let fitted = fit(&[-0.0, 0.0, 1.0], &[0.0, 1.0, 1.0]);
assert_eq!(fitted.thresholds().len(), 2);
assert_eq!(fitted.values(), &[0.5, 1.0]);
}
#[test]
fn prediction_interpolates_between_thresholds_and_clamps_outside_them() {
let fitted = fit(&[0.0, 1.0, 2.0, 3.0], &[0.0, 0.0, 1.0, 1.0]);
for (input, expected) in [
(-1.0, 0.0),
(0.0, 0.0),
(0.5, 0.0),
(1.0, 0.0),
(1.25, 0.25),
(1.5, 0.5),
(1.75, 0.75),
(2.0, 1.0),
(2.5, 1.0),
(3.0, 1.0),
(4.0, 1.0),
] {
assert_eq!(fitted.map(input), expected, "at {input}");
}
}
#[test]
fn a_single_distinct_input_maps_everything_to_its_mean() {
let fitted = fit(&[1.0, 1.0, 1.0], &[0.0, 1.0, 1.0]);
assert_eq!(fitted.thresholds(), &[1.0]);
for input in [-1.0_f32, 1.0, 5.0] {
assert_eq!(fitted.map(input), 2.0 / 3.0);
}
}
#[test]
fn the_fitted_map_is_non_decreasing_everywhere() {
let scores: Vec<f32> = (0..64).map(|step| (step as f32) * 0.37 - 7.0).collect();
let values: Vec<f32> = (0..64)
.map(|step| ((step * 37) % 11) as f32 / 10.0)
.collect();
let fitted = fit(&scores, &values);
assert!(
fitted.values().windows(2).all(|pair| pair[0] <= pair[1]),
"fitted values are not non-decreasing: {:?}",
fitted.values()
);
assert!(
fitted.thresholds().windows(2).all(|pair| pair[0] < pair[1]),
"thresholds are not strictly increasing"
);
let mut previous = f32::NEG_INFINITY;
for step in -300..=300 {
let mapped = fitted.map(step as f32 * 0.05);
assert!(mapped >= previous, "map decreased at {step}");
previous = mapped;
}
}
#[test]
fn calibration_fitting_needs_both_labels_and_matching_lengths() {
let scores = [0.1_f32, 0.4, 0.8];
assert_eq!(
IsotonicRegression::fit_calibration(
&scores,
&BinaryTargets::new(vec![0, 0, 0]).unwrap(),
IsotonicRegressionParams,
),
Err(ModelError::RequiresTwoClasses)
);
assert_eq!(
IsotonicRegression::fit_calibration(
&scores,
&BinaryTargets::new(vec![0, 1]).unwrap(),
IsotonicRegressionParams,
),
Err(ModelError::TargetLength {
rows: 3,
targets: 2,
})
);
assert_eq!(
IsotonicRegression::fit_calibration(
&[],
&BinaryTargets::new(vec![0, 1]).unwrap(),
IsotonicRegressionParams,
),
Err(ModelError::EmptyData)
);
assert_eq!(
IsotonicRegression::fit_calibration(
&[0.1, f32::NAN, 0.8],
&BinaryTargets::new(vec![0, 1, 1]).unwrap(),
IsotonicRegressionParams,
),
Err(ModelError::NonFiniteFeature { row: 1, column: 0 })
);
}
#[test]
fn calibration_values_stay_inside_the_probability_range() {
let scores = [0.9_f32, 0.1, 0.5, 0.3, 0.7];
let targets = BinaryTargets::new(vec![0, 1, 0, 1, 1]).unwrap();
let fitted =
IsotonicRegression::fit_calibration(&scores, &targets, IsotonicRegressionParams)
.unwrap();
assert!(
fitted
.values()
.iter()
.all(|value| (0.0..=1.0).contains(value))
);
for step in -20..=20 {
let mapped = fitted.map(step as f32 * 0.1);
assert!((0.0..=1.0).contains(&mapped), "at {step}: {mapped}");
}
}
#[test]
fn the_regressor_path_validates_width_and_output_length_before_writing() {
let fitted = fit(&[0.0, 1.0, 2.0], &[0.0, 0.5, 1.0]);
let wide = DenseMatrix::new(vec![0.0; 6], 3, 2).unwrap();
let mut sentinel = [f32::MAX; 3];
assert_eq!(
fitted.predict_into(&wide.as_view(), &mut sentinel),
Err(ModelError::FeatureDimension {
expected: 1,
actual: 2,
})
);
let narrow = DenseMatrix::new(vec![0.0, 1.0, 2.0], 3, 1).unwrap();
assert_eq!(
fitted.predict_into(&narrow.as_view(), &mut sentinel[..2]),
Err(ModelError::OutputLength {
expected: 3,
actual: 2,
})
);
assert_eq!(sentinel, [f32::MAX; 3]);
assert_eq!(fitted.predict(&narrow.as_view()), Ok(vec![0.0, 0.5, 1.0]));
assert_eq!(fitted.predict_one(&[1.0]), Ok(0.5));
assert_eq!(
fitted.predict_one(&[1.0, 2.0]),
Err(ModelError::FeatureDimension {
expected: 1,
actual: 2,
})
);
}
#[test]
fn fitting_validates_shape_before_any_work() {
let wide = DenseMatrix::new(vec![0.0; 6], 3, 2).unwrap();
let targets = RegressionTargets::new(vec![0.0, 1.0, 2.0]).unwrap();
assert_eq!(
IsotonicRegression::fit(&wide.as_view(), &targets, IsotonicRegressionParams),
Err(ModelError::FeatureDimension {
expected: 1,
actual: 2,
})
);
let narrow = DenseMatrix::new(vec![0.0, 1.0, 2.0], 3, 1).unwrap();
assert_eq!(
IsotonicRegression::fit(
&narrow.as_view(),
&RegressionTargets::new(vec![0.0, 1.0]).unwrap(),
IsotonicRegressionParams,
),
Err(ModelError::TargetLength {
rows: 3,
targets: 2,
})
);
}
#[test]
fn the_crate_wide_estimator_conventions_hold_here_too() {
let data = DenseMatrix::new(vec![0.0, 1.0, 2.0, 3.0], 4, 1).unwrap();
let targets = RegressionTargets::new(vec![0.0, 0.0, 1.0, 1.0]).unwrap();
let fitted =
IsotonicRegression::fit(&data.as_view(), &targets, IsotonicRegressionParams).unwrap();
assert_eq!(fitted.get_params(), &IsotonicRegressionParams);
assert_eq!(
<IsotonicRegression as HasParams>::get_params(&fitted),
&IsotonicRegressionParams
);
assert_eq!(fitted.n_features_in(), 1);
let allocated = fitted.predict(&data.as_view()).unwrap();
let mut buffer = vec![f32::NAN; data.rows()];
fitted.predict_into(&data.as_view(), &mut buffer).unwrap();
assert_eq!(allocated, buffer);
assert_eq!(allocated, vec![0.0, 0.0, 1.0, 1.0]);
assert_eq!(
allocated,
<IsotonicRegression as Regressor>::predict(&fitted, &data.as_view()).unwrap()
);
}
#[test]
fn every_fitting_entry_point_takes_the_params_type() {
let scores = [0.1_f32, 0.4, 0.6, 0.9];
let labels = BinaryTargets::new(vec![0, 0, 1, 1]).unwrap();
let calibrator =
IsotonicRegression::fit_calibration(&scores, &labels, IsotonicRegressionParams)
.unwrap();
assert_eq!(calibrator.get_params(), &IsotonicRegressionParams);
}
#[test]
fn refitting_the_same_sample_reproduces_the_same_model() {
let scores: Vec<f32> = (0..40).map(|step| (step % 7) as f32 * 0.5).collect();
let values: Vec<f32> = (0..40).map(|step| ((step * 13) % 5) as f32).collect();
assert_eq!(fit(&scores, &values), fit(&scores, &values));
}
}