An introduction to Dempster-Shafer Theory can be found within the thorough reports of Sentz and Ferson1 or El-Mahassni and White2. This implementation is in futhark pseudocode.


There’s three functions to compute: \(bel\), \(pl\), and \(comb\). Skipping \(comb\) for later, given the universe \(X\)…

\[bel(A) = \sum_{B \vert B \subseteq A} m(B). \ \ \ \ \ \ pl(A) = \sum_{B \vert B \cap A \neq \emptyset} m(B).\]

A potential implementation might involve t as a tuple composing some \(\vert X \vert\)-bit bitset and an accompanying real to represent mass.

type u          -- some bitset implementation.
type m = f64
type t = (u, m) 

val bel [f] : [f]t -> u -> m
val pl  [f] : [f]t -> u -> m

def bel e a = 
  map (\(b_s, b_m) -> 
    if (X.is_subset b_s a) 
      then b_m else 0.0f64
  ) e |> f64.sum

def pl e a = -- An alternative expression of `pl` that only needs `bel`.
  complement a |> bel e |> (f64.-) 1.0f64

A problem arises with \(comb\) rules; consider Dempster’s rule of combination:

\[(m_{1} \oplus m_{2})(A) = \frac{1}{1-K} \sum_{B \cap C = A \neq \emptyset} m_{1}(B)m_{2}(C)\]

Forming the basic belief assignment requires computing all possible intersections of \(m_{1}\) and \(m_{2}\), or a function with the signature [b]t -> [c]t -> [b*c]t. There’s two problems here:

  1. [b]t -> [c]t -> [b*c]t implies exponential growth. Looking closer, this isn’t truly accurate; intersections that produce the empty set can be removed and assignments with the same bitset can be merged. However, these aforementioned cleanups can’t be reasoned about at compile-time and we run into problems with irregular arrays.
  2. reduce takes an op parameter with the signature a -> a -> a. To court this attractive O(log(n)) span, [b]t -> [c]t -> [b*c]t must become [b]t -> [b]t -> [b*b]t -> [b]t.


Approximation schemes are a potential solution: we can take the resulting array of [b*c]t (or the cleaned up []t) and compute an approximation to a set of focal elements [a]t.

Bauer’s paper3 details a few; within it, there’s this bit I found:

A second criterion to assess the quality of an approximation is its ability to induce some “structure” on the given information, …

This “structure” provided by an approximation, in our case, easily enables parallelization of \(comb\) rules.

Both of the two schemes below are rather simple. kx (effectively klx) takes the largest k masses and then normalizes; summarize takes the largest k masses and then concats the union/sum of what’s left over.

val kx [f] : (k: i64) -> [f]t -> [k]t
def kx k e = 
  let sorted = merge_sort_by_key (.1) (f64.<=) e |> reverse
  -- if k is larger than w, we need to pad with `nil`.
  in (if k > f
    then (++) sorted (replicate (k - f) (nil, 0.0f64)) :> [k]t
    else take k sorted
  ) |> normalize

val summarize [f] : (k: i64) -> [f]t -> [k+1]t
def summarize k e =
  let sm (a: []t): t = 
    let a_union = map (.0) a |> reduce (union) (nil)
    let a_sum   = map (.1) a |> f64.sum
    in (a_union, a_sum)

  let sorted = merge_sort_by_key (.1) (f64.<=) e |> reverse
  -- if k is larger than w, we need to pad with nil.
  in if k > f
    then (++) sorted (replicate ((k + 1) - f) (nil, 0.0f64)) :> [k+1]t
    else (++) (take k sorted) [(sm (drop k sorted))]

With these, we can write \(comb\) such that it utilizes reduce.

-- | Combine a set of masses together with a combination rule and an
-- | approximation scheme.
val comb [f][a][b] : 
  ([a]t -> [a]t -> [b]t) -> ([b]t -> [a]t) -> [f][a]t -> [a]t

-- https://futhark-lang.org/examples/no-neutral-element.html
type with_neutral [a] 't = #neutral | #val [a]t

def comb [f][a] rl apx e =
  let e_tagged: [f]with_neutral [a]t = map (\z -> #val z) e
  let m = 
    reduce (\m1 m2 -> match (m1, m2)
      case (#val b, #val c) -> #val (rl b c |> apx)
      case (#neutral, _) -> m2
      case (_, #neutral) -> m1
    ) #neutral e_tagged

  in match m 
    case #neutral -> replicate a (X.nil, 0.0f64)
    case #val x   -> x

A highly parallel combination routine becomes the pleasing, curried let comb_dempster_kx k = comb comb_dempster (kx k).


  1. Sentz, Ferson - Combination of Evidence in Dempster-Shafer Theory ↩

  2. El-Mahassni, White - A Discussion of Dempster-Shafer Theory and its Application to Identification Fusion ↩

  3. Bauer - Approximations for Decision Making in the Dempster-Shafer Theory of Evidence ↩