Comp.Exam.  Artificial Intelligence  Fall 1995

Answer one of the first two questions, and all the remaining questions.

1. Two astronomers make measurements M_{1} and M_{2} of the number of stars N in some small region of the sky, using their telescopes. Each telescope can be out of focus (events F_{1} and F_{2}), leading to errors in counting. A final conclusion about N′, the number of stars, needs to be made based on the astronomers’ measurements. Construct a belief network or probabilistic inference network relating M_{1}, M_{2}, N, N′, F_{1} and F_{2}. A priori, P (N = 1) = P (N = 2) = 2 ∗ P (N = 0) = 2 ∗ P (N = 3). The probability that a telescope is out of focus is 0.2. If a telescope is out of focus, the resulting measurement may be 0,1,2 or 3 with equal probability. If a telescope is not out of focus, we can expect the resulting measurement to be accurate. If M_{1} = 1 and M_{2} = 3, what is the most likely number of stars (N)? Give clear reasons for your answer. State all simplifying assumptions.

2. Regions in a bitmap image are painted using the three patterns below:

010  111  101
010  111  010
010  111  101

The first pattern consists of a single vertical line of 1’s, the second pattern is filled with 1’s, and third consists of alternating 1’s and 0’s. The size of a region painted with a pattern may be arbitrarily large. The following is an example of such an image containing each of these four patterns:

000000000111
000000000111
000000000111
101000000111
010000010000
101000010000
000000010000
000000010000
000000010000

Design a neural network to identify the presence of such patterns in an image.

3. Animals can outrun any animals that they eat. Carnivores eat other animals. Outrunning is transitive. Outrunning is antisymmetric. Lions eat zebras. Zebras outrun dogs. Dogs are carnivores. Dogs eat zebras.

Translate the above statements into first order logic, and use resolution to show that zebras eat lions. A formal proof is expected.

4. Construct an augmented transition network for a library information retrieval system in which users ask (in English) for information about books on various subjects, by various authors, and with various titles. Each user query may contain a subject phrase, title, and/or author names.

5. What is the Hough transform? Where is it useful? Describe an algorithm that uses the Hough transform.

6. (a) How does search in A.I. differ from non-A.I. search techniques?

(b) How may planning be viewed as a state-space search problem? Identify the state space, initial and final goal states, move set, and “intelligent” search methodology.

7. Describe the version space approach to concept learning. What is the scope of applicability of this approach?