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