1CS 1571 Intro to AIM. HauskrechtCS 1571 Introduction to AILecture 23Milos [email protected] Sennott SquareModeling uncertainty using probabilitiesCS 1571 Intro to AIM. HauskrechtAdministration• Final exam:– December 11, 2006– 12:00-1:50pm, 5129 Sennott Square2CS 1571 Intro to AIM. HauskrechtUncertaintyTo make diagnostic inference possible we need to represent knowledge (axioms) that relate symptoms and diagnosis Problem: disease/symptoms relations are not deterministic– They are uncertain (or stochastic) and vary from patient to patientPneumoniaCoughFeverPalenessWBC countCS 1571 Intro to AIM. HauskrechtModeling the uncertainty.Key challenges:• How to represent the relations in the presence of uncertainty? • How to manipulate such knowledge to make inferences?– Humans can reason with uncertainty. PneumoniaCoughFeverPalenessWBC count?3CS 1571 Intro to AIM. HauskrechtMethods for representing uncertaintyProbability theory • A well defined theory for modeling and reasoning in the presence of uncertainty• A natural choice to replace certainty factors Facts (propositional statements)• Are represented via random variables with two or more valuesExample: is a random variablevalues: True and False• Each value can be achieved with some probability:001.0)(==TruePneumoniaP005.0)(==highWBCcountPPneumoniaCS 1571 Intro to AIM. HauskrechtModeling uncertainty with probabilitiesProbabilistic extension of propositional logic.• Propositions:– statements about the world– Represented by the assignment of values to random variables• Random variables:– Boolean – Multi-valued– ContinuousFalseTruePneumonia ,either is },,,{ of one is SevereModerateMildNopainPainRandom variable ValuesRandom variableValues><250 ; 0in valuea is HeartRate Random variableValues!!4CS 1571 Intro to AIM. HauskrechtProbabilitiesUnconditional probabilities (prior probabilities)Probability distribution• Defines probabilities for all possible value assignments to a random variable• Values are mutually exclusive001.0)(==TruePneumoniaP001.0)( =PneumoniaP005.0)(== highWBCcountPor001.0)(== TruePneumoniaP999.0)(== FalsePneumoniaP)(PneumoniaPPneumoniaTrueFalse001.0999.0999.0)(== FalsePneumoniaPCS 1571 Intro to AIM. HauskrechtProbability distributionDefines probability for all possible value assignments001.0)(== TruePneumoniaP999.0)(== FalsePneumoniaP1)()(==+= FalsePneumoniaPTruePneumoniaP)(PneumoniaPPneumoniaTrueFalse001.0999.0005.0)(== highWBCcountP)(WBCcountPWBCcounthighnormal005.0993.0993.0)(== normalWBCcountP002.0)(== highWBCcountPlow 002.0Probabilities sum to 1 !!!Example 1:Example 2:5CS 1571 Intro to AIM. HauskrechtJoint probability distributionJoint probability distribution (for a set variables)• Defines probabilities for all possible assignments of values to variables in the setExample: variables Pneumonia and WBCcounthighnormal lowPneumoniaTrueFalseWBCcount0008.00042.00001.09929.00001.00019.0),( WBCcountpneumoniaPmatrix32×Is represented by CS 1571 Intro to AIM. HauskrechtJoint probabilitiesMarginalization• reduces the dimension of the joint distribution• Sums variables out )(WBCcountP005.0993.0 002.0),( WBCcountpneumoniaPhighnormal lowPneumoniaTrueFalseWBCcount0008.00042.00001.09929.00001.00019.0)(PneumoniaP001.0999.0Marginalization (here summing of columns or rows)matrix32×6CS 1571 Intro to AIM. HauskrechtFull joint distribution• the joint distribution for all variables in the problem– It defines the complete probability model for the problem• Example: pneumonia diagnosisVariables: Pneumonia, Fever, Paleness, WBCcount, Cough– Full joint defines the probability for all possible assignments of values to Pneumonia, Fever, Paleness, WBCcount, Cough ),,,,( FPalenessTCoughTFeverHighWBCcountTPneumoniaP ===== ),,,,( TPalenessFCoughTFeverHighWBCcountTPneumoniaP =====Ketc ),,,,( TPalenessTCoughTFeverHighWBCcountTPneumoniaP =====CS 1571 Intro to AIM. HauskrechtConditional probabilitiesConditional probability distribution • Defines probabilities for all possible assignments, given a fixed assignment to some other variable values)|()|(highWBCcountfalsePneumoniaPhighWBCcounttruePneumoniaP==+==0.10.10.1)|( WBCcountPneumoniaPhighnormal lowPneumoniaTrueFalseWBCcount08.092.00001.09999.00001.09999.03 element vector of 2 elements)|( highWBCcounttruePneumoniaP==7CS 1571 Intro to AIM. HauskrechtConditional probabilitiesConditional probability• Is defined in terms of the joint probability:• Example:=== )|( highWBCcounttruepneumoniaP0)( s.t. )(),()|( ≠= BPBPBAPBAP)(),(highWBCcountPhighWBCcounttruepneumoniaP====== )|( highWBCcountfalsepneumoniaP)(),(highWBCcountPhighWBCcountfalsepneumoniaP===CS 1571 Intro to AIM. HauskrechtConditional probabilities• Conditional probability distribution. • Product rule. Join probability can be expressed in terms of conditional probabilities• Chain rule. Any joint probability can be expressed as a product of conditionals)()|(),,(1,11,121 −−=nnnnXXPXXXPXXXP KKK0)( s.t. )(),()|( ≠= BPBPBAPBAP)()|(),( BPBAPBAP=)()|()|(2,12,111,1 −−−−=nnnnnXXPXXXPXXXP KKK∏=−=niiiXXXP11,1)|( K8CS 1571 Intro to AIM. HauskrechtBayes ruleConditional probability. Bayes rule:When is it useful?• When we are interested in computing the diagnostic query from the causal probability• Reason: It is often easier to assess causal probability– E.g. Probability of pneumonia causing fevervs. probability of pneumonia given fever )(),()|(BPBAPBAP =)()|(),( APABPBAP= )()()|()|(BPAPABPBAP = )()()|()|(effectPcausePcauseeffectPeffectcauseP =CS 1571 Intro to AIM. HauskrechtBayes Rule in a simple diagnostic inference. • Device (equipment) operating normally or malfunctioning.– Operation of the device sensed indirectly via a sensor• Sensor reading is either high or lowDevice statusSensor readingP(Device status)0.9 0.1normal malfunctioningDevice\Sensor high lownormal 0.1 0.9malfunctioning 0.6 0.4P(Sensor reading| Device status)9CS 1571 Intro to AIM. HauskrechtBayes Rule in a simple diagnostic inference.• Diagnostic inference: compute the probability of device operating normally or malfunctioning given a sensor reading• Note that typically the opposite conditional probabilities are given to us: they are much easier to estimate• Solution: apply Bayes rule to reverse the conditioning variables?)readingSensor |status