CSC 247/447 (and BCS 235, LIN 247): Natural Language Processing

This page (and its links) are still under construction and subject to change

Credit Hours: 4

Class Time and Location: Tuesday/Thursday 9:40 - 10:55, CSB 632

Course Description:

This course is an introduction to natural language processing, with emphasis on constructing computer programs that understand natural language.
Topics include English phrase structure, parsing, semantic analysis, speech acts, knowledge representation, and NL system design.

Instructor:

Len Schubert
Department of Computer Science
Room 733, Computer Studies Building
University of Rochester
E-mail: lastname at cs dot rochester dot edu
Office Hours: Tuesday and Thursday 5:00 - 6:00 (or by appointment)

TA:

Francis Ferraro (email: f followed without gap by ferraro at u dot etc.)
Frank's website for CSC 247/447
Office Hours: TBA

Prerequisites: CSC242

Knowledge of LISP (or scheme) is assumed, and some acquaintance with context-free grammars (e.g., from CSC 280, CSC 254, LIN 110 (or better 260or LIN 225)) is helpful.
A prior logically oriented course such as CSC 244, CSC 219, or PHL 110 is also very desirable.

Course Goals and Schedule:

The goals are to learn ...
  • basic concepts of English syntax (grammar), including features and "unbounded movement";
  • basic techniques of parsing (syntactic analysis);
  • basic concepts of semantic representation, and techniques for mapping syntactic structures to (preliminary) logical forms ;
  • basic techniques of structural and lexical disambiguation, including statistical techniques based on text corpora;
  • ``deindexing": converting context-dependent logical forms to context-independent ones;
  • basic concepts of knowledge representation and reasoning (KR & R), and techniques of using world knowledge and knowledge of discourse structure to infer causal (etc.) connections between sentences;
  • (esp. grads) basic concepts of speech acts and the beliefs, desires, obligations, intentions, and plans underlying them, and how these shape communication.
In more general terms, after taking this course you should
  • have a sense of the current state of the art, major difficulties, and future prospects in NLU;
  • be ready to delve into the more specialized and research literature;

    CL, Ann. Meet. of the ACL, EACL, COLING, ANLP, Linguistics and Philosophy, special workshops (e.g., AAAI Spring and Fall Symposia, workshops on speech, discourse, dialogue, large corpora, knowledge extraction, question-answering, etc.)

    General AI literature: AIJ, JAIR, CI, Cog. Sci., AAAI, IJCAI, ECAI, ...

  • have some awareness of the new vistas opened by large computerized text/speech corpora -- disambiguation, learning syntax, semantic categories, world knowledge, ...
  • be able to program basic techniques for parsing, interpretation, corpus processing, etc., in Lisp.
The course schedule made available through this link (as a pdf file) will also be handed out in the first class. The schedule is approximate and subject to adjustment.

Textbook:

James Allen, Natural Language Understanding, Benjamin/Cummings, 2nd edition, 1995.

Supplementary Texts (on reserve in Carlson library):

  1. Robert Wilensky, Common LISPcraft, W.W. Norton, 1986. Amazon link

  2. Peter Seibel, Practical COMMON LISP, Apress, 2005.

  3. D. Jurafsky and J.H. Martin, Speech and Language Processing, Prentice-Hall, 2008 (2nd edition). Amazon link.

  4. C.D. Manning and H. Schuetze, Foundations of Statistical Natural Language Processing, MIT Press, 1999. Amazon link

  5. R. Hausser, Foundations of Computational Linguistics: Human-Computer Communication in Natural Language , Springer, 1999. Amazon link

Grading:

The following contribute to the grades (where percentage weights may be adjusted upward or downward by up to 3%):

  1. 5 homework assignments (50% for undergrads, 35% for grads)
  2. in-class midterm test (20% for undergrads, 15% for grads)
  3. Final exam (30% for undergrads, 25% for grads)
  4. graduate project/essay (25%, grads only)
  5. class participation (no direct contribution as points, but borderline cases are judged based on this).

Homework:

The homework assignments will include problems requiring written answers and Lisp programming. The problems will be based on the lectures that have been given.
The later Lisp assignments may form a staged NLP project, perhaps aimed at simple text summarization, or knowledge extraction, or something similar. This may well involve use of some pre-existing code, such as parsers and logical form generators. It may also involve use (and perhaps further development) of resources such as lexicons and text or treebank corpora.

The project/essay for graduate students can be on a freely chosen topic in natural language processing, but could also be an elaboration, in some direction, of the assigned project. (But in all cases some delving into the relevant literature is expected; i.e., even a programming-oriented project should describe how the work relates to the state of the art, though in less depth than an essay-style project.) Essays/project writeups are typically 3500-7000 words in length, and should be well-written and well-organized, and should include illustrative examples, relevant citations, and should show the author's ability to digest and clearly present (in his or her own words) technically nontrivial material and to contribute novel ideas and a personal perspective. Project topics should be thought about as early as possible. Some more detailed guidelines will be provided.

Academic honesty policy:

In your writing, problem-solving and programming, you are expected to use your own ideas, your own words, and your own code, unless otherwise indicated (e.g., you are advised to use some code written by the TA, or from some other source). Where you do use another author's text verbatim, give a proper citation, and similarly, where you make permissible use of code from a non-prescribed source, cite your source. The following applies to assignments that you've been asked to do individually (as opposed to any group project that might possibly be assigned, and explicitly designated as such).

Students may discuss among themselves the nature of the problems or tasks assigned, but not the solutions. If you collaborated with someone (namely, worked on a problem with someone or shared your solution with someone), then on your paper report who the persons are. The points you earn on that particular problem will be divided by the total number of students involved in the collaboration. Failure to report collaboration, if detected, will result in a penalty---the entire score of the paper will be reduced to zero.

Supplementary Course Materials:

Some course materials may be made available through this (or the TA's) web page.
Lectures will involve use of overhead slides and the board, and copies of the slides (and some other informal notes) will be provided to students via the web or as hard copy.

Meaning, significance, and methods of NLP

A quick introduction to Common Lisp

Hints for dealing with symbols in Lisp

Top-down parse example

Bottom-up-parse example

Improvements to backtrack parsers

Essay/project guidelines

James Allen's basic parser is located here
(or look for it on James Allen's web page).

Slides from lectures:
(A slide-printing script is available here, and now a 10 times faster version (with only slightly lower resolution) is available here,
both thanks to Fabrizio Morbini.)

01: basic linguistic concepts

02: English phrase structure

03: Syntactic analysis

04: Chart Parsing

05: Formalizing Features

06: Managing Features

07: Auxiliaries, Passives, Imperatives, Y-N-Questions

08: Questions, Gaps, and Parsing with Gaps

09: Other Unbounded Dependencies

10: Towards Deterministic Parsing

14: Semantic Interpretation Intro

15: Model Theory

16: Scoping Logical Operators

17: Interpreting PPs, Simple Relatives, and Yes-No Questions

18: Interpreting Gaps

19: Further Issues in Semantic Interpretation

20: Resolving Ambiguity

Supplement to 20: Scoping preference examples