Abstract
The paper discusses the use of dictionaries for resolving referential ambiguity in dialogue. We present a heuristic algorithm for detection of the indirect antecedents for dialogue phrases based on the use of a dictionary of prototypic scenarios associated with each headword, as well as of a thesaurus of the standard type. The conditions for filtration of the candidates for the antecedent are presented. The structure of the prototypic scenarios dictionary is discussed. We also present an algorithm for reconstruction of elliptical phrases of a special kind – short clarifications – in dialogue using a kind of a combinatory dictionary, with similar heuristic rules.
1. Introduction
The dialogue has been recently in the focus of the linguistic research, see for example [2], [3], [9]. At the same time, the problem of development of natural language interface modules for a long time has been on the agenda of artificial intelligence.
One of the difficult problems in the design of a dialogue interface module is that of the anaphoric relations in consequent dialogue phrases. In this paper, we discuss a special and more complicated that a usual one kind of anaphoric relation, so called indirect anaphora [7], [8]. An example of such a problem is given by the dialogue:
1.
“There is a PS/2 computer in the
store.”
“Is the motherboard from Intel?”
Here, there is an anaphoric relation computer ¬ the motherboard, since the motherboard stands for its motherboard (with computer ¬ it), or the motherboard of the computer.
The difference between the usual, or direct, anaphora, and indirect anaphora, as in the example 1, consists in that in case of the indirect anaphora, the anaphoric relation holds between two conceptually different words, such as computer and motherboard. Note that there is no direct coreference between these two words. Nevertheless such a phenomenon is very common in natural dialogues, a human-machine dialogue system must be able to restore the omitted relation.
Another, even more difficult problem 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 (see, for example [6]). Let us consider an example,
2. “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 spite of the similarity between the two phenomena, ellipsis and indirect anaphora (which looks much like ellipsis, with motherboard in the example 1 standing for its motherboard), the methods of the restoration of the links are slightly different.
In this paper, we discuss the ways of restoration of the lost links using two different dictionaries. In the first part of the article, we discuss the problem of indirect antecedents; in the second part, the problem of ellipsis. Both parts of the article have the same structure. 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. Indirect Antecedents in Dialogue
Let us consider some examples of the indirect antecedents in dialogues. In each example, the first line is the utterance of the first participant of the dialogue (supposedly the computer), and the second line is the reply of the second participant. The unacceptable variants are marked with an asterisk.
1.
“You can buy a house.”
“Is the/*this kitchen large?”
2.
“You
can buy a house.”
“What are the/*these
dimensions?”
3.
“You
can buy a house.”
“Who is the/*this previous
owner?”
4.
“John
sold a house.”
“Did he count the/*this money
carefully?”
5.
“You sold a house.”
“What can I do with the/this money?”
6.
“Do
you want to buy the house?”
“I like the/this price.”
7.
“You
sold a house.”
“Is the/this selling
profitable?”
8.
“Do
you want to buy a house?”
“Is the/this cottage
convenient?”
9.
““You sold a
house.”
“I did not like the/this architect.”
The problem is to find the interpretation of the definite clause in the second utterance of each dialogue. In our opinion this is anaphoric link. Making the link explicit is necessary to maintain the coherence of the dialogue, connecting together the semantic graphs of different utterances.
For instance, in the example 1 the indirect anaphoric relation holds between kitchen and house: the kitchen
is the kitchen of this house. In this case, the semantic network of the
dialogue is made connected by restoring the implicit link 
between the two
representations of the utterances:
.
A question arises: How to distinguish the cases when the dialogue is coherent and the indirect antecedent of the noun groups marked with the definite article or a demonstrative pronoun can be found in the dialogue, and in this case, how to find it?
3. Detection of Antecedents with a Scenario Dictionary
The idea of the algorithm we present in this section is to find a possible antecedent for a word that is suspected to be the source of an anaphoric relation, and if such a highly probable antecedent is found, in this way detect the very fact of the presence of the anaphoric relation between the utterances of the dialogue.
Let us call the entities implicitly or potentially introduced by a word a prototypic scenario of this word. For example, the scenario for the word house includes kitchen, roof, windows, district, place, owner, etc. Thus, the first utterance in the example 1 introduces in the common view of the participants all these entities: the house, its kitchen, the district it is located in, etc. We suggest that the indirect anaphoric relation holds between a word and an element of the prototypic scenario of another word previously appeared in the text.
The possibility or impossibility for a potential link to exist between two words in the dialogue depends on two kinds of conditions: semantic properties of the two words in question and the form of the utterance.
The first condition is illustrated by the cases where the definite article or demonstrative pronoun has no anaphoric interpretation similar to the one in the previous examples:
10. “I bought a house.”
* “Are the/this flowers beautiful?”
Obviously, such a dialogue is incoherent: either the second participant of the dialogue has shifted her attention to another topic, or some information significant for the maintenance of the dialogue coherence has been lost.
The second condition is illustrated by different interpretations of the dialogues with the anaphora expressed with the definite article the and the demonstrative pronoun this in the examples above. The peculiarities of the usage of the demonstrative pronouns are discussed in detail in [10] and are represented by Condition 2.
Let us denote the potential antecedent x, the anaphor y, and the scenario of a word w, S (w). Note that the Conditions are necessary but not sufficient.
Condition 1 (preliminary version). Indirect anaphoric relation between x and y is possible only if any of the following conditions hold:
· y Î S (x), or
· x Î S (y), or
· S (x) Ç S (y) ¹ Æ.
Condition 2. Indirect anaphora can be expressed by a demonstrative pronoun if both of the following conditions hold:
· The antecedent denotes a process or situation and
· The anaphor is included into the lexical meaning of the antecedent.
However, the Condition 1 is most important for the detection of the antecedents, since the other conditions are usually satisfied.
Let us call the words that are equivalent for our algorithms compatible. Then Condition 1 is satisfied even if the word in question does not belong to the corresponding scenario, but a compatible word does. Thus, synonyms, derivatives, hypernyms, hyponyms, and metaphors of a word can be compatible with it (see [10]). Denoting the compatibility relation between the words w and u as w ~ u, we can reformulate the Condition 1 as follows:
Condition 1. Indirect anaphoric relation between x and y is possible only if any of the following conditions holds:
· $ w Î S (x) such that y ~ w, or
· $ w Î S (y) such that x ~ w, or
· $ w Î S (x) and $ u Î S (y) such that u ~ w.
The algorithm for detecting anaphoric links between the utterances in the dialogue, or within an utterance, works as follows. It analyzes the current utterance word by word. If a word is introduced with a definite article or a demonstrative pronoun, then it is a potential anaphor, and the algorithm tries to find a plausible antecedent for it. It looks for the possible candidates first within the same utterance and then in the previous utterance(s) from right to left. The candidates are a priori scored the lower the greater the distance; the algorithm stops when an antecedent with high score is found or the scores become too little.
For each candidate, the conditions described above are tested. If the candidate satisfies all applicable conditions (and has the scores above the threshold), the anaphoric link is found.
To check the possibility of an indirect antecedent, a prototypic scenario dictionary is used. In our experiments, we used a dictionary compiled from several sources, such as Clasitex’s dictionary [5], FACTOTUM SemNet dictionary derived from the Roget thesaurus, and some other dictionaries. Currently the dictionary contains about 1,000 entries, and the scenarios contain in total about 40,000 words.
Our dictionary of prototypic scenarios has the structure suggested in [5]. In such a dictionary, each headword is supplied with a list of words represented the potential participants of the corresponding situation. For example, the dictionary entry for the word church includes the words related to this one in the dictionaries mentioned above: priest, candle, icon, prayer, etc.
The relations between these words and the headword do not have to be one of the standard relations (such as subtype, part, actant, etc.). Since our algorithm does not use the type of the relation, it does not have to be specified in the dictionary.
4. 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.
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, e.g., the noun in the example 11 is omitted in the utterance Really fatal? where fatal stands for fatal error. We indicate the omission of the element with parentheses.
11. (N) ® Adj (see also example 2): “The user found an error in the program.” -“Really fatal?”
12. (Adj) ® Adv: “It uses a dangerous tinder fuel.” - “Ecologically?”
13. (Adv) ® Adv: “Is it dangerous to use this tinder fuel?” - “Ecologically.”
14. (V) ® Adv: “Have you found the software you searched for it in the store?” - “Easily.”
15. (V) ® Nobj: ”John was eating.” - “Potatoes, as usually?”
16. (V) ® Nindirect: ”The error was found by the user.” - “In the program?”
17. (V) ® Nsubj :”Again cycles!” - “The program?”
18. (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 11). 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.
5. Detection of Ellipsis Using a Combinatory Dictionary
To restore the elliptical relations in the dialogue, we use the same idea as for the indirect anaphoric relations. Namely, we try to find a highly probable target.
We 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 is not true since fatal ® error is impossible.
Also program 
fatal is not true since normally 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 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:
19. “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 3. Elliptical relation between x and 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 4. Elliptical relation between x and y is possible only if POS (x) 
POS (y).
As our examples show, nearly any combination of parts of speech for which the Condition 4 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 4 can be generalized as follows:
Condition 5. Elliptical relation between x and y is possible only if the utterance containing the target (x) remains syntactically correct when the source (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:
20. “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 3 to 5 should hold. In this article, we do not deal with such cases. Note that without the substitution, the example 20 will be filtered out by Condition 5 (though not by Conditions 3 nor 4). However, the following example:
21. “The user
found a serious error in the program.”
“Fatal?”
will be accepted by Condition 5 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.
The algorithm for detecting potential antecedents is very much similar to the one for detecting the indirect antecedents. Namely, 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 3 to 5. Since the condition 4 is less computationally expensive, it is tried first; then the condition 3. 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 3, 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.
In our experiments, we use the CrossLexica dictionary (Bolshakov 1994) 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.
As in the case of the indirect anaphora,
some lexical relations – such as synonyms, hyponyms, etc. – are transparent for
syntactical combinability. However, the rules for the presence or absence of
such transparency are more complicated than those for the case of anaphora are.
Because of this, 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 [1]. 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.
6. Conclusions
A substantial similarity can be noted between our handling of indirect anaphoric and elliptical antecedents. Probably the similarity is due to the fact that both phenomena are equivalent to a combination of ellipsis with direct anaphora expressed by the pronoun it, though in different grammatical function. For example, the second utterance of the example 1 is equivalent to “Is its kitchen large?”, and of the example 11, “Is it fatal?” (When the antecedent is not a noun, a pronoun it cannot be used to refer to it on the surface; however, conceptually the structure of the phenomenon is the same (one can even imagine a “pronoun” for a verb, like in “The program does?” for the example 17).
However, there are two significant differences between these two cases. In the case of ellipsis, an easy to detect structural incompleteness of the text with high probability indicates the type of the ellipsis we have discussed, and the task is only to find the antecedent. For indirect anaphora, though, its very presence in the utterance containing a definite noun group is to be automatically detected and proved. In the case of anaphora, semantic relations are involved, which are more regular than the syntactic relations involved in the resolution of ellipsis, e.g., as to the rules of compatibility of the words.
We have discussed a dictionary-based heuristic algorithm of filtration of the possible candidates for indirect antecedents marked with a definite article or a demonstrative pronoun. We also discussed a similar algorithm of detection the elliptical antecedents in a special kind of elliptical utterances. In both cases, the very fact that the phenomenon in question is present in the utterance is checked by looking for a plausible (anaphoric or elliptical) antecedent.
The algorithms use large dictionaries with rather simple structure. The algorithms are not complicated and do not perform any deep linguistic analysis.
References
[7] Indirect Anaphora Workshop. 1996. Lancaster University, Lancaster.