Basis of the theory of belief functions

This page is directly inspired from [Thierry Denoeux's talks] and [Philippe Smets' articles].

Introduction

Introduced by Dempster (1968) and Shafer (1976), belief functions constitute one of the main frameworks for reasoning with imperfect information.

Belief function is a mathematical tool used in different models with different semantics:

   - Lower-upper probabilities (Dempster's model, Hint model);
- Random sets;
- Degrees of belief (Transferable Belief Model - TBM).


It generalizes both Set Theory and Probability Theory: a belief function may be viewed both as a generalized set and as a non additive measure.

The theory includes extensions of probabilistic notions (conditioning, marginalization) and set-theoretic notions (intersection, union, inclusion, etc.)

Representing Information

Let $\Omega = \{\omega_1, \ldots, \omega_K\}$, called the frame of discernment, be a finite set comprising all possible answers to a given question $Q$ of interest.

The beliefs held by a rational agent Ag regarding the answer to question $Q$ can be quantified by a basic belief assignment (BBA) or a mass function $m^\Omega_{Ag}$, defined as a function from $2^\Omega$ to $[0,1]$ verifying:

$\sum_{A\subseteq\Omega} m^\Omega_{Ag} (A) = 1 ~.$

The quantity $m^\Omega_{Ag}(A)$ represents the part of the unit mass allocated to the hypothesis that the answer to question $Q$ is in the subset $A$ of $\Omega$. When there is no ambiguity on the agent or the frame of discernment, the notation $m^\Omega_{Ag}$ will be simplified to $m^\Omega$ or $m$.

Some definitions

  - A subset $A$ of $\Omega$ such that $m(A) > 0$ is called a  focal set of $m$.
- A BBA $m$ with only one focal set $A$ is called a categorical BBA and is denoted $m_A$; we then have $m_A(A) = 1$.
- Total ignorance is represented by the BBA $m_\Omega$ such that $m_\Omega(\Omega)=1$, called the vacuous mass function.
- A normal BBA $m$ satisfies the condition $m(\emptyset)=0$.
- A BBA whose focal sets are nested is said to be consonant.


Other representations

The belief and plausibility functions associated with a BBA $m$ are defined, respectively, as:

$bel(A)=\sum_{\emptyset \neq B \subseteq A} m(B),$

and

$pl(A)=\sum_{B \cap A\neq \emptyset} m(B),$

for all $A \subseteq \Omega$.

Functions $m$, $bel$ and $pl$ are in one-to-one correspondence, and thus constitute different forms of the same information.

Combining evidence

The basic operation for combining BBAs induced by distinct sources of information is the conjunctive rule of combination, also referred to as the unnormalized Dempster's rule of combination, defined as

$m_1 \cap m_2 (A) = \sum_{B \cap C = A} m_1(B) m_2(C), \quad \quad \forall A \subseteq \Omega .$

Other rules exist: disjunctive rule, cautious rule, ...

Making decisions

In Bayesian decision theory, modeling a decision process implies defining:

  - A set $D$ of decisions that can be made;
- A set $\Gamma$ of considered states of nature;
- A cost function $c: D \times \Gamma \rightarrow \mathbb{R}$, such that $c(d,\gamma)$ represents the cost of making decision $d\in D$
when $\gamma\in \Gamma$ is the true state of nature.


Rationality principles justify the choice of the decision $d^* \in D$ corresponding to the minimum expected cost or risk according to some probability measure $P^\Gamma$ on $\Gamma$:

$d^* = \arg \min_d \rho(d),$

with

$\rho(d) = \sum_{\gamma \in \Gamma} c(d,\gamma)P^\Gamma(\{\gamma\})~, \quad \forall d \in D.$

In the TBM, this decision-theoretic framework is accepted (see Smets 2005 for instance).

The set $\Gamma$, called the betting frame, is often taken equal to $\Omega$. However, it may be any refinement or coarsening of $\Omega$,or it may be obtained from $\Omega$ by a succession of refinings and coarsenings.

The probability measure $P^\Gamma$ is obtained by the pignistic transformation, which consists in firstly expressing the piece of evidence $m^\Omega$, initially defined on the frame of discernment, on the betting frame $\Gamma$, and then computing the pignistic probability $BetP^\Gamma = P^\Gamma$ as:

$BetP^\Gamma(\{\gamma\}) = \sum_{\{A \subseteq \Gamma, \gamma \in A\}} \frac{m^\Gamma(A)}{|A|(1 - m^\Gamma(\emptyset))},$

where $|A|$ denotes the cardinality of $A$.