xsf/scipy_special/convex_analysis.rs
1//! Translated into pure Rust from `xsf/convex_analysis.h` (scipy/xsf@95e131e). Original author:
2//! argriffing.
3
4/// Elementwise function for computing the entropy
5///
6/// $$
7/// \mathrm{entr}(x_i) = \begin{cases}
8/// -x_i \ln(x_i) \& x_i > 0 \\\\
9/// 0 \& x_i = 0 \\\\
10/// -\infty \& \text{otherwise}
11/// \end{cases}
12/// $$
13///
14/// Translated from [`scipy.special.entr`][entr] into pure Rust.
15///
16/// [entr]: https://docs.scipy.org/doc/scipy/reference/generated/scipy.special.entr.html
17///
18/// # Notes
19///
20/// This function is concave.
21///
22/// The origin of this function is in convex programming [^1]. Given a discrete probability
23/// distribution $p_1,\dotsc,p_n$, the definition of entropy in the context of
24/// *information theory* is
25///
26/// $$
27/// H\[ \\{ p_i \\} \] = \sum\_{i} \mathrm{entr}(p_i).
28/// $$
29///
30/// [^1]: S. Boyd and L. Vandenberghe. *Convex optimization*. Cambridge University Press, 2004.
31/// <https://doi.org/10.1017/CBO9780511804441>
32///
33/// # See also
34/// - [`rel_entr`]
35/// - [`kl_div`]
36#[must_use]
37#[inline]
38pub fn entr(x_i: f64) -> f64 {
39 if x_i.is_nan() {
40 x_i
41 } else if x_i > 0.0 {
42 -x_i * x_i.ln()
43 } else if x_i == 0.0 {
44 0.0
45 } else {
46 f64::NEG_INFINITY
47 }
48}
49
50/// Elementwise function for computing relative entropy
51///
52/// Translated from [`scipy.special.rel_entr`][rel_entr] into pure Rust.
53///
54/// $$
55/// \mathrm{rel\\_entr}(x_i,\\, y_i) = \begin{cases}
56/// x_i \ln(x_i / y_i) \& x_i > 0 \wedge y_i > 0 \\\\
57/// 0 \& x_i = 0 \wedge y_i \ge 0 \\\\
58/// \infty \& \text{otherwise}
59/// \end{cases}
60/// $$
61///
62/// [rel_entr]: https://docs.scipy.org/doc/scipy/reference/generated/scipy.special.rel_entr.html
63///
64/// # Notes
65///
66/// This function is jointly convex in $x$ and $y$.
67///
68/// The origin of this function is in convex programming [^1]. Given two discrete probability
69/// distributions $p_1,\dotsc,p_n$ and $q_1,\dotsc,q_n$, the definition of relative entropy in the
70/// context of *information theory* is [^2]
71///
72/// $$
73/// H\left[ \\{ p_i \\} \\, \rvert \\, \\{ q_i \\} \right]
74/// = \sum_i \mathrm{rel\\_entr}(p_i,\\, q_i).
75/// $$
76///
77/// [^1]: S. Boyd and L. Vandenberghe. *Convex optimization*. Cambridge University Press, 2004.
78/// <https://doi.org/10.1017/CBO9780511804441>
79/// [^2]: Kullback-Leibler divergence, <https://wikipedia.org/wiki/KL-divergence>
80///
81/// # See also
82/// - [`entr`]
83/// - [`kl_div`]
84#[must_use]
85#[inline]
86pub fn rel_entr(x_i: f64, y_i: f64) -> f64 {
87 if x_i.is_nan() || y_i.is_nan() {
88 f64::NAN
89 } else if x_i <= 0.0 || y_i <= 0.0 {
90 if x_i == 0.0 && 0.0 <= y_i {
91 0.0
92 } else {
93 f64::INFINITY
94 }
95 } else {
96 let ratio = x_i / y_i;
97 if 0.5 < ratio && ratio < 2.0 {
98 // When x_i and y_i are close, this is more accurate
99 x_i * ((x_i - y_i) / y_i).ln_1p()
100 } else if f64::MIN_POSITIVE < ratio && ratio < f64::INFINITY {
101 // There are no underflow or overflow issues
102 x_i * ratio.ln()
103 } else {
104 // x_i and y_i are so far apart that taking x_i / y_i results in either an underflow,
105 // overflow, or subnormal number -- do the logarithm first
106 x_i * (x_i.ln() - y_i.ln())
107 }
108 }
109}
110
111/// Elementwise function for computing the Kullback-Leibler divergence
112///
113/// $$
114/// \mathrm{kl\\_div}(x_i,\\, y_i) = \begin{cases}
115/// x_i \ln(x_i / y_i) - x_i + y_i \& x_i > 0 \wedge y_i > 0 \\\\
116/// y_i \& x_i = 0 \wedge y_i \ge 0 \\\\
117/// \infty \& \text{otherwise}
118/// \end{cases}
119/// $$
120///
121/// Translated from [`scipy.special.kl_div`][kl_div] into pure Rust.
122///
123/// [kl_div]: https://docs.scipy.org/doc/scipy/reference/generated/scipy.special.kl_div.html
124///
125/// # Notes
126///
127/// This function is non-negative and is jointly convex in $x$ and $y$.
128///
129/// The origin of this function is in convex programming [^1]. This is why the function contains
130/// the extra $-x_i + y_i$ terms over what might be expected from the Kullback-Leibler divergence.
131/// For a version of the function without the extra terms, see [`rel_entr`].
132///
133/// [^1]: S. Boyd and L. Vandenberghe. *Convex optimization*. Cambridge University Press, 2004.
134/// <https://doi.org/10.1017/CBO9780511804441>
135///
136/// # See also
137/// - [`entr`]
138/// - [`rel_entr`]
139#[must_use]
140#[inline]
141pub fn kl_div(x: f64, y: f64) -> f64 {
142 if x.is_nan() || y.is_nan() {
143 f64::NAN
144 } else if 0.0 < x && 0.0 < y {
145 // Unlike in xsf (scipy/xsf#362), `rel_entr` is reused, and y ((1 + e) ln(1 + e) - e) is
146 // used near x = y.
147 let e = (x - y) / y;
148 if (-0.5..1.0).contains(&e) {
149 y * (crate::log1pmx(e) + e * e.ln_1p())
150 } else {
151 rel_entr(x, y) - x + y
152 }
153 } else if x == 0.0 && 0.0 <= y {
154 y
155 } else {
156 f64::INFINITY
157 }
158}
159
160/// Huber Loss function
161///
162/// $$
163/// L_\delta(r) = \begin{cases}
164/// \infty & \delta < 0 \\\\
165/// \frac{1}{2} r^2 & \|r\| \le \delta \\\\
166/// \delta \left(\|r\| - \frac{1}{2} \delta \right) & \text{otherwise}
167/// \end{cases}
168/// $$
169///
170/// Translated from [`scipy.special.huber`][huber] into pure Rust.
171///
172/// [huber]: https://docs.scipy.org/doc/scipy/reference/generated/scipy.special.huber.html
173///
174/// # Notes
175///
176/// `huber` is useful as a loss function in robust statistics or machine learning to reduce the
177/// influence of outliers as compared to the common squared error loss, residuals with a magnitude
178/// higher than $\delta$ are not squared [^1].
179///
180/// Typically, $r$ represents residuals, the difference between a model prediction and data.
181/// Then, for $\|r\| \leq \delta$, `huber` resembles the squared error and for $\|r\| > \delta$ the
182/// absolute error. This way, the Huber loss often achieves a fast convergence in model fitting for
183/// small residuals like the squared error loss function and still reduces the influence of
184/// outliers ($\|r\| > \delta$) like the absolute error loss. As $\delta$ is the cutoff between
185/// squared and absolute error regimes, it has to be tuned carefully for each problem. `huber` is
186/// also convex, making it suitable for gradient based optimization.
187///
188/// [^1]: Peter Huber, "Robust Estimation of a Location Parameter".
189/// 1964. Annals of Statistics. 53 (1): 73 - 101
190///
191/// # See also
192/// - [`pseudo_huber`]
193#[must_use]
194#[inline]
195pub fn huber(delta: f64, r: f64) -> f64 {
196 if delta < 0.0 {
197 f64::INFINITY
198 } else {
199 let r_abs = r.abs();
200 if r_abs <= delta {
201 0.5 * r * r
202 } else {
203 delta * (r_abs - 0.5 * delta)
204 }
205 }
206}
207
208/// Pseudo-Huber Loss function
209///
210/// $$
211/// \widetilde{L}_\delta(r) =
212/// \delta^2 \left( \sqrt{ 1 + \left( \frac{r}{\delta} \right)^2 } - 1 \right)
213/// $$
214///
215/// Translated from [`scipy.special.pseudo_huber`][phuber] into pure Rust.
216///
217/// [phuber]: https://docs.scipy.org/doc/scipy/reference/generated/scipy.special.pseudo_huber.html
218///
219/// # Notes
220///
221/// Like [`huber`], `pseudo_huber` often serves as a robust loss function in statistics or machine
222/// learning to reduce the influence of outliers. Unlike [`huber`], `pseudo_huber` is smooth.
223///
224/// Typically, $r$ represents residuals, the difference between a model prediction and data.
225/// Then, for $\|r\| \leq \delta$, `pseudo_huber` resembles the squared error and for
226/// $\|r\| > \delta$ the absolute error. This way, the Pseudo-Huber loss often achieves a fast
227/// convergence in model fitting for small residuals like the squared error loss function and still
228/// reduces the influence of outliers ($\|r\| > \delta$) like the absolute error loss. As $\delta$
229/// is the cutoff between squared and absolute error regimes, it has to be tuned carefully for each
230/// problem. `pseudo_huber` is also convex, making it suitable for gradient based optimization
231/// [^1] [^2].
232///
233/// [^1]: Hartley, Zisserman, "Multiple View Geometry in Computer Vision".
234/// 2003. Cambridge University Press. p. 619
235/// [^2]: Charbonnier et al. "Deterministic edge-preserving regularization in computed imaging".
236/// 1997. IEEE Trans. Image Processing. 6 (2): 298 - 311
237///
238/// # See also
239/// - [`huber`]
240#[must_use]
241#[inline]
242pub fn pseudo_huber(delta: f64, r: f64) -> f64 {
243 if delta < 0.0 {
244 f64::INFINITY
245 } else if delta == 0.0 || r == 0.0 {
246 0.0
247 } else {
248 // delta^2 (sqrt(1 + v^2) - 1) = r^2 / (sqrt(1 + v^2) + 1) with v = r / delta,
249 // scaled by the larger of |r| and delta to avoid over- and underflow
250 let r = r.abs();
251 if r <= delta {
252 let v = r / delta;
253 r * (r / ((1.0 + v * v).sqrt() + 1.0))
254 } else {
255 let w = delta / r;
256 r * (delta / ((1.0 + w * w).sqrt() + w))
257 }
258 }
259}