Recovering from errors during programming by demonstration

ABSTRACT

Many end-users wish to customize their applications, automating common tasks and routines. Unfortunately, this automation is difficult today --- users must choose between brittle macros and complex scripting languages. Programming by demonstration (PBD) offers a middle ground, allowing users to demonstrate a procedure multiple times and generalizing the requisite behavior with machine learning. Unfortunately, many PBD systems are almost as brittle as macro recorders, offering few ways for a user to control the learning process or correct the demonstrations used as training examples. This paper presents CHINLE, a system which automatically constructs PBD systems for applications based on their interface specification. The resulting PBD systems have novel interaction and visualization methods, which allow the user to easily monitor and guide the learning process, facilitating error recovery during training. CHINLE-constructed PBD systems learn procedures with conditionals and perform partial learning if the procedure is too complex to learn completely.

REFERENCES

• 1: J. Allen, N. Chambers, G. Ferguson, L. Galescu, H. Jung, M. Swift, and W. Taysom. Plow: A collaborative task learning agent. In Proc. of AAAI'07.
• 2: Lawrence Bergman , Vittorio Castelli , Tessa Lau , Daniel Oblinger, DocWizards: a system for authoring follow-me documentation wizards, Proceedings of the 18th annual ACM symposium on User interface software and technology, October 23-26, 2005, Seattle, WA, USA [doi>10.1145/1095034.1095067]
• 3: J. Blythe. An analysis of procedure learning by instruction. In Proc. of AAAI-05
• 4: Jim Blythe, Task learning by instruction in tailor, Proceedings of the 10th international conference on Intelligent user interfaces, January 10-13, 2005, San Diego, California, USA [doi>10.1145/1040830.1040874]
• 5: C. A. Brewer. Color use guidelines for mapping and visualization. In A. MacEachren and D. Taylor, editors, Visualization in Modern Cartography, pages 123--147. Elsevier Science, 1994.
• 6: Vittorio Castelli , Lawrence Bergman, Distributed augmentation-based learning: a learning algorithm for distributed collaborative programming-by-demonstration, Proceedings of the 12th international conference on Intelligent user interfaces, January 28-31, 2007, Honolulu, Hawaii, USA [doi>10.1145/1216295.1216327]
• 7: Allen Cypher , Daniel C. Halbert , David Kurlander , Henry Lieberman , David Maulsby , Brad A. Myers , Alan Turransky, Watch what I do: programming by demonstration, MIT Press, Cambridge, MA, 1993
• 8: Randall Davis, Diagnostic reasoning based on structure and behavior, Artificial Intelligence, v.24 n.1-3, p.347-410, Dec. 1984 [doi>10.1016/0004-3702(84)90042-0]
• 9: Alexander Faaborg , Henry Lieberman, A goal-oriented web browser, Proceedings of the SIGCHI conference on Human Factors in computing systems, April 22-27, 2006, Montréal, Québec, Canada [doi>10.1145/1124772.1124883]
• 10: Martin R. Frank , James D. Foley, A pure reasoning engine for programming by demonstration, Proceedings of the 7th annual ACM symposium on User interface software and technology, p.95-101, November 02-04, 1994, Marina del Rey, California, United States [doi>10.1145/192426.192466]
• 11: Krzysztof Gajos , Daniel S. Weld, SUPPLE: automatically generating user interfaces, Proceedings of the 9th international conference on Intelligent user interfaces, January 13-16, 2004, Funchal, Madeira, Portugal [doi>10.1145/964442.964461]
• 12: H. Hirsh. Theoretical underpinnings of version spaces. In Proc. of IJCAI'91.
• 13: Won Chul Kim , James D. Foley, Providing high-level control and expert assistance in the user interface presentation design, Proceedings of the INTERCHI '93 conference on Human factors in computing systems, p.430-437, May 1993, Amsterdam, The Netherlands
• 14: Cory Kissinger , Margaret Burnett , Simone Stumpf , Neeraja Subrahmaniyan , Laura Beckwith , Sherry Yang , Mary Beth Rosson, Supporting end-user debugging: what do users want to know?, Proceedings of the working conference on Advanced visual interfaces, May 23-26, 2006, Venezia, Italy [doi>10.1145/1133265.1133293]
• 15: Andrew J. Ko , Brad A. Myers, Designing the whyline: a debugging interface for asking questions about program behavior, Proceedings of the SIGCHI conference on Human factors in computing systems, p.151-158, April 24-29, 2004, Vienna, Austria [doi>10.1145/985692.985712]
• 16: Tessa Lau , Lawrence Bergman , Vittorio Castelli , Daniel Oblinger, Sheepdog: learning procedures for technical support, Proceedings of the 9th international conference on Intelligent user interfaces, January 13-16, 2004, Funchal, Madeira, Portugal [doi>10.1145/964442.964464]
• 17: 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
• 18: Tessa Lau , Pedro Domingos , Daniel S. Weld, Learning programs from traces using version space algebra, Proceedings of the 2nd international conference on Knowledge capture, October 23-25, 2003, Sanibel Island, FL, USA [doi>10.1145/945645.945654]
• 19: Tessa Lau , Steven A. Wolfman , Pedro Domingos , Daniel S. Weld, Programming by Demonstration Using Version Space Algebra, Machine Learning, v.53 n.1-2, p.111-156, October-November 2003 [doi>10.1023/A:1025671410623]
• 20: L. Liao, D. Fox, and K. H. Location-based activity recognition using relational markov networks. In Procs. of IJCAI'05.
• 21: H. Lieberman. Your Wish is My Command: Giving Users the Power to Instruct their Software. Morgan Kaufmann, 2001.
• 22: H. Lieberman. End User Development. Springer, 2006.
• 23: Greg Little , Tessa A. Lau , Allen Cypher , James Lin , Eben M. Haber , Eser Kandogan, Koala: capture, share, automate, personalize business processes on the web, Proceedings of the SIGCHI conference on Human factors in computing systems, April 28-May 03, 2007, San Jose, California, USA [doi>10.1145/1240624.1240767]
• 24: Greg Little , Robert C. Miller, Translating keyword commands into executable code, Proceedings of the 19th annual ACM symposium on User interface software and technology, October 15-18, 2006, Montreux, Switzerland [doi>10.1145/1166253.1166275]
• 25: Roderick J A Little , Donald B Rubin, Statistical analysis with missing data, John Wiley & Sons, Inc., New York, NY, 1986
• 26: T. Mitchell. Generalization as search. Artificial Intelligence, 18:203--226, 1982.
• 27: Jeffrey Nichols , Brad A. Myers , Michael Higgins , Joseph Hughes , Thomas K. Harris , Roni Rosenfeld , Mathilde Pignol, Generating remote control interfaces for complex appliances, Proceedings of the 15th annual ACM symposium on User interface software and technology, October 27-30, 2002, Paris, France [doi>10.1145/571985.572008]
• 28: Daniel Oblinger , Vittorio Castelli , Lawrence Bergman, Augmentation-based learning: combining observations and user edits for programming-by-demonstration, Proceedings of the 11th international conference on Intelligent user interfaces, January 29-February 01, 2006, Sydney, Australia [doi>10.1145/1111449.1111494]
• 29: I. H. Paynter, G. W. and Witten. Applying machine learning to programming by demonstration. Journal of Experimental and Theoretical Artificial Intelligence, 16(3):161--188, 2004.
• 30: J. Ross Quinlan, C4.5: programs for machine learning, Morgan Kaufmann Publishers Inc., San Francisco, CA, 1993
• 31: Charles Wiecha , William Bennett , Stephen Boies , John Gould , Sharon Greene, ITS: a tool for rapidly developing interactive applications, ACM Transactions on Information Systems (TOIS), v.8 n.3, p.204-236, July 1990 [doi>10.1145/98188.98194]
• 32: Steven A. Wolfman , Tessa Lau , Pedro Domingos , Daniel S. Weld, Mixed initiative interfaces for learning tasks: SMARTedit talks back, Proceedings of the 6th international conference on Intelligent user interfaces, p.167-174, January 14-17, 2001, Santa Fe, New Mexico, United States [doi>10.1145/359784.360332]

INDEX TERMS

Primary Classification:
  D. Software
  D.2 SOFTWARE ENGINEERING
      D.2.2 Design Tools and Techniques

Additional Classification:
  H. Information Systems
  H.1 MODELS AND PRINCIPLES
      H.1.2 User/Machine Systems

General Terms:
Algorithms, Human Factors