CS 188: Artificial Intelligence Fall 2008AnnouncementsSamplingPrior SamplingRejection SamplingLikelihood WeightingLikelihood SamplingSlide 10Slide 11Pacman ContestRecap: Inference ExampleDecision NetworksSlide 17Example: Decision NetworksSlide 19Value of InformationSlide 21VPI ExampleVPI PropertiesVPI ScenariosReasoning over TimeMarkov ModelsConditional IndependenceExample: Markov ChainMini-Forward AlgorithmSlide 30Slide 31Stationary DistributionsWeb Link AnalysisMost Likely ExplanationMini-Viterbi AlgorithmMini-ViterbiCS 188: Artificial IntelligenceFall 2008Lecture 18: Decision Diagrams10/30/2008Dan Klein – UC Berkeley1AnnouncementsP4 EXTENDED to Tuesday 11/4Midterms graded, pick up after lectureMidterm course evaluation up on web soon, please fill out!Final contest instructions out today!Prizes will be good 2SamplingBasic idea:Draw N samples from a sampling distribution SCompute an approximate posterior probabilityShow this converges to the true probability POutline:Sampling from an empty networkRejection sampling: reject samples disagreeing with evidenceLikelihood weighting: use evidence to weight samples3Prior SamplingCloudySprinklerRainWetGrassCloudySprinklerRainWetGrass4Rejection SamplingLet’s say we want P(C)No point keeping all samples aroundJust tally counts of C outcomesLet’s say we want P(C| s)Same thing: tally C outcomes, but ignore (reject) samples which don’t have S=sThis is rejection samplingIt is also consistent for conditional probabilities (i.e., correct in the limit)c, s, r, wc, s, r, wc, s, r, wc, s, r, wc, s, r, wCloudySprinklerRainWetGrassCSRW7Likelihood WeightingProblem with rejection sampling:If evidence is unlikely, you reject a lot of samplesYou don’t exploit your evidence as you sampleConsider P(B|a)Idea: fix evidence variables and sample the restProblem: sample distribution not consistent!Solution: weight by probability of evidence given parentsBurglary AlarmBurglary Alarm8Likelihood SamplingCloudySprinklerRainWetGrassCloudySprinklerRainWetGrass9Likelihood WeightingSampling distribution if z sampled and e fixed evidenceNow, samples have weightsTogether, weighted sampling distribution is consistentCloudyRainCSRW10Likelihood WeightingNote that likelihood weighting doesn’t solve all our problemsRare evidence is taken into account for downstream variables, but not upstream onesA better solution is Markov-chain Monte Carlo (MCMC), more advancedWe’ll return to sampling for robot localization and tracking in dynamic BNsCloudyRainCSRW11Pacman Contest14Recap: Inference ExampleFind P(W|F=bad)Restrict all factorsNo hidden vars to eliminate (this time!)Just join and normalizeWeatherForecastW P(W)sun 0.7rain 0.3F P(F|rain)good 0.1bad 0.9F P(F|sun)good 0.8bad 0.2W P(W)sun 0.7rain 0.3W P(F=bad|W)sun 0.2rain 0.9W P(W,F=bad)sun 0.14rain 0.27W P(W | F=bad)sun 0.34rain 0.6615Decision NetworksMEU: choose the action which maximizes the expected utility given the evidenceCan directly operationalize this with decision diagramsBayes nets with nodes for utility and actionsLets us calculate the expected utility for each actionNew node types:Chance nodes (just like BNs)Actions (rectangles, must be parents, act as observed evidence)Utilities (depend on action and chance nodes)WeatherForecastUmbrellaU16Decision NetworksAction selection:Instantiate all evidenceCalculate posterior over parents of utility nodeSet action node each possible wayCalculate expected utility for each actionChoose maximizing actionWeatherForecastUmbrellaU17Example: Decision NetworksWeatherUmbrellaUW P(W)sun 0.7rain 0.3A W U(A,W)leave sun 100leave rain 0take sun 20take rain 70Umbrella = leaveUmbrella = takeOptimal decision = leave18Example: Decision NetworksWeatherForecast=badUmbrellaUA W U(A,W)leave sun 100leave rain 0take sun 20take rain 70W P(W|F=bad)sun 0.34rain 0.66Umbrella = leaveUmbrella = takeOptimal decision = take19Value of InformationIdea: compute value of acquiring each possible piece of evidenceCan be done directly from decision networkExample: buying oil drilling rightsTwo blocks A and B, exactly one has oil, worth kPrior probabilities 0.5 each, mutually exclusiveCurrent price of each block is k/2MEU = 0 (either action is a maximizer)Solution: compute value of information= expected gain in MEU from observing new informationProbe gives accurate survey of A. Fair price?Survey may say “oil in a” or “oil in b,” prob 0.5 eachIf we know O, MEU is k/2 (either way)Gain in MEU?VPI(O) = k/2Fair price: k/2OilLocDrillLocUD O Ua a k/2a b -k/2b a -k/2b b k/2O Pa 1/2b 1/220Value of InformationCurrent evidence E=e, utility depends on S=sPotential new evidence E’: suppose we knew E’ = e’BUT E’ is a random variable whose value is currently unknown, so:Must compute expected gain over all possible values(VPI = value of perfect information)21VPI ExampleWeatherForecastUmbrellaUA W Uleave sun 100leave rain 0take sun 20take rain 70MEU with no evidenceMEU if forecast is badMEU if forecast is goodF P(F)good 0.59bad 0.41Forecast distribution22VPI PropertiesNonnegative in expectationNonadditive ---consider, e.g., obtaining Ej twiceOrder-independent23VPI ScenariosImagine actions 1 and 2, for which U1 > U2How much will information about Ej be worth?Little – we’re sure action 1 is better.Little – info likely to change our action but not our utilityA lot – either could be much better24Reasoning over TimeOften, we want to reason about a sequence of observationsSpeech recognitionRobot localizationUser attentionMedical monitoringNeed to introduce time into our modelsBasic approach: hidden Markov models (HMMs)More general: dynamic Bayes’ nets25Markov ModelsA Markov model is a chain-structured BNEach node is identically distributed (stationarity)Value of X at a given time is called the stateAs a BN:Parameters: called transition probabilities or dynamics, specify how the state evolves over time (also, initial probs)X2X1X3X4[DEMO: Battleship]26Conditional IndependenceBasic conditional independence:Past and future independent of the presentEach time step only depends on the previousThis is called the (first order) Markov propertyNote that the chain is just a (growing) BNWe can always use
View Full Document
Unlocking...