Prediction and reanalysis are considered two key processes that underly humans’ capacity to comprehend language in real time. Computational models capture it using Large Language Models (LLMs) and a statistical measure known as ‘surprisal’. Despite successes of LLMs, surprisal-based models face challenges when it comes to sentences requiring reanalysis due to pervasive temporary structural ambiguities, such as garden path sentences. We ask whether structural information can be extracted from LLM’s and develop a model that integrates it with their learnt statistics. When applied to a dataset of garden path sentences, the model achieved a significantly higher correlation with human reading times than surprisal. It also provided a better prediction of the garden path effect and could distinguish between sentence types with different levels of difficulty.

Humans understand sentences word-by-word, in the order that they hear them.This incrementality entails resolving temporary ambiguities about syntactic relationships.We investigate how humans process these syntactic ambiguities by correlating predictions from incremental generative dependency parsers with timecourse data from people undergoing functional neuroimaging while listening to an audiobook.In particular, we compare competing hypotheses regarding the number of developing syntactic analyses in play during word-by-word comprehension: one vs more than one.This comparison involves evaluating syntactic surprisal from a state-of-the-art dependency parser with LLM-adapted encodings against an existing fMRI dataset.In both English and Chinese data, we find evidence for multipath parsing.Brain regions associated with this multipath effect include bilateral superior temporal gyrus.

Do large multilingual language models learn language universals?We consider a much discussed candidate universal, the Final-over-Final Condition (Sheehan et al., 2017b).This Condition is syntactic in the sense that it can only be stated by reference to abstract sentence properties such as nested phrases and head direction.A study of typologically diverse "mixed head direction" languages confirms that the Condition holds in corpora.But in a targeted syntactic evaluation, Gemini Pro only seems to respect the Condition in German, Russian, Hungarian and Serbian.These relatively high-resource languages contrast with Basque, where Gemini Pro does not seem to have learned the Condition at all.This result suggests that modern language models may need additional sources of bias in order to become truly human-like, within a developmentallyrealistic budget of training data.

Most computational models of dependency syntax consist of distributions over spanning trees.However, the majority of dependency treebanks require that every valid dependency tree has a single edge coming out of the ROOT node, a constraint that is not part of the definition of spanning trees.For this reason all standard inference algorithms for spanning trees are suboptimal for inference over dependency trees.Zmigrod et al. (2021b) proposed algorithms for sampling with and without replacement from the dependency tree distribution that incorporate the single-root constraint.In this paper we show that their fastest algorithm for sampling with replacement, Wilson-RC, is in fact producing biased samples and we provide two alternatives that are unbiased.Additionally, we propose two algorithms (one incremental, one parallel) that reduce the asymptotic runtime of algorithm for sampling k trees without replacement to O(kn 3 ).These algorithms are both asymptotically and practically more efficient.

In the paper “Formal Basis of a Language Universal” by Miloš Stanojević and Mark Steedman in Computational Linguistics 47:1 (https://doi.org/10.1162/coli_a_00394), there is an error in example (12) on page 17.The two occurrences of the notation ∖W should appear as |W. The paper has been updated so that the paragraph reads:In the full theory, these rules are generalized to “second level” cases, in which the secondary function is of the form (Y|Z)|W such as the following “forward crossing” instance, in which — matches either / or ∖ in both input and output:(12) The Forward Crossing Level Two Composition Rule X/×Y (Y∖Z)|W ⇒B× (X∖Z)|W (B×2)

Abstract We introduce Transformer Grammars (TGs), a novel class of Transformer language models that combine (i) the expressive power, scalability, and strong performance of Transformers and (ii) recursive syntactic compositions, which here are implemented through a special attention mask and deterministic transformation of the linearized tree. We find that TGs outperform various strong baselines on sentence-level language modeling perplexity, as well as on multiple syntax-sensitive language modeling evaluation metrics. Additionally, we find that the recursive syntactic composition bottleneck which represents each sentence as a single vector harms perplexity on document-level language modeling, providing evidence that a different kind of memory mechanism—one that is independent of composed syntactic representations—plays an important role in current successful models of long text.

We describe two approaches to single-root dependency parsing that yield significant speed ups in such parsing.One approach has been previously used in dependency parsers in practice, but remains undocumented in the parsing literature, and is considered a heuristic.We show that this approach actually finds the optimal dependency tree.The second approach relies on simple reweighting of the inference graph being input to the dependency parser and has an optimal running time.Here, we again show that this approach is fully correct and identifies the highest-scoring parse tree.Our experiments demonstrate a manyfold speed up compared to a previous graph-based state-of-the-art parser without any loss in accuracy or optimality. 1

Abstract Steedman (2020) proposes as a formal universal of natural language grammar that grammatical permutations of the kind that have given rise to transformational rules are limited to a class known to mathematicians and computer scientists as the “separable” permutations. This class of permutations is exactly the class that can be expressed in combinatory categorial grammars (CCGs). The excluded non-separable permutations do in fact seem to be absent in a number of studies of crosslinguistic variation in word order in nominal and verbal constructions. The number of permutations that are separable grows in the number n of lexical elements in the construction as the Large Schröder Number Sn−1. Because that number grows much more slowly than the n! number of all permutations, this generalization is also of considerable practical interest for computational applications such as parsing and machine translation. The present article examines the mathematical and computational origins of this restriction, and the reason it is exactly captured in CCG without the imposition of any further constraints.

Incremental syntactic parsing has been an active research area both for cognitive scientists trying to model human sentence processing and for NLP researchers attempting to combine incremental parsing with language modelling for ASR and MT.Most effort has been directed at designing the right transition mechanism, but less has been done to answer the question of what a probabilistic model for those transition parsers should look like.A very incremental transition mechanism of a recently proposed CCG parser when trained in straightforward locally normalised discriminative fashion produces very bad results on English CCGbank.We identify three biases as the causes of this problem: label bias, exposure bias and imbalanced probabilities bias.While known techniques for tackling these biases improve results, they still do not make the parser state of the art.Instead, we tackle all of these three biases at the same time using an improved version of beam search optimisation that minimises all beam search violations instead of minimising only the biggest violation.The new incremental parser gives better results than all previously published incremental CCG parsers, and outperforms even some widely used non-incremental CCG parsers.

Minimalist Grammars (Stabler, 1997) are a computationally oriented, and rigorous formalisation of many aspects of Chomsky's (1995) Minimalist Program.This paper presents the first ever application of this formalism to the task of realistic wide-coverage parsing.The parser uses a linguistically expressive yet highly constrained grammar, together with an adaptation of the A* search algorithm currently used in CCG parsing (Lewis and Steedman, 2014;Lewis et al., 2016), with supertag probabilities provided by a bi-LSTM neural network supertagger trained on MGbank, a corpus of MG derivation trees.We report on some promising initial experimental results for overall dependency recovery as well as on the recovery of certain unbounded long distance dependencies.Finally, although like other MG parsers, ours has a high order polynomial worst case time complexity, we show that in practice its expected time complexity is O(n 3 ).The parser is publicly available.

One of the most pressing issues in discontinuous constituency transition-based parsing is that the relevant information for parsing decisions could be located in any part of the stack or the buffer.In this paper, we propose a solution to this problem by replacing the structured perceptron model with a recursive neural model that computes a global representation of the configuration, therefore allowing even the most remote parts of the configuration to influence the parsing decisions.We also provide a detailed analysis of how this representation should be built out of sub-representations of its core elements (words, trees and stack).Additionally, we investigate how different types of swap oracles influence the results.Our model is the first neural discontinuous constituency parser, and it outperforms all the previously published models on three out of four datasets while on the fourth it obtains second place by a tiny difference.

In this paper we explore the novel idea of building a single universal reordering model from English to a large number of target languages. To build this model we exploit typological features of word order for a large number of target languages together with source (English) syntactic features and we train this model on a single combined parallel corpus representing all (22) involved language pairs. We contribute experimental evidence for the usefulness of linguistically defined typological features for building such a model. When the universal reordering model is used for preordering followed by monotone translation (no reordering inside the decoder), our experiments show that this pipeline gives comparable or improved translation performance with a phrase-based baseline for a large number of language pairs (12 out of 22) from diverse language families.

Existing approaches for evaluating word order in machine translation work with metrics computed directly over a permutation of word positions in system output relative to a reference translation. However, every permutation factorizes into a permutation tree (PET) built of primal permutations, i.e., atomic units that do not factorize any further. In this paper we explore the idea that permutations factorizing into (on average) shorter primal permutations should represent simpler ordering as well. Consequently, we contribute Permutation Complexity, a class of metrics over PETs and their extension to forests, and define tight metrics, a sub-class of metrics implementing this idea. Subsequently we define example tight metrics and empirically test them in word order evaluation. Experiments on the WMT13 data sets for ten language pairs show that a tight metric is more often than not better than the baselines.

We present a novel approach for unsupervised induction of a Reordering Grammar using a modified form of permutation trees (Zhang and Gildea, 2007), which we apply to preordering in phrase-based machine translation.Unlike previous approaches, we induce in one step both the hierarchical structure and the transduction function over it from word-aligned parallel corpora.Furthermore, our model (1) handles non-ITG reordering patterns (up to 5-ary branching), ( 2) is learned from all derivations by treating not only labeling but also bracketing as latent variable, (3) is entirely unlexicalized at the level of reordering rules, and (4) requires no linguistic annotation.Our model is evaluated both for accuracy in predicting target order, and for its impact on translation quality.We report significant performance gains over phrase reordering, and over two known preordering baselines for English-Japanese.

Sentence level evaluation in MT has turned out far more difficult than corpus level evaluation. Existing sentence level metrics employ a lim-ited set of features, most of which are rather sparse at the sentence level, and their intricate models are rarely trained for ranking. This pa-per presents a simple linear model exploiting 33 relatively dense features, some of which are novel while others are known but seldom used, and train it under the learning-to-rank frame-work. We evaluate our metric on the stan-dard WMT12 data showing that it outperforms the strong baseline METEOR. We also ana-lyze the contribution of individual features and the choice of training data, language-pair vs. target-language data, providing new insights into this task. 1