Constrained Example Generation: A Testbed for Studying Issues in Learning

CONSTRAINED EXAMPLE GENERATION: A TESTBED FOR STUDYING

ISSUES IN LEARNING

Edwina L. Rissland·

Elliot M. Soloway··

University of Massachusetts Amherst, MA 01003

We have explored the robustness of this model, and its LISP realization, in such domains as: generating specific atoms and lists in LISP, generating simple recursive programs in LISP, generating lines in algebra, generating scenes in a simple blocks world, and generating tactics in a game [5)[11). Effectively, the same system was used in each domain; only the domain specific knowledge was changed. The core system operates in a GPS-like fashion, applying a set of difference-detectors and a set of difference-reducers in order to modify examples to meet the desired constraints. Thus, in this work, the system could undertake remedial modifications since it "knew what to do".

ABSTRACT

In this paper we explore issues in learning such as the role of agenda mechanisms, noticers, history keepers, initial seed sets of knowledge, and problem sequences in the context of our Constrained Exampled Generation (CEG) system working problems in the mini-domain of linear functions.

1, INTRODUCTION

In past work, we have investigated the structure of knowledge in complex domains like mathematics and computer science [3)[4)[7) in particular the important role played by examples and the process of generating examples that meet specified properties or constraints [2)[5)[6). We have built a computational model of the process of constrained example generation which was motivated in part by our observations of human subjects.

The basic idea behind the CEG system is as follows: given the goal of producing an entity with certain properties, instead of generating the entity from first principles, find an example in the data base which "most closely" matches the desired constraints, and then apply difference-reducing operators in order to modify that example to fit the given constraints. The architecture of the CEG system is given in Fig.

1.

·This work supported, in part, by the National Science Foundation under grant IST-80-17343.

··This work was also supported, in part, by the Army Research Institute for the Behavioral and Social Sciences, under ARI Grant No. MDA903-80-C-0508.

Any opinions, findings, recommendations expressed in those of the authors, and do conclusions or this report are not necessarily

reflect the views of the U.S. Government.

Currently, we are investigating learning. To learn, a system must acquire experience and be able to review and summarize it [8)[9]. The design of the CEG system has the necessary modules to allow it to do so; in particular, the JUDGE, AGENDA-KEEPER, HISTORY-KEEPER, and NOTICER/GENERALIZF.R can be used to allow the system to monitor its own performance, and provide feedback, which as noted by Smith et al [10] is critical to learning.

Architecture of the CEG System. (Dashes indicate that module is not yet fully perational.)

The specific task we have set for the l earning-CEG system is to learn under which c i rcumstances a particular reducer is appropriate. Neves [1) explored a similar problem. This task allows us to explore the space of factors involved in learning:

1. The role of agenda mechanisms
2. The role of history-taking and -summarization
3. The role of initial "seed" sets of examples
4. The role of posed problems, their content and order.

The CEG system provides a vehicle in which to empirically explore the tradeoffs and i nteractions of these factors. The contribution of each of these components is a "parameter" t o t he current system. We are in the process of systematically testing various settings of these parameters.

For example, learning the appropriateness of an action implies learning something about t he order in which to apply it. This is particularly important in the case of i nteracting constraints where remediation of one constraint deficiency might destroy satisfaction of another constraint.

The agenda mechanism also affects the ex pl oration of sequences of actions and modified examples. For instance, if a particular modificat i on routine has just made the candidate ex ample "better" ·, e.g., closer to meeting a constra i nt, should it be tried again, and if so, fo r how many times? On the other hand, should other routines be given an opportunity to demonstrate their effects? The latter technique would lead to discovering routines which are a mi xed sequence of actions, whereas the former technique would lead to discovering routines composed of multiple copies of the same actions.

2. AN EXAMPLE FROM THE LINES DOMAIN

The domain chosen for our investigations is t hat of linear functions on the real numbers, i. e ., lines l i ke y = 2x + 1. A typical CEG problem might be to generate a line such that:

1. it is steeper than a given line, and
2. it ha s a negative slope.

Fo r a general line, ay = bx + c, steepness is t he absolute value of the slope, i.e . , :bla : . The sign of the slope is the sign of (b/ a).

The CEG system has an initial data base of ex ampl e , i.e. , an "Examples Space." An example is a spe ci fi c line, ay = bx + c, represented as a frame, whose value slot contains the three-tuple (a b c). Other slots include "de rived-from" pointers indicating from which othe r example the example is constructed, and scoring and history information gathered during att empted modifications.

The "goodness" of a modification is measured by the JUDGE module and expressed in terms of two scores: ( 1) the "global esc" (constraint satisfaction count) which measures the example's satisfaction of all posed constraints; (2) the "local esc" which measures its satisfaction of the constraint currently being worked on. The scores are expressed disc retely as "success", "better", "no-change", or "worse".

The system possesses five "primitive" routines that modify the x-coefficient :

1. make-steeper1 (ms1) which adds 1 to the x-coefficient;
2. make-steeper2 (ms2) which doubles the x-coefficient;
3. make-steeper3 (ms3) which squares the x-coefficient.
4. make-steeper4 (ms4) which subtracts from the x-coefficient;
5. make-negative (mn) which changes the sign of the x-coefficient.

Thus, there are four routines that modify the steepness and one that modifies the s i gn of the slope. The system starts out "knowing" that ms1, ms2, ms3 and ms4 affect the steepness and thus, implicitly that steepness has something t o do with the x-coefficient of a line. It does not know of the role of the y-coefficient .

Some speci fie "facts" we wish to have the system acquire are:

1. ms2 (doubling) always works;
2. ms1 (add1) works for slopes > 0;
3. ms3 (squaring) works where :slope: > 1.
4. ms3 is "faster" than ms2 which is "faster" than ms1.
5. it is better to fix the steepness before the sign.

3. EXPERIMENTS AND RESULTS

Thus far, our experiments have involved variation of the following:

1. The agenda mechanism, the search of modi fie at ions; in particular, sequences of
2. the scoring of problems, in particular, which sequences count as "successes", "better", etc.;
3. The initial seed set possessed by the system ; of examples

1. The order of problems posed to the system;
2. The "remembering" examples created the addition of examples to "Examples-space". and "forgetting" of by the system, e.g., succ,ssfuJ solut ion the system' s

A sample of the observations made on our experiments are:

1. Selection of operators: Random selection (which allows the system to try the powerful ms3 routine more often) does in fact perform better than the regime that does not vary from the initial choice of operator. However, the sequences of operators obtained under random selection are effectively "impossible" to analyze, even by humans. Thus the style of the AGENDA-KEEPER influences the credit assignment task of the NOTICER/GENERALIZER.
2. Influence of Initial Knowledge Base. The initial seed set of examples should include a variety of examples, for instance, some likely-to-cause-trouble examples like y=2, some nicely-behaved examples like y=2x. The variety affects what is accessible t o discovery; for instance, without lines with :slope: < 1, the system would never learn ms3's weakness, and without lines with negative slopes, ms4's strengths. There is a trade-off between the variety of the knowledge base and the complexity of the agenda mechanism: the system didn't need a highly tuned AGENDA-KEEPER if the KB contained variety. This is related t o mesa and false peak problems in hill-climbing.
3. Tuning the data-base. The "goodness" or---certain examples (leading to successes), like y=2x, and the "troublesome-ness" of others (leading to worse-es), like y:2, became readily apparent.
4. Remembering/forgetting. exercise and learning don't save answers. To force of abilities,
5. Persistence. Don't give up evaluat ing even if the situation looks l ocally worse. For instance, one agenda mechanism stops the modifi cati on attempts at the first encountered "local worse; it never led to evaluati ons that might have showed that ms 1 f,nd ms 4 tried in sequence lead t o gl obal no-change: which could lead t o discovery of their relation as inverses.

In summary, we are using CEG to systematically expl ore alternative work-loads, influences, and contributions of modules in a learning sys tem. We feel strongly that an empirical testbed i s necessary for the understanding of AI systems which evolve in complex ways. There i s a difference between making a system perfo rm better and learning how it can l earn to pe rfo rm better. While expert system research o ft. en emphasizes the former, we feel it can benefit from study o f the latter, whi ch is our focu s .