Introduction to Natural Language Processing

CMPSCI 585, Fall 2014, UMass Amherst CS

Instructor:		Brendan O’Connor brenocon@cs.umass.edu	Office hours: Thursday after lecture (4pm–?), room 222, but see Piazza/email announcements for changes
TA:		David Belanger belanger@…	Office hours announced via Piazza/email
Lectures:	CS Building room 142, Tues and Thurs, 2:30–3:45pm
Links:	Schedule, Moodle (for hw submissions), Piazza (for questions/discussion), Grading/policies, Final project

Course description

Natural Language Processing (NLP) is the scientific and engineering discipline of how to get computers to understand and process human language. Machine translation, speech recognition, and search engines are all NLP systems that have revolutionized how we work with information. This course focuses on text, introducing the fundamental techniques for automated text analysis and understanding, which combine computational algorithms, statistical machine learning, and insights from linguistics.

There are no formal prerequisites for this course, though students should be very comfortable with programming, and have basic experience with algorithm analysis, probability theory, and machine learning (for example: big-O notation, Bayes Rule, and supervised classifiers), or be willing to work extra to learn these things independently. Students should also have some interest in natural language and linguistics.

After finishing this course, our goal is that students will:

• Understand the fundamental methods that are in widespread use in modern NLP systems.
• Have experience implementing near-state-of-the-art NLP systems for several tasks.
• Appreciate the basic linguistic issues that underlie NLP problems.
• Be able to read and implement current research papers (well, at least the simpler ones) published in places like ACL and EMNLP.
• Be able to solve a new NLP task by clarifying its linguistic definition, collecting annotated data, and building a system to solve it.

Requirements

• Weekly short exercises. These are short assignments to develop linguistic intutions.
• Several problem sets: substantial problems and programming assignments.
• Midterm and final exam.
• Final project: TBD

Readings

The suggested textbook is Jurafsky and Martin, Speech and Language Processing, 2nd ed.. Readings are listed on the schedule page.

Other useful texts include:

• Manning and Schütze, Foundations of Stat NLP. Free access at UMass.
• Smith, Linguistic Structure Prediction. Free access at UMass. Short book. Excellent coverage of structured prediction inference methods for NLP.
• Murphy, Machine Learning: a Probabilistic Perspective. Excellent coverage of almost all the machine learning methods we will use, though less of structured prediction inference.
• Bender, Linguistic Fundamentals for NLP. Short book.
• Bird et al, NLP with Python, a.k.a. the NLTK book. Completely free. NLTK’s prepackaged NLP tools are usually not state-of-the-art, but it has easy to use interfaces to data and resources, and the book is a great way to be introduced to NLP/CL.

Course topics

The following is a provisional list of topics. We will not have time to cover all of them, so it will be shortened and changed in various ways.

• Naive Bayes, maximum likelihood, Bayseian posteriors.
• N-gram language models.
• Machine translation.
• EM algorithm.
• Decoding: greedy and heuristic search.
• Logistic regression (aka maxent).
• Stochastic gradient descent with adaptive learning rates.
• Where do labels come from? Collecting annotations from humans.
• Sentiment analysis.
• Finite-state automata, regular expressions.
• Finite-state transducers, edit distance, morphology.
• Shallow syntax: Part-of-speech tagging, named entity recognition.
• Hidden Markov models, Viterbi decoding, forward-backward, semirings.
• Conditional random fields, structured perceptron.
• Constituent syntax: CFGs, PCFGs, independence issues, weighted CKY, inside-outside algorithm.
• Dependency syntax: shift-reduce algorithms, graph-based algorithms.
• NLP for conversational language and social media.
• Lexical semantics.
• Logical-form semantic parsing.
• Entity coreference: within-document, entity linking, cross-document
• Representation learning: Topic models.
• Representation learning: Neural networks (“deep learning”).

Related courses

If you would like to look at previous versions of the course, see:

• Fall 2009, taught by David Smith.
• Fall 2007, taught by Andrew McCallum.