Language Analysis for Dialogue Understanding


Graduate School of Information Science Nara Institute of Science and Technology
8916-5 Takayama, Ikoma, Nara 630-01, Japan

Dialogue may include a number of grammatically incorrect but semantically understandable sentences, leading dialogue systems to handle grammatically ill-formed inputs. Speakers often omit words, change order of phrases, or make some careless errors such as agreement inconsistency, misspellings or extra words. Dialogue systems have to handle not only grammatically well-formed inputs but also grammatically ill-formed inputs. That is, robust parsing systems should not just reject the grammatically ill-formed inputs, but process them anyway.
Many works use context-free grammars (CFGs) for describing well-formedness of input sentences because of their simplicity and tractability. Another reason to use CFGs is that there are efficient parsing algorithms. However, there are linguistic phenomena which are hard for CFGs to define every detail of phenomena, such as word order variation in a free word order language. To cope with the problem, in recent grammar formalisms, grammars with various kind of constraints instead of one single kind of rules as in a CFG are prevailing. Especially, in unification-based grammar formalisms, grammar rules are described using the notion of unification.
Moreover, since utterances usually contain sufficient information for understanding the speakers intention, they have to be interpreted within contexts.
We developed a new method to deal with grammatically ill-formed inputs. Considering grammatically ill-formed inputs as violation of constraints on grammar rules, these are regarded as being caused by some failure of unification operation. In the ordinary definition of unification, the result of an unification operation is a success or a failure. That is, if feature structures to be unified include inconsistent information, the unification operation simply fails.
Only when a normal parsing process fails to find a complete parse, the recovery process is invoked.
In order to perform a recovery process efficiently, it is necessary
(1) not to search the result of the failure repeatedly,
(2) to know what is to be obtainable if the failure is recovered, and
(3) to know the degree of the failure.
Since the result of ordinary unification only ends in failure, (1) to (3) above are not attainable in ordinary unification operation. It is necessary to keep results of failure. In order to attain the conditions (1) through (3), we extend the unification operation for handling feature structures that include inconsistency. We call this extended unification cost-based unification, which always succeeds even if two feature structures include inconsistent information. When inconsistency is detected between feature structures, a cost is assigned to the resultant feature structure according to the degree of inconsistency. We also introduced the notion of reward, which reflects the goodness of the result.
Our approach consists of three methods for parsing grammatically ill-formed inputs, based on syntactic, semantic and contextual information. The first method handles a local ill-formedness such as constraint violation. The second and third methods handle a non-local ill-formedness such as word order violation, incomplete sentential fragment and ellipses.
The first two methods try to discover a phrase which covers the whole input. After they are performed, the third method receives the result, and then finds the appropriate interpretation of the input using contextual information. Since these methods are performed on the basis of cost and reward trade-off, they can be integrated into a uniform framework.
The contextual processing performed by the third method is based on Relevance theory. The most relevant interpretation is obtained by looking for contextual information of low accessibility that produced the maximal information. We have implemented a prototype parser for grammatically ill-formed inputs using an HPSG-style grammar formalism of Japanese.

Keywords: robust parsing, cost-based unification, relevance theory