• defining an n dimensional space;
• defining the concept within this space;
• presenting the learner a sequence of positive and negative examples; and
• testing to determine whether the learner had acquired the concept definition.

   This approach can be illustrated by defining a concept space that involves 4 dimensions, each of which has two values. The dimensions or attributes for this example are:

• Shape: Square(sq) or Circle(¬sq);
• Size: Large(l) or Small(¬l);
• Color: White(w) or Black(¬w);
• Position of Shape on Field: Right(r) or Left(¬r);

where the letters in parentheses indicate the abbreviation that will be used in the figures when the the concept instance is described. The concept instance is described as a conjunction of propositions. Note that with 4 dimensions each of which can take on one of two values there are 2 to the 4th or 16 possible concept instances. This space of possible instances is shown below.

   Consider the example shown to the right. Assume that this example is an instance of the concept that is to be learned. In this example a white small square is shown on the left of the field. The description of this example as a conjunctive description is shown beneath the figure. If this is the only instance, that is the concept is exactly this conjunction of features, then all of the other possibilities lie in the other element of the partition. If the concept is 'white and square', then the space is partitioned into two sets of 4 and 12 elements.

   In order to gain some experience with this type of task, there are two different examples of a concept identification experiment provided below. For each of them, the examples are presented using a QuickTime movie. The controller for the movie is displayed at the bottom of the player. Clicking on the arrow on the left will play the movie. Clicking again will pause the movie. On the right of the controller are two arrows, one pointing left and one pointing right. Clicking once on one of these arrows steps the movie either forward or backward. The movie immediately below simply presents each of the 16 possible examples. Use the controller to play this movie to familiarize yourself with the controller functions. Note that if you click on the down arrow on the right, a menu will appear. One option on the menu is called Plug-In Settings. If you select this menu item you can then set the Plug-In so that the movies are not played automatically when the page is loaded. This is the best option for carrying out these experiments.

• Your concept hypothesis that you believed when the example was presented.
• Your prediction from your current hypothesis whether the example is a positive or negative example of the concept.
• Notation indicating whether your prediction was correct or incorrect.
• And, if your concept hypothesis is changed then the new hypothesis should be written down.

   Do not look back at any of the earlier examples. Always moved forward in the movie event if you are confused.

Do this for each of the examples in Experiment 1 below.

    Now we will analyze your concept learning protocols. For each experiment:

• First check whether you revised your hypotheses whenever it yielded an incorrect prediction. Indicate any points where you failed to do this.
• Next, starting with your first hypothesis, work backward and determine whether it correctly categorized all of the examples that preceded it. If so, mark a C next to it; if not mark an I next to it. Do this for all revisions of you hypothesis. Note, if your final hypothesis is marked C then you have learned a "correct" definition of the concept (or at least a definition that is consistent with the examples provided.).
• Finally, summarize the analysis by counting up the number of hypotheses considered during the experiment.

You will be asked to hand in the analyzed protocols. There are some further questions below, but these are "thought" questions and you needn't hand in your answers.

     For Experiment 1 the conjunctive concept black and large(¬w and l) is consistent with this training set. Note that this is a concept that can be represented by what your text refers to as a monomial; that is, a conjunction of literals. You may have noticed that in this experiment you were shown only positive examples of the concept. What kind of learning strategy is required to learn from positive examples only? Is the hypothesis that the concept is given by the rule (¬w and l) the only hypothesis consistent with this training set?

     Did you identify the concept for the second experiment? Was there any point prior to the last example where you could be absolutely certain that you had learned the correct concept? If you found this concept hard to learn it may help you to know that the rule can not be expressed as a monomial.

     Most of us don't recognize the enormous number of possible hypotheses that can be considered even in simple concept space such as the one used here. Click on Possible Hypotheses below to see some hypotheses that could have been considered after a single example. Did you consider more than one of these at the time?

     One of the important issues in research on concept learning is hypothesis revision. That is, when a hypothesis becomes inconsistent with the training instance, then how does the learner revise the hypothesis so that it is consistent with the training set that has been presented? It is because the space of possible revisions is usually very large that this is an important issue. If the revisions can be enumerated, then a breadth first search over the space of hypothesis is possible in principle. However, when the space is very large, this solution is not practical. And, if the wrong hypothesis is chosen at some point the learner may find it difficult or impossible to recover from the error. The page Structuring the Hypothesis Space begins to develop some of the ideas that have been used to address the problem of hypothesis revision.