Schedule

This is the schedule for Advanced Seminar in Computational Linguistics: Computational Models of Human Parsing, Fall 2016.

After some administrivial and general preliminaries, we'll begin by looking at how the parsing problem is introduced in computational linguistics. In the process of looking at a textbook NLP introduction to syntactic parsing, we'll make sure everyone gets up to speed on some core computational concepts like search, time and space complexity, formal description of parsing algorithms. We'll also include discussion of computational modeling a bit more generally, assisted by Marr's levels of description.

Readings

• Jurafsky and Martin, Chapter 13, Syntactic Parsing

  • You might also find the following useful

    • Stephen Pulman, Basic Parsing Techniques: an introductory survey, In Encyclopaedia of Language and Linguistics. Pergamon Press/ Aberdeen University Press. 1992.

    • Shieber et al., Principles and Implementation of Deductive Parsing (see Sections 1-3). Incidentally, I've realized that my specific characterization of deductive parsing as "logic plus control" (the latter discussed in Section 5) was, without doing so consciously, a reference to Kowalski (1979), Algorithm = logic + control.

• Marr, D. (1982), Vision: A Computational Approach, San Francisco, Freeman & Co., Introduction and Chapter 1

• Omaki (2009), Levels of Description in Linguistics (slides)

Optional homework

To really solidify your understanding of top down and bottom up parsing, I recommend you work your way through the top-down example on pages 7-9 of Shieber et al., and then see if you can understand the bottom-up shift-reduce parser and work through the example on pages 10-11 without first looking at the answer.

If you want to get hands on, a good starting point would be Chapter 8, Analyzing Sentence Structure from the NLTK (Natural Language Toolkit) book. NLTK is a suite of open source Python modules, data sets and tutorials supporting research and development in natural language processing and it can be very useful for (self-)learning.

Optional background

There is, of course, a voluminous literature in psycholinguistics discussing parsing from a computational angle, albeit not computational modeling per se. An early review touching on many of the major issues from a psycholinguistic perspective is

• Frazier, Lyn (1987), "Sentence processing: A tutorial review", in Coltheart, M., Attention and Performance XII: The Psychology of Reading, Lawrence Erlbaum Associates,

and a more current example reviewing some relevant issues, focused on comprehension of relative clauses, is

• P. Gordon and M. Lowder, "Complex Sentence Processing: A Review of Theoretical Perspectives on the Comprehension of Relative Clauses", Language and Linguistics Compass 6/7 (2012): 403–415, 10.1002/lnc3.347.

Readings

• If you've never read Marr before, read Marr, D. (1982), Vision: A Computational Approach, San Francisco, Freeman & Co., Introduction and Chapter 1.

• Stephen G. Pulman, Grammars, Parsers, and Memory Limitations, Language and Cognitive Processes 1(3), pp. 197-225, 1986.

  • If you're short on time, the following conference paper is a substitute that will get you the basics: Stephen G. Pulman, A Parser that Doesn't (more readable version here,

• Steve Abney and Mark Johnson (1991), Memory Requirements and Local Ambiguities of Parsing Strategies. (Larger-text version available here.)

• Philip Resnik (1992), Left-Corner Parsing and Psychological Plausibility, COLING.

Readings

• Stuart Shieber (1983), Sentence Disambiguation by a Shift-Reduce Parsing Technique

• Jurafsky and Martin, Chapter 14, Statistical Parsing

• Thorsten Brants and Matthew Crocker (2010), Probabilistic Parsing and Psychological Plausibility

Readings

• James Henderson (2004), Lookahead in Deterministic Left-Corner Parsing

• Dan Jurafsky (1996), A Probabilistic Model of Lexical and Syntactic Access and Disambiguation

Not about ambiguity but it's come up a number of times so let's have it on the reading list somewhere!

• Stuart Shieber (1983), Evidence against the context-freeness of natural language

Readings

• Dan Jurafsky (1996), A Probabilistic Model of Lexical and Syntactic Access and Disambiguation

• Steve Abney (1996), Statistical Methods and Linguistics

Readings

• Marten van Schijndel and William Schuler (2013), An Analysis of Frequency- and Memory-Based Processing Costs

• William Schuler, Samir AbdelRahman, Tim Miller, and Lane Schwartz (2010), Broad-Coverage Parsing Using Human-Like Memory Constraints

• Van Schijndel, Marten, Luan Nguyen, and William Schuler. "An analysis of memory-based processing costs using incremental deep syntactic dependency parsing." Proceedings of CMCL (2013).

• van Schijndel, Marten, Brian Murphy, and William Schuler. "Evidence of syntactic working memory usage in MEG data.". Proceedings of CMCL (2015): 79-88.

No class: Yom Kippur

Readings

• Continue: William Schuler, Samir AbdelRahman, Tim Miller, and Lane Schwartz (2010), Broad-Coverage Parsing Using Human-Like Memory Constraints

• Frank Keller (2010), Cognitively plausible models of human language processing

• Colin Phillips (2002), Linear Order and Constituency

Readings

• Eugene Charniak (2010), Top-Down Nearly-Context-Sensitive Parsing

• Vera Demberg, Frank Keller, and Alexander Koller (2013), Incremental, Predictive Parsing with Psycholinguistically Motivated Tree-Adjoining Grammar

Project discussions

Note late-breaking change to this week's reading

Readings

• Richard L. Lewis and Shravan Vasishth (2005), An Activation-Based Model of Sentence Processing as Skilled Memory Retrieval

Also of interest:

• Jonides et al. (2008) The Mind and Brain of Short-Term Memory. A very nice discussion arguing for unitary-store models that combine short-term and long-term memory.

• Whitehill (2013), Understanding ACT-R – an Outsider’s Perspective. A brief and useful overview.

• ACT-R parser code

Class will only go until 3:30pm today so that everyone can attend the first Baggett lecture.

We are covering this topic spread out over two class sessions. Today's session is a ramping-up, and then on November 30th we'll look at Stabler 2013 in depth.

Readings

• Kobele (2006), Syntax and Semantics in Minimalist Grammars Section 1. If you have time and inclination, it could be useful to look over Section 2.1 also.

• Tim Hunter and Chris Dyer (2013), Distributions on Minimalist Grammar Derivations, Section 2.

No class. Happy Thanksgiving!

Reading

• Edward Stabler (2013), Two models of minimalist, incremental syntactic analysis

• Tim Hunter and commentators (2013), Guest Post: Tim Hunter on Minimalist Grammars and Stats. (Make sure to read the entire comment thread.)

• Thomas Graf et al. (2015), A Refined Notion of Memory Usage for Minimalist Parsing

• Mark Johnson (2013), Language Acquisition as Statistical Inference (slides, video). Mainly focused on acquisition/statistical inference, but there's a section discussing probabilistic minimalist grammars related to Hunter and Dyer (2013).

• Stabler (1997), Derivational Minimalism

• Stabler (2010), Computational perspectives on minimalism

This week we'll be doing more of an introduction to a class of methods, rather than a deep dive into a specific piece of research about computational modeling of human parsing.

Plan:

• Philip will do a more lecture-style discussion of Yoav Goldberg, A Primer on Neural Network Models for Natural Language Processing sections 10-12. Earlier sections of this primer may be useful background in order to get core ideas and understand notation.

• We'll probably zoom in on LSTMs in particular, for which Colah, Understanding LSTM Networks would be worth looking at.

• Please look over Linzen et al., Assessing the ability of LSTMs to learn syntax-sensitive dependencies.

Of related interest

• Here is a really nice, understandable discussion of the vanishing gradient problem, motivating rectified linear units (ReLU) by Rohan Kapur.

• Schuler, William. "Sentence processing in a vectorial model of working memory." ACL 2014 (2014): 19.

• Chris Dyer, Adhiguna Kuncoro, Miguel Ballesteros, and Noah A. Smith, Recurrent neural network grammars

Philip Resnik, Associate Professor
Department of Linguistics and Institute for Advanced Computer Studies


Department of Linguistics
1401 Marie Mount Hall            UMIACS phone: (301) 405-6760       
University of Maryland           Linguistics phone: (301) 405-8903
College Park, MD 20742 USA	   Fax: (301) 314-2644 / (301) 405-7104
http://umiacs.umd.edu/~resnik	   E-mail: resnik AT umd _DOT.GOES.HERE_ edu