Coherence Maintenance
in Man-Machine Dialogue with Ellipses*

Alexander Gelbukh, Grigori Sidorov, and Igor A. Bolshakov

Center for Computing Research (CIC) of National Polytechnic Institute (IPN),
Av. Juan de Dios Bátiz, s/n, esq. Mendizabal, Zacatenco, C.P. 07738, Mexico D.F., Mexico.

Phone: (52) 5729-6000, ext. 56544. Fax: (52) 5586-2936
{gelbukh, sidorov, igor}@cic.ipn.mx

Abstract. The paper discusses the use of a dictionary of collocations for resolving referential ambiguity related with ellipsis in man-machine dialogue. A heuristic algorithm for the reconstruction of elliptical phrases of a special kind – short clarifications – using such a dictionary is presented.

 

Keywords: man-machine dialogue, ambiguity resolution, ellipsis, dictionaries.

1          Introduction

The dialogue has been recently in the focus of the linguistic research; see for example (Carberry and Lambert, 1999). At the same time, the problem of development of natural language interface modules for a long time has been at the agenda of artificial intelligence.

One of the difficult problems consists in omission of some parts of the expression that seem obvious for the human, but not for the system; this phenomenon is called ellipsis. For example, there are elliptical sentences where the noun phrases are omitted, like in

1.        “There is a printer in the store.”
“Narrow?”

In this example, the system must restore the omitted word to restore the intended link printer ¬ narrow, since the word narrow here stands for narrow printer.

In this paper, we discuss the ways of restoration of the lost links using the dictionary of a special type. We start from some language data exemplifying the problem. Then we formulate a necessary condition for the detection of the corresponding phenomenon. Finally, we discuss the structure of the dictionary used by the algorithm of restoration of the lost relationship, and describe the algorithm itself.

2          Ellipsis in Dialogue

We consider the cases of the elliptical construction where the omitted word was introduced into the dialogue in the previous utterance(s), and the purpose of the utterance is to clarify or add a detail to a previous one. Thus, we leave aside the cases where the omitted word was introduced, say, by the extralinguistic situation (say, both participants see a strange man; “Drunk,” says one of them) or by the pragmatics of the communication. Note that at least in the former cases, the dialogue is not coherent.

Let us consider several examples of such type of ellipsis. With each example, we indicate the part of speech (noun, verb, adjective, adverb) of the words involved. In each pair, the first element is omitted in the second utterance, though is explicitly present in the first one, e.g., the noun in the example 2 is omitted in the utterance Really fatal? where fatal stands for fatal error. We indicate the omission of the element with parentheses.

2.        (N) ® Adj (see also example 1)
“The user found an error in the program.”
“Really fatal?”

3.        (Adj) ® Adv
“It uses a dangerous tinder fuel.”
“Ecologically?”

4.        (Adv) ® Adv
“Is it dangerous to use this tinder fuel?”
“Ecologically.”

5.        (V) ® Adv
“Have you found the software you searched for it in the store?”
“Easily.”

6.        (V) ® N_obj
“John was eating.”
“Potatoes, as usually?”

7.        (V) ® N_indirect
“The error was found by the user.”
“In the program?”

8.        (V) ® N_subj
“Again cycles!”
“The program?”

9.        (N) ® N
“You can find this program in the store.”
“Of software?”

The problem of interpretation of these examples consists in the restoration of the omitted structural element. Traditionally this is viewed as filling in the gap in the syntactic structure by substitution, say, fatal error for error (example 2). For the purposes of the coherence maintenance in the dialogue, though, it is more appropriate to view the interpretation as establishing a link (similar to a syntactic one) between the words fatal and error across the utterances. This produces a connected semantic network of the whole dialogue:

Let us call such a link elliptical relation that in the example holds between the words fatal and error, the word fatal being the source of the relation and the word error being its target.

One of the problems is the detection of the very presence of the ellipsis of the type we consider here, i.e., detection of the fact that the structural incompleteness is due to a reference to a previously introduced word. Another problem is, as usually in language processing, ambiguity. For example, how should the program guess that in the example 2 it is the error that is fatal rather than the program or the user?

3          Detection of Ellipsis Using a Combinatory Dictionary

To restore the elliptical relations in the dialogue, we try to find a highly probable target for such a relation and in this way detect the very presence of the relation. For simplicity and to emphasize the commonality of elliptical relation with anaphoric one, we will call the target of elliptical relation an (elliptical) antecedent.

3.1    The necessary conditions for elliptical relation

We will call the words that potentially, with high probability can form a word combination combinable, and denote this as u  w. Here u is the governor and w is the dependent: error  fatal is true since the syntactic combination fatal ¬ error is highly probable; however, *fatal  error[1] is not true since *fatal ® error is impossible. Also *program  fatal is not true since *fatal program is not a combination that can be normally expected in the text. Other examples: error  program (error in the program), user  to find (user found an error), to find  error (to find an error). Note that this is a lexical property of the corresponding words, specified in the dictionary, rather than the syntactic relation in a specific context.

We will use the same symbol for parts of speech, meaning by V  N the fact that a verb in general can syntactically govern a noun. For example, the following relations do not hold: *Adj  Adj, *N  Adv, *Adv  V, etc. On the other hand, the following relations do hold: N  Adj, Adv  Adv, etc. (see the examples above). Note that this property for the parts of speech is specified in the grammar.

As we have seen, in the elliptical constructions under consideration, the target and the source of the relation form a syntactic word combination. Thus, denoting x and y the target and the source of the elliptical relation, we can note that in all examples above, the condition x  y holds. The following example illustrates the impossibility of the situation when the source of the ellipsis syntactically governs the antecedent:

10.     “This was fatal to my hopes.”
“The error?”

Though the dialogue is coherent, its interpretation with an elliptical relation *fatal ® error is impossible. We did not find any example where the dependent would be omitted in the elliptical construction. Thus, in the following condition, only one direction of the  relation is appropriate:

Condition 1. Elliptical relation between the antecedent x and source y is possible only if x  y.

If the lexical information is not available for a specific word, a relaxed condition using only the parts of speech POS (x) and POS (y) can be used, with less reliability of the positive result:

Condition 2. Elliptical relation between the antecedent x and source y is possible only if POS (x)  POS (y).

As our examples show, nearly any combination of parts of speech for which the Condition 2 holds can be found in an elliptical relation with some appropriate words. Since we treat the type of the ellipsis under consideration as a potential insertion of a word into the target utterance, the Condition 2 can be generalized as follows:

Condition 3. Elliptical relation between the antecedent x and source y is possible only if the utterance that contains x remains syntactically correct when y is added to it and syntactically connected to x.

However, such a generalized condition is much more expensive computationally to test.

A special case of elliptical relation is substitution of a word in the target utterance rather than insertion of a word. Such cases represent a combination of ellipsis and direct anaphora, as in the following example:

11.     “The program is cycling again.”
“WinWord?”

Here, WinWord is intended to substitute the program and then form a word combination WinWord is cycling. In this case, the source of the elliptical relation has to be a subtype of its target, and the substitution, the Conditions 1 to 2 should hold. In this article, we do not deal with such cases. Note that without the substitution, the example 11 will be filtered out by Condition 3 (though not by Condition 1 nor 2). However, the following example:

12.     “The user found a serious error in the program.”
“Fatal?”

will be accepted by Condition 3 in the interpretation that the error is both serious and fatal. This effect is related to the well-known distinction between repeatable (e.g., attributive) and non-repeatable (e.g., subjective) syntactic relations.

3.2    The algorithm and the dictionary for detecting potential elliptical antecedents

The algorithm for detecting potential antecedents works as follows. For each case of structural incompleteness, the hypothesis of the possible elliptical link is checked by trying, word by word, the candidates in the previous utterance and verifying the Conditions 1 to 3. Since the condition 2 is less computationally expensive, it is tried first; then the condition 1. The process stops when a plausible antecedent is found or when the distance from the end of the previous utterance becomes too large.

To check the condition 1, a dictionary of word combinations is used. For each headword, the dictionary lists the words that can syntactically combine with it, together with the prepositions (or grammatical cases) used in such a combination. In addition to the mere fact of combinability, the dictionary can specify a quantitative measure of the probability (frequency) of the combination in the texts. Such bigram dictionaries are trained on large text corpora (Yuret 1998).

In our experiments, we use the CrossLexica dictionary (Bolshakov 1994a, 1994b) in its part of word combinations. The Russian version of this dictionary contains more than 500,000 word combinations; the English version is under construction.

Note that some lexical relations – such as synonyms, hyponyms, etc. – are transparent for syntactical combinability. We consider such transparency (when it takes place) a part of the  relation.

The CrossLexica system automatically applies such rules to infer potential combinability of some words from the known combinability of other ones (Bolshakov and Gelbukh, 1999). Such an inference is performed only in the case if for a word w and a given type of syntactic relation r (such as objective, attributive, etc.) there is no information in the database about the words combinable with it by this relation, nor the information that there are no such words. Then the information about combinability of the word w with a word x by this particular relation r is inherited from another word u if any of the following conditions holds:

·           u is the most immediate superclass (hypernym) of w for which such information is available;

·           u is so-called dominant synonym of w, i.e., the near-synonym that does not have any additional meaning (and thus is similar to a hypernym);

·           w is a noun and u is the same noun in the other number (since plural and singular nouns have different combinability, they are handled separately by CrossLexica).

However, a relation is not inherited if any of the following exceptions apply:

·           x is an adjective expressing the selection of a subclass of the modifying noun u;

·           The source relation u  x or x  u is marked as idiomatic or has any stylistic mark.

4          Conclusions

We have discussed a dictionary-based heuristic algorithm of filtration of the possible candidates for indirect antecedents marked with a definite article or, as a special case, with a demonstrative pronoun. We also have discussed a dictionary-based heuristic algorithm of detection the elliptical antecedents in a special kind of elliptical utterances. The very fact that the phenomenon in question is present in the utterance at hand is checked by looking for a plausible elliptical antecedent.

The algorithm uses large dictionary with rather simple structure. However, it is rather simple and do not perform any deep linguistic analysis.

References

Ariel, M. 1988. Referring and accessibility. Journal of Linguistics, 24: 67-87.

Bol'shakov, I.A. 1994a. Multifunctional thesaurus for computerized preparation of Russian texts. Automatic Documentation and Mathematical Linguistics. Allerton Press Inc. Vol. 28, No. 1, 1994, p. 13-28.

Bolshakov, I.A. 1994b. Multifunction thesaurus for Russian word processing. Proceedings of 4th Conference on Applied Natural language Processing, Stuttgart, 13-15 October, 1994, p. 200-202.

Bolshakov, I.A., and A.F. Gelbukh, 1999. Enriquecimiento de la base de combinaciones de palabras por medio de un tesauro jerárquico (in Spanish). CIC-99, Simposium Internacional de Computación, November 15 - 19, 1999, Mexico D.F.

Bosch, P. 1988. Representing and accessing focussed referents. Language and Cognitive Processes, 3: 207-231.

Carberry, S., and Lambert, L. 1999. A process model for recognizing communicative acts and modeling negotiation subdialogues. Computational Linguistics, 25 (1): 1-54.

Chierchia, G. 1995. Dynamics of Meaning : Anaphora, Presupposition, and the Theory of Grammar. University of Chicago Press.

Cowan, R. 1995. What are Discourse Principles Made of? In P. Downing and M. Noonan (Eds.), Word Order in discourse. Benjamins, Amsterdam/Philadelfia.

Chafe, W. 1987. Cognitive Constraints in Information Flow. In R. Tomlin  (Ed.), Coherence and Grounding in Discourse. Benjamins, Amsterdam. pp. 21-51.

Chafe, W. 1994. Discourse, Consciousness, and Time. The University of Chicago Press, Chicago – London. 327 pp.

Cornish, F. 1999. Anaphora, Discourse, and Understanding : Evidence from English and French. Oxford Univ Press.

Downing, P., and M. Noonan (Eds.). 1995. Word Order in discourse. Benjamins, Amsterdam/Philadelfia. 595 pp.

Fraurud, K. 1992. Processing noun phrases in natural discourse. Doctoral dissertation, Stockholm University, Stockholm.

Fraurud, K. 1996. Cognitive ontology and NP form. In T. Fretheim and J. K. Gundel (Eds.), Reference and referent accessibility (pp. 193-212). John Benjamins, Amsterdam.

Fretheim, T., and J. K. Gundel (Eds.). 1996. Reference and referent accessibility. John Benjamins, Amsterdam.

Gelbukh, A. F., G. Sidorov, and A. Guzmán-Arenas. 1999. Use of a Weighted Topic Hierarchy for Document Classification. In: Text, Speech and Dialogue, Lecture Notes in Artificial Intelligence 1692, Springer, 1999.

Hahn, U., M. Strube, and K. Markert. 1996. Bridging textual ellipses. Proceedings of the 16th International Conference on Computational Linguistics. pp. 496-501.

Hellman, C. 1996. The ‘price tag’ on knowledge activation in discourse processing. In T. Fretheim and J. K. Gundel (Eds.), Reference and referent accessibility. John Benjamins, Amsterdam.

Lambrecht, K. 1994. Information Structure and Sentence Form. Topic, Focus and the Mental Representation of Discourse Referents. Cambridge University Press, Cambridge. 388 pp.

Mel’čuk, I. A. 1999. Communicative Organization in Natural Language: The Semantic-Communicative Structure of Sentence. 380 pp. (to appear)

Partee, B., and P. Sgall (Eds.). 1996. Discourse and Meaning. Papers in Honour of Eva Hajičova. Benjamins, Amsterdam/Philadelphia.

Rose, Carolyn Penstein, B. Di Eugenio, L. Levin, and C. Van Ess-Dykema. 1995. Discourse processing of dialogues with multiple threads. Proc. of the 33th ACL annual meeting, 31-38.

Sidorov, G., and  Gelbukh, A. (1999). Demonstrative pronouns as markers of indirect anaphora. Proc. 2^nd International Conference on Cognitive Science and 16^th Annual Meeting of the Japanese Cognitive Science Society Joint Conference (ICCS/JCSS99), July 27-30, 1999, Tokyo, Japan, pp. 418-423.

Tomlin, R. (Ed.). 1987. Coherence and Grounding in Discourse. Benjamins, Amsterdam. 512 pp.

Ward, G., and B. Birner. 1994. Definiteness and the English existential. Language, 71: 722-742.

Yuret, D. 1998. Discovery of linguistic relations using lexical attraction, Ph.D. thesis, MIT. See http://xxx.lanl.gov/abs/cmp-lg/9805009.