Interactive learning of structural shape descriptions from automatically generated near-miss examples

ABSTRACT

Sketch interfaces provide more natural interaction than the traditional mouse and palette tool, but can be time consuming to build if they have to be built anew for each new domain. A shape description language, such as the LADDER language we created, can significantly reduce the time necessary to create a sketch interface by enabling automatic generation of the interface from a domain description. However, structural shape descriptions, whether written by users or created automatically by the computer, are frequently over- or under- constrained. We present a technique to debug over- and under-constrained shapes using a novel form of active learning that generates its own suspected near-miss examples. Using this technique we implemented a graphical debugging tool for use by sketch interface developers.

REFERENCES

• 1: David Cohn , Les Atlas , Richard Ladner, Improving Generalization with Active Learning, Machine Learning, v.15 n.2, p.201-221, May 1994 [doi>10.1023/A:1022673506211]
• 2: Gennaro Costagliola , Genoveffa Tortora , Sergio Orefice , Andrea De Lucia, Automatic Generation of Visual Programming Environments, Computer, v.28 n.3, p.56-66, March 1995 [doi>10.1109/2.366162]
• 3: M. D. Gross. The electronic cocktail napkin - a computational environment for working with design diagrams. Design Studies, 17:53--69, 1996.
• 4: T. Hammond and R. Davis. LADDER: A language to describe drawing, display, and editing in sketch recognition. Proceedings of the 2003 Internaltional Joint Conference on Artificial Intelligence (IJCAI), 2003.
• 5: T. Hammond and R. Davis. Automatically transforming symbolic shape descriptions for use in sketch recognition. Proceedings of the Nineteenth National Conference on Artificial Intelligence (AAAI-04), pages 450--456, 2004.
• 6: T. Hammond and R. Davis. Shady: A shape description debugger for use in sketch recognition. AAAI Fall Symposium on Making Pen-Based Interaction Intelligent and Natural, 2004.
• 7: Allan Christian Long, Jr. , James A. Landay, Quill: a gesture design tool for pen-based user interfaces, 2001
• 8: O. Veselova and R. Davis. Perceptually based learning of shape descriptions. Proceedings of the Nineteenth National Conference on Artificial Intelligence (AAAI-04), pages 482--487, 2004.
• 9: VoiceXML Forum, http://www.voicexml.org/specs/VoiceXML-100.pdf. Voice eXtensible Markup Language, 1.00 edition, March 07 2000.
• 10: P. H. Winston. Learning structural description from examples. Psychology of Computer Vision, 1975.
• 11: Zue and Glass. Conversational interfaces: Advances and challenges. Proc IEEE, pages 1166--1180, 2000.

INDEX TERMS

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

Additional Classification:
  D. Software
  D.2 SOFTWARE ENGINEERING
      D.2.2 Design Tools and Techniques
          Subjects: User interfaces

  I. Computing Methodologies
  I.2 ARTIFICIAL INTELLIGENCE
        I.2.10 Vision and Scene Understanding
            Subjects: Shape; Representations, data structures, and transforms; Perceptual reasoning
      I.2.4 Knowledge Representation Formalisms and Methods
          Subjects: Representation languages; Representations (procedural and rule-based)

General Terms:
Algorithms, Design, Human Factors, Languages

Keywords:
active learning, ladder, near-miss, shape description, sketch recognition, structural description, user interfaces