Modeling Incremental Language Comprehension in the Brain with C ombinatory C ategorial G rammar (2021)

Abstract: Hierarchical sentence structure plays a role in word-by-word human sentence comprehension, but it remains unclear how best to characterize this structure and unknown how exactly it would be recognized in a step-by-step process model. With a view towards sharpening this picture, we model the time course of hemodynamic activity within the brain during an extended episode of naturalistic language comprehension using Combinatory Categorial Grammar (CCG). CCG has well-defined incremental parsing algorithms, surface compositional semantics, and can explain long-range dependencies as well as complicated cases of coordination. We find that CCG-derived predictors improve a regression model of fMRI time course in six language-relevant brain regions, over and above predictors derived from context-free phrase structure. Adding a special Revealing operator to CCG parsing, one designed to handle right-adjunction, improves the fit in three of these regions. This evidence for CCG from neuroimaging bolsters the more general case for mildly context-sensitive grammars in the cognitive science of language.

## introduction the mechanism of human sentence comprehension remains elusive; the scientific community has not come to an agreement about the sorts of abstract steps or cognitive operations that would bestexplain people's evident ability to understand sentences as they are spoken word-by-word. one way of approaching this question begins with a competence grammar that is well-supported on linguistic grounds, then adds other theoretical claims about how that grammar is deployed in real-time processing. the combined theory is then evaluated against observations from actual human language processing. this approach has been successful in accounting for eye-tracking data, for instance * correspondence to m.stanojevic@ed.ac.uk starting from tree-adjoining grammar and adding a special verification operation @xcite . in this spirit, the current paper models the hemodynamics of language comprehension in the brain using complexity metrics from psychologicallyplausible parsing algorithms. we start from a mildly context-sensitive grammar that supports incremental interpretation, foot_0 combinatory categorial grammar (ccg; for a review see @xcite . we find that ccg offers an improved account of fmri blood-oxygen level dependent time courses in "language network" brain regions, and that a special revealing parser operation, which allows ccg to handle optional postmodifiers in a more human-like way, improves fit yet further @xcite . these results underline the consensus that an expressive grammar, one that goes a little beyond context-free power, will indeed be required in an adequate model of human comprehension @xcite . ## a focus on the algorithmic level a step-by-step process model for human sentence parsing would be a proposal at @xcite middle level, the algorithmic level (for a textbook introduction to these levels, see bermúdez, 2020, §2.3). while this is a widely shared research goal, a large proportion of prior work linking behavioral and neural data with parsing models has relied upon the flower that you love np /n n (n \n )/(s /np ) np (s [dcl ]\np )/@xmath0: ccg derivation and extracted semantic dependencies for a relative clause from the little prince. red highlighting indicates filler-gap relationship. the surprisal linking hypothesis, which is not an algorithm. in fact surprisal wraps an abstraction barrrier around an algorithmic model, deriving predictions solely from the probability distribution on that model's outputs (for a review see @xcite . this abstraction is useful because it allows for the evenhanded comparison of sequence-oriented models such as ngrams or recurrent neural networks against hierarchical, syntax-aware models. and indeed in eye-tracking, this approach confirms that some sort of hierarchical structure is needed (see e.g. @xcite . this same conclusion seems to be borne out by fmri data @xcite @xcite . but precisely because of the abstraction barrier that it sets up, surprisal is ill-suited to the task of distinguishing ordered steps in a processing mechanism. we therefore put surprisal aside in this paper, focusing instead on complexity metrics that are nearer to algorithms; the ones introduced below in §5.3 all map directly on to tree traversals. by counting derivation tree nodes, these metrics track work that the parser does, rather than the rar-ity of particular words or ambiguity of particular constructions. 2 previous research at the algorithmic level has been limited in various ways. @xcite used an expressive grammar, but it was not broad coverage and the step counts were based on derived x-bar trees rather than the derivation trees that would need to be handled by a provably correct parsing algorithm @xcite . @xcite used a full-throated parser but employed the penn treebank phrase structure without explicit regard for long-distance dependency. figure 2 shows an example of one of these dependencies. ## why ccg? ccg presents an opportunity to remedy the limitations identified above in section 2. as already mentioned, ccg is appropriately expressive @xcite . and it has special characteristics that are particularly attractive for incremental parsing. ccg can extract filler-gap dependencies such as those in the object relative clause in figure 2 , synchronously and incrementally building surface compositional semantics (cf. demberg 2012). 3 ccg also affords many different ways of 2 counting derivation-tree nodes dissociates from surprisal. @xcite addresses the choice of linking hypothesis empirically by deriving both step-counting and surprisal predictors from the same parser. the former but not the latter predictor significantly improves a regression model of fmri timecourse in posterior temporal lobe, even in the presence of a co-predictor derived from a sequence-oriented language model. 3 the derivations in figure 1 and 2 use type-raising as a parser operation. in the definition of ccg from @xcite type-raising is not a syntactic, but a lexical operation. the reason why we use it as a parsing operation is because that is the way it was defined in the ccgbank @xcite and because it is implemented as such in all broad coverage parsers. type-raising contributes to the complexity metric described in section 5.3 deriving the same sentence (see figure 1 ). these alternative derivations all have the same semantics, so from the point of view of comprehension they are all equally useful. @xcite 2) argues that this flexible constituency is the key to achieving human-like incremental interpretation without unduly complicating the relationship between grammar and processor. incremental interpretation here amounts to delivering updated meaning-representations at each new word of the sentence. such early delivery would seem to be necessary to explain the high degree of incrementality that has been demonstrated in laboratory experiments @xcite @xcite . other types of grammar rely upon special parsing strategies to achieve incrementality. eager left-corner parsing (lc) is often chosen because it uses a finite amount of memory for processing leftand right-branching structures @xcite . @xcite was the first to notice a similarity between eager left-corner cfg parsing and shift-reduce parsing of ccg left-branching derivations. in short, forward type-@xmath1. however, ccg has other combinators that make it even more incremental. for instance, in a level one center embedding such as "mary gave john a book" a left-corner parser cannot establish connection between mary and gave before it sees john. ccg includes a generalized forward function @xmath2. to our knowledge, the present study is the first to validate the human-like processing characteristics of ccg by quantifying their fit to human neural signals. ## the challenge of right adjunction for incremental parsing a particular grammatical analysis may be viewed as imposing ordering requirements on left-to-right incremental parser operations; it obligates certain operations to wait until others have finished. a case in point is right adjunction in sentences such as "mary reads papers daily." (see figure 3a ). here the parser has built "mary reads papers" eagerly, as it should be expected from any parser with humanlike behavior, but then it encountered the adjunct "daily". this adjunct is an optional postmodifier of the verb phrase "reads papers." it could be analyzed using the rule @xmath3. with this rule, a context-free phrase structure parser will be forced either (i) to backtrack upon seeing "daily" or (ii) to leave the vp open for postmodification @xcite opts for the latter). neither of these alternatives is particularly appealing from the perspective of cognitive modeling, and indeed @xcite report a pattern of eyetracking data that appears to be inconsistent with ccg. they suggest that ccg's account of conjunction, itself analyzable as adjunction, imposes an ordering requirement that cannot be satisfied in psycholinguistically-realistic way. sturt and lombardo's 2005 finding is an important challenge for theories of incremental interpretation, including neurolinguistic models based on lc parsing @xcite . @xcite offer a crucial part of a solution to this problem. first, they relax the notion of attaching of a right-adjunct: an adjunct does not have to attach to the top category of the tree but it can attach to any node on the right spine of the derivation, as long as the attachment respects the node's syntactic type. in figure 3a the right spine is highlighted in blue. however, none of the constituents on the right spine can be modified by "daily" because the constituent that needs to be modified, "reads papers" was never built; it is not part of the leftbranching derivation. to address this, the stanojević and steedman parser includes a second innovation: it applies a special tree-rotation operation that transforms left-branching derivations into semantically equivalent right-branching ones. in figure 3b this operation produces a new right spine, revealing a node of type s\np , which is the type assigned to english verb phrases in ccg. in figure 3c the adjunct "daily" is properly attached to this boxed node via application, a ccg rule that is used quite generally across many different constructions. the idea of attaching right-adjuncts to a node of an already-built tree has appeared several times before @xcite @xcite and in all cases it crucially leverages ccg's flexible constituency as shown in figure 1 . see @xcite for more detailed treatment of sturt and lombardo's construction using predictive completion. the present study examines whether or not the addition of the revealing operation increases the fidelity of ccg-derived parsing predictions to human fmri time course data. ## methods we follow @xcite and @xcite in using a spoken narrative as a stimulus in the fmri study. participants hear the story over headphones while they are in the scanner. the neuroimages collected during their session serve as data for regression modeling with word-by-word predictors derived from the text of the story. ## discussion the improvement that ccg brings to modeling fmri time courses -over and above predictors derived from well-known context-free parsing strategies -confirms that mildly context-sensitive grammars capture real aspects of human sentence processing, as suggested earlier by @xcite . we interpret the additional improvement due to the revealing operation as neurolinguistic evidence in support of that particular way of achieving heightened incrementality in a parser. while it is possible that other incremental parsing techniques might adequately address the challenge of right adjunction (see §4 above) we are at present unaware of any that are supported by evidence from human neural signals. the patterning of fits across regions aligns with the suggestion that different kinds of processing, some more eager and others less so, may be happening across the brain (cf. just and varma 2007). for instance the explanatory success of predictors derived from left-branching and revealing derivations in the middle temporal pole (matl) supports the idea that this region tracks tightly time-locked, incremental language combinatorics foot_6 while other regions such as the inferior frontal gyrus (ifg) hang back, waiting to process linguistic relationships until the word at which they would be integrated into a rightbranching ccg derivation (roughly consistent with @xcite . in the superior temporal gyrus (stg) the sign of the effect changes for ccg-derived predictors. this is the unique region where @xcite observe an effect of phrase structure processing, as opposed to dependency grammar processing. this could be because our ccg is lexicalized. of course, the ccgbank grammar captures many other aspects of sentence structure besides lexical dependencies (see @xcite . @xcite use a different, noncombinatory categorial grammar to model fmri time courses. whereas this earlier publication employs the surprisal linking hypothesis to study predictive processing, the present study considers instead the parsing steps that would be needed to recover grammatical descriptions assigned by ccg. this distinction can be cast as the difference between marr's computational and algorithmic levels of analysis, as suggested above in §2. but besides the choice of vantage point, there are conceptual differences that lead to different modeling at both levels. for instance, the generalized categorial grammar of @xcite is quite expressive and may go far beyond context-free power. but in that study it was first flattened into a probabilistic context-free grammar (pcfg) to derive surprisal predictions. the present study avoids this step by deriving processing complexity predictions directly from ccg derivations using node count. this directness is important when reasoning from human data, such as neural signals, to mathematical properties of formal systems, such as grammars (see discussion of competence hypotheses in @xcite ). this prior work by @xcite includes a telling observation: that surprisal from a 5-gram language model improves fit to brain data, over and above a pcfg. shain et al. hypothesize that this additional contribution is possible expressly because of pcfgs' context-freeness, and that a (mildly) context-sensitive grammar would do better. the results reported here are consistent with this suggestion. ## conclusion and future work ccg, a mildly context-sensitive grammar, helps explain the time course of word-by-word language comprehension in the brain over and above penn treebank-style context-free phrase structure grammars regardless of whether they are parsed leftcorner, top-down or bottom-up. this special contribution from ccg is likely attributable to its more realistic analysis of "movement" constructions (e.g. figure 2 ) which would not be assigned by naive context-free grammars. ccg's flexible approach to constituency may offer a way to understand both immediate and delayed subprocesses of language comprehension from the perspective of a single grammar. the revealing operation, designed to facilitate more human-like ccg parsing, indeed leads to increased neurolinguistic fidelity in a subset of brain regions that have been previously implicated in language comprehension. we look ahead in future work to quantifying the effect of individual complexity metrics across brain regions using alternative metrics related to surprise and memory (e.g. @xcite . this future work also includes investigation of syntactic ambiguity, for instance via beam search along the lines of @xcite using the incremental neural ccg model of @xcite .