Analogical Reasoning in Problem Solving

David T. Chen* and Nicholas v. Findler Dept. of Computer Science, SUNY at Buffalo Amherst, N.Y. 14226

INTRODUCTION

Our ability to cope w1th the environment is the result of continual learninq from experience. Learning "makes sense" only because situations resemble each ot~er, and some information obtained in one situation is of use in others -- or, expressed more broadly, similar situations call for si~i­ lar actions. Ne also learn to extract the essential characteristic features of the situations '"e become familiar with, which then help us in retrieving the situations most similar to the one we are faced Hith.

S1mr!ar1ty can be of different types and at different levels of complexity. Its discovery is often the result of a goal oriented process associated '"ith problem solving activity. Once similarity bet\'leen a problem with a knm·m nolution and an un­ solved problem has been recognized, Ana­ logical Reasoning {AR) is normally called into action by humans to generate possible solutions to be tested then for adequa~'·

We have attempted to investigate N1 de­ tached from specific tasks and to formulate its general principles. Our objective has been to create an AR component for problem solving programs and to assume for it the level of generality the means-ends analysis was shown to have in GPS.

WORKINc; HYPOTHESES OF NlAr.or:ICAL J'IEASOHINf~ The underly1ng rationaie of Xh can be expressed by a few working hypotheses:

{i) Each problem is describable as an {ordered) collection of, possibly overlap­ ping, features. {A feature represents one or several chunked properties. ~mereas properties are atomic and directly mea­ surable, features can in general be mea­ sured as present or absent only.) The identification and extraction of features are, however, left either to a program component external to AR or to the user.

{ii) Solutions are associated with re­ spective problems in a well-defined, de­ terministic manner. This assumption goes beyond the usual concept of causality. It requires that the features be identifiable and strongly enough correlated with the solutions so that the latter can be derived directly from the former.

{iii) In the task domains of interest to us, similar problems have similar solu­ tions. {Similarity must be measured along certain dimensions that depend on a priori features of both problems and solutions.)

{iv) When t\'TO problems have similar so­ lutions, the features present in one pro­ blem but not in the other are likely to be of lesser importance. In turn, features shared by problems which have similar so­ lutions are likely to be important. These can be strengthened quantitatively: the

*Now at the Dept. of ~omp. Sc1ence, Univ. of Missouri, Co1Ul"h.i.2., ~ !0 6520 1

more problems, which have similar solu­ tions, share a feature the more important it is likely to be. Also, the more fea­ tures are shared by two problems the more similar their solutions will be.

THE CONTRIBUTIVE AND HIERARCHICAL HODELS

A decision must be made as to what In­ formation should be extracted from "raw" experience with problems and solutions, and how this information should be used in det­ termining solutions to new problems. In the contributive model, the features of a problem are assoc1ated with the appropriate solution steps or segments. The frequency of prior usage of a solution segment for problems \'Tith a given feature provides a heuristic guide in selecting and ordering for testing that solution segment for a new problem possessing the same feature.

The hierarchical model also considers the relevance of ind1v1dual features. The so­ lution segments offered for testing are selected in an order based on matching with a set of features hierarchically structured in the knowledge base. The learning pro­ cess here not only enters new information about problems, their features and sequence of solution seqments, as above, but it may also rearrange the feature hierarchy.

We feel some combination of the above two models can deal also with high order simi­ larities -- such as theorems of duality, structural, semantic, functional and the­ matic similarities if sophisticated feature extraction programs can be employed in cooperation Nith the AR component.

PROGRA!UlED EXPLORATIONS

First, He carr1ed out a few preliminary experiements with simple tasks. These in­ cluded the contributive model for the "simulation" of some piece-'"ise smooth functions and the hierarchical model for several concent formation tasks.

Ne have then implemented a simplified system consisting of three main components: The first orqanizes and coordinates the logic of problem solvinq and is responsible for sub-problem generation. The second is the task-independent AR component offering recomnendations to the previous one. Fi­ nally, a data base separate from the rest contains the task domain description, the procedures to interpret the semantics of the definitions used, and a list of all possible features. This system was used for two areas sufficiently disjoint for generality consinderations but having identical machine representation of problem constituents -- theorem proving and con­

struction tasks in plane geometry.

The objective was to prove that AR works with non-trivial problems rather than to compete with previous impressive accom­ plishments in the above areas. We ,.,ere also able to show that the knowledge ac­ quisition system is both effective and ef­ ficient. New concepts, such as circle, can be introduced on-line, in a high-level manner. The system is flexible, open ended

and capable of accepting extensions.