Instructor

• Professor Chan
• Office: Douglass 305
• Office hours:
  M 12-2 by appointment
  T 1-2
  Th 1-3 by appointment
  F 1-3
• Office phone: 520-626-0678
• E-mail: echan3@email.arizona.edu

How to make an appointment: send me e-mail with a range of possible days and times.

Course information

• Syllabus
• 3 Units. This course will introduce students to the computational methods used in modern Statistical Natural Language Processing: corpora, principles of machine learning, statistical models of linguistic structure, and evaluation of performance. Applications include parsing, language modeling, part of speech tagging, sentiment analysis, machine translation, word sense disambiguation, information extraction, and other topics.

  Prerequisites: proficiency in computer programming. Recommended: formal language theory (LING 388 or 438/538 or automata theory), elementary probability, introductory linguistics. This course is intended to be accessible to students who have not taken college-level mathematics.

• Code of Academic Integrity

Schedule, slides, and readings

• 1/8 course introduction .pptx .pdf

  Recommended reading for non-linguists: Introduction to Linguistics for Natural Language Processing, Manning & Schutze chapter 3, Linguistics Essentials

  News articles about NLP:
  For Second Opinion, Consult a Computer? (12/4/2012)
  Facebook’s False Faces Undermine Its Credibility (11/13/2012)
  The Age of Big Data (2/12/2012)
  Software That Listens for Lies (12/4/2011)
  How Revolutionary Tools Cracked a 1700s Code (10/25/2011)
  Computer Conquers 'Jeopardy!' (1/14/2011)
  Computers That Trade on the News (12/23/2010)
  Mining the Web for Feelings, Not Facts (8/24/2009)
  For Today’s Graduate, Just One Word: Statistics (8/6/2009)

• 1/14 N-grams, Zipf's law, smoothing
  .pptx .pdf
  zipf.py Matplotlib plotting tutorial
  Reading: Manning & Schutze 1.4, 4; Jurafsky & Martin 4
  Google n-grams
  NLTK corpora
  Linguistic Data Consortium (LDC)
  other text corpora
  Math refreshers: sums, logarithms

• 1/16 topic modeling, conditional probability, entropy
  .pptx .pdf
  Reading: Manning & Schutze 2.1.1-2.1.7 (probability), 2.2.1 (entropy)
  Math refreshers: Venn diagrams, conditional probability, properties of logarithms
• 1/21 no class: MLK day
• 1/23 collocations, independence, chi-square test, pointwise mutual information
  .pptx .pdf
  Reading: Manning & Schutze chapter 5 (collocations)
  examples of collocations
  chi-square test
• 1/28 classification, feature choice, zero-count features
  .pptx .pdf
  read-features-numpy.py read-features.py
  Recommended reading: NLTK book, chapter 6
  Math refreshers: matrices, vectors and matrices
• 1/30 model selection
  .pptx .pdf
  plot-discriminants.py
  Recommended reading: Hastie chapters 1 and 2, Nilsson chapter 1
  Math refreshers: linear equations
• 2/4 perceptron
  .pptx .pdf
  perceptron.py
  Recommended reading: Perceptron, chapter on perceptron, Nilsson chapter 5, Neural Networks
  Perceptron applets: applet #1, applet #2, applet #3
  Math refreshers: dot product, transpose of a matrix, matrix multiplication, dot product and matrix multiplication

• 2/6 linear separability, SVM, sentiment analysis, stylometry
  .pptx .pdf
  Recommended reading: Hastie Chapter 12, sections 1-3
  SVM applets: applet #1, applet #2
  movie review analysis: Pang et al. (2002)
  Sentiment analysis webpage
  Sentiment analysis survey (2008)
  additional sentiment analysis links
  Stylometry: Wikipedia, Federalist papers: Fung (2003)

• 2/11 cognitive modeling, neural networks, English past tense; go over WA #2 and WA #3
  .pptx .pdf
  Recommended reading: Connectionism (Wikipedia), Nilsson chapter 5, Neural Networks
  Rumelhart & McClelland (1986): On Learning the Past Tense of English verbs (using a neural network)
  Pinker & Prince (1988): On Language and Connectionism: Analysis of a Parallel Distributed Processing Model of Language Acquisition
  Pinker & Ullman (2002): The past and future of the past tense
• 2/13 decision trees, memory-based learning, vowel perception
  .pptx .pdf
  Recommended reading: Marsland chapter 6, Nilsson 5.3 and chapter 6, Hastie 13.3
  K-nearest neighbors: applet #1, applet #2
  Orphanos et al. (1999): Decision Trees and NLP: A Case Study in POS Tagging
  acoustic phonetics, vowel perception,
  Math refreshers: Euclidean distance, Euclidean distance
• 2/18 ensemble learning; more probability theory
  part 1: .pptx .pdf
  part 2: .pptx .pdf
  Recommended reading: Marsland chapter 7, Hastie 7.10-7.11, 8.7
  Math refreshers: combinations, Bayes theorem
• 2/20 Bayesian networks, Naive Bayes classifier
  .pptx .pdf
  Bayesian networks: Kevin Murphy's tutorial, Kevin Murphy's paper, Andrew Moore's tutorial, Wikipedia
  Pantel & Lin (1998): SpamCop
• 2/25 generative probabilistic models, language models
  .pptx .pdf
  Recommended reading: Jurafsky & Martin chapter 4
  CMU-Cambridge Statistical Language Modeling
  SRI Language Modeling Toolkit
• 2/27 sequence classification, POS tagging, Hidden Markov Models
  .pptx .pdf
  Recommended reading: Jurafsky & Martin chapter 5 through 5.7, chapter 6 through 6.5
• 3/4 HMMs continued, evaluation of POS tagging
  .pptx .pdf
  Recommended reading on HMMs: Jurafsky & Martin chapter 5 through 5.7, chapter 6 through 6.5
  Recommended reading on error analysis for POS tagging: Jurafsky & Martin 5.7, Toutanova & Manning (2000): POS tagging and evaluation
• 3/6 POS tagging through transformation-based learning; NP chunking and named entity recognition
  .pptx .pdf
  Recommended reading: Jurafsky & Martin 22.1 (Named Entity Recognition), 13.5.2-3 (chunking)
  Transformation-based learning: Brill (1995)
  Phrase chunking: Ramshaw & Marcus (1995): text chunking, Tjong Kim Sang & Veenstra (1999): representing text chunks, CoNLL 2000 chunking shared task website, Tjong Kim Sang & Buchholz (2000): CoNLL 2000 shared task results
  Named entity recognition: Bikel et al. (1999): named entity recognition, CoNLL 2003 NER shared task website, Tjong Kim Sang & De Meulder (2003): results on NER shared task
• 3/18 no class
• 3/20 noisy channel model, statistical machine translation
  .pptx .pdf
  Recommended reading: Jurafsky & Martin 25, Machine Translation
  New York Times: Using Computing Might, Google Improves Translation Tool
  Warren Weaver (1949): memorandum
  Brown et al. (1990): statistical translation
  Brown et al. (1993): statistical translation
  Gale & Church (1993): sentence alignment
  Papinieni et al. (2002): BLEU MT evaluation
• 3/25 CFGs, PCFGs, parsing with CKY
  .pptx .pdf
  Recommended reading: Jurafsky & Martin chapters 12, 13, 14
  CFG review: 1, 2, 3
  Chris Manning videos on CFGs and parsing: 1, 2, 3, 4, 5
• 3/27 parsing the Penn Treebank, improving statistical parsing
  .pptx .pdf
  Marcus et al. (1993): Penn Treebank
  Klein & Manning (2003): accurate unlexicalized parsing
  Petrov et al. (2006): splitting tags for parsing
  Charniak & Johnson (2005): parse reranking
  NLTK data (includes part of Penn Treebank)

• NLP in the news:
  predictive typing
  randomly generated t-shirt slogans
• 4/1 Discriminative classifiers, word sense disambiguation, decision list; coreference resolution, information extraction
  .pptx .pdf
  Recommended reading: Jurafsky & Martin 20.0-20.4 (WSD), 21.3 (Reference resolution), 22 (information extraction)
  Yarowsky (1994): decision list (supervised)
  Yarowsky (1995): decision list applied to WSD (semi-supervised)
  WordNet
  Book chapter: Naive Bayes and Logistic Regression
  Haghighi & Klein (2009): coreference resolution
  Ng (2010): 15 years of NP coreference research
  MUC data for information extraction
• 4/3 Semi-supervised learning: co-training, Yarowsky algorithm
  .pptx .pdf
  Banko & Brill (2001): classifier performance on large datasets
  Joachims (1999): transductive SVM
  Blum & Mitchell (1998): co-training
  Yarowsky (1995): word sense disambiguation
  Collins & Singer (1999): named entity recognition
• 4/8 Semi-supervised learning: information extraction patterns, paraphses; sentence alignment
  .pptx .pdf
  Riloff (1996): supervised learning of relation patterns
  Yangarber (2000): learning relation patterns through bootstrapping
  Yangarber (2003): learning relation patterns through countertraining
  Gale & Church (1993): sentence alignment
  Barzilay & McKeown (2001): paraphrase induction
  Review: edit distance videos 1 2
• 4/10 Unsupervised learning: segmentation
  .pptx .pdf
  Harris (1954): From phoneme to morpheme
  Saffran et al. (1996): word segmentation by infants
  Gambell & Yang (2005): segmentation with stress information
  Hewlett & Cohen (2011): word segmentation as general chunking
  Ando & Lee (2003): Japanese segmentation
• 4/15 Unsupervised learning: model selection, minimal description length, morphology
  .pptx .pdf
  Goldsmith (2001): unsupervised learning of morphology
  Goldsmith (2007): towards a new empiricism
  Chan & Lignos (2011): unsupervised learning of morphology
  Linguistica software
• 4/17 Unsupervised learning: morphology continued; word class induction, k-means clustering
  .pptx .pdf
  list of tags in BNC enriched tagset
  cluster analysis (Wikipedia)
  clustering applets
  Christodopoulos et al (2010): 2 decades of unsupervised POS induction
• 4/22 Unsupervised learning: distributional learning, agglomerative clustering, lexical category induction
  .pptx .pdf
  Labelle (2005): grammatical category acquisition in children
  Redington, Chater, & Finch (1998): model children's acquisition of POS through clustering
  Mintz, Newport, & Bever (2002): model children's acquisition of POS through clustering
  Chan (2008): lexical category induction
  CHILDES corpora
• 4/24 Unsupervised learning: semantic topic models, latent semantic analysis
  .pptx .pdf
  Jia Lu's slides on topic models
  Deerwester et al. (1990): Latent Semantic Analysis
  LSA website
  Singular Value Decomposition
  Hofmann (1999): probabilistic LSA
  Latent Dirichlet Allocation
  Blei (2011): introduction to probabilistic topic models
• 4/29 unsupervised grammar induction; modeling children's acquisition of grammar
  .pptx .pdf
  Grunwald (1996): grammar induction through MDL
  Phillips (2004): benchmarks for grammar induction algorithms
  Fodor (1998): unambiguous triggers
  Yang (2002): probabilistic parameter setting
• 5/1 course summary; NLP and linguistic theory
  .pptx .pdf
  Vivek's blog: The Trouble with SVMs
  Abney (1996)
  Pereira (2000)
  Lee (2001/4)
  Chater & Manning (2006)
  Lappin & Shieber (2007)
  Bod (2009)
• 5/9 Last day of finals; last day to turn in assignments

Assignments

• Programming assignment #0, optional ungraded programming exercise
  english_vocab.txt
  (if you can successfully complete this exercise, your programming skills are sufficient for this course)
  pa0-answer.py
• Written assignment #1: survey and quiz, due 1/14
• Programming assignment #1, due 2/1 at 11:59 p.m. .pdf
  Penn Treebank POS tag set
• Written assignment #2: probability, due 2/4 .docx .pdf
  sample answers
• Written assignment #3: formulating classification problems, due 2/6 .docx .pdf
• Programming assignment #2: sentiment analysis, due 2/24 at 11:59 p.m. .pdf
  Pang et al. (2002)
  data: movie-review-train-valid.zip, movie-review-test.zip
  SVMlight
  sentiment-feature-count.py
  sentiment-baseline.py (incomplete)
• Written assignment #4: probability and Bayes nets, due 2/27 .docx .pdf
  answers
• Programming assignment #3: (Hidden|ε) Markov models, due 3/193/31 at 11:59 p.m. .docx .pdf
  sample.py
  alice.txt
• Written assignment #5, due 4/3: parse time flies like an arrow using CKY and the CFG in lecture 18 (3/25), slide 74.
• Programming assignment #4, due 4/21 at 11:59 p.m.: semi-supervised Word Sense Disambiguation .docx .pdf
  data
  Yarowsky (1994): decision list (supervised)
  Yarowsky (1995): decision list applied to WSD (semi-supervised)
  Collins & Singer (1999): named entity recognition
• Written assignment #6, due 4/29: exploration of NLP literature and resources .docx .pdf
• Programming assignment #5, due 5/9 at 11:59 p.m.: unsupervised learning of word classes and semantic topics .docx .pdf
  20 Newsgroups data
• (extra credit) (serves as extra credit for a written assignment) "#7", due 5/9 at 11:59 p.m.: essay on language and NLP .docx .pdf

NLP software

• List_of_natural_language_processing_toolkits, with programming language indicated
• Stanford NLP tools
• LingPipe
• OpenNLP
• FreeLing
• GATE

Programming resources

Students may use any programming language in completing their assignments.

For the benefit of students with less programming experience, below are some lectures on Python 3, taken from the course LING 508, Fall 2012. The basic concepts of programming covered in these lectures should be sufficient for completion of programming assignments in 539.

• introduction .pptx .pdf
• running Python, primitive and compound datatypes, assignment operator .pptx .pdf
• functions, variable scope, modules .pptx .pdf
• lists, mutability .pptx .pdf
• booleans, logical operators, conditionals, while loops .pptx .pdf
• loop control flow, linear and binary search, computational complexity .pptx .pdf
• sets, for loops .pptx .pdf
• for loops, bubble sort .pptx .pdf
• strings, string formatting .pptx .pdf
• file input/output, regular expressions .pptx .pdf alice.txt
• tuples, dictionaries .pptx .pdf
• dictionaries, word frequencies, references and mutability .pptx .pdf
• Numerical Python .pptx .pdf
• matplotlib resources
  • tutorial 1
  • tutorial 2
  • gallery
  • cookbook
  • user's guide

• Python for Java Programmers

NLP textbooks

• Daniel Jurafsky and James H. Martin. 2008. An Introduction to Natural Language Processing, Computational Linguistics, and Speech Recognition, Second Edition. Pearson / Prentice-Hall. website
• Christopher D. Manning and Hinrich Schütze. 1999. Foundations of Statistical Natural Language Processing. 6th printing with corrections, 2003. The MIT Press. website. Can be downloaded through the U of A library
• Christopher D. Manning, Prabhakar Raghavan and Hinrich Schütze. 2008. Introduction to Information Retrieval, Cambridge University Press. Available for free at the book website
• Noah A. Smith. 2011. Linguistic Structure Prediction. Morgan and Claypool. website

Machine learning textbooks

• John Kruschke. 2011. Doing Bayesian Data Analysis: A Tutorial with R and BUGS. Elsevier. website
• Simon Rogers and Mark Girolami. A First Course in Machine Learning. website
• Ethem Alpaydin. 2010. Introduction to Machine Learning, second edition. website
• Nils J. Nilsson. Draft, 2010. Introduction to Machine Learning. Available for free at the book website
• Stuart Russell and Peter Norvig. 2009. Artificial Intelligence: a Modern Approach, Third Edition. Pearson / Prentice-Hall. book website
• Stephen Marsland. 2009. Machine Learning: An Algorithmic Perspective. CRC Press. book website
• Christopher M. Bishop. 2006. Pattern Recognition and Machine Learning. Springer. book website
• Richard O. Duda, Peter E. Hart, and David G. Stork. 2001. Pattern Classification, 2nd Second Edition. Wiley-Interscience. website
• Trevor Hastie, Robert Tibshirani, and Jerome Friedman. 2001. The Elements of Statistical Learning: Data Mining, Inference, and Prediction. Springer. Available for free at the book website
• Tom Mitchell. 1997. Machine Learning. WCB / McGraw-Hill. website
• Thomas M. Cover and Joy A. Thomas. 2006. Elements of Information Theory, Second Edition. John Wiley & Sons. website

Other links

• LING 538, Fall 2012
• LING 388, Fall 2012
• LING 508, Fall 2012
• ACL anthology (research papers in NLP)
• Language Log (linguistics blog)
• Linguist List jobs
• NLP jobs from monster
• NLP blog
• Andrew Moore's statistical data mining tutorials

Further Study in Linguistics (for undergrads)

• Why Major in Linguistics: http://www.lsadc.org/info/ling-faqs-whymajor.cfm
• UA Linguistics Webpage: http://linguistics.arizona.edu/
• Information on our UG program: http://linguistics.arizona.edu/node/203
• Make an Appointment with a Linguistics Advisor: http://sbs.arizona.edu/advising/scheduling.php