Proceedings

A Learning System Able to Synthesize Arithmetical Functions

Download BibTeX Cite

Proceedings of the Sixth International Joint Conference on Artificial Intelligence. .

© 1979 International Joint Conferences on Artificial Intelligence

Abstract

This paper describes a system able to synthesize functions and predicates from examples taken in an arithmetical domain. Numbers are repr e sented as characters strings. They are not represented as bags as in Lenat or Knapman's works. The representations of functions and predicates are sets of Horn clauses and the synthesis lies in the construction of new clauses or in the debugging of the exis~t ones. The paper describes the concepts which are used in the system and the synthesis process.

Full text extracted automatically from the PDF; figures, tables and equations may differ. The PDF is the version of record.

A LEARNING SYSTEM ABLE TO SYNTHESIZE ARITHMETICAL FUNCTIONS

Fran<;ois SCHYN

Laboratoire de Recherche en Informatique Equipe de Recherche Associee au CNRS "AL KHOWARIZMI" Universite de Paris Sud

91405 - ORSAY (France)

Gerard GUIHO

Laboratoire de Recherche en Informatique Equipe de Recherche Associee au CNRS "AL KHOWARIZMI" Universite de Paris Sud 91405 - ORSAY (France)

This paper describes a system able to synthesize functions and predicates from examples taken in an arithmetical domain. Numbers are represented as characters strings. They are not represented as bags as in Lenat or Knapman's works. The representations of functions and predicates are sets of Horn clauses and the syn­ thesis lies in the construction of new clauses or in the debugging of the exis~t ones. The paper describes the concepts which are used in the system and the syn­ thesis process.

~~~~-~~E~~ : Learning, Horn clauses, Program synthesis

I. INTRODUCTION

Program synthesis from examples have been stud~d quite rece~tly. They can be classified according to the following categories :

  • Systems which construct function from non­ ambiguous and self-contained examples. That means that all the information which is necessary for the synthesis is contained in the example and that there is no ambiguity in the construction of elementaries functions [see fl01 fl 1 , [4l,r5l
  • Systems which are considered as the growing of a knowledge base. The examples do not need to be self-contained or non-ambiguous. That is the case with fJJlrJ J"l, in some sense rs1 , and more recently r6,

Our system belongs to the second category. It is able to construct some recursive concepts (pre­ dicates or functions) as in f81 but uses a more significance and effective representation of num­ bers than rg1 or r61 representation. The repre­ sentation of numbers which is discovered by the system consists in strings of digits rather than bags as a PEANO representation. The concepts of arithmetical operators (Like successor) are then more effective but they are less obvious to infe&

II. TECHNICAL TOOLS OF THE SYSTEM

II. I Functions and predicates representation

Functions a~d predicates are represented as sets of Horn clauses as in First Order Logic. In fact we use an equivalent representation which more accuratly represents a procedural form of clauses.

For instance, if Eq is the Equal predicate, the classical clause

Eq (z,AQc,y)) cEq(F~), B (H6Q , V(y))) A ~1(~, ~~~ Eq ~, V(y)) will be represented by

z+A(x,y)ca+F(z),b+H(x), z+V(y), a+B(b,z), P(b,~

II. 2 Examples

An expert can interact with the system in two different ways.

  • Examples of inputs and of the corresponding output are given to the system as in

2258 + SUC(2257)

NUMBER ( 12 32 9)

  • An input is given to the system with an in­ terrogation on the output

? + SUC(l59)

The system tries to answer correctly. After l"aving been told by the expert if it has succeded, a positive example is generated. If the sysiBn !ives a wrong output, a negative example is then gene­ rated and the expert gives the correct output. For instance let us suppose that the current ans­ wer to the question? + SUC(l59) is 1510. The expert indicates the correc t answer -160- and then both a negative example rx=l59,yll510l and a positive exampl e rx=l59,y=l60l are generated.

As !17 1 and in opposition to [61 , we think that negative examples (which are near-miss in our system) are fundamental for a complete function synthesis and, above all, for predicate syntheas.

II. 3 Memory

There are in fact three memories.

  • A long term memory which contains every clause of the system. They are referred ton<lllles
  • An active memory which is a short term me­ mory. This memory will contain the names of func­ tions or predicates which have been recently learnt or used.
  • A predicate hierarchy which is a concept hierarchy as in r6l. For each new predicate, we try to find a correct position in the hierarchy and in fact we find more than one possibility. The candidate positions are organized in subhie­ rarchies which are also attached to the name of the predicate.

II. 4 Evaluator

Our evaluator is a Prolog like evaluator which includes a sophisticated tool used when the pro­ lag evaluator fails. For instance, during the learning of the successor function, when this learning is incomplete, a Prolog evaluator will

answer "False" with the input 2750+SUC(2749) (carry on successor of 9 has not been encountered yet).

A simple answer "False" is not sufficient for us. since we specially want to know the point where the failure is the most relevant. Such a fa1lure point is unique in a Prolog evaluator but it is not so if we change the order of clauses or terms. We need an evaluator which gives the "best" failure point on all these orders (or one point which is reasonably close to th~ best one). The evaluator we use in the system is described in r12l.

II.S Locking

A clause is locked if paths exist from the inputs (here x and y) to the output (here z) which al­ low to calculate the output. (see r.41).

Often during the learning process, the gener&ed clauses are not locked and a significant part of the system deals with locking of clauses.

Locking of predicates is more frequently used to place the predicate in the hierarchy than to ac­ tually construct the predicate.

11.6 Learning heuristics

This paragraph describes the main heuristics which are used in the learning process. Some of them arc expanding heuri sties, some others deal with n·duction or simplification.

li.h.l ~:ar5hing

Wlwn tlw l'Valuator fails on an example, it gives a claust· whii.eh represents the most relevant fai­ lure. Catching is then a partial copy of that clause. Predicates or functions which are compa­ tible with the example are copied. Predicates which are false in the example become negative in the catching clause. Multiple values are sep~ rated, when a value is out the input domain of a function, a new function is created.

This last action could be considered as an una­ voidable combinatorial explosion but subsumption will reduce it.

II.6.2 Remarks

The "remark" heuristic is used with three elerent:J a clause, an example on this clause and the ac­ tive memory. It is a combinatorial testing of all concepts which are in the active memory, these concepts being tested on all the values induced by the example.

1!.6.3 Unfolding

Our unfolding is the classical one r31. To tnfold a function F (or a predicate) which appears on the right part of a clause is to add to this clause the right part of ·a clause in which F con­ stitutes the left part.

Unfolding is controlled by an example and then the right part of F which is added must be com­ patible with the example.

11.6.4 Locking by constant

Hhen the three preceding heuristics (catching, remarks, unfolding) have failed to lock the clau­ se. A localization process delivers a set of va­ riables which can be replaced by constants.

11.6.5 Simplification

Nl'ar the end of the learning process, many terms become useless, particularly in a recently crea­ ted clause. The objective of the simplification process is to detect these terms and to get rid of them.

1!.6.6 Subsumption r.9J

A clause C is said to subsume a clause D if all the positive examples of D are accepted by C. D can be cancelled and all its positive examples become positive examples of C.

11.7 Learning process

As the heuristics can be greatly changed, many different learning processes are possible. The objective of the newly designed system is to study experimentally these different kinds of heuristics or learning processes. For this rea­ son we are presently designing a new version of the system which will allow a more flexible chan­ ge of heuristi cs or the learning process. The one which is now described here is very close to the first version of the system. rt3l.

After the expert introduces an example, the sys­ tem works in this manner :

- for a function

  1. EVALUATION
  2. If the example is compatible, it is added as a positive example to the clause which accepted it and the process stops
  3. If not the CATCHING heuristic is used
  4. If the new clause is not LOCKED try REMARKS

5. If the clause if locked now do SUBSUMPTION,

if possible, then SIMPLIFICATION and stop.

6. Try UNFOLDING

7. If the clause is not LOCKED try REMARKS again

8. If the clause is still unlocked, LOCK it by

CONSTANT function

  1. Try SUBSUMPTION, then do SIMPLIFICATION and stop

- for a predicate

I. EVALUATION

  1. If the example is compatible add it to the clause. If there is no subhierarchy, then stop
  2. If not, do CATCHING
  3. Then do REMARKS
  4. If the clause is LOCKED, do an EVALUATION on negative examples. If there is no problem try SUBSUMPTION, SIMPLIFICATION and STOP, else refi­ ne the subhierarchy
  5. Try UNFOLDING
  6. If the clause is not locked, LOCK it by CONS­ TANT function, try SUBSUMPTION, SIMPLIFICATION and stop
  7. Else do an EVALUATION on negative examples, refine the SUBHIEARCHY, try SUBSUMPTION, SIMPLI­ FICATION and stop

III. Some of the experiments

The initial knowledge of the system is composed as characer strings and some basic functions or predicates.

LAST which gives the last character of a string PREF which gives the whole string except the last character

CONC which gives the concatenation of two st~ings NUL which is true is a string is empty

K which is true if the string is a one character string

ST which is always true on strings

Once NB (number) and D (digit) predicates have been learne~ : the following inputs : 1·-SUC(O), 2+SUC( I) ... 9+SUC(8)

123+SUC(I24), 360+SUC(359), 100+SUC(99)

will give as output :

y+SUC(x)cx+O,y+l ,D(x),D(y) cx+8,y 9,D(x) ,D(y) ca+PREF(x,) ,b+LAST(x),c+SUC(b) y+CONC(a,c) ,x+CONC(a,b),a+PREF(y) c+LAST(y),NB(a),D(b),D(c),ID(x),ID(y) rx 2 123, y·l24]
ca+PREF(x),b+LAST(x),c+F(b) ,d+SUC(a), y+CONC(d,c),x+CONC(a,b),d+PREF(y), c+LAST(y),NB(a),NB(d),D(b) ,D(c),ID(x) ID(y), [x·99,y=IOO] [x·359,y=360] ca+PREF(x),d+G(a),c+F(x),y+CONC(d,c) d+PREF(y) ,c+LAST(y) ,NB(d) ,D(c) ,D~;lD(y) rx .. 9,y·10l y+F(x)cx+9,y+O,D(x),D(y) y+�(x)c~0,y+l ,NUL(x),D(y) [x·9,y=O] [x·0,y·ll

A complete description of the example can be fa.md in r14l.

IV. Conclusion

The system which has been described here ~esents some particularities

  • The learning capacity is greatly related to the expert pedagogy. One of our further interests is to study how the modifications or introducticrs of heuristics can more or less allow a sophis­ ticated pedagogy.
  • The concepts which have been synthetized rere are relatively CD!llplex. In Lena!! s work, the concept of addition is simple because addition is a particulari­ sation c% mion m bags Our representation of numbers is IIDre realistic. The synthesis oc the !llccessor fuoc­ tion is constructive mel is noc a restriction of a pre­ viously mown roncept. Ha·,wever the system is able to infer simple concepts and can be used as a powerfull learning-knowledge-base.
Welcome Future Conferences AI Journal Division IJCAI Proceedings About IJCAI IJCAI Awards