CS 470 - Problem Set 5

Assigned:Wednesday March 4
Deadline:Thursday April 2, 11:59pm

Reading

Russell and Norvig, "Artificial Intelligence: A Modern Approach", Third Edition, 2010. Chapters 13-17. pdf

Deliverable

Submit a file hw5.pdf with your answers. You may submit a file hw5.py with any code used in deriving your answers.

Chapter 13

  • 13.10. Deciding to put probability theory to good use, we encounter a slot machine with three independent wheels, each producing one of the four symbols BAR, BELL, LEMON, or CHERRY with equal probability. The slot machine has the following payout scheme for a bet of 1 coin (where “?” denotes that we don’t care what comes up for that wheel): 
    BAR/BAR/BAR pays 20 coins
BELL/BELL/BELL pays 15 coins
LEMON/LEMON/LEMON pays 5 coins
CHERRY/CHERRY/CHERRY pays 3 coins
CHERRY/CHERRY/? pays 2 coins
CHERRY/?/? pays 1 coin
    1. Compute the expected “payback” percentage of the machine. In other words, for each coin played, what is the expected coin return?
    2. Compute the probability that playing the slot machine once will result in a win.
    3. Estimate the mean and median number of plays you can expect to make until you go broke, if you start with 10 coins. You can run a simulation to estimate this, rather than trying to compute an exact answer.
  • 13.13. Consider two medical tests, A and B, for a virus. Test A is 95% effective at recognizing the virus when it is present, but has a 10% false positive rate (indicating that the virus is present, when it is not). Test B is 90% effective at recognizing the virus, but has a 5% false positive rate. The two tests use independent methods of identifying the virus. The virus is carried by 1% of all people. Say that a person is tested for the virus using only one of the tests, and that test comes back positive for carrying the virus. Which test returning positive is more indicative of someone really carrying the virus? Justify your answer mathematically.

    Chapter 14

  • 14.1. We have a bag of three biased coins a, b, and c with probabilities of coming up heads of 20%, 60%, and 80%, respectively. One coin is drawn randomly from the bag (with equal likelihood of drawing each of the three coins), and then the coin is flipped three times to generate the outcomes X1, X2, and X3.
    1. Draw the Bayesian network corresponding to this setup and define the necessary CPTs.
    2. Calculate which coin was most likely to have been drawn from the bag if the observed flips come out heads twice and tails once.

    Chapter 15

    None

    Chapter 16

    None

    Chapter 17

  • 17.5. For the environment shown in Figure 17.1, find all the threshold values for R(s) such that the optimal policy changes when the threshold is crossed. You will need a way to calculate the optimal policy and its value for fixed R(s). (Hint: Prove that the value of any fixed policy varies linearly with R(s).)

    Other hint: use the /c/cs470/hws/aima/mdp.py module, including the policy_iteration(mdp) procedure. Also, see the GridMDP editor in the /c/cs470/hws/aima/gui/grid_mdp.py module discussed at the end of the mdp.ipynb notebook.