Natural language processing

Administration

Instructor:
Shuly Wintner
Times:
Spring 2001, Tuesday, 8:00-10:00 and Thursday, 8:00-10:00
Place:
Rabin 6004
Prerequisites:
Either computational models (203.3510, preferred) or compilers (203.2130). Students without the required background should talk to the instructor prior to registration
Grading:
The final grade will be based on 4-6 home assignments (approximately 33%) and two mid-term exams (approximately 33% each). There will be no final exam.
Attendance:
Optional but highly recommended.

Content

Abstract:
The structure of natural languages. Different levels of language understanding: morphology, syntax and semantics. Finite-state approaches to language processing. Context-free grammars. Parsing algorithms. Unification grammars. Applications.
Textbook:
James Allen, Natural Language Understanding, second edition, Benjamin/Cummings 1995.
Detailed syllabus:
Morphology
  • introduction to morphology: word structure
  • inflections and derivations
  • finite-state automata
  • finite-state transducers
Syntax
  • introduction to syntax: the structure of natural languages
  • context-free grammars: grammars, forms, derivations, trees, languages
  • parsing: top-down, CYK algorithm, Earley algorithm, bottom-up chart parsing
  • the limitations of CFGs
  • unification grammars: feature structures and unification
Semantics
  • Montague grammars
Applications

Copies of the slides

Introduction
in PDF format, in PostScript format, 4-up PDF, 4-up PostScript, as a PDF presentation.
Morphology
in PDF format, in PostScript format, 4-up PDF, 4-up PostScript, as a PDF presentation.
Regular languages
in PDF format, in PostScript format, 4-up PDF, 4-up PostScript, as a PDF presentation.
Finite-state machines
in PDF format, in PostScript format, 4-up PDF, 4-up PostScript.
The XFST interface
in PDF format, in PostScript format, 4-up PDF, 4-up PostScript, as a PDF presentation.
Introduction to syntax
(unavailable)
Context-free grammars
in PDF format, in PostScript format, 4-up PDF, 4-up PostScript.
Parsing
in PDF format, in PostScript format, 4-up PDF, 4-up PostScript.
Complexity of natural languages
in PDF format, in PostScript format, 4-up PDF, 4-up PostScript.
Unification grammars
in PDF format, in PostScript format, 4-up PDF, 4-up PostScript.

Home assignments

  1. Morphological analysis of Hebrew nouns. Handed out: 15 March 01. Due: by midnight on 31 March 01. PostScript, PDF.
  2. Fun with XFST. Handed out: 27 March 01. Due: by midnight on 19 April 01. PostScript, PDF.
  3. Earley parsing. Handed out: 17 May 01. Due: by midnight on 31 May 01. Postponed until 7 June 01. PostScript, PDF. Example inputs: PostScript, PDF.
  4. Grammars. Handed out: 29 May 01. Due: by midnight on 12 June 01. PostScript, PDF.
  5. Unification grammars. Handed out: 12 June 01. No due date, this is for fun only. PostScript, PDF.

Announcements

22 June 01
A solutions of the second mid-term exam: pages 1, 2, 4, in PDF, page 3, in PDF.
22 June 01
The final grades are here, in PDF. Ten points were added to the grade of the second mid-term; this is reflected in the "fixed" grade column, which is your actual final grade.
7 June 01
The slides for Unification Grammars were modified.
29 May 01
The second exam will take place Thursday, June 21, 8:30-10:00 (in the classroom).
24 May 01
Home assignment 3 can be submitted until 7 June 2001.
17 May 01
On Tuesday, 22 May, we'll have a guest lecturer: Dr. Yoad Winter of the Technion will talk on Natural Language Semantics. You don't want to miss this class.
1 May 01
A solution to the exam is on-line.
28 April 01
The first mid-term exam is on-line as PostScript or PDF.
27 March 01
Input for assignment 1 is available as PostScript or PDF.
27 March 01
The first mid-term exam will take place on Thursday, 19 April 2001, during class time. Material covered includes morphology, phonology and their computational implementation using finite-state technology. Duration: 90 minutes. You may bring anything but computers and friends.

Links

Natural language processing, http://cs.haifa.ac.il/~shuly/teaching/01/nlp/
Updated by shuly@cs.haifa.ac.il on 22 June 2001