The class will cover machine learning methods for structured prediction problems. The main focus will be on problems from natural language processing but most of the methods we will consider will have applications in other domains (e.g., bioinformatics, vision, information retrieval, etc).

Structured prediction problems are classification problems where a classifier predicts not a binary/multiclass label, but rather an element of some structured space. Examples of structured problems include sequence labeling problems, segmentation problems, parsing (syntactic or semantic in NLP or, e.g, image parsing in vision) and many others. In the class we will cover most of the state-of-the-art methods for this class of problems: starting from hidden Markov models, structured perceptron, conditional random fields to more advanced techniques such as structured SVM, Searn and others.

Though most of the applications will be from the NLP domain, we do not require any prior exposure to NLP (though it would be a plus). Ideally, I expect that you have some prior experience with machine learning, statistical NLP or IR. If you aren't sure if the class is for you, feel free to contact us and ask.


Ivan Titov and Alexandre Klementiev.

Time and Location

Thursdays at 14:15 in building C 7.2, room 2.11. [Note new timing!]

Office Hours

Please send us an e-mail to arrange a meeting (preferably meeting date is Tuesday).

Course Requirements

Requirements for the course are:

  • Present a paper to the class (30 - 45 minute presentation)
  • Write a very short review (1-2 paragraphs) for at least one paper presented at each class
  • Write a term paper (15-20 pages) (you do not need to write the term paper, if registered for 4 points)
  • Read papers before the talks and participate in discussion

Class Presentation

  • Present the chosen paper in an accessible way
  • Present sufficient background, do not expect the audience to know much about Machine Learning or Natural Language Processing, except for the material already covered in the class (according to surveys there is a good number of people who have no ML background)
  • Have a critical view on the paper: discuss shortcomings, possible future work, etc
  • To give a good presentation in most of the cases you will need to read one or two additional papers (e.g., those referenced in the paper)
  • You should have a look into material on how to give a good presentation compiled by Alexander Koller
  • The language for talks and discussions will be English
  • Given the number of students now, we are planning to have 35 minutes long presentations, on some days we may decide to have 2 presentations
  • Send both of us your slides (preferably in PDF) 7 days before the talk by 6 pm (the first 2 presenters can send me slides 2 days before the talk)
    • If we keep the class on Thursday, the deadline would be on Thursday the week before at 6 pm
    • You will get feedback from us 3 days before the seminar (on Mon)
    • If needed, we can meet to discuss the comments on Tue


  • A very short critical essay reviewing one of the papers recommended for each class
    • One or two paragraphs presenting the essence of the paper.
    • Other parts underlying both positive sides (what you like) of the paper and shortcomings.
  • You need to submit one review for each class
  • The review should be submitted (by email in text) before the presentation of the paper in class (Exception is the additional reviews submitted for the classes you missed: you should submit such an additional review within 2 weeks of the corresponding class and before the end of the term).
  • No copy-paste from the paper. It should be all your words.
  • Please send the reviews to the email address: reviews.winter2012@gmail.com and not to our addresses

Term paper


  • Choose a sub-topic covered in class, usually closely-related to the paper you presented (unless it happens that you are more interested in something else).
  • Do additional reading -- this would normally require reading around 10-12 additional papers. You can ask us or do some search yourself and then discuss you choice with us.
  • The paper may be either an insightful survey of the research on this topic or some novel ideas. In either cases you need to discuss the topic with us.
  • It should be written in a style of a research paper, the only difference is that in this paper most of the work you present here is not your own.
  • Your ideas, analysis, comparison.
  • It should be written in English.
  • Example structure:
    • Introduction and motivation for the problem.
    • Detailed survey of existing work.
    • Ideas on improvement of the approach
    • Alternative interpretation or analysis.
    • Amount of reading is adequate.

Grading criteria:

  • Clarity.
  • Paper organization.
  • Technical correctness.
  • Style (written in research style without inappropriate speculations, correct citations, etc).
  • Your ideas are meaningful and interesting.

Length: 12 - 15 pages.

Format: Submitted in PDF over email to both of us

Grading Policy

Marks will be assigned as follows:

  • Class participation: 60%
    • Your talk and discussion after the talk
    • Participation and discussion of other papers
    • 2 reviews (5% each)
  • Term paper: 40% (only if registered for 7 points, otherwise, class participation constitutes 100% of the grade)

Attendance Policy

You can skip ONE class without giving any explanation (if you are not presenting). If you need to skip more, you will need to write an additional critical review for every paper presented while you were absent.