CS413: Knowledge-Based Natural Language Processing

(Adapted from an exercise at Indiana University)

Due before Friday, December 20 at 5:00PM.

Please place all of your code inside of the turnin directory for hw3. In addition put your answers to the questions marked in red into a document called hw3.html (also placed in the turnin directory, and in HTML format). For clarity be sure to restate each question before answering it.

Part I: Conceptual Dependency Theory and Conceptual Analysis

Proponents of conceptual analysis argue that the goal of parsing is to extract meaning and that semantic expectations play the primary role in guiding parsing. This part of the assignment applies a knowledge representation that provides those expectations--Conceptual Dependency theory (CD)---to the parsing process.

Your first task involves practice at writing conceptual dependency and writing requests to extend the vocabulary of a conceptual analyzer. We provide a scheme version of the simple conceptual analyzer, MicroELI [Schank and Riesbeck, 81]. Its code has been annotated with numerous comments on the process and representations used. MicroELI is a "micro" version of Riesbeck's conceptual analyzer ELI (English Language Interpreter).

An important note about microprograms: "Microprograms" are distillations of landmark AI programs into very simple forms that illustrate key aspects of their processing. Working with them gives a a hands-on understanding of the basic framework without the overhead of building the system from scratch or analyzing a huge program. However, it is important to always keep in mind that they are only distillations, not the programs themselves---the original programs should not be judged by the microprograms. The original programs are tens of thousands of lines of code, with very subtle mechanisms and a lot of knowledge, involving many person-years of work. The microprograms are a few hundred lines with almost no knowledge. An interesting question to think about as you go over their code is what is missing: what would be needed to scale these up to full-fledged systems again, and how could it be done?

Trying out MicroELI: Load MicroELI and test it by typing (PROCESS-TEXT KITE-TEXT). KITE-TEXT contains the CD equivalent of the story:

Jack went to the store.
He got a kite.
He went home.
In the output trace, observe how expectations drive parsing. Note also that the parse is successful despite the program's lack of definitions for some of the words in the story (e.g., for the word ``to'').

In a conceptual analyzer, the dictionary of requests is the main source of knowledge. In this assignment we will study that knowledge and how it is used:

  1. Using conceptual dependency: Write CD representations for the following sentences. Unfilled slots in the CD representations can either be left in (to make the missing information more obvious) or omitted for convenience (CD-based programs would always know they're unfilled, though). Because we will not address object representations, try to make up your own scheme for representing objects, analogous to CD's representation for actions. If you notice an ambiguity that must be resolved before the representation can be done, point out the ambiguity and how you are resolving it.

    1. Sally drove a motorcycle to New York.
    2. John donated his sofa to the Salvation Army.
    3. John roared into town in a new BMW. (For this sentence, represent reasonable inferences.)
    4. John ate popcorn with his foot.
    5. Mary broke John's TV.

  2. Defining requests:Add to MicroELI's dictionary the definitions needed to parse:

    Jack went to a restaurant.
    He ordered a lobster.
    He left.

  3. Disambiguation: Sometimes requests associated with a word can disambiguate the word by looking at what comes next. For example, ``John had an apple'' normally means ``John ate an apple.'' while ``John had a newspaper'' normally means ``John possessed a newspaper.''

    Add to MicroELI's dictionary the definition for the verb HAD so that ``Jack had a kite.'' becomes 

    (POSSESS (ACTOR (PERSON (NAME (JACK)))) (OBJECT (KITE)))

    But ``Jack had a lobster.'' becomes 

           (INGEST (ACTOR (PERSON (NAME (JACK)))) 
               (OBJECT (LOBSTER)))

    Also define requests so that ``had'' is interpreted as ``ingest'' for the sentences ``Jack had beef'' and ``Jack had steak.'' In a full-scale conceptual analyzer, this information would be stored at the appropriate level of generality in an abstraction hierarchy. However, you may simply use an association list pairing classes (e.g., "food") with lists of instances.

    Note: McELI doesn't support variables in the headers of CD forms. Consequently, your requests can't change the primitive act by using a variable to be assigned later. Instead, your solution will have to replace the entire CD form if a different meaning applies, reusing accumulated information.
  4. Ambiguity of words: As the previous example shows, MicroELI can handle ambiguous verbs fairly easily. Discuss the issues involved in writing requests that would enable mcELI to handle ambiguous nouns. (E.g., the word ``bill'' in ``Bill paid the bill.'') Sketch how you might change the MicroELI framework and how you would write requests using the new framework to enable the program to parse the sentence ``Bill paid the bill with a bill.''
  5. Difficulty of CD: Spend some time thinking about what makes a sentence hard or easy to represent using CD. What kinds of sentences are easy to represent? What kinds of sentences are hard? Give concrete examples of sentences illustrating the types of issues you identify. Why?

Part 2: Schema Based Story Understanding

Schema-based story understanding

You have already worked with micro-ELI to generate CD representations for representing sentences. Now we will build on this work to represent, "understand," and summarize stories.  Cullingford's Script Applier Mechanism (SAM) has been distilled into micro-SAM [Schank and Riesbeck, 81], a short program with the same basic algorithm.

Micro-SAM processes Conceptual Dependency input and stores a CD representation of its understanding in its memory. We have prepared a scheme version of micro-SAM to use as the starting point for your work in this part.

You will first write a simple script for micro-SAM, then combine micro-SAM with micro-ELI to form a script-based story understander that can understand simple stories in English, and finally give it a simple facility for generating natural language summarizies of stories. You will also examine the relationship of this small model to some of the hard problems for natual language processing, and how to apply knowledge to address them.

  1. Writing a script: Write the template actions for a restaurant script, using CD. Include the following events:

    The script should have the roles RESTAURANT, DINER, WAITER, and MEAL (and any other roles you consider necessary). Add the restaurant script to micro-SAM's script library.

  2. Combining mcELI and mcSAM into an English story understander: With your changes, micro-ELI can parse the story:
    Jack went to a restaurant.
    He ordered a lobster.
    He left.
    Write a top-level function PROCESS-ENGLISH-STORY that takes list of English sentences as input, runs micro-ELI on those sentences to produce a CD representation, and then runs micro-SAM on the CD representation to understand the story.

    Process the story of Jack's dinner. Afterwards, the memory should contain instantiations of all the CDs in your restaurant script.
    Thinking critically about the system:  (Not to be handed in) At this point you have a skeletal story understander. What is missing? What doesn't work the way it should? Experiment with it to see what you can find out before proceeding to the next questions, which identifies one problem and has you suggest approaches to repair it.

  3. A Problem: Assume that the sentence ``A coin rolled into the store'' is analyzed as (PTRANS (OBJECT (MONEY)) (TO (STORE)))  Process this line with micro-SAM. Then process the CD representation for ``John bought a restaurant.''
    1. Explain what goes wrong in each case and the causes of the problems.
    2. What is a simple way that you could modify the code to address this? (You do not need to write this code; simply give your strategy.)
    3. When might your simple approach fail?
    4. What would you propose to address this problem? Try to think of a method that is robust (applies to a wide range of situations) and efficient, and sketch its tradeoffs. (Addressing this problem in a rich way has been the subject of much work in the literature, as well as the heart of at least one dissertation in AI.)