AI: Representation and Problem Solving

This comprehensive course covers topics such as Classical Planning, Propositional Logic, Markov Decision Processes (MDPs), Reinforcement Learning (RL), Bayes Nets, and more. Mid-terms, homework deadlines, and key concepts are highlighted. Explore Bayes nets and delve into Omega Pizzeria probability scenarios. Notations, discrete probability distributions, and problem-solving algorithms are also detailed. Dive into exploring random variables, outcomes, and domains. Learn about discrete random variables and their significance in problem-solving processes.

• AI
• Bayes Nets
• Problem Solving
• MDPs
• Reinforcement Learning

wininger_k Follow

Uploaded on Feb 15, 2025 | 0 Views

Download Presentation

Please find below an Image/Link to download the presentation.

The content on the website is provided AS IS for your information and personal use only. It may not be sold, licensed, or shared on other websites without obtaining consent from the author.If you encounter any issues during the download, it is possible that the publisher has removed the file from their server.

You are allowed to download the files provided on this website for personal or commercial use, subject to the condition that they are used lawfully. All files are the property of their respective owners.

The content on the website is provided AS IS for your information and personal use only. It may not be sold, licensed, or shared on other websites without obtaining consent from the author.

Presentation Transcript

1. AI: Representation and Problem Solving Bayes Nets Instructors: Aditi Raghunathan and Vince Conitzer Slide credits: CMU AI and http://ai.berkeley.edu

2. Announcements o Mid-term 2 11/9 o covers Classical Planning, Propositional Logic, MDPs, RL, Bayes 1, Bayes 2 o 80 minutes in class, same general rules HW7 due 10/31 HW8 due 11/7 P4 being released 11/2, due 11/16 2

3. MDPs and RL (things to be familiar with) o Formulation o Algorithms to solve MDPs o Try to really understand where these algorithms come from o Be able to do a few iterations yourself o RL (formulation what s known and what s unknown) o Direct policy evaluation, TD learning, Q-learning, approximate Q-learning o Exploration-exploitation tradeoff, regret 3

4. Bayes nets 4

5. Omega Pizzeria! What is the probability of getting a slice with: 1) No mushrooms 2) Spinach and no mushrooms 3) Spinach, when asking for slice with no mushrooms Icons: CC, https://openclipart.org/detail/296791/pizza-slice

6. Omega Pizzeria! What is the probability of getting a slice with: Mushrooms Spinach No spinach No spinach and mushrooms No spinach when asking for no mushrooms No spinach when asking for mushrooms Spinach when asking for mushrooms No mushrooms and no spinach Icons: CC, https://openclipart.org/detail/296791/pizza-slice

7. Notations and conventions in the course oRandom variables: oCapitalized oRepresents all potential outcomes oe.g. ? oOutcomes (values): olower case oe.g. +?, ?1, ?2, ?3 oVariables for values: olower case oE.g. ?

8. Discrete Probability Distributions For each random variable o Discrete outcomes o Disjoint outcomes o Accounts for entire event space o Not always binary Discrete Random Variables (and their domains) ? ?1,?2,?3 ? {+?, ?} ? {+?, ?}

9. Probability notation o In this lecture, we use upper case letters, Ato denote random variables o For a random variable Ataking values ?1,?2,?3 0.1 0.5 0.4 o ? ? = o represents the set of probabilities for each value that Acan take on (this is a function mapping values of Ato numbers that sum to one) o Conversely, we will use lower case ? to denote a specific value of ? (i.e., for above example a ?1,?2,?3), and ? ? = ? or just ? ? refers to a number (the corresponding entry of ? ? ) 9

10. Probability notation o Given two random variables: ? with values in {+?, ?} and ? with values in +?, ? : ?(B,?) refers to the joint distribution, i.e., a set of 6 possible values for each setting of variables, i.e. a function mapping +?,+? , +?, ? , ?,+? , to corresponding probabilities) ?(+?, ?) is a number: probability that B = +? and ? = ? ?(?,?) is a set of 2 values, the probabilities for all values of ? for the given value C = ?, i.e., it is a function mapping +?, ? to numbers (note: not probability distribution, it will not sum to one) Why? 10

11. Probability notation o Three random variables: ? ?1,?2,?3,? +?, ? ,? {+?, ?} o ? B = +?,? = ? ?1,?2,?3? ? = ?,B = +?,? o Also written as ? +?,? = ? ?1,?2,?3? ?,+?,?

12. Joint probability distribution ? +?, ? ? {+?, ?} o Table representing all values ? {+?, ?} A B C P(A=a, B=b, C=c) +a +? +? +a +? ? +a ? +? +a ? ? a +? +? a +? ? a ? +? a ? ? 12

13. Marginalization o For random variables B,? with joint distribution ? ?,? , the marginal probabilities ? ? ,?(?) are as follows o ? ? = ? {+?, ?} ? B,? = ? o ? ? = ? {+?, ?} ? B = b,C o ? +? = ? {+?, ?} ? +b,? = ? +?,+? + ?(+?, ?) 13

14. Marginalization from table A B C P(A=a, B=b, C=c) ? +?, ? ? {+?, ?} +a +? +? +a +? ? ? {+?, ?} +a ? +? +a ? ? a +? +? a +? ? a ? +? a ? ? What is ? ? ? 14

15. Marginalization from table A B C P(A=a, B=b, C=c) ? +?, ? ? {+?, ?} +a +? +? +a +? ? ? {+?, ?} +a ? +? +a ? ? a +? +? a +? ? a ? +? a ? ? Marginalization to get ?(?) : aggregating rows that share the same value of ? 15

16. Conditional probability o The conditional probability ? ? ?) (the conditional probability of ? given ?) is defined as ? ? ? =? ?,? ? ? ? +?,+? ? +? o ?(+? | ? = +?) = ? ?,+? ? +? o ?( ? | ? = +?) = 16

17. Conditional probability from table A B C P(A=a, B=b, C=c) ? +?, ? ? {+?, ?} +a +? +? +a +? ? ? {+?, ?} +a ? +? +a ? ? a +? +? a +? ? a ? +? a ? ? What is ? ?| ? = +? ? 17

18. Conditional probability from table A B C P(A=a, B=b, C=c) ? +?, ? ? {+?, ?} +a +? +? +a +? ? ? {+?, ?} +a ? +? +a ? ? a +? +? a +? ? a ? +? a ? ? We restrict our attention to rows that satisfy the given condition, and then normalize the values so that they sum to 1 (form a distribution) 18

19. Discrete probability distributions ?(?,?,?) o Joint distribution Discrete Random Variables (and their domains) ? +?, ? ? +?, ? ? +?, ? Icons: CC, https://openclipart.org/detail/296791/pizza-slice

20. Discrete probability distributions o Marginal distribution ?(?2) Discrete Random Variables (and their domains) ? +?, ? ? +?, ? ? +?, ? Icons: CC, https://openclipart.org/detail/296791/pizza-slice

21. Discrete probability distributions o Conditional distribution ? ?1, ?2 ?2) Discrete Random Variables (and their domains) ? +?, ? ? +?, ? ? +?, ? Icons: CC, https://openclipart.org/detail/296791/pizza-slice

22. Poll 1 o Which of the following probability tables sum to one? o Select all that apply i. ii. ? ?,?,? iii. ? ?,? ? iv. ? ?,? ? ?(? ?)

23. Bayes rule ?(B|C) =? ? B)?(B) ? ? Intuition: follow the expression for conditional probability ?(B|C) =? B,? ? ? =?(C|B)?(B) ? ? When is it used? Go from ? ? ? to ? ? ? 23

24. Poll 2 o I want to know if I have come down with a rare strain of flu (occurring in only 1/10,000 people). There is an accurate test for the flu: if I have the flu, it will tell me I have 99% of the time, and if I do not have it, it will tell me I do not have it 99% of the time. I go to the doctor and test positive. What is the probability I have this flu? (A) 99% (B) 10% (C) 1% (D) 0.1% 24

25. Probability Tools Summary ? ? ? =? ?,? 1. Definition of conditional probability ?(?) ?(?,?) = ? ? ? ?(?) 2. Product Rule ? ? ? =? ?|? ?(?) 3. Bayes theorem ?(?) ? 4. Chain Rule ? ?1, ,?? = ?(?? ?1, ,?? 1) ?=1

26. Additional probability tools Marginalization (law of total probability) (summing out) ?(?) = ?(?,?,?) ? ? ? ? ? =?(?,?) ?(?) Normalization ? ? ? ?(?,?) ? ? ? =1 ??(?,?) ? = ? ? = ?(?,?) ?

27. More practice What is the probability of getting a slice with: Icons: CC, https://openclipart.org/detail/296791/pizza-slice

28. Answer queries from joint distribution o You can answer all of these questions: ?(?| + ?) ?(?| s) ?(?,?) ?(?) +? +? 12/20 +? +?+? ? ? ? +? ? ?(?| + ?) ?(?| ?) ?+? ?(?) +? +? ? ? +? ? ? 6/12 ?

29. More practice Season Temp Weathe r P(S, T, W) o P(Weather)? summer hot sun 0.30 summer hot rain 0.05 o P(Weather | winter)? summer cold sun 0.10 summer cold rain 0.05 winter hot sun 0.10 winter hot rain 0.05 winter cold sun 0.15 o P(Weather | winter, hot)? winter cold rain 0.20

30. Answer Any Query from Joint Distribution Season Temp Weathe r P(S, T, W) o P(Weather)? summer hot sun 0.30 summer hot rain 0.05 summer cold sun 0.10 summer cold rain 0.05 winter hot sun 0.10 winter hot rain 0.05 winter cold sun 0.15 winter cold rain 0.20

31. Answer Any Query from Joint Distribution Season Temp Weathe r P(S, T, W) o P(Weather | winter)? summer hot sun 0.30 summer hot rain 0.05 summer cold sun 0.10 summer cold rain 0.05 winter hot sun 0.10 winter hot rain 0.05 winter cold sun 0.15 winter cold rain 0.20

32. Answer Any Query from Joint Distribution Season Temp Weathe r P(S, T, W) o P(Weather | winter, hot)? summer hot sun 0.30 summer hot rain 0.05 summer cold sun 0.10 summer cold rain 0.05 winter hot sun 0.10 winter hot rain 0.05 winter cold sun 0.15 winter cold rain 0.20

33. Answer Any Query from Joint Distribution o Joint distributions are the best! Joint Query ? ?1,?2 ?1,?2,?3)

34. Joint distributions o Joint distributions are the best! Joint Query o Problems with joints We aren t given the joint table o Usually some set of conditional probability tables ? ? ?)

35. Build joint distribution using CPTs Conditional Probability Tables and Chain Rule Joint Query ? ? ?) ? ? ? ? ? ? ? ?,? ? ? ?,?,??(?|?,?,?,?)

36. Build joint distribution using chain rule Two tools to construct joint distribution 1. Product rule o ? ?,? = ? ? ? ? ? o ? ?,? = ? ? ? ?(?) 2. Chain rule o ? ?1,?2, ,?? = ?? ?? o ? ?,?,? = ? ? ? ? ? ? ? ?,? for ordering A, B, C ?1, ,?? 1 o ? ?,?,? = ? ? ? ? ? ? ? ?,? for ordering A, C, B o ? ?,?,? = ? ? ? ? ? ? ? ?,? for ordering C, B, A o

37. Build joint distribution using chain rule o Binary random variables o Fire o Smoke o Alarm

38. Poll 3 o Variables o B: Burglary o A: Alarm goes off o M: Mary calls o J: John calls o E: Earthquake! How many different ways can we write the chain rule? A. 1 B. 5 C. 5 ? ???? 5 D. 5! E. 55

39. Build joint distribution using chain rule Conditional Probability Tables and Chain Rule Joint Query ? ? ?) ? ? ? ? ? ? ? ?,? ? ? ?,?,??(?|?,?,?,?)

40. Queries from CPTs o Process to go from (specific) conditional probability tables to query 1. Construct the joint distribution 1. Product Rule or Chain Rule 2. Answer query from joint 1. Definition of conditional probability 2. Law of total probability (marginalization, summing out)

41. Queries from CPTs o Bayes rule as an example o Given: ? ? ? , ? ? Query: ?(? ?) 1. Construct the joint distribution 1. Product Rule or Chain Rule ? ?,? = ? ? ? ?(?) 2. Answer query from joint 1. Definition of conditional probability ? ? ? =? ?,? ? ? 2. Law of total probability (marginalization, summing out) ? ?,? ??(?,?) o ? ? ? =

42. Bayes nets o Graphical representation of conditional probability tables o One node per random variable o Directed acyclic graph o Each node corresponds to a conditional probability distribution 42

43. Bayes nets o Each node corresponds to a conditional probability distribution o Bayes nets encode joint distributions as product of conditional distributions on each variable P(node | parents (node)) o Encode joint distributions as product of conditional distributions on each variable ? ?1, ,?? = ? ?? ???????(??)) 43 ?

44. Bayes nets ? ? ? ? ? ?,?,?,? = ? ? ? ? ? ? ? ?,? ? ? ?,?,? 44

45. Build Bayes Net Using Chain Rule o Binary random variables o Fire o Smoke o Alarm

46. Question o Variables o B: Burglary o A: Alarm goes off o M: Mary calls o J: John calls o E: Earthquake! ? ? ? ? ?

47. Answer Any Query from Bayes Net Joint Bayes Net and Conditional Probability Tables ? Query ? ? ? ?) ? ?

48. Answer any query from CPTs Conditional Probability Tables and Chain Rule Joint Query ? ? ?) ? ? ? ? ? ? ? ?,? ? ? ?,?,??(?|?,?,?,?)

49. Answer Any Query from Condition Probability Tables Conditional Probability Tables and Chain Rule o Problems Huge o ? variables with ? values o ?? entries We aren t given the right tables ? ? ? ? ? ? ? ?,? ? ? ?,?,??(?|?,?,?,?)

50. Do we need the full chain rule? o Some Bayes Nets represent simpler distributions o ? ?1,?2,?3,?4 = ? ?1? ?2?1? ?3?1,?2? ?4?1,?2,?3 = ? ?1? ?2?1)? ?3?2? ?4?3 50

Load More ...