CSEP 573: Applications of Artificial Intelligence

 

Homework Assignment #2

 

Due: In class on Thursday, February 18, 2010

 

Turn-in procedure:  Bring a hardcopy containing your answers to class on February 18.

Make sure you write your name on the hardcopy.

If you are unable to make it to class, use the dropbox: https://catalysttools.washington.edu/collectit/dropbox/afriesen/8677

and submit your answers before class time on February 18. Use the naming convention HW2_<LastnameFirstname> for your file(s).

 

Reading: Chapters 5, 7-9, 13-14 in the textbook AIMA (3rd ed.).

 

Problems:

 

PART I: GAMES, LOGIC AND REASONING

 

1.      [20 points] Adversarial Search. Exercise 5.9, all parts in AIMA (3rd ed.).

 

2.      [20 points] Propositional Logic. Your neighborhood car mechanic has found out from Facebook that you are taking an AI course. She has asked you to build an expert system for diagnosing automobile problems and has provided you with the following rules to enter into the knowledge base of the expert system:

·         If there is gas in the tank and the fuel line is okay, then there is gas in the engine;

·         If there is gas in the engine and a good spark, the engine runs;

·         If there is power to the plugs and the plugs are clean, a good spark is produced;

·         If the battery is charged and the cables are okay, then there is power to the plugs.

 

a.       Convert the rules above to CNF using proposition symbols such as GasInTank, FuelLineOK, GasInEngine, etc.

b.      Suppose that you are given the facts that there is gas in the tank, the battery is charged, the fuel line and cables are both okay, and the plugs are clean. Using resolution, prove that the engine runs.

c.       Now write the four rules above as Horn clauses (as in Figure 7.16 in the text) using the same proposition symbols as in (a).

d.      Construct an AND-OR graph (as in Figure 7.16 in the text) based on (c).

e.       Given the same facts as in (b), prove using Forward Chaining that the engine runs: show the contents of the queue agenda in the forward chaining algorithm in Figure 7.15 in the AIMA text (3rd ed.), after initialization and after each iteration of the for loop.

 

3.      [10 points] First-Order Logic. Exercise 8.28 in AIMA (3rd ed.), parts c, d, f, h, and k.

 

4.      [15 points] Inference in FOL. Exercise 9.19 in AIMA (3rd ed.), all parts.

 

PART II: UNCERTAINTY AND PROBABILISTIC REASONING

 

5.      [15 points] Probabilistic Reasoning using Bayesian Networks. This problem is based on the Burglar Alarm Bayesian network shown in Figure 14.2, with its associated CPTs.

    1. Use inference by enumeration to compute the following (see Lecture Slides and section 14.4 in the text for an example):

                                                              i.      P(Burglary | JohnCalls = true, MaryCalls = false)

                                                            ii.      P(Alarm)

    1. Now, compute P(Burglary | JohnCalls = true, MaryCalls = false) using the variable elimination algorithm. Show all the steps and factors involved (see section 14.4 in the text for an example).

 

6.      [20 points] Fun with Bayesian Networks in Weka. Download and install Weka 3.6.2 from: http://www.cs.waikato.ac.nz/~ml/weka/index_downloading.html.

Open the application and under “Tools”, select “Bayes net editor”. You should now get a new window titled Bayes Network Editor. Under Edit, you will find Add Node and Add Arc. Create the Burglar Alarm Network from Figure 14.2 in the text. Once you have the correct structure, right click on each node and Edit CPT to match Figure 14.2 (note: you have to double-click each CPT box to enter values). Now you are ready for inference!

a.       Go to Tools and select Show Margins. This should show the marginal probabilities for each node. You can now set a node to a particular value (the evidence) by right clicking the node and selecting “Set evidence”. Use this to compute P(Burglary | JohnCalls = true, MaryCalls = false). Does the result match your answers from 5a and 5b above? Now compute the probability of burglary given that both John and Mary have called. Submit a screen capture of the Weka window showing your network and outputs.

 

b.      You have recently joined the Fraud Detection group of a major corporation (that shall go unnamed).  You have been assigned the job of building a Bayesian reasoning system for detecting fraud in credit card transactions. You have been given the following information:

Fraudulent transactions are more likely during foreign travel: 2% of purchases are fraudulent given a customer is travelling, whereas only 0.5% of the transactions are fraudulent if the customer is not traveling. Overall, 10% of all transactions happen while traveling and the rest while not travelling. When the customer is not traveling, 15% of the fraudulent transactions are foreign purchases but only 2% of the legitimate transactions are foreign purchases. On the other hand, when the customer is traveling, 90% of the transactions are foreign purchases regardless of the legitimacy of the transactions. 

Create a Bayesian network with three nodes, Travelling, ForeignPurchase, and Fraud, with the appropriate arcs and CPTs that capture the information above. Suppose there has been a foreign purchase but the system does not know if the customer is travelling or not. Compute the probability of fraud given the foreign purchase. Submit a screen capture of the Weka window showing your network and outputs.

 

 

EXTRA CREDIT PROBLEMS:

 

1.      [10 points] Exercise 5.7 in AIMA (3rd ed.).

 

2.      [10 points] (Based on “The Adventure of Silver Blaze,” an original Sherlock Holmes mystery by A. Conan Doyle)

A prize-winning racehorse named Silver Blaze has been stolen from a stable, and a bookmaker named Fitzroy Simpson has been arrested by good old Inspector Gregory as the prime suspect. Sherlock Holmes, however, after ample use of his magnifying glass and some of the strongest black tobacco this side of the Atlantic, is able to find the true thief by reasoning from the following premises:

 

a)      The horse was stolen either by Fitzroy or by its trainer John Straker.

b)      The thief had to have entered the stable the night of the theft.

c)      If a stranger enters the stable, the dog barks.

d)     Fitzroy was a stranger.

e)      The dog did not bark.

 

Who stole Silver Blaze? Prove your assertion using the technique of resolution. Construct your resolution proof using only the following proposition symbols:

ThiefFitzroy                      ThiefJohn

EnteredStableFitzroy        EnteredStableJohn

StrangerFitzroy                 StrangerJohn

BarksDog

 

3.      [10 points] Exercise 9.10 in AIMA (3rd ed.).

4.      [10 points] Using the Weka Bayes Network Editor, construct the Bayesian network in Figure 14.23 in AIMA (3rd ed.).

a.       Calculate the probability of being jailed if you break the election law.

b.      Calculate the probability of being jailed given that you broke the law, have been indicted, and your prosecutor is politically motivated.

c.       Calculate the probability that your prosecutor was politically motivated, given that you are in jail.

d.      Suppose you want to add a new variable P = PresidentialPardon to the network. Construct the new network and explain any new probabilities and arcs (links) you have added. Now recompute the probability of being jailed if you break the election law.

Along with your answers for (a)-(d), include a screen capture of the Weka window showing the network and outputs.