Dagstuhl-Seminar 13502
Approaches and Applications of Inductive Programming
( 08. Dec – 11. Dec, 2013 )
(zum Vergrößern in der Bildmitte klicken)
Permalink
Bitte benutzen Sie folgende Kurz-Url zum Verlinken dieser Seite:
https://www.dagstuhl.de/13502
Organisatoren
- Sumit Gulwani (Microsoft Corporation - Redmond, US)
- Emanuel Kitzelmann (Universität Duisburg - Essen, DE)
- Ute Schmid (Universität Bamberg, DE)
Kontakt
- Susanne Bach-Bernhard (für administrative Fragen)
Impacts
- Can Machine Intelligence be Measured in the Same Way as Human intelligence? : article : pp. 291-297 - Besold, Tarek; Hernandez-Orallo, Jose; Schmid, Ute - Heidelberg : Springer, 2015 - (Künstliche Intelligenz : 29. 2015, 3).
- Comparing Computer Models Solving Number Series Problems : article in LNAI 9205 : pp. 352-361 - Schmid, Ute; Ragni, Marco - Berlin : Springer, 2015 - (Lecture notes in artificial intelligence ; 9205 : article).
- Inductive programming meets the real world : article : pp. 90-99 - Gulwani, Sumit; Hernandez-Orallo, Jose; Kitzelmann, Emanuel; Muggleton, Stephen H.; Schmid, Ute; Zorn, Benjamin - New York : ACM, 2015. - (Communications of the ACM : 58. 2015,11).
Inductive programming research addresses the problem of learning programs from incomplete specifications, such as input/output examples or constraints. Beginning in the 1960-ies, this area of research was initiated in artificial intelligence (AI) exploring the complex intellectual cognitive processes involved in producing program code which satisfies some specification. Furthermore, applications of AI for software engineering are investigated resulting in methodologies and techniques for automating parts of the program development process. Inductive programming can be seen as a very special subdomain of machine learning where the hypothesis space consists of classes of computer programs.
Nowadays, researchers working on inductive programming are distributed over different communities, especially inductive logic programming, evolutionary programming, grammar inference, functional programming, and programming languages and verification. Furthermore, similar approaches are of interest in programming by demonstration applications for end-user programming as well as in cognitive models of inductive learning.
Inductive programming methodologies are of potential use in different areas:
End-user development Even if the use of computers has become ubiquitous in everyday life, there is still a fundamental gap between users and their personal computers. Computers must be programmed, yet programming remains to be a highly specialized task requiring experts skills. As a consequence, millions of users carry out repetitive tasks or cannot even achieve a goal at all { although a few lines of code could potentially solve the problem. Inductive programming can help end users program computers by demonstrations, or even simply by examples.
Autonomous Intelligent Agents Generalizing particular problem-solving experience into general strategies that help to solve other problems in the same domain is a fundamental capability of human cognition. Inductive programming is a promising approach to computationally model this capability and to implement it in autonomous intelligent agents such as in tools for computer-aided education, and even in robots to make them more useful in open environments such as households.
Process Mining Computationally analyzing procedural data { e.g., biological network data or logs from business processes { by directly executable models such as Petri nets, becomes more and more important in science as well as in industry. Inductive programming will help to automatically mine such executable models from collected data.
Software Synthesis Inductive programming can even be useful in professional software development. In (deductive) software synthesis { e.g., synthesis of specific algorithm details that are hard to figure out by humans {, inductive reasoning can be used to generate program candidates from either user-provided data such as test cases or from data automatically derived from a formal specification. The aim of this seminar is to bring together researchers from the different areas where inductive programming is of interest. We expect that the possibility to discuss and evaluate approaches from different perspectives will be fruitful for (a) gaining better insights in general mechanisms underlying inductive programming algorithms, (b) identifying commonalities between induction algorithms and empirical knowledge about cognitive characteristics of the induction of complex rules, and (c) open up new areas for applications for inductive programming in end-user programming, support tools for example driven programming, and architectures for cognitive systems.
Inductive programming (IP) research addresses the problem of learning programs from incomplete specifications, such as input/output examples, traces, or constraints. In general, program synthesis is a topic of interest to researchers in artificial intelligence as well as in programming research since the 1960s [2]. On the one hand, this research aims at relieving programmers from the tedious task of explicit coding on the other hand it helps to uncover the complex cognitive processes involved in programming as a special domain of complex problem solving. From the beginning, there were two main directions of research -- deductive knowledge based approaches and inductive machine learning based approaches. Due to the progress in machine learning, over the last decades the inductive approach currently seems to be the more promising.
Researchers working on the topic of IP are distributed over different communities, especially inductive logic programming (ILP) [12,6], evolutionary programming [13], functional programming [15,5,10], grammar inference [1], and programming languages and verification [7]. Furthermore, domain specific IP techniques are developed for end-user programming [4,9] and in the context of intelligent tutoring in the domain of programming [8]. In cognitive science, researchers concerned with general principles of human inductive reasoning have constructed computer models for inductive generalization which also have some relation to IP [3,16].
In general, approaches can be classified by (1) the strategy of program construction which can be example-driven or generate-and-test driven; (2) the implicit or explicit restriction bias which can be Horn clauses, functional programs, or domain specific languages possibly with further constraints given as meta-interpreters, templates or program schemes; (3) the possibility to consider background knowledge.
IP research had its first boost in the 1970s in the context of learning Lisp programs from examples. Due to only limited progress, this direction of research decayed and in the 1990s was newly addressed in the context of ILP and evolutionary programming. Again, after first promising results, disappointment set in [14,11]. However, over the last years, a new revival in IP research can be observed in different communities and promising results, for example in the domain of enduser programming, give rise to new expectations.
Therefore, in the Dagstuhl Seminar AAIP we brought together researchers from these different communities as well as researchers of related fields. The possibility to discuss and evaluate approaches from different perspectives helped to (a) gaining better insights in general mechanisms underlying inductive programming algorithms, (b) identifying commonalities between induction algorithms and empirical knowledge about cognitive characteristics of the induction of complex rules, and (c) open up new areas for applications for inductive programming in enduser programming, support tools for example driven programming, and architectures for cognitive systems.
The presentations covered several aspects of inductive programming and were grouped in the topic sessions
- Inductive Programming Systems and Algorithms (with an introductory talk by Stephen Muggleton),
- Enduser Programming (with an introductory talk by Sumit Gulwani),
- Intelligent Tutoring and Grading,
- Cognitive Aspects of Induction (with an introductory talk by José Hernández-Orallo),
- Combining Inductive Programming with Declarative Programming and with Other Approaches to Program Synthesis (with an introductory talk by Luc de Raedt).
In an initial discussion round three focus topics were identified and further discussed in working groups
- Comparing Inductive Logic and Inductive Functional Programming as well as other Approaches to Program Synthesis,
- Potential New Areas of Applications and Challenges for Inductive Programming,
- Benchmarks and Metrics.
Concluding Remarks and Future Plans
In the final panel discussion the results of the seminar as well as future plans were identified. Participants stated that they learned a lot about different inductive programming techniques and tools to try. The general opinion was that it was very inspiring to have researchers from different backgrounds. To facilitate mutual understanding it was proposed to give introductory lectures, define the vocabulary of the different groups, collect a reading list, and identify common benchmark problems.
To progress in establishing inductive programming as a specific area of research it was proposed to write a Wikipedia page, and to collect introductory literature from the different areas covered in the seminar. Furthermore, plans for joint publications and joint grant proposals were made.
This seminar was highly productive and everybody hoped that there will be a follow-up in the near future.
References
- D. Angluin and C. H. Smith. Inductive inference: theory and methods. Computing Surveys, 15(3):237–269, September 1983.
- A. W. Biermann, G. Guiho, and Y. Kodratoff, editors. Automatic Program Construction Techniques. Macmillan, New York, 1984.
- P. A. Carpenter, M. A. Just, and P. Shell. What one intelligence test measures: A theoretical account of the processing in the Raven Progressive Matrices test. Psychological Review, 97:404–431, 1990.
- A. Cypher. EAGER: Programming repetitive tasks by example. In Human Factors in Computing Systems, Proc. of CHI’91, pages 33–39. ACM Press, 1991.
- C. Ferri-Ramírez, José Hernández-Orallo, and M. José Ramírez-Quintana. Incremental learning of functional logic programs. In FLOPS ’01: Proceedings of the 5th International Symposium on Functional and Logic Programming, pages 233–247, London, UK, 2001. Springer-Verlag.
- P. Flener and S. Yilmaz. Inductive synthesis of recursive logic programs: Achievements and prospects. Journal of Logic Programming, 41(2–3):141–195, 1999.
- Sumit Gulwani. Synthesis from examples: Interaction models and algorithms. In SYNASC, pages 8–14, 2012.
- Sumit Gulwani. Example-based learning in computer-aided stem education. To appear in Commun. ACM, 2014.
- Sumit Gulwani, William R. Harris, and Rishabh Singh. Spreadsheet data manipulation using examples. Commun. ACM, 55(8):97–105, 2012.
- E. Kitzelmann and U. Schmid. Inductive synthesis of functional programs: An explanation based generalization approach. Journal of Machine Learning Research, 7(Feb):429–454, 2006.
- Tessa Lau. Why programming-by-demonstration systems fail: Lessons learned for usable ai. AI Magazine, 30(4):65–67, 2009.
- S. Muggleton and L. De Raedt. Inductive logic programming: Theory and methods. Journal of Logic Programming, Special Issue on 10 Years of Logic Programming, 19-20:629–679, 1994.
- Roland Olsson. Inductive functional programming using incremental program transformation. Artificial Intelligence, 74(1):55–83, March 1995.
- J.R. Quinlan and R.M. Cameron-Jones. FOIL: A midterm report. In P. B. Brazdil, editor, Proceedings of the ECML’93, number 667 in LNCS, pages 3–20. Springer, 1993.
- U. Schmid and F. Wysotzki. Induction of recursive program schemes. In Proc. 10th European Conference on Machine Learning (ECML-98), volume 1398 of LNAI, pages 214–225. Springer, 1998.
- Ute Schmid and Emanuel Kitzelmann. Inductive rule learning on the knowledge level. Cognitive Systems Research, 12(3):237–248, 2011.
Creative Commons BY 3.0 Unported license
Sumit Gulwani, Emanuel Kitzelmann, and Ute Schmid
- Umair Zafrulla Ahmed (Indian Institute of Technology - Kanpur, IN) [dblp]
- Sam Bayless (University of British Columbia - Vancouver, CA) [dblp]
- Tarek Richard Besold (Universität Osnabrück, DE) [dblp]
- Luc De Raedt (KU Leuven, BE) [dblp]
- Eyal Dechter (MIT - Cambridge, US) [dblp]
- Alexey Grigoryev (National Nuclear Research University MEPhI, RU)
- Sumit Gulwani (Microsoft Corporation - Redmond, US) [dblp]
- Mike Hansen (Indiana University - Bloomington, US)
- Robert Henderson (Imperial College London, GB) [dblp]
- José Hernández-Orallo (Technical University of Valencia, ES) [dblp]
- Petra Hofstedt (TU Cottbus, DE) [dblp]
- Frank Jäkel (Universität Osnabrück, DE) [dblp]
- Susumu Katayama (University of Miyazaki, JP) [dblp]
- Dileep Kini (University of Illinois - Urbana-Champaign, US) [dblp]
- Emanuel Kitzelmann (Universität Duisburg - Essen, DE) [dblp]
- Mark Marron (Microsoft Corporation - Redmond, US) [dblp]
- Fernando Martinez-Plumed (Technical University of Valencia, ES) [dblp]
- Martin Möhrmann (Universität Osnabrück, DE) [dblp]
- Stephen H. Muggleton (Imperial College London, GB) [dblp]
- Daniel Perelman (University of Washington - Seattle, US) [dblp]
- Iurii Perov (University of Oxford, GB)
- Ruzica Piskac (Yale University, US) [dblp]
- Alex Polozov (University of Washington - Seattle, US) [dblp]
- Marco Ragni (Universität Freiburg, DE) [dblp]
- Ute Schmid (Universität Bamberg, DE) [dblp]
- George M. Sergievsky (National Nuclear Research University MEPhI, RU) [dblp]
- Michael Siebers (Universität Bamberg, DE) [dblp]
- Rishabh Singh (MIT - Cambridge, US) [dblp]
- Armando Solar-Lezama (MIT - Cambridge, US) [dblp]
- Janis Voigtländer (Universität Bonn, DE) [dblp]
- David White (Universität Bamberg, DE) [dblp]
- Eran Yahav (Technion - Haifa, IL) [dblp]
- Benjamin Zorn (Microsoft Research - Redmond, US) [dblp]
Verwandte Seminare
- Dagstuhl-Seminar 15442: Approaches and Applications of Inductive Programming (2015-10-25 - 2015-10-30) (Details)
- Dagstuhl-Seminar 17382: Approaches and Applications of Inductive Programming (2017-09-17 - 2017-09-20) (Details)
- Dagstuhl-Seminar 19202: Approaches and Applications of Inductive Programming (2019-05-12 - 2019-05-17) (Details)
- Dagstuhl-Seminar 21192: Approaches and Applications of Inductive Programming (2021-05-09 - 2021-05-12) (Details)
- Dagstuhl-Seminar 23442: Approaches and Applications of Inductive Programming (2023-10-29 - 2023-11-03) (Details)
- Dagstuhl-Seminar 25491: Approaches and Applications of Inductive Programming (2025-11-30 - 2025-12-05) (Details)
Klassifikation
- artificial intelligence / robotics
- programming languages / compiler
- verification / logic
Schlagworte
- inductive program synthesis
- end-user programming
- universal artificial intelligence
- constraint programming
- probabilistic programming
- cognitive modeling
