A computational model of human parsing

This report describeslicensing-structure parsing (LS-parsing), a computational model of human parsing. LS-parsing corresponds to human parsing at three points: (1) the order in which the LS parser builds nodes is psychologically more accurate than the orders in which either LL or LR parsers build nodes, (2) the LS parser's preferences in resolving local ambiguities are preferable to Frazier's strategies on both empirical and theoretical grounds, and (3) the backtracking strategies the parser uses when it has made an error at an earlier choice point model the distinction betweenweak andstrong garden paths-strong garden paths being irrecoverable, weak garden paths causing psychological difficulty, but not preventing recovery of the correct structure.     

Competition and recency in a hybrid network model of syntactic disambiguation

The competitive attachment model of human parsing is a hybrid connectionist architecture consisting of a distributed feature passing method for establishing syntactic relations within the network, and a numeric competition mechanism for resolving ambiguities, which applies to all syntactic relations. Because the approach employs a uniform mechanism for establishing syntactic relations, and a single competition mechanism for disambiguation, the model can capture general behaviors of the human parser that hold across a range of syntactic constructions. In particular, attachment and binding relations are similarly processed and are therefore subject to the very same influences of disambuguation and processing over time. An important influence on the competitive disambiguation process is distance within the network. Decay of numeric activation, along with distributed feature passing through the network structure, has an unavoidable effect on the outcome of attachment and binding competitions. Inherent properties of the model thus lead to a principled explanation of recency effects in the human parsing of both attachment and filler/gap ambiguities.     

Judgments of Processing Load in Japanese: The Effect of NP-ga Sequences

This study reports an effect of more than two consecutive noun phrases (NPs) with the same nominative case marker, -ga, on ratings of processability for Japanese multiply center-embedded sentences. The findings imply that the processing overload theory of Babyonyshev and Gibson (1995) requires modification. Although that theory sets the critical limit (beyond which parser breakdown occurs) at four processing load units (PLUs), it appears that the parser is overloaded by anything over five PLUs. where a three NP-ga sequence contributes roughly an additional PLU to processing cost. The evidence also suggests that inherently cased NPs are not cost free.     

The sausage machine: A new two-stage parsing model

It is proposed that the human sentence parsing device assigns phrase structure to word strings in two steps. The first stage parser assigns lexical and phrasal nodes to substrings of roughly six words. The second stage parser then adds higher nodes to link these phrasal packages together into a complete phrase marker.This model of the parser is compared with ATN models, and with the two-stage models of Kimball (1973) and Fodor, Bever and Garrett (1974). Our assumption that the units which are shunted from the first stage to the second stage are defined by their length, rather than by their syntactic type, explains the effects of constituent length on perceptual complexity in center embedded sentences and in sentences of the kind that fall under Kimball's principle of Right Association. The particular division of labor between the two parsing units allows us to explain, without appeal to any ad hoc parsing strategies, why the parser makes certain ‘shortsighted’ errors even though, in general, it is able to make intelligent use of all the information that is available to it.     

A Probabilistic Model of Lexical and Syntactic Access and Disambiguation

The problems of access—retrieving linguistic structure from some mental grammar —and disambiguation—choosing among these structures to correctly parse ambiguous linguistic input—are fundamental to language understanding. The literature abounds with psychological results on lexical access, the access of idioms, syntactic rule access, parsing preferences, syntactic disambiguation, and the processing of garden-path sentences. Unfortunately, it has been difficult to combine models which account for these results to build a general, uniform model of access and disambiguation at the lexical, idiomatic, and syntactic levels. For example, psycholinguistic theories of lexical access and idiom access and parsing theories of syntactic rule access have almost no commonality in methodology or coverage of psycholinguistic data. This article presents a single probabilistic algorithm which models both the access and disambiguation of linguistic knowledge. The algorithm is based on a parallel parser which ranks constructions for access, and interpretations for disambiguation, by their conditional probability. Low-ranked constructions and interpretations are pruned through beam-search; this pruning accounts, among other things, for the garden-path effect. I show that this motivated probabilistic treatment accounts for a wide variety of psycholinguistic results, arguing for a more uniform representation of linguistic knowledge and for the use of probabilistically-enriched grammars and interpreters as models of human knowledge of and processing of language.     

Falsifying Serial and Parallel Parsing Models: Empirical Conundrums and An Overlooked Paradigm

When the human parser encounters a local structural ambiguity, are multiple structures pursued (parallel or breadth-first parsing), or just a single preferred structure (serial or depth-first parsing)? This note discusses four important classes of serial and parallel models: simple limited parallel, ranked limited parallel, deterministic serial with reanalysis, and probabilistic serial with reanalysis. It is argued that existing evidence is compatible only with probabilistic serial-reanalysis models, or ranked parallel models augmented with a reanalysis component. A new class of linguistic structures is introduced on which the behavior of serial and parallel parsers diverge the most radically: multiple local ambiguities are stacked to increase the number of viable alternatives in the ambiguous region from two to eight structures. This paradigm may provide the strongest test yet for parallel models.     

Syntactic structure assembly in human parsing: a computational model based on competitive inhibition and a lexicalist grammar

We present the design, implementation and simulation results of a psycholinguistic model of human syntactic processing that meets major empirical criteria. The parser operates in conjunction with a lexicalist grammar and is driven by syntactic information associated with heads of phrases. The dynamics of the model are based on competition by lateral inhibition ('competitive inhibition'). Input words activate lexical frames (i.e. elementary trees anchored to input words) in the mental lexicon, and a network of candidate 'unification links' is set up between frame nodes. These links represent tentative attachments that are graded rather than all-or-none. Candidate links that, due to grammatical or 'treehood' constraints, are incompatible, compete for inclusion in the final syntactic tree by sending each other inhibitory signals that reduce the competitor's attachment strength. The outcome of these local and simultaneous competitions is controlled by dynamic parameters, in particular by the Entry Activation and the Activation Decay rate of syntactic nodes, and by the Strength and Strength Build-up rate of Unification links. In case of a successful parse, a single syntactic tree is returned that covers the whole input string and consists of lexical frames connected by winning Unification links. Simulations are reported of a significant range of psycholinguistic parsing phenomena in both normal and aphasic speakers of English: (i) various effects of linguistic complexity (single versus double, center versus right-hand self-embeddings of relative clauses; the difference between relative clauses with subject and object extraction; the contrast between a complement clause embedded within a relative clause versus a relative clause embedded within a complement clause); (ii) effects of local and global ambiguity, and of word-class and syntactic ambiguity (including recency and length effects); (iii) certain difficulty-of-reanalysis effects (contrasts between local ambiguities that are easy to resolve versus ones that lead to serious garden-path effects); (iv) effects of agrammatism on parsing performance, in particular the performance of various groups of aphasic patients on several sentence types.     

Use of verb information in syntactic parsing: evidence from eye movements and word-by-word self-paced reading

We investigated whether readers use verb information to aid in their initial parsing of temporarily ambiguous sentences. In the first experiment, subjects' eye movements were recorded. In the second and third experiments, subjects read sentences by using a noncumulative and cumulative word-by-word self-paced paradigm, respectively. The results of the first two experiments supported Frazier and Rayner's (1982) garden-path model of sentence comprehension: Verb information did not influence the initial operation of the parser. The third experiment indicated that the cumulative version of the self-paced paradigm is not appropriate for studying on-line parsing. We conclude that verb information is not used by the parser to modify its initial parsing strategies, although it may be used to guide subsequent reanalysis.     

Prediction and substantiation: A new approach to natural language processing

This paper describes a new approach to natural language processing which results in a very robust and efficient system. The approach taken is to integrate the parser with the rest of the system. This enables the parser to benefit from predictions that the rest of the system makes in the course of its processing. These predictions can be invaluable as guides to the parser in such difficult problem areas as resolving referents and selecting meanings of ambiguous words. A program, called FRUMP for Fast Reading Understanding and Memory Program, employs this approach to parsing. FRUMP skims articles rather than reading them for detail. The program works on the relatively unconstrained domain of news articles. It routinely understands stories it has never before seen. The program's success is largely due to its radically different approach to parsing.     

Against repair-based reanalysis in sentence comprehension

Structural reanalysis is generally assumed to be representation-preserving, whereby the initial analysis is manipulated or repaired to arrive at a new structure. This paper contends that the theoretical and empirical basis for such approaches is weak. A conceptually simpler alternative is that the processor reprocesses (some portion of) the input using just those structure-building operations available in first-pass parsing. This reprocessing is a necessary component of any realistic processing model. By contrast, the structural revisions required for second-pass repair are more powerful than warranted by the abilities of the first-pass parser. This paper also reviews experimental evidence for repair presented by Sturt, Pickering, and Crocker (1999). We demonstrate that the Sturt et al. findings are consistent with a reprocessing account and present a self-paced reading experiment intended to tease apart the repair and reprocessing accounts. The results support a reprocessing interpretation of Sturt et al.'s data, rendering a repair-based explanation superfluous.     

Learning To Parse?

A strong claim about human sentence comprehension is that the processing mechanism is fully innate and applies differently to different languages only to the extent that their grammars differ. If so, there is hope for an explanatory project which attributes all parsing strategies to fundamental design characteristics of the parsing device. However, the whole explanatory program is in peril because of the discovery (Cuetos & Mitchell, 1988) that Late Closure is not universal: Spanish, and also Dutch and other languages, favor Early Closure (high attachment) where English favors Late Closure flow attachment). I argue that the universal parser can weather this storm. Exceptions to Late Closure in Spanish and other languages are observed only in one construction (a relative clause attaching into a complex noun phrase [NP]), which is borderline in English too. For other constructions, low attachment is preferred in all languages tested. I propose that what differentiates the complex NP construction is the heaviness of the attachee compared to that of the host configuration. A relative clause is a heavy attachee, and the lower NP alone is small as a host; the relative is therefore better balanced if the whole complex NP is its host. A wide range of facts is accounted for by the principle that a constituent likes to have a sister of its own size. Light constituents will tend to attach low, and heavy ones to attach high, since larger constituents are dominated by higher nodes. A preference for balanced weight is familiar from work on prosodic phrasing. I suggest, therefore, that prosodic processing occurs in parallel with syntactic processing (even in reading) and influences structural ambiguity resolution. Height of attachment ambiguities are resolved by the prosodically motivated same-size-sister constraint. The exceptional behavior of English may be due to its prosodic packaging of a relative pronoun with the adjacent noun, overriding the balance tendency. If this explanation is correct, it is possible that all cross-language variations in parsing preferences are due to cross-language variations in the prosodic component of the competence grammar.     

Simple,applied text parsing

Text parsing for use in linguistic or artificial intelligence research can often be ill-suited for use in other lines of investigation in which simple, problem-specific parsing techniques may be used. This paper describes the development of a simple text parser for use in a specific research setting. The resulting parsing programs are compact enough for easy use on most available m inland microcomputers, while still providing adequate results for some applications such as chunking text into small units for later presentation.     

Working memory constraints on the processing of syntactic ambiguity.

We propose a model that explains how the working-memory capacity of a comprehender can constrain syntactic parsing and thereby affect the processing of syntactic ambiguities. The model's predictions are examined in four experiments that measure the reading times for two constructions that contain a temporary syntactic ambiguity. An example of the syntactic ambiguity is The soldiers warned about the dangers . . . ; the verb warned may either be the main verb, in which case soldiers is the agent; or the verb warned may introduce a relative clause, in which case soldiers is the patient of warned rather than the agent, as in The soldiers warned about the dangers conducted the midnight raid. The model proposes that both alternative interpretations of warned are initially activated. However, the duration for which both interpretations are maintained depends, in part, on the reader's working-memory capacity, which can be assessed by the Reading Span task (Daneman & Carpenter, 1980). The word-by-word reading times indicate that all subjects do additional processing after encountering an ambiguity, suggesting that they generate both representations. Furthermore, readers with larger working-memory capacities maintain both representations for some period of time (several words), whereas readers with smaller working-memory capacities revert to maintaining only the more likely representation.     

Parsing to Learn

Learning a language by parameter setting is almost certainly less onerous than composing a grammar from scratch. But recent computational modeling of how parameters are set has shown that it is not at all the simple mechanical process sometimes imagined. Sentences must be parsed to discover the properties that select between parameter values. But the sentences that drive learning cannot be parsed with the learner's current grammar. And there is not much point in parsing them with just one new grammar. They must apparently be parsed with all possible grammars, in order to find out which one is most successful at licensing the language. The research task is to reconcile this with the fact that the human sentence parsing mechanism, even in adults, has only very limited parallel parsing capacity. I have proposed that all possible grammars can be folded into one, if parameter values are fragments of sentential tree structures that the parser can make use of where necessary to assign a structure to an input sentence. However, the problem of capacity limitations remains. The combined grammar will afford multiple analyses for some sentences, too many to be computed on-line. I propose that the parser computes only one analysis per sentence but can detect ambiguity, and that the learner makes use of unambiguous input only. This provides secure information but relatively little of it, particularly at early stages of learning where few grammars have been excluded and ambiguity is rife. I consider three solutions: improving the parser's ability to extract unambiguous information from partially ambiguous sentences, assuming default parameter values to temporarily eliminate ambiguity, reconfiguring the parameters so that some are subordinate to others and do not present themselves to the learner until the others have been set. A more radical alternative is to give up the quest for error-free learning and permit parameters to be set without regard for whether the parser may have overlooked an alternative analysis of the sentence. If it can be assumed that the human parser keeps a running tally of the parameter values it has accessed, then the learner would do nothing other than parse sentences for comprehension, as adults do. The most useful parameter values would become more and more easily accessed; the noncontributors would drop out of the running. There would be no learning mechanism at all, over and above the parser. But how accurate this system would be remains to be established.     

Effects of tasks on BOLD signal responses to sentence contrasts: Review and commentary

Functional neuroimaging studies of syntactic processing have been interpreted as identifying the neural locations of parsing and interpretive operations. However, current behavioral studies of sentence processing indicate that many operations occur simultaneously with parsing and interpretation. In this review, we point to issues that arise in discriminating the effects of these concurrent processes from those of the parser/interpreter in neural measures and to approaches that may help resolve them.     

Testing the shared resource assumption in theories of text processing

Eight experiments evaluated a core assumption of several theories of text processing, the shared resource assumption, which states that component text processes share limited processing resources. Short texts each contained two critical sentences that together warranted a causal inference. The syntactic structure of the second sentence was either more or less difficult to parse. Results from a lexical decision task suggested that readers formed the causal inferences when the syntactic structure was less difficult to parse but that inferencing was constrained when syntactic structure was more difficult. Follow-up experiments suggested that this interference was not due to inferior output of the syntactic parser nor to the increased demands of difficult syntax interfering with maintenance of information needed to form the inference. The results suggest insufficient resources were available for the operation of inference processes due to the increased demands of syntactic parsing, consistent with the shared resource assumption.     

Syntactic Features in Reanalysis: Positive and Negative Symptoms

Meng and Bader have presented evidence that a Case conflict is a more effective cue for garden-path reanalysis than a number conflict is, for German wh-sentences with subject–object ambiguities. The preferred first-pass analysis has the wh-trace in subject position, although object position is correct. In a speeded grammaticality judgment task, perceivers accepted Case-disambiguated examples more often and more rapidly than number-disambiguated examples, although comprehension questions indicated that both were eventually understood correctly. For ungrammatical sentences, a Case mismatch error resulted in more false positive grammaticality judgments than a number mismatch error. We offer an explanation for why Case and number features differ in these two ways in their effects on sentence processing. We propose, within the Diagnosis Model of garden-path processing, that reanalysis triggered by a Case mismatch guides the parser more effectively toward the correct structure. Case is a positive symptom, which carries information about the new structure that must be built. By contrast, a number mismatch is a negative symptom; it invalidates the incorrect structure without showing how to rebuild it. This difference in the transparency of garden-path repair can also account for the greater overacceptance of Case-disambiguated ungrammatical sentences. The speeded grammaticality judgment task is designed to encourage hasty responses. Usually, these are hasty rejections of garden path sentences that, on calmer reflection, the parser would find acceptable. Conversely, over-hasty acceptance could occur if some initial progress is made in resolving a grammatical problem. Thus, a higher rate of false positives on ungrammaticals is to be expected where reanalysis proceeds successfully for a while before blocking.     

Making and correcting errors during sentence comprehension: Eye movements in the analysis of structurally ambiguous sentences

Eye movements were recorded as subjects read sentences containing temporary structural ambiguities. In accord with the garden-path theory of sentence comprehension, shorter reading times were found for sentences conforming to certain independently motivated parsing strategies (late closure and minimal attachment) than for comparable sentences which violate these strategies. Further, longer fixation durations were associated with the very first fixation in the region of the sentence which disambiguated the sentence, suggesting that the human sentence-parsing mechanism operates in a rather systematic fashion, immediately computing the structural consequences of fixated material for the analysis of preceding material. The pattern of regressive eye movements did not conform to the view that the parsing mechanism automatically returns to the beginning of the sentence to revise an incorrect analysis of linguistic material nor did it support the view that the parsing mechanism systematically backtracks through the sentence until the source of the erroneous analysis is located. Rather, the pattern of regressions indicated that the parsing mechanism typically engages in selective reanalysis, exploiting whatever information it has available about the type of error it has committed to guide its reanalysis attempts. Finally, it is emphasized that an understanding of the parser's revision procedures is essential to an explanation of why certain linguistic structures cannot be successfully parsed by humans.