use crate::api::ModelError;
use crate::data::{MatrixView, SampleWeights};
use crate::numeric::sum_in_order;
use faer::dyn_stack::{MemBuffer, MemStack};
use faer::linalg::householder::{
apply_block_householder_sequence_transpose_on_the_left_in_place_scratch,
apply_block_householder_sequence_transpose_on_the_left_in_place_with_conj,
};
use faer::linalg::solvers::Solve;
use faer::{Conj, Mat, MatRef, Par, Side};
fn pin_sequential() {
faer::set_global_parallelism(Par::Seq);
debug_assert!(
matches!(faer::get_global_parallelism(), Par::Seq),
"the backend refused a sequential pin, so reduction order is no longer fixed"
);
}
pub(super) struct LeastSquaresFit {
pub(super) coefficients: Vec<f64>,
pub(super) intercept: f64,
pub(super) rank: usize,
}
pub(super) struct DenseLinearFit {
pub(super) coefficients: Vec<f64>,
pub(super) intercept: f64,
}
pub(super) fn fit_dense(
data: &MatrixView<'_>,
targets: &[f32],
sample_weights: Option<&SampleWeights>,
fit_intercept: bool,
tolerance: f32,
) -> Result<LeastSquaresFit, ModelError> {
fit_dense_by(
data,
targets,
sample_weights,
fit_intercept,
tolerance,
reduce_before_decomposing(data.rows(), data.columns()),
)
}
fn fit_dense_by(
data: &MatrixView<'_>,
targets: &[f32],
sample_weights: Option<&SampleWeights>,
fit_intercept: bool,
tolerance: f32,
reduce: bool,
) -> Result<LeastSquaresFit, ModelError> {
debug_assert_eq!(data.rows(), targets.len());
debug_assert!(sample_weights.is_none_or(|weights| weights.len() == data.rows()));
pin_sequential();
let preprocessed = preprocess(data, targets, sample_weights, fit_intercept);
let rows = data.rows();
let columns = data.columns();
let (coefficients, rank) = if reduce {
let (upper, projected) = reduce_by_qr(&preprocessed)?;
solve_min_norm(upper.as_ref(), &projected, rows, columns, tolerance)?
} else {
solve_min_norm(
preprocessed.matrix_ref(),
&preprocessed.targets,
rows,
columns,
tolerance,
)?
};
let intercept = preprocessed.target_mean
- preprocessed
.feature_means
.iter()
.zip(&coefficients)
.map(|(&mean, &coefficient)| mean * coefficient)
.sum::<f64>();
if coefficients.iter().any(|value| !value.is_finite()) || !intercept.is_finite() {
return Err(ModelError::LinearSolveFailed);
}
Ok(LeastSquaresFit {
coefficients,
intercept,
rank,
})
}
fn reduce_before_decomposing(rows: usize, columns: usize) -> bool {
4 * rows >= 5 * columns
}
fn reduce_by_qr(preprocessed: &PreprocessedDense) -> Result<(Mat<f64>, Vec<f64>), ModelError> {
let rows = preprocessed.rows;
let columns = preprocessed.columns;
debug_assert!(
rows >= columns,
"the R-SVD reduction was handed an underdetermined design, whose \
minimum-norm solution lives in the part `R` discards"
);
let qr = preprocessed.matrix_ref().qr();
let packed = qr.R();
let upper = Mat::from_fn(columns, columns, |row, column| packed[(row, column)]);
let basis = qr.Q_basis();
let coefficients = qr.Q_coeff();
let mut rhs = Mat::from_fn(rows, 1, |row, _| preprocessed.targets[row]);
let mut buffer = MemBuffer::new(
apply_block_householder_sequence_transpose_on_the_left_in_place_scratch::<f64>(
rows,
coefficients.nrows(),
1,
),
);
apply_block_householder_sequence_transpose_on_the_left_in_place_with_conj(
basis,
coefficients,
Conj::No,
rhs.as_mut(),
Par::Seq,
MemStack::new(&mut buffer),
);
let projected = (0..columns).map(|row| rhs[(row, 0)]).collect::<Vec<_>>();
if projected.iter().any(|value| !value.is_finite()) {
return Err(ModelError::LinearSolveFailed);
}
Ok((upper, projected))
}
fn solve_min_norm(
matrix: MatRef<'_, f64>,
targets: &[f64],
rows: usize,
columns: usize,
tolerance: f32,
) -> Result<(Vec<f64>, usize), ModelError> {
debug_assert_eq!(matrix.nrows(), targets.len());
let svd = matrix
.thin_svd()
.map_err(|_| ModelError::LinearSolveFailed)?;
let singular = svd.S();
let singular = singular.column_vector();
let largest_singular = singular.iter().copied().fold(0.0_f64, f64::max);
if !largest_singular.is_finite() {
return Err(ModelError::LinearSolveFailed);
}
let numerical_floor = f64::EPSILON * rows.max(columns) as f64 * largest_singular;
let cutoff = (f64::from(tolerance) * largest_singular).max(numerical_floor);
let rank = singular.iter().filter(|&&value| value > cutoff).count();
let left = svd.U();
let right = svd.V();
let mut projected = vec![0.0_f64; singular.nrows()];
for (index, projection) in projected.iter_mut().enumerate() {
let value = singular[index];
if value > cutoff {
*projection =
sum_in_order((0..matrix.nrows()).map(|row| left[(row, index)] * targets[row]))
/ value;
}
}
let coefficients = (0..columns)
.map(|column| {
sum_in_order(
projected
.iter()
.enumerate()
.map(|(index, &projection)| right[(column, index)] * projection),
)
})
.collect::<Vec<_>>();
Ok((coefficients, rank))
}
pub(super) fn fit_ridge_dense(
data: &MatrixView<'_>,
targets: &[f32],
sample_weights: Option<&SampleWeights>,
fit_intercept: bool,
alpha: f32,
) -> Result<DenseLinearFit, ModelError> {
if alpha == 0.0 {
let fit = fit_dense(data, targets, sample_weights, fit_intercept, 0.0)?;
return Ok(DenseLinearFit {
coefficients: fit.coefficients,
intercept: fit.intercept,
});
}
pin_sequential();
let preprocessed = preprocess(data, targets, sample_weights, fit_intercept);
let design = preprocessed.matrix_ref();
let mut gram: Mat<f64> = design.transpose() * design;
for index in 0..gram.nrows() {
gram[(index, index)] += f64::from(alpha);
}
let right: Mat<f64> = design.transpose() * preprocessed.targets_ref();
let solution = gram
.llt(Side::Lower)
.map_err(|_| ModelError::LinearSolveFailed)?
.solve(&right);
let coefficients = (0..solution.nrows())
.map(|index| solution[(index, 0)])
.collect::<Vec<_>>();
let intercept = preprocessed.target_mean
- preprocessed
.feature_means
.iter()
.zip(&coefficients)
.map(|(&mean, &coefficient)| mean * coefficient)
.sum::<f64>();
if coefficients.iter().any(|value| !value.is_finite()) || !intercept.is_finite() {
return Err(ModelError::LinearSolveFailed);
}
Ok(DenseLinearFit {
coefficients,
intercept,
})
}
pub(super) struct PreprocessedDense {
pub(super) matrix: Vec<f64>,
pub(super) targets: Vec<f64>,
pub(super) rows: usize,
pub(super) columns: usize,
pub(super) feature_means: Vec<f64>,
pub(super) target_mean: f64,
}
impl PreprocessedDense {
fn matrix_ref(&self) -> MatRef<'_, f64> {
MatRef::from_column_major_slice(&self.matrix, self.rows, self.columns)
}
fn targets_ref(&self) -> MatRef<'_, f64> {
MatRef::from_column_major_slice(&self.targets, self.rows, 1)
}
}
pub(super) fn preprocess(
data: &MatrixView<'_>,
targets: &[f32],
sample_weights: Option<&SampleWeights>,
fit_intercept: bool,
) -> PreprocessedDense {
let rows = data.rows();
let columns = data.columns();
let total_weight = sample_weights.map_or(rows as f64, SampleWeights::total);
let mut feature_means = vec![0.0_f64; columns];
let mut target_mean = 0.0_f64;
if fit_intercept {
for (row_index, (row, &target)) in data.iter_rows().zip(targets).enumerate() {
let weight = sample_weight(sample_weights, row_index);
for (column, &value) in row.iter().enumerate() {
feature_means[column] += weight * f64::from(value);
}
target_mean += weight * f64::from(target);
}
for mean in &mut feature_means {
*mean /= total_weight;
}
target_mean /= total_weight;
}
let weight_sqrts = sample_weights.map(|weights| {
weights
.as_slice()
.iter()
.map(|&weight| f64::from(weight).sqrt())
.collect::<Vec<_>>()
});
let row_scale = |row: usize| weight_sqrts.as_ref().map_or(1.0, |weights| weights[row]);
let mut matrix_values = Vec::with_capacity(rows * columns);
for (column, &mean) in feature_means.iter().enumerate() {
for row in 0..rows {
let value = data.as_slice()[row * columns + column];
matrix_values.push(row_scale(row) * (f64::from(value) - mean));
}
}
let target_vector = targets
.iter()
.enumerate()
.map(|(row, &target)| row_scale(row) * (f64::from(target) - target_mean))
.collect::<Vec<_>>();
PreprocessedDense {
matrix: matrix_values,
targets: target_vector,
rows,
columns,
feature_means,
target_mean,
}
}
fn sample_weight(sample_weights: Option<&SampleWeights>, row: usize) -> f64 {
sample_weights.map_or(1.0, |weights| f64::from(weights.as_slice()[row]))
}
#[cfg(test)]
mod tests {
use super::*;
use crate::data::DenseMatrix;
use crate::numeric::OwnedRng;
#[derive(Clone, Copy, Debug)]
enum Conditioning {
Well,
Ill,
Deficient,
}
fn corpus_design(
rows: usize,
columns: usize,
conditioning: Conditioning,
seed: u64,
) -> (Vec<f32>, Vec<f32>) {
let mut rng = OwnedRng::new(seed);
let mut values = vec![0.0_f32; rows * columns];
for row in 0..rows {
for column in 0..columns {
values[row * columns + column] = (rng.unit_f64() * 2.0 - 1.0) as f32;
}
}
match conditioning {
Conditioning::Well => {}
Conditioning::Ill => {
for column in 0..columns {
let scale =
10.0_f64.powf(-8.0 * column as f64 / (columns - 1).max(1) as f64) as f32;
for row in 0..rows {
values[row * columns + column] *= scale;
}
}
}
Conditioning::Deficient => {
for row in 0..rows {
values[row * columns + columns - 1] = values[row * columns];
}
}
}
let targets = (0..rows)
.map(|_| (rng.unit_f64() * 2.0 - 1.0) as f32)
.collect::<Vec<f32>>();
(values, targets)
}
fn scaled_normal_equation_gradient(
values: &[f32],
targets: &[f32],
rows: usize,
columns: usize,
coefficients: &[f64],
intercept: f64,
weights: Option<&[f32]>,
) -> f64 {
let weight = |row: usize| weights.map_or(1.0, |w| f64::from(w[row]));
let residual = (0..rows)
.map(|row| {
let predicted = sum_in_order((0..columns).map(|column| {
f64::from(values[row * columns + column]) * coefficients[column]
})) + intercept;
weight(row) * (predicted - f64::from(targets[row]))
})
.collect::<Vec<_>>();
let scale = values
.iter()
.fold(0.0_f64, |m, &v| m.max(f64::from(v).abs()))
* targets
.iter()
.fold(0.0_f64, |m, &v| m.max(f64::from(v).abs()))
* rows as f64;
let mut worst = 0.0_f64;
for column in 0..columns {
let gradient = sum_in_order(
(0..rows).map(|row| f64::from(values[row * columns + column]) * residual[row]),
);
worst = worst.max(gradient.abs() / scale);
}
worst
}
#[test]
fn the_shape_guard_never_routes_an_underdetermined_design_into_the_reduction() {
let mut reduced_shapes = 0_usize;
for columns in 1..48_usize {
for rows in 0..96_usize {
if reduce_before_decomposing(rows, columns) {
reduced_shapes += 1;
assert!(
rows >= columns,
"the guard routes a {rows}x{columns} design into a reduction \
that discards the part its minimum-norm solution lives in"
);
}
}
}
assert!(
reduced_shapes > 1000,
"only {reduced_shapes} shapes reach the reduction at all, so this \
implication is close to vacuous"
);
}
#[test]
fn the_backends_qr_returns_a_square_upper_triangular_r() {
pin_sequential();
let rows = 17_usize;
let columns = 5_usize;
let mut rng = OwnedRng::new(0xD1CE_0007);
let values = (0..rows * columns)
.map(|_| (rng.unit_f64() * 2.0 - 1.0) as f32 + 1.5)
.collect::<Vec<f32>>();
let data = DenseMatrix::new(values, rows, columns).unwrap();
let targets = vec![1.0_f32; rows];
let preprocessed = preprocess(&data.as_view(), &targets, None, false);
let factor = preprocessed.matrix_ref().qr();
let upper = factor.R();
assert_eq!(
(upper.nrows(), upper.ncols()),
(columns, columns),
"the backend's `R` is no longer square, so `reduce_by_qr` is \
truncating it rather than copying it"
);
for row in 0..columns {
for column in 0..row {
assert_eq!(
upper[(row, column)],
0.0,
"the backend's `R` has {} below the diagonal at ({row}, \
{column}), so it is the packed factor and `reduce_by_qr` is \
feeding Householder vectors to the SVD",
upper[(row, column)]
);
}
assert_ne!(
upper[(row, row)],
0.0,
"the backend's `R` has a zero diagonal entry at {row} on a design \
with no zeros in it, so this is not the factor it claims to be"
);
}
}
#[test]
fn the_two_paths_agree_on_well_conditioned_ill_conditioned_and_deficient_designs() {
let shapes = [
(500_usize, 8_usize, Conditioning::Well),
(400, 6, Conditioning::Ill),
(300, 5, Conditioning::Deficient),
(40, 40, Conditioning::Well),
(41, 40, Conditioning::Well),
(40, 40, Conditioning::Ill),
(41, 40, Conditioning::Deficient),
(60, 12, Conditioning::Deficient),
(200, 3, Conditioning::Ill),
(129, 128, Conditioning::Well),
];
let mut worst_well = 0.0_f64;
let mut worst_ill = 0.0_f64;
let mut worst_gradient = 0.0_f64;
let mut seed = 0x00A1_1CE5_u64;
for &(rows, columns, conditioning) in &shapes {
for &fit_intercept in &[false, true] {
for &weighted in &[false, true] {
seed = seed.wrapping_mul(6_364_136_223_846_793_005).wrapping_add(1);
let (values, targets) = corpus_design(rows, columns, conditioning, seed);
let data = DenseMatrix::new(values.clone(), rows, columns).unwrap();
let weight_values = (0..rows)
.map(|row| 0.25 + (row % 7) as f32 * 0.5)
.collect::<Vec<f32>>();
let weights =
weighted.then(|| SampleWeights::new(weight_values.clone()).unwrap());
let direct = fit_dense_by(
&data.as_view(),
&targets,
weights.as_ref(),
fit_intercept,
0.0,
false,
)
.unwrap();
let reduced = fit_dense_by(
&data.as_view(),
&targets,
weights.as_ref(),
fit_intercept,
0.0,
true,
)
.unwrap();
assert_eq!(
direct.rank, reduced.rank,
"the two paths disagree on the rank of a {rows}x{columns} \
{conditioning:?} design (intercept {fit_intercept}, weighted \
{weighted}): {} against {}",
direct.rank, reduced.rank
);
if matches!(conditioning, Conditioning::Deficient) {
assert_eq!(
reduced.rank,
columns - 1,
"a duplicated column leaves rank {} at {rows}x{columns}",
columns - 1
);
}
let scale = direct
.coefficients
.iter()
.fold(direct.intercept.abs(), |m, &v| m.max(v.abs()))
.max(f64::MIN_POSITIVE);
let mut deviation = (direct.intercept - reduced.intercept).abs() / scale;
for (&a, &b) in direct.coefficients.iter().zip(&reduced.coefficients) {
deviation = deviation.max((a - b).abs() / scale);
}
match conditioning {
Conditioning::Ill => worst_ill = worst_ill.max(deviation),
_ => worst_well = worst_well.max(deviation),
}
for fit in [&direct, &reduced] {
worst_gradient = worst_gradient.max(scaled_normal_equation_gradient(
&values,
&targets,
rows,
columns,
&fit.coefficients,
if fit_intercept { fit.intercept } else { 0.0 },
weighted.then_some(weight_values.as_slice()),
));
}
}
}
}
assert!(
worst_well < 1.0e-12,
"the reduced and direct paths disagree by {worst_well:e} relative on a \
well-conditioned or exactly rank-deficient design, which is far past the \
last-bit spread two backward-stable solves are entitled to"
);
assert!(
worst_ill < 1.0e-6,
"the reduced and direct paths disagree by {worst_ill:e} relative on a \
design conditioned at about 1e8, past the `cond * eps` spread"
);
assert!(
worst_gradient < 1.0e-12,
"some fit is not a least-squares solution: worst scaled normal-equation \
gradient {worst_gradient:e}"
);
}
#[test]
fn the_rank_floor_scales_with_the_designs_rows_and_not_the_reductions() {
pin_sequential();
let rows = 2000_usize;
let small = (2.0_f64).powi(-16) as f32;
let mut values = vec![0.0_f32; rows * 2];
for row in 0..rows {
let base = if row == rows / 2 { small } else { 1.0_f32 };
values[row * 2] = base;
values[row * 2 + 1] = 2.0 * base;
}
let perturbed = (rows / 2) * 2 + 1;
values[perturbed] = f32::from_bits(values[perturbed].to_bits() + 1);
let data = DenseMatrix::new(values.clone(), rows, 2).unwrap();
let targets = (0..rows)
.map(|row| if row % 3 == 0 { 1.0_f32 } else { -0.5 })
.collect::<Vec<f32>>();
let preprocessed = preprocess(&data.as_view(), &targets, None, false);
let (upper, _) = reduce_by_qr(&preprocessed).unwrap();
let svd = upper.as_ref().thin_svd().unwrap();
let singular = svd.S();
let singular = singular.column_vector();
let largest = singular.iter().copied().fold(0.0_f64, f64::max);
let ratio = singular[1] / largest;
assert!(
ratio > f64::EPSILON * 2.0 * 4.0,
"σ₂/σ₁ = {ratio:e} does not clear the floor `R`'s own dimensions would \
give, so the two rules are not being separated"
);
assert!(
ratio < f64::EPSILON * rows as f64 / 4.0,
"σ₂/σ₁ = {ratio:e} is not below the floor the design's dimensions give, \
so the two rules are not being separated"
);
for reduce in [false, true] {
let fit = fit_dense_by(&data.as_view(), &targets, None, false, 0.0, reduce).unwrap();
assert_eq!(
fit.rank,
1,
"the {} path reports rank {} on a design whose second singular value \
is below the floor `eps * rows * σ₁`, so it took the reduction's \
dimensions rather than the design's",
if reduce { "reduced" } else { "direct" },
fit.rank
);
}
}
#[test]
fn preprocess_writes_a_dense_column_major_buffer_the_backend_reads_the_same_way() {
let data = DenseMatrix::new(vec![1.0, 10.0, 2.0, 20.0, 3.0, 30.0], 3, 2).unwrap();
let targets = [1.0_f32, 2.0, 3.0];
let preprocessed = preprocess(&data.as_view(), &targets, None, false);
assert_eq!(preprocessed.rows, 3);
assert_eq!(preprocessed.columns, 2);
assert_eq!(preprocessed.matrix, vec![1.0, 2.0, 3.0, 10.0, 20.0, 30.0]);
let view = preprocessed.matrix_ref();
assert_eq!(view.nrows(), 3);
assert_eq!(view.ncols(), 2);
for row in 0..3 {
for column in 0..2 {
assert_eq!(
view[(row, column)],
preprocessed.matrix[column * 3 + row],
"element ({row}, {column}) is not where the column-major slice puts it"
);
assert_eq!(
view[(row, column)],
f64::from(data.as_slice()[row * 2 + column])
);
}
}
}
#[test]
fn exactly_rank_deficient_tall_designs_get_a_minimum_norm_least_squares_answer() {
let mut rng = OwnedRng::new(0x5EED_1234);
let mut worst_gradient = 0.0_f64;
let mut worst_split = 0.0_f64;
for &(rows, columns) in &[(64_usize, 3_usize), (256, 4), (300, 6)] {
for _ in 0..25 {
let mut values = vec![0.0_f32; rows * columns];
for row in 0..rows {
for column in 0..columns - 1 {
values[row * columns + column] = (rng.unit_f64() * 2.0 - 1.0) as f32;
}
values[row * columns + columns - 1] = values[row * columns];
}
let targets = (0..rows)
.map(|_| (rng.unit_f64() * 2.0 - 1.0) as f32)
.collect::<Vec<f32>>();
let data = DenseMatrix::new(values.clone(), rows, columns).unwrap();
for reduce in [false, true] {
let fit =
fit_dense_by(&data.as_view(), &targets, None, false, 0.0, reduce).unwrap();
assert_eq!(
fit.rank,
columns - 1,
"a duplicated column leaves rank {} at {rows}x{columns} \
(reduced: {reduce})",
columns - 1
);
worst_gradient = worst_gradient.max(scaled_normal_equation_gradient(
&values,
&targets,
rows,
columns,
&fit.coefficients,
0.0,
None,
));
let split = (fit.coefficients[0] - fit.coefficients[columns - 1]).abs();
worst_split = worst_split.max(split);
}
}
}
assert!(
worst_gradient < 1.0e-12,
"the fit is not a least-squares solution: worst scaled normal-equation \
gradient {worst_gradient:e}"
);
assert!(
worst_split < 1.0e-9,
"duplicated columns did not split evenly, so the solution is not the \
minimum-norm one: worst gap {worst_split:e}"
);
}
#[test]
fn the_vanishing_singular_value_clears_the_rank_floor_with_margin() {
pin_sequential();
let data = DenseMatrix::new(vec![1.0, 2.0, 2.0, 4.0, 3.0, 6.0], 3, 2).unwrap();
let targets = [1.0_f32, 2.0, 3.0];
assert!(
reduce_before_decomposing(3, 2),
"the reference design no longer takes the reduced path, so this test \
stopped covering the path that decides its rank"
);
let preprocessed = preprocess(&data.as_view(), &targets, None, false);
let (upper, _) = reduce_by_qr(&preprocessed).unwrap();
for (label, matrix) in [
("the design", preprocessed.matrix_ref()),
("the reduced R", upper.as_ref()),
] {
let svd = matrix.thin_svd().unwrap();
let singular = svd.S();
let singular = singular.column_vector();
let largest = singular.iter().copied().fold(0.0_f64, f64::max);
let floor = f64::EPSILON * 3.0 * largest;
assert!(
singular[1] < floor / 4.0,
"σ₂ of {label} is {} — within a factor of four of the rank floor \
{floor}, which leaves no margin for the comparison `rank()` reports",
singular[1]
);
assert!(
singular[0] > floor * 1.0e12,
"σ₁ of {label} is {} and does not clear the floor by a wide margin",
singular[0]
);
}
}
}