# Opening the black box of language acquisition

Anna Jon-And E-mail<EMAIL_ADDRESS>Centre for cultural evolution,
Department of psychology, Stockholm University  Jérôme Michaud  Centre for
cultural evolution, Department of psychology, Stockholm University  Division
of mathematics and physics, Mälardalen University

###### Abstract

Recent advances in large language models using deep learning techniques have
renewed interest on how languages can be learned from data. However, it is
unclear whether or how these models represent grammatical information from the
learned languages. In addition, the models must be pre-trained on large
corpora before they can be used. In this work, we propose an alternative, more
transparent and cognitively plausible architecture for learning language.
Instead of using deep learning, our approach uses a minimal cognitive
architecture based on sequence memory and chunking. The learning mechanism is
based on the principles of reinforcement learning. We test our architecture on
a number of natural-like toy languages. Results show that the model can learn
these artificial languages from scratch and extract grammatical information
that supports learning. Our study demonstrates the power of this simple
architecture and stresses the importance of sequence memory as a key component
of the language learning process. Since other animals do not seem to have a
faithful sequence memory, this may explain why only humans have developed
complex languages.

##  1 Introduction

The remarkable and often human-like linguistic performance of modern large
language models (LLMs) using deep learning techniques has drawn attention
towards language learning and processing. Among other things, it is discussed
what we can learn about human linguistic abilities from studying the
mechanisms by which LLMs learn from data and generate output from input. It is
possible to gain some insight into what kind of information LLMs are able to
store at the semantic, syntactic and morphological levels by studying their
attentional mechanisms Manning et al. (2020); Vaswani et al. (2017);
Piantadosi (2023); Piantasodi and Hill (2022). But the neural networks upon
which LLMs rely contain billions to trillions of parameters Piantadosi (2023);
Brown et al. (2020) and it is not possible to extract information on whether
or how any morpho-syntactic abstractions emerge in these models and, if so,
what is their nature. In this sense, LLMs are black boxes that generate
impressive results but provide us with very limited cues as to what cognitive
mechanisms may underlie human language learning.

In this article, we propose a minimal cognitive architecture that is not a
neural network, but follows a simple and traceable error-correction temporal
difference learning algorithm Sutton and Barto (2018), with the aim of opening
up the black box of language learning. The minimal architecture allows us, on
the one hand, to discuss what minimal cognitive properties are necessary for
language learning and, on the other hand, to follow the process of extracting
grammatical information that supports the language learning process. Our
approach is inspired by cognitive architecture research in artificial
intelligence, that aims at building a unified theory of cognition where few
general mechanisms should be able to explain diverse phenomena and
characteristics of human cognition Newell (1994). In line with recent domain-
general artificial intelligence modelling Wiggins (2020); van der Velde et al.
(2017), we aim at including as few assumptions as possible to account for the
language acquisition process. Our initial assumptions, drawing upon a pilot
study for the present work Jon-And and Michaud (2020), are that sequence
memory and chunking are two key domain-general cognitive mechanisms underlying
the human language ability. Our approach implements principles of usage-based
language learning, i.e. that language acquisition occurs through language use
and through continuous updating of linguistic knowledge encoded as chunks or
constructions Bybee (2006); Tomasello (2003).

The task of our learning model is to identify sentences in an artificial
linguistic stream where cues to sentence borders like punctuation or
capitalization are removed. However, differently from LLMs, our model learns
from very limited amounts of data and learning is local and based on simple
principles of updating associative strengths in agreement with humans’ limited
working memory and processing capacities. Furthermore, the learning task is
grounded in cognitively plausible assumptions since the identification of
meaningful units in an incrementally perceived stream is a real goal during
language learning. In our model, the learner follows a chunk-and-pass learning
principle Christiansen and Chater (2016b) in which it decides whether to place
a boundary or to chunk a newly encountered word to other words kept in the
working memory. Our chunking mechanism is hierarchic in that it associates
chunks to binary tree structures with the words as leaves. Since chunks retain
the order in which words are encountered, they encode both the ability for
sequence memory and the ability to chunk. Boundary placement triggers
reinforcement, where correct sentence identification is rewarded and wrong
sentence identification is negatively reinforced. Our design differs from most
syntactic parsing, where the task is to identify parse trees, dependencies
and/or constituents, and not to identify sentence boundaries. Our learning
mechanism has access to less information than most unsupervised syntactic
parsers, that have full access to boundaries as sentences are parsed one at a
time, and that generally have access to entire large corpora for probability
calculations Klein and Manning (2002); Bod (2006). Our model thus relies on
computationally cheaper principles than statistical learning in general.

The evaluation of the model is based on the one hand on it’s ability to fully
learn to identify sentences in artificial languages with varying degrees of
complexity, and on the other hand on its ability to identify and re-use chunks
that are extracted from exposure to these languages. We use probabilistic
context-free grammars to generate languages reflecting common natural language
structures. We find that the model is able to efficiently identify informative
chunks and re-use them when they occur in new structures, thus in a simplified
manner accounting for the emergence of grammar during learning. The limited
working memory of our model creates an information bottleneck that lets
grammatical structure emerge during the learning process as a way to overcome
the combinatorial explosion problem inherent to language acquisition. We also
find that the model over time learns to ignore less informative chunks and
gives priority to those that contribute more frequently to the correct
identification of sentences. In this way, we see how a simple task like
identification of sentence borders gives rise to self-organization and
consolidation in the emergent grammatical system.

This paper is organized as follows: Section 2 provides some background for
this study. Section 3 presents the computational framework used, i.e. the
framework of Markov Decision Processes Sutton and Barto (2018). In particular,
we discuss the learning task as well as the learning algorithms studied in
this paper. Section 4 presents the results of our study and discusses the
performance of our model on a number of small human-like toy languages. We
show that our model successfully learns these languages and provide some
interesting insights into how learning is performed. Finally, Section 5
provides a discussion of the implication of our results and outlines how this
work could be continued.

##  2 Background

###  2.1 Divergences in language learning in LLMs and humans

The advent of LLMs has revolutionized natural language processing, with the
neural network based Transformer architecture as their foundation Vaswani et
al. (2017). Even though neural networks are biologically inspired, LLMs are
designed to be useful engineering tools and not to model human cognition, and
they exhibit notable disparities in learning mechanisms compared to human
language acquisition. The difference in training data size is a critical
distinction; LLMs typically leverage datasets approximately 1000 times larger
than the linguistic input available to a child Warstadt and Bowman (2022).
Moreover, humans learn and use language in parallel Bybee (2006); Ellis,
O’Donnell, and Römer (2015); Tomasello (2003), while LLMs are generally pre-
trained and no longer learn when they are put in use. This implies that LLMs
have access to huge resources during learning, not only in terms of data, but
also in terms of memory and processing power. Once trained, LLMs can base
their output on very long input sequences, sometimes containing thousands of
tokens Beltagy, Peters, and Cohan (2020); Liang et al. (2023); Brown et al.
(2020). This differs radically from humans, that are typically able to store
somewhere between three and ten meaningful items in their working memory Cowan
(2001); Miller (1956). The chunk-and-pass principle, proposed as a strategy
for overcoming this constraint, is theorized to underpin the multilevel
representational structure of language Christiansen and Chater (2016b);
Christiansen and Chater (2016a). Principles of local decision-making and
memory updating, rooted in the utilization of limited recent information and
associations derived from past experiences, have also been implemented in
models that successfully account for aspects of language acquisition, change,
and emergence McCauley and Christiansen (2019); Baxter et al. (2006); Michaud
(2019); Steels and Loetzsch (2012).

###  2.2 Foundation of the human linguistic capacity: Sequence memory and
chunking

The human language capacity stands out among species for its flexibility and
expressive power. A fundamental and yet unsolved question is what kind of
cognitive mechanisms enable humans to learn grammar. Theories on cognitive
mechanisms underlying human language abilities range from inborn language
organization Chomsky (1957); Pinker and Jackendoff (2005); Bolhuis et al.
(2014); Christophe et al. (2008); Valian et al. (2013) to compromises between
inborn factors and flexibility Nowak, Komarova, and Niyogi (2002); Reali and
Griffiths (2009); Thompson, Kirby, and Smith (2016) to domain-general learning
Bybee (1985); Tomasello (2003); Heyes (2018), where linguistic structure would
be emergent and dynamic rather than innate Booij (2010); Goldberg (2007);
Croft and Cruse (2004); Croft (2001); Langacker (1987). The linguistic
capacities of modern LLMs, that rely on statistical and distributional
learning, contradicts claims that language learning needs to rely on specific
inborn properties Piantadosi (2023).

Associative learning is a fundamental mechanism in LLMs that also holds
explanatory power for general learning in both humans Heyes (2018) and other
animals Wasserman, Kain, and O’Donoghue (2023); Lind (2018); Heyes (2012b, a);
Enquist, Lind, and Ghirlanda (2016); Bouton (2016); Haselgrove (2016);
Enquist, Ghirlanda, and Lind (2023). However, the inability of non-human
animals to match the language usage capacity of LLMs and humans calls for
identifying unique properties that are present in humans, that may be shared
by LLMs but not by other animals. Sequence learning has been pointed out as
especially important for human linguistic capacities Heyes (2018);
Christiansen and MacDonald (2009); Bybee (2002a); Christiansen and Kirby
(2003); Christiansen and Arnon (2017); Frank, Bod, and Christiansen (2012);
Cornish et al. (2017); Udden et al. (2012); Kolodny, Edelman, and Lotem
(2015); Kolodny and Edelman (2018) and moreover, sequences constitute the
fundamental input of LLMs. At the same time, there is strong empirical support
for non-human animals limited capacity to represent the exact order of stimuli
Roberts and Grant (1976); MacDonald (1993); Ghirlanda, Lind, and Enquist
(2017); Read, Manrique, and Walker (2021); Lind et al. (2023). This suggests
faithful sequence representation to be a basic defining feature of human
cognition and linguistic abilities Enquist, Ghirlanda, and Lind (2023); Jon-
And et al. (2023). These findings call for testing the capacity for language
learning of a minimalist associative learning model with a precise but limited
sequence memory.

To enable processing of language or of any kind of sequential information,
sequence memory likely needs to be combined with a capacity for chunking, i.e.
considering a recurrent sequence of stimuli of flexible length as a unit.
Without chunking, it is impossible to faithfully represent a sequence.
Chunking is known to be central for human language learning Tomasello (2003);
Bybee (2002a); Servan-Schreiber and Anderson (1990); McCauley and Christiansen
(2019) and the aforementioned chunk-and-pass principle has been identified as
essential for overcoming memory constraints in online language processing
Christiansen and Chater (2016b).

###  2.3 Language models learning formal languages

In this paper, we use probabilistic context-free grammars as a straightforward
way to generate diverse hierarchical sentence structures of the kind we know
exist in natural languages. A seemingly similar approach is applied in a body
of work where language learning models evaluate hypothetical grammars of
formal languages via Bayesian inference Rule et al. (2018); Rule, Tenenbaum,
and Piantadosi (2020); Goodman et al. (2008); Goodman, Tenenbaum, and
Gerstenberg (2014); Piantadosi, Tenenbaum, and Goodman (2016); Amalric et al.
(2017); Planton et al. (2021); Ullman, Goodman, and Tenenbaum (2012); Ellis et
al. (2018). The formal languages are composed of sequences generated by rule
systems known as artificial grammars. These grammars are organized within a
mathematical hierarchy of escalating generative power, commonly referred to as
the Chomsky hierarchy Chomsky (2002, 1959). In a recent study a learning model
discovers the underlying system in a number of context-free and context-
sensitive formal languages through exposure to these languages without any
pre-defined hypothesis Yang and Piantadosi (2022). Most of the formal
languages in these studies do not, however, resemble natural languages.
Context-free languages like e.g. $a^{n}b^{n}$ are even impossible for humans
to learn without explicit counting if $n$ is high. Hochmann, Azadpour, and
Mehler (2008) showed that human performance in recognizing such strings more
likely relies on distributional regularities than any underlying grammar. It
is thus unclear what we can learn about the human language capacity by
studying the performance of machines on formal languages generated by
artificial grammars. This motivates our choice to limit the linguistic input
for our learner to structures that are common in natural languages and not
explore different levels in the Chomsky hierarchy. Furthermore, our approach
is more cognitively plausible than the approach generally used in the formal
language paradigm, as our model does not form any hypotheses on what grammar
underlie the data, but instead it relies on emergent dynamic rules to guide
each local decision, without necessarily formulating the whole set of rules
explicitly. In addition, the model we evaluate is much more minimalist than
previous learning models of similar scope, and strives for cognitive
plausibility, including only two basic features, sequence memory and chunking,
that are well-studied in humans.

##  3 Computational framework

The method used in this paper is that of reinforcement learning applied to a
Markov Decision Process (MDP) Sutton and Barto (2018), that encodes a language
learning task. The learner tries to identify sentences by placing boundaries
between words and gets positive reinforcement when it succeeds and negative
reinforcement when it fails. The model will then be evaluated by looking at
learning curves, i.e. the fraction of correct responses from a population of
agents, and at the grammar generated by the model. This section provides an
overview of the learning task, learning algorithms and evaluation methodology.

###  3.1 The learning task

We start by defining the learning task our cognitive architecture will use.
Following Sutton and Barto (2018), we define the task as a MDP. MDPs provide a
useful framework for studying learning from interactions to achieve a goal. In
this framework, a learner is called an _agent_. In our case, the agent aims to
identify sentences in a sequence of words constituting the environment. The
sequence of words used here is generated using a probabilistic context free
grammar (PCFG), but our model should work on any sequential input with well-
defined units. To illustrate the type of input the model receives it is useful
to take a natural language example. Consider for example the following three
sentences:

> _The cat chases the dog. The man loves his girlfriend. The sun shines._

Since identifying sentences in this context is too easy due to punctuation and
capitalization, we create a raw input by removing any hint as to the beginning
of sentences, for example capital letters and punctuation are removed from the
list of words, yielding the following modified input:

> _the cat chases the dog the man loves his girlfriend the sun shines_

The information about sentence boundaries is stored in a Boolean sequence
encoding whether a word in the raw input is preceded by a boundary or not.
This Boolean sequence is used to drive the reinforcement procedure. The aim of
the learning agent is then to identify sentences, i.e. sequences of words
separated by boundaries and not containing any other boundaries. This task can
be seen as a masking task, where sentence boundaries are masked and the aim of
the model is to predict where boundaries occur.

####  3.1.1 MDP formalism: states, actions, and rewards

In order to specify this task within the MDP framework, we need to specify

  1. 1.

how agent represent information, i.e. their state space;

  2. 2.

what they can do in a given state, i.e. their action spaces, which depends on
their state, and

  3. 3.

what consequences their actions have, i.e. the reward structure and
transitions between states.

More specifically, the agent interacts with its environment at discrete time
steps, $t=0,1,2,3,\dots$. At each time step $t$, the agent is in a given state
$S_{t}\in\mathcal{S}$ and takes an action $A_{t}\in\mathcal{A}(S_{t})$. As a
result of that action, the agent receives a reward
$R_{t+1}\in\mathcal{R}\subset\mathbb{R}$ and finds itself in a new state
$S_{t+1}\in\mathcal{S}$. To encode the behaviour of the agent, we use state-
action values $Q(s,a)$ encoding the value of taking action
$a\in\mathcal{A}(s)$, when the agent finds herself in state $s$ and define the
policy of an agent $\pi(a|s)$ as the probability to select action
$a\in\mathcal{A}(s)$ when in state $s$.

####  3.1.2 Specifying the language learning task as a MDP

In our case, the states are encoded as pairs of structured _chunks_ of words.
A chunk refers to a sequence of words and an associated binary tree with the
words as leaves. By default, the second and most recently perceived chunk
always consists of a single word. An example state is given by:

$S_{t}=\left(\leavevmode\hbox to0pt{\vbox
to0pt{\pgfpicture\makeatletter\hbox{\hskip 0.0pt\lower 0.0pt\hbox
to0.0pt{\pgfsys@beginscope\pgfsys@invoke{
}\definecolor{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@rgb@stroke{0}{0}{0}\pgfsys@invoke{
}\pgfsys@color@rgb@fill{0}{0}{0}\pgfsys@invoke{
}\pgfsys@setlinewidth{0.4pt}\pgfsys@invoke{ }\nullfont\hbox
to0.0pt{\pgfsys@beginscope\pgfsys@invoke{ } \Tree[ [ John ] [ [ eats ] [ cake
] ] ] \pgfsys@invoke{\lxSVG@closescope }\pgfsys@endscope{{
{}{}{}{}{}}{{{}}{{}}}}{}{}\hss}\pgfsys@discardpath\pgfsys@invoke{\lxSVG@closescope
}\pgfsys@endscope\hss}}\lxSVG@closescope\endpgfpicture}},\leavevmode\hbox
to0pt{\vbox to0pt{\pgfpicture\makeatletter\hbox{\hskip 0.0pt\lower 0.0pt\hbox
to0.0pt{\pgfsys@beginscope\pgfsys@invoke{
}\definecolor{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@rgb@stroke{0}{0}{0}\pgfsys@invoke{
}\pgfsys@color@rgb@fill{0}{0}{0}\pgfsys@invoke{
}\pgfsys@setlinewidth{0.4pt}\pgfsys@invoke{ }\nullfont\hbox
to0.0pt{\pgfsys@beginscope\pgfsys@invoke{ } \Tree[ and ]
\pgfsys@invoke{\lxSVG@closescope }\pgfsys@endscope{{
{}{}{}{}{}}{{{}}{{}}}}{}{}\hss}\pgfsys@discardpath\pgfsys@invoke{\lxSVG@closescope
}\pgfsys@endscope\hss}}\lxSVG@closescope\endpgfpicture}}\right)\,.$ (1)

In such a state, the agent has a number of possible actions: she can choose to
place a boundary between the two elements of her state, or to integrate the
second element into the structure of the first. Figure 1 illustrates the four
possible actions associated with the example above.

Figure 1: Illustration of the four possible actions. On the right, the results
of the four actions are shown. As can be seen, there are three different ways
of chunking the second element into the first.

The possible actions in a given state depend on the structure of the binary
tree and on how many ways it can be chunked with the second element of the
state. We define the right-depth of a state $d(S_{t})$ as the number of ways
the second chunk can be integrated into the first. In the example above
$d(S_{t})=3$, as is illustrated in Figure 1. There are $d(S_{t})+1$ possible
actions $a_{0},\dots,a_{d(S_{t})}$ in state $S_{t}$. We refer to the chunking
actions as $a_{0}$ when chunking at the root, and we increase the index as we
go down the tree. The deepest chunking action we can take is $a_{d(S_{t})-1}$.
For example, action $a_{2}$ in Figure 1 corresponds to grouping the last two
stimuli together. The last action $a_{d(S_{t})}$ corresponds to placing a
boundary between the elements of $S_{t}$.

When a chunking action is selected, the resulting chunk becomes the first
element of $S_{t+1}$ and the next word is read. In this case, no reward is
given.

Upon boundary placement, reinforcement is triggered. Whenever the first
element of $S_{t}$ is a correct sentence, a positive reward of
$R_{t+1}=r_{+}>0$ is given. Otherwise, a negative reward of $R_{t+1}=r_{-}<0$
is given. The next section describes how the rewards are used to update state-
action values and the policy of the agents. After reinforcement, we considered
two different ways of reinitializing the task:

Continuous:

The second element of $S_{t}$ becomes the first element of $S_{t+1}$ and the
next word is read to instantiate the second element.

Next sentence:

The first element of $S_{t+1}$ is set to the first word of the next sentence
in the sequence of words, and the second element is the following word.

These types of reinitialization process make the MDP episodic in the sense
that the process terminates upon boundary placement and restarts in a new
state. Thus, each attempt to identify a sentence constitutes a new episode.

###  3.2 Learning algorithms

During learning, an agent must choose between actions in order to increase its
expected reward. In this paper, we use a variant of the Q-learning algorithm
Sutton and Barto (2018) in which state-action values are updated according to
a temporal difference (TD) algorithm. These state-action values can be
considered as estimators of the expected reward from that specific state and
learning is driven by reducing the error in prediction. In our case, states
possess a hierarchic structure whenever $d(S_{t})>1$ and it is possible to
modify the standard Q-learning algorithm to take advantage of this structure.

####  3.2.1 State-action values, sub-states, and sub-actions

In order to decide what to do in a given state, an agent relies on the state-
action value $Q(s,a)$ of taking action $a$ in state $s$. However, the states
we consider here have a hierarchic structure. If the right-depth of a state
$d(s_{t})>1$, then there are a number of associated sub-states and
corresponding actions. Consider again the state in Eq. 1. Since this state has
right-depth 3, it has two associated sub-states, namely,

$S^{1}_{t}=\left(\leavevmode\hbox to0pt{\vbox
to0pt{\pgfpicture\makeatletter\hbox{\hskip 0.0pt\lower 0.0pt\hbox
to0.0pt{\pgfsys@beginscope\pgfsys@invoke{
}\definecolor{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@rgb@stroke{0}{0}{0}\pgfsys@invoke{
}\pgfsys@color@rgb@fill{0}{0}{0}\pgfsys@invoke{
}\pgfsys@setlinewidth{0.4pt}\pgfsys@invoke{ }\nullfont\hbox
to0.0pt{\pgfsys@beginscope\pgfsys@invoke{ } \Tree[ [ eats ] [ cake ] ]
\pgfsys@invoke{\lxSVG@closescope }\pgfsys@endscope{{
{}{}{}{}{}}{{{}}{{}}}}{}{}\hss}\pgfsys@discardpath\pgfsys@invoke{\lxSVG@closescope
}\pgfsys@endscope\hss}}\lxSVG@closescope\endpgfpicture}},\leavevmode\hbox
to0pt{\vbox to0pt{\pgfpicture\makeatletter\hbox{\hskip 0.0pt\lower 0.0pt\hbox
to0.0pt{\pgfsys@beginscope\pgfsys@invoke{
}\definecolor{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@rgb@stroke{0}{0}{0}\pgfsys@invoke{
}\pgfsys@color@rgb@fill{0}{0}{0}\pgfsys@invoke{
}\pgfsys@setlinewidth{0.4pt}\pgfsys@invoke{ }\nullfont\hbox
to0.0pt{\pgfsys@beginscope\pgfsys@invoke{ } \Tree[ and ]
\pgfsys@invoke{\lxSVG@closescope }\pgfsys@endscope{{
{}{}{}{}{}}{{{}}{{}}}}{}{}\hss}\pgfsys@discardpath\pgfsys@invoke{\lxSVG@closescope
}\pgfsys@endscope\hss}}\lxSVG@closescope\endpgfpicture}}\right)\quad\text{and}\quad
S^{2}_{t}=\left(\leavevmode\hbox to0pt{\vbox
to0pt{\pgfpicture\makeatletter\hbox{\hskip 0.0pt\lower 0.0pt\hbox
to0.0pt{\pgfsys@beginscope\pgfsys@invoke{
}\definecolor{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@rgb@stroke{0}{0}{0}\pgfsys@invoke{
}\pgfsys@color@rgb@fill{0}{0}{0}\pgfsys@invoke{
}\pgfsys@setlinewidth{0.4pt}\pgfsys@invoke{ }\nullfont\hbox
to0.0pt{\pgfsys@beginscope\pgfsys@invoke{ } \Tree[ cake ]
\pgfsys@invoke{\lxSVG@closescope }\pgfsys@endscope{{
{}{}{}{}{}}{{{}}{{}}}}{}{}\hss}\pgfsys@discardpath\pgfsys@invoke{\lxSVG@closescope
}\pgfsys@endscope\hss}}\lxSVG@closescope\endpgfpicture}},\leavevmode\hbox
to0pt{\vbox to0pt{\pgfpicture\makeatletter\hbox{\hskip 0.0pt\lower 0.0pt\hbox
to0.0pt{\pgfsys@beginscope\pgfsys@invoke{
}\definecolor{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@rgb@stroke{0}{0}{0}\pgfsys@invoke{
}\pgfsys@color@rgb@fill{0}{0}{0}\pgfsys@invoke{
}\pgfsys@setlinewidth{0.4pt}\pgfsys@invoke{ }\nullfont\hbox
to0.0pt{\pgfsys@beginscope\pgfsys@invoke{ } \Tree[ and ]
\pgfsys@invoke{\lxSVG@closescope }\pgfsys@endscope{{
{}{}{}{}{}}{{{}}{{}}}}{}{}\hss}\pgfsys@discardpath\pgfsys@invoke{\lxSVG@closescope
}\pgfsys@endscope\hss}}\lxSVG@closescope\endpgfpicture}}\right)\,,$

where we used an upper index to label these sub-states. The original state is
labeled $0$ or is left unlabeled. An action
$a_{i}^{0}\in\mathcal{A}_{t}^{0}(S^{0}_{t})$ associated with the state
corresponds to an action $a_{i-k}^{k}\in\mathcal{A}_{t}^{k}(S^{k}_{t})$
associated with sub-state $S^{k}_{t}$ whenever $i-k\geq 0$. To specify the
learning mechanism, it is convenient to use the Heaviside step function $H(x)$
defined as

$H(x)=\begin{cases}1&\text{ if }x\geq 0\\\ 0&\text{ otherwise}\end{cases}\,.$

To take advantage of this structure, we define two composite versions of the
state-action values:

  1. 1.

The _average composite state-action value_ $\overline{Q}(s,a_{i})$ is defined
as:

$\overline{Q}(s,a_{i}):=\frac{\sum_{k=0}^{d(s)-1}Q(s^{k},a^{k}_{i-k})H(i-k)}{\sum_{k=0}^{d(s)-1}H(i-k)}\,,\quad
i=0,\dots,d(s)\,;$

  2. 2.

_The additive composite state-action value_ $\widetilde{Q}(s,a_{i})$ is
defined as:

$\widetilde{Q}(s,a_{i}):=\sum_{k=0}^{d(s)-1}Q(s^{k},a^{k}_{i-k})H(i-k)\,,\quad
i=0,\dots,d(s)\,;$

The average composite state-action value $\overline{Q}(s,a_{i})$ averages the
state-action values of a state and its sub-states. The Heaviside function
selects the actions that are valid for the sub-states. This quantity will be
used in decision making. The additive composite state action value
$\widetilde{Q}(s,a_{i})$ computes the sum of state-action values from a state
and its associated sub-states. This quantity will be used in the learning
mechanism to implement blocking in a similar way as Rescorla and Wagner
(1972).

####  3.2.2 Updating state-action pairs

We are now in position to explain how state-action values are updated. We
consider two alternative learning rules:

Q-learning:

In this case, state-action values associated with states and sub-states are
updated independently. The updating rule is given by

$Q(S^{k}_{t},a^{k}_{i-k})\leftarrow
Q(S^{k}_{t},a^{k}_{i-k})+\alpha\left[R_{T}-Q(S^{k}_{t},a^{k}_{i-k})\right]H(i-k)\,.$

Rescorla-Wagner Q-learning:

In this case, state-action values associated with states and sub-states are
considered elements of a composite stimulus. The updating rule is given by

$Q(S^{k}_{t},a^{k}_{i-k})\leftarrow
Q(S^{k}_{t},a^{k}_{i-k})+\alpha\left[R_{T}-\widetilde{Q}(S_{t},a_{i})\right]H(i-k)\,.$

In both cases, $R_{T}$ is the reward obtained upon boundary placement and
$\alpha$ is a learning parameter. The update is performed for all time step
$t\in 0,\dots,T$ of the episode and for all sub-states $k\in
0,\dots,d(S_{t})$. These TD algorithms are driven by the error in prediction
of the reward $R_{T}$. The Heaviside function is there to avoid updating an
action that does not exist in a given sub-state. The difference between
Q-learning and Rescorla-Wagner Q-learning, is that in the first case, the
state-action values are used as predictors, whereas in the latter case, we use
the additive composite state-action values.

State-action values are initialized by setting

$Q(S_{t},a_{i})=\begin{cases}q_{b}&\text{if }i=d(S_{t}),\\\
q_{c}&\text{otherwise}\end{cases}\,.$

The parameters $q_{b}$ and $q_{c}$ encode the initial values of placing a
border or choosing a chunking behaviour, respectively.

####  3.2.3 Using state-action pairs to make decisions

In order to choose actions in a given state, $S_{t}$, we use a soft-max
policy. The soft-max policy computes the probability of choosing a given
action using the rule

$\pi(a_{i}|S_{t})=\frac{e^{\beta\overline{Q}(S_{t},a_{i})}}{\sum_{k=0}^{d(S_{t})+1}e^{\beta\overline{Q}(S_{t},a_{k})}}\,,$

where $\beta$ is a parameter controlling the amount of exploration performed
by the model. Note that we use the average composite state-action values
$\overline{Q}(S_{T},a_{i})$ as the support for each action. We want to take
advantage of the internal structure of the state and this is the best way to
avoid creating biases towards one specific behaviour. We use the same policy
for the two possible learning rules mentioned above. Overall, the model has 6
parameters summarized in Table 1.

Parameter | Interpretation
---|---
$\alpha$ | Learning rate
$\beta$ | Exploration parameter
$r_{+}$ | Positive reward
$r_{-}$ | Negative reward
$q_{b}$ | Initial value for border
$q_{c}$ | Initial value for chunking
Table 1: Parameters of the model.

###  3.3 Evaluation methods

To evaluate the performance of the model, we need to assess whether it
successfully learns the input languages and, if so, how quickly. In addition,
we are interested in what grammatical information it extracts. To achieve
these goals, we use learning curves to test the ability of the model to learn
and quantify its speed. Grammatical information is extracted directly from the
state-action values.

####  3.3.1 Extracting learning curves

In order to get a learning curve, we simulate $N$ agents and record for each
episode of the MDP whether the decision was correct or incorrect. We then
compute the fraction of agents being successful at each episode and plot the
fraction of correct responses as a function of the number of episodes of the
MDP that we refer to as _trials_. If all agents eventually learn the language
perfectly, then the fraction of correct responses should go to one.

In order to estimate the learning speed, we fit a logistic curve of the form

$f(x)=\frac{1}{1+e^{-k(x-x_{0})}}\,,$ (2)

that has the two parameters $k$ and $x_{0}$. $k$ is a measure of the stiffness
of the logistic curve and $x_{0}$ corresponds to the parameter where the
function value is $\frac{1}{2}$. We estimate the learning time as $2x_{0}$,
since at the beginning of the simulation the fraction of correct responses is
$0$.

####  3.3.2 Extracting grammatical information

In our model, all grammatical information is encoded in the state-action
values of states and their associated sub-states, i.e. in the $Q$ values. In
order to extract grammatical information, we need to extract for every state
the most likely action to be taken. To do so, we choose a threshold
$0<t_{G}<r_{+}$ and extract all state-action values greater than $t_{G}$ and
interpret them as grammatical information. Of course, state-action with lower
values also constitute grammatical information, but a threshold is necessary
to select data to display. For each state, i.e. for each pairs of chunks, we
then have the most likely action to be taken and its associated value. This
representation of grammatical information does not constitute a standard
grammar, but is instructive for understanding how an agent learns. The
extracted grammatical information is then saved in an Microsoft Excel
spreadsheet. The code of this project as well as all Excel files used in this
project are available online in the GitHub repository:
https://github.com/michaudj/LanguageLearner/.

Since one of the aim of this paper is to open the black box of language
acquisition, we can use this technique of extracting grammatical information
at various stages of the learning process and save them as different sheets in
the Excel file. This allows us to look at how the grammatical information of
an agent changes over time and whether it converges to a systematic
representation.

For more complex languages in which the number of relevant state-action values
is too high, we will provide a more qualitative discussion of the grammatical
information learned.

##  4 Results

In this section, we present the results of our experiments on various
artificial languages. We start by considering a simple language consisting of
nouns (N) and verbs (V) organized in sentences with the structure noun-verb-
noun (NVN), and then move on to consider more complex grammars.

###  4.1 A baseline case: NVN languages

Our baseline case has been chosen to illustrate how the agent learns the
language and will be used to motivate the choice of learning algorithm used
for more complex languages. We start by considering a simple NVN language. Our
language is generated by a PCFG
$G=(\mathcal{M},\mathcal{T},\mathcal{R},\mathcal{S},\mathcal{P})$, where
$\mathcal{M}$ is the set of non-terminal symbols, $\mathcal{T}$ is the set of
terminal symbols, $\mathcal{R}$ is the set of production rules, $\mathcal{S}$
is the start symbol, and $\mathcal{P}$ is the set of probabilities on
production rules.

####  4.1.1 Defining the grammar

For our simple NVN grammar, we use

$\displaystyle\mathcal{M}$ $\displaystyle=\\{S,N,V\\}\,,$
$\displaystyle\mathcal{T}$
$\displaystyle=\\{n_{1},n_{2},\dots,n_{K_{n}}\\}\cup\\{v_{1},v_{2},\dots,v_{K_{v}}\\}\,,$
$\displaystyle\mathcal{S}$ $\displaystyle=S\,,$

where, $K_{n}$ is the total number of nouns and $K_{v}$ is the total number of
verbs. The production rules are:

$R=\left\\{\begin{aligned} S&\to N,V,N\\\ N&\to n_{1}|\ n_{2}|\ n_{3}|\dots\\\
V&\to v_{1}|\ v_{2}|\ v_{3}|\dots\end{aligned}\right\\}$ (3)

and are equiprobable. This means that $S$ always rewrites as $N,V,N$, and the
nouns $N$ rewrites as $n_{i}$, $i\in[1,2,\dots,K_{n}]$ uniformly at random,
and similarly for the verbs.

####  4.1.2 Learning curves

Figure 2: Learning curves for the four combinations of sentence conditions QC,
QN, RWQC, and RWQN. The NVN language has $K_{n}=K_{v}=5$. Fractions are
obtained over 100 agents.

With this NVN language defined, we test the ability of our models to learn
this language using the proposed task. We consider the four cases combining
the definition of Sections 3.1.2 and 3.2.2:

QC:

Q-learning with continuous border condition;

QN:

Q-learning with next sentence border condition;

RWQC:

Rescorla-Wagner Q-learning with continuous border condition;

RWQN:

Rescorla-Wagner Q-learning with next sentence condition.

The value of parameters is the same for all models and provided in column
”value NVN” of Table 2.

Parameter |  Value NVN |  Value MD |  Value RelClause |  Value ComplexNP
---|---|---|---|---
$\alpha$ | 0.1 | 0.1 | 0.1 | 0.1
$\beta$ | 1.9 | 1.0 | 1.0 | 1.0
$r_{+}$ | 25 | 25 | 25 | 25
$r_{-}$ | -10 | -10 | -10 | -10
$q_{b}$ | 1 | 1 | 1 | 1
$q_{c}$ | -1 | -1 | -1 | -1
Table 2: Parameter values for the different languages studied. Algorithm | Learning time
---|---
QC | 927
QN | 402
RWQC | 925
RWQN | 388
Table 3: Learning times of the four learning algorithms for a NVN language
with $K_{n}=K_{v}=5$.

The obtained learning curves are displayed in Fig 2. We see that all variants
of the model successfully learn the language reaching a fraction of correct
responses very close to 1. Using the fit to the logistic curve in Eq. (2), we
estimated the learning times of the four models in Table 3.

We observe that when the next sentence condition is used, learning is faster.
This is not surprising, since the task is easier because only one of the two
boundaries of a sentence has to be identified. With respect to learning times,
there is very little difference between Q-learning and Rescorla-Wagner
Q-learning, which is expected since the two learning algorithms are very
similar. The main difference between these two algorithms is the information
used to drive error-correction, i.e. whether blocking is used or not. This
will be examined below when we look at what is learned at different stages of
the learning process.

####  4.1.3 Grammar extraction and acquisition process

As we have seen above, the performance of Q-learning and Rescorla-Wagner
Q-learning are very similar in terms of learning curve. The question addressed
in this section is what type of grammatical information is extracted and used
by these two learning algorithms and whether the sentence condition affects
what is learned. To achieve this, we report the grammatical information
extracted in terms of the two elements of a state/sub-state, the action with
the highest state-action value. The results are shown in Tables 4 and 5 for
the continuous border condition and are extracted from the two Excel
spreadsheets QLearnerC_paper.xlsx and RWQLearnerC_paper.xlsx available in the
GitHub repository: https://github.com/michaudj/LanguageLearner/. Snapshots are
taken at the beginning of the S-shaped learning curve, when learning fraction
is close to 0.5, when learning is just completed, and at two later points,
when performances are very high. The columns labeled # refer to the number of
states $(s_{1},s_{2})$ matching the pattern. For example, two states
$([n_{2},v_{3}],n_{4})$ and $([n_{1},v_{5}],n_{2})$ have the same structure
and constitute two instances of the $([N,V],N)$ state. The results for the
next sentence condition are similar and can be found in Excel spreasheets
QLearnerN_paper.xlsx and RWQLearnerN_paper.xlsx in the GitHub repository.

Our results show that the Rescorla-Wagner algorithm is much more parsimonious
in the number of state-action values it relies upon. This is best seen by
looking at the number of instances of a given state-action pair reported in
columns ”#” of Tables 4 and 5. While these numbers steadily increase in
Q-learning, only some of them increase in Rescorla-Wagner Q-learning and some
of them even decrease after some time. For example, in the last three rows of
Table 5, the number of instances decreases and even reached 0 for one of them.
This shows that the model learns more specific information than the Q-learning
algorithm. The same can be observed in the averaged state-action values, where
all actions reported increase in value for the Q-learning algorithm, while
only some of them increase for Rescorla-Wagner Q-learning and some even
decrease after some point.

The results for Q-learning suggest that all state-action pairs will eventually
reach the maximum reinforcement value of 25 and the rule will not specify a
preferable tree structure over the sentence. For instance, both $[N,[V,N]]$
and $[[N,V],N]$ tree structure will occur with significant probability. This
grammatical output is not very informative.

The results for Rescorla-Wagner Q-learning suggest that if learning continues
only 4 state-action pairs are relevant for the decision making process:

  1. 1.

Place border between $N$ and $N$;

  2. 2.

Chunk together $N$ and $V$;

  3. 3.

Chunk together $V$ and $N$;

  4. 4.

When $[N,V]$ is followed by $N$, chunk at the deepest level, yielding
$[N,[V,N]]$.

This means that all information about sentence boundary placement is encoded
in the $N-N$ transitions and rules 2, 3, and 4 control the parsing process.
This model seems much more informative about the parsing process and is, in
some sense, minimalist with regard to the information it extracts. Therefore,
we choose Rescorla-Wagner Q-learning for the analysis of more complex sentence
structures.

###  4.2 Towards natural language input

In this section, we will explore how the Rescorla-Wagner Q-learning algorithm
with continuous border condition performs on more complex grammars. We will
consider a number of different grammars. First, we consider a grammar that has
both mono- and ditransitive verbs to show that when $N-N$ transitions are
unreliable to predict sentence transitions, then the model is still able to
perform well. We then increase the complexity of the grammars by either
introducing relative clauses or a number of other adnominal elements. For
these more complex languages, the grammatical information extracted will often
be too big to analyze in a table as we have done for the NVN language.
Instead, we study the learning curve and break it down by sentence length to
get some insight into which sentences are learned first. We then examine some
examples of parsed sentences to show some systematic reuse of identified
structures.

####  4.2.1 Mono and ditransitive verb

We first consider a grammar with both monotransitive verbs (MV), that are
always followed by one noun, and ditransitive verbs (DV), that are always
followed by two nouns. The grammar is defined as follows:

$\displaystyle\mathcal{M}$ $\displaystyle=\\{S,N,MV,DV\\}\,,$
$\displaystyle\mathcal{T}$
$\displaystyle=\\{n_{1},n_{2},\dots,n_{K_{n}}\\}\cup\\{mv_{1},mv_{2},\dots,mv_{K_{m}}\\}\cup\\{dv_{1},dv_{2},\dots,dv_{K_{d}}\\}\,,$
$\displaystyle\mathcal{S}$ $\displaystyle=S\,,$

where, $K_{n}$ is the total number of nouns, $K_{m}$ is the total number of
monotransitive verbs, and $K_{d}$ is the total number of ditransitive verbs.
The production rules are

$\mathcal{R}=\left\\{\begin{aligned} S&\to N,MV,N|\ N,DV,N,N\\\ N&\to n_{1}|\
n_{2}|\ n_{3}|\dots\\\ MV&\to mv_{1}|\ mv_{2}|\ mv_{3}|\dots\\\ DV&\to
dv_{1}|\ dv_{2}|\ dv_{3}|\dots\end{aligned}\right\\}$ (4)

and are equiprobable. This means that $S$ always rewrites as $N,MV,N$ in 50%
of the cases and as $N,DV,N,N$ otherwise. The different word classes rewrites
uniformly as in the NVN language above. We refer to this language as the MD
language.

$s_{1}$ | $s_{2}$ | action | $Q_{300}$ | # | $Q_{600}$ | # | $Q_{900}$ | # | $Q_{2000}$ | # | $Q_{4000}$ | # | Total number
---|---|---|---|---|---|---|---|---|---|---|---|---|---
$N$ | $N$ |  $a_{1}$ (border) | 6.00 | 3 | 11.56 | 24 | 20.70 | 25 | 24.95 | 25 | 25.00 | 25 | 25
$N$ | $V$ |  $a_{0}$ (chunk) | 6.37 | 2 | 11.56 | 23 | 20.45 | 25 | 24.94 | 25 | 25.00 | 25 | 25
$V$ | $N$ |  $a_{0}$ (chunk) | 5.39 | 1 | 11.82 | 14 | 19.73 | 18 | 24.36 | 19 | 24.90 | 19 | 25
$[N,V]$ | $N$ |  $a_{0}$ (chunk at root) | 6.05 | 1 | 7.19 | 13 | 9.03 | 61 | 17.53 | 87 | 23.49 | 87 | 125
$[N,V]$ | $N$ |  $a_{1}$ (chunk deep) | — | — | 6.24 | 12 | 8.69 | 31 | 17.72 | 38 | 23.62 | 38 | 125
$[V,N]$ | $N$ |  $a_{2}$ (border) | 5.56 | 1 | 7.21 | 26 | 9.41 | 70 | 16.76 | 95 | 22.38 | 95 | 125
$[[N,V],N]$ | $N$ |  $a_{2}$ (border) | — | — | 5.80 | 8 | 6.09 | 40 | 7.49 | 150 | 11.61 | 189 | 625
$[N,[V,N]]$ | $N$ |  $a_{3}$ (border) | 5.56 | 1 | 5.86 | 13 | 5.56 | 76 | 7.64 | 318 | 11.55 | 427 | 625
Table 4: Grammar extracted by the Q-learning algorithm with continuous border. Snapshots are taken after 300, 600, 900, 2000, and 4000 trials. The language is a NVN language with $R_{n}=R_{v}=5$ and we used a threshold of $t_{G}=5$. Columns labeled ”$Q_{i}$” report averaged values of $Q((s_{1},s_{2}),a_{j})$ over the number of relevant instances (reported in the # columns) after $i$ trials. The total number column reports the maximum number of instances of the corresponding state-action pairs. $s_{1}$ | $s_{2}$ | action | $Q_{300}$ | # | $Q_{600}$ | # | $Q_{900}$ | # | $Q_{2000}$ | # | $Q_{4000}$ | # | Total number
---|---|---|---|---|---|---|---|---|---|---|---|---|---
$N$ | $N$ |  $a_{1}$ (border) | 5.27 | 1 | 8.48 | 9 | 14.80 | 24 | 20.60 | 25 | 21.33 | 25 | 25
$N$ | $V$ |  $a_{0}$ (chunk) | — | — | 6.92 | 12 | 16.45 | 25 | 24.89 | 25 | 25.00 | 25 | 25
$V$ | $N$ |  $a_{0}$ (chunk) | — | — | 7.75 | 5 | 13.15 | 14 | 19.01 | 17 | 19.14 | 17 | 25
$[N,V]$ | $N$ |  $a_{0}$ (chunk at root) | — | — | 6.66 | 4 | 6.65 | 13 | 6.96 | 19 | 8.57 | 10 | 125
$[N,V]$ | $N$ |  $a_{1}$ (chunk deep) | — | — | 6.31 | 4 | 8.30 | 34 | 17.25 | 56 | 23.14 | 56 | 125
$[V,N]$ | $N$ |  $a_{2}$ (border) | — | — | 6.13 | 4 | 6.91 | 21 | 5.68 | 10 | — | — | 125
$[[N,V],N]$ | $N$ |  $a_{2}$ (border) | — | — | — | — | 6.07 | 9 | 5.67 | 9 | 5.50 | 5 | 625
$[N,[V,N]]$ | $N$ |  $a_{3}$ (border) | — | — | — | — | 5.75 | 7 | 5.97 | 4 | 5.36 | 2 | 625
Table 5: Grammar extracted by the RW Q-learning algorithm with continuous
border. Snapshots are taken after 300, 600, 900, 2000, and 4000 trials. The
language is a NVN language with $R_{n}=R_{v}=5$ and we used a threshold of
$t_{G}=5$. Columns labeled ”$Q_{i}$” report averaged values of
$Q((s_{1},s_{2}),a_{j})$ over the number of relevant instances (reported in
the # columns) after $i$ trials. The total number column reports the maximum
number of instances of the corresponding state-action pairs.

Here, we report results for a MD language with $K_{n}=5$, and $K_{m}=K_{d}=1$.
We simulate the learning using the Rescorla-Wagner Q-learning with continuous
border condition and parameters listed in Table 2 in the ”value MD” column.

Figure 3 reports the learning curve for this language. The first panel
displays the standard learning curve and the second panel shows the learning
curve for different sentence lengths. Sentences of length 3 are monotransitive
sentences and sentences of length 4 are ditransitive sentences. As can be
seen, even when $N-N$ transitions are not a reliable predictor of sentence
boundaries, the learning algorithm still learns to identify sentences. The
second panel shows that monotransitive sentences are learned first and that
there is some interference between the mono- and ditransitive sentences. At
the beginning, monotransitive sentences are quickly learned, but the learning
slows down as the learner figures out how to deal with ditransitive sentences.
After a transition period, both types of sentences are learned. In order to
better understand how the processing is done, we look at snapshots taken
during the learning process. All data is available online in the Excel
spreadsheet RWQLearnerCMD_paper.xlsx stored in the GitHub repository:
https://github.com/michaudj/LanguageLearner/. The results are displayed in
Table 6.

Figure 3: First panel: Learning curve for the Rescorla-Wagner Q-learning with
continuous border condition for the MD language with $K_{n}=5$,
$K_{m}=K_{d}=1$. Fractions are obtained over 200 agents. Second panel,
breakdown of the learning curve by sentence length. Note that if at a given
trial no learner encounter a sentence of a given length, then it contributes
to sentences of length 0, which are, therefore, meaningless.

The first two snapshots show that at this stage of learning, only information
about monotransitive verbs has been learned and decision making relies a lot
on full sentences. However, from trial $3000$, the learner starts to rely more
on shorter chunks in the decision making process. At this point, the learner
starts to have knowledge about ditransitive verbs. At the next snapshot,
learning is complete and we see that now boundary placement essentially relies
on $N-N$ transitions as in the $NVN$ case. The ditransitive case is solved by
using longer chunks containing ditransitive verbs to inhibit border placement
and favor a chunking action instead. But in both sentence structures, border
placement relies on $N-N$ transitions. This is best seen in the last snapshot
where only the $N-N$ transition supports border placements (except for one
instance of monotransitive verb, but this is marginal and can be seen as the
left over of the previously used chunking strategy).

$s_{1}$ | $s_{2}$ | action | $Q_{1000}$ | # | $Q_{1500}$ | # | $Q_{3000}$ | # | $Q_{6000}$ | # | $Q_{25000}$ | # | Total number
---|---|---|---|---|---|---|---|---|---|---|---|---|---
$N$ | $N$ |  $a_{1}$ (border) | — | — | — | — | 11.45 | 6 | 16.30 | 25 | 18.27 | 25 | 25
$N$ | $MV$ |  $a_{0}$ (chunk) | — | — | — | — | 24.65 | 5 | 24.99 | 5 | 25.00 | 5 | 5
$N$ | $DV$ |  $a_{0}$ (chunk) | — | — | — | — | 12.40 | 4 | 24.79 | 5 | 25.00 | 5 | 5
$MV$ | $N$ |  $a_{0}$ (chunk) | — | — | — | — | 15.85 | 4 | 16.04 | 4 | 16.11 | 4 | 5
$DV$ | $N$ |  $a_{0}$ (chunk) | — | — | — | — | 12.32 | 3 | 19.48 | 5 | 19.55 | 5 | 5
$[N,MV]$ | $N$ |  $a_{0}$ (chunk at root) | — | — | 11.22 | 2 | 11.81 | 5 | 12.06 | 5 | 11.60 | 6 | 25
$[N,MV]$ | $N$ |  $a_{1}$ (chunk deep) | — | — | — | — | 21.47 | 11 | 24.99 | 11 | 25.00 | 11 | 25
$[N,DV]$ | $N$ |  $a_{0}$ (chunk at root) | — | — | — | — | 10.51 | 3 | — | — | — | — | 25
$[N,DV]$ | $N$ |  $a_{1}$ (chunk deep) | — | — | — | — | — | — | 23.80 | 1 | 25.00 | 1 | 25
$[MV,N]$ | $N$ |  $a_{2}$ (border) | — | — | — | — | 13.25 | 13 | 10.19 | 1 | — | — | 25
$[DV,N]$ | $N$ |  $a_{0}$ (chunk at root) | — | — | — | — | 10.27 | 3 | 14.84 | 6 | 15.33 | 6 | 25
$[DV,N]$ | $N$ |  $a_{1}$ (chunk deep) | — | — | — | — | 18.31 | 2 | 20.39 | 15 | 19.95 | 16 | 25
$[[N,MV],N]$ | $N$ |  $a_{2}$ (border) | 10.64 | 1 | 12.44 | 4 | 13.14 | 30 | 11.63 | 26 | 14.01 | 1 | 125
$[[N,DV],N]$ | $N$ |  $a_{1}$ (chunk deep) | — | — | — | — | 11.18 | 1 | 15.90 | 8 | 19.85 | 9 | 125
$[N,[MV,N]]$ | $N$ |  $a_{3}$ (border) | — | — | 10.93 | 2 | 11.33 | 5 | — | — | — | — | 125
$[N,[DV,N]]$ | $N$ |  $a_{2}$ (chunk deepest) | — | — | — | — | 10.65 | 3 | 18.18 | 30 | 24.98 | 33 | 125
$[N,[DV,N]]$ | $N$ |  $a_{1}$ (chunk deep) | — | — | — | — | — | — | — | — | 13.68 | 1 | 125
Table 6: Grammar extracted by the RW Q-learning algorithm with continuous
border. Snapshots are taken after 1000, 1500, 3000, 6000, and 25000 trials.
The language is a MD language with $R_{n}=5$, and $R_{m}=R_{d}=1$ and we used
a threshold of $t_{G}=10$. Columns labeled ”$Q_{i}$” report averaged values of
$Q((s_{1},s_{2}),a_{j})$ over the number of relevant instances (reported in
the # columns) after $i$ trials. The total number column reports the maximum
number of instances of the corresponding state-action pairs.

####  4.2.2 Adding relative clauses

The next sentences structure we analyze is relative clauses. We add possible
relative clauses to the MD grammar above, by letting some nouns be followed by
a relative pronoun (Rel), a monotransitive verb and a noun. We choose to only
include monotransitive verbs in relative clauses to avoid a combinatorial
explosion in the output. The grammar is defined as follows:

$\displaystyle\mathcal{M}$ $\displaystyle=\\{S,VP,Rel,N,MV,DV,R\\}\,,$
$\displaystyle\mathcal{T}$
$\displaystyle=\\{n_{1},n_{2},\dots,n_{K_{n}}\\}\cup\\{mv_{1},mv_{2},\dots,mv_{K_{m}}\\}\cup\\{dv_{1},dv_{2},\dots,dv_{K_{d}}\\}\cup\\{r_{1},r_{2},\dots,r_{K_{r}}\\}\,,$
$\displaystyle\mathcal{S}$ $\displaystyle=S\,,$

where, $K_{n}$ is the total number of nouns, $K_{m}$ is the total number of
monotransitive verbs, $K_{d}$ is the total number of ditransitive verbs, and
$K_{r}$ is the number of relative pronouns. The production rules are:

$\mathcal{R}=\left\\{\begin{aligned} S&\to N,VP\\\ VP&\to MV,N|\ DV,N,N|\
MV,N,Rel|\ DV,N,N,Rel\\\ Rel&\to R,MV,N\\\ N&\to n_{1}|\ n_{2}|\
n_{3}|\dots\\\ MV&\to mv_{1}|\ mv_{2}|\ mv_{3}|\dots\\\ DV&\to dv_{1}|\
dv_{2}|\ dv_{3}|\dots\\\ R&\to r_{1}|\ r_{2}|\
r_{3}|\dots\end{aligned}\right\\}$ (5)

and the probabilities of the different production rules for the verb phrase
$VP$ are set to 0.3 for production rules without relative clause and to 0.2
for production rules with relative clause, i.e. $N,MV,N$ occur in 30% of the
time, $N,DV,N,N$ in 30%, $N,MV,N,R,MV,N$ in 20%, and $N,DV,N,N,R,MV,N$ in 20%
of the time. Other production rules are equiprobable. We refer to this
language as the RelClause language.

Here, we report results for a RelClause language with $R_{n}=5$,
$R_{m}=R_{d}=R_{r}=1$. Once again, learning is done using the Rescorla-Wagner
Q-learning algorithm with continuous border condition. Parameters are the same
as in the MD case and displayed in Table 2.

Figure 4: First panel: Learning curve for the Rescorla-Wagner Q-learning with
continuous border condition for the relative clause language with $K_{n}=5$,
$K_{m}=K_{d}=K_{r}=1$. Fractions are obtained over 100 agents. Second panel:
breakdown of the learning curve by sentence length. Note that if at a given
trial no learner encounter a sentence of a given length, then it contributes
to sentences of length 0, which are, therefore, meaningless. Since only a
fraction of learners encounter a sentence of the same length, explaining the
layering structure of the breakdown plot.

The learning curves are displayed in Figure 4. Once again, we see that the
model learns this language without problems. Interestingly, we observe a
U-shaped curve at the beginning of the learning process and we can clearly see
that the learning process is irregular and shows a staircase pattern with a
plateau around trial 15 000. The breakdown into sentence lengths is showing
that at first short sentences are learned well, but then performances decrease
while the system learns to deal with ditransitive structures and relative
clauses. After some delay all longer sentences get learned without significant
delays, pointing out the generalization process over the end of sentences, for
instance, 75% of the sentences end with $MV,N$, making $[MV,N]-N$ transitions
a good predictor of sentence boundaries.

We now take a closer look at the development of the grammatical information of
a single learner by extracting snapshots of its state-action values. Selected
results are displayed in Table 7. Not all constructions are displayed due to
their high number. The display is limited to $s_{1}$ constructions of a
maximum length of $3$ to avoid a combinatorial explosion in the table. The
display is also limited to to constructions that are relatively frequent or
that reach relatively high Q-values. The threshold of the the Q-values of the
displayed structure is set to $tG=4$, lower than previous thresholds, in order
to capture what is going on in the initial U-curve. For full data on all the
state-action values above 4 for this learner are available in the Excel file
RWQLearnerC_rel.xlsx available online in the GitHub repository
https://github.com/michaudj/LanguageLearner/.

In the snapshots we first explore the initial U-shaped curve. We see that in
the peak at $400$ trials, the model has learned to identify one $N,MV,N$
sentence by making two chunkings, and then using both the $N-N$ transition and
the transition between the full sentence and a following $N$ to place a
border. Soon, at $1000$ trials, the model has unlearned to chunk $N-MV$ and to
place border between $N-N$, probably because it using the same strategies in
longer still unknown sentences and fails. It then relies mainly on the full
sentence, that has become difficult to find it when the shorter chunkings are
less likely to happen. The shorter transitions are actually very efficient and
reliable when the learner is more proficient, and we see that they reappear
later, but only around the plateau at $15000$ trials, when the model is
starting to learn to deal with relative clauses. At $700$ trials the U-curve
has turned and we see that the model starts to learn to handle ditransitive
sentences, but it has still not learned to chunk the relative pronoun with
preceding constructions. This implies that it still fails to identify the
sentences of length $6$ and $7$ and is therefore not able to rely on the
shorter constructions that appear in all sentences. At $15000$ trials, the
model has started to identify the relative constructions and this is
important, because this allows for relying on the shorter transitions to a
higher degree. This pattern is strengthened and consolidated at $50000$ trials
when the model has learned to correctly identify the sentences with relative
clauses and thus performs well on the entire language. Once the transition to
the relative clauses is learned, the model learns to recognize the sentences
of length $6$ and $7$ more or less in parallel, as the mono- and ditransitive
constructions are already learned.

As for the full longer sentences, their tree-structures tend to follow some
common patterns at the end of the learning process. The strongest tendency is
to deep chunk all verbs with the following noun in both main and subordinate
clauses, as in the monotransitive example $[N,[MV,[[N,R],[MV,N]]]]$ or the
ditransitive example $[N,[[[DV,N],N],[R,[MV,N]]]]$. This is an efficient re-
use of a recurring structure. Because verbs can be preceded by both nouns and
relative pronouns, it is more efficient to rely only on the verb for chunking
with the following noun than to rely on a chunk that includes one or more
elements that precede the verb. We see in the snapshots that single verbs as
predictors of chunkings with nouns emerge together with the acquisition of
relative constructions at the plateau at $15000$ trials. Just like with the
other shorter constructions, their efficiency as predictors depend to a
certain extent on the learners ability to identify relative clauses and thus
successfully use and re-use them in the longer sentences. The relative
pronouns, on the other hand are always precede by a noun and followed by a
monotransitive verb in this language. This make the strategies to group them
with the preceding noun, as in the first example, or with the following verb,
as in the latter example, equally efficient. This results in a lot of
variation between these strategies.

$s_{1}$ | $s_{2}$ | action | $Q_{400}$ | # | $Q_{1000}$ | # | $Q_{7000}$ | # | $Q_{15000}$ | # | $Q_{50000}$ | # | Total number
---|---|---|---|---|---|---|---|---|---|---|---|---|---
$N$ | $N$ |  $a_{1}$ (border) | 4.81 | 1 | — | — | — | — | 14.15 | 25 | 16.87 | 25 | 25
$N$ | $MV$ |  $a_{0}$ (chunk) | 6.22 | 1 | — | — | — | — | 24.58 | 5 | 24.53 | 5 | 5
$N$ | $DV$ |  $a_{0}$ (chunk) | — | — | — | — | — | — | 16.00 | 5 | 24.94 | 5 | 5
$N$ | $R$ |  $a_{0}$ (chunk) | — | — | — | — | — | — | 12.56 | 4 | 16.82 | 4 | 5
$MV$ | $N$ |  $a_{0}$ (chunk) | — | — | — | — | — | — | 19.43 | 5 | 23.05 | 5 | 5
$DV$ | $N$ |  $a_{0}$ (chunk) | — | — | — | — | — | — | 18.59 | 5 | 17.43 | 5 | 5
$R$ | $MV$ |  $a_{0}$ (chunk) | — | — | — | — | — | — | 20.20 | 1 | 22.47 | 1 | 1
$[N,MV]$ | $N$ |  $a_{0}$ (chunk at root) | — | — | — | — | 5.61 | 6 | 5.35 | 14 | — | — | 25
$[N,MV]$ | $N$ |  $a_{1}$ (chunk deep) | 7.80 | 1 | — | — | — | — | 4.02 | 1 | 25.00 | 1 | 25
$[N,DV]$ | $N$ |  $a_{0}$ (chunk at root) | — | — | — | — | 5.24 | 1 | 7.87 | 23 | 7.48 | 25 | 25
$[N,N]$ | $N$ |  $a_{2}$ (border) | — | — | — | — | 4.25 | 1 | 5.95 | 43 | 4.51 | 22 | 125
$[R,MV]$ | $N$ |  $a_{1}$ (chunk deep) | — | — | — | — | — | — | — | — | 23.13 | 1 | 5
$[MV,N]$ | $N$ |  $a_{2}$ (border) | — | — | 4.06 | 1 | 4.75 | 4 | 10.06 | 25 | 5.81 | 22 | 25
$[MV,N]$ | $R$ |  $a_{0}$ (chunk at root) | — | — | — | — | — | — | 10.59 | 4 | 8.00 | 2 | 5
$[MV,N]$ | $R$ |  $a_{1}$ (chunk deep) | — | — | — | — | — | — | 7.21 | 1 | 20.54 | 1 | 5
$[DV,N]$ | $N$ |  $a_{0}$ (chunk at root) | — | — | — | — | — | — | 15.55 | 15 | 18.14 | 15 | 25
$[DV,N]$ | $N$ |  $a_{0}$ (chunk deep) | — | — | — | — | — | — | 16.63 | 9 | 18.58 | 11 | 25
$[[N,MV],N]$ | $N$ |  $a_{2}$ (border) | 5.28 | 1 | 5.33 | 7 | 7.35 | 22 | 8.18 | 25 | 6.68 | 25 | 125
$[N,[MV,N]]$ | $N$ |  $a_{3}$ (border) | — | — | — | — | 6.87 | 16 | 7.15 | 84 | — | — | 125
$[N,[MV,N]]$ | $R$ |  $a_{1}$ (chunk deep) | — | — | — | — | — | — | 5.44 | 3 | 4.46 | 5 | 25
$[N,[MV,N]]$ | $R$ |  $a_{2}$ (chunk deepest) | — | — | — | — | — | — | 6.97 | 1 | 25.00 | 2 | 125
$[N,[DV,N]]$ | $N$ |  $a_{1}$ (chunk deep) | — | — | — | — | — | — | 8.14 | 25 | 5.52 | 43 | 125
$[N,[DV,N]]$ | $N$ |  $a_{2}$ (chunk deepest) | — | — | — | — | — | — | 8.08 | 18 | 25.00 | 19 | 125
$[MV,[N,R]]$ | $MV$ |  $a_{1}$ (chunk deep) | — | — | — | — | — | — | — | — | 13.36 | 2 | 5
$[MV,[N,R]]$ | $MV$ |  $a_{2}$ (chunk deepest) | — | — | — | — | — | — | — | — | 20.90 | 1 | 5
$[[DV,N],N]$ | $N$ |  $a_{3}$ (border) | — | — | — | — | 5.10 | 3 | — | — | 5.53 | 57 | 125
$[[DV,N],N]$ | $R$ |  $a_{1}$ (chunk deep) | — | — | — | — | — | — | — | — | 20.00 | 2 | 25
$[DV,[N,N]]$ | $N$ |  $a_{3}$ (border) | — | — | — | — | 4.25 | 1 | 7.08 | 46 | 4.60 | 25 | 125
$[DV,[N,N]]$ | $R$ |  $a_{2}$ (chunk deepest) | — | — | — | — | — | — | 5.38 | 4 | 21.00 | 5 | 25
Table 7: Grammar extracted by the RW Q-learning algorithm with continuous
border. Snapshots are taken after 400, 1000, 7000, 15000, and 50000 trials.
The language is a MD language with $R_{n}=5$, and $R_{m}=R_{d}=1$ and we used
a threshold of $t_{G}=4$. Columns labeled ”$Q_{i}$” report averaged values of
$Q((s_{1},s_{2}),a_{j})$ over the number of relevant instances (reported in
the # columns) after $i$ trials. The total number column reports the maximum
number of instances of the corresponding state-action pairs.

####  4.2.3 Complexifying NPs

In this section, instead of adding relative clauses to the noun phrase (NP),
we add andvary several shorter adnominal elements see how the model handles
these more complex and variable NPs. We add determiners (D) and one or two
adjectives (A) before the noun, and prepositional phrases consisting of a
preposition (P) and a noun after the noun. The language we use is specified
by:

$\displaystyle\mathcal{M}$ $\displaystyle=\\{S,NP,VP,N,MV,DV,A,D,P\\}\,,$
$\displaystyle\mathcal{T}$
$\displaystyle=\\{n_{1},n_{2},\dots,n_{K_{n}}\\}\cup\\{mv_{1},mv_{2},\dots,mv_{K_{m}}\\}\cup\\{dv_{1},dv_{2},\dots,dv_{K_{v}}\\}\cup\\{a_{1},a_{2},\dots,a_{K_{r}}\\}$
$\displaystyle\cup\\{a_{1},a_{2},\dots,a_{K_{a}}\\}\cup\\{d_{1},d_{2},\dots,d_{K_{d}}\\}\cup\\{p_{1},p_{2},\dots,p_{K_{p}}\\}\,,$
$\displaystyle\mathcal{S}$ $\displaystyle=S\,,$

where, $K_{n}$ is the total number of nouns, $K_{m}$ is the total number of
monotransitive verbs, $K_{v}$ is the total number of ditransitive verbs,
$K_{a}$ is the number of adjectives, $K_{d}$ is the number of determiners, and
$K_{p}$ is the number of prepositions. The production rules are

$\mathcal{R}=\left\\{\begin{aligned} S&\to NP,VP\\\ NP&\to N|\ D,N|\ D,A,N|\
D,A,A,N|\ N,P,N\\\ VP&\to MV,NP|\ DV,NP,NP\\\ N&\to n_{1}|\ n_{2}|\
n_{3}|\dots\\\ MV&\to mv_{1}|\ mv_{2}|\ mv_{3}|\dots\\\ DV&\to dv_{1}|\
dv_{2}|\ dv_{3}|\dots\\\ A&\to a_{1}|\ a_{2}|\ a_{3}|\dots\\\ D&\to d_{1}|\
d_{2}|\ d_{3}|\dots\\\ P&\to p_{1}|\ p_{2}|\
p_{3}|\dots\end{aligned}\right\\}\,,$ (6)

where all productions rules are equiprobable except for NPs which rewrite
according to the following probabilities:

  * •

$NP\to N$: 0.25

  * •

$NP\to D,N$: 0.25

  * •

$NP\to D,A,N$: 0.1875

  * •

$NP\to D,A,A,N$: 0.0625

  * •

$NP\to N,P,N$: 0.25

This means that double adjectives are less common than single adjective NPs,
and NP with adjectives are as common as other NP production rules. We refer to
this language as a ComplexNP language.

Here, we report result for a ComplexNP language with
$K_{n}=K_{m}=K_{v}=K_{a}=K_{d}=K_{p}=1$. This language contains 150 different
sentence structures, which is much more than the 4 possibilities of the
RelClause language above. This is why we restrict the analysis to a smaller
vocabulary. Figure 5 displays the learning curve for that language. We again
used the Rescorla-Wagner Q-learning algorithm with continuous border
condition. As we can see, the learner successfully learns this language but as
in the RelClause language, the learning curve does not follow a standard
S-shaped curve. The fit to the logistic is thus imperfect to capture the
learning time. We chose not to display the breakdown of the learning curve by
sentence length because many different sentence structures are of the same
length, for example, compare the sentences $D,N,MV,N$, to $N,DV,N,N$. Both
have length 4, and there are other structures of length 4, such as $N,MV,D,N$.
This ambiguity is even stronger for longer sentences, which justifies only
displaying the overall learning curve.

Figure 5: Learning curve for the Rescorla-Wagner Q-learning with continuous
border condition for the ComplexNP language with
$K_{n}=K_{m}=K_{v}=K_{a}=K_{d}=K_{p}=1$. Fractions are obtained over 100
agents.

Figure 5 is characterized by an irregular learning curve, where short plateaus
can be seen. The learning curve displays a period of quick learning following
by a period of slow learning. Why this pattern occurs is unclear, but to get
an idea of how the sentences are processed, we study one specific learner and
record the sentences correctly identified between trial 500 000 and trial 1
000 000, i.e. after learning is complete. Due to the large number of possible
sentences, we only study 5 sentence structures, those starting with
$D,A,N,DV,D,A,N$, i.e. ditransitive sentences in which the first two NPs
rewrite as $D,A,N$. Data for these 5 sentences as well as other structures is
available in the Excel spreadsheet sentencesCompNP_paper.xlsx in the GitHub
repository https://github.com/michaudj/LanguageLearner/. For these five
sentence structures, we report the frequency of each tree structure in Table
8. Looking at the most frequent structures, we observe that they are very
similar. Compare the most likely structure for the first and third sentences
in the table. The structures are $[[D,A],[[N,[DV,[[D,A],N]]],N]]$ and
$[[D,A],[[N,[DV,[[D,A],N]]],[[N,P],N]]]$, which only differ in the parse of
the last NP where $N$ is replaced by $[[N,P],N]$. Similar analysis holds for
the three other sentences, which shows the high reuse of extracted
information.

Sentence | Tree structure | Frequency
---|---|---
$D,A,N,DV,D,A,N,N$ | $[[D,A],[[N,[DV,[[D,A],N]]],N]]$ | 0.62
| $[[D,A],[[N,[DV,[D,[A,N]]]],N]]$ | 0.17
| $[[[D,A],[N,[[DV,D],[A,N]]]],N]$ | 0.17
| $[[D,A],[N,[[DV,D],[[A,N],N]]]]$ | 0.04
$D,A,N,DV,D,A,N,D,N$ | $[[D,A],[N,[[[DV,[[D,A],N]],D],N]]]$ | 0.55
| $[[[D,A],[N,[[DV,[D,[A,N]]],D]]],N]$ | 0.16
| $[[D,A],[N,[[[DV,D],[A,N]],[D,N]]]]$ | 0.10
| $[[D,A],[N,[[DV,[[D,A],N]],[D,N]]]]$ | 0.06
| $[[D,A],[[N,[[[DV,D],[A,N]],D]],N]]$ | 0.05
| $[[D,A],[N,[[DV,D],[[A,N],[D,N]]]]]$ | 0.03
| $[[D,A],[[N,[DV,[[D,A],[N,D]]]],N]]$ | 0.02
| $[[D,A],[N,[[[DV,D],[[A,N],D]],N]]]$ | 0.02
| $[[D,A],[N,[[DV,[D,[[A,N],D]]],N]]]$ | 0.01
| $[[D,A],[N,[[DV,D],[A,[[N,D],N]]]]]$ | 0.01
$D,A,N,DV,D,A,N,N,P,N$ | $[[D,A],[[N,[DV,[[D,A],N]]],[[N,P],N]]]$ | 0.49
| $[[[D,A],[N,[[DV,D],[A,N]]]],[[N,P],N]]$ | 0.18
| $[[D,A],[[N,[DV,[D,[A,N]]]],[[N,P],N]]]$ | 0.15
| $[[D,A],[[[N,[DV,[[D,A],N]]],[N,P]],N]]$ | 0.08
| $[[D,A],[[N,[DV,[[D,A],N]]],[N,[P,N]]]]$ | 0.04
| $[[D,A],[[N,[[DV,D],[[A,N],N]]],[P,N]]]$ | 0.03
| $[[D,A],[[N,[DV,[D,[A,N]]]],[N,[P,N]]]]$ | 0.02
| $[[D,A],[N,[[DV,D],[[A,N],[[N,P],N]]]]]$ | 0.01
$D,A,N,DV,D,A,N,D,A,N$ | $[[D,A],[[N,[[[DV,[[D,A],N]],D],A]],N]]$ | 0.56
| $[[D,A],[N,[[[[DV,[D,[A,N]]],D],A],N]]]$ | 0.09
| $[[D,A],[N,[[[[DV,D],[A,N]],D],[A,N]]]]$ | 0.09
| $[[D,A],[N,[[[DV,[D,[A,N]]],D],[A,N]]]]$ | 0.07
| $[[D,A],[N,[[[DV,[[D,A],N]],[D,A]],N]]]$ | 0.05
| $[[D,A],[N,[[[DV,D],[A,N]],[[D,A],N]]]]$ | 0.05
| $[[D,A],[[N,[[DV,D],[[A,N],D]]],[A,N]]]$ | 0.04
| $[[[D,A],[N,[DV,[[D,A],[N,D]]]]],[A,N]]$ | 0.02
| $[[D,A],[N,[[DV,[[D,A],N]],[[D,A],N]]]]$ | 0.01
| $[[D,A],[N,[[DV,[D,[A,N]]],[[D,A],N]]]]$ | 0.01
| $[[D,A],[N,[[[DV,D],[A,N]],[D,[A,N]]]]]$ | 0.01
$D,A,N,DV,D,A,N,D,A,A,N$ | $[[D,A],[[N,[[[DV,[[D,A],N]],D],[A,A]]],N]]$ | 0.45
| $[[D,A],[N,[[[DV,[D,[A,N]]],D],[[A,A],N]]]]$ | 0.15
| $[[D,A],[N,[[[[DV,[[D,A],N]],D],A],[A,N]]]]$ | 0.09
| $[[D,A],[[N,[[DV,[[D,A],N]],[[D,A],A]]],N]]$ | 0.06
| $[[D,A],[N,[[[DV,D],[A,N]],[[[D,A],A],N]]]]$ | 0.06
| $[[D,A],[N,[[[[DV,D],[A,N]],D],[[A,A],N]]]]$ | 0.06
| $[[D,A],[[N,[[DV,D],[[A,N],D]]],[[A,A],N]]]$ | 0.04
| $[[D,A],[N,[[[DV,[D,[A,N]]],D],[A,[A,N]]]]]$ | 0.03
| $[[[D,A],[N,[DV,[[D,A],[N,D]]]]],[[A,A],N]]$ | 0.02
| $[[D,A],[N,[[DV,[D,[A,N]]],[[D,A],[A,N]]]]]$ | 0.01
Table 8: Sample of parses of sentences from the ComplexNP language. We report
only the parses of sentences starting by $D,A,N,DV,D,A,N$. The second column
shows the possible tree structures and the last column report frequencies
between the 500 000 and the 1 000 000 trials

Another thing we can discuss it the parsimony of the grammatical information
extracted. Although there are many different structures available in this
table, the number of possible tree structures is actually a lot larger. It is
given by the Catalan number $C_{n-1}=\frac{1}{n}\binom{2(n-1)}{n-1}$ for a
sentence of length $n$. This means that for a sentence of length $8$ such as
the first sentence of Table 8 there are $C_{7}=429$ different tree structures,
which is much larger than the 4 listed above. The same argument holds for
longer sentences. We have about $10$ tree structures for the other sentences,
but the Catalan number increases extremely rapidly. In fact, we have
$C_{8}=1430$, $C_{9}=4862$, $C_{10}=16796$, which means that the 10 tree
structures for the last sentence are among the $16796$ possibilities.

##  5 Discussion

Our results show that our model is able to identify and re-use chunks of
information that facilitates language learning, thus in a simplified manner
accounting for the emergence of grammar during learning. For a simple language
only containing the sentence structure noun-verb-noun, we see that the model
is able to efficiently avoid the combinatorial explosion that comes with
recognizing each sentence individually by only relying on noun-noun
transitions to identify sentence borders. In a slightly extended language with
both mono- and ditransitive verbs, containing the sentence structures noun-
verb-noun and noun-verb-noun-noun, the noun-noun transition is no longer a
reliable cue to sentence borders. The model then learns to use the information
in the ditransitive verbs to avoid border placement between the nouns
following them, and keeps the noun-noun transition as support for border
placement in all other cases. The model is also able to learn languages with
extended complexity, including relative clauses and noun phrases with
determiners, adjectives and prepositional phrases. In these languages, that
include many common structures of natural languages, we see how the model
gradually learns to identify and re-use sequences of words that often occur
together, like verbs and following nouns, or elements of noun phrases, thus
reproducing empirical observations of natural language acquisition, where
structures are initially acquired by learning frequency-based multi-word
sequential chunks Tomasello (2005); Tomasello, Kuhn, and Siegler (2008); Bybee
(2002b); Arnon and Clark (2011). This re-use of learned information results in
high parsimony in the emergent tree-structures, where only a tiny fraction of
all the possible tree structures actually occur. Studying learning curves and
snapshots from our models’ acquisition of different languages also show that
shorter sentences are acquired earlier than longer, similarly to natural
language acquisition Hoff and Shatz (2009). Furthermore, in la language with
relative clauses we see an interesting development where the model initially
learns to rely on some frequent noun-verb and noun-noun transitions for
identifying sentences, and then over-uses this knowledge before it has
identified longer less frequent constructions or the transition to relative
clauses. The model thus reproduces a U-shaped curve that can be compared to
those resulting from over-regularization of many different kinds that
typically occur in early phases of language acquisition Bowerman (1982);
Plunkett and Marchman (2020); Marcus et al. (1992); Ramscar, Dye, and McCauley
(2013)

Another interesting result concerns the use of the blocking mechanism inspired
by the Rescorla-Wagner model when learning to respond to a hierarchical
structure. It is well-observed that when animals learn to respond to compound
stimuli containing one known element that is sufficient for making a good
decision, they do not update any stimulus-response associations for the other
elements in the compound, thus blocking unnecessary learning about new stimuli
Rescorla and Wagner (1972). Here we apply the same principle when our model is
exposed to a hierarchical structure where one state can contain many dependent
sub-states, with possibilities to recruit information from all levels. A state
with one or more sub-states can be compared to a compound stimulus. We tested
the model without blocking, i.e. reinforcing the state-action values for all
levels in the hierarchy separately and with blocking, where all levels are
reinforced jointly. We found that blocking leads to a more parsimonious
grammar and seems to be a more efficient strategy for extracting relevant
information from linguistic input, since the more informative levels are
allowed to block the reinforcement of less informative levels.

Our cognitive architecture uses the framework of Markov Decision Processes.
This framework can be related to memory systems and other cognitive theories.
We can interpret the state-action values as representing the long-term memory
of the learners. Information about action selection during an episode of the
Markov Decision Process Sutton and Barto (2018) constitute the short-term
memory. States, sub-states and the selected actions are stored and manipulated
during the processing of a sentence and this information is used for decision-
making and reinforcement. This processing system resembles what Baddeley calls
the Central Executive in his model of the working memory Baddeley, Eysenck,
and Anderson (2015). Furthermore, the limited access to information in the
working memory is compatible with the chunk-and-pass principle of Christiansen
and Chater (2016b) and mirrors the memory limitations discussed in Cowan
(2001); Miller (1956). All these aspects of our model stresses its cognitive
plausibility and highlight its minimalist nature.

The architecture we present and its learning conditions are radically
different from those of LLMs, both in terms of the size of the training data
and in terms of the length of the strings that are used as input, that are
both very limited in our case. Furthermore, our model operationalizes usage-
based language learning Bybee (2006); Ellis, O’Donnell, and Römer (2015);
Tomasello (2003), where learning and use occur in parallel, which is not
generally the case for LLMs. Our minimal temporal difference model is also
different from neural networks in general, as it aims at maximal simplicity.
This makes results easier to trace and interpret, and it also enables us to
make as few assumptions as possible and see how far they can take us in
understanding the human language learning process. Our results indicate that
limiting working memory and training data may be cues to understanding human
language learning, as our model learns to find the shortest and most
informative chunks as a strategy to overcome these constraints. Our results
also indicate that a limited sequence memory combined with chunking, are
central components that may be sufficient to learn language.

Our model is limited by the lack of generalization and abstraction, preventing
it from scaling to larger languages. We see that learning times increase
exponentially when increasing the size of the vocabulary or the complexity of
the artificial languages. While our results provide an initial proof of
concept that the minimal cognitive architecture we present suffices for
extracting grammatical information, future studies should explore
generalization to generate abstract categories that would enable testing the
model on larger languages and eventually apply it to natural languages.
Emergent abstract categories would then be expected to resemble grammatical
categories like word classes or syntactic constituents. Error-correction
models have previously successfully accounted for the emergence of phones
Milin, Tucker, and Divjak (2023) and the learning of regular and irregular
morphological forms Ramscar, Dye, and McCauley (2013); MacWhinney et al.
(1989) in a human-like manner from exposure to limited parts of language that
are relevant to these tasks. The modeling of the emergence of syntactic
categories is arguably a more challenging and more interesting problem, as it
needs to involve tracing relationships between words and constituents at
different levels, and requires exposure to a somewhat complete language. A
generalization system in our model should generalize over the information that
the model uses, i.e. information about sequences and chunks, as we have done
manually to report the results in this study. One way of implementing this is
using the mathematical theory of type systems, being the simplest mathematical
framework for handling ordering, composition and abstraction of things Heunen,
Sadrzadeh, and Grefenstette (2013), thus incorporating the features sequence
memory, chunking, and schematizing. In generative linguistics, an application
of this framework is made in the theory of syntactic types Lambek (1958). A
pilot study, where the theory of syntactic types is modified to be dynamic and
compatible with usage-based learning, shows that functional abstract
categories can emerge for short sentences Jon-And and Michaud (2023),
indicating that this is a promising framework for further development.

Another limitation of our model is that it only considers syntax and not
semantics or meaning. This complicates the learning task since, meaning of
words highly constrain the possible parsing of a sentence. Form-meaning
pairings are considered fundamental for usage-based learning and the
compatible framework of construction grammar Langacker (2002); Goldberg
(2007). In LLMs, even though words are not mapped onto real-world meanings,
meaning can be represented in a distributional sense, and this has been shown
to be important for their performance Piantasodi and Hill (2022); Manning et
al. (2020). This distributional, text-related sense of meaning could be
implemented in a minimalist model like ours and would likely be a key for it
to perform well on natural language corpora. A further possible future
development of our model would be to use the emergent grammar it abstracts for
linguistic production, and to let production and feedback to production be
part of the learning process. This would be an important progress towards
testing the models ability to account for the complete language acquisition
process. There are still quite a few steps that needs to be taken to achieve
this, but our initial results motivate further development and exploration of
this minimal cognitive architecture.

## Acknowledgments

We thank our colleagues at the Centre for Cultural Evolution, Stockholm
University for all inspiring and helpful discussions. This work was supported
by the Swedish Research Council (VR 2022-02737).

## References

  * Amalric et al. (2017) Amalric, Marie, Liping Wang, Pierre Pica, Santiago Figueira, Mariano Sigman, and Stanislas Dehaene. 2017.  The language of geometry: Fast comprehension of geometrical primitives and rules in human adults and preschoolers.  _PLoS computational biology_ , 13(1):e1005273.
  * Arnon and Clark (2011) Arnon, Inbal and Eve V Clark. 2011.  Why brush your teeth is better than teeth–children’s word production is facilitated in familiar sentence-frames.  _Language Learning and Development_ , 7(2):107–129.
  * Baddeley, Eysenck, and Anderson (2015) Baddeley, Alan, Michael W Eysenck, and Michael C Anderson. 2015.  _Memory_.  Psychology Press.
  * Baxter et al. (2006) Baxter, Gareth J, Richard A Blythe, William Croft, and Alan J McKane. 2006.  Utterance selection model of language change.  _Physical Review E_ , 73(4):046118.
  * Beltagy, Peters, and Cohan (2020) Beltagy, Iz, Matthew E Peters, and Arman Cohan. 2020.  Longformer: The long-document transformer.  _arXiv preprint arXiv:2004.05150_.
  * Bod (2006) Bod, Rens. 2006.  An all-subtrees approach to unsupervised parsing.  In _Proceedings of the 21st International Conference on Computational Linguistics and 44th Annual Meeting of the Association for Computational Linguistics_ , pages 865–872.
  * Bolhuis et al. (2014) Bolhuis, Johan J, Ian Tattersall, Noam Chomsky, and Robert C Berwick. 2014.  How could language have evolved?  _PLoS biology_ , 12(8):e1001934.
  * Booij (2010) Booij, Geert. 2010.  Construction morphology.  _Language and linguistics compass_ , 4(7):543–555.
  * Bouton (2016) Bouton, M. E. 2016.  _Learning and behavior: A contemporary synthesis_ , 2nd edition.  Sinauer.
  * Bowerman (1982) Bowerman, Melissa. 1982.  Starting to talk worse: Clues to language acquisition from children’s late speech errors.  In _U shaped behavioral growth_. Academic Press, pages 101–145.
  * Brown et al. (2020) Brown, Tom, Benjamin Mann, Nick Ryder, Melanie Subbiah, Jared D Kaplan, Prafulla Dhariwal, Arvind Neelakantan, Pranav Shyam, Girish Sastry, Amanda Askell, et al. 2020.  Language models are few-shot learners.  _Advances in neural information processing systems_ , 33:1877–1901.
  * Bybee (2002a) Bybee, Joan. 2002a.  Phonological evidence for exemplar storage of multiword sequences.  _Studies in second language acquisition_ , 24(2):215–221.
  * Bybee (2002b) Bybee, Joan. 2002b.  Sequentiality as the basis of constituent structure.  _The evolution of language out of pre-language_ , 53:109–134.
  * Bybee (2006) Bybee, Joan. 2006.  From usage to grammar: The mind’s response to repetition.  _Language_ , pages 711–733.
  * Bybee (1985) Bybee, Joan L. 1985.  _Morphology: A study of the relation between meaning and form_.  John Benjamins Publishing.
  * Chomsky (1957) Chomsky, N. 1957.  _Syntactic structures_.  Mouton, The Hague/Paris.
  * Chomsky (1959) Chomsky, Noam. 1959.  On certain formal properties of grammars.  _Information and control_ , 2(2):137–167.
  * Chomsky (2002) Chomsky, Noam. 2002.  _Syntactic structures_.  Mouton de Gruyter.
  * Christiansen and Arnon (2017) Christiansen, Morten H and Inbal Arnon. 2017.  More than words: The role of multiword sequences in language learning and use.  _Topics in cognitive science_ , 9(3):542–551.
  * Christiansen and Chater (2016a) Christiansen, Morten H and Nick Chater. 2016a.  _Creating language: Integrating evolution, acquisition, and processing_.  MIT Press.
  * Christiansen and Chater (2016b) Christiansen, Morten H and Nick Chater. 2016b.  The now-or-never bottleneck: A fundamental constraint on language.  _Behavioral and brain sciences_ , 39.
  * Christiansen and Kirby (2003) Christiansen, Morten H and Simon Kirby. 2003.  Language evolution: Consensus and controversies.  _Trends in cognitive sciences_ , 7(7):300–307.
  * Christiansen and MacDonald (2009) Christiansen, Morten H and Maryellen C MacDonald. 2009.  A usage-based approach to recursion in sentence processing.  _Language Learning_ , 59:126–161.
  * Christophe et al. (2008) Christophe, Anne, Séverine Millotte, Savita Bernal, and Jeffrey Lidz. 2008.  Bootstrapping lexical and syntactic acquisition.  _Language and speech_ , 51(1-2):61–75.
  * Cornish et al. (2017) Cornish, Hannah, Rick Dale, Simon Kirby, and Morten H Christiansen. 2017.  Sequence memory constraints give rise to language-like structure through iterated learning.  _PloS one_ , 12(1):e0168532.
  * Cowan (2001) Cowan, Nelson. 2001.  The magical number 4 in short-term memory: A reconsideration of mental storage capacity.  _Behavioral and brain sciences_ , 24(1):87–114.
  * Croft (2001) Croft, William. 2001.  _Radical construction grammar: Syntactic theory in typological perspective_.  Oxford University Press on Demand.
  * Croft and Cruse (2004) Croft, William and D Alan Cruse. 2004.  _Cognitive linguistics_.  Cambridge University Press.
  * Ellis et al. (2018) Ellis, Kevin, Lucas Morales, Mathias Sablé-Meyer, Armando Solar-Lezama, and Josh Tenenbaum. 2018.  Learning libraries of subroutines for neurally–guided bayesian program induction.  _Advances in Neural Information Processing Systems_ , 31.
  * Ellis, O’Donnell, and Römer (2015) Ellis, Nick C, Matthew Brook O’Donnell, and Ute Römer. 2015.  Usage-based language learning.  _The handbook of language emergence_ , pages 163–180.
  * Enquist, Ghirlanda, and Lind (2023) Enquist, Magnus, Stefano Ghirlanda, and Johan Lind. 2023.  _The Human Evolutionary Transition: From Animal Intelligence to Culture_.  Princeton University Press.
  * Enquist, Lind, and Ghirlanda (2016) Enquist, Magnus, Johan Lind, and Stefano Ghirlanda. 2016.  The power of associative learning and the ontogeny of optimal behaviour.  _Royal Society open science_ , 3(11):160734.
  * Frank, Bod, and Christiansen (2012) Frank, Stefan L, Rens Bod, and Morten H Christiansen. 2012.  How hierarchical is language use?  _Proceedings of the Royal Society B: Biological Sciences_ , 279(1747):4522–4531.
  * Ghirlanda, Lind, and Enquist (2017) Ghirlanda, Stefano, Johan Lind, and Magnus Enquist. 2017.  Memory for stimulus sequences: a divide between humans and other animals?  _Open Science_ , 4(6):161011.
  * Goldberg (2007) Goldberg, A.E. 2007.  _Constructions at work : the nature of generalization in language_.  Oxford linguistics. Oxford University Press.
  * Goodman et al. (2008) Goodman, Noah D, Joshua B Tenenbaum, Jacob Feldman, and Thomas L Griffiths. 2008\.  A rational analysis of rule-based concept learning.  _Cognitive science_ , 32(1):108–154.
  * Goodman, Tenenbaum, and Gerstenberg (2014) Goodman, Noah D, Joshua B Tenenbaum, and Tobias Gerstenberg. 2014.  Concepts in a probabilistic language of thought.  Technical report, Center for Brains, Minds and Machines (CBMM).
  * Haselgrove (2016) Haselgrove, Mark. 2016.  Overcoming associative learning.  _Journal of Comparative Psychology_ , 130(3):226.
  * Heunen, Sadrzadeh, and Grefenstette (2013) Heunen, Chris, Mehrnoosh Sadrzadeh, and Edward Grefenstette. 2013.  _Quantum physics and linguistics: a compositional, diagrammatic discourse_.  Oxford University Press, USA.
  * Heyes (2012a) Heyes, Cecilia. 2012a.  Simple minds: a qualified defence of associative learning.  _Philosophical Transactions of the Royal Society B: Biological Sciences_ , 367(1603):2695–2703.
  * Heyes (2012b) Heyes, Cecilia. 2012b.  What’s social about social learning?  _Journal of comparative psychology_ , 126(2):193.
  * Heyes (2018) Heyes, Cecilia. 2018.  _Cognitive gadgets: the cultural evolution of thinking_.  Harvard University Press.
  * Hochmann, Azadpour, and Mehler (2008) Hochmann, Jean-Rémy, Mahan Azadpour, and Jacques Mehler. 2008.  Do humans really learn anbn artificial grammars from exemplars?  _Cognitive science_ , 32(6):1021–1036.
  * Hoff and Shatz (2009) Hoff, Erika and Marilyn Shatz. 2009.  _Blackwell handbook of language development_.  John Wiley & Sons.
  * Jon-And et al. (2023) Jon-And, Anna, Markus Jonsson, Johan Lind, Stefano Ghirlanda, and Magnus Enquist. 2023.  Sequence representation as an early step in the evolution of language.  _PLoS computational biology_.
  * Jon-And and Michaud (2020) Jon-And, Anna and Jérôme Michaud. 2020.  Minimal prerequisites for processing language structure: A model based on chunking and sequence memory.  In _EvoLang XIII, 14-17 April 2020, Brussels, Belgium_.
  * Jon-And and Michaud (2023) Jon-And, Anna and Jérôme Michaud. 2023.  Emergent grammar from a minimal cognitive architecture.  To be published in: EvoLang XV, 18-21 May 2024, Madison, USA.
  * Klein and Manning (2002) Klein, Dan and Christopher D Manning. 2002.  A generative constituent-context model for improved grammar induction.  In _Proceedings of the 40th Annual Meeting of the Association for Computational Linguistics_ , pages 128–135.
  * Kolodny and Edelman (2018) Kolodny, Oren and Shimon Edelman. 2018.  The evolution of the capacity for language: the ecological context and adaptive value of a process of cognitive hijacking.  _Philosophical Transactions of the Royal Society B: Biological Sciences_ , 373(1743):20170052.
  * Kolodny, Edelman, and Lotem (2015) Kolodny, Oren, Shimon Edelman, and Arnon Lotem. 2015.  Evolution of protolinguistic abilities as a by-product of learning to forage in structured environments.  _Proceedings of the Royal Society B: Biological Sciences_ , 282(1811):20150353.
  * Lambek (1958) Lambek, Joachim. 1958.  The mathematics of sentence structure.  _The American Mathematical Monthly_ , 65(3):154–170.
  * Langacker (1987) Langacker, Ronald W. 1987.  _Foundations of cognitive grammar: Volume I: Theoretical prerequisites_ , volume 1.  Stanford university press.
  * Langacker (2002) Langacker, Ronald W. 2002.  _Concept, image, and symbol_.  Walter de Gruyter Inc.
  * Liang et al. (2023) Liang, Xinnian, Bing Wang, Hui Huang, Shuangzhi Wu, Peihao Wu, Lu Lu, Zejun Ma, and Zhoujun Li. 2023.  Unleashing infinite-length input capacity for large-scale language models with self-controlled memory system.  _arXiv preprint arXiv:2304.13343_.
  * Lind (2018) Lind, Johan. 2018.  What can associative learning do for planning?  _Royal Society open science_ , 5(11):180778.
  * Lind et al. (2023) Lind, Johan, Vera Vinken, Markus Jonsson, Stefano Ghirlanda, and Magnus Enquist. 2023.  A test of memory for stimulus sequences in great apes.  _Plos one_ , 18(9):e0290546.
  * MacDonald (1993) MacDonald, Suzanne E. 1993.  Delayed matching-to-successive-samples in pigeons: Short-term memory for item and order information.  _Animal Learning & Behavior_, 21(1):59–67.
  * MacWhinney et al. (1989) MacWhinney, Brian, Jared Leinbach, Roman Taraban, and Janet McDonald. 1989.  Language learning: Cues or rules?  _Journal of Memory and language_ , 28(3):255–277.
  * Manning et al. (2020) Manning, Christopher D, Kevin Clark, John Hewitt, Urvashi Khandelwal, and Omer Levy. 2020.  Emergent linguistic structure in artificial neural networks trained by self-supervision.  _Proceedings of the National Academy of Sciences_ , 117(48):30046–30054.
  * Marcus et al. (1992) Marcus, Gary F, Steven Pinker, Michael Ullman, Michelle Hollander, T John Rosen, Fei Xu, and Harald Clahsen. 1992.  Overregularization in language acquisition.  _Monographs of the society for research in child development_ , pages i–178.
  * McCauley and Christiansen (2019) McCauley, Stewart M and Morten H Christiansen. 2019.  Language learning as language use: A cross-linguistic model of child language development.  _Psychological review_ , 126(1):1.
  * Michaud (2019) Michaud, Jérôme. 2019.  Dynamic preferences and self-actuation of changes in language dynamics.  _Language Dynamics and Change_ , 9(1):61 – 103.
  * Milin, Tucker, and Divjak (2023) Milin, Petar, Benjamin V. Tucker, and Dagmar Divjak. 2023.  A learning perspective on the emergence of abstractions: the curious case of phone(me)s.  _Language and Cognition_ , page 1–23.
  * Miller (1956) Miller, George A. 1956.  The magical number seven, plus or minus two: Some limits on our capacity for processing information.  _Psychological review_ , 63(2):81.
  * Newell (1994) Newell, Allen. 1994.  _Unified theories of cognition_.  Harvard University Press.
  * Nowak, Komarova, and Niyogi (2002) Nowak, Martin A., Natalia L. Komarova, and Partha Niyogi. 2002.  Computational and evolutionary aspects of language.  _Nature_ , 417(6889):611–617.
  * Piantadosi (2023) Piantadosi, ST. 2023.  Modern language models refute chomsky’s approach to language.  _Lingbuzz Preprint, lingbuzz_ , 7180.
  * Piantadosi, Tenenbaum, and Goodman (2016) Piantadosi, Steven T, Joshua B Tenenbaum, and Noah D Goodman. 2016.  The logical primitives of thought: Empirical foundations for compositional cognitive models.  _Psychological review_ , 123(4):392.
  * Piantasodi and Hill (2022) Piantasodi, Steven T and Felix Hill. 2022.  Meaning without reference in large language models.  _arXiv preprint arXiv:2208.02957_.
  * Pinker and Jackendoff (2005) Pinker, Steven and Ray Jackendoff. 2005.  The faculty of language: what’s special about it?  _Cognition_ , 95(2):201–236.
  * Planton et al. (2021) Planton, Samuel, Timo van Kerkoerle, Leïla Abbih, Maxime Maheu, Florent Meyniel, Mariano Sigman, Liping Wang, Santiago Figueira, Sergio Romano, and Stanislas Dehaene. 2021.  A theory of memory for binary sequences: Evidence for a mental compression algorithm in humans.  _PLoS computational biology_ , 17(1):e1008598.
  * Plunkett and Marchman (2020) Plunkett, Kim and Virginia Marchman. 2020.  U-shaped learning and frequency effects in a multilayered perceptron: Implications for child language acquisition.  _Connectionist Psychology_ , pages 487–526.
  * Ramscar, Dye, and McCauley (2013) Ramscar, Michael, Melody Dye, and Stewart M McCauley. 2013.  Error and expectation in language learning: The curious absence of” mouses” in adult speech.  _Language_ , pages 760–793.
  * Read, Manrique, and Walker (2021) Read, Dwight W, Héctor M Manrique, and Michael J Walker. 2021.  On the working memory of humans and great apes: Strikingly similar or remarkably different?  _Neuroscience & Biobehavioral Reviews_.
  * Reali and Griffiths (2009) Reali, Florencia and Thomas L Griffiths. 2009.  The evolution of frequency distributions: Relating regularization to inductive biases through iterated learning.  _Cognition_ , 111(3):317–328.
  * Rescorla and Wagner (1972) Rescorla, R. A. and A. R Wagner. 1972.  A theory of Pavlovian conditioning: Variations in the effectiveness of reinforcement and nonreinforcement.  In _Classical conditioning: current research and theory_. Appleton-Century-Crofts, pages 64–69.
  * Roberts and Grant (1976) Roberts, W. A. and D. S. Grant. 1976.  Studies of short-term memory in the pigeon using the delayed matching to sample procedure.  In R.T. Davis D.L. Medin, W.A. Roberts, editor, _Processes of animal memory,_. Erlbaum, Hillsdale, NJ, pages 79–112.
  * Rule et al. (2018) Rule, Joshua, Eric Schulz, Steven T Piantadosi, and Joshua B Tenenbaum. 2018.  Learning list concepts through program induction.  _BioRxiv_ , page 321505.
  * Rule, Tenenbaum, and Piantadosi (2020) Rule, Joshua S, Joshua B Tenenbaum, and Steven T Piantadosi. 2020.  The child as hacker.  _Trends in cognitive sciences_ , 24(11):900–915.
  * Servan-Schreiber and Anderson (1990) Servan-Schreiber, Emile and John R Anderson. 1990.  Learning artificial grammars with competitive chunking.  _Journal of Experimental Psychology: Learning, Memory, and Cognition_ , 16(4):592.
  * Steels and Loetzsch (2012) Steels, Luc and Martin Loetzsch. 2012.  The grounded naming game.  _Experiments in cultural language evolution_ , 3:41–59.
  * Sutton and Barto (2018) Sutton, Richard S and Andrew G Barto. 2018.  _Reinforcement learning: An introduction_.  MIT press.
  * Thompson, Kirby, and Smith (2016) Thompson, Bill, Simon Kirby, and Kenny Smith. 2016.  Culture shapes the evolution of cognition.  _Proceedings of the National Academy of Sciences_ , 113(16):4530–4535.
  * Tomasello (2003) Tomasello, Michael. 2003.  _Constructing a language: A usage-based theory of language acquisition_.  Harvard University Press.
  * Tomasello (2005) Tomasello, Michael. 2005.  _Constructing a language: A usage-based theory of language acquisition_.  Harvard university press.
  * Tomasello, Kuhn, and Siegler (2008) Tomasello, Michael, D Kuhn, and R Siegler. 2008.  Acquiring linguistic constructions.  _Child and adolescent development_ , page 263.
  * Udden et al. (2012) Udden, Julia, Martin Ingvar, Peter Hagoort, and Karl M Petersson. 2012.  Implicit acquisition of grammars with crossed and nested non-adjacent dependencies: Investigating the push-down stack model.  _Cognitive Science_ , 36(6):1078–1101.
  * Ullman, Goodman, and Tenenbaum (2012) Ullman, Tomer D, Noah D Goodman, and Joshua B Tenenbaum. 2012.  Theory learning as stochastic search in the language of thought.  _Cognitive Development_ , 27(4):455–480.
  * Valian et al. (2013) Valian, Virginia, M Sanz, I Laka, and M Tanenhaus. 2013.  Determiners: An empirical argument for innateness.  _Language down the garden path: The cognitive and biological basis for linguistic structure_ , pages 272–279.
  * Vaswani et al. (2017) Vaswani, Ashish, Noam Shazeer, Niki Parmar, Jakob Uszkoreit, Llion Jones, Aidan N Gomez, Łukasz Kaiser, and Illia Polosukhin. 2017.  Attention is all you need.  _Advances in neural information processing systems_ , 30.
  * van der Velde et al. (2017) van der Velde, Frank, Jamie Forth, Deniece S Nazareth, and Geraint A Wiggins. 2017\.  Linking neural and symbolic representation and processing of conceptual structures.  _Frontiers in psychology_ , 8:1297.
  * Warstadt and Bowman (2022) Warstadt, Alex and Samuel R Bowman. 2022.  What artificial neural networks can tell us about human language acquisition.  In _Algebraic Structures in Natural Language_. CRC Press, pages 17–60.
  * Wasserman, Kain, and O’Donoghue (2023) Wasserman, Edward A, Andrew G Kain, and Ellen M O’Donoghue. 2023.  Resolving the associative learning paradox by category learning in pigeons.  _Current biology_ , 33(6):1112–1116.
  * Wiggins (2020) Wiggins, Geraint A. 2020.  Creativity, information, and consciousness: the information dynamics of thinking.  _Physics of life reviews_ , 34:1–39.
  * Yang and Piantadosi (2022) Yang, Yuan and Steven T Piantadosi. 2022.  One model for the learning of language.  _Proceedings of the National Academy of Sciences_ , 119(5):e2021865119.