Learning programs from traces using version space algebra

ABSTRACT

While existing learning techniques can be viewed as inducing programs from examples, most research has focused on rather narrow classes of programs, e.g., decision trees or logic rules. In contrast, most of today's programs are written in languages such as C++ or Java. Thus, many tasks we wish to automate (e.g. programming by demonstration and software reverse engineering) might be best formulated as induction of code in a procedural language. In this paper we apply version space algebra [10] to learn such procedural programs given execution traces. We consider two variants of the problem (whether or not program-step information is included in the traces) and evaluate our implementation on a corpus of programs drawn from introductory computer science textbooks. We show that our system can learn correct programs from few traces.

REFERENCES

• 1: D. R. Barstow. An experiment in knowledge-based automatic programming. Artificial Intelligence, 12:73--119, 1979.
• 2: A. W. Biermann. On the Inference of Turing Machines from Sample Computations. Artificial Intelligence, 3:181--198, 1972.
• 3: Thomas T. Cormen , Charles E. Leiserson , Ronald L. Rivest, Introduction to algorithms, MIT Press, Cambridge, MA, 1990
• 4: Edsger Wybe Dijkstra, A Discipline of Programming, Prentice Hall PTR, Upper Saddle River, NJ, 1997
• 5: Michael D. Ernst , Adam Czeisler , William G. Griswold , David Notkin, Quickly detecting relevant program invariants, Proceedings of the 22nd international conference on Software engineering, p.449-458, June 04-11, 2000, Limerick, Ireland [doi>10.1145/337180.337240]
• 6: C. Green and D. Barstow. On program synthesis knowledge. Artificial Intelligence, 10:241--279, 1978.
• 7: David Gries, The Science of Programming, Springer-Verlag New York, Inc., Secaucus, NJ, 1987
• 8: Haym Hirsh. Theoretical underpinnings of version spaces. In Proceedings of the Twelfth International Joint Conference on Artificial Intelligence, pages 665--670. San Francisco, CA: Morgan Kaufmann, July 1991.
• 9: N. Kushmerick, D. Weld, and R. Doorenbos. Wrapper Induction for Information Extraction. In Proceedings of the Fifteenth International Joint Conference on Artificial Intelligence, pages 729--737. San Francisco, CA: Morgan Kaufmann, 1997.
• 10: Tessa A. Lau , Pedro Domingos , Daniel S. Weld, Version Space Algebra and its Application to Programming by Demonstration, Proceedings of the Seventeenth International Conference on Machine Learning, p.527-534, June 29-July 02, 2000
• 11: Henry Lieberman, editor. Your Wish is My Command: Giving Users the Power to Instruct their Software. Morgan Kaufmann, 2001.
• 12: Z. Manna and R. Waldinger. Knowledge and reasoning in program synthesis. Artificial Intelligence, 6, 1975.
• 13: T. Mitchell. Generalization as search. Artificial Intelligence, 18:203--226, 1982.
• 14: Dan Hua Mo. Learning Text Editing Procedures from Examples. Master's thesis, University of Calgary, December 1989.
• 15: C. Nédellec, C. Rouveirol, H. Adé, F. Bergadano, and B. Tausend. Declarative bias in ILP. In L. de Raedt, editor, Advances in Inductive Logic Programming, pages 82--103. IOS Press, Amsterdam, the Netherlands, 1996.
• 16: S. W. Norton and H. Hirsh. Classifier learning from noisy data as probabilistic evidence combination. In Proceedings of the Tenth National Conference on Artificial Intelligence, pages 141--146, Menlo Park, CA, 1992. AAAI Press.
• 17: Charles Rich , Richard C. Waters, The Programmer's Apprentice: A Research Overview, Computer, v.21 n.11, p.10-25, November 1988 [doi>10.1109/2.86782]
• 18: David E. Shaw, William R. Swartout, and C. Cordell Green. Inferring lisp programs from examples. In Proceedings of the Fourth International Joint Conference on Artificial Intelligence, pages 260--267, Tblisi, Georgia, USSR, 1975. San Francisco, CA: Morgan Kaufmann.

INDEX TERMS

Primary Classification:
  I. Computing Methodologies
  I.2 ARTIFICIAL INTELLIGENCE
      I.2.6 Learning
          Subjects: Knowledge acquisition

Additional Classification:
  I. Computing Methodologies
  I.2 ARTIFICIAL INTELLIGENCE
      I.2.2 Automatic Programming
          Subjects: Program synthesis
      I.2.6 Learning
          Subjects: Induction

General Terms:
Algorithms, Experimentation, Human Factors