Generation of Unambiguous Utterances

A fundamental assumption is that it is often possible to obtain an unambiguous utterance by slightly changing an ambiguous one. Thus, after generating an ambiguous utterance, it may be possible to change that utterance locally, to obtain an unambiguous utterance with the same meaning. In the case of a simple lexical ambiguity this idea is easily illustrated. Given the two meanings of the word `bank' (`riverside' vs. `money institution') a generator may produce, as a first possibility, the following sentence in the case of the first reading of `bank'.

To `repair' this utterance we simply alter the word `bank' into the word `river side' and we obtain an unambiguous result. Similar examples can be constructed for structural ambiguities. Consider the German sentence:

which is ambiguous (in German) between `withdraw [the army of Croatia]' and `[withdraw [the army] away from Croatia]'. In German this ambiguity can be repaired locally simply by changing the order of `aus Kroatien' and `die Armee', which forces the second reading. Thus again we only need to change only a small part of the utterance in order for it to be un-ambiguous.

Figure 2: Derivation trees

Locating ambiguity with derivation trees

We hypothesise that a good way to characterise the location of the ambiguity of an utterance is by referring to the notion `derivation tree'. We are assuming that the underlying grammar formalism comes with a notion `derivation tree' which represents how a certain derivation is licenced by the rules and lexical entries of the grammar. Note that such a derivation tree does not necessarily reflect how the parser or generator goes about finding such a derivation for a given string or logical form. For example, the derivation trees for the two readings of `John is standing near the bank' may look as in figure 2. The intuition that the ambiguity of this sentence is local is reflected in these derivation trees: the trees are identical up to the difference between bank4 and bank7. For simplicity we assume that in our examples each sign sign(LF,Str,Syn,D) is specified for its corresponding derivation tree D, where the other arguments represent the semantic information (LF), the string (Str) and syntactic information (Syn). In Prolog such a tree is represented with terms of the form t(Label,Ds,M) where Label is the node name (the unique name of a rule) and Ds is a list of Daughter trees. The third argument position will be explained below.

Given a derivation tree t of a generated sentence s, we can now mark the places where the ambiguity occurs as follows. If s is ambiguous it can be parsed in several ways, giving rise to a set of derivation trees T = t₁...t_n. We can now compare t with the set of trees T in a top-down fashion. If for a given node label in t there are several possible labels at the corresponding nodes in T then we have found an ambiguous spot, and the corresponding node in t is marked. Thus, in the previous example of structural ambiguity we may first generate sentence (6) above. After checking whether this sentence is ambiguous we obtain, as a result, the marked derivation tree of that sentence. A marked node in such a tree relates to an ambiguity. The relevant part of the resulting derivation tree of the example above may be the tree in figure 3.

Figure 3: Marked derivation tree

Marking a derivation tree

The predicate mark(Tree,Set) marks the generated tree Tree given the trees Set found by the parser. The third argument M of the terms t(Label,Ds,M) representing derivation trees indicates whether the current node is marked (in that case the value is y) or not (using the value n). Subtrees of marked nodes have no instantiated value for this variable. root_same(L,[]). root_same(L,[t(L,_,_)|T]):- root_same(L,T).

mark_ds([],[]).
mark_ds([H|T],[Hs|Ts]):-
    mark(H,Hs), mark_ds(T,Ts).

get_f([],[],[]). get_f([t(_,[H3|B],_)|T], [t(_,B,_)|T2],[H3|T3]):- get_f(T,T2,T3).

Changing the ambiguous parts

Generating an utterance given a marked derivation tree proceeds as follows. The generator simply `repeats' the previous generation in a top-down fashion, as long as it encounters unmarked nodes. This part of the generation algorithm thus simply copies previous results. If a marked node is encountered the embedded generation algorithm is called for this partial structure. The result should be a different derivation tree from the given one. Now clearly, this may or may not be possible depending on the grammar. The next paragraph discusses what happens if it is not possible.

The following definition assumes that grammar rules are represented simply as rule(Name, Mother, Ds) where Name is the rule name, Mother is the mother sign and Ds is a list of daughter signs. The predicate mgen is used to generate an utterance, using a marked derivation tree as an extra guide. mgen(sign(Lf,Str,S,D),t(Name,Ds,n)):- rule(Name,sign(Lf,Str,S,D),Kids), mgen_ds(Kids,Ds).

mgen_ds([],_).
mgen_ds([S|T],[Stree,Ttree]):-
    mgen(S,Stree),
    mgen_ds(T,Ttree).

Redefining locality

Often it will not be possible to generate an alternative expression by a local change as we suggested. We propose that the monitor first tries to change things as locally as possible. If all possibilities are tried, the notion `locality' is redefined by going up one level. This process repeats itself until no more alternative solutions are possible. Thus, given a marked derivation tree the monitored generation first tries to find alternatives for the marked parts of the tree. If no further possibilities exist, all markers in the trees are inherited by their mother nodes. Again the monitored generation tries to find alternatives, after which the markers are pushed upwards yet another level, etc.

It is possible that by successively moving markers upwards in a marked derivation tree the root node of the tree will be marked. If also in that case no unambiguous alternative will be possible then this means that the generator is not able to compute a grammatical unambiguous alternative. In this case the whole monitored generation process terminates and the strategic component has to decide whether to utter the ambiguous structure or to provide an alternative logical form.

The following definition of the predicate mark_l_g(Tree, Set, Guide) will (procedurally speaking) first construct the `guide' Guide given a derivation tree Tree and a set of derivation trees Set; upon backtracking it will push the markers in the tree one level upward at the time. l_g(Tree,Tree). l_g(Tree,Guide):- one_up(Tree,Tree2), l_g(Tree2,Guide).

one_up_ds([],[]). one_up_ds([H|T],[H2|T2]):- one_up(H,H2), one_up_ds(T,T2).

Now, the whole algorithm can be completed as follows. ⁶

revision(sign(LF,Str1,Syn1,D1),TreeSet,sign(LF,Str,Syn,D)):- mark_l_g(D1,TreeSet,Guide), mgen(sign(LF,Str,Syn,D),Guide), unambiguous(sign(_,Str,_,_)).

find_all_parse(Sign,SignSet,TreeSet) :-
    setof(Sign,parse(Sign),SignSet),
    extract_trees(SignSet,TreeSet).

unambiguous(Sign):-
    find_all_parse(Sign,[One],_).

Summarising, the generator first generates a possible utterance. This utterance is then given as input to the monitor. The monitor calls the parser to find which parts of that utterance are ambiguous. These parts are marked in the derivation tree associated with the utterance. Finally the monitor tries to generate an utterance which uses alternative derivation trees for the marked, i.e., ambiguous parts, eventually pushing the markers successively upwards.

Simple attachment example

In order to clarify the monitoring strategy we will now consider how an attachment ambiguity may be avoided. The following German sentence constitutes a simplified example of the sort of attachment ambiguity shown in (6).

Suppose indeed that the generator, as a first possibility, constructs this sentence in order to realize the (simplified) semantic representation:

mit(fernglas, sehen(pl (mann), frau))

The corresponding derivation tree is the left tree in figure 4.

Figure 4: Derivation trees of the simple attachment example

To find out whether this sentence is ambiguous the parser is called. The parser will find two results, indicating that the sentence is ambiguous. For the alternative reading the right derivation tree shown in figure 4 is found. The derivation tree of the result of generation is then compared with the trees assigned to the alternative readings (in this case only one), given rise to the marked derivation tree shown in figure 5.

Figure 5: Marked tree of German example

The monitored generation will then try to find alternative possibilities at these marked nodes. However, no such alternatives exist. Therefore, the markers are pushed up one level, obtaining the derivation tree given in figure 6.

Figure 6: Markers are pushed one level upward

At this point the monitored generator again tries to find alternatives for the marked nodes, this time successfully yielding:

At this point we may stop. However, note that if we ask for further possibilities we will eventually obtain all possible results. For example, if the markers are pushed to the root node of the derivation tree we will also obtain

Properties

Some of the important properties of our approach can be characterised as follows.

The strategy is sound and complete in the sense that no ambiguous utterances will be produced, and all un-ambiguous utterances are produced. If for a given semantic structure no un-ambiguous utterance is possible, the current strategy will not deliver a solution (it is foreseen that in such cases the planner decides what should happen).

The strategy is completely independent on the grammars that are being used (except for the reliance on derivation trees). Even more interestingly, the nature of the underlying parsing and generation strategy is not important either. The strategy can thus be used with any parsing- or generation strategy.

During the monitored generation previously generated structures are re-used, because only the ambiguous partial structures have to be re-generated.

Finally, for the proposed strategy to be meaningful, it must be the case that reversible grammars are being used. If this were not the case then it would not make sense to compare the derivation tree of a generation result with the derivation trees which the parser produces.