The Computational Complexity of Avoiding Conversational Implicatures

THE COMPUTATIONAL COMPLEXITY OF AVOIDING CONVERSATIONAL IMPLICATURES Ehud Reiterf Aiken Computation Lab Harvard University Cambridge, Mass 02138 ABSTRACt Referring expressions and other object descriptions should be maximal under the Local Brevity, No Unnecessary Components, and Lexical Preference preference rules; otherwise, they may lead hearers to infer unwanted conversational implicatures. These preference rules can be incorporated into a polyno- mial time generation algorithm, while some alterna- tive formalizations of conversational impficature make the generation task NP-Hard. 1. Introduction Natural language generation (NLG) systems should produce referring expressions and other object descriptions that are free of false implicatures, i.e., that do not cause the user of the system to infer incorrect and unwanted conversational implicatures (Grice 1975). The following utterances illustrate referring expressions that are and are not free of false implicatures: la) "Sit by the table" lb) "Sit by the brown wooden table" In a context where only one table was visible, and this table was brown and made of wood, utterances (la) and (lb) would both fulfill the referring goal: a hearer who heard either utterance would have no trouble picking out the object being referred to. However, a hearer who heard utterance (lb) would probably assume that it was somehow important that the table was brown and made of wood, i.e., that the speaker was trying to do more than just identify the table. If the speaker did not have this intention, and only wished to tell the hearer where to sit, then this would be an incorrect conversational implicature, and could lead to problems later in the discourse. Accordingly, a speaker who only wished to identify the table should use utterance (la) in this situation, f Currently at the Depamnem of Artificial Intelligence, University of Edinburgh, 80 South Bridge, Edinburgh EHI 1HN, Scotland. 97 and avoid utterance (lb). Incorrect conversational implicatures may also arise from inappropriate attributive (informational) descriptions. 1 This is illustrated by the following utterances, which might be used by a salesman who wished to inform a customer of the color, material, and sleeve-length of a shirt: 2a) "I have a red T-shirt" 2b) "I have a lightweight red cotton shirt with short sleeves" Utterances (2a) and (2b) both successfully inform the hearer of the relevant properties of the shirt, assum- ing the hearer has some domain knowledge about T- shirts. However, if the hearer has this domain knowledge, the use of utterance (2b) might incorrectly implicate that the object being described was not a T-shirt -- because if it was, the hearer would reason, then the speaker would have used utterance (Za). Therefore, in the above situations the speaker, whether a human or a computer NLG system, should use utterances (la) and (2a), and should avoid utter- ances (lb) and (2b); utterances (la) and (2a) are free of false implicatures, while the utterances (lb) and (2b) are not. This paper proposes a computational model for determining when an object description is free of false implicatures. Briefly, a description is considered free of false implicatures if …

Content truncated to 500 words