# Behavioural contracts for linear dynamical systems:
input assumptions and output guarantees

B. M. Shali, A. J. van der Schaft, B. Besselink The authors are with the Jan
C. Willems Center for Systems and Control, and the Bernoulli Institute for
Mathematics, Computer Science, and Artificial Intelligence, University of
Groningen, Groningen, The Netherlands; Email<EMAIL_ADDRESS>;
<EMAIL_ADDRESS><EMAIL_ADDRESS>
###### Abstract

We introduce contracts for linear dynamical systems with inputs and outputs.
Contracts are used to express formal specifications on the dynamic behaviour
of such systems through two aspects: assumptions and guarantees. The
assumptions are a linear system that captures the available knowledge about
the dynamic behaviour of the environment in which the system is supposed to
operate. The guarantees are a linear system that captures the required dynamic
behaviour of the system when interconnected with its environment. In addition
to contracts, we also define and characterize notions of contract refinement
and contract conjunction. Contract refinement allows one to determine if a
contract expresses a stricter specifications than another contract. On the
other hand, contract conjunction allows one to combine multiple contracts into
a single contract that fuses the specifications they express.

##  I Introduction

Modern engineering systems, such as smart grids and intelligent transportation
systems, often comprise a large number of interconnected physical components
that are modelled as continuous dynamical systems. Specifications on such
components typically belong to one of two categories: dissipativity or set-
invariance. Dissipativity theory [1] provides an elegant unifying framework
that captures requirements such as stability, passivity or performance, while
set-invariance techniques [2] are  natural candidates for expressing safety
requirements. However, the growing complexity of modern engineering systems
necessitates a theory of specifications that goes beyond dissipativity and
set-invariance.  Namely, these frameworks generally do not permit _dynamic_
specifications: the supply rates that are central to dissipativity theory are
static, as are typical invariant sets. Moreover, when employed as
specifications on components of large-scale interconnected systems, these
frameworks do not allow to explicitly take the (dynamics of the) environment
of such a component into account, possibly making the specification
unnecessarily conservative.

Motivated by these issues, we introduce _contracts_ as specifications for
linear dynamical systems.  Contracts were initially developed in the field of
software engineering [3] but were later adapted to a variety of system classes
in computer science: rely-guarantee contracts were introduced in [4] to deal
with programs that operate concurrently, while the popularisation of interface
theories [5, 6] has led to a boom in the development of contract-based
theories for cyber-physical systems [7, 8]. Consequently, there is a great
diversity of styles and approaches to using contracts as specifications, which
nevertheless follow a common philosophy, namely, to support the independent
design of components within interconnected systems. This philosophy is
captured in the meta-theory of contracts introduced in [9]. This meta-theory
abstracts away the specific design choices made when developing a contract
theory, while still formally defining all relevant concepts.

Inspired by this meta-theory, we define assume-guarantee contracts for linear
dynamical systems with inputs and outputs. As the name suggests, these
contracts consist of assumptions and guarantees, both of which are linear
systems themselves, and which can be used to express specifications for a
system in the following sense. First, the assumptions capture the available
knowledge on the dynamic behaviour of the environment in which the system is
supposed to operate, thus establishing a class of compatible environments.
Second, the guarantees capture the required dynamic behaviour of the system
when interconnected with a compatible environment, thus establishing a class
of implementations. This is formalized very naturally using the behavioural
approach to systems theory [10, 11].

In addition to defining contracts, we characterize contract implementation and
provide a method for verifying that a given linear system implements a given
contract. We also define and characterize the concepts of contract refinement
and contract conjunction, again taking inspiration from the meta-theory in
[9]. The notion of contract refinement allows us to reason when one contract
represents a stricter specification than another contract. On the other hand,
the notion of contract conjunction allows us to construct a contract that
fuses the specifications expressed by several different contracts. As will be
shown later in this paper, these two concepts are intimately related and can
be characterized in a very intuitive and conceptually simple manner.

We regard this work as a first step towards a comprehensive contract theory
for linear dynamical systems. Nevertheless, we note that  ideas from contract
theories have already been used to express specifications on dynamical
systems. Assume-guarantee contracts that capture set-invariance properties
were introduced in [12] and used in [13] for the design of symbolic
controllers. Closely related are also the assume-guarantee contracts for
safety introduced in [14]. However, in contrast to the contracts in this
paper, the contracts presented in [13] and [14] do not allow specifications
involving dynamics, neither in the assumptions nor in the guarantees. This is
not the case for another class of contracts, called parametric assume-
guarantee contracts [15, 16], which were introduced to express specifications
on input-output gain properties. Nonetheless, the latter are only defined for
discrete systems,  whereas we consider continuous systems in this paper. In
fact, the contracts in this paper are most closely related to the contracts
introduced in [17], the main difference being that the external variable there
is not assumed to be an input-output pair. Our work is also closely related to
the work on compositional analysis and assume-guarantee reasoning for linear
systems presented in [18, 19, 20], although these do not explicitly define
contracts.

The remainder of this paper is structured as follows. In Section II, we
discuss the class of systems that will be treated in this paper. There, we
also review the concept of external behaviour together with some relevant
results. In Section III, we define assume-guarantee contracts for the class of
systems discussed in Section II. Moreover, we define and characterize the
notions of contract implementation, contract refinement and contract
conjunction. As such, Section III contains the main contributions of this
paper. These are then demonstrated with an illustrative example in Section IV,
followed by concluding remarks in Section V.

The notation in this paper is mostly standard. The space of smooth functions
from $\mathbb{R}$ to $\mathbb{R}^{n}$ is denoted by
$\mathcal{C}^{\infty}_{n}$. A matrix whose entries are polynomials is called a
_polynomial matrix_ , and a matrix whose entries are rational functions is
called a _rational matrix_. All polynomials are univariate and have real
coefficients. A rational function is _proper_ if the degree of its denominator
is greater than or equal to the degree of its numerator. A rational matrix is
proper if all of its entries are proper rational functions. We say that a
square polynomial matrix $P(s)$ is _invertible_ if there exists a rational
matrix $Q(s)$ such that $P(s)Q(s)=I$. We say that $P(s)$ is _unimodular_ if
there exists a _polynomial_ matrix $Q(s)$ such that $P(s)Q(s)=I$. In both
cases, we say that $Q(s)$ is the _inverse_ of $P(s)$, which we denote by
$P(s)^{-1}$.

##  II Models of physical systems

Consider the linear system

${\Sigma}:\left\\{\begin{aligned} \dot{x}&=Ax+Bu,\\\
y&=Cx+Du,\end{aligned}\right.$ (1)

with state trajectory $x\in\mathcal{C}^{\infty}_{n}$, input trajectory
$u\in\mathcal{C}^{\infty}_{m}$, output trajectory
$y\in\mathcal{C}^{\infty}_{p}$. The system ${\Sigma}$ is regarded as an open
system in which the external variables $u$ and $y$ interact with the
environment, whereas the state $x$ is internal and does not interact with the
environment.

${\Sigma}$$u$$y$ Figure 1: The system ${\Sigma}$ as a signal processor.

More precisely, ${\Sigma}$ is seen as a signal processor that takes an
externally provided input signal $u\in\mathcal{C}^{\infty}_{m}$ and transforms
it to an externally available output signal $y\in\mathcal{C}^{\infty}_{p}$, as
shown by the diagram in Figure 1. Our goal in this paper is to develop a
formal method for expressing specifications on the dynamic behaviour of such a
system. The approach we take requires a method for system comparison; we need
to be able to say when one system behaves “like” another system. This is
formalized quite naturally using the behavioural approach to systems theory
[21, 11]. In particular, we define the _external behaviour_
$\mathfrak{B}\lparen{\Sigma}\rparen$ of ${\Sigma}$ as the linear subspace

$\mathfrak{B}\lparen{\Sigma}\rparen=\left\\{(u,y)\in\mathcal{C}^{\infty}_{m+p}~{}\left|~{}\vphantom{(u,y)\in\mathcal{C}^{\infty}_{m+p}}\exists
x\in\mathcal{C}^{\infty}_{n}\text{ s.t.\ }\eqref{eq:sys_iso}\text{
holds}\right.\right\\}.$

###### Remark 1

The external behaviour can be used to compare systems in the following sense.
Consider two systems ${\Sigma}_{1}$ and ${\Sigma}_{2}$ of the form (1). If
$\mathfrak{B}\lparen{\Sigma}_{1}\rparen\subset\mathfrak{B}\lparen{\Sigma}_{2}\rparen$,
then for a given input, the set of outputs generated by ${\Sigma}_{1}$ is
contained in the set of outputs generated by ${\Sigma}_{2}$, thus
${\Sigma}_{2}$ can be considered to have “richer” dynamics than
${\Sigma}_{1}$. Taking this a step further, if
$\mathfrak{B}\lparen{\Sigma}_{1}\rparen=\mathfrak{B}\lparen{\Sigma}_{2}\rparen$,
then for a given input, the set of outputs generated by ${\Sigma}_{1}$ is
precisely the same as the set of outputs generated by ${\Sigma}_{2}$, hence
${\Sigma}_{1}$ and ${\Sigma}_{2}$ cannot be distinguished on the basis of
external behaviour alone. In such a case, we will view ${\Sigma}_{1}$ and
${\Sigma}_{2}$ as different representations of the same external behaviour
rather than different systems, i.e., we identify the system with its external
behaviour.

There are many different representations of a given external behaviour. As we
are interested in providing specifications only on the external behaviour of a
system, a representation that does not involve the internal state would be
more appropriate for our purposes. With this in mind, consider the linear
system

${\Sigma}:\begin{aligned}
P\left\lparen\tfrac{\textup{d}}{\textup{d}t}\right\rparen
y=Q\left\lparen\tfrac{\textup{d}}{\textup{d}t}\right\rparen u\end{aligned}$
(2)

with $u\in\mathcal{C}^{\infty}_{m}$, $y\in\mathcal{C}^{\infty}_{p}$ and real
polynomial matrices $P(s)$ and $Q(s)$. If $P(s)$ is square and invertible and
$P(s)^{-1}Q(s)$ is a proper rational matrix, then we say that ${\Sigma}$ is in
_input-output form_ [11, Section 3.3]. The system ${\Sigma}$ being in input-
output form guarantees that $u$ can be chosen freely, i.e., for all
$u\in\mathcal{C}^{\infty}_{m}$, there exists $y\in\mathcal{C}^{\infty}_{p}$
such that $(u,y)\in\mathfrak{B}\lparen{\Sigma}\rparen$. In fact, it also
guarantees that none of the components of $y$ can be chosen freely, thus
ensuring that $u$ and $y$ in (2) have the roles of input and output,
respectively. Similarly to before, we define the external behaviour of
${\Sigma}$ of the form (2) as

$\mathfrak{B}\lparen{\Sigma}\rparen=\left\\{(u,y)\in\mathcal{C}^{\infty}_{m+p}~{}\left|~{}\vphantom{(u,y)\in\mathcal{C}^{\infty}_{m+p}}\eqref{eq:sys_io}\text{
holds}\right.\right\\}.$

The external behaviour of a system of the form (1) can be compared to that of
a system of the form (2). In fact, we have the following result on
representations.

###### Theorem 1

[22, Theorem 6.2] Let $\mathfrak{B}\subset\mathcal{C}^{\infty}_{m+p}$ be a
linear subspace. There exists ${\Sigma}_{1}$ of the form (1) such that
$\mathfrak{B}\lparen{\Sigma}_{1}\rparen=\mathfrak{B}$ if and only if there
exists ${\Sigma}_{2}$ of the form (2) in input-output form such that
$\mathfrak{B}\lparen{\Sigma}_{2}\rparen=\mathfrak{B}$.

In view of Theorem 1, it makes no difference whether we consider systems of
the form (1) or systems of the form (2) in input-output form to represent
external behaviours. However, the latter are better suited for the type of
analysis that will be carried out in the following sections. For example,
inclusion of external behaviours has a simple algebraic characterization for
systems of the form (2), as shown next.

###### Theorem 2

Let $\mathfrak{B}_{j}$, $j\in\\{1,2\\}$, be defined as

$\mathfrak{B}_{j}=\left\\{w\in\mathcal{C}^{\infty}_{k}~{}\left|~{}\vphantom{w\in\mathcal{C}^{\infty}_{k}}R_{j}\left\lparen\tfrac{\textup{d}}{\textup{d}t}\right\rparen
w=0\right.\right\\},$

where $R_{j}(s)$ is a polynomial matrix. Then
$\mathfrak{B}_{1}\subset\mathfrak{B}_{2}$ if and only if there exists a
polynomial matrix $M(s)$ such that $R_{2}(s)=M(s)R_{1}(s)$.

###### Proof:

Suppose that there exists a polynomial matrix $M(s)$ satisfying
$R_{2}(s)=M(s)R_{1}(s)$. Let $w\in\mathfrak{B}_{1}$. Then

$R_{2}\left\lparen\tfrac{\textup{d}}{\textup{d}t}\right\rparen
w=M\left\lparen\tfrac{\textup{d}}{\textup{d}t}\right\rparen
R_{1}\left\lparen\tfrac{\textup{d}}{\textup{d}t}\right\rparen w=0,$

hence $w\in\mathfrak{B}_{2}$ and thus
$\mathfrak{B}_{1}\subset\mathfrak{B}_{2}$. Conversely, suppose that
$\mathfrak{B}_{1}\subset\mathfrak{B}_{2}$, i.e.,
$R_{1}\left\lparen\tfrac{\textup{d}}{\textup{d}t}\right\rparen w=0$ implies
$R_{2}\left\lparen\tfrac{\textup{d}}{\textup{d}t}\right\rparen w=0$. Using
[23, Lemma 2.1], it follows that there exists a polynomial matrix $M(s)$ such
that $R_{2}(s)=M(s)R_{1}(s)$. ∎

As a consequence of Theorem 2, given two systems ${\Sigma}_{1}$ and
${\Sigma}_{2}$ of the form (2), we have that
$\mathfrak{B}\lparen{\Sigma}_{1}\rparen\subset\mathfrak{B}\lparen{\Sigma}_{2}\rparen$
if and only if there exists a polynomial matrix $M(s)$ such that

$\begin{bmatrix}P_{2}(s)&-Q_{2}(s)\end{bmatrix}=M(s)\begin{bmatrix}P_{1}(s)&-Q_{1}(s)\end{bmatrix}.$

The following lemma utilizes the Smith canonical form [24, Section 1.8] to
produce a condition for the existence of such a polynomial matrix $M(s)$.

###### Lemma 1

Let $R_{1}(s)$ and $R_{2}(s)$ be polynomial matrices and assume that
$R_{1}(\lambda)$ has full row rank for some $\lambda\in\mathbb{C}$. Moreover,
let $U_{1}(s)$ and $V_{1}(s)$ be unimodular matrices that bring $R_{1}(s)$ to
its Smith canonical form, i.e.,
$R_{1}(s)=U_{1}(s)\begin{bmatrix}D_{1}(s)&0\end{bmatrix}V_{1}(s)$, where
$D_{1}(s)$ is an invertible diagonal polynomial matrix. Then there exists a
polynomial matrix $M(s)$ such that $R_{2}(s)=M(s)R_{1}(s)$ if and only if the
following conditions hold:

  1. 1.

$R_{2}(s)V_{1}(s)^{-1}\begin{bmatrix}0\\\ I\end{bmatrix}=0$;

  2. 2.

$R_{2}(s)V_{1}(s)^{-1}\begin{bmatrix}D_{1}(s)^{-1}\\\ 0\end{bmatrix}$ is a
polynomial matrix.

###### Proof:

Suppose that there exists a polynomial matrix $M(s)$ that satisfies
$R_{2}(s)=M(s)R_{1}(s)$. Then we obtain

$R_{2}(s)V_{1}(s)^{-1}=\begin{bmatrix}M(s)U_{1}(s)D_{1}(s)&0\end{bmatrix},$

hence conditions 1 and 2 hold, the latter because $M(s)U_{1}(s)$ is a
polynomial matrix. For the converse, suppose that conditions 1 and 2 hold.
Condition 2 tells us that

$M(s)=R_{2}(s)V_{1}(s)^{-1}\begin{bmatrix}D_{1}(s)^{-1}\\\
0\end{bmatrix}U_{1}(s)^{-1}$

is a polynomial matrix. In view of condition 1, we obtain

$\displaystyle M(s)R_{1}(s)$
$\displaystyle=R_{2}(s)V_{1}(s)\begin{bmatrix}I&0\\\
0&0\end{bmatrix}V_{1}(s)^{-1}$
$\displaystyle=R_{2}(s)V_{1}(s)\begin{bmatrix}I&0\\\
0&I\end{bmatrix}V_{1}(s)^{-1}=R_{2}(s),$

which concludes the proof. ∎

Note that if ${\Sigma}_{1}$ of the form (2) is in input-output form, then
$[P_{1}(\lambda)\quad Q_{1}(\lambda)]$ has full row rank for some
$\lambda\in\mathbb{C}$ because $P_{1}(s)$ is invertible, hence the assumption
on $R_{1}(s)$ in Lemma 1 is satisfied. More generally, given a behaviour

$\mathfrak{B}=\left\\{w\in\mathcal{C}^{\infty}_{k}~{}\left|~{}\vphantom{w\in\mathcal{C}^{\infty}_{k}}R\left\lparen\tfrac{\textup{d}}{\textup{d}t}\right\rparen
w=0\right.\right\\},$

we can always find a polynomial matrix $R^{\prime}(s)$ such that

$\mathfrak{B}=\left\\{w\in\mathcal{C}^{\infty}_{k}~{}\left|~{}\vphantom{w\in\mathcal{C}^{\infty}_{k}}R^{\prime}\left\lparen\tfrac{\textup{d}}{\textup{d}t}\right\rparen
w=0\right.\right\\}$

and $R^{\prime}(\lambda)$ has full row rank for some $\lambda\in\mathbb{C}$,
hence the assumption on $R_{1}(s)$ in Lemma 1 is not restrictive at all.

We conclude this section with the following remark.

###### Remark 2

Although we have chosen to represent external behaviours without involving a
state variable, it is often convenient to represent a given external behaviour
with the help of so-called _latent variables_. These are variables that are
included in the representation of the external behaviour but are not
necessarily of interest to us. Therefore, most generally, we will consider
systems of the form

${\Sigma}:P\left\lparen\tfrac{\textup{d}}{\textup{d}t}\right\rparen
y=Q\left\lparen\tfrac{\textup{d}}{\textup{d}t}\right\rparen
u+E\left\lparen\tfrac{\textup{d}}{\textup{d}t}\right\rparen l,$ (3)

where $l\in\mathcal{C}^{\infty}_{r}$ is a latent variable and $E(s)$ is a
polynomial matrix. Note that ${\Sigma}$ of the form (1) is actually a latent
variable representation of its external behaviour
$\mathfrak{B}\lparen{\Sigma}\rparen$ with the state $x$ as the latent
variable. We already know that for all ${\Sigma}_{1}$ of the form (1) there
exists ${\Sigma}_{2}$ of the form (2) in input-output form such that
$\mathfrak{B}\lparen{\Sigma}_{1}\rparen=\mathfrak{B}\lparen{\Sigma}_{2}\rparen$.
More generally, the latent variable in ${\Sigma}_{3}$ of the form (3) can
always be eliminated to obtain ${\Sigma}_{2}$ of the form (2) such that
$\mathfrak{B}\lparen{\Sigma}_{3}\rparen=\mathfrak{B}\lparen{\Sigma}_{2}\rparen$,
as follows from [11, Theorem 6.2.6].

##  III Contracts

Consider a system ${\Sigma}$ of the form (2) in input-output form. We want to
express specifications on the external behaviour of such a system. To this
end, as an open system, we can assume that ${\Sigma}$ operates in
interconnection with its environment. Having knowledge about this environment
can ease the design burden of ${\Sigma}$, hence it should be taken into
account when expressing specifications. With this in mind, we will assume that
the environment of ${\Sigma}$ is another system that generates inputs for it.
More precisely, an _environment_ E is a system of the form

$\text{E}:0=E\left\lparen\tfrac{\textup{d}}{\textup{d}t}\right\rparen u,$ (4)

where $u\in\mathcal{C}^{\infty}_{m}$ and $E(s)$ is a real polynomial matrix.
The environment E defines the _input behaviour_

$\mathfrak{B}_{\textup{i}}\lparen\text{E}\rparen=\left\\{u\in\mathcal{C}^{\infty}_{m}~{}\left|~{}\vphantom{u\in\mathcal{C}^{\infty}_{m}}\eqref{eq:env}\text{
holds}\right.\right\\}.$

The interconnection of ${\Sigma}$ with the environment E is obtained by
setting the input generated by E as input of ${\Sigma}$. This results in the
interconnection

$\text{E}\wedge{\Sigma}:\begin{bmatrix}P\left\lparen\tfrac{\textup{d}}{\textup{d}t}\right\rparen\\\\[2.84526pt]
0\end{bmatrix}y=\begin{bmatrix}Q\left\lparen\tfrac{\textup{d}}{\textup{d}t}\right\rparen\\\\[2.84526pt]
E\left\lparen\tfrac{\textup{d}}{\textup{d}t}\right\rparen\end{bmatrix}u,$ (5)

which is represented graphically in Figure 2.

E${\Sigma}$$u$$y$ Figure 2: The interconnection $\text{E}\wedge{\Sigma}$.

As a means of expressing specifications on the external behaviour of
${\Sigma}$, we are interested in guaranteeing properties of ${\Sigma}$ when
interconnected with relevant environments E. In particular, if we define the
_output behaviour_

$\mathfrak{B}_{\textup{o}}\lparen\text{E}\wedge{\Sigma}\rparen=\left\\{y\in\mathcal{C}^{\infty}_{p}~{}\left|~{}\vphantom{y\in\mathcal{C}^{\infty}_{p}}\eqref{eq:env_sys}\text{
holds}\right.\right\\},$

then we want to guarantee properties of
$\mathfrak{B}_{\textup{o}}\lparen\text{E}\wedge{\Sigma}\rparen$ for all
relevant environments E. We will make this explicit by introducing two
systems: _assumptions_ A and _guarantees_ ${\Gamma}$. Assumptions A are a
system of the form

$\text{A}:0=A\left\lparen\tfrac{\textup{d}}{\textup{d}t}\right\rparen u,$ (6)

and, like environments, they represent the input behaviour

$\mathfrak{B}_{\textup{i}}\lparen\text{A}\rparen=\left\\{u\in\mathcal{C}^{\infty}_{m}~{}\left|~{}\vphantom{u\in\mathcal{C}^{\infty}_{m}}\eqref{eq:ass}\text{
holds}\right.\right\\}.$

On the other hand, guarantees ${\Gamma}$ are a system of the form

${\Gamma}:G\left\lparen\tfrac{\textup{d}}{\textup{d}t}\right\rparen y=0,$ (7)

and they represent the output behaviour

$\mathfrak{B}_{\textup{o}}\lparen{\Gamma}\rparen=\left\\{y\in\mathcal{C}^{\infty}_{p}~{}\left|~{}\vphantom{y\in\mathcal{C}^{\infty}_{p}}\eqref{eq:gar}\text{
holds}\right.\right\\}.$

###### Remark 3

Although we define environments, assumptions and guarantees as systems
involving a single variable, we might represent the behaviours they define
with the help of latent variables, as in the general form (3).  Since latent
variables can always be eliminated (recall Remark 2), the representations (4),
(6) and (7) do not pose a restriction.

With assumptions and guarantees defined, we are ready to introduce the
definition of a contract.

###### Definition 1

A _contract_ $\mathcal{C}$ is a pair $(\text{A},{\Gamma})$ of assumptions A
and guarantees ${\Gamma}$.

Contracts can be used to express formal specifications for the external
behaviour of systems ${\Sigma}$ of the form (2) in input-output form, as
captured in the following definition.

###### Definition 2

An environment E is _compatible_ with the contract
$\mathcal{C}=(\text{A},{\Gamma})$ if
$\mathfrak{B}_{\textup{i}}\lparen\text{E}\rparen\subset\mathfrak{B}_{\textup{i}}\lparen\text{A}\rparen$.
A system ${\Sigma}$ of the form (2) in input-output form _implements_
$\mathcal{C}$ if
$\mathfrak{B}_{\textup{o}}\lparen\text{E}\wedge{\Sigma}\rparen\subset\mathfrak{B}_{\textup{o}}\lparen{\Gamma}\rparen$
for all environments E compatible with $\mathcal{C}$. In such a case, we say
that ${\Sigma}$ is an _implementation_ of $\mathcal{C}$.

In other words, an environment is compatible with a contract if the inputs
that it generates can be generated by the assumptions, and a system implements
a contract if the outputs that it generates when interconnected with any
compatible environment can be generated by the guarantees. A contract thus
gives a formal specification for the external behaviour of a system through
two aspects. First, it specifies (by the assumptions) the class of
environments in which the system is supposed to operate. Second, it
characterizes the required external behaviour of the system through the
guarantees, which the system needs to satisfy for any compatible environment.
We emphasize that both the assumptions and guarantees are dynamical systems,
hence the specification that a contract expresses is also dynamic.

Although contract implementation is defined using the class of compatible
environments, verifying whether a system ${\Sigma}$ of the form (2) in input-
output form is an implementation can be done directly via the assumptions and
guarantees, i.e., without explicitly constructing the class of compatible
environments. This is stated in the following theorem, which is represented
graphically in Figure 3.

###### Theorem 3

A system ${\Sigma}$ of the form (2) is an implementation of
$\mathcal{C}=(\text{A},{\Gamma})$ if and only if
$\mathfrak{B}_{\textup{o}}\lparen\text{A}\wedge{\Sigma}\rparen\subset\mathfrak{B}_{\textup{o}}\lparen{\Gamma}\rparen$.

###### Proof:

Suppose that
$\mathfrak{B}_{\textup{o}}\lparen\text{A}\wedge{\Sigma}\rparen\subset\mathfrak{B}_{\textup{o}}\lparen{\Gamma}\rparen$.
Note that $y\in\mathfrak{B}_{\textup{o}}\lparen\text{A}\wedge{\Sigma}\rparen$
if and only if there exists
$u\in\mathfrak{B}_{\textup{i}}\lparen\text{A}\rparen$ such that
$(u,y)\in\mathfrak{B}\lparen{\Sigma}\rparen$. With this in mind, let E be an
environment compatible with $\mathcal{C}$, and let
$y\in\mathfrak{B}_{\textup{o}}\lparen\text{E}\wedge{\Sigma}\rparen$. Then
there exists
$u\in\mathfrak{B}_{\textup{i}}\lparen\text{E}\rparen\subset\mathfrak{B}_{\textup{i}}\lparen\text{A}\rparen$
such that $(u,y)\in\mathfrak{B}\lparen{\Sigma}\rparen$, hence
$y\in\mathfrak{B}_{\textup{o}}\lparen\text{A}\wedge{\Sigma}\rparen\subset\mathfrak{B}_{\textup{o}}\lparen{\Gamma}\rparen$.
This shows that
$\mathfrak{B}_{\textup{o}}\lparen\text{E}\wedge{\Sigma}\rparen\subset\mathfrak{B}_{\textup{o}}\lparen{\Gamma}\rparen$
for all compatible environments E and thus ${\Sigma}$ is an implementation of
$\mathcal{C}$. Conversely, suppose that ${\Sigma}$ is an implementation of
$\mathcal{C}$. Since A is a compatible environment of $\mathcal{C}$, it
follows that
$\mathfrak{B}_{\textup{o}}\lparen\text{A}\wedge{\Sigma}\rparen\subset\mathfrak{B}_{\textup{o}}\lparen{\Gamma}\rparen$.
∎

A${\Sigma}$$\text{A}\wedge{\Sigma}$$u$$y$$\subset$${\Gamma}$$y$ Figure 3:
Implementation of $\mathcal{C}=(\text{A},{\Gamma})$.

###### Remark 4

Theorem 3 allows us to verify that ${\Sigma}$ of the form (2) is an
implementation of $\mathcal{C}=(\text{A},{\Gamma})$ provided that we can
verify that
$\mathfrak{B}_{\textup{o}}\lparen\text{A}\wedge{\Sigma}\rparen\subset\mathfrak{B}_{\textup{o}}\lparen{\Gamma}\rparen$.
The latter can be done in two steps. First, in view of [11, Theorem 6.2.6], we
can eliminate the variable $u$ from $\text{A}\wedge{\Sigma}$ to obtain

$\mathfrak{B}_{\textup{o}}\lparen\text{A}\wedge{\Sigma}\rparen=\left\\{y\in\mathcal{C}^{\infty}_{p}~{}\left|~{}\vphantom{y\in\mathcal{C}^{\infty}_{p}}R\left\lparen\tfrac{\textup{d}}{\textup{d}t}\right\rparen
y=0\right.\right\\}$ (8)

for some polynomial matrix $R(s)$, where $R(\lambda)$ has full row rank for
some $\lambda\in\mathbb{C}$. Second, from Theorem 2 we know that
$\mathfrak{B}_{\textup{o}}\lparen\text{A}\wedge\text{E}\rparen\subset\mathfrak{B}_{\textup{o}}\lparen{\Gamma}\rparen$
if and only if there exists a polynomial matrix $M(s)$ such that
$G(s)=M(s)R(s)$, where the latter can be verified using Lemma 1. Note that due
to Theorem 1, Theorem 3 is also valid for systems ${\Sigma}$ of the form (1).
For the latter, we need to eliminate $x$ as well as $u$ in order to obtain a
polynomial matrix $R(s)$ such that (8) holds.

A distinguishing feature of using contracts for specifications is that
contracts themselves can be compared through a notion of refinement.

###### Definition 3

The contract $\mathcal{C}_{1}$ _refines_ the contract $\mathcal{C}_{2}$,
denoted by $\mathcal{C}_{1}\preccurlyeq\mathcal{C}_{2}$, if all compatible
environments of $\mathcal{C}_{2}$ are compatible environments of
$\mathcal{C}_{1}$ and all implementations of $\mathcal{C}_{1}$ are
implementations of $\mathcal{C}_{2}$.

We have that $\mathcal{C}_{1}$ refines $\mathcal{C}_{2}$ if it specifies
stricter guarantees that have to be satisfied for a larger class of
environments. In such a case, it is clear that $\mathcal{C}_{1}$ expresses a
more restrictive specification than $\mathcal{C}_{2}$. Just like contract
implementation, contract refinement can be verified on the basis of
assumptions and guarantees alone, i.e., without explicitly constructing the
classes of compatible environments and implementations of the two contracts.
This is the content of the following theorem, whose proof can be found in the
appendix.

###### Theorem 4

The contract $\mathcal{C}_{1}=(\text{A}_{1},{\Gamma}_{1})$ refines the
contract $\mathcal{C}_{2}=(\text{A}_{2},{\Gamma}_{2})$ if and only if
$\mathfrak{B}_{\textup{i}}\lparen\text{A}_{2}\rparen\subset\mathfrak{B}_{\textup{i}}\lparen\text{A}_{1}\rparen$
and
$\mathfrak{B}_{\textup{o}}\lparen{\Gamma}_{1}\rparen\subset\mathfrak{B}_{\textup{o}}\lparen{\Gamma}_{2}\rparen$.

If a contract $\mathcal{C}$ refines both contracts $\mathcal{C}_{1}$ and
$\mathcal{C}_{2}$, then $\mathcal{C}$ captures both the specifications that
$\mathcal{C}_{1}$ expresses and the specifications that $\mathcal{C}_{2}$
expresses. This suggests that multiple contracts can be combined into a single
contract that represents a fusion of their specifications. This motivates the
following definition.

###### Definition 4

The _conjunction_ of contracts $\mathcal{C}_{1}$ and $\mathcal{C}_{2}$,
denoted by $\mathcal{C}_{1}\wedge\mathcal{C}_{2}$, is the largest (with
respect to contract refinement) contract that refines both $\mathcal{C}_{1}$
and $\mathcal{C}_{2}$.

Note that the largest contract that refines both $\mathcal{C}_{1}$ and
$\mathcal{C}_{2}$ corresponds to the least restrictive contract that fuses the
specifications of $\mathcal{C}_{1}$ and $\mathcal{C}_{2}$. This suggests that
the guarantees of $\mathcal{C}_{1}\wedge\mathcal{C}_{2}$ should be the
guarantees common to $\mathcal{C}_{1}$ and $\mathcal{C}_{2}$ and nothing more,
and the assumptions of $\mathcal{C}_{1}\wedge\mathcal{C}_{2}$ should include
the assumptions of both $\mathcal{C}_{1}$ and $\mathcal{C}_{2}$ and nothing
less. The following lemma captures some of this intuition.

###### Lemma 2

A contract $\mathcal{C}=(\text{A},{\Gamma})$ refines both contracts
$\mathcal{C}_{1}=(\text{A}_{1},{\Gamma}_{1})$ and
$\mathcal{C}_{2}=(\text{A}_{2},{\Gamma}_{2})$ if and only if
$\mathfrak{B}_{\textup{i}}\lparen\text{A}_{1}\rparen+\mathfrak{B}_{\textup{i}}\lparen\text{A}_{2}\rparen\subset\mathfrak{B}_{\textup{i}}\lparen\text{A}\rparen$
and
$\mathfrak{B}_{\textup{o}}\lparen{\Gamma}\rparen\subset\mathfrak{B}_{\textup{o}}\lparen{\Gamma}_{1}\rparen\cap\mathfrak{B}_{\textup{o}}\lparen{\Gamma}_{2}\rparen$.

###### Proof:

Due to Theorem 4, the contract $\mathcal{C}$ refines both contracts
$\mathcal{C}_{1}$ and $\mathcal{C}_{2}$ if and only if
$\mathfrak{B}_{\textup{i}}\lparen\text{A}_{i}\rparen\subset\mathfrak{B}_{\textup{i}}\lparen\text{A}\rparen$
and
$\mathfrak{B}_{\textup{o}}\lparen{\Gamma}\rparen\subset\mathfrak{B}_{\textup{o}}\lparen{\Gamma}_{i}\rparen$
for all $i\in\\{1,2\\}$. Since behaviours are linear, this is the case if and
only if
$\mathfrak{B}_{\textup{i}}\lparen\text{A}_{1}\rparen+\mathfrak{B}_{\textup{i}}\lparen\text{A}_{2}\rparen\subset\mathfrak{B}_{\textup{i}}\lparen\text{A}\rparen$
and
$\mathfrak{B}_{\textup{o}}\lparen{\Gamma}\rparen\subset\mathfrak{B}_{\textup{o}}\lparen{\Gamma}_{1}\rparen\cap\mathfrak{B}_{\textup{o}}\lparen{\Gamma}_{2}\rparen$.
∎

In view of Theorem 4, Lemma 2 tells us that if there exist assumptions A with
$\mathfrak{B}_{\textup{i}}\lparen\text{A}\rparen=\mathfrak{B}_{\textup{i}}\lparen\text{A}_{1}\rparen+\mathfrak{B}_{\textup{i}}\lparen\text{A}_{2}\rparen$
and guarantees ${\Gamma}$ with
$\mathfrak{B}_{\textup{o}}\lparen{\Gamma}\rparen=\mathfrak{B}_{\textup{o}}\lparen{\Gamma}_{1}\rparen\cap\mathfrak{B}_{\textup{o}}\lparen{\Gamma}_{2}\rparen$,
then $(\text{A},{\Gamma})$ is the largest contract that refines both
$\mathcal{C}_{1}=(\text{A}_{1},{\Gamma}_{1})$ and
$\mathcal{C}_{2}=(\text{A}_{2},{\Gamma}_{2})$, hence
$\mathcal{C}_{1}\wedge\mathcal{C}_{2}=(\text{A},{\Gamma})$. Fortunately, such
assumptions and guarantees exist and are defined below.

###### Definition 5

The _join_ of assumptions $\text{A}_{1}$ and $\text{A}_{2}$, denoted by
$\text{A}_{1}\vee\text{A}_{2}$, is defined as the assumptions

$\text{A}_{1}\vee\text{A}_{2}:\begin{bmatrix}I&I\\\
A_{1}\left\lparen\tfrac{\textup{d}}{\textup{d}t}\right\rparen&0\\\
0&A_{2}\left\lparen\tfrac{\textup{d}}{\textup{d}t}\right\rparen\end{bmatrix}\begin{bmatrix}l_{1}\\\
l_{2}\end{bmatrix}=\begin{bmatrix}I\\\ 0\\\ 0\end{bmatrix}u.$

The _meet_ of guarantees ${\Gamma}_{1}$ and ${\Gamma}_{2}$, denoted by
${\Gamma}_{1}\wedge{\Gamma}_{2}$, is defined as the guarantees

${\Gamma}_{1}\wedge{\Gamma}_{2}:\begin{bmatrix}G_{1}\left\lparen\tfrac{\textup{d}}{\textup{d}t}\right\rparen\\\\[2.84526pt]
G_{2}\left\lparen\tfrac{\textup{d}}{\textup{d}t}\right\rparen\end{bmatrix}y=0.\vspace{2mm}$

We remark that although the join $\text{A}_{1}\vee\text{A}_{2}$ is represented
with latent variables, these can be eliminated to obtain assumptions as in
(6). However, the latent variable representation clearly indicates that every
$u\in\mathfrak{B}_{\textup{i}}\lparen\text{A}_{1}\vee\text{A}_{2}\rparen$ is
obtained by summing
$l_{1}\in\mathfrak{B}_{\textup{i}}\lparen\text{A}_{1}\rparen$ and
$l_{2}\in\mathfrak{B}_{\textup{i}}\lparen\text{A}_{2}\rparen$. Having defined
the join and meet, we can now write the conjunction of contracts
$\mathcal{C}_{1}$ and $\mathcal{C}_{2}$ explicitly.

###### Theorem 5

The conjunction of contracts $\mathcal{C}_{1}=(\text{A}_{1},{\Gamma}_{1})$ and
$\mathcal{C}_{2}=(\text{A}_{2},{\Gamma}_{2})$ is given by

$\mathcal{C}_{1}\wedge\mathcal{C}_{2}=(\text{A}_{1}\vee\text{A}_{2},{\Gamma}_{1}\wedge{\Gamma}_{2}).\vspace{2mm}$

###### Proof:

It is easy to see that
$\mathfrak{B}_{\textup{i}}\lparen\text{A}_{1}\vee\text{A}_{2}\rparen=\mathfrak{B}_{\textup{i}}\lparen\text{A}_{1}\rparen+\mathfrak{B}_{\textup{i}}\lparen\text{A}_{2}\rparen$
and
$\mathfrak{B}_{\textup{o}}\lparen{\Gamma}_{1}\wedge{\Gamma}_{2}\rparen=\mathfrak{B}_{\textup{o}}\lparen{\Gamma}_{1}\rparen\cap\mathfrak{B}_{\textup{o}}\lparen{\Gamma}_{2}\rparen$.
Therefore, due to Lemma 2 and Theorem 4,
$(\text{A}_{1}\vee\text{A}_{2},{\Gamma}_{1}\wedge{\Gamma}_{2})$ is the largest
contract that refines both $\mathcal{C}_{1}$ and $\mathcal{C}_{2}$. ∎

Theorem 5 allows us to check when ${\Sigma}$ of the form (2) in input-output
form is simultaneously an implementation of $\mathcal{C}_{1}$ and
$\mathcal{C}_{2}$. Indeed, this is the case if and only if ${\Sigma}$
implements the conjunction $\mathcal{C}_{1}\wedge\mathcal{C}_{2}$, whose
assumptions and guarantees we can compute explicitly. Given the assumptions
and guarantees of $\mathcal{C}_{1}\wedge\mathcal{C}_{2}$, we have already
explained how to verify that ${\Sigma}$ implements
$\mathcal{C}_{1}\wedge\mathcal{C}_{2}$ in Remark 4.

##  IV Illustrative example

In this section, we will illustrate the concepts and results from last section
with a simple example. To this end, suppose that we need to design a car
component that does not vibrate while the car is moving, e.g., the driver’s
seat. For simplicity, we only consider the vertical motion of the car, which
we describe by a quarter car model, as shown in Figure 4. The model consists
of two masses: the mass $m_{1}$ of the body and the mass $m_{2}$ of the wheel.
The wheel is attached to the body of the car through a spring with constant
$k_{1}$ and a damper with coefficient $b$. The wheel is connected to the
ground by a tire represented as a spring with constant $k_{2}$. Let $u_{1}$
and $u_{2}$ be the vertical positions of the body and the wheel, respectively,
and let $l$ be the reference signal from the ground. Then the dynamics of
$u_{1}$ and $u_{2}$ are given by

$\displaystyle\vspace{-1mm}m_{1}\ddot{u}_{1}$
$\displaystyle=-b(\dot{u}_{1}-\dot{u}_{2})-k_{1}(u_{1}-u_{2}),$ (9)
$\displaystyle m_{2}\ddot{u}_{2}$
$\displaystyle=-b(\dot{u}_{2}-\dot{u}_{1})-k_{1}(u_{2}-u_{1})-k_{2}(u_{2}-l).\vspace{-1mm}$
(10)

$m_{2}$$m_{1}$$d_{1}$$k_{1}$$k_{2}$$u_{1}$$u_{2}$$l$E${\Sigma}$$u$$y$ Figure
4: Quarter car model of the environment.

Now, suppose that the vertical position of our component is controlled
electronically on the basis of the positions of the body and the wheel. In
other words, the input to our system is given by $u=[u_{1}\quad
u_{2}]^{\top}$. The component, with vertical position $y$, will be devoid of
vibrations if it has zero acceleration, hence the desired guarantees
${\Gamma}$ are given by (7) with $G(s)=s^{2}$. If there is no information
about the reference signal $l$, i.e., there is no information about the
surface on which the car moves, then the available information about $u$ is
given by (9). Therefore, the assumptions A are given by $\eqref{eq:ass}$ with
$A(s)=\begin{bmatrix}m_{1}s^{2}+bs+k_{1}&-bs-k_{1}\end{bmatrix}$ and our
specification is captured by the contract $\mathcal{C}=(\text{A},{\Gamma})$.

An implementation of $\mathcal{C}$ is given by the system

${\Sigma}:\left\\{\begin{aligned} \dot{x}&=\begin{bmatrix}0&1\\\
0&0\end{bmatrix}x+\tfrac{1}{m_{1}}\begin{bmatrix}b&-b\\\
k_{1}&-k_{1}\end{bmatrix}u,\\\\[5.69054pt]
y&=\begin{bmatrix}1&0\end{bmatrix}x+\begin{bmatrix}1&0\end{bmatrix}u\rule[-6.02773pt]{0.0pt}{0.0pt}.\end{aligned}\right.$

Indeed, we can eliminate $x$ from ${\Sigma}$ to obtain

$\tfrac{\textup{d}^{2}}{\textup{d}t^{2}}y=\tfrac{\textup{d}^{2}}{\textup{d}t^{2}}u_{1}+\tfrac{b}{m_{1}}\tfrac{\textup{d}}{\textup{d}t}(u_{1}-u_{2})+\tfrac{k_{1}}{m_{1}}(u_{1}-u_{2})$

where the right-hand side is zero for all
$u\in\mathfrak{B}_{\textup{i}}\lparen\text{A}\rparen$. Then

$\mathfrak{B}_{\textup{o}}\lparen\text{A}\wedge{\Sigma}\rparen=\left\\{y\in\mathcal{C}^{\infty}_{p}~{}\left|~{}\vphantom{y\in\mathcal{C}^{\infty}_{p}}\tfrac{\textup{d}^{2}}{\textup{d}t^{2}}y=0\right.\right\\},$

and thus
$\mathfrak{B}_{\textup{o}}\lparen\text{A}\wedge{\Sigma}\rparen=\mathfrak{B}_{\textup{o}}\lparen{\Gamma}\rparen$,
which shows that ${\Sigma}$ is an implementation of $\mathcal{C}$ because of
Theorem 3.

Alternatively, if there is information about the reference signal $l$, then we
can use that information to construct a contract which is easier to implement.
For example, if we assume that $l=0$, then (9) and (10) yield the assumptions

$\text{A}_{0}:A_{0}\left\lparen\tfrac{\textup{d}}{\textup{d}t}\right\rparen
u=0,$

where the polynomial matrix $A_{0}(s)$ is given by

$A_{0}(s)=\begin{bmatrix}m_{1}s^{2}+bs+k_{1}&-bs-k_{1}\\\ -bs-
k_{1}&m_{2}s^{2}+bs+k_{1}+k_{2}\end{bmatrix}.$

Consequently, the contract $\mathcal{C}_{0}=(\text{A}_{0},{\Gamma})$ is
implemented by

${\Sigma}_{0}:\left\\{\begin{aligned} \dot{x}&=\begin{bmatrix}0&1\\\
0&0\end{bmatrix}x+\tfrac{1}{m_{2}}\begin{bmatrix}-b&b\\\
-k_{1}&k_{1}+k_{2}\end{bmatrix}u,\\\\[5.69054pt]
y&=\begin{bmatrix}1&0\end{bmatrix}x+\begin{bmatrix}0&1\end{bmatrix}u\rule[-6.02773pt]{0.0pt}{0.0pt}.\end{aligned}\right.$

Indeed, eliminating $x$ from ${\Sigma}_{0}$ yields

$\tfrac{\textup{d}^{2}}{\textup{d}t^{2}}y=\tfrac{\textup{d}^{2}}{\textup{d}t^{2}}u_{2}+\tfrac{b}{m_{2}}\tfrac{\textup{d}}{\textup{d}t}(u_{2}-u_{1})+\tfrac{k_{1}}{m_{2}}(u_{2}-u_{1})+\tfrac{k_{2}}{m_{2}}u_{2},$

where the right-hand side is zero for all
$u\in\mathfrak{B}_{\textup{i}}\lparen\text{A}_{0}\rparen$, hence
$\mathfrak{B}_{\textup{o}}\lparen\text{A}_{0}\wedge{\Sigma}_{0}\rparen=\mathfrak{B}_{\textup{o}}\lparen{\Gamma}\rparen$.
Note that ${\Sigma}_{0}$ does not implement $\mathcal{C}$ because the right-
hand side of the latter is not necessarily zero for all
$u\in\mathfrak{B}_{\textup{i}}\lparen\text{A}\rparen$. However, we clearly
have that
$\mathfrak{B}_{\textup{i}}\lparen\text{A}_{0}\rparen\subset\mathfrak{B}_{\textup{i}}\lparen\text{A}\rparen$,
hence $\mathcal{C}$ refines $\mathcal{C}_{0}$ due to Theorem 4. This implies
that ${\Sigma}$ implements $\mathcal{C}_{0}$, and more generally, that any
implementation of $\mathcal{C}$ is an implementation of $\mathcal{C}_{0}$. Of
course, we already expected a component that works for arbitrary reference
signal $l$ to work for $l=0$ in particular.

Finally, we might want to take into account different possibilities for the
reference signal $l$. For example, we might want to consider reference signals
that satisfy $\dot{l}=0$ (“flat” road) and $\ddot{l}+l=0$ (“wavy” road).
Substituting these in equations (9) and (10) results in the assumptions

$\text{A}_{1}:A_{1}\left\lparen\tfrac{\textup{d}}{\textup{d}t}\right\rparen
u=0,\quad\text{A}_{2}:A_{2}\left\lparen\tfrac{\textup{d}}{\textup{d}t}\right\rparen
u=0,$

with polynomial matrices $A_{1}(s)$ and $A_{2}(s)$ given by

$A_{1}(s)=\begin{bmatrix}1&0\\\ 0&s\end{bmatrix}A_{0}(s),\quad
A_{2}(s)=\begin{bmatrix}1&0\\\ 0&s^{2}+1\end{bmatrix}A_{0}(s).$

Then a component that works for a “flat” road needs to satisfy the contract
$\mathcal{C}_{1}=(\text{A}_{1},{\Gamma})$, and a component that works for a
“wavy” road needs to satisfy the contract
$\mathcal{C}_{2}=(\text{A}_{2},{\Gamma})$. Therefore, a component that works
for both roads needs to satisfy the conjunction
$\mathcal{C}_{1}\wedge\mathcal{C}_{2}=(\text{A}_{1}\vee\text{A}_{2},{\Gamma})$,
which we have obtained using Theorem 5. Note that $\mathcal{C}$ refines both
$\mathcal{C}_{1}$ and $\mathcal{C}_{2}$, while $\mathcal{C}_{1}$ and
$\mathcal{C}_{2}$ both refine $\mathcal{C}_{0}$. Therefore, $\mathcal{C}$
refines the conjunction $\mathcal{C}_{1}\wedge\mathcal{C}_{2}$, which in turn
refines $\mathcal{C}_{0}$.

##  V Conclusion

We have introduced assume-guarantee contracts for linear dynamical systems
with inputs and outputs. We defined these as a pair of linear systems, called
assumptions and guarantees, which were used to characterize the class of
compatible environments and the class of implementations through the notion of
system behaviour, and in particular, by inclusion of behaviours. In addition
to defining contracts, we also characterized contract implementation and
proposed a method for verifying it. Moreover, we characterized contract
refinement by mirrored inclusions of behaviours of assumptions and guarantees.
Using this, we provided an explicit characterization of contract conjunction
in terms of the join of assumptions and meet of guarantees. We also
demonstrated our setup and results with an illustrative example. Finally, we
still require a suitable notion of contract composition. This would enable the
component-based analysis and design of interconnected systems, hence its
definition and characterization will be the focus of future work.

Before we give the proof of Theorem 4, we will state and prove an intermediate
result involving autonomous systems. A system ${\Sigma}$ is called
_autonomous_ if

$\mathfrak{B}_{\textup{o}}\lparen{\Sigma}\rparen=\left\\{y\in\mathcal{C}^{\infty}_{p}~{}\left|~{}\vphantom{y\in\mathcal{C}^{\infty}_{p}}P\left\lparen\tfrac{\textup{d}}{\textup{d}t}\right\rparen
y=0\right.\right\\}$

for some square and invertible polynomial matrix $P(s)$.

###### Lemma 3

If
$\mathfrak{B}_{\textup{o}}\lparen{\Sigma}\rparen\subset\mathfrak{B}_{\textup{o}}\lparen{\Gamma}_{1}\rparen$
implies
$\mathfrak{B}_{\textup{o}}\lparen{\Sigma}\rparen\subset\mathfrak{B}_{\textup{o}}\lparen{\Gamma}_{2}\rparen$
for all autonomous ${\Sigma}$, then
$\mathfrak{B}_{\textup{o}}\lparen{\Gamma}_{1}\rparen\subset\mathfrak{B}_{\textup{o}}\lparen{\Gamma}_{2}\rparen$.

###### Proof:

Let ${\Gamma}_{1}$ and ${\Gamma}_{2}$ be given by

${\Gamma}_{1}:G_{1}\left\lparen\tfrac{\textup{d}}{\textup{d}t}\right\rparen
y=0\quad\text{and}\quad{\Gamma}_{2}:G_{2}\left\lparen\tfrac{\textup{d}}{\textup{d}t}\right\rparen
y=0$

for some polynomial matrices $G_{1}(s)$ and $G_{2}(s)$. Furthermore, let
$U(s)$ and $V(s)$ be unimodular matrices that bring $G_{1}(s)$ to its Smith
canonical form, that is,

$G_{1}(s)=U(s)\begin{bmatrix}G_{11}(s)&0\\\ 0&0\end{bmatrix}V(s)$

where $G_{11}(s)$ is an invertible diagonal polynomial matrix. Then, for any
positive integer $k$, the system

${\Sigma}_{k}:\begin{bmatrix}G_{11}\left\lparen\tfrac{\textup{d}}{\textup{d}t}\right\rparen&0\\\
0&\frac{\textup{d}^{k}}{\textup{d}t^{k}}I\end{bmatrix}V\left\lparen\tfrac{\textup{d}}{\textup{d}t}\right\rparen
y=0$

is autonomous and, due to Theorem 2 and the fact that

$G_{1}(s)=U(s)\begin{bmatrix}I&0\\\
0&0\end{bmatrix}\begin{bmatrix}G_{11}(s)&0\\\ 0&s^{k}I\end{bmatrix}V(s),$ (11)

it is such that
$\mathfrak{B}_{\textup{o}}\lparen{\Sigma}_{k}\rparen\subset\mathfrak{B}_{\textup{o}}\lparen{\Gamma}_{1}\rparen$.
From this it follows that
$\mathfrak{B}_{\textup{o}}\lparen{\Sigma}_{k}\rparen\subset\mathfrak{B}_{\textup{o}}\lparen{\Gamma}_{2}\rparen$,
hence, for any positive integer $k$, there exists a polynomial matrix
$M_{k}(s)$ such that

$G_{2}(s)=M_{k}(s)\begin{bmatrix}G_{11}(s)&0\\\ 0&s^{k}I\end{bmatrix}V(s).$
(12)

We can partition $M_{k}(s)=[M_{k1}(s)\quad M_{k2}(s)]$ to obtain

$G_{2}(s)V(s)^{-1}=\begin{bmatrix}M_{k1}(s)G_{11}(s)&M_{k2}(s)s^{k}\end{bmatrix}.$

Since $G_{2}(s)V(s)^{-1}$ is independent of $k$, it follows that
$M_{k2}(s)s^{k}$ is also independent of $k$. In particular, the degree of
$M_{k2}(s)s^{k}$, defined as the maximum of the degrees of its entries, is the
same for all $k$. But then taking $k$ to be greater than this degree implies
that $M_{k2}(s)=0$. Indeed, if $M_{k2}(s)\neq 0$, then the degree of
$M_{k2}(s)s^{k}$ is greater than or equal to $k$, hence it is greater than
itself, which is a contradiction. This implies that $M_{k2}(s)s^{k}=0$ for
some $k$, which implies that $M_{k2}(s)s^{k}=0$ for all $k$ since
$M_{k2}(s)s^{k}$ is independent of $k$. Let $k$ be fixed. Then $M_{k2}(s)=0$
because $M_{k2}(s)s^{k}=0$ and we can write

$M_{k}(s)=M_{k}(s)\begin{bmatrix}I&0\\\
0&0\end{bmatrix}=M_{k}(s)U(s)^{-1}U(s)\begin{bmatrix}I&0\\\ 0&0\end{bmatrix}.$

Finally, it follows that (12) can be rewritten as

$G_{2}(s)=M_{k}(s)U(s)^{-1}U(s)\begin{bmatrix}I&0\\\
0&0\end{bmatrix}\begin{bmatrix}G_{11}(s)&0\\\ 0&s^{k}I\end{bmatrix}V(s),$

which yields $G_{2}(s)=M_{k}(s)U(s)^{-1}G_{1}(s)$ because of (11), hence
$\mathfrak{B}_{\textup{o}}\lparen{\Gamma}_{1}\rparen\subset\mathfrak{B}_{\textup{o}}\lparen{\Gamma}_{2}\rparen$
due to Theorem 3. ∎

Now we can turn to the proof of Theorem 4.

###### Proof:

Suppose that
$\mathfrak{B}_{\textup{i}}\lparen\text{A}_{2}\rparen\subset\mathfrak{B}_{\textup{i}}\lparen\text{A}_{1}\rparen$
and
$\mathfrak{B}_{\textup{o}}\lparen{\Gamma}_{1}\rparen\subset\mathfrak{B}_{\textup{o}}\lparen{\Gamma}_{2}\rparen$.
Let E be an environment compatible with $\mathcal{C}_{2}$. Then
$\mathfrak{B}_{\textup{i}}\lparen\text{E}\rparen\subset\mathfrak{B}_{\textup{i}}\lparen\text{A}_{2}\rparen\subset\mathfrak{B}_{\textup{i}}\lparen\text{A}_{1}\rparen$,
hence E is compatible with $\mathcal{C}_{2}$. On the other hand, let
${\Sigma}$ be an implementation of $\mathcal{C}_{1}$. Note that $\text{A}_{2}$
is an environment compatible with $\mathcal{C}_{1}$, hence
$\mathfrak{B}_{\textup{o}}\lparen\text{A}_{2}\wedge{\Sigma}\rparen\subset\mathfrak{B}_{\textup{o}}\lparen{\Gamma}_{1}\rparen\subset\mathfrak{B}_{\textup{o}}\lparen{\Gamma}_{2}\rparen$
and thus ${\Sigma}$ is an implementation of $\mathcal{C}_{2}$.

Conversely, suppose that $\mathcal{C}_{1}$ refines $\mathcal{C}_{2}$. Since
$\text{A}_{2}$ is an environment compatible with $\mathcal{C}_{2}$, it follows
that $\text{A}_{2}$ is compatible with $\mathcal{C}_{1}$ and
$\mathfrak{B}_{\textup{i}}\lparen\text{A}_{2}\rparen\subset\mathfrak{B}_{\textup{i}}\lparen\text{A}_{1}\rparen$.
Note that if ${\Sigma}$ is autonomous, then

$\mathfrak{B}_{\textup{o}}\lparen\text{A}_{1}\wedge{\Sigma}\rparen=\mathfrak{B}_{\textup{o}}\lparen\text{A}_{2}\wedge{\Sigma}\rparen=\mathfrak{B}_{\textup{o}}\lparen{\Sigma}\rparen.$

In view of Theorem 3, this means that an autonomous ${\Sigma}$ is an
implementation of $\mathcal{C}_{i}$, $i\in\\{1,2\\}$, if and only if
$\mathfrak{B}_{\textup{o}}\lparen{\Sigma}\rparen\subset\mathfrak{B}_{\textup{o}}\lparen{\Gamma}_{i}\rparen$.
Since all implementations of $\mathcal{C}_{1}$ are implementations of
$\mathcal{C}_{2}$, it follows that
$\mathfrak{B}_{\textup{o}}\lparen{\Sigma}\rparen\subset\mathfrak{B}_{\textup{o}}\lparen{\Gamma}_{1}\rparen$
implies
$\mathfrak{B}_{\textup{o}}\lparen{\Sigma}\rparen\subset\mathfrak{B}_{\textup{o}}\lparen{\Gamma}_{2}\rparen$
for all autonomous ${\Sigma}$ and thus
$\mathfrak{B}_{\textup{o}}\lparen{\Gamma}_{1}\rparen\subset\mathfrak{B}_{\textup{o}}\lparen{\Gamma}_{2}\rparen$
because of Lemma 3. ∎

## References

  * [1] J. C. Willems, “Dissipative dynamical systems part I: General theory,” Archive for Rational Mechanics and Analysis, vol. 45, no. 5, pp. 321–351, 1972\.
  * [2] F. Blanchini, “Set invariance in control,” Automatica, vol. 35, no. 11, pp. 1747–1767, 1999.
  * [3] B. Meyer, “Applying ‘design by contract’,” Computer, vol. 25, no. 10, pp. 40–51, 1992.
  * [4] C. Jones, “Specification and design of (parallel) programs.,” in Proceedings Of IFIP Congress ’, vol. 83, pp. 321–332, 1983.
  * [5] A. Chakrabarti, L. de Alfaro, T. A. Henzinger, and F. Y. C. Mang, “Synchronous and bidirectional component interfaces,” in Computer Aided Verification (E. Brinksma and K. G. Larsen, eds.), pp. 414–427, Springer Berlin Heidelberg, 2002.
  * [6] L. de Alfaro and T. A. Henzinger, “Interface-based design,” in Engineering Theories of Software Intensive Systems (M. Broy, J. Grünbauer, D. Harel, and T. Hoare, eds.), pp. 83–104, Springer Netherlands, 2005.
  * [7] A. Davare, D. Densmore, L. Guo, R. Passerone, A. L. Sangiovanni-Vincentelli, A. Simalatsar, and Q. Zhu, “metroII: A design environment for cyber-physical systems,” ACM Transactions on Embedded Computing Systems, vol. 12, no. 1s, 2013.
  * [8] A. Sangiovanni-Vincentelli, W. Damm, and R. Passerone, “Taming dr. Frankenstein: Contract-based design for cyber-physical systems,” European Journal of Control, vol. 18, no. 3, pp. 217–238, 2012.
  * [9] A. Benveniste, B. Caillaud, D. Nickovic, R. Passerone, J.-B. Raclet, P. Reinkemeier, A. Sangiovanni-Vincentelli, W. Damm, T. A. Henzinger, and K. G. Larsen, Contracts for System Design.  Foundations and Trends in Electronic Design Automation, Now Publishers, 2018.
  * [10] J. C. Willems, “Models for dynamics,” in Dynamics Reported: A Series in Dynamical Systems and Their Applications (U. Kirchgraber and H. O. Walther, eds.), pp. 171–269, Vieweg+Teubner Verlag, 1989.
  * [11] J. W. Polderman and J. C. Willems, Introduction to Mathematical Systems Theory.  Springer-Verlag New York, 1998.
  * [12] A. Saoud, A. Girard, and L. Fribourg, “On the composition of discrete and continuous-time assume-guarantee contracts for invariance,” in Proceedings of the European Control Conference, pp. 435–440, 2018.
  * [13] A. Saoud, A. Girard, and L. Fribourg, “Contract based design of symbolic controllers for interconnected multiperiodic sampled-data systems,” in Proceedings of the IEEE Conference on Decision and Control, pp. 773–779, 2018\.
  * [14] A. Eqtami and A. Girard, “A quantitative approach on assume-guarantee contracts for safety of interconnected systems,” in Proceedings of the European Control Conference, pp. 536–541, 2019.
  * [15] E. S. Kim, M. Arcak, and S. A. Seshia, “A small gain theorem for parametric assume-guarantee contracts,” in Proceedings of the 20th International Conference on Hybrid Systems: Computation and Control, HSCC ’17, pp. 207–216, 2017.
  * [16] M. Al Khatib and M. Zamani, “Controller synthesis for interconnected systems using parametric assume-guarantee contracts,” in Proceedings of the American Control Conference, pp. 5419–5424, 2020.
  * [17] B. Besselink, K. H. Johansson, and A. van der Schaft, “Contracts as specifications for dynamical systems in driving variable form,” in Proceedings of the European Control Conference, pp. 263–268, 2019.
  * [18] F. Kerber and A. van der Schaft, “Assume-guarantee reasoning for linear dynamical systems,” in Proceedings of the European Control Conference, pp. 5015–5020, 2009.
  * [19] F. Kerber and A. van der Schaft, “Compositional analysis for linear systems,” Systems & Control Letters, vol. 59, no. 10, pp. 645–653, 2010.
  * [20] F. Kerber and A. J. van der Schaft, “Decentralized control using compositional analysis techniques,” in Proceedings of the IEEE Conference on Decision and Control and European Control Conference, pp. 2699–2704, 2011.
  * [21] J. C. Willems, “The behavioral approach to open and interconnected systems,” IEEE Control Systems Magazine, vol. 27, no. 6, pp. 46–99, 2007\.
  * [22] J. C. Willems, “Input-output and state-space representations of finite-dimensional linear time-invariant systems,” Linear Algebra and its Applications, vol. 50, pp. 581–608, 1983.
  * [23] J. W. Polderman, “A new and simple proof of the equivalence theorem for behaviors,” Systems & Control Letters, vol. 41, no. 3, pp. 223–224, 2000\.
  * [24] T. Kaczorek, Polynomial and Rational Matrices.  Springer-Verlag London, 2007.


#  Pre-Trained Multilingual Sequence-to-Sequence Models:
A Hope for Low-Resource Language Translation?

En-Shiun Annie Lee,* Sarubi Thillainathan,$\dagger$ Shravan Nayak,$\ddagger$
Surangika Ranathunga,$\dagger$
David Ifeoluwa Adelani,$\mathsection\text{,}\mathparagraph$ Ruisi Su,$\|$ Arya
D. McCarthy#
*University of Toronto, $\dagger$University of Moratuwa, $\ddagger$IIT(BHU) Varanasi,
$\mathsection$Masakhane NLP, $\mathparagraph$Saarland University, $\|$Sway AI,
#Johns Hopkins University
<EMAIL_ADDRESS>

###### Abstract

What can pre-trained multilingual sequence-to-sequence models like mBART
contribute to translating low-resource languages? We conduct a thorough
empirical experiment in 10 languages to ascertain this, considering five
factors: (1) the amount of fine-tuning data, (2) the noise in the fine-tuning
data, (3) the amount of pre-training data in the model, (4) the impact of
domain mismatch, and (5) language typology. In addition to yielding several
heuristics, the experiments form a framework for evaluating the data
sensitivities of machine translation systems. While mBART is robust to domain
differences, its translations for unseen and typologically distant languages
remain below 3.0 BLEU. In answer to our title’s question, mBART is not a low-
resource panacea; we therefore encourage shifting the emphasis from new models
to new data111Code is available at https://github.com/LRLNMT/LRLNMT.

##  1 Introduction

Pre-trained multilingual sequence-to-sequence (PMSS) models, such as mBART
(Tang et al., 2021) and mT5 (Xue et al., 2021), are pre-trained on large
general data, then fine-tuned to deliver impressive results for natural
language inference, question answering, and text simplification (Hu et al.,
2020). Their performance on machine translation shows promise for translating
low-resource languages (Liu et al., 2021b; Adelani et al., 2021; Thillainathan
et al., 2021), which remains an open challenge (Lopez and Post, 2013; Koehn
and Knowles, 2017; Mager et al., 2021; Ranathunga et al., 2021).

When can mBART and mT5 succeed in translating a low-resource language? Despite
their promise, the specific conditions for their practical application are not
yet clear. Understanding their sensitivities is crucial to guide data
acquisition efforts and apply PMSS models to new languages.

We introduce a framework for assessing data-dependency of performance of
machine translation systems. We then apply it in a large-scale study of
mBART’s viability for low-resource machine translation on 10 typologically and
geographically varied languages. Eight languages are low-resource, and four
are unseen by mBART during pre-training. Through our results, we gauge the
importance of five dimensions of the training data:

  1. 1.

Amount of fine-tuning data

  2. 2.

Noise in fine-tuning data

  3. 3.

Amount of pre-training data

  4. 4.

Domain mismatch

  5. 5.

Language typology

The closest work to ours (Liu et al., 2021b) considers only the first two.

For the seen languages, mBART reaches acceptable performance with either 10k
high-quality, in-domain sentence pairs or 100k noisy ones. However, mBART’s
BLEU score for unseen languages is often below 3.0—far below usability. For
these unseen, low-resource languages, the fact that even mBART—which has
already seen billions of sentences—cannot succeed in virtually any of our
conditions speaks to the need for appropriate in-domain data. Therefore, the
analytical framework in our experimental design can help to target new data
acquisition efforts.

##  2 Models and Data

mBART and mT5 are PMSS models that rely on the encoder–decoder Transformer
architecture (Vaswani et al., 2017) trained on Common Crawl–derived data with
variants of a monolingual autoencoding objective: they must recreate the input
text that they are provided. Neither is trained with an explicit objective
encouraging similar tokens or sentences to have similar representations.

After model weights have been learned, the models can be fine-tuned on
parallel text for translation. The ideal fine-tuning scenario would be vast,
clean data matching the language and domain of interest. Because this scenario
is unlikely for low-resource languages, we test the relaxation of these
assumptions for PMSS models.

In a preliminary experiment comparing mBART and mT5, mBART performed better
than mT5 on 11 of the 18 translation directions, especially the en$\to$xx
directions (Table 1), corroborating Liu et al. (2021b). Because mBART
performed better both in number of translation directions and average BLEU, we
focus hereafter on it.

|  |  |  en→xx | xx→en
---|---|---|---|---
Language | Training data | Size | mBART | mT5 | mBART | mT5
af | JW300 | 1,104k | 30.9 | 32.9 | 43.9 | 46.9
xh | JW300 | 866k | 9.1 | 8.4 | 22.8 | 23.2
yo | JW300 | 472k | 3.9 | 2.6 | 7.9 | 8.1
ga | EUBookShop | 133k | 15.1 | 7.6 | 15.7 | 16.7
fr | DGT-TM | 100k | 18.8 | 19.8 | 19.3 | 20.3
si | Gov’t | 56k | 5.4 | 2.3 | 9.6 | 8.4
ta | Gov’t | 56k | 3.5 | 2.4 | 10.7 | 10.1
hi | PMIndia | 50k | 14.1 | 10.5 | 19.5 | 16.4
kn | PMIndia | 25k | 4.1 | 2.9 | 4.2 | 10.7
Average |  |  | 11.7 | 9.9 | 17.1 | 17.9
Table 1: Preliminary results for mBART and mT5 (base version) in six
languages. We test on Flores in all cases. The best score for each direction
is in bold.

###  2.1 Languages

To assess mBART’s translation ability, we selected a set of high- and low-
resource languages with high typological and geographical diversity (Table 2).
Five of the ten languages do not use the Latin script, so that we can evaluate
mBART’s generalization to non-Latin scripts (see Pires et al., 2019). Eight
are considered low-resource languages by Joshi et al. (2020), while two high-
resource languages (fr and hi) give a skyline of performance.222Joshi et al.
(2020)’s taxonomy is out-of-date. Because si is used to train mBART, it must
be at least class 3. We believe that, according to Joshi et al. (2020)’s
definition, no language in our study is below class 2. Four are unseen during
mBART’s pre-training. Together, these languages let us probe the effects of
pre-training data size and language typology on translation.

Joshi mBART Language Family Script class tokens fr French Romance (IE) Latin 5
9780M hi Hindi Indo-Aryan (IE) Devanagari 4 1715M ta Tamil Dravidian Tamil 3
595M si Sinhala Indo-Aryan (IE) Sinhala 1 243M af Afrikaans Germanic (IE)
Latin 3 242M xh Xhosa Niger–Congo Latin 2 13M ga Irish Celtic (IE) Latin 2 –
yo Yorùbá Niger–Congo Latin 2 – as Assamese Indo-Aryan (IE) Bengali–Assamese 1
– kn Kannada Dravidian Kannada 1 –

Table 2: The 10 languages in our study.

###  2.2 Corpora

Selecting suitable parallel corpora enables us to probe the remaining three
factors: amount of fine-tuning data, noise in the fine-tuning data, and domain
mismatch.

For each of our 10 languages, we use three training corpora: data from Common
Crawl, the Bible, and one other domain-specific dataset (Table 3; complete
details in Appendix A). Common Crawl is large and open-domain, while the
others are smaller curated translations. We use Flores (which is also open-
domain) and the two domain-specific corpora for testing. Comparing on these
lets us assess the impact of domain mismatch.

To evaluate consistently across differently sized corpora, we sampled fixed-
size training sets from each corpus. For the Common Crawl data, we used two
sizes: 25k and 100k sentence pairs. For the Bible, we used a 1k-sentence-pair
sample. Finally, for each language’s other domain-specific dataset, depending
on the amount of parallel text available, we used up to four sizes (1k, 10k,
50k, 100k).

The Common Crawl datasets are large open-domain parallel corpora, but their
construction by automatic alignment invites substantial noise. This problem is
especially severe for low-resource languages (Kreutzer et al., 2022). Noisy
data often harm translation models (Khayrallah and Koehn, 2018), but it is
possible to use them effectively (McCarthy et al., 2020a). This raises the
question of whether mBART can do so. Among our experiments, we can see whether
and when a smaller, clean parallel corpus would be preferable.

Dataset Domain Languages Flores-101 Open all except si Floresv1 Open si
CCAligned Open all except ga CCMatrix Open ga JHU Bibles Religious all JW300
Religious+magazines af, yo, xh Government Administrative si, ta PMIndia News
as, kn, hi DGT-TM Legal fr, ga

Table 3: Parallel corpora used in our study.

|  |  en→xx | xx→en
---|---|---|---
|  | af | xh | yo | af | xh | yo
Training | Size | Flores | Bible | JW300 | Flores | Bible | JW300 | Flores | Bible | JW300 | Flores | Bible | JW300 | Flores | Bible | JW300 | Flores | Bible | JW300
Transformer |  |  |  |  |  |  |  |  |  |  |  |  |  |  |  |  |  |  |
Bible | 1k | 0.1 | 1.3 |  0.7 | 0.0 | 0.0 |  0.0 | 0.0 | 1.4 |  0.0 | 0.1 | 1.7 |  0.8 | 0.0 | 0.9 |  0.2 | 0.0 | 2.4 | 0.0
JW300 | 100k | 19.2 | 13.8 |  44.2 | 1.8 | 0.7 |  31.8 | 1.2 | 0.6 |  18.7 | 22.5 | 15.1 |  42.4 | 6.6 | 4.9 |  37.5 | 2.4 | 1.0 | 17.7
Common Crawl | 100k | 23.6 | 7.0 |  17.4 | 2.5 | 0.6 | 2.3 | 1.2 | 1.6 | 1.4 | 28.3 | 10.3 |  22.3 | 7.7 | 2.9 |  10.2 | 2.1 | 3.3 | 4.1
mBART50 |  |  |  |  |  |  |  |  |  |  |  |  |  |  |  |  |  |  |
Bible | 1k | 0.1 | 0.1 |  0.1 | 0.6 | 0.2 | 3.5 | 0.6 | 3.6 | 3.6 | 20.5 | 13.4 |  23.5 | 2.8 | 3.3 | 3.1 | 0.2 | 0.4 | 0.2
JW300 | 1k | 18.9 | 11.1 |  32.4 | 1.6 | 0.1 |  11.0 | 1.0 | 0.0 | 6.7 | 28.8 | 12.6 |  32.5 | 0.1 | 0.1 |  0.1 | 0.0 | 0.0 | 0.0
| 10k | 26.5 | 14.1 |  42.7 | 4.1 | 1.8 |  22.1 | 2.0 | 0.2 | 7.8 | 32.4 | 16.0 |  39.0 | 11.4 | 4.8 |  29.1 | 6.2 | 1.0 | 15.4
| 50k | 30.1 | 15.8 |  48.0 | 6.0 | 4.0 |  30.8 | 3.8 | 0.7 |  20.1 | 40.9 | 17.5 |  41.7 | 16.2 | 9.2 |  41.3 | 7.8 | 1.3 | 19.8
| 100k | 30.1 | 16.2 |  49.7 | 7.4 | 4.3 |  34.9 | 3.9 | 0.9 |  23.6 | 42.0 | 17.9 |  43.7 | 19.9 | 11.5 |  45.7 | 7.9 | 1.5 | 22.0
Common Crawl | 25k | 28.0 | 13.4 |  31.4 | 4.8 | 0.5 |  10.1 | 2.6 | 1.7 | 3.8 | 36.0 | 15.0 |  35.0 | 11.3 | 3.0 |  18.6 | 3.5 | 3.2 | 5.2
| 100k | 33.9 | 15.5 |  34.4 | 7.9 | 2.1 |  16.8 | 2.8 | 4.5 | 5.9 | 44.8 | 16.9 |  40.2 | 19.7 | 9.0 |  27.8 | 5.0 | 7.5 | 6.7
|  |  en→xx | xx→en
|  | hi | kn | as | hi | kn | as
Training | Size | Flores | Bible | PMI | Flores | Bible | PMI | Flores | Bible | PMI | Flores | Bible | PMI | Flores | Bible | PMI | Flores | Bible | PMI
Transformer |  |  |  |  |  |  |  |  |  |  |  |  |  |  |  |  |  |  |
Bible | 1k | 0.0 | 0.2 |  0.0 | 0.0 | 0.0 |  0.0 | 0.0 | 0.0 |  0.0 | 0.0 | 0.0 |  0.0 | 0.0 | 0.9 |  0.0 | 0.0 | 0.3 | 0.0
PMI | 50k | 7.7 | 1.3 |  22.9 | 0.0 | 0.0 | 4.9 | 0.0 | 0.0 | 1.3 | 7.7 | 2.4 |  26.2 | 6.6 | 0.6 | 9.7 | 0.0 | 0.0 | 3.4
Common Crawl | 100k | 8.7 | 2.3 | 7.3 | 0.2 | 0.0 |  0.0 | 0.0 | 0.0 |  0.0 | 6.6 | 3.0 | 4.7 | 0.1 | 0.0 |  0.1 | 0.0 | 0.1 | 0.1
mBART50 |  |  |  |  |  |  |  |  |  |  |  |  |  |  |  |  |  |  |
Bible | 1k | 3.7 | 7.0 | 4.3 | 0.0 | 0.1 |  0.0 | 0.1 | 0.9 | - | 7.1 | 9.3 | 7.2 | 0.1 | 0.3 |  0.0 | 1.4 | 4.6 | -
PMI | 1k | 7.0 | 2.3 |  14.5 | 0.0 | 0.0 |  0.1 | 0.0 | 0.0 | 2.1 | 7.4 | 4.1 |  11.8 | 0.3 | 0.1 | 1.7 | 0.0 | 0.0 | 0.2
| 10k | 11.5 | 2.5 |  24.2 | 1.8 | 0.1 |  10.7 | - | - | - | 16.8 | 7.1 |  30.6 | 0.9 | 0.2 | 5.2 | - | - | -
| 50k | 14.1 | 3.4 |  28.8 | - | - | - | - | - | - | 19.5 | 8.2 |  37.6 | - | - | - | - | - | -
Common Crawl | 25k | 14.2 | 5.5 |  12.0 | 0.4 | 0.0 |  0.1 | 1.4 | 0.3 | 1.4 | 17.6 | 10.2 |  14.0 | 0.2 | 0.0 |  0.1 | 1.6 | 0.8 | 1.6
| 100k | 20.9 | 6.2 |  17.0 | 1.2 | 0.0 |  0.7 | - | - | - | 22.4 | 11.2 |  17.1 | 0.4 | 0.0 |  0.5 | - | - | -
|  |  en→xx | xx→en
|  | si | ta | ga | si | ta | ga
Training | Size | Flores | Bible | Gov’t | Flores | Bible | Gov’t | Flores | Bible | DGT | Flores | Bible | Gov’t | Flores | Bible | Gov’t | Flores | Bible | DGT
Transformer |  |  |  |  |  |  |  |  |  |  |  |  |  |  |  |  |  |  |
Bible | 1k | 0.0 | 0.0 |  0.0 | 0.0 | 0.0 |  0.0 | 0.0 | 0.1 |  0.0 | 0.0 | 1.1 |  0.1 | 0.0 | 0.7 |  0.0 | 0.0 | 1.0 | 0.0
Gov’t/DGT | 50k/100k | 1.3 | 0.0 |  20.6 | 0.5 | 0.0 |  13.7 | 3.3 | 0.0 | 3.2 | 2.7 | 0.4 |  23.9 | 2.7 | 0.7 |  23.9 | 3.2 | 0.0 | 3.0
Common Crawl | 100k | 2.1 | 0.0 | 5.6 | 1.8 | 0.0 | 1.8 | 0.0 | 0.0 |  0.0 | 4.7 | 1.9 | 7.9 | 5.2 | 3.4 | 4.9 | 0.1 | 0.0 | 0.0
mBART50 |  |  |  |  |  |  |  |  |  |  |  |  |  |  |  |  |  |  |
Bible | 1k | 0.2 | 3.6 | 1.2 | 0.7 | 1.1 | 1.1 | 0.9 | 1.3 |  0.1 | 4.8 | 9.0 | 4.5 | 5.3 | 7.8 | 4.4 | 0.0 | 0.0 | 0.0
Gov’t/DGT | 1k | 1.4 | 0.1 |  11.2 | 1.1 | 0.1 | 6.6 | 0.8 | 0.0 | 1.5 | 6.5 | 2.5 |  14.8 | 6.1 | 2.1 |  12.6 | 0.3 | 0.1 | 0.8
| 10k | 4.2 | 0.2 |  26.4 | 2.3 | 0.2 |  17.4 | 4.7 | 0.1 | 4.1 | 8.4 | 3.3 |  30.7 | 7.7 | 2.6 |  23.8 | 5.8 | 0.2 | 4.7
| 50k | 5.1 | 0.2 |  35.4 | 3.7 | 0.2 |  23.4 | 12.2 | 0.3 | 4.2 | 9.2 | 3.5 |  38.8 | 10.4 | 3.3 |  37.3 | 12.3 | 0.4 | 5.1
| 100k | - | - | - | - | - | - | 8.9 | 0.2 | 4.3 | - | - | - | - | - | - | 9.5 | 0.2 | 4.9
Common Crawl | 25k | 4.4 | 0.5 | 9.6 | 4.7 | 0.9 | 4.6 | 0.0 | 0.0 |  0.0 | 9.6 | 5.2 |  13.5 | 7.2 | 6.5 | 5.6 | 0.1 | 0.1 | 0.0
| 100k | 6.6 | 0.5 |  16.9 | 7.6 | 0.8 | 8.6 | 0.0 | 0.0 |  0.0 | 13.8 | 8.5 |  20.5 | 17.3 | 9.6 |  16.8 | 0.0 | 0.0 | 0.0

Table 4: Experimental results, reported in SacreBLEU Post (2018). Values <1.0
grey; values >10.0 bold.

##  3 Experimental Setting

We fine-tune mBART models on each of the training corpora and sizes listed
above, and we evaluate their performance using the development and test sets
from the domain-specific corpora and Flores.

We additionally train a standard Transformer baseline (Vaswani et al., 2017)
to compare pre-training versus training from scratch.

We score translations with SacreBLEU (Post, 2018). Details of training and
evaluation are given in Appendix B.

##  4 Results and Analysis

en→fr fr→en Training Size Flores Bible DGT Flores Bible DGT Transformer Bible
1k 0.0 2.4 0.0 0.0 1.6 0.0 DGT 100k 5.7 1.4 22.8 6.1 2.4 26.6 Common Crawl
100k 9.0 6.5 5.6 10.7 6.8 7.3 mBART50 Bible 1k 13.2 15.5 10.9 0.0 0.0 0.0 DGT
1k 15.1 5.7 20.2 19.9 11.9 27.8 10k 15.5 4.4 25.4 17.7 7.8 29.7 50k 17.8 5.1
31.2 18.3 8.5 35.3 100k 18.8 5.0 34.6 19.3 7.6 36.6 Common Crawl 25k 24.0 14.9
15.6 26.0 18.0 19.4 100k 29.4 16.3 19.6 29.1 18.9 22.6

Table 5: Experimental results for French, reported in SacreBLEU. Values <1.0
grey; values >10.0 bold.

The results of our empirical study are given in Table 4, with fr given in
Table 5. By contrasting specific groups of rows, we probe our five factors.

###  4.1 Amount of fine-tuning data

To assess this dimension, we compare the Transformer and mBART models trained
on varying sizes of the same corpus with their corresponding open-domain and
domain-specific evaluation sets.

In the open-domain case (training on Common Crawl), for languages seen during
pre-training, mBART fine-tuned with 25k sentence pairs outperforms the
Transformer trained with 100k parallel sentences; this pattern holds for 18 of
the 20 language directions. This indicates that pre-trained mBART is at least
four times as data-efficient. Although it also outperforms the Transformer on
unseen languages in terms of BLEU, the scores are often below 3.0—a far cry
from even the BLEU score needed for gisting.

Figure 1: Impact of fine-tuning dataset size on mBART performance translating
into English on JW300.

On the other hand, we observe a similar trend when training with domain-
specific datasets (JW300, Gov’t, and DGT). For the government-domain dataset,
mBART trained with 10k sentences of si or ta achieves a higher BLEU than the
Transformer trained with 50k sentences (+3.4 to +6.8); this suggests at least
a fivefold data efficiency. The exception is si$\to$en, where the difference
in scores is 0.1 BLEU. For JW300, mBART trained with 10k parallel sentences
outperforms the Transformer trained with 100k for some translation tasks
tenfold. Further, mBART trained with 50k sentences outperforms the Transformer
model for all languages by a large margin333The only exceptions are af-en and
en-xh in-domain testing, with less than or equal to 1.0 BLEU point
difference.. Of note, yo begins to perform well in-domain on JW300 with tens
of thousands of sentences.

When do we reach diminishing returns on fine-tuning size? Figure 1 shows how
fine-tuning size affects translation of JW300 into en from af, xh, and yo.
Although training with more data improves BLEU, the gain saturates as the
dataset size reaches approximately 50k sentence pairs. Liu et al. attribute
this to the limit of the model’s capacity: that the pre-trained weights are
“washed out” (2020) when fine-tuning with more parallel data.

###  4.2 Noise in fine-tuning data

At what point is a small-but-clean corpus more useful than an automatically
mined one like from Common Crawl? Comparing mBART trained on Common Crawl
versus domain-specific data, we see that for several languages both in and not
in mBART, 10k high-quality in-domain sentences leads to better performance
than 100k sentences from Common Crawl.

###  4.3 Amount of pre-training data

Figure 2: Effect of pre-training open-domain dataset size, using 100k Common
Crawl sentence pairs for fine-tuning, translating from English

The improvement of mBART over the Transformer is more prominent for languages
with more pre-training data. The correlation between BLEU and number of pre-
training sentences is $R^{2}=0.31$ for open-domain (Figure 2), and the effect
in the domain-specific case is similar. This shows that mBART effectively
leverages the pre-training data. Taken with the results of § 4.1, the
contrasting behavior between seen and unseen languages belies a “rich-get-
richer” phenomenon.

###  4.4 Domain mismatch

This section compares the performance of models when trained and tested on
matching versus mismatched domains.

Unsurprisingly, taking a training set from the same domain as the test set
consistently yields higher BLEU than a mismatched training set. This pattern
repeats across domains and directions.

Of greater interest is that Common Crawl–trained models often do better on
domain-specific test sets than open-domain test sets. For languages with JW300
or Gov’t, testing BLEU on these was higher than on the open-domain Flores
data.

Further, for si and ta, mBART trained on 10k sentences achieved higher BLEU
than the Transformer trained on 100k data, suggesting the pre-training gain
was able to compensate the lack of in-domain data. This may indicate that
mBART is valuable for domain-specific translation with low amounts of high-
quality data.

Results for fr on DGT and the Bible and hi on PMI show that mBART can excel
with even 1k parallel sentences for languages with sufficient pre-training. If
data from a different domain is available in sufficient quantities, an
acceptable translation can be expected, as evident from the Gov’t 50k and
JW300 100k settings. Noticeably, issues related to domain difference and fine-
tuning dataset size are less pronounced for fr (see results for 1k Bible data
and 1k DGT). This reiterates the impact of language coverage in the mBART
model.

###  4.5 Language typology

Figure 3: Cosine similarities of syntactic features

This analysis relates properties of the languages to their performance.

Foremost, af regularly achieves the highest BLEU among low-resource languages
used to pre-train mBART. This observation is consistent with Zhou and Waibel
(2021). We attribute this to af’s relationship with en: both are Germanic and
share the Latin script, with large lexical overlap. Multilingual machine
translation systems can learn shared representations for linguistically
similar languages (Dabre et al., 2017; Neubig and Hu, 2018; Kudugunta et al.,
2019; Hokamp et al., 2019); we expect that mBART taps into this relationship.
Further, a smaller token set may help explain this improved generalization
(Arivazhagan et al., 2019).

For unseen languages that share the Latin script with English, explaining
mBART’s performance is less trivial, so we turn to a computational analysis.
ga reaches lower BLEU than yo, despite being Indo-European like most of
mBART’s training data. It could be a result of its rare VSO word order (Liu et
al., 2021a), its initial consonant mutations, or other rare syntactic
phenomena. To explain the divergent behavior of af and ga, we use syntactic
features estimated by the $k$ nearest neighbors (Littell et al., 2017) of
their WALS features (Dryer and Haspelmath, 2013). Figure 3 shows the syntactic
similarities between af, ga, and four high-resource languages (en, de, fr, and
nl). This confirms that af is more syntactically similar to these high-
resource languages than ga is.

Finally, we consider the interplay of translation direction and BLEU.
Translating into en regularly outperforms translating from en, which we may
attribute to mBART and the Transformer learning a strong en language model in
the decoder (Voita et al., 2021). But it may also come from BLEU’s ignorance
of subword phenomena. When translating into a morphologically rich language
like si or ta, no partial credit is awarded for partially correct sets of
morphemes. We see this as bolstering the movement toward character-aware
metrics (Popović, 2015; Mager et al., 2021).

##  5 Conclusion

We have assessed the value of PMSS models like mBART for low-resource machine
translation. We designed a reusable framework of experiments, capturing
mBART’s sensitivity to five facets of data. Consistently, mBART fails in
learning to translate new under-resourced languages—those unseen in the pre-
trained model. For languages used in monolingual pre-training, we find four-
to tenfold data efficiency over a from-scratch Transformer, plus robustness to
domain differences.

For domain-specific datasets, mBART might outperform standard Transformers by
an efficiency of five to ten times; future work can pinpoint the saturation
size. Fine-tuned mBART is robust to domain differences, while the Transformer
flounders for out-domain datasets. However, the performance on unseen
languages is generally not indicative of usable translation system.

Taken in tandem, these results point to the paramountcy of monolingual pre-
training for the bilingual task of translation. The biggest open issue,
though, is not how to tune PMSS models on limited data; instead, greater data
acquisition is the hope for truly low-resource machine translation.

## Acknowledgments

This project has been supported by the ICLR CoSubmitting Summer (CSS) program
2022 initiated by ICLR DEI co-chairs Rosanne Liu and Krystal Maughan. David
Adelani acknowledges the support of the EU funded Horizon 2020 project ROXANNE
under grant agreement No. 833635. Lastly, we thank the Spoken Language Systems
Chair, Dietrich Klakow at Saarland University for providing GPU resources to
train the models.

## References

  * Abbott and Martinus (2019) Jade Abbott and Laura Martinus. 2019.  Benchmarking neural machine translation for Southern African languages.  In _Proceedings of the 2019 Workshop on Widening NLP_ , pages 98–101, Florence, Italy. Association for Computational Linguistics.
  * Adelani et al. (2021) David Adelani, Dana Ruiter, Jesujoba Alabi, Damilola Adebonojo, Adesina Ayeni, Mofe Adeyemi, Ayodele Esther Awokoya, and Cristina España-Bonet. 2021.  The effect of domain and diacritics in Yoruba–English neural machine translation.  In _Proceedings of Machine Translation Summit XVIII: Research Track_ , pages 61–75, Virtual. Association for Machine Translation in the Americas.
  * Agić and Vulić (2019) Željko Agić and Ivan Vulić. 2019.  JW300: A wide-coverage parallel corpus for low-resource languages.  In _Proceedings of the 57th Annual Meeting of the Association for Computational Linguistics_ , pages 3204–3210, Florence, Italy. Association for Computational Linguistics.
  * Alabi et al. (2020) Jesujoba Alabi, Kwabena Amponsah-Kaakyire, David Adelani, and Cristina España-Bonet. 2020.  Massive vs. curated embeddings for low-resourced languages: the case of Yorùbá and Twi.  In _Proceedings of the 12th Language Resources and Evaluation Conference_ , pages 2754–2762, Marseille, France. European Language Resources Association.
  * Arivazhagan et al. (2019) Naveen Arivazhagan, Ankur Bapna, Orhan Firat, Dmitry Lepikhin, Melvin Johnson, Maxim Krikun, Mia Xu Chen, Yuan Cao, George Foster, Colin Cherry, et al. 2019\.  Massively multilingual neural machine translation in the wild: Findings and challenges.  _arXiv preprint arXiv:1907.05019_.
  * Cahyawijaya et al. (2021) Samuel Cahyawijaya, Genta Indra Winata, Bryan Wilie, Karissa Vincentio, Xiaohong Li, Adhiguna Kuncoro, Sebastian Ruder, Zhi Yuan Lim, Syafri Bahar, Masayu Leylia Khodra, et al. 2021.  Indonlg: Benchmark and resources for evaluating indonesian natural language generation.  _arXiv preprint arXiv:2104.08200_.
  * Dabre et al. (2017) Raj Dabre, Tetsuji Nakagawa, and Hideto Kazawa. 2017.  An empirical study of language relatedness for transfer learning in neural machine translation.  In _Proceedings of the 31st Pacific Asia Conference on Language, Information and Computation_ , pages 282–286. The National University (Phillippines).
  * Dryer and Haspelmath (2013) Matthew S. Dryer and Martin Haspelmath, editors. 2013.  _WALS Online_.  Max Planck Institute for Evolutionary Anthropology, Leipzig.
  * Ebrahimi and Kann (2021) Abteen Ebrahimi and Katharina Kann. 2021.  How to adapt your pretrained multilingual model to 1600 languages.  In _Proceedings of the 59th Annual Meeting of the Association for Computational Linguistics and the 11th International Joint Conference on Natural Language Processing (Volume 1: Long Papers)_ , pages 4555–4567, Online. Association for Computational Linguistics.
  * El-Kishky et al. (2020) Ahmed El-Kishky, Vishrav Chaudhary, Francisco Guzmán, and Philipp Koehn. 2020\.  CCAligned: A massive collection of cross-lingual web-document pairs.  In _Proceedings of the 2020 Conference on Empirical Methods in Natural Language Processing (EMNLP)_ , pages 5960–5969, Online. Association for Computational Linguistics.
  * Fan et al. (2021) Angela Fan, Shruti Bhosale, Holger Schwenk, Zhiyi Ma, Ahmed El-Kishky, Siddharth Goyal, Mandeep Baines, Onur Celebi, Guillaume Wenzek, Vishrav Chaudhary, Naman Goyal, Tom Birch, Vitaliy Liptchinsky, Sergey Edunov, Michael Auli, and Armand Joulin. 2021.  Beyond English-centric multilingual machine translation.  _Journal of Machine Learning Research_ , 22(107):1–48.
  * Fernando et al. (2020) Aloka Fernando, Surangika Ranathunga, and Gihan Dias. 2020.  Data augmentation and terminology integration for domain-specific Sinhala-English-Tamil statistical machine translation.  _arXiv preprint arXiv:2011.02821_.
  * Haddow and Kirefu (2020) Barry Haddow and Faheem Kirefu. 2020.  PMIndia - A collection of parallel corpora of languages of India.  _CoRR_ , abs/2001.09907.
  * Hokamp et al. (2019) Chris Hokamp, John Glover, and Demian Gholipour Ghalandari. 2019.  Evaluating the supervised and zero-shot performance of multi-lingual translation models.  In _Proceedings of the Fourth Conference on Machine Translation (Volume 2: Shared Task Papers, Day 1)_ , pages 209–217, Florence, Italy. Association for Computational Linguistics.
  * Hu et al. (2020) Junjie Hu, Sebastian Ruder, Aditya Siddhant, Graham Neubig, Orhan Firat, and Melvin Johnson. 2020.  XTREME: A massively multilingual multi-task benchmark for evaluating cross-lingual generalisation.  In _Proceedings of the 37th International Conference on Machine Learning_ , volume 119 of _Proceedings of Machine Learning Research_ , pages 4411–4421. PMLR.
  * Joshi et al. (2020) Pratik Joshi, Sebastin Santy, Amar Budhiraja, Kalika Bali, and Monojit Choudhury. 2020.  The state and fate of linguistic diversity and inclusion in the NLP world.  In _Proceedings of the 58th Annual Meeting of the Association for Computational Linguistics_ , pages 6282–6293, Online. Association for Computational Linguistics.
  * Kann et al. (2019) Katharina Kann, Kyunghyun Cho, and Samuel R. Bowman. 2019.  Towards realistic practices in low-resource natural language processing: The development set.  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 3342–3349, Hong Kong, China. Association for Computational Linguistics.
  * Khayrallah and Koehn (2018) Huda Khayrallah and Philipp Koehn. 2018.  On the impact of various types of noise on neural machine translation.  In _Proceedings of the 2nd Workshop on Neural Machine Translation and Generation_ , pages 74–83, Melbourne, Australia. Association for Computational Linguistics.
  * Koehn and Knowles (2017) Philipp Koehn and Rebecca Knowles. 2017.  Six challenges for neural machine translation.  In _Proceedings of the First Workshop on Neural Machine Translation_ , pages 28–39, Vancouver. Association for Computational Linguistics.
  * Kreutzer et al. (2022) Julia Kreutzer, Isaac Caswell, Lisa Wang, Ahsan Wahab, Daan van Esch, Nasanbayar Ulzii-Orshikh, Allahsera Tapo, Nishant Subramani, Artem Sokolov, Claytone Sikasote, Monang Setyawan, Supheakmungkol Sarin, Sokhar Samb, Benoît Sagot, Clara Rivera, Annette Rios, Isabel Papadimitriou, Salomey Osei, Pedro Ortiz Suarez, Iroro Orife, Kelechi Ogueji, Andre Niyongabo Rubungo, Toan Q. Nguyen, Mathias Müller, André Müller, Shamsuddeen Hassan Muhammad, Nanda Muhammad, Ayanda Mnyakeni, Jamshidbek Mirzakhalov, Tapiwanashe Matangira, Colin Leong, Nze Lawson, Sneha Kudugunta, Yacine Jernite, Mathias Jenny, Orhan Firat, Bonaventure F. P. Dossou, Sakhile Dlamini, Nisansa de Silva, Sakine Çabuk Ballı, Stella Biderman, Alessia Battisti, Ahmed Baruwa, Ankur Bapna, Pallavi Baljekar, Israel Abebe Azime, Ayodele Awokoya, Duygu Ataman, Orevaoghene Ahia, Oghenefego Ahia, Sweta Agrawal, and Mofetoluwa Adeyemi. 2022.  Quality at a Glance: An Audit of Web-Crawled Multilingual Datasets.  _Transactions of the Association for Computational Linguistics_ , 10:50–72.
  * Kudugunta et al. (2019) Sneha Kudugunta, Ankur Bapna, Isaac Caswell, and Orhan Firat. 2019.  Investigating multilingual NMT representations at scale.  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 1565–1575, Hong Kong, China. Association for Computational Linguistics.
  * Littell et al. (2017) Patrick Littell, David R. Mortensen, Ke Lin, Katherine Kairis, Carlisle Turner, and Lori Levin. 2017.  URIEL and lang2vec: Representing languages as typological, geographical, and phylogenetic vectors.  In _Proceedings of the 15th Conference of the European Chapter of the Association for Computational Linguistics: Volume 2, Short Papers_ , pages 8–14, Valencia, Spain. Association for Computational Linguistics.
  * Liu et al. (2020) Yinhan Liu, Jiatao Gu, Naman Goyal, Xian Li, Sergey Edunov, Marjan Ghazvininejad, Mike Lewis, and Luke Zettlemoyer. 2020.  Multilingual denoising pre-training for neural machine translation.  _Transactions of the Association for Computational Linguistics_ , 8:726–742.
  * Liu et al. (2021a) Zihan Liu, Genta I Winata, Samuel Cahyawijaya, Andrea Madotto, Zhaojiang Lin, and Pascale Fung. 2021a.  On the importance of word order information in cross-lingual sequence labeling.  _Proceedings of the AAAI Conference on Artificial Intelligence_ , 35(15):13461–13469.
  * Liu et al. (2021b) Zihan Liu, Genta Indra Winata, and Pascale Fung. 2021b.  Continual mixed-language pre-training for extremely low-resource neural machine translation.  In _Findings of the Association for Computational Linguistics: ACL-IJCNLP 2021_ , pages 2706–2718, Online. Association for Computational Linguistics.
  * Lopez and Post (2013) Adam Lopez and Matt Post. 2013.  Beyond bitext: Five open problems in machine translation.  In _Twenty Years of Bitext_.
  * Madaan et al. (2020) Lovish Madaan, Soumya Sharma, and Parag Singla. 2020.  Transfer learning for related languages: Submissions to the WMT20 similar language translation task.  In _Proceedings of the Fifth Conference on Machine Translation_ , pages 402–408, Online. Association for Computational Linguistics.
  * Mager et al. (2021) Manuel Mager, Arturo Oncevay, Abteen Ebrahimi, John Ortega, Annette Rios, Angela Fan, Ximena Gutierrez-Vasques, Luis Chiruzzo, Gustavo Giménez-Lugo, Ricardo Ramos, Ivan Vladimir Meza Ruiz, Rolando Coto-Solano, Alexis Palmer, Elisabeth Mager-Hois, Vishrav Chaudhary, Graham Neubig, Ngoc Thang Vu, and Katharina Kann. 2021.  Findings of the AmericasNLP 2021 shared task on open machine translation for indigenous languages of the Americas.  In _Proceedings of the First Workshop on Natural Language Processing for Indigenous Languages of the Americas_ , pages 202–217, Online. Association for Computational Linguistics.
  * McCarthy et al. (2020a) Arya D. McCarthy, Xian Li, Jiatao Gu, and Ning Dong. 2020a.  Addressing posterior collapse with mutual information for improved variational neural machine translation.  In _Proceedings of the 58th Annual Meeting of the Association for Computational Linguistics_ , pages 8512–8525, Online. Association for Computational Linguistics.
  * McCarthy et al. (2020b) Arya D. McCarthy, Rachel Wicks, Dylan Lewis, Aaron Mueller, Winston Wu, Oliver Adams, Garrett Nicolai, Matt Post, and David Yarowsky. 2020b.  The Johns Hopkins University Bible corpus: 1600+ tongues for typological exploration.  In _Proceedings of the 12th Language Resources and Evaluation Conference_ , pages 2884–2892, Marseille, France. European Language Resources Association.
  * Mueller et al. (2020) Aaron Mueller, Garrett Nicolai, Arya D. McCarthy, Dylan Lewis, Winston Wu, and David Yarowsky. 2020.  An analysis of massively multilingual neural machine translation for low-resource languages.  In _Proceedings of the 12th Language Resources and Evaluation Conference_ , pages 3710–3718, Marseille, France. European Language Resources Association.
  * Neubig and Hu (2018) Graham Neubig and Junjie Hu. 2018.  Rapid adaptation of neural machine translation to new languages.  In _Proceedings of the 2018 Conference on Empirical Methods in Natural Language Processing_ , pages 875–880, Brussels, Belgium. Association for Computational Linguistics.
  * Nicolai et al. (2020) Garrett Nicolai, Dylan Lewis, Arya D. McCarthy, Aaron Mueller, Winston Wu, and David Yarowsky. 2020.  Fine-grained morphosyntactic analysis and generation tools for more than one thousand languages.  In _Proceedings of the 12th Language Resources and Evaluation Conference_ , pages 3963–3972, Marseille, France. European Language Resources Association.
  * Pires et al. (2019) Telmo Pires, Eva Schlinger, and Dan Garrette. 2019.  How multilingual is multilingual BERT? In _Proceedings of the 57th Annual Meeting of the Association for Computational Linguistics_ , pages 4996–5001, Florence, Italy. Association for Computational Linguistics.
  * Popović (2015) Maja Popović. 2015.  chrF: character n-gram F-score for automatic MT evaluation.  In _Proceedings of the Tenth Workshop on Statistical Machine Translation_ , pages 392–395, Lisbon, Portugal. Association for Computational Linguistics.
  * Post (2018) Matt Post. 2018.  A call for clarity in reporting BLEU scores.  In _Proceedings of the Third Conference on Machine Translation: Research Papers_ , pages 186–191, Brussels, Belgium. Association for Computational Linguistics.
  * Ranathunga et al. (2021) Surangika Ranathunga, En-Shiun Annie Lee, Marjana Prifti Skenduli, Ravi Shekhar, Mehreen Alam, and Rishemjit Kaur. 2021.  Neural machine translation for low-resource languages: A survey.  _arXiv preprint arXiv:2106.15115_.
  * Schwenk (2018) Holger Schwenk. 2018.  Filtering and mining parallel data in a joint multilingual space.  In _Proceedings of the 56th Annual Meeting of the Association for Computational Linguistics (Volume 2: Short Papers)_ , pages 228–234, Melbourne, Australia. Association for Computational Linguistics.
  * Schwenk et al. (2021) Holger Schwenk, Guillaume Wenzek, Sergey Edunov, Edouard Grave, Armand Joulin, and Angela Fan. 2021.  CCMatrix: Mining billions of high-quality parallel sentences on the web.  In _Proceedings of the 59th Annual Meeting of the Association for Computational Linguistics and the 11th International Joint Conference on Natural Language Processing (Volume 1: Long Papers)_ , pages 6490–6500, Online. Association for Computational Linguistics.
  * Tang et al. (2021) Yuqing Tang, Chau Tran, Xian Li, Peng-Jen Chen, Naman Goyal, Vishrav Chaudhary, Jiatao Gu, and Angela Fan. 2021.  Multilingual translation from denoising pre-training.  In _Findings of the Association for Computational Linguistics: ACL-IJCNLP 2021_ , pages 3450–3466, Online. Association for Computational Linguistics.
  * Thillainathan et al. (2021) Sarubi Thillainathan, Surangika Ranathunga, and Sanath Jayasena. 2021.  Fine-tuning self-supervised multilingual sequence-to-sequence models for extremely low-resource NMT.  In _2021 Moratuwa Engineering Research Conference (MERCon)_ , pages 432–437.
  * Tiedemann (2012) Jörg Tiedemann. 2012.  Parallel data, tools and interfaces in OPUS.  In _Proceedings of the Eighth International Conference on Language Resources and Evaluation (LREC’12)_ , pages 2214–2218, Istanbul, Turkey. European Language Resources Association (ELRA).
  * Vaswani et al. (2017) Ashish Vaswani, Noam Shazeer, Niki Parmar, Jakob Uszkoreit, Llion Jones, Aidan N. Gomez, Lukasz Kaiser, and Illia Polosukhin. 2017.  Attention is all you need.  In _Advances in Neural Information Processing Systems 30: Annual Conference on Neural Information Processing Systems 2017, December 4-9, 2017, Long Beach, CA, USA_ , pages 5998–6008.
  * Voita et al. (2021) Elena Voita, Rico Sennrich, and Ivan Titov. 2021.  Analyzing the source and target contributions to predictions in neural machine translation.  In _Proceedings of the 59th Annual Meeting of the Association for Computational Linguistics and the 11th International Joint Conference on Natural Language Processing (Volume 1: Long Papers)_ , pages 1126–1140, Online. Association for Computational Linguistics.
  * Xue et al. (2021) Linting Xue, Noah Constant, Adam Roberts, Mihir Kale, Rami Al-Rfou, Aditya Siddhant, Aditya Barua, and Colin Raffel. 2021.  mT5: A massively multilingual pre-trained text-to-text Transformer.  In _Proceedings of the 2021 Conference of the North American Chapter of the Association for Computational Linguistics: Human Language Technologies_ , pages 483–498, Online. Association for Computational Linguistics.
  * Zhou and Waibel (2021) Zhong Zhou and Alexander Waibel. 2021.  Family of origin and family of choice: Massively parallel lexiconized iterative pretraining for severely low resource text-based translation.  In _Proceedings of the Third Workshop on Computational Typology and Multilingual NLP_ , pages 67–80, Online. Association for Computational Linguistics.

##  Appendix A Supplementary Material on Corpora

Here we give details of the corpora used in our study.

#### Bible.

The JHU Bible Corpus (McCarthy et al., 2020b) is a recently released corpus of
Bible translations in over 1600 languages. In several low-resource languages,
the Bible is the only available text parallel with another language; moreover,
its verse structure makes it multi-parallel across thousands of languages. It
has been used to assess multilingual translation at massive linguistic scale
(Mueller et al., 2020), develop new morphological tools (Nicolai et al.,
2020), and fine-tune pre-trained language models to new low-resource languages
(Ebrahimi and Kann, 2021).

#### Gov’t.

The government document corpus of Fernando et al. (2020) is a multilingual
corpus for Sinhala, Tamil, and English. It contains official Sri Lankan
government documents: annual reports, crawled content from government
institutional websites, committee reports, procurement documents, and acts.

#### PMI.

PMIndia (Haddow and Kirefu, 2020) is a parallel corpus of news updates for
English and 13 other languages in India, extracted from the Prime Minister of
India’s website.

#### JW300.

The JW300 corpus (Agić and Vulić, 2019) is another parallel corpus, spanning
343 languages. It is obtained from jw.org and includes Jehovah’s Witness
magazines like Awake and Watchtower. The domain is highly religious, but it
includes other societal topics such as reports about persecution of their
disciples around the world. While JW300 was automatically aligned, Abbott and
Martinus (2019) and Alabi et al. (2020) have verified its quality for African
languages. For languages with non-Latin scripts in our study, the alignment
has been judged to be poor by native speakers.

#### DGT.

The European Commission’s Directorate-General for Translation–Translation
Memory (Tiedemann, 2012) covers 25 languages and corresponds to the ‘Summaries
of EU legislation’. They are short explanations of the main acts passed by the
European Union. The legislation included in the dataset includes directives,
regulations, decisions, and international agreements.

#### Common Crawl.

CCAligned (El-Kishky et al., 2020) and CCMatrix (Schwenk et al., 2021) are
web-scraped corpora that were automatically aligned using LASER sentence
embeddings (Schwenk, 2018). CCAligned is newer, and it has more text in low-
resource languages. The dataset, albeit noisy (Kreutzer et al., 2022), has
been used to develop highly multilingual machine translation models like
M2M100 Fan et al. (2021) and mBART multilingual MT Tang et al. (2021); a
modified version is used to train mT5 (Xue et al., 2021).

#### Data splits

For Flores and the Bible, we always use 1000 sentence pairs for development
(see Kann et al., 2019) and 1000 sentence pairs for test. For the second in-
domain dataset, the size varies between 1000 and 2000 sentence pairs based on
availability.

##  Appendix B Supplementary Material on Experimental Setup

#### mBART and mT5.

We compared mBART50 and mT5-base because they have comparable numbers of
parameters. For both the mBART50 and mT5-base models (Tang et al., 2021), we
train up to 3 epochs with a learning rate of $5\times 10^{-5}$, dropout of
0.1, maximum lengths of 200 for the source and target, and a batch size of 10.
We decode using beam searh with a beam size of 5. We use the implementations
in the HuggingFace Transformers library, and we leverage hardware-level
parallelism by training on Nvidia Tesla V100 GPUs.

We perform bilingual fine-tuning on the 10 selected language pairs. For each
language direction, we initialize the encoder–decoder model’s parameters from
the pre-trained mBART model’s corresponding encoder and decoder. After
initialization, we continue training.

Because mBART requires a target language to be specified during decoding from
amongst those that the model has seen, we follow past work in selecting
languages related to our target languages for unseen languages (Madaan et al.,
2020; Cahyawijaya et al., 2021). Considering syntactic and phylogenic
closeness of languages (Dryer and Haspelmath, 2013; Littell et al., 2017), we
chose bn for as, te for kn, fr for ga, and sw for yo.

#### mT5.

Considering memory bottlenecks, we use the mT5-base model. It supports over
100 languages, including five of the six from our preliminary experiment.
Because Irish (ga) is not among these, we use the French language code for
fine-tuning the model.

#### Transformer.

We train Transformer models implemented in Fairseq using the same datasets as
we used for fine-tuning mBART. We use two Transformer architectures, depending
on the data size. When there are fewer than 10k parallel sentences, the model
consists of 3 encoder layers and 3 decoder layers, with embedding dimension of
512 and 2 attention heads. When there are 10k or more parallel sentences, we
instead use a model that consists of 6 encoder layers and 6 decoder layers,
with an embedding dimension of 256 and 2 attention heads. In each case, we
have an initial learning rate of $1\times 10^{-3}$, a weight decay of $1\times
10^{-4}$, dropout of $0.4$, and batch size of $32$. We use early stopping
based on the validation loss. We train the models from scratch with
segmentation into subword tokens performed by SentencePiece. When decoding, we
use beam search with a beam size of $5$.

#### Evaluation.

To ease the comparison of future work with ours, we report that the SacreBLEU
settings we use are represented by the signature
`BLEU+c.mixed+#.1+s.exp+tok.13a+v.1.5.0`.