# How Furiously Can Colourless Green Ideas Sleep?
Sentence Acceptability in Context

Jey Han Lau1,7 Carlos Armendariz2 Shalom Lappin2,3,4 Matthew Purver2,5 Chang
Shu6,7
1 The University of Melbourne 2 Queen Mary University of London
3 University of Gothenburg 4 King’s College London
5 Jožef Stefan Institute 6 University of Nottingham Ningbo China 7 DeepBrain
<EMAIL_ADDRESS><EMAIL_ADDRESS>
<EMAIL_ADDRESS><EMAIL_ADDRESS><EMAIL_ADDRESS>
###### Abstract

We study the influence of context on sentence acceptability. First we compare
the acceptability ratings of sentences judged in isolation, with a relevant
context, and with an irrelevant context. Our results show that context induces
a cognitive load for humans, which compresses the distribution of ratings.
Moreover, in relevant contexts we observe a discourse coherence effect which
uniformly raises acceptability. Next, we test unidirectional and bidirectional
language models in their ability to predict acceptability ratings. The
bidirectional models show very promising results, with the best model
achieving a new state-of-the-art for unsupervised acceptability prediction.
The two sets of experiments provide insights into the cognitive aspects of
sentence processing and central issues in the computational modelling of text
and discourse.

##  1 Introduction

Sentence _acceptability_ is the extent to which a sentence appears natural to
native speakers of a language. Linguists have often used this property to
motivate grammatical theories. Computational language processing has
traditionally been more concerned with _likelihood_ — the probability of a
sentence being produced or encountered. The question of whether and how these
properties are related is a fundamental one. Lau et al. (2017b) experiment
with unsupervised language models to predict acceptability, and they obtained
an encouraging correlation with human ratings. This raises foundational
questions about the nature of linguistic knowledge: if probabilistic models
can acquire knowledge of sentence acceptability from raw texts, we have prima
facie support for an alternative view of language acquisition that does not
rely on a categorical grammaticality component.

It is generally assumed that our perception of sentence acceptability is
influenced by _context_. Sentences which may appear odd in isolation can
become natural in some environments, and sentences which seem perfectly well
formed in some contexts are odd in others. On the computational side, much
recent progress in language modelling has been achieved through the ability to
incorporate more document context, using broader and deeper models (e.g.
Devlin et al. (2019); Yang et al. (2019)). While most language modelling is
restricted to individual sentences, models can benefit from using additional
context Khandelwal et al. (2018). However, despite the importance of context,
few psycholinguistic or computational studies systematically investigate how
context affects acceptability, or the ability of language models to predict
human acceptability judgments.

Two recent studies which explore the impact of document context on
acceptability judgments both identify a _compression_ effect Bernardy et al.
(2018); Bizzoni and Lappin (2019). Sentences perceived to be low in
acceptability when judged without context receive a boost in acceptability
when judged within context. Conversely those with high out-of-context
acceptability see a reduction in acceptability when context is presented. It
is unclear what causes this compression effect. Is it a result of cognitive
load, imposed by additional processing demands, or is it the consequence of an
attempt to identify a discourse relation between context and sentence?

We address these questions in this paper. To understand the influence of
context on human perceptions, we ran three crowdsourced experiments to collect
acceptability ratings from human annotators. We develop a methodology to
ensure comparable ratings for each target sentence in isolation (without any
context), in a relevant three-sentence context, and in the context of
sentences randomly sampled from another document. Our results replicate the
compression effect, and careful analyses reveal that both cognitive load and
discourse coherence are involved.

To understand the relationship between sentence acceptability and probability,
we conduct experiments with unsupervised language models to predict
acceptability. We explore traditional unidirectional (left-to-right) recurrent
neural network models, and modern bidirectional transformer models (e.g.
bert). We found that bidirectional models consistently outperform
unidirectional models by a wide margin, calling into question the suitability
of left-to-right bias for sentence processing. Our best bidirectional model
achieves simulated human performance on the prediction task, establishing a
new state-of-the-art.

##  2 Acceptability in Context

###  2.1 Data Collection

To understand how humans interpret acceptability, we require a set of
sentences with varying degrees of well-formedness. Following previous studies
Lau et al. (2017b); Bernardy et al. (2018), we use round trip machine
translation to introduce a wide range of infelicities into naturally occurring
sentences.

We sample 50 English (target) sentences and their contexts (three preceding
sentences) from the English Wikipedia.111We preprocess the raw dump with
WikiExtractor (https://github.com/attardi/wikiextractor), and collect
paragraphs that have $\geq 4$ sentences with each sentence having $\geq 5$
words. Sentences and words are tokenised with spaCy (https://spacy.io/) to
check for these constraints. We use Moses to translate the target sentences
into 4 languages (Czech, Spanish, German and French) and then back to
English.222We use the pre-trained Moses models from
http://www.statmt.org/moses/RELEASE-4.0/models/ for translation. This produces
250 sentences in total (5 languages including English) for our test set. Note
that we only do round trip translation for the target sentences; the contexts
are not modified.

We use Amazon Mechanical Turk to collect acceptability ratings for the target
sentences.333https://www.mturk.com/. We run three experiments where we expose
users to different types of context. For the experiments, we split the test
set into 25 HITs of 10 sentences. Each HIT contains 2 original English
sentences and 8 round trip translated sentences, which are different from each
other and not derived from either of the originals. Users are asked to rate
the sentences for naturalness on a 4-point ordinal scale: bad (1.0), not very
good (2.0), mostly good (3.0) and good (4.0). We recruit 20 annotators for
each HIT.

In the first experiment we present only the target sentences, without any
context. In the second experiment, we first show the context paragraph (three
preceding sentences of the target sentence), and ask users to select the most
appropriate description of its topic from a list of 4 candidate topics. Each
candidate topic is represented by three words produced by a topic model.444We
train a topic model with 50 topics on 15K Wikipedia documents with Mallet
McCallum (2002) and infer topics for the context paragraphs based on the
trained model. Note that the context paragraph consists of original English
sentences which did not undergo translation. Once the users have selected the
topic, they move to the next screen where they rate the target sentence for
naturalness.555Note that we do not ask the users to judge the naturalness of
the sentence in context; the instructions they see for the naturalness rating
task is the same as the first experiment. The third experiment has the same
format as the second, except that the three sentences presented prior to
rating are randomly sampled from another Wikipedia article.666Sampled
sentences are sequential, running sentences. We require annotators to perform
a topic identification task prior to rating the target sentence to ensure that
they read the context before making acceptability judgements.

For each sentence, we aggregate the ratings from multiple annotators by taking
the mean. Henceforth we refer to the mean ratings collected from the first (no
context), second (real context), and third (random context) experiments as h∅,
h+ and h-, respectively. We rolled out the experiments on AMT over several
weeks and prevented users from doing more than one experiment. Therefore a
disjoint group of annotators performed each experiment.

(a) h+ vs. h∅

(b) h- vs. h∅

(c) h- vs. h+

Figure 1: Scatter plots comparing human acceptability ratings.

To control for quality, we check that users are rating the English sentences
$\geq 3.0$ consistently. For the second and third experiments, we also check
that users are selecting the topics appropriately. In each HIT one context
paragraph has 1 real topic (from the topic model), and 3 fake topics with
randomly sampled words as the candidate topics. Users who fail to identify the
real topic above a confidence level are filtered out. Across the three
experiments, over three quarters of workers passed our filtering conditions.

To calibrate for the differences in rating scale between users, we follow the
postprocessing procedure of Hill et al. (2015), where we calculate the average
rating for each user and the overall average (by taking the mean of all
average ratings), and decrease (increase) the ratings of a user by 1.0 if
their average rating is greater (smaller) than the overall average by
1.0.777No worker has an average rating that is greater or smaller than the
overall average by 2.0. To reduce the impact of outliers, for each sentence we
also remove ratings that are more than 2 standard deviations away from the
mean.888This postprocessing procedure discarded a total of 504
annotations/ratings (approximately 3.9%) over 3 experiments. The final average
number of annotations for a sentence in the first, second, and third
experiments is 16.4, 17.8, and 15.3, respectively.

###  2.2 Results and Discussion

We present scatter plots to compare the mean ratings for the 3 different
contexts (h∅, h+ and h-) in Figure 1. The black line represents the diagonal,
and the red one the regression line. In general, the mean ratings correlate
strongly with each other. Pearson’s $r$ for h+ vs. h∅ $=$ 0.940, h- vs. h∅ $=$
0.911, and h- vs. h+ $=$ 0.891.

The regression (red) and diagonal (black) lines in h+ vs. h∅ (Figure 1(a))
show a compression effect. Bad sentences appear a little more natural, and
perfectly good sentences become slightly less natural when context is
introduced.999On average, good sentences (ratings $\geq 3.5$) observe a rating
reduction of 0.08 and bad sentences (ratings $\leq 1.5$) an increase of 0.45.
This is the same compression effect observed by Bernardy et al. (2018). It is
also present in the graph for h- vs. h∅ (Figure 1(b)).

Two explanations of the compression effect seem plausible to us. The first is
a discourse coherence hypothesis that takes this effect to be caused by a
general tendency to find infelicitous sentences more natural in context. This
hypothesis, however, does not explain why perfectly natural sentences appear
less acceptable in context. The second hypothesis is a variant of a cognitive
load account. On this view interpreting context imposes a significant burden
on a subject’s processing resources, and this reduces their focus on the
sentence presented for acceptability judgments. At the extreme ends of the
rating scale, as they require all subjects to be consistent in order to
achieve the minimum/maximum mean rating, the increased cognitive load
increases the likelihood of a subject making a mistake. This increases/lowers
the mean rating, and creates a compression effect.

The discourse coherence hypothesis would imply that the compression effect
should appear with real contexts, but not with random ones, as there is little
connection between the target sentence and a random context. By contrast, the
cognitive load account predicts that the effect should be present in both
types of context, as it depends only on the processing burden imposed by
interpreting the context. We see compression in both types of contexts, which
suggests that the cognitive load hypothesis is the more likely account.

However, these two hypotheses are not mutually exclusive. It is, in principle,
possible that both effects — discourse coherence and cognitive load — are
exhibited when context is introduced.

To better understand the impact of discourse coherence, consider Figure 1(c),
where we compare h- vs. h+. Here the regression line is parallel to and below
the diagonal, implying that there is a consistent decrease in acceptability
ratings from h+ to h-. As both ratings are collected with some form of
context, the cognitive load confound is removed. What remains is a discourse
coherence effect. Sentences presented in relevant contexts undergo a
consistent increase in acceptability rating.

To analyse the significance of this effect, we use the non-parametric Wilcoxon
signed-rank test (one-tailed) to compare the difference between h+ and h-.
This gives a $p$-value of $1.9\times 10^{-8}$, indicating that the discourse
coherence effect is significant.

Returning to Figures 1(a) and 1(b), we can see that (1) the offset of the
regression line, and (2) the intersection point of the diagonal and the
regression line, is higher in Figure 1(a) than in Figure 1(b). This suggests
that there is an increase of ratings, and so, in addition to the cognitive
load effect, a discourse coherence effect is also at work in the real context
setting.

We performed hypothesis tests to compare the regression lines in Figures 1(a)
and 1(b) to see if their offsets (constants) and slopes (coefficients) are
statistically different.101010We follow the procedure detailed in
https://statisticsbyjim.com/regression/comparing-regression-lines/ where we
collate the data points in Figures 1(a) and 1(b) and treat the in-context
ratings (h+ and h-) as the dependent variable, the out-of-context ratings (h∅)
as the first independent variable, and the type of the context (real or
random) as the second independent variable, to perform regression analyses.
The significance of the offset and slope can be measured by interpreting the
$p$-values of the second independent variable, and the interaction between the
first and second independent variables, respectively. The $p$-value for the
offset is $1.7\times 10^{-2}$, confirming our qualitative observation that
there is a significant discourse coherence effect. The $p$-value for the
slope, however, is $3.6\times 10^{-1}$, suggesting that cognitive load
compresses the ratings in a consistent way for both h+ and h-, relative to h∅.

To conclude, our experiments reveal that context induces a cognitive load for
human processing, and this has the effect of compressing the acceptability
distribution. It moderates the extremes by making very unnatural sentences
appear more acceptable, and perfectly natural sentences slightly less
acceptable. If the context is relevant to the target sentence, then we also
have a discourse coherence effect, where sentences are perceived to be
generally more acceptable.

##  3 Modelling Acceptability

In this section, we explore computational models to predict human
acceptability ratings. We are interested in models that do not rely on
explicit supervision (i.e. we do not want to use the acceptability ratings as
labels in the training data). Our motivation here is to understand the extent
to which sentence probability, estimated by an unsupervised model, can provide
the basis for predicting sentence acceptability.

To this end, we train language models (Section 3.1) using unsupervised
objectives (e.g. next word prediction), and use these models to infer the
probabilities of our test sentences. To accommodate sentence length and
lexical frequency we experiment with several simple normalisation methods,
converting probabilities to acceptability measures (Section 3.2). The
acceptability measures are the final output of our models; they are what we
use to compare to human acceptability ratings.

###  3.1 Language Models

Our first model is an LSTM language model (lstm: Hochreiter and Schmidhuber
(1997); Mikolov et al. (2010)). Recurrent neural network models (RNNs) have
been shown to be competitive in this task Lau et al. (2015); Bernardy et al.
(2018), and they serve as our baseline.

Our second model is a joint topic and language model (tdlm: Lau et al.
(2017a)). tdlm combines topic model with language model in a single model,
drawing on the idea that the topical context of a sentence can help word
prediction in the language model. The topic model is fashioned as an auto-
encoder, where the input is the document’s word sequence and it is processed
by convolutional layers to produce a topic vector to predict the input words.
The language model functions like a standard LSTM model, but it incorporates
the topic vector (generated by its document context) into the current hidden
state to predict the next word.

We train lstm and tdlm on 100K uncased English Wikipedia articles containing
approximately 40M tokens with a vocabulary of 66K words.111111We use Stanford
CoreNLP Manning et al. (2014) to tokenise words and sentences. Rare words are
replaced by a special UNK symbol.

Next we explore transformer-based models, as they have become the benchmark
for many NLP tasks in recent years Vaswani et al. (2017); Devlin et al.
(2019); Yang et al. (2019). The transformer models that we use are trained on
a much larger corpus, and they are 4–5 times larger with respect to their
model parameters.

Our first transformer is gpt2 Radford et al. (2019). Given a target word, the
input is a sequence of previously seen words, which are then mapped to
embeddings (along with their positions) and fed to multiple layers of
“transformer blocks” before the target word is predicted. Much of its power
resides in these transformer blocks: each provides a multi-headed self-
attention unit over all input words, allowing it to capture multiple
dependencies between words, while avoiding the need for recurrence. With no
need to process a sentence in sequence, the model parallelises more
efficiently, and scales in a way that RNNs cannot.

gpt2 is trained on WebText, which consists of over 8 million web documents,
and uses Byte Pair Encoding (BPE: Sennrich et al. (2016)) for tokenisation
(casing preserved). BPE produces sub-word units, a middle ground between word
and character, and it provides better coverage for unseen words. We use the
released medium-sized model (“Medium”) for our
experiments.121212https://github.com/openai/gpt-2.

Our second transformer is bert Devlin et al. (2019). Unlike gpt2, bert is not
a typical language model, in the sense that it has access to both left and
right context words when predicting the target word.131313Note that context is
burdened with 2 senses in the paper. It can mean the preceding sentences of a
target sentence, or the neighbouring words of a target word. The intended
sense should be apparent from the usage. Hence, it encodes context in a
bidirectional manner.

To train bert, Devlin et al. (2019) propose a masked language model objective,
where a random proportion of input words are masked and the model is tasked to
predict them based on non-masked words. In addition to this objective, bert is
trained with a next sentence prediction objective, where the input is a pair
of sentences, and the model’s goal is to predict whether the latter sentence
follows the former. This objective is added to provide pre-training for
downstream tasks that involve understanding the relationship between a pair of
sentences, e.g. machine comprehension and textual entailment.

The bidirectionality of bert is the core feature that produces its state-of-
the-art performance on a number of tasks. The flipside of this encoding style,
however, is that bert lacks the ability to generate left-to-right and compute
sentence probability. We discuss how we use bert to produce a probability
estimate for sentences in the next section (Section 3.2).

In our experiments, we use the largest pre-trained model (“BERT-
Large”)141414https://github.com/google-research/bert., which has a similar
number of parameters (340M) to gpt2. It is trained on Wikipedia and BookCorpus
Zhu et al. (2015), where the latter is a collection of fiction books. Like
gpt2, bert also uses sub-word tokenisation (WordPiece). We experiment with two
variants of bert: one trained on cased data (bert${}_{\text{cs}}$), and
another on uncased data (bert${}_{\text{ucs}}$). As our test sentences are
uncased, a comparison between these two models allows us to gauge the impact
of casing in the training data.

Our last transformer model is xlnet Yang et al. (2019). xlnet is unique in
that it applies a novel permutation language model objective, allowing it to
capture bidirectional context while preserving key aspects of unidirectional
language models (e.g. left-to-right generation).

The permutation language model objective works by first generating a possible
permutation (also called “factorisation order”) of a sequence. When predicting
a target word in the sequence, the context words that the model has access to
are determined by the factorisation order. To illustrate this, imagine we have
the sequence $\mathbf{x}=[x_{1},x_{2},x_{3},x_{4}]$. One possible
factorisation order is: $x_{3}\rightarrow x_{2}\rightarrow x_{4}\rightarrow
x_{1}$. Given this order, if predicting target word $x_{4}$, the model only
has access to context words $\\{x_{3},x_{2}\\}$; if the target word is
$x_{2}$, it sees only $\\{x_{3}\\}$. In practice, the target word is set to be
the last few words in the factorisation order (e.g. $x_{4}$ and $x_{1}$), and
so the model always sees some context words for prediction.

Model Configuration Training Data Architecture Encoding #Param. Casing Size
Tokenisation Corpora lstm RNN Unidir. 60M Uncased 0.2GB Word Wikipedia tdlm
RNN Unidir. 80M Uncased 0.2GB Word Wikipedia gpt2 Transformer Unidir. 340M
Cased 40GB BPE WebText bert${}_{\text{cs}}$ Transformer Bidir. 340M Cased 13GB
WordPiece Wikipedia, BookCorpus bert${}_{\text{ucs}}$ Transformer Bidir. 340M
Uncased 13GB WordPiece Wikipedia, BookCorpus xlnet Transformer Hybrid 340M
Cased 126GB Sentence- Wikipedia, BookCorpus, Giga5 Piece ClueWeb, Common Crawl

Table 1: Language models and their configurations.

As xlnet is trained to work with different factorisation orders during
training, it has experienced both full/bidirectional context and
partial/unidirectional context, allowing it to adapt to tasks that have access
to full context (e.g. most language understanding tasks), as well as those
that do not (e.g. left-to-right generation).

Another innovation of xlnet is that it incorporates the segment recurrence
mechanism of Dai et al. (2019). This mechanism is inspired by truncated
backpropagation through time used for training RNNs, where the initial state
of a sequence is initialised with the final state from the previous sequence.
The segment recurrence mechanism works in a similar way, by caching the hidden
states of the transformer blocks from the previous sequence, and allowing the
current sequence to attend to them during training. This permits xlnet to
model long range dependencies beyond its maximum sequence length.

We use the largest pre-trained model (“XLNet-
Large”),151515https://github.com/zihangdai/xlnet. which has a similar number
of parameters to our bert and gpt2 models (340M). xlnet is trained on a much
larger corpus combining Wikipedia, BookCorpus, news and web articles. For
tokenisation, xlnet uses SentencePiece Kudo and Richardson (2018), another
sub-word tokenisation technique. Like gpt2, xlnet is trained on cased data.

Table 1 summarises the language models. In general, the RNN models are orders
of magnitude smaller than the transformers in both model parameters and
training data, although they are trained on the same domain (Wikipedia), and
use uncased data as the test sentences. The RNN models also operate on a word
level, while the transformers use sub-word units.

###  3.2 Probability and Acceptability Measure

Given a unidirectional language model, we can infer the probability of a
sentence by multiplying the estimated probabilities of each token using
previously seen (left) words as context Bengio et al. (2003):

$\overset{\text{\tiny$\rightarrow$}}{P}(s)=\prod_{i=0}^{|s|}P(w_{i}|w_{<i})$
(1)

where $s$ is the sentence, and $w_{i}$ a token in $s$.

lstm, tdlm, gpt2 are unidirectional models, and so they all compute sentence
probability as described. xlnet’s unique permutational language model
objective allows it to compute probability in the same way, and to explicitly
mark this we denote it as xlnet${}_{\text{uni}}$ when we infer sentence
probability using only left context words.

bert is trained with bidirectional context, and as such it is unable to
compute left-to-right sentence probability.161616Technically we can mask all
right context words and predict the target words one at a time, but because
the model is never trained in this way, we found that it performs poorly in
preliminary experiments. We therefore compute sentence probability as follows:

$\overset{\text{\tiny$\leftrightarrow$}}{P}(s)=\prod_{i=0}^{|s|}P(w_{i}|w_{<i},w_{>i})$
(2)

With this formulation, we allow bert to have access to both left and right
context words when predicting each target word, since this is consistent with
the way in which it was trained. It is important to note, however, that
sentence probability computed this way is not a true probability value: these
probabilities do not sum to 1.0 over all sentences. Equation (1), in contrast,
does guarantee true probabilities. Intuitively, the sentence probability
computed with this bidirectional formulation is a measure of the model’s
confidence in the likelihood of the sentence.

To compute the true probability, Wang and Cho (2019) show that we need to sum
the pre-softmax weights for each token to score a sentence, and then divide
the score by the total score of all sentences. As it is impractical to compute
the total score of all sentences (an infinite set), the true sentence
probabilities for these bidirectional models are intractable. We use our non-
normalised confidence scores as stand-ins for these probabilities.

For xlnet, we also compute sentence probability this way, applying
bidirectional context, and we denote it as xlnet${}_{\text{bi}}$. Note that
xlnet${}_{\text{uni}}$ and xlnet${}_{\text{bi}}$ are based on the same trained
model. They differ only in how they estimate sentence probability at test
time.

Acc. Measure | Equation
---|---
LP | $\log P(s)$
MeanLP | $\dfrac{\log P(s)}{|s|}$
PenLP | $\dfrac{\log P(s)}{((5+|s|)/(5+1))^{\alpha}}$
NormLP | $-\dfrac{\log P(s)}{\log P_{\text{u}}(s)}$
SLOR | $\dfrac{\log P(s)-\log P_{\text{u}}(s)}{|s|}$
Table 2: Acceptability measures for predicting the acceptability of a
sentence; $P(s)$ is the sentence probability, computed using Equation (1) or
Equation (2) depending on the model; $P_{\text{u}}(s)$ is the sentence
probability estimated by a unigram language model; and $\alpha=$ 0.8.

Sentence probability (estimated either using unidirectional or bidirectional
context) is affected by its length (e.g. longer sentences have lower
probabilities), and word frequency (e.g. the cat is big vs. the yak is big).
To modulate for these factors we introduce simple normalisation techniques.
Table 2 presents 5 methods to map sentence probabilities to acceptability
measures: LP, MeanLP, PenLP, NormLP and SLOR.

LP is the unnormalised log probability. Both MeanLP and PenLP are normalised
on sentence length, but PenLP scales length with an exponent ($\alpha$) to
dampen the impact of large values Wu et al. (2016); Vaswani et al. (2017). We
set $\alpha=0.8$ in our experiments. NormLP normalises using unigram sentence
probability (i.e. $P_{\text{u}}(s)=\prod_{i=0}^{|s|}P(w_{i})$), while SLOR
utilises both length and unigram probability Pauls and Klein (2012).

When computing sentence probability we have the option of including the
context paragraph that the human annotators see (Section 2). We use the
superscripts $\varnothing$, $+$, $-$ to denote a model using no context, real
context, and random context respectively (e.g. lstm∅, lstm+, and lstm-). Note
that these variants are created at test time, and are all based on the same
trained model (e.g. lstm).

For all models except tdlm, incorporating the context paragraph is trivial. We
simply prepend it to the target sentence before computing the latter’s
probability. For tdlm+ or tdlm-, the context paragraph is treated as the
document context, from which a topic vector is inferred and fed to the
language model for next-word prediction. For tdlm∅, we set the topic vector to
zeros.

###  3.3 Implementation

For the transformer models (gpt2, bert and xlnet), we use the implementation
of pytorch-transformers.171717https://github.com/huggingface/pytorch-
transformers. Specifically, we employ the following pre-trained models:
gpt2-medium for gpt2, bert-large-cased for bert${}_{\text{cs}}$, bert-large-
uncased for bert${}_{\text{ucs}}$, and xlnet-large-cased for
xlnet${}_{\text{uni}}$/xlnet${}_{\text{bi}}$.

xlnet requires a long dummy context prepended to the target sentence for it to
compute the sentence probability properly.181818In the scenario where we
include the context paragraph (e.g. xlnet${}_{\text{uni}}^{+}$), the dummy
context is added before it. Other researchers have found a similar problem
when using xlnet for generation.191919https://medium.com/@amanrusia/xlnet-
speaks-comparison-to-gpt-2-ea1a4e9ba39e. We think that this is likely due to
xlnet’s recurrence mechanism (Section 3.1), where it has access to context
from the previous sequence during training.

For tdlm, we use the implementation provided by Lau et al.
(2017a),202020https://github.com/jhlau/topically-driven-language-model.
following their optimal hyper-parameter configuration without tuning.

We implement lstm based on Tensorflow’s Penn Treebank language
model.212121https://github.com/tensorflow/models/blob/master/tutorials/rnn/ptb/ptb_word_lm.py.
In terms of hyper-parameters, we follow the configuration of tdlm where
applicable. tdlm uses Adam as the optimiser Kingma and Ba (2014), but for lstm
we use Adagrad Duchi et al. (2011), as it produces better development
perplexity.

For NormLP and SLOR, we need to compute $P_{\text{u}}(s)$, the sentence
probability based on a unigram language model. As the language models are
trained on different corpora, we collect unigram counts based on their
original training corpus. That is, for lstm and tdlm, we use the 100K English
Wikipedia corpus. For gpt2, we use an open source implementation that
reproduces the original WebText
data.222222https://skylion007.github.io/OpenWebTextCorpus/. For bert we use
the full Wikipedia collection and crawl smashwords.com to reproduce
BookCorpus.232323We use the scripts in https://github.com/soskek/bookcorpus to
reproduce BookCorpus. Finally, for xlnet we use the combined set of Wikipedia,
WebText and BookCorpus.242424xlnet also uses Giga5 and ClueWeb as part of its
training data, but we think that our combined collection is sufficiently large
to be representative of the original training data.

Source code for our experiments is publicly available at:
https://github.com/jhlau/acceptability-prediction-in-context.

Rtg Encod. Model LP MeanLP PenLP NormLP SLOR h∅ Unidir. lstm∅ 0.29 0.42 0.42
0.52 0.53 lstm+ 0.30 0.49 0.45 0.61 0.63 3-8 tdlm∅ 0.30 0.49 0.45 0.60 0.61
tdlm+ 0.30 0.50 0.45 0.59 0.60 3-8 gpt2∅ 0.33 0.34 0.56 0.38 0.38 gpt2+ 0.38
0.59 0.58 0.63 0.60 3-8 xlnet${}_{\text{uni}}^{\varnothing}$ 0.31 0.42 0.51
0.51 0.52 xlnet${}_{\text{uni}}^{+}$ 0.36 0.56 0.55 0.61 0.61 Bidir.
bert${}_{\text{cs}}^{\varnothing}$ 0.51 0.54 0.63 0.55 0.53
bert${}_{\text{cs}}^{+}$ 0.53 0.63 0.67 0.64 0.60 3-8
bert${}_{\text{ucs}}^{\varnothing}$ 0.59 0.63 0.70 0.63 0.60
bert${}_{\text{ucs}}^{+}$ 0.60 0.68 0.72 0.67 0.63 3-8
xlnet${}_{\text{bi}}^{\varnothing}$ 0.52 0.51 0.66 0.53 0.53
xlnet${}_{\text{bi}}^{+}$ 0.57 0.65 0.73 0.66 0.65 — ub1/
ub${{}_{1}^{\varnothing}}$ 0.75 / 0.66 ub2/ ub${{}_{2}^{\varnothing}}$ 0.92 /
0.88 h+ Unidir. lstm∅ 0.29 0.44 0.43 0.52 0.52 lstm+ 0.31 0.51 0.46 0.62 0.62
3-8 tdlm∅ 0.30 0.50 0.45 0.59 0.59 tdlm+ 0.30 0.50 0.46 0.58 0.58 3-8 gpt2∅
0.32 0.33 0.56 0.36 0.37 gpt2+ 0.38 0.60 0.59 0.63 0.60 3-8
xlnet${}_{\text{uni}}^{\varnothing}$ 0.30 0.42 0.50 0.49 0.51
xlnet${}_{\text{uni}}^{+}$ 0.35 0.56 0.55 0.60 0.61 Bidir.
bert${}_{\text{cs}}^{\varnothing}$ 0.49 0.53 0.62 0.54 0.51
bert${}_{\text{cs}}^{+}$ 0.52 0.63 0.66 0.63 0.58 3-8
bert${}_{\text{ucs}}^{\varnothing}$ 0.58 0.63 0.70 0.63 0.60
bert${}_{\text{ucs}}^{+}$ 0.60 0.68 0.73 0.67 0.63 3-8
xlnet${}_{\text{bi}}^{\varnothing}$ 0.51 0.50 0.65 0.52 0.53
xlnet${}_{\text{bi}}^{+}$ 0.57 0.65 0.74 0.65 0.65 — ub1/
ub${{}_{1}^{\varnothing}}$ 0.73 / 0.66 ub2/ ub${{}_{2}^{\varnothing}}$ 0.92 /
0.89 h- Unidir. lstm∅ 0.28 0.44 0.43 0.50 0.50 lstm- 0.27 0.41 0.40 0.47 0.47
3-8 tdlm∅ 0.29 0.52 0.46 0.59 0.58 tdlm- 0.28 0.49 0.44 0.56 0.55 3-8 gpt2∅
0.32 0.34 0.55 0.35 0.35 gpt2- 0.30 0.42 0.51 0.44 0.41 3-8
xlnet${}_{\text{uni}}^{\varnothing}$ 0.30 0.44 0.51 0.49 0.49
xlnet${}_{\text{uni}}^{-}$ 0.29 0.40 0.49 0.46 0.46 Bidir.
bert${}_{\text{cs}}^{\varnothing}$ 0.48 0.53 0.62 0.53 0.49
bert${}_{\text{cs}}^{-}$ 0.49 0.52 0.61 0.51 0.47 3-8
bert${}_{\text{ucs}}^{\varnothing}$ 0.56 0.61 0.68 0.60 0.56
bert${}_{\text{ucs}}^{-}$ 0.56 0.58 0.66 0.57 0.53 3-8
xlnet${}_{\text{bi}}^{\varnothing}$ 0.49 0.48 0.62 0.49 0.48
xlnet${}_{\text{bi}}^{-}$ 0.50 0.51 0.64 0.51 0.50 — ub1/
ub${{}_{1}^{\varnothing}}$ 0.75 / 0.68 ub2/ ub${{}_{2}^{\varnothing}}$ 0.92 /
0.88

Table 3: Modelling results. Boldface indicates optimal performance in each
row.

###  3.4 Results and Discussion

We use Pearson’s $r$ to assess how well the models’ acceptability measures
predict mean human acceptability ratings, following previous studies Lau et
al. (2017b); Bernardy et al. (2018). Recall that for each model (e.g. lstm),
there are 3 variants with which we infer the sentence probability at test
time. These are distinguished by whether we include no context (lstm∅), real
context (lstm+), or random context (lstm-). There are also three types of
human acceptability ratings (ground truth), where sentences are judged with no
context, (h∅), real context (h+), and random context (h-). We present the full
results in Table 3.

To get a sense of what the correlation figures indicate for these models, we
compute two human performance estimates to serve as upper bounds on the
accuracy of a model. The first upper bound (ub1) is the one-vs-rest annotator
correlation, where we select a random annotator’s rating and compare it to the
mean rating of the rest, using Pearson’s $r$. We repeat this for a large
number of trials (1000) to get a robust estimate of the mean correlation. ub1
can be interpreted as the average human performance working in isolation. The
second upper bound (ub2) is the half-vs-half annotator correlation. For each
sentence we randomly split the annotators into two groups, and compare the
mean rating between groups, again using Pearson’s $r$ and repeating it (1000)
to get a robust estimate. ub2 can be taken as the average human performance
working collaboratively. Overall, the simulated human performance is fairly
consistent over context types (Table 3), e.g. ub1 $=$ 0.75, 0.73, and 0.75 for
h∅, h+, and h-, respectively.

When we postprocess the user ratings, remember that we remove the outlier
ratings ($\geq$ 2 standard deviation) for each sentence (Section 2.1). While
this produces a cleaner set of annotations, this filtering step does
(artificially) increase the human agreement or upper bound correlations. For
completeness we also present upper bound variations where we do not remove the
outlier ratings, and denote them as ub${{}_{1}^{\varnothing}}$ and
ub${{}_{2}^{\varnothing}}$. In this setup, the one-vs-rest correlations drop
to 0.62–0.66 (Table 3). Note that all model performances are reported based on
the outlier-filtered ratings, although there are almost no perceivable changes
to the performance figures when they are evaluated on the outlier-preserved
ground truth.

Looking at Table 3, the models’ performances are fairly consistent over
different types of ground truths (h∅, h+, and h-). This is perhaps not very
surprising, as the correlations among the human ratings for these context
types are very high (Section 2).

We now focus on the results with h∅ as ground truth (“Rtg” $=$ h∅). SLOR is
generally the best acceptability measure for unidirectional models, with
NormLP not far behind (the only exception is gpt2∅). The recurrent models
(lstm and tdlm) are very strong compared to the much larger transformer models
(gpt2 and xlnet${}_{\text{uni}}$). In fact tdlm has the best performance when
context is not considered (tdlm∅, SLOR $=$ 0.61), suggesting that model
architecture maybe more important than number of parameters and amount of
training data.

For bidirectional models, the unnormalised LP works very well. The clear
winner here, however, is PenLP. It substantially and consistently outperforms
all other acceptability measures. The strong performance of PenLP that we see
here illuminates its popularity in machine translation for beam search
decoding Vaswani et al. (2017). With the exception of PenLP, the gain from
normalisation for the bidirectional models is small, but we don’t think this
can be attributed to the size of models or training corpora, as the large
unidirectional models (gpt2 and xlnet${}_{\text{uni}}$) still benefit from
normalisation. The best model without considering context is
bert${}_{\text{ucs}}^{\varnothing}$ with a correlation of 0.70 (PenLP), which
is very close to the idealised single-annotator performance ub1 (0.75) and
surpasses the unfiltered performance ub${{}_{1}^{\varnothing}}$ (0.66),
creating a new state-of-the-art for unsupervised acceptability prediction Lau
et al. (2015, 2017b); Bernardy et al. (2018). There is still room to improve,
however, relative to the collaborative ub2 (0.92) or
ub${{}_{2}^{\varnothing}}$ (0.88) upper bounds.

We next look at the impact of incorporating context at test time for the
models (e.g. lstm∅ vs. lstm+ or bert${}_{\text{ucs}}^{\varnothing}$ vs.
bert${}_{\text{ucs}}^{+}$). To ease interpretability we will focus on SLOR for
unidirectional models, and PenLP for bidirectional models. Generally, we see
that incorporating context always improves correlation, for both cases where
we use h∅ and h+ as ground truths, suggesting that context is beneficial when
it comes to sentence modelling. The only exception is tdlm, where tdlm∅ and
tdlm+ perform very similarly. Note, however, that context is only beneficial
when it is relevant. Incorporating random contexts (e.g. lstm∅ vs. lstm- or
bert${}_{\text{ucs}}^{\varnothing}$ vs. bert${}_{\text{ucs}}^{-}$ with h- as
ground truth) reduces the performance for all models.252525There is one
exception: xlnet${}_{\text{bi}}^{\varnothing}$ (0.62) vs.
xlnet${}_{\text{bi}}^{-}$ (0.64). As we saw previously in Section 3.3, xlnet
requires a long dummy context to work, and so this observation is perhaps
unsurprising, because it appears that context — whether it is relevant or not
— seems to always benefit xlnet.

Recall that our test sentences are uncased (an artefact of Moses, the machine
translation system that we use). While the recurrent models are all trained on
uncased data, most of the transformer models are trained with cased data. bert
is the only transformer that is pre-trained on both cased
(bert${}_{\text{cs}}$) and uncased data (bert${}_{\text{ucs}}$). To understand
the impact of casing, we look at the performance of bert${}_{\text{cs}}$ and
bert${}_{\text{ucs}}$ with h∅ as ground truth. We see an improvement of 5–7
points (depending on whether context is incorporated), which suggests that
casing has a significant impact on performance. Given that
xlnet${}_{\text{bi}}^{+}$ already outperforms bert${}_{\text{ucs}}^{+}$ (0.73
vs. 0.72), even though xlnet${}_{\text{bi}}^{+}$ is trained with cased data,
we conjecture that an uncased xlnet is likely to outperform
bert${}_{\text{ucs}}^{\varnothing}$ when context is not considered.

To summarise, our first important result is the exceptional performance of
bidirectional models. It raises the question of whether left-to-right bias is
an appropriate assumption for predicting sentence acceptability. One could
argue that this result may be due to our experimental setup. Users are
presented with the sentence in text, and they have the opportunity to read it
multiple times, thereby creating an environment that may simulate
bidirectional context. We could test this conjecture by changing the
presentation of the sentence, displaying it one word at a time (with older
words fading off), or playing an audio version (e.g. via a text-to-speech
system). However, these changes will likely introduce other confounds (e.g.
prosody), but we believe it is an interesting avenue for future work.

Our second result is more tentative. Our experiments seem to indicate that
model architecture is more important than training or model size. We see that
tdlm, which is trained on data orders of magnitude smaller and has model
parameters 4 times smaller in size (Table 1), outperforms the large
unidirectional transformer models. To establish this conclusion more firmly we
will need to rule out the possibility that the relatively good performance of
lstm and tdlm is not due to a cleaner (e.g. lowercased) or more relevant (e.g.
Wikipedia) training corpus. With that said, we contend that our findings
motivate the construction of better language models, instead of increasing the
number of parameters, or the amount of training data. It would be interesting
to examine the effect of extending tdlm with a bidirectional objective.

Our final result is that our best model, bert${}_{\text{ucs}}$, attains a
human-level performance and achieves a new state-of-the-art performance in the
task of unsupervised acceptability prediction. Given this level of accuracy,
we expect it would be suitable for tasks like assessing student essays and the
quality of machine translations.

##  4 Linguists’ Examples

One may argue that our dataset is potentially biased, as round-trip machine
translation may introduce particular types of infelicities or unusual features
to the sentences Graham et al. (2019). Lau et al. (2017b) addressed this by
creating a dataset where they sample 50 grammatical and 50 ungrammatical
sentences from Adger (2003)’s syntax textbook, and run a crowdsourced
experiment to collect their user ratings. Lau et al. (2017b) found that their
unsupervised language models (e.g. simple recurrent networks) predict the
acceptability of these sentences with similar performances, providing evidence
that their modelling results are robust.

We test our pre-trained models using this linguist-constructed dataset, and
found similar observations: gpt2, bert${}_{\text{cs}}$ and
xlnet${}_{\text{bi}}$ produce a PenLP correlation of 0.45, 0.53, and 0.58
respectively. These results indicate that these language models are able to
predict the acceptability of these sentences reliably, consistent with our
modelling results with round-trip translated sentences (Section 3.4). While
the correlations are generally lower, we want to highlight that these
linguists’ examples are artificially constructed to illustrate specific
syntactic phenomena, and so this constitutes a particularly strong case of
out-of-domain prediction. These texts are substantially different in nature
from the natural text that the pre-trained language models are trained on
(e.g. the linguists’ examples are much shorter — less than 7 words on average
— than the natural texts).

##  5 Related Work

Acceptability is closely related to the concept of grammaticality. The latter
is a theoretical construction corresponding to syntactic well-formedness, and
it is typically interpreted as a binary property (i.e. a sentence is either
grammatical or ungrammatical). Acceptability, on the other hand, includes
syntactic, semantic, pragmatic, and non-linguistic factors, such as sentence
length. It is gradient, rather than binary, in nature Denison (2004); Sorace
and Keller (2005); Sprouse (2007).

Linguists and other theorists of language have traditionally assumed that
context affects our perception of both grammaticality Bolinger (1968) and
acceptability Bever (1970), but surprisingly little work investigates this
effect systematically, or on a large scale. Most formal linguists rely heavily
on the analysis of sentences taken in isolation. However many linguistic
frameworks seek to incorporate aspects of context-dependence. Dynamic theories
of semantics (Heim, 1982; Kamp and Reyle, 1993; Groenendijk and Stokhof, 1990)
attempt to capture intersentential coreference, binding, and scope phenomena.
Dynamic Syntax (Cann et al., 2007) uses incremental tree construction and
semantic type projection to render parsing and interpretation discourse
dependent. Theories of discourse structure characterise sentence coherence in
context through rhetorical relations Mann and Thompson (1988); Asher and
Lascarides (2003), or by identifying open questions and common ground Ginzburg
(2012). While these studies offer valuable insights into a variety of context
related linguistic phenomena, much of it takes grammaticality and
acceptability to be binary properties. Moreover, it is not formulated in a way
that permits fine-grained psychological experiments, or wide coverage
computational modelling.

Psycholinguistic work can provide more experimentally grounded approaches.
Greenbaum (1976) found that combinations of particular syntactic constructions
in context affect human judgments of acceptability, although the small scale
of the experiments make it difficult to draw general conclusions. More recent
work investigates related effects, but it tends to focus on very restricted
aspects of the phenomenon. For example, Zlogar and Davidson (2018) investigate
the influence of context on the acceptability of gestures with speech,
focussing on interaction with semantic content and presupposition. The
_priming_ literature shows that exposure to lexical and syntactic items leads
to higher likelihood of their repetition in production Reitter et al. (2011),
and to quicker processing in parsing under certain circumstances Giavazzi et
al. (2018). Frameworks such as ACT-R Anderson (1996) explain these effects
through the impact of cognitive activation on subsequent processing. Most of
these studies suggest that coherent or natural contexts should increase
acceptability ratings, given that the linguistic expressions used in
processing become more activated. Warner and Glass (1987) show that such
syntactic contexts can indeed affect grammaticality judgments in the expected
way for _garden path_ sentences. Cowart (1994) uses comparison between
positive and negative contexts, investigating the effect of contexts
containing alternative more or less acceptable sentences. But he restricts the
test cases to specific pronoun binding phenomena. None of the psycholinguistic
work investigates acceptability judgments in real textual contexts, over large
numbers of test cases and human subjects.

Some recent computational work explores the relation of acceptability
judgments to sentence probabilities. Lau et al. (2015, 2017b) show that the
output of unsupervised language models can correlate with human acceptability
ratings. Warstadt et al. (2018) treat this as a semi-supervised problem,
training a binary classifier on top of a pre-trained sentence encoder to
predict acceptability ratings with greater accuracy. Bernardy et al. (2018)
explore incorporating context into such models, eliciting human judgments of
sentence acceptability when the sentences were presented both in isolation and
within a document context. They find a compression effect in the distribution
of the human acceptability ratings. Bizzoni and Lappin (2019) observe a
similar effect in a paraphrase acceptability task.

One possible explanation for this compression effect is to take it as the
expression of cognitive load. Psychological research on the cognitive load
effect (Sweller, 1988; Ito et al., 2018; Causse et al., 2016; Park et al.,
2013) indicates that performing a secondary task can degrade or distort
subjects’ performance on a primary task. This could cause judgments to regress
towards the mean. However, the experiments of Bernardy et al. (2018) and
Bizzoni and Lappin (2019) do not allow us to distinguish this possibility from
a coherence or priming effect, as only coherent contexts were considered. Our
experimental setup improves on this by introducing a topic identification task
and incoherent (random) contexts in order to tease the effects apart.

##  6 Conclusions and Future Work

We found that processing context induces a cognitive load for humans, which
creates a compression effect on the distribution of acceptability ratings. We
also showed that if the context is relevant to the sentence, a discourse
coherence effect uniformly boosts sentence acceptability. Our language model
experiments indicate that bidirectional models achieve better results than
unidirectional models. The best bidirectional model performs at a human level,
defining a new state-of-the art for this task.

In future work we will explore alternative ways to present sentences for
acceptability judgments. We plan to extend tdlm, incorporating a bidirectional
objective, as it shows significant promise. It will also be interesting to see
if our observations generalise to other languages, and to different sorts of
contexts, both linguistic and non-linguistic.

## Acknowledgements

We are grateful to three anonymous reviewers for helpful comments on earlier
drafts of this paper. Some of the work described here was presented in talks
in the seminar of the Centre for Linguistic Theory and Studies in Probability
(CLASP), University of Gothenburg, December 2019, and in the Cambridge
University Language Technology Seminar, February 2020\. We thank the
participants of both events for useful discussion.

Shalom Lappin’s work on the project was supported by grant 2014-39 from the
Swedish Research Council, which funds CLASP. Santos Armendariz and Purver were
partially supported by the European Union’s Horizon 2020 research and
innovation programme under grant agreement No 825153, project EMBEDDIA (Cross-
Lingual Embeddings for Less-Represented Languages in European News Media). The
results of this publication reflect only the authors’ views and the Commission
is not responsible for any use that may be made of the information it
contains.

## References

  * Adger (2003) David Adger. 2003.  _Core syntax: A minimalist approach_.  Oxford University Press, United Kingdom.
  * Anderson (1996) John R. Anderson. 1996.  ACT: A simple theory of complex cognition.  _American Psychologist_ , 51:355–365.
  * Asher and Lascarides (2003) Nicholas Asher and Alex Lascarides. 2003.  _Logics of Conversation_.  Cambridge University Press.
  * Bengio et al. (2003) Yoshua Bengio, Réjean Ducharme, Pascal Vincent, and Christian Janvin. 2003.  A neural probabilistic language model.  _The Journal of Machine Learning Research_ , 3:1137–1155.
  * Bernardy et al. (2018) Jean-Philippe Bernardy, Shalom Lappin, and Jey Han Lau. 2018.  The influence of context on sentence acceptability judgements.  In _Proceedings of the 56th Annual Meeting of the Association for Computational Linguistics (ACL 2018)_ , pages 456–461, Melbourne, Australia.
  * Bever (1970) Thomas G. Bever. 1970.  The cognitive basis for linguistic structures.  In J. R. Hayes, editor, _Cognition and the Development of Language_ , pages 279–362. Wiley, New York.
  * Bizzoni and Lappin (2019) Yuri Bizzoni and Shalom Lappin. 2019.  The effect of context on metaphor paraphrase aptness judgments.  In _Proceedings of the 13th International Conference on Computational Semantics - Long Papers_ , pages 165–175, Gothenburg, Sweden.
  * Bolinger (1968) Dwight Bolinger. 1968.  Judgments of grammaticality.  _Lingua_ , 21:34–40.
  * Cann et al. (2007) Ronnie Cann, Ruth Kempson, and Matthew Purver. 2007.  Context and well-formedness: the dynamics of ellipsis.  _Research on Language and Computation_ , 5(3):333–358.
  * Causse et al. (2016) Mickaël Causse, Vsevolod Peysakhovich, and Eve F. Fabre. 2016.  High working memory load impairs language processing during a simulated piloting task: An erp and pupillometry study.  _Frontiers in Human Neuroscience_ , 10:240.
  * Cowart (1994) Wayne Cowart. 1994.  Anchoring and grammar effects in judgments of sentence acceptability.  _Perceptual and Motor Skills_ , 79(3):1171–1182.
  * Dai et al. (2019) Zihang Dai, Zhilin Yang, Yiming Yang, Jaime G. Carbonell, Quoc V. Le, and Ruslan Salakhutdinov. 2019.  Transformer-xl: Attentive language models beyond a fixed-length context.  _CoRR_ , abs/1901.02860.
  * Denison (2004) David Denison. 2004.  _Fuzzy Grammar: A Reader_.  Oxford University Press, United Kingdom.
  * Devlin et al. (2019) Jacob Devlin, Ming-Wei Chang, Kenton Lee, and Kristina Toutanova. 2019.  BERT: Pre-training of deep bidirectional transformers for language understanding.  In _Proceedings of the 2019 Conference of the North American Chapter of the Association for Computational Linguistics: Human Language Technologies, Volume 1 (Long and Short Papers)_ , pages 4171–4186, Minneapolis, Minnesota.
  * Duchi et al. (2011) John Duchi, Elad Hazan, and Yoram Singer. 2011.  Adaptive subgradient methods for online learning and stochastic optimization.  _Journal of Machine Learning Research_ , 12:2121–2159.
  * Giavazzi et al. (2018) Maria Giavazzi, Sara Sambin, Ruth de Diego-Balaguer, Lorna Le Stanc, Anne-Catherine Bachoud-Lévi, and Charlotte Jacquemot. 2018.  Structural priming in sentence comprehension: A single prime is enough.  _PLoS ONE_ , 13(4):e0194959.
  * Ginzburg (2012) Jonathan Ginzburg. 2012.  _The Interactive Stance: Meaning for Conversation_.  Oxford University Press.
  * Graham et al. (2019) Yvette Graham, Barry Haddow, and Philipp Koehn. 2019.  Translationese in machine translation evaluation.  _CoRR_ , abs/1906.09833.
  * Greenbaum (1976) Sidney Greenbaum. 1976.  Contextual influence on acceptability judgements.  _Linguistics_ , 15(187):5–12.
  * Groenendijk and Stokhof (1990) Jeroen Groenendijk and Martin Stokhof. 1990.  Dynamic montague grammar.  In _Proceedings of the 2nd Symposium on Logic and Language_ , pages 3–48, Budapest.
  * Heim (1982) Irene Heim. 1982.  _The Semantics of Definite and Indefinite Noun Phrases_.  Ph.D. thesis, University of Massachusetts at Amherst.
  * Hill et al. (2015) Felix Hill, Roi Reichart, and Anna Korhonen. 2015.  SimLex-999: Evaluating semantic models with (genuine) similarity estimation.  _Computational Linguistics_ , 41:665–695.
  * Hochreiter and Schmidhuber (1997) Sepp Hochreiter and Jürgen Schmidhuber. 1997.  Long short-term memory.  _Neural Computation_ , 9:1735–1780.
  * Ito et al. (2018) Aine Ito, Martin Corley, and Martin J. Pickering. 2018.  A cognitive load delays predictive eye movements similarly during l1 and l2 comprehension.  _Bilingualism: Language and Cognition_ , 21(2):251–264.
  * Kamp and Reyle (1993) Hans Kamp and Uwe Reyle. 1993.  _From Discourse To Logic_.  Kluwer Academic Publishers.
  * Khandelwal et al. (2018) Urvashi Khandelwal, He He, Peng Qi, and Dan Jurafsky. 2018.  Sharp nearby, fuzzy far away: How neural language models use context.  In _Proceedings of the 56th Annual Meeting of the Association for Computational Linguistics (Volume 1: Long Papers)_ , pages 284–294, Melbourne, Australia. Association for Computational Linguistics.
  * Kingma and Ba (2014) Diederik P. Kingma and Jimmy Ba. 2014.  Adam: A method for stochastic optimization.  _CoRR_ , abs/1412.6980.
  * Kudo and Richardson (2018) Taku Kudo and John Richardson. 2018.  SentencePiece: A simple and language independent subword tokenizer and detokenizer for neural text processing.  In _Proceedings of the 2018 Conference on Empirical Methods in Natural Language Processing: System Demonstrations_ , pages 66–71, Brussels, Belgium.
  * Lau et al. (2017a) Jey Han Lau, Timothy Baldwin, and Trevor Cohn. 2017a.  Topically driven neural language model.  In _Proceedings of the 55th Annual Meeting of the Association for Computational Linguistics (Volume 1: Long Papers)_ , pages 355–365, Vancouver, Canada.
  * Lau et al. (2015) Jey Han Lau, Alexander Clark, and Shalom Lappin. 2015.  Unsupervised prediction of acceptability judgements.  In _Proceedings of the Joint conference of the 53rd Annual Meeting of the Association for Computational Linguistics and the 7th International Joint Conference on Natural Language Processing of the Asian Federation of Natural Language Processing (ACL-IJCNLP 2015)_ , pages 1618–1628, Beijing, China.
  * Lau et al. (2017b) Jey Han Lau, Alexander Clark, and Shalom Lappin. 2017b.  Grammaticality, Acceptability, and Probability: A Probabilistic View of Linguistic Knowledge.  _Cognitive Science_ , 41:1202–1241.
  * Mann and Thompson (1988) William Mann and Sandra Thompson. 1988.  Rhetorical structure theory: Toward a functional theory of text organization.  _Text_ , 8(3):243–281.
  * Manning et al. (2014) Christopher D. Manning, Mihai Surdeanu, John Bauer, Jenny Finkel, Steven J. Bethard, and David McClosky. 2014.  The Stanford CoreNLP natural language processing toolkit.  In _Association for Computational Linguistics (ACL) System Demonstrations_ , pages 55–60.
  * McCallum (2002) Andrew Kachites McCallum. 2002.  Mallet: A machine learning for language toolkit.  Http://mallet.cs.umass.edu.
  * Mikolov et al. (2010) Tomas Mikolov, Martin Karafiát, Lukas Burget, Jan Cernockỳ, and Sanjeev Khudanpur. 2010.  Recurrent neural network based language model.  pages 1045–1048, Makuhari, Japan.
  * Park et al. (2013) Hyangsook Park, Jun-Su Kang, Sungmook Choi, and Minho Lee. 2013.  Analysis of cognitive load for language processing based on brain activities.  In _Neural Information Processing_ , pages 561–568, Berlin, Heidelberg. Springer Berlin Heidelberg.
  * Pauls and Klein (2012) Adam Pauls and Dan Klein. 2012.  Large-scale syntactic language modeling with treelets.  In _Proceedings of the 50th Annual Meeting of the Association for Computational Linguistics (Volume 1: Long Papers)_ , pages 959–968, Jeju Island, Korea.
  * Radford et al. (2019) Alec Radford, Jeff Wu, Rewon Child, David Luan, Dario Amodei, and Ilya Sutskever. 2019.  Language models are unsupervised multitask learners.
  * Reitter et al. (2011) Daivd Reitter, Frank Keller, and Johanna D. Moore. 2011.  A computational cognitive model of syntactic priming.  _Cognitive Science_ , 35(4):587–637.
  * Sennrich et al. (2016) Rico Sennrich, Barry Haddow, and Alexandra Birch. 2016.  Neural machine translation of rare words with subword units.  In _Proceedings of the 54th Annual Meeting of the Association for Computational Linguistics (Volume 1: Long Papers)_ , pages 1715–1725, Berlin, Germany.
  * Sorace and Keller (2005) Antonella Sorace and Frank Keller. 2005.  Gradience in linguistic data.  _Lingua_ , 115:1497–1524.
  * Sprouse (2007) Jon Sprouse. 2007.  Continuous acceptability, categorical grammaticality, and experimental syntax.  _Biolinguistics_ , 1:123–134.
  * Sweller (1988) John Sweller. 1988.  Cognitive load during problem solving: Effects on learning.  _Cognitive Science_ , 12(2):257–285.
  * Vaswani et al. (2017) Ashish Vaswani, Noam Shazeer, Niki Parmar, Jakob Uszkoreit, Llion Jones, Aidan N Gomez, Łukasz Kaiser, and Illia Polosukhin. 2017.  Attention is all you need.  In _Advances in Neural Information Processing Systems 30_ , pages 5998–6008.
  * Wang and Cho (2019) Alex Wang and Kyunghyun Cho. 2019.  BERT has a mouth, and it must speak: BERT as a Markov random field language model.  In _Proceedings of the Workshop on Methods for Optimizing and Evaluating Neural Language Generation_ , pages 30–36, Minneapolis, Minnesota. Association for Computational Linguistics.
  * Warner and Glass (1987) John Warner and Arnold L Glass. 1987.  Context and distance-to-disambiguation effects in ambiguity resolution: Evidence from grammaticality judgments of garden path sentences.  _Journal of Memory and Language_ , 26(6):714 – 738.
  * Warstadt et al. (2018) Alex Warstadt, Amanpreet Singh, and Samuel R Bowman. 2018.  Neural network acceptability judgments.  _CoRR_ , abs/1805.12471.
  * Wu et al. (2016) Yonghui Wu, Mike Schuster, Zhifeng Chen, Quoc V. Le, Mohammad Norouzi, Wolfgang Macherey, Maxim Krikun, Yuan Cao, Qin Gao, Klaus Macherey, Jeff Klingner, Apurva Shah, Melvin Johnson, Xiaobing Liu, Lukasz Kaiser, Stephan Gouws, Yoshikiyo Kato, Taku Kudo, Hideto Kazawa, Keith Stevens, George Kurian, Nishant Patil, Wei Wang, Cliff Young, Jason Smith, Jason Riesa, Alex Rudnick, Oriol Vinyals, Greg Corrado, Macduff Hughes, and Jeffrey Dean. 2016.  Google’s neural machine translation system: Bridging the gap between human and machine translation.  _CoRR_ , abs/1609.08144.
  * Yang et al. (2019) Zhilin Yang, Zihang Dai, Yiming Yang, Jaime G. Carbonell, Ruslan Salakhutdinov, and Quoc V. Le. 2019.  XLNet: Generalized autoregressive pretraining for language understanding.  _CoRR_ , abs/1906.08237.
  * Zhu et al. (2015) Yukun Zhu, Ryan Kiros, Rich Zemel, Ruslan Salakhutdinov, Raquel Urtasun, Antonio Torralba, and Sanja Fidler. 2015.  Aligning books and movies: Towards story-like visual explanations by watching movies and reading books.  In _Proceedings of the 2015 IEEE International Conference on Computer Vision (ICCV)_ , pages 19–27, Washington, DC, USA.
  * Zlogar and Davidson (2018) Christina Zlogar and Kathryn Davidson. 2018.  Effects of linguistic context on the acceptability of co-speech gestures.  _Glossa_ , 3(1):73.


11institutetext: Institute of Informatics, University of Warsaw, Poland

# Improved Complexity Analysis of Quasi-Polynomial Algorithms Solving Parity
Games

Paweł Parys Author supported by the National Science Centre, Poland (grant no.
2021/41/B/ST6/03914). 0000-0001-7247-1408 Aleksander Wiącek

###### Abstract

We improve the complexity of solving parity games (with priorities in
vertices) for $d=\omega(\log n)$ by a factor of $\Theta(d^{2})$: the best
complexity known to date was
$\mathcal{O}(mdn^{1{.}45+\log_{2}(d/\log_{2}n)})$, while we obtain
$\mathcal{O}(mn^{1{.}45+\log_{2}(d/\log_{2}n)}/d)$, where $n$ is the number of
vertices, $m$ is the number of edges, and $d$ is the number of priorities.

We base our work on existing algorithms using universal trees, and we improve
their complexity. We present two independent improvements. First, an
improvement by a factor of $\Theta(d)$ comes from a more careful analysis of
the width of universal trees. Second, we perform (or rather recall) a finer
analysis of requirements for a universal tree: while for solving games with
priorities on edges one needs an $n$-universal tree, in the case of games with
priorities in vertices it is enough to use an $n/2$-universal tree. This way,
we allow solving games of size $2n$ in the time needed previously to solve
games of size $n$; such a change divides the quasi-polynomial complexity again
by a factor of $\Theta(d)$.

###### Keywords:

Parity games Universal trees Quasi-polynomial time

##  1 Introduction

Parity games have played a fundamental role in automata theory, logic, and
their applications to verification and synthesis since early 1990s. The
algorithmic problem of finding the winner in parity games can be seen as the
algorithmic back end to problems in the automated verification and controller
synthesis. It is polynomial-time equivalent to the emptiness problem for
nondeterministic automata on infinite trees with parity acceptance conditions,
and to the model-checking problem for modal $\mu$-calculus [14]. It lies also
at the heart of algorithmic solutions to the Church’s synthesis problem [29].
Moreover, decision problems for modal logics like validity or satisfiability
of formulae in these logics can be reduced to parity game solving. Some ideas
coming originally from parity games allowed obtaining new results concerning
translations between automata models for $\omega$-words [5, 10], as well as
concerning relatively far areas of computer science, like Markov decision
processes [15] and linear programming [19, 18].

The complexity of solving parity games, that is, deciding which player has a
winning strategy, is a long standing open question. The problem is known to be
in $\mathsf{UP}\cap\mathsf{coUP}$ [20] (a subclass of
$\mathsf{NP}\cap\mathsf{coNP}$) and the search variant (i.e., to find a
winning strategy) is in PLS, PPAD, and even in their subclass CLS [9]. The
study of algorithms for solving parity games has been dominated for over two
decades by algorithms whose run-time was exponential in the number of distinct
priorities [33, 6, 31, 21, 32, 30, 2], or mildly subexponential for a large
number of priorities [4, 25]. The breakthrough came in 2017 from Calude, Jain,
Khoussainov, Li, and Stephan [7] who gave the first quasi-polynomial-time
algorithm using the novel idea of _play summaries_. Several other quasi-
polynomial-time algorithms were developed soon after [22, 16, 26, 28, 27, 11,
24, 3].

Fijalkow [17] made explicit the concept of _universal trees_ that is implicit
in the _succinct tree coding_ result of Jurdziński and Lazić [22]. It was then
observed that universal trees are not only present, but actually necessary in
all existing quasi-polynomial-time approaches for solving parity games [8, 23,
1]. Namely, it was shown that any algorithm solving a parity game with $n$
vertices, and following existing approaches, needs to operate on an
$n$-universal tree (as defined in the sequel). There is, however, a catch
here: this necessity proof is for parity games with priorities on edges, while
quite often one considers less succinct games with priorities in vertices. (A
general method for switching from priorities on edges to priorities in
vertices is to replace each vertex by $d$ vertices, one for each priority, and
to redirect every edge to a copy of the target vertex having the appropriate
priority; then the number of vertices changes from $n$ to $nd$.)

The main contribution of this paper lies in a finer analysis of the width of
$n$-universal trees. We improve the upper bound on this width (and thus also
the upper bound on the running time of algorithms using such trees) by a
factor of $\Theta\left(\frac{d}{\log n}\right)$, where $d$ is the number of
priorities.

Then, a second improvement is obtained by recalling from Jurdziński and Lazić
[22] that in order to solve parity games with priorities in vertices it is
enough to use an $\lfloor n/2\rfloor$-universal tree instead of an
$n$-universal trees, exploiting the “catch” mentioned above. This allows
solving games of size $2n$ in the time needed previously to solve games of
size $n$ and, in consequence, improves the complexity of solving parity games
(with priorities in vertices) once again by a factor of
$\Theta\left(\frac{d}{\log n}\right)$.

Combining the two improvements, we decrease the upper bound on the complexity
of solving parity games with $d=\omega(\log n)$ by a factor of
$\Theta\left(\frac{d^{2}}{\log^{2}n}\right)$: the best bound known to date
[17, 22], namely $\mathcal{O}(mdn^{1{.}45+\log_{2}(d/\log_{2}n)})$, is
decreased to the bound $\mathcal{O}(mn^{1{.}45+\log_{2}(d/\log_{2}n)}/d)$. We
remark that both bounds do not display polylogarithmic factors; they are
dominated by $n^{\mathcal{O}(1)}$, where the $\mathcal{O}(1)$ comes from the
difference between $1{.}45$ and the actual constant $\log_{2}e$ which should
appear in the exponent (the same style of writing the bound is employed in
prior work). Thus, while writing the bounds in such a form, the improvement is
by a factor of $\Theta(d^{2})$. Simultaneously, the two observations become
too weak to improve asymptotics of the complexity in the case of
$d=\mathcal{O}(\log n)$.

##  2 Preliminaries

### Parity games.

A _parity game_ is a two-player game between players Even and Odd played on a
_game graph_ defined as a tuple $\mathcal{G}=(V,V_{\mathsf{Even}},E,d,\pi)$,
where $(V,E)$ is a nonempty finite directed graph in which every vertex has at
least one successor; its vertices are labelled with positive integer
_priorities_ by $\pi\colon V\rightarrow\\{1,2,\dots,d\\}$ (for some _even_
number $d\in\mathbb{N}$), and divided between vertices $V_{\mathsf{Even}}$
_belonging to Even_ and vertices $V_{\mathsf{Odd}}=V\setminus
V_{\mathsf{Even}}$ _belonging to Odd_. We usually denote $|V|$ by $n$ and
$|E|$ by $m$.

Intuitively, the dynamics of the game are defined as follows. The play starts
in a designated starting vertex. Then, the player to whom the current vertex
belongs selects a successor of this vertex, and the game continues there.
After an infinite time, we check for the maximal priority visited infinitely
often; its parity says which player wins.

Formally, we define the winner of a game using positional (i.e., memoryless)
strategies. An _Even’s positional strategy_ is a set $\sigma\subseteq E$ of
edges such that for every vertex $v$ of Even, in $\sigma$ there is exactly one
edge starting in $v$, and for every vertex $v$ of Odd, in $\sigma$ there are
all edges starting in $v$. An _Odd’s positional strategy_ is defined by
swapping the roles of Even and Odd. An Even’s (Odd’s) positional strategy
$\sigma$ is winning from a vertex $v$ if for every infinite path in the
subgraph $(V,\sigma)$, the maximal priority occurring infinitely often on this
path is even (odd, respectively). We say that Even/Odd _wins_ from $v$ if
Even/Odd has a positional strategy winning from $v$.

The above definition accurately describes the winning player due to
_positional determinacy_ of parity games: from every vertex $v$ of a parity
game, one of the players, Even or Odd, wins from $v$ [13]. It follows that if
a player can win from a vertex by a general strategy (not defined here), then
he can win also by a positional strategy.

### Trees and universal trees.

In progress measure algorithms [22, 17, 11] strategies are described by
mappings from game graphs to ordered trees, defined as follows: an _ordered
tree_ (or simply a _tree_) $T$ of height $h$ is a finite connected acyclic
graph, given together with a linear order $\leq_{x}$ for every node $x$
thereof, such that

  * •

there is exactly one node with in-degree $0$, called a _root_ ; every other
node has in-degree $1$;

  * •

for every _leaf_ (i.e., a node of out-degree $0$), the unique path from the
root to this leaf consists of $h$ edges;

  * •

$\leq_{x}$ is a linear order on the _children_ of $x$ (i.e., nodes to which
there is an edge from $x$), which describes the left-to-right ordering of
these children.

The _width_ of a tree $T$ is defined as its number of leaves and denoted
$|T|$.

Let $T_{1}$ and $T_{2}$ be two ordered trees of the same height. We say that
$T_{1}$ _embeds_ into $T_{2}$ if there is an injective mapping $f$ preserving
the child relation and the $\leq_{x}$ relations:

  * •

if $y$ is a child of $x$ in $T_{1}$, then $f(y)$ is a child of $f(x)$ in
$T_{2}$, and

  * •

if $y\leq_{x}z$ in $T_{1}$, then $f(y)\leq_{f(x)}f(z)$ in $T_{2}$.

Figure 1: All four trees of height 2 and width 3 (left); a 3-universal tree of
height 2 (right)

A tree $\mathcal{T}$ of height $h$ is _$n$ -universal_ if every ordered tree
of height $h$ and width at most $n$ embeds into $\mathcal{T}$. Consult Figure
1 for an example.

##  3 On the width of universal trees

In this section we prove an improved upper bound on the width of universal
trees, as described by the following theorem:

###### Theorem 3.1

For all $n,h\in\mathbb{N}$, where $n\geq 1$, there exists an $n$-universal
tree of height $h$ and width at most $f(n,h)$, where

$\displaystyle f(n,h)\leq
n\cdot\binom{h-1+\lfloor\log_{2}n\rfloor}{\lfloor\log_{2}n\rfloor}\leq
n^{2{.}45-\varepsilon+\log_{2}\left(1+\frac{h-1}{\log_{2}n}\right)}$

for some $\varepsilon>0$. Additionally,
$f(n,h)=\mathcal{O}(n^{2{.}45-\varepsilon+\log_{2}(h/\log_{2}n)})$ if
$h=\omega(\log n)$.

We remark that as the height $h$ we usually take (numbers close to) $d/2$,
where $d$ is the number of priorities in a parity game. The value
$2{.}45-\varepsilon$ in the exponent means that the actual constant is
slightly smaller than $2{.}45$.

Before giving a proof, let us compare the above bound with bounds known to
date: Fijalkow [17, Theorem 4] derives an upper bound of
$2^{\lceil\log_{2}n\rceil}\binom{h-1+\lceil\log_{2}n\rceil}{\lceil\log_{2}n\rceil}$.
The difference is thus in replacing $\lceil\log_{2}n\rceil$ by
$\lfloor\log_{2}n\rfloor$. For “a majority” of $n$ these two values differ by
$1$, in which case the quotient of the two binomial coefficients is
$\frac{h-1+\lceil\log_{2}n\rceil}{\lceil\log_{2}n\rceil}$; this quotient is in
$\Theta\left(\frac{h}{\log n}\right)$ if $h=\omega(\log n)$. Coming to the
asymptotics, the bound of Fijalkow is in
$\mathcal{O}(hn^{2{.}45-\varepsilon+\log_{2}(h/\log_{2}n)})$ (see Jurdziński
and Lazić [22, Lemma 6] for a proof), which is indeed worse by a factor of
$\Theta(h)$ than our bound.

In order to prove Theorem 3.1, we use a construction of Fijalkow [17, Theorem
4] (which is essentially the same construction as in Jurdziński and Lazić
[22]). He shows that there exists an $n$-universal tree of height $h$ and
width $f(n,h)$, where the function $f$ (extended to $n=0$ by setting
$f(0,h)=0$, and to $h=0$, $n\geq 1$ by setting $f(n,0)=1$) is defined by the
following recursive formula:

$\displaystyle f(0,h)$ $\displaystyle=0$ $\displaystyle\text{for }h\geq 0,$
$\displaystyle f(n,0)$ $\displaystyle=1$ $\displaystyle\text{for }n\geq 1,$
$\displaystyle f(n,h)$ $\displaystyle=f(n,h-1)+f(\lfloor
n/2\rfloor,h)+f(n-1-\lfloor n/2\rfloor,h)$ $\displaystyle\text{for }n,h\geq
1.$ (1)

Compared to Fijalkow [17], we thus perform a more careful analysis of the
above recursive formula. First, we provide an explicit formula for $f(n,h)$:

###### Lemma 1

The function $f$ can be described by the following explicit formula, for all
$n,h\geq 1$:

$\displaystyle
f(n,h)=\sum_{i=0}^{\lfloor\log_{2}n\rfloor-1}2^{i}\cdot\binom{h-1+i}{h-1}+(n-2^{\lfloor\log_{2}n\rfloor}+1)\cdot\binom{h-1+\lfloor\log_{2}n\rfloor}{h-1}.$

While it is possible to confirm the correctness of Lemma 1 by an inductive
proof, we present here a proof based on generating functions, as it is more
instructive.

######  Proof (Lemma 1)

Let $F(x,y)=\sum_{n,h\geq 1}f(n,h)x^{n}y^{h}$ be a generating function of the
two-dimensional sequence $f(n,h)$, excluding the values for $n=0$ and for
$h=0$. We multiply both sides of Equation 1 by $x^{n}y^{h}$, and then we sum
the result over all $n,h\geq 1$; we obtain that

$\displaystyle F(x,y)$ $\displaystyle=\sum_{\begin{subarray}{c}n\geq 1\\\
h\geq 1\end{subarray}}f(n,h-1)x^{n}y^{h}+\sum_{\begin{subarray}{c}k\geq 1\\\
h\geq 1\end{subarray}}(f(k,h)+f(k-1,h))x^{2k}y^{h}$ $\displaystyle\hskip
180.00027pt+\sum_{\begin{subarray}{c}k\geq 0\\\ h\geq
1\end{subarray}}2f(k,h)x^{2k+1}y^{h}.$

Next, in the first sum above we shift $h$ by $1$, and we move components with
$f(n,0)$ into a separate sum; in the second sum above we split
$f(k,h)+f(k-1,h)$ into two separate sums, where in the latter we shift $k$ by
$1$, and we move components with $f(0,h)$ into a separate sum; in the last sum
above, we move components for $k=0$ into a separate sum. We obtain

$\displaystyle F(x,y)$ $\displaystyle=\sum_{n\geq
1}f(n,0)x^{n}y+\sum_{\begin{subarray}{c}n\geq 1\\\ h\geq
1\end{subarray}}f(n,h)x^{n}y^{h+1}$
$\displaystyle\quad+\sum_{\begin{subarray}{c}k\geq 1\\\ h\geq
1\end{subarray}}f(k,h)(x^{2})^{k}y^{h}+\sum_{h\geq
1}f(0,h)x^{2}y^{h}+\sum_{\begin{subarray}{c}k\geq 1\\\ h\geq
1\end{subarray}}f(k,h)(x^{2})^{k}y^{h}x^{2}$ $\displaystyle\quad+\sum_{h\geq
1}2f(0,h)xy^{h}+\sum_{\begin{subarray}{c}k\geq 1\\\ h\geq
1\end{subarray}}2f(k,h)(x^{2})^{k}y^{h}x$
$\displaystyle=\frac{xy}{1-x}+yF(x,y)+F(x^{2},y)+0+x^{2}F(x^{2},y)+0+2xF(x^{2},y).$

This gives us the following equation concerning the generating function:

$\displaystyle F(x,y)=yF(x,y)+F(x^{2},y)(1+2x+x^{2})+\frac{xy}{1-x}.$ (2)

Let $H(x,y)=\frac{1-x}{y}F(x,y)$; then $F(x,y)=\frac{y}{1-x}H(x,y)$. Note that
$H$ is the generating function representing the differences between values of
$f$ for successive values of $n$, with $h$ shifted by $1$. Substituting this
to Equation 2 we obtain:

$\displaystyle\frac{y}{1-x}H(x,y)$
$\displaystyle=\frac{y^{2}}{1-x}H(x,y)+\frac{y}{1-x^{2}}H(x^{2},y)(1+x)^{2}+\frac{xy}{1-x},$
$\displaystyle\frac{y}{1-x}H(x,y)$
$\displaystyle=\frac{y^{2}}{1-x}H(x,y)+\frac{y}{1-x}H(x^{2},y)(1+x)+\frac{xy}{1-x},$
$\displaystyle H(x,y)$ $\displaystyle=yH(x,y)+H(x^{2},y)(1+x)+x.$

Next, let us write $H(x,y)=\sum_{n\geq 1}x^{n}h_{n}(y)$. We substitute this to
the equation above:

$\displaystyle\sum_{n\geq 1}x^{n}h_{n}(y)=\sum_{n\geq
1}x^{n}yh_{n}(y)+\sum_{n\geq 1}(x^{2n}+x^{2n+1})h_{n}(y)+x.$

In order to find $h_{n}$, we compare coefficients in front of $x^{n}$, on both
sides of the equation. For $n=1$ we have

$\displaystyle h_{1}(y)=yh_{1}(y)+1,$ so $\displaystyle
h_{1}(y)=\frac{1}{1-y},$

and for $n\geq 2$ we have

$\displaystyle h_{n}(y)=yh_{n}(y)+h_{\lfloor n/2\rfloor}(y),$ so
$\displaystyle h_{n}(y)=\frac{h_{\lfloor n/2\rfloor}(y)}{1-y}.$

It follows that for all $n\geq 1$ we have a formula

$\displaystyle h_{n}(y)=\frac{1}{(1-y)^{\lfloor\log_{2}n\rfloor+1}}.$

Below, we use the notation $[x^{n}]A(x)$ for the coefficient in front of
$x^{n}$ in the function $A(x)$. We also use the following formula, where
$k\geq 1$:

$\displaystyle\frac{1}{(1-x)^{k}}=\sum_{n=0}^{\infty}\binom{n+k-1}{n}x^{n}.$
(3)

We now conclude the proof (here we assume that $n,h\geq 1$):

$\displaystyle f($ $\displaystyle
n,h)=[x^{n}y^{h}]F(x,y)=[x^{n}y^{h}]\frac{y}{1-x}H(x,y)$
$\displaystyle=[y^{h-1}]\sum_{j=0}^{n}[x^{j}]H(x,y)=[y^{h-1}]\sum_{j=1}^{n}h_{j}(y)$
$\displaystyle=[y^{h-1}]\left(\sum_{i=0}^{\lfloor\log_{2}n\rfloor-1}2^{i}h_{2^{i}}(y)+(n-2^{\lfloor\log_{2}n\rfloor}+1)h_{2^{\lfloor\log_{2}n\rfloor}}(y)\right)$
$\displaystyle=\sum_{i=0}^{\lfloor\log_{2}n\rfloor-1}2^{i}[y^{h-1}]\frac{1}{(1-y)^{i+1}}+(n-2^{\lfloor\log_{2}n\rfloor}+1)[y^{h-1}]\frac{1}{(1-y)^{\lfloor\log_{2}n\rfloor+1}}$
$\displaystyle=\sum_{i=0}^{\lfloor\log_{2}n\rfloor-1}2^{i}\cdot\binom{h-1+i}{h-1}+(n-2^{\lfloor\log_{2}n\rfloor}+1)\cdot\binom{h-1+\lfloor\log_{2}n\rfloor}{h-1}.$

Above, the third line is obtained based on the fact that
$h_{2^{i}}=h_{2^{i}+1}=\ldots=h_{2^{i+1}-1}$, and the last line is obtained
based on Equation 3. This finishes the proof of Lemma 1.

Next, we give two auxiliary lemmata, useful while bounding the asymptotics:

###### Lemma 2

For all $x\geq 0$ it holds that $\ln(1+x)\cdot(1+x)\geq x$.

###### Proof

Denote $h(x)=\ln(1+x)\cdot(1+x)-x$. Because $h(0)=0$, it is enough to prove
that the function $h$ is increasing. To this end, we compute its derivative.
We obtain $h^{\prime}(x)=\ln(1+x)$, so $h^{\prime}(x)>0$ for $x>0$ and indeed
the function $h$ is increasing.

###### Lemma 3

For every $c\geq 0$ the function

$\displaystyle\alpha_{c}(x)=\left(1+\frac{c}{x}\right)^{x}$

is nondecreasing for $x>0$.

###### Proof

We compute the derivative of $\alpha_{c}$:

$\displaystyle\alpha^{\prime}_{c}(x)=\alpha_{c}(x)\cdot\left(\ln\left(1+\frac{c}{x}\right)-\frac{c}{x\cdot\left(1+\frac{c}{x}\right)}\right).$

Because $\alpha_{c}(x)\geq 0$ for $x>0$, in order to confirm that
$\alpha^{\prime}_{c}(x)\geq 0$ it is enough to check that

$\displaystyle\ln\left(1+\frac{c}{x}\right)\geq\frac{c}{x\cdot\left(1+\frac{c}{x}\right)}.$

To show this inequality, we multiply to both its sides $1+\frac{c}{x}$ and we
use Lemma 2.

We are now ready to finish the proof of Theorem 3.1:

######  Proof (Theorem 3.1)

In order to obtain $f(n,h)\leq
n\cdot\binom{h-1+\lfloor\log_{2}n\rfloor}{\lfloor\log_{2}n\rfloor}$, we
replace all binomial coefficients in the formula of Lemma 1 by
$\binom{h-1+\lfloor\log_{2}n\rfloor}{\lfloor\log_{2}n\rfloor}$; obviously
$\binom{h-1+i}{h-1}\leq\binom{h-1+\lfloor\log_{2}n\rfloor}{h-1}=\binom{h-1+\lfloor\log_{2}n\rfloor}{\lfloor\log_{2}n\rfloor}$
for $i\leq\lfloor\log_{2}n\rfloor$.

Recall that $x^{\log_{2}y}=y^{\log_{2}x}$ for any $x,y>0$. The second
inequality from the theorem’s statement is obtained using, consecutively, the
estimation $\binom{n}{k}\leq\left(\frac{en}{k}\right)^{k}$, the inequality
$\log_{2}e<1{.}45$, and Lemma 3:

$\displaystyle f(n,h)$ $\displaystyle\leq
n\cdot\binom{h-1+\lfloor\log_{2}n\rfloor}{\lfloor\log_{2}n\rfloor}\leq
n\cdot\left(e\left(1+\frac{h-1}{\lfloor\log_{2}n\rfloor}\right)\right)^{\lfloor\log_{2}n\rfloor}$
$\displaystyle\leq n\cdot
e^{\log_{2}n}\cdot\left(1+\frac{h-1}{\lfloor\log_{2}n\rfloor}\right)^{\lfloor\log_{2}n\rfloor}=n^{1+\log_{2}e}\cdot\left(1+\frac{h-1}{\lfloor\log_{2}n\rfloor}\right)^{\lfloor\log_{2}n\rfloor}$
$\displaystyle\leq
n^{2{.}45-\varepsilon}\cdot\left(1+\frac{h-1}{\log_{2}n}\right)^{\log_{2}n}=n^{2{.}45-\varepsilon+\log_{2}\left(1+\frac{h-1}{\log_{2}n}\right)}.$

Assume now that $h=\omega(\log n)$. Then

$\displaystyle\log_{2}\left(1+\frac{h-1}{\log_{2}n}\right)$
$\displaystyle=\log_{2}\left(\frac{h}{\log_{2}n}\cdot(1+o(1))\right)$
$\displaystyle=\log_{2}\left(\frac{h}{\log_{2}n}\right)+\log_{2}(1+o(1)).$

The component $\log_{2}(1+o(1))=o(1)$ can be removed at the cost of decreasing
the constant $\varepsilon$, hence we obtain that

$\displaystyle f(n,h)\leq
n^{2{.}45-\varepsilon+\log_{2}\left(1+\frac{h-1}{\log_{2}n}\right)}=\mathcal{O}\left(n^{2{.}45-\varepsilon+\log_{2}\left(\frac{h}{\log_{2}n}\right)}\right).$
∎

##  4 Using smaller trees

Papers showing how to solve parity games with use of universal trees [17, 11,
23, 24] assume that in order to solve games with $n$ vertices one needs
$n$-universal trees. And for games with priorities on edges it can be shown
that $n$-universality is indeed required [8, 1]. However most papers
(including ours) define parity games with priorities on vertices, in which
case the necessity proof does not apply.

Let us come back to the paper of Jurdziński and Lazić [22]. Although it does
not mention universal trees explicitly, it uses a very particular universal
tree, called succinct tree coding. The important point is that this tree is
not $n$-universal, but rather $\eta$-universal, where $\eta$ can be either the
number of vertices of odd priority, or the number of vertices of even
priority, whatever is smaller, so clearly $\eta\leq\lfloor n/2\rfloor$
(formally, throughout their paper $\eta$ denotes the number of vertices of
even priority, but they explain at the beginning of Section 4 that priorities
can be shifted by $1$ ensuring that $\eta\leq\lfloor n/2\rfloor$). Moreover,
by looking into their paper one can see that the only “interface” between
Section 2, defining the succinct tree coding, and later sections, using the
coding, is Lemma 1, where it is shown that the succinct tree coding is an
$\eta$-universal tree. It is then easy to see that the algorithm of Jurdziński
and Lazić works equally well with any other $\eta$-universal tree (of
appropriate height, namely $d/2$) in place of the succinct tree coding. In
particular, we can use the universal trees from our Theorem 3.1, being of
smaller width.

Let us now bound the width of a universal tree that is needed for the
algorithm, comparing it with previous approaches. In order to avoid the
additional parameter $\eta$, we replace it in the sequel by $\lfloor
n/2\rfloor$, making use of the inequality $\eta\leq\lfloor n/2\rfloor$.
Substituting $d/2$ for $h$ and $\lfloor n/2\rfloor$ for $n$ in the formula
from Theorem 3.1, we obtain that the width of an $\lfloor
n/2\rfloor$-universal tree $\mathcal{T}$ of height $d/2$ can satisfy

$\displaystyle|\mathcal{T}|\leq\left\lfloor\frac{n}{2}\right\rfloor\cdot\binom{d/2-1+\lfloor\log_{2}\lfloor
n/2\rfloor\rfloor}{\lfloor\log_{2}\lfloor n/2\rfloor\rfloor}.$

To compare, for an $n$-universal tree $\mathcal{T}^{\prime}$ by Theorem 3.1 we
have

$\displaystyle|\mathcal{T}^{\prime}|\leq
n\cdot\binom{d/2-1+\lfloor\log_{2}n\rfloor}{\lfloor\log_{2}n\rfloor}.$

For natural $n$ we always have $\lfloor\log_{2}\lfloor
n/2\rfloor\rfloor=\lfloor\log_{2}(n/2)\rfloor=\lfloor\log_{2}n\rfloor-1$, so
the quotient of the two binomial coefficients is
$\frac{d/2-1+\lfloor\log_{2}n\rfloor}{\lfloor\log_{2}n\rfloor}$, which is in
$\Theta\left(\frac{d}{\log n}\right)$ if $d=\omega(\log n)$.

Let us now determine the asymptotics for $d=\omega(\log n)$. First, let us
simplify the formula for the $n$-universal tree $\mathcal{T}^{\prime}$:

$\displaystyle|\mathcal{T}^{\prime}|=\mathcal{O}(n^{2{.}45-\varepsilon+\log_{2}(d/2/\log_{2}n)})=\mathcal{O}(n^{1{.}45-\varepsilon+\log_{2}(d/\log_{2}n)}).$

For the $\lfloor n/2\rfloor$-universal tree $\mathcal{T}$ we thus have

$\displaystyle|\mathcal{T}|=\mathcal{O}\left(\left\lfloor\frac{n}{2}\right\rfloor^{1{.}45-\varepsilon+\log_{2}(d/\log_{2}\lfloor
n/2\rfloor)}\right)=\mathcal{O}\left(\left(\frac{n}{2}\right)^{1{.}45-\varepsilon+\log_{2}(d/\log_{2}n)}\right).$
(4)

The second equality above is obtained by replacing
$\left\lfloor\frac{n}{2}\right\rfloor$ with the slightly greater value of
$\frac{n}{2}$, and by observing that

$\displaystyle\log_{2}\left(\frac{d}{\log_{2}\lfloor n/2\rfloor}\right)$
$\displaystyle=\log_{2}\left(\frac{d}{\log_{2}n}\cdot(1+o(1))\right)$
$\displaystyle=\log_{2}\left(\frac{d}{\log_{2}n}\right)+\log_{2}(1+o(1));$

the component $\log_{2}(1+o(1))=o(1)$ can be removed at the cost of decreasing
the constant $\varepsilon$. We continue by analysing the logarithm of the
bound:

$\displaystyle\log_{2}\left(\frac{n}{2}\right)\cdot\left(1{.}45-\varepsilon+\log_{2}\frac{d}{\log_{2}n}\right)=\left(\log_{2}n-1\right)\cdot\left(1{.}45-\varepsilon+\log_{2}\frac{d}{\log_{2}n}\right)$
$\displaystyle\hskip
50.00008pt\leq\log_{2}n\cdot\left(1{.}45-\varepsilon+\log_{2}\frac{d}{\log_{2}n}\right)-\log_{2}\frac{d}{\log_{2}n}+\varepsilon$
$\displaystyle\hskip
50.00008pt\leq\log_{2}n\cdot\left(1{.}45-\varepsilon+o(1)+\log_{2}\frac{d}{\log_{2}n}\right)-\log_{2}d+\varepsilon;$
(5)

the last equality above was obtained by observing that

$\displaystyle-\log_{2}\frac{d}{\log_{2}n}=-\log_{2}d+\log_{2}\log_{2}n=-\log_{2}d+\log_{2}n\cdot
o(1).$

Combining Equations 4 and 5, we obtain the following bound on $|\mathcal{T}|$:

$\displaystyle|\mathcal{T}|=\mathcal{O}\left(n^{1{.}45-\varepsilon+o(1)+\log_{2}(d/\log_{2}n)}\cdot\frac{1}{d}\right).$

The $o(1)$ component can be removed at the cost of decreasing the constant
$\varepsilon$ again; we can thus write

$\displaystyle|\mathcal{T}|=\mathcal{O}\left(n^{1{.}45-\varepsilon+\log_{2}(d/\log_{2}n)}\cdot\frac{1}{d}\right).$

We now come to the complexity of the algorithm itself. As observed by
Jurdziński and Lazić [22, Theorem 7], their algorithm, when using a universal
tree $\widehat{\mathcal{T}}$, works in time $\mathcal{O}(m\cdot\log n\cdot\log
d\cdot|\widehat{\mathcal{T}}|)$. Using $\mathcal{T}$ as
$\widehat{\mathcal{T}}$, and observing that the polylogarithmic function
$O(\log n\cdot\log d)$ can be again “eaten” by the $-\varepsilon$ component of
the exponent, we obtain the following bound on the complexity, which is our
main theorem:

###### Theorem 4.1

For $d=\omega(\log n)$ one can find a winner in a parity game with $n$
vertices, $m$ edges, and $d$ priorities in time

$\displaystyle\mathcal{O}\left(m\cdot
n^{1{.}45+\log_{2}(d/\log_{2}n)}\cdot\frac{1}{d}\right).$

###### Remark 1

Compared to the previous bound of $\mathcal{O}\left(m\cdot d\cdot
n^{1{.}45+\log_{2}(d/\log_{2}n)}\right)$ (from Fijalkow [17]), we obtain an
improvement by a factor of $\Theta(d^{2})$. One $\Theta(d)$ is gained in
Theorem 3.1, by improving the bound for the size of a universal tree. A second
$\Theta(d)$ is gained by using $\lfloor n/2\rfloor$-universal trees instead of
$n$-universal trees.

###### Remark 2

The complexity obtained in Fijalkow [17] is the same as in Jurdziński and
Lazić [22]: he gains a factor of $\Theta(d)$ by using a better construction of
a universal tree instead of the “succinct tree coding”, but simultaneously he
loses a factor of $\Theta(d)$ due to using $n$-universal trees in place of
$\lfloor n/2\rfloor$-universal trees.

Let us also use this place to note that there is a small mistake in the paper
of Jurdziński and Lazić [22]. Namely, in the proof of Lemma 6 they switch to
analysing a simpler expression
$\binom{\lceil\log_{2}\eta\rceil+d/2}{\lceil\log_{2}\eta\rceil}$ in place of
$\binom{\lceil\log_{2}\eta\rceil+d/2+1}{\lceil\log_{2}\eta\rceil+1}$, saying
that the simpler expression is within a constant factor of the latter one.
This statement is false, though: the quotient of the two expressions is
$\frac{\lceil\log_{2}\eta\rceil+d/2+1}{\lceil\log_{2}\eta\rceil+1}$, which is
in $\Theta\left(\frac{d}{\log\eta}\right)$ if $d=\omega(\log\eta)$. Thus, the
actual complexity upper bound resulting from their analysis of the algorithm
for $d=\omega(\log\eta)$ should not be $\mathcal{O}\left(m\cdot
d\cdot\eta^{1{.}45+\log_{2}(d/\log_{2}\eta)}\right)$ as they claim, but rather
$\mathcal{O}\left(m\cdot
d^{2}\cdot\eta^{1{.}45+\log_{2}(d/\log_{2}\eta)}\right)$ (and taking $n/2$ for
$\eta$ this gives us the complexity $\mathcal{O}\left(m\cdot d\cdot
n^{1{.}45+\log_{2}(d/\log_{2}n)}\right)$, the same as in Fijalkow [17]).

###### Remark 3

While the current paper was under preparation, Dell’Erba and Schewe [12]
published some other improvement of Jurdziński and Lazić’s algorithm [22]. A
complete discussion is difficult to perform, since the authors have not
provided a precise bound.

## References

  * [1] Arnold, A., Niwiński, D., Parys, P.: A quasi-polynomial black-box algorithm for fixed point evaluation. In: CSL. LIPIcs, vol. 183, pp. 9:1–9:23. Schloss Dagstuhl - Leibniz-Zentrum für Informatik (2021)
  * [2] Benerecetti, M., Dell’Erba, D., Mogavero, F.: Solving parity games via priority promotion. Formal Methods Syst. Des. 52(2), 193–226 (2018)
  * [3] Benerecetti, M., Dell’Erba, D., Mogavero, F., Schewe, S., Wojtczak, D.: Priority promotion with Parysian flair. CoRR abs/2105.01738 (2021)
  * [4] Björklund, H., Vorobyov, S.G.: A combinatorial strongly subexponential strategy improvement algorithm for mean payoff games. Discret. Appl. Math. 155(2), 210–229 (2007)
  * [5] Boker, U., Lehtinen, K.: On the way to alternating weak automata. In: FSTTCS. LIPIcs, vol. 122, pp. 21:1–21:22. Schloss Dagstuhl - Leibniz-Zentrum für Informatik (2018)
  * [6] Browne, A., Clarke, E.M., Jha, S., Long, D.E., Marrero, W.R.: An improved algorithm for the evaluation of fixpoint expressions. Theor. Comput. Sci. 178(1-2), 237–255 (1997)
  * [7] Calude, C.S., Jain, S., Khoussainov, B., Li, W., Stephan, F.: Deciding parity games in quasipolynomial time. In: STOC. pp. 252–263. ACM (2017)
  * [8] Czerwiński, W., Daviaud, L., Fijalkow, N., Jurdziński, M., Lazić, R., Parys, P.: Universal trees grow inside separating automata: Quasi-polynomial lower bounds for parity games. In: SODA. pp. 2333–2349. SIAM (2019)
  * [9] Daskalakis, C., Papadimitriou, C.H.: Continuous local search. In: SODA. pp. 790–804. SIAM (2011)
  * [10] Daviaud, L., Jurdziński, M., Lehtinen, K.: Alternating weak automata from universal trees. In: CONCUR. LIPIcs, vol. 140, pp. 18:1–18:14. Schloss Dagstuhl - Leibniz-Zentrum für Informatik (2019)
  * [11] Daviaud, L., Jurdziński, M., Thejaswini, K.S.: The Strahler number of a parity game. In: ICALP. LIPIcs, vol. 168, pp. 123:1–123:19. Schloss Dagstuhl - Leibniz-Zentrum für Informatik (2020)
  * [12] Dell’Erba, D., Schewe, S.: Smaller progress measures and separating automata for parity games. CoRR abs/2205.00744 (2022)
  * [13] Emerson, E.A., Jutla, C.S.: Tree automata, mu-calculus and determinacy (extended abstract). In: FOCS. pp. 368–377. IEEE Computer Society (1991)
  * [14] Emerson, E.A., Jutla, C.S., Sistla, A.P.: On model checking for the $\mathrm{\mu}$-calculus and its fragments. Theor. Comput. Sci. 258(1-2), 491–522 (2001)
  * [15] Fearnley, J.: Exponential lower bounds for policy iteration. In: ICALP (2). Lecture Notes in Computer Science, vol. 6199, pp. 551–562. Springer (2010)
  * [16] Fearnley, J., Jain, S., de Keijzer, B., Schewe, S., Stephan, F., Wojtczak, D.: An ordered approach to solving parity games in quasi-polynomial time and quasi-linear space. Int. J. Softw. Tools Technol. Transf. 21(3), 325–349 (2019)
  * [17] Fijalkow, N.: An optimal value iteration algorithm for parity games. CoRR abs/1801.09618 (2018)
  * [18] Friedmann, O.: A subexponential lower bound for Zadeh’s pivoting rule for solving linear programs and games. In: IPCO. Lecture Notes in Computer Science, vol. 6655, pp. 192–206. Springer (2011)
  * [19] Friedmann, O., Hansen, T.D., Zwick, U.: Subexponential lower bounds for randomized pivoting rules for the simplex algorithm. In: STOC. pp. 283–292. ACM (2011)
  * [20] Jurdziński, M.: Deciding the winner in parity games is in UP $\cap$ co-UP. Inf. Process. Lett. 68(3), 119–124 (1998)
  * [21] Jurdziński, M.: Small progress measures for solving parity games. In: STACS. Lecture Notes in Computer Science, vol. 1770, pp. 290–301. Springer (2000)
  * [22] Jurdziński, M., Lazić, R.: Succinct progress measures for solving parity games. In: LICS. pp. 1–9. IEEE Computer Society (2017)
  * [23] Jurdziński, M., Morvan, R.: A universal attractor decomposition algorithm for parity games. CoRR abs/2001.04333 (2020)
  * [24] Jurdziński, M., Morvan, R., Ohlmann, P., Thejaswini, K.S.: A symmetric attractor-decomposition lifting algorithm for parity games. CoRR abs/2010.08288 (2020)
  * [25] Jurdziński, M., Paterson, M., Zwick, U.: A deterministic subexponential algorithm for solving parity games. SIAM J. Comput. 38(4), 1519–1532 (2008)
  * [26] Lehtinen, K.: A modal $\mu$ perspective on solving parity games in quasi-polynomial time. In: LICS. pp. 639–648. ACM (2018)
  * [27] Lehtinen, K., Parys, P., Schewe, S., Wojtczak, D.: A recursive approach to solving parity games in quasipolynomial time. Log. Methods Comput. Sci. 18(1) (2022)
  * [28] Parys, P.: Parity games: Zielonka’s algorithm in quasi-polynomial time. In: MFCS. LIPIcs, vol. 138, pp. 10:1–10:13. Schloss Dagstuhl - Leibniz-Zentrum für Informatik (2019)
  * [29] Rabin, M.O.: Automata on Infinite Objects and Church’s Problem. American Mathematical Society, Boston, MA, USA (1972)
  * [30] Schewe, S.: Solving parity games in big steps. J. Comput. Syst. Sci. 84, 243–262 (2017)
  * [31] Seidl, H.: Fast and simple nested fixpoints. Inf. Process. Lett. 59(6), 303–308 (1996)
  * [32] Vöge, J., Jurdziński, M.: A discrete strategy improvement algorithm for solving parity games. In: CAV. Lecture Notes in Computer Science, vol. 1855, pp. 202–215. Springer (2000)
  * [33] Zielonka, W.: Infinite games on finitely coloured graphs with applications to automata on infinite trees. Theor. Comput. Sci. 200(1-2), 135–183 (1998)