Content deleted Content added
m adding links using Google Scholar |
m adding links using Google Scholar |
||
Line 21:
These approaches were split into two phases: first, input-output examples are transformed into non-recursive programs (traces) using a small set of basic operators; second, regularities in the traces are searched for and used to fold them into a recursive program. The main results until the mid 1980s are surveyed by Smith.<ref>{{cite journal|first1=D.R.|last1=Smith|title=The synthesis of LISP programs from examples: a survey|editor1-first=A.W.|editor1-last=Biermann|editor2-first=G.|editor2-last=Guiho|publisher=Macmillan|journal=Automatic program construction techniques|pages=307–324|year=1984}}</ref> Due to limited progress with respect to the range of programs that could be synthesized, research activities decreased significantly in the next decade.
The advent of logic programming brought a new elan but also a new direction in the early 1980s, especially due to the MIS system of Shapiro<ref>{{cite book|first1=E.Y.|last1=Shapiro|title=Algorithmic program debugging|publisher=The MIT Press|year=1983}}</ref> eventually spawning the new field of inductive logic programming (ILP).<ref>{{Cite journal | last1 = Muggleton | first1 = S. | title = Inductive logic programming | doi = 10.1007/BF03037089 | journal = New Generation Computing | volume = 8 | issue = 4 | pages = 295–318 | year = 1991 | pmid = | pmc = }}</ref> The early works of Plotkin,<ref>{{cite journal|first1=Gordon D.|last1=Plotkin|title=A Note on Inductive Generalization|editor1-first=B.|editor1-last=Meltzer|editor2-first=D.|editor2-last=Michie|publisher=Edinburgh University Press|journal=Machine Intelligence|volume=5|pages=153–163|year=1970|url=http://homepages.inf.ed.ac.uk/gdp/publications/MI5_note_ind_gen.pdf}}</ref><ref>{{cite journal|first1=Gordon D.|last1=Plotkin|title=A Further Note on Inductive Generalization|editor1-first=B.|editor1-last=Meltzer|editor2-first=D.|editor2-last=Michie|publisher=Edinburgh University Press|journal=Machine Intelligence|volume=6|pages=101–124|year=1971}}</ref> and his "''relative least general generalization (rlgg)''", had an enormous impact in inductive logic programming. Most of ILP work addresses a wider class of problems, as the focus is not only on recursive logic programs but on machine learning of symbolic hypotheses from logical representations. However, there were some encouraging results on learning recursive Prolog programs such as quicksort from examples together with suitable background knowledge, for example with GOLEM.<ref>{{cite journal|first1=S.H.|last1=Muggleton|first2=C.|last2=Feng|title=Efficient induction of logic programs|publisher=the Japanese Society for AI|journal=Proceedings of the Workshop on Algorithmic Learning Theory|volume=6|pages=368–381|year=1990|url=https://pdfs.semanticscholar.org/6a66/9636e0ada62a0fb444e95435e24fdbdf4dbd.pdf}}</ref> But again, after initial success, the community got disappointed by limited progress about the induction of recursive programs<ref>{{cite journal
|first1=J.R.|last1=Quinlan|first2=R.M.|last2=Cameron-Jones
|title=Avoiding Pitfalls When Learning Recursive Theories
Line 27:
|journal=IJCAI
|pages=1050–1057
|year=1993
|url=https://pdfs.semanticscholar.org/4af3/18f1d267889faec6ecf1be6bc5fe570838dd.pdf}}
</ref><ref>
{{cite journal
Line 34 ⟶ 35:
|publisher=Springer
|volume=13 |issue=3-4|pages=287–312
|year=1995
|url=http://dottorato.di.uniba.it/dottoratoXXVI/dm/FOILvsRelatedSystems.pdf}}
</ref><ref>
{{cite journal
Line 50 ⟶ 52:
|title=Genetic Programming: vol. 1, On the programming of computers by means of natural selection
|publisher=MIT Press
|year=1992
|url=https://books.google.com/books?id=Bhtxo60BV0EC&printsec=frontcover#v=onepage&q&f=false}}
</ref> proposed genetic programming in the early 1990s as a generate-and-test based approach to learning programs. The idea of genetic programming was further developed into the inductive programming system ADATE<ref>
{{cite journal
Line 65 ⟶ 68:
|journal=PRICAI 2008: Trends in Artificial Intelligence
|pages=199–210
|year=2008
|url=http://nautilus.cs.miyazaki-u.ac.jp/~skata/skatayama_pricai2008.pdf}}
</ref> Here again, functional programs are learned from sets of positive examples together with an output evaluation (fitness) function which specifies the desired input/output behavior of the program to be learned.
Line 124 ⟶ 128:
|publisher=Wiley
|journal=Computational Intelligence
|year=2014
|url=https://pdfs.semanticscholar.org/48f2/2821220555f8e327c2aa9614fb28c98f9542.pdf}}
</ref> abstraction has also been explored as a more powerful approach to [[cumulative learning]] and function invention.<ref>
{{cite journal
Line 131 ⟶ 136:
|publisher=Imperial College Press
|journal=Advances in Inductive Logic Programming
|year=2012
|url=http://ilp11.doc.ic.ac.uk/short_papers/ilp2011_submission_62.pdf}}
</ref><ref>
{{cite arXiv
Line 146 ⟶ 152:
|volume=4(B)
|pages=141–153
|year=2000
|url=https://ocs.aaai.org/Papers/Workshops/2000/WS-00-06/WS00-06-006.pdf}}
</ref><ref>
{{cite book
Line 182 ⟶ 189:
|title=Your wish is my command: Programming by example
|publisher=Morgan Kaufmann
|year=2001
|url=https://books.google.com/books?id=wM2JYafw11gC&printsec=frontcover#v=onepage&q&f=false}}
</ref> and [[programming by demonstration]],<ref>
{{cite journal
| |||