A Logical Approach to Reasoning by Analogy

1 Introduction to the Problem

In this paper we consider the conditions under which propositions inferred by analogy are true or sound. As such, we are concerned with normative criteria for analog­ ical transfer rather than a descriptive or heuristic theory. The goal is to provide a reliable, programmable strategy that will enable a system to draw conclusions by analogy only when it should.

Reasoning by analogy may be defined as the process of inferring that a conclusion property Q holds of a partic­ ular situation or object T (the target) from the fact that T shares a property or set of properties P with another situation/object S (the source) that has property Q. The set of common properties P is the similarity between S

1 This research was made possible in part by a grant from the Sys­ tem Development Foundation to the Center for the Study of Language and Information, and in part by the Office of Naval Research under Contracts N00014-85-C-0013 and N00014-81-K-0004. The views and conclusions contained in this document are those of the authors and should not be interpreted as representing the official policies, either expressed or implied, of the Office of Naval Research or the United States Government. This research was done while the second author was a student in the Computer Science Department at Stanford Uni­ versity, supported by a NATO studentship from the UK Science and Engineering Research Council. The first author is presently also affil­ iated with the Psychology Department at Stanford University.

A Logical Approach to Reasoning by Analogy

Todd R. Davies Artificial Intelligence Center SRI International Menlo Park, CA 94025, USA

Stuart J. Russell Computer Science Division University of California Berkeley, CA 94 720, USA

and T, and the conclusion property Q is projected from S onto T . The process may be summarized schematically as follows:

This form of argument is nondeductive, in that its con­ clusion does not follow syntactically just from its premises. Instances of this argument' form vary greatly in cogency. Bob's car and John's car share the property of being 1982 Mustang GLX V6 hatchbacks, but we could not infer that Bob's car is painted red just because John's car is painted red. The fact that John's car is worth about $3500 is, however, a good indication that Bob's car is worth about $3500. In the former example, the inference is not com­ pelling; in the latter it is very probable, but the premises are true in both examples. Clearly the plausibility of the conclusion depends on information that is not provided in the premises. So the justification aspect of the logical problem of analogy, which has been much studied in the field of philosophy (see, e.g. (5], (13], (16], (31]), may be defined as follows:

THE JUSTIFICATION PROBLEM:

Find a criterion which, if satisfied by any partic­ ular analogical inference, sufficiently establishes the truth of that inference.

Specifically, we take this to be the task of specifying back­ ground knowledge that , when added to the premises of the analogy, makes the conclusion follow soundly.

It might be noticed that the analogy process defined above can be broken down into a two-step argument as follows: (1) From the first premise P(S) 1\ Q(S) , conclude the generalization VxP(x) => Q(x ), and (2) instantiate the generalization to T and apply modus ponens to get the conclusion Q(T) . In this process, only the first step is nondeductive, so it looks as if the problem of justifying the analogy has been reduced to the problem of justify­ ing a single-instance inductive generalization. The tradi­ tional criteria for evaluating the cogency of enumerative induction, however, tell us only that the inference increases in plausibility as the number of instances confirming the generalization increases (without counter-examples) and is dependent on the conclusion property being "projectible"

(see (11]) . If this is the only criterion applied to analog­ ical inferences, then all projectible conclusions by anal­ ogy without counter-examples should be equally plausible, which is not the case. For example, if inspection of a red robin reveals that its legs are longer than its beak, a projec­ tion of this conclusion onto unseen red robins is plausible, but projecting that the scratch on the first bird's beak will be observed on a second red robin is implausible. A per­ son who has looked closely at the beak of only one red robin will have no counter-examples to either conclusion, and both conclusion properties are projectible, so the dif­ ference in cogency must be accounted for by some other criterion. The problem of analogy is thus distinct from the problem of enumerative induction because the former requires a stronger criterion for plausibility.

One approach to the analogy problem has been to regard the conclusion as plausible in proportion to the amount of similarity that exists between the target and the source (see (19]) . Heuristic variants of this have been popular in research on analogy in AI (see, e.g. (32] and (3]) . Such similarity-based methods, although intuitively appealing, suffer from some serious drawbacks. Consider again the problem of inferring properties of an unseen red robin from those of one already studied: the amount of similarity is fixed, namely that both things are red robins, but we are much happier to infer that the bodily proportions will be the same in both cases than to infer that the unseen robin will also have a scratched beak. In other words, the amount of similarity is clearly an insufficient guide to the plausibil­ ity of an analogical inference. Recognizing this, researchers studying analogy have adverted to relevance as an impor­ tant condition on the relation between the similarity and the conclusion ((27], (15]).

To be a useful criterion, the condition of the similarity P being relevant to the conclusion Q needs to be weaker than the rule Vx P(x) =} Q(x), for otherwise the conclusion in plausible analogies would always follow just by application of the rule to the target. Inspection of the source would then be redundant. So a solution to the logical problem of analogy must, in addition to providing a justification for the conclusion, also ensure that the information pro­ vided by the source instance is used in the inference. We therefore have the following:

THE NON-REDUNDANCY PROBLEM:

The background knowledge that justifies an anal­ ogy or single-instance generalization should be insufficient to imply the conclusion given infor­ mation only about the target. The source in­ stance should provide information not otherwise contained in the database.

This condition rules out trivial solutions to the justifica­ tion problem. In particular, though the additional premise Vx P( x) =? Q( x) is sufficient for the truth of the inference, it does not solve the non-redundancy problem and is there­ fore inadequate as a general solution to the logical problem of analogy. To return to the example of Bob's and John's cars, the non-redundancy requirement stipulates that it should not be possible, merely from knowing that John's car is a 1982 Mustang GLX V6 hatchback and some rules for calculating current value, to conclude that the value of John's car is about $3500-for then it would be unnec­ essary to invoke the information that Bob's car is worth that amount. The role of the source analogue (or instance) would in that case be just to point to a conclusion which could then be verified independently by applying general knowledge directly to John's car. The non-redundancy re­ quirement assumes, by contrast, that the information pro­ vided by the source instance is not implicit in other knowl­ edge. This requirement is important if reasoning from in­ stances is to provide us with any conclusions that could not be inferred otherwise.

This seems like an opportune place to draw a distinction between this work and that of many others researching analogy. There has been a good deal of fruitful work on different methods for learning by analogy ((12], (2], (3] , (32], (1], (15], (10]) in which the logical problem is of secondary importance to the empirical usefulness of the methods for particular domains. Similarity measures, for instance, can prove. to be a successful guide to analogizing when pre­ cise relevance information is unavailable ((24]) . However, when studying any form of inference, it behooves the re­ searcher to at least consider what the basis of the infer­ ence process might be; for the most part such consider­ ation has been lacking, with the result that analogy sys­ tems have yet to demonstrate any wide applicability or reliable performance. Our project is to provide an un­ derlying justification for the plausibility of analogy from a logical perspective, and in so doing to provide a way to specify background knowledge that is sufficient for drawing reliable analogical inferences. The approach is intended to complement, rather than to compete with, more heuristic methods.

2 Determination Rules as a Solu­ tion

If we think about the example of the two cars (Bob's and John's), it seems clear that, while we may not know what the value of a 1986 Mustang GLX V6 hatchback is prior to knowing the value of Bob's car, we do know that the fact that a car is a Mustang GLX V6 hatchback is sufficient to determine its value. Al:1stractly, we know that either all objects with property P also have property Q, or that none do:

Having this assumption in a background theory is sufficient to guarantee the truth of the conclusion Q(T) from P(S)I\ P(T)I\Q(S) while at the same time requiring an inspection of the source S to rule out one of the disjuncts. It is therefore a solution to both the justification problem and the non-redundancy problem.

As a way of describing the relation between P and Q in the above disjunction, we might say that P decide3 whether Q is true for any situation x. Of course, one might notice that the background knowledge we bring to the car example is more general in form. Specifically, we have knowledge of what is called in database theory a "de­ pendency" relation ([28]), that the make, model, design, engine, condition, and year of a car determine its current value. Abstractly, a functional dependency is defined as follows ([29]) :

In this case, we say that a function (or set of functions) F functionally determines the value offunction(s) G because the value assignment for F is associated with a unique value assignment for G. We may know this to be true without knowing exactly which value for G goes with a particular value for F. A taxonomy of the forms for the relation "F( x) determines G( x )" has been worked out by researchers in database theory, in which such dependencies are used as integrity constraints ([28]). If the example of Bob's and John's cars (GarB and CarJ respectively) from above is written in functional terms, as follows:

Make( GarB)= Ford/\ Make(CarJ) =Ford Model( GarB)= Mustang/\ Model(CarJ) =Mustang Design( GarB)= GLX /\ Design(CarJ) = GLX Engine( GarB)= V6 /\ Engine(CarJ) = V(} Condition( Car B) = Good /\ Condition( Car J) = Good Year(CarB) = 1982/\ Year(CarJ) = 1982 Value(CarB) = $3500 Value(CarJ) = $3500,

then knowing that the make, model, design, engine, condi­ tion, and year determine value thus makes the conclusion valid. In our generalized logical definition of determina­ tion (see the section on "Representation and Semantics"), the forms (*) and (**) are subsumed as special cases of a single relation "P determines Q", written asP>- Q.

Assertions of the form "P determines Q" are actually quite common in ordinary language. When we say "The IRS decides whether you get a tax refund", or "What school you attend determines what courses are available", or, quoting a recent television advertisement, "It's when you start to save that decides where in the world you can retire to", we are expressing an invariant relation more complicated than ·a purely implicational rule. At the same time, we are expressing weaker information than is con­ tained in the statement that P implies Q. If P implies Q then P determines Q, but the reverse is not true, so traditional implication falls out as a special case of deter­ mination. That the knowledge of a determination rule is what underlies preferred analogical inferences seems rela­ tively transparent once the problem is set up as we have done. We therefore find it surprisiJJ.g that only recently has the possibility of valid reasoning by analogy been rec­ ognized (in [30]) and the logical form of its justification been worked out in a way that solves the non-redundancy propblem (in [6]) . Most research on analogy and general­ ization seems to have assumed that an instance can provide at most inductive support for a rule. Our work suggests that rule formation and analogical projection are better viewed as being guided by higher level domain knowledge about what sorts of generalizations can be inferred from an instance. This perspective seems consistent with more recent AI techniques for doing induction and analogy (e.g. [14],[15]) which view such inferences as requiring specific knowledge about relevance rather than just an ability to evaluate similarity. We have concentrated on making the relevance criterion deductive.

3 Representation and Semantics

To define the general logical form for determination in predicate logic, we need a representation that covers ( 1) determination of the truth value or polarity of an expres­ sion, as in example cases of the form "P(x) decides whether or not Q(x)" (formula(*) from previous section), (2) func­ tional determination rules like (**) above, and (3) other cases in which one expression in first order logic deter­ mines another. Rules of the first form require us to extend the notion of a first order predicate schema in the following way. Because the truth value of a first order formula can­ not be a defined function within the language, we introduce the concept of a polar variable, which can be placed at the beginning of an expression to denote that its truth value is not being specified by the expression. For example, the notation "i P( x )" can be read "whether or not P( x )", and it can appear on either side of the determination relation sign ">-" in a determination rule, as in

This would be read, "P1(x) and whether or not P2(x) to­ gether jointly determine whether or not Q(x)," where i 1 and i 2 are polar variables.

The determination relation cannot be formulated as a connective, i.e., a relation between propositions or closed formulas. Instead, it should be thought of as a relation between predicate schemata, or open formulas with polar variables. For a first order language L, the set of pred­ icate schemata for the language may be characterized as follows. If Sis a sentence (closed formula or wff) of L, then the following operations may be applied, in order, to S to generate a predicate schema:

1. Polar· variables may be placed in front of any wffs that are contained as strings in S,
2. Any object variables in Smay be unbound (made free) by removing quantification for any part of S, and
3. Any object constants in S may be replaced by object variables.

All of and only the expressions generated by these rules are schemata of L.

To motivate the definition of determination, let us turn to some example pairs of schemata for which the determi­ nation relation holds. As an example of the use of polar variables, consider the rule that, being a student athlete, one's school, year, sport, and whether one is female deter­ mine who one's coach is and whether or not one has to do sit-ups. This can be represented as follows:

EXAMPLE 1:

As a second example, to illustrate that the component schemata may contain quantified variables, consider the rule that, not having any deductions, having all your in­ come from a corporate employer, and one's income deter­ .mine one's tax rate:

EXAMPLE 2:

In each of the above examples, the free variables in the component schemata may be divided, relative to the de­ termination rule, into a ca~e set it of those that appear free in both the determinant (left-hand side) and the re3ultant (right-hand side), a predictor set 1L of those that appear only in the determinant schema, and a re~pon~e set I. of those that appear only in the resultant. 2 · These sets are uniquely defined for each determination rule. In particu­ lar, for example 1 they are it= {x}, 1L = {s,y,z,it}, and I.= {c,i2}; and for example 2 they are ;t = {x}, 1L = {p}, and I. = {r}. In general, for a predicate schema E with free variables it and 11.· and a predicate schema X with free variables ;t (shared with E) and I. (unshared), whether the determination relation holds is defined as follows:

THE DEFINITION OF DETERMINATION:

In interpreting this formula, quantified polar variables range over the unary Boolean operators (negation and af­ firmation) as their domain of constants, and the standard Tarskian semantics is applied i.n evaluating truth in the usual way (see [9]). This definition covers the full range of determination rules expressible in first order logic, and is therefore more·expressive than the set of rules restricted to dependencies between frame slots, given a fixed vocabu­ lary of constants. Nonetheless, one way to view a predicate schema is as a frame, with slots corresponding to the free variables.

4 Use in Reasoning

Much of the work in machine learning, from the early days when Shakey was learning macro-operators for ac­ tion ([21]) to more recent work on chunking ([22]) and explanation-based generalization ([20]), has involved get­ ting systems to learn and represent explicitly rules and relations between concepts that could have been derived from the start . In Shakey's case, for example, the plan­ ning algorithm and knowledge about operators in STRIPS were a sufficient apparatus for deriving a plan to achieve a given goal. To say that Shakey "learned" a specific se­ quence of actions for achieving the goal means only that the plan was not derived until the goal first arose. Like­ wise, in EBG, explaining why the training example is an instance of a concept requires knowing beforehand that the instance embodies a set of conditions sufficient for the concept to apply, and chunking, despite its power to sim­ plify knowledge at the appropriate level, does not in the logician's terms add knowledge to the system. By defining determination rules prior to the acquisition of case data, we can enable the system to generalize appropriately without making the rules it will generate implicit from the start.

lReaders familia.r with statistical modeling might notice that the terms for these sets of va.riables a.re borrowed from regression analysis. For a discussion of the statistical analogue of determination, and its relations to regression and dassificiation, see [7)

Determination rules are the kind of knowledge that pro­ grammers of an intelligent system often have. We may not know very many specific rules about which coaches instruct which teams, but we still know that the latter de­ termines the former, and this knowledge has the potential to generate an infinite number of more fine-grained rules. In addition to enhancing the power of intelligent systems, the logical formulation of analogical inference enables it to be used reliably in the logic programming and expert system contexts. A logic programming implementation is described in the next section. Determination rules may be useful in knowledge engineering for two reasons:

1. In many domains a strong (implicational) theory may not be available, whereas determination rules can be provided, and the system can gain expertise through the acquisition of examples from which it can reason by analogy.
2. Even when a strong theory is available, its complete elucidation may be difficult, and it may be easier to elicit knowledge using questions of the form "What are the factors which go into making decisions about Q?", i.e., to extract determination rules.

The use of determination rules appears to be a natural stage in the process of knowledge acquisition, occurring prior to the acquisition of a strong predictive theory; for example, we have as yet no theory that can even come close to predicting the vocabulary, grammar and usage of an en­ tire language simply from facts about the nation it belongs to, but we still have the corresponding determination rule that one's nationality determines one's native language, with a few exceptions. We have been building a list of different categories of determinative knowledge. Here are some examples of processes in which determination rules are found:

• Physical processes: initial conditions determine out­ come; boundary conditions determine steady-state values for whole system; biological ancestry deter­ mines gross physical structure;· developmental envi­ ronment determines fine structure of behavior; struc-

ture determines function; function determines struc­ ture (less strongly); disease determines symptoms; symptoms determine disease (less well); diet, exercise and genes determine weight; etc.

• Processes performed by "rational agents": case de­ scription determines legal outcome; upbringing and education determine political leaning; social class and location determine buying patterns; nationality de­ termines language; zip code determines state; address determines newspaper delivery time; etc.
• Processes in formal systems: program input deter­ mines program output; program specification deter­ mines program; etc.
• The system's own problem-solving processes: all the problem solving abilities the system has, be they plan­ ning, search, inference, programming or whatever, can be analyzed into an input P and an output Q. Constructive processes, such as planning and design, which have enormous search spaces, are particularly amenable to reasoning by analogy. ([4] begins to ad­ dress these issues, implicitly using the determination rule that (exact) problem specification determines so­ lution; the key issue to be resolved before such work can succeed is to identify the various abstracted levels of description for problems and solutions which will allow use of less specific determination rules that do not require exact matching of specifications.)

5 Implementation in a Logic Pro­ gramming System

Determination-based analogical reasoning can be imple­ mented directly as an extension to a logic programming system, such as Genesereth's MRS system (see [23]). The programmer simply adds whatever determination rules are · available to the database and the system will use them whenever possible to perform analogical reasoning.

Given a query X[T, ~], the basic procedure for solving it by analogy is as follows:

1. Find E such that E[J<.,1l) >- X[J<.,~] (i.e., decide which facts could be relevant).
2. Find 1L such that E[T;1l} (i.e., see how those facts are instantiated in the target) .
3. FindS such that E[S,1l) and S =/; T (i.e., find a suit­ able source).
4. Find~ such that X[S,~] (i.e., find the answer to the query from the source).
5. Return~ as the solution to the query X[T,.t].

We add this procedure to the system's recursive routine for solving a goal, so that it now has three alternatives:

1. Look up the answer in the database.
2. Backchain on an applicable implication rule.
3. Analogize using an applicable determination rule.

To solve goal X[T; &.] using determination rule E[.t., 1l) >­ X[.I., .t], we simply add the following conjunctive goal to the agenda:

The subgoals of this can· be solved recursively by the same three alternative methods, thus achieving the procedure given above.

An example may be helpful here. Suppose we have the goal of finding out what language Jack speaks, i.e., N ativeLanguage( Jack, z ). We have the following back­ ground information:

Nationality( Jack, UK) Male(Jack) Height( Jack, 6') Nationality( Giuseppe, Italy) Male( Giuseppe) Height( Giuseppe, 6') N ativeLanguage( Giuseppe, Italian) Nationality( J i"ll, UK) Female( Jill) Height( Jill, 5'10") N ativeLanguage( Jill, English)

and among our determination rules we have that nation­ ality determines native language (except for Swiss), as well as other such rules, for instance that nationality and whether or not one has dual citizenship determines whether or not one needs a vis&. to enter the United States and how long one may stay:

(Nationality(x, n) A -.Nationality(x, Swiss)) >- (NativeLanguage(x, l). (Nationality( x, n) A i 1 Dualcitizen( x, US)) >- (i2N eedVisa(x, US) 1\ M axstay(x, t)).

Using the first of these determination rules, the system generates the new goal:

(Nationality( Jack, n )A -.Nationality( Jack, Swiss ))A (Nationality(s, n) A -.Nationality(s, Swiss))/\ s =/;JackA N ativeLanguage( s, z ),

which is solved after a few simple deduction steps, with Jill as the sources. One may observe that the more "similar" source Giuseppe is ignored, and that the irrelevant facts about Jack and Jill are not examined. When the facts satisfying the various subgoals of the analogy are not ex­ plicitly available in the database, the system will of course attempt solutions by further reasoning, either analogical or implicational. For example, if N ationalitv( Jill. UK)

were replaced by Birthplace( Jill, London), then the anal­ ogy could still succeed if a rule relating Birthplace and Nationality were available. Thus we have a natural, goal­ directed reformulation which reveals implicit similarities in an efficient manner.

In comparison to the more traditional, heuristic ap­ proaches to analogy, the use of determination rules has significant efficiency advantages in addition to its other properties. Winston ([32]) and Greiner ([12]) point out the enormous complexity of matching the target against all possible sources in all possible ways to find out the most similar source; as we observed in the implementa­ tion example, finding the determination rule first enables us to pick out the relevant target facts and use those to index directly to an appropriate source, thus overcoming the matching problem. We also render irrelevant the prob­ lem of finding a suitable similarity metric, and transform the reformulation problem (which arises when a change of representation might reveal a previously hidden similarity) from an open-ended nightmare of forward inference into a relatively controlled, goal-directed process.

The ability of determination-based analogical reasoning to avoid unnecessary matching makes it a reasonable al­ ternative to traditional rule-based logic systems. For some problems, analogy is more efficient than using a corre­ sponding set of implication rules. A determination rule P(x, y) >- Q(x, z) and a set of instances replace a set of implication rules:

where n can be arbitrarily large. Furthermore, since it must test the premises- of every rule that could imply a goal until it finds the right one, a backward chaining system requires a lengthy search that Cl\ll be avoided by using a determination rule.

A common form of reasoning that displays this behavior is taxonomic inheritance, for which we might use a rule such as

to conclude the current resale value of one of our cars. With 7500 models in our database, this would take us 7500/2 backchains on. average. Replacing the im­ plication rules with a determination rule IsA(x, y) >­ V aluel n86( x, z) and a collection of prototypical instances (exactly analogous to the TypicalElephant frames in se­ mantic nets) we can solve our goal in four backchaining steps.

Another example is that of diagnostic reasoning, in which the (simplified) traditional approach uses a collec­ tion of rules of the form:

These implication rules would be replaced by a determina­ tion rule HasSymptoms(x,y) >- HasDisease(x, z) and a case library.

6 Conclusion

There are a number of problems related to analogy that we have not solved. What we have is a method for gen­ erating correct generalizations and analogical inferences, given correct determination rules. At the same time, our work has created new problems: a reasonable next step is to work out how determination rules can themselves be acquired. Some early thought on the determination rule acquisition problem points to four basic methods:

1. Deduce a determination rule from other known facts (For an example, see [26]).
2. Induce a determination rule from instances (essen­ tially calculate the empirical degree of determination · of X by L;-see [25] and [7]).
3. Induce a determination rule from a collection of spe­ cific rules.
4. Generalize from a collection of more specific determi­ nation rules.

Because we have a formal definition for determination, inductive acquisition of determination rules is conceptually straightforward, if pragmatically troublesome. Acquisition experiments on a broad knowledge base are currently un­ der way using the CYC system ([17]). We are also building determination-based expert systems by induction from ex­ amples in the domains of market forecasting and mechan­ ical device diagnosis from acoustic emission. The results so far seem very promising.

A full understanding of the human processes of analog­ ical inference and generalization will surely r~quire fur­ ther investigations into ·bow we measure similarity, how situations and rules are encoded and retrieved, and what heuristics are used in projecting conclusions when a valid argument cannot be made. But it seems that logic can tell us quite a lot about analogy, by giving us a standard for evaluating the truth of its conclusions, a general form for its justification, and a language for distinguishing it from other forms of inference. At the same time, we have found a consideration of the logical problem to be of prac­ tical benefit, for reasoning by analogy using determinative knowledge appears to give a system the ability to learn reliably new rules that would otherwise need to be pro­ grammed.

7 Acknowledgments

We would like to thank our advisors, John Perry, Mike Genesereth, and Doug Lenat, as well as Doug Edwards, Bryn Ekroot, Russ Greiner, Benjamin Grosof, David Hel­ man, Jerry Hobbs, Dikran Karagueuzian, Kurt Konolige, Stan Rosenschein, Devika Subramanian, Dirk Ruiz, Amos Tversky, Paul Rosenbloom, and J . 0 . Urmson for fruitful discussions, constructive criticism and moral support. .