Uncertainly and ProbabilisticReasoning1Overview• Uncertainty• Decision theory example• Probability basics• Conditional probability• Axioms of probability• Joint probability distribution• Bayes rule• Bayes rule: Example2Uncertainty• Problem with first-order logic: agents almost never have fullaccess to the whole truth about their environment.• Therefore, the agent must act under uncertainty.• Uncertainty can also arise because of incompleteness andincorrectness in the agent’s understanding of the properties in theenvironment.• Incomplete, because there are too many conditions to explicitlyenumerate.There are trade-offs (playing safe can result in other annoyances), thusthe right thing to do depends on both the relative importance of variousgoals and the likelihood (and degree to which) they will be achieved.3Example: Trying to Catch a FlightAt: plan to leave home t minutes before the flight departure time.• The traveler needs to make a decision in an uncertainenvironment: car can break down, traffic can be extremelycongested, natural disaster, etc.• Such worst-case scenarios are hard to explicitly enumerate: thelist goes on – ran out of gas, spouse/children in an emergency,flight crews goes on a strike, etc. etc.• Thus the traveler only has an incomplete understanding of thesituation.• The traveler can play safe by going with plan A1440, but this cancause the traveler to wait for a long time at the airport beforedeparture.4Difficulties in Applying F-O-L in Uncertain DomainsFor example, application of first-order logic in medical diagnosisdomain can fail because of these reasons:• Laziness: cannot list the complete set of antecedents andconsequents needed to ensure an exceptionless rule, and toohard to use the enormous rules that result.• Theoretical ignorance: medical science has no complete theory.• Practical ignorance: even though we have all the rules, it ispractically impossible to run all the tests.Similar situation arises in law, business, dating, etc. The agent’sknowledge can at best provide only a degree of belief. Probabilitytheory is well suited for such a domain.5Acquisition of New Information and Probability• The degree of belief changes as an agent perceives or acquiresnew information from the world: we call this the evidence.• This is analogous to saying whether or not a given logicalsentence is entailed by (i.e. is a logical consequence of) theknowledge base, because the truth value can change when newfacts are added to the KB.• Before the evidence is received, we talk about prior orunconditional probability.• After the evidence is obtained, we talk about posterior orconditional probability.6ExampleWhen playing black jack,• as new cards are drawn and shown, your degree of belief in thefact that you need more cards can change.What about poker? or slot machine?7Rational Decisions Under Uncertainty: DecisionTheory• There are trade-offs, and an agent must first have preferencesbetween different results when a certain plan was executed.• Utility theory deals with such preferences: how useful is suchand such result to the agent?• Decision theory is a general theory of rational decision underuncertainty, combining probability theory and utility theory.8Decision Theory• An agent is rational iff it chooses the action that yields the highestexpected utility, averaged over all possible outcomes of the action:Principle of Maximum Expected Utility• Example: backgammon (discussed earlier) – min-max trees withprobabilistic levels.9Decision Theoretic Agentfunction DT-Agent (percept) returns actionstatic: a set probabilistic belief about the state of the worldcalculate updated probabilities for current state based on per-cept and past actionscalculate outcome probabilities for actions, given action de-scriptions and prob of current states.select action with highest expected utility given prob of out-comes and utility information.return action10Decision Theory: ExampleDecision theory = Probability theory + Utility theoryUtility of Resulting State ProbabilityAction 1 10 0.2Action 2 10000 0.001Action 3 5 0.799Which action would an optimal Decision Theoretic Agent take?11Decision Theory: ExampleDecision theory = Probability theory + Utility theoryUtility of Resulting State × Probability Expected UtilityAction 1 10 × 0.2 2Action 2 1000 × 0.001 1Action 3 5 × 0.799 3.995 ←−Action 3 has the maximum expected utility, thus action 3 will be carr iedout.12Probability: Notationsa• Random variable: variable that can take on different values– A, B, ... : boolean values (T or F ).– X, Y, ... : numerical values or other multi-valuedenumerations (1, 2, 0.5, Cloudy, Rainy, Sunny, ...)• P (X = v) : probability of the variable X having value v.– This can be viewed as an event.– For boolean variables, P (A) means P (A = T), andP (¬A) means P (A = F).• P(X) : probability distribution, a full list of probabilities for allpossible values that X can take (note that P is in bold.aAll conventions follow Russel & Norvig13Examples• Boolean:P (Infected) = 0.01, P (¬Infected) = 0.99.• Multi valued:P (Dice = 1) =16, P (Dice = 2) =16, ...• Multi valued:P (W eather = Sunny) = 0.7,P (W eather = Rainy) = 0.2, ...14Logical Connectives and Conditional Probability• Logical connectives can be used:P (A ∨ B), P (A ∧ ¬B), P (Cavity ∧ ¬Insured), etc.• Conditional Probability P (A|B) (read probability of A given B):P (Cavity|T oothache) = 0.8• As new evidence comes in, the conditional probability getsupdated:P (Cavity| T oothache ∧ BadBr ea th| {z })15Conditional ProbabilityABA/\B=P(A|B) = P(A/\B)P(B)U• Think about the area occupied by each event.• The bounding rectangle U has an area of 1, thusP (A) =Area of AArea of U=Area of A1= Area of A• P (A|B) means B now takes on the role of U. Within thislimited event space, what is the probability of A.16The Axioms of ProbabilityAll axioms1. All probabilities are between 0 and 10 ≤ P (A) ≤ 12. For a valid proposition A (T under all interpretations):P (A) = 1, and for a inconsistent proposition A (F under allinterpretations): P (A) = 0.3. P (A ∨ B) = P (A) + P (B) − P (A ∧ B)Other properties follow from these three axioms.17Other Properties• From the axioms,P (A ∨ ¬A) = P (A) + P (¬A) − P (A ∧ ¬A)P (T) = P (A) + P (¬A) − P (F)1 = P (A) + P (¬A)P (¬A) = 1 − P (A)• More generally, the sum of probabilities P (X = v) is 1, for allvalues v