|
|
|
|
|
|
|
Now our objective is to designate subsets of  which have attributes in common. To do this let the symbol " " indicate that we "don't care" what attribute occurs at a given position (i.e., for a given detector). Thus  designates the subset of all elements in having the attribute  . (Equivalently, (v13, , . . . . , ) designates the set of all l-tuples in beginning with the symbol v13; hence, for l = 3, (v13, v22, v32) and (v13, v21, v31) belong to  , but (v12, v22, v32) does not.) The set of all l-tuples involving combinations of "don't cares" and attributes is given by the augmented product set  Then any l-tuple  designates a subset of as follows:  belongs to the subset if and only if (i) whenever  , any attribute from Vj may occur at the jth position of A, and (ii) whenever DijÎ Vj, the attribute Dij must occur at the jth position of A. (For example, (v11, v21, v31, v43) and (v13, v21, v32, v43) belong to  but (v11, v21, v31, v42) does not.) The set of l-tuples belonging to X will be called the set of schemata; X amounts to a decomposition of into a large number of subsets based on the representation in terms of the l detectors  . |
|
|
|
|
|
|
|
|
Schemata provide a basis for associating combinations of attributes with potential for improving current performance. To see this, let "improvement" be defined as any increment in the average performance over past history. That is, if  is the performance of the structure  tried at time t, the object is to discover ways of incrementing |
|
|
|
|
|
|
|
|
(A more sophisticated measure would give more weight to recent history, using |
|
|
|
|
|
|
|
|
but the simple average suffices for the present discussion.) Though  can be incremented by simply repeating the structure yielding the best performance up to time T this does not yield new information. Hence the object is to find new structures which have a high probability of incrementing significantly. An adaptive plan can use schemata to this end as follows: Let  have a probability P(A) of being tried by the plan t at time T + 1. That is, t induces a probability distribution P over and, under this distribution, becomes a sample space. The performance measure µ then becomes a random variable over , being tried with probability P(A) and yielding payoff µ(A). More importantly, any schema  designates an event on the sample space . Thus, the restriction µ | x of µ to |
|
|
|
|
|
