Artificial Intelligence: Problem Set 6

Assigned: April 11
Due: April 25

Problem 1

Note: This problem is open ended: that is, there is no single ``correct'' answer. You should discuss the problem in a paragraph or two. What I want to see is an intelligent discussion that concretely addresses the specific question asked.

The learning procedures we have discussed in class (with the arguable exception of AM) have all been passive , in the sense that the examples are supplied to the learner from the outside world. Another important category of learning is active learning, in which the learner can seek out examples to help him learn. For example, experimental science is a process of active learning; the experimenter sets up a circumstance where he wishes to make an observation that will help him improve his knowledge.

Suppose that a scientist are trying to determine the conditions that govern a particular feature of an object. He wishes to design a series of experiments that lead him to the correct rule governing the feature. Assume that actually carrying out an experiment is expensive compared to thinking or computation, so the scientist is willing to spend a good bit of thought or computer time in order to pick the experiments as well as possible.

A. Suppose that the learning algorithm being used, once the data is obtained, is the Candidate Elimination algorithm. How can an experiment be selected, at each stage, that will help refine the concept definition?

B. Suppose that the learning algorithm being used is a feed-forward back-propagation neural network. (In this case the ``rule'' being sought is just the correct state of the network.) How can an experiment be designed that will help push the network toward the correct definition?

(There is a discussion in the book of active learning (p. 607); this is a technical discussion of dealing with the tradeoff between performing actions to learn the environment and performing actions to further one's goals. I would like you to think more in terms of the purely learning issues, working on the assumption that the primary objective is to learn.)

Problem 2

Again, this is an open-ended problem.

The categorization problems that we have discussed have mostly been supervised learning; that is, the examples came labelled with their categories. Categorization may also be unsupervised, in which the learner must devise his own categories. For example, when a taxonomist studies animals, they do not come labelled by species, genus, family, etc.; these categories have to be invented.

Suppose that two competing programmers have each developed a program to create such a taxonomy of categories from a collection of data. Each programmer, of course, claims that his program gives better results than the other. How should such a claim be evaluated? That is, what makes one taxonomy better than another?

Problem 3

Consider a world of boxes and keys. A key may be inside a box or may be outside all the boxes. Boxes can be locked or unlocked. Certain keys fit certain boxes. There are four actions: Locking and unlocking a box, putting a key into a box, and taking a key out of a box. These are characterized as follows:

Consider the following planning problem:
Start: k1 fits b1, k2 fits b2, k1 is in b2, k2 is in b1, k3 and k4 are outside, b1 and b2 are unlocked.
Goal: b1 and b2 are locked. There is a key in b1. There is a key in b2.

Show how this planning problem can be compiled into SAT. In particular, enumerate all the forms of the fluents and of the axioms that you will need.