https://www.dagstuhl.de/17382

17. – 20. September 2017, Dagstuhl-Seminar 17382

Approaches and Applications of Inductive Programming

Organisatoren

Stephen H. Muggleton (Imperial College London, GB)
Ute Schmid (Universität Bamberg, DE)
Rishabh Singh (Microsoft Research – Redmond, US)

Auskunft zu diesem Dagstuhl-Seminar erteilt

Dagstuhl Service Team

Dokumente

Dagstuhl Report, Volume 7, Issue 9 Dagstuhl Report
Motivationstext
Teilnehmerliste
Gemeinsame Dokumente
Programm des Dagstuhl-Seminars [pdf]

Summary

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

  1. A. W. Biermann, G. Guiho, and Y.Kodratoff, editors. Automatic Program Construction Techniques. Macmillan, New York, 1984.
  2. Rastislav Bodik and Emina Torlak. Synthesizing programs with constraint solvers. In CAV, page 3, 2012.
  3. A. Cypher, editor. Watch What I Do: Programming by Demonstration. MIT Press, Cambridge, MA, 1993.
  4. Allen Cypher, Mira Dontcheva, Tessa Lau, and Jeffrey Nichols, editors. No Code Required: Giving Users Tools to Transform the Web. Elsevier, 2010.
  5. P. Flener and U. Schmid. Inductive programming. In C. Sammut and G. Webb, editors, Encyclopedia of Machine Learning, pages 537-544. Springer, 2010.
  6. Sumit Gulwani. Automating string processing in spreadsheets using input-output examples. In 8th Symposium on Principles of Programming Languages. ACM, 2011.
  7. Sumit Gulwani, William R. Harris, and Rishabh Singh. Spreadsheet data manipulation using examples. Communications of the ACM, 55(8):97-105, 2012.
  8. 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.
  9. 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.
  10. 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.
  11. Vu Le and Sumit Gulwani. Flashextract: A framework for data extraction by examples. ACM SIGPLAN Notices, 49(6):542-553, 2014.
  12. Henry Lieberman, editor. Your Wish is My Command: Programming by Example. Morgan Kaufmann, San Francisco, 2001.
  13. 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.
  14. Zohar Manna and Richard Waldinger. A deductive approach to program synthesis. ACM Transactions on Programming Languages and Systems, 2(1):90-121, 1980.
  15. 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.
  16. 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.
  17. Ute Schmid and Emanuel Kitzelmann. Inductive rule learning on the knowledge level. Cognitive Systems Research, 12(3):237--248, 2011.
  18. 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.
  19. Rishabh Singh, Sumit Gulwani, and Armando Solar-Lezama. Automated feedback generation for introductory programming assignments. ACM SIGPLAN Notices, 48(6):15-26, 2013.
  20. Douglas R. Smith. The synthesis of {LISP} programs from examples: A survey. In Automatic Program Construction Techniques, pages 307-324. Macmillan, 1984.
  21. 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.
License
  Creative Commons BY 3.0 Unported license
  Ute Schmid

Dagstuhl-Seminar Series

Classification

  • Artificial Intelligence / Robotics

Keywords

  • Inductive program synthesis
  • Inductive logic programming
  • Enduser programming
  • Probabilistic programming
  • Human-like computing

Buchausstellung

Bücher der Teilnehmer 

Buchausstellung im Erdgeschoss der Bibliothek

(nur in der Veranstaltungswoche).

Dokumentation

In der Reihe Dagstuhl Reports werden alle Dagstuhl-Seminare und Dagstuhl-Perspektiven-Workshops dokumentiert. Die Organisatoren stellen zusammen mit dem Collector des Seminars einen Bericht zusammen, der die Beiträge der Autoren zusammenfasst und um eine Zusammenfassung ergänzt.

 

Download Übersichtsflyer (PDF).

Publikationen

Es besteht weiterhin die Möglichkeit, eine umfassende Kollektion begutachteter Arbeiten in der Reihe Dagstuhl Follow-Ups zu publizieren.

Dagstuhl's Impact

Bitte informieren Sie uns, wenn eine Veröffentlichung ausgehend von
Ihrem Seminar entsteht. Derartige Veröffentlichungen werden von uns in der Rubrik Dagstuhl's Impact separat aufgelistet  und im Erdgeschoss der Bibliothek präsentiert.