Inductive programming (IP) is a special area of
automatic programming, covering research from
artificial intelligence
Artificial intelligence (AI) is the capability of computer, computational systems to perform tasks typically associated with human intelligence, such as learning, reasoning, problem-solving, perception, and decision-making. It is a field of re ...
and
programming, which addresses
learning
Learning is the process of acquiring new understanding, knowledge, behaviors, skills, value (personal and cultural), values, Attitude (psychology), attitudes, and preferences. The ability to learn is possessed by humans, non-human animals, and ...
of typically
declarative (
logic
Logic is the study of correct reasoning. It includes both formal and informal logic. Formal logic is the study of deductively valid inferences or logical truths. It examines how conclusions follow from premises based on the structure o ...
or
functional) and often
recursive
Recursion occurs when the definition of a concept or process depends on a simpler or previous version of itself. Recursion is used in a variety of disciplines ranging from linguistics to logic. The most common application of recursion is in m ...
programs from incomplete specifications, such as input/output examples or constraints.
Depending on the programming language used, there are several kinds of inductive programming. Inductive functional programming, which uses functional programming languages such as
Lisp
Lisp (historically LISP, an abbreviation of "list processing") is a family of programming languages with a long history and a distinctive, fully parenthesized Polish notation#Explanation, prefix notation.
Originally specified in the late 1950s, ...
or
Haskell
Haskell () is a general-purpose, statically typed, purely functional programming language with type inference and lazy evaluation. Designed for teaching, research, and industrial applications, Haskell pioneered several programming language ...
, and most especially
inductive logic programming
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 ...
, which uses logic programming languages such as
Prolog
Prolog is a logic programming language that has its origins in artificial intelligence, automated theorem proving, and computational linguistics.
Prolog has its roots in first-order logic, a formal logic. Unlike many other programming language ...
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
Constraint programming (CP) is a paradigm for solving combinatorial problems that draws on a wide range of techniques from artificial intelligence, computer science, and operations research. In constraint programming, users declaratively state t ...
or
probabilistic programming
Probabilistic programming (PP) is a programming paradigm based on the declarative specification of probabilistic models, for which inference is performed automatically.
Probabilistic programming attempts to unify probabilistic modeling and trad ...
.
Definition
Inductive programming incorporates all approaches which are concerned with learning programs or algorithms from incomplete (
formal
Formal, formality, informal or informality imply the complying with, or not complying with, some set of requirements ( forms, in Ancient Greek). They may refer to:
Dress code and events
* Formal wear, attire for formal events
* Semi-formal atti ...
) 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 type
In computer science and computer programming, a data type (or simply type) is a collection or grouping of data values, usually specified by a set of possible values, a set of allowed operations on these values, and/or a representation of these ...
s, 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
In computability theory, a system of data-manipulation rules (such as a model of computation, a computer's instruction set, a programming language, or a cellular automaton) is said to be Turing-complete or computationally universal if it can be ...
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
In computer science, program synthesis is the task to construct a computer program, program that provably correct, provably satisfies a given high-level formal specification. In contrast to program verification, the program is to be constructed rat ...
, usually opposed to 'deductive' program synthesis, 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
Machine learning (ML) is a field of study in artificial intelligence concerned with the development and study of Computational statistics, statistical algorithms that can learn from data and generalise to unseen data, and thus perform Task ( ...
, the more specific area of
structure mining
Structure mining or structured data mining is the process of finding and extracting useful information from semi-structured data sets. Graph mining, sequential pattern mining and molecule mining are special cases of structured data mining.
Des ...
or the area of
symbolic artificial intelligence
Symbolic may refer to:
* Symbol, something that represents an idea, a process, or a physical entity
Mathematics, logic, and computing
* Symbolic computation, a scientific area concerned with computing with mathematical formulas
* Symbolic dynamic ...
. 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
Functional logic programming is the combination, in a single programming language, of the paradigms of functional programming and logic programming.Antoy, Sergio, and Michael Hanus.Functional logic programming" Commun. ACM 53.4 (2010): 74–85. Thi ...
,
constraint programming
Constraint programming (CP) is a paradigm for solving combinatorial problems that draws on a wide range of techniques from artificial intelligence, computer science, and operations research. In constraint programming, users declaratively state t ...
,
probabilistic programming
Probabilistic programming (PP) is a programming paradigm based on the declarative specification of probabilistic models, for which inference is performed automatically.
Probabilistic programming attempts to unify probabilistic modeling and trad ...
,
abductive logic programming,
modal logic
Modal logic is a kind of logic used to represent statements about Modality (natural language), necessity and possibility. In philosophy and related fields
it is used as a tool for understanding concepts such as knowledge, obligation, and causality ...
,
action language
In computer science, an action language is a language for specifying state transition systems, and is commonly used to create formal models of the effects of actions on the world. Action languages are commonly used in the artificial intelligence ...
s, 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 and work of Biermann.
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. 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 eventually spawning the new field of inductive logic programming (ILP). The early works of Plotkin, 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. But again, after initial success, the community got disappointed by limited progress about the induction of recursive programs 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 Relational data mining is the data mining technique for relational
databases.Dzeroski, Saso, Nada Lavrač, Lavrač, Nada (Eds.), Relational Data Mining, Springer 200/ref> Unlike traditional data mining algorithms, which look for
patterns in a single ...
and knowledge discovery.
In parallel to work in ILP, Koza proposed
genetic programming
Genetic programming (GP) is an evolutionary algorithm, an artificial intelligence technique mimicking natural evolution, which operates on a population of programs. It applies the genetic operators selection (evolutionary algorithm), selection a ...
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 and the systematic-search-based system MagicHaskeller. 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
Grammar induction (or grammatical inference) is the process in machine learning of learning a formal grammar (usually as a collection of ''re-write rules'' or '' productions'' or alternatively as a finite-state machine or automaton of some kind) ...
(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. 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. More recently, the language learning problem was addressed by the inductive programming community.
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; abstraction has also been explored as a more powerful approach to
cumulative learning and function invention.
One powerful paradigm that has been recently used for the representation of hypotheses in inductive programming (generally in the form of
generative model
In statistical classification, two main approaches are called the generative approach and the discriminative approach. These compute classifiers by different approaches, differing in the degree of statistical modelling. Terminology is inconsiste ...
s) is
probabilistic programming
Probabilistic programming (PP) is a programming paradigm based on the declarative specification of probabilistic models, for which inference is performed automatically.
Probabilistic programming attempts to unify probabilistic modeling and trad ...
(and related paradigms, such as stochastic logic programs and Bayesian logic programming).
[
]
Application areas
Th
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, the related areas of programming by example In computer science, programming by example (PbE), also termed programming by demonstration or more generally as demonstrational programming, is an end-user development technique for machine learning, teaching a computer new behavior by demonstratin ...
and programming by demonstration, and intelligent tutoring system
An intelligent tutoring system (ITS) is a computer system that imitates human tutors and aims to provide immediate and customized instruction or feedback to learners, usually without requiring intervention from a human teacher. ITSs have the comm ...
s.
Other areas where inductive inference has been recently applied are knowledge acquisition, artificial general intelligence
Artificial general intelligence (AGI)—sometimes called human‑level intelligence AI—is a type of artificial intelligence that would match or surpass human capabilities across virtually all cognitive tasks.
Some researchers argue that sta ...
, reinforcement learning
Reinforcement learning (RL) is an interdisciplinary area of machine learning and optimal control concerned with how an intelligent agent should take actions in a dynamic environment in order to maximize a reward signal. Reinforcement learnin ...
and theory evaluation, and cognitive science
Cognitive science is the interdisciplinary, scientific study of the mind and its processes. It examines the nature, the tasks, and the functions of cognition (in a broad sense). Mental faculties of concern to cognitive scientists include percep ...
in general.[
][ There may also be prospective applications in intelligent agents, games, robotics, personalisation, ambient intelligence and human interfaces.
]
See also
* Evolutionary programming
Evolutionary programming is an evolutionary algorithm, where a share of new population is created by mutation of previous population without crossover. Evolutionary programming differs from evolution strategy ES(\mu+\lambda) in one detail. All in ...
* Inductive reasoning
Inductive reasoning refers to a variety of method of reasoning, methods of reasoning in which the conclusion of an argument is supported not with deductive certainty, but with some degree of probability. Unlike Deductive reasoning, ''deductive'' ...
* Test-driven development
Test-driven development (TDD) is a way of writing source code, code that involves writing an test automation, automated unit testing, unit-level test case that fails, then writing just enough code to make the test pass, then refactoring both the ...
References
Further reading
*
*
*
*
*
*
* https://web.archive.org/web/20040906084947/http://www-ai.ijs.si/SasoDzeroski/ILPBook/
*
*
External links
Inductive Programming community page
hosted by the University of Bamberg.
{{Programming paradigms navbox
Programming paradigms
Machine learning