steeldb/

evidence.rs

//! **Dempster–Shafer evidence combination** (paper §4.1–4.2).
//!
//! The rest of the engine reads one corpus, so a token's belief interval can be computed by counting polarity
//! bitmaps directly ([`crate::index::InfonIndex::belief_interval`]). That is not the same operation as fusing
//! *two independent sources* — a sensor reading and a supplier schedule, or two documents that disagree — and
//! it cannot express the thing the paper cares about most:
//!
//! > they fail to distinguish between **ignorance** (lack of evidence) and **conflict** (contradictory
//! > evidence)
//!
//! Ignorance is a wide interval: `[0, 1]`, nobody said. Conflict is two sources each confident and pointing
//! opposite ways. Both are "uncertain" and they demand different responses — the first wants more data, the
//! second means one source is wrong and averaging them silently invents a consensus that no source holds.
//!
//! So combination carries a conflict mass `K`, and a threshold guard refuses to fuse when `K` is too high
//! rather than normalising the disagreement away. That refusal is the point: Dempster's rule divides by
//! `1 − K`, so as sources approach total disagreement the normaliser approaches zero and the result becomes
//! arbitrary while still looking like a confident number.
//!
//! Focal sets are bitmaps of situation ids, so `B ∩ C` is a hardware AND and `B ∩ C = ∅` is a population
//! count against zero, exactly as §4.2 specifies.

use crate::bitmap::Postings;

/// A Basic Belief Assignment: mass distributed over focal sets.
///
/// Invariants from §4.1: `m(∅) = 0`, and the masses sum to 1. Both are checked on construction rather than
/// assumed, because a mass function that does not sum to 1 produces belief values that look plausible and are
/// meaningless.
#[derive(Debug, Clone)]
pub struct Mass<B: Postings> {
    /// `(focal set, mass)`, no empty sets, masses summing to 1
    focals: Vec<(B, f64)>,
}

/// Why a combination was refused.
#[derive(Debug, Clone, PartialEq)]
pub enum EvidenceError {
    /// a focal set was empty, which §4.1 forbids
    EmptyFocalSet,
    /// masses did not sum to 1 (within tolerance)
    NotNormalised { total: f64 },
    /// negative or non-finite mass
    BadMass { value: f64 },
    /// the sources contradict each other beyond the caller's threshold — the guard of §4.2
    ConflictExceeded { conflict: f64, threshold: f64 },
    /// total conflict: every pair of focal sets is disjoint, so Dempster's rule divides by zero
    TotalConflict,
}

impl std::fmt::Display for EvidenceError {
    fn fmt(&self, f: &mut std::fmt::Formatter<'_>) -> std::fmt::Result {
        match self {
            EvidenceError::EmptyFocalSet => write!(f, "a focal set is empty; m(∅) must be 0"),
            EvidenceError::NotNormalised { total } => {
                write!(f, "masses sum to {total:.6}, not 1")
            }
            EvidenceError::BadMass { value } => write!(f, "mass {value} is negative or not finite"),
            EvidenceError::ConflictExceeded { conflict, threshold } => write!(
                f,
                "evidential conflict K={conflict:.4} exceeds the threshold {threshold:.4}; \
                 the sources disagree too much to combine"
            ),
            EvidenceError::TotalConflict => {
                write!(f, "total conflict (K=1): the sources share no possibility, so fusion is undefined")
            }
        }
    }
}

impl std::error::Error for EvidenceError {}

impl<B: Postings> Mass<B> {
    /// Build a mass function, checking the §4.1 invariants.
    pub fn new(focals: Vec<(B, f64)>) -> Result<Self, EvidenceError> {
        let mut total = 0.0;
        for (set, m) in &focals {
            if !m.is_finite() || *m < 0.0 {
                return Err(EvidenceError::BadMass { value: *m });
            }
            if set.is_empty() {
                return Err(EvidenceError::EmptyFocalSet);
            }
            total += *m;
        }
        if (total - 1.0).abs() > 1e-6 {
            return Err(EvidenceError::NotNormalised { total });
        }
        Ok(Mass { focals })
    }

    /// All mass on one set — a single source asserting one possibility with full confidence.
    pub fn certain(set: B) -> Result<Self, EvidenceError> {
        Mass::new(vec![(set, 1.0)])
    }

    /// All mass on the frame itself: the honest representation of knowing nothing. This is the state a
    /// point-estimate probability cannot express, and combining it with anything returns that thing unchanged.
    pub fn vacuous(frame: B) -> Result<Self, EvidenceError> {
        Mass::new(vec![(frame, 1.0)])
    }

    pub fn focals(&self) -> &[(B, f64)] {
        &self.focals
    }

    /// `Bel(A) = Σ_{B ⊆ A} m(B)` — mass that commits *entirely* to A. The lower bound.
    pub fn belief(&self, a: &B) -> f64 {
        self.focals
            .iter()
            // B ⊆ A iff B has nothing outside A
            .filter(|(set, _)| set.and_not(a).is_empty())
            .map(|(_, m)| *m)
            .sum()
    }

    /// `Pl(A) = Σ_{B ∩ A ≠ ∅} m(B)` — mass not ruling A out. The upper bound.
    pub fn plausibility(&self, a: &B) -> f64 {
        self.focals
            .iter()
            .filter(|(set, _)| !set.and(a).is_empty())
            .map(|(_, m)| *m)
            .sum()
    }

    /// The evidential bound `[Bel(A), Pl(A)]`.
    pub fn interval(&self, a: &B) -> (f64, f64) {
        (self.belief(a), self.plausibility(a))
    }

    /// How much of the interval is pure ignorance: `Pl − Bel`.
    pub fn ignorance(&self, a: &B) -> f64 {
        (self.plausibility(a) - self.belief(a)).max(0.0)
    }
}

/// Conflict mass `K = Σ_{B ∩ C = ∅} m₁(B)·m₂(C)` (§4.2).
///
/// The share of the two sources' joint mass that lands on impossible combinations. `K = 0` means they are
/// compatible; `K = 1` means every pairing is contradictory.
pub fn conflict<B: Postings>(m1: &Mass<B>, m2: &Mass<B>) -> f64 {
    let mut k = 0.0;
    for (b, mb) in m1.focals() {
        for (c, mc) in m2.focals() {
            // B ∩ C = ∅ — an AND followed by a zero population count
            if b.and(c).is_empty() {
                k += mb * mc;
            }
        }
    }
    k.clamp(0.0, 1.0)
}

/// Dempster's rule of combination with the conflict guard of §4.2.
///
/// `(m₁ ⊕ m₂)(A) = (1/(1−K)) · Σ_{B ∩ C = A} m₁(B)·m₂(C)`
///
/// Refuses rather than normalising when `K` exceeds `max_conflict`. That refusal is the whole reason the
/// metric is computed: the `1/(1−K)` factor grows without bound as sources diverge, so a near-total
/// disagreement yields a confident-looking number derived from almost nothing. Returning an error hands the
/// caller a fact it can act on instead.
///
/// Pass `max_conflict = 1.0` to combine regardless, which is textbook Dempster behaviour.
pub fn combine<B: Postings>(
    m1: &Mass<B>,
    m2: &Mass<B>,
    max_conflict: f64,
) -> Result<Mass<B>, EvidenceError> {
    let k = conflict(m1, m2);
    if k >= 1.0 - 1e-12 {
        return Err(EvidenceError::TotalConflict);
    }
    if k > max_conflict {
        return Err(EvidenceError::ConflictExceeded { conflict: k, threshold: max_conflict });
    }

    // accumulate mass onto each distinct intersection
    let scale = 1.0 / (1.0 - k);
    let mut out: Vec<(B, f64)> = Vec::new();
    for (b, mb) in m1.focals() {
        for (c, mc) in m2.focals() {
            let inter = b.and(c);
            if inter.is_empty() {
                continue; // counted in K
            }
            let add = mb * mc * scale;
            // merge into an existing focal set with the same members, so the result stays a proper BBA
            match out.iter_mut().find(|(s, _)| s.and_not(&inter).is_empty() && inter.and_not(s).is_empty()) {
                Some((_, m)) => *m += add,
                None => out.push((inter, add)),
            }
        }
    }
    Mass::new(out)
}

/// Combine a stream of sources left to right, stopping at the first pair that exceeds the threshold.
///
/// Sequential rather than all-at-once because that is how the guard stays useful: it reports *which* source
/// introduced the disagreement, rather than only that the set as a whole is inconsistent.
pub fn combine_all<B: Postings>(
    sources: &[Mass<B>],
    max_conflict: f64,
) -> Result<Mass<B>, (usize, EvidenceError)> {
    let mut iter = sources.iter();
    let Some(first) = iter.next() else {
        return Err((0, EvidenceError::NotNormalised { total: 0.0 }));
    };
    let mut acc = first.clone();
    for (i, next) in iter.enumerate() {
        acc = combine(&acc, next, max_conflict).map_err(|e| (i + 1, e))?;
    }
    Ok(acc)
}

#[cfg(test)]
mod tests {
    use super::*;
    use crate::bitmap::RoarPostings as P;

    fn set(ids: &[u32]) -> P {
        P::from_sorted(ids)
    }

    #[test]
    fn invariants_are_checked_not_assumed() {
        assert_eq!(Mass::new(vec![(set(&[1]), 0.5)]).unwrap_err(), EvidenceError::NotNormalised { total: 0.5 });
        assert_eq!(Mass::new(vec![(set(&[]), 1.0)]).unwrap_err(), EvidenceError::EmptyFocalSet);
        assert!(matches!(
            Mass::new(vec![(set(&[1]), -1.0), (set(&[2]), 2.0)]).unwrap_err(),
            EvidenceError::BadMass { .. }
        ));
    }

    #[test]
    fn belief_and_plausibility_bracket_the_truth() {
        // 0.6 says "definitely situation 1", 0.4 says "1 or 2, not sure which"
        let m = Mass::new(vec![(set(&[1]), 0.6), (set(&[1, 2]), 0.4)]).unwrap();
        let a = set(&[1]);
        // only the first focal set is a subset of {1}; both intersect it
        assert!((m.belief(&a) - 0.6).abs() < 1e-9);
        assert!((m.plausibility(&a) - 1.0).abs() < 1e-9);
        assert!((m.ignorance(&a) - 0.4).abs() < 1e-9);
    }

    #[test]
    fn ignorance_and_conflict_are_different_states() {
        let frame = set(&[1, 2]);
        // ignorance: everything on the frame — [0, 1] for either outcome
        let unknown = Mass::vacuous(frame.clone()).unwrap();
        assert_eq!(unknown.interval(&set(&[1])), (0.0, 1.0));

        // conflict: two sources each certain, of opposite things
        let yes = Mass::certain(set(&[1])).unwrap();
        let no = Mass::certain(set(&[2])).unwrap();
        assert!((conflict(&yes, &no) - 1.0).abs() < 1e-9, "disjoint certainties are total conflict");
        // and the vacuous source conflicts with nothing
        assert!(conflict(&unknown, &yes).abs() < 1e-9);
    }

    #[test]
    fn combining_with_ignorance_changes_nothing() {
        // the neutral element of Dempster's rule: fusing "I don't know" must not move the belief
        let frame = set(&[1, 2, 3]);
        let src = Mass::new(vec![(set(&[1]), 0.7), (frame.clone(), 0.3)]).unwrap();
        let fused = combine(&src, &Mass::vacuous(frame).unwrap(), 1.0).unwrap();
        let a = set(&[1]);
        assert!((fused.belief(&a) - src.belief(&a)).abs() < 1e-9);
        assert!((fused.plausibility(&a) - src.plausibility(&a)).abs() < 1e-9);
    }

    #[test]
    fn agreeing_sources_sharpen_the_interval() {
        let frame = set(&[1, 2, 3]);
        let s1 = Mass::new(vec![(set(&[1]), 0.6), (frame.clone(), 0.4)]).unwrap();
        let s2 = Mass::new(vec![(set(&[1]), 0.6), (frame.clone(), 0.4)]).unwrap();
        let a = set(&[1]);
        let fused = combine(&s1, &s2, 1.0).unwrap();
        // two independent sources leaning the same way should believe it MORE than either alone
        assert!(fused.belief(&a) > s1.belief(&a), "{} vs {}", fused.belief(&a), s1.belief(&a));
        assert!(fused.ignorance(&a) < s1.ignorance(&a), "ignorance must shrink");
    }

    #[test]
    fn total_conflict_is_refused_rather_than_divided_by_zero() {
        let yes = Mass::certain(set(&[1])).unwrap();
        let no = Mass::certain(set(&[2])).unwrap();
        // textbook Dempster would divide by 1 - K = 0 here
        assert_eq!(combine(&yes, &no, 1.0).unwrap_err(), EvidenceError::TotalConflict);
    }

    #[test]
    fn the_guard_refuses_before_the_normaliser_gets_extreme() {
        let frame = set(&[1, 2]);
        // mostly-opposed sources: high but not total conflict
        let s1 = Mass::new(vec![(set(&[1]), 0.9), (frame.clone(), 0.1)]).unwrap();
        let s2 = Mass::new(vec![(set(&[2]), 0.9), (frame.clone(), 0.1)]).unwrap();
        let k = conflict(&s1, &s2);
        assert!(k > 0.7, "expected high conflict, got {k}");

        // permissive: combines, but the result rests on a tiny share of the joint mass
        assert!(combine(&s1, &s2, 1.0).is_ok());
        // guarded: refused, and the error carries the number so a caller can report it
        match combine(&s1, &s2, 0.5).unwrap_err() {
            EvidenceError::ConflictExceeded { conflict, threshold } => {
                assert!((conflict - k).abs() < 1e-9);
                assert!((threshold - 0.5).abs() < 1e-9);
            }
            other => panic!("expected ConflictExceeded, got {other:?}"),
        }
    }

    #[test]
    fn combine_all_reports_which_source_broke_it() {
        let frame = set(&[1, 2]);
        let ok1 = Mass::new(vec![(set(&[1]), 0.8), (frame.clone(), 0.2)]).unwrap();
        let ok2 = Mass::new(vec![(set(&[1]), 0.7), (frame.clone(), 0.3)]).unwrap();
        let bad = Mass::new(vec![(set(&[2]), 0.95), (frame.clone(), 0.05)]).unwrap();

        assert!(combine_all(&[ok1.clone(), ok2.clone()], 0.5).is_ok());
        let (idx, err) = combine_all(&[ok1, ok2, bad], 0.5).unwrap_err();
        assert_eq!(idx, 2, "the third source is the one that disagrees");
        assert!(matches!(err, EvidenceError::ConflictExceeded { .. }));
    }

    #[test]
    fn the_result_is_still_a_valid_mass_function() {
        let frame = set(&[1, 2, 3, 4]);
        let s1 = Mass::new(vec![(set(&[1, 2]), 0.5), (set(&[2, 3]), 0.3), (frame.clone(), 0.2)]).unwrap();
        let s2 = Mass::new(vec![(set(&[2, 3]), 0.6), (frame, 0.4)]).unwrap();
        let fused = combine(&s1, &s2, 1.0).unwrap();
        let total: f64 = fused.focals().iter().map(|(_, m)| *m).sum();
        assert!((total - 1.0).abs() < 1e-9, "masses must renormalise to 1, got {total}");
        assert!(fused.focals().iter().all(|(s, _)| !s.is_empty()), "no empty focal sets");
    }
}