A probabilistic approach to reference resolution in multimodal user interfaces

ABSTRACT

Multimodal user interfaces allow users to interact with computers through multiple modalities, such as speech, gesture, and gaze. To be effective, multimodal user interfaces must correctly identify all objects which users refer to in their inputs. To systematically resolve different types of references, we have developed a probabilistic approach that uses a graph-matching algorithm. Our approach identifies the most probable referents by optimizing the satisfaction of semantic, temporal, and contextual constraints simultaneously. Our preliminary user study results indicate that our approach can successfully resolve a wide variety of referring expressions, ranging from simple to complex and from precise to ambiguous ones.

REFERENCES

• 1: Richard A. Bolt, “Put-that-there”: Voice and gesture at the graphics interface, ACM SIGGRAPH Computer Graphics, v.14 n.3, p.262-270, July 1980
• 2: J. Cassell , T. Bickmore , M. Billinghurst , L. Campbell , K. Chang , H. Vilhjálmsson , H. Yan, Embodiment in conversational interfaces: Rea, Proceedings of the SIGCHI conference on Human factors in computing systems: the CHI is the limit, p.520-527, May 15-20, 1999, Pittsburgh, Pennsylvania, United States [doi>10.1145/302979.303150]
• 3: Context-Based Multimodal Input Understanding in Conversational Systems, Proceedings of the 4th IEEE International Conference on Multimodal Interfaces, p.87, October 14-16, 2002 [doi>10.1109/ICMI.2002.1166974]
• 4: Philip R. Cohen , Michael Johnston , David McGee , Sharon Oviatt , Jay Pittman , Ira Smith , Liang Chen , Josh Clow, QuickSet: multimodal interaction for distributed applications, Proceedings of the fifth ACM international conference on Multimedia, p.31-40, November 09-13, 1997, Seattle, Washington, United States [doi>10.1145/266180.266328]
• 5: Steven Gold , Anand Rangarajan, A Graduated Assignment Algorithm for Graph Matching, IEEE Transactions on Pattern Analysis and Machine Intelligence, v.18 n.4, p.377-388, April 1996 [doi>10.1109/34.491619]
• 6: Barbara J. Grosz , Candace L. Sidner, Attention, intentions, and the structure of discourse, Computational Linguistics, v.12 n.3, p.175-204, July-September 1986
• 7: Gustafson, J., Bell, L., Beskow, J., Boye J., Carlson, R., Edlund, J., Granstrom, B., House D., and Wiren, M. AdApt -- a Multimodal Conversational Dialogue System in an Apartment Domain. Proceedings of 6th International Conference on Spoken Language Processing (ICSLP), 2000.
• 8: Carla Huls , Wim Claassen , Edwin Bos, Automatic referent resolution of deictic and anaphoric expressions, Computational Linguistics, v.21 n.1, p.59-79, March 1995
• 9: Michael Johnston , Philip R. Cohen , David McGee , Sharon L. Oviatt , James A. Pittman , Ira Smith, Unification-based multimodal integration, Proceedings of the eighth conference on European chapter of the Association for Computational Linguistics, p.281-288, July 07-12, 1997, Madrid, Spain
• 10: Michael Johnston, Unification-based multimodal parsing, Proceedings of the 36th annual meeting on Association for Computational Linguistics, August 10-14, 1998, Montreal, Quebec, Canada
• 11: Michael Johnston , Srinivas Bangalore, Finite-state multimodal parsing and understanding, Proceedings of the 18th conference on Computational linguistics, p.369-375, July 31-August 04, 2000, Saarbrücken, Germany [doi>10.3115/990820.990874]
• 12: Andrew Kehler, Cognitive Status and Form of Reference in Multimodal Human-Computer Interaction, Proceedings of the Seventeenth National Conference on Artificial Intelligence and Twelfth Conference on Innovative Applications of Artificial Intelligence, p.685-690, July 30-August 03, 2000
• 13: David B. Koons , Carlton J. Sparrell , Kristinn R. Thorisson, Integrating simultaneous input from speech, gaze, and hand gestures, Intelligent multimedia interfaces, American Association for Artificial Intelligence, Menlo Park, CA, 1993
• 14: Jeannette G. Neal , Stuart C. Shapiro, Intelligent multi-media interface technology, Intelligent user interfaces, ACM Press, New York, NY, 1991 [doi>10.1145/107215.128690]
• 15: J. G. Neal , C. Y. Thielman , Z. Dobes , S. M. Haller , S. C. Shapiro, Natural language with integrated deictic and graphic gestures, Readings in intelligent user interfaces, Morgan Kaufmann Publishers Inc., San Francisco, CA, 1998
• 16: Sharon Oviatt, Multimodal interfaces for dynamic interactive maps, Proceedings of the SIGCHI conference on Human factors in computing systems: common ground, p.95-102, April 13-18, 1996, Vancouver, British Columbia, Canada [doi>10.1145/238386.238438]
• 17: Sharon Oviatt , Antonella DeAngeli , Karen Kuhn, Integration and synchronization of input modes during multimodal human-computer interaction, Proceedings of the SIGCHI conference on Human factors in computing systems, p.415-422, March 22-27, 1997, Atlanta, Georgia, United States [doi>10.1145/258549.258821]
• 18: Sharon Oviatt, Mutual disambiguation of recognition errors in a multimodel architecture, Proceedings of the SIGCHI conference on Human factors in computing systems: the CHI is the limit, p.576-583, May 15-20, 1999, Pittsburgh, Pennsylvania, United States [doi>10.1145/302979.303163]
• 19: Sharon Oviatt, Multimodal system processing in mobile environments, Proceedings of the 13th annual ACM symposium on User interface software and technology, p.21-30, November 06-08, 2000, San Diego, California, United States [doi>10.1145/354401.354408]
• 20: Amanda Stent , John Dowding , Jean Mark Gawron , Elizabeth Owen Bratt , Robert Moore, The CommandTalk spoken dialogue system, Proceedings of the 37th annual meeting of the Association for Computational Linguistics on Computational Linguistics, p.183-190, June 20-26, 1999, College Park, Maryland [doi>10.3115/1034678.1034713]
• 21: Oliviero Stock, ALFRESCO: Enjoying the combination of natural language processing and hypermedia for information exploration, Intelligent multimedia interfaces, American Association for Artificial Intelligence, Menlo Park, CA, 1993
• 22: Tsai, W.H. and Fu, K.S. Error-correcting isomorphism of attributed relational graphs for pattern analysis. IEEE Trans. Sys., Man and Cyb., vol. 9, 1979, pp. 757--768.
• 23: Wolfgang Wahlster, User and discourse models for multimodal communication, Readings in intelligent user interfaces, Morgan Kaufmann Publishers Inc., San Francisco, CA, 1998
• 24: Zancanaro, M., Stock, O., and Strapparava, C. 1997. Multimodal Interaction for Information Access: Exploiting Cohesion. Computational Intelligence 13(7):439--464.
• 25: Michelle X. Zhou , Shimei Pan, Automated authoring of coherent multimedia discourse in conversation systems, Proceedings of the ninth ACM international conference on Multimedia, September 30-October 05, 2001, Ottawa, Canada [doi>10.1145/500141.500241]

INDEX TERMS

Primary Classification:
  H. Information Systems
  H.5 INFORMATION INTERFACES AND PRESENTATION (I.7)
      H.5.2 User Interfaces (D.2.2, H.1.2, I.3.6)
          Subjects: Theory and methods

Additional Classification:
  H. Information Systems
  H.5 INFORMATION INTERFACES AND PRESENTATION (I.7)
      H.5.2 User Interfaces (D.2.2, H.1.2, I.3.6)
          Subjects: Natural language

General Terms:
Algorithms

Keywords:
graph matching, multimodal user interfaces, reference resolution