COGS1680: Human and Machine Learning

Fall semester, 2008
Instructor: Mark Johnson
Teaching assistant: William Headden
Meeting time: Tu Th 9:00-10:30 (the only time we could find!)
Classroom: Watson Center (CIT), room 367

This year CG168 will focus on machine learning techniques, and there will be a class project that will involve applying these techniques to dependency parsing. Somewhat less than half the class will be on supervised learning techniques (such as K-nearest neighbours, Maximum Entropy, Support Vector Machines) and slightly more than half of the class will be on unsupervised learning techniques (such as K-means, Expectation Maximization, Markov Chain Monte Carlo and Particle Filtering). We'll use the supervised techniques to build an incremental dependency parser, and then we'll use the unsupervised techniques to learn a dependency grammar from strings alone.

You can get 200-level credit for this class by doing extra work in the class project.

Grades for the class will be determined by in-class mid-term and final exams, and by the quality of your work on the class project.

Everyone in this class should have a CS account (let me know if you don't!). The course directory on the CS machines is /course/cog168.

Office hours

• Mark Johnson's office hours are Wednesdays 10-12, Metcalf Research, room 231.

• William Headden's office hours are Tuesdays 12:30-2:30 in CIT room 453.

• Joseph Browne's office hours are MWF 7-8 pm in CIT room 219. (3hrs a week -- wow!)

Homework

• Homework submission instructions

• Final exam, due midnight, Monday 8th December. Updated version now available!

• Homework due Tuesday, 2nd December. Updated! You will need the C code for computing the Digamma function Ψ(x) to do this assignment.

• Homework due Tuesday, 18th November

• Homework due Tuesday, 11th November

• Homework due Tuesday, 21st October (updated 14th October, 2008)

• Homework due Thursday, 9th October

• Homework due Thursday, 25th September

• Homework due Thursday, 18th September

Useful links

• Slides on Chinese Restaurant Processes

• Slides on Gibbs sampling for Dirichlet-Multinomials

• Slides on Mean Field Variational Bayesian inference for Dirichlet-Multinomials

• Course syllabus (pdf file)

• For estimating MaxEnt models using numerical optimization, I recommend the L-BFGS algorithm. I've found the C++ orthant-wise optimizer (basically a modified L-BFGS that handles L1-regularization in a particularly efficient manner) by Galen Andrew at Microsoft Research to be easy to use, and as good as other optimizers I've tried. (Galen's documentation suggests that his code runs best under Windows, but I find it runs well with g++ under Linux as well).

  I have written a wrapper and an example C++ program that shows how to use this optimizer, which you can find in /course/cog168/asgn/c++/optimizer on the CS machines.

  The Python SciPy library and the Gnu Scientific Library have L-BFGS implementations. I haven't tried them.

• Slides on Bayesian Inference and Dirichlet-Multinomials

• Nivre et al (2007) MaltParser: A language-independent system for data-driven dependency parsing, Natural Language Engineering 13(2): 95-135.

• The CONLL-X shared task on dependency parsing
  • The CONLL X data is available in CONLL-X format on the CS machines in /course/cog168/asgn/data/ as train.conll, dev.conll and test.conll
  • There's a description of the CONLL data format here
  • The CONLL software page has a Perl script for evaluating dependency parser output.

• Many of you will want to program the computationally more demanding algorithms in C++. You can download some of the C++ utilities I find most useful here.

• Recommended textbook: Bishop (2006) Pattern Recognition and Machine Learning.

• David MacKay (2003) Information Theory, Inference and Learning Algorithms is an excellent book on many course topics.