## Artificial Intelligence Final Exam : May 1996 --- Solutions

### Problem 1:

(15 points) Give an example of an English text that has a potential anaphoric ambiguity that can be resolved using selectional restrictions. Explain the selectional restriction used.

Answer: The easiest way to construct an example is to first think of a selectional restriction. E.g. The subject of "eat" must be animate. Then for the anaphoric ambiguity, construct a text in which "it" is the subject of "eat" and it could refer either to an animate or an inaminate precedent. E.g. "Yesterday, I saw a pigeon sitting on the grass. It was eating a piece of bread." Here the anaphoric ambiguity of whether "it" refers to the pigeon or the grass is resolved by the selectional restriction that the subject of "it" must be animate. There are many other possible answers, of course.

### Problem 2:

(20 points) Consider the following problem: You have a collection of blocks, and you wish to stack them one on top of another to make as tall a tower as possible. However, the blocks are oddly shaped, so not every block will fit on top of every other block. For instance, you might know that block A will fit on blocks D, E, and F; that block B will fit on top of A, C, D,; that C will fit on A, D and E; that D will fit on C and E; that E fits on A and D; and that F does not fit on any block. Then the tallest tower has height 5; for example, A, E, D, C, B. It is not possible to build a block using all 6 blocks.
• A. Show how to use state space search to solve this problem. In particular, you should specify (i) What is a state? (ii) What is an operator? (iii) What is the start state? (iv) What is the objective of the search?

Answer:

i. A state is a tower.

ii. An operator is adding a block to the top of the tower.

iii. The start state is the empty tower.

iv. The objective of the search is to find the state furthest from the start state. In that respect, it differs from the various state space searches we discussed in class.

• B. What search technique would you use to solve this problem? Give an upper bound on the required time and space.

Answer: Since we are looking for the deepest solution, the search technique to use is a depth-first search. The time is proportional to the number of states in the space. Now, there is one state at the root; N states at the 1st level; at most N(N-1) states at the second level at most N(N-1)(N-2) states at the third level ... at most N! states at the Nth level. Hence the number of states is bounded by
N!/(N-1)! + N!/(N-2)! + N!/(N-3)! + ... + N!/1! + N!/0! < e N! which is O(N!). The space required is proportional to the depth of the search space, which is N.

### Problem 3:

(10 points) In the MAX-MIN tree shown below, for what values of node X can node Y be pruned?

Answer: Y can be pruned if X <= 5.

### Problem 4:

(10 points) Name three conditions that must hold on a game for the technique of MIN-MAX game-tree evaluation to be applicable.

Answer: (i) It must be (i) zero-sum; (ii) perfect knowledge; (iii) deterministic; (iv) two-player; (v) discrete.

### Problem 5:

(10 points) Give an example of a Prolog program and a query that never returns an answer if the interpreter uses a depth-first search (as Prolog does), but that will return an answer if the interpreter is modified to use an iterative deepening search. (Hint: there is an example that uses one rule and one fact.)

Answer:

```Program:
p(X) :- p(X).
p(a).

Query:
?- p(a).
```

### Problem 6:

(5 points) Which of the following describes the process of task execution (classifying input signal) in a feed-forward, back-propagation neural network? Which describe the process of learning? (One answer is correct for each.)
• a. Activation levels are propagated from the inputs through the hidden layers to the outputs.
• b. Activation levels are propagated from the outputs through the hidden layers to the inputs.
• c. Weights on the links are modified based on messages propagated from input to output.
• d. Weights on the links are modified based on messages propagated from output to input.
• e. Connections in the network are modified, gradually shortening the path from input to output.
• f. Weights at the input level are compared to the weights at the output level, and modified to reduce the discrepancy.

Answer: Task execution is carried out through process (a). Learning is carried out through process (d).

### Problem 7:

(10 points) Explain briefly (2 or 3 sentences) the use of a training set and a test set in evaluating learning programs.

Answer: When you wish to evaluate a learning program using a fixed corpus of examples, it is common to divide the corpus into a training set and a test set. The program is first trained by running it on the training set. Then the learning module is turned off, and the quality of the current state of the execution module is tested by running it on the test set. In this way you guard against the possibility of overlearning, in which the program simply learns the examples in the corpus, rather than the underlying concept.

### Problem 8:

(10 points) Let H be a hypothesis in the set S (of too specialized hypotheses) in the candidate elimination algorithm. What does the algorithm do if H gives a false positive on some input example? What does the algorithm do if H gives a false negative?

Answer: If H in S gives a false positive, then it is deleted from S. If it gives a false negative on example E, then H is replaced by all minimal generalizations of H that include E.

### Problem 9:

(10 points) Describe briefly two ways in which texture can be used in vision systems.

Answer. (i) An abrupt change in the form of the texture can signal a change of surface. (ii) Variance in the size of textural elements are assumed to correspond to a change in the distance of the object. (iii) A change in a textural element that compresses it in one dimension, such as a change from a circle to an ellipse or from a square to a rectangle or parallelogram, can correspond to a change in the orientation of the surface from a head-on view to a sidelong view.