use crate::math::squared_euclidean_distance_row;
use crate::parallel_gates::{cheap_map_f64_parallel_threshold, exp_map_f64_parallel_threshold};
use crate::{Deserialize, Serialize};
use gemmkit_ndarray::dot;
use ndarray::{Array2, ArrayBase, ArrayView1, Axis, Data, Ix2, Zip};
#[derive(Debug, Clone, Copy, PartialEq, Deserialize, Serialize)]
pub enum RegularizationType {
L1(f64),
L2(f64),
}
#[derive(Debug, Copy, Clone, PartialEq, Deserialize, Serialize)]
pub enum Gamma {
Scale,
Auto,
Value(f64),
}
impl Gamma {
pub fn resolve(self, n_features: usize, x_variance: f64) -> Result<f64, crate::error::Error> {
if n_features == 0 {
return Err(crate::error::Error::invalid_input(
"cannot resolve gamma: data has zero features",
));
}
let value = match self {
Gamma::Scale => {
if x_variance <= 0.0 || !x_variance.is_finite() {
return Err(crate::error::Error::invalid_input(
"cannot use Gamma::Scale: training data has zero (or non-finite) variance",
));
}
1.0 / (n_features as f64 * x_variance)
}
Gamma::Auto => 1.0 / n_features as f64,
Gamma::Value(v) => v,
};
Ok(value)
}
fn value(self) -> f64 {
match self {
Gamma::Value(v) => v,
Gamma::Scale | Gamma::Auto => {
panic!("kernel gamma must be resolved (Gamma::resolve) before kernel evaluation")
}
}
}
pub(crate) fn explicit_is_finite(self) -> bool {
match self {
Gamma::Value(v) => v.is_finite(),
Gamma::Scale | Gamma::Auto => true,
}
}
pub(crate) fn explicit_is_positive(self) -> bool {
match self {
Gamma::Value(v) => v.is_finite() && v > 0.0,
Gamma::Scale | Gamma::Auto => true,
}
}
}
#[derive(Debug, Copy, Clone, PartialEq, Deserialize, Serialize)]
pub enum KernelType {
Linear,
Poly {
degree: u32,
gamma: Gamma,
coef0: f64,
},
RBF {
gamma: Gamma,
},
Sigmoid {
gamma: Gamma,
coef0: f64,
},
Cosine,
}
impl KernelType {
pub fn resolve_gamma(
&self,
n_features: usize,
x_variance: f64,
) -> Result<KernelType, crate::error::Error> {
Ok(match *self {
KernelType::Poly {
degree,
gamma,
coef0,
} => KernelType::Poly {
degree,
gamma: Gamma::Value(gamma.resolve(n_features, x_variance)?),
coef0,
},
KernelType::RBF { gamma } => KernelType::RBF {
gamma: Gamma::Value(gamma.resolve(n_features, x_variance)?),
},
KernelType::Sigmoid { gamma, coef0 } => KernelType::Sigmoid {
gamma: Gamma::Value(gamma.resolve(n_features, x_variance)?),
coef0,
},
other => other,
})
}
}
impl KernelType {
#[inline]
pub fn compute(&self, x1: ArrayView1<f64>, x2: ArrayView1<f64>) -> f64 {
match *self {
KernelType::Linear => x1.dot(&x2),
KernelType::Poly {
degree,
gamma,
coef0,
} => (gamma.value() * x1.dot(&x2) + coef0).powi(degree as i32),
KernelType::RBF { gamma } => {
let squared_norm = squared_euclidean_distance_row(&x1, &x2);
(-gamma.value() * squared_norm).exp()
}
KernelType::Sigmoid { gamma, coef0 } => (gamma.value() * x1.dot(&x2) + coef0).tanh(),
KernelType::Cosine => {
let norm_product = (x1.dot(&x1) * x2.dot(&x2)).sqrt();
if norm_product <= f64::EPSILON {
0.0
} else {
x1.dot(&x2) / norm_product
}
}
}
}
pub fn compute_matrix<S1, S2>(
&self,
x: &ArrayBase<S1, Ix2>,
y: &ArrayBase<S2, Ix2>,
) -> Array2<f64>
where
S1: Data<Elem = f64> + Sync,
S2: Data<Elem = f64> + Sync,
{
let mut k = dot(x, &y.t());
let elems = k.len();
match *self {
KernelType::Linear => {}
KernelType::Poly {
degree,
gamma,
coef0,
} => {
let degree = degree as i32;
let gamma = gamma.value();
let f = |v: f64| (gamma * v + coef0).powi(degree);
if elems >= cheap_map_f64_parallel_threshold() {
k.par_mapv_inplace(f);
} else {
k.mapv_inplace(f);
}
}
KernelType::Sigmoid { gamma, coef0 } => {
let gamma = gamma.value();
let f = |v: f64| (gamma * v + coef0).tanh();
if elems >= exp_map_f64_parallel_threshold() {
k.par_mapv_inplace(f);
} else {
k.mapv_inplace(f);
}
}
KernelType::RBF { gamma } => {
let gamma = gamma.value();
let x_norm_sq = x.map_axis(Axis(1), |row| row.dot(&row));
let y_norm_sq = y.map_axis(Axis(1), |row| row.dot(&row));
let transform_row = |mut k_row: ndarray::ArrayViewMut1<f64>, &x_sq: &f64| {
Zip::from(&mut k_row).and(&y_norm_sq).for_each(|v, &y_sq| {
let dist = (x_sq + y_sq - 2.0 * *v).max(0.0);
*v = (-gamma * dist).exp();
});
};
let zip = Zip::from(k.rows_mut()).and(&x_norm_sq);
if elems >= exp_map_f64_parallel_threshold() {
zip.par_for_each(transform_row);
} else {
zip.for_each(transform_row);
}
}
KernelType::Cosine => {
let x_norm_sq = x.map_axis(Axis(1), |row| row.dot(&row));
let y_norm_sq = y.map_axis(Axis(1), |row| row.dot(&row));
let transform_row = |mut k_row: ndarray::ArrayViewMut1<f64>, &x_sq: &f64| {
Zip::from(&mut k_row).and(&y_norm_sq).for_each(|v, &y_sq| {
let norm_product = (x_sq * y_sq).sqrt();
*v = if norm_product <= f64::EPSILON {
0.0
} else {
*v / norm_product
};
});
};
let zip = Zip::from(k.rows_mut()).and(&x_norm_sq);
if elems >= cheap_map_f64_parallel_threshold() {
zip.par_for_each(transform_row);
} else {
zip.for_each(transform_row);
}
}
}
k
}
}
#[cfg(test)]
mod tests {
use super::*;
use approx::assert_abs_diff_eq;
use ndarray::array;
#[test]
fn gamma_scale_resolves_to_inverse_features_times_variance() {
let n_features = 4;
let x_var = 2.5;
let g = Gamma::Scale.resolve(n_features, x_var).unwrap();
assert_abs_diff_eq!(g, 1.0 / (4.0 * 2.5), epsilon = 1e-12);
}
#[test]
fn gamma_auto_resolves_to_inverse_features() {
let g = Gamma::Auto.resolve(5, 999.0).unwrap();
assert_abs_diff_eq!(g, 1.0 / 5.0, epsilon = 1e-12);
}
#[test]
fn gamma_value_resolves_to_itself() {
let g = Gamma::Value(0.73).resolve(3, 10.0).unwrap();
assert_abs_diff_eq!(g, 0.73, epsilon = 1e-12);
}
#[test]
fn gamma_scale_errors_on_zero_variance() {
assert!(Gamma::Scale.resolve(3, 0.0).is_err());
assert!(Gamma::Auto.resolve(3, 0.0).is_ok());
assert!(Gamma::Value(1.0).resolve(3, 0.0).is_ok());
}
#[test]
fn kernel_resolve_gamma_produces_value_variant() {
let resolved = KernelType::RBF { gamma: Gamma::Auto }
.resolve_gamma(8, 1.0)
.unwrap();
assert_eq!(
resolved,
KernelType::RBF {
gamma: Gamma::Value(1.0 / 8.0)
}
);
assert_eq!(
KernelType::Linear.resolve_gamma(8, 1.0).unwrap(),
KernelType::Linear
);
}
#[test]
fn kernel_linear_orthogonal_vectors() {
let k = KernelType::Linear;
let x1 = array![1.0_f64, 0.0];
let x2 = array![0.0_f64, 1.0];
assert_abs_diff_eq!(k.compute(x1.view(), x2.view()), 0.0, epsilon = 1e-6);
}
#[test]
fn kernel_linear_general_vectors() {
let k = KernelType::Linear;
let x1 = array![1.0_f64, 2.0];
let x2 = array![3.0_f64, 4.0];
assert_abs_diff_eq!(k.compute(x1.view(), x2.view()), 11.0, epsilon = 1e-6);
}
#[test]
fn kernel_rbf_identical_vectors() {
let k = KernelType::RBF {
gamma: Gamma::Value(1.0),
};
let x = array![1.0_f64, 0.0];
assert_abs_diff_eq!(k.compute(x.view(), x.view()), 1.0, epsilon = 1e-6);
}
#[test]
fn kernel_rbf_orthogonal_unit_vectors() {
let k = KernelType::RBF {
gamma: Gamma::Value(1.0),
};
let x1 = array![1.0_f64, 0.0];
let x2 = array![0.0_f64, 1.0];
let expected = (-2.0_f64).exp(); assert_abs_diff_eq!(k.compute(x1.view(), x2.view()), expected, epsilon = 1e-6);
}
#[test]
fn kernel_poly_degree2_orthogonal() {
let k = KernelType::Poly {
degree: 2,
gamma: Gamma::Value(1.0),
coef0: 0.0,
};
let x1 = array![1.0_f64, 0.0];
let x2 = array![0.0_f64, 1.0];
assert_abs_diff_eq!(k.compute(x1.view(), x2.view()), 0.0, epsilon = 1e-6);
}
#[test]
fn kernel_poly_degree3_general() {
let k = KernelType::Poly {
degree: 3,
gamma: Gamma::Value(2.0),
coef0: 1.0,
};
let x1 = array![1.0_f64, 1.0];
let x2 = array![1.0_f64, 1.0];
assert_abs_diff_eq!(k.compute(x1.view(), x2.view()), 125.0, epsilon = 1e-6);
}
#[test]
fn kernel_sigmoid_unit_vector() {
let k = KernelType::Sigmoid {
gamma: Gamma::Value(1.0),
coef0: 0.0,
};
let x = array![1.0_f64, 0.0];
let expected = 1.0_f64.tanh(); assert_abs_diff_eq!(k.compute(x.view(), x.view()), expected, epsilon = 1e-6);
}
#[test]
fn kernel_cosine_zero_vector() {
let k = KernelType::Cosine;
let zero = array![0.0_f64, 0.0];
let other = array![1.0_f64, 2.0];
assert_abs_diff_eq!(k.compute(zero.view(), other.view()), 0.0, epsilon = 1e-6);
}
#[test]
fn kernel_cosine_identical_vectors() {
let k = KernelType::Cosine;
let x = array![1.0_f64, 0.0];
assert_abs_diff_eq!(k.compute(x.view(), x.view()), 1.0, epsilon = 1e-6);
}
#[test]
fn kernel_cosine_orthogonal_vectors() {
let k = KernelType::Cosine;
let x1 = array![1.0_f64, 0.0];
let x2 = array![0.0_f64, 1.0];
assert_abs_diff_eq!(k.compute(x1.view(), x2.view()), 0.0, epsilon = 1e-6);
}
#[test]
fn compute_matrix_matches_pairwise() {
use ndarray::Array2;
let x = Array2::from_shape_fn((5, 3), |(i, j)| ((i * 3 + j) as f64) * 0.3 - 1.1);
let y = Array2::from_shape_fn((4, 3), |(i, j)| ((i + 2 * j) as f64) * 0.2 + 0.4);
let kernels = [
KernelType::Linear,
KernelType::Poly {
degree: 3,
gamma: Gamma::Value(0.5),
coef0: 1.0,
},
KernelType::RBF {
gamma: Gamma::Value(0.7),
},
KernelType::Sigmoid {
gamma: Gamma::Value(0.3),
coef0: -0.2,
},
KernelType::Cosine,
];
for k in kernels {
let gram = k.compute_matrix(&x, &x);
for i in 0..x.nrows() {
for j in 0..x.nrows() {
assert_abs_diff_eq!(
gram[[i, j]],
k.compute(x.row(i), x.row(j)),
epsilon = 1e-9
);
}
}
let cross = k.compute_matrix(&x, &y);
assert_eq!(cross.dim(), (x.nrows(), y.nrows()));
for i in 0..x.nrows() {
for j in 0..y.nrows() {
assert_abs_diff_eq!(
cross[[i, j]],
k.compute(x.row(i), y.row(j)),
epsilon = 1e-9
);
}
}
}
}
#[test]
fn compute_matrix_rbf_diagonal_is_one() {
use ndarray::Array2;
let x = Array2::from_shape_fn((6, 4), |(i, j)| ((i * 4 + j) as f64).sin());
let gram = KernelType::RBF {
gamma: Gamma::Value(1.3),
}
.compute_matrix(&x, &x);
for i in 0..x.nrows() {
assert_abs_diff_eq!(gram[[i, i]], 1.0, epsilon = 1e-12);
}
}
#[test]
fn compute_matrix_cosine_zero_row_guard() {
use ndarray::Array2;
let mut x = Array2::from_shape_fn((4, 3), |(i, j)| (i + j) as f64 + 1.0);
x.row_mut(2).fill(0.0); let m = KernelType::Cosine.compute_matrix(&x, &x);
for j in 0..x.nrows() {
assert_abs_diff_eq!(m[[2, j]], 0.0, epsilon = 1e-12);
assert_abs_diff_eq!(m[[j, 2]], 0.0, epsilon = 1e-12);
}
}
}