An Examination of the Third Stage in the Analogy Process: Verification-based Analogical Learning

An Examination of the Third Stage in the Analogy Process: Verification-Based Analogical Learning 1

Brian Falkenhainer Qualitative Reasoning Group Department of Computer Science University of Illinois at Urbana-Champaign 1304 W. Springfield Avenue, Urbana, Illinois 61801

Acceu: The access stage has two purposes. First , it locates a body of prior knowledge (the ba~e) which may be analogous to the current situation (the target) . Second, it should garner out those features of the base which are pertinent to the analogy.

Mapping: The mapping stage consists of finding similarities between the base and target (matching), and possibly transferring addi­ tional knowledge from the baae to the target (inference) . The work presented in thi.a paper draws from Gentner's (1983) Struc­ ture-Mapping theory of analogy and uses a simulation of these principles, the Structure-Mapping Engine (SME) (Falkenhainer, et al, 1986). Mappings conatructed by SME consist of the set of bue/target correspondences and a potentially empty set of ana­ logical inference~ - relations that augment the target description by traneferring knowledge from the base. SME i.e guided by a set of match con1tructor rule. that specify what items may plausibly match, providing a useful programability option.

Evaluation and Use: Once the correspondences have been found, the quality of the match and its consistency with general domain knowledge should be evaluated before using the proposed anal­ ogy. The uaes for analogy are di.acussed in the following section.

2.1 U1lng an Analogy

Analogy matchu a base description with a target description of varying levels of completenesa. When the target i.e complete, analogy indicates where the correapondences are and has no predictive power. When the target lacks certain relations, analogical inference may occur; relations which hold in the base but are not known to hold in the target are mapped into the target domain. Borrowing from lndurkhya (1985) , we may formally define two types of analogical inference:

Definition: A set of analogical inferences are drongly coherent if every aentence being mapped i.e logically entailed by the target. The inferences are weakly coherent if they are merely consistent with the target, rather than entajled by it . 2

Thua, some analogical inferences may be seen as knowledge which exists for the target domain, yet i.e not explicitly stated (i.e., search would be required to retrieve it). Other analogical inferences represent new . knowledge · conjectured facta about the target domain. This is an important distinction for categorisint~ the different uses of analogy:

Analogical Reuonlng. Analogical reasoning involves using past ex­ periences as heuristic· to guide or assist current reasoning pro­ ceases, as in recommending promising search paths (e.g. Car­ bonell (19113), Kedar-Cabelli (1985)) . The classification also refers to cuea in which analogy i.e uaed aa a focusing mechani.am (e.g., atating an analogy to point out the aalient features of the target) . It also applies to cau-baaed rea·oning systems, which draw on previous inatances of similar situations for guidance (e.g. Kolod­ ner et al, 1985; Hammond, 1986). Here a strict definition of

2 tndurkhya (1~15) uaea ........., and ill aubaet , """'f'r colurant, co refer to the entire analocical mappinc (match01 pluo inference~) . Here we add the term wra.llr columot and only apply theae Ierma to the inferenceo.

Abstract

M~ny studio· of ~nalogy in Artiflci:.llntelligence have focuaed on ~n:.logy u :. heuristic mechanism to guide search ~nd aimplify problem aolving or u a buia for forming gener~lizationa . Thia paper examine· analogical leaming, where an~logy ia used to conjecture new knowledge about some domain. A theory of Verification-Baud Analogical Learning ia preaented which ~ddre11e1 the tenuous n~ture of ~nalogic~lly inferred concepti ~nd deacribea procedure· that can be used to increase confidence in the inferred knowledge. The theory describe· how ~nalogy may be uaed to diocover ~nd refine acientiflc modet. of the physical world. Ex~mplea ~re t~ken from an implemented ayatem, which diecoven qualit~tive modele of proceuea ouch u liquid flow and heat flow.

i Introduction

Analogy i.e roughly composed of three stages: Acceu, Mapping, and Evaluatiort and U~e. Previous work in analogy has focused primar­ ily on how one forms an analogical mapping and how thi.a mapping may be used as a heuristic mechanism to guide search and simplify problem solving. This paper makes a di.atinction between the differ­ ent uses of analogy and focuses on analogical learning, where ~nalogy is used to conjecture new knowledge nbout some domain. Since the underlying assumption of analogical inference is that certain similar­ ities between two domains imply stronger, relational similarities, the validity of knowledge inferred in this manner is very tenuous. Thi.a pa­ per describes some procedures that can be used to increase confidence in the inferred knowledge. Specifically, a theory of Verification·Ba~ed Analogical Learning is presented which may be used to discover and refine scientific models of the physical world. New models' predictions are compared against observed behavior, enabling the system to test the validity of the analogy and unction refinements where the anal­ ogy i.e incorrect. The work also addreues another common problem in analogy, that of knowing what relations to map, by showing that the behavioral similarity of two phenomena can be used to initiate and guide the mapping process.

Many scientific theories are postulated as qualitative models of physical phenomena which must be actively confirmed or refuted. Thi.a work shows how analogy may be seen as one source of creativity in dis­ covering such models and focuses on how the results of thi.a creativity must be carefully examined. Intuitively, the theory corresponds to how one might construct a wave model of sound from prior knowledge of water wave behavior. Examples are taken from an implemented ays­ tem to demonstrate how the theory may be used to diocover qualitative modele of liquid flow and heat flow.

2 The Analogy Process

To understand the possible uses for analogy, one muat firat have a clear definition of analogy itself. Thi.a aection aerves to clarify common terminology by presenting a breakdown of the analogy proceu (similar to Gentner, 1986), followed by a di.ac uuion of the different uaes for analogy.

1 Thia roaearch ia aupported by an IBM Groduate Fellowahip and by the Olllce of N.val Reuarch, Contract No. N00014-85-K-05&~ . Thia paper repr01enll a brief aummary of work deacribed in (Falkenhainer, 1~16) .

reasoning by analogy will be employed, in which analogy ia used for guidance and those analogical inferences which end up being useful are &trongly coherent.

• Similarity-Based Generalization. In analogy, one may use the sim­ ilarity between two concepts found during the matching stage to form a dingle, generalized concept. This corresponds closely to many empirical (often called similarity-based) learning methods, some of which use pattern matching techniques to detect similar­ ities in the structural representation of features (e.g., Hayes-Roth & McDermott, 1978; Michalski, 1980).

Analogical Learning. This is a method of learning that ia unique· to analogy. Roughly, if we know about some base situation and we encounter some target situation which ia believed to be similar to the base, perhaps the additional knowledge we have about the base may also hold for the target . Thus, analogical learning uses weakly coherent analogical inferences to posit new knowledge about the target domain.

These uses of analogy may be intermixed. For example, one may use the results of analogical learning to form a more general concept description. Thus,· knowledge of the solar system could be used to learn about the Rutherford model of the atom. In turn, these could be used to form a general concept of central-force systems. In addition, the results of analogical reasoning ·processes may be stored, thus "learn­ ing" in the analytical (EBL) sense. This paper focuses on analogical learning. In analogical reasoning, the inferences are used as a heuristic . device. Falsely drawn inferences only mean an impact on performance rather than correctness (i.e., they will cause backtracking). In analog­ ical learning, the inferences are accepted as new knowledge which did not exist prior to the analogy. Thus, we must be sure there are sound reasons for believing that the inferences are correct.

The underlying assumption of analogical inference is that surface similarity implies a stronger, relational similarity. Thus, it ia a tenu­ e>us form of plausible inference. Accepting weakly coherent inferences requires a cautious investigation of the learned concepts. One way to ensure that they make sense is to compare the consequences of these in­ ferences against observed physical behavior - hence, verification-based analogical learning. Theories produced by analogy are evaluated by their ability to predict observed physical phenomena.

3 A Theory Of Model Acquisition

Scientific theories are seldom constructed in a vacuum. They tend to be either refined versions of existing theories or they are trans­ ferred theories of similar phenomena. This work addresses both types of theory construction, using analogical inference as the "inventive" mechanism. Knowledge refinement techniques model the incremental stage of theory construction. By contrast, discovery techniques enable the construction of "first-pass" theories of the world. Analogy offers a method for making large leaps in current knowledge. It allows a reasoning system to come up with an initial theory for some domain which knowledge refinement methods may subsequently adjust.

In general, we know that· when two bodies, one hot and one cold, are placed in contact with each other, after a period of time they will reach the same temperature. What happens between the time the two objects are placed in contact and the time the two temperatures equal­ ize? U the notion of water ftow suggests itseU, we may construct a model for the situation in which heat is seen "Bowing" from a higher temperature to a lower temperature. Using the new model shows that it accurately explains the phenomenon. This is called verifying the corm.cency of the model. The new theory now predicts that certain 'lther events must also be able to happen, such as the bidirectional­ ir.y of heat ftow. We attempt to recollect a prior experience (history) demonstrating this predicted behavior or we conduct simple experi­ ments to explore the space of hypothesized behaviors. This is called vtrtfytny tht predichan· of the modd. If we were to extend the anal­ ·'1() 1u11 hPr by ln-pnth~·izinl! t.hat heat "'"" it·elf a t.ype of liquid (i.e .. rlt ·· .·.7 o ri·: thr·JI'Y ·)f l1t~:tt ). a uuruhl"l t)( additional prt"di r th·ll:o: IH .IY bt·

made based upon the intrinsic properties of liquids and physical ob­ jects. For example, co!lservation of matter would lead to predictions based on co!lurvation of heat. Exploring the consequences of these additional predictions ia called verifying the ezten&ion of the analogy. Th!. entire process of hypothesis formation , confirmation, refutation, and subsequent refinement ia the essence of verification-based analogi­ cal learning (VBAL) .

In order to learn in this manner, we must be able to reason about scientific theories and the physical situations they describe. This work models the world in terms of qualitative physics, using Forbus' Quali­ tative Process theory (Forbus, 1984). J A physics reasoner, QPE (For­ bus, 1986b), ;. employed, which takes qualitative models and produces an e!lvisionment for a given system that describes its possible phys­ ical states and the possible transitions between them. A single path through the envisionment (an actual behavior) is called a hi&tory. In addition, a physics interpreter, ATMI (Forbus, 1986a), is used to mon­ itor the world and relate obserations to known or postulated theories.

The current implementation of VBAL, called Phineas (Figure 2), is designed to operate as a passive observer, relating observed physical phenomena to known theories of the world. When ATMI fails to ade­ quately interpret a new event, the VBAL control module is called upon to construct a potential explanation of the situation (see Figure 1). It interacts with SME and a knowledge refinement module to construct a new or revised model: 4

1. Dynamic Behavior Match. First, a prior situation that ap­ pears to exhibit similar behavior is accessed and SME is used to form a match between the behavior of the current and prior sit­ uations. This analogy serves to explicitly indicate which aspects of their behavior are the same (e.g., perhaps only some of the prior behavior's states are analogous) and establi~hes the object and quantity correspondences between the two domains.
2. Relevant Theory Retrieval. Once a satisfactory experience has been retrieved, the domain theories used to explain the matched parts of the prior situation are fetched. These theories are simply a collection of the entity and process definitions that were used by ATMI when it originally encountered the previous behavior. Each state in the history indicates what processes were active during that state. Thus, if the current h!.tory only matches a subset of the states in the old history, only the relevant process models are used.
3. Theory Mapping. SME is invoked a second time to map the potentially analogous domain theory to the new domain of inter­ est . This second analogy;. generally a pure mapping of structure from one domain to another, appropriately transformed accord­ ing to the object correspondences provided by the prior analogy

3 Jn QP th.ory, a aituation 11 repreaented u 3. collection (){ obJects . a. set ,,f relationahipl between them, and a set of proceseea which l\cc,;·mt for ~,11 chanjlett tn .ne world (··I ·· liquid ftow) . Each object h31 a set ofcontmuuu~ paranh!ter1 ~uch a. !ENPUATUU :1nd Pl!SSUIE, which are repreaented :t.a aymbohc qwi'Wtltl ~hat havt: :,n ·Jnw·uU and a ·knvattw. Proce·· deHnition1 contain a set r f 1n1t1al condat~·:,ll$ · nar Ct)OI' n111 a~tiv:ltion :..nd a ·et ·.)( relataon11 thJ. t llh:iic ;.Ltl! how 1h~ :J.Cttve prri" t!l.:i

between the histories. The analogical match is constrained by the object and quantity correspondences established during the dynamic behavior match.

1. Consistency Verification. The correctness of the new model is verified by using it to account for the original situation. QPE takes the model and produces a new envisionment, which ATMI in turn compares to the current situation. If verification fails, model refinement may be used to account for slight imperfections in the analogy, or a different analogy may be tried.
2. Empirical Verification. Given that the new model is con­ sistent with what has been observed, we may now seek further empiri~al confirmation of its validity through various stages of ex­ -perimentation. A time-based planner is being used to explore the possibility of constructing simple experiments to perform predic­ tion verification. More complex experiments may have to be per­ formed to verify extensions of the analogy (Falkenhainer, 1987).

At any time during the verification stages, if the model is found to be flawed, knowledge refinement would be required to make the appropriate adjustments in the model. For example, we could call upon our general physical knowledge to make "common sense" adjustments. Alternately, we could resort to directed experimentation to uncover the source of the discrepancy (e.g., Rajamoney, 1985) . Finally, we could resort to analogy again, using different situations to fill in and correct the missing theory (e.g., Burstein, 1983).

Phineas' operation will now be reviewed in conjuction with an ex­ ample of how the system learns a new model of heat flow by drawin~ an analogy with a similar water How experience.

3.1 Accessing Analogous Behavior

Suppose the program was given time-ordered measurements of a heat flow situation in which a hot horse shoe has just been thrown into a bucket of cold water. ATMI would translate this sequence into. the qualitative history shown in Figure 3 and attempt to explain it in terms of known theories. If the program has no knowledge of heat flow, interpretation will fail. As a result, the analogical learning module will attempt to construct a plausible explanation. First, an analogous history must be located from past experience. Currently, we assume that a suitable situation has been retrieved, leaving the problem of analogical access for separate investigation. 5

In this case, an analogous water flow history is found (a beaker and a vial attached by a pipe) and SME is invoked to match the cur­ rent heat flow history to the prior water flow history. This establishes which things are behaving in an analogous manner (e.g. , which ob­ ject is the source of flow and which object is the destination). The roles of the beaker water and vial water in the water flow history are found to correspond to the roles of the horse shoe and water in the heat flow history, respectively. Those correspondences which provide a mapping between entities or between their quantities are stored for later reference (the correspondences shown in Figure .!).

:'Tht:! current implementation .; imply quen~:::' the USt!r fr.r t:he n:tm~ ·A tht' \llal· ·'lgous b~~e <titua.tion. A number nf analugic:1.i :-tcc~s~ nter:h1·u~tt·~ .r .. ·w:'". ~ .~· .. . ,t.

Heat Flow History

3.2 Forming a New Model

The program now fetches the relevant domain theory which led to its prior understanding of water How. A second analogical match is performed by SME, this time between the retrieved process model for water flow and the current heat flow situation, producing a new model for heat flow based upon the old water flow model (Figure 4). 6

The analogy at this stage is highly constrained, due to the set of entity and function correspondences established when the dynamic behaviors were matched. SME's rule-based architecture complements this activity, since the reasoning program may dynamically modify SME's match construction rules to force a match between those entities and quantities that were found to be analogous during the access stage (e.g., Pressure and Temperature) and prevent any alternate matches for these items (e.g., Amount-Of and Temperature) .

Notice that the "analogy" here is composed almost entirely of weakly coherent inferences, ·ince the system had no prior model of heat flow. Thus. the model was constructed by analogy rather than a1igmented by analo~y. Additionally, this method shows how SME's rule-based architecture supports situations in which entity correspondences are given prior to the match, rather than derived as a result of the match.

In many cases, not enough information is explicitly given for the theory to properly match. In the heat flow example, we need a way of knowing what is flowing. This information is not available if the temperature change is all that is known. The domain model for wa­ ter flow includes an AMOU!IT-OF function which corresponds to HEAT in the heat flow domain. However, the quantity HEAT .never appeared in the he~t flow history as an observable. Without a notion of heat , the program would be forced to either map AMOUNT-OF directly into the new heat flow model or postulate the existence of an unknown aspect of the objects involved which corresponds to an AMOUNT-OF concept for heat flow situations. To avoid this, the world knowledge must include enough information to deduce that temperature and heat possess a relationship similar to the relationship between pressure and amount (mass) . In this example, the relation FUNCTION-OF was used to ap­ proximate this relationship, enabling the system to match PRESSURE to TEMPERATURE and AMOUNT-OF to HEAT.

The results produced by SME (Figure 4) contain the entity (·akolem· pipe) . This indicates that . at the moment, the heat path is

gated .:1t this time but have yet to be installed ::md evaluated .

'~The model shown tn the figure was produced by SME The VBAL contr')l nt(lriule later r.ran·:ilatef t.has into QPE prr..cess definiti(m synr:-.x Tht> fig11r~ :iPrve,.. '· t>X!)hcttly sh·)'4 what was produceri by :-analt·"Y

Gaap tl : Eaapo: 'Ieight: (lNOOIIT-OF-6 IIE!T-WATEI) (ANOOIIT-OF-3 HEU-HSHOE) (PRESS-BE.UEll TEMP-HSHOE) (PilESS-VUL TEMP-WlTEll) (eo-baakar horoe-ohoe) (es-vial water) ~.876 Candidate Inferaneeo : (IIIipliaa (And (Aligned ( · okole·· pipe)) (Greater-Than (A TEMP-HSHOE) (A TEMP-WATER))) (And (Q= (Flow-Rata pi) (- TEMP-HSHOE TEMP-WATER)) (Greater-Than (A (Flow-Rate pi)) zero) (I+ HEAT-WATER (A (Flow-Rate pi))) (I- HEAT-HSHOE (A (Flow-Rate pi)))))

a conjectured entity. Further experimentation could be used to identify the actual heat path, a knowledge of paths in general could be used to indicate that immersion is a likely path, or the path could be left as a conjectured entity. This last choice corresponds closely to the period in science when a substance, called the ether, was believed to exist in order to provide a medium for the flow of light waves. In this example, Phineas concludes that physical contact represents a valid path.

lUI Consistency Verification

Now that Phineas has a new process model for heat flow, it may repeat its attempt to interpret the original situation. The heat flow process model is given to QPE and ATMI compares QPE's new predictions against the original observations. Since the water flow and heat flow situations are so similar, ATMI finds that the new theory accurately models the heat flow situation. The program hall thus verified that the theory is accurate for this and functionally similar instances of heat flow. Experiments may be used to further verify the theory and the new model may be added to the set of known domain theories. VBAL takes weakly coherent analogical inferences and adds a new dimension of validity to them, that of empirical validity.

4 Other Examples

Phineas has been used to learn different types of water flow and heat flow models (e.g., an infinite heat source - a stove) and its knowledge representation is being extended to enable learning of oscillation mod­ els. A common problem in analogy is knowing what to map . Focusing on the theory that explained the base history indicates which system of relations should be mapped, thus eliminating the need to consider irrel­ evant relations (e.g., evaporation) in the water- heat analogy. (Falken­ hainer, 1986} describes an example in which a model of water flow was learned by drawing upon a two-state heat flow situation (heating up, boiling). It shows how the dynamic behavior match enabled the system to deam the boiling irrelevant to the purpose of the analogy.

The examples described above consist of ideal situations; that is, the recalled behavior and corresponding theory were sufficiently similar to analogously explain the observed behavior. Since this will often not be the case, any general theory of analogical learning must include a theory of model refinement . See (Falkenhainer, 1986} for a discussion of refinement in the context of VBAL and how analogy may serve to focus the refinement process.

5 Discussion

Analogy has been shown to be a useful "inventive" mechanism. en­ abling a reasoning system to construct initial theories .of some domain which knowledge refinement methods may subsequently adjust. Th current implementation opens the door for a variety of future re"earr h darections. For example, the various access mecha.nasm; LUrrently be­ ing investigated may now be installed and evalua.r ed. ln :,Jditinn. the ')SI.Pill lack; .1 knowledge refinemPrrt module 'nrl ;n ;, uuJbl· I n ''"·­ recti)' IJrl)(~ss the non-idPal ~ituatinn~ recpurin~ 111 '"difi, ·ui'"' "''f·rk 1:in progress to construct a suitable refinement module. This will allow direct testing of the utility of different refinement schemes in the con­ text of analogy. We would also like to test different and more complex domain models to explore the limits of analogy as a learning device.

A key issue in analogical learning concerns the tenuous nature of the inferences made. Given that two domains appear to be similar in a number of ways, how valid are the conjectures made by the matching module about the target domain? One way to ensure they make sense is to compare the consequences of these inferences against observed phys­ ical behavior , that is, to establish their empirical validity. Similarity­ based and explanation-based techniques produce learned concepts that are guaranteed to be correct for the examples used to generate them. In analogical learning, explicit verification and refinement are required in order to learn anything , yet alone refine past knowledge.

This paper has stressed a number of points. First, when discussing analogy, we must draw a clear distinction between reasoning by anal­ ogy, similarity-based generalization, and analogical learning. Second, in learning physical models , dynamic behavior may be used to initi­ ate and guide the analogy process. Third, when performing analogical lsa.rning, it is important that we ensure there is a "causal" argument for believing that surface similarities will lead to meaningful and valid inferences. In addition, we must confirm these inferences by comparing the derived theories against real world behavior. Finally, it has been stressed that any model of analogical learning must necessarily possess a complementary model of knowledge refinement.

Acknowledgements

l would like to t hank Ken Forbus, Dedre Gentner, Barry Smith, Janice Skorstad, and Steve Chien for interesting and educational discussions on analogy and helpful comments on prior drafts of this paper.