%----------------------------------------------------------------------------

NATURAL LANGUAGE TEXT UNDERSTANDING -
LEXICON, SEMANTICS, and PRAGMATICS

%----------------------------------------------------------------------------

CONCEPTUAL ANALYSIS:
Natural language processing as Conceptual information processing

Schank et al argue for semantic interpretation without prior syntactic
analysis on the following grounds:
    - We make decisions about the meanings of words or the sentence as we
      read from left to right.
    - We use meaning as soon as we can; meaning, not syntax, is the crucial
      factor in understanding.
    - Syntax is an aid in determining meaning, not an end in itself.

MARGIE used "conceptual analysis" (Riesbeck, 1970-74).  The parser was called
CA (conceptual analyzer) or ELI (english language interpreter).  Natural
language understanding driven by semantic considerations; syntactic knowledge
used when necessary.

Consider:
        John took a sedative.
        John took a bath.
        John took a train.

Parser is mostly VERB-BASED, i.e., most knowledge is organized around verbs
or verb-like structures (ACTION-ORIENTED STRUCTURES).  CD works well as a
representation for this purpose because it is an action-oriented
representation.

The premise of conceptual analysis is that when a person reads or hears words
with certain meanings (such as "took"), he or she expects or predicts that
words with certain other meanings may follow or already may have been seen.

The dictionary entry for "take" is not "a verb with an agent, direct object,
and optional direction" (a syntactic definition), but rather representations
of the CONCEPTUAL MEANING of "take":

                                --> stomach(X)       X: subject, higher animate
    "take1": X <=> INGEST <- Y -|                    Y: direct object, medicine
                                --< 

    "take2": <get action and constraints from object>
             (empty verb with no contribution to meaning of action.  E.g.,
              "John took a bath" = "John bathed".)

                                --> W                X: subject, higher animate
    "take3": X <=> PTRANS <- X -|                    Y: object, vehicle
                ^               --< V                Z: Y's driver
                |instr          --> W                W: location
             Z <=> PTRANS <- Y -|                    V: X's current location
                                --< V

The "slots" in these structures (X, Y, etc.) provide suggestions as to where
to find fillers for the slots, and what kinds of fillers to look for.  E.g.,
in "take1", the X (actor) slot is filled in by looking for a higher animate
object in the subject position (normally to the left of the verb) of the
sentence.

Most positional information is provided by prepositions (e.g., "to", "from",
etc. provide information about W, V, etc. in "take3").  For example, in "John
took a cab to the plane", "plane" fills the W (destination) slot in "take3",
even though "plane" is a "vehicle" and not a "location".

Compare this with syntactic methods.  E.g., Winograd uses the heuristic "look
for the longest phrase" when parsing noun phrases, and then backtracks if
semantics objects at a later stage.

        "John sold Mary water meter cover adjustment screws."
                   ----------------------------------------
                   initial noun phrase does not make semantic sense

Riesbeck's approach, in contrast, is to let semantics tell you when to stop.
E.g., "sold" would tell you to look for a person and a physical object.
These predictions would tell the parser to separate "Mary" from "water
meter ..." rather than try to make sense of "Mary water meter ...".

Eventually, both systems use similar types of knowledge; the difference is in
how the knowledge is represented and applied.

%----------------------------------------------------------------------------

KNOWLEDGE REPRESENTATION FOR CONCEPTUAL ANALYSIS

In a conceptual analyzer (CA), knowledge is represented in the form of
expectations associated with words.  Expectations are implemented as
"requests" (or test-action pairs or production rules).  Thus a conceptual
analyzer can be viewed as an expert system or a rule-based system for
understanding language.

Knowledge is stored in the form of TEST-ACTION pairs known as REQUESTS.  For
example, "eat" has a bunch of requests stored as its definition, including
the following:

        TEST: Can a concept representing an edible object be found?
        ACTION: Put it in the OBJECT slot of the INGEST concept.

Words can build new concepts which are stored on the C-list (concept list).
E.g., "eat" puts an INGEST concept on the C-list.  Now if there is already an
edible object concept on the C-list, it will get filled into the INGEST's
OBJECT slot.  If not, a prediction for an edible object is created, by
activating a request on the R-list (request list)).  Whenever a word is seen
which has an edible object concept as one of its meanings, the concept will
be built and put into the INGEST's OBJECT slot.

%----------------------------------------------------------------------------

DATA STRUCTURES

    A "C-list" or concept list, which is like a short term memory where
    conceptual structures are built and stored.

    A "R-list" or request list, which is where the requests or expectations
    waiting to be satisfied are stored.

%----------------------------------------------------------------------------

REPRESENTATION OF REQUESTS

  A request looks like (<test> <action>), where <test> can be:
  
    1) check input for occurrence of a word or phrase
    2) check for semantic or ordering properties on conceptual structures
       on the C-list

  and <action> can be:

    1) add a structure to the C-list
    2) fill a slot in a conceptual structure on the C-list with another
       conceptual structure
    3) add more requests to the R-list
    4) take requests (including the request containing this action)
       off the R-list

%----------------------------------------------------------------------------

CONTROL STRUCTURE FOR CONCEPTUAL ANALYSIS:

1. Get next lexical item (word or idiomatic phrase) from input, reading left
   to right.  If none, end.

2. Load (activate) the requests associated with the new item into the R-list
   (request list).

3. Consider the active requests on the R-list.

4. Loop back to step 1.

%----------------------------------------------------------------------------

CA EXAMPLE

  Input:  John ate an apple.

  Read "John".
  Get definition of "John" from lexicon and put it on C-list:
    con0 = (pp John (type animate)(subtype human)(gender male)(name John))
  ["con" stands for "conceptualization" or "concept".]
  There are no requests associated with "John" so nothing goes on R-list.
  There are no requests currently on the R-list so go to the next word.

  Read "ate".
  Get definition of "ate" from lexicon and put it on C-list:
    con1 = (ingest (actor slot0)
                   (object slot1)
                   (to stomach (part-of slot0))
                   (from slot2))
  Get requests associated with "ate" and put them on R-list:
    req0 = if there is a concept on C-list before the one you just put there
              (i.e., con1) and it's animate
           then fill slot0 of con1 with that earlier concept
    req1 = if there is a concept on C-list after con1 and it's edible
           then fill slot1 of con1 with that concept
    req2 = if there is a concept on the C-list after con1 and it's a
             location outside of the body of whatever filled slot0
           then fill slot2 with that concept
  Execute any requests on the R-list:
    req0 fires: con0 is an animate concept before con1 so fill slot0
                of con1 with con0 and remove req0 from R-list:
                con1 is now: (ingest (actor con0)
                                     (object slot1)
                                     (to stomach (part-of con0))
                                     (from slot2))
    req1 doesn't fire
    req2 doesn't fire
  Get the next word.

  Read "an".
  Get definition of "an" from lexicon; there's nothing to put on the C-list.
  Get requests associated with "an" and put them on R-list:
    req3 = if a new concept is put on the c-list (i.e., after con1)
           then add "(ref indef)" to that concept
  Execute any requests on the R-list:
    req1 doesn't fire
    req2 doesn't fire
    req3 doesn't fire
  Get the next word.

  Read "apple".
  Get definition of "apple" from lexicon and put it on C-list:
    con2 = (pp apple (type inanimate)(subtype food))
  There are no requests associated with "apple" so nothing goes on R-list.
  Execute any requests on the R-list:
    req1 fires: there's a concept on the C-list after con1 and it's edible
                so put con2 in slot1 of con1 and remove req1 from R-list:
                con1 is now: (ingest (actor con0)
                                     (object con2)
                                     (to stomach (part-of con0))
                                     (from slot2))
    req2 doesn't fire
    req3 fires: there's a new concept on the C-list after con1, so modify
                it (con2) with "(ref indef)" and remove req3 from R-list:
                con2 is now: (pp apple (type inanimate)
                                       (subtype food)
                                       (ref indef))
  Get the next word.

  We're at the end of the sentence, so we check the R-list one last time
  for requests that might fire now after we last modified the C-list.
  The only one there is req2, and it doesn't fire, so we can just clean
  up by filling all the empty slots with "nil" and we're done.  The
  C-list looks like this:

v    con0 = (pp John (type animate)(subtype human)(gender male)(name John))
    con1 = (ingest (actor con0)
                   (object con2)
                   (to stomach (part-of con0))
                   (from nil))
    con2 = (pp apple (type inanimate)(subtype food)(ref indef))

%----------------------------------------------------------------------------

CA pros and cons:

  The good points are:

    + there's no need for pre-processing into a parse tree; the semantic
      analysis is not dependent upon syntactic analysis, so that is 
      going to make the processing a little more flexible
    + CA satisfies our intuition of human understanders doing all the 
      processing at once by bringing as much information as possible
      to bear on the understanding problem as soon as possible
    + CA constrains ambiguous interpretations and the search for the
      right interpretation by applying semantic knowledge early 

  The bad points are:

    - syntactic and semantic knowledge are mixed together and stored in
      the lexicon; this means that the syntactic knowledge must be repeated
      for each lexical entry, which eats up space; this also means that
      any changes to grammar must be made throughout the lexicon, not just
      in one place, which eats up the programmer's time
    - disambiguation will be easier in some cases at the semantic analysis
      phase if we know the parse tree in advance; this balances agains
      the third "good" point above (constraining search by applying 
      semantic knowledge early) so this one's a toss up
    - there is psychological evidence that while syntactic and semantic
      processing take place at the same time in the human understander,
      syntactic and semantic evaluations can be done independently; so
      just because two things happen at the same time doesn't mean that
      they must be done by the same process or that they rely on the
      same knowledge.

%----------------------------------------------------------------------------

SAM (script applier mechanism) used scripts to understand stories without
doing exhaustive inference.  FRUMP (fast reading understanding and memory
program) was a very fast script-based newspaper story reader that was hooked
up to the UPI newswire.  It could read 10-15% of the news stories.

SAM and FRUMP's problems, in turn, were in selecting the appropriate script
vwithout trying them all, and in dealing with novel (non-scripty) situations.

While SAM and FRUMP could deal only with stereotypical (scripty) situations,
PAM used inference rules about plans and goals to construct explanations for
non-scripty situations using MARGIE-like exhaustive chaining.  PAM could deal
with a wider range of stories, but it ran into the combinatorial explosion
problem again.

%----------------------------------------------------------------------------

SAM - Script Applier Mechanism (Cullingord 1978)

Scripts:
    A script is a set of CDs related together by causal relations.  Each CD
    is a SCENE in the script.  (Therefore a script is action-oriented.)

    Scripts have ROLES (or SLOTS) and FILLERS.  One slot, always included, is
    filled with a CAUSAL CHAIN (which may have many branches).

        ROLES in $RESTAURANT script:
            ROLES       CONSTRAINTS     DEFAULTS
            &Patron     *human*         *adult*
            &Waiter     *human*         *female adult*
            &Food       ...
            ...

Example: The restaurant script.

$RESTAURANT
                                               o           --> inside(&REST.)
    Go in.                 &PATRON <=> PTRANS <-- &PATRON -|
                           ^                               --<
                           |c                       Jack went to a restaurant.
    Sit down.              &PATRON <=> PTRANS
    Look at the menu.      ^-c- MTRANS
    Decide what to order.  ^-c- MBUILD
    Order your meal.       ^-c- MTRANS              He ordered a hamburger.
    (Wait.)
    Waiter brings food.    ^-c- PTRANS
    Eat.                   ^-c- INGEST
    Pay.                   ^-c- ATRANS              He paid...
    Tip waiter.            ^-c- ATRANS
    Leave.                 ^-c- PTRANS              ...and left.

How do we use this to understand stories?  When the story about the scripted
activity comes in, we match inputs against the script, trying to find which
script element it matches.  When we find a match, we update role bindings
(e.g., who is the patron, what is the food), and infer actions and states
left implicit (i.e., fill in the gaps in the causal chain).

Script-based processing:

    SCRIPT SUGGESTION -- on the basis of words or phrases that mention script
    headers, make a list of the possibly active scripts (hopefully not a
    large number).

    SCRIPT SELECTION -- deciding which script is being referred to in the
    story, on the basis of the tentative instantiations of the candidate
    scripts, or perhaps on some more specific tests, select the appropriate
    script.

    SCRIPT INSTANTIATION -- identify input as an instance of some script.
    Start APPLYING the script to subsequent inputs.

    SCRIPT APPLICATION -- using script to fill in the important details in
    the causal chain being built.  Identify input conceptualizations as
    instances of script concepts, fill roles, and build a causal chain
    representation by instantiating missing concepts, i.e., those lying
    on the script between the last mentioned template concept and the current
    one.

Why scripts are good:
        FUNCTIONAL: Control of combinatorial explosion
        PSYCHOLOGICAL: Psychological validity (Abbott, Black and Smith)

Limitations of scripts:
        Script selection - which script to use when?
        Script learning - where do scripts come from?
        Non-scripty situations
          Example:
              John went to a restaurant.
              He sat down.
              He got mad.
              He left.

%----------------------------------------------------------------------------

Copyright (c) Ashwin Ram, 1990-93
Assistant Professor, College of Computing
Georgia Institute of Technology, Atlanta, Georgia 30332-0280
E-mail: <ashwin@cc.gatech.edu>

%----------------------------------------------------------------------------