Memory-bounded Neural Incremental Parsing for Psycholinguistic Prediction (2020)

Abstract: Syntactic surprisal has been shown to have an effect on human sentence processing, and can be predicted from prefix probabilities of generative incremental parsers. Recent state-of-the-art incremental generative neural parsers are able to produce accurate parses and surprisal values but have unbounded stack memory, which may be used by the neural parser to maintain explicit in-order representations of all previously parsed words, inconsistent with results of human memory experiments. In contrast, humans seem to have a bounded working memory, demonstrated by inhibited performance on word recall in multi-clause sentences (Bransford and Franks, 1971), and on center-embedded sentences (Miller and Isard,1964). Bounded statistical parsers exist, but are less accurate than neural parsers in predict-ing reading times. This paper describes a neural incremental generative parser that is able to provide accurate surprisal estimates and can be constrained to use a bounded stack. Results show that the accuracy gains of neural parsers can be reliably extended to psycholinguistic modeling without risk of distortion due to un-bounded working memory.

## introduction syntactic surprisal has been shown to have an effect on human sentence processing, and can be calculated from prefix probabilities of generative incremental parsers @xcite , making it a useful baseline predictor when looking for effects of other factors, like limits of memory or attention. recent work in generative neural network parsing @xcite has shown that generative parsers based on neural networks are more accurate than earlier statistical generative parsers, and can be used for surprisal calculation. although a typical shift-reduce neural network parser like that used by @xcite and @xcite may be successful in predicting brain imaging data, the depth of its stack memory, the model component where past predicted items are faithfully stored, can be as long as the whole derivational history of the parse @xcite . this potentially sentence-length stack may be used by the neural parser to maintain explicit in-order representations of all previously parsed words. in contrast, humans seem to have a bounded working memory, demonstrated by inhibited performance on word recall in multiclause sentences @xcite , and on center-embedded sentences @xcite ). 1 explicit storage of this long parsing history may improve parsing accuracy, but it also risks distorting the predictions of the model when used as a statistical control in psycholinguistic experiments. left-corner parsers @xcite ) have been argued to provide human-like limits on working memory, because the stack memory requirements of this kind of parser do not grow unboundedly in linguistically common cases of left-or right recursion, only in linguistically rare cases of center recursion. for example, a left corner parser would require only one memory element to process the right recursive sentence, 'the dog chased the cat that ate the rat that nibbled the malt,' but would require three elements to process the center recursive 1 specifically, @xcite found that subjects were not reliably able to recall word-order information such as whether sentences were in passive or active voice following exposure to sentence stimuli, and @xcite found that subjects were not able to understand sentences with deeply nested center-embedded structures, such as: this paper therefore defines a neural-network left-corner parser with bounded stack memory for parsing and psycholinguistic prediction. experiments described in this paper show that this generative left-corner neural network parser is competitive with incremental generative parsers that use unbounded stack memory in a parsing task, and outperforms statistical memory-bounded generative left-corner parsers both in parsing accuracy and in fitting human behavioral data on two different datasets, consistent with the conclusion that accuracy gains of neural parsers can be reliably extended to psycholinguistic modeling without risk of distortion due to unbounded working memory. ## related work incremental generative constituent parsers are able to process sentences in time order and provide psycholinguistically predictive measures like syntactic surprisal and entropy reduction @xcite @xcite , which in turn are used in psycholinguistic experiments for probing effects of syntax on behavioral data @xcite @xcite . statistical incremental parsers like ones proposed by @xcite and @xcite are based on contextfree grammars. the @xcite parser builds syntactic structures top-down incrementally and has been used in studies for calculating surprisal @xcite @xcite . left-corner parsers @xcite are often used to model limits on center embedding @xcite @xcite @xcite . van @xcite proposed an incremental parser that takes working memory constraints into account, and is able to produce probabilistic measures as well as predictions about working memory operations @xcite . @xcite propose a parser which is also able to produce prefix probabilities for tree-adjoining grammars. all of these statistical parsers lag behind state-of-the-art parsers in parsing accuracy, because of psycholinguistic constraints like incrementality and because they use less expressive statistical models. state-of-the-art constituency parsers generally are neural network models @xcite @xcite . @xcite propose a generative neural model for top-down incremental parsing but use it only as a reranker for a discriminative parser. extensions to @xcite model allow the parser to do in-order tree traversal @xcite . 2 however, the in-order transition system has a bias towards left children of constituents, which is not desirable when the model is used to calculate prefix probabilities. this issue was addressed by using word-synchronous beam search @xcite or variable sized beam search @xcite and successfully predict brain imaging data. however, all of these parsers do not limit the number of stack elements the parser has direct access to at any timestep, which in some cases can be equal to number of derivational decisions made up to the current timestep. this behavior of unbounded stack does not match what we know about human working memory and is undesirable for calculating predictors like probabilistically-weighted emdedding depth @xcite . the model described in this paper avoids these problems by using a left-corner transition system, which uses a bounded pushdown store and a fixed set of probabilistic decisions per word. the bounded stack memory not only more closely implements human working memory limits in a model designed to calculate cognitive predictors, other work @xcite shows that it also helps limit search space for unsupervised grammar acquisition. there are two sets of a and b nodes on the stack. at each timestep, a and b nodes of the lowest derivation fragment will be predicted. if they have already been predicted or they do not exist, then the decision will be null. pos tags for terminals are omitted. ## incremental left corner transition system with bounded working memory this paper introduces a neural left-corner transition system for incremental constituency parsing with minimal working memory requirements. this system defines a fixed set of parser decisions at each time step. following these parsing decisions, the parser incrementally generates each word in a sentence and the syntactic structures associated with that word, in time order. because the parser needs space on the stack only when there is center-embedding in the sentence, this transition system uses much less stack memory than other shift-reduce transition systems @xcite , modeling the psycholinguistic phenomenon that center-embedding is rare and hard for humans to process. ## parsing model this section defines a memory-bounded neural incremental generative parser as a generative probability model for surprisal calculation using the proposed left-corner transition system. in the description below, all lstms are stack-lstms @xcite with coupled input and forget gates @xcite and all ffs are feed-forward neural networks. surprisal at a word w t is defined as the negative log of the probability of that word given its preceding words w 1..t-1 under some model θ. this can be computed by marginalizing over the final hidden state of a sequence: the hidden states q t of the model described in this paper consist of: probabilities for observing a word and transitioning to a new hidden state at each time step t, given a hidden state at the previous time step t-1, can then be decomposed into terms for each individual decision and resulting vector: the probability of observing a word depends on bounded representations of the store, the decision sequence and the word sequence: this probability term defines a distribution over generate decisions. the probability of a cell and hidden vector of the word lstm is deterministic given the preceding operations, and is modeled as an indicator equal to one when the vectors are as defined by the corresponding lstm model, zero otherwise: similarly for the cell and hidden states of the decision lstm: the probability of a preterminal category decision depends on a bounded representation of the word sequence at the current time step, and a bounded representation of the decision sequence and the store at the previous time step, and the trained and untrained pre-trained word embeddings: this term defines a distribution over preterminal (part of speech) decisions. the probability of a top category decision depends on a bounded representation of the word sequence at the current time step and a bounded representation of the decision sequence and the store at the previous time step: this term defines a distribution over pja decisions. the probability of a bottom category decision depends on a bounded representation of the word the lstm ✓@xmath0 a p j e 6 y v z m p u j f w 6 c g 4 w g 6 p h 0 e v m 8 z r s 1 1 z s m x 4 q g t 6 7 v a t d p n x b w c 0 q x n y i v n 0 6 5 z s i v 2 b n y i c w a k q g a o d s 0 v t x e y 2 i c a m a b k t r 0 7 w k 5 c j x i m i m 2 7 s y k i s h e d q f v t g p q g o s n k k n q 6 0 u r p 6 o d s v 4 d w r p 2 9 k v b f q b h v 6 u m f 4 l d n e 5 n 4 n 9 e o s x / r s x g q x q g b m z 7 u j 4 w f o z w l y v w 4 b i z i r a l l k u u / w m x i j w w o s 8 v r e j z 5 k x d j 4 6 z o l i q x t 6 v c u t s l i 0 c o y t e 5 j q 4 5 j 2 v s i v v s j 4 w 8 k m f y s t 6 m j + p f e d c + p q n l x m z n g p y b 8 f k d n + c a u @xmath1 figure 3 : the model makes the prediction for the generate-the decision at timestep 3 in the probability of a top vector is deterministic given the preceding operations, and is modeled as an indicator function equal to one when the vectors are as defined by a set of lstms over dependent top and bottom store vectors, depending on the previous bottom category and current top category decisions: the probability of a bottom vector is also deterministic and modeled as an indicator function equal to one when the vectors are as defined by a set of lstms over dependent top and bottom store vectors, depending on the previous bottom category and current top category decisions: finally, the probability of a cell and hidden vector of the decision lstm is also deterministic and modeled as an indicator equal to one when the vectors are as defined by the corresponding lstm model, zero otherwise: ## experiments a first set of experiments compare the linguistic accuracy of the bounded neural parser to other generative incremental parsers using bracketing f1 scores on the penn treebank @xcite . a second set of experiments then compare the psycholinguistic accuracy of the bounded neural parsing model against an equivalently bounded non-neural parsing model by regressing syntactic surprisal derived from each model to selfpaced reading times from the natural stories corpus @xcite and eye-tracking fixation durations of newspaper article reading from the dundee eye-tracking corpus @xcite . the neural parser used in all experiments is trained on sections 02 -21 of the wall street journal part of the penn treebank. hyper-parameters of the parser are tuned on the development set, wsj section 22. the cross-entropy objective is used for about 9 epochs before accuracy on the development set starts to decrease, with stochastic gradient descent (sgd) using initial learning @xmath2.1 and gradually decreasing the learning baseline baseline +vs13 baseline +neural baseline +both 102340 102330 102320 102310 102300 102290 loglikelihood ns *** *** natural stories baseline baseline +vs13 baseline +neural baseline +both model 32332 32330 32328 32326 32324 32322 ns *** ** dundee: first-pass baseline baseline +vs13 baseline +neural baseline +both 39724 39722 39720 39718 39716 ns ** * dundee: go-past figure 4: goodness of fit of the regression model with different surprisal values calculated by the incremental left-corner parser in van schijndel et al. (2013) and the incremental neural parser to human reading times and eye tracking data. likelihood ratio tests are conducted to obtain p values. * * * : @xmath3, * * : @xmath4, * : @xmath5, ns: @xmath6.05. the trained model then is used to calculate surprisal for sentences in the natural stories corpus and the dundee corpus for psycholinguistic accuracy evaluation. these experiments only use the exploratory set of both corpora. corpus cleaning follows @xcite . the parser uses the basic set of constraints to parse the natural stories and dundee corpora, only rejecting parses that would lead to premature termination of the parsing process while doing beam search, with width 2000. ## conclusion this paper proposes a new incremental left-corner transition system that can calculate surprisal and other psycholinguistic predictors, and a new neural generative incremental parser to use this transition system to do memory-bounded incremental generative parsing. experiments described in this paper show that this generative left-corner neural network parser is competitive with incremental generative parsers that use unbounded stack memory in a parsing task, and outperforms statistical memory-bounded generative left-corner parsers both in parsing accuracy and in fitting human behavioral data on two different datasets, showing that accuracy gains of neural parsers can be reliably extended to psycholinguistic modeling without risk of distortion due to unbounded working memory.