Computational Linguistics, Winter 2003/04

Administration

Instructor:: Shuly Wintner, shuly@cs.haifa.ac.il. Office hours: Monday 15:00-16:00, Jacobs 43. Phone: (828)8180.
Teaching assistant:: Yael Cohen-Sygal, yaelc@cs.haifa.ac.il. Office hours: Thursday 15:00-16:00, Education 3-513. Phone: (828)8460.
Times:: Monday and Wednesday, 16:00-18:00.
Place:: Mondays: Education 3502; Wednesdays: Jacobs 57D.
Prerequisites:: Computational models (203.3510). Students without the required background should talk to the instructor prior to registration.
Attendance:: Optional but highly recommended.
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.
Mid-term exams:: The first mid-term will cover the first half of the material and will take place on December 3rd or 10th (during class time). The second mid-term will cover the other half of the material and will take place on January 21st (during class time).
Home assignments:: Approximately 5 home assignments will be handed out during the semester. Submission is mandatory. Homework is to be done independently and plagiarism will not be tolerated.

Content

Textbook:

There is no recommended textbook for this course, but some of the material can be found in Speech and Language Processing, by Daniel Jurafsky and James H. Martin. It's a good book, albeit too shallow sometimes.

Syllabus:

Introduction

Applications of natural language processing
The structure of natural languages
Different levels of language understanding: morphology, syntax and semantics
Ambiguity

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 complexity of natural language
The limitations of CFGs
Unification grammars: feature structures and unification

Other topics

As time permits

Announcements

February 5th, 2004: Partial solutions of the exam are available here.
January 25th, 2004: Grades are available here. Appeals: photocopy your exam (check with the secretaries how) and submit a written appeal with a copy of the exam. Justify your claims clearly. Please do not appeal in person.
January 25th, 2004: Home assignment 3 can was graded. You can find it on the 2nd floor of Jacobs Building.
January 14th, 2004: Second mid-term exam of last year is available here.
January 14th, 2004: Assuming that the date of the second exam does not change: the exam will start on Wednesday, 21st January 2004, at 15:30. The first part will last 90 minutes and will end at 17:00. Then, those of you who would like to improve on their first mid-term exam's grade will be able to stay for a thirty-minute exam on the material of the first mid-term. The grade in this short exam will add up to 15 points to your mid-term's grade, with a maximum of 100. Attendance is optional.
January 14th, 2004: HW3: if you submit by Thursday, 15th January 2004, 16:00, you will have your assignment graded by Monday the 19th. Otherwise, you may submit by class time on Monday the 19th, in which case you will have your graded assignment (and, therefore, the final grade) only around the end of January. This refers to the entire assignment. We will not deal with partial submissions.
January 7th, 2004: The deadline for submitting HW3 is Thursday, 15th January 2004, 16:00.
December 25th, 2003: Home assignment 3 handed out.
December 24th, 2003: Slides for today's recitation added.
December 23rd, 2003: Updated list of grades.
December 18th, 2003: On Wednesday, December 24th, class will take place in the lab (Jacobs 59D).
December 17, 2003: Appeals: on Monday, December 22, 14:30 - 16:00 in my office.
December 14, 2003: Midterm exam is solved here. Grades are also published.
December 9th, 2003: On Wednesday, December 17th, class is canceled. You are invited to attend the Israeli Seminar on Computational Linguistics.
December 9th, 2003: Solutions for home assignment 2 published.
December 1st, 2003: On Monday, December 29th, class will take place in the lab (Jacobs 59D).
November 24, 2003: The mid-term exam will take place on Wednesday, December 10th, 16:00, in the classroom. Please be there before 16:00 as we want to start on 16:00 prompt.
November 24, 2003: On Wednesday, November 26th, class will not move to the computer lab, and will take place in the usual classroom. The class om Monday, December 1st, will take place in the lab (Jacobs 59D).
November 20, 2003: You can use the XFST system by downloading the following two files: xfst.exe and liblxrt_fake.dll. Both are password protected: use the user name and password given in class.
November 16, 2003: The slides for finite-state transducers were updated (fst4.pdf).
November 13, 2003: Inputs for home assignment 1 are here. Please run your program on these inputs as well as the ones on the assignment sheet. Note that your program is not expected to handle all the examples correctly.
November 11, 2003: On Wednesday, November 26th, class will move to the computer lab at Jacobs building (room 59D).
November 10, 2003: First home assignment: please ignore the verb eat in section 1. Your program does not have to deal with it correctly.
November 5, 2003: First home assignment handed out.

Copies of the slides

The slides for the entire course are available as PostScript or PDF. These are huge files, and there's no guarantee that no changes will be made during the course, so printing these files is not recommended.

Introduction: 4-up PDF
Morphology: 4-up PDF
Regular languages: 4-up PDF
Finite-state technology: 4-up PDF
XFST: 4-up PDF
XFST recitation (tirgul): PDF
Syntax: 4-up PDF
Context-free grammars: 4-up PDF
CFG recitation (tirgul): Presentation, Introduction to PCPATR in Word .doc or PostScript, a zip file with examples.
Parsing: 4-up PDF
Computational complexity of natural languages: 4-up PDF
Unification grammars: 4-up PDF

Home assignments

Morphology. Handed out: 5 November 2003. Due: by class time on 19 November 2003. PDF or Word doc. Inputs.
Morphology. Handed out: 19 November 2003. Due: by 6pm on 4 December 2003. Please deliver it to Yael's mailbox. PDF or Word doc.
Solutions: PostScript or Word .doc.
Syntax and CFG. Handed out: 25 December 2003. Due: by 6pm on 12 January 2004. Please deliver it to Yael's mailbox. PDF or Word doc.