The Superiority of Relative Criteria in Partial Matching and Generalization

1. EVery condition has an instantiation

Textbooks sometimes provide more information in the statement of example problems than is strictly required for their solution. This extra information would prevent the examples from being seen as relevant to the solution of exercise problems not sharing those inessential features if we were to retain the full-match criterion that all propositions in a problem description must receive an instantiation .

* Many full matchers will allow two variables to be bound to the same constant; however, additional mechanisms are then required to deal with the inevitable cases where this is inappropriate. These additional mechanisms play no role in partial matching, so it simplifies the discussion to make the one-one assumption.

2. Constants

Students find problems involving the algebraic relation "<" very reminiscent of the ">" versions of those problems. In such cases partial matches between these problems would have to violate the full-match criterion that a condition and its instantiation contain the same constants. The unsuitability of full-match criteria (1) and (2) for partial matching is not controversial. All four algori thims reviewed in [ 4] for inducing a general description of a concept from examples can deal with these kinds of departures from a full match.

3. Variable Binding Requires 1-1 Functions

Imagine a person who has seen many National League baseball games, but is watching American League baseball for the first time. In the National League, besides playing in the field, a pitcher takes his turn at bat; in the American League, however, the pitcher is replaced in the batting lineup by the designated hitter. If the baseball fan tries to instantiate his pattern for National League baseball using the lineups for this game should he bind the variable V-NLpitcher to the pitcher or to the designated hitter? The correct answer seems to be both; to the pitcher if he is instantiating propositions describing the National League pitcher's role in the field, but to the designated hitter when instantiating propositions about the National League pitcher's role as a batter. On the other hand, an American League fan watching National League baseball for the first time has the problem of too few players rather than too many. He is in the position of having the same constant, NLpitcher, as the binding of two different variables, V-ALpitcher and

V-A Ldesighi tter.

1. Only Match Propositions Having the Same Structure

Fig. 1 shows two problems that some students can see as quite similar -- Fig. 1b being just an angle version of the problem in Fig. 1a. This apparently requires that a partial matcher accept the proposition (angle VR' VX VO') as an ins tan tia tion of the proposition Tsegment VR VO). That segment can be matched by angle 1s just another example of matching one constant to another. What is more interesting is that the second argument, VO, of segment must be bound to the third argument, VO', of angle rather than to the second argument, VX.

II SOME RELATIVE CRITERIA

Since all of the criteria we have identifi ed f or full matching are found to be unsuitable for partial matching we are forced to try an entirely different approach:

While it may be totally unclear what makes an instantiation absolutely unacceptable, it may at least be clear what makes one

instantiation better than another.

We will now discuss an implementation of a partial matcher, RELAX, based on this principle.

RELAX is a modification of the full matcher used by the ACT production system [ 1, 2]. ACT's data base is a semantic network, so its pattern matcher operationalizes the full-match criteria discussed above by attempting to find a subgraph of the semantic network that is isomorphic to a network representation of the left-hand side of a production rule. Criterion (2) is achieved by requiring that the node representing a particular constant in the network representing the production conditions be mapped by the isomorphism onto the node for that same constant in the semantic-network data base. In addition, since all occurrences of a particular variable in a production's conditions are represented by a single node in its condition network, the isomorphism found will necessarily obey full-match criterion (3).

The general approach followed in turning this program into a partial matcher was to leave the search for an isomorphism intact, but to simultaneously compute a partial match "behind the scenes". This partial mat ch respects none of the full-match criteria except the one that requires a condition proposition and its instantiation to have the same structure. (A later section will discuss how problems that violate this requirement can receive the correct partial match.) RElAX begins by assigning the node representing one of the constants in a production to the node representing that constant in the data base and then proceeds to conduct a depth-first search for an isomorphism. All of the INTERLISP function calls that are performed when full matching are also performed when partial matching and they return exactly the same results. This guarantees that a full match will be found if one exists. However, since the partial matcher fully expects the search for an isomorphism to fail, it is busily passing its own results through independent channels. It steps in every time the full-match criteria have ruled out all of the instantia t ions available at this point in the search for one of the condition propositions. It then conducts whatever depth-first search is required to complete its evaluation of the suitability of these rejected instantiations for a partial match. From the point of view of computing an isomorphism such search is pointless--but also harmless.

The goal of this extra search is to determine which of these candidate instantiations, if accepted as a partial match, would permit the largest number of other conditions of the rule to also receive an instantiation. The best such instantiation available in this context is returned through the partial matcher's private channels and the collection of these instantiations is returned as the best partial match if it turns out that a full match is not obtained. This "bigger is better" comparison is the first of the promised relative criteria.

By itself, however, this criterion is relatively ineffectual. If the extra search done to evaluate the alternative instantiations respects none of the full-match criteria ( 1 )- (3), then the candidates are likely to be all equally successful in leading to the instantiation of other conditions--and thus all equally unsuccessful, since the policy is that if no candidate is best in these size comparisons, then the partial matcher returns no instantiation at all as its result in this context. Another defect of this criterion is that it is effectively an exhaustive-search solution of an NP-complete problem and is therefore expected to be highly inefficient.

B. Best Use of the Data ----------

What's needed is a heuristic that can prune these search trees down to a more manageable size . A heuristic that has proven itself very effective is one that asks whether accepting a data proposition as an instantiation of a condition would be the best way found so far of using this data proposition. Thus, before doing any search to evaluate the implications that choosing this instantiation would have for other conditions, t he current use of the data proposition is compared with all other uses of that data that are currently viable.

• If the current use of this data is not as good as a previous use, then the current use is immediately abandoned.
• If the current use of this data is better than one of the previous uses, then that previous use is abandoned and so are any other instantiations that are dependent on it (i.e., below it in the search tree).
• If the current use of this data is equally as good as a previous use, then both uses are permitted and there is no pruning of the search tree. (Thus, this criterion differs from the "bigger is better" criterion which tolerates no ties.)

The discussion of this heurist ic up until this po i nt has neglected to say what makes one use of some data better than another. The briefest possible answer to this is that all uses of data will be considered equally good unless some variable has more than one binding. The idea is that while multiple assignments for a variable are permitted, there is some cost associated with multiple assignments and one use of some data is

better than another if less of this cost is i ncurred. Thus, suppose that at some point in the pr ocess of attempting to see American League basebal l as a partial match to National League baseball we have tentatively accepted the following instantiations

( pitch V-NLpitcher) -> (pitch ALpitcher) (catch V-NLcatcher) -> (catch ALcatcher) (bat V-NLcatcher) -> (bat ALcatcher)

and we are evaluating

( bat V-NLpi tcher) -> (bat ALcatcher).

This use of this data is unacceptable because it r equires that the variable V -NLpi tcher be bound bo th to A Lpi tcher and to A Lcatcher, whereas the cond ition (bat V-NLcatcher) uses this data without the need formul tiple assignments for V -NLcatcher. Suppose at this point we then evaluate

( bat V-NLpitcher) -> (bat ALdesighitter).

Si nc e there is no competing use of this data, this instantiation is permitted in the partial match.

C. Constants~ One-Many

On the face of it, this second relative c rit e rion is only useful for regulating departures f r om full-rna tch criterion (3). However, the heuris tic has wider applicability sine~ it turns out t hat constants may be viewed as variables that j us t happen to have a binding already when we start to match the left-hand side of a rule. To motivate blurring the distinction between constants and variables in this way, consider the problem we get by mod i fying Fig. Ia so that RO > NY is given and RN > OY is what's-to be proven.- This problem occurs as an exercise in our geometry text and the hi nt is prov i ded that it should be compared with the example problem Fig. Ia. Now, as is discussed in [3] , an occasional student will attempt to r eplace al l references to "=" in the proof that the tex t provides for Fig. Ia with ">" -- only to find hims elf with ON > ON as a line in his proof. This e rror shows that what is required for a correct und erstanding of the similarity between these pr oblems is that some of the "=" signs in the exampl e problem should be matched to ">", while othe rs should remain matched to "=" Thus the cons t ant "=" effectively has two "bindings"; a fact that we already know how to deal with if constants are v iewed as already-bound variables.

III RELATED WORK

Robert Kling [9] has described the kinds of mappings needed to capture the correspondences between similar theorems in abstract algebra:

Fo r diffe r ent intuitively analogous theorem pa irs , this mapping would need to be able to assoc iate predicates (and axioms) in a one-one, one-many, or many-many fashion, possibly dependent upon context. (p. 153)

De spite this clear statement of what the program Kling implemented, ZORBA, of fulfilling these goals. ZORBA one-many mappings between predicates is required, falls short does permit in theorem statements, so that the predicate "=" can be mapped to both "=" and ">" as required for the example of the previous section. However, only one-one mappings of prop;:>si tions (axioms in Kling's terminology) are permitted. ZORBA' s deficiencies must be attributed to the difficulty of Kling's overall goal: to select a minimal set of axioms for proving a theorem by analogizing from the known proof of a similar theorem.

There has not been great success in incorporating these unrestrictive sorts of mappings in generalization programs either. For example, Hayes-Roth & McDermott [5, 6] have established the need for one-many and many-one mappings i n computing generalizations and have offered an approach that permits such mappings for variables . Basically their approach is to allow their partial matcher, SPROUTER, to keep believing that a variable can have only one binding, but to adjus t their description of examples in such a way that the effect of multiple bindings can be a chi eved. So the propositions (pitch V-NLpitcher ) and (bat V -NLpi tcher) would be recast in the "uniform representation"

(pitch V-NLpitcher 1 ) (bat V-NLpitcher 2 )

(SP V-NLpitcher 1 V-NLpitcher 2 ).

The "same parameter" pred lea te, SP, is true if both its arguments denote the same individual. Applied to an American League lineup the SP proposition shown would have no instantiation~ but the SP propositions for all the other positions would be successfully instantiated. Complementing SP' s in uniform representations are DP's ("different parameters"). These would be -enployed in the description of American League baseball to encode the fact that all variables should be bound to different individuals. The proposition (DP V-A Lpi tcher V-A Ldesighi tter), would receive no instantiation when applied to National League baseball since both of these variables would have to be bound to the NLpitcher.

Hayes-Roth & McDerm0tt point out two problems inherent t0 their appr0ach. The first is that the introducti0n of all these SP and DP pr0posi tions has very serious consequences for SPROUTER' s computational efficiency. For example, a pr0blem which took 6 sec of cpu time without SP's and DP's took 5 min and 3 sec when recast in a uniform representation. The other deficiency 0f SPROUTER that they discuss is one that it shares with ZORBA these programs will permit only 0ne instantiati0n for a condition pr0p0siti0n. Thus if the descripti0n of Nati0nal League baseball contains the pr;:>p;:>si tion (male V-NLpi tcher), these pNgrams will permit it t;:> receive the instantiati;:>n (male ALpitcher), 0r the instantiation (male ALdesighitter), but not b0th. Thus SPROUTER and ZORBA are [;>reed t 0 make the unintuitive claim that if the American League instituted a rule that the designated hitter had to be female, this w0uld have no impac t ;:>n the similarity of American League baseball to National League baseball.

RELAX does n0t have either of SPROUTER's

deficiencies. The vagaries of variable binding are handled explicitly, s;:> there is no need for SP and DP predicates. Also, when a variable such as V-NLpitcher·receives a second binding, all of the propositions mentioning that variable, whether they already have an instantiation using the first binding or not, are checked to see if they have an instantiation using this new binding. Thus RELAX computes all of the kinds of mappings that Kling claims are necessary for c~pturing the correspondences between similar problems and does so using "best use" criteria whi ch express preferences that are meaningful only to a program that is aware that it has these options regarding the form of its mappings.

A. Best Use of the Condition

One use for the output from partial matching a set of conditions to a set of data is in computing a generalization, i.e., a new set of conditions which receives a full match when instantiated by either the original conditions or the original data. Since the original conditions and the original data play entirely parallel roles in the definition of generalization, one is led rather naturally (though not inescapably) to the idea that the output of the partial match should not depend in any essential way on which set of proposi tiona we call data and which set we call conditions. In fact, in implementing RELAX we found that there are computational advantages to viewing the matching prJcess as searching for condi tiona to instantiate data at the same time as it is searching for data to instantiate conditions. For example, this viewpoint suggests that in addition to the requirement that each instantiation be the best available use of its data proposition, there should also be a complementary requirement that each instantiation be the best available use of its condition proposition. In this third (and last) of RELAX's relative criteria for partial matching, cost is again measured in terms of multiple assignments: but since in this context conditions are thought of as instantiations of data proposi tiona, a multiple assignment means that a constant in the data is the binding for more than one condition variable. The two instantiations mentioned above for (male V-NLpitcher) are equally good in this respect since both ALpitcher and A Ldesighitter are bindings of only one variable: thus both instantiations are permitted in the partial match. However, any attempt to get a second instantiation for (male V-NLcatcher) would be ruled out by this new criterion.

IV SOME EXAMPLES

A. A Generalization Example

Fig. 2 shows the generalization problem that led Hayes-Roth & McDermott to be concerned with multiple assignments for variables. The generalization that Hayes-Roth & McDermott wanted but were unable to get SPROUTER to produce was:

There is a small square above a small circle and one of these small figures is inside a large triangle.

Fig. 2: A generalization problem used by Hayes-Roth & McDermott.

When partial matching the description of Example 1 using the description of Example 2 as data, the variable Vsqr 1 requires two bindings so that we can have both of the instantiations

These two instantiations are taken from Table which shows the full set found by RELAX. The 15 instantiations in Table 1. are the survivors of the 185 instantiations that RELAX considered in computing this match. Of these 185 pairings, 100 , or 54%, were rejected by the "best use" criteria without the need for any search at all. In 21 cases, pairings which satisfied these criteria when first made subsequently were rejected by them as the match proceeded and better uses were found for the i r conditions or their data.

Table 1: The set of instantiations found as the partial match of the examples in Fig. 2.

The demonstration that this partial match wi ll lead to the correct generalization will have to be postponed until a later section which gives the details of the approach taken toward disjunctions. However, there are a number of things we can say at this point to defend the view that this is the correct partial match for these examples. The fact tha t exactly the same correspondences are obtained when Example 2 is treated as the set of conditions and Example 1 is treated as the data provides a demonstration that RELAX at least functions as i ntended. However, how can correspondences such as

be de fended ? The answer to this is that there is an obv i ous alternative to viewing Fig. 2 as two examples in need of a generalization. That alternat i ve i s to see Example 1 as the situation at time .!_ 1 and Example 2 as the situation at a later time ~, where the task is to characterize the t ransformation that has occurred. One cha racterization of the transformation that changes Example 1 into Example 2 is:

The triangle that originally contains the square moves down to contain the circle.

The quest i onable correspondences mentioned above have an obvious relevance for characterizing this t r ansformation.

B. ~ Transformation Example

The next example comes from observations of t wo s ubjec ts learning to program in LISP made by John R. Anderson and his collee;ues at CMU. As an exer c ise in their textbook [10J these subjects had to write a LISP function to compute the powerset (i.e ., the set of all subsets) of the set (YALL COME BACK). This problem is quite difficult for nov ices and both subjects had little success until they hi t upon the represents tion for the problem s hown in Table 2. Once in this form, it appeared that both subjects simply did some pattern matching to arrive at the following solution: POWERSET( YA LL COME BACK) requires two copies of POWERSET(COME BACK) and the second copy must have YA LL CONSed onto t he front of all of its sublists.

Tabl e 2: The r esults of successive calls to the function POWERSET(L).

L (COME BACK) L = (YALL COME BACK)

( )

(COME)

( BACK)

(COME BACK)

( )

(COME)

(BACK)

(COME BACK)

( YA LL)

( YA LL COME)

(YALL BACK)

{YALL COME BACK)

I n pattern matching terms, the need for one copy i s trivial -- it results from a full match of the sets in POWERSET(COME BACK) using the sets in POWERSET(YALL COME BACK) as data. The need for the second copy, however, requires a partial match of POWERSET (COME BACK) to the remaining sets in POWERSET(YALL COME BACK).

When the problem of finding this partial match was given to RELAX the results were as shown in Fig. 3. Here each sublist was successfully matched starting from the left end up until the point where the YA LL was encountered and also was successfully matched starting from the right end until the YALL was encountered. Extending the match from the left end any farther was ruled out by the best-use-of-the-data and best-use-of-the-condition criteria.

If the results of this partial match could be used as data by other rules, then we could construct a rule that would recognize that an atom had been CONSed onto each sublist because the characteristic transformation produced by CONS is found in each case. In general, however, without some notion of a constituent, RELAX would not be able to detect other cases where a list (rather than an atom) has been CONSed onto each sublist. Thus, while RELAX falls short of accounting for all of the pattern matching that subj ects can displ ay in an exercise like this, it does appear to be a promising beginning.

V DISJUNCTIONS

Exclusive disjunctions arise in two different ways in the process of forming generalizations. What we might call external disjunctions have their source in the fact that for any set of examples ~ 1 , ··· , ~ there is the logically correct, but unilluminating, generalization ~ 1 or~ or ·.. ~· The goal of generalization programs that attempt to account for external disjunctions [ 7, 11 ] is to merge as many of the ~i as possible into conjunctive generalizations so as to minimize the number of disjuncts in the resulting disjunctive normal form generalization.

Internal emerge until between two instantiation disjunctions, by contrast, do not a partial match has been computed examples ~i and ~j· Then each in the partial match

yields the again logically unilluminating, generalization correct, but

Just as in the case of external disjunctions, the way to produce pleasing general i zations seems to be t o remove as many disjunctions as possible. The simplest case of this is the reduction of all disjunctions of the form ( c or c) to the single constant c. Less obvious cases Where disjunctions can be removed are best understood by reference t o Fig . 4a which shows a portion of the full network of bindings that can be extracted from Table 1.

RELAX operates on this network in order to determine a way of realizing each of these bindings in a generalization. The goal is to choose a different label for each link in this network, where possible labels are the terms at either end of a link or the disjunction of those terms. Link ~ in Fig. 4~ receives the label Vsqr 1 because three conditions are satisfied: 1) ~ has only one connection to the network, 2) Vsqr 1 can have the binding ~ in a full match, and 3) the label V sqr 1 is not already used as the label for some other link. Link ~ receives the label Vcr1 2 because these conditions are also satisfied there. Link f is then forced to have the label (Vsqr 1 or Vcrl 2 because both of its endpoints have already been used as labels.

(inside (Vsqr 1 or Vcrl 2 ) Vtri) (contains Vtri (Vsqr 1 or Vcrl 2 )) (( bel ow or inside) Vcrl 2 Vtri) ((ins ide or above) Vsqr 1 Vtri) (samesize Vsqr 1 Vcrl 2 ) ( above Vsqr 1 Vcrl 2 ) (below Vcrl 2 Vsqr 1 ) ( size Vsqr 1 small) (size Vcrl 2 small) (size Vtri large) (triangle Vtri) (square Vsqr 1 ) (circle Vcrl 2 )

RELAX produces the generalization in Table 3 from the instantiations in Table 1. It can be seen that Table 3 contains propositions expressing the generalization that Hayes-Roth ll McDermott wanted f or the examples of Fig. 2.

Example 1 from Fig. 2 produces a full match to this generalization by matching the first member of every disjunction, while Example 2 produces a full match by matching the second member of every disjunction. In fact, there is a new full-match criterion requiring that the same position be matched in all disjunctions in a rule. Now it should come as no suprise that vhen partial matching we will want to violate this criterion and match different positions or even both positions of some disjunctions. However, this an tic ipa tes an approach to partial matching disjunctions that there is insufficient space to elaborate on here.

Although the natural way of viewing the partial match found in the POWERSET example presented above is as a characterization of the transformations required to go from POWERSET(COME BACK) to POWERSET(YALL COME BACK), it is also informative t o look at the generalization tha t would result from this partial rna tch. Fig. 4 b shows the pattern of bindings found for the partial match of the sublist (COME) to the sublist ( YA LL COME) and indicates convergences t~at should lead to disjunctions. The generalization obtained for this sublist (ignoring the need for type-token distinctions) is:

(before Lparen (Come or Yall))

(before ( Lparen or Yall) Come) (before Come Rparen)

This generalization provides a disjunctive representation of the fact that YALL is an optional first element of these lists. In the case where the YALL's are present, the second position of every disjunction is matched and the first two propositions of this generalization are instantiated by (before Lparen Yall) and (before Yall Come), respectively. On the other hand, when the YALL 1 s are absent, the first position of every disjunction is matched so in this case these two propositions are both instantiated by the single proposition (before Lparen Come).

A. Implications for Semantic Approaches

Obtaining a sensible generalization for this problem is important because it helps bolster our confidence in the unorthodox correspondences made by RELAX in partial matching these lists. If a left paren t hesis must be matched to the atom YALL to get the correct generalization, then wha t about partial-matching programs that compare the semantic categorization of terms before making assignments? Surely these two terms are sufficiently differen t semantically that such programs shoul d be rel uctan t to see them as corresponding.

How serious a problem this poses depends l argely on whether these partial matchers use semantic re latedness as an absolute criterion or as a relative one. Programs such as Kling's ZORBA [ 9] which make semantic relatedness an absolute criterion will either reject the assignemen t of LPAREN to YA LL or will have to decrease the amount of semantic rtlatedness required to the point where this criterion has little ability left to discriminate useful from useless matches. On the other hand, in Winston's program [ 12] the closer t wo t erms are semantically the more "points" that assignmen t contributes to an overall match score which dete rmines the best partial match. By making semantic relatedness a relative criterion in this manne r, Winston allows for the possibility that othe r fac to rs can compensate for the semantic divergence of two terms. (Winston's partial matcher re l ies totally on one-one mappings, so presumab l y there is no way for his program to produce t he correct generalization for this particular example, however.)

VI _TH_E _LA_S_T :.:A.=;BS=..;O:..:L:..:U..:.T=.E CRITERION

Now RELAX does obey one absolute criterion, namely , the t a proposition and its instantiation must have the same structure. However, as was discussed above , the problem in Fig. 1b may be seen as a version of the problem in Fig. 1 a using angles i nstead of segments. Detecting the similari ty of these problems requires that the cond ition ( segment VR VO) have the instantiation (angle VR' VX VO'). To enable RELAX to find the correc t partial match for this example we followed the lead of Hayes-Roth & McDermott (cf. their use of SCR' a) and switched to a more fine-grained representation. Finer grain was obtained by "explodi ng" each proposition in the description of these probl ems in such a way that every link in the semantic network representation of that proposition itself becomes a full proposition in the exploded version . Thus ( segment VR VO) becomes the set of proposit ions

(Rel segment VsegRO)

(Arg1 VR VsegRO)

(Arg2 VO Vs egRO) .

For these cond i tion proposi tiona, RELAX finds the instantiat i ons

(Rel segment VsegRO) -> (Rel angle VangR'XO') (Arg1 VR VsegRO) -> (Arg1 VR' VangR'XO') (Arg2 VO VsegRO) -> (Arg3 VO' VangR'XO').

No use i s made of the data proposition (Arg2 VX V angR ' XO ' ) .

RELAX was able to calculate the correct pa r tial match for the two problems in Fig. 1 when they were described in this detail. In the pr ocess , Arg2 was matched to Arg3 five times and to A rg2 t hree times. This success suggests the t the relative criteria outlined in this paper are also adequate , at least in principle, for matching different structures. However, finding the 36 instantiations in the final match required searches to evalua t e 230 candidate instantiations. Thus it was clear that by receding whole problems into this fine- gr a ined representation we had placed a large computa t ional burden on RELAX. Work is in progress on defini ng princ i ples that would permit the program to swi tch dynamically to the more fine- grained representation for just those portions of the p~oblem description where it is required. This capabili ty woul d effectively free RELAX from the need to rely on any absolute criteria whatsoever.

ACKNOWLEDGEMENTS

The author would like to acknowl edge t he hundreds of hours of discussion that he has had with John R. Anderson about these topics. The l ack of a shared consensus on these issues has, if anything, only made these discussions more valuable. Helpful comments on a previous draft of this paper were also provided by G. Iba, J. Perlmutter, M. Schustack, and the I JCAI reviewers.