hyperopt/
kde.rs

1//! Kernel density estimator implementation.
2
3use std::fmt::Debug;
4
5use fastrand::Rng;
6use num_traits::{FromPrimitive, Zero};
7
8use crate::{
9    traits::loopback::{SelfAdd, SelfDiv},
10    Density,
11    Sample,
12};
13
14/// [Kernel density estimator][1].
15///
16/// It is used to model «good» and «bad» parameter distributions, but can also be used standalone.
17///
18/// # Type parameters
19///
20/// - [`C`]: iterator of KDE's components that are [`Density`] and [`Sample`].
21///
22/// [1]: https://en.wikipedia.org/wiki/Kernel_density_estimation
23#[derive(Copy, Clone, Debug)]
24pub struct KernelDensityEstimator<C>(pub C);
25
26impl<Ks> Density for KernelDensityEstimator<Ks>
27where
28    Ks: Iterator + Clone,
29    Ks::Item: Density,
30    <<Ks as Iterator>::Item as Density>::Param: Copy,
31    <<Ks as Iterator>::Item as Density>::Output: SelfAdd + SelfDiv + FromPrimitive + Zero,
32{
33    type Param = <<Ks as Iterator>::Item as Density>::Param;
34    type Output = <<Ks as Iterator>::Item as Density>::Output;
35
36    /// Calculate the KDE's density at the specified point.
37    ///
38    /// The method returns [`P::zero()`], if there are no components.
39    #[allow(clippy::cast_precision_loss)]
40    fn density(&self, at: Self::Param) -> Self::Output {
41        let (n_points, sum) = self
42            .0
43            .clone()
44            .fold((0_usize, Self::Output::zero()), |(n, sum), component| {
45                (n + 1, sum + component.density(at))
46            });
47        if n_points == 0 {
48            Self::Output::zero()
49        } else {
50            sum / Self::Output::from_usize(n_points).unwrap()
51        }
52    }
53}
54
55impl<Ks> Sample for KernelDensityEstimator<Ks>
56where
57    Ks: Iterator + Clone,
58    Ks::Item: Sample,
59{
60    type Param = Option<<<Ks as Iterator>::Item as Sample>::Param>;
61
62    /// Sample a random point from the KDE.
63    ///
64    /// The algorithm uses «[reservoir sampling][1]» to pick a random component,
65    /// and then samples a point from that component.
66    ///
67    /// The method returns [`None`], if the estimator has no components.
68    ///
69    /// [1]: https://en.wikipedia.org/wiki/Reservoir_sampling
70    fn sample(&self, rng: &mut Rng) -> Self::Param {
71        let sample = self
72            .0
73            .clone()
74            .enumerate()
75            .filter(|(i, _)| rng.usize(0..=*i) == 0)
76            .last()?
77            .1
78            .sample(rng);
79        Some(sample)
80    }
81}
82
83#[cfg(test)]
84mod tests {
85    use std::iter;
86
87    use super::*;
88    use crate::kernel::universal::Uniform;
89
90    #[test]
91    fn sample_single_component_ok() {
92        let kernel: Uniform<_, ()> = Uniform::with_bounds(-1.0..=1.0);
93        let kde = KernelDensityEstimator(iter::once(kernel));
94        let mut rng = Rng::new();
95
96        let sample = kde.sample(&mut rng).unwrap();
97        assert!((-1.0..=1.0).contains(&sample));
98
99        // Ensure that the iterator can be reused.
100        let _ = kde.sample(&mut rng).unwrap();
101    }
102}
hyperopt/kde.rs

hyperopt/
kde.rs
