Defining the complexity of natural language dialogue system domains
Ronnie W. Smith, Shannon Pollard · 2006
While Natural Language Dialogue Systems are becoming more widely used, there is a lack of theory addressing the complexity of the dialogue task. Because the technology can be used in many different domains, it is difficult to compare system performance or to hypothesize about the difficulty inherent in a new task. A theory of dialogue complexity would allow the task difficulty to be taken into account in system comparisons after implementation and give an indication of the difficulty in creating a system or applying certain algorithms before implementation. While there are many ways to quantify the complexity of the syntax in a domain, there are far fewer findings when it comes to the semantics of statements. In addition, the real job of understanding—converting syntax into semantics—is studied even less. This work provides a unified theory of the complexity of the dialogue system domain, taking into account the syntax the user is allowed, the semantics needed for the computer to understand user statements, the difficulty in translating the syntax into semantics (that is, the amount of ambiguity in the syntax), and the extent to which context models are used to aid in understanding. All complexity elements are calculated based on Claude Shannon's theory of information. The result is a suite of complexity measures calculating the bits per utterance (BPU) communicated by a user in a dialogue. Two methods of calculating the complexity are given. A corpus-based calculation is used when there is data available from experimental uses of the system, and a grammar-based calculation is also available so that the complexity can be calculated before the system is implemented. The resulting complexity measures give a way to affirm and quantify the dialogue system expert's intuition on the difficulty in the understanding task for a dialogue system in a specific domain. Results of several system analyses are given, showing that the complexity measures are applicable to various real-world domains. In addition, a tool for analyzing the complexity of existing and new domains is provided.