Sheepdog: learning procedures for technical support

ABSTRACT

Technical support procedures are typically very complex. Users often have trouble following printed instructions describing how to perform these procedures, and these instructions are difficult for support personnel to author clearly. Our goal is to learn these procedures by demonstration, watching multiple experts performing the same procedure across different operating conditions, and produce an executable procedure that runs interactively on the user's desktop. Most previous programming by demonstration systems have focused on simple programs with regular structure, such as loops with fixed-length bodies. In contrast, our system induces complex procedure structure by aligning multiple execution traces covering different paths through the procedure. This paper presents a solution to this alignment problem using Input/Output Hidden Markov Models. We describe the results of a user study that examines how users follow printed directions. We present Sheepdog, an implemented system for capturing, learning, and playing back technical support procedures on the Windows desktop. Finally, we empirically evalute our system using traces gathered from the user study and show that we are able to achieve 73% accuracy on a network configuration task using a procedure trained by non-experts.

REFERENCES

• 1: Y. Bengio and P. Frasconi. Input-output HMMs for sequence processing. IEEE Transactions on Neural Networks, 7(5):1231 -- 1249, September 1996.
• 2: Y. Bengio and P. Frasconi. Input-Output HMM's for Sequence Processing. IEEE Trans. Neural Networks, 7(5):1231--1249, September 1996.
• 3: 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
• 4: B.V. Dasarathy, editor. Nearest Neighbor Pattern Classification Techniques. IEEE Computer Society, 1991.
• 5: B. D. Davison and H. Hirsh. Predicting sequences of user actions. In Predicting the Future: AI Approaches to Time Series Problems, pages 5--12, Madison, WI, 1998. AAAI Press. Technical Report WS-98-07.
• 6: A.P. Dempster, N.M. Laird, and D.B. Rubin. Maximum likelihood from incomplete data via the EM algorithm. J. Royal Statistical Soc. B, 39(1):1--38, 1977.
• 7: P. Frasconi and Y. Bengio. An EM approach to grammatical inference: Input/output HMMs. In Proc. IEEE Int. Conf. Pattern Recognition, ICPR '94, pages 289--294, Jerusalem, October 9-13 1994.
• 8: Andrew Garland , Kathy Ryall , Charles Rich, Learning hierarchical task models by defining and refining examples, Proceedings of the 1st international conference on Knowledge capture, October 22-23, 2001, Victoria, British Columbia, Canada [doi>10.1145/500737.500748]
• 9: Benjamin Korvemaker , Russell Greiner, Predicting UNIX Command Lines: Adjusting to User Patterns, Proceedings of the Seventeenth National Conference on Artificial Intelligence and Twelfth Conference on Innovative Applications of Artificial Intelligence, p.230-235, July 30-August 03, 2000
• 10: 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]
• 11: 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]
• 12: H. Lieberman, editor. Your Wish is My Command: Giving Users the Power to Instruct their Software. Morgan Kaufmann, 2001.
• 13: G. W. Paynter. Automating iterative tasks with programming by demonstration. PhD thesis, University of Waikato, February 2000.
• 14: Lawrence R. Rabiner. A Tutorial on Hidden Markov Models and Selected Applications in Speech Recognition. Proceedings of the IEEE, 77(2):257--285, February 1989.
• 15: L. Siklóssy and D. A. Sykes. Automatic program synthesis from example problems. In Proceedings of the Fourth International Joint Conference on Artificial Intelligence, pages 268--273, Tblisi, Georgia, USSR, 1975. San Francisco, CA: Morgan Kaufmann.

INDEX TERMS

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

General Terms:
Algorithms, Design, Experimentation, Human Factors

Keywords:
alignment, hidden Markov models, machine learning, programming by demonstration, user study