Reasoning with Uncertainty

• Utility
  • If a problem is not deterministic, the outcome of a state space transformation is uncertain.
  • The possible outcomes have degrees of probability, which must sum to 1.
  • The utility of a transformation is the sum of the products of the utilities of the outcome states with their probabilities.
  • If the environment is dynamic or not accessible, then the quality of a state is uncertain.
  • The possible state values have degrees of probability, which must sum to 1.
  • The utility of a state is the sum of the products of the quality of the state values with their probabilities.
  • Decision theory uses the utility of a transformation to decide what to do next.
    • Example with indeterminism
    • Example with inaccessible/dynamic environment
    • Example with indeterminism and inaccessible/dynamic environment

• Probability
  • P(A) is the prior or unconditional probability that A is true.
    • Probabilities for propositions of the form Variable = Value give the probabilities for the random Variable having the given Value
    • A probability distribution for a random variable gives the probabilities for all the possible values, e.g., P(Weather) = <0.7,0.2,0.08,0.02>, for the possible values sunny, rainy, cloudy, snowing.
  • Axioms of probability
    • P(true) = 1
    • P(false) = 0
    • P(A v B) = P(A) + P(B) - P(A & B) (note v for or)
    • For independent events, P(A & B) = P(A) * P(B)
    • For independent events, P(A by the Nth try) = 1 - (1 - P(A))^N
  • P(A|B) is the posterior or conditional probability that A is true given that B is known.
  • Converting between unconditional and conditional probabilities
    • P(A) = P(A|)
    • P(A|B) = P(A & B)/P(B)
    • P(A & B) = P(A|B)*P(B) (product rule for dependent events)
    • P(A & B) = P(B|A)*P(A)
    • P(A₁ & ... & A_n) = P(A₁|A₂ & ... & A_n) * P(A₂|A₃ & ... & A_n) * ... P(A_n) (chain rule)
  • Joint probability distribution
    • Assigns probabilities to all combinations of values for all the random variables, based on observations
    • The sum must be 1.
    • Given the joint, unconditional and conditional probabilities can be computed
    • Example

              sunny rainy cloudy snowing
      cold     0.01  0.10   0.04    0.20
      hot      0.50  0.05   0.10    0.00
                     

      • P(hot & sunny) = 0.50
      • P(hot) = 0.50 + 0.05 + 0.10 + 0.00 = 0.65
      • P(hot v sunny) = 0.01 + 0.50 + 0.05 + 0.10 + 0.00 = 0.66
      • P(hot v sunny) = P(hot) + P(sunny) - P(hot & sunny) = 0.65 + 0.51 - 0.50 = 0.66
      • P(hot|sunny) = P(hot & sunny)/P(sunny) = 0.50/0.51 = 0.98

• Baysian Reasoning
  • Bayes' rule is formed by combining the two forms of the product rule
    • P(A & B) = P(A|B)*P(B)
      P(A & B) = P(B|A)*P(A)
      ---------------------
      P(A|B) = P(B|A)*P(A)/P(B)
  • Example
    • P(meningitis) = 0.00002
      (count number of people who are treated)
    • P(stiff_neck|meningitis) = 0.5
      (collect data about people who are treated)
    • P(stiff_neck) = 0.05
    • P(meningitis|stiff_neck)
      = P(stiff_neck|meningitis)*P(meningitis)/P(stiff_neck)
      = 0.5 * 0.00002 / 0.05 = 0.0002
  • Example
    • 80% of students who pass have studied
    • 60% of students pass
    • 50% of students study
    • What is the probability of passing given that you study?

  • Normalization
    • If evidence supports two hypotheses, the relative likelyhood of the two can be computed without knowing the prior for the evidence.
      • P(A1|B) = P(B|A1)*P(A1)/P(B)
        P(A2|B) = P(B|A2)*P(A2)/P(B)
        ---------------------------------------------
        P(A1|B)/P(A2|B) = (P(B|A1)*P(A1)) / (P(B|A2)*P(A2))
    • Example
      • P(whiplash) = 0.001
      • P(stiff_neck|whiplash) = 0.08
      • P(meningitis|stiff_neck)/P(whiplash|stiff_neck)
        = (P(stiff_neck|meningitis)*P(meningitis)) / (P(stiff_neck|whiplash)*P(whiplash))
        = 0.5*0.00002/0.08*0.001 = 0.00125
  • Exhaustive consideration
    • If the prior for evidence is unknown, it can be eliminated by exhaustive consideration.
    • P(A|B) = P(B|A)*P(A)/P(B)
      P(~A|B) = P(B|~A)*P(~A)/P(B)
      P(A|B) + P(~A|B) = 1 = P(B|A)*P(A)/P(B) + P(B|~A)*P(~A)/P(B)
      P(B) = P(B|A)*P(A) + P(B|~A)*P(~A)
      P(A|B) = P(B|A)*P(A)/(P(B|A)*P(A) + P(B|~A)*P(~A))
      -----------------------------------------------------
      P(A|B) = P(B|A)*P(A)/(P(B|A)*P(A) + P(B|~A)*(1-P(A)))
    • Example
      • P(stiff_neck|~meningitis) = 0.05 (hard to get?)
      • P(meningitis|stiff_neck)
        = P(stiff_neck|meningitis)*P(meningitis)/
            (P(stiff_neck|meningitis)*P(meningitis) + P(stiff_neck|~meningitis)*(1-P(meningitis)))
        = 0.5*0.00002/(0.5*0.00002 + 0.05*0.99998) = 0.0002
  • Combining conditionally independent evidence
    • Given P(A|B) and P(A|C), what is P(A|B & C)
    • P(A|B & C) = P(B & C|A)*P(A)/P(B & C)
    • Conditional independence of evidence
      • B and C are independent in the face of A (but not completely independent).
      • E.g., A = raining, B = running, C = wet. Running and being wet are independent, but linked by the common cuae raining.
      • P(B|A & C) = P(B|A)
      • P(C|A & B) = P(C|A)
      • P(B & C|A) = P(B|A)*P(C|A)
      • Bayes updating equation:
        P(A|B & C)
        = P(B & C|A) * P(A) / P(B & C)
        = P(B|A) * P(C|A) * P(A) / P(B & C)
    • Independence of evidence
      • B and C are independent
      • P(A|B & C)
        = P(B|A) * P(C|A) * P(A) / P(B & C)
        = P(B|A) * P(C|A) * P(A) / (P(B) * P(C))
        = P(A|B) * P(C|A) / P(C)
    • Example
      • P(stiff_neck|whiplash & meningitis)
        = P(stiff_neck|whiplash) * P(meningitis|stiff_neck) / P(meningitis)
        = 0.08 * 0.0002 / 0.00002
        = 0.8
  • Belief Networks
    • Represent causes and effects, and their probabilities
    • Represent the joint, but as much of the joint is 0.0, belief networks are more compact and intuitive
    • Example

      Burglary P(B)=0.001      Earthquake P(E)=0.002
                         \     /
                          Alarm P(A| B &  E)=0.95
                                P(A| B & ~E)=0.94
                                P(A|~B &  E)=0.29
                                P(A|~B & ~E)=0.001
                         /     \
      JohnCalls P(J| A)=0.90    MaryCalls P(M| A)=0.70
                P(J|~A)=0.05              P(M|~A)=0.01
                     

    • The probability of some event is the product of it's probability and that of it's evidence.
      • Example:
        P(J & M & A & ~B & ~E) =
        P(J|A)*P(M|A)*P(A|~B & ~E)*P(~B)*P(~E) =
        0.90 * 0.70 * 0.001 * 0.999 * 0.998 = 0.00062
      • This can used to produce formulae for computing various forms of inference in a belief network
    • Causal inferences
      • From causes to effects
      • Example: P(J|B) = 0.85 and P(M|B) = 0.67
    • Diagnostic inferences
      • From effects to causes
      • Example: P(B|J) = 0.016
    • Intercausal inferences
      • Between causes of a common effect
      • Example: P(B|A) = 0.376 but P(B|A & E) = 0.003
    • Mixed inference
      • Combining the above
      • Example, diagnostic+causal: P(A|J & ~E) = 0.03
      • Example, intercausal+diagnostic: P(B|J & ~E) = 0.017

• Dempster-Shafer Theory of Evidence [Lug Ch.8.2.3]
  • Assigns a degree of belief and plausibility to subsets of a universe of atoms, given probabilities for the subsets.
    • The atoms must be exhaustive and mutually exclusive
    • Probabilities are for the exlusive disjunctions (XORs) of the atoms, and must be established externally
    • The probability of the empty set must be 0.
    • The sum of the probabilities over all subsets must be 1.
  • Example
    • Universe is {Good,Bad,Ugly}
    • P1({}) = 0.0
      P1({Good}) = 0.1
      P1({Bad}) = 0.3
      P1({Ugly}) = 0.4
      P1({Good,Ugly}) = 0.0
      P1({Good,Bad}) = 0.0
      P1({Bad,Ugly}) = 0.1
      P1({Good,Bad,Ugly}) = 0.1
      
  • Computing belief and plausibility
    • Beliefs and plausibilities are for the disjunction of the atoms
    • The belief in a subset is the sum of the probabilities for all subsets of the subset.
    • plausibility(X) = 1 - belief(~X), i.e., plausibility is the extent to which you could believe X
    • belief(~X) = belief(U\X)
    • The gap between belief and plausibility is the uncertainty.
  • Example
    • belief,plausibility({Good}) = 0.1, 0.2
      belief,plausibility({Bad}) = 0.3, 0.5
      belief,plausibility({Ugly}) = 0.4, 0.6
      belief,plausibility({Good,Bad}) = 0.4, 0.6
      belief,plausibility({Bad,Ugly}) = 0.8, 0.9
      belief,plausibility({Good,Ugly}) = 0.5, 0.7
      belief,plausibility({Good,Bad,Ugly}) = 1.0, 1.0
  • Combining beliefs
    • Given two independent probability distributions, e.g., from two different agents, the overall belief and plausibility can be computed with the Dempster rule

                         Sum of P1(X)*P2(Y) for all X,Y with intersection A
           P1+P2(A) = -------------------------------------------------------------
                      1 - Sum of P1(X)*P2(Y) for all X,Y with empty intersection
                     

    • Example
      • P2({Good}) = 0.2
        P2({Bad}) = 0.3
        P2({Ugly}) = 0.2
        P2({Good,Bad}) = 0.2
        P2({Bad,Ugly}) = 0.1
        belief,plausibility({Good}) = 0.2, 0.4
        belief,plausibility({Bad}) = 0.3, 0.6
        belief,plausibility({Ugly}) = 0.2, 0.3
        belief,plausibility({Good,Bad}) = 0.7, 0.8
        belief,plausibility({Bad,Ugly}) = 0.6, 0.8
        belief,plausibility({Good,Ugly}) = 0.4, 0.7
        belief,plausibility({Good,Bad,Ugly}) = 1.0, 1.0
      • P1+P2({Ugly}) = (0.08 + 0.04 + 0.02 + 0.02) / (1 - 0.48) = 0.31
        
      • P1+P2({Good,Bad}) = 0.02 / (1 - 0.48) = 0.04
        P1+P2({Good}) = 0.06 / (1 - 0.48) = 0.115
        P1+P2({Bad}) = 0.26 / (1 - 0.48) = 0.5
        Total = 0.655
      • belief,plausibility({Ugly}) = 0.31, 0.345
        

Exam Style Questions

• What are three sources of uncertainty?
• Give the algorithm for search with uncertainty, based on expected utility.
• Explain the difference between prior probability and conditional probability. Give the formula for computing conditional probability from prior probabilities.
• Derive how P(p -> q) can be computed from P(p), P(q), and P(~p & q).
• Given that 80% of students who pass have studied, on average 60% of students pass, and the probability of a student studying is 0.5, what is the probability of passing given that you study?
• Explain how Bayesian updating can be used to combine evidence.
• Explain what each of the following kinds of probabilistic inference are:
  • Diagnostic
  • Causal
  • Intercausal
  • Mixed