Content deleted Content added
RandFreeman (talk | contribs) Adding local short description: "Area of automatic programming", overriding Wikidata description "learning programs from data" |
|||
| (66 intermediate revisions by 28 users not shown) | |||
Line 1:
{{Short description|Area of automatic programming}}
'''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.
Depending on the programming language used, there are several kinds of inductive programming.
== Definition ==
Line 9 ⟶ 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
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.
The diversity of inductive programming usually comes from the applications and the languages that are used: apart from logic programming and functional programming, other programming paradigms and representation languages have been used or suggested in inductive programming, such as [[functional logic programming]], [[constraint programming]], [[probabilistic programming language|probabilistic programming]], [[abductive logic programming]], [[modal logic]], [[action language]]s, agent languages and many types of [[imperative languages]].
Line 17 ⟶ 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>
{{cite journal
|first1=
|title=
|journal=The Journal of Logic Programming
|volume=
|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>
In parallel to work in ILP, Koza<ref>
{{cite book
|first1=J.R.|last1=Koza
|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|isbn=9780262111706
}}
</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
|first1=J.R.|last1=Olsson
|title=Inductive functional programming using incremental program transformation
|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
|first1=Susumu|last1=Katayama
|title=PRICAI 2008: Trends in Artificial Intelligence
|chapter=Efficient Exhaustive Generation of Functional Programs Using Monte-Carlo Search with Iterative Deepening
|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
|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.
The early work in [[grammar induction]] (also known as grammatical inference) is related to inductive programming, as rewriting systems or logic programs can be used to represent production rules. In fact, early works in inductive inference considered grammar induction and Lisp program inference as basically the same problem.<ref>
{{cite journal
|first1=D.|last1=Angluin|first2=Smith|last2=C.H.
|title=Inductive inference: Theory and methods
|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
|first1=E.M.
|last1=Gold |title=Language identification in the limit
|journal=Information and Control
|volume=10
|pages=447–474 |year=1967
|doi-access=free
}}
</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
|title=Machine learning of human language through automatic programming
|journal=Proceedings of the International Conference on Cognitive Science
|pages=507–512
|year=2003}}
</ref>
In the recent years, the classical approaches have been resumed and advanced with great success. Therefore, the synthesis problem has been reformulated on the background of constructor-based term rewriting systems taking into account modern techniques of functional programming, as well as moderate use of search-based strategies and usage of background knowledge as well as automatic invention of subprograms. Many new and successful applications have recently appeared beyond program synthesis, most especially in the area of data manipulation, programming by example and cognitive modelling (see below).
Other ideas have also been explored with the common characteristic of using declarative languages for the representation of hypotheses. For instance, the use of higher-order features, schemes or structured distances have been advocated for a better handling of [[recursive data
{{cite journal
|first1=J.W.|last1=Lloyd
|title=Knowledge Representation, Computation, and Learning in Higher-order Logic
|year=2001
|url=http://users.cecs.anu.edu.au/~jwl/logic.pdf}}
</ref><ref>
{{cite book
|first1=J.W.|last1=Lloyd
|title=Logic for learning: learning comprehensible theories from structured data
|publisher=Springer
|year=2003
|url=https://books.google.com/books?id=8dioCAAAQBAJ|isbn=9783662084069
}}
</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
|first1=R.J.|last1=Henderson|first2=S.H.|last2=Muggleton
|title=Automatic invention of functional abstractions
|journal=Advances in Inductive Logic Programming
|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.
|volume=4(B)
|pages=
|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
|title=Probabilistic inductive logic programming
|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">
{{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 165:
Since then, these and many other areas have shown to be successful application niches for inductive programming, such as [[End-user development|end-user programming]],<ref>
{{cite book
|first1=H.|last1=Lieberman|first2=F.|last2=Paternò|first3=V.|last3=Wulf
|title=End user development
|publisher=Springer
|year=2006}}
</ref> the related areas of [[programming by example]]<ref>
{{cite book
|first1=H.|last1=Lieberman
|title=Your wish is my command: Programming by example
|publisher=Morgan Kaufmann
|year=2001
|url=https://books.google.com/books?id=wM2JYafw11gC|isbn=9781558606883
}}
</ref> and [[programming by demonstration]],<ref>
{{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
|pages=162–167
|year=2009
|url=http://www.cogsys.wiai.uni-bamberg.de/publications/cognigor-final.pdf}}
</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
|pages=19–24
|year=2009
|url=https://download.atlantis-press.com/article/1824.pdf}}
</ref> [[reinforcement learning]] and theory evaluation,<ref>
{{cite journal
|first1=J.|last1=Hernandez-Orallo
|title=Constructive reinforcement learning
|journal=International Journal of Intelligent Systems
|volume=15 | issue = 3|pages=241–264
|year=2000
|doi=10.1002/(sici)1098-111x(200003)15:3<241::aid-int6>3.0.co;2-z
|s2cid=123390956
}}
</ref><ref>
{{cite journal
|first1=C.|last1=Kemp|first2=N.|last2=Goodman|first3=J.B.|last3=Tenenbaum
|title=Learning and using relational theories
|journal=Advances in
|pages=753–760
|year=2007
|url=http://papers.nips.cc/paper/3332-learning-and-using-relational-theories.pdf}}
</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 -->
==
{{reflist}}
== 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=Approaches and Applications of Inductive Programming |chapter=Inductive Programming: A Survey of Program Synthesis Techniques |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|s2cid=206403583 }}
* {{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]]
| |||