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

sklears_kernel_approximation/
budget_constrained.rs
