A Learning System Which Accommodates Feature Interactions

1. INTRODUCTION

The evaluation function has frequent­ ly been used ·as a heuristic in what is called best-first search [1,2,4,9]. A standard technique is to combine several more elementary functions or features. As argued in [ 3], forming a heuristic func­ tion from a set of features is theoreti­ cally as powerful as any other design. The problem though is to merge features usefully. Often the linear combination H = b.f is imposed, where b is the coef­ ficient vector for the feature vector f, though this is generally insufficient [1,9]. Even with this restrictive formulation, ~is difficult to optimize.

The optimization should be governed by some performance measure (such as num­ ber of states generated to reach the goal) but often no solution whatever can be found within resource constraints. Despite this impediment, some approaches have been very effective, e.g. [9]. In [8] the present author described a successful new basis for learning. The system implemen­ ted was able not only to solve the fifteen puzzle, but also to optimize feature coefficients for linear evaluation func­ tions, a unique result. Since the scheme has good conceptual and experimental support, work is underway to improve it. One extension is to increase accuracy [7]; another is to accommodate feature inter­ actions, to allow more general evaluation. The latter uses a natural piecewise linear method outlined in [6], and developed, implemented and tested here.

2. KNOWLEDGE STRUCTURE

Like other recent approaches [10], a penetrance learning system (PLS) uses completed searches of training problems. Unlike them, it computes statistics mea­ suring solution density in feature space (Fig. 1). Although it is data driven, PLS is insensitive to noise since it is sto­ chastic. The raw statistics, which depend on the problem instance set P attempted and heuristic H guiding the search, are called elementary penetrances p(r, H, p), where r is a (rectangular) feature space volume. From these data, a normalized true penetrance estimate a<r) is computed. This value is the estimated probability of a state A being in a breadth first solu­ tion of a random problem instance, given that A maps into r. Derived from repeated observations and incremental computations, the evolving evaluation function H is designed to predict true penetrance.

To house the true penetrance estimate p of a feature space volume r, a region R is defined to be the quintuple (r, c, p, e, b). The second element cis the centroid,-a representative of r. The final two elements relate to p: e is the error, an inverse measure of the rel1ability of p, and b is a coefficient vector, explained later.- A set of these regions, the cumulative region set C, is both the control structure use-d--by the problem solver and the knowledge structure improved by the learning element (Fig. 2). This set accumulatates information over several iterations, as its regions are incrementally resolved into smaller units just adequate to express known relation­ ships. The result is an effective economy, a refinement of Samuel's [9] signature tables which did not alter data categories automatically.

3. LEARNING ELEMENT MECHANISMS

While [8] gives considerable detail of the original implementation PLS1, the main notions are summarized here to motivate further development. The incremental three step operation is pictured in Fig. 2. First, given some training problems and evaluation function, the solver extracts penetrance statistics from -----rhe- resulting search t1·ees. Secondly, the clusterer modifies the cumulative region set based on these penetrance measures. Finally, the new cumulative region set becomes data for the ~esse~, a curve fitting algorithm which generates an improved heuristic for the next iteration. Together the clusterer and regresser form the learning element.

The clusterer is complex. New regions are formed when penetrance data are found to diverge within any existing region R. This region refinement is realized by an efficient algorithm that repeatedly splits rectangles, until further differentiation is not warranted by the recent data. In any iteration after the first, these elementary penetrances are heavily biased by the heuristic used to obtain them, so a fine normalization procedure unbiases values within R. Thus, penetrances for newly split rectangles become commensurate with the true penetrance estimates of the cumulative regi ons . Region refinement is repeated i n every iteration, so that knowledge is increasingly resolved.

A separate coarse normalization algorithm operating over the whole feature space obtains fresh true penetrance esti­ mates for established regions. This algo­ rithm assumes a pattern in the biased data. It smooths the true penetrance esti­ mates of all established regions against the new elementary values within matching feature space rectangles to find a conver­ sion factor to apply to all elementary penetrances. After normalization, these new values are averaged with the old to improve estimates. In this pen etrance revision, weights for the averaging depend on the accuracy of each datum. Tbe end result is decreased error in the combina­ tion, so that cumulative true penetrances gradually become more inert (although region refinement counters this trend).

All this manipulation by the cluster­ er is designed to provide proper data to fit true penetrance as a function of features for the solver's heuristic. Each region R = (r, c, p, e, b) in the c umula­ tive set C has-an undefTned feature coef­ ficient vector~ after clustering, but the regresser (Fig. 2) determines b from C. (The contribution of each R is inversely related to its erior e.) The regresser rejects any useless or less general features by zeroing their coefficients and decides the relative importance of th~ discriminating features by setting their coefficients to values best suiting C. The next section will describe how b now becomes a property of R, to accommodate feature interactions.

4. PIECEWISE LINEARITY

This method takes advantage of the natural partitioning of the feature space into regions (c.f. [1, p.430], [5, p.317]) and allows increasing departure from linearity as the refinement improves in later iterations (as the number of regions increases). In this extension of PLS1, the clusterer remains unchanged while the regresser is altered.

Instead of a single penetrance-fea­ ture surface fitted over the whole space, there are now as many of these hyperplanes as regions in the cumulative set C. Each region R = (r, ~' P, e, ~r) of C is viewed as the principal one for its own regression; the coefficient vector br is computed using an R-eentered weighting of every contributing region Q E C. As mentioned in the previous section, the ~egression is already weighted according to penetrance error e. In this new, piecewise linear design PLS1a, the former weight is multiplied by an additional factor r~lated to the distance between R and Q, so that Q plays a greater role if it is near R. In the determination of this distance, the feature space is deformed to capture the relative importance of the various features. (Details of this and related aspects are provided in the appendix.)

Since each regression is still linear, the process is quite stable. (In contrast, permitting feature interaction by using higher order models requires many m'ore co effie ients and this 'uses up' the data.) At the same time the piecewise linear scheme PLS1a is . flexible, allowing a continuously variable amount of nonlinearity in order to suit the current power of the entire learning system. This variability is mechanized by introducting a system parameter called the localization power L ~ 0 as an exponent for the OIStance measure (again, refer to the appendix).

To test the utility of this more sophisticated learning element, the solver was altered so that two new modes of evaluation can be selected. The first, discrete piecewise linear procedure simply predicts the true penetrance of a state A according to the local heuristic function of the region into which A maps. The more complex evaluation mode, smooth piecewise linear, uses all regions in the cumulative set 1n every evaluation, employing a distance weighting like the one above.

Prelimarary program runs have been made to discover characteristics of the scheme: its utility, cost, and stability. The cumulative region set used was a four dimensional one for the fifteen puzzle

[8]. Since these four features were originally used in the strictly linear system, they had been deliberately selected for low interaction . Hence this is a mild test of PLS1a. In the solver, the cost increase of discrete piecewise linear evaluation over the strictly linear PLS1 mode is negligible, but edge effects (discontinuities) vitiate the scheme; performance is very poor. On the other hand, smooth piecewise linearity seems promising; its cost is also low. Results are shown in Fig. 3, where the extent o f nonlinearity is varied by choice of the localization power L. In this curve the optimum is attributed to two conflicting factors: As L is increased some advantage occurs because the relationships are inherently nonlinear, and nearby regions now play a justifiably bigger part in the determination of each local heuristic. However, distant regions, which formerly had a stabilizing role, now have a diminished influence, so there is a general loss of support. The inaccuracy and graininess of individual regions gradually overpower the benefit of localization.

An important property of PLS1a is its stability. When PLS1 was used with higher order models instead of piecewise linearity, performance was degraded. Also in contrast, PLS1a allows easy observation of the relative importance of features in any area of the space, since simple feature weighting is used. Furthermore, relationships exemplified by Fig. 3 are useful. The magnitude of the optimal localization power is a measure of region accuracy, and indirectly, of the utility of the entire learning system.

5. CONCLUSIONS

The piecewise linear scheme PLS1a is natural, flexible and stable. Its low cost and performance improvement warrant fur­ ther investigation. The next step is to attempt stronger feature interaction, with support from a scheme designed to improve the accuracy of true penetrance estimates [7]. The freedom to vary the localization power L will facilitate experimentation in determining the general utility o f PLS1a as a heuristic learning system.