Material for Fall 2002

Lecture Note 1, Tree Syntax of Natural Language (ps pdf)

Introduction to Natural Language Processing
COM S/LING/COGST 474
Spring 2002

Mats Rooth
Morrill 203A (enter through Linguistics main office)
Office hour: Wednesday 3-4

Regular meetings are TR 2:55-4:10 in Thurston 203.
In-class labs are in Morrill B07.

1. Tree syntax of natural language

Readings: Manning and Schuetze Chapter 3 Linguistic Essentials
Sag and Wasow Chapters 2 and 3.

2. Context free grammars and parse forest algorithms

Readings: Revesz Chapters 1,2,3, and section 8.3.
Alternative readings on CFG and CKY algorithm: Lectures 19 and 27 of Kozen, Automata and Complexity.

CKY algorithm as presented in class.
PS 1 ps
Solution to Problem Set 1

Parse forest algorithms and grammar development

3. Weighted grammars

Parse forest inside algorithm
In-class Lab 1 Probabilistic parsing.
Parse forest frequency algorithm
Problem set 2 Parse forest construction and parse forest algorithms.

4. Tagging and markup methodology

Readings: Manning and Schuetze Chapter 10

5. Estimation of weighted grammars

6. Feature constraint grammar

Readings: Sag and Wasow Ch. 3 "Complex Feature Values"
Sag and Wasow Ch. 15 "Long Distance Dependencies"
PS 3

Project topics.