📄 Broad-Coverage Parsing Using Human-Like Memory Constraints

Summary

The paper asks whether human sentence comprehension could run entirely inside general-purpose short-term memory, which is thought to hold only about three or four items. The authors propose a performance-oriented parsing model that applies a reversible right-corner transform, a variant of left-corner parsing. The transform turns right-branching structure into left-branching structure, so that incomplete constituents can be combined before either is finished. Each transformed tree maps onto random variables of a Hierarchical Hidden Markov Model (HHMM), which behaves like a probabilistic pushdown automaton with a pushdown store of fixed size. On the Penn Treebank, after a linguistically motivated head-based binarization, most sentences can be recognized with at most three incomplete constituents in memory, and almost all with four. Accuracy experiments show that the predictions forced by early composition can be learned reliably from training data. The work matters because it shows that rich phrase structure is compatible with realistic memory limits. It also complements, rather than replaces, surprisal- and interference-based explanations of processing difficulty.

Key points

• Resource and method: Penn Treebank, binarized with head-projection rules for NP, VP, ADJP, ADVP, PP and S (listed in Appendix A), then right-corner transformed and mapped onto an HHMM (Murphy and Paskin 2001).
• Coverage claim: a memory bound of 3 incomplete constituents covers the vast majority of sentences, and a bound of 4 covers nearly all. This matches Cowan's (2001) estimate of human memory capacity, not the older figure of about seven used in left-corner accounts by Johnson-Laird and by Abney and Johnson.
• Parser setup: the bounded-memory parser is evaluated without lexicalization or smoothing. It is compared with unbounded parsers that use similar conditioning information. The exact coverage and accuracy figures fall in the part of the paper omitted from the supplied extract.
• Theoretical position: the model treats memory as allocated conjunctively, across incomplete constituents within one hypothesis. Surprisal and activation models describe disjunctive allocation, across competing hypotheses. The authors therefore see the two accounts as orthogonal but potentially unifiable.
• Future work: a lexicalized version with head-word dependencies is postponed. It would require converting weighted PCFGs into right-corner form (Schuler 2009) using an approximation similar to value iteration. The research was funded by NSF CAREER/PECASE award 0,447,685 and NASA award NNX08AC36A.