Class Note for CMPSCI 683 at UMass(19)
Class Note for CMPSCI 683 at UMass(19)
Popular in Course
Popular in Department
This 14 page Class Notes was uploaded by an elite notetaker on Friday February 6, 2015. The Class Notes belongs to a course at University of Massachusetts taught by a professor in Fall. Since its upload, it has received 12 views.
Reviews for Class Note for CMPSCI 683 at UMass(19)
Report this Material
What is Karma?
Karma is the currency of StudySoup.
You can buy or earn more Karma at anytime and redeem it for class notes, study guides, flashcards, and more!
Date Created: 02/06/15
Victor Lesser CMPSCI 683 Fall 2004 The sources of uncertainty in intelligent systems Representing and reasoning with uncertain information Bayesian reasoning Chapter13i 136 In complex environment agent almost never have access to the whole truth about their environment RusseampNorvig Vimsta im Imprecise model of the environment medical diagnosisweather forecast Stochastic environment random processes moving obstacles Limited computational resources chess planning wih partial information Practical ignorance Limited communication resources distributed systems MAS without global view Practical Ignorance vvmamrm Noisy sensory data object identi cation and tracking Imprecise model of the system Medical science Theoretical Ignorance Exceptions to our knowledge can never be fully enumerated All birds ly Laziness Probability provides a way of numerically summarizing this uncertainty Vimsta im Because uncertainty a fact of life in most domains agents must be able to act in spite of uncertainty Making decisions without knowing everything relevant but using the best of what we do know Exploiting background and commonsense knowledge which is knowledge about what is generally true 39 HOW Shou39d agents bahaVe What is the quotrightquot thing to do Dif cult to eain represent in classical logic 7 l lroduce rEWlIemenf S f0 vaguwesa Wife aWl39i The rational agent model agents should do what is WWW9f 9W comadlctorv lnfovmation expected to maximize their performance measure glven Very different approaches based on type of reasoning the information thell haV DECiSion Theory required and assumptions about independence ofevidence Crucial to the architecture of an agent that is interacting 39 Thus a mt39ona39 dec39s39on 39quotVmVes kn w39quot9 with the real world 7 The relallve likelihood of achieying dirrerent statesgoals W e The challenge is how to acquire the necessary qualltatlve Probability Theory and quarllltatlve relationships and devlSll lg efficient methods WW me 59ml We from men WOW edge e The relallve importance payoff forval lous statesgoals W Utility Theory y Wicca nmt 5 y Wicca nmt a FirstOrder Loglc FOL makes the epl emological commitment that facts are either true false or Probability is about the agent s belief unkmwn not directly about the world rCOl ltrast Wlth ProbabllltyTheol y Degree of Bellef er Pl OpOSlllOl l same epistemological commitment as FOL Analogous to saying whether a given logical rCOl39ltract with Fuzzy Logic Degree ofTrutn in Proposition statement is entailed by the knowledge base Deductive inference can be done only with o Benefs depend on the percepts that the categorical facts de nitely true statements Thus FOL and logical agents cannot deal With uncerlalnly agent has recewed to date This is a naiorlinitation Sll39lcevlrtually all realaworld domains Percepts constitute the evidence on WW9 mm which probability assertions are based Eliminating uncertainty would require that ethe world be accessible Statlc and deterministic PrObab39 3995 can Change When more ethe agent has complete and correct knowledge evidence is acquired ill l5 practlcal to do complete sound ll39lferel39lce y Wicca nmt 7 y Wicca nmt a Most real domains are inaccessible dynamic and non deterministic at least from the agent s perspective in these domains it is impossible for an agent to know the exact state of its environment 7 Also agents can rarely be assumed to have complete correct knowledge of a domain The qualitication problem many rules about a domain will be incompleteincorrect because there are too many conditions to explicitly enumerate them all 7 E g birds tly unless they are dead hon7iiying types have broken a wing are caged etc Finally even where exact reasoning may be possible it will typically be impractical computationally FOL assumes that knowledge is complete and consistent Leads to the property of monotonicity once a fact is truebelieved it must remain so 7 Thus adding new knowledge always increases the size oithe knowledge base Nonmonotonicity the addition of new knowledge may require the retractionremoval of previously derived conclusions Using incomplete andor uncertain knowledge leads to nonmonotonicity 7 WM require that assumptions be made 7 lnterences may not be deducllvey vaid Probability exhibits nonmonotonicity 7 PAlE E2 not determined by RAlEQ y mesa nmt u More realistic approach to many applications but reasoning under uncertainty is more dif cult Nonmonotonic need to examine previously made conclusions based on new or modi ed evidence Nonmodular all the available evidence must be considered Uncertainty measures maraderize invisible fads how do the exceptions to A r B interact with the exceptions to B r C to yield the exceptions to A a C7 7 Probability as a way of summarizing the uncertainty that comes from our laziness and ignorance M Symbolic approaches represent the different possibilities without measuring their likelihood Can potentially combine There are several different numeric approaches probabilities certainty factors belief functions Dempster Shafer fuzzy logic We will focus on probabilistic reasoning faced lots of early objections y mesa nmt 2 McCarthy and Hayes claimed that probabilities are epistemologically inadequate leading AI researchers to stay away from it Some philosophical problems from the standpoint of arti cial intelligencequot Machine Intelligence 4463502 1969 Arguments against a probabilistic approach Use of probability requires a massive amount ofdata Use of probability requires the enumeration of all possibilities Hides details of character of uncertainty People are bad probability estimators We do not have those numbers We nd their use inconvenient v muses mm a The only satisfactory description of uncertainty is probability By this it is meant that every uncertainty statement must be in the form ofa probability that several uncertainties must be combined using the rules of probability and that the calculation ofprobabilities is adequate to handle all situations involving uncertainty In particular alternative descriptions of uncertainty are unnecessaryquot DV Lindey Statistical Science 2 1 724 1987 Probability theory is really about the structure of reasoningquot Glen Shafer v mesa mm 14 When I began writing Probabilistic Reasoning in Intelligent Systems 1988 I was working within the empiricist tradition In this tradition probabilistic relationships constitute the foundations of human knowledge whereas causality simply provides useful ways of abbreviating and organizing intricate patterns ofprobabilistic relationships Today my view is quite different I now take causal relationships to be the fundamental building blocks both of physical reality and of human understanding of that reality and I regard probabilistic relationships as but the surface phenomena of the causal machinery that underlies and propels our understanding of the worldquot Judea Pearl CAUSALITY Models Reasoning and Inference Cambridge University Press January 2000 v muses mm 15 A rulebased expert system developed In the mid 1970 s for automated diagnosis of infectious diseases Used certainty factors to represent likelihood Example if the stain of the organism is grampositive and the morpnoiogy ofthe organism is coccus and the growth conformation ofthe organism is clumps then 7 the identity ortne organism is staphyloccus Early and Simplified Approach to Dealing with Uncertainty and Incompleteness of Knowledge and Evidence data v mesa mm a Certainty factors are real numbers between 1 and 1 attached to facts and rules Positive and negative values indicate increase and decrease in the degree of belief Certainty factors are relative measures do not translate to absolute level of belief 7 The user provides uncertain observations with certainty factors attached to them Ex 09 organism is grampositive 04 morphology of the organism is coccus 07 the organism grows in clumps Belief in a conjunction of premises is calculated by max0min090407 04 Belief in conclusion CF x belief in premises 07 x 04 028 v mm m a B12 B1 Bz 1 B1 when both positive or negative B12 B1 Bzl1 minB1B2 with opposite signs Ex Combining 04 with 06 gives 04 06 1 o4 076 More positive evidence will always increase the certainty factor Evidence combination rule is commutative and associative hence order is unimportant g Evaluations of MYCIN show that it is as good or better than most human experts But certainty factors have no operational definition Hard to use in decision making Surprisingly good with appropriate knowledge engineering and limited forms of deduction v mm m 2 Connecting information derived from different paths Bidirectional inferences explaining away Correlated nonindependent sources of evidence Retracting conclusions monotonicity 21 Scenario c Events 5 spiinkiei was an Ins niiini w mass IS we R ii rained last niiiiii MVCINsole rules 1mm munquot was in 1m inan um mm 2 smmmve meme ml um the glass ml he Wet nquot mxmnq mm gm 2 wet in munquot um mm 2 Imam meme m um n tanned 1m mm combining miesweget IVBIWiSFng sprinkler suiiiies wei IVBIRMF an my 172 wet suggess mlquot so sprinkler made us believe rain v mesa mi 22 Let At leave for airport t minutes before the ight VWI At get me there on time Problems inaccessible world road state noisy sensors traf c reports uncertain actions blowout Suppose PA2504 PAeo6i PA1209i PAmo9995 Which action to choose Depends on preferences utilities Decision theory probability utility v mesa m 23 Assign a numerical degree of belief to propositions and ground sentences 0 s PA s 1 PTrue 1 PFalse D PA v B PA PB PA A B Other properties can be derived 1 PTrue PA v A PA P A PA A A PA P A So P A1 PA v mesa mi 24 Random experiments and uncertain outcomes Event Set refer to possible outcomes of a random experiment Elementary events the most detailed events of interest The number of distinct events and their definitions are totally subjective and depend on the decisionmaker v mm m 25 Represent the result of random experiments Notation x y 2 represent particular values of the variables X Y 2 Sample space the domain of a random variable set of all elementary events Ex Sample space graduating students Elementary events John Mary Event set Females graduating in civil engineering v mm m za For random variables we are interested in equalities like PX x1 07 E PX xi 1 since the values are exhaustive and mutually exclusive Can refer to the probabilities of all values at once as a vector PX 070102 Eg for Weather mnny cloudy rainy snowy can have PWeather 0702008002 Propositions are Boolean random variables v mm m 27 An assignment of probability to each event in the sample space Discrete vs continuous distributions Ex PWeather 07 02 008 002 sunnyraincloudysnow Q What are those numbers Where do they come from v mm m 22 Probabilities are precise properties ofthe universe Value can be obtained by reasoning for example if a coin is perfect use symmetry When probability of elementary events are equally likely Prevent size of event set size of sample space Exist only in artificial domains Require high degree of symmetry 29 Represent degrees of belief More realistic approach to representing expert opinion Examples The likelihood ofa patient recovering 39om a heart attack The quality of life in a certain city v mesa nmt u Probability as frequency of occurrence Prevent number of time event occurs number of repeated random experiments Problem Need to gather infinite amount of data and assume that the probability does not change over time Some experiments cannot be repeated 0 Success ofoil drilling at a particular location 0 Success ofmarketing a new PC operating system 0 Success ofthe UMass basketball team in 2005 u The appropriate probability to associate with a proposition depends on the knowledge Information that Is available PA denotes the prior probability prior The probability that A is true in the absence ofany speci c knowledge Once an agent has some knowledge evidence the prior is no longer applicable v mesa nmt 2 PA E denotes the conditional probability posterior probability the probability that A is true given that all we know is E e Probabilistic reasoning is inherently rlorlrmorlotorllc because there are no constraints on how conditional probabilities can vary e gwe can have PA lglbutPAlE1 590 7 Contrast this With FOL in which it K51 l othen K51 E l d Ex PCavityToothache 08 Similarly can use PABC etc as The notation PXY refers to the two dimensional table PXxiYyi Conditional probability can be defined in terms of unconditional probabilities PAB PABIPB when PB gt 0 or PAB PAB PB the product rule v was nmt 4 A probabilistic model consists of a set of random variables that can take on particular combinations orvaiues with certain probabilities An atomic event is an assignment of values to all the variabies eg X1x mXnx Atomic events are mutually exclusive and collectively exhaustive Theioint probability distribution loint PXXn assigns probabilities to all possible atomic events Thus it completely specifies the probability assignments for all propositions in the domain PA A B PAB PA v B PA PB PAB PA growl marginaiization or summing out PA EMA Bi PBi conditioning v was nmt as Given X1 Xquot thejoint probability distribution PX1 Xquot assigns probab es to each set of possible values of the variables Example Toothache Toothache Cavity 004 006 quotCavity 001 089 From the joint distribution we can compute the probability of any complex proposition such as PCavity v Toothache or PCavity Toothache Why not use thejoint probability distribution v was nmt as From the product rule Pi PlAIBl PM PlBIAl PlAl Hence PBA PAB PlBIPA Don t really need PlA llormalizatlon PlBIA a PlAIB PB Pl BIA 1 PW 39 Bl Pl B or WWW We can condition on background knowledge PlBIAiEl PlAIBiEl PlBIEll PlAIEl vumcsiwnm n Plobject image proportional to Plimage object Plobject Plsentence audio proportional to Plaudio sentence Plsentence Plfaut symptoms Plsymptoms fault Plfault Abductive Inferencell mnmsixmlm pa Abduction if As can cause Bs and know ofa B then hypothesize A as an explanation for the B Abductive inferences are uncertainlplausible inferences as opposed to deductivellogical inferences The existence of B provides evidence for A ie a reason to believe A Evidence from abductive inference is uncertain because there may be some other causelexplanation for B Abduction is the basis for medical diagnosis If disease D can cause symptom Sthen ifa patient has symptom S hypothesize that she suffers from disease D mneiusien may um have expiammn CONCLUSION uulmnwnvs negative EXPLANATION Maybe iineeriainirinreienee is v vana due m iineeriainaiirmues mneiusien may nei have 5 in premise and mneiusien Bumplete suppumugevldeulze T iukn wuvs negative premise may have a alernaime explauamus ennsrmeennr pnsnne PREMISE premise math lulerlam due tn menamfy in suppumugevideupe mnmsixmlm m HypotheSis Ebased on the ewdenc Ai where the compie evidence ix Hand A CAz Potenual xourcex of uncemintyin hypothexix rPanial evidenceric A A1 rUmE aln evidence satis es the inference axinmi Bi uncertain same Aquot E A ii E A1 rUmE aln pmmiSEriE somet E AIMS uncertain anssihle altamauve interpretations fEIIEVldBnEBrl Bi faminet E Alihecnnect1nferenceisAquot a C anssihle almamauve evidence furihe hypothesis 7 1 e i for same Aquot 6 Al the annealevidence 13 actually AI u Tmck Mama yixmym vmymzi pamatmusismy lt ltVDLVIDZis Vim pamatsuppunm E mismgsnppunmw g pusnhlealtrexpiauatmrehyp g te mayhepanufan g aiemaiwemk E menamtymsuppunmgemme mm Emmi Vehicle pusnhlealtrexpiauatmmypes P n MW anuistwghcst ammvu e W amth Eumrrmal mlmn vm mwmz u 3 pennies are placed in a box 2headed 2 tailed fair A coin is selected at random and tossed What is the probability that the 2H win was selected given that the outcome is H P2HH PH2H P2H PH2HP2H PH2TP2T PHFPF 11311l301l31l21l3 2l3 H i x PM P i y X Enwnw Consider a diagnosis probiem Witn muitipie symptoms Pdisrsl PdPsrslid 135 51 For eacn pair of symptoms We need to know Psrslid and Pssl Large amount of data is needed Need to make independence assumptions Psisl 135 Or conditional independence assumptions Ps isyd mid Psrslid rigid Psid 1mphciily d causes 3 and 3 With conditionai independence Bayes mie becomes PZiXiY oiPZ PXiZ PYiZ u Given PCavityToothache 08 PCavityCatch 095 Compute PCavityToothacheCatch PToothacheCatchCavity PCavity I P Need to know PToothacheCatchCavity Assuming conditional independence PXYZ PXZ and Bayes39 rule becomes PZXY u PZ PXZ PYZ PCatchCavity PToothacheCavity v mm m 45 Three prisoners A B and C have been tried for murder and their verdicts will be read and their sentences executed tomorrow morning They knowthat only one of them will be declared guilty and will be hanged while the other two will be set free the identity of the condemned prisoner is revealed to a very reliable prison guard but not to the prisoners themselves v mm m In the middle of the night Prisoner A calls the guard and makes the following request Please give this letter to one of my friends to one who is to be released You and I know that at least one of them will be freedquot The guard takes the letter and promises to do as told An hour later prisoner A calls the guard again and asks Can you tell me which of my friends you gave the letter to It should give me no clue regarding my own status because each of my friends has an equal chance of receiving my letterquot v mm m 47 The guard answers I gave the letter to prisoner B he will be released tomorrow Prisoner A returns to his bed and thinks Before ltalked to the guard my chances of being executed were one in three Nowthat lwas told that B will be released only C and I remain and my chances of dying have gone from 333 to 50 What did I do wrong I made certain not to ask any information relevant to my own fate Problem Did the guard reveal any information to prisoner A regarding his fate v mm m BM IE B will he declared innocentquot L21 IX stand 0 prison X will he declared innocentquot Ler ex stand ror prisoner x will he declared guiltyquot W 39quotquotquotquot quot 39quot 39quot quot quotquot1 mm I39B Guam said that B received the M12quot Then we compute HcAu39ap we get are correct answer PuarcAchp mm m 1 Hanna P1BGAJ PGAJ mm 1 PM PM M 2 HGNI39BD Pu39m m 3 o 5n Considerthefollowin resultsofatestoftwot es ofdrugs onagroup cheaply yp Probabilistic reasoning Mth belief networks DrugA mugs livai prep lived aim Men 550 am 20 10 Women 100 mu m m Suwivallormen DRUGA05LDRUGB 67 Suwivallorwomen DRUGAMSDRUG 42 Fonhelotal population DRUGA IME DRUG B 01 Is this a paradox 5r 52 Extra Slides
Are you sure you want to buy this material for
You're already Subscribed!
Looks like you've already subscribed to StudySoup, you won't need to purchase another subscription to get this material. To access this material simply click 'View Full Document'