Uncertainty Management

Drawbacks

The primary drawback of applying Bayes' rule for uncertainty management is that the number of probability values that need to be calculated and stored increases exponentially.

@TODO: add graph of the aforementioned exponential growth

Let us find an expression for \(P(H | E, e)\), where

\(H\) is the hypothesis
\(E\) is some new observation
\(e\) is a prior body of evidence

\[\begin{align} P(H | E, e) &= P(H | e) \cdot \frac{P(e | E \cap H)}{P(e | E)} \\ \end{align}\]

Specifically,

\[\begin{align} \frac{P(H \cap E \cap e)}{P(E \cap e)} &= \frac{P(e \cap E \cap H)}{P(E \cap e)} \\[0.8em] &= \frac{P(e | E \cap H) \cdot P(E \cap H)}{P(E \cap e)} \\[0.8em] &= \frac{P(e | E \cap H) \cdot P(H | E) \cdot P(E)}{P(e | E) \cdot P(E)} \\[0.8em] &= \frac{ P(H | E) \cdot P(e | E \cap H)}{P(e | E)} \\[0.8em] \end{align}\]

Dempster-Shafer Theory

Dempster-Shafer Theory (DST) assigns a belief interval to each/each set of hypotheses for some evidence.

It also provides a belief combination rules for multiple sources of evidence.

Example

Let:

\(U \rightarrow\) the universe of discourse
\(D \rightarrow\) certain disease
\(E \rightarrow\) some evidence

\(U = \{ D, \sim D \}\)

Let \(E\) suggest disease \(D\) with belief \(0.5\).

\[\text{Bel}(D) = 0.5\]

Then,

\[\underbrace{\enclose{horizontalstrike}{\text{Bel}(\sim D) = 0.5}}_{\text{Incorrect!}}\]

Instead, the negative belief is usually known.

Let \(\text{Bel}(\sim D) = 0.2\).

Then we define the plausibility \( (\text{Pl}) \) of \(D\) as:

\[\begin{align} \text{Pl}(D) &= 1 - \text{Bel}(\sim D)\\ &= 1 - 0.2 = 0.8 \end{align}\]

Now, the uncertainty in \(D\) is given by:

\[\text{Pl}(D) - \text{Bel}(D) = 0.8 - 0.5 = 0.3\]

And the belief interval for \(D\) is:

\[[\text{Bel}(D), \text{Pl}(D)] = [0.5, 0.8]\]

Computing Belief for Multiple Hypotheses

Let \(U = \{ A, F, C, P \}\), where:

\(U \rightarrow\) the universe of discourse
\(A \rightarrow\) Allergy
\(F \rightarrow\) Flu
\(C \rightarrow\) Cold
\(P \rightarrow\) Pneumonia

We define the mass probability assignment \(m\) as:

\[m : 2^U \rightarrow [0, 1]\]

For all possible subsets \(X \subseteq U\), we have:

\[\sum_{X \subseteq U} m(X) = 1\]

where:

\(m(X) \rightarrow\) measure of belief committed to exactly \(X\)
\(m(\emptyset) = 0\)

Also,

\[\text{Bel}(X) = \sum_{Y \subseteq X} m(Y)\]

The plausibility of \(X\) is also known as the "doubt on \(X\)":

\[\text{Pl}(X) = 1 - \text{Bel}(\sim X)\]

... and the belief interval for \(X\) is:

\[[\text{Bel}(X), \text{Pl}(X)] \text{ of } [0, 1]\]

Combining Belief Functions

We can combine belief functions arising out of different sources of evidence.

Let \(U = \{ A, F, C, P \}\)

Let \(e_1\) = fever suggest:

\(m_1(\{F, C, P\}) = 0.6\)
\(m_1({U}) = 0.4\)

Let \(e_2\) = runny nose suggest:

\(m_2(\{A, F, C\}) = 0.8\)
\(m_2({U}) = 0.2\)

We know,

\[\sum_{X \subseteq U} m(X) = 1\]

And thus we can derive \(m_3\) from \(m_1\) and \(m_2\). Each value of \(m_3\) is the product of the corresponding values of \(m_1\) and \(m_2\), and each set in \(m_3\) is the intersection of the corresponding sets in \(m_1\) and \(m_2\).

\( m_2(\{A, F, C\}) \; (0.8) \)

\( m_2(U) \; (0.2)\)

\( m_1(\{F, C, P\}) \; (0.6) \)

\(m_3(\{F, C\}) = 0.6 \times 0.8 = 0.48\)

\(m_3(\{F, C, P\}) = 0.6 \times 0.2 = 0.12\)

\( m_1(U) \; (0.4) \)

\( m_3(\{A, F, C\}) = 0.4 \times 0.8 = 0.32 \)

\( m_3(U) = 0.4 \times 0.2 = 0.08 \)

Now, let \(e_3\) = "the person goes away on trips" suggest:

\(m_4(\{ A \}) = 0.9\)
\(m_4(U) = 0.1\)

\( m_4(\{ A \}) \; (0.9) \)

\( m_4(U) \; (0.1)\)

\( m_3( \{F, C\} ) \; (0.48) \)

\( \emptyset \; (0.432) \)

\( \{F, C\} \; (0.048) \)

\( m_3( \{A, F, C\} ) \; (0.32) \)

\( {A} \; (0.288) \)

\( \{A, F, C\} \; (0.032) \)

\( m_3( \{F, C, P\}) \; (0.12) \)

\( \emptyset \; (0.108) \)

\( \{F, C, P\} \; (0.012) \)

\( m_3(U) \; (0.08) \)

\( {A} \; (0.072) \)

\( {U} \; (0.008) \)

From the table, \(m_5(\emptyset) = 0.432 + 0.108 = 0.54\).

Normalizing to get rid of belief 0.54 associated with \( \emptyset \) gives \(m_5\):

\(m_5(\{ F, C \}) = \frac{0.048}{1 - 0.54} = 0.104\)
\(m_5(\{ A, F, C \}) = \frac{0.032}{1 - 0.54} = 0.0696\)
\(m_5(\{ F, C, P \}) = \frac{0.012}{1 - 0.54} = 0.026\)
\(m_5(\{ A \}) = \frac{0.288 + 0.072}{1 - 0.54} = 0.782\)
\(m_5(U) = \frac{0.008}{1 - 0.54} = 0.017\)