Human Sentence Processing: Models of Computation and Storage

Evaluating Models of Computation and Storage in Human Sentence Processing Thang Luong CogACLL 2015 Tim J. O Donnell & Noah D. Goodman

What computed and what stored? Storage bucket kick the bucket kick the A basic question for theories of language representation, processing, and acquisition. At the sub-word level (O Donnell, 2015): ness in pine-scentedness vs. th in warmth. Many empirical & theoretical work. Few work applies to cognitive datasets.

Human Sentence Processing Probabilistic syntax models Incremental parsing algorithms Human reading difficulty + Probabilistic syntax models: Reading times: (Roark et al., 2009). Eye fixation times: (Demberg & Keller, 2008). No work has examined the influence of storage and computation in syntax.

This work Maximal computation Maximal storage Study the influence of storage units in predicting reading difficulty. surprisals C&S models Reading difficulty Incremental Parser Mixed-effects Analysis Propose a framework to evaluate C&S models.

Models of computation & storage 3 models of computation & storage (C&S) Dirichlet Fragment Grammars MAP Adaptor Grammars multinomial PCFGs Maximal computation Maximal storage Gold parse trees are assumed to be known Can do MAP estimation.

C&S Models Maximal Computation N N N N A dj -ity A dj -ity A dj -ity -ness A dj V -able V -able V -able V -able agre e agre e agre e count Dirichlet-Multinomial PCFG (Johnson, et al. 2007) Storage: minimal abstract units PCFG rules Computation: maximal. Put less probability mass on frequent structures

C&S Models Maximal storage N N N N -ity A dj A dj -ity A dj -ity A dj -ness V -able V -able V -able V -able agre e agre e agre e count MAP Adaptor Grammar (Johnson, et al. 2007) Storage: DMPCFGs + maximally specific units. Computation: minimal. Put probability mass on two many infrequent structures

C&S Models Inference-based N N N N A dj -ity A dj -ity A dj -ity -ness A dj V -able V -able V -able V -able agre e agre e agre e count Fragment grammars (O Donnell, et al. 2009) Storage: inference over rules best explains data. Rules in MAG + rules rewrite to non-terminals / terminals Computation: optimal. Make the right trade-off between storage and computation.

Human reading time prediction surprisals C&S models Reading difficulty Incremental Parser Mixed-effects Analysis Improve our parser to handle different grammars.

Surprisal Theory Lexical predictability of words given contexts (Hale, 2001) and (Levy, 2008) Surprisal value: Strong correlation with: Eye-tracking time: (Demberg and Keller, 08). Self-paced reading time: (Roark et al., 09).

Incremental Parser Top-down approach for CFG (Earley, 1970). Earley algorithm for PCFG (Stolcke, 1995): Prefix probabilities Needed to to compute surprisal values: Our parser: based on Levy (08) s parser. Additional features to handle different grammars. Publicly available.

Incremental parser Features Handle arbitrary PCFG rewrite rules: MAP Adaptor Grammars: VP -> kick the bucket Fragment Grammars: VP -> kick NP Handle large grammars: Grammars # rules DM-PCFG 75K FG 146K MAG 778K

Human reading time prediction surprisals C&S models Reading data Incremental Parser Mixed-effects Analysis Show consistent results in two different corpora.

Experiments Grammars: DMPCFG, MAG, FG trained on WSJ (length < 40 words). Corpora: Eye-tracking: Dundee corpus (Kennedy & Pynte, 05). Self-paced reading: MIT corpus (Bachrach et al., 09). Sent Word Subj Orig Filtered Dundee 2,370 58K 10 586K 229K MIT 199 3.5K 23 81K 70K

Model Prediction Evaluation Dundee MIT DMPCFG MAG 6.82 6.91 6.80 6.95 FG 6.35 6.35 How well models predict words in the test data? Average the surprisal values. Ranking: FG DMPCFG MAG

Evaluation on Cognitive Data How well models explain reading times? Mixed-effects analysis. Surprisal values for DMPCFG, MAG, FG as predictors. Settings: similar to (Fossum and Levy, 2012). Random effects: by-word and by-subject intercepts. Eye fixation and reading times: log-transformed. Nested model comparisons with ?2 tests.

Additive tests ? ?2 Dundee MIT Base + DMPCFG Base + MAG 70.9** 10.9* 38.5** 0.1 Base + FG 118.3** 62.5** (**: 99% significant, *: 95% significant) Effect of each grammar predictor. Ranking: FG DMPCFG MAG

Subtractive tests ? ?2 Dundee MIT Full - DMPCFG Full - MAG 4.0* 14.3** 3.5* 23.6** Full - FG 62.5** 42.9** (**: 99% significant, *: 95% significant) Effect of each grammar predictor explains above and beyond others. Ranking: FG MAG DMPCFG DMPCFG doesn t explain above and beyond FG.

Mixed-effect coefficients Dundee MIT DMPCFG MAG 0.00195 -0.00141 0.00324 -0.00282 FG 0.00549 0.00697 Full setting: with predictors from all models. MAG is negatively correlated with reading time. Syntax is still mostly compositional. Only a small fraction of structures are stored.

Conclusion Study the effect of computation & storage in predicting reading difficulty: Dirichlet Fragment Grammars MAP Adaptor Grammars multinomial PCFGs Maximal computation Maximal storage Provide a framework for future research in human sentence processing. Thank you!

Earley parsing algorithm Top-down approach developed by Earley (1970): States pending derivations: [l, r] X Y . Z Operations state transitions: predict, scan, complete Predict Scan Complete Grammar: S NP VP, VP V NP, NP dogs, NP cats, V chase dogs chase cats Root . S Root S . S . NP VP S NP . VP S NP VP . VP . V NP VP V . NP VP V NP . NP . cats NP cats . NP . dogs NP dogs . V . chase V chase . 0 1 2 3

Earley algorithm for PCFGs (Stolcke, 95) Earley path: a sequence of states linked by Earley operations (predict, scan, complete). Partial derivations Earley paths. P(d) = product of rule probs used in predicted states. Prefix probability: sum of derivation probabilities across all paths yielding a prefix x. Root P(dn) Earley paths d1 d2 ... dn Prefix probability P(w0w1 wi) P(d2) w0 w1 the wi P(d1) dogs piggie