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, SVD};
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 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());
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    fn compute_nystroem_quality(&self, x_transformed: &Array2<f64>) -> Result<f64> {
600        // Compute effective rank as quality measure
601        let (_, s, _) = x_transformed
602            .svd(true)
603            .map_err(|_| SklearsError::InvalidInput("SVD computation failed".to_string()))?;
604
605        let s_sum = s.sum();
606        if s_sum == 0.0 {
607            return Ok(0.0);
608        }
609
610        let s_normalized = &s / s_sum;
611        let entropy = -s_normalized
612            .iter()
613            .filter(|&&x| x > 1e-12)
614            .map(|&x| x * x.ln())
615            .sum::<f64>();
616
617        Ok(entropy.exp())
618    }
619}
620
621/// Fitted budget-constrained Nyström method
622pub struct FittedBudgetConstrainedNystroem {
623    fitted_nystroem: crate::nystroem::Nystroem<sklears_core::traits::Trained>,
624    optimization_result: BudgetOptimizationResult,
625}
626
627impl Fit<Array2<f64>, ()> for BudgetConstrainedNystroem {
628    type Fitted = FittedBudgetConstrainedNystroem;
629
630    fn fit(self, x: &Array2<f64>, _y: &()) -> Result<Self::Fitted> {
631        // Find optimal configuration within budget
632        let optimization_result = self.find_optimal_config(x)?;
633
634        // Fit Nyström method with optimal configuration
635        let nystroem = Nystroem::new(self.kernel, optimization_result.optimal_components);
636        let fitted_nystroem = nystroem.fit(x, &())?;
637
638        Ok(FittedBudgetConstrainedNystroem {
639            fitted_nystroem,
640            optimization_result,
641        })
642    }
643}
644
645impl Transform<Array2<f64>, Array2<f64>> for FittedBudgetConstrainedNystroem {
646    fn transform(&self, x: &Array2<f64>) -> Result<Array2<f64>> {
647        self.fitted_nystroem.transform(x)
648    }
649}
650
651impl FittedBudgetConstrainedNystroem {
652    /// Get the optimization result
653    pub fn optimization_result(&self) -> &BudgetOptimizationResult {
654        &self.optimization_result
655    }
656
657    /// Get the optimal number of components
658    pub fn optimal_components(&self) -> usize {
659        self.optimization_result.optimal_components
660    }
661
662    /// Get the quality score
663    pub fn quality_score(&self) -> f64 {
664        self.optimization_result.quality_score
665    }
666
667    /// Get the budget usage
668    pub fn budget_usage(&self) -> &BudgetUsage {
669        &self.optimization_result.budget_usage
670    }
671
672    /// Check if optimization completed within budget
673    pub fn completed(&self) -> bool {
674        self.optimization_result.completed
675    }
676}
677
678#[allow(non_snake_case)]
679#[cfg(test)]
680mod tests {
681    use super::*;
682    use approx::assert_abs_diff_eq;
683
684    #[test]
685    fn test_budget_constrained_rbf_sampler() {
686        let x = Array2::from_shape_vec((100, 4), (0..400).map(|i| (i as f64) * 0.01).collect())
687            .unwrap();
688
689        let config = BudgetConstrainedConfig {
690            budget: BudgetConstraint::Time { max_seconds: 5.0 },
691            min_components: 10,
692            max_components: 50,
693            step_size: 10,
694            n_trials: 2,
695            ..Default::default()
696        };
697
698        let sampler = BudgetConstrainedRBFSampler::new().gamma(0.5).config(config);
699
700        let fitted = sampler.fit(&x, &()).unwrap();
701        let transformed = fitted.transform(&x).unwrap();
702
703        assert_eq!(transformed.nrows(), 100);
704        assert!(fitted.optimal_components() >= 10);
705        assert!(fitted.optimal_components() <= 50);
706        assert!(fitted.quality_score() >= 0.0);
707        assert!(fitted.budget_usage().time_used <= 5.0);
708    }
709
710    #[test]
711    fn test_budget_constrained_nystroem() {
712        let x =
713            Array2::from_shape_vec((80, 3), (0..240).map(|i| (i as f64) * 0.02).collect()).unwrap();
714
715        let config = BudgetConstrainedConfig {
716            budget: BudgetConstraint::Memory { max_bytes: 100000 },
717            min_components: 5,
718            max_components: 30,
719            step_size: 5,
720            n_trials: 2,
721            ..Default::default()
722        };
723
724        let nystroem = BudgetConstrainedNystroem::new().gamma(1.0).config(config);
725
726        let fitted = nystroem.fit(&x, &()).unwrap();
727        let transformed = fitted.transform(&x).unwrap();
728
729        assert_eq!(transformed.nrows(), 80);
730        assert!(fitted.optimal_components() >= 5);
731        assert!(fitted.optimal_components() <= 30);
732        assert!(fitted.budget_usage().memory_used <= 100000);
733    }
734
735    #[test]
736    fn test_budget_constraint_types() {
737        let x =
738            Array2::from_shape_vec((50, 2), (0..100).map(|i| (i as f64) * 0.05).collect()).unwrap();
739
740        let constraints = vec![
741            BudgetConstraint::Time { max_seconds: 10.0 },
742            BudgetConstraint::Memory { max_bytes: 100000 },
743            BudgetConstraint::Operations {
744                max_operations: 50000,
745            },
746            BudgetConstraint::Combined {
747                max_seconds: Some(10.0),
748                max_bytes: Some(100000),
749                max_operations: Some(50000),
750            },
751        ];
752
753        for constraint in constraints {
754            let config = BudgetConstrainedConfig {
755                budget: constraint,
756                min_components: 5,
757                max_components: 20,
758                step_size: 5,
759                n_trials: 1,
760                ..Default::default()
761            };
762
763            let sampler = BudgetConstrainedRBFSampler::new()
764                .gamma(0.8)
765                .config(config.clone());
766
767            let fitted = sampler.fit(&x, &()).unwrap();
768            let usage = fitted.budget_usage();
769
770            // Verify budget constraints are respected
771            assert!(
772                usage.is_within_budget(&config.budget),
773                "Budget constraint violated"
774            );
775        }
776    }
777
778    #[test]
779    fn test_optimization_strategies() {
780        let x =
781            Array2::from_shape_vec((60, 3), (0..180).map(|i| (i as f64) * 0.03).collect()).unwrap();
782
783        let strategies = vec![
784            OptimizationStrategy::MaxQuality,
785            OptimizationStrategy::MinCost {
786                target_quality: 0.7,
787            },
788            OptimizationStrategy::Balanced {
789                quality_weight: 1.0,
790                cost_weight: 0.01,
791            },
792            OptimizationStrategy::Greedy,
793        ];
794
795        for strategy in strategies {
796            let config = BudgetConstrainedConfig {
797                budget: BudgetConstraint::Time { max_seconds: 4.0 },
798                strategy,
799                min_components: 10,
800                max_components: 30,
801                step_size: 10,
802                n_trials: 1,
803                ..Default::default()
804            };
805
806            let sampler = BudgetConstrainedRBFSampler::new().gamma(0.5).config(config);
807
808            let fitted = sampler.fit(&x, &()).unwrap();
809
810            assert!(fitted.optimal_components() >= 10);
811            assert!(fitted.optimal_components() <= 30);
812            assert!(fitted.quality_score() >= 0.0);
813        }
814    }
815
816    #[test]
817    fn test_budget_usage_tracking() {
818        let mut usage = BudgetUsage::new();
819        usage.time_used = 2.5;
820        usage.memory_used = 1000;
821        usage.operations_used = 500;
822
823        let constraint1 = BudgetConstraint::Time { max_seconds: 3.0 };
824        let constraint2 = BudgetConstraint::Memory { max_bytes: 800 };
825        let constraint3 = BudgetConstraint::Operations {
826            max_operations: 600,
827        };
828        let constraint4 = BudgetConstraint::Combined {
829            max_seconds: Some(3.0),
830            max_bytes: Some(1200),
831            max_operations: Some(600),
832        };
833
834        assert!(usage.is_within_budget(&constraint1));
835        assert!(!usage.is_within_budget(&constraint2));
836        assert!(usage.is_within_budget(&constraint3));
837        assert!(usage.is_within_budget(&constraint4));
838    }
839
840    #[test]
841    fn test_early_stopping() {
842        let x =
843            Array2::from_shape_vec((40, 2), (0..80).map(|i| (i as f64) * 0.05).collect()).unwrap();
844
845        let config = BudgetConstrainedConfig {
846            budget: BudgetConstraint::Time { max_seconds: 10.0 },
847            min_components: 5,
848            max_components: 50,
849            step_size: 5,
850            n_trials: 1,
851            early_stopping_tolerance: 0.001,
852            ..Default::default()
853        };
854
855        let sampler = BudgetConstrainedRBFSampler::new().gamma(0.3).config(config);
856
857        let result = sampler.find_optimal_config(&x).unwrap();
858
859        // Should find a reasonable solution
860        assert!(result.optimal_components >= 5);
861        assert!(result.optimal_components <= 50);
862        assert!(result.quality_score >= 0.0);
863    }
864
865    #[test]
866    fn test_reproducibility() {
867        let x =
868            Array2::from_shape_vec((50, 3), (0..150).map(|i| (i as f64) * 0.02).collect()).unwrap();
869
870        let config = BudgetConstrainedConfig {
871            budget: BudgetConstraint::Time { max_seconds: 3.0 },
872            min_components: 10,
873            max_components: 30,
874            step_size: 10,
875            n_trials: 2,
876            random_seed: Some(42),
877            ..Default::default()
878        };
879
880        let sampler1 = BudgetConstrainedRBFSampler::new()
881            .gamma(0.7)
882            .config(config.clone());
883
884        let sampler2 = BudgetConstrainedRBFSampler::new().gamma(0.7).config(config);
885
886        let fitted1 = sampler1.fit(&x, &()).unwrap();
887        let fitted2 = sampler2.fit(&x, &()).unwrap();
888
889        assert_eq!(fitted1.optimal_components(), fitted2.optimal_components());
890        assert_abs_diff_eq!(
891            fitted1.quality_score(),
892            fitted2.quality_score(),
893            epsilon = 1e-10
894        );
895    }
896}
sklears_kernel_approximation/budget_constrained.rs

sklears_kernel_approximation/
budget_constrained.rs
