Content deleted Content added
→History: wikilink |
RandFreeman (talk | contribs) Adding local short description: "Area of automatic programming", overriding Wikidata description "learning programs from data" |
||
| (23 intermediate revisions by 12 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|
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
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
|first1=J.R.|last1=Quinlan|first2=R.M.|last2=Cameron-Jones
|s2cid=11138624|title=Avoiding Pitfalls When Learning Recursive Theories
|journal=IJCAI
|pages=1050–1057
|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=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 60 ⟶ 52:
|journal=Artificial Intelligence
|volume=74 | issue = 1|pages=55–83
|year=1995|doi=10.1016/0004-3702(94)00042-y|doi-access=free}}
</ref> and the systematic-search-based system MagicHaskeller.<ref>
{{cite book
|first1=Susumu|last1=Katayama
|chapter=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
|chapter-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
Line 82 ⟶ 74:
|journal=ACM Computing Surveys
|volume=15|issue=3|pages=237–269
|year=1983|doi=10.1145/356914.356918|s2cid=3209224}}
</ref> The results in terms of learnability were related to classical concepts, such as identification-in-the-limit, as introduced in the seminal work of Gold.<ref>
{{cite journal
Line 92 ⟶ 84:
|issue=5
|pages=447–474
|year=1967
|doi=10.1016/s0019-9958(67)91165-5
|
}}
</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|doi-access=free}}; here: Sect.2.1</ref><ref>
{{cite journal
|first1=J.R.|last1=Olsson|first2=D.M.W.|last2=Powers
Line 123 ⟶ 111:
|publisher=Springer
|year=2003
|url=https://books.google.com/books?id=8dioCAAAQBAJ
}}
</ref><ref>
{{cite journal
|first1=V.|last1=Estruch|first2=C.|last2=Ferri|first3=J.|last3=Hernandez-Orallo|first4=M.J.|last4=Ramirez-Quintana
|s2cid=7255690|title=Bridging the gap between distance and generalization
|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 139 ⟶ 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
|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>
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.
|title=Learning stochastic logic programs
|journal=Electron. Trans. Artif. Intell.
Line 154 ⟶ 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
|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 161 ⟶ 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 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
|s2cid=7602205|title=Reasoning about reasoning by nested conditioning: Modeling theory of mind with probabilistic programs
|journal=Cognitive Systems Research
|year=2012
|volume=28|pages=80–99|doi=10.1016/j.cogsys.2013.07.003}}
</ref>
Line 196 ⟶ 181:
{{Cite book
|first1=E.|last1=Cypher|first2=D.C.|last2=Halbert
|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 212 ⟶ 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 226 ⟶ 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 237 ⟶ 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
|volume=12 | issue = 3
|pages=237–248
|year=2011|doi=10.1016/j.cogsys.2010.12.002|s2cid=18613664}}
</ref><ref name="Reasoning about reasoning by nested conditioning: Modeling theory of mind with probabilistic programs"/> There may also be prospective applications in intelligent agents, games, robotics, personalisation, ambient intelligence and human interfaces.
== See also ==
* [[Evolutionary programming]]
* [[Inductive reasoning]]
* [[Test-driven development]]<!-- starting with input/output examples and manually producing a program that satisfies them -->
Line 269 ⟶ 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|title=
▲* {{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 journal|first1=
▲* {{cite book|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=
▲* {{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}}
* {{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 |
* {{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=
{{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]]
| |||