A Learning System Able to Synthesize Arithmetical Functions
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
- EVALUATION
- If the example is compatible, it is added as a positive example to the clause which accepted it and the process stops
- If not the CATCHING heuristic is used
- 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
- Try SUBSUMPTION, then do SIMPLIFICATION and stop
- for a predicate
I. EVALUATION
- If the example is compatible add it to the clause. If there is no subhierarchy, then stop
- If not, do CATCHING
- Then do REMARKS
- 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
- Try UNFOLDING
- If the clause is not locked, LOCK it by CONS TANT function, try SUBSUMPTION, SIMPLIFICATION and stop
- 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.
@inproceedings{ijcai1979p172,
title = {A Learning System Able to Synthesize Arithmetical Functions},
author = {Schyn, Francois and Guiho, Gerard},
booktitle = {Proceedings of the Sixth International Joint Conference on
Artificial Intelligence, {IJCAI-79}},
publisher = {International Joint Conferences on Artificial Intelligence},
editor = {Bruce G. Buchanan},
year = {1979},
month = {8},
url = {https://ijcai.org/proceedings/1979/172},
}
TY - CPAPER TI - A Learning System Able to Synthesize Arithmetical Functions AU - Schyn, Francois AU - Guiho, Gerard T2 - Proceedings of the Sixth International Joint Conference on Artificial Intelligence, IJCAI-79 PB - International Joint Conferences on Artificial Intelligence PY - 1979 UR - https://ijcai.org/proceedings/1979/172 ER -Copied
Machine-readable versions of this paper, for tools and AI agents:
Welcome
Future Conferences
AI Journal Division
IJCAI Proceedings
About IJCAI
IJCAI Awards