hyperspace_sdk/
fuzzy.rs

1#![allow(clippy::manual_range_contains)]
2//! Fuzzy set-theoretic operators: t-norms, t-conorms, and negation.
3//!
4//! These operators extend crisp set operations (intersection, union, complement)
5//! to fuzzy membership values in \[0, 1\]. They are the foundation of fuzzy
6//! query answering over knowledge graphs.
7//!
8//! # T-norms (fuzzy intersection)
9//!
10//! A t-norm `T: [0,1]^2 -> [0,1]` must satisfy:
11//! - Commutativity: `T(a, b) = T(b, a)`
12//! - Associativity: `T(a, T(b, c)) = T(T(a, b), c)`
13//! - Monotonicity: if `a <= c` then `T(a, b) <= T(c, b)`
14//! - Identity: `T(a, 1) = a`
15//! - Annihilator: `T(a, 0) = 0`
16//!
17//! # T-conorms (fuzzy union)
18//!
19//! Each t-norm has a dual t-conorm via De Morgan's law:
20//! `S(a, b) = 1 - T(1-a, 1-b)`.
21//!
22//! # References
23//!
24//! - Chen et al. (AAAI 2022), "Fuzzy Logic Based Logical Query Answering on
25//!   Knowledge Graphs" (`FuzzQE`)
26//!
27//! # Examples
28//!
29//! ```rust
30//! use hyperspace_sdk::fuzzy::{TNorm, TConorm, fuzzy_negation};
31//!
32//! // Fuzzy intersection: how "aquatic" AND "mammal" is a dolphin?
33//! let aquatic = 0.9;
34//! let mammal = 0.95;
35//!
36//! let min = TNorm::Min.apply(aquatic, mammal);       // 0.9
37//! let prod = TNorm::Product.apply(aquatic, mammal);   // 0.855
38//! let luk = TNorm::Lukasiewicz.apply(aquatic, mammal); // 0.85
39//! assert!(min >= prod && prod >= luk); // Min >= Product >= Lukasiewicz
40//!
41//! // De Morgan duality: neg(T(a,b)) = S(neg(a), neg(b))
42//! let t = TNorm::Product;
43//! let s = t.dual(); // TConorm::Probabilistic
44//! let lhs = fuzzy_negation(t.apply(0.7, 0.4));
45//! let rhs = s.apply(fuzzy_negation(0.7), fuzzy_negation(0.4));
46//! assert!((lhs - rhs).abs() < 1e-6);
47//! ```
48
49/// Godel t-norm: `min(a, b)`.
50///
51/// The strongest t-norm: `min(a, b) >= T(a, b)` for any t-norm T.
52#[inline]
53#[must_use]
54pub fn tnorm_min(a: f32, b: f32) -> f32 {
55    a.min(b)
56}
57
58/// Product t-norm: `a * b`.
59///
60/// Corresponds to probabilistic independence: if two events are independent,
61/// the probability of both occurring is the product of their probabilities.
62#[inline]
63#[must_use]
64pub fn tnorm_product(a: f32, b: f32) -> f32 {
65    a * b
66}
67
68/// Lukasiewicz t-norm: `max(a + b - 1, 0)`.
69///
70/// The weakest common t-norm. Produces 0 unless both inputs are high.
71#[inline]
72#[must_use]
73pub fn tnorm_lukasiewicz(a: f32, b: f32) -> f32 {
74    (a + b - 1.0).max(0.0)
75}
76
77/// Godel t-conorm (dual of min): `max(a, b)`.
78#[inline]
79#[must_use]
80pub fn tconorm_max(a: f32, b: f32) -> f32 {
81    a.max(b)
82}
83
84/// Probabilistic t-conorm (dual of product): `a + b - a*b`.
85#[inline]
86#[must_use]
87pub fn tconorm_probabilistic(a: f32, b: f32) -> f32 {
88    a + b - a * b
89}
90
91/// Lukasiewicz t-conorm (dual of Lukasiewicz): `min(a + b, 1)`.
92#[inline]
93#[must_use]
94pub fn tconorm_lukasiewicz(a: f32, b: f32) -> f32 {
95    (a + b).min(1.0)
96}
97
98/// Standard fuzzy negation: `1 - a`.
99#[inline]
100#[must_use]
101pub fn fuzzy_negation(a: f32) -> f32 {
102    1.0 - a
103}
104
105/// A triangular norm (t-norm) for fuzzy intersection.
106#[derive(Debug, Clone, Copy, PartialEq, Eq, Hash)]
107pub enum TNorm {
108    /// Godel t-norm: `min(a, b)`.
109    Min,
110    /// Product t-norm: `a * b`.
111    Product,
112    /// Lukasiewicz t-norm: `max(a + b - 1, 0)`.
113    Lukasiewicz,
114}
115
116impl TNorm {
117    /// Apply this t-norm to two fuzzy values.
118    #[inline]
119    #[must_use]
120    pub fn apply(&self, a: f32, b: f32) -> f32 {
121        match self {
122            TNorm::Min => tnorm_min(a, b),
123            TNorm::Product => tnorm_product(a, b),
124            TNorm::Lukasiewicz => tnorm_lukasiewicz(a, b),
125        }
126    }
127
128    /// Get the dual t-conorm (via De Morgan).
129    #[inline]
130    #[must_use]
131    pub fn dual(&self) -> TConorm {
132        match self {
133            TNorm::Min => TConorm::Max,
134            TNorm::Product => TConorm::Probabilistic,
135            TNorm::Lukasiewicz => TConorm::Lukasiewicz,
136        }
137    }
138}
139
140/// A triangular conorm (t-conorm) for fuzzy union.
141#[derive(Debug, Clone, Copy, PartialEq, Eq, Hash)]
142pub enum TConorm {
143    /// Godel t-conorm: `max(a, b)`.
144    Max,
145    /// Probabilistic t-conorm: `a + b - a*b`.
146    Probabilistic,
147    /// Lukasiewicz t-conorm: `min(a + b, 1)`.
148    Lukasiewicz,
149}
150
151impl TConorm {
152    /// Apply this t-conorm to two fuzzy values.
153    #[inline]
154    #[must_use]
155    pub fn apply(&self, a: f32, b: f32) -> f32 {
156        match self {
157            TConorm::Max => tconorm_max(a, b),
158            TConorm::Probabilistic => tconorm_probabilistic(a, b),
159            TConorm::Lukasiewicz => tconorm_lukasiewicz(a, b),
160        }
161    }
162
163    /// Get the dual t-norm (via De Morgan).
164    #[inline]
165    #[must_use]
166    pub fn dual(&self) -> TNorm {
167        match self {
168            TConorm::Max => TNorm::Min,
169            TConorm::Probabilistic => TNorm::Product,
170            TConorm::Lukasiewicz => TNorm::Lukasiewicz,
171        }
172    }
173}
174
175/// Represents a fuzzy logic search query over vector space.
176#[derive(Debug, Clone)]
177pub enum FuzzyQuery {
178    /// A single target vector.
179    Vector(Vec<f64>),
180    /// Fuzzy intersection (AND) using a t-norm.
181    And(Box<FuzzyQuery>, Box<FuzzyQuery>, TNorm),
182    /// Fuzzy union (OR) using a t-conorm.
183    Or(Box<FuzzyQuery>, Box<FuzzyQuery>, TConorm),
184    /// Fuzzy negation (NOT).
185    Not(Box<FuzzyQuery>),
186}
187
188impl FuzzyQuery {
189    /// Flatten and extract all vectors in the query graph to a list.
190    pub fn extract_vectors(&self, out: &mut Vec<Vec<f64>>) {
191        match self {
192            FuzzyQuery::Vector(v) => out.push(v.clone()),
193            FuzzyQuery::And(lhs, rhs, _) | FuzzyQuery::Or(lhs, rhs, _) => {
194                lhs.extract_vectors(out);
195                rhs.extract_vectors(out);
196            }
197            FuzzyQuery::Not(expr) => expr.extract_vectors(out),
198        }
199    }
200
201    /// Evaluates the `FuzzyQuery` for a database item yielding a final membership score \[0, 1\].
202    /// `distance_fn` provides the distance from the database item to a specific query node via its traversal index.
203    pub fn evaluate_indexed<F>(&self, counter: &mut usize, distance_fn: &F) -> f32
204    where
205        F: Fn(usize) -> f32,
206    {
207        match self {
208            FuzzyQuery::Vector(_) => {
209                let idx = *counter;
210                *counter += 1;
211                let dist = distance_fn(idx);
212                // Convert distance to fuzzy membership [0, 1].
213                (-dist).exp()
214            }
215            FuzzyQuery::And(lhs, rhs, tnorm) => tnorm.apply(
216                lhs.evaluate_indexed(counter, distance_fn),
217                rhs.evaluate_indexed(counter, distance_fn),
218            ),
219            FuzzyQuery::Or(lhs, rhs, tconorm) => tconorm.apply(
220                lhs.evaluate_indexed(counter, distance_fn),
221                rhs.evaluate_indexed(counter, distance_fn),
222            ),
223            FuzzyQuery::Not(expr) => fuzzy_negation(expr.evaluate_indexed(counter, distance_fn)),
224        }
225    }
226}
227
228#[cfg(test)]
229mod tests {
230    #![allow(clippy::float_cmp)]
231    use super::*;
232    use proptest::prelude::*;
233
234    // ---- Unit tests ----
235
236    #[test]
237    fn tnorm_min_basic() {
238        assert_eq!(tnorm_min(0.3, 0.7), 0.3);
239        assert_eq!(tnorm_min(0.5, 0.5), 0.5);
240        assert_eq!(tnorm_min(1.0, 0.4), 0.4);
241        assert_eq!(tnorm_min(0.0, 0.9), 0.0);
242    }
243
244    #[test]
245    fn tnorm_product_basic() {
246        assert!((tnorm_product(0.5, 0.5) - 0.25).abs() < 1e-7);
247        assert_eq!(tnorm_product(1.0, 0.7), 0.7);
248        assert_eq!(tnorm_product(0.0, 0.5), 0.0);
249    }
250
251    #[test]
252    fn tnorm_lukasiewicz_basic() {
253        assert_eq!(tnorm_lukasiewicz(0.3, 0.5), 0.0); // 0.3+0.5-1 = -0.2 -> 0
254        assert!((tnorm_lukasiewicz(0.8, 0.9) - 0.7).abs() < 1e-7);
255        assert_eq!(tnorm_lukasiewicz(1.0, 1.0), 1.0);
256        assert_eq!(tnorm_lukasiewicz(0.0, 1.0), 0.0);
257    }
258
259    #[test]
260    fn tconorm_max_basic() {
261        assert_eq!(tconorm_max(0.3, 0.7), 0.7);
262        assert_eq!(tconorm_max(0.0, 0.0), 0.0);
263        assert_eq!(tconorm_max(1.0, 0.5), 1.0);
264    }
265
266    #[test]
267    fn tconorm_probabilistic_basic() {
268        // 0.3 + 0.7 - 0.21 = 0.79
269        assert!((tconorm_probabilistic(0.3, 0.7) - 0.79).abs() < 1e-6);
270        assert_eq!(tconorm_probabilistic(0.0, 0.5), 0.5);
271        assert_eq!(tconorm_probabilistic(1.0, 0.5), 1.0);
272    }
273
274    #[test]
275    fn tconorm_lukasiewicz_basic() {
276        assert!((tconorm_lukasiewicz(0.3, 0.5) - 0.8).abs() < 1e-7);
277        assert_eq!(tconorm_lukasiewicz(0.6, 0.7), 1.0); // 1.3 clamped
278        assert_eq!(tconorm_lukasiewicz(0.0, 0.0), 0.0);
279    }
280
281    #[test]
282    fn fuzzy_negation_basic() {
283        assert_eq!(fuzzy_negation(0.0), 1.0);
284        assert_eq!(fuzzy_negation(1.0), 0.0);
285        assert!((fuzzy_negation(0.3) - 0.7).abs() < 1e-7);
286    }
287
288    #[test]
289    fn enum_apply() {
290        assert_eq!(TNorm::Min.apply(0.3, 0.7), tnorm_min(0.3, 0.7));
291        assert_eq!(TNorm::Product.apply(0.3, 0.7), tnorm_product(0.3, 0.7));
292        assert_eq!(
293            TNorm::Lukasiewicz.apply(0.3, 0.7),
294            tnorm_lukasiewicz(0.3, 0.7)
295        );
296        assert_eq!(TConorm::Max.apply(0.3, 0.7), tconorm_max(0.3, 0.7));
297        assert_eq!(
298            TConorm::Probabilistic.apply(0.3, 0.7),
299            tconorm_probabilistic(0.3, 0.7)
300        );
301        assert_eq!(
302            TConorm::Lukasiewicz.apply(0.3, 0.7),
303            tconorm_lukasiewicz(0.3, 0.7)
304        );
305    }
306
307    #[test]
308    fn dual_roundtrip() {
309        assert_eq!(TNorm::Min.dual().dual(), TNorm::Min);
310        assert_eq!(TNorm::Product.dual().dual(), TNorm::Product);
311        assert_eq!(TNorm::Lukasiewicz.dual().dual(), TNorm::Lukasiewicz);
312    }
313
314    // ---- Property tests ----
315
316    fn arb_unit() -> impl Strategy<Value = f32> {
317        0.0f32..=1.0
318    }
319
320    proptest! {
321        // -- Commutativity --
322
323        #[test]
324        fn prop_tnorm_min_commutative(a in arb_unit(), b in arb_unit()) {
325            prop_assert_eq!(tnorm_min(a, b), tnorm_min(b, a));
326        }
327
328        #[test]
329        fn prop_tnorm_product_commutative(a in arb_unit(), b in arb_unit()) {
330            prop_assert!((tnorm_product(a, b) - tnorm_product(b, a)).abs() < 1e-6);
331        }
332
333        #[test]
334        fn prop_tnorm_lukasiewicz_commutative(a in arb_unit(), b in arb_unit()) {
335            prop_assert!((tnorm_lukasiewicz(a, b) - tnorm_lukasiewicz(b, a)).abs() < 1e-6);
336        }
337
338        // -- Associativity --
339
340        #[test]
341        fn prop_tnorm_min_associative(a in arb_unit(), b in arb_unit(), c in arb_unit()) {
342            let lhs = tnorm_min(a, tnorm_min(b, c));
343            let rhs = tnorm_min(tnorm_min(a, b), c);
344            prop_assert!((lhs - rhs).abs() < 1e-6);
345        }
346
347        #[test]
348        fn prop_tnorm_product_associative(a in arb_unit(), b in arb_unit(), c in arb_unit()) {
349            let lhs = tnorm_product(a, tnorm_product(b, c));
350            let rhs = tnorm_product(tnorm_product(a, b), c);
351            prop_assert!((lhs - rhs).abs() < 1e-5);
352        }
353
354        #[test]
355        fn prop_tnorm_lukasiewicz_associative(a in arb_unit(), b in arb_unit(), c in arb_unit()) {
356            let lhs = tnorm_lukasiewicz(a, tnorm_lukasiewicz(b, c));
357            let rhs = tnorm_lukasiewicz(tnorm_lukasiewicz(a, b), c);
358            prop_assert!((lhs - rhs).abs() < 1e-6);
359        }
360
361        // -- Boundary conditions --
362
363        #[test]
364        fn prop_tnorm_identity(a in arb_unit()) {
365            // T(a, 1) = a for all t-norms.
366            prop_assert!((TNorm::Min.apply(a, 1.0) - a).abs() < 1e-6);
367            prop_assert!((TNorm::Product.apply(a, 1.0) - a).abs() < 1e-6);
368            prop_assert!((TNorm::Lukasiewicz.apply(a, 1.0) - a).abs() < 1e-6);
369        }
370
371        #[test]
372        fn prop_tnorm_annihilator(a in arb_unit()) {
373            // T(a, 0) = 0 for all t-norms.
374            prop_assert!((TNorm::Min.apply(a, 0.0)).abs() < 1e-6);
375            prop_assert!((TNorm::Product.apply(a, 0.0)).abs() < 1e-6);
376            prop_assert!((TNorm::Lukasiewicz.apply(a, 0.0)).abs() < 1e-6);
377        }
378
379        // -- De Morgan: neg(T(a,b)) = S(neg(a), neg(b)) --
380
381        #[test]
382        fn prop_de_morgan_min(a in arb_unit(), b in arb_unit()) {
383            let lhs = fuzzy_negation(tnorm_min(a, b));
384            let rhs = tconorm_max(fuzzy_negation(a), fuzzy_negation(b));
385            prop_assert!((lhs - rhs).abs() < 1e-6,
386                "De Morgan min: {lhs} != {rhs}");
387        }
388
389        #[test]
390        fn prop_de_morgan_product(a in arb_unit(), b in arb_unit()) {
391            let lhs = fuzzy_negation(tnorm_product(a, b));
392            let rhs = tconorm_probabilistic(fuzzy_negation(a), fuzzy_negation(b));
393            prop_assert!((lhs - rhs).abs() < 1e-5,
394                "De Morgan product: {lhs} != {rhs}");
395        }
396
397        #[test]
398        fn prop_de_morgan_lukasiewicz(a in arb_unit(), b in arb_unit()) {
399            let lhs = fuzzy_negation(tnorm_lukasiewicz(a, b));
400            let rhs = tconorm_lukasiewicz(fuzzy_negation(a), fuzzy_negation(b));
401            prop_assert!((lhs - rhs).abs() < 1e-6,
402                "De Morgan Lukasiewicz: {lhs} != {rhs}");
403        }
404
405        // -- Output range --
406
407        #[test]
408        fn prop_tnorm_output_in_unit(a in arb_unit(), b in arb_unit()) {
409            for t in [TNorm::Min, TNorm::Product, TNorm::Lukasiewicz] {
410                let v = t.apply(a, b);
411                prop_assert!(v >= -1e-7 && v <= 1.0 + 1e-7,
412                    "t-norm {:?} output {v} out of [0,1]", t);
413            }
414        }
415
416        #[test]
417        fn prop_tconorm_output_in_unit(a in arb_unit(), b in arb_unit()) {
418            for s in [TConorm::Max, TConorm::Probabilistic, TConorm::Lukasiewicz] {
419                let v = s.apply(a, b);
420                prop_assert!(v >= -1e-7 && v <= 1.0 + 1e-7,
421                    "t-conorm {:?} output {v} out of [0,1]", s);
422            }
423        }
424
425        // -- Double negation --
426
427        #[test]
428        fn prop_double_negation(a in arb_unit()) {
429            let result = fuzzy_negation(fuzzy_negation(a));
430            prop_assert!((result - a).abs() < 1e-6, "double negation: {result} != {a}");
431        }
432    }
433}
hyperspace_sdk/fuzzy.rs

hyperspace_sdk/
fuzzy.rs
