UncertaintyChapter 14AIMA SlidescStuart Russell and Peter Norvig, 1998 Chapter 14 1Outline}Uncertainty}Probability}Syntax}Semantics}Inference rulesAIMA SlidescStuart Russell and Peter Norvig, 1998 Chapter 14 2UncertaintyLet actionAt= leave forairporttminutes before ightWillAtget me there on time?Problems:1) partial observability (road state, other drivers' plans, etc.)2) noisy sensors (KCBS trac rep orts)3) uncertainty in action outcomes (at tire, etc.)4) immense complexity of modelling and predicting tracHence a purely logical approach either1) risks falseho o d: \A25will get me there on time"or 2) leads to conclusions that are to o weak for decision making:\A25will get me there on time if there's no accident on the bridgeand it do esn't rain and my tires remain intact etc etc."(A1440might reasonably b e said to get me there on timebut I'd have to stay overnight in the airport:::)AIMA SlidescStuart Russell and Peter Norvig, 1998 Chapter 14 3Metho ds for handling uncertaintyDefault or nonmonotonic logic:Assume my car does not have a at tireAssumeA25works unless contradicted by evidenceIssues: What assumptions are reasonable? How to handle contradicti on?Rules with fudge factors:A257!0:3get there on timeS pr ink ler7!0:99W etGrassW etGrass7!0:7RainIssues: Problems with combination, e.g.,SprinklercausesRain??ProbabilityGiven the available evidence,A25will get me there on time with probability 0.04Mahaviracarya (9th C.), Cardamo (1565) theory of gambling(Fuzzy logic handlesdegree of truthNOT uncertainty e.g.,W etGrassis true to degree 0.2)AIMA SlidescStuart Russell and Peter Norvig, 1998 Chapter 14 4ProbabilityProbabilistic assertionssummarizeeects oflaziness: failure to enumerate exceptions, qualications, etc.ignorance : lack of relevant facts, initial conditions, etc.SubjectiveorBayesian probabili ty:Probabilities relate prop ositions to one's own state of knowledgee.g.,P(A25jno rep orted accidents)=0:06These are notassertions about the worldProbabilities of propositions change with new evidence:e.g.,P(A25jno rep orted accidents;5a.m.)=0:15(Analogous to logical entailment statusKBj=, not truth.)AIMA SlidescStuart Russell and Peter Norvig, 1998 Chapter 14 5Making decisions under uncertaintySupp ose I b elieve the following:P(A25gets me there on timej:::) = 0:04P(A90gets me there on timej:::) = 0:70P(A120gets me there on timej:::) = 0:95P(A1440gets me there on timej:::) = 0:9999Which action to cho ose?Dep ends on my preferences for missing ight vs. airp ort cuisine, etc.Utilitytheoryis used to represent and infer preferencesDecision theory= utility theory + probabili tytheoryAIMA SlidescStuart Russell and Peter Norvig, 1998 Chapter 14 6Axioms of probabilityFor any propositionsA,B1.0P(A)12.P(True)=1andP(False)=03.P(A_B)=P(A)+P(B),P(A^B)>A BTrueABde Finetti (1931): an agent who b ets according to probabiliti es thatviolate these axioms can b e forced to b et so as to lose money regardlessof outcome.AIMA SlidescStuart Russell and Peter Norvig, 1998 Chapter 14 7SyntaxSimilartoprop ositional logic: p ossible worlds dened by assignment ofvalues to random variables.Prop ositional or Bo olean random variablese.g.,C av ity(do I have a cavity?)Include prop ositional logic expressionse.g.,:Burglary_E ar thq uak eMultivalued random variablese.g.,W eatheris one ofhsunny ; r ain; cl oudy ; snowiValues must b e exhaustive and mutually exclusiveProp osition constructed by assignment of a value:e.g.,W eather=sunny; alsoCavity=tr ueforclarityAIMA SlidescStuart Russell and Peter Norvig, 1998 Chapter 14 8Syntax contd.Prior or unconditional probabilities of prop ositionse.g.,P(C av ity)=0:1andP(W eather=sunny)=0:72corresp ond to b elief priortoarrival of any (new) evidenceProbability distribution gives values for all possible assignments:P(W eather)=h0:72;0:1;0:08;0:1i(normalize d, i.e., sums to 1)Joint probability distributionforasetofvariables givesvalues for each possible assignment to all the variablesP(W eather; C av ity)=a42matrix of values:W eather=sunny rain cl oudy snowCavity=tr ueCavity=falseAIMA SlidescStuart Russell and Peter Norvig, 1998 Chapter 14 9Syntax contd.Conditional or p osteriorprobabilitie se.g.,P(C av ityjT oothache)=0:8i.e., given thatT oothacheis all I knowNotation for conditiona l distributions:P(W eatherjE ar thq uak e)= 2-element vector of 4-element vectorsIf weknowmore, e.g.,C av ityis also given, then we haveP(C av ityjT oothache; C av ity)=1Note: the less sp ecic b eliefremains validafter more evidence arrives,but is not alwaysusefulNew evidence may b e irrelevant , allowing simplicati on, e.g.,P(C av ityjT oothache;49er sW in)=P(CavityjT oothache)=0:8This kind of inference, sanctioned by domain knowledge, is crucialAIMA SlidescStuart Russell and Peter Norvig, 1998 Chapter 14 10Conditional probabilityDenition of conditional probabili ty:P(AjB)=P(A^B)P(B)ifP(B)6=0Pro duct rule gives an alternative formulation:P(A^B)=P(AjB)P(B)=P(BjA)P(A)A general version holds for whole distribution s, e.g.,P(W eather; C av ity)=P(W eatherjCavity)P(C av ity)(View as a42set of equations,notmatrix mult.)Chain ruleis derived by successive applicati on of product rule:P(X1;:::;Xn)=P(X1;:::;Xn,1)P(XnjX1;:::;Xn,1)=P(X1;:::;Xn,2)P(Xn1jX1;:::; Xn,2)P(XnjX1;:::; Xn,1)=:::=ni=1P(XijX1;:::;Xi,1)AIMA SlidescStuart Russell and Peter Norvig, 1998 Chapter 14 11Bayes' RulePro duct ruleP(A^B)=P(AjB)P(B)=P(BjA)P(A))Bayes' ruleP(AjB)=P(BjA)P(A)P(B)Why is this useful???For assessing diagnosticprobabili ty from causal probability:P(C ausejEffect)=P(Ef f ectjCause)P(C aus e)P(Ef f ect)E.g., letMb e meningitis,Sb e sti neck:P(MjS)=P(SjM)P(M)P(S)=0:80:00010:1=0:0008Note: p osteriorprobability of meningitis still very small!AIMA SlidescStuart Russell and Peter Norvig, 1998 Chapter 14 12NormalizationSupp ose we wish to compute a p osterior distribution overAgivenB=b, and supp oseAhas p ossible valuesa1:::amWe can apply Bayes' rule for each value ofA:P(A=a1jB=b)=P(B=bjA=a1)P(A=a1)=P(B=b):::P(A=amjB=b)=P(B=bjA=am)P(A=am)=P(B=b)Adding these up, and noting thatiP(A=aijB=b)=1:1=P(B=b)=1=iP(B=bjA=ai)P(A=ai)This is the normalization factor , constant w.r.t.i, denoted:P(AjB=b)=P(B=bjA)P(A)Typically compute an unnormalized distributi on, normalize at ende.g., supp oseP(B=bjA)P(A)=h0:4;0:2;0:2ithenP(AjB=b)=h0:4;0:2;0:2i=h0:4;0:2;0:2i0:4+0:2+0:2=h0:5;0:25;0:25iAIMA SlidescStuart Russell and Peter Norvig,