CMPS 287 Final, Spring 1997

OF BEGAUT wieamrennsce! DEPARTMENT OF MATHEMATICS AMERICAN UNIVERSITY OF BEIRUT Math-287 Artificial Intelligence Final Exam — Spring, 1997 Three Hours Adnan Darwiche ID Number 1 Search (15 pts) (10pts) You are given a search tree with one node labeled as a start state S and another node labeled as a goal state G. Number the nodes in the tree according to the order in which they will be expanded (not the order in which they will first be encountered). When the order of expansion is arbitrary, assume that nodes are expanded from right to left. (a) (2pts) Breadth First Search. (b) (2pts) Depth First Search. ce (c) (2pts) Iterative Deepening Search. (d) (2pts) Uniform Cost Search. The cost of edges are given below. h. The cost of edges and the heuristic function are given below. (5pts) Consider the problem of scheduling classes for an undergraduate student through graduation. That is, we want to assign a set of classes for each semester of the student’s stay at school under the following assumptions: - The student must finish a given set of classes S. - For each class ¢, there is a set of prerequisites P, the student must finish before taking c. - The student must take between 2 and 5 classes per semester. The goal is to minimize the total number of semesters that the student spends at school. Represent this problem as a search problem. Describe the states, initial state, goal test, cost function (cost of each arc in the search tree) and operators. 2 Propositional Logic (10 pts) (4 pts) A satisfiable knowledge base A in propositional logic is said to be complete if and only if AF aorA - -a for any propositional sentence a. Prove that A is complete if and only if the meaning of A, M(A), is {w} for some world w. (3pts) Mark each of the following sentences as either unsatisfiable, satisfiable, or valid. (a) P>P (b) P> (Q=> P) (c) P= 7P (3pts) What is the difference between the following statements? (a) P>Q (b) PEQ (c) PFQ 3 First-Order Logic (15 pts) (3 pts) Use the following vocabulary to express the assertions in the following sentences: - Male(x) means that x is male. Female(x) means that x is female. Vegetarian(x) means that x is a vegetarian. Butcher(x) means that x is a butcher. Likes(x,y) means that x likes y. (a) All men except butchers like vegetarians. (b) No man likes a woman who is a vegetarian. (c) No woman likes a man who does not like all vegetarians. (6pts) The law says that it is a crime to sell an unregistered gun. Red has several unregistered guns, and all of them were purchased from Lefty. (a) Represent the previous information using first-order logic. Use the following vocabulary: Sold(x,y,z): x sold y to z. Unregistered(y): y is an unregistered gun. Criminal (x): x is a criminal. Owns(x,y): x owns y. (b) Convert the semences into clausal form (conjunctive normal form). (2pts) Pind the most general unifier if it exists: (a) P(z,F(G(w)),w) with P(F(y) , Fy) ,B) (b) PCF(x,x),A) with P(F(y,FCy,A)),A) Figure 1: A circuit. (4pts) Heads I win; tails you lose. Represent the previous situation using Logic and then use resolution to show that I win. Heads: flipping the coin yields a heads. Tails: flipping the coin yields a tails. Win(x): x wins. Lose(x): x loses. Restrict yourself to the above vocabulary. 4 Beliefs (10 pts) (2pts) Show that if a - G, then Belief(a) < Belief(f). (6pts) After your yearly checkup, the doctor has bad news and good news. ‘The bad news is that you tested positive for a serious disease, and the test is 99% accurate (that is, the probability of testing positive given that you have the disease is .99, as is the probability of testing negative given that you don’t have the disease). The good news is that this is a rare disease, striking only one in 10,000 people. (a) What is the probability that a person will test positive? (b) What is the probability that you have the disease? (c) Why is it good news that the disease is rare? Use the following vocabulary in your analysis: HaveDisease and TestPositive. (2pts) Is it possible to have Belief(a) = .3, Belief(@) = .4 and Belief(a V 8) = .5? Why? 5 Belief Networks (30 pts) (15pts) Consider the circuit in Figure 1. Each wire is either on or off. Each gate has one of three modes: stuck_at_0 (the output is zero independent of input), stuck_at_1 and ok. The belief in A being either on or off is equal, and the same applies to B. The belief in any mode being stuck_at_0 is .02 and the belief in it being stuck_at_/ is .01. Your task is to build a belief network for diagnosing the circuit. That is, given some observations about its input and output, the network will be used to compute the belief in each mode of cach gate. (a) Draw the structure of the belief network, using the following variables A, B, C, D, BE, ModeX, ModeY and ModeZ. (b) Provide the conditional belief table of each node. (c) Compute the belief in (A = on) A(B = on) A(C'= off) A(D = on) A (2 = off). (d) True or false: i. Belief(C = on | A= on A ModeX = ok) = Belief (C = on | A= on A ModeX = ok A D = on)? ii, Belief(C = on | A= on A ModeX = ok) = Belief(C = on | A= on A ModeX = ok A E = off)? (15pts) In your local nuclear power station, there is an alarm that senses when a temperature gauge exceeds a certain threshold. Consider the Boolean variables A (alarm sounds), #4 (alarm is faulty), and Fg (gauge is faulty), and the multivalued nodes G (gauge reading) and T (temperature). (a) Draw the belief network structure for this domain, assuming the gauge is more likely to fail when the temperature gets too high. (b) Suppose that there are only two valucs for the variables 7 and G: Normal and High. Suppose further that the gauge gives the incorrect reading 7% of the time when it is working, but y% of the time when it is faulty, Give the conditional probability table associated with G. (c) How would the belief in f4 change given that we observe the temperature T to be High? (d) Suppose we add a second temperature gauge H, connected so that the alarm will sound when either gauge reads High. Where do H and Fy; (gauge // failing) fit in the network? Draw the extended network. Figure 2: A neural network. 6 Neural Networks (15 pts) (3pts) Define each of the following terms briefly: (a) Perceptron (b) Feed-forward network (c) Recurrent network (7pts) Sanja is a robot operating in a world with two blocks A and B. Sanja’s goal is to keep the two blocks clear at all times. She has two sensors S4 and Sig. Sensor $4 tells Sanja whether Block Ais clear and sensor Sg tells her whether Block B is clear. Based on her sensory input, Sanja can take one of four actions: clear A, clear B, do nothing, and complain that she is sensing an impossible situation. Design a perceptron network that takes Sanja’s sensors as input and generates Sanja’s action as output. You need to have three oulpuls for the network, one for the action of clearing A, another for clearing B, and a third for complaining. For the neural network shown in Figure 2: (a) How many layers does the network have? (b) What is the output of the network given the inputs J; = 1 and J; = —1? (c) Give the equation for the output Os in terms of the inputs /; and /). The activation function at each node is a sign function. 7 Natural Language (5 pts) List three main difficulties that arise in natural language understanding but do not represent prob- lems for formal languages such as Pascal. Your points must concern syntax, semantics, and prag- matics. Explain each poirt briefly.