Basis of the theory of belief functions
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.)
Let , called the frame of discernment, be a finite set comprising all possible answers to a given question of interest.
The beliefs held by a rational agent Ag regarding the answer to question can be quantified by a basic belief assignment (BBA) or a mass function , defined as a function from to verifying:
The quantity represents the part of the unit mass allocated to the hypothesis that the answer to question is in the subset of . When there is no ambiguity on the agent or the frame of discernment, the notation will be simplified to or .
- A subset of such that is called a focal set of . - A BBA with only one focal set is called a categorical BBA and is denoted ; we then have . - Total ignorance is represented by the BBA such that , called the vacuous mass function. - A normal BBA satisfies the condition . - A BBA whose focal sets are nested is said to be consonant.
The belief and plausibility functions associated with a BBA are defined, respectively, as:
for all .
Functions , and are in one-to-one correspondence, and thus constitute different forms of the same information.
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
Other rules exist: disjunctive rule, cautious rule, ...
In Bayesian decision theory, modeling a decision process implies defining:
- A set of decisions that can be made; - A set of considered states of nature; - A cost function , such that represents the cost of making decision when is the true state of nature.
Rationality principles justify the choice of the decision corresponding to the minimum expected cost or risk according to some probability measure on :
In the TBM, this decision-theoretic framework is accepted (see Smets 2005 for instance).
The set , called the betting frame, is often taken equal to . However, it may be any refinement or coarsening of ,or it may be obtained from by a succession of refinings and coarsenings.
The probability measure is obtained by the pignistic transformation, which consists in firstly expressing the piece of evidence , initially defined on the frame of discernment, on the betting frame , and then computing the pignistic probability as:
where denotes the cardinality of .