ITR: Semantically Tractable Questions: Theory and Implementation

University Of Washington, Seattle WA

Investigators

Abstract

Understanding arbitrary natural language sentences is widely regarded as very challenging. Yet understanding questions such as ``What is the capital of Italy?'' or ``What Chinese restaurants are open on Sunday in Seattle?'' seems straightforward even for a machine. While natural language sentences have the potential to be subtle, complex, and rife with ambiguity, they can also be simple, straight forward, and clear. This project formalizes this intuition by identifying classes of questions that are ``easy to understand'' in a well defined sense. People are unwilling to trade reliable and predictable user interfaces for intelligent but unreliable ones. To satisfy users, Natural Language Interfaces (NLIs) should not be allowed to misinterpret their questions often, if at all. Consequently, this research project has three components. First, it introduces a theoretical framework for analyzing the reliability of an NLI by formally defining the properties of soundness and completeness and identifying a class of semantically tractable natural language questions for which sound and complete NLIs can be built. Second, it is shown that the theory has practical import by measuring the prevalence of semantically tractable questions and by measuring the performance of a sound and complete NLI in practice. Finally, the project extends the framework to dialog systems and to increasingly broad classes of natural language sentences. The research has the potential to reinvigorate basic research on NLIs, and to have the broader societal impact of making powerful information resources more readily available to ordinary people regardless of their knowledge of Computer Science.