Preduction: A Common Form of Induction and Analogy

1 Introduction

Deduction, induction, and analogy are most common patterns of our thinking. While deduction infers a prop­ erty about a specific individual from a general property which every individual satisfies, inductive reasoning in­ fers an unknown property which every individual will satisfy commonly from specific properties about individ­ uals. Analogical reasoning infers an unknown property about an individual from known properties about simi­ lar others. Because of their generality and importance in our intelligent activities, understanding their reasoning processes is indispensable for embodying artificial intel­ ligence.

More formally, inferences by deduction, induction, and analogy are typically represented as Table 1 1 . De­ du_ction(D.1) expresses "(D.l.l) a is P. (D.l.2) all P­ thmgs are Q. Therefore (D.l.3) a is Q." Induction(I.l) which we call mathematical expresses the usual axiom schema of induction in the arithmetic axioms. "(1.1.1) the case of 0 satisfies P. (1.1.2) if the case of x satis­ fies P, the succeeding case of x also satisfies P. Conse­ quently, (1.1.3) any case will satisfy P." Induction (1.2) expresses more empirical reasoning than (!.1); the same consequence is inferred not from a general assertion like (1.1.2) but from an observation that (1.2.2) every case of 0 to n satisfies P. Analogy (A.1) and (A.2) express "(A.*.1) the base case b satisfies P. (A.*.2) the target case t is similar to b. Thus, (A.*.3) t also satisfies P." They are different in that the similarity between a target and a base is explicit as a property Sin (A.2).

1 Deduction (D.1) is a derivative rule from \>'-elimination and modus ponens.

In this paper, we especially focus on two logical as­ pects of induction and analogy; their consistency and their relationship on inference. In contrast with (D.1) and (1.1), each inference rule of (1.2), (A.1), and (A.2) has at least one critical logical defect. The former, each o.f (D.1) and (1.1), preserves consistency (i.e., only con­ Sistent theorems are inferred from consistent axioms) while the latter, each of (1.2), (A.1), and (A.2) does not: In spite of this fact, the latter inference rules seem to ?e natural to our common sense. For example, when we mfer a general rule from individual observations where knowledge as (1.1.2) comes from? Can we directly rec­ ognize the knowledge from observations? Although we may recognize knowledge such as (1.2.2) from our envi­ ronments, we do not recognize such an (1.1.2) at least from our daily life. From our view, it is the heart of our empirical induction to infer (1.1.2) from (1.2.1) and (1.2.2), and it is the process which we should investigate and formalize.

Conjectural reasoning which always brings a consis­ tent conclusion at present but possibly inconsistent in the future immediately implies that it is non-monotonic. Analogy and empirical induction often bring us con­ clusions turned to be wrong after we know more. In such cases, their conclusions are invalidated in our belief. This non-monotonicity is quite cqmmon to our reason­ ing. McCarthy introduced circumscription[McCarthy, 1980] for the purpose of formalizing non-monotonicity in common-sense reasoning. Circumscription of a predi­ cate P makes its extension minimized; anything is not P unless it is stated P by given axioms. Helft[Helft, 1988] used minimization of all predicates to formalize induc­ tive reasoning. By means of minimizing all predicates, although preferably inferred when P(a) A S(a), a gen­ eralization \lx(S(x) ::) P(x)) is no more inferred when P(a) A S(a) A S(b) that normally happens whenever we want to deduce a useful conclusion from the general­ ization. Inductive reasoning (and analogical reasoning) should be naturally interpreted as a particular expansion of the extension of a predicate rather than minimization. Our approach follows circumscription just for formaliza­ tion of non-monotonicity, but does not inherit the idea of minimality.

Relation between induction and analogy is another point to be investigated. Analogy (A.2) can be viewed as a two-step argument[Davies and Russell, 1987]; \lx(S(x) ::) P(x)) by a single-instance induction from S(b) in (A.2.2) and P(b) in (A.2.1), and then by deduc­ tion with S(t) in (A.2.2), we obtain (A.2.3). A similar idea is suggested in [Peirce, 1932; Mostow, 1983]. Un­ like to their views, we consider there is a common infer­ ential structure behind induction (1.2), analogy (A.1), and (A.2). Analogy includes a projection of informa­ tion from a similar known object to an unknown object. Induction similarly includes a projection of information from known previous cases. We discuss more about this common denominator in the next section. We formal­ ize this type of projection based on a transitive relation between objects. We call the formalization preduction because the introduction of preduction allows empirical induction and analogy: to be broken into a stable part, (I.l) and (D.1), and the preceding more conjectural part corresponding to the preduction (Figure 1).

Formalizing consistent preduction has at least two significant points. One is (of course) to allow us to use empirical induction and analogy free from inconsis­ tency. If consistency of preduction guaranteed, because of consistency of deduction and mathematical induction, the whole processes of empirical induction and analogy would become consistent.

The other is to bring us a better understanding of logical aspects of induction and analogy by stepping into their insides. Their inferences are reduced into two clear pieces; a common denominator, preduction, and each of their residues, mathematical induction and deduction that are well investigated. It allows us to focus on an unexplored central part of thinking related to induction and analogy by removing differential and well-explored parts from them.

This paper is organized as follows. Section 2 gives a formal view about the common denominator between induction and analogy. Section 3 proposes a form of preduction. Section 4 shows its generality by applying the form to various examples over induction and analogy. Section 5 proposes its model theory and shows that the form preserves consistency. Section 6 concludes this.

2 Common Denominator

Figure 2 illustrates two typical processes by analogy and by induction from another point of view than their log­ ical aspects. In analogical reasoning, an unknown prop­ erty P' about a target case is inferred by finding, based on a property s' of the target case, a base case which satisfies a corresponding property S to S', and by pro­ jecting a relevant base case property P to the target case. In inductive reasoning, we see a similar inference which is made possible by a result of induction rather than induction itself. By a result of induction, an unknown attribute value Vkt1 of an example indexed by Xk+ 1 be­ comes possible to e inferred based on the known value vk of its preceding example indexed by xk. (e.g., the value, Vk+l> of factorial of (k + 1), Xk+1 ' is computed from the preceding case, the value of factorial of k.) To get the unknown value Vk+l> we may have to trace back (recursively) to some example indexed by x0 whose value is known (e.g., the value of factorial of 0 is 1). Let us identify this known example in induction with a base case in analogy, and the unknown example indexed by Xk+1 with a target case. Then, although the number of repetition of inference is different, we can identify these structures where information is mapped from a base case into a target case.

Now, in order to formalize a more general common structure related to both analogy and induction, we ab­ stract these in two ways: number of repetition and parameters of their cases/examples. Let us represent inner­ relation among the n-parameters inside a case/example by an n-ary predicate P (n ~ 1), and their parameters by a tuple of n-arguments of P. In this representation, we do not distinguish a parameter for an index from a parameter for a value. This abstraction is needed to capture an inference about a concept which is naturally represented by a predicate without parameter for value (e.g., a predicate, "Is a number"). Let us denote outer­ relation between the par~meters in a case/example and the parameters in a preceding case/example by a 2 · n­ ary predicate .R .. Then, letting x and y be n-tuples of variables, the following sentence absorbs the number of repetition,

which we call the R-expansile sentence of P. This im­ plies that, if there is a P-thing, any entities which relate to it by R are also P-things. That is, by this sentence the property P will be (recursively) projected from a case/example known to be P to the unknown successive ·case/example.

Returning to the schemas in Table 1, let us see how this sentence relates with them. If we substitute y = s( x) for xRy, we get

which is equivalent to (1.1.2) by the nature of =, and if x,...., y and S(x) 1\ S(y) for xRy, we get

with which (A.1.3) and (A.2.3) can be deduced from their premises, respectively. Now let us assume an infer­ ential schema, preduction, which can conclude each R­ expansile sentence of (i), (ii), and (iii) from the premises of (1.2), (A.1), and (A.2), respectively. Then by this new schema, Induction (1.2) can be broken down into two steps; 1} from the premises (1.2.1) and (1.2.2), con­ clude the expansile sentence (i) by preduction, and 2} from (1.2.1) and (i), conclude (1.2.3) by Induction (I.l). Each of Analogy (A.1) and (A.2), on the other hand, becomes a derivative rule from preduction and deduc­ tion; 1} from the premises, conclude each R-expansile sentence (ii)/(iii) by preduction, and 2) from (ii)/(iii) together with their premises, conclude (A.l.3)/(A.2.3) by deduction, respectively. Thus, preduction is a com­ mon inference of (1.2), (A.1), and (A.2) (Figure 1).

3 Preduction

Preduction is a formal representation of the following concept: "If every entity known to be P can be traced back to some roots of P along a relation R, then the unknown descendants of their roots will satisfy P simi­ larly." Here, a set of roots corresponds to a set which includes a base case/an example Xo in the previous sec­ tion.

Before describing a form of the concept, we introduce some terminology. For a transitive relation -< and a pair of objects e and e', when e -< e', we say e is an ancestor of e' and e' is a descendant of e with respect to -<. An n-ary predicate U is generally expressed by )..xQ, where x is a tuple of n object variables, Q is a sentence in which no object variables except variables in x occur free.

For a 2 ·n-ary predicate .R. and . -<R ., let T1·(R; -<R) express that -<R is the transitive closure of R, that is, -<R is the minimal predicate which satisfies

Let P be an n-ary predicate symbol and A a first order sentence. Let . -< . be a 2 · n-ary transitive predicate in which P does not occ~r. The preductive sentence of P on -< in A, written Pd(A; P; -<), is

where A[)..x(<l>(x)V3z(<l>(z)l\z-< x))] expresses the result of substituting the predicate h( <I>( x) V 3z( <I>( z) 1\ z -< x)) for all occurrences of P in A.

In the left side of the implication of the preductive sentence, a predicate variable <I> represents a concept of root of P-things with respect to a relation -<. The first conjunct expresses that <I> is a sub-class of P. The second conjunct confirms that there is an entity of <I> that is an ancestor (with respect to -<) of an entity of P. The third conjunct expresses that P can be interpreted as a set of entities who have their roots in <I>. If a predicate <I> satisfies all these three conditions, Pd(A; P; -<) tells us every -<-descendants of an entity satisfying P satisfies P similarly.

Let P do not occur in R. Then, the pred·uction of P on R from A is the sentence,

denoted by Preduct(A; P; R), where -<R is a new predi­ cate symbol which does not occur in A.

Preduction is guaranteed to maintain consistency, which will be proved in Section 5. The following prop­ erties are straightforward and used in the next section. The conclusion of a preductive sentence, Vx,y(P(x) 1\ x -<R y :J P(y)), implies the R-expansile sentence of P, Vx, y(P(x) 1\ xRy :J P(y)), because ofTr(R; -<R)· Tr(R; -<R) can be expressed formally by a second order sentence which circumscribes -<R alone in the above two sentences ofTr(R; -<R) [McCarthy, 1980]. If R is transi­ tive, the transitive closure of R is R itself. Thus, in this case Preduct(A; P; R) is simplified to A 1\ Vx, y(xRy = X -<R y) 1\ Pd(A; P; R).

4 Examples: Induction and Analogy

In the following examples, we implicitly use a classical logic with equality axioms and with the unique name axioms [Clark, 1978] which tells us that different ground terms denote different objects (or you may always add these axioms to A; in these examples) .

4.1 Induction

Example 1. Let At and S be

and

Let -<s denote the transitive closure of S by Tr(S; -<s ). Then, Pd(At; N; -<s) is

The sentence scoped by 3<I>, if substituted <I>( x) = x :::: 0 ("xis a root iff x is 0"), becomes

and follows from At 1\ T1·( S; -<s). Thus, as the left side of the implication of Pd(A1 ; N; -<s) hold, the preduction of P on S from At concludes

and, by ilx, y(y:::: s(x) ::l x -<s y) (in T1·(S; -<s)) and by the equality axioms,

As this example shows, the preduction from "0 and 2 are natural numbers" gives "the successor of each natural number is a natural number" and thus, N(1), N(3), · · · are also theorems of the preduction . It shows the pre­ duction expands the extension of N.

The preduction is non-monotonic with respect. to A, that is, the theorems of some preduction from A does not always include the theorems of the preduction from a sub-set theory of A. The following shows an example where a theorem of a preduction from a sub-set At of .4.2 is not the theorem from A2.

Example 2 . Let A. 2 = Ati\·N(s(O)) and Sis the same as in Example 1. Pd(A. 2 ; N; -<s) is the result obtained just by attaching the following sentence to the left side of the implication of Pd(A1 ; N; -<s) in the scope of 3<I>;

which, by distribution of the negation, becomes

This second conjunct telling us "any less than 1 does not satisfy <I>" . This contradicts ( <I>(O) V 3z( <I>( z) 1\ z -<s 0)) in the left side of the implication of Pd(At ; N; S) by the transitivity of -<s. Thus, for <I>, no predicate satisfies the left side of the implication of Pd(A2 ; N; S), and Pd(A2 ; N; S) is seen to be tautology.

Example 3. In Inductive Logic Programming (ILP), the inference of the following form is most commonly used in generalizing a clause (absorption [Muf!?gleton, 1991], saturation [Rouveirol and Puget, 1990J, fold­ ing [Lu and Arima, 1996], and etc.):

where P is a predicate symbol and o:, f3 are conjunctions of literals. Unfortunately, this rule also does not main­ tain consistency. Thus, to check consistency is always necessary to discard an inconsistent conclusion produced by this rule. (It corresponds to over-generalization in ILP where a negative example e of P is covered by the newly obtained generalized clause H, that is, A f- ·P( e) but A, H f- P(e).) The preduction can work as a consis­ tent version of this rule.

Proposition 1 Let P do not appear in f3. Let xBy be f3(x) 1\ f3(y). Then the following is a theorem of Preduct(A; P; B):

Proof. B is transitive. Thus, Pd(A; P; B) is a theorem of Preduct(A; P; B). Assuming ilx(o:(x) ::l P(x)), ilx(o:(x) ::l f3(x)), and 3xo:(x), it is sufficient to prove that A[f3] ::l ilx(f3(x) ::l P(x)) is a theorem of Pd(A; P;B).

Consider a preduct.ive sentence Pd(A; P; B) where o: substituted for <I>. The first condition of the sentence is just the same as the first assumption ilx(o:(x) ::l P(x)). The second condition,

is equivalent to 3x(o:(x) 1\ f3(x)), which follows from the second and the third assumptions. The third condition of the preductive sentence becomes simply A[/3] under the second and the third assumptions, because

Consequently, the conditions of the preductive sentence is equivalent to A[f3]. Also, these assumptions give

which simplifies the conclusion of the preductive sentence ilx, y(P(x) 1\ f3(x) 1\ f3(y) ::l P(y)) to ilx(f3(x) ::l P(x)).

As Proposition 1 shows, the preduction proposes two more conditions than the two premises of Induction(1.3) . The former condition 3xo:( x) relates to the justification of induction (1.3) . If 3xo:( x) is not required like Induc­ tion(1.3), it allows the case A f- ·3xo:(x), where (1.3.1) and (1.3.2) hold always, because these preconditions are always false . Thus Induction(1.3) yields, no matter what f3 is, ilx(f3(x) ::l P(x)). There would be no reason to jus­ tify such an inference. The latter condition keeps con­ sistency. This will be shown in Theorem 2.

4.2 Analogy

A consistent version of Analogy (A.2) is also deduced from a preduction. In the next proposition, as in (A.2), S corresponds to similarity and P a projected property by the similarity.

Proposition 2 Let P do not appear in S. Let xCy be S(x) 1\ S(y). Then the following is a theorem of Preduct(A; P; C):

Proof. Cis transitive. Thus, Pd(A; P; C) is a theorem. Assuming P( v) 1\ S( v), consider the sentence obtained by substituting ..\x(x = v) for <I> in Pd(A; P; C). The first condition Vx( x = v :::> P( x)) of the sentence is satisfied because P(v), and the second condition 3y(S(v)I\S(y) 1\ P(y)) is satisfied because of v as y. The third condition becomes simply A[S], because (x = v V vCx) = S(x) from S( v). The conclusion of the preductive sentence is simplified to Vx(S(x) :::> P(x)) because 3x(P(x) 1\ S(x)) from the assumption. Consequently, P1·educt(A; P; C) 1\ P(v) 1\ S(v) gives

which proves the proposition.

Example 4. Let A3 be

human(t) 1\ mortal( b) 1\ human(b).

We define C by their similarity, human(= S), that is,

Then, as Proposition 2 shows, Pred11ct(A3; mortal; C) yields

Substituted the target case b for z, the left, side of the implication is

1\human(t) 1\ human(b) 1\ human(b)

which follows from A3. Thus, Preduct(A3; mortal; C) yields

which tells us that every human is mortal. Therefore, the preduct ion of m01·tal on C can derive an analogical conclusion mortal(t) by the fact human(t).

Attempts to understand analogical reasoning are rig­ orously continued in Philosophy, Cognitive Science, and Artificial Intelligence[Helman, 1988]. The schemas (A.1) and (A.2) are too simple description of the process of analogy. Davies and Russell clearly argue that there should be more premises in their schemas by posing the following example: we will not infer that one (t) of two cars of the same model (S) is painted red (P) just because the other (b) is painted red, although we may guess a price ( P') of the one just because the other same model car is valued at the price (?')[Davies and Russell, 1987] . That is, we prefer the latter inference, (P'(t) just for P'(b) 1\ S(b) 1\ S(t)) than the former (P(t) just for P(b) 1\ S(b) 1\ S(t)) by the difference of the properties (P and P') although there is no difference in applying the schemas to the cases. The missing premise should be weaker than Vx(S(x) :::> P(x)), because, if otherwise, S(t) is enough for the conclusion P(t) and thus infor­ mation about the base case (b) becomes unnecessary. Davies and Russell proposed the following premise :

which allows a particular pair of s (as a similarity) and p (as a projected property) to work in analogical reasoning based on a base case ( x ). (e.g., I; = Mode/ and II = Price) . They call this sentence determination rule.

Although weaker than Vx(S(x) :::> P(x)), this preduc­ tion is not an answer for the query of the missing premise in analogical schema. Instead, preduction provides a consistent way to infer determination itself. Given a cer­ tain triplet, a sentence A, a predicate P and a relat ion R, the preduction can yield the determination rule as a theorem. This would be enough by showing the fact that the determination rule is an expansile sentence.

Example 5. In the R-expansile sentence, substituting Ax,pll(x,p) for P, Ax ,p, y,p'3s(I:(x, s)I\E(y, s)l\p = p'), for R, {x,p} for x and {y,p'} for y results in

by the nature of=, which is arranged to the determina­ tion rule.

5 Model Theory

Let U and r.p be sets such that r.p ~ U. Let -< be a transitive relation on U. We say a set tf; is the expo.ns'ile set of r.p with respect to -< if tf; is the union of r.p with the (ascending) segment by r.p with respect to -<, that is,

For a predicate P and a structure M, we write P''vi for the extension of P in M. Let M and N be structures. For a predicate P and a predicate R in which P does not occur , we say that M is an R-expans'ile structure of N in P, if i) M and N have the same universe , ii) all other predicate symbols and function symbols besides P have the same extensions in M and N (thus, RM = RAf), iii) but, for some subset ¢ of pAf such that an entity e E ¢ and an entity e' E pAf satisfy e...<Re', pM is the · expansile set of¢ with respect to -<·R, where -<:R is the transitive closure of RAf .

Let M be a model of A. We say that M is a preductive model of A in P on R, if i) any R-expansile structure of M is not a model of A, or otherwise ii) M is an R­ expansile structure of a model of A.

Theorem 1 We write A I=~ f if a sentence f is true in all preductive models of A in P on R. Then,

Proof. Let M be a preductive model of A in P on R. Let <p be a predicate which,· for the transitive clo­ sure -<R of R, satisfies the left side of the implication of Pd(A; P; -<R) when substituted for <I>. Then the exten­ sion of <p is a subset of the extension of P and includes an entity which is an ancestor of an ent ity of P with re­ spect to -<R, and its expansile set with respect to -<R is an alternative extension of P. Thus, there is a model of A that is an R-expansile structure of M. It implies that M should also be an R-expansile structure of a model of A by the definition of the.preductive model. If the right side of Pd(A; P; R) were not true on M, there would exist a pair of entities, (e1 , e2 ), such that they satisfies Rand that e 1 is an entity of P but e2 is not of P. This would cont radict that M is an R-expansile structure.

Theorem 2 (consistency): A predicate P does not oc­ cur in a predicate R. If A is consistent, the preductive sentence P1·educt(A; P; R) is consistent.

Proof. Assume that A is consistent but that ?reduct( A; P; R) is inconsistent. A 1\ T1·(R; -<R) is con­ sistent because T1·( R; -<R) just defines a new predicate -<.R to be the transitive closure of R. By the assumption, for any model N of AI\T1·(R; -<R), N I= -.Pd(A; P; -<R)­ Thus, because the left side of Pd(A; P; -<R) is true on N, there is a predictive model of AAT1·(R; -<R) that is an R­ expansile structure of .N. Let this be M. Now, by the as­ sumption, the negat ion of the right side of Pd(A; P; -<R) is also true on M , that is,

M I= 3x, y(P(x) 1\ x -<R y 1\ -.P(y)) .

M agrees with Non all symbols (including R and -<R) except P and, on P , agrees with the expansile set of the extension of <I> on ;V with respect to -<R- Therefore, letting <I>N = ¢'\A. ,

M I= 3x , y((¢>(x) V 3z(¢(z) 1\ z -<R x)) 1\x -<.R y 1\ (-.q'>(y) 1\ -.3z(¢(z) 1\ z -<R y))). M I= 3x , y((¢(x)l\x -<R yV3z(,P(z)l\z -<R xl\x -<R y)) l\-.3z(¢>( z) 1\ z -<R y)) .

The both disjuncts in the first conjunct contradict the second conjunct by the transitivity of -<R- Thus, there is no such a model M. This contradicts the assumption.

6 Conclusion

This paper proposes a common form of analogy and (em­ pirical) induction . The form, called preduction, preserves consistency and brings a view that analogy and induc­ tion come from the same type of inference and diverge depending on types of sequent inference, deduction and mathematical induction, respectively. The generality of this form is verified by its broad application ranging over analogy and induction in the logical approach of artifi­ cial intelligence. Although the form will not contribute directly to a design of a general inference machine, we hope that this promotes us to devise it by better under­ standing logical aspects of analogy and induction .

Acknowledgments

I would like to thank Norman Foo, his research members and Takeshi Ohtani for their helpful comments.