Last update: April 13, 2010UncertaintyCMSC 421: Chapter 13CMSC 421: Chapter 13 1MotivationLet action At= leave for airport t minutes before flightWill Atget me there on time?Problems:1) partial observability (road state, other drivers’ plans, etc.)2) noisy sensors (radio traffic reports)3) uncertainty in action outcomes (flat tire, etc.)4) immense complexity of modelling and predicting trafficHence a purely logical approach either1) risks falsehood: “A25will get me there on time”or 2) leads to conclusions that are too weak for decision making:“A25will get me there on time if there’s no accident on the bridgeand it doesn’t rain and my tires remain intact etc etc.”CMSC 421: Chapter 13 2Methods for handling uncertaintyDefault or nonmonotonic logic:Assume my car does not have a flat tireAssume A25works unless contradicted by evidenceIssues: What assumptions are reasonable? How to handle contradiction?Rules with fudge factors:A257→0.3AtAirportOnT imeSprinkler 7→0.99W etGrassW etGrass 7→0.7RainIssues: Problems with combination, e.g., Sprinkler causes Rain?ProbabilityGiven the available evidence,A25will get me there on time with probability 0.04Mahaviracarya (9th C.), Cardamo (1565) theory of gambling(Fuzzy logic handles degree of truth NOT uncertainty e.g.,W etGrass is true to degree 0.2)CMSC 421: Chapter 13 3Outline♦ Probability♦ Syntax and Semantics♦ Inference♦ Independence and Bayes’ RuleCMSC 421: Chapter 13 4ProbabilityProbabilistic assertions summarize effects oflaziness: failure to enumerate exceptions, qualifications, etc.ignorance: lack of relevant facts, initial conditions, etc.Subjective or Bayesian probability:Probabilities relate propositions to one’s own state of knowledgee.g., P (A25|no reported accidents) = 0.06They are not claims of a “probabilistic tendency” in the current situationThey might be learned from past experience of similar situationsProbabilities of propositions change with new evidence:e.g., P (A25|no reported accidents, 5 a.m.) = 0.15CMSC 421: Chapter 13 5Making decisions under uncertaintySuppose I believe the following:P (A25gets me there on time|. . .) = 0.04P (A90gets me there on time|. . .) = 0.70P (A120gets me there on time|. . .) = 0.95P (A1440gets me there on time|. . .) = 0.9999Which action to choose?Depends on both the probabilities and my preferencesmissing flight vs. getting to airport early and waiting, etc.Utility theory (Chapter 16) is used to represent and infer preferencesDecision theory = utility theory + probability theoryCMSC 421: Chapter 13 6Probability basicsBegin with a set Ω called the sample spaceEach ω ∈ Ω is a sample point/possible world/atomic evente.g., 6 possible rolls of a die: {1, 2, 3, 4, 5, 6}Probability space or probability model: take a sample space Ω, and assigna number P (ω) (the probability of ω) to every atomic event ω ∈ ΩA probability space must satisfy the following properties:0 ≤ P (ω) ≤ 1 for every ω ∈ ΩΣω∈ΩP (ω) = 1e.g., for rolling the die, P (1) = P (2) = P (3) = P(4) = P (5) = P (6) = 1/6.An event A is any subset of ΩP (A) = Σ{ω∈A}P (ω)E.g., P (die roll < 4) = P (1) + P (2) + P (3) = 1/6 + 1/6 + 1/6 = 1/2CMSC 421: Chapter 13 7Random variablesA random variable is a function from sample points to some rangeWe’ll use capitalized words for random variablese.g., rolling the die: Odd(ω) =true if ω is even,false otherwiseA probability distribution gives a probability for every possible value. If X isa random variable, then P (X = xi) = Σ{P (ω) : X(ω) = xi}e.g., P (Odd = true) = P (1) + P (3) + P (5) = 1/6 + 1/6 + 1/6 = 1/2Note that we don’t write Odd’s argument ω here.CMSC 421: Chapter 13 8PropositionsOdd is a Boolean or propositional random variable: its range is {true, false}We’ll use the corresponding lower-case word (in this case odd) for the eventthat a propositional random variable is truee.g., P (odd) = P (Odd = true) = 1/6P (¬odd) = P (Odd = false) = 5/6Boolean formula = disjunction of the sample points in which it is truee.g., (a ∨ b) ≡ (¬a ∧ b) ∨ (a ∧ ¬b) ∨ (a ∧ b)⇒ P (a ∨ b) = P (¬a ∧ b) + P (a ∧ ¬b) + P (a ∧ b)CMSC 421: Chapter 13 9Why use probability?The definitions imply that certain logically related events must have relatedprobabilitiesE.g., P (a ∨ b) = P (a) + P (b) − P (a ∧ b)>A BTrueA Bde Finetti (1931): an agent who bets according to probabilities that violatethese axioms can be forced to bet so as to lose money regardless of outcome.CMSC 421: Chapter 13 10Syntax for propositionsPropositional or Boolean random variablese.g., Cavity (do I have a cavity in one of my teeth?)Cavity = true is a proposition, also written cavityDiscrete random variables (finite or infinite)e.g., W eather is one of hsunny, rain, cloudy, snowiW eather = rain is a propositionValues must be exhaustive and mutually exclusiveContinuous random variables (bounded or unbounded)e.g., T emp = 21.6; also allow, e.g., T emp < 22.0.Arbitrary Boolean combinations of basic propositionse.g., ¬cavity means Cavity = falseProbabilities of propositionse.g., P (cavity) = 0.1 and P (W eather = sunny) = 0.72CMSC 421: Chapter 13 11Syntax for probability distributionsRepresent a discrete probability distribution as a vector of probability values:P(W eather) = h 0.72, 0.1, 0.08, 0.1 iprobabilities of sunny, rain, cloudy, snow (must sum to 1)If B is a Boolean random variable, then P(B) = hP (b), P (¬b)iA joint probability distribution for a set of n random variables gives theprobability of every atomic event on those variables (i.e., every sample point)Represent it as an n-dimensional matrixe.g., P(W eather, Cavity) is a 4 × 2 matrix:W eather =sunny rain cloudy snowCavity = true 0.144 0.02 0.016 0.02Cavity = false 0.576 0.08 0.064 0.08Every event is a sum of sample points, hence its probability is determined bythe joint distributionCMSC 421: Chapter 13 12Probability for continuous variablesExpress continuous probability distributions using parameterized functions,e.g.,Uniform density between 18 and 26f(x) = U[18, 26](x)0.125dx18 26Here f is a density; integrates to 1.P (20 ≤ X ≤ 22) =Z22200.125 dx = 0.25Gaussian densityP (x) =1√2πσe−(x−µ)2/2σ20CMSC 421: Chapter 13 13Conditional probabilityConditional or posterior probabilitiese.g., P (cavity|toothache) = 0.8i.e., given that toothache is all I knowNOT “if toothache then 80% chance of cavity”(Notation for conditional