A SEMANTIC PARSER FOR UNDERSTANDING ILL-FORMED INPUT

Kathleen McCoy, Patrick Demasco, Yu Gong, Christopher Pennington, &
Charles Rowe

Applied Science and Engineering Laboratories,
University of Delaware and AI DuPont Institute

(c) 1989 RESNA Press. Reprinted with permission.

Abstract

In this paper we explore the integration of natural language
understanding techniques into augmentative communication devices. A
semantic parser is described which takes a string of words (chosen
from a word board) from the user and tries to identify a semantic
interpretation of those words. One goal is to allow the disabled
individual to input a compacted message (i.e., one containing mainly
the content words of the desired utterance) and eventually have the
intended message generated in full. This task requires that the
utterance first be understood. Understanding is complicated because we
expect the utterance to be largely ill-formed with respect to the
normal syntactic rules of the language. The ill-formedness constraint
has led us to develop a novel semantic parser which is driven by the
possible semantic interpretation of the individual words in the input
utterance.

Introduction

This work is part of the compansion project being done at the Applied
Science and Engineering Laboratories at the University of Delaware and
the AI DuPont Institute. The goal of the project is to allow the
disabled individual to input a compressed message containing the
content words of his/her intended utterance. The system will take this
input, generate a semantic representation using natural language
understanding techniques, and eventually generate a well-formed
English sentence.

A semantic processor of this type would also be useful in other
applications such as a system which translates American Sign Language
into English, or a word prediction system, or a system which checks
the grammar of a written text.

The semantic processor is concerned with creating possible semantic
representations for the words input by the user. We have taken as our
semantic representation a case-frame analysis of the sentence based on
[2]. Thus the semantic interpreter must: identify the verb of the
sentence, identify which constituent is playing the role of the actor,
which is the object, instrument, to-location, from-location etc...

Classically the process of constructing a semantic representation from
some input words has been broken up into two phases [1]. In the first
phase a grammar of English is used to generate the deep structure
representation of the sentence. The assumption of this phase is that
the sentence is syntactically well formed. Next, semantic rules are
applied to this deep structure in order to generate the semantic
representation.

Due to the potentially severe syntactic ill-formedness of our user's
input, this approach was not feasible. We have accordingly focused our
efforts on understanding which does not rely on a syntactic phase [4].

Methods

Our work is based on that of Small and Rieger [3] who designed a "word
expert parser" which basically allowed each individual word in the
input to contribute to the overall meaning of the sentence
individually. However, the meaning of an individual word in isolation
(i.e., the role it plays in the sentence) is ambiguous. For instance
"John" may either play the role of an actor or an object in a
sentence. The words in a sentence, however, are mutually
constraining. Thus the words in a word expert parser may communicate
with each other so that the correct interpretations can be
identified. For instance, the verb "laugh" requires an animate actor
and no object. Because of this, "John" must play the actor role with
respect to the verb "laugh".

We can think of the words in a word expert parser as working in a
bottom-up fashion - each individual word is declaring what role it can
play and all of the words are trying to fit together into a
well-formed semantic structure. In our system we augment this
bottom-up processing with a top-down component which uses more specific
semantic structures (associated with domain contexts) which look for
words to fill their roles. In our system, groups of words which
naturally occur together in conversation are divided into contests.  A
particular word may occur in more than one context and may contribute
a different meaning in each. For instance, the word "Boston" might be
associated with the "airline flight" context as well as with the "city
government" context. The "flight" context contains rules that say that
"Boston" can fill the role of either TO-LOC or FROM-LOC. On the other
hand, rules in the "city government" context might allow "Boston" to
fill the ACTOR role (as in "Boston instituted a law making it illegal
to...").

In order to implement different words contributing different meaning
in different contexts, associated with each specific context is a set
of semantic rules whose preconditions specify specific words. The
actions of the rule will build pieces of semantic representations for
the word which are specific to the particular context. The semantic
rules serve the purpose of bottom-up interpretation of the input
sentence in each specific context.

In addition to the context adding different interpretations of the
individual words, each context has associated with it expectations
(which we call frames) about an overall semantic structure for a
sentence in that context. These semantic structures may be more
specific than a general semantic structure. For instance, in the
flight domain, to and from locations must be cities with airports
(while they may generally be any place). The frames associated with a
context "look" for words in the input which can fill their roles. They
serve to further disambiguate the role played by particular input
words since they specify constraints on the role fillers imposed by
the domain (e.g., in the flight domain Newark, Delaware must not
normally be a to or from location since it doesn't have an airport).

In order to take advantage of the frames and specialized word meanings
associated with a context, the context of the sentence as a whole must
be identified. The sentence context is determined by taking (something
like) the intersection of the contexts of the individual words. That
is, we choose that context which every word of the input utterance is
a part of. The sentence context lends a top-down orientation to the
semantic processing by identifying a set of frames which are basically
skeletons of semantic structures. Each frame corresponds to a possible
final semantic structure for a sentence under the context. The
semantic interpretation for the individual words must be fit into the
frames for the specified sentence context(s).

Conclusions

In this work some natural language processing techniques have been
applied to the design of an augmentative communication device. Our
goal is to speed up the communication rate of the user by allowing
him/her to type in a very sparse, ill-formed message. Our system first
attempts to "understand" the input by creating a semantic
representation and then "generates" syntactically well-formed
sentences.

The semantic processor is innovative in that it does not rely on
syntactic clues. We expect this aspect of the system to be
particularly useful in cases where the user has limited or diminished
linguistic skills. Instead the processor operates in a bottom-up
fashion combining possible semantic interpretations of the individual
input words into a semantic structure. At the same time, it works
top-down from skeletons of semantic structures associated with the
domain context.

Acknowledgments

This work is supported by Grant #H133E80015 from the National
Institute on Disability and Rehabilitation Research.  Additional
support has been provided by the Nemours Foundation.

References

[1] Allen, J. Natural Language Understanding. Benjamin/Cummings, CA,
l987.

[2] Fillmore, C. J. The case for case reopened. In P. Cole and
J. M. Sadock, editors, Syntax and Semantics VIII: Grammatical
Relations, pages 59-81, Academic Press, New York, 1977.

[3] Small, S. and Rieger, C. Parsing and comprehending with word
experts (a theory and its realization). In Wendy G.  Lehnert and
Martin H. Ringle, editors, Strategies for Natural Language Processing,
1982.

[4] Wilks, Y. Does anyone really still believe this kind of thing? In
K. Sparck Jones and Y. Wilks, editors, Automatic Natural Language
Parsing, pages l82-l89, Ellis Horwood Limited, 1983.

Contact

Kathleen McCoy
Dept. of Computer and Information Sciences
University of Delaware
Newark, De. 19716