11institutetext: DERI, NUI Galway, Ireland
11email<EMAIL_ADDRESS>22institutetext: iSOCO, Madrid, Spain
22email<EMAIL_ADDRESS>
# Data Shapes and Data Transformations

Michael Hausenblas 11 Boris Villazón-Terrazas 22 Richard Cyganiak 11

###### Abstract

Nowadays, information management systems deal with data originating from
different sources including relational databases, NoSQL data stores, and Web
data formats, varying not only in terms of data formats, but also in the
underlying data model. Integrating data from heterogeneous data sources is a
time-consuming and error-prone engineering task; part of this process requires
that the data has to be transformed from its original form to other forms,
repeating all along the life cycle. With this report we provide a principled
overview on the fundamental data shapes _tabular_ , _tree_ , and _graph_ as
well as transformations between them, in order to gain a better understanding
for performing said transformations more efficiently and effectively.

##  1 Motivation

These days, content and information management systems have to deal with data
originating from an array of sources, such as relational databases, NoSQL data
stores, and Web data formats. The data sources vary not only in terms of data
formats, but first and foremost in the underlying data model, be it
implicit—such as with JSON—or explicit, think: RDF.

As recently put forward by Helland [Hel11], data integration of heterogeneous
data sources is a time-consuming, costly, and error-prone engineering task.
Typically, the data has to be transformed from its original form to other
forms, repeating all along the life cycle. For example, let us assume we want
to publish data from an government agency such as spreadsheets containing
statistical information into the Linked Open Data cloud111http://lod-
cloud.net. One task of the Linked Data life cycles would then be to transform
the original tabular spreadsheet data into (graph-shaped) RDF. Once we have
the data transformed into RDF according to, say, the RDF Data Cube
Vocabulary222http://www.w3.org/TR/vocab-data-cube/, we want to visualize it in
an appealing way, so we decide to use the Google Charts
API333https://developers.google.com/chart/ requiring us to provide input as
tabular data. So, again we have to transform a graph into a tabular, and then
the application visualize the information in an appealing way.

Apparently, even in this toy example, we have to transform data from its
original form to potentially many (intermediate) other forms. This was the
motivation for us to compile this report, aiming to provide a principled
overview of possible fundamental data shapes and transformations between them.
In the following we will focus on the data transformation within the context
of the “Extract, Transform and Load” process, a valuable process, growing in
its use and scale. We use the term _data shape_ to refer to how the data is
arranged and structured, closely related to the term data
model444http://en.wikipedia.org/wiki/Structured_data: we have identified three
fundamental _data shapes_ : tabular, tree, and graph and respective
transformations between them.

The remainder of the report is organized as follows: in Section 2 we introduce
and motivate the fundamental data shapes, then in Section 3 we describe
transformations between data shapes, and, finally, in Section 4 we discuss
open issues and challenges concerning the transformations.

##  2 Fundamental data shapes

In the following we motivate and introduce the three fundamental data shapes
_tabular_ , _tree_ , and _graph_ , derived from data
structures555http://en.wikibooks.org/wiki/Data_Structures and as found in the
wild in various datas sources, including but not limited to relational
databases (RDB), NoSQL data stores [Cat11], or Web data formats such as JSON,
OData and RDF serialisations.

###  2.1 Tabular

A tabular data shape organizes data items into a table. A table is a set of
data elements (values) that are organized using a model of vertical columns
(identified by their name), and horizontal rows. A table has a specified
number of columns. Examples of tabular data shapes are:

  * •

CSV (Comma Separated Values) files as of RFC
4180666http://tools.ietf.org/html/rfc4180—These files are used to store
tabular data, capable of storing numbers as well as text in a plain-text
format that can be easily written and read by humans and software alike.

  * •

RDB (relational databases)—A relational database is essentially a group of
tables (entities). Tables are made up of columns and rows (tuples). Those
tables have constraints, and relationships are defined between them.
Relational databases are queried using SQL, and result sets are produced from
queries that access data from one or more tables.

###  2.2 Tree

A tree is a non-empty set, one element of which is designated the root of the
tree while the remaining elements are partitioned into non-empty sets each of
which is a subtree of the root. Tree nodes have many useful properties. The
depth of a node is the length of the path (or the number of edges) from the
root to that node. The height of a node is the longest path from that node to
its leaves. The height of a tree is the height of the root. A leaf node has no
children, its only path is up to its parent.

A particular case of a tree is the _key-value data shape_ —a linked list of
key-value pairs. Examples of tree data shapes are:

  * •

XML (eXtensible Markup Language)—An open and flexible format used to exchange
a wide variety of data on and off the Web. XML is a tree structure of nodes
and nested nodes of information where the user defines the names of the
nodes777http://www.w3.org/XML/.

  * •

JSON (JavaScript Object Notation)— A lightweight data-interchange format. It
is easy for humans to read and write as well as straightforward for machines
to parse and generate888http://json.org/.

  * •

YAML (YAML Ain’t Markup Language)—A Super-set of JSON and general-purpos data
serialization language designed to be human-friendly and work well with modern
programming languages for common everyday tasks999http://yaml.org/.

###  2.3 Graph

A graph is a mathematical structure consisting of a set of vertexes (also
called nodes), and a set of edges. An edge is a pair of vertexes. The two
vertexes are called edge endpoints. A graph may be either undirected or
directed. Intuitively, an undirected edge models a “two-way” or “duplex”
connection between its endpoints, while a directed edge is a “one-way”
connection, and is typically represented by an arrow.

Examples of graphs are:

  * •

RDF (Resource Description Framework)— A family of World Wide Web Consortium
(W3C) specifications originally designed as a metadata model. It has come to
be used as a general method for conceptual description or modeling of
information that is implemented in web resources, using a variety of syntax
formats101010http://www.w3.org/RDF/.

  * •

Topic Maps—Topic maps are an ISO standard for describing knowledge structures
and associating them with information
resources111111http://www.isotopicmaps.org/.

##  3 Data shapes transformations

In this section we compare the possible transformations we can perform between
two given data shapes. To this end, we have identified a set of features along
three dimensions—the input, the output, and the transformation process—and
provide motivational usage scenarios per transformation. We acknowledge that
the characterisations and the formats presented in following are neither
exhaustive nor complete, however, serve as a useful starting point.

  * •

Dimension 1—concerning the input data shape:

    * –

The generic data shape, e.g., tabular, tree or graph.

    * –

The specific implementation of the data shape, e.g., XML, JSON, relational
database, ect.

  * •

Dimension 2—concerning the output data shape:

    * –

The generic data shape, e.g., tabular, tree or graph.

    * –

The specific implementation of the data shape, e.g., XML, JSON, relational
database, ect.

  * •

Dimension 3—concerning the transformation process:

    * –

The transformation process can be declarative or operational.

      * *

_Declarative_. There is a transformation description, the transformation is
based on a language that describes the mappings between the input and output
shapes.

      * *

_Operational_. The transformation is only based on an _ad-hoc_ transformation
engine.

    * –

The transformation process can have an information loss (also known as lossy
transformation) defined by: “all queries that are possible on the original
shape are also possible on the resultant shape”. We have information loss when
we change the abstraction level; this happens typically, when we transform a
“richer” shape into a “less rich shape”, e.g., from graph to tabular.

The Table 3.1 illustrates all possible transformations between two given data
shapes and provides pointers to the respective subsections where we discuss
them in further detail.

Table 3.1: Data shapes transformations overview. _from/to_ |  tree |  tabular |  graph
---|---|---|---
tree |  cf. Section 3.1 |  cf. Section 3.2 |  cf. Section 3.3
tabular |  cf. Section 3.4 |  cf. Section 3.5 |  cf. Section 3.6
graph |  cf. Section 3.7 |  cf. Section 3.8 |  cf. Section 3.9

###  3.1 Tree–Tree

In this case, the transformation takes as input a given tree and outputs
another tree. Let us suppose we have a set of XML documents that contain the
description of the transactions of a company, and we need to submit these tin
JSON files instead of XML, so we need to perform a transformation from tree to
tree. Examples of these transformations are:

  * •

XML to XML. An XSLT that turns a DocBook121212http://www.docbook.org/ file
into XHTML.

  * •

XML to JSON. A program that turns a XML file into JSON, or, for example via
XSLT.

###  3.2 Tree–Tabular

This transformation takes as input a tree and outputs a tabular. Let us
suppose we have a set of XML that contain the description of the transactions
of a company, and we need to submit these to an entity such as a government
agency that works with CSV files instead of XML, so we need to perform a
transformation from tree to tabular. Examples of these transformations are:

  * •

XML to RDB:

    * –

In [Fli09] a technique is described to transform XML into a RDB. The thecnique
relies on the XSD of the XML.

    * –

The connect xml-2-db
tool131313http://www.skyhawksystems.com/users_guide/runningxml2db.htm relies
on mapping files.

  * •

XML to CSV:

    * –

XSLT141414http://www.w3.org/TR/xslt.

    * –

Scripts151515For example, http://www.ricebridge.com/xml-csv-convert.htm.

###  3.3 Tree–Graph

This transformation takes as input a tree and outputs a graph. Let us suppose
we have a set of XML document that contain the description of the transactions
of a company, and we need to submit these to an entity such as a government
agency that works with RDF for integration purposes.In this setup, we need to
transform from tree to graph. Examples of these transformations are:

  * •

For example, with _Gleaning Resource Descriptions from Dialects of Languages_
(GRDDL)161616http://www.w3.org/TR/grddl/ one can turn an OData
document171717http://www.odata.org/ file into a corresponding RDF
representation.

  * •

Rhizomik ReDeFer181818http://rhizomik.net/redefer/ that includes XSD2OWL,
XML2RDF.

  * •

XSPARQL191919http://www.w3.org/Submission/xsparql-language-specification is a
query language combining XQuery and SPARQL for transformations between RDF and
XML.

###  3.4 Tabular–Tree

This transformation takes as input a tabular shape and outputs a tree shape.
Let us suppose we have a relational database containing transaction data of a
company, and we need to submit these transactions that requires, for
integration purposes, the data in XML, so we need to transform from tabular to
tree. Examples of these transformations are not standardised, but there are
bespoke systems such as:

  * •

XML representation of a relational
database202020http://www.w3.org/XML/RDB.html.

  * •

XMLSpy Relational Database
Integration212121http://www.altova.com/xmlspy/database-xml.html.

  * •

CSV-to-XML222222http://csv2xml.sourceforge.net/.

###  3.5 Tabular–Tabular

This transformation takes as input a tabular and outputs a tabular. Let us
suppose we have a relational database that contain the description of the
transactions in our company. We need to display these transactions in the
company web page. To this end, we have to transform from a tabular (RDB) to a
tabular (web page). Examples of these transformations are:

  * •

RDB to RDB: SQL SELECT.

  * •

CSV to RDB: relying on a particular DBMS import tool.

###  3.6 Tabular–Graph

This transformation takes as input a tabular and outputs a graph. Let us
suppose we have a relational database that contain the description of the
transactions in our company, and we need to submit these transactions into the
central office in London. For integration purposes the central office is using
RDF, so we need to transform from tabular to graph. Examples of these
transformations are:

  * •

RDB to RDF:

    * –

W3C’s RDB2RDF activity232323http://www.w3.org/2001/sw/rdb2rdf/: Direct Mapping
and R2RML, a language for expressing customized mappings from relational
databases to RDF datasets.

  * •

CSV to RDF:

    * –

XLWrap - language

    * –

TopBraid - tool

    * –

RDF extension of Google Refine - tool - GUI

  * •

RDB to Topic maps [NP09].

###  3.7 Graph–Tree

This transformation takes as input a graph and outputs a tree. Let us suppose
we have an RDF dataset for representing the statistical information of a
company and we need to transfer this information to an XML-based format such
as PC-Axis, used by the Irish CSO. Examples of these transformations are:

  * •

Turning RDF to XML242424http://www.w3.org/wiki/ConverterFromRdf.

  * •

XSPARQL252525http://www.w3.org/Submission/xsparql-language-specification is a
query language combining XQuery and SPARQL for transformations between RDF and
XML.

  * •

Geo2KML262626http://graphite.ecs.soton.ac.uk/geo2kml/ web service which
converts RDF to KML suitable for showing on Google Earth & Maps.

###  3.8 Graph–Tabular

The transformation takes as input a graph and outputs a tabular. Let us
suppose we have an RDF dataset for representing the statistical information of
a company and want to use Google Charts for visualising it. This requires a
tabular representation in CSV and therefore we have to perform a
transformation from graph to tabular. Examples of these transformations are:

  * •

SPARQL SELECT

  * •

_ad-hoc_ conversion scripts.

###  3.9 Graph–Graph

This transformation takes as input a graph and outputs a graph. Let us suppose
we have an RDF dataset for representing the statistical information of a
company, expressed in the W3C RDF Data Cube
vocabulary272727http://www.w3.org/TR/vocab-data-cube/. Now, further assume
that someone is still using the deprecated
SCOVO282828http://purl.org/NET/scovo# vocabulary for representing the
statistical information. Therefore we need to transform our data expressed in
RDF Data Cube to SCOVO. In this case, we have to perform a transformation from
a graph to graph. Examples of these transformations are:

  * •

RDF to RDF:

    * –

SPARQL CONSTRUCT.

    * –

R2R292929http://www4.wiwiss.fu-berlin.de/bizer/r2r/.

  * •

JSON to RDF: JSON to RDF web
service303030http://graphite.ecs.soton.ac.uk/rdf2json/

  * •

RTM313131http://www.ontopia.net/topicmaps/materials/rdf2tm.html is a
vocabulary that can be used to describe the mapping of an RDF vocabulary to
topic maps in such a way that RDF data using that vocabulary can be converted
automatically to topic maps.

###  3.10 Summary

In Table 3.2 we provide a summary of the data shapes transformation and their
characteristics.

Table 3.2: Data shapes transformations comparison. Input |  Output |  Nature |  Lossy? |  Standard
---|---|---|---|---
Tabular (RDB) |  Tabular (RDB) |  Declarative |  No |  SQL
Tabular (RDB) |  Tree (XML) |  Operational |  No |  No
Tabular (RDB) |  Graph (RDF) |  Declarative |  No |  RDB2RDF
Tree (XML) |  Tabular (RDB) |  Operational |  No |  No
Tree (XML) |  Tree (XML) |  Declarative |  No |  XSLT
Tree (XML) |  Tree (XML) |  Declarative |  No |  XSLT
Graph (RDF) |  Tabular (RDB) |  Declarative |  Yes |  SPARQL SELECT
Graph (RDF) |  Tree (XML) |  Declarative |  Yes |  No
Graph (RDF) |  Graph (RDF) |  Declarative |  No |  SPARQL CONSTRUCT

##  4 Discussion

Motivated by our experiences gathered in data integration projects as well as
in standardisation activities within W3C we wanted to provide a principled
overview on the fundamental data shapes and transformations between them.
Summarising, we can state the following:

  * •

We can perform (loss-less) data shape transformations between certain shapes.

  * •

A number of data shape transformations are already standards or in the process
of being standardised, including:

    * –

For RDB2RDF, see R2RML and Direct Mapping.

    * –

For XML2XML, see XSLT.

    * –

For XML2RDF, see GRDDL.

  * •

We found that some data shape transformations are declarative in nature and it
would be interesting to learn if others can and should be expressed
declaratively as well.

  * •

To this end, we have not taken provenance information in the transformation
process into account. Again, this is something worthwhile to follow up on.

  * •

In certain cases we have to deal with lossy transformations. A more systematic
study of these cases, including an assessment of the implications concerning
the data integration process is subject to future research.

We hope that the report in the current form is useful for both researchers and
practitioners alike and consider it as one contribution in helping to
establish a discussion around data shapes and their transformations in order
to advance the state of the art.

##  5 Acknowledgements

The authors are grateful for the support received through the European
Commission FP7 ICT projects BIG– _Big Data Public Private Forum_ (Grant
Agreement No. 257943) as well as LATC– _LOD Around-The-Clock_ (Grant Agreement
No. 256975).

## References

  * [Cat11] Rick Cattell.  Scalable SQL and NoSQL data stores.  SIGMOD Rec., 39:12–27, May 2011.
  * [Fli09] Amy Flik.  Transforming XML into a Relational Database Using XML Schema Document Type.  Technical Library. Paper 48., Grand Valley State University, 2009\.
  * [Hel11] Pat Helland.  If You Have Too Much Data, then ’Good Enough’ Is Good Enough.  Queue, 9:40:40–40:50, May 2011.
  * [NP09] Thomas Neidhart and Rani Pinchuk.  Semantic Integration of Relational Data Sources With Topic Maps.  In Fifth International Conference on Topic Maps Research and Applications, 2009.


# Multipath parsing in the brain

Berta Franzluebbers
University of Georgia
<EMAIL_ADDRESS>
Donald Dunagan
University of Georgia
<EMAIL_ADDRESS>
Miloš Stanojević
Google DeepMind
<EMAIL_ADDRESS>
Jan Buys
University of Cape Town
<EMAIL_ADDRESS>
John T. Hale
University of Georgia
<EMAIL_ADDRESS>

###### Abstract

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

##  1 Introduction

A major unsolved problem in computational psycholinguistics is determining
whether human sentence comprehension considers a _single_ analysis path111The
“paths” terminology (vs “serial” or “parallel”) serves to categorize the
cognitive issue as one of process rather than architecture (see Lewis, 2000b,
§3.3.3). at a time, or whether it sometimes entertains _multiple_ lines of
reasoning about the structure of a sentence. These lines of reasoning
typically correspond to syntactic ambiguities (e.g. between Subject and
Modifier as shown in Figure 1). Multipath accounts of ambiguity resolution
(e.g. Gibson, 1991; Jurafsky, 1996) are quite different from single-path
accounts (e.g. Frazier and Fodor, 1978; Marcus, 1980). The debate within
cognitive science has focused on the special case of garden path sentences
leaving open the broader question: Is human comprehension ever multipath in
the sense of Ranked Parallel parsing (Lewis, 2000a; Gibson and Pearlmutter,
2000)? If it is, where in the brain does such multipath parsing happen?

Figure 1: A sentence fragment from our stimulus text showing temporary
syntactic ambiguity about the correct relationship between The and desert,
which is resolved by hearing the next word (blue).

We take up the call to answer this question in a linguistically-transparent
way by combining broad coverage incremental parsing (e.g. Nivre, 2004) with
information-theoretical complexity metrics to derive predictions about
neuroimaging. Analyzing an entire book (Li et al., 2022) makes it possible to
examine – for the first time – all of the ambiguities that are implicated by a
given conception of syntax and a given parsing strategy – not just those
attested in classic garden path materials (Mason et al., 2003; Hopf et al.,
2003; Rodd et al., 2010).

We extend the state of the art in incremental generative dependency parsing by
using a large language model (BLOOM; Le Scao et al., 2022b) together with
parameter efficient fine-tuning using adapters Pfeiffer et al. (2020). We fix
the parsing strategy while varying the number of allowable analysis paths and
connect neural data with parser actions via surprisal for a review of this
information-theoretical metric see Hale, 2016 or neuroimaging studies such as
Brennan et al., 2016; Henderson et al., 2016; Shain et al., 2020; Brennan et
al., 2020. This sets up a contrast between a multipath model that considers
(at most) five paths at a time, versus a single-path model that can only
consider one at a time. The results, reported in section 5, ultimately support
the multipath view, as the surprisals from the five-way parser are better-
correlated with the neuroimaging data. This obtains for both English and
Chinese.

Action | Before | After | Arc | Probability
---|---|---|---|---
Shift | ($\sigma|i,j$) | ($\sigma|i|j,j+1$) | - | $p_{tr}(\mathrm{sh}|h_{i},h_{j})p_{gen}(w_{j+1}|h_{i},h_{j})$
Left-arc | ($\sigma|i,j$) | ($\sigma,j$) | $j\rightarrow i$ | $p_{tr}(\mathrm{re}|h_{i},h_{j})p_{dir}(\mathrm{la}|h_{i},h_{j})$
Right-arc | ($\sigma|l|i,j$) | ($\sigma|l,j$) | $l\rightarrow i$ | $p_{tr}(\mathrm{re}|h_{i},h_{j})p_{dir}(\mathrm{ra}|h_{i},h_{j})$
Table 1: The arc-hybrid transition system of Kuhlmann et al. (2011) defines
the possible parser actions (shift, left-arc, and right-arc) as transitions
from previous to current parser states. States are indicated by (stack,
current index) tuples, e.g. $w_{i}$ is the token on top of the stack
($\sigma$), and $w_{j}$ is the current index token at time step $j$. The
probabilities associated with these actions are decomposed into complementary
shift (sh) and reduce (re) transitions, and complementary left-arc (la) and
right-arc (ra) arc directions. The shift action also includes the probability
of generating the next token $w_{j+1}$.

##  2 Related Work

This paper follows a line of research which aims to characterize human
language processing by evaluating word-by-word difficulty predictions against
neuroimaging data from the brain. Hale et al. (2022) reviews many studies that
fit into this tradition. Most of them consider just a single gold standard or
single system-assigned analysis. Hale et al. (2018) and Crabbé et al. (2019)
are notable exceptions to this general trend because they derive predictions
from multiple analyses that would be considered as part of a beam. Hale and
Crabbé work with phrase structure. By contrast, the present study uses
dependency parsing. This choice is motivated by prior work in neurolinguistics
(e.g. Bornkessel-Schlesewsky and Schlesewsky, 2015). For instance, Li and Hale
(2019) relates a dependency-based structural distance metric to hemodynamic
activity in left posterior temporal lobe, among other brain areas. Their study
used spoken English materials. Lopopolo et al. (2021) apply a related metric
to Dutch. Oota et al. (2023) use graph neural networks to embed dependency
analyses of sentence-initial substrings. Using the encoding approach of Reddy
and Wehbe (2021) and written stimuli, this work identifies many of the same
brain areas as the studies mentioned above.

The single-path vs multipath question is itself motivated by prior work with
eyetracking data. By varying the number of paths available to a parser, Boston
et al. (2011) find support for Ranked Parallel parsing in the sense of Gibson
1991 and Jurafsky 1996, further characterized below in §3.4.

Apart from these cognitive considerations, a complementary motivation for this
research is to investigate the parsing improvements that come by leveraging
large language models (LLMs; see accuracy scores in Table 2). Such models are
trained on datasets that far exceed classic treebanks in size. This allows
LLMs to capture distributional regularities at a vast scale. However, it is
challenging to explain at an algorithmic level what these models are doing.

Instead of deriving a processing complexity metric directly from the output of
a large language model, or correlating next word predictions with fMRI data,
as in Schrimpf et al. (2021) and Caucheteux and King (2022), this work uses
initial substring encodings from an LLM to inform an incremental parser. Our
project also differs from Eisape et al. (2022), who probe LLM representations
to arrive at incremental unlabeled dependency analyses. In contrast to their
goal of investigating the syntactic properties of LLMs, we use LLM
representations as a starting point for a parser which builds the set of all
possible analyses, increasing accuracy. Our scientific goal is to relate such
parser states to human brain activity.

##  3 Dependency Parsing

###  3.1 Parser Architecture

The construction of our dependency parser relies on the work of Buys and
Blunsom (2018), which employs the transition based parsing system detailed in
Nivre (2008) and exactly enumerates all parser paths. Following Kuhlmann et
al. (2011), dynamic programming is used to sum over all paths. We use the arc-
hybrid transition system shown in Table 1 because it showed good parsing
performance in Buys and Blunsom (2018). The generative parser assigns a
probability to each of the words in the sentence incrementally, similar to a
language model, in contrast to discriminative parsers which only predict
transition actions. The shift action predicts the next word on the buffer,
which corresponds to the buffer-next model in Buys and Blunsom (2018).

We update Buys and Blunsom by encoding sequences not with an LSTM but with
representations from the BigScience Large Open-science Open-access
Multilingual Language Model (BLOOM; Le Scao et al., 2022b), chosen based on
its open-access status and training on both English and Chinese data. These
BLOOM representations encode an entire initial substring up to and including a
particular word (or subword token). A set of classifiers over these substring
representations estimates the probability of each transition, word and arc
label. The classifiers correspond to the subscripted probabilities in the
rightmost column of Table 1.

We use the pre-trained BLOOM-560 model. Larger BLOOM models showed no
significant increase in accuracy. This corroborates the work of Oh and Schuler
(2023) and Pasquiou et al. (2023), who correlate large language model
encodings to human reading times and fMRI data, respectively, and find that
smaller models provide an equal (or better) fit to the human data.

Instead of fine-tuning the entire pre-trained BLOOM model on dependency
parsing, we apply a Pfeiffer adapter after each layer (Pfeiffer et al., 2020).
This bottleneck adapter introduces a new linear layer which reduces the
dimension from 1024 down to 64 and back up to 1024, for input into the next
pre-trained BLOOM layer. The adapter approach enables parameter-efficient
fine-tuning while preserving the original language modelling representations
as much as possible in the generative parser.

The goal of these design choices is to deliver linguistically plausible
dependency analyses of sentence-initial substrings. Some aspects of the
overall architecture play the role of auxiliary hypotheses that do not map on
to the brain. As subsection 3.5 lays out in further detail, the cognitive
claim is limited to proposals that (a) human parsing involves recognizing
dependency relations via a schema like Table 1 and (b) surprising parser
actions, within this schema, call for greater hemodynamic resources than do
unsurprising ones. Proposal (a) is situated at Marr’s middle level of analysis
(Marr, 1982).

###  3.2 Parser Training

The parser is trained on English and Chinese treebanks annotated with Stanford
Dependencies De Marneffe and Manning (2008). The English model is trained on
the Penn Treebank (PTB) version 3, with the standard split of training on
sections 02-21, development on section 22, and testing on section 23. The
Chinese model is trained on Chinese Treebank version 7, with the standard
split of files 0-2082 for training, development on files 2083-2242, and
testing on files 2243-2447. This results in 39,832 training sentences for
English and 19,457 training sentences for Chinese.

The parser’s next word prediction classifier predicts over a limited
vocabulary, where words seen only once in the training data are replaced with
unknown word tokens according to the rules in the Berkeley Parser. This
results in 23,830 word types for English and 19,671 for Chinese. The LLM
encoder, however, uses the BLOOM sub-word tokenizer and the BLOOM vocabulary,
which is of size 250,680.222This vocabulary size mismatch is one reason we did
not directly assign next-word probabilities using the LLM.

Corpus | Model | Dev | Test
---|---|---|---
LAS | UAS | LAS | UAS
PTB-3 | Buys and Blunsom (2018) | 88.66 | 91.19 | 88.54 | 91.01
PTB-3 | English BLOOM (brain analysis) | 90.26 | 92.71 | 90.32 | 92.62
CTB-7 | Chinese BLOOM (brain analysis) | 77.07 | 83.65 | 74.71 | 81.66

Table 2: Labeled attachment score (LAS), Unlabeled attachment score (UAS), and
Label accuracy score for the English PTB corpus and Chinese CTB corpus Figure
2: Parser input in the form of (stack ($\sigma$), current index ($\beta$))
tuples is pre-processed by adding a leading space to all pretokenized text
from the corpus. The BLOOM model is pre-trained and fine tuned using the
Pfeiffer Adapter, and the system of classifiers is trained from random
weights. Note that the word prediction classifier predicts over the size of
the training data vocabulary + Berkeley unknown tokens instead of the BLOOM
vocabulary.

Token sequences are encoded by the LLM, selecting the encoding of the right-
most sub-word of each word for parser predictions. This allows sequence
encodings to be as detailed as possible while still limiting the vocabulary
during training. It should be noted, though, that using this encoding for
words that are unknown to the parser’s next word classifier prevents the
parser from being strictly generative. More information on strictly generative
models can be found in the appendix.

While training, sentences are shuffled at each epoch, and within batches
(batch size = 16), which are created from sentences of the same length. The
BLOOM-560 model has 24 hidden layers, after encoding.

Figure 3: Labeled Accuracy Score (LAS), Unlabeled Accuracy Score (UAS), Label
Accuracy for our parser trained and evaluated (dev set) on the Universal
Dependencies ParTUT corpus. Each model uses a different BLOOM layer as a
sequence encoder.

We select the 17th layer as the representation to input into the model, which
was decided based on optimization of development set accuracy on the ParTUT
Universal Dependencies corpus De Marneffe et al. (2021). We use this smaller
corpus (2,090 sentences) in order to conserve resources when investigating the
utility of BLOOM representations for dependency parsing. As seen in Fig. 3,
BLOOM layers 10 to 17 have similar accuracy levels. Selecting different layers
based on a search of the English and Chinese Treebank corpora development set
may be able to provide minor improvements in accuracy beyond that reported in
Table 2. Further training hyperparameters can be found in the Appendix.

###  3.3 Parser Accuracy

While state of the art methods employ information about the entire sentence
(using global methods, or incremental methods with bidirectional embeddings)
in order to predict dependency relations, for the purposes of creating a
cognitively plausible model, strictly incremental methods must be used without
including useful information from words occurring later in the sentence. We
compare the accuracy of the incremental generative parser proposed here to
that of Buys and Blunsom (2018), which employs the same transition system with
encodings based on an LSTM with random initial weights.

Parser accuracy is evaluated on the development set after each epoch, and the
highest scoring epoch is reported in Table 2. However, the cognitive modeling
results reported in Section 5 rely on earlier training checkpoints. The epoch
is chosen by maximizing $r^{2}$ correlation with the fMRI data. The labeled
attachment score and unlabeled attachment score (LAS/UAS) for the epochs
chosen are 89.75/92.37 for English, and 77.06/83.59 for Chinese. We find that
the objective of obtaining minimal loss does not correspond to optimal
correlation with fMRI activity.

###  3.4 Multiple paths

Multipath parsing, as a psycholinguistic claim about human sentence
comprehension, is simply the idea that ambiguity-resolution pursues more than
one alternative at the same time. This contrasts with Frazier and Fodor’s
(1978) conception, in which a single parse is developed along one path. We
consider here a version of the multipath idea that Kurtzman (1984) calls
“strong” parallelism, in which paths can persist from word to word. Gorrell
(1987) emphasizes that multiple alternatives are not equally available (page
84). This is naturally formalized by ranking the paths. Such ranking can be
implemented with beam search, at the heart of parsing systems like Roark
(2001), which is widely applied in computational psycholinguistics and
neurolinguistics.

###  3.5 Complexity Metric

In order to correlate parser predictions to brain activity, and in particular
to take multiple parser paths into consideration, it is necessary to include a
metric which summarizes the parser prediction information. One such metric is
surprisal, revived by Hale (2001) as a method of predicting sentence-
processing difficulty at a word level. The basic formula is the logarithm of
the inverse of the marginal probability.

$\mathrm{log}_{2}\left(\frac{1}{p(y)}\right)=-\mathrm{log}_{2}(p(y))$ (1)

In the case of incremental sentence comprehension, the surprisal of a word at
position $w_{i}$ which follows a string ending in $w_{i-1}$, is a ratio of the
probability at the current word with the previous probability:

$-\mathrm{log}_{2}\left(\frac{p(w_{i},w_{i-1},...,w_{1}))}{p(w_{i-1},...,w_{1}))}\right)$
(2)

####  3.5.1 Syntactic Surprisal

Word probabilities, denoted $p_{gen}$ in Table 1, are affected by nonsyntactic
factors. As Fig. 4 shows, these nonsyntactic factors can overshadow the
difference between syntactic alternatives. For this reason, we follow Roark et
al. (2009) in decomposing surprisal into lexical and syntactic expectations.
Discarding lexical expectations, we focus exclusively on differences among
competing syntactic analyses by adopting their syntactic surprisal measure,
given below as Eq. 3. Syntactic surprisal does not consider word probability.

Figure 4: A sentence from The Little Prince, showing incremental surprisal
from joint probability decomposed into lexical (red), and syntactic surprisal
(blue)

In addition, we limit the sum to the top $k$ transition sequences. Here, $j$
indexes discrete ranks of a ranked parallel parser, and $t_{a(i)}$ refers to
all the parser transitions in the path that ends at generation of token
$w_{i}$.

$\mathrm{SynS}_{k}(w_{i})=-\mathrm{log}_{2}\sum_{j=1}^{k}\frac{p\left(t_{a(i)}\mid
w_{i-1}\dots\\!w_{1}\right)_{j}}{p\left(t_{a(i-1)}\mid
w_{i-1}\\!\dots\\!w_{1}\right)_{j}}$ (3)

This limitation to $k$ paths follows Boston et al. (2011). Unlike Boston et
al., we retain all analyses and simply chose the top $k$ at each successive
word. This allows paths that would have been lost forever in true beam search
to later rejoin the beam. Such restoration has essentially the same effect as
backtracking, in cases where it would lead to a higher-scoring analyses.

An example calculation is shown in Fig. 5.

Figure 5: A sentence fragment from The Little Prince showing shift-reduce
parser actions with associated probabilities. The probability of the most
likely path at time = 3 is 0.55, which corresponds to surprisal for k=1:
-log2(0.55/0.99) = 0.86, and k=2: -log(0.99/0.99) = 0.

####  3.5.2 Why Five Paths?

Figure 6: Syntactic surprisal at $k=1$ (blue) and $k=5$ (orange) for tokens in
The Little Prince

Addressing the single-path vs multipath question entails choosing some number
of paths, $k$ to represent multipath parsing in general. Empirical literature
such as Gibson and Pearlmutter (2000) has been primarily concerned with the
distinction between 1 and 2 paths. By contrast, accurate NLP systems sometimes
consider tens or even hundreds of paths.333Many of these paths lead to similar
syntactic structures. Grouping them in a cognitively realistic way brings up
foundational questions regarding the mental representation of grammatical
relations see Bresnan and Kaplan 1982, Sturt 1996, and §4.4 of Brasoveanu and
Dotlačil 2020, among others. These questions, along with the proper
formulation of reanalysis or repair operations (e.g. Lewis, 1992; Buch-
Kromann, 2004) are important directions for future work. This mismatch calls
for a setting of $k$ that is small, but clearly different from 1. The
syntactic surprisal metric itself also mitigates against settings of $k$ that
are too large. With this metric, more ranks quickly eat up the available
probability mass, up to 1.0, when considering all possible paths. In this
limiting case syntactic surprisal would trivially equal zero for all tokens
(see Figure 6). For these reasons, we selected five paths to contrast with
single-path parsing.444This goal of this study is to adjudicate between
single-path and multipath parsing. This question has remained open within the
literature on human sentence processing for quite some time. An alternative
approach seeks to maximize correlations with fMRI data by e.g. searching for
the optimal number of paths. This suggests a natural follow-up.

##  4 fMRI Methods

###  4.1 Participants

As detailed in Li et al. (2022), the English dataset includes 49 participants
(30 female, mean age = 21.3, range = 18-37), and the Chinese dataset includes
35 participants (15 female, mean age = 19.9, range = 18-24).

###  4.2 Data Acquisition

The English audio stimulus is an English translation of The Little Prince,
read by Karen Savage. The Chinese audio stimulus is a Chinese translation of
The Little Prince, read by a professional female Chinese broadcaster. The
English and Chinese audiobooks are 94 and 99 minutes in length, respectively.
The presentations were divided into nine sections, each lasting around ten
minutes. Participants listened passively to the nine sections and completed
four quiz questions after each section (36 questions in total). These
questions were used to confirm participant comprehension of the story.

The English and Chinese brain imaging data were acquired with a 3T MRI GE
Discovery MR750 scanner with a 32-channel head coil. Anatomical scans were
acquired using a T1-weighted volumetric magnetization prepared rapid gradient-
echo pulse sequence. Blood-oxygen-level-dependent (BOLD) functional scans were
acquired using a multi-echo planar imaging sequence with online reconstruction
(TR = 2000 ms; TE’s = 12.8, 27.5, 43 ms; FA = 77°; matrix size = 72 x 72; FOV
= 240.0 mm x 240.0 mm; 2x image acceleration; 33 axial slices, voxel size =
3.75 x 3.75 x 3.8 mm).

###  4.3 Data Preprocessing

The English and Chinese fMRI data were preprocessed using AFNI version 16
(Cox, 1996). The first 4 volumes in each run were excluded from analyses to
allow for T1-equilibration effects. Multi-echo independent components analysis
(ME-ICA), was used to denoise data for motion, physiology, and scanner
artifacts Kundu et al. (2012). Images were then spatially normalized to the
standard space of the Montreal Neurological Institute (MNI) atlas, yielding a
volumetric time series resampled at 2 mm cubic voxels.

###  4.4 Statistical Analysis

The goal of the analysis is to compare surprisal for models that consider
different numbers of analysis paths ($k$) against observed fMRI signal. To
this end, we apply the same methodology as Crabbé et al. (2019), in which
model comparisons using cross-validated coefficient of determination ($r^{2}$)
maps are carried out in order to evaluate the goodness of fit of two alternate
metrics with BOLD signal.

For each subject individually, the BOLD signal is modeled by a General Linear
Model (GLM) at each voxel. The following five regressors are included in the
GLM: word rate, fundamental frequency (f0), word frequency, root mean square
intensity (RMS), and surprisal at the top $k$ derivations. Word rate is a
timing function marking the offset of each spoken word; f0 is the fundamental
frequency, or pitch of the audio; word frequency is obtained from words in a
movie subtitles database Brysbaert and New (2009); and RMS is an indicator of
audio intensity, taken every 10ms. These predictors are known to affect speech
comprehension, and are included as control variables to isolate the BOLD
signal specific to processing syntactic ambiguity corresponding to the
surprisal regressor.

Surprisal for each word was also aligned to the offset of each word in the
audiobook. All predictors were convolved using SPM’s canonical Hemodynamic
Response Function Friston et al. (2007).

For each participant, we compute how much the inclusion of the surprisal
regressor increases the cross-validated $r^{2}$ over the baseline model, which
includes only the control variables. We repeat this process for surprisal at
different levels of $k$ separately in order to keep the number of parameters
in each GLM model constant. Therefore, the $r^{2}$ increase scores represent
the variance explained in each voxel by the addition of surprisal to the model
as a predictor.

To compare models across two different levels of $k$ and analyze their ability
to explain fMRI signal, we performed a paired t-test on individual $r^{2}$
increase maps, and obtained z-maps showing the brain regions where surprisal
at one level of parallelism explains the signal significantly better than
surprisal at the other (see Figures 7 and 8).

##  5 Results

Figure 7: English Brain z-maps showing the significant clusters (p < .001
uncorrected; cluster threshold = 15 voxels) for the model comparison between
syntactic surprisal at k=1 vs k=5. All significant clusters show greater
$r^{2}$ increase for surprisal at k=5 than for surprisal at k=1.  Figure 8:
Chinese Brain z-maps showing the significant clusters (p < .001 uncorrected;
cluster threshold = 15 voxels) for the model comparison between syntactic
surprisal at k=1 vs k=5. All significant clusters show greater $r^{2}$
increase for surprisal at k=5 than for surprisal at k=1.

Both English and Chinese paired t-tests on $r^{2}$ increase maps show
differences in the superior temporal gyrus (STG). The Chinese results further
show differences in middle temporal gyrus (MTG), while the English results
show differences in the parietal lobe, including bilateral angular gyrus. The
full list of statistically significant clusters corresponding to Figures 7 and
8 can be found in the Appendix. Although the paired t-tests were two-tailed,
all of the resulting significant clusters show greater $r^{2}$ increase for
surprisal at k=5 than for surprisal at k=1. The $r^{2}$ increase maps for each
model individually can be found in the Appendix.

##  6 Discussion

Multipath parsing effort, outside of the 1-best analysis, localizes to
superior temporal regions of the brain bilaterally in both English and
Chinese. This finding converges with Crabbé et al. (2019). Crabbé and
colleagues parse phrase structure, rather than dependencies, employ a
different complexity metric, and use a very large beam (400). Despite all
these differences, their results implicate roughly the same brain regions.

These results also cohere with proposals regarding the large-scale
organization of language processing in the brain. On the Neuroanatomical
Pathway model, for instance, “most basic syntactic processes” are handled by a
ventral pathway that passes through STG regions identified here (Friederici,
2015). Matchin and Hickok (2020) similarly point to the ventral pathway as
essential for “basic” syntactic processes. This heuristic notion of basic
syntactic processing aligns well with Stanford Dependencies’ avowed goal of
providing a simple, surface-oriented notation for local grammatical relations.

The present results do not identify a significant difference in $r^{2}$
increase in Broca’s area (left IFG). Some increase in $r^{2}$ can be seen,
however, in middle and IFG in the individual model maps shown in the Appendix.
The absence of a significant difference, however makes sense in light of two
considerations. The first is the idea that left IFG subserves reanalysis in
the face of misinterpretation (Novick et al., 2005). The second is the
literary style of the The Little Prince. The stimulus text is dissimilar to
the sorts of garden-path materials psycholinguists have used see e.g. Sedivy
2019, chapter 9 or Fernández and Cairns 2010, chapter 7. It seems likely that
any garden-pathing was mild, remaining below the level of conscious awareness.
This distinction between misinterpretations that rise to the level of
conscious awareness and those that do not could help reconcile these results
with earlier studies showing IFG activation in response to garden path stimuli
(e.g. Mason et al., 2003; Rodd et al., 2010). For instance, Jäger et al.
(2015) suggests that Chinese relative clauses involve as many as four
temporary ambiguities. To our knowledge none of these reach the level of
conscious awareness in everyday comprehension. Yet in a naturalistic fMRI
study Dunagan et al. (2022) observe activation in anterior and middle STG that
is specific to Chinese object-extracted relative clauses. This contrast was
not reliable in a statistical comparison between English and Chinese. Further
work is needed to chart the space between unproblematic ambiguities (Lewis,
1993, §2.4.2) and conscious misinterpretations engendered by syntactic
ambiguity. In a similar vein, the localization to primary auditory cortices
could mean that basic syntactic processing is multipath even at very early
stages of perceptual processing. This possibility could be examined in a
followup fMRI study with written or signed materials, along the lines of
Henderson et al. (2016).

##  7 Conclusion and Future Work

The main conclusion is that human parsing is multipath. This follows from
observing greater $r^{2}$ increase for multipath surprisal than single-path
surprisal in fMRI data. Even with a very bottom-up strategy, such as the arc-
hybrid system used here, it seems that more than one path must be pursued in
order to best-align with humans’ word-by-word effort profile. This conclusion
is consistent with disjunctive representations of choicese such as PP
attachment (Kitaev et al., 2022, §5.5).

This multipath interpretation that we offer here can be confirmed or refuted
with other linked linguistic and neuro-cognitive databases – for instance, in
different genres or languages. In addition, using brain data with a higher
temporal resolution, such as MEG, may provide a benefit given the temporary
nature of the syntactic ambiguities included in our model. Although we take
the primary finding to be one of commonality across STG regions in both
languages, English listeners did uniquely show an additional effect of
multipath parsing in parietal regions. Activation in this area has been
correlated with measures of human memory such as digit span (Meyer et al.,
2012). Individuals’ memory span may modulate the number of paths that they
pursue during comprehension (Vos et al., 2001; Prat and Just, 2010). Future
work should address the interaction between disambiguation and memory (e.g.
Campanelli et al., 2018).

## Limitations

The goal of correlating parser states with fMRI data is limited by the
particularities of the parsing system – namely the arc-hybrid transition
system and the limited size and content of the training data (which is
dissimilar in genre to the audiobook text we study). In addition, the English
results in particular are the result of careful model selection to limit
“training away” the syntactic ambiguity we would like to measure. This may
indicate that more formalized external limitations should be applied to modern
high-performing parsers should they be used to model human sentence
processing.

## Ethics

Language models pose risks when used outside of their intended scope. We use
BLOOM, which is publicly available under the Responsible AI License (RAIL) Le
Scao et al. (2022a). Our scientific enquiry falls within the intended use of
public research on LLMs. We also use a publicly available fMRI dataset Li et
al. (2022), which is available under a CCO license. This dataset was
anonymized to remove identifying facial features before publication.

## Acknowledgements

This material is based upon work supported by the National Science Foundation
under Grant Number 1903783. We thank Laura Rimell and Michael Covington for
valuable discussion, along with Christophe Pallier for developing the cross-
validated $r^{2}$ code used here. We are grateful to many collaborators for
assistance with the fMRI data collection. Among them are Shohini Bhattasali,
Jixing Li, Wen-Ming Luh and Nathan Spreng.

## References

  * Bornkessel and Schlesewsky (2006) Ina Bornkessel and Matthias Schlesewsky. 2006.  The extended argument dependency model: A neurocognitive approach to sentence comprehension across languages.  _Psychological Review_ , 113(4):787–821.
  * Bornkessel-Schlesewsky and Schlesewsky (2015) Ina Bornkessel-Schlesewsky and Matthias Schlesewsky. 2015.  The Argument Dependency Model.  In Hickok et al. (2015), chapter 30.
  * Boston et al. (2011) Marisa Ferrara Boston, John T Hale, Shravan Vasishth, and Reinhold Kliegl. 2011\.  Parallel processing and sentence comprehension difficulty.  _Language and Cognitive Processes_ , 26(3):301–349.
  * Brasoveanu and Dotlačil (2020) Adrian Brasoveanu and Jakub Dotlačil. 2020.  _Computational Cognitive Modeling and Linguistic Theory_.  Language, Cognition, and Mind. Springer.
  * Brennan et al. (2020) Jonathan R. Brennan, Chris Dyer, Adhiguna Kuncoro, and John T. Hale. 2020.  Localizing syntactic predictions using recurrent neural network grammars.  _Neuropsychologia_ , 146:1074–1079.
  * Brennan et al. (2016) Jonathan R. Brennan, Edward P. Stabler, Sarah E Van Wagenen, Wen-Ming Luh, and John T. Hale. 2016.  Abstract linguistic structure correlates with temporal activity during naturalistic comprehension.  _Brain Lang._ , 157-158:81–94.
  * Bresnan and Kaplan (1982) Joan Bresnan and Ronald M. Kaplan. 1982.  Introduction: Grammars as mental representations of language.  In Joan Bresnan, editor, _The Mental Representation of Grammatical Relations_ , pages xvii,lii. MIT Press, Cambridge, MA.
  * Brysbaert and New (2009) Marc Brysbaert and Boris New. 2009.  Moving beyond Kučera and Francis: A critical evaluation of current word frequency norms and the introduction of a new and improved word frequency measure for American English.  _Behavior research methods_ , 41(4):977–990.
  * Buch-Kromann (2004) Matthias Buch-Kromann. 2004.  Optimality parsing and local cost functions in Discontinuous Grammar.  _Electronic Notes in Theoretical Computer Science_ , 53:163–179.  Proceedings of the joint meeting of the 6th Conference on Formal Grammar and the 7th Conference on Mathematics of Language.
  * Buys and Blunsom (2018) Jan Buys and Phil Blunsom. 2018.  Neural syntactic generative models with exact marginalization.  In _Proceedings of the 2018 Conference of the North American Chapter of the Association for Computational Linguistics: Human Language Technologies, Volume 1 (Long Papers)_ , pages 942–952.
  * Campanelli et al. (2018) Luca Campanelli, Julie A. Van Dyke, and Klara Marton. 2018.  The modulatory effect of expectations on memory retrieval during sentence comprehension.  In Timothy T. Rogers, Marina Rau, Xiaojin Zhu, and Charles W. Kalish, editors, _Proceedings of the 40th Annual Conference of the Cognitive Science Society_ , pages 1434–1439. Cognitive Science Society, Austin, Texas.
  * Caucheteux and King (2022) Charlotte Caucheteux and Jean-Rémi King. 2022.  Brains and algorithms partially converge in natural language processing.  _Nature Communications Biology_ , 5(1):134.
  * Cox (1996) Robert W Cox. 1996.  Afni: software for analysis and visualization of functional magnetic resonance neuroimages.  _Computers and Biomedical research_ , 29(3):162–173.
  * Crabbé et al. (2019) Benoit Crabbé, Murielle Fabre, and Christophe Pallier. 2019.  Variable beam search for generative neural parsing and its relevance for the analysis of neuro-imaging signal.  In _Proceedings of the 2019 Conference on Empirical Methods in Natural Language Processing and the 9th International Joint Conference on Natural Language Processing (EMNLP-IJCNLP)_ , pages 1150–1160, Hong Kong, China. Association for Computational Linguistics.
  * De Marneffe and Manning (2008) Marie-Catherine De Marneffe and Christopher D Manning. 2008.  The stanford typed dependencies representation.  In _Coling 2008: proceedings of the workshop on cross-framework and cross-domain parser evaluation_ , pages 1–8.
  * De Marneffe et al. (2021) Marie-Catherine De Marneffe, Christopher D Manning, Joakim Nivre, and Daniel Zeman. 2021.  Universal dependencies.  _Computational linguistics_ , 47(2):255–308.
  * Dunagan et al. (2022) Donald Dunagan, Miloš Stanojević, Maximin Coavoux, Shulin Zhang, Shohini Bhattasali, Jixing Li, Jonathan Brennan, and John Hale. 2022.  Neural correlates of object-extracted relative clause processing across English and Chinese.  _Neurobiology of Language_ , pages 1–43.
  * Eisape et al. (2022) Tiwalayo Eisape, Vineet Gangireddy, Roger Levy, and Yoon Kim. 2022.  Probing for incremental parse states in autoregressive language models.  In _Findings of the Association for Computational Linguistics: EMNLP 2022_ , pages 2801–2813, Abu Dhabi, United Arab Emirates. Association for Computational Linguistics.
  * Fernández and Cairns (2010) Eva M. Fernández and Helen Smith Cairns. 2010.  _Fundamentals of Psycholinguistics_.  Wiley-Blackwell.
  * Ford (1989) Marilyn Ford. 1989.  Parsing complexity and a theory of parsing.  In Greg N. Carlson and Michael K. Tanenhaus, editors, _Linguistic Structure in Language Processing_ , pages 239–272. Kluwer.
  * Frazier and Fodor (1978) Lyn Frazier and Janet Dean Fodor. 1978.  The sausage machine: a new two-stage parsing model.  _Cognition_ , 6:291–325.
  * Friederici (2015) Angela D. Friederici. 2015.  The neuroanatomical pathway model of language.  In Hickok et al. (2015), chapter 29.
  * Friston et al. (2007) Karl J Friston, John Ashburner, Stefan J Kiebel, T Nichols, and William Penny. 2007\.  _Statistical Parametric Mapping_.  Academic Press.
  * Gibson (1991) Edward Gibson. 1991.  _A Computational Theory of Human Linguistic Processing: Memory Limitations and Processing Breakdown_.  Ph.D. thesis, Carnegie Mellon University.
  * Gibson and Pearlmutter (2000) Edward Gibson and Neal J. Pearlmutter. 2000.  Distinguishing serial and parallel parsing.  _Journal of Psycholinguistic Research_ , 29(2).
  * Gorrell (1987) Paul G. Gorrell. 1987.  _Studies of human syntactic processing: Ranked-parallel versus serial models_.  Ph.D. thesis, University of Connecticut.
  * Hale (2016) John Hale. 2016.  Information-theoretical complexity metrics.  _Language and Linguistics Compass_ , 10(9):397–412.
  * Hale et al. (2018) John Hale, Chris Dyer, Adhiguna Kuncoro, and Jonathan Brennan. 2018.  Finding syntax in human encephalography with beam search.  In _Proceedings of the 56th Annual Meeting of the Association for Computational Linguistics (Volume 1: Long Papers)_ , pages 2727–2736, Melbourne, Australia. Association for Computational Linguistics.
  * Hale (2001) John T Hale. 2001.  A probabilistic Earley parser as a psycholinguistic model.  In _Second meeting of the North American chapter of the association for computational linguistics_.
  * Hale et al. (2022) John T Hale, Luca Campanelli, Jixing Li, Shohini Bhattasali, Christophe Pallier, and Jonathan R Brennan. 2022.  Neurocomputational models of language processing.  _Annual Review of Linguistics_ , 8:427–446.
  * Henderson et al. (2016) John M Henderson, Wonil Choi, Matthew W Lowder, and Fernanda Ferreira. 2016.  Language structure in the brain: A fixation-related fMRI study of syntactic surprisal in reading.  _NeuroImage_ , 132:293–300.
  * Hickok et al. (2015) Gregory Hickok, Steven L. Small, and Steven L. Small. 2015.  _Neurobiology of Language_.  Elsevier, San Diego.
  * Hopf et al. (2003) Jens-Max Hopf, Markus Bader, Michael Meng, and Josef Bayer. 2003.  Is human sentence parsing serial or parallel?: Evidence from event-related brain potentials.  _Cognitive Brain Research_ , 15(2):165–177.
  * Jäger et al. (2015) Lena Jäger, Zhong Chen, Qiang Li, Chien-Jer Charles Lin, and Shravan Vasishth. 2015.  The subject-relative advantage in Chinese: Evidence for expectation-based processing.  _Journal of Memory and Language_ , 79:97–120.
  * Jurafsky (1996) Daniel Jurafsky. 1996.  A probabilistic model of lexical and syntactic access and disambiguation.  _Cognitive science_ , 20(2):137–194.
  * Kitaev et al. (2022) Nikita Kitaev, Thomas Lu, and Dan Klein. 2022.  Learned incremental representations for parsing.  In _Proceedings of the 60th Annual Meeting of the Association for Computational Linguistics (Volume 1: Long Papers)_ , pages 3086–3095, Dublin, Ireland. Association for Computational Linguistics.
  * Kuhlmann et al. (2011) Marco Kuhlmann, Carlos Gómez-Rodríguez, and Giorgio Satta. 2011.  Dynamic programming algorithms for transition -based dependency parsers.  In _Proceedings of the 49th Annual Meeting of the Association for Computational Linguistics: Human Language Technologies_ , pages 673–682, Portland, Oregon, USA. Association for Computational Linguistics.
  * Kundu et al. (2012) Prantik Kundu, Souheil J Inati, Jennifer W Evans, Wen-Ming Luh, and Peter A Bandettini. 2012.  Differentiating BOLD and non-BOLD signals in fMRI time series using multi-echo EPI.  _Neuroimage_ , 60(3):1759–1770.
  * Kurtzman (1984) Howard S. Kurtzman. 1984.  Ambiguity resolution in the human syntactic parser: An experimental study.  In _10th International Conference on Computational Linguistics and 22nd Annual Meeting of the Association for Computational Linguistics_ , pages 481–485, Stanford, California, USA. Association for Computational Linguistics.
  * Le Scao et al. (2022a) Teven Le Scao, Angela Fan, Christopher Akiki, Ellie Pavlick, Suzana Ilić, Daniel Hesslow, Roman Castagné, Alexandra Sasha Luccioni, François Yvon, Matthias Gallé, et al. 2022a.  Bloom: A 176b-parameter open-access multilingual language model.  _arXiv preprint 2211.05100_.
  * Le Scao et al. (2022b) Teven Le Scao, Thomas Wang, Daniel Hesslow, Stas Bekman, M Saiful Bari, Stella Biderman, Hady Elsahar, Niklas Muennighoff, Jason Phang, Ofir Press, Colin Raffel, Victor Sanh, Sheng Shen, Lintang Sutawika, Jaesung Tae, Zheng Xin Yong, Julien Launay, and Iz Beltagy. 2022b.  What language model to train if you have one million GPU hours? In _Findings of the Association for Computational Linguistics: EMNLP 2022_ , pages 765–782, Abu Dhabi, United Arab Emirates. Association for Computational Linguistics.
  * Lewis (1992) Richard L. Lewis. 1992.  Recent Developments in the NL-Soar Garden Path Theory.  Technical Report CMU-CS-92-141, Carnegie Mellon University.
  * Lewis (1993) Richard L. Lewis. 1993.  _An Architecturally-based Theory of Human Sentence Comprehension_.  Ph.D. thesis, Carnegie Mellon University, Pittsburgh, PA.
  * Lewis (2000a) Richard L. Lewis. 2000a.  Falsifying serial and parallel parsing models: empirical conundrums and an overlooked paradigm.  _Journal of Psycholinguistic Research_ , 29(2).
  * Lewis (2000b) Richard L. Lewis. 2000b.  Specifying architectures for language processing: Process, control, and memory in parsing and interpretation.  In Matthew W. Crocker, Martin Pickering, and Charles Clifton, Jr., editors, _Architectures and mechanisms for language processing_. Cambridge University Press.
  * Li et al. (2022) Jixing Li, Shohini Bhattasali, Shulin Zhang, Berta Franzluebbers, Wen-Ming Luh, R Nathan Spreng, Jonathan R Brennan, Yiming Yang, Christophe Pallier, and John Hale. 2022.  Le Petit Prince multilingual naturalistic fMRI corpus.  _Scientific data_ , 9(1):530.
  * Li and Hale (2019) Jixing Li and John Hale. 2019.  Grammatical predictors for fMRI timecourses.  In Robert C. Berwick and Edward P. Stabler, editors, _Minimalist Parsing_. Oxford University Press.
  * Lopopolo et al. (2021) Alessandro Lopopolo, Antal van den Bosch, Karl-Magnus Petersson, and Roel M. Willems. 2021.  Distinguishing syntactic operations in the brain: Dependency and phrase-structure parsing.  _Neurobiology of Language_ , 2(1):152–175.
  * Marcus (1980) Mitchell P. Marcus. 1980.  _A theory of syntactic recognition for natural language_.  MIT Press.
  * Marr (1982) David Marr. 1982.  _Vision: A computational investigation into the human representation and processing of visual information_.  W.H. Freeman and Company.
  * Marslen-Wilson (1973) William Marslen-Wilson. 1973.  Linguistic structure and speech shadowing at very short latencies.  _Nature_ , 244:522–523.
  * Mason et al. (2003) Robert A Mason, Marcel Adam Just, Timothy A Keller, and Patricia A Carpenter. 2003\.  Ambiguity in the brain: what brain imaging reveals about the processing of syntactically ambiguous sentences.  _Journal of Experimental Psychology: Learning, Memory, and Cognition_ , 29(6):1319.
  * Matchin and Hickok (2020) William Matchin and Gregory Hickok. 2020.  The cortical organization of syntax.  _Cerebral Cortex_ , 30(3):1481–1498.
  * Meyer et al. (2012) Lars Meyer, Jonas Obleser, Alfred Anwander, and Angela D Friederici. 2012.  Linking ordering in broca’s area to storage in left temporo-parietal regions: the case of sentence processing.  _Neuroimage_ , 62(3):1987–1998.
  * Nivre (2004) Joakim Nivre. 2004.  Incrementality in deterministic dependency parsing.  In _Proceedings of the workshop on incremental parsing: Bringing engineering and cognition together_ , pages 50–57.
  * Nivre (2008) Joakim Nivre. 2008.  Algorithms for deterministic incremental dependency parsing.  _Computational Linguistics_ , 34(4):513–553.
  * Novick et al. (2005) Jared M. Novick, John C. Trueswell, and Sharon L. Thompson-Schill. 2005.  Cognitive control and parsing: Reexamining the role of Broca’s area in sentence comprehension.  _Cognitive, Affective & Behavioral Neuroscience_, 5(3):263–281.
  * Oh and Schuler (2023) Byung-Doh Oh and William Schuler. 2023.  Why does surprisal from larger transformer-based language models provide a poorer fit to human reading times?  _Transactions of the Association for Computational Linguistics_ , 11:336–350.
  * Oota et al. (2023) Subba Reddy Oota, Mounika Marreddy, Manish Gupta, and Raju Bapi. 2023.  How does the brain process syntactic structure while listening? In _Findings of the Association for Computational Linguistics: ACL 2023_ , pages 6624–6647, Toronto, Canada. Association for Computational Linguistics.
  * Pasquiou et al. (2023) Alexandre Pasquiou, Yair Lakretz, Bertrand Thirion, and Christophe Pallier. 2023\.  Information-restricted neural language models reveal different brain regions’ sensitivity to semantics, syntax and context.  _arXiv preprint arXiv:2302.14389_.
  * Pfeiffer et al. (2020) Jonas Pfeiffer, Andreas Rücklé, Clifton Poth, Aishwarya Kamath, Ivan Vulić, Sebastian Ruder, Kyunghyun Cho, and Iryna Gurevych. 2020.  Adapterhub: A framework for adapting transformers.  In _Proceedings of the 2020 Conference on Empirical Methods in Natural Language Processing (EMNLP 2020): Systems Demonstrations_ , pages 46–54, Online. Association for Computational Linguistics.
  * Prat and Just (2010) Chantel S. Prat and Marcel Adam Just. 2010.  Exploring the Neural Dynamics Underpinning Individual Differences in Sentence Comprehension.  _Cerebral Cortex_ , 21(8):1747–1760.
  * Reddy and Wehbe (2021) Aniketh Janardhan Reddy and Leila Wehbe. 2021.  Can fmri reveal the representation of syntactic structure in the brain? In _Advances in Neural Information Processing Systems_ , volume 34, pages 9843–9856. Curran Associates, Inc.
  * Roark (2001) Brian Roark. 2001.  Probabilistic top-down parsing and language modeling.  _Computational Linguistics_ , 27(2):249–276.
  * Roark et al. (2009) Brian Roark, Asaf Bachrach, Carlos Cardenas, and Christophe Pallier. 2009.  Deriving lexical and syntactic expectation-based measures for psycholinguistic modeling via incremental top-down parsing.  In _Proceedings of the 2009 Conference on Empirical Methods in Natural Language Processing_ , pages 324–333, Singapore. Association for Computational Linguistics.
  * Rodd et al. (2010) Jennifer M Rodd, Olivia A Longe, Billi Randall, and Lorraine K Tyler. 2010.  The functional organisation of the fronto-temporal language system: evidence from syntactic and semantic ambiguity.  _Neuropsychologia_ , 48(5):1324–1335.
  * Schrimpf et al. (2021) Martin Schrimpf, Idan Asher Blank, Greta Tuckute, Carina Kauf, Eghbal A. Hosseini, Nancy Kanwisher, Joshua B. Tenenbaum, and Evelina Fedorenko. 2021.  The neural architecture of language: Integrative modeling converges on predictive processing.  _Proceedings of the National Academy of Sciences_ , 118(45):e2105646118.
  * Sedivy (2019) Julie Sedivy. 2019.  _Language in Mind: An Introduction to Psycholinguistics_ , second edition.  Oxford University Press.
  * Shain et al. (2020) Cory Shain, Idan Asher Blank, Marten van Schijndel, William Schuler, and Evelina Fedorenko. 2020.  fMRI reveals language-specific predictive coding during naturalistic sentence comprehension.  _Neuropsychologia_ , 138:107307.
  * Sturt (1996) Patrick Sturt. 1996.  Monotonic Syntactic Processing: A Cross-linguistic Study of Attachment and Reanalysis.  _Language and Cognitive Processes_ , 11(5):449–494.
  * Tanenhaus et al. (1995) Michael Tanenhaus, Michael Spivey-Knowlton, Kathleen Eberhard, and Julie Sedivy. 1995.  Integration of visual and linguistic information in spoken language comprehension.  _Science_ , 268:1632–1634.
  * Vos et al. (2001) Sandra H. Vos, Thomas C. Gunter, Herbert Schriefers, and Angela D. Friederici. 2001\.  Syntactic parsing and working memory: The effects of syntactic complexity, reading span, and concurrent load.  _Language and Cognitive Processes_ , 16(1):65–103.

##  Appendix A Appendix

###  A.1 Generative Models

As noted in Section 3.2, we use BLOOM’s tokenizer to encode all tokens. Since
some of these tokens are not found in the training data, and thus are unknown
to the parser’s next word prediction classifier, this prevents our parser from
being strictly generative.

As a comparison, we train additional models which are truly generative by
replacing tokens not seen in the training data with unknown tokens in the
encoder input, in the same way as the word prediction classes are defined. We
report the accuracy for this generative approach alongside the previously
defined full input model in Table 3. This distinction is also explained in
Fig. 9 for an example prefix string.

Figure 9: Parser input in the form of (stack ($\sigma$), current index
($\beta$)) tuples is pre-processed according to the given method: Full Input
indicates no pre-processing apart from adding a leading space to all
pretokenized text from the corpus. Generative indicates tokens are
preprocessed by replacing tokens not seen more than once in the training data
with unknown tokens according to the rules of the Berkeley Parser. The BLOOM
model and the system of classifiers used to output probabilities is the same
for both models. Note that the word prediction classifier predicts over the
size of the training data vocabulary + Berkeley unknown tokens for both
methods.

Corpus | Model | Dev | Test
---|---|---|---
LAS | UAS | LAS | UAS
PTB-3 | Buys and Blunsom (2018) | 88.66 | 91.19 | 88.54 | 91.01
PTB-3 | English BLOOM Generative | 89.27 | 92.00 | 90.53 | 92.68
PTB-3 | English BLOOM Full Input (brain analysis) | 90.26 | 92.71 | 90.32 | 92.62
CTB-7 | Chinese BLOOM Generative | 73.12 | 80.60 | 74.47 | 81.60
CTB-7 | Chinese BLOOM Full Input (brain analysis) | 77.07 | 83.65 | 74.71 | 81.66

Table 3: Labeled attachment score (LAS), Unlabeled attachment score (UAS), and
Label accuracy score for the English PTB corpus and Chinese CTB corpus

###  A.2 Parser Training

The output representation from the BLOOM model has a dropout of 0.5 applied,
and is then fed into a single layer feedforward neural network.

During training, gradient norms are clipped to 5.0, and the initial learning
rate is 1.0, with a decay factor of 1.7 applied every epoch after the initial
6 epochs. English and Chinese models train for approximately 5.5 and 4.5
minutes, respectively, per epoch on an A100 GPU.

###  A.3 Intermediate Results

Figure 10: English Brain z-maps showing the $r^{2}$ increase for the model
including surprisal at k=5 compared to the model including only the following
regressors: word rate, fundamental frequency (f0), word frequency, and root
mean square intensity (RMS). Figure 11: English Brain z-maps showing the
$r^{2}$ increase for the model including surprisal at k=1 compared to the
model including only the following regressors: word rate, fundamental
frequency (f0), word frequency, and root mean square intensity (RMS). Figure
12: Chinese Brain z-maps showing the $r^{2}$ increase for the model including
surprisal at k=5 compared to the model including only the following
regressors: word rate, fundamental frequency (f0), word frequency, and root
mean square intensity (RMS). Figure 13: Chinese Brain z-maps showing the
$r^{2}$ increase for the model including surprisal at k=1 compared to the
model including only the following regressors: word rate, fundamental
frequency (f0), word frequency, and root mean square intensity (RMS).

###  A.4 Results

Tables 4 and 5 show the full list of significant clusters (p < .001
uncorrected; cluster threshold = 15 voxels) for the model comparison between
syntactic surprisal at k=1 vs k=5.

Region | X | Y | Z | Peak Stat | Cluster Size (mm3)
---|---|---|---|---|---
Left-SecVisual(18), Right/Left DorsalPCC(31) | -12.0 | -64.0 | 24.0 | 4.78 | 968
Right-VisMotor(7) | 0.0 | -64.0 | 48.0 | 4.02 | 856
Right-AngGyrus (39) | 38.0 | -54.0 | 38.0 | 4.42 | 800
Left-PreMot + SuppMot(6) / Left-PrimAuditory (41) | -48.0 | -10.0 | 4.0 | 4.68 | 568
Right-VentPostCing(23) | 14.0 | -54.0 | 20.0 | 4.57 | 488
Right-AngGyrus (39) | 36.0 | -74.0 | 40.0 | 4.27 | 360
Left-AngGyrus (39) | -44.0 | -68.0 | 36.0 | 3.77 | 352
Right-DorsalPCC (31) | 14.0 | -62.0 | 34.0 | 4.03 | 216
Right-DorsalPCC (31) | 4.0 | -50.0 | 44.0 | 3.65 | 192
Right-PrimAuditory (41) | 48.0 | -12.0 | 2.0 | 3.69 | 160
Right-PrimAuditory (41) | 38.0 | -26.0 | 12.0 | 3.39 | 152
Table 4: English significant clusters (p < .001 uncorrected; cluster threshold = 15 voxels) for the model comparison between syntactic surprisal at k=1 vs k=5 Region | X | Y | Z | Peak Stat | Cluster Size (mm3)
---|---|---|---|---|---
Right-MedTempGyrus (21) / Right-SupTempGyrus (22) | 56.0 | -36.0 | 4.0 | 4.68 | 1336
Left-SupTempGyrus (22) | -64.0 | -26.0 | 6.0 | 4.32 | 392
Right-PrimAuditory (41) | 52.0 | -14.0 | 6.0 | 4.59 | 384
Left-PrimAuditory(41) | -56.0 | -6.0 | 4.0 | 5.04 | 384
Left-MedTempGyrus (21) | -48.0 | -42.0 | 4.0 | 4.25 | 320
Left-SupTempGyrus (22) | -58.0 | -26.0 | 0.0 | 4.06 | 288
Table 5: Chinese significant clusters (p < .001 uncorrected; cluster threshold
= 15 voxels) for the model comparison between syntactic surprisal at k=1 vs
k=5


* [STT88] Daniel D. Sleator, Robert E. Tarjan, and William P. Thurston.  Rotation distance, triangulations, and hyperbolic geometry.  J. Amer. Math. Soc., 1(3):647–681, 1988.
  * [STWZ19] Vivek Shende, David Treumann, Harold Williams, and Eric Zaslow.  Cluster varieties from Legendrian knots.  Duke Math. J., 168(15):2801–2871, 2019.
  * [STZ17] Vivek Shende, David Treumann, and Eric Zaslow.  Legendrian knots and constructible sheaves.  Invent. Math., 207(3):1031–1133, 2017.
  * [TZ18] David Treumann and Eric Zaslow.  Cubic planar graphs and Legendrian surface theory.  Adv. Theor. Math. Phys., 22(5):1289–1345, 2018.
  * [Ust06] A. V. Ustinov.  A short proof of Euler’s identity for continuants.  Mat. Zametki, 79(1):155–156, 2006.