A training example with a desired evaluation measure of 1 is considered a ``perfect" example of an object from a given category. Perfect training examples are desirable in the training set because all primitive measurements for perfect examples are known to fall in the range [n1,n2]. For example, if a conventional chair training example has a desired evaluation measure of 1, then we know that all of the membership functions in its proof tree (see Figure 4) must return values of 1. This is because the result of the PAND function can be no greater than the minimum input.
OMLET now examines the set of desired points that have been propagated to each range in the definition tree and determines ``limit" points. These are defined as follows. If any two desired points have y values (memberships) of 1, then at least a segment of the normal range [n1,n2] is known. The n1 range parameter is set to the minimum x value of all desired points with y values of 1. Similarly, the n2 parameter is set to the maximum x value of all desired points with y values of 1. Note that if only one such desired point is found then n1 and n2 are set to the same value, and the membership function is initially triangular. Since some portion of the normal range is known to be correct, an upper limit is set on the n1 value and a lower limit is set on the n2 value to assure that the known segment of the normal range is not reduced during subsequent training. Since training examples have desired membership values greater than 0, we know that all x input values must lie between z1 and z2. OMLET uses the minimum and maximum x values from the set of desired points to set limits on the z1 and z2 range parameters. The z1 range parameter is never permitted to increase above the minimum x value during training. Similarly, the z2 value may never decrease below the maximum x value in the set of desired points. Figure 7 shows the range parameters (limit points) OMLET sets during the initialization phase given a set of 10 examples.
Figure 7: Range parameter limits that may be set when
initializing range parameters.
The limits on the range parameters serve several purposes. First, the limits assure that perfect training examples will not be assigned evaluation measures less than 1, and that all training examples will have evaluation measures greater than 0. More importantly, by limiting the changes that can be made to some range parameters, better approximations to the desired membership functions can be learned. In subsequent learning, the error is propagated down the proof tree with the assumption that equal amounts of the error come from each input to a node. This assumption is not always valid, and there is no way to directly determine the portion of the error that belongs to each input. If an error propagated to a membership function would cause a change in one or more of the range parameters (z1,n1,n2,z2) that moves the parameter past its set limit, the portion of the overall error assumed to be caused by the membership function has not been correctly estimated. When this occurs the parameter is set equal to its limit, effectively reducing the degree to which changes in the membership function would compensate for the overall error. This should allow the learning algorithm to find a good solution in the case where different membership functions contribute different amounts of error.
If a segment of the normal range is known for some membership function, then initialization of the range parameters is straight-forward. The n1 and n2 values will have already been set. The z1 value is set simply by making the left leg of the trapezoid pass through the point (n1,1.0) and the point from the set of desired points with the minimum x value. Similarly, the z2 value is set by making the right leg of the trapezoid pass through the point (n2,1.0) and the desired point with the maximum x value. If there are no points to the left (right) of the n1 (n2) point, then the membership function is assumed to be one-legged (as for CONTIGUOUS SURFACE in Figure 4) and the parameters n1 and z1 (n2 and z2) are extended to a very large negative (positive) value and not permitted to change during training.
If no portion of the normal range of a membership function can be determined, then we attempt to fit a trapezoid to the set of desired points. First, the two desired points with the maximum y values are found. We assume that the normal range lies somewhere between them. A best-fit trapezoid is determined by varying the n1 and n2 range parameters over the assumed normal range, and selecting the normal range [n1,n2] that produces the lowest error for the set of desired points. The error is the sum of the absolute values of the difference between the desired y value and the actual y value found for each point. The z1 (z2) range parameter is set in the same manner as before, where the left (right) trapezoid leg is forced to pass through the desired point with the minimum (maximum) x value. The n1 value is varied from the leftmost point of the assumed normal range to the rightmost point in small increments. For each different value of n1, the n2 value is varied from n1 to the rightmost point of the assumed normal range in small increments. So, we are simply testing a range of possible trapezoids (with the degree of accuracy, and number of trapezoids tested, defined by the increments in which n1 and n2 are varied) that have a normal range [n1,n2] somewhere within the assumed normal range. From these we select the set of range parameters that minimize the total error over the set of training examples. The use of a best-fit trapezoid approach is helpful, because we have no initial way to accurately associate error with any given trapezoid.