Inductive programming: Difference between revisions

Revision as of 21:10, 29 October 2018

Revision as of 06:36, 20 February 2019

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 journalbook|first1=C.|last1=Rich|first2=R.C.|last2=Waters|title=Approaches to automatic programming|editor1-first=M.C.|editor1-last=Yovits|journal=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|title=Achievements and prospects of program synthesis|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 62:

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

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

{{cite journalbook

|first1=Susumu|last1=Katayama

|title=Efficient exhaustive generation of functional programs using Monte-Carlo search with iterative deepening

|journal=PRICAI 2008: Trends in Artificial Intelligence

|volume=5351

|pages=199–210

|year=2008

|url=http://nautilus.cs.miyazaki-u.ac.jp/~skata/skatayama_pricai2008.pdf}}|doi=10.1007/978-3-540-89197-0_21

|citeseerx=10.1.1.606.1447

|series=Lecture Notes in Computer Science

|isbn=978-3-540-89196-3

}}

</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 95 ⟶ 100:

|df=

}}

</ref> More recently, the language learning problem was addressed by the inductive programming community.<ref>{{cite journal|first1=Stephen|last1=Muggleton|title=Inductive Logic Programming: Issues, Results and the Challenge of Learning Language in Logic|journal=Artificial Intelligence|volume=114|issue=1–2|pages=283–296|year=1999|doi=10.1016/s0004-3702(99)00067-3}}; here: Sect.2.1</ref><ref>

{{cite journal

|first1=J.R.|last1=Olsson|first2=D.M.W.|last2=Powers

Line 123 ⟶ 128:

|title=Bridging the gap between distance and generalization

|journal=Computational Intelligence

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

|url=https://pdfs.semanticscholar.org/48f2/2821220555f8e327c2aa9614fb28c98f9542.pdf|doi=10.1111/coin.12004}}

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

{{cite journal

Line 269 ⟶ 274:

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

* {{cite journalbook|first1=E.|last1=Kitzelmann|title=Inductive programming: A survey of program synthesis techniques|journal=Approaches and Applications of Inductive Programming|volume=5812|pages=50–73|year=2010|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}}