Inductive programming: Difference between revisions

Revision as of 09:19, 23 January 2015

Revision as of 09:20, 23 January 2015

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|publisher=Wiley|journal=Encyclopedia of artificial intelligence|pages=18–35|year=1992}}</ref><ref>{{cite journal|first1=C.|last1=Rich|first2=R.C.|last2=Waters|title=Approaches to automatic programming|editor1-first=M.C.|editor1-last=Yovits|publisher=Academic Press|journal=Advances in computers|volume=37|year=1993}}</ref> usually opposed to 'deductive' program synthesis,<ref>{{cite book|editor1-first=M.L.|editor1-last=Lowry|editor1-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}}</ref><ref>{{cite journal|first1=P.|last1=Flener|title=Achievements and prospects of program synthesis|editor1-first=A.|editor1-last=Kakas|editor2-first=F.|editor2-last=Sadri|publisher=Springer|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}}</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}}</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}}</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|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.

Line 40:

title=Inductive synthesis of recursive logic programs: Achievements and prospects|

journal=The Journal of Logic Programming|

volume=41( | issue = 2)|

pages=141–195|

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

</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 57:

publisher=Elsevier|

journal=Artificial Intelligence|

volume=74( | issue = 1)|pages=55–83|

year=1995|doi=10.1016/0004-3702(94)00042-y}}

</ref> and the systematic-search-based system MagicHaskeller.<ref>

{{cite journal|

Line 193:

volume=55 | issue = 8|

pages=97–105|

year=2012|doi=10.1145/2240236.2240260}}

</ref><ref>{{cite web|last=Harris|first=Steven|title=Excel 2013 - Flash Fill|url=http://www.experts-exchange.com/Software/Office_Productivity/Office_Suites/MS_Office/Excel/A_12314-Excel-2013-Flash-Fill.html|work=Experts-Exchange.com|publisher=Experts Exchange|accessdate=23 November 2013|date=1 October 2013}}</ref> in [[Microsoft Excel]].

Line 232:

volume=12 | issue = 3|

pages=237–248|

year=2011|doi=10.1016/j.cogsys.2010.12.002}}

</ref><ref>

{{cite journal|

Line 266:

{{Refbegin}}

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

* {{cite journal|first1=E.|last1=Kitzelmann|title=Inductive programming: A survey of program synthesis techniques|publisher=Springer|journal=Approaches and Applications of Inductive Programming|pages=50–73|year=2010}}

* {{cite journal|first1=D.|last1=Partridge|title=The case for inductive programming|publisher=IEEE|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|publisher=Springer|journal=Automated Software Engineering|volume=8( | issue = 2)|pages=131–137|year=2001|doi=10.1023/a:1008797606116}}

* {{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}}

Line 280:

* {{cite book | first1 = N. | last1 = Lavrac | first2 = S. | last2 = Dzeroski | title = Inductive Logic Programming: Techniques and Applications | publisher = Ellis Horwood | ___location = New York | year = 1994 | isbn = 0-13-457870-8 | url = 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|publisher=Springer|journal=Machine Learning|volume=86( | issue = 1)|pages=3–23|year=2012|doi=10.1007/s10994-011-5259-2}}

== References ==