# Fort Formation by an Automaton

Kartikey Kant  Indian Institute of Technology Guwahati
Guwahati, India
<EMAIL_ADDRESS>Debasish Pattanayak  Indian Statistical Institute
Kolkata, India
<EMAIL_ADDRESS>Partha Sarathi Mandal  Indian Institute of Technology
Guwahati
Guwahati, India
<EMAIL_ADDRESS>
###### Abstract

Building structures by low capability robots is a very recent research
development [3]. A robot (or a mobile agent) is designed as a deterministic
finite automaton. The objective is to make a structure from a given
distribution of materials (bricks) in an infinite grid $Z\times Z$. The grid
cells may contain a brick (full cells) or it may be empty (empty cells). The
field, a sub-graph induced by the full cells, is initially connected. At a
given point in time, a robot can carry at most one brick. The robot can move
in four directions (north, east, south, and west) and starts from a full cell.
The Manhattan distance between the farthest full cells is the span of the
field. We consider the construction of a fort, a structure with the minimum
span and maximum covered area. On a square grid, a fort is a hollow rectangle
with bricks on the perimeter. We show that the construction of such a fort can
be done in $O(z^{2})$ time – with a matching lower bound $\Omega(z^{2})$ –
where $z$ is the number of bricks present in the environment.

###### Index Terms:

Automaton, Programmable Matter, Fort Formation, Infinite Grid, Mobile Robots.

##  I Introduction

###  I-A The Problem

Czyzowicz et al. [3] have initiated a study on building structures by a robot
(or mobile agent) designed as a deterministic finite automaton in an infinite
grid with materials. The motivation behind building such a structure stems
from many areas, such as the demarcation of land using a robot in inaccessible
areas or building structures in space where the materials are limited. In
these cases, it is important to utilize the available resources to their
complete capacity. This paper explores how a connected structure can be formed
enclosing the maximum possible area with a given number of bricks. We denote
the resulting structure as a fort.

###  I-B Environment Model

We are given an infinite oriented grid $Z\times Z$, which can be viewed as a
grid of cells in a two-dimensional plane, with the cells having either
horizontal or vertical common edges. Thus, each cell can have four adjacent
cells to its North, East, South, and West. We denote a cell having a brick as
a full cell and a cell without a brick as an empty cell. The sub-graph induced
by the full cells is called a field. Initially, the field is connected, i.e.,
there exists a rectilinear path between any two full cells, which consists of
full cells. However, after operations by the robot, the field may get
disconnected. The maximally connected sub-graph of a field is called its
component. The number of cells in a field is called its size and the maximum
Manhattan distance111Manhattan distance between two cells at $(x,y)$ and
$(x^{\prime},y^{\prime})$ is $\lvert x-x^{\prime}\rvert+\lvert
y-y^{\prime}\rvert$. between two cells in a field is called its span.

###  I-C Robot Model

The robot starts at one of the full cells. It can move in one of the four
directions (East, North, West, or South) from a cell. It is oriented towards
one of the directions, and when we say the robot turns left, it reorients
itself locally (A robot facing north turns left to face west). It can only
observe the state of its current cell, i.e., the cell contains a brick or not.
It can pick up a brick from a full cell and drop the brick in an empty cell.
It can move with or without carrying a brick (makes the robots light or
heavy). It can carry at most one brick at once. The robot can move through
full cells while carrying a brick. It is formalized as a Mealy automaton
$\mathcal{R}=(X,Y,\mathsection,\delta,\lambda,S_{0},S_{f})$, where
$X=\\{e,f\\}\times\\{l,h\\}$ is the input,
$Y=\\{N,E,S,W\\}\times\\{e,f\\}\times\\{l,h\\}$ is the output, $\mathsection$
is the set of states, $\lambda$ is the transition function with $S_{0}$ as
initial state and $S_{f}$ as the final state. The alphabet denote the
following in order: $N$ : North, $E$: East, $S$: South, $W$: West, $e$: empty
cell, $f$: full cell, $l$: light robot (not carrying a brick), $h$: heavy
robot (carries a brick). The state of the robot contains its current
orientation, the current cell’s status, and if the robot carries a brick. We
follow the same model for the robot introduced by Czyzowicz et al. [3]. The
robot has a very limited amount of memory, which maintains the set of states.
Even with limited memory, it can perform a bounded exploration up to a small
distance (say 8) and keep the state of the cells encoded in its states. In
other words, at any point in time, the robot can have information about all
the cells at a distance at most $8$ from its current cell.

###  I-D Target Structure

The largest connected structure with the maximum enclosed area in a square
grid is a hollow rectangle, i.e., the bricks are only on the sides of the
rectangle. The target is to construct this hollow rectangle – denoted as fort
– using the bricks available. A perfect fort is the fort having all its sides
made up of an equal number of bricks. The manhattan distance between the
diagonally opposite bricks is the span of the fort. This span will always be
an even number for a perfect fort. For a perfect fort, it is easy to deduce
the relation $z=2s^{\prime}$ where $z$ is the total number of bricks in the
fort, and $s^{\prime}$ is the span of the fort. The fort, shown in Fig. 2, is
an example of a perfect fort. A perfect fort contains $4m$ bricks, where each
wall of the fort contains $m+1$ bricks. Note that the bricks at the corner are
shared by two walls. Any fort consisting of odd number of bricks is a rough
fort (ref. Fig. 6(b), (d), (f) and (h)). The rough fort is a rectangle where
an additional brick may be attached to one of its corners since the number of
bricks is odd.

###  I-E Challenge

Designing algorithms for a low memory robot with minimal capability is
challenging, given the absence of the information. If the robot has sufficient
memory, it suffices to keep track of the entire structure of the field by
doing a simple zig-zag exploration and build any structure. Due to the lack of
memory, the robot can neither remember its past actions nor the positions of
the bricks in the infinite grid. Since the grid does not have any markers, it
is easy for a robot to get lost, and systematic exploration of an infinite
grid is impossible with limited memory [1]. It is also important to keep track
of the state of the structure and achieve termination after all bricks have
been used by the robot.

###  I-F Our Contribution

We consider the problem of the construction of a fort with a finite automaton
in an infinite square grid. Specifically, we show that

  * •

any algorithm that builds a fort from a given initial connected field of span
$s=O(\sqrt{z})$ and size, $z$ must use at least $\Omega(z^{2})$ time.

  * •

Algorithm 7 BuildFort builds a fort from a given initial connected field of
span $s$ and size $z$ in $O(z^{2})$ time. Hence, our algorithm is optimal.

###  I-G Related Works

Many problems with robots or mobile agents exploring an unknown environment
have been studied over the years [4, 6]. The studies can broadly be
categorized in two ways based on the environment in which the robot operates;
it can be a network designed as a graph along the edges of which the robot
moves, or it can be a geographical terrain that might be filled with
obstacles. A problem of pattern formation has been studied in [5] and [10]. It
discusses robots that can freely move in the plane, arrange themselves in a
pattern given as an input. In these studies, the robots are asynchronous and
have full visibility of each others’ positions. Programmable particles modeled
as automatons are also considered in the literature [9, 7, 8]. Luna et al. [9]
considered shape formation by a set of programmable particles in a triangular
grid. With faulty particles, Luna et al. [7] showed the recovery of a line in
a triangular grid. The graph exploration problem can have two different
scenarios depending on whether the nodes have a unique label or not. In the
former case, the robot can identify different labels and thus uniquely
identify each node. In our case, the grid is anonymous, so it is similar to an
undirected anonymous graph. Such graph exploration problems have also been
discussed [2, 3].

###  I-H Organization

The rest of the paper is organized as the following. In Section II, we prove a
lower bound to build a fort. In Section III, we present an algorithm that
builds the fort with Section IV proving the correctness and determining the
complexity of the algorithm. Finally Section V concludes the paper.

##  II Lower Bound to Build a Fort

In this section, we prove the lower bound for the formation of a fort from an
initially connected field to be $\Omega(z^{2})$, where $z$ is the number of
bricks. We show this lower bound by converting a configuration of bricks in a
rough disc to a fort. A rough disc is an arrangement of bricks such that the
distance from any brick on the boundary from a center brick is either $r$ or
$r+1$, where $r$ is the radius (measured with Manhattan distance) of the rough
disc as shown in Fig. 1(a). A perfect disc has all the bricks on the boundary
at a distance $r$ from the center.

Figure 1: A rough disc and a fort

###### Theorem II.1

There exists an initial field of size $z$ and span $s=O(\sqrt{z})$ such that
any algorithm that builds a fort starting from this field must use time
$\Omega(z^{2})$.

###### Proof:

Consider a rough disc $D_{1}$ with $z$ bricks and radius $r\geq 9$. Then $z$
satisfies $z_{1}\leq z<z_{2}$, where $z_{1}=2r^{2}+2r+1$ and
$z_{2}=2r^{2}+4r+2~{}(=2r^{2}+2r+1+2r+1)$. The span of this initial
arrangement of bricks is $s=2r$ and $z=O(r^{2})$, so we have $s=O(\sqrt{z})$.
Consider the two opposite walls of the resulting fort. The distance between
the two opposite walls is $z/4$, and there are at least $z/4$ bricks on each
wall. Suppose the bricks in $D_{1}$ are at a distance $k$ from one wall, then
they are at a distance at least $z/4-k-s$ from the opposite wall. Now, the
bricks would occupy their target position on one of the walls. So at least
$z/4$ bricks would move a distance $k^{\prime}=\max(k,z/4-k-s)$. Since
$s=O(\sqrt{z})$, we have $k^{\prime}\geq z/10$ for $z\geq 100$. Any algorithm
must move at least $z/4$ bricks by a distance $z/10$ and must use
$\Omega(z^{2})$ time to build the fort. ∎

Note that the span of the resulting fort is $O(z)$. Also, the maximum span of
the initial configuration can be at most $z$.

##  III Fort Formation

Figure 2: A fort with 8 bricks, the marker and a free component. The cell
labeled F is the first cell of the fort and the cell labeled M is the marker.

The algorithm for fort formation works like the following. The robot first
creates two special components, the marker and the first cell of the fort, to
initiate the construction of the fort (ref. Fig. 2). Any other component is
called a free component. A marker is used to determine when the robot is in
the vicinity of the fort. The marker is always positioned closer to the fort
and farther from the free component. The construction of a fort constitutes of
four main steps:

  1. 1.

create enough area for the fort to extend

  2. 2.

pick a brick from the field

  3. 3.

bring the brick back to the fort

  4. 4.

add the brick to the fort to extend it

To achieve this goal, we use three procedures developed by Czyzowicz et al.
[3] for nest formation as subroutine for fort formation, that are Sweep,
FindNextBrick and ReturnToMarker. We present a summary of those subroutines
and refer the reader to the paper by Czyzowicz et al. [3] for more details.

  1. Sweep:

This procedure is called every time a brick is added to the structure starting
from the first brick. As the name suggests, in this procedure, the robot
sweeps the bricks nearby the structure to a distance such that there is enough
space to build the structure. Specifically, the robot makes a counterclockwise
traversal of the fort and checks for full cells at a distance at most seven
from the fort, which is not part of the fort. It finds an empty cell at a
distance at least seven from the fort, which is in a direction away from the
fort and places the brick that it has picked from the full cell. This
procedure may create multiple components. The components are created at a
distance of seven while the robot has information about all the bricks up to
distance eight; hence all the components remain accessible. At the end of the
procedure, the marker is placed at a distance three from the fort and a
distance four from a component.

  2. FindNextBrick:

Once the first cell of the fort is established, we need to add bricks to the
fort to make it larger. This procedure finds the next brick that is to be
added to the fort. It performs a switch-traversal of a search-walk in one of
the components until it reaches a leaf cell222A full cell with exactly one
adjacent cell and then picks the brick at the leaf cell. If it does not reach
a leaf cell at the end of the search walk, it performs shifting to get a free
brick.

  3. ReturnToMarker:

After the robot picks the free brick, it performs a reverse switch-traversal.
It reaches near the marker at the end of the reverse switch-traversal, and
then it returns to the marker.

Procedure 1 Sweep

1:$M$ = Marker

2:if the robot is at $M$ then

3: go to the first cell of the fort $F$

4:end if

5:perform a full counterclockwise direction of the border of $F$, perform the
following actions after every step:

6:for each full cell $c\notin F\cup\\{M\\}$ at distance at most 7 from the
robot do

7: $c^{\prime}$ = the cell currently occupied by the robot

8: go to $c$ and pick the brick

9: move in direction away from $F$ and stop at the first empty cell at
distance at least 7 from $F$

10: drop and brick and return to $c^{\prime}$

11:end for

12:if there exists a free component $C$ then

13: pick the brick from marker and place it at distance $3$ from the first
cell of $F$ and at distance $4$ from $C$, creating a new marker

14:end if

15:go to the new marker

Procedure 2 FindNextBrick

1:$W$ = the search walk that starts at the cell where the robot is located

2:go to the nearest cell belonging to a free component

3:perform a switch-traversal of $W$

4:if the robot is at the a leaf then

5: pick the brick

6:else

7: perform shifting

8:end if

Procedure 3 ReturnToMarker

1:$W$ = the search walk traversed in the last cell to FindNextBrick

2:let $S_{1},S_{2},\cdots,S_{l}$ be the segments in $W$

3:if the robot is at the first cell of $S_{l}$ then

4: turn towards the penultimate cell of $S_{l-1}$

5: move $min\\{2,|S_{l-1}|-1\\}$ cells forward

6: if $|S_{l-1}|=2$ and $l>2$, then make a turn towards the penultimate cell
of $S_{l-2}$

7:end if

8:starting at the current location, perform a switch-traversal of $\psi(W)$

9:go to the marker

In Example 1, we describe the switch traversal of a field and how the robot
obtains a free brick to bring back to the marker. We consider a simple
example. There can be much more complicated cases.

Figure 3: (a) The search-walk $\mathcal{W}$ starts at $w_{1}$, follows a left-
free segment to $w_{4}$, and a right free segment up to the leaf node at
$w_{7}$. (b) Switch traversal moves the brick at $f_{6}$ to $e_{6}$. (c) The
robot picks the brick at leaf cell $w_{7}$. (d) The robot performs switch
traversal on the reverse search walk of $\mathcal{W}$ to return to $w_{1}$.

###### Example 1

Consider a field, as shown in Fig. 3(a). The robot starts at $w_{1}$ and
facing north. The robot starts with a left-oriented traversal. It moves
straight until it is possible to move left and then it turns left. After the
turn, it switches its orientation to the right and moves straight until it is
possible to move right. The search walk $\mathcal{W}$ starts at $w_{1}$ with a
left-free segment $S_{1}=(w_{1},w_{2},w_{3},w_{4})$ and then a right-free
segment $S_{2}=(w_{4},w_{5},w_{6},w_{7})$ which ends at the leaf cell $w_{7}$.
Observe that, for the walk to proceed further, the robot has to turn right at
$w_{7}$ or go straight, but there are no full cells after $w_{7}$. The robot
performs a switch traversal, as shown in Fig. 3(b), and arrives at $w_{7}$. To
keep track of the path it has traversed, it converts the left-free segments
into right-free segments and vice versa. As shown in Fig. 3(b), it moves the
brick from left to right from $f_{6}$ to $e_{6}$. Now, the reverse of the
segment $S_{2}$ becomes a right-free segment starting from $w_{7}$. As per
Fig. 3(c), it picks up the leaf cell at $w_{7}$ and turns around to reach
$w_{6}$. Finally, while the robot performs the reverse search walk, it
restores the brick from $e_{6}$ to $f_{6}$, and the connectivity of the
component is reestablished. Thus we pick a brick from the component and arrive
at the starting point $w_{1}$.

Figure 4: (a) The search-walk $\mathcal{W}$ starts at $w_{1}$, follows a left-
free segment to $w_{4}$, and a right free segment up to the corner at $w_{6}$.
(b) The robot picks the brick at leaf cell $w_{6}$ and performs shifting by
moving the brick at $w_{5}$ to $e_{5}$.

In the next call to FindNextBrick, the robot will again perform a switch
traversal and arrive at $w_{6}$ as shown in Fig. 4(a). Now, it cannot turn
right at $w_{6}$. So, the robot has to pick a brick from there, since the
position of a leaf node may not be close to $w_{6}$. To get a free brick, the
performs shifting after picking the brick at $w_{6}$. In shifting, the robot
moves $w_{5}$ to $e_{5}$ and reaches $w_{4}$ carrying a brick as shown in Fig.
4(b). It makes sure that the component remains connected while a free brick is
obtained by the robot, and then it performs a reverse switch traversal to
return to $w_{1}$. It obtains a brick at the end of the traversal. ∎

###  III-A Constructing the Fort

As described in Example 1, the Procedure 1 (Sweep), Procedure 2
(FindNextBrick) and Procedure 3 (ReturnToMarker) work in tandem to provide a
free brick. Next, we describe the construction of the fort as we add bricks
one by one to extend the structure. The robot carrying a free brick arrives at
a marker after ReturnToMarker. From the marker, the robot comes to the first
cell of the fort and invokes Procedure 4 (ExtendFort). Until the size of the
fort is $4$, the robot follows a strict rule of adding bricks to the fort in
the manner shown in Figure 5.

Figure 5: The first four stages of construction of a fort where the newly
added brick in each step is marked with a red shade.

These configurations are handled when the value of the variable $stage=0$.
Once the fourth brick is added, the value of $stage$ becomes $1$. Now the
bricks are added in a manner that the resulting configuration is similar after
every four steps. This can be seen in Figure 6.

Figure 6: The repeating configurations where (a), (e) and (i) are perfect
forts; (c) and (g) are rectangular forts; (b), (d), (f) and (h) are rough
forts. Procedure 4 ExtendFort

1:Arrive at the first cell of the fort oriented to east

2:if $stage=0$ then

3: if $counter=1$ then

4: Place the brick in the front

5: Increase $counter$ by 1

6: else if $counter$ is 2 then

7: Move one step forward

8: Place brick on the right

9: Increase $counter$ by 1

10: else if $counter$ is 3 then

11: Place the brick on the right

12: Increase $counter$ by 1

13: Increase $stage$ by 1

14: end if

15:else

16: if $counter$ is 0 then

17: Call TraverseWall

18: Drop Brick in Front

19: Increase $counter$ by 1

20: else if $counter$ is 1 then

21: Call TraverseWall

22: Move one step back

23: Turn Right

24: Call ShiftBricks

25: Increase $counter$ by 1

26: else if $counter$ is 2 then

27: Call TraverseWall

28: Turn Right

29: Call TraverseWall

30: Drop Brick in front

31: Increase $counter$ by 1

32: else if $counter$ is 3 then

33: Call TraverseWall

34: Turn Right

35: Call TraverseWall

36: Move one step back

37: Turn Right

38: Call ShiftBricks

39: Increase $counter$ by 1

40: end if

41:end if

42:$counter\leftarrow counter$ mod $4$

43:Call Sweep

In ExtendFort, one should note that turning right means the robot orients
itself in the direction which is to its right originally. The same goes for
turning around and turning left.

A configuration of the fort is controlled by the variables $stage$ and
$counter$. Depending on this configuration, the robot, starting from the first
cell, traverses the perimeter of the fort and extends the fort. Sometimes, it
needs to shift the bricks to the left. It does this by dropping the brick it
currently carries to the left, picking the brick from the current cell, and
moving forward. After adding the brick and changing the variables accordingly
and Sweep is called.

Procedure ExtendFort invokes Procedure 5 (TraverseWall) and Procedure 6
(ShiftBricks). In TrverseWall, the robot moves along the wall of the fort
until it reaches the end of the wall. In ShiftBricks, the robot shifts the
bricks of the wall outwards. Since we traverse the walls of the fort in a
clockwise manner, ShiftBricks always moves the bricks to the left of it.

Procedure 5 TraverseWall

1:while the cell in front is full do

2: move one step forward

3:end while

Procedure 6 ShiftBricks

1:while the cell in front is full do

2: move one step forward

3: drop the brick on the left

4: if the cell in front is full then

5: pick the brick from the current cell

6: end if

7:end while

###  III-B Algorithm BuildFort

This section describes Algorithm 7 (BuildFort) for the robot to build a fort
from a given initial connected field. First, the robot points out the marker
and the first cell of the fort. Then Sweep is called to create space for fort
formation, and the variables are declared. The robot brings bricks one by one
and adds them to the fort to extend it. At last, the robot brings the brick to
the marker and adds it to the fort.

Algorithm 7 BuildFort

1:if the span of the field is at most 2 then

2: exit

3:end if

4:the cell occupied by the robot is at the marker.

5:a full cell at distance 2 from the marker becomes the first cell of the fort
(i.e., the north-west corner cell of the fort)

6:Call Sweep

7:Set $counter=1$

8:Set $stage=0$

9:while there exists a free component C do

10: Call FindNextBrick

11: Call ReturnToMarker

12: Call ExtendFort

13:end while

14:pick the marker and add it using ExtendFort

##  IV Correctness and Complexity

To prove the correctness of the procedures, we will define a few terms first.
A fort has a gap of width k if each free component is at a distance $k+1$ from
the fort. A field is structured if it satisfies the following conditions:

  * •

the marker is at a distance three from the first cell of the fort and a
distance four from some free component.

  * •

the fort has a gap of width seven.

If a component is at a distance larger than $7$ from the fort, it is called a
lost component. A field is strongly structured if it satisfies the following
conditions:

  * •

the field is structured

  * •

there are no lost components

  * •

the robot is at the marker.

###  IV-A Correctness

We refer the reader to the paper by Czyzowicz et al. [3] for the correctness
of the procedures Sweep, FindNextBrick, and ReturnToMarker. After execution of
Sweep, the robot moves the bricks nearby the fort to a distance at least 7 to
create space for expansion. The robot takes the bricks from full cells within
distance seven from the fort and drops them in an empty cell next to a full
cell so that the brick remains part of a free component which is at most
distance seven from the fort. This may result in multiple components, but
Sweep ensures that there are no lost components and properly repositions the
marker such that a free component can always be found for the robot to execute
FindNextBrick on the free component. We state the following lemma.

###### Lemma IV.1

Sweep results in a strongly structured field. [3]

Next, we show the correctness of procedures ShiftBricks, ExtendFort before
showing the correctness of Algorithm BuildFort.

###### Lemma IV.2

Procedure ShiftBricks correctly shifts the bricks on one wall of the fort
outwards apart from the first and last brick of that wall.

###### Proof:

The robot carrying a brick has three different situations when Procedure
ShiftBricks is invoked. It shifts all the bricks to the left of its current
orientation until it encounters an empty cell. In Fig. 7(a), the robot carries
a brick. Since the cell in front of the robot is not an empty cell, it moves
forward and drops the brick on its left, as shown in Fig. 7(b). Now it picks
up the brick from its current cell, and the resulting configuration of bricks
looks like Fig. 7(c). Finally, the procedure terminates when it encounters an
empty cell as per Fig. 7(d) and places the brick to its left and does not pick
up the brick in its current cell. Note that the configurations of bricks in
Fig. 7(a) and Fig. 7(d) correspond to a rough fort with an odd number of
bricks and a rectangular fort.

Figure 7: An execution of Procedure ShiftBricks

If the cell in front of the current cell of the robot is empty, then the
condition on line 1 of Procedure 6 returns false, and the procedure
terminates. If the first cell of the wall has an empty cell in front of it
along the robot’s orientation, it is also the last. If the first cell has a
full cell in front, then line 2 gets executed, and the cell moves forward
without picking the brick from the first cell of the row. Hence the first cell
of the row is not shifted. This is due to the fact that the cell to the left
of the first cell is full, and ShiftBricks is invoked to align the wall with
the cell to its left.

The robot moves one cell forward according to line 2, and this cell contains a
brick as it satisfied the condition in line 1. Now the brick is dropped to the
left as per line 3 and will be the new wall. Since ShiftBricks is invoked
after Sweep, the left cell would be empty since there is a gap of width seven
from any nearest component. Hence it can drop the brick it is carrying on its
left in line 3 correctly. Now, since the robot does not carry any brick, it
can pick the brick from the current cell if the condition in line 4 is
satisfied, i.e., the robot is not at the last cell of the wall. Only the last
cell of the wall will not have a full cell in the front, and thus all the
cells of the wall will shift one cell to the left except the last one. ∎

In the following lemma, we prove the correctness of ExtendFort.

###### Lemma IV.3

The robot correctly adds a brick to the fort in Procedure 4 (ExtendFort).

###### Proof:

Before the start of Procedure 4 (ExtendFort), the robot is at the marker and
carries a brick. This procedure works in two stages with $stage=0$ and
$stage=1$.

When $stage$ is 0, the robot follows a defined set of instructions to place
the first $3$ bricks to get a perfect fort of size $4$. In line 1, it arrives
at the first cell of the fort since it is at a bounded distance from the
marker, and no other brick is closer to the marker. Initially, $counter$ is
$1$, lines 4-5 get executed. Shifting done in FindNextBrick moves a brick by
at most two cells, and from lemma IV.1, we know before FindNextBrick, the
field was strongly structured. Thus the fort had a gap of width seven, and
after its execution, the fort has a gap of width at least 5. Thus the cell on
the east of the first cell should be empty, and hence the robot can place the
brick in front as it is oriented to the east. The robot increases $counter$ by
$1$ so that in the next call of ExtendFort lines 6-9 get executed. Since the
fort now has two bricks, in line 8, the robot can move one cell forward and
place the brick in the empty adjacent cell. The robot extends the fort and
increases $counter$ by $1$. Thus, when the robot arrives to add the next
brick, lines 10-14 get executed. The robot places the brick to get a perfect
fort of span $2$ correctly since the gap is at least five, and thus, the cell
on the south of the first cell of the fort must be empty. The robot increases
$counter$ by $1$ and $stage$ by $1$. Thus, in every call to ExtendFort
hereafter, the else block in lines 15-39 will get executed. Also, since line
40, updates $counter$ to be its remainder when divided by $4$, $counter$
becomes $0$ after every $4^{th}$ brick is added.

When $stage$ is $1$, the robot adds the brick to the fort in a recursive
manner, the shape of the fort being repeated after adding every $4^{th}$
brick. When the number of bricks in the fort is of the form $4t$ where $t$ is
any positive integer and new brick has to be added, lines 16-19 get executed.
The call to TraverseWall ensures that the robot reaches the end of the north
wall of the fort. Since the gap is at least $5$, the robot places the brick in
the empty cell extending the north wall of the fort by one brick. Now the
number of bricks in the fort is of the form $4t+1$, and $counter$ is $1$. When
the next brick is added, lines 20-25 get executed. The call to TraverseWall
ensures that the robot reaches the last cell of the north wall. Then it moves
one step back and arrives at the penultimate cell, which is also the north of
the east wall of the fort. It turns to the right and moves along the east
wall. Lemma IV.2 ensures that the call to ShiftBricks shifts all the bricks of
this row to one cell to the left. As a result, the new brick is placed at the
south-east corner of the fort. In the next call, the number of bricks is
$4t+2$, and $counter$ is $2$ results in the execution of lines 26-31. The
first call to TraverseWall ensures that the robot reaches the last cell of the
north wall, and then it turns right to the east wall where another call to
TraverseWall ensures that it reaches the south of the east wall. The robot
places the brick in the front, extending the east wall to the south by one
brick. In the next call to ExtendFort, lines 32-39 get executed. After two
calls to TraverseWall and a turn between them, the robot arrives at the
southernmost cell of the east wall. Then it moves one step and turns right
onto the south wall. It invokes ShiftBricks procedure and moves the bricks on
the south wall one step to the south (ref. Lemma IV.2). After this, the robot
places brick on the south-west corner of the fort, extending the size of the
fort to $4t+4$ and $counter$ to $4$. After line 42 is executed, $counter$
resets to $0$, and the procedure runs repetitively. In line 43, Procedure
Sweep ensures that the gap of the fort is of width $7$ before the robot goes
on to pick another brick. Thus the procedure ExtendFort correctly adds a brick
to the fort. ∎

###### Theorem IV.4

BuildFort correctly builds a fort.

###### Proof:

To prove this theorem, we use induction on the number of iterations of the
while loop in line 9 in BuildFort. Sweep is called in line 6 before the while
loop. From lemma IV.1, we know that the execution of Sweep has resulted in a
strongly structured field. Thus before the first iteration, i.e., $i=1$, of
the while loop, the field is strongly structured. We assume the induction
hypothesis holds after the $i^{th}$ iteration that the field is strongly
structured and prove this remains true after the $(i+1)^{th}$ iteration. Using
procedures FindNextBrick and ReturnToMarker, the robot carries a brick after
it performs the search walk on one of the components. From Lemma IV.3, we know
that the robot correctly adds a brick to the fort. Also, Sweep is called again
in ExtendFort, which results in a strongly structured field. Thus, we proved
our induction argument. Thus, the field is strongly structured before each
iteration of the while loop in BuildFort and correctly builds the fort. ∎

###  IV-B Complexity

From [3], we have the complexity of Sweep, FindNextBrick and ReturnToMarker to
be $O(s)$ for each of the procedures. We show the time complexity of Procedure
4 in Lemma IV.5 and then we show the complexity of Algorithm 7 in Theorem
IV.6.

###### Lemma IV.5

The execution of ExtendFort requires $O(z)$ time.

###### Proof:

Since we add bricks to the fort starting from the north-west corner, adding a
brick in the south-east corner requires the robot to travel a distance
$s^{\prime}$, where $s^{\prime}$ is the span of the resulting fort. In case of
the fort, $s^{\prime}=O(z)$. Hence ExtendFort takes $O(z)$ time. ∎

###### Theorem IV.6

A fort is created by BuildFort given an initial connected field in time
$O(z^{2})$ where $z$ is the number of bricks in the field.

###### Proof:

There are a total of $z$ bricks in the field. Initially, one brick was chosen
as the fort and another as the marker. Thus the rest of $z-2$ bricks will be
picked in the while loop of BuildFort. Thus there will be $z-2$ iterations of
this loop. Also, we know that $O(s)$ is the length of the search walk, and the
robot traverses it twice, once while picking the brick and the other while
returning from it. We know that a single execution of Sweep takes time $O(s)$.
Also, we saw in lemma IV.5 that adding a brick to the fort requires time
$O(z)$, which is done in one execution of ExtendFort. The span of the initial
configuration can be at most $z$. Thus, BuildFort requires $O(z^{2})$ time. ∎

##  V Conclusion and Future Work

We proposed a Fort formation problem by a robot modeled as a finite automaton
in an infinite grid and established a lower bound for the same. We developed
an algorithm that builds a Fort from a given initial connected field of bricks
in an infinite grid by a mobile robot in worst-case optimal time. The research
area is quite nascent, and a lot can be done further. One can explore in the
direction of building different structures given an initial field. A variation
of the bricks with hexagonal tiling can also be considered instead of a square
bricks. Extension to 3 dimensions with six directions of movement can also be
considered as a future work. Further research using multiple mobile agents to
build the structures can be performed to determine if the time complexity can
be improved.

## References

  * [1] Romas Aleliunas, Richard M. Karp, Richard J. Lipton, László Lovász, and Charles Rackoff.  Random walks, universal traversal sequences, and the complexity of maze problems.  In 20th Annual Symposium on Foundations of Computer Science, San Juan, Puerto Rico, 29-31 October 1979, pages 218–223. IEEE Computer Society, 1979.
  * [2] Jérémie Chalopin, Shantanu Das, and Adrian Kosowski.  Constructing a map of an anonymous graph: Applications of universal sequences.  In Chenyang Lu, Toshimitsu Masuzawa, and Mohamed Mosbah, editors, Principles of Distributed Systems - 14th International Conference, OPODIS 2010, Tozeur, Tunisia, December 14-17, 2010. Proceedings, volume 6490 of Lecture Notes in Computer Science, pages 119–134. Springer, 2010\.
  * [3] Jurek Czyzowicz, Dariusz Dereniowski, and Andrzej Pelc.  Building a nest by an automaton.  Algorithmica, 2020.
  * [4] Shantanu Das.  Graph explorations with mobile agents.  In Paola Flocchini, Giuseppe Prencipe, and Nicola Santoro, editors, Distributed Computing by Mobile Entities, Current Research in Moving and Computing, volume 11340 of Lecture Notes in Computer Science, pages 403–422. Springer, 2019.
  * [5] Shantanu Das, Paola Flocchini, Nicola Santoro, and Masafumi Yamashita.  On the computational power of oblivious robots: Forming a series of geometric patterns.  In Proceedings of the 29th ACM SIGACT-SIGOPS Symposium on Principles of Distributed Computing, PODC ’10, page 267–276, New York, NY, USA, 2010. Association for Computing Machinery.
  * [6] Joshua J. Daymude, Kristian Hinnenthal, Andréa W. Richa, and Christian Scheideler.  Computing by programmable particles.  In Paola Flocchini, Giuseppe Prencipe, and Nicola Santoro, editors, Distributed Computing by Mobile Entities, Current Research in Moving and Computing, volume 11340 of Lecture Notes in Computer Science, pages 615–681. Springer, 2019.
  * [7] Giuseppe Antonio Di Luna, Paola Flocchini, Giuseppe Prencipe, Nicola Santoro, and Giovanni Viglietta.  Line recovery by programmable particles.  In Paolo Bellavista and Vijay K. Garg, editors, Proceedings of the 19th International Conference on Distributed Computing and Networking, ICDCN 2018, Varanasi, India, January 4-7, 2018, pages 4:1–4:10. ACM, 2018\.
  * [8] Giuseppe Antonio Di Luna, Paola Flocchini, Nicola Santoro, Giovanni Viglietta, and Yukiko Yamauchi.  Mobile RAM and shape formation by programmable particles.  In Maciej Malawski and Krzysztof Rzadca, editors, Euro-Par 2020: Parallel Processing - 26th International Conference on Parallel and Distributed Computing, Warsaw, Poland, August 24-28, 2020, Proceedings, volume 12247 of Lecture Notes in Computer Science, pages 343–358. Springer, 2020.
  * [9] Giuseppe Antonio Di Luna, Paola Flocchini, Nicola Santoro, Giovanni Viglietta, and Yukiko Yamauchi.  Shape formation by programmable particles.  Distributed Comput., 33(1):69–101, 2020.
  * [10] Ichiro Suzuki and Masafumi Yamashita.  Distributed anonymous mobile robots: Formation of geometric patterns.  SIAM Journal on Computing, 28(4):1347–1363, 1999.


# SLABERT Talk Pretty One Day: Modeling Second Language Acquisition with BERT

⋆Aditya Yadavalli1 ⋆Alekhya Yadavalli2 Vera Tobin2
1 Karya Inc.
2 Language and Cognition Lab, Case Western Reserve University
<EMAIL_ADDRESS>{alekhya.yadavalli<EMAIL_ADDRESS>
Work done as a visiting researcher at Case Western Reserve University

###### Abstract

Second language acquisition (SLA) research has extensively studied cross-
linguistic transfer, the influence of linguistic structure of a speaker’s
native language [L1] on the successful acquisition of a foreign language [L2].
Effects of such transfer can be positive (facilitating acquisition) or
negative (impeding acquisition). We find that NLP literature has not given
enough attention to the phenomenon of negative transfer. To understand
patterns of both positive and negative transfer between L1 and L2, we model
sequential second language acquisition in LMs. Further, we build a
Mutlilingual Age Ordered CHILDES (MAO-CHILDES)—a dataset consisting of 5
typologically diverse languages, i.e., German, French, Polish, Indonesian, and
Japanese—to understand the degree to which native Child-Directed Speech (CDS)
[L1] can help or conflict with English language acquisition [L2]. To examine
the impact of native CDS, we use the TILT-based cross lingual transfer
learning approach established by Papadimitriou and Jurafsky (2020) and find
that, as in human SLA, language family distance predicts more negative
transfer. Additionally, we find that conversational speech data shows greater
facilitation for language acquisition than scripted speech data. Our findings
call for further research using our novel Transformer-based SLA models and we
would like to encourage it by releasing our code, data, and models.††Code,
data and models are here: https://github.com/AdityaYadavalli1/SLABERT
††$\star$ Authors contributed equally

##  1 Introduction

Cross-linguistic transfer can be described as the influence of native language
[L1] properties on a speaker’s linguistic performance in a new, foreign
language [L2]. The interaction of the linguistic structure of a speaker’s L1
with the successful acquisition of L2 results in what are termed as transfer
effects. Transfer effects appear in various aspects of linguistic performance,
including vocabulary, pronunciation, and grammar Jarvis and Pavlenko (2007).
Cross-linguistic transfer can be positive or negative in nature: positive
transfer refers to the facilitating effects of one language in acquiring
another (e.g., of Spanish vocabulary in acquiring French) and negative
transfer between the learner’s native [L1] and target [L2] languages,
producing errors. The greater the differences between two languages, the
greater the negative effects.

While cross-lingual transfer has received considerable attention in NLP
research Wu and Dredze (2019); Wu et al. (2019); Conneau et al. (2017, 2018);
Artetxe et al. (2018); Ruder et al. (2017), most of this research has
concentrated on practical implications such as the degree to which the right
tokenizer can optimize cross-lingual transfer, and has not looked at the kind
of sequential transfer relationships that arise in human second language
acquisition. Meanwhile, approaches like the Test for Inductive Bias via
Language Model Transfer (TILT) Papadimitriou and Jurafsky (2020) focus on
positive transfer with divergent pairs of training sets, such as MIDI music
and Spanish, to shed light on which kinds of data induce generalizable
structural features that linguistic and non-linguistic data share. Patterns of
both positive and negative transfer between a given L1 and L2, however, can be
a valuable source of information about general processes of second language
acquisition and typological relationships between the languages in question
Berzak et al. (2014).

Most cross-lingual models do not mimic how humans acquire language, and
modeling the differences between first and second language acquisition is a
particularly under-explored area. To engage with questions about second
language acquisition using LMs, we model sequential second language
acquisition in order to look more closely at both positive and negative
transfer effects that may occur during the acquisition of L2.

Using Child-Directed Speech (CDS) to create L1 training sets that are
naturalistic, ecologically valid, and fine-tuned for language acquisition, we
model the kind of cross-linguistic transfer effects that cause linguistic
structure of the native L1 to influence L2 language acquisition in our novel
Second Language Acquisition BERT (SLABERT) framework. The resulting models,
when tested on the BLiMP (Benchmark of Linguistic Minimal Pairs for English)
grammar test suite Warstadt et al. (2020), show that L1 may not only
facilitate L2 learning, but can also interfere. To the extent that
interference is considered in NLP research, it is often understood simply as a
failure of positive transfer in model training. We suggest, instead, that
these results should be analyzed in terms of distinctive patterns of both
negative and positive transfer, which can reveal not just the existence of
generalizable features across datasets, but also finer-grained information
about structural features of these languages and their accessibility to second
language learners.

##  2 Related Work

Our work is closely related to and in many ways builds on the work done by
Huebner et al. (2021). They proposed that Child-Directed Speech has greater
potential than other kinds of linguistic data to provide the structure
necessary for language acquisition, and released BabyBERTa, a smaller sized
RoBERTa Liu et al. (2019) model designed to investigate the language
acquisition ability of Transformer-based Language Models (TLM) when given the
same amount of data as children aged 1-6 get from their surroundings. They
also released Zorro, a grammar test suite, that is compatible with the small
vocabulary of child-directed input.

Child-directed speech (CDS) refers to the special register adopted by some
adults, especially parents, when talking to young children Saxton (2009). CDS
typically features higher fundamental pitch, exaggerated intonation, slower
speech, and longer pauses than Adult-Directed Speech (ADS) Clark (2016).
Utterances in CDS are usually well-formed grammatically, but are syntactically
simpler than ADS, often comprising single word utterances or short
declaratives. Adults often repeat words, phrases, and whole utterances in CDS
Küntay and Slobin (2002); Snow (1972) and make fewer errors Broen (1972) than
they do in ADS. CDS also tends to use a smaller and simplified vocabulary,
especially with very young children Hayes and Ahrens (1988). While the
universality and necessity of CDS for language acquisition is a matter of
debate Pinker (1995); Hornstein et al. (2005); Haggan (2002), it is likely
that the features of CDS are universally beneficial in language acquisition
Saxton (2009). NLP literature suggests that are certain benefits when models
are trained on CDS Gelderloos et al. (2020). Studies from other fields suggest
that the pitch contours, repetitiveness, fluency, and rhythms of CDS make it
easier for children to segment speech, acquire constructions, and understand
language Cristia (2011); Thiessen et al. (2005); Nelson et al. (1986); Ma et
al. (2011); Soderstrom et al. (2008); Kirchhoff and Schimmel (2003). Many of
these distinctive qualities of CDS seem tailor-made for human language
acquisition, which is why we use CDS data as L1 in our SLABERT models.

Several recent studies confirm that the distinctive distributional features of
CDS influence the grammatical and lexical categories that children acquire.
For instance, Mintz (2003) found that "frequent frames" in CDS–commonly
recurring co-occurance patterns of words in sentences–yield very accurate
grammatical category information for both adults and children. Similarly,
Veneziano and Parisse (2010) found that patterns of frequent use and,
importantly, reinforcement in CDS-specific conversational exchanges were most
predictive of the constructions children learn. Together, these findings
suggest that both token distribution and the distinctive conversational
structure of CDS provide useful reinforcement for acquisition. Therefore, when
training our L1 model, we pay attention to qualities of the training input
such as the conversational structure.

In second language acquisition (SLA) research, patterns of negative transfer
are a topic of much interest and have been considered a source of information
both about what happens in second language learning and what it can reveal
about the typological relationships between L1 and L2. For instance, Dulay and
Burt (1974) show that closely analyzing data from children learning a second
language reveals that some errors are due to L1 interference (negative
transfer), while others arise from developmental cognitive strategies similar
to those made during L1 acquisition (developmental errors). Berzak et al.
(2014) show a strong correlation between language similarities derived from
the structure of English as Second Language (ESL) texts and equivalent
similarities obtained directly from the typological features of the native
languages. This finding was then leveraged to recover native language
typological similarity from ESL texts and perform prediction of typological
features in an unsupervised fashion with respect to the target languages,
showing that structural transfer in ESL texts can serve as valuable data about
typological facts.

The phenomenon of cross-linguistic transfer has received considerable
attention in NLP research in the context of multilingual Language Models Wu
and Dredze (2019); Wu et al. (2019); Conneau et al. (2017, 2018); Artetxe et
al. (2018); Ruder et al. (2017). Our investigation is particularly inspired by
Papadimitriou and Jurafsky (2020)’s Test for Inductive Bias via Language Model
Transfer (TILT). This is a novel transfer mechanism where the model is
initially pre-trained on training data [L1]. Next, they freeze a part of the
model and fine-tune the model on L2. Finally, they test the resulting model on
a test set of L2. We follow a similar approach to our model’s second language
acquisition.

Language | Vocabulary | Total tokens | Avg. Sentence Length | No. of Children | Utterances
---|---|---|---|---|---
American English | 27,723 | 4,960,141 | 5.54832 | 1117 | 893,989
French | 22,809 | 2,473,989 | 5.74531 | 535 | 487,156
German | 59,048 | 4,795,075 | 5.65909 | 134 | 951,559
Indonesian | 21,478 | 2,122,374 | 3.97058 | 9 | 572,581
Polish | 31,462 | 493,298 | 5.84276 | 128 | 84,578
Japanese | 44,789 | 2,397,386 | 4.17552 | 136 | 588,456
Wikipedia-4 | 84,231 | 1,907,706 | 23.8456 | - | 80,000
English ADS | 55,673 | 905,378 | 13.1901 | - | 74,252
Table 1: MAO-CHILDES corpus statistics: the number of unique tokens, total
tokens, the average sentence length, the total number of children, and the
mean age of child for each language dataset is presented

##  3 Data

###  3.1 Why Child-Directed Speech

We wanted L1 training sets that are both realistic and fine-tuned to teach
language to developmental (first language) learners. We also wanted to
reproduce the findings of Huebner et al. (2021) which suggest that Child-
Directed Speech as training data has superior structure-teaching abilities for
models compared to scripted adult-directed language.

The BabyBERTa studies Huebner et al. (2021) found that their LM required less
data than RoBERTa to achieve similar (or greater) linguistic/syntactic
expertise (as tested by Zorro), and suggested that CDS is better than
Wikipedia text for teaching linguistic structure to models. Given these
findings and widespread support in cognitive science and linguistics for the
facilitative nature of CDS in child language learning, we choose to use CDS
data from five different languages as our L1s to examine our hypothesis that
preexisting linguistic structure of L1 interacts differentially with the
acquisition of L2 (English).

Additionally, building on the Huebner et al. (2021) efforts to find superior
training data for LMs in general, we explore the possibility that comparing
conversational CDS with scripted ADS is a less fair comparison than comparing
the quality of conversational CDS with that of conversational ADS as training
input for LMs.

####  3.1.1 Why CHILDES

Our focus in training the Child-Directed Speech model is on replicating for
the LM, as closely as possible, the primary linguistic input of young
children. While young children are exposed to passive Adult-Directed Speech,
speech that is directed at them and intended to communicate with them plays a
more central role in the child’s linguistic experience Soderstrom (2007). For
this reason, we use a language database of naturalistic speech directed at
children. The CHILDES Macwhinney (2000) database, a component of the larger
TalkBank corpus, is a vast repository of transcriptions of spontaneous
interactions and conversations between children of varying ages and
adults.111https://talkbank.org The database comprises more than 130 corpora
from over 40 different languages and includes speech directed at children from
ages of 6 months to 7 years. The large selection of languages permits us the
necessary flexibility in choosing different languages for our L1 data (see
Section 3.1.2 for more on Language Selection). The range of child ages allows
us to train our models with increasingly complex linguistic input, emulating
the linguistic experience of a growing child.

####  3.1.2 Language Selection

Our focus is on cross-linguistic transfer of language structure; therefore, we
use a simple selection criterion and choose five languages with varying
distance from English according to their language family: German, French,
Polish, Indonesian, and Japanese. We hypothesize languages that are
structurally similar to English should perform better (show more positive
transfer and less negative transfer). German, French, and Polish, like
English, are all Indo-European languages. However, each of these languages
belongs to a unique genus: German and English are Germanic languages, French
is a Romance language, and Polish is a Slavic language. While English and
French do not share the same genus, there is much overlap between the two
languages due to the substantial influence of French on English stretching
back to the time of Norman Conquest. Japanese belongs to the Japanese language
family and Indonesian to the Austronesian language family.

####  3.1.3 Using the AO-CHILDES corpus

The AO-CHILDES (AO: age-ordered) corpus was created from Huebner and Willits
(2021) American English transcripts from the CHILDES database. To curate the
American English collection, we followed the same cleaning criteria as Huebner
and Willits (2021): only transcripts involving children 0 to 6 years of age
were procured, from which child (non-adult) utterances and empty utterances
were omitted. The initial CHILDES transcriptions were converted from CHAT
transcription format to csv format files using childes-db Sanchez et al.
(2019) to conduct the data cleaning processes. The resulting dataset, which
now contains 2,000,352 sentences, 27723 unique words, and 4,960,141 total word
tokens, forms the American English input. This cleaning process was repeated
for the corpora of German, French, Polish, Japanese, and Indonesian to create
the dataset for each language (see Table 1 for the language statistics).

####  3.1.4 MAO-CHILDES

For the sake of simplicity we refer to the corpus resulting from the
collective datasets of the six languages as MAO-CHILDES (MAO is short for
Multilingual Age-Ordered) to show that the transcripts it contains include a
selection of different languages and also are ordered by age of child (see
Table 1).

Data in MAO-CHILDES is not uniformly distributed across languages, as seen in
Table 1. First, Polish is represented by significantly less data than every
other language. Second, Indonesian has a lower number of unique tokens
compared to other languages. The Indonesian data is also only collected from
conversations with 9 children, a much smaller sample size compared to the
other languages, which have sample sizes in the hundreds if not thousands.
Third, the average sentence length of the Asian languages—Indonesian and
Japanese—is smaller than any of the other languages. The effect of these
variations in data, caused by both available resources and natural linguistic
characteristics of the languages, on the performance of the cross-lingual
model is anticipated.

Figure 1: Diagram illustrating our experimental process for each L1, as listed
in Table 1. Training occurs in two stages and each model is finally tested on
the BLiMP test suite.

###  3.2 Adult-Directed Speech corpus

The Adult-Directed Speech (ADS) corpus comprises conversational speech data
and scripted speech data. We build on the BabyBERTa efforts to find superior
training data for LMs (in general) by experimenting with conversational ADS
and comparing its training utility with that of conversational CDS. This
investigation is aimed at narrowing down the true source, child-directed
language or conversational language, of the reduced data size requirements of
BabyBERTa.

To create our conversational ADS corpus, we use the sample COCA SPOKEN
corpus.222https://www.corpusdata.org COCA (Corpus of Contemporary American
English) is one of the most widely used corpora of English for its rich
representation of texts from a wide range of genres, dialects, and time
periods. The SPOKEN genre comprises transcriptions of spontaneous
conversations between adults. To clean this sample corpus we followed a three
step process:

  * •

All spoken disfluencies such as pauses, laughter, and filler utterances
encoded in the spoken transcripts were cleaned.

  * •

All meta tags that mention the names of the speakers were removed.

  * •

Finally, the data was sampled manually to check that the corpus was clean.

After cleaning, we were left with 74,252 utterances. We use this cleaned
corpus to train our conversational Adult-Directed Speech (ADS) model.

To replicate the findings of the BabyBERTa study, we also train a model on
scripted ADS. To create our scripted ADS corpus, we randomly sample 80,000
sentences from Wikipedia-3 Huebner et al. (2021), which we term Wikipedia-4,
so that the data size of conversational ADS and scripted ADS is approximately
equal, to allow fair comparison. All the information about the data we used is
in Table 1.

##  4 Experimental Setup

We use BabyBERTa Huebner et al. (2021) to run all our experiments. BabyBERTa
is a smaller-sized RoBERTa Liu et al. (2019) tuned to perform well on data of
the size of AO-CHILDES. However, we make additional changes to the vocabulary
size of the model as we found that to improve the results of the model. The
implementation details of the model can be found in Appendix A.1.

We follow the TILT approach introduced by Papadimitriou and Jurafsky (2020) to
originally test the LSTM-based Hochreiter and Schmidhuber (1997) LM’s
structure acquisition. Their general approach is followed in the current study
with a few notable changes (See Figure 1). Our approach comprises two stages:
(1) train the model on L1 (CDS language) (2) freeze all parameters except the
word embeddings at the transfer stage of the experiment, and fine-tune the
model on L2 (English ADS). Finally, the resulting model is tested on a test
set of L2 for which we use the Benchmark of Linguistic Minimal Pairs (BLiMP)
Warstadt et al. (2020), a challenge set for evaluating the linguistic
knowledge of the model on major grammatical phenomena in English. Our study
deviates from Papadimitriou and Jurafsky (2020) approach in three ways: (1)
instead of using LSTM-based LMs we use Transformer-based LMs Vaswani et al.
(2017) (2) they freeze all layers except the word embedding and linear layers
between the LSTM layers however, for simplicity we freeze all parameters
except the word embeddings (3) while they report their findings based on LM
perplexity scores, we use the BLiMP test suite to report how L1 structure
(particularly, syntax and semantics) affects L2 acquisition in our
Transformer-based LMs.

Figure 2: Performance of model on various grammatical phenomena from the BLiMP
test suite

There are two experiments for which we follow a different procedure than what
is explained above:

  * •

In the case of random-baseline experiment, we freeze all of the model except
the embeddings and let the model train on conversational English ADS. The
corresponding tokenizer is also trained on conversational English ADS. This
experiment is run in order to have the right benchmark to compare against.
This method prevents the model from picking up any grammatical structure from
the training data, while allowing it to acquire English vocabulary.

  * •

In the case of the scripted ADS and conversational ADS experiments, we do not
employ TILT-based cross lingual transfer. We train the model from scratch on
scripted ADS and conversational ADS respectively.

Testing: We use the BLiMP grammar test suite to evaluate the linguistic
knowledge of our model. BLiMP consists of 67 paradigms categorized into 12
major grammatical phenomena in English. Each of these 67 datasets comprises
1,000 minimal pairs i.e. pairs of minimally different sentences, one of which
is grammatically acceptable and the other not (refer to Warstadt et al. (2020)
for a detailed description of the test suite).

##  5 Results and Discussion

###  5.1 Results

The proportion of the BLiMP minimal pairs in which the model assigns a higher
probability to the acceptable sentence informs the accuracy of the model. A
total of 9 models are compared in their performance using the accuracy scores
obtained on 12 different grammatical tests from the BliMP test suite. We
report the results for all models in Figure 2 (see Appendix A.2 for detailed
results). The model trained on conversational English ADS achieves the highest
accuracy and the one trained on Indonesian CDS achieves the lowest. Despite
the conversational English ADS corpus size being at least 10x smaller than the
CDS corpora sizes, it performs the best in 9 out of 12 grammatical phenomena
from the BLiMP test suite. CDS demonstrates higher accuracy only in anaphor
agreement, irregular forms, and quantifiers. Overall, English CDS performs
5.13 points behind English ADS. These results show that (conversational)
Adult-Directed speech makes for superior training data for models as compared
to (conversational) Child-Directed Speech. From Figure 2, we note a few other
significant trends:

First, the results indicate that conversational speech data form a superior
training data for language models in general as compared to the conventional
scripted data. Table 2 compares the performance of models when trained on
different types of training inputs of the same language (English): scripted
ADS (Wikipedia-4), conversational ADS, and conversational CDS. Among the
three, the performance of the model trained on conversational ADS is highest,
followed by conversational CDS, and lastly scripted ADS. Important to note
here is that, corroborating the findings of the BabyBERTa study,
conversational CDS still outperforms scripted ADS (Wikipedia-4) but falls
behind compared to conversational ADS. These results suggest that
conversational speech data are a more effective training source for models
than scripted data (more on this in Section 5.2).

Second, the results show a negative correlation between the distance of the
CDS language from English and the performance of the model, i.e., as the
typological distance between L1 and L2 increases, the performance of the model
decreases. We term this the Language Effect. This finding supports our
hypothesis that, given the relation between transfer errors and typological
distance between L1 and L2 Ringbom (2006), the increasing structural
dissimilarities between the L1 (CDS language) and the L2 (always English ADS)
should adversely impact the performance of the model (more on this in Section
5.3).

Third, the results show that CDS performs worse than ADS in several
grammatical phenomena (9 out of 12). Considering the simplistic and
facilitating structure and, more importantly, the ecologically valid nature of
CDS, these results engender some interesting hypotheses which we discuss
briefly in Section 5.4.

Fourth, we see several results in which individual models perform poorly on
individual tests in ways that are not cleanly predicted by general trends. We
believe these results reflect patterns of negative transfer, in which
L1-specific structures actively interfere with the acquisition of structures
in L2 (more on this in Section 5.5).

###  5.2 Conversational vs. Scripted Data

The conventional training data for LMs is scripted adult-directed speech,
perhaps owing to its easily accessible nature compared to other forms of data,
such as conversational ADS or any form of CDS. However, our findings
demonstrate that conversational data yields better model performance than
scripted data (see Table 2). The best accuracy scores are produced by
conversational ADS on 67% of the phenomena, by conversational CDS on 25% of
the phenomena, by scripted ADS on 8% of the phenomena. Conversational data may
make for a better training input for language acquisition given a higher level
of interactive components in its composition which is an essential feature of
language acquisition in children. Much of the previous research has looked at
what conversational language does for the people who are directly contributing
to the conversation in question. For instance, there is a general tendency for
speakers to reproduce grammatical Bock (1986); Gries (2005) elements of their
interloctor’s previous utterances. These behaviors both enhance interactive
alignment Bois (2014) and ease cognitive load for utterance planning Bock
(1986); Pickering and Ferreira (2008). Studies of children’s conversational
behavior Veneziano and Parisse (2010); Köymen and Kyratzis (2014) show,
similarly, that children use their interlocutors’ immediately preceding
utterances as resources for producing and reinforcing construction types they
are in the process of acquiring. Our findings suggest that the resulting
distributional patterns of "dialogic syntax" Bois (2014) in the conversational
record leave a trace that can make conversational data especially informative
for model training.

###  5.3 Language Effect

Figure 3: Mean multilingual CDS performance compared to ADS Phenomenon | Wikipedia-4 | Conversational ADS | Conversational CDS
---|---|---|---
Ananaphor Agreement | 51.4 | 60.6 | 62.9
Argument Structure | 54.5 | 56.1 | 55.1
Binding | 60.7 | 61.6 | 58.9
Control/Raising | 48.8 | 59.1 | 55.6
Determiner Noun Agreement | 65.2 | 70.9 | 67.8
Ellipses | 68.6 | 66.2 | 57.5
Filler Gap | 62.4 | 67.3 | 62.6
Irregular Forms | 61.8 | 68.2 | 70.9
Island Effects | 51.8 | 72.7 | 51.3
NPI Licensing | 53.7 | 62.6 | 51.9
Quantifiers | 58.5 | 62.4 | 71.7
Subject Verb Agreement | 54.9 | 57.7 | 53.8
Table 2: Performance of model on BLiMP test suite when trained on different
types of input data.

We selected five languages at varying distances from English according to
their language family and examined how structural dissimilarities with
increasing distance from English impact the performance of the model. Figure 3
shows the increase in difference between the performance of model trained on
English ADS and CDS of the various languages. Our results show negative
correlation between the distance of the CDS language from English and the
performance of the model, i.e., as the typological distance between L1 and L2
increases, the performance of the model decreases. Based on prior work on
transfer errors and typological distance Ringbom (2006), this decrease in
performance could be the result of negative transfer effects, which tend to
increase with increase in typological distance between L1 and L2. Among all
CDS languages, English CDS performs closest to English ADS (5.13 points behind
ADS), suggesting that even within the same language the linguistic differences
between ADS and CDS affect model performance (see Table 2). This is considered
as comparisons between other CDS languages and English ADS are made. German
shows the next best performance (6.71 points behind English ADS), followed by
French (7.27 points behind ADS), Polish (7.57 points behind ADS), Japanese
(8.17 points behind ADS), and lastly Indonesian (8.69 points behind ADS).
These results confirm our hypothesis that L1s that are structurally closer to
L2 (English ADS) perform better, owing to greater degree of positive transfer
effects.

For human language learners, transfer works both ways: sometimes knowledge of
parallel structures in the native language facilitate performance in the new
language. Other times, there is interference from the native language,
resulting in errors. The SLABERT models, similarly, show evidence of both
positive and negative transfer. As with human second-language learners, some
of the errors we see in SLABERT performance suggest the effect of negative
transfer from native [L1] language, while others can be characterized as
developmental, in that they are similar to the kinds of errors that even
native human speakers will make on their way to learning the target
constructions.

###  5.4 CDS & Sources of Errors in Language Learning

Our results show that CDS performs worse than ADS in a majority (9 out of 12)
of the grammatical phenomena from the BLiMP test suite (see Figure 2). We
discuss some theoretical explanations for these results.

Negation and NPIs: Child language acquisition research strongly suggests that
mastering the full range of negative licensing and anti-licensing contexts
takes a long time. Across languages, detailed acquisition studies find that
children do use NPIs with licensing expressions consistently by age 3 or 4
Tieu (2013); Lin et al. (2015) but only with a limited range of negative
licensers. Moreover, Schwab et al. (2021) showed that, even 11 and 12-year-
olds, whose language input by that age is entirely ADS, are still in the
process of learning some polarity-sensitive expressions. Thus, CDS input alone
may not be sufficient for learning the licensing conditions for NPIs. Previous
NLP literature also suggests that negation is particularly challenging for
language models to learn Kassner and Schütze (2019); Ettinger (2019). Given
this, and acquisition studies that have shown that learning licensing
conditions for NPIs goes hand-in-hand with learning negation van der Wal
(1996), we expected our model trained on CDS to make developmental errors on
tests related to NPIs. As discussed in Section 5.5, as a Slavic language,
Polish also has distinctive constraints on the appearance of NPIs that are the
result of competition with grammatical constraints not present in English. In
this case, NPI performance is likely subject to both developmental errors and
negative transfer .

Longer Distance Dependencies: Short and simple sentences are characteristic of
CDS. However, it is likely that such utterances do not make ideal training
input for LMs to learn long-distance dependencies (LDDs). Consequently, we
expect all models trained on CDS data to be negatively impacted on tests that
demand long-distance dependency understanding. Island effects, the phenomenon
that showed the widest difference in performance compared to ADS-trained
(-21.3 points), is one such phenomenon in the BLiMP test suite, requiring
long-distance dependency understanding to perform well Sprouse and Hornstein
(2013). Ellipsis and filler-gap structures also depend on LDDs and also suffer
from significant decreases in scores compared to ADS (-10.8 and -6.5 points,
respectively). This also applies to binding and control/raising phenomena
(-2.8 and -3.6 respectively); however, island effects, ellipsis, and filler-
gap tests are particularly affected by the model’s lack of LDD understanding.

Phenomena That Confuse Humans: Warstadt et al. (2020) report human performance
scores which we use to gain an understanding of how our model performs on
tests compared to humans. From the reported human performance scores, we
observe that not all of the grammatical phenomena in the BLiMP test suite are
equally transparent to humans. Human performance on 8 out of 12 phenomena is
below 90 points and 3 of those are below 85 points. The lowest is a mean score
of 81 for tests on argument structure, where the CDS-trained and ADS-trained
models are also seen struggling (rather more seriously) with a mean score of
55.1 and 56.1, respectively. For control/raising, similarly, human performance
has a mean score of 84 points while CDS-trained and ADS-trained models have
mean scores of 55.6 and 59.1 respectively. We expect CDS to perform poorly on
these tests, which are challenging even for people.

###  5.5 Negative Transfer

There are tests where performance of CDS-trained models would be expected to
be better given the nature of the phenomena and the characteristics of CDS
utterances. However, CDS underperforms compared to ADS even on tests we might
expect to be in its wheelhouse. In particular, determiner-noun agreement and
subject-verb agreement are the kinds of phenomena that should be easy for the
model to learn even from shorter utterances and with relatively small
vocabulary size, since they are matters of simple, regular morphology. The
results, therefore, are interesting. We hypothesize one reason we do not see
good transfer boosts from other-language CDS on these is that patterns of
morphology are very language specific.

Looking broadly at the performance of non-English CDS models, we suggest that
these results reflect negative cross-linguistic transfer. For example, the
distribution of negative polarity items in Polish and many other Slavic
languages displays what has been termed the "Bagel problem" Pereltsvaig
(2006): because of conflicts with the demands of strict negative concord (in
which negation requires multiple elements of an expression must all appear in
their negative forms), in Slavic languages, there are NPIs that never appear
in what would otherwise be the canonical context of negative polarity
licensing, i.e. direct negation Hoeksema (2012). In this way, language-
specific paradigmatic patterns supersede the general correlational
relationship between NPIs and their licensing contexts, producing an
opportunity for negative transfer and L1 interference effects.

##  6 Conclusion

In this paper, we explore how second language acquisition research and models
of second language acquisition can contribute to questions in NLP about the
learnability of grammar. Drawing from the previous research on the unique role
of child-directed speech (CDS) in language acquisition, we investigate the
potential of spontaneously generated CDS to form a special source from which
LMs can acquire the structure necessary for first language acquisition. To
test sequential second language acquisition in LMs, we introduce SLABERT. The
results from our experiments suggest that while positive transfer is a lot
more common than negative transfer, negative transfer occurs in LMs just like
it occurs in English Second Language (ESL) learners. We believe these novel
findings call for further research on this front, and suggest that models like
SLABERT can provide useful data for testing questions about both language
acquisition and typological relationships through patterns of cross-linguistic
transfer. To support this, we release our code, novel MAO-CHILDES corpus, and
models.

##  7 Limitations

Given that many special properties of Child-Directed Speech are not present in
text, we would have liked to work on a multimodal dataset, where both visual
and speech information would be present. More specifically, we would have
liked to test the effect of the following:

  * •

Grounding the language models in vision to test the effect of joint attention
Rowe (2012); Akhtar and Gernsbacher (2007). Joint attention refers to the
phenomena where the caregiver’s and the child’s coordinated attention
attention to each other to a third object or an event.

  * •

Child-Directed Speech is known to have special prosodic properties such as
higher variability in pitch Fernald et al. (1989); McRoberts and Best (1997);
Papousek et al. (1991), lengthening of vowels and pauses Albin and Echols
(1996); Ratner (1986); Fernald et al. (1989), context-specific intonational
contours Katz et al. (1996); Papousek et al. (1991); Stern et al. (1982).
These properties have been suggested by many researchers to serve as a
mechanism for getting the infants attention Cruttenden (1994); Ferguson
(1977); Fernald (1989). This attentive role may be considered to be beneficial
for language development in children Garnica (1977). As our models only take
text as the input, we were unable to test the relationship the between these
properties and language acquisition in neural network based models have.

  * •

Caregivers give a lot of feedback when young children are first producing and
acquiring language Soderstrom (2007). Our current mainstream language models
are not interactive. Therefore, it is difficult to incorporate the feedback
loop and the test the effect of the same in models’ language acquisition.

As it is, our findings suggest that many of the most important facilitative
features of Child-Directed Speech are relevant to precisely those formal and
conceptual aspects of language acquisition that are not captured by text-based
language models.

In this paper, we have tested the effect of native CDS in L2 acquisition with
5 typologically diverse languages. However, there is enormous scope to test
the effect of the same with many more different languages, which may lead to
more pointed implications and conclusions than the findings offered here.

##  8 Ethics Statement

We use publicly available CHILDES data to build our corpora (MAO-CHILDES).
Please read more about their terms before using the
data.333https://talkbank.org We use the dataset extracted from the CHILDES
database only for research purposes and not for commercial reasons. We will
release the dataset upon publication under the same license as CHILDES and
this is compatible with the license of CHILDES database Macwhinney (2000). The
results of this study are reported on a single run as part of measures taken
to avoid computation wastage. We do not foresee any harmful uses of this work.

## Acknowledgements

We would like to acknowledge Philip Huebner for clearing our queries regarding
the BabyBERTa code-base. We would also like to thank Saujas Vaduguru for
helping us improve our initial drafts. We also thank the anonymous reviewers
for their feedback on our work. This work made use of the High Performance
Computing Resource in the Core Facility for Advanced Research Computing at
Case Western Reserve University.

## References

  * Akhtar and Gernsbacher (2007) Nameera Akhtar and Morton Ann Gernsbacher. 2007.  Joint attention and vocabulary development: A critical look.  _Language and Linguistics Compass_ , 1 3:195–207.
  * Albin and Echols (1996) Drema Dial Albin and Catharine H. Echols. 1996.  Stressed and word-final syllables in infant-directed speech.  _Infant Behavior & Development_, 19:401–418.
  * Artetxe et al. (2018) Mikel Artetxe, Gorka Labaka, and Eneko Agirre. 2018.  A robust self-learning method for fully unsupervised cross-lingual mappings of word embeddings.  In _Proceedings of the 56th Annual Meeting of the Association for Computational Linguistics (Volume 1: Long Papers)_ , pages 789–798, Melbourne, Australia. Association for Computational Linguistics.
  * Berzak et al. (2014) Yevgeni Berzak, Roi Reichart, and Boris Katz. 2014.  Reconstructing native language typology from foreign language usage.  In _CoNLL_.
  * Bock (1986) J. Kathryn Bock. 1986.  Syntactic persistence in language production.  _Cognitive Psychology_ , 18:355–387.
  * Bois (2014) John W. Du Bois. 2014.  Towards a dialogic syntax.  _Cognitive Linguistics_ , 25:359–410.
  * Broen (1972) Patricia Broen. 1972.  The verbal environment of the language-learning child.  _Monographs of the American Speech and Hearing Association_ , 17.
  * Clark (2016) Eve V. Clark. 2016.  _First Language Acquisition_, 3 edition.  Cambridge University Press.
  * Conneau et al. (2017) Alexis Conneau, Guillaume Lample, Marc’Aurelio Ranzato, Ludovic Denoyer, and Herv’e J’egou. 2017.  Word translation without parallel data.  _ArXiv_ , abs/1710.04087.
  * Conneau et al. (2018) Alexis Conneau, Ruty Rinott, Guillaume Lample, Adina Williams, Samuel Bowman, Holger Schwenk, and Veselin Stoyanov. 2018.  XNLI: Evaluating cross-lingual sentence representations.  In _Proceedings of the 2018 Conference on Empirical Methods in Natural Language Processing_ , pages 2475–2485, Brussels, Belgium. Association for Computational Linguistics.
  * Cristia (2011) Alejandrina Cristia. 2011.  Fine-grained variation in caregivers’ /s/ predicts their infants’ /s/ category.  _The Journal of the Acoustical Society of America_ , 129 5:3271–80.
  * Cruttenden (1994) Alan Cruttenden. 1994.  _Phonetic and prosodic aspects of Baby Talk_, page 135–152. Cambridge University Press.
  * Dulay and Burt (1974) Heidi C. Dulay and Marina K. Burt. 1974.  Errors and strategies in child second language acquisition.  _TESOL Quarterly_ , 8:129.
  * Ettinger (2019) Allyson Ettinger. 2019.  What bert is not: Lessons from a new suite of psycholinguistic diagnostics for language models.  _Transactions of the Association for Computational Linguistics_ , 8:34–48.
  * Ferguson (1977) Ch A. Ferguson. 1977.  Baby talk as a simplified register snow.  In Catherine E. Snow and Charles A. Ferguson, editors, _Talking to Children_ , pages 209–235. Cambridge University Press.
  * Fernald (1989) Anne Fernald. 1989.  Intonation and communicative intent in mothers’ speech to infants: Is the melody the message? _Child Development_ , 60(6):1497–1510.
  * Fernald et al. (1989) Anne Fernald, Traute Taeschner, Judy Dunn, Mechthild Papousek, Bénédicte de Boysson-Bardies, and I Fukui. 1989.  A cross-language study of prosodic modifications in mothers’ and fathers’ speech to preverbal infants.  _Journal of Child Language_ , 16:477 – 501.
  * Gage (1994) Philip Gage. 1994.  A new algorithm for data compression.  _C Users J._ , 12(2):23–38.
  * Garnica (1977) Olga K. Garnica. 1977.  Some prosodic and paralinguistic features of speech to young children.  In Catherine E. Snow and Charles A. Ferguson, editors, _Talking to Children_ , pages 63–88. Cambridge University Press.
  * Gelderloos et al. (2020) Lieke Gelderloos, Grzegorz Chrupała, and A. Alishahi. 2020.  Learning to understand child-directed and adult-directed speech.  In _Annual Meeting of the Association for Computational Linguistics_.
  * Gries (2005) Stefan Th. Gries. 2005.  Syntactic priming: A corpus-based approach.  _Journal of Psycholinguistic Research_ , 34:365–399.
  * Haggan (2002) Madeline Haggan. 2002.  Self-reports and self-delusion regarding the use of motherese: implications from kuwaiti adults.  _Language Sciences_ , 24(1):17–28.
  * Hayes and Ahrens (1988) Donald P. Hayes and Margaret G. Ahrens. 1988.  Vocabulary simplification for children: a special case of ‘motherese’? _Journal of Child Language_ , 15(2):395–410.
  * Hochreiter and Schmidhuber (1997) Sepp Hochreiter and Jürgen Schmidhuber. 1997.  Long short-term memory.  _Neural computation_ , 9:1735–80.
  * Hoeksema (2012) Jack Hoeksema. 2012.  On the natural history of negative polarity items.  _Linguistic Analysis_ , 44:3–33.
  * Hornstein et al. (2005) Norbert Hornstein, Jairo Nunes, and Kleanthes K. Grohmann. 2005.  _Understanding Minimalism_.  Cambridge Textbooks in Linguistics. Cambridge University Press.
  * Huebner et al. (2021) Philip A. Huebner, Elior Sulem, Fisher Cynthia, and Dan Roth. 2021.  BabyBERTa: Learning more grammar with small-scale child-directed language.  In _Proceedings of the 25th Conference on Computational Natural Language Learning_ , pages 624–646, Online. Association for Computational Linguistics.
  * Huebner and Willits (2021) Philip A. Huebner and Jon A. Willits. 2021.  Chapter eight - using lexical context to discover the noun category: Younger children have it easier.  In Kara D. Federmeier and Lili Sahakyan, editors, _The Context of Cognition: Emerging Perspectives_ , volume 75 of _Psychology of Learning and Motivation_ , pages 279–331. Academic Press.
  * Jarvis and Pavlenko (2007) Scott Jarvis and Aneta Pavlenko. 2007.  Crosslinguistic influence in language and cognition.
  * Kassner and Schütze (2019) Nora Kassner and Hinrich Schütze. 2019.  Negated and misprimed probes for pretrained language models: Birds can talk, but cannot fly.  In _Annual Meeting of the Association for Computational Linguistics_.
  * Katz et al. (1996) Gary S. Katz, Jeffrey F. Cohn, and Christopher A. Moore. 1996.  A combination of vocal fo dynamic and summary features discriminates between three pragmatic categories of infant-directed speech.  _Child development_ , 67 1:205–17.
  * Kirchhoff and Schimmel (2003) Katrin Kirchhoff and Steven M. Schimmel. 2003.  Statistical properties of infant-directed versus adult-directed speech: insights from speech recognition.  _The Journal of the Acoustical Society of America_ , 117 4 Pt 1:2238–46.
  * Köymen and Kyratzis (2014) Bahar Köymen and Amy Kyratzis. 2014.  Dialogic syntax and complement constructions in toddlers’ peer interactions.  _Cognitive Linguistics_ , 25:497 – 521.
  * Küntay and Slobin (2002) Aylin Küntay and Dan Slobin. 2002.  Putting interaction back into child language: Examples from turkish.  _Psychology of Language and Communication, v.6 (2002)_ , 6.
  * Lin et al. (2015) Jing Lin, F. P. Weerman, and Hedde Zeijlstra. 2015.  Emerging npis: The acquisition of dutch hoeven ‘need’.  _The Linguistic Review_ , 32:333 – 374.
  * Liu et al. (2019) Yinhan Liu, Myle Ott, Naman Goyal, Jingfei Du, Mandar Joshi, Danqi Chen, Omer Levy, Mike Lewis, Luke Zettlemoyer, and Veselin Stoyanov. 2019.  Roberta: A robustly optimized bert pretraining approach.  _ArXiv_ , abs/1907.11692.
  * Ma et al. (2011) Weiyi Ma, Roberta Michnick Golinkoff, Derek M. Houston, and Kathy Hirsh-Pasek. 2011\.  Word learning in infant- and adult-directed speech.  _Language Learning and Development_ , 7:185 – 201.
  * Macwhinney (2000) Brian Macwhinney. 2000.  The childes project: Tools for analyzing talk (third edition): Volume i: Transcription format and programs, volume ii: The database.  _Computational Linguistics - COLI_ , 26:657–657.
  * McRoberts and Best (1997) Gerald McRoberts and Catherine T. Best. 1997.  Accommodation in mean f0 during mother–infant and father–infant vocal interactions: a longitudinal case study.  _Journal of Child Language_ , 24:719 – 736.
  * Mintz (2003) Toben H. Mintz. 2003.  Frequent frames as a cue for grammatical categories in child directed speech.  _Cognition_ , 90:91–117.
  * Nelson et al. (1986) Deborah G Kemler Nelson, Kathy Hirsh-Pasek, Peter W. Jusczyk, and Kimberly Wright Cassidy. 1986.  How the prosodic cues in motherese might assist language learning.  _Journal of Child Language_ , 16:55 – 68.
  * Papadimitriou and Jurafsky (2020) Isabel Papadimitriou and Dan Jurafsky. 2020.  Learning Music Helps You Read: Using transfer to study linguistic structure in language models.  In _Proceedings of the 2020 Conference on Empirical Methods in Natural Language Processing (EMNLP)_ , pages 6829–6839, Online. Association for Computational Linguistics.
  * Papousek et al. (1991) Mechthild Papousek, Hanǔs Papousek, and David T Symmes. 1991.  The meanings of melodies in motherese in tone and stress languages.  _Infant Behavior & Development_, 14:415–440.
  * Pereltsvaig (2006) Asya Pereltsvaig. 2006.  Small nominals.  _Natural Language and Linguistic Theory_ , 24:433–500.
  * Pickering and Ferreira (2008) Martin John Pickering and Victor S. Ferreira. 2008.  Structural priming: a critical review.  _Psychological bulletin_ , 134 3:427–59.
  * Pinker (1995) Steven Pinker. 1995.  _The Language Instinct_.  PENGUIN.
  * Ratner (1986) Nan Bernstein Ratner. 1986.  Durational cues which mark clause boundaries in mother–child speech.  _Journal of Phonetics_ , 14:303–309.
  * Ringbom (2006) Håkan Ringbom. 2006.  _Cross-linguistic Similarity in Foreign Language Learning_.  Multilingual Matters, Bristol, Blue Ridge Summit.
  * Rowe (2012) Meredith L. Rowe. 2012.  A longitudinal investigation of the role of quantity and quality of child-directed speech in vocabulary development.  _Child development_ , 83 5:1762–74.
  * Ruder et al. (2017) Sebastian Ruder, Ivan Vulic, and Anders Søgaard. 2017.  A survey of cross-lingual word embedding models.  _J. Artif. Intell. Res._ , 65:569–631.
  * Sanchez et al. (2019) Alessandro Sanchez, Stephan Meylan, Mika Braginsky, Kyle Macdonald, Daniel Yurovsky, and Michael Frank. 2019.  childes-db: A flexible and reproducible interface to the child language data exchange system.  _Behavior Research Methods_ , 51.
  * Saxton (2009) Matthew L. Saxton. 2009.  The inevitability of child directed speech.
  * Schwab et al. (2021) Juliane Schwab, Mingya Liu, and Jutta L. Mueller. 2021.  On the acquisition of polarity items: 11- to 12-year-olds’ comprehension of german npis and ppis.  _Journal of Psycholinguistic Research_ , 50:1487 – 1509.
  * Snow (1972) Catherine E. Snow. 1972.  Mothers’ speech to children learning language.  _Child Development_ , 43(2):549–565.
  * Soderstrom (2007) Melanie Soderstrom. 2007.  Beyond babytalk: Re-evaluating the nature and content of speech input to preverbal infants.  _Developmental Review_ , 27:501–532.
  * Soderstrom et al. (2008) Melanie Soderstrom, Megan Stratton Blossom, Rina Foygel, and James L. Morgan. 2008\.  Acoustical cues and grammatical units in speech to two preverbal infants*.  _Journal of Child Language_ , 35:869 – 902.
  * Sprouse and Hornstein (2013) Jon Sprouse and Norbert Hornstein. 2013.  _Experimental syntax and island effects: Toward a comprehensive theory of islands_, page 1–18. Cambridge University Press.
  * Stern et al. (1982) Daniel N. Stern, Susan J. Spieker, and K. Mackain. 1982.  Intonation contours as signals in maternal speech to prelinguistic infants.  _Developmental Psychology_ , 18:727–735.
  * Thiessen et al. (2005) Erik D. Thiessen, Emily A. Hill, and Jenny R. Saffran. 2005.  Infant-directed speech facilitates word segmentation.  _Infancy_ , 7(1):53–71.
  * Tieu (2013) Lyn Tieu. 2013.  Logic and grammar in child language: How children acquire the semantics of polarity sensitivity.
  * van der Wal (1996) S. van der Wal. 1996.  Negative polarity items and negation: Tandem acquisition.
  * Vaswani et al. (2017) Ashish Vaswani, Noam M. Shazeer, Niki Parmar, Jakob Uszkoreit, Llion Jones, Aidan N. Gomez, Lukasz Kaiser, and Illia Polosukhin. 2017.  Attention is all you need.  In _NIPS_.
  * Veneziano and Parisse (2010) Edy Veneziano and Christophe Parisse. 2010.  The acquisition of early verbs in french: Assessing the role of conversation and of child-directed speech.  _International Conference on Infant Studies 2010_ , 30.
  * Warstadt et al. (2020) Alex Warstadt, Alicia Parrish, Haokun Liu, Anhad Mohananey, Wei Peng, Sheng-Fu Wang, and Samuel R. Bowman. 2020.  BLiMP: The benchmark of linguistic minimal pairs for English.  _Transactions of the Association for Computational Linguistics_ , 8:377–392.
  * Wolf et al. (2019) Thomas Wolf, Lysandre Debut, Victor Sanh, Julien Chaumond, Clement Delangue, Anthony Moi, Pierric Cistac, Tim Rault, Rémi Louf, Morgan Funtowicz, and Jamie Brew. 2019.  Huggingface’s transformers: State-of-the-art natural language processing.  _ArXiv_ , abs/1910.03771.
  * Wu et al. (2019) Shijie Wu, Alexis Conneau, Haoran Li, Luke Zettlemoyer, and Veselin Stoyanov. 2019\.  Emerging cross-lingual structure in pretrained language models.  _ArXiv_ , abs/1911.01464.
  * Wu and Dredze (2019) Shijie Wu and Mark Dredze. 2019.  Beto, bentz, becas: The surprising cross-lingual effectiveness of BERT.  In _Proceedings of the 2019 Conference on Empirical Methods in Natural Language Processing and the 9th International Joint Conference on Natural Language Processing (EMNLP-IJCNLP)_ , pages 833–844, Hong Kong, China. Association for Computational Linguistics.

##  Appendix A Appendix

Figure 4: Performance of model on all 67 paradigms in BLiMP test suite along
with examples of minimal pairs

###  A.1 Implementation Details

We conduct our experiments using BabyBERTa Huebner et al. (2021), a RoBERTa-
based model Liu et al. (2019), with 8 hidden layers, 8 attention heads, and
dimensionality of the encoder layer being 256, dimensionality of the
intermediate or the feed-forward layer in the transfer based encoder being
1024. We train this model with a learning rate of 1e-4, batch size of 16 and
limit the maximum sequence length to 128. This model is trained for 10 epochs
with max step size of 260. We train this on a single V100 GPU. To tokenize the
words we use Byte Pair Encoder (BPE) Gage (1994) based tokenizer with
vocabulary size set to 52,000 and minimum frequency set to 2. The rest of the
hyperparameters are set to their default settings in the Transformers library
Wolf et al. (2019).

###  A.2 Comprehensive Results

Figure 4 illustrates the organization of the BLiMP test suite and the
performance of all models along with examples of minimal pairs from each of
the 67 paradigms.

####  A.2.1 Organization of BLiMP

BLiMP consists of 67 minimal pair paradigms grouped into 12 distinct
linguistic phenomena: anaphor agreement, argument structure, binding,
control/raising, determiner-noun agreement, ellipsis, filler gap, irregular
forms, island effects, NPI licensing, quantifiers, and subject-verb agreement.
Each paradigm comprises 1,000 sentence pairs in English and isolates specific
phenomenon in syntax, morphology, or semantics. A complete description of each
linguistic phenomenon and finer details of the test suite can be found in
Warstadt et al. (2020).

####  A.2.2 Models

A total of 9 models are used in our study. (1) The Random Baseline model that
is specifically trained such that it acquires no grammatical structure from
the training data and only acquires English vocabulary (2) the Wikipedia-4
model that is trained on scripted ADS English data (3) the English ADS model
that is trained on transcriptions of spontaneous, conversational speech in
English (4) the English CDS model (5) the German CDS model (6) the French CDS
model (7) the Polish CDS model (8) the Japanese CDS model (9) the Indonesian
CDS model, where models 4 through 9 are trained on conversational CDS data
from 6 different languages.