1use ndarray::{Array1, ArrayView1, ArrayView2};
50use solow_core::{numeric::NeumaierSum, Error, Result};
51
52#[derive(Clone, Debug)]
58pub struct Ridge {
59 pub coef: Array1<f64>,
61 pub intercept: f64,
63 pub alpha: f64,
65 pub fit_intercept: bool,
67}
68
69impl Ridge {
70 pub fn fit(
76 y: ArrayView1<'_, f64>,
77 x: ArrayView2<'_, f64>,
78 alpha: f64,
79 fit_intercept: bool,
80 ) -> Result<Self> {
81 if y.len() != x.nrows() || x.ncols() == 0 {
82 return Err(Error::Shape(format!(
83 "Ridge::fit: shape mismatch (y: {}, x: {}×{})",
84 y.len(),
85 x.nrows(),
86 x.ncols()
87 )));
88 }
89 if !(alpha >= 0.0 && alpha.is_finite()) {
90 return Err(Error::Value(format!(
91 "Ridge::fit: alpha must be finite and ≥ 0 (got {alpha})"
92 )));
93 }
94 let (n, p) = (x.nrows(), x.ncols());
95 let mut x_c = x.to_owned();
97 let mut y_c = y.to_owned();
98 let (mean_x, mean_y) = if fit_intercept {
99 let mut mx = Array1::<f64>::zeros(p);
100 for j in 0..p {
101 mx[j] = compensated_mean(x.column(j).iter().copied(), n);
102 }
103 let my = compensated_mean(y.iter().copied(), n);
104 for j in 0..p {
105 let mj = mx[j];
106 for i in 0..n {
107 x_c[[i, j]] -= mj;
108 }
109 }
110 for i in 0..n {
111 y_c[i] -= my;
112 }
113 (mx, my)
114 } else {
115 (Array1::<f64>::zeros(p), 0.0)
116 };
117 let mut a = vec![vec![0.0_f64; p]; p];
120 let mut b = vec![0.0_f64; p];
121 for i in 0..n {
122 for j in 0..p {
123 let xj = x_c[[i, j]];
124 b[j] += xj * y_c[i];
125 for k in j..p {
126 a[j][k] += xj * x_c[[i, k]];
127 }
128 }
129 }
130 for j in 0..p {
131 for k in 0..j {
132 a[j][k] = a[k][j];
133 }
134 a[j][j] += alpha;
135 }
136 let beta_vec = cholesky_solve(&a, &b)?;
137 let coef = Array1::from(beta_vec);
138 let intercept = if fit_intercept {
139 let mut s = 0.0_f64;
140 for j in 0..p {
141 s += coef[j] * mean_x[j];
142 }
143 mean_y - s
144 } else {
145 0.0
146 };
147 Ok(Self {
148 coef,
149 intercept,
150 alpha,
151 fit_intercept,
152 })
153 }
154
155 pub fn predict(&self, x: ArrayView2<'_, f64>) -> Result<Array1<f64>> {
157 if x.ncols() != self.coef.len() {
158 return Err(Error::Shape(format!(
159 "Ridge::predict: expected {} columns, got {}",
160 self.coef.len(),
161 x.ncols()
162 )));
163 }
164 let mut out = Array1::<f64>::zeros(x.nrows());
165 for i in 0..x.nrows() {
166 let mut s = self.intercept;
167 for j in 0..x.ncols() {
168 s += self.coef[j] * x[[i, j]];
169 }
170 out[i] = s;
171 }
172 Ok(out)
173 }
174}
175
176#[derive(Clone, Debug)]
182pub struct Lasso {
183 pub coef: Array1<f64>,
185 pub intercept: f64,
187 pub alpha: f64,
189 pub fit_intercept: bool,
191 pub n_iter: usize,
193 pub converged: bool,
195}
196
197impl Lasso {
198 pub fn fit(
200 y: ArrayView1<'_, f64>,
201 x: ArrayView2<'_, f64>,
202 alpha: f64,
203 fit_intercept: bool,
204 ) -> Result<Self> {
205 Self::fit_with(y, x, alpha, fit_intercept, 1000, 1e-4)
206 }
207
208 pub fn fit_with(
210 y: ArrayView1<'_, f64>,
211 x: ArrayView2<'_, f64>,
212 alpha: f64,
213 fit_intercept: bool,
214 max_iter: usize,
215 tol: f64,
216 ) -> Result<Self> {
217 let en = ElasticNet::fit_with(y, x, alpha, 1.0, fit_intercept, max_iter, tol)?;
219 Ok(Self {
220 coef: en.coef,
221 intercept: en.intercept,
222 alpha,
223 fit_intercept,
224 n_iter: en.n_iter,
225 converged: en.converged,
226 })
227 }
228
229 pub fn predict(&self, x: ArrayView2<'_, f64>) -> Result<Array1<f64>> {
231 predict_linear(&self.coef, self.intercept, x, "Lasso")
232 }
233}
234
235#[derive(Clone, Debug)]
246pub struct ElasticNet {
247 pub coef: Array1<f64>,
249 pub intercept: f64,
251 pub alpha: f64,
253 pub l1_ratio: f64,
255 pub fit_intercept: bool,
257 pub n_iter: usize,
259 pub converged: bool,
261}
262
263impl ElasticNet {
264 pub fn fit(
266 y: ArrayView1<'_, f64>,
267 x: ArrayView2<'_, f64>,
268 alpha: f64,
269 l1_ratio: f64,
270 fit_intercept: bool,
271 ) -> Result<Self> {
272 Self::fit_with(y, x, alpha, l1_ratio, fit_intercept, 1000, 1e-4)
273 }
274
275 pub fn fit_with(
285 y: ArrayView1<'_, f64>,
286 x: ArrayView2<'_, f64>,
287 alpha: f64,
288 l1_ratio: f64,
289 fit_intercept: bool,
290 max_iter: usize,
291 tol: f64,
292 ) -> Result<Self> {
293 if y.len() != x.nrows() || x.ncols() == 0 {
294 return Err(Error::Shape(format!(
295 "ElasticNet::fit_with: shape mismatch (y: {}, x: {}×{})",
296 y.len(),
297 x.nrows(),
298 x.ncols()
299 )));
300 }
301 if !(alpha >= 0.0 && alpha.is_finite()) {
302 return Err(Error::Value(format!(
303 "ElasticNet::fit_with: alpha must be finite and ≥ 0 (got {alpha})"
304 )));
305 }
306 if !(0.0..=1.0).contains(&l1_ratio) {
307 return Err(Error::Value(format!(
308 "ElasticNet::fit_with: l1_ratio must be in [0, 1] (got {l1_ratio})"
309 )));
310 }
311 let (n, p) = (x.nrows(), x.ncols());
312 let n_f = n as f64;
313
314 let mut x_c = x.to_owned();
316 let mut y_c = y.to_owned();
317 let mean_x: Array1<f64>;
318 let mean_y: f64;
319 if fit_intercept {
320 let mut mx = Array1::<f64>::zeros(p);
321 for j in 0..p {
322 mx[j] = compensated_mean(x.column(j).iter().copied(), n);
323 }
324 mean_y = compensated_mean(y.iter().copied(), n);
325 for j in 0..p {
326 let mj = mx[j];
327 for i in 0..n {
328 x_c[[i, j]] -= mj;
329 }
330 }
331 for i in 0..n {
332 y_c[i] -= mean_y;
333 }
334 mean_x = mx;
335 } else {
336 mean_x = Array1::<f64>::zeros(p);
337 mean_y = 0.0;
338 }
339
340 let mut col_norms = vec![0.0_f64; p];
343 for j in 0..p {
344 let mut s = NeumaierSum::new();
345 for i in 0..n {
346 s.add(x_c[[i, j]] * x_c[[i, j]]);
347 }
348 col_norms[j] = s.finish() / n_f;
349 }
350
351 let l1 = alpha * l1_ratio;
352 let l2 = alpha * (1.0 - l1_ratio);
353 let mut beta = Array1::<f64>::zeros(p);
354 let mut r = y_c.clone();
356
357 let mut n_iter = 0usize;
358 let mut converged = false;
359 for it in 0..max_iter {
360 n_iter = it + 1;
361 let mut max_change = 0.0_f64;
362 for j in 0..p {
363 let denom = col_norms[j] + l2;
364 if denom <= 0.0 {
365 continue;
366 }
367 let bj = beta[j];
370 if bj != 0.0 {
371 for i in 0..n {
372 r[i] += bj * x_c[[i, j]];
373 }
374 }
375 let mut z = NeumaierSum::new();
377 for i in 0..n {
378 z.add(x_c[[i, j]] * r[i]);
379 }
380 let z_j = z.finish() / n_f;
381 let new_bj = soft_threshold(z_j, l1) / denom;
383 if new_bj != 0.0 {
385 for i in 0..n {
386 r[i] -= new_bj * x_c[[i, j]];
387 }
388 }
389 let change = (new_bj - bj).abs();
390 if change > max_change {
391 max_change = change;
392 }
393 beta[j] = new_bj;
394 }
395 if max_change < tol {
396 converged = true;
397 break;
398 }
399 }
400
401 let intercept = if fit_intercept {
402 let mut s = 0.0_f64;
403 for j in 0..p {
404 s += beta[j] * mean_x[j];
405 }
406 mean_y - s
407 } else {
408 0.0
409 };
410 Ok(Self {
411 coef: beta,
412 intercept,
413 alpha,
414 l1_ratio,
415 fit_intercept,
416 n_iter,
417 converged,
418 })
419 }
420
421 pub fn predict(&self, x: ArrayView2<'_, f64>) -> Result<Array1<f64>> {
423 predict_linear(&self.coef, self.intercept, x, "ElasticNet")
424 }
425}
426
427fn soft_threshold(z: f64, lambda: f64) -> f64 {
432 if z > lambda {
433 z - lambda
434 } else if z < -lambda {
435 z + lambda
436 } else {
437 0.0
438 }
439}
440
441fn predict_linear(
442 coef: &Array1<f64>,
443 intercept: f64,
444 x: ArrayView2<'_, f64>,
445 label: &str,
446) -> Result<Array1<f64>> {
447 if x.ncols() != coef.len() {
448 return Err(Error::Shape(format!(
449 "{label}::predict: expected {} columns, got {}",
450 coef.len(),
451 x.ncols()
452 )));
453 }
454 let mut out = Array1::<f64>::zeros(x.nrows());
455 for i in 0..x.nrows() {
456 let mut s = intercept;
457 for j in 0..x.ncols() {
458 s += coef[j] * x[[i, j]];
459 }
460 out[i] = s;
461 }
462 Ok(out)
463}
464
465fn compensated_mean<I: IntoIterator<Item = f64>>(it: I, n: usize) -> f64 {
466 let mut acc = NeumaierSum::new();
467 for v in it {
468 acc.add(v);
469 }
470 acc.finish() / n as f64
471}
472
473fn cholesky_solve(a: &[Vec<f64>], b: &[f64]) -> Result<Vec<f64>> {
475 let n = a.len();
476 let mut l = vec![vec![0.0_f64; n]; n];
478 for i in 0..n {
479 for j in 0..=i {
480 let mut s = a[i][j];
481 for k in 0..j {
482 s -= l[i][k] * l[j][k];
483 }
484 if i == j {
485 if s <= 0.0 {
486 return Err(Error::Value(
487 "Ridge: Cholesky failed — matrix is not positive definite".into(),
488 ));
489 }
490 l[i][j] = s.sqrt();
491 } else {
492 l[i][j] = s / l[j][j];
493 }
494 }
495 }
496 let mut z = vec![0.0_f64; n];
498 for i in 0..n {
499 let mut s = b[i];
500 for k in 0..i {
501 s -= l[i][k] * z[k];
502 }
503 z[i] = s / l[i][i];
504 }
505 let mut x = vec![0.0_f64; n];
507 for i in (0..n).rev() {
508 let mut s = z[i];
509 for k in (i + 1)..n {
510 s -= l[k][i] * x[k];
511 }
512 x[i] = s / l[i][i];
513 }
514 Ok(x)
515}
516
517#[cfg(test)]
518mod tests {
519 use super::*;
520 use approx::assert_abs_diff_eq;
521 use ndarray::array;
522
523 #[test]
524 fn ridge_reduces_to_ols_at_alpha_zero() {
525 let x = array![[1.0], [2.0], [3.0], [4.0], [5.0]];
527 let y = array![5.0, 8.0, 11.0, 14.0, 17.0];
528 let r = Ridge::fit(y.view(), x.view(), 0.0, true).unwrap();
529 assert_abs_diff_eq!(r.intercept, 2.0, epsilon = 1e-9);
530 assert_abs_diff_eq!(r.coef[0], 3.0, epsilon = 1e-9);
531 }
532
533 #[test]
534 fn ridge_shrinks_coefficients_as_alpha_grows() {
535 let x = array![[1.0], [2.0], [3.0], [4.0], [5.0]];
536 let y = array![5.0, 8.0, 11.0, 14.0, 17.0];
537 let a = Ridge::fit(y.view(), x.view(), 0.0, true).unwrap().coef[0];
538 let b = Ridge::fit(y.view(), x.view(), 100.0, true).unwrap().coef[0];
539 assert!(
540 b.abs() < a.abs(),
541 "|β(α=100)| = {b} should shrink below |β(0)| = {a}"
542 );
543 }
544
545 #[test]
546 fn lasso_at_large_alpha_zeroes_all_coefficients() {
547 let x = array![[1.0, 0.5], [2.0, -0.3], [3.0, 1.2], [4.0, -0.8]];
548 let y = array![2.0, 4.0, 6.0, 8.0];
549 let l = Lasso::fit(y.view(), x.view(), 1e6, true).unwrap();
551 for &b in l.coef.iter() {
552 assert_abs_diff_eq!(b, 0.0, epsilon = 1e-9);
553 }
554 assert_abs_diff_eq!(l.intercept, 5.0, epsilon = 1e-9);
556 }
557
558 #[test]
559 fn lasso_recovers_linear_signal_at_small_alpha() {
560 let x = array![[1.0, 5.0], [2.0, -3.0], [3.0, 4.0], [4.0, 0.0], [5.0, 2.0]];
563 let y = array![4.0, 7.0, 10.0, 13.0, 16.0];
564 let l = Lasso::fit_with(y.view(), x.view(), 0.01, true, 5000, 1e-6).unwrap();
565 assert!((l.coef[0] - 3.0).abs() < 0.1, "coef[0] = {}", l.coef[0]);
566 assert!(l.coef[1].abs() < 0.1, "coef[1] = {}", l.coef[1]);
567 }
568
569 #[test]
570 fn elastic_net_interpolates_between_ridge_and_lasso() {
571 let x = array![[1.0, 5.0], [2.0, -3.0], [3.0, 4.0], [4.0, 0.0], [5.0, 2.0]];
572 let y = array![4.0, 7.0, 10.0, 13.0, 16.0];
573 let en_lasso_like = ElasticNet::fit(y.view(), x.view(), 0.5, 1.0, true).unwrap();
574 let en_ridge_like = ElasticNet::fit(y.view(), x.view(), 0.5, 0.0, true).unwrap();
575 assert!(
577 en_lasso_like.coef[1].abs() <= en_ridge_like.coef[1].abs() + 1e-9,
578 "expected the l1-like fit to shrink coef[1] at least as much as the l2-like fit"
579 );
580 }
581}