Dagstuhl Seminar 17382
Approaches and Applications of Inductive Programming
( Sep 17 – Sep 20, 2017 )
Permalink
Organizers
- Stephen H. Muggleton (Imperial College London, GB)
- Ute Schmid (Universität Bamberg, DE)
- Rishabh Singh (Microsoft Research - Redmond, US)
Contact
- Michael Gerke (for scientific matters)
- Annette Beyer (for administrative matters)
Impacts
- Computer Models Solving Intelligence Test Problems : Progress and Implications : Extended Abstract : in Proceedings of the Twenty-Sixth International Joint Conference on Artificial Intelligence, IJCAI 17 - Hernandez-Orallo, Jose; Martinez-Plumed, Fernando; Schmid, Ute; Siebers, Michael; Dowe, David L. - IJCAI 17 - IJCAI, 2017. - pp. 5005-5009.
- Ultra-Strong Machine Learning : comprehensibility of programs learned with ILP : article - Muggleton, Stephen H.; Schmid, Ute; Zeller, Christina; Tamaddoni-Nezhad, Alireza; Besold, Tarek R. - Berlin : Springer, 2018. - pp. 1119-1140 - (Machine learning ; 107. 2018).
Schedule
The Dagstuhl Seminar Approaches and Applications of Inductive Programming (AAIP'17) is a follow-up to the successful seminars 15442 (http://www.dagstuhl.de/15442) and 13502 (http://www.dagstuhl.de/13502) and is the 7th AAIP event overall (started as AAIP'05 as ICML workshop).
The term 'inductive programming' (IP) was coined in 2005 for the first AAIP event as a common label for inductive logic programming (ILP) and inductive functional programming. IP research addresses the problem of learning (mostly declarative) programs from incomplete specifications, such as input/output examples, observed traces, 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 generalization of current machine learning where the hypothesis space consists of classes of computer programs. Approaches to inductive programming are gaining interest in the machine learning community as the need for interpretability, verification, and debugging of learnt models (programs) is growing.
Researchers working on IP 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.
Interest in IP has been steadily growing over the last years. One reason is that with the release of FlashFill as a plug-in tool for Microsoft Excel there exists a convincing demonstration that inductive programming research has matured in such a way that commercial applications become feasible. Another one is that researchers in artificial intelligence and in machine learning are becoming more and more interested in comprehensible and explainable systems and inductive programming approaches provide symbolic representations of rules.
A long-term objective of the seminar series is to establish inductive programming as a self-contained research topic in artificial intelligence, especially as a field of machine learning and of cognitive modeling.
The seminar serves as community building event by bringing together researchers from different areas of inductive programming {especially inductive logic programming and inductive functional programming {, from different application areas such as end-user programming and tutoring, and from cognitive science research, especially from cognitive models of inductive (concept) learning. In this meeting we are open to discussions of the relationship between IP and other forms of machine learning including, for instance, neuro-symbolic learning. For successful community building we seek to balance junior and senior researchers, and to mix researchers from universities and from industry.
The two previous seminars resulted in new collaborations between researchers from different back-grounds as documented in joint publications and we expect that the collaborations will continue, deepen and extend, resulting not only in further joint publications but also in joint research projects.
In this seminar, we plan to continue and extend discussion addressing the following aspects:
- Identifying the specific contributions of inductive programming to machine learning research and applications of machine learning, especially identifying problems for which inductive programming approaches more suited than standard machine learning approaches, including deep learning.
- Establishing criteria for evaluating inductive programming approaches in comparison to each other and in comparison to other approaches of machine learning and providing a set of benchmark problems.
- Discussing current applications of inductive programming in end-user programming and programming education and identifying further relevant areas of application.
- Establishing stronger relations between cognitive science research on inductive learning and inductive programming.
Inductive programming (IP) addresses the automated or semi-automated generation of computer programs from incomplete information such as input-output examples, constraints, computation traces, demonstrations, or problem-solving experience [5]. The generated - typically declarative - program has the status of a hypothesis which has been generalized by induction. That is, inductive programming can be seen as a special approach to machine learning. In contrast to standard machine learning, only a small number of training examples is necessary. Furthermore, learned hypotheses are represented as logic or functional programs, that is, they are represented on symbol level and therefore are inspectable and comprehensible [17, 8, 18]. On the other hand, inductive programming is a special approach to program synthesis. It complements deductive and transformational approaches [20, 14, 2]. In cases where 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 [16].
Inductive program synthesis is of interest for researchers in artificial intelligence since the late sixties [1]. On the one hand, the complex intellectual cognitive processes involved in producing program code which satisfies some specification are investigated, on the other hand methodologies and techniques for automating parts of the program development process are explored. One of the most relevant areas of application of inductive programming techniques is end-user programming [3, 12, 4]. For example, the Microsoft Excel plug-in Flashfill synthesizes programs from a small set of observations of user behavior [8, 7, 6]. Related applications are in process mining and in data wrangling [11]. Inductive programming in general offers powerful approaches to learning from relational data [15, 13] and to learning from observations in the context of autonomous intelligent agents [10, 17]. Furthermore, inductive programming can be applied in the context of teaching programming [19, 21].
Recent Trends and Applications
When the first Dagstuhl Seminar on Approaches and Applications of Inductive Programming took place in 2013, the following trends could be identified:
- Combining different approaches to inductive programming to leverage their complementary strengths.
- New inductive programming approaches based on adapting and using well-developed techniques such as SAT-solving.
- Putting inductive programming to application, for example in the areas of automated string manipulations in spreadsheets or web programming.
- Applying concepts of inductive programming to cognitive models of learning structural concepts.
The main outcomes of the second seminar were (1) a joint publication in the Artificial Intelligence Journal with respect to the evaluation of computational models solving intelligence test problems – among them inductive programming systems [9], (2) a joint publication addressing comprehensibility as a second criterium to evaluate machine learning approaches besides accuracy [18], and (3) a NIPS’2016 workshop on Neural Nets and Program Induction.
Based on the results of the second seminar, the focus of the third seminar has been on the following aspects:
- Identifying the specific contributions of inductive programming to machine learning research and applications of machine learning, especially identifying problems for which inductive programming approaches more suited than standard machine learning approaches, including deep learning.
- Establishing criteria for evaluating inductive programming approaches in comparison to each other and in comparison to other approaches of machine learning and providing a set of benchmark problems.
- Discussing current applications of inductive programming in enduser programming and programming education and identifying further relevant areas of application.
- Establishing stronger relations between cognitive science research on inductive learning and inductive programming.
In the seminar, we brought together researchers from different areas of computer science - especially from machine learning, AI, declarative programming, and software engineering - and researchers from cognitive psychology interested in inductive learning as well as in teaching and learning computer programming. Furthermore, participants from industry presented current as well as visionary applications for inductive programming.
The seminar was opened with lecture style talks introducing the four major approaches of inductive programming: Inductive functional programming, inductive logic programming, inductive probabilistic logical programming, and programming by example.
Talks covered current developments of IP algorithms, challenging applications -especially in data wrangling and in education -, and relations of IP to cognition.
In addition, several system demons and tutorials were given: Igor and EasyIgor (by Sebastian Seufert and Ute Schmid), MagicHaskeller (by Susumu Katayama), Sketch (by Armando Solar-Lezama), PROSE (by Oleksandr Polozov), Slipcover (by Fabrizio Riguzzi), and TaCLe (by Luc De Raedt).
The following topics were identified and further discussed in working groups during the seminar:
- How to determine relevancy of background knowledge to reduce search?
- Integrating IP with other types of machine learning, especially Deep Learning?
- Data wrangling as exiting area of application.
Additional topics identified as relevant have been anomaly detection, noise, robustnes, as well as non-example based interaction (e.g., natural language).
Concluding remarks and future plans
In the wrapping-up section, we collected answers to the question
“What would constitute progress at Dagstuhl 2019?”
The most prominent answers were
- make available systems, data sets (via IP webpage)
- compare systems
- common vocabulary, work on applications attempted by others: drawing problems, string transformation, general ai challenge, benchmarks starexec, learn robot strategy, grammar learning what is inductive programming
- open problems
As the grand IP challenge we came up with: An IP program should invent an algorithm publishable in a serious journal (e.g., an integer factorization algorithm) or win a programming competition!
References
- A. W. Biermann, G. Guiho, and Y.Kodratoff, editors. Automatic Program Construction Techniques. Macmillan, New York, 1984.
- Rastislav Bodik and Emina Torlak. Synthesizing programs with constraint solvers. In CAV, page 3, 2012.
- A. Cypher, editor. Watch What I Do: Programming by Demonstration. MIT Press, Cambridge, MA, 1993.
- Allen Cypher, Mira Dontcheva, Tessa Lau, and Jeffrey Nichols, editors. No Code Required: Giving Users Tools to Transform the Web. Elsevier, 2010.
- P. Flener and U. Schmid. Inductive programming. In C. Sammut and G. Webb, editors, Encyclopedia of Machine Learning, pages 537-544. Springer, 2010.
- Sumit Gulwani. Automating string processing in spreadsheets using input-output examples. In 8th Symposium on Principles of Programming Languages. ACM, 2011.
- Sumit Gulwani, William R. Harris, and Rishabh Singh. Spreadsheet data manipulation using examples. Communications of the ACM, 55(8):97-105, 2012.
- Sumit Gulwani, José Hernández-Orallo, Emanuel Kitzelmann, Stephen H. Muggleton, Ute Schmid, and Benjamin G. Zorn. Inductive programming meets the real world. Commununications of the ACM, 58(11):90-99, 2015.
- José Hernández-Orallo, Fernando Martínez-Plumed, Ute Schmid, Michael Siebers, and David L Dowe. Computer models solving intelligence test problems: Progress and implications. Artificial Intelligence, 230:74-107, 2016.
- P. Langley and D. Choi. A unified cognitive architecture for physical agents. In Proceedings of the Twenty-First National Conference on Artificial Intelligence, Boston, MA, 2006. AAAI Press.
- Vu Le and Sumit Gulwani. Flashextract: A framework for data extraction by examples. ACM SIGPLAN Notices, 49(6):542-553, 2014.
- Henry Lieberman, editor. Your Wish is My Command: Programming by Example. Morgan Kaufmann, San Francisco, 2001.
- D. Lin, E. Dechter, K. Ellis, J.B. Tenenbaum, and S.H. Muggleton. Bias reformulation for one-shot function induction. In Proceedings of the 23rd European Conference on Artificial Intelligence (ECAI 2014), pages 525-530, Amsterdam, 2014. IOS Press.
- Zohar Manna and Richard Waldinger. A deductive approach to program synthesis. ACM Transactions on Programming Languages and Systems, 2(1):90-121, 1980.
- Stephen H. Muggleton, Dianhuan Lin, and Alireza Tamaddoni-Nezhad. Meta-interpretive learning of higher-order dyadic datalog: predicate invention revisited. Machine Learning, 100(1):49-73, 2015.
- Reudismam Rolim, Gustavo Soares, Loris D'Antoni, Oleksandr Polozov, Sumit Gulwani, Rohit Gheyi, Ryo Suzuki, and Bjoern Hartmann. Learning syntactic program transformations from examples. arXiv preprint arXiv:1608.09000, 2016.
- Ute Schmid and Emanuel Kitzelmann. Inductive rule learning on the knowledge level. Cognitive Systems Research, 12(3):237--248, 2011.
- Ute Schmid, Christina Zeller, Tarek Besold, Alireza Tamaddoni-Nezhad, and Stephen Muggleton. How does predicate invention affect human comprehensibility? In International Conference on Inductive Logic Programming, pages 52-67. Springer, 2016.
- Rishabh Singh, Sumit Gulwani, and Armando Solar-Lezama. Automated feedback generation for introductory programming assignments. ACM SIGPLAN Notices, 48(6):15-26, 2013.
- Douglas R. Smith. The synthesis of {LISP} programs from examples: A survey. In Automatic Program Construction Techniques, pages 307-324. Macmillan, 1984.
- Christina Zeller and Ute Schmid. Automatic generation of analogous problems to help resolving misconceptions in an intelligent tutor system for written subtraction. In Proceedings of the Workshop on Computational Analogy at the 24th International Conference on Case Based Reasoning (ICCBR 2016, Atlanta, GA, 31th October to 2nd November 2016), 2016.
- Aws Albarghouthi (University of Wisconsin - Madison, US) [dblp]
- Peter Buhler (IBM Research Zurich, CH) [dblp]
- Lidia Contreras-Ochando (Technical University of Valencia, ES) [dblp]
- Andrew Cropper (Imperial College London, GB) [dblp]
- Luc De Raedt (KU Leuven, BE) [dblp]
- Richard Evans (Google DeepMind - London, GB) [dblp]
- Cesar Ferri Ramirez (Technical University of Valencia, ES) [dblp]
- Elena Leah Glassman (University of California - Berkeley, US) [dblp]
- Katsumi Inoue (National Institute of Informatics - Tokyo, JP) [dblp]
- Frank Jäkel (PSIORI - Freiburg, DE) [dblp]
- Susumu Katayama (University of Miyazaki, JP) [dblp]
- Martin Möhrmann (Universität Osnabrück, DE) [dblp]
- Stephen H. Muggleton (Imperial College London, GB) [dblp]
- David Nieves Cordones (Technical University of Valencia, ES)
- Hila Peleg (Technion - Haifa, IL) [dblp]
- Alex Polozov (Microsoft Corporation - Redmond, US) [dblp]
- Fabrizio Riguzzi (University of Ferrara, IT) [dblp]
- Ute Schmid (Universität Bamberg, DE) [dblp]
- Sebastian Seufert (Universität Bamberg, DE)
- Michael Siebers (Universität Bamberg, DE) [dblp]
- Rishabh Singh (Microsoft Research - Redmond, US) [dblp]
- Armando Solar-Lezama (MIT - Cambridge, US) [dblp]
- Claes Strannegård (Chalmers University of Technology - Göteborg, SE) [dblp]
- Janis Voigtländer (Universität Duisburg-Essen, DE) [dblp]
- Christina Zeller (Universität Bamberg, DE) [dblp]
Related Seminars
- Dagstuhl Seminar 13502: Approaches and Applications of Inductive Programming (2013-12-08 - 2013-12-11) (Details)
- Dagstuhl Seminar 15442: Approaches and Applications of Inductive Programming (2015-10-25 - 2015-10-30) (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)
Classification
- artificial intelligence / robotics
Keywords
- inductive program synthesis
- inductive logic programming
- enduser programming
- probabilistic programming
- human-like computing