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.

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.)


p(X) :- p(X).

?- p(a).

Problem 6:


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.