sklears_kernel_approximation/
budget_constrained.rs

1//! Budget-constrained kernel approximation methods
2//!
3//! This module provides kernel approximation methods that operate within
4//! specified computational budgets for time, memory, or operations.
5
6use crate::{Nystroem, RBFSampler};
7use scirs2_core::ndarray::Array2;
8use scirs2_linalg::compat::Norm;
9use sklears_core::{
10    error::Result,
11    traits::{Fit, Transform},
12};
13use std::collections::HashMap;
14use std::time::Instant;
15
16/// Budget constraint types
17#[derive(Debug, Clone)]
18/// BudgetConstraint
19pub enum BudgetConstraint {
20    /// Time budget in seconds
21    Time { max_seconds: f64 },
22    /// Memory budget in bytes
23    Memory { max_bytes: usize },
24    /// Operations budget (approximate number of operations)
25    Operations { max_operations: usize },
26    /// Combined budget with multiple constraints
27    Combined {
28        max_seconds: Option<f64>,
29
30        max_bytes: Option<usize>,
31        max_operations: Option<usize>,
32    },
33}
34
35/// Budget usage tracking
36#[derive(Debug, Clone)]
37/// BudgetUsage
38pub struct BudgetUsage {
39    /// Time used in seconds
40    pub time_used: f64,
41    /// Memory used in bytes
42    pub memory_used: usize,
43    /// Operations performed
44    pub operations_used: usize,
45}
46
47impl Default for BudgetUsage {
48    fn default() -> Self {
49        Self::new()
50    }
51}
52
53impl BudgetUsage {
54    /// Create a new budget usage tracker
55    pub fn new() -> Self {
56        Self {
57            time_used: 0.0,
58            memory_used: 0,
59            operations_used: 0,
60        }
61    }
62
63    /// Check if budget is within constraints
64    pub fn is_within_budget(&self, constraint: &BudgetConstraint) -> bool {
65        match constraint {
66            BudgetConstraint::Time { max_seconds } => self.time_used <= *max_seconds,
67            BudgetConstraint::Memory { max_bytes } => self.memory_used <= *max_bytes,
68            BudgetConstraint::Operations { max_operations } => {
69                self.operations_used <= *max_operations
70            }
71            BudgetConstraint::Combined {
72                max_seconds,
73                max_bytes,
74                max_operations,
75            } => {
76                let time_ok = max_seconds.map_or(true, |max| self.time_used <= max);
77                let memory_ok = max_bytes.map_or(true, |max| self.memory_used <= max);
78                let ops_ok = max_operations.map_or(true, |max| self.operations_used <= max);
79                time_ok && memory_ok && ops_ok
80            }
81        }
82    }
83}
84
85/// Optimization strategy for budget-constrained approximation
86#[derive(Debug, Clone)]
87/// OptimizationStrategy
88pub enum OptimizationStrategy {
89    /// Maximize approximation quality within budget
90    MaxQuality,
91    /// Minimize computational cost for target quality
92    MinCost { target_quality: f64 },
93    /// Balance quality and cost
94    Balanced {
95        quality_weight: f64,
96
97        cost_weight: f64,
98    },
99    /// Greedy approach - stop when budget is exhausted
100    Greedy,
101}
102
103/// Configuration for budget-constrained approximation
104#[derive(Debug, Clone)]
105/// BudgetConstrainedConfig
106pub struct BudgetConstrainedConfig {
107    /// Budget constraint
108    pub budget: BudgetConstraint,
109    /// Optimization strategy
110    pub strategy: OptimizationStrategy,
111    /// Minimum number of components to test
112    pub min_components: usize,
113    /// Maximum number of components to test
114    pub max_components: usize,
115    /// Step size for component search
116    pub step_size: usize,
117    /// Number of trials for each configuration
118    pub n_trials: usize,
119    /// Random seed for reproducibility
120    pub random_seed: Option<u64>,
121    /// Early stopping tolerance
122    pub early_stopping_tolerance: f64,
123}
124
125impl Default for BudgetConstrainedConfig {
126    fn default() -> Self {
127        Self {
128            budget: BudgetConstraint::Time { max_seconds: 10.0 },
129            strategy: OptimizationStrategy::MaxQuality,
130            min_components: 10,
131            max_components: 1000,
132            step_size: 10,
133            n_trials: 3,
134            random_seed: None,
135            early_stopping_tolerance: 0.01,
136        }
137    }
138}
139
140/// Result from budget-constrained optimization
141#[derive(Debug, Clone)]
142/// BudgetOptimizationResult
143pub struct BudgetOptimizationResult {
144    /// Optimal number of components
145    pub optimal_components: usize,
146    /// Quality score achieved
147    pub quality_score: f64,
148    /// Budget usage
149    pub budget_usage: BudgetUsage,
150    /// All tested configurations
151    pub tested_configs: HashMap<usize, (f64, BudgetUsage)>,
152    /// Whether optimization completed or was stopped due to budget
153    pub completed: bool,
154}
155
156/// Budget-constrained RBF sampler
157#[derive(Debug, Clone)]
158/// BudgetConstrainedRBFSampler
159pub struct BudgetConstrainedRBFSampler {
160    gamma: f64,
161    config: BudgetConstrainedConfig,
162}
163
164impl Default for BudgetConstrainedRBFSampler {
165    fn default() -> Self {
166        Self::new()
167    }
168}
169
170impl BudgetConstrainedRBFSampler {
171    /// Create a new budget-constrained RBF sampler
172    pub fn new() -> Self {
173        Self {
174            gamma: 1.0,
175            config: BudgetConstrainedConfig::default(),
176        }
177    }
178
179    /// Set gamma parameter
180    pub fn gamma(mut self, gamma: f64) -> Self {
181        self.gamma = gamma;
182        self
183    }
184
185    /// Set configuration
186    pub fn config(mut self, config: BudgetConstrainedConfig) -> Self {
187        self.config = config;
188        self
189    }
190
191    /// Set budget constraint
192    pub fn budget(mut self, budget: BudgetConstraint) -> Self {
193        self.config.budget = budget;
194        self
195    }
196
197    /// Set optimization strategy
198    pub fn strategy(mut self, strategy: OptimizationStrategy) -> Self {
199        self.config.strategy = strategy;
200        self
201    }
202
203    /// Find optimal configuration within budget
204    pub fn find_optimal_config(&self, x: &Array2<f64>) -> Result<BudgetOptimizationResult> {
205        let _start_time = Instant::now();
206        let mut total_usage = BudgetUsage::new();
207        let mut tested_configs = HashMap::new();
208        let mut best_quality = f64::NEG_INFINITY;
209        let mut best_components = self.config.min_components;
210        let mut completed = true;
211
212        // Split data for validation
213        let n_samples = x.nrows();
214        let split_idx = (n_samples as f64 * 0.8) as usize;
215        let x_train = x
216            .slice(scirs2_core::ndarray::s![..split_idx, ..])
217            .to_owned();
218        let x_val = x
219            .slice(scirs2_core::ndarray::s![split_idx.., ..])
220            .to_owned();
221
222        // Test different numbers of components
223        for n_components in
224            (self.config.min_components..=self.config.max_components).step_by(self.config.step_size)
225        {
226            let _config_start = Instant::now();
227            let mut config_usage = BudgetUsage::new();
228            let mut trial_qualities = Vec::new();
229
230            // Check if we have budget for this configuration
231            if !total_usage.is_within_budget(&self.config.budget) {
232                completed = false;
233                break;
234            }
235
236            // Run multiple trials
237            for trial in 0..self.config.n_trials {
238                let trial_start = Instant::now();
239
240                // Create sampler
241                let seed = self.config.random_seed.map(|s| s + trial as u64);
242                let sampler = if let Some(s) = seed {
243                    RBFSampler::new(n_components)
244                        .gamma(self.gamma)
245                        .random_state(s)
246                } else {
247                    RBFSampler::new(n_components).gamma(self.gamma)
248                };
249
250                // Fit and transform
251                let fitted = sampler.fit(&x_train, &())?;
252                let _x_train_transformed = fitted.transform(&x_train)?;
253                let x_val_transformed = fitted.transform(&x_val)?;
254
255                // Compute quality
256                let quality = self.compute_quality(&x_val, &x_val_transformed)?;
257                trial_qualities.push(quality);
258
259                // Update trial usage
260                let trial_time = trial_start.elapsed().as_secs_f64();
261                config_usage.time_used += trial_time;
262                config_usage.memory_used += self.estimate_memory_usage(n_components, x.ncols());
263                config_usage.operations_used += self.estimate_operations(n_components, x.nrows());
264
265                // Check budget constraints
266                if !config_usage.is_within_budget(&self.config.budget) {
267                    completed = false;
268                    break;
269                }
270            }
271
272            // Average quality across trials
273            let avg_quality = trial_qualities.iter().sum::<f64>() / trial_qualities.len() as f64;
274
275            // Update total usage
276            total_usage.time_used += config_usage.time_used;
277            total_usage.memory_used = total_usage.memory_used.max(config_usage.memory_used);
278            total_usage.operations_used += config_usage.operations_used;
279
280            // Store configuration result
281            tested_configs.insert(n_components, (avg_quality, config_usage));
282
283            // Update best configuration based on strategy
284            if self.is_better_config(avg_quality, n_components, best_quality, best_components) {
285                best_quality = avg_quality;
286                best_components = n_components;
287            }
288
289            // Early stopping check
290            if self.should_stop_early(avg_quality, &tested_configs) {
291                break;
292            }
293
294            // Check if we're out of budget
295            if !total_usage.is_within_budget(&self.config.budget) {
296                completed = false;
297                break;
298            }
299        }
300
301        Ok(BudgetOptimizationResult {
302            optimal_components: best_components,
303            quality_score: best_quality,
304            budget_usage: total_usage,
305            tested_configs,
306            completed,
307        })
308    }
309
310    /// Compute quality score for transformed data
311    fn compute_quality(&self, x: &Array2<f64>, x_transformed: &Array2<f64>) -> Result<f64> {
312        // Compute reconstruction quality (simplified)
313        let n_samples = x.nrows().min(100); // Limit for efficiency
314        let x_subset = x.slice(scirs2_core::ndarray::s![..n_samples, ..]);
315        let x_transformed_subset = x_transformed.slice(scirs2_core::ndarray::s![..n_samples, ..]);
316
317        // Compute approximate kernel matrix
318        let k_approx = x_transformed_subset.dot(&x_transformed_subset.t());
319
320        // Compute exact kernel matrix (small subset)
321        let mut k_exact = Array2::zeros((n_samples, n_samples));
322        for i in 0..n_samples {
323            for j in 0..n_samples {
324                let diff = &x_subset.row(i) - &x_subset.row(j);
325                let squared_norm = diff.dot(&diff);
326                k_exact[[i, j]] = (-self.gamma * squared_norm).exp();
327            }
328        }
329
330        // Compute alignment score
331        let k_exact_norm = k_exact.norm_l2();
332        let k_approx_norm = k_approx.norm_l2();
333        let alignment = if k_exact_norm > 1e-12 && k_approx_norm > 1e-12 {
334            (&k_exact * &k_approx).sum() / (k_exact_norm * k_approx_norm)
335        } else {
336            0.0
337        };
338
339        Ok(alignment)
340    }
341
342    /// Estimate memory usage for a given configuration
343    fn estimate_memory_usage(&self, n_components: usize, n_features: usize) -> usize {
344        // Rough estimate: components * features * sizeof(f64) + overhead
345        n_components * n_features * 8 + 1024
346    }
347
348    /// Estimate number of operations for a given configuration
349    fn estimate_operations(&self, n_components: usize, n_samples: usize) -> usize {
350        // Rough estimate: fitting + transformation operations
351        n_components * n_samples * 10
352    }
353
354    /// Check if a configuration is better based on optimization strategy
355    fn is_better_config(
356        &self,
357        quality: f64,
358        components: usize,
359        best_quality: f64,
360        best_components: usize,
361    ) -> bool {
362        match &self.config.strategy {
363            OptimizationStrategy::MaxQuality => quality > best_quality,
364            OptimizationStrategy::MinCost { target_quality } => {
365                if quality >= *target_quality {
366                    components < best_components || best_quality < *target_quality
367                } else {
368                    quality > best_quality
369                }
370            }
371            OptimizationStrategy::Balanced {
372                quality_weight,
373                cost_weight,
374            } => {
375                let score = quality * quality_weight - (components as f64) * cost_weight;
376                let best_score =
377                    best_quality * quality_weight - (best_components as f64) * cost_weight;
378                score > best_score
379            }
380            OptimizationStrategy::Greedy => quality > best_quality,
381        }
382    }
383
384    /// Check if early stopping should be applied
385    fn should_stop_early(
386        &self,
387        _current_quality: f64,
388        tested_configs: &HashMap<usize, (f64, BudgetUsage)>,
389    ) -> bool {
390        if tested_configs.len() < 3 {
391            return false;
392        }
393
394        // Check if improvement is minimal
395        let mut recent_qualities: Vec<f64> = tested_configs
396            .values()
397            .map(|(quality, _)| *quality)
398            .collect();
399        recent_qualities.sort_by(|a, b| a.partial_cmp(b).unwrap_or(std::cmp::Ordering::Equal));
400
401        let n = recent_qualities.len();
402        if n >= 3 {
403            let improvement = recent_qualities[n - 1] - recent_qualities[n - 3];
404            improvement < self.config.early_stopping_tolerance
405        } else {
406            false
407        }
408    }
409}
410
411/// Fitted budget-constrained RBF sampler
412pub struct FittedBudgetConstrainedRBFSampler {
413    fitted_rbf: crate::rbf_sampler::RBFSampler<sklears_core::traits::Trained>,
414    optimization_result: BudgetOptimizationResult,
415}
416
417impl Fit<Array2<f64>, ()> for BudgetConstrainedRBFSampler {
418    type Fitted = FittedBudgetConstrainedRBFSampler;
419
420    fn fit(self, x: &Array2<f64>, _y: &()) -> Result<Self::Fitted> {
421        // Find optimal configuration within budget
422        let optimization_result = self.find_optimal_config(x)?;
423
424        // Fit RBF sampler with optimal configuration
425        let rbf_sampler = RBFSampler::new(optimization_result.optimal_components).gamma(self.gamma);
426        let fitted_rbf = rbf_sampler.fit(x, &())?;
427
428        Ok(FittedBudgetConstrainedRBFSampler {
429            fitted_rbf,
430            optimization_result,
431        })
432    }
433}
434
435impl Transform<Array2<f64>, Array2<f64>> for FittedBudgetConstrainedRBFSampler {
436    fn transform(&self, x: &Array2<f64>) -> Result<Array2<f64>> {
437        self.fitted_rbf.transform(x)
438    }
439}
440
441impl FittedBudgetConstrainedRBFSampler {
442    /// Get the optimization result
443    pub fn optimization_result(&self) -> &BudgetOptimizationResult {
444        &self.optimization_result
445    }
446
447    /// Get the optimal number of components
448    pub fn optimal_components(&self) -> usize {
449        self.optimization_result.optimal_components
450    }
451
452    /// Get the quality score
453    pub fn quality_score(&self) -> f64 {
454        self.optimization_result.quality_score
455    }
456
457    /// Get the budget usage
458    pub fn budget_usage(&self) -> &BudgetUsage {
459        &self.optimization_result.budget_usage
460    }
461
462    /// Check if optimization completed within budget
463    pub fn completed(&self) -> bool {
464        self.optimization_result.completed
465    }
466}
467
468/// Budget-constrained Nyström method
469#[derive(Debug, Clone)]
470/// BudgetConstrainedNystroem
471pub struct BudgetConstrainedNystroem {
472    kernel: crate::nystroem::Kernel,
473    config: BudgetConstrainedConfig,
474}
475
476impl Default for BudgetConstrainedNystroem {
477    fn default() -> Self {
478        Self::new()
479    }
480}
481
482impl BudgetConstrainedNystroem {
483    /// Create a new budget-constrained Nyström method
484    pub fn new() -> Self {
485        Self {
486            kernel: crate::nystroem::Kernel::Rbf { gamma: 1.0 },
487            config: BudgetConstrainedConfig::default(),
488        }
489    }
490
491    /// Set kernel type
492    pub fn kernel(mut self, kernel: crate::nystroem::Kernel) -> Self {
493        self.kernel = kernel;
494        self
495    }
496
497    /// Set gamma parameter (for RBF kernel)
498    pub fn gamma(mut self, gamma: f64) -> Self {
499        self.kernel = crate::nystroem::Kernel::Rbf { gamma };
500        self
501    }
502
503    /// Set configuration
504    pub fn config(mut self, config: BudgetConstrainedConfig) -> Self {
505        self.config = config;
506        self
507    }
508
509    /// Find optimal configuration within budget
510    pub fn find_optimal_config(&self, x: &Array2<f64>) -> Result<BudgetOptimizationResult> {
511        let _start_time = Instant::now();
512        let mut total_usage = BudgetUsage::new();
513        let mut tested_configs = HashMap::new();
514        let mut best_quality = f64::NEG_INFINITY;
515        let mut best_components = self.config.min_components;
516        let mut completed = true;
517
518        // Test different numbers of components
519        for n_components in
520            (self.config.min_components..=self.config.max_components).step_by(self.config.step_size)
521        {
522            let _config_start = Instant::now();
523            let mut config_usage = BudgetUsage::new();
524            let mut trial_qualities = Vec::new();
525
526            // Check if we have budget for this configuration
527            if !total_usage.is_within_budget(&self.config.budget) {
528                completed = false;
529                break;
530            }
531
532            // Run multiple trials
533            for trial in 0..self.config.n_trials {
534                let trial_start = Instant::now();
535
536                // Create Nyström method
537                let seed = self.config.random_seed.map(|s| s + trial as u64);
538                let nystroem = if let Some(s) = seed {
539                    Nystroem::new(self.kernel.clone(), n_components).random_state(s)
540                } else {
541                    Nystroem::new(self.kernel.clone(), n_components)
542                };
543
544                // Fit and transform
545                let fitted = nystroem.fit(x, &())?;
546                let x_transformed = fitted.transform(x)?;
547
548                // Compute quality (simplified)
549                let quality = self.compute_nystroem_quality(&x_transformed)?;
550                trial_qualities.push(quality);
551
552                // Update trial usage
553                let trial_time = trial_start.elapsed().as_secs_f64();
554                config_usage.time_used += trial_time;
555                config_usage.memory_used += n_components * x.ncols() * 8;
556                config_usage.operations_used += n_components * x.nrows() * 5;
557
558                // Check budget constraints
559                if !config_usage.is_within_budget(&self.config.budget) {
560                    completed = false;
561                    break;
562                }
563            }
564
565            // Average quality across trials
566            let avg_quality = trial_qualities.iter().sum::<f64>() / trial_qualities.len() as f64;
567
568            // Update total usage
569            total_usage.time_used += config_usage.time_used;
570            total_usage.memory_used = total_usage.memory_used.max(config_usage.memory_used);
571            total_usage.operations_used += config_usage.operations_used;
572
573            // Store configuration result
574            tested_configs.insert(n_components, (avg_quality, config_usage));
575
576            // Update best configuration
577            if avg_quality > best_quality {
578                best_quality = avg_quality;
579                best_components = n_components;
580            }
581
582            // Check if we're out of budget
583            if !total_usage.is_within_budget(&self.config.budget) {
584                completed = false;
585                break;
586            }
587        }
588
589        Ok(BudgetOptimizationResult {
590            optimal_components: best_components,
591            quality_score: best_quality,
592            budget_usage: total_usage,
593            tested_configs,
594            completed,
595        })
596    }
597
598    /// Compute quality score for Nyström approximation
599    ///
600    /// Uses trace-based effective rank estimation: effective_rank = trace(X^T X)^2 / trace((X^T X)^2)
601    /// This avoids expensive eigendecomposition/SVD while providing a good quality metric.
602    fn compute_nystroem_quality(&self, x_transformed: &Array2<f64>) -> Result<f64> {
603        // Compute X^T X which is (n_components x n_components) - much smaller than X
604        let xtx = x_transformed.t().dot(x_transformed);
605        let n = xtx.nrows();
606
607        // trace(X^T X) = sum of diagonal elements
608        let trace_xtx: f64 = (0..n).map(|i| xtx[[i, i]]).sum();
609
610        if trace_xtx <= 1e-12 {
611            return Ok(0.0);
612        }
613
614        // trace((X^T X)^2) = sum of squared elements of X^T X (for symmetric matrices)
615        // Because trace(A^2) = sum_{i,j} A_{ij}^2 = ||A||_F^2
616        let trace_xtx_sq: f64 = xtx.iter().map(|&x| x * x).sum();
617
618        if trace_xtx_sq <= 1e-24 {
619            return Ok(0.0);
620        }
621
622        // Effective rank = trace(A)^2 / trace(A^2) (a.k.a. participation ratio)
623        // This ranges from 1 (rank-1 matrix) to n (full rank with equal eigenvalues)
624        let effective_rank = (trace_xtx * trace_xtx) / trace_xtx_sq;
625
626        Ok(effective_rank)
627    }
628}
629
630/// Fitted budget-constrained Nyström method
631pub struct FittedBudgetConstrainedNystroem {
632    fitted_nystroem: crate::nystroem::Nystroem<sklears_core::traits::Trained>,
633    optimization_result: BudgetOptimizationResult,
634}
635
636impl Fit<Array2<f64>, ()> for BudgetConstrainedNystroem {
637    type Fitted = FittedBudgetConstrainedNystroem;
638
639    fn fit(self, x: &Array2<f64>, _y: &()) -> Result<Self::Fitted> {
640        // Find optimal configuration within budget
641        let optimization_result = self.find_optimal_config(x)?;
642
643        // Fit Nyström method with optimal configuration
644        let nystroem = Nystroem::new(self.kernel, optimization_result.optimal_components);
645        let fitted_nystroem = nystroem.fit(x, &())?;
646
647        Ok(FittedBudgetConstrainedNystroem {
648            fitted_nystroem,
649            optimization_result,
650        })
651    }
652}
653
654impl Transform<Array2<f64>, Array2<f64>> for FittedBudgetConstrainedNystroem {
655    fn transform(&self, x: &Array2<f64>) -> Result<Array2<f64>> {
656        self.fitted_nystroem.transform(x)
657    }
658}
659
660impl FittedBudgetConstrainedNystroem {
661    /// Get the optimization result
662    pub fn optimization_result(&self) -> &BudgetOptimizationResult {
663        &self.optimization_result
664    }
665
666    /// Get the optimal number of components
667    pub fn optimal_components(&self) -> usize {
668        self.optimization_result.optimal_components
669    }
670
671    /// Get the quality score
672    pub fn quality_score(&self) -> f64 {
673        self.optimization_result.quality_score
674    }
675
676    /// Get the budget usage
677    pub fn budget_usage(&self) -> &BudgetUsage {
678        &self.optimization_result.budget_usage
679    }
680
681    /// Check if optimization completed within budget
682    pub fn completed(&self) -> bool {
683        self.optimization_result.completed
684    }
685}
686
687#[allow(non_snake_case)]
688#[cfg(test)]
689mod tests {
690    use super::*;
691    use approx::assert_abs_diff_eq;
692
693    #[test]
694    fn test_budget_constrained_rbf_sampler() {
695        let x = Array2::from_shape_vec((100, 4), (0..400).map(|i| (i as f64) * 0.01).collect())
696            .unwrap();
697
698        let config = BudgetConstrainedConfig {
699            budget: BudgetConstraint::Time { max_seconds: 5.0 },
700            min_components: 10,
701            max_components: 50,
702            step_size: 10,
703            n_trials: 2,
704            ..Default::default()
705        };
706
707        let sampler = BudgetConstrainedRBFSampler::new().gamma(0.5).config(config);
708
709        let fitted = sampler.fit(&x, &()).unwrap();
710        let transformed = fitted.transform(&x).unwrap();
711
712        assert_eq!(transformed.nrows(), 100);
713        assert!(fitted.optimal_components() >= 10);
714        assert!(fitted.optimal_components() <= 50);
715        assert!(fitted.quality_score() >= 0.0);
716        assert!(fitted.budget_usage().time_used <= 5.0);
717    }
718
719    #[test]
720    fn test_budget_constrained_nystroem() {
721        let x =
722            Array2::from_shape_vec((80, 3), (0..240).map(|i| (i as f64) * 0.02).collect()).unwrap();
723
724        let config = BudgetConstrainedConfig {
725            budget: BudgetConstraint::Memory { max_bytes: 100000 },
726            min_components: 5,
727            max_components: 30,
728            step_size: 5,
729            n_trials: 2,
730            ..Default::default()
731        };
732
733        let nystroem = BudgetConstrainedNystroem::new().gamma(1.0).config(config);
734
735        let fitted = nystroem.fit(&x, &()).unwrap();
736        let transformed = fitted.transform(&x).unwrap();
737
738        assert_eq!(transformed.nrows(), 80);
739        assert!(fitted.optimal_components() >= 5);
740        assert!(fitted.optimal_components() <= 30);
741        assert!(fitted.budget_usage().memory_used <= 100000);
742    }
743
744    #[test]
745    fn test_budget_constraint_types() {
746        let x =
747            Array2::from_shape_vec((50, 2), (0..100).map(|i| (i as f64) * 0.05).collect()).unwrap();
748
749        let constraints = vec![
750            BudgetConstraint::Time { max_seconds: 10.0 },
751            BudgetConstraint::Memory { max_bytes: 100000 },
752            BudgetConstraint::Operations {
753                max_operations: 50000,
754            },
755            BudgetConstraint::Combined {
756                max_seconds: Some(10.0),
757                max_bytes: Some(100000),
758                max_operations: Some(50000),
759            },
760        ];
761
762        for constraint in constraints {
763            let config = BudgetConstrainedConfig {
764                budget: constraint,
765                min_components: 5,
766                max_components: 20,
767                step_size: 5,
768                n_trials: 1,
769                ..Default::default()
770            };
771
772            let sampler = BudgetConstrainedRBFSampler::new()
773                .gamma(0.8)
774                .config(config.clone());
775
776            let fitted = sampler.fit(&x, &()).unwrap();
777            let usage = fitted.budget_usage();
778
779            // Verify budget constraints are respected
780            assert!(
781                usage.is_within_budget(&config.budget),
782                "Budget constraint violated"
783            );
784        }
785    }
786
787    #[test]
788    fn test_optimization_strategies() {
789        let x =
790            Array2::from_shape_vec((60, 3), (0..180).map(|i| (i as f64) * 0.03).collect()).unwrap();
791
792        let strategies = vec![
793            OptimizationStrategy::MaxQuality,
794            OptimizationStrategy::MinCost {
795                target_quality: 0.7,
796            },
797            OptimizationStrategy::Balanced {
798                quality_weight: 1.0,
799                cost_weight: 0.01,
800            },
801            OptimizationStrategy::Greedy,
802        ];
803
804        for strategy in strategies {
805            let config = BudgetConstrainedConfig {
806                budget: BudgetConstraint::Time { max_seconds: 4.0 },
807                strategy,
808                min_components: 10,
809                max_components: 30,
810                step_size: 10,
811                n_trials: 1,
812                ..Default::default()
813            };
814
815            let sampler = BudgetConstrainedRBFSampler::new().gamma(0.5).config(config);
816
817            let fitted = sampler.fit(&x, &()).unwrap();
818
819            assert!(fitted.optimal_components() >= 10);
820            assert!(fitted.optimal_components() <= 30);
821            assert!(fitted.quality_score() >= 0.0);
822        }
823    }
824
825    #[test]
826    fn test_budget_usage_tracking() {
827        let mut usage = BudgetUsage::new();
828        usage.time_used = 2.5;
829        usage.memory_used = 1000;
830        usage.operations_used = 500;
831
832        let constraint1 = BudgetConstraint::Time { max_seconds: 3.0 };
833        let constraint2 = BudgetConstraint::Memory { max_bytes: 800 };
834        let constraint3 = BudgetConstraint::Operations {
835            max_operations: 600,
836        };
837        let constraint4 = BudgetConstraint::Combined {
838            max_seconds: Some(3.0),
839            max_bytes: Some(1200),
840            max_operations: Some(600),
841        };
842
843        assert!(usage.is_within_budget(&constraint1));
844        assert!(!usage.is_within_budget(&constraint2));
845        assert!(usage.is_within_budget(&constraint3));
846        assert!(usage.is_within_budget(&constraint4));
847    }
848
849    #[test]
850    fn test_early_stopping() {
851        let x =
852            Array2::from_shape_vec((40, 2), (0..80).map(|i| (i as f64) * 0.05).collect()).unwrap();
853
854        let config = BudgetConstrainedConfig {
855            budget: BudgetConstraint::Time { max_seconds: 10.0 },
856            min_components: 5,
857            max_components: 50,
858            step_size: 5,
859            n_trials: 1,
860            early_stopping_tolerance: 0.001,
861            ..Default::default()
862        };
863
864        let sampler = BudgetConstrainedRBFSampler::new().gamma(0.3).config(config);
865
866        let result = sampler.find_optimal_config(&x).unwrap();
867
868        // Should find a reasonable solution
869        assert!(result.optimal_components >= 5);
870        assert!(result.optimal_components <= 50);
871        assert!(result.quality_score >= 0.0);
872    }
873
874    #[test]
875    fn test_reproducibility() {
876        let x =
877            Array2::from_shape_vec((50, 3), (0..150).map(|i| (i as f64) * 0.02).collect()).unwrap();
878
879        let config = BudgetConstrainedConfig {
880            budget: BudgetConstraint::Time { max_seconds: 3.0 },
881            min_components: 10,
882            max_components: 30,
883            step_size: 10,
884            n_trials: 2,
885            random_seed: Some(42),
886            ..Default::default()
887        };
888
889        let sampler1 = BudgetConstrainedRBFSampler::new()
890            .gamma(0.7)
891            .config(config.clone());
892
893        let sampler2 = BudgetConstrainedRBFSampler::new().gamma(0.7).config(config);
894
895        let fitted1 = sampler1.fit(&x, &()).unwrap();
896        let fitted2 = sampler2.fit(&x, &()).unwrap();
897
898        assert_eq!(fitted1.optimal_components(), fitted2.optimal_components());
899        assert_abs_diff_eq!(
900            fitted1.quality_score(),
901            fitted2.quality_score(),
902            epsilon = 1e-10
903        );
904    }
905}
sklears_kernel_approximation/budget_constrained.rs

sklears_kernel_approximation/
budget_constrained.rs
