Reasoning under Uncertainty: Probability, Bayes, Dempster-Shafer, and Decision Trees

Key Concepts and Definitions

Probability and Uncertainty

Uncertainty arises when we lack complete information about an event or outcome. Probability quantifies this uncertainty, providing a numerical measure of how likely an event is to occur. Probability theory is foundational for reasoning under uncertainty.

Probability Basics

• Probability Space: Defined by a sample space $S$, events $E\subseteq S$, and a probability measure $P$.
• Conditional Probability: $P(A|B)=\frac{P(A\cap B)}{P(B)}$, representing the probability of event $A$ given that $B$ has occurred.
• Bayes' Theorem: $P(H|E)=\frac{P(E|H)P(H)}{P(E)}$, used to update beliefs based on evidence.

Bayesian Networks

Bayesian networks (or belief networks) are graphical models that represent probabilistic relationships among variables. They consist of nodes (random variables) and directed edges (dependencies).

Structure of Bayesian Networks

• Nodes: Represent random variables (e.g., disease, symptoms).
• Edges: Indicate conditional dependencies (e.g., a disease causing symptoms).
• Conditional Probability Tables (CPTs): Specify probabilities for each variable given its parents.

Example: Medical Diagnosis

Consider a simple Bayesian network for diagnosing a disease $D$ based on symptoms $S_1$ and $S_2$:

Nodes:

• $D$: Disease (True/False)
• $S_1$: Symptom 1 (Present/Absent)
• $S_2$: Symptom 2 (Present/Absent)

CPT for $D$:

• $P(D=\text{True})=0.01$
• $P(D=\text{False})=0.99$

CPT for $S_1$ given $D$:

• $P(S_1=\text{Present}|D=\text{True})=0.9$
• $P(S_1=\text{Present}|D=\text{False})=0.1$

CPT for $S_2$ given $D$:

• $P(S_2=\text{Present}|D=\text{True})=0.8$
• $P(S_2=\text{Present}|D=\text{False})=0.2$

Worked Example: Calculating Probability of Disease

Suppose a patient exhibits both symptoms $S_1$ and $S_2$. What is the probability that the patient has the disease $D$?

Using Bayes' Theorem: $$P(D=\text{True}|S_1,S_2)=\frac{P(S_1,S_2|D)P(D)}{P(S_1,S_2)}$$

First, calculate $P(S_1,S_2|D)$: $$P(S_1,S_2|D)=P(S_1|D)P(S_2|D)=0.9\times 0.8=0.72$$

Next, calculate $P(S_1,S_2)$: $$P(S_1,S_2)=P(S_1,S_2|D)P(D)+P(S_1,S_2|\neg D)P(\neg D)$$ $$P(S_1,S_2|\neg D)=P(S_1|\neg D)P(S_2|\neg D)=0.1\times 0.2=0.02$$ $$P(S_1,S_2)=0.72\times 0.01+0.02\times 0.99=0.0072+0.0198=0.027$$

Finally, apply Bayes' Theorem: $$P(D=\text{True}|S_1,S_2)=\frac{0.72\times 0.01}{0.027}\approx 0.267$$

Thus, the probability that the patient has the disease given both symptoms is approximately 26.7%.

Dempster-Shafer Theory of Evidence

Dempster-Shafer theory (DST) is an extension of Bayesian probability that allows for uncertainty and ignorance. It uses belief functions to represent degrees of belief.

Key Concepts

• Frame of Discernment: Set of all possible hypotheses $\Theta$.
• Mass Function: Assigns a degree of belief to subsets of $\Theta$.
• Belief Function: Sum of masses of all subsets of a given hypothesis.
• Plausibility Function: Sum of masses of all subsets that do not contradict the hypothesis.

Comparison with Bayesian Probability

Worked Example: DST in Fraud Detection

Suppose a bank uses DST to detect fraudulent transactions. The frame of discernment $\Theta =\{F,\neg F\}$, where $F$ is "fraudulent" and $\neg F$ is "not fraudulent."

Mass Function Assignments:

• $m(\{F\})=0.3$ (30% belief in fraud)
• $m(\{\neg F\})=0.4$ (40% belief in no fraud)
• $m(\Theta )=0.3$ (30% ignorance)

Belief and Plausibility:

• Belief in $F$: $Bel(F)=m(\{F\})=0.3$
• Plausibility of $F$: $Pl(F)=1-m(\{\neg F\})=1-0.4=0.6$

Decision Making under Uncertainty

Decision-making under uncertainty involves choosing the best action given incomplete information. Common approaches include:

• Utility Theory: Maximizing expected utility.
• Decision Trees: Graphical representation of decisions and outcomes.

Decision Trees

Decision trees model sequential decisions and outcomes, incorporating probabilities and utilities.

flowchart TD
    A["Buy Stock"] --> B["Market Up: +1000"]
    A --> C["Market Down: -500"]
    D["Sell Stock"] --> E["Market Up: 0"]
    D --> F["Market Down: 0"]

Structure of a Decision Tree

• Decision Nodes: Represent choices (e.g., "Buy Stock" or "Sell Stock").
• Chance Nodes: Represent uncertain events (e.g., "Market Up" or "Market Down").
• Leaf Nodes: Represent outcomes with associated utilities.

Worked Example: Investment Decision

Consider an investor deciding whether to buy a stock. The market can go up (probability 0.6) or down (probability 0.4).

```mermaid
flowchart TD
    A["Buy Stock"] --> B["Market Up: +$1000"]
    A --> C["Market Down: -$500"]
    D["Sell Stock"] --> E["Market Up: $0"]
    D --> F["Market Down: $0"]

Utilities:

• Buy and Market Up: $1000
• Buy and Market Down: -$500
• Sell: $0 (regardless of market)

Expected Utility for Buying: [ EU(\text{Buy}) = 0.6 \times 1000 + 0.4 \times (-500) = 600 - 200 = 400 ]

Expected Utility for Selling: [ EU(\text{Sell}) = 0.6 \times 0 + 0.4 \times 0 = 0 ]

The investor should buy the stock since the expected utility ($400) is higher than selling ($0).

In the Real World

1. eSewa (Nepal):

   • Application: Fraud detection in online payments.
   • Idea Used: Bayesian networks to assess the probability of fraudulent transactions based on user behavior, transaction history, and device information.
   • How: If a user suddenly makes a large transaction from a new device, the system calculates the probability of fraud using Bayes' Theorem and flags suspicious activities.

2. Pathao (Nepal):

   • Application: Dynamic pricing and route optimization for ride-hailing.
   • Idea Used: Decision trees to adjust prices based on demand, time of day, and driver availability.
   • How: During peak hours, the system increases prices to balance supply and demand, using expected utility calculations to maximize both driver earnings and passenger satisfaction.

3. Ncell (Nepal):

   • Application: Predictive maintenance of network infrastructure.
   • Idea Used: Dempster-Shafer theory to combine sensor data and historical failure rates to predict equipment failures.
   • How: If multiple sensors indicate potential failure, the system aggregates evidence to compute belief and plausibility scores, triggering maintenance before a full breakdown occurs.

Exam Tip

For exams, focus on the following:

1. Understand the Definitions: Clearly define probability, conditional probability, Bayes' Theorem, and Dempster-Shafer theory.
2. Practice Calculations: Work through numerical examples for Bayesian networks and decision trees. Show all steps clearly.
3. Compare Methods: Be able to explain the differences between Bayesian probability and Dempster-Shafer theory, including when to use each.
4. Real-World Applications: Relate concepts to real-world scenarios like fraud detection, medical diagnosis, or dynamic pricing. Examiners often test applied understanding.
5. Diagrams: Draw Bayesian networks and decision trees accurately. Label nodes, edges, and probabilities clearly.
6. Common Pitfalls:
   • Misapplying Bayes' Theorem (e.g., confusing ( P(H|E) ) and ( P(E|H) )).
   • Incorrectly combining evidence in Dempster-Shafer theory (e.g., ignoring the frame of discernment).
   • Forgetting to calculate expected utilities correctly in decision trees.

flowchart TD
    A["Bayesian Network"] --> B["Nodes: Variables"]
    A --> C["Edges: Dependencies"]
    A --> D["CPTs: Probabilities"]
    E["Dempster-Shafer Theory"] --> F["Frame of Discernment"]
    E --> G["Mass Function"]
    E --> H["Belief/Plausibility"]
    I["Decision Trees"] --> J["Decision Nodes"]
    I --> K["Chance Nodes"]
    I --> L["Leaf Nodes: Utilities"]