mod error;
mod folds;
mod metric;
mod rows;
pub use crate::fit::{CrossValidationFit, FoldPath};
pub use error::CrossValidationError;
pub use folds::FoldAssignments;
pub use metric::{CrossValidationDatafit, ValidationMetric};
pub use rows::RowSubset;
use lazymatrix::RawColumns;
use crate::error::{finite, invalid};
use crate::{
FitError, PathFit, PathOptions, PathPenalty, PathSolver, Problem, RegularizationPathSolver,
Termination,
};
#[derive(Clone, Copy, Debug, Default, PartialEq, Eq)]
pub enum SelectionRule {
#[default]
MinimumError,
OneStandardError,
}
#[derive(Clone, Debug)]
#[must_use]
pub struct CrossValidation {
folds: FoldAssignments,
metric: Option<ValidationMetric>,
selection_rule: SelectionRule,
}
impl CrossValidation {
pub fn new(folds: FoldAssignments) -> Self {
Self {
folds,
metric: None,
selection_rule: SelectionRule::MinimumError,
}
}
pub fn metric(mut self, metric: ValidationMetric) -> Self {
self.metric = Some(metric);
self
}
pub fn selection_rule(mut self, rule: SelectionRule) -> Self {
self.selection_rule = rule;
self
}
pub fn folds(&self) -> &FoldAssignments {
&self.folds
}
}
pub trait ValidationFit {
fn predict<M: RawColumns<f64> + ?Sized>(&self, design: &M) -> Result<Vec<f64>, FitError>;
fn termination(&self) -> Termination;
}
macro_rules! validation_fit {
($($fit:ty),* $(,)?) => {$ (
impl ValidationFit for $fit {
fn predict<M: RawColumns<f64> + ?Sized>(&self, design: &M) -> Result<Vec<f64>, FitError> {
self.predict(design)
}
fn termination(&self) -> Termination { self.termination() }
}
)*};
}
validation_fit!(
crate::LassoFit,
crate::IrlsFit,
crate::ProximalFit,
crate::HybridFit
);
impl<M, D, P> Problem<&M, D, P>
where
M: RowSubset + ?Sized,
D: CrossValidationDatafit,
{
pub fn cross_validate_path_with<S, Q, F>(
&self,
solver: &S,
penalties: Vec<Q>,
cv: &CrossValidation,
) -> Result<CrossValidationFit<F, Q>, CrossValidationError<M::Error>>
where
Q: Clone,
F: ValidationFit,
S: PathSolver<Self, Q, Fit = F, Error = FitError<M::Error>>,
for<'a> S: PathSolver<
Problem<&'a M::Subset, D::WithResponse<'a>, ()>,
Q,
Fit = F,
Error = FitError<M::Error>,
>,
{
let metric = self.validate_cross_validation(cv)?;
if penalties.is_empty() {
return Err(invalid("cross-validation requires at least one candidate").into());
}
let mut folds = Vec::with_capacity(cv.folds.nfolds());
for fold in 0..cv.folds.nfolds() {
let result = (|| {
let (training_rows, validation_rows) = cv.folds.rows(fold);
let training = self.design().select_rows(&training_rows)?;
let response = training_rows
.iter()
.map(|&i| self.datafit().response()[i])
.collect::<Vec<_>>();
let datafit = self.training_datafit(&response)?;
let problem = Problem::new(&training, datafit, ()).normalize(self.normalization());
let path = solver.solve_path(&problem, penalties.clone())?;
self.score_fold(path, validation_rows, metric, penalties.len())
})()
.map_err(|source| CrossValidationError::Fold { fold, source })?;
check_convergence(&result.path, Some(fold))?;
folds.push(result);
}
let summary = summarize(&folds, cv.selection_rule)?;
let refit = solver
.solve_path(self, penalties)
.map_err(|source| CrossValidationError::Refit { source })?;
finish(cv, metric, folds, refit, summary, None)
}
pub fn cross_validate_regularization_path_with<S, F>(
&self,
solver: &S,
options: &PathOptions,
cv: &CrossValidation,
) -> Result<CrossValidationFit<F, P::AtStrength>, CrossValidationError<M::Error>>
where
P: PathPenalty + Clone,
F: ValidationFit,
S: RegularizationPathSolver<
Self,
Fit = F,
Penalty = P::AtStrength,
Error = FitError<M::Error>,
>,
for<'a> S: RegularizationPathSolver<
Problem<&'a M::Subset, D::WithResponse<'a>, P>,
Fit = F,
Penalty = P::AtStrength,
Error = FitError<M::Error>,
>,
{
let metric = self.validate_cross_validation(cv)?;
options.validate()?;
let min_training = self.design().nrows() - cv.folds.fold_sizes().iter().max().unwrap();
let (options, fractions) = options.cross_validation(min_training, self.design().ncols());
let mut folds = Vec::with_capacity(cv.folds.nfolds());
for fold in 0..cv.folds.nfolds() {
let result = (|| {
let (training_rows, validation_rows) = cv.folds.rows(fold);
let training = self.design().select_rows(&training_rows)?;
let response = training_rows
.iter()
.map(|&i| self.datafit().response()[i])
.collect::<Vec<_>>();
let datafit = self.training_datafit(&response)?;
let problem = Problem::new(&training, datafit, self.penalty().clone())
.normalize(self.normalization());
let path = solver.solve_regularization_path(&problem, &options)?;
self.score_fold(path, validation_rows, metric, fractions.len())
})()
.map_err(|source| CrossValidationError::Fold { fold, source })?;
check_convergence(&result.path, Some(fold))?;
folds.push(result);
}
let summary = summarize(&folds, cv.selection_rule)?;
let refit = solver
.solve_regularization_path(self, &options)
.map_err(|source| CrossValidationError::Refit { source })?;
finish(cv, metric, folds, refit, summary, Some(fractions))
}
fn validate_cross_validation(
&self,
cv: &CrossValidation,
) -> Result<ValidationMetric, FitError<M::Error>> {
if self.design().nrows() != self.datafit().response().len()
|| self.design().nrows() != cv.folds.assignments().len()
{
return Err(invalid(
"design, response, and fold assignment lengths must match",
));
}
if self.centers().is_some() || self.scales().is_some() {
return Err(invalid(
"cross-validation must estimate preprocessing within each training fold; remove supplied centers and scales",
));
}
self.datafit()
.validate_training()
.map_err(|e| FitError::from_component(e, 0))?;
crate::problem::validate_matrix(*self.design())?;
let metric = cv
.metric
.unwrap_or_else(|| self.datafit().validation_metric());
if !self.datafit().supports_metric(metric) {
return Err(invalid(
"validation metric does not support the problem's response family",
));
}
Ok(metric)
}
fn training_datafit<'a>(
&self,
response: &'a [f64],
) -> Result<D::WithResponse<'a>, FitError<M::Error>> {
let datafit = self.datafit().with_response(response);
datafit
.validate_training()
.map_err(|e| FitError::from_component(e, 0))?;
Ok(datafit)
}
fn score_fold<F: ValidationFit, Q>(
&self,
path: PathFit<F, Q>,
validation_rows: Vec<usize>,
metric: ValidationMetric,
count: usize,
) -> Result<FoldPath<F, Q>, FitError<M::Error>> {
if path.len() != count {
return Err(invalid(
"every cross-validation path must fit the complete candidate sequence",
));
}
let validation = self.design().select_rows(&validation_rows)?;
let response = validation_rows
.iter()
.map(|&i| self.datafit().response()[i])
.collect::<Vec<_>>();
let scores = path
.fits()
.iter()
.map(|fit| {
let predictor = fit
.predict(&validation)
.map_err(|e| FitError::from_component(e, 0))?;
metric
.score(&response, &predictor)
.map_err(|e| FitError::from_component(e, 0))
})
.collect::<Result<_, _>>()?;
Ok(FoldPath {
validation_rows,
path,
scores,
})
}
}
struct Summary {
means: Vec<f64>,
errors: Vec<f64>,
minimum: usize,
one_standard_error: usize,
selected: usize,
}
fn summarize<F, P, E>(
folds: &[FoldPath<F, P>],
rule: SelectionRule,
) -> Result<Summary, FitError<E>> {
let k = folds.len() as f64;
let mut means = Vec::with_capacity(folds[0].scores.len());
let mut errors = Vec::with_capacity(folds[0].scores.len());
for candidate in 0..folds[0].scores.len() {
let mean = finite(
folds.iter().map(|fold| fold.scores[candidate] / k).sum(),
"averaging validation scores",
0,
)?;
let divisor = k.sqrt() * (k - 1.0).sqrt();
let se = folds.iter().fold(0.0_f64, |norm, fold| {
norm.hypot((fold.scores[candidate] - mean) / divisor)
});
means.push(mean);
errors.push(finite(se, "computing validation standard errors", 0)?);
}
let minimum = (0..means.len()).fold(0, |best, j| if means[j] < means[best] { j } else { best });
let one_standard_error = (0..means.len())
.find(|&j| means[j] <= means[minimum] || means[j] - means[minimum] <= errors[minimum])
.unwrap();
let selected = match rule {
SelectionRule::MinimumError => minimum,
SelectionRule::OneStandardError => one_standard_error,
};
Ok(Summary {
means,
errors,
minimum,
one_standard_error,
selected,
})
}
fn check_convergence<F: ValidationFit, P, E>(
path: &PathFit<F, P>,
fold: Option<usize>,
) -> Result<(), CrossValidationError<E>> {
for (candidate, fit) in path.fits().iter().enumerate() {
if fit.termination() != Termination::Converged {
return Err(CrossValidationError::NonConverged { fold, candidate });
}
}
Ok(())
}
fn finish<F: ValidationFit, P, E>(
cv: &CrossValidation,
metric: ValidationMetric,
folds: Vec<FoldPath<F, P>>,
refit: PathFit<F, P>,
summary: Summary,
fractions: Option<Vec<f64>>,
) -> Result<CrossValidationFit<F, P>, CrossValidationError<E>> {
if refit.len() != summary.means.len() {
return Err(CrossValidationError::Refit {
source: invalid("full-data refit must retain every validation candidate"),
});
}
check_convergence(&refit, None)?;
Ok(CrossValidationFit {
assignments: cv.folds.clone(),
folds,
refit,
mean_scores: summary.means,
standard_errors: summary.errors,
metric,
selection_rule: cv.selection_rule,
minimum: summary.minimum,
one_standard_error: summary.one_standard_error,
selected: summary.selected,
relative_strengths: fractions,
})
}