Inductive programming: Difference between revisions

Revision as of 12:03, 21 September 2021

Latest revision as of 11:08, 23 June 2025

(16 intermediate revisions by 10 users not shown)

Line 1:

{{Short description|Area of automatic programming}}

{{Programming paradigms}}

'''Inductive programming''' ('''IP''') is a special area of [[automatic programming]], covering research from [[artificial intelligence]] and [[Computer programming|programming]], which addresses [[machine learning|learning]] of typically [[declarative programming|declarative]] ([[logic programming|logic]] or [[functional programming|functional]]) and often [[recursion|recursive]] programs from incomplete specifications, such as input/output examples or constraints.

Line 10:

Output of an IP system is a program in some arbitrary programming language containing conditionals and loop or recursive control structures, or any other kind of [[Turing completeness|Turing-complete]] [[Knowledge representation and reasoning|representation]] language.

In many applications the output program must be correct with respect to the examples and partial specification, and this leads to the consideration of inductive programming as a special area inside automatic programming or [[program synthesis]],<ref>{{cite journal|first1=A.W.|last1=Biermann|title=Automatic programming|editor1-first=S.C.|editor1-last=Shapiro|journal=Encyclopedia of Artificial Intelligence|pages=18–35|year=1992}}</ref><ref>{{cite book|first1=C.|last1=Rich|first2=R.C.|last2=Waters|title=Approaches to automatic programming|editor1-first=M.C.|editor1-last=Yovits|journalseries=Advances in Computers|volume=37|pages=1–57|year=1993|url=http://www.merl.com/publications/docs/TR92-04.pdf|doi=10.1016/S0065-2458(08)60402-7|isbn=9780120121373}}</ref> usually opposed to 'deductive' program synthesis,<ref>{{cite book|editor1-first=M.L.|editor1-last=Lowry|editor2-first=R.D.|editor2-last=McCarthy|title=Automatic software design|year=1991}}</ref><ref>{{cite journal|first1=Z.|last1=Manna|first2=R.|last2=Waldinger|title=Fundamentals of deductive program synthesis|journal=IEEE Trans Softw Eng|volume=18 | issue = 8|pages=674–704|year=1992|doi=10.1109/32.153379|citeseerx=10.1.1.51.817}}</ref><ref>{{Cite book|first1=P.|last1=Flener|chapter=Achievements and Prospects of Program Synthesis |title=Computational Logic: Logic Programming and Beyond|chapter=Achievements; andEssays prospectsin Honour of programRobert synthesisA. Kowalski|editor1-first=A.|editor1-last=Kakas|editor2-first=F.|editor2-last=Sadri|journal=Computational Logic: Logic Programming and Beyond; Essays in Honour of Robert A. Kowalski|volume=LNAI 2407|pages=310–346|year=2002|doi=10.1007/3-540-45628-7_13|series=Lecture Notes in Computer Science|isbn=978-3-540-43959-2}}</ref> where the specification is usually complete.

In other cases, inductive programming is seen as a more general area where any declarative programming or representation language can be used and we may even have some degree of error in the examples, as in general [[machine learning]], the more specific area of [[structure mining]] or the area of [[symbolic artificial intelligence]]. A distinctive feature is the number of examples or partial specification needed. Typically, inductive programming techniques can learn from just a few examples.

Line 18:

== History ==

Research on the inductive synthesis of recursive functional programs started in the early 1970s and was brought onto firm theoretical foundations with the seminal THESIS system of Summers<ref>{{cite journal|first1=P.D.|last1=Summers|title=A methodology for LISP program construction from examples|journal=J ACM|volume=24 | issue = 1|pages=161–175|year=1977|doi=10.1145/321992.322002|s2cid=7474210|doi-access=free}}</ref> and work of Biermann.<ref>{{cite journal|first1=A.W.|last1=Biermann|title=The inference of regular LISP programs from examples|journal=IEEE Trans Syst Man Cybern|volume=8 | issue = 8|pages=585–600|year=1978|doi=10.1109/tsmc.1978.4310035|s2cid=15277948}}</ref>

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|journal=Automatic Program Construction Techniques|pages=307–324|year=1984|url=https://www.researchgate.net/publication/239059541}}</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 | citeseerx = 10.1.1.329.5312 | s2cid = 5462416 }}</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|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|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|s2cid=14992676|title=Efficient induction of logic programs|journal=Proceedings of the Workshop on Algorithmic Learning Theory|volume=6|pages=368–381|year=1990}}</ref> But again, after initial success, the community got disappointed by limited progress about the induction of recursive programs<ref>{{cite journal

Line 28:

|year=1993

}}

</ref><ref>{{cite journal|first1=J.R.|last1=Quinlan|first2=R.M.|last2=Cameron-Jones|title=Induction of logic programs: FOIL and related systems|publisher=Springer|volume=13|issue=3–4|pages=287–312|year=1995|url=http://dottorato.di.uniba.it/dottoratoXXVI/dm/FOILvsRelatedSystems.pdf|access-date=2017-09-07|archive-date=2017-09-07|archive-url=https://web.archive.org/web/20170907080358/http://dottorato.di.uniba.it/dottoratoXXVI/dm/FOILvsRelatedSystems.pdf|url-status=dead}}</ref><ref>

</ref><ref>

{{cite journal

|first1=J.R.|last1=Quinlan|first2=R.M.|last2=Cameron-Jones

|title=Induction of logic programs: FOIL and related systems

|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

|first1=P.|last1=Flener|first2=S.|last2=Yilmaz

Line 43 ⟶ 35:

|volume=41 | issue = 2

|pages=141–195

|year=1999|doi=10.1016/s0743-1066(99)00028-x|doi-access=free}}

</ref> with ILP less and less focusing on recursive programs and leaning more and more towards a machine learning setting with applications in [[relational data mining]] and knowledge discovery.<ref>{{citation|first1=Sašo|last1=Džeroski|contribution=Inductive Logic Programming and Knowledge Discovery in Databases|pages=117–152|editor1-first=U.M.|editor1-last=Fayyad|editor2-first=G.|editor2-last=Piatetsky-Shapiro|editor3-first=P.|editor3-last=Smith|editor4-first=R.|editor4-last=Uthurusamy|title=Advances in Knowledge Discovery and Data Mining|publisher=MIT Press|year=1996}}</ref>

Line 64 ⟶ 56:

{{cite book

|first1=Susumu|last1=Katayama

|journaltitle=PRICAI 2008: Trends in Artificial Intelligence

|chapter=Efficient exhaustiveExhaustive generationGeneration of functionalFunctional programsPrograms usingUsing Monte-Carlo searchSearch with iterativeIterative deepeningDeepening

|journal=PRICAI 2008: Trends in Artificial Intelligence

|volume=5351

|pages=199–210

Line 127 ⟶ 119:

|journal=Computational Intelligence

|volume=30|issue=3|pages=473–513|year=2014

|doi=10.1111/coin.12004|doi-access=free|hdl=10251/34946|hdl-access=free}}

</ref> abstraction has also been explored as a more powerful approach to [[cumulative learning]] and function invention.<ref>

{{cite journal

Line 135 ⟶ 127:

|year=2012

|url=http://ilp11.doc.ic.ac.uk/short_papers/ilp2011_submission_62.pdf}}

</ref><ref name="Inducing probabilistic programs by">{{cite arXiv

</ref><ref>

{{cite arXiv

|first1=H.|last1=Irvin|first2=A.|last2=Stuhlmuller|first3=N.D.|last3=Goodman

|title=Inducing probabilistic programs by Bayesian program merging|eprint=1110.5667

|year=2011|class=cs.AI}}</ref>

</ref>

One powerful paradigm that has been recently used for the representation of hypotheses in inductive programming (generally in the form of [[generative model]]s) is [[probabilistic programming language|probabilistic programming]] (and related paradigms, such as stochastic logic programs and Bayesian logic programming).<ref>{{cite journal

|first1=S.

{{cite journal

|first1=S.|last1=Muggleton

|title=Learning stochastic logic programs

|journal=Electron. Trans. Artif. Intell.

Line 150 ⟶ 140:

|pages=141–153

|year=2000

|url=https://ocs.aaai.org/Papers/Workshops/2000/WS-00-06/WS00-06-006.pdf}}

|access-date=2017-09-07

</ref><ref>

|archive-date=2017-09-07

|archive-url=https://web.archive.org/web/20170907080041/https://ocs.aaai.org/Papers/Workshops/2000/WS-00-06/WS00-06-006.pdf

|url-status=dead

}}</ref><ref>

{{cite book

|first1=L.|last1=De Raedt|first2=K.|last2=Kersting

Line 157 ⟶ 151:

|publisher=Springer

|year=2008}}

</ref><ref name="Inducing probabilistic programs by"/><ref name="Reasoning about reasoning by nested conditioning: Modeling theory of mind with probabilistic programs">

</ref><ref>

{{cite arXiv

|first1=H.|last1=Irvin|first2=A.|last2=Stuhlmuller|first3=N.D.|last3=Goodman

|title=Inducing probabilistic programs by Bayesian program merging|eprint=1110.5667

|year=2011|class=cs.AI}}

</ref><ref name="Reasoning about reasoning by nested conditioning: Modeling theory of mind with probabilistic programs">

{{cite journal

|first1=A.|last1=Stuhlmuller|first2=N.D.|last2=Goodman

Line 194 ⟶ 183:

|title=Watch what I do: programming by demonstration

|year=1993

|publisher=MIT Press |url=https://books.google.com/books?id=Ggzjo0-W1y0C|isbn=9780262032131}}

</ref> and [[intelligent tutoring system]]s.

Other areas where inductive inference has been recently applied are [[knowledge acquisition]],<ref>

{{cite journal

|first1=U.|last1=Schmid|author1-link= Ute Schmid |first2=M.|last2=Hofmann|first3=E.|last3=Kitzelmann

|title=Analytical inductive programming as a cognitive rule acquisition devise

|journal=Proceedings of the Second Conference on Artificial General Intelligence

Line 207 ⟶ 196:

</ref> [[artificial general intelligence]],<ref>

{{cite journal

|first1=N.|last1=Crossley|first2=E.|last2=Kitzelmann|first3=M.|last3=Hofmann|first4=U.|last4=Schmid|author4-link= Ute Schmid

|title=Combining analytical and evolutionary inductive programming

|journal=Proceedings of the Second Conference on Artificial General Intelligence

Line 221 ⟶ 210:

|year=2000

|doi=10.1002/(sici)1098-111x(200003)15:3<241::aid-int6>3.0.co;2-z|citeseerx=10.1.1.34.8877

|s2cid=123390956

}}

</ref><ref>

Line 232 ⟶ 222:

</ref> and [[cognitive science]] in general.<ref>

{{cite journal

|first1=U.|last1=Schmid|author1-link= Ute Schmid |first2=E.|last2=Kitzelmann

|title=Inductive rule learning on the knowledge level

|journal=Cognitive Systems Research

Line 250 ⟶ 240:

== Further reading ==

{{Refbegin}}

* {{cite journal|first1=P.|last1=Flener|first2=U.|last2=Schmid|author2-link= Ute Schmid |title=An introduction to inductive programming|journal=Artificial Intelligence Review|volume=29 | issue = 1|pages=45–62|year=2008|doi=10.1007/s10462-009-9108-7|s2cid=26314997}}

* {{cite book|first1=E.|last1=Kitzelmann|chaptertitle=InductiveApproaches programming:and A surveyApplications of programInductive synthesisProgramming techniques|journalchapter=ApproachesInductive andProgramming: ApplicationsA Survey of InductiveProgram Synthesis Techniques Programming|volume=5812|pages=50–73|year=2010|chapter-url=http://emanuel.kitzelmann.org/documents/publications/Kitzelmann2010.pdf|doi=10.1007/978-3-642-11931-6_3|citeseerx=10.1.1.180.1237|series=Lecture Notes in Computer Science|isbn=978-3-642-11930-9}}

* {{cite journal|first1=P.|last1=Flener|first2=U.|last2=Schmid|title=An introduction to inductive programming|journal=Artificial Intelligence Review|volume=29 | issue = 1|pages=45–62|year=2008|doi=10.1007/s10462-009-9108-7|s2cid=26314997}}

* {{cite journal|first1=D.|last1=Partridge|title=The case for inductive programming|journal=Computer|volume=30 | issue = 1|pages=36–41|year=1997|doi=10.1109/2.562924|s2cid=206403583 }}

* {{cite book|first1=E.|last1=Kitzelmann|chapter=Inductive programming: A survey of program synthesis techniques|journal=Approaches and Applications of Inductive Programming|volume=5812|pages=50–73|year=2010|chapter-url=http://emanuel.kitzelmann.org/documents/publications/Kitzelmann2010.pdf|doi=10.1007/978-3-642-11931-6_3|citeseerx=10.1.1.180.1237|series=Lecture Notes in Computer Science|isbn=978-3-642-11930-9}}

* {{cite journal|first1=D.|last1=Partridge|title=The case for inductive programming|journal=Computer|volume=30 | issue = 1|pages=36–41|year=1997|doi=10.1109/2.562924}}

* {{cite journal|first1=P.|last1=Flener|first2=D.|last2=Partridge|title=Inductive Programming|journal=Automated Software Engineering|volume=8 | issue = 2|pages=131–137|year=2001|doi=10.1023/a:1008797606116|s2cid=6675212}}

* {{cite journal|first1=M.|last1=Hofmann|first2=E.|last2=Kitzelmann|title=A unifying framework for analysis and evaluation of inductive programming systems|journal=Proceedings of the Second Conference on Artificial General Intelligence|pages=55–60|year=2009|url=http://www.atlantis-press.com/php/download_paper.php?id=1839}}

* {{Cite journal | last1 = Muggleton | first1 = S. | last2 = De Raedt | doi = 10.1016/0743-1066(94)90035-3 | first2 = L. | title = Inductive Logic Programming: Theory and methods | journal = The Journal of Logic Programming | volume = 19-20 | pages = 629–679 | year = 1994 | url = https://lirias.kuleuven.be/handle/123456789/125406 | doi-access = free }}

* {{cite book | first1 = N. | last1 = Lavrac |author1-link=Nada Lavrač| first2 = S. | last2 = Dzeroski | title = Inductive Logic Programming: Techniques and Applications | publisher = Ellis Horwood | ___location = New York | year = 1994 | isbn = 978-0-13-457870-5 }} https://web.archive.org/web/20040906084947/http://www-ai.ijs.si/SasoDzeroski/ILPBook/

* {{cite journal|first1=S.|last1=Muggleton|first2=Luc.|last2=De Raedt|first3=D.|last3=Poole|first4=I.|last4=Bratko|first5=P.|last5=Flach|first6=K.|last6=Inoue|first7=A.|last7=Srinivasan|title=ILP turns 20|journal=Machine Learning|volume=86 | issue = 1|pages=3–23|year=2012|doi=10.1007/s10994-011-5259-2|doi-access=free}}

* {{cite journal|first1=S.|last1=Gulwani|first2=J.|last2=Hernandez-Orallo|first3=E.|last3=Kitzelmann|first4=S.H.|last4=Muggleton|first5=U.|last5=Schmid|author5-link= Ute Schmid |first6=B.|last6=Zorn|title=Inductive Programming Meets the Real World|journal=Communications of the ACM|volume=58 | issue = 11|pages=90–99|year=2015|doi=10.1145/2736282|url=http://cacm.acm.org/magazines/2015/11/193326-inductive-programming-meets-the-real-world/abstract|citeseerx=10.1.1.696.3800|hdl=10251/64984|s2cid=425881}}

{{refend}}

== External links ==

* [http://www.inductive-programming.org/ Inductive Programming community page], hosted by the University of Bamberg.

{{Programming paradigms navbox}}

[[Category:Programming paradigms]]

[[Category:Machine learning]]

[[Category:Logic programming]]

[[Category:Artificial intelligence]]