### Create a StudySoup account

#### Be part of our community, it's free to join!

Already have a StudySoup account? Login here

# Intro CS 3600

GPA 3.81

### View Full Document

## 8

## 0

## Popular in Course

## Popular in ComputerScienence

This 0 page Class Notes was uploaded by Alayna Veum on Monday November 2, 2015. The Class Notes belongs to CS 3600 at Georgia Institute of Technology - Main Campus taught by Thad Starner in Fall. Since its upload, it has received 8 views. For similar materials see /class/234032/cs-3600-georgia-institute-of-technology-main-campus in ComputerScienence at Georgia Institute of Technology - Main Campus.

## Reviews for Intro

### 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: 11/02/15

UNCERTAINTY AIMA2E CHAPTER 13 AIMAQe Thamer 3913 39l Outline ltgt Uncertainty ltgt Probability ltgt Syntax and Semantics ltgt Inference ltgt Independence and Bayes39 Rule AIMAQe Thamer 3913 2 Uncertainty Let action At leave for airport t minutes before flight Will At get me there on time Problems 1 partial observability road state other drivers39 plans etc 2 noisy sensors KCBS traffic reports 3 uncertainty in action outcomes flat tire etc 4 immense complexity of modelling and predicting traffic Hence a purely logical approach either 1 risks falsehood Ag5 will get me there on timequot or 2 leads to conclusions that are too weak for decision making Ag5 will get me there on time if there39s no accident on the bridge and it doesn39t rain and my tires remain intact etc etcquot A1440 might reasonably be said to get me there on time but I39d have to stay overnight in the airport AIMAQe Chapter 3913 3 Methods for handling uncertainty Default or nonmonotonic logic Assume my car does not have a flat tire Assume A25 works unless contradicted by evidence Issues What assumptions are reasonable How to handle contradiction Rules with fudge factors A25 H03 get there on time Sprinkler H099 WetGrass WetGrass r my Ram Issues Problems with combination eg Sprinkler causes Rain Probability Given the available evidence A25 will get me there on time with probability 004 Mahaviracarya 9th C Cardamo 1565 theory of gambling Fuzzy logic handles degree of truth NOT uncertainty eg WetGrass is true to degree 02 AIMAQe Thamer 3913 4 Probability Probabilistic assertions summarize effects of laziness failure to enumerate exceptions qualifications etc ignorance lack of relevant facts initial conditions etc Subjective or Bayesian probability Probabilities relate propositions to one39s own state of knowledge eg PAg5no reported accidents 006 These are not claims of some probabilistic tendency in the current situation but might be learned from past experience of similar situations Probabilities of propositions change with new evidence eg PA25no reported accidents 5 am 015 Analogous to logical entailment status KB oz not truth AIMAQe Chapter 3913 5 Making decisions under uncertainty Suppose I believe the following PA25 gets me there on time 004 PAgg gets me there on time 070 PA120 gets me there on time 095 PA1440 gets me there on time 09999 Which action to choose Depends on my preferences for missing flight vs airport cuisine etc Utility theory is used to represent and infer preferences Decision theory utility theory probability theory AIMAQe Chapter 3913 6 Probability basics Begin with a set Q the sample space eg 6 possible rolls of a die to E Q is a sample pointpossible worldatomic event A probability space or probability model is a sample space with an assignment PM for every w E Q st 0 S PW S 1 ZWPW 1 eg 131 132 133 134 135 136 16 An event A is any subset of Q PM I Zw APltw Eg Pdie roll lt 416 16 16 12 AIMAQe Thamer 3913 7 II Random variables A random variable is a function from sample points to some range eg the reals or Booleans eg Odd1true P induces a probability distribution for any rv X PX 332 ZwXwa7Pltw eg POddtrue 16 16 16 12 AIMAQe Thamer 3913 8 Propositions Think of a proposition as the event set of sample points where the proposition is true Given Boolean random variables A and B event a set of sample points where Aw true event pa set of sample points where Aw false event a b points where Aw true and Bw true Often in Al applications the sample points are defined by the values of a set of random variables ie the sample space is the Cartesian product of the ranges of the variables With Boolean variables sample point propositional logic model eg Atrue B false or a ob Proposition disjunction of atomic events in which it is true eg aVb E iaAbVaibVab gt PaVb PiabPaibPab AIMAQe Chapter 3913 9 Why use probability The definitions imply that certain logically related events must have related probabilities Eg Pa V b Pa Pb Pa 1 True de Finetti 1931 an agent who bets according to probabilities that violate these axioms can be forced to bet so as to lose money regardless of outcome ALMA Chapwr 3 u Syntax for propositions Propositional or Boolean random variables eg Cavity do I have a cavity Discrete random variables nite or in nite eg Weather is one of sunnyrainel0udy snow Weather rain is a proposition Values must be exhaustive and mutually exclusive Continuous random variables bounded or unbounded eg Temp216 also allow eg Temp lt 220 Arbitrary Boolean combinations of basic propositions AIMAQe Chapter 3913 39l 39l H Prior probability Prior or unconditional probabilities of propositions eg PCavitytrue 01 and PWeather sunny 072 correspond to belief prior to arrival of any new evidence Probability distribution gives values for all possible assignments PWeather 0720100801gt normalized ie sums to 1 Joint probability distribution for a set of rvs gives the probability of every atomic event on those rvs ie every sample point PWeather Cavity a 4 X 2 matrix of values Weather sunny rain Cloudy snow Cavitytrue 0144 002 0016 002 Cavityfalse 0576 008 0064 008 Every question about a domain can be answered by the joint distribution because every event is a sum of sample points AIMAQe Chapter 3913 3912 Probability for continuous variables Express distribution as a parameterized function of value PX 33 U18 26 uniform density between 18 and 26 0125 18 dX 26 Here P is a density integrates to 1 PX205 0125 really means dligopaos g X g 205 dacda 0125 AIMAQe Thamer 3913 3913 H Gaussian density 1 e H2202 27m 1393 AIMAQe Thamer 3913 3914 Conditional probability Conditional or posterior probabilities eg PCavitytoothache 08 ie given that toothache is all I know NOT if toothache then 80 chance of cavityquot Notation for conditional distributions PCavityToothaChe 2element vector of 2element vectors If we know more eg cavity is also given then we have PCavitytoothachecavity 1 Note the less specific belief remains valid after more evidence arrives but is not always useful New evidence may be irrelevant allowing simplification eg PCavitytoothache496rsWin PCavitytoothache 08 This kind of inference sanctioned by domain knowledge is crucial AIMAQe Chapter 3913 3915 Conditional probability Definition of conditional probability Pa b PU me NP 0 Product rule gives an alternative formulation Pa b PabPb pbaPa A general version holds for whole distributions eg PWeather Cavity PWeatherCavityPCavity View as a 4 X 2 set of equations not matrix mult Chain rule is derived by successive application of product rule PX17 Xn PX17 Xn1 PXnX17 Xn1 PX1 Xn2 PXmX1Xn2 PXnX1 Xn1 1PX77lX17 7Xi 1 AIM ARV Chapmr i3 i6 Inference by enumeration Start with the joint distribution toothache I toothache catch I catch catch I catch cavity 108 012 072 008 I cavity 016 064 144 576 For any proposition qb sum the atomic events where it is true Pub I szwi PWgt AIMAQe Thamer 3913 3917 Inference by enumeration Start with the joint distribution toothache I toothache catch I catch catch I catch cavity 108 012 072 008 I cavity 016 064 144 576 For any proposition qb sum the atomic events where it is true Pub I szwi PWgt Ptoothache 0108 0012 0016 0064 02 AIMAQe Thamer 3913 18 Inference by enumeration Start with the joint distribution toothache toothache catch I catch catch I catch cavity 108 012 072 008 I cavity 016 064 144 576 For any proposition qb sum the atomic events where it is true szwi Pltw Pcavitytoothache 010800120072000800160064 028 AIMAQe Thamer 3913 3919 Inference by enumeration Start with the joint distribution I toothache I toothache I catch catchl catch I catch cavity 108 012 072 008 I cavity 016 064 144 576 Can also compute conditional probabilities Pbcam ty toothache Ptoothache 0016 0064 0 4 0108 0012 0016 0064 39 P icavityltoothache AIMAQe Thamer 3913 20 II Normalization toothache toothache catch I catch catch I catch cavity 108012 072 008 Icavtty 016 064 144 576 Denominator can be viewed as a normalization constant 04 PCavitytoothache oz PCam39ty toothache oz PCam39ty toothache catch PCam39ty toothache icatch oz 0108 0016gt 0012 0064gt oz 012008gt 0604 General idea compute distribution on query variable by fixing evidence variables and summing over hidden variables AIMAQe Thamer 3913 239 Inference by enumeration contd Typically we are interested in the posterior joint distribution of the query variables Y given specific values 9 for the evidence variables E Let the hidden variables be H X Y E Then the required summation of joint entries is done by summing out the hidden variables PYEe aprv E29 aZhPY E29 th The terms in the summation are joint entries because Y E and H together exhaust the set of random variables Obvious problems 1 Worstcase time complexity 0d where d is the largest arity 2 Space complexity 0d to store the joint distribution 3 How to find the numbers for 0d entries AIMAQe Chapter 13 22 Independence A and B are independent iff PABPA or PBAPB or PABPAPB Cavity CaVlty decomposes into Toothache Catch Toothache Catch Weather 9 PT00thache Catch Cavity Weather PT00thache Catch CavityPWeather 32 entries reduced to 12 for n independent biased coins 2 gt 11 Absolute independence powerful but rare Dentistry is a large field with hundreds of variables none of which are independent What to do AIMAQe Chapter 13 23 Conditional independence PT00thachc Cavity Catch has 23 1 7 independent entries If I have a cavity the probability that the probe catches in it doesn39t depend on whether I have a toothache 1 Pcatcht00thachc cavity Pcatchcavity The same independence holds it I haven39t got a cavity 2 Pcatcht00thachc 1cavity Pcatchwcavity Catch is conditionally independent of Toothache given Cavity PCatchT00thachc Cavity PCatchCavity Equivalent statements PT00thachcCatch Cavity PT00thachcCavity PT00thachc Catcthavity PToothacheCavityPCatchCavity AIMAQe Chapter 13 21 Conditional independence contd Write out full joint distribution using chain rule PT00thache Catch Cavity PT00thache0atch CavityPCatCh Cavity PT00thache0atch CavityPCatchCavityPCavity PToothacheCavityPCatchCavityPCavity e 2 2 1 5 independent numbers equations 1 and 2 remove 2 In most cases the use of conditional independence reduces the size of the representation of the joint distribution from exponential in n to linear in n Conditional independence is our most basic and robust form of knowledge about uncertain environments AIMAQe Chamer 13 25 ayes ue B R 1 Product rule PM b PabPb PbaPa gt Bayes39 rule Pab W or in distribution form PltYIX 1W ozPXYPY Useful for assessing diagnostic probability from causal probability PEffect0ausePCause PEffect Eg let M be meningitis S be stiff neck P8mPm 08 X 00001 Hmls ms 01 Note posterior probability of meningitis still very small PCauselEffect 00008 AIMAQe Chapter 13 26 Bayes Rule and conditional independence PCavitylt00thache catch oz Pt00thache catcthavityPCavity ozPtoothachelCavityPcatcthavityPCavity This is an example of a naive Bayes model PCauseEffect1 Effectn PCauseHiPEffectiCause V Total number of parameters is linear in n AIMAQe Chamer 13 27 Wumpus World PM true iff 72j contains a pit Bij true iff 72 j is breezy Include only 811B12Bg1 in the probability model AIMAQe Chamer 13 28 Specifying the probability model The full joint distribution is PP11 PM BM 812 821 Apply product rule PBl1Bl2Bg1 P11 P44PP11 P4y4 Do it this way to get PEffect0ause First term 1 if pits are adjacent to breezes 0 otherwise Second term pits are placed randomly probability 02 per square PP11 P4A Hfj ylpmj 02n x 0816 for n pits AIMAQe Chapter 13 29 Observations and query We know the following facts I ob 312 bu known opm opm opal Query is PP13known b Define Unknown Bjs other than P13 and Known For inference by enumeration we have PP13known b ozzmkmmPP13 unknown known b Grows exponentially with number of squares AIMAQe Chamer 13 30 Using conditional independence Basic insight observations are conditionally independent of other hidden squares given neighbouring hidden squares Define Unknown Fringe U Other PbP13 Known Unknown PbP13 Known Fringe Manipulate query into a form where we can use this AIMAQe Chamer 13 31 Using conditional independence contd PP13known b oz Mam PP13 unknown known b oz Mam PbP13 known unknownPP13 known unknown 04 agLL96 07 Pbknown P13 fringe otherPP13 known fringe other 04 ag 96 07 Pbknown P13 fringePP13 known fringe other 04 Z PbknownP13fringe PP13knownfringeother 0t er fringe afz PbknownP13fringe L PP13PknownPfringePother ringe 0t er ozPknownPP13 f 2 PbknownP13 fringePfringe L Pother ringe 0t er oPP13 f 2 PbknownP13 fringePfringe range AIMAQe Chamer 13 32 PP13Iltm0wn b 0 02004 016 016 06004 016 031 069 22 ll PP22Im0wnb z 086014 AIMAQe Chamer 13 33

### BOOM! Enjoy Your Free Notes!

We've added these Notes to your profile, click here to view them now.

### 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'

## Why people love StudySoup

#### "I was shooting for a perfect 4.0 GPA this semester. Having StudySoup as a study aid was critical to helping me achieve my goal...and I nailed it!"

#### "I bought an awesome study guide, which helped me get an A in my Math 34B class this quarter!"

#### "I was shooting for a perfect 4.0 GPA this semester. Having StudySoup as a study aid was critical to helping me achieve my goal...and I nailed it!"

#### "It's a great way for students to improve their educational experience and it seemed like a product that everybody wants, so all the people participating are winning."

### Refund Policy

#### STUDYSOUP CANCELLATION POLICY

All subscriptions to StudySoup are paid in full at the time of subscribing. To change your credit card information or to cancel your subscription, go to "Edit Settings". All credit card information will be available there. If you should decide to cancel your subscription, it will continue to be valid until the next payment period, as all payments for the current period were made in advance. For special circumstances, please email support@studysoup.com

#### STUDYSOUP REFUND POLICY

StudySoup has more than 1 million course-specific study resources to help students study smarter. If you’re having trouble finding what you’re looking for, our customer support team can help you find what you need! Feel free to contact them here: support@studysoup.com

Recurring Subscriptions: If you have canceled your recurring subscription on the day of renewal and have not downloaded any documents, you may request a refund by submitting an email to support@studysoup.com

Satisfaction Guarantee: If you’re not satisfied with your subscription, you can contact us for further help. Contact must be made within 3 business days of your subscription purchase and your refund request will be subject for review.

Please Note: Refunds can never be provided more than 30 days after the initial purchase date regardless of your activity on the site.