In this section, we describe the OMLET learning (sub)system. OMLET learns fuzzy membership functions, which are located at the leaves of an AND/OR categorization tree, from sets of training examples. OMLET works together with GRUFF to automatically learn object category definitions and use those definitions to recognize new objects.
In the training mode, OMLET uses examples to learn the fuzzy ranges for primitive measurements. Each training example consists of an object description coupled with a desired overall evaluation measure. In the testing mode, OMLET uses the previously learned ranges to act as a function-based object recognition system. Knowledge primitives form the building blocks of the OMLET system, and rules make up the representation language. The rules, which are fixed, are derived from GRUFF'S category definition tree. They indicate 1) how the knowledge primitives are combined to define functional properties, and 2) how the functional properties are combined to give the function-based definition of an object category.
Given a training example, OMLET uses the rules to construct a general proof tree for the example's given object category. The proof tree is simply a data structure that mimics the way GRUFF combines primitive evaluation measures. The proof tree also maintains the primitive ranges that are modified by the learning algorithm. An example proof tree generated from the rules that define an object in the conventional chair category is shown in Figure 4. The proof trees contain only those knowledge primitives which are defined using range parameters. This is because the other knowledge primitives return only 0/1 measures, and so there is no primitive membership function to learn. The training example must satisfy these ``binary", or necessary, functional properties and return evaluation measures of 1 in order for the example to be a member of the given category. For example, in Figure 4, the left branch of the top PAND node represents the functional property provides_stable_support. This functional property is defined by a single knowledge primitive which has no range parameters. Therefore, this input to the PAND node is fixed to always return a 1.
Figure 4: The simplified proof tree constructed for a learning
example from the category conventional chair. The ?a, ?b, and ?c symbols
in the rules represent the physical aspects of a shape that
are used by the rules. An orientation of the shape,
the face of the sittable surface, and the front edge of the sittable surface
are substituted for ?a, ?b, and ?c, respectively. This way OMLET knows
which elements of a shape are to be ``measured" and evaluated by the
knowledge primitives.
For OMLET to obtain an overall evaluation measure for an example object, the physical measurements of the shape elements of the object are input to the primitive fuzzy membership functions in the leaves of the proof tree. The output at a leaf node represents the evaluation measure for the individual functional property. The evaluation measures are combined at the internal nodes of the tree using the probabilistic T-norm/T-conorm combiners described in Section 2.3. The overall evaluation measure of the input example is then output at the root node (see Figure 4).
Figure 5: Training goal input to OMLET for a
conventional chair object.
Input to OMLET consists of a set of goals for specific examples from object (sub)categories. The goal includes the example's (sub)category, the elements of the 3-D shape that fulfill the functional properties, and an overall desired evaluation measure which is greater than 0 (otherwise the object is not an example of the object category). Figure 5 shows an example of a goal for a conventional chair object.
Using the training examples, OMLET attempts to learn the ranges used in the trapezoidal membership functions associated with the knowledge primitive definitions (see Figure 2). When a training example is presented, OMLET attempts to prove via the rule base that the object is a member of the specified category. Here, the check is to make sure the physical elements of the object listed in the goal satisfy the binary, or necessary, functional properties. So, for a conventional chair training example, OMLET checks that the given orientation is stable, and the given seating surface is accessible (clearance in front and above) and meets a minimum width to depth ratio. If the necessary functional properties have all been satisfied, a proof tree is constructed. The actual overall evaluation measure is then calculated in the manner described above. If the actual evaluation measure is sufficiently different from the desired evaluation measure, then the primitive fuzzy membership functions that were included in the definition need to be adjusted.
Primitive membership functions are adjusted by propagating the overall error for each training sample down through the nodes of the proof tree in a way that attempts to give each leaf node (i.e., range) some portion of the error. The range parameters (z1, n1, n2, and z2) that define the fuzzy membership trapezoids are then adjusted in an attempt to reduce the total error of the examples in the training set. The next few subsections provide details of the OMLET learning algorithm. First, we discuss the method for calculating an error value and propagating it down through the proof tree. Next, we present a method for making initial estimates of the parameters for each membership function. We describe error propagation first because it is utilized in the initialization phase. We then describe how OMLET makes adjustments to the membership functions in an attempt to reduce the error over the entire training set. The last subsection describes the general learning paradigm and provides some theoretical justification for our implementation.