mod solver;
use std::convert::Infallible;
use std::error::Error;
use std::fmt;
use lazymatrix::{ColumnStats, LazyMatrix, RawColumn, RawColumns};
use crate::{Centering, Normalization, Scaling};
use solver::{NumericalFailure, finite};
#[derive(Clone, Debug)]
#[must_use]
pub struct Lasso {
lambda: f64,
fit_intercept: bool,
normalization: Normalization,
tolerance: f64,
max_iterations: usize,
}
impl Lasso {
pub fn new(lambda: f64) -> Self {
Self {
lambda,
fit_intercept: true,
normalization: Normalization::Auto,
tolerance: 1e-6,
max_iterations: 10_000,
}
}
pub fn fit_intercept(mut self, enabled: bool) -> Self {
self.fit_intercept = enabled;
self
}
pub fn normalize(mut self, normalization: Normalization) -> Self {
self.normalization = normalization;
self
}
pub fn tolerance(mut self, tolerance: f64) -> Self {
self.tolerance = tolerance;
self
}
pub fn max_iterations(mut self, max_iterations: usize) -> Self {
self.max_iterations = max_iterations;
self
}
pub fn fit<M>(&self, x: &M, y: &[f64]) -> Result<LassoFit, LassoError<M::Error>>
where
M: RawColumns<f64> + ColumnStats<f64> + ?Sized,
{
self.validate()?;
if x.nrows() == 0 {
return Err(invalid("training data must have at least one observation"));
}
if y.len() != x.nrows() {
return Err(invalid(format!(
"response length {} does not match {} training rows",
y.len(),
x.nrows()
)));
}
for (i, value) in y.iter().enumerate() {
if !value.is_finite() {
return Err(invalid(format!("response at row {i} is not finite")));
}
}
validate_matrix(x)?;
let spec = self.normalization.specification(self.fit_intercept);
let (centers, mut scales) = if spec.center != Centering::None || spec.scale != Scaling::None
{
x.normalization_stats(spec)
.map_err(|source| LassoError::Backend {
operation: "computing training normalization statistics",
source,
})?
} else {
(None, None)
};
validate_statistics(
¢ers,
x.ncols(),
spec.center != Centering::None,
"column centers",
)?;
validate_statistics(
&scales,
x.ncols(),
spec.scale != Scaling::None,
"column scales",
)?;
if let Some(scales) = &mut scales {
for scale in scales {
if *scale < 0.0 {
return Err(invalid(
"matrix backend returned a negative normalization scale",
));
}
if *scale == 0.0 {
*scale = 1.0;
}
}
}
let matrix = LazyMatrix::from_parts(x, centers, scales);
let solution = solver::solve(&matrix, y, self)?;
let (_, centers, scales) = matrix.into_parts();
let mut coefficients = solution.coefficients;
if let Some(scales) = &scales {
for (coefficient, scale) in coefficients.iter_mut().zip(scales) {
*coefficient = finite(
*coefficient / scale,
"back-transforming coefficients",
solution.iterations,
)?;
}
}
let mut intercept = solution.intercept;
if let Some(centers) = ¢ers {
for (coefficient, center) in coefficients.iter().zip(centers) {
intercept = finite(
intercept - coefficient * center,
"back-transforming intercept",
solution.iterations,
)?;
}
}
Ok(LassoFit {
coefficients,
intercept,
preprocessing: Preprocessing {
spec,
centers,
scales,
},
termination: solution.termination,
iterations: solution.iterations,
objective: solution.objective,
kkt_violation: solution.kkt_violation,
})
}
fn validate<E>(&self) -> Result<(), LassoError<E>> {
if !self.lambda.is_finite() || self.lambda < 0.0 {
return Err(invalid("lambda must be finite and nonnegative"));
}
if !self.tolerance.is_finite() || self.tolerance <= 0.0 {
return Err(invalid("tolerance must be finite and strictly positive"));
}
if self.max_iterations == 0 {
return Err(invalid("max_iterations must be strictly positive"));
}
Ok(())
}
}
#[derive(Clone, Debug)]
pub struct Preprocessing {
spec: lazymatrix::Normalization,
centers: Option<Vec<f64>>,
scales: Option<Vec<f64>>,
}
impl Preprocessing {
pub fn centering(&self) -> Centering {
self.spec.center
}
pub fn scaling(&self) -> Scaling {
self.spec.scale
}
pub fn centers(&self) -> Option<&[f64]> {
self.centers.as_deref()
}
pub fn scales(&self) -> Option<&[f64]> {
self.scales.as_deref()
}
}
#[derive(Clone, Copy, Debug, PartialEq, Eq)]
pub enum Termination {
Converged,
IterationLimit,
}
#[derive(Clone, Debug)]
#[must_use]
pub struct LassoFit {
coefficients: Vec<f64>,
intercept: f64,
preprocessing: Preprocessing,
termination: Termination,
iterations: usize,
objective: f64,
kkt_violation: f64,
}
impl LassoFit {
pub fn coefficients(&self) -> &[f64] {
&self.coefficients
}
pub fn intercept(&self) -> f64 {
self.intercept
}
pub fn preprocessing(&self) -> &Preprocessing {
&self.preprocessing
}
pub fn termination(&self) -> Termination {
self.termination
}
pub fn iterations(&self) -> usize {
self.iterations
}
pub fn objective(&self) -> f64 {
self.objective
}
pub fn kkt_violation(&self) -> f64 {
self.kkt_violation
}
pub fn predict<M: RawColumns<f64> + ?Sized>(&self, x: &M) -> Result<Vec<f64>, LassoError> {
if x.ncols() != self.coefficients.len() {
return Err(invalid(format!(
"prediction design has {} columns; expected {}",
x.ncols(),
self.coefficients.len()
)));
}
validate_matrix(x)?;
let mut predictions = vec![self.intercept; x.nrows()];
for (j, &coefficient) in self.coefficients.iter().enumerate() {
if coefficient != 0.0 {
x.raw_column(j)
.affine_add_to(coefficient, 0.0, &mut predictions);
}
}
for &value in &predictions {
finite(value, "predicting", self.iterations)?;
}
Ok(predictions)
}
}
#[derive(Debug)]
pub enum LassoError<E = Infallible> {
InvalidInput {
message: String,
},
NumericalFailure {
operation: &'static str,
iteration: usize,
},
Backend {
operation: &'static str,
source: E,
},
}
impl<E: fmt::Display> fmt::Display for LassoError<E> {
fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
match self {
Self::InvalidInput { message } => write!(f, "invalid lasso input: {message}"),
Self::NumericalFailure {
operation,
iteration,
} => write!(
f,
"nonfinite arithmetic while {operation} at sweep {iteration}"
),
Self::Backend { operation, source } => {
write!(f, "backend failed while {operation}: {source}")
}
}
}
}
impl<E: Error + 'static> Error for LassoError<E> {
fn source(&self) -> Option<&(dyn Error + 'static)> {
match self {
Self::Backend { source, .. } => Some(source),
_ => None,
}
}
}
impl<E> From<NumericalFailure> for LassoError<E> {
fn from(error: NumericalFailure) -> Self {
Self::NumericalFailure {
operation: error.operation,
iteration: error.iteration,
}
}
}
fn invalid<E>(message: impl Into<String>) -> LassoError<E> {
LassoError::InvalidInput {
message: message.into(),
}
}
fn validate_matrix<M: RawColumns<f64> + ?Sized, E>(x: &M) -> Result<(), LassoError<E>> {
for j in 0..x.ncols() {
let column = x.raw_column(j);
if column.len() != x.nrows() || column.stored_len() > x.nrows() {
return Err(invalid(format!(
"matrix backend returned invalid dimensions for column {j}"
)));
}
let mut invalid_row = None;
column.for_each_stored(|i, value| {
if (i >= x.nrows() || !value.is_finite()) && invalid_row.is_none() {
invalid_row = Some(i);
}
});
if let Some(i) = invalid_row {
return Err(invalid(format!(
"invalid matrix entry at row {i}, column {j}: expected an in-bounds, finite value"
)));
}
}
Ok(())
}
fn validate_statistics<E>(
values: &Option<Vec<f64>>,
ncols: usize,
expected: bool,
operation: &'static str,
) -> Result<(), LassoError<E>> {
if values.is_some() != expected || values.as_ref().is_some_and(|v| v.len() != ncols) {
return Err(invalid(format!(
"matrix backend returned unexpected {operation}"
)));
}
if let Some(values) = values {
for &value in values {
finite(value, operation, 0)?;
}
}
Ok(())
}