Inductive Inference on the Base of Fixed Point Theory

1 . I HTRODUCT I OH

Inductive reasoning is an important way to generate knowleQ;je from the propositions reflecting facts e.g. propositions describino experimentel results. The knowled;)e to be extracted from factual propositions or data is to provide a general characterization of these factual data. This characterization may be a law or a reoularity which describes some besic interrelation emong factuel deta (cf.(Finn and Gergely 1984), (Gergely and Szabo 1986)). The process of discovering this regularity is but a learning process which aims to acquisit new declarative knowledge (cf.(Carbonell, Michalski and Mitchell 1983)). This new declarative knowledge may be also in the form of a general rule generated from examples that correspond to factual data (cf.(Angluin and Smith 1983)). Therefore the subject of this paper is connected with the field of machine learning and inductive inference which belong to the mainstream of AI research. As it is known (e.g. from (Angluin and Smith 1983)) the majority of inductive methods deflnes the regularity in question as a recursive function. From the point of view of logic this means that these methods use the standard model of arithmetics as to model the reality and date obtained ebout the latter end they select one recursive function and identify the regularity with this function. However this approach is not the best if we aim to derive new knowled;)e. Therefore we think about such an approach which approximate the regularity step by step without the preconception of recursivity. The selected recursive function is a new one within the standard model of arithmetics. To have it as a part of our knowledge it should be defined by the use of a formal languaoe, i.e. the regulerity should be defined by axioms obt!lined during the inductive procedure. These axioms already extend our knowledge supposed also

to be axiomatically oiven.

A definition is of the form R(x) .. lf'(x) where R is the new

symbol to be defined and 'f is the deflning formula. If If' doesn't relation lilesn't hold in a given situation then even this has information content for u~. Therefore we need a fixed point theory which allows to work also with negation.

We develop such a theory in the next section. The inductive inference method of building up appropriate fixed point equation system as hypothesis is given in Section 3. The defining formulas in this equation system will use only bounded quantifiers. Note that this is a subcase or the existentially closed defining formulas. Talcing into account the fremeworlc of recur~ive function theory we note that ell primitive recursive relations can be defined by the formulas of the considered case.( see (Gergely and Szabo 1986) ). for the majority of problems with practical interest the relations to be found can be defined by such a hypothetical implicit definition. An example is given in Section 4.

2. QUASI EOUATIOH SYSTEMS

Ue use a first order language of a given alphabet (si·i larity type) ~ and a given constructive 1odel by ·hich ·e interpret the factual data. The given si·i larity type is ext ended by ne· sy·bo Is ·h i ch ·e correspond to the obtained solution of the hypothetical fixed point equation.

For the sake of si1pl icity, further on, ·e use the language of arith·etics ·hich contains ho binary reI at ion sy·bo Is equa I i ty C· ) and "less then" (<) and t·o constant sy·bols 0 and 1 and t·hree bInary f unctl on sy1bo Is +, · and exponant i on t · The standard ·ode I Jl of ar i t h1et i cs i s cons i de red as the requ i red constructive 1odel ·here 1e denote the corresponding functions and relations si·i larly. Ue also olio· the usage of other recursive functions and relations on natural nu1bers H (·{0,1,2,_}), Let us see ho· ne· reI at i on sy1bo Ia can be i nt roduced i nt o the signature. Let Rt,-·Rn denote ne· relation sy1bols of arlty k 1 ,_,kn, respectively. Ue ·rite ~(x) to indicate that the free variables of ~ are a·ong x·x 1 ,_,x 1 . If ·e ·rite ~ ·ithout x then it 1eans that it has no free

variables .

R for1ula S(x,y) is called finite bounding f or·u I a · . r . t. x i t for any f i xed b ( H1 the set { a I Jl· 6(x,y)[a,b]} Is finite. Let BF be a fixed recursive set of finite bounding for·ulas. Ue Introduce shorthands

3x[&(x,y)]'f(x,y) for 3x(&(x,y) &«f(x,y)) Vx[& (x,y)] 'f (x,y) for Vx(6) (x,y) --lf'(x,y)) where we suppose that G(x,y) E BF, I.e. we bound the do·a In of quant I f I cat I on. Therefore further on ·e use the notations 3x[S(x,y)] and Vx[&(x,y)] as quantifiers and call the· bounded quantifiers .

DEF I HI T I OH I.

• A, The set t. 0 (At , _,An) is the least set of

for1ulas that

• (i) contains ato1ic for1ulos a·ong ·hich rela­ tion sy1bols R 1 , _,An to be defined can also occur;
• (li) Is closed under connective &,V,~;
• (Ill) Is closed under bounded quantifiers 3x[$(x,y)] and Vx[&(x,y)] for any &(x,y) E BF .
• 6, The set ~I (R 1 ,_,Rn) ( It (Rt , _,Rn) is
• the least set of for1ulos that
• (i) contains t. 0 (A 1 , _,An) as subset;
• (ii) is closed under connectives &, V;
• (iii) is closed under bounded quantifiers;
• ( i v) is c I osed under existent i a I ( un i verso I )
• quanti f i er .

A total solution of a for1ula "2EI 1 CA 1 , _,Rn) Is said to be a set of Interpretations 9 1 ,_,,n of R 1 , _,Rn In Jl for which (Jl, t,, _, sn>..,. '1 holds. Let TS("Z) be the set of all total

so I ut i on of "'l .

The con f i gurat ion space of A 1 , _,An denoted as CS(A 1 , _,An) consist of all pairs (i,a), where 1=1 , _,n and aEHk,, Hote that CS(Rt , _,Rn) prov ides all the possible interpretations of

the relation sy·bols R 1 , _,Rn on H. Let

uo·(,) :={(i,a)ECS(Al, _,An) I

for all <!,,-,gn)ersrn c:a,,,, _ ,~n)to,k "?.} Let UO("l): -=UD+("'l )vUD-("l) denote the ·e 11-de­ fined part of CS(A 1 , _,Rn) defined by 1.

THEOREM 1. There exist an algorlth· which, for any for·ula "/EI1(R1,_,Rn), ter·inates if T5("2)·.8, other1ise it enu·erates uo+("1) and uo-c~>.

Let ~i(zi), 'fiCzi) E I 1 (R 1 ,_,Rn), ·here zi are k1 long variable tuples. R1 (z:J) +- lf1 (z: 1 ) .,RJ(z:J) \' '~"J(ZJ) Rn(z:o) +- 'fln(z:o) .. Rn(z:o) 4- lfn(z:o)

Is said to be a auasl equation syste·. Throughout this chapter let S denote a quasi equat I on syst e· . Ue cons 1 der 1 t as the conjunction of the l·pllcatlons, where each z. I Ia · bounded by a un i versa I quant i f i er , So C' E t 11(R1,-·Rn) since lf+-'f=lfv .. f and .. 3x'f·V;'f',

Let 'f<x) E I1(R1,-·Rn) ·ith x is · tuple and atH' be fixed. An ele·ent (j,b) of CS(R 1 ,_,Rn) can be influencing for Cf[a] denoted as (l~b)EIH(f(x),a) iff b is such an ele·ent of H' that Rj(b) takes part In the deter·lnatlon of the truthva I ue of the for·u I a Cf[a/x],

DEEIHITJOH 2. For a given quasi equation ayate· ~ the dependency relation ~ over CS(R1,-·Rn) Ia defined oa follo·a: -

(l,a)>--g (j,b). iff (j,b)c: IH('fi(zi),a) or (j ,b)£ IH(<fi (zi) ,a).

DEE I H I T! OH 3 . The quas i equati on syste· S ia reduced to on irreflexive partial ordering >- over CS(R 1 , _, Rn) iff for a 11 (l,a),(j,b)E CS(RI,-·Rn) If (l,a)>"z(J,b) then (i,a)~(j,b).

The ordering >-- ollo·s us not to define the truthvalue of R; (a) whi Je defining the truthvalue of RJ(b), if (i,a)~(j.b).

Ue also need that the for·ulas Cf ( ) d i z; an '#j(zl) (i·l,_,n) of :=: not be true at the ao·e t l·e I . e . <fj ( z; ) and 'fl ( z i ) are to be fu j unct .

THEOREM 2. I f a quos i equation ayate· S i a reduced 1.r.t. an irreflexive partial ordering and it satisfies the disjunction property, then TS(2).-0.

THEOREM 3. There exists an w -type ·ell-ordering >- over CS(R 1 ,_,Rn) 1hich is explicitly definable by an D- 0 -for·ula and for .1hich, for any for·ula "'EI 1 (R 1 ,_,Rn), a quasi equation syste· Scan be constructed that is reduced 1 . r . t. t h i s ~ and i t sot i sf i es the disjunction condition, such that if TS("l).-0 then TS( "2 )=TS( 2.).

Let Q 0 CR 1 ,_,Rn) denote the set of quasi equation syste·s which are reduced w.r.t. so·e irreflexive partial ordering~ and the for·ulas 'fi(zi),fi(zi) of which belong to D. 0 (R1,-·Rn>· Since the i·plicotiona Ri(zi) +- <tj(zi) and .. Ri(zi)~ .,<fi(zi) can be written in the for· of Ri(zi).,..'fi(zi), it is called equivalent lYP! equation. EQ 0 (R 1 ,_,Rn) denotes the set of those equation syste·s of Q 0 (Rt,-·Rn) which cons i at on I y of equ i va I ent type equot i ons and are reduced 1.r.t. so·e ·ell-founded ordering.

THEOREM~. If SEEQ 0 (Rt,-·Rn) then it has one solution exactly, i.e. card(TS(2))=1.

THEOREM 5. If S' ~ Q 0 (R 1 ,_,Rn) and the ordering >- w.r.t. which it Is reduced is recursive and well-founded, then U0+(2.) and uo-(~) are recursive sets.

DEFIHIIIOH ~. An irreflexive well-founded ordering >- over CS(R1, _, Rn) is said to be natural iff for all i,jzl,_,n one of the fol lo1ing conditions holds:

If the ordering >- is natural then iMtead of Q 0 (R 1 ,_,Rn) and EQ 0 (R 1 ,_,Rn) we write HQ 0 (Rt,-·Rn) and HEQ 0 (R 1 ,_,Rn), respectively.

If we intend to deteraine the properties of the observed rei at ions R 1 ,_,Rn, then we also need soae auxi I iary relations Rn+I· ·-·Rn+d defined by equivalent type equations, where the observed relation syabols cannot occure. Haaely, we have the following, so called, generative quasi equation systea

DEFIHITIOH 5. A generative quasi equation systea is said to be natural (denoted their set as HGQ 0 (Rt, - ·Rn)) if it is reduced w.r.t. an irreflexiv ordering>- for which ( i ,a)>- (j ,b) iff i,j E {t, _,n} and (i,a)>-.....,(j,b);

or i,j E {n+l,_,n+d} and (i,a)>-'(j,b);

or i E {I , _,n} and j E; {n+l ,_,n+d) for a I I ( i , a) , ( j , b) € CS ( R 1 , -, Rn+d) , where >-..., is an ~-type ordering on CS(R 1 ,_,Rn) and 'r! is a natural ordering on CS(Rn+I·-·Rn+d),

THEOREM 6. For any 2E EHQ 0 (R 1 ,-,Rn) there exists a 2* E- HGQ 0 (R 1 ,_,R 1 ) such that their solutions for R 1 ,_,R 1 are the saae, where lin.

3.1HDUCTIUE IHFEREHCE ALGORITHM

Let us consider now the theory of inductive i n f erence, espec i a I I y how we d i scover properties . fro· observations. Ue generate hypotheses in the fora of natural generative quasi equation syste1s corresponding to the given set of observations. For si1pl icity's sake we give a 1ethod for the recognition of only one observed relation now. It can be generalized for aore easily.

Let function )�:H·~ H 1 be the data presentation i .e. )G describes a sequence of observations, where H+ denotes the set of all positive integers. More precise I y, i f we want to recognize an 1-ary reI at ion R, then we get inforaation R["o] at the n-th step, where R[?<n]:·{<?<(I),R(?<(I))>; _;<?<(n),R("(n))>}.

Since the solution of the natural quasi equations for the auxiliary relations are unique, so they are enuaerable, therefore instead of giving the defining equations for auxilary relations it is sufficient to refer to thea by naaes of a fixed encoding. Let <f> be a function, enuaerating all the foraulas of ~ 0 (R) with free variable z, and let ~(i) denote the 1-th eleaent of the enu1erat ion. However, If we have soae knowledge In the fora of quasi equations with ~ 0 (R) for1ulas on the right hand side concerning the observed relation, then we take these foraulas at the beginning of the enuaerat ion. Of course, the enuaerat ed f orau I as are coaposed of encoded naaes of the auxi I iary relations and of the syabo I R of the observed reI at ion, ·here, i f R(t) appears in a foraula, then t is bounded by z, i n order to sat i sf y the cond i t i on of the

reduction .

Let ·. · denote the concatenation of finite sequence. Let the generated hypothesis for infor1ation R["o) be characterized by Hn wh i ch i s a f i n i t e sequence of subhypot heses, lOre exactly Hn = (a 1 n,b 1 n),_,(akn·bkn), where n II a in E H and bin~{O, I}. Hn corresponds to the following defining quasi equations:

Let 2(Hn) denote this quasi equation syste1 to Hn . Here (ain,bin) is a subhypothesis ·here ain refers to cp(a1n) and ~In detertlnes the equations there this fortula occurs positively. The occurences of negated forts of these fortulas quarantee the ful flltent of the criterion of disjunctivness.

Let T and F denote "true· and "false" respectively.

Ue say that H·(a 1 ,~ 1 )._.(ak,~k) proyldes y for x, If for all 9~TF(Z(H)) hold ,g(x)·yl ·here yE{T1F}, Let Fr(H11) denote the left frogtent of H1 of I enght I 1 that Is (at 1 4)1).- ·(a 1 1 4) i) · If i is greater or equal to length of H1 then let Fr(H1i)·H. Let ·e· denote the etpty H i.e. if length of H is 0.

Let Xn:·{)G(i) I 1iiin }. Ue say that H aatchc;r R[X,) on the set M(H1R[X,]) if M(H1R["o])·{xEXn I H provides R(x) for x}; and H does not tatch R["o] on the set ii(HIR["o]) if fi(H, R[Xo])·(X 0 " UD(2(H))) \ M(H, R["o]).

The general ion of hypotheses occurs siti larly to the original enuterat ion tethod· introduced by Gold (Gold 1967). lnfortally:

• 0, Ue start 1ith the eapty hypothesis (or if ·e have sote kno·ledge in the fora of quasi equation syste· 1Ith fortulas fro· ~ 0 (R), then ·e start 1Ith this quasi equation syste· as hypothesis); ·
• 1, Ue do not change hypothesis if provides the result correctly for the next ovservation;
• 21 If ·e have no subhypothesis fro· Hn_ 1 for the next observat i on )(.( n) , then te take the f i rst net i ndex i for ·h i ch Hn-t . ( i , a) i s consistent . 1Ith R["o] for ~·0 or a·t and attach (i,'a) to the end of Hn-ti
• 3 1 I f soae o { the subhypot hes i s of H 0 _ 1 contradict the next observation, then ·e delete the· thi le the rest of Hn contradicts R["o], and ·e repeat this procedure until the resulted hypothesis ·Ill be consistent 1Ith all of the observations.

Ue ·ant that the hypothesis Hn be consistent · i th the observations at every step i . e. if gE.TS(8(Hn)) then s(x) .. R(x) for all x~Xn.

Furthertore, ·e ·ould like that the sequence of the relation sets TS(2(Hn)) converge to the relation to be .recognized.

,., C(H, i) · i II denote the set of rejected or used Indices at the 1-th step and belong to H. For every poss i b l·e hypothesis H and for any i let C(H, i) be etpty at the beginning. This C infinite tatrix ·ill help the backtrack of the procedure.

then let <p(O)·If<z) and <p(1 ):o:f(z) as ·e said.

• So

• 2, If )(.(n) (. UD(8(Hn_ 1 )) then Hn:=Hn_1. (a, a) ·here a=tin{iECnl~a,{0,1} such that Xn= =M(Hn_ 1 .(1 14)), R[)(.n])}

• 3, If )(.(n) E M(Hn_ 1 1 R["o]) then ·e cannot te II 1hlch subhypothesls Is to be blated. So ·e start out to fInd the 1rong subhypot hes Is,

begInnIng the search · i th the 1-st one. Therefore ·e prefer to save the subhypotheses generated earlier. In this ·ay ·e'll obtain H~ ( n-1 n-1) ( n-1 A n-1) n fro· Hn-t= a 1 ,D 1 ,_, al<. ,vk . ore precisely:

Here C~,l ·eons the set of those indices ·hich ·e reject during the generation of H~ up to the i-th step. Ho· ·e attach subhypotheses to end H~ ·hich provide ne· correct results. More exactly:

H 0 : =H~, { if f={ iE H I M(H~, i, R["n] )=Xn}, ·here

H~, 0 :=H~ and for i>O:

H~,i:·H~,i-t·(a,a), ·here

a := ·in{ j£C 0 , 1 13 lJt{O, 1} such that

and let

.....

..

+

and let C(Hn,i-l,n):=(H \ Cn,i)v

+

-

-t

u{xEH I x<a and M(Hn,i-t·<x,O),R[Xy,])"0

- +

and M(Hn,i-t·<x,I),R["n])"0 },

"' + In the end let C(H 0 ,n):=H \ Cn,t·

-4. AH EXAMPLE

Let the date presentetion x be such thet X( I)= I 0 X( 2)=0 o X( 3)=4 end X( 4 )=3. In this order the results of the test of R ere f,T,f,T i.e. we obtain R(l)=f o R(O)=To R(4)=f andR(3)=T. We hBVe to recognize this relation R. Let us BSSume that we hi!Ye knowledge about a property of R in the form of the following fixed point equation:

R(x)- x=O V3y[y!x](R(x-y) & R(x·y))

This is an original positive existential fixed point equation with e bounded quantifier end is e g3Jd exemple to show thet the original fixed point equations often are not informative enough. For example, it is difficult to decide whether R(5) may be T when R( 6 )=F for the above fixed point equetion o while truthvalue of R( 3) influences R( 2) end R( 4) influenceR( 3) e.t.c. However the above fixed point equation can be regarded as e universe! stetement with a bounded quantifier. Therefore it can be eutomaticelly transformed to the following quasi equetion system 8 reduced by usuel ordering <:

This follows the netural way of thinking because this refers to the argument of R less than z. So all the solutions ofE can be generated as infinite peths of the following tree:

Therefore 0 one is able to decide whether a hypothesis is consistent with all the observations or not. It can be shown that TS~ consists of all such relations which - as paths - are in one of the forms of the followings: T 00 o Tn.Foo 0 ( u2n)oo and ( T.F2n)k.Foo o where k,n>O. We remark that the original fixed point theory can determine the least fixed point only.

Let us see how our strategy can recognize relation R when R( z)= 3 x( 3x=z) for all z (this relation belongs to TS(2) ). Now we oo not detll with the encoding of solutions of auxiliary relations of the natural generative quasi equations, because it would take the situation comp heated and it is not necessery in this case. For simplicity's sel<e we BSSume that the enumeretino function' enumerates formulas beginning with the following ones:

Formulas <f> ( 0) end 'PC 1) ere in our knowleQ;JB so H 0 :=(0o 1 ).( 1 ,0).

Let us denote the formulas 'f'( 0) end~ 1) by 'f and '#', respectively.

The first information obtained is R( 1 )·F. In this C8:!e H 1 will be (0 ,1 ).( 1,0).(2,0) i.e.

The next information obtained is R( O)=T. It matches the hypothesis H 1 , therefore H2 :=H 1. The situation is the same in the case of information R( 4)=F. so H 3 :=H 2 .

Observation R( 3)=T ma!(es a change because H 3 Iiles not match R(3)=T, therefore we heve to reject subhypothesis (2,0). Now H;j:=( 0, 1 ).( 1,0 ). Therefore R( 1 )=F, R( 4 )=F end R( 3 )= T ere to be produced. H"4 r=(O, l ).( 1,0).(3,0) provides R( 1 )=Fend R( 4)af, but it Iiles n~t provideR( 3)=T, although it permits it i.e.2CH,4 1 ) OOe8 not define R( 3) well. H4 t=< 0,1 ).( 1,0).( 3,0).( 4,1) will' be I ,.. correct for R( 3) · T too. Therefore H4:· H4 ,2 i.e.:

It would be 1etter if the strategy simplified the right hand side of the quasi equations e.g. it would write (z> 1) insteed of ( x> 1)&( zoo 1 ).

So E( H4) is the following:

R(z)+-(z=O)V(z> 1 )& x(0<2xiZ](R(z-x)V-.R(z-2x)) -.R(z).,.3x[0<2x.!Z]( -.R(z-x)&R(z-2x))V(z·1) It is easy to see that the only solution of ::X H4) is just the relation to be recognized.

CONCLUSION

We heve given an inductive inference method which builds up the implicit definition of the regularity or of the 113neral rule in question in the form of netur!!l gener!!tive fixed point equ~~tion system with bounded quantifiers. It defines the regularity to be rero;Jnized as the solution of the hypothetical quasi equation system which C!!n match in time the increasing set of experiment!! I dirt!!. The sequence of hypotheses generated by the developed inductive inference methocl wm converge on a large class to the rule that 1s to be recognized. The so fer described procedure can discover eech primitive recursive relation provided the basic functions are Acl:ermt~nn functions (cf.( Gergely !!nd Sz8b6 1986)). Therefore the proposed inductive inference procedure is sufficient for practical purposes. Ours is en asymptotic enumeration strategy and therefore it eppeers to be better then the origin!! I enumer!!tion str!!tegies for being more stable. It is able to recognize even certain non-recursive relations 1n asymptotic sense (cf.(Szab6 1986)).