Inductive programming

Last updated

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

Contents

Depending on the programming language used, there are several kinds of inductive programming. Inductive functional programming, which uses functional programming languages such as Lisp or Haskell, and most especially inductive logic programming, which uses logic programming languages such as Prolog and other logical representations such as description logics, have been more prominent, but other (programming) language paradigms have also been used, such as constraint programming or probabilistic programming.

Definition

Inductive programming incorporates all approaches which are concerned with learning programs or algorithms from incomplete (formal) specifications. Possible inputs in an IP system are a set of training inputs and corresponding outputs or an output evaluation function, describing the desired behavior of the intended program, traces or action sequences which describe the process of calculating specific outputs, constraints for the program to be induced concerning its time efficiency or its complexity, various kinds of background knowledge such as standard data types, predefined functions to be used, program schemes or templates describing the data flow of the intended program, heuristics for guiding the search for a solution or other biases.

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-complete 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, [1] [2] usually opposed to 'deductive' program synthesis, [3] [4] [5] 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.

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, abductive logic programming, modal logic, action languages, agent languages and many types of imperative languages.

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 [6] and work of Biermann. [7] 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. [8] 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 [9] eventually spawning the new field of inductive logic programming (ILP). [10] The early works of Plotkin, [11] [12] 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. [13] But again, after initial success, the community got disappointed by limited progress about the induction of recursive programs [14] [15] [16] 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. [17]

In parallel to work in ILP, Koza [18] 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 [19] and the systematic-search-based system MagicHaskeller. [20] 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. [21] 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. [22] More recently, the language learning problem was addressed by the inductive programming community. [23] [24]

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 types and structures; [25] [26] [27] abstraction has also been explored as a more powerful approach to cumulative learning and function invention. [28] [29]

One powerful paradigm that has been recently used for the representation of hypotheses in inductive programming (generally in the form of generative models) is probabilistic programming (and related paradigms, such as stochastic logic programs and Bayesian logic programming). [30] [31] [29] [32]

Application areas

The first workshop on Approaches and Applications of Inductive Programming (AAIP) held in conjunction with ICML 2005 identified all applications where "learning of programs or recursive rules are called for, [...] first in the domain of software engineering where structural learning, software assistants and software agents can help to relieve programmers from routine tasks, give programming support for end users, or support of novice programmers and programming tutor systems. Further areas of application are language learning, learning recursive control rules for AI-planning, learning recursive concepts in web-mining or for data-format transformations".

Since then, these and many other areas have shown to be successful application niches for inductive programming, such as end-user programming, [33] the related areas of programming by example [34] and programming by demonstration, [35] and intelligent tutoring systems.

Other areas where inductive inference has been recently applied are knowledge acquisition, [36] artificial general intelligence, [37] reinforcement learning and theory evaluation, [38] [39] and cognitive science in general. [40] [32] There may also be prospective applications in intelligent agents, games, robotics, personalisation, ambient intelligence and human interfaces.

See also

Related Research Articles

Logic programming is a programming, database and knowledge representation paradigm based on formal logic. A logic program is a set of sentences in logical form, representing knowledge about some problem domain. Computation is performed by applying logical reasoning to that knowledge, to solve problems in the domain. Major logic programming language families include Prolog, Answer Set Programming (ASP) and Datalog. In all of these languages, rules are written in the form of clauses:

Inductive logic programming (ILP) is a subfield of symbolic artificial intelligence which uses logic programming as a uniform representation for examples, background knowledge and hypotheses. The term "inductive" here refers to philosophical rather than mathematical induction. Given an encoding of the known background knowledge and a set of examples represented as a logical database of facts, an ILP system will derive a hypothesised logic program which entails all the positive and none of the negative examples.

In computer science, declarative programming is a programming paradigm—a style of building the structure and elements of computer programs—that expresses the logic of a computation without describing its control flow.

Machine learning (ML) is a field of study in artificial intelligence concerned with the development and study of statistical algorithms that can learn from data and generalize to unseen data, and thus perform tasks without explicit instructions. Recently, generative artificial neural networks have been able to surpass many previous approaches in performance.

Inferences are steps in reasoning, moving from premises to logical consequences; etymologically, the word infer means to "carry forward". Inference is theoretically traditionally divided into deduction and induction, a distinction that in Europe dates at least to Aristotle. Deduction is inference deriving logical conclusions from premises known or assumed to be true, with the laws of valid inference being studied in logic. Induction is inference from particular evidence to a universal conclusion. A third type of inference is sometimes distinguished, notably by Charles Sanders Peirce, contradistinguishing abduction from induction.

<span class="mw-page-title-main">Symbolic artificial intelligence</span> Methods in artificial intelligence research

In artificial intelligence, symbolic artificial intelligence is the term for the collection of all methods in artificial intelligence research that are based on high-level symbolic (human-readable) representations of problems, logic and search. Symbolic AI used tools such as logic programming, production rules, semantic nets and frames, and it developed applications such as knowledge-based systems, symbolic mathematics, automated theorem provers, ontologies, the semantic web, and automated planning and scheduling systems. The Symbolic AI paradigm led to seminal ideas in search, symbolic programming languages, agents, multi-agent systems, the semantic web, and the strengths and limitations of formal knowledge and reasoning systems.

Solomonoff's theory of inductive inference is a mathematical theory of induction introduced by Ray Solomonoff, based on probability theory and theoretical computer science. In essence, Solomonoff's induction derives the posterior probability of any computable theory, given a sequence of observed data. This posterior probability is derived from Bayes' rule and some universal prior, that is, a prior that assigns a positive probability to any computable theory.

In computer science, program synthesis is the task to construct a program that provably satisfies a given high-level formal specification. In contrast to program verification, the program is to be constructed rather than given; however, both fields make use of formal proof techniques, and both comprise approaches of different degrees of automation. In contrast to automatic programming techniques, specifications in program synthesis are usually non-algorithmic statements in an appropriate logical calculus.

In computer science, in particular in knowledge representation and reasoning and metalogic, the area of automated reasoning is dedicated to understanding different aspects of reasoning. The study of automated reasoning helps produce computer programs that allow computers to reason completely, or nearly completely, automatically. Although automated reasoning is considered a sub-field of artificial intelligence, it also has connections with theoretical computer science and philosophy.

Grammar induction is the process in machine learning of learning a formal grammar from a set of observations, thus constructing a model which accounts for the characteristics of the observed objects. More generally, grammatical inference is that branch of machine learning where the instance space consists of discrete combinatorial objects such as strings, trees and graphs.

<span class="mw-page-title-main">Stephen Muggleton</span> Artificial intelligence researcher

Stephen H. Muggleton FBCS, FIET, FAAAI, FECCAI, FSB, FREng is Professor of Machine Learning and Head of the Computational Bioinformatics Laboratory at Imperial College London.

Progol is an implementation of inductive logic programming that combines inverse entailment with general-to-specific search through a refinement graph.

Statistical relational learning (SRL) is a subdiscipline of artificial intelligence and machine learning that is concerned with domain models that exhibit both uncertainty and complex, relational structure. Typically, the knowledge representation formalisms developed in SRL use first-order logic to describe relational properties of a domain in a general manner and draw upon probabilistic graphical models to model the uncertainty; some also build upon the methods of inductive logic programming. Significant contributions to the field have been made since the late 1990s.

In information technology a reasoning system is a software system that generates conclusions from available knowledge using logical techniques such as deduction and induction. Reasoning systems play an important role in the implementation of artificial intelligence and knowledge-based systems.

This glossary of artificial intelligence is a list of definitions of terms and concepts relevant to the study of artificial intelligence, its sub-disciplines, and related fields. Related glossaries include Glossary of computer science, Glossary of robotics, and Glossary of machine vision.

In programming languages and machine learning, Bayesian program synthesis (BPS) is a program synthesis technique where Bayesian probabilistic programs automatically construct new Bayesian probabilistic programs. This approach stands in contrast to routine practice in probabilistic programming where human developers manually write new probabilistic programs.

The following outline is provided as an overview of and topical guide to machine learning:

Kristian Kersting is a German computer scientist. He is Professor of Artificial intelligence and Machine Learning at the Department of Computer Science at the Technische Universität Darmstadt, Head of the Artificial Intelligence and Machine Learning Lab (AIML) and Co-Director of hessian.AI, the Hessian Center for Artificial Intelligence.

ProbLog is a probabilistic logic programming language that extends Prolog with probabilities. It minimally extends Prolog by adding the notion of a probabilistic fact, which combines the idea of logical atoms and random variables. Similarly to Prolog, ProbLog can query an atom. While Prolog returns the truth value of the queried atom, ProbLog returns the probability of it being true.

References

  1. Biermann, A.W. (1992). Shapiro, S.C. (ed.). "Automatic programming". Encyclopedia of Artificial Intelligence: 18–35.
  2. Rich, C.; Waters, R.C. (1993). Yovits, M.C. (ed.). Approaches to automatic programming (PDF). Advances in Computers. Vol. 37. pp. 1–57. doi:10.1016/S0065-2458(08)60402-7. ISBN   9780120121373.
  3. Lowry, M.L.; McCarthy, R.D., eds. (1991). Automatic software design.
  4. Manna, Z.; Waldinger, R. (1992). "Fundamentals of deductive program synthesis". IEEE Trans Softw Eng. 18 (8): 674–704. CiteSeerX   10.1.1.51.817 . doi:10.1109/32.153379.
  5. Flener, P. (2002). "Achievements and Prospects of Program Synthesis". In Kakas, A.; Sadri, F. (eds.). Computational Logic: Logic Programming and Beyond; Essays in Honour of Robert A. Kowalski. Lecture Notes in Computer Science. Vol. LNAI 2407. pp. 310–346. doi:10.1007/3-540-45628-7_13. ISBN   978-3-540-43959-2.
  6. Summers, P.D. (1977). "A methodology for LISP program construction from examples". J ACM. 24 (1): 161–175. doi: 10.1145/321992.322002 . S2CID   7474210.
  7. Biermann, A.W. (1978). "The inference of regular LISP programs from examples". IEEE Trans Syst Man Cybern. 8 (8): 585–600. doi:10.1109/tsmc.1978.4310035. S2CID   15277948.
  8. Smith, D.R. (1984). Biermann, A.W.; Guiho, G. (eds.). "The synthesis of LISP programs from examples: a survey". Automatic Program Construction Techniques: 307–324.
  9. Shapiro, E.Y. (1983). Algorithmic program debugging. The MIT Press.
  10. Muggleton, S. (1991). "Inductive logic programming". New Generation Computing. 8 (4): 295–318. CiteSeerX   10.1.1.329.5312 . doi:10.1007/BF03037089. S2CID   5462416.
  11. Plotkin, Gordon D. (1970). Meltzer, B.; Michie, D. (eds.). "A Note on Inductive Generalization" (PDF). Machine Intelligence. 5: 153–163.
  12. Plotkin, Gordon D. (1971). Meltzer, B.; Michie, D. (eds.). "A Further Note on Inductive Generalization". Machine Intelligence. 6: 101–124.
  13. Muggleton, S.H.; Feng, C. (1990). "Efficient induction of logic programs". Proceedings of the Workshop on Algorithmic Learning Theory. 6: 368–381. S2CID   14992676.
  14. Quinlan, J.R.; Cameron-Jones, R.M. (1993). "Avoiding Pitfalls When Learning Recursive Theories". IJCAI: 1050–1057. S2CID   11138624.
  15. Quinlan, J.R.; Cameron-Jones, R.M. (1995). "Induction of logic programs: FOIL and related systems" (PDF). 13 (3–4). Springer: 287–312. Archived from the original (PDF) on 2017-09-07. Retrieved 2017-09-07.{{cite journal}}: Cite journal requires |journal= (help)
  16. Flener, P.; Yilmaz, S. (1999). "Inductive synthesis of recursive logic programs: Achievements and prospects". The Journal of Logic Programming. 41 (2): 141–195. doi: 10.1016/s0743-1066(99)00028-x .
  17. Džeroski, Sašo (1996), "Inductive Logic Programming and Knowledge Discovery in Databases", in Fayyad, U.M.; Piatetsky-Shapiro, G.; Smith, P.; Uthurusamy, R. (eds.), Advances in Knowledge Discovery and Data Mining, MIT Press, pp. 117–152
  18. Koza, J.R. (1992). Genetic Programming: vol. 1, On the programming of computers by means of natural selection. MIT Press. ISBN   9780262111706.
  19. Olsson, J.R. (1995). "Inductive functional programming using incremental program transformation". Artificial Intelligence. 74 (1): 55–83. doi: 10.1016/0004-3702(94)00042-y .
  20. Katayama, Susumu (2008). "Efficient Exhaustive Generation of Functional Programs Using Monte-Carlo Search with Iterative Deepening" (PDF). PRICAI 2008: Trends in Artificial Intelligence. Lecture Notes in Computer Science. Vol. 5351. pp. 199–210. CiteSeerX   10.1.1.606.1447 . doi:10.1007/978-3-540-89197-0_21. ISBN   978-3-540-89196-3.
  21. Angluin, D.; C.H., Smith (1983). "Inductive inference: Theory and methods". ACM Computing Surveys. 15 (3): 237–269. doi:10.1145/356914.356918. S2CID   3209224.
  22. Gold, E.M. (1967). "Language identification in the limit". Information and Control. 10 (5): 447–474. doi: 10.1016/s0019-9958(67)91165-5 .
  23. Muggleton, Stephen (1999). "Inductive Logic Programming: Issues, Results and the Challenge of Learning Language in Logic". Artificial Intelligence. 114 (1–2): 283–296. doi: 10.1016/s0004-3702(99)00067-3 .; here: Sect.2.1
  24. Olsson, J.R.; Powers, D.M.W. (2003). "Machine learning of human language through automatic programming". Proceedings of the International Conference on Cognitive Science: 507–512.
  25. Lloyd, J.W. (2001). "Knowledge Representation, Computation, and Learning in Higher-order Logic" (PDF).{{cite journal}}: Cite journal requires |journal= (help)
  26. Lloyd, J.W. (2003). Logic for learning: learning comprehensible theories from structured data. Springer. ISBN   9783662084069.
  27. Estruch, V.; Ferri, C.; Hernandez-Orallo, J.; Ramirez-Quintana, M.J. (2014). "Bridging the gap between distance and generalization". Computational Intelligence. 30 (3): 473–513. doi: 10.1111/coin.12004 . S2CID   7255690.
  28. Henderson, R.J.; Muggleton, S.H. (2012). "Automatic invention of functional abstractions" (PDF). Advances in Inductive Logic Programming.
  29. 1 2 Irvin, H.; Stuhlmuller, A.; Goodman, N.D. (2011). "Inducing probabilistic programs by Bayesian program merging". arXiv: 1110.5667 [cs.AI].
  30. Muggleton, S. (2000). "Learning stochastic logic programs" (PDF). Electron. Trans. Artif. Intell. 4(B): 141–153. Archived from the original (PDF) on 2017-09-07. Retrieved 2017-09-07.
  31. De Raedt, L.; Kersting, K. (2008). Probabilistic inductive logic programming. Springer.
  32. 1 2 Stuhlmuller, A.; Goodman, N.D. (2012). "Reasoning about reasoning by nested conditioning: Modeling theory of mind with probabilistic programs". Cognitive Systems Research. 28: 80–99. doi:10.1016/j.cogsys.2013.07.003. S2CID   7602205.
  33. Lieberman, H.; Paternò, F.; Wulf, V. (2006). End user development. Springer.
  34. Lieberman, H. (2001). Your wish is my command: Programming by example. Morgan Kaufmann. ISBN   9781558606883.
  35. Cypher, E.; Halbert, D.C. (1993). Watch what I do: programming by demonstration. MIT Press. ISBN   9780262032131.
  36. Schmid, U.; Hofmann, M.; Kitzelmann, E. (2009). "Analytical inductive programming as a cognitive rule acquisition devise" (PDF). Proceedings of the Second Conference on Artificial General Intelligence: 162–167.
  37. Crossley, N.; Kitzelmann, E.; Hofmann, M.; Schmid, U. (2009). "Combining analytical and evolutionary inductive programming" (PDF). Proceedings of the Second Conference on Artificial General Intelligence: 19–24.
  38. Hernandez-Orallo, J. (2000). "Constructive reinforcement learning". International Journal of Intelligent Systems. 15 (3): 241–264. CiteSeerX   10.1.1.34.8877 . doi:10.1002/(sici)1098-111x(200003)15:3<241::aid-int6>3.0.co;2-z. S2CID   123390956.
  39. Kemp, C.; Goodman, N.; Tenenbaum, J.B. (2007). "Learning and using relational theories" (PDF). Advances in Neural Information Processing Systems: 753–760.
  40. Schmid, U.; Kitzelmann, E. (2011). "Inductive rule learning on the knowledge level". Cognitive Systems Research. 12 (3): 237–248. doi:10.1016/j.cogsys.2010.12.002. S2CID   18613664.

Further reading