A Measure of Semantic Complexity for Natural Language Systems

A Measure of Semantic Complexity for Natural Language Systems Shannon Pollard*and Alan W. Biermann Department of Computer Science, Duke University Box 90129, D224, LSRC, Durham, NC 27708-0129 office: (919)660-6583 fax: (919)660-6519 e-mail: shannon@cs.duke.edu Abstract This paper will describe a way to organize the salient objects, their attributes, and relationships between the objects in a given domain. This organization allows us to assign an information value to each col- lection, and to the domain as a whole, which cor- responds to the number of things to "talk about" in the domain. This number gives a measure of se- mantic complexity; that is, it will correspond to the number of objects, attributes, and relationships in the domain, but not to the level of syntactic diver- sity allowed when conveying these meanings. Defining a measure of semantic complexity for a dialog system domain will give an insight towards making a complexity measurement standard. With such a standard, natural language programmers can measure the feasibility of making a natural lan- guage interface, compare different language proces- sors' ability to handle more and more complex do- mains, and quantify the abilities of the current state of the art in natural language processors. 1 Introduction Quantification of task difficulty has been applied to many areas in artificial intelligence, including in- formation retrieval (Bagga, 1997) (Bagga and Bier- mann, 1997), machine learning (Niyogi, 1996), pars- ing and grammatical formalisms(G. Edward Bar- ton et al., 1987), and language learning in general (Ristad, 1993). In addition to providing a way of comparing systems, these measures quantify task complexity before a system is built. The goal of this paper is to measure the complexity of domains for dialog processing. With a standard measure of complexity, domains can be compared and analyzed without having to build the dialog system first. This measure would be an indication of the cost, amount of code, accuracy, reliability, and execution time of the finished dialog system specified by the domain. The hope is to have a single number or pair of num- bers that correlates strongly with these standard measures. * Supported by the Defense Advanced Research Projects Agency, CPoF project, Grant F30602-99-C-0060 Specifically, if domain D1 has complexity C1 and domain D2 has complexity C2 where C2 > C1, then we would expect D2 to have a greater cost of soft- ware, more lines of code, less accuracy, less reliabil- ity, and longer execution time. Section 2 will describe the difference in seman- tic and syntactic complexity and explain why we consider each separately. In section 3 we define the terms in the complexity analysis, which is explained in section 4. Sections 5 and 6 discuss how to compute information measures that are needed in the com- plexity analysis, and in sections 7 and 8 we present future work and conclude. 2 Semantic vs. Syntactic complexity The complexity measurement described above must be one that takes into account both the semantic and syntactic complexity of the domain. Semantic com- plexity is the number of …

Content truncated to 500 words