Intelligent Systems Lecture Notes

21 October 2011 • Belief Networks

---

Outline

• Information and Knowledge
• Measuring Belief
• Conditioning
• The Chain Rule
• Conditional Independence
• Belief Networks
• Subjective Probability

Let’s Pretend

• You’re a doctor.
  There’s a patient waiting to see you.
  What’s wrong with the patient?
• Use health statistics and probability:

  Pr(lyme disease)	= 0.01%
  Pr(chlamydia)	= 0.4%
  Pr(heart disease)	= 55%

  The patient has heart disease.

• This doesn’t seem right, though. Why not?

Information and Knowledge

• What you know effects what you believe.
• Your belief that X can fly depends on X.
  • X is a pig; X is a bird; X is a man.
• Gathering and exploiting information about the world is important.
• But gathering and exploiting is imperfect.
  • Gathering the wrong information.
  • Misinterpreting the information gathered.

Measuring Belief

• With imperfection comes believing instead of knowing.
• Belief in proposition f is a number in [0..1], the probability of f.
  • The range [0..1] is a convention.
• 0: f is completely unbelievable.
• 1: f is unreservedly believed.
• A value between 0 and 1 is a measure of uncertainty (ignorance) about f.

Conditioning

• Conditioning revises beliefs based on new information.
• Prior probabilities (priors) model background information.
• All other information is handled by conditioning.
• If evidence e is all subsequent information, the conditional probability P(h | e) of h given e is the posterior probability of h.

Conditional Probability

• Evidence e rules out possible worlds incompatible with e.
• Evidence e induces a new measure \(\mu\)_e, over all possible worlds.
• The conditional probability of formula h given evidence e is

Conditionals

• The conditional probability

  Pr(a | b) = Pr(a \(\wedge\) b)/Pr(b)

• re-arranges to

  Pr(a | b)Pr(b) = Pr(a \(\wedge\) b)

• What is Pr(a \(\wedge\) b \(\wedge\) c)?

  
  
  

  Pr(a \(\wedge\) b \(\wedge\) c)	= Pr(a \(\wedge\) (b \(\wedge\) c))
  	= Pr(a | b \(\wedge\) c)Pr(b \(\wedge\) c)
  	= Pr(a | b \(\wedge\) c)Pr(b | c)Pr(c)

The Chain Rule

• The general pattern for conditional probabilities is known as the chain rule: \[Pr(\bigwedge_{i=1}^{n}p_i) = \prod_{i=1}^{n} Pr(p_i\;| \bigwedge_{j = i + 1}^{n} p_j) \]
• For example:

  Pr(p1 \(\wedge\) p2 \(\wedge\) p3 \(\wedge\) p4) =	Pr(p1 | p2 \(\wedge\) p3 \(\wedge\) p4) \(\cdot\)
  	Pr(p2 | p3 \(\wedge\) p4) \(\cdot\)
  	Pr(p3 | p4) \(\cdot\)
  	Pr(p4)

Chain Rule Example

Given a world with four boolean random variables

(p₁, p₂, p₃, p₄)

• The probability of some particular state of the world is

  Pr(p1 \(\wedge\) p2 \(\wedge\) p3 \(\wedge\) p4) =	Pr(p1 | p2 \(\wedge\) p3 \(\wedge\) p4) \(\cdot\)
  	Pr(p2 | p3 \(\wedge\) p4) \(\cdot\)
  	Pr(p3 | p4) \(\cdot\)
  	Pr(p4)

Problems

• A world with n boolean random variables requires O(2ⁿ) probability assignments.
  • The chain rule doesn’t change the computational complexity.
• Exponential growth is too expensive to be practical.
• How can the growth be tamed?

Cancer Rates

• Let C be “x has cancer.” Then Pr(C) = 0.0046.
• Let M be “x is male.” Then Pr(C | M) = 0.0054.
• Let R be “it is raining.” What is Pr(C | R)?
  • Rain has nothing to do with cancer (let us assume hope).
  • Then Pr(C | R) = Pr(C) = 0.46%.
• The evidence R has no influence on the hypothesis C.
  • C is conditionally independent of R.

Conditional Independence

• When does Pr(H | E) = Pr(H)?
  • That is, when is H conditionally independent of E?

  

So?

• If H is conditionally independent of E₁, then

  Pr(H | E₁ \(\wedge\) E₂) = Pr(H | E₂)

• Conditionally independent pairs (H, E) reduce the computation required by conditional probability.
• Straightforwardly applying the chain rule doesn’t exploit conditional independence.
  • This is what needs to be fixed.

Belief Networks

• Given a world, construct a directed, acyclic graph:
  • The nodes are random variables.
  • If p_i is conditionally independent of p_j, there is an edge from p_j to p_i.
    • p_j is a parent of p_i.
    • parent(p_i) is the set of p_i’s parents.
• The graph is a belief (or Bayesian) network.

Example

• The random variables

  p1 = burning		p3 = excessive heat
  p2 = excessive smoke		p4 = evacuation

• produce the belief network

  

Exploiting Independence

• Given a belief network, the chain rule can be re-interpreted as \[Pr(\bigwedge_{i=1}^{n}p_i) = \prod_{i=1}^{n} Pr(p_i\;|\;parents(p_i)) \]
• potentially reducing the computation required.
  • Alas, the computation is still exponential in the worst case.

Belief Network Example

• Adding independence reduces the amount computation needed.

  

  Pr(p1 \(\wedge\) p2 \(\wedge\) p3 \(\wedge\) p4) =	Pr(p1) \(\cdot\)
  	Pr(p2 | p1) \(\cdot\)
  	Pr(p3 | p1) \(\cdot\)
  	Pr(p4 | p2 \(\wedge\) p3)

Subjective Probability

• There are no definitive rules to
  • Figure out what evidence to use.
  • Figure out the independence between hypotheses and evidence.
• Different people make different choices, producing different results.
• Individual choice leads to subjective (or Bayesian) probability.

Summary

References

• Confidence Factors, Probability, Belief Networks, and Multivalued Logic (Chapter 10) in Intelligent Systems by Robert Schalkoff, Jones and Bartlett, 2011.
• Probabilistic Reasoning (Chapter 14) in Artifical Intelligence, third edition, by Stuart Russell and Peter Norvig, Prentice Hall, 2010.
• Vagueness, Uncertainty, and Degrees of Belief (Chapter 12) in Knowledge Representation and Reasoning by Ronald Brachman and Hector Levesque, Morgan Kaufmann, 2004.

Credits

• Health statistics from www.cdc.gov and seer.cancer.gov.

---

This page last modified on 2011 October 25.