# Robust and efficient change point detection using novel multivariate rank-
energy GoF test

###### Abstract

In this paper, we use and further develop upon a recently proposed
multivariate, distribution-free Goodness-of-Fit (GoF) test based on the theory
of Optimal Transport (OT) called the Rank Energy ($\mathsf{RE}$) [1], for non-
parametric and unsupervised Change Point Detection (CPD) in multivariate time
series data. We show that directly using $\mathsf{RE}$ leads to high
sensitivity to very small changes in distributions (causing high false alarms)
and it requires large sample complexity and huge computational cost. To
alleviate these drawbacks, we propose a new GoF test statistic called as soft-
Rank Energy ($\mathsf{sRE}$) that is based on entropy regularized OT and
employ it towards CPD. We discuss the advantages of using $\mathsf{sRE}$ over
$\mathsf{RE}$ and demonstrate that the proposed $\mathsf{sRE}$ based CPD
outperforms all the existing methods in terms of Area Under the Curve (AUC)
and F1-score on real and synthetic data sets.

©2022 IEEE. Personal use of this material is permitted. Permission from IEEE
must be obtained for all other uses, in any current or future media, including
reprinting/republishing this material for advertising or promotional purposes,
creating new collective works, for resale or redistribution to servers or
lists, or reuse of any copyrighted component of this work in other works.

Index Terms—  multivariate rank, rank energy, soft rank energy, optimal
transport, halton points.

##  1 Introduction

A significant part of the multivariate time series analysis deals with the
detection of unknown abrupt changes in a temporal signal that represent the
transitions from one state to another. This problem, commonly referred to as
the change point detection (CPD), has been extensively studied in statistics
and machine learning and is found in many real-world applications including
the analysis of physiological [2], financial [3] and sensor data [4].

Statistical CPD methods can be categorized into different criteria e.g.,
univariate vs. multivariate, parametric vs. nonparametric. Parametric or
model-based methods assume that parameters of the underlying time series data
distribution are either known or can be learned from data [5, 6]. Parametric
methods are advantageous if either of these assumptions holds true. When the
distributions are unknown or learning the parameters from data is difficult,
nonparametric methods are desirable. Approximation of divergence based on
direct density-ratio estimation [7] and the integral probability metric e.g.,
maximum mean discrepancy (MMD) [8] based two-sample multivariate Goodness-of-
fit (GoF) test have been proposed in [9, 10] as the nonparametric ways to
detect change points. Some other nonparametric GoF tests that have been used
for CPD such as Kolmogorov-Smirnov (KS), and Cramer-von-Mises [11], are
univariate in nature. Recently [12] used the univariate Wasserstein two-sample
test (W2T) based on the theory of OT in one-dimension [13] for CPD. However,
one of the drawbacks of this method is that it projects the data onto several
one dimensional directions and uses the average statistic, which can lead to
the loss of detection power.

Main contributions \- In this work, we propose CPD using recently developed
statistics known as the Rank Energy ($\mathsf{RE}$) [1]. What makes
$\mathsf{RE}$ attractive for CPD is that it is a multivariate rank-based and
distribution-free GoF test [1], where the notion of rank is derived leveraging
the theory of Optimal Transport (OT) in high dimensions.

However, as we outline in more detail subsequently and as borne out from
simulation results, directly using the sample version of $\mathsf{RE}$ for CPD
has some drawbacks, namely, high sensitivity to small changes (leading to high
false alarm rates), high computational complexity, and large sample
complexity. To alleviate these shortcomings, we propose a new statistic,
called soft-Rank Energy ($\mathsf{sRE}$) that leverages the computational and
sample efficient entropy regularized OT [14] and exploit it for CPD. We
demonstrate the advantages of using $\mathsf{sRE}$ over $\mathsf{RE}$. We also
evaluate the performances of $\mathsf{RE}$ and $\mathsf{sRE}$ on both toy and
real datasets and compare them with the existing state-of-the-art (SOTA)
methods.

The rest of the paper is organized as follows- In section 3 we provide
necessary background on the multivariate $\mathsf{RE}$ and highlight the pros
and cons of using $\mathsf{RE}$ in CPD. In section 4, we then introduce the
sample version of $\mathsf{sRE}$ and employ it in CPD. In section 5 we show
improved AUC and F1-score for CPD on real datasets compared to state-of-the-
art.

##  2 Problem set-up

Notation: We use bold-math capital letters $\bm{X}$ for multivariate random
variables, bold-face capital letters $\mathbf{X}$ for matrices and maps,
lower-case bold face bold-math $\bm{x}$ for vectors. We denote by
$\mathcal{P}(\mathbb{R}^{d})$ the set of probability measures on
$\mathbb{R}^{d}$. The rest of the notation is standard and should be clear
from the context.
Given a time series $\bm{Z}[t]\in\mathbb{R}^{d}$, $t=1,2,\dots$, where the
data consists of distinct segments
$[0,\\!\tau_{1}],\\!\;[\tau_{1}\\!+\\!1,\\!\tau_{2}],\dots,[\tau_{k-1}+1,\tau_{k}]$
with $\tau_{1}<\tau_{2}<\dots$ Samples within each segment,
$\bm{X}[t],t\in[\tau_{i-1}+1,\tau_{i}]$, are assumed to be i.i.d. and
originated from an unknown distribution. In general, the distributions in two
adjoining segments are considered to be different, whereas two distant
segments may have a similar distribution. The primary objective of a
nonparametric CPD method is to detect the change points
$\tau_{1},\tau_{2},\dots,\tau_{k}$ without any prior knowledge or assumptions
on the set of underlying distributions of the distinct time segments.

A sliding window two-sample GoF test: A common framework to detect change
points is the sliding-window approach [9]. Given a window size $n$ on each
side of a possible change point, an offline, unsupervised sliding window-based
CPD method generally takes two adjacent time segments
$\\{\bm{Z}[t-n],\bm{Z}[t-n+1],\dots,\bm{Z}[t-1]\\}\sim\mu_{X}$ and
$\\{\bm{Z}[t+1],\bm{Z}[t+2],\dots,\bm{Z}[n+t-1]\\}\sim\mu_{Y}$ and carry out a
two-sample GoF test at each $t=1,2,\dots$

For CPD, using the sliding window GoF test, a detection range $\delta$ is
utilized. A time point $t$ is declared as a change point if the statistic
$\sigma(t)$ at this point is the local maximum within $\delta$ and above a
threshold $\eta$. In general, $\eta$ is specific to the statistical tests
which is calculated from the distribution of the statistics under the null
given a confidence level. The sliding-window based CPD procedure is described
in Algorithm 1. In this context, our main contributions in this paper are to
apply the recently proposed Rank-Energy ($\mathsf{RE}$) [1] as the GoF test
for CPD, highlight its main properties and shortcomings and then propose a new
test that improves upon this GoF test.

Algorithm 1 Sliding-window based CPD employing GoF test

1:$\bm{Z}[t]$: data, window size: $n$, threshold: $\eta$.

2:for each $t:n:(T-n)$ do

3: $\mathbf{X}[t]=\\{\bm{Z}[t-n],\dots,\bm{Z}[t-1]\\}$

4: $\mathbf{Y}[t]=\\{\bm{Z}[t],\dots,\bm{Z}[t-n+1]\\}$

5: $\sigma(t)\leftarrow\text{GoF-
statistic}\big{(}\mathbf{X}[t],\mathbf{Y}[t]$)

6:end for

7:Output:
$\\{\tau_{1},\tau_{2},\dots\\}\\!\\!\leftarrow\\!\\!\\{t|\text{max}(\sigma(t)\\!>\\!\eta)\\}$

##  3 Background: Optimal Transport (OT) Based Multivariate Rank Energy Test

Optimal Transport, in it’s most well-studied setting [15, 14], aims to find
$\mathbf{T}:\mathbb{R}^{d}\rightarrow\mathbb{R}^{d}$\- a map that pushes a
source distribution $\mu\in\mathcal{P}(\mathbb{R}^{d})$ to a target
distribution $\nu\in\mathcal{P}(\mathbb{R}^{d})$ with a minimal expected
squared Euclidean cost. That is, given two multivariate random variables,
$\bm{X}\in\mathbb{R}^{d}\sim\mu$, and $\bm{Y}\in\mathbb{R}^{d}\sim\nu$, OT
finds a map $\mathbf{T}$ that solves for,

$\displaystyle\inf_{\mathbf{T}}\int\|\bm{x}-\mathbf{T}(\bm{x})\|^{2}d\mu(\bm{x})\;\;\text{subject
to.}\;\;\bm{Y}=\mathbf{T}(\bm{x})\sim\nu,$ (1)

where $\|\cdot\|$ denotes the standard Euclidean norm in $\mathbb{R}^{d}$.
Note that if $\mathbf{T}(\bm{X})\sim\nu$ when $\bm{X}\sim\mu$, we write
$\nu=\mathbf{T}_{\\#}\mu$. In this case, the measure $\nu$ is referred to as
the push-forward of measure $\mu$ under the mapping $\mathbf{T}$.

When $d=1$, it is known that the optimal map is
$\mathbf{T}=\mathsf{F}_{\nu}^{-1}\circ\mathsf{F}_{\mu}$, where
$\mathsf{F}_{\mu}$ and $\mathsf{F}_{\nu}$ are the (cumulative) distribution
functions for $\mu$ and $\nu$, respectively [15, 14]. If the target measure
$\nu=\mathsf{U}[0,1]$ is a uniform distribution on the line, then
$\mathbf{T}=\mathsf{F}_{\mu}$, which is similar to the rank function in $1$-d.
Extending this insight to the multivariate case, the notion of rank has been
developed based on the following landmark result in OT theory.

######  Theorem 1 (McCann [16]).

Assume $\mu,\nu\in\mathcal{P}(\mathbb{R}^{d})$ be absolutely continuous
measures, then there exist transport maps $\mathbf{R}(\cdot)$ and
$\mathbf{Q}(\cdot)$, that are gradients of real-valued $d$-variate convex
functions such that $\mathbf{R}_{\\#}\mu=\nu,\;\;\mathbf{Q}_{\\#}\nu=\mu$,
$\mathbf{R}$ and $\mathbf{Q}$ are unique and
$\mathbf{R}\circ\mathbf{Q}(\bm{x})=\bm{x}$,
$\mathbf{Q}\circ\mathbf{R}(\bm{y})=\bm{y}$.

In particular, the fact that the gradients of convex functions are monotone
maps [16] has led the authors in [1, 17] to define $\mathbf{R}$ and
$\mathbf{Q}$ as the multivariate rank and quantile map respectively under
appropriate selection of the target measure $\nu$.
Specific to this work, the authors in [1] use the uniform measure on the unit
cube in $\mathbb{R}^{d}$ as the target measure and, developed the rank energy
statistic as a GoF measure between distributions, whose sample version is
stated below.

Sample Multivariate Rank Energy [1]: Given two sets of i.i.d. samples
$\\{\\!\bm{X}_{1},\dots,\bm{X}_{m}\\!\\}\\!\sim\\!\mu_{X}\\!\in\\!\mathcal{P}(\mathbb{R}^{d})$
and
$\\{\bm{Y}_{1},\dots,\bm{Y}_{n}\\}\sim\mu_{Y}\in\mathcal{P}(\mathbb{R}^{d})$.
Let
$\mu^{\bm{X}}_{m}\\!\\!=\\!\\!\frac{1}{m}\sum_{i=1}^{m}\delta_{\bm{X}_{i}}$,
$\mu^{\bm{Y}}_{n}\\!\\!=\\!\\!\frac{1}{n}\sum_{i=1}^{n}\delta_{\bm{Y}_{i}}$
denote the empirical measures. A set of fixed Halton sequences [18], that
mimic randomly chosen vectors in the unit cube in $\mathbb{R}^{d}$, denoted as
$\mathcal{H}_{m+n}^{d}:=\\{\bm{h}_{1}^{d},\dots,\bm{h}^{d}_{m+n}\\}\subset[0,1]^{d}$
with the empirical measure
$\nu_{m,n}^{\mathbf{H}}=(m+n)^{-1}\sum_{i=1}^{m+n}\delta_{\bm{h}_{i}}$ is
taken as the target points.

A joint empirical map $\mathbf{\widehat{R}}_{m,n}$ is computed between the
joint empirical measure
$\mu_{m,n}^{\bm{X},\bm{Y}}:=(m+n)^{-1}(m\mu^{\bm{X}}_{m}+n\mu^{\bm{Y}}_{n})$
and $\nu_{m,n}^{\mathbf{H}}$ by solving the following discrete OT problem,

$\displaystyle\mathbf{\widehat{P}}=\arg\min_{\mathbf{P}\in\Pi}\sum_{i,j=1}^{m+n}\mathbf{C}_{i,j}\mathbf{P}_{i,j},$
(2)

where $\mathbf{C}_{i,j}$ is the squared Euclidean distance, and
$\Pi=\\{\mathbf{P}:\mathbf{P}\bm{1}=\frac{1}{m+n}\bm{1},\bm{1}^{\top}\mathbf{P}=\frac{1}{m+n}\bm{1}^{\top}\\}$.
The above formulation is also known as the Kantorovich relaxation [14]. Now
for any $\bm{X}_{i}$, one obtains a map as
$\widehat{\mathbf{R}}_{m,n}(\bm{X}_{i})\\!\\!=\\!\\!\bm{h}_{\sigma(i)}$, where
$\sigma(i)$ is the non-zero index in the $i$-th row of $\widehat{\mathbf{P}}$.
Given the ranks corresponding to $\bm{X}_{i}$’s and $\bm{Y}_{j}$’s, sample
rank energy [1] is defined as,

$\displaystyle\mathsf{RE}\\!\\!$
$\displaystyle:=\\!\\!\frac{2}{mn}\\!\\!\sum_{i,j=1}^{m,n}\\!\\!\|\widehat{\mathbf{R}}_{m,n}(\bm{X}_{i})\\!-\\!\widehat{\mathbf{R}}_{m,n}(\bm{Y}_{j})\|\\!\\!-\\!\\!\frac{1}{m^{2}}\\!\\!\\!\sum_{i,j=1}^{m}\\!\\!\|\widehat{\mathbf{R}}_{m,n}(\bm{X}_{i})$
$\displaystyle-\widehat{\mathbf{R}}_{m,n}(\bm{X}_{j})\|-\frac{1}{n^{2}}\sum_{i,j=1}^{n}\\!\\!\|\widehat{\mathbf{R}}_{m,n}(\bm{Y}_{i})\\!\\!-\\!\\!\widehat{\mathbf{R}}_{m,n}(\bm{Y}_{j})\|.$
(3)

The null hypothesis $H_{0}$ is rejected if $mn(m+n)^{-1}\mathsf{RE}$ is
greater than the threshold and accepted otherwise. As shown in [1],
$\mathsf{RE}$ is distribution-free under the null for fixed sample size, a
property that is desirable for selecting an optimal universal threshold to
reject the null hypothesis, $H_{0}:\mu_{\bm{X}}=\mu_{\bm{Y}}$.

We now note several shortcomings of directly using $\mathsf{RE}$ for CPD.

  * •

Sensitivity: As shown from Figure 1, we note that $\mathsf{RE}$ is
particularly sensitive to small shift in the mean and changes in the
covariance. This characteristic may be useful in applications where it is
required to detect any tiny changes. However, in many real-world datasets,
these tiny changes may not be labeled as the true change points. Hence using
$\mathsf{RE}$ in CPD may lead to the detection of many false positives and
deteriorate the overall performance.

  * •

Sample Complexity: Curse of dimensionality - In general case, sample
complexity for reliable estimation of the sample rank map scales as
$O(n^{-1/d})$ with dimension $d$ [19].

  * •

Computational complexity: Being a linear program, the computational complexity
of the OT plan for sample $\mathsf{RE}$ scales as $\mathcal{O}(n^{3}\log n)$,
for a given sample size $n$, which is expensive.

To alleviate these issues, in the next section, we introduce the sample soft-
Rank Energy that leverages the properties of entropy regularized optimal
transport [14].

Fig. 1: $\mathsf{RE}$ and $\mathsf{sRE}$ with $\varepsilon=\\{0.001,1,5\\}$
statistics (right axis) produced on a toy dataset using a sliding-window CPD
approach with a window size $n=250$. Dataset consists of 5 different
$3$-dimensional Gaussian distributions
$\mathcal{N}(\bm{\mu}_{3},\sigma\mathbf{I}_{3})$, with zero baselines on both
ends. Here, $\mathbf{I}_{3}$ denotes the identity matrix.
$\mathsf{RE}(\varepsilon=0)$ and $\mathsf{sRE}(\varepsilon=0.001)$ can detect
the tiny changes between the baseline and
$\mathcal{N}(0_{3},0.001\mathbf{I}_{3})$ on both sides, whereas $\mathsf{sRE}$
with $\varepsilon=\\{1,5\\}$ do not label these points as true change points.

##  4 Proposed Sample Multivariate Soft Rank Energy

Given two sets of i.i.d. samples
$\\{\bm{X}_{1},\dots,\bm{X}_{m}\\}\\!\\!\sim\\!\\!\mu_{X}\in\mathcal{P}(\mathbb{R}^{d})$
and
$\\{\bm{Y}_{1},\dots,\bm{Y}_{n}\\}\\!\\!\sim\\!\\!\mu_{Y}\in\mathcal{P}(\mathbb{R}^{d})$.
To compute the soft rank, an entropy regularized OT with a regularizer
$\varepsilon$, is solved via Sinkhorn algorithm [14] between the empirical
joint source measure $\mu_{m,n}^{\bm{X},\bm{Y}}$ and the reference measure
$\nu_{m,n}^{\mathbf{H}}$,

$\displaystyle\mathbf{\widehat{P}}^{\epsilon}=\arg\min_{\mathbf{P}\in\Pi}\sum_{i,j=1}^{m+n}\mathbf{C}_{i,j}\mathbf{P}_{i,j}-\varepsilon
H(\mathbf{P}),$ (4)

where $\mathbf{C}_{i,j}$ is the squared Euclidean distance, $\varepsilon>0$,
$\Pi=\\{\mathbf{P}:\mathbf{P}\bm{1}=\frac{1}{m+n}\bm{1},\bm{1}^{\top}\mathbf{P}=\frac{1}{m+n}\bm{1}^{\top}\\}$,
and $H(\mathbf{P})=-\sum_{i,j}\mathbf{P}_{i,j}\log\mathbf{P}_{i,j}$ is the
entropy functional. $\mathbf{\widehat{P}^{\varepsilon}}$ is a diffused optimal
plan, where the degree of diffusion increases as $\varepsilon$ increases.
Soft ranks are then obtained as follows. We compute a _row-normalized_ plan
$\mathbf{\bar{P}}^{\epsilon}$ via
$\mathbf{\bar{P}}_{i,j}^{\epsilon}=\frac{\mathbf{\widehat{P}}_{i,j}^{\varepsilon}}{\sum_{j=1}^{m+n}\mathbf{\widehat{P}}_{i,j}^{\varepsilon}}$.
Now, for any $\bm{X}_{i}$, one obtains the soft ranks via,

$\displaystyle\widehat{\mathbf{R}}^{s,\epsilon}(\bm{X}_{i})$
$\displaystyle=\sum_{j=1}^{m+n}\mathbf{\bar{P}^{\varepsilon}_{i,j}}\bm{h}_{j}=\mathbb{E}_{\mathbf{\widehat{P}^{\varepsilon}}}[\bm{h}_{j}|\bm{X}_{i}].$
(5)

In other words, soft ranks are the conditional expectation of Halton sequences
under the joint distribution $\mathbf{\widehat{P}}^{\varepsilon}$ given the
source samples.
Given the soft ranks corresponding to $\bm{X}_{i}$’s and $\bm{Y}_{j}$’s,
sample soft rank energy is defined using the same formulation as in Equation
(3):

$\displaystyle\mathsf{sRE}\\!\\!$
$\displaystyle:=\\!\\!\frac{2}{mn}\\!\\!\sum_{i,j=1}^{m,n}\\!\\!\|\widehat{\mathbf{R}}^{s,\epsilon}(\bm{X}_{i})\\!-\\!\widehat{\mathbf{R}}^{s,\epsilon}(\bm{Y}_{j})\|\\!\\!-\\!\\!\frac{1}{m^{2}}\sum_{i,j=1}^{m}\|\widehat{\mathbf{R}}^{s,\epsilon}(\bm{X}_{i})$
$\displaystyle-\widehat{\mathbf{R}}^{s,\epsilon}(\bm{X}_{j})\|-\frac{1}{n^{2}}\sum_{i,j=1}^{n}\|\widehat{\mathbf{R}}^{s,\epsilon}(\bm{Y}_{i})-\widehat{\mathbf{R}}^{s,\epsilon}(\bm{Y}_{j})\|.$
(6)

The null hypothesis $H_{0}$ is rejected if $mn(m+n)^{-1}\mathsf{sRE}$ is
greater than the threshold and accepted otherwise. We note the following
result relating $\mathsf{sRE}$ and $\mathsf{RE}$.

######  Proposition 1.

Soft rank energy $\mathsf{sRE}$ will converge to rank energy $\mathsf{RE}$ as
$\varepsilon\rightarrow 0$.

###### Proof.

The unique minimizer $\mathbf{P^{\varepsilon}}$ of Equation (4) converges to
the optimal solution $\mathbf{P}$ (Equation 2) with a cost function
$\mathbf{C}_{i,j}=\|\bm{X}_{i}-\bm{h}_{j}\|^{2}$ [20],

$\displaystyle\mathbf{P^{\varepsilon}}\rightharpoonup\mathbf{P},$ (7)

where $\rightharpoonup$ denotes convergence w.r.t. weak topology. Let
$\bar{\mathbf{P}}$ denote the row-normalized $\mathbf{P}$. Then Equation (7)
implies that $\lim_{\varepsilon\rightarrow
0}\mathbf{\bar{P}^{\varepsilon}}\rightharpoonup\mathbf{\bar{P}}$, and
$\widehat{\mathbf{R}}^{s,\epsilon}(\bm{X}_{i})\rightharpoonup\widehat{\mathbf{R}}_{m,n}(\bm{X}_{i})$.
Therefore, $\lim_{\varepsilon\rightarrow 0}\mathsf{sRE}=\mathsf{RE}$.

∎

We note the following properties of $\mathsf{sRE}$ that help alleviate the
issues in directly using $\mathsf{RE}$ for CPD.

  * •

Proposition (1) implies that $\mathsf{sRE}$ will be nearly distribution-free
for small enough $\varepsilon$.

  * •

Sensitivity: As shown in Figure 1, $\mathsf{sRE}$ is sensitive to small
changes for $\varepsilon=0.001$. For $\varepsilon=1$, sensitivity decreases.
However, $\mathsf{sRE}$ still generates visible peaks at all the change points
except the transition between the baseline and Gaussian distribution with tiny
covariance. With $\varepsilon=5$, $\mathsf{sRE}$ shows the least sensitivity
with barely visible peaks at the change points. The entropic regularization
parameter thus allows control of the degree of sensitivity that can be adapted
or adjusted to control the false alarms. A good choice for CPD will be the
$\varepsilon$, for which $\mathsf{sRE}$ is neither too sensitive nor totally
unresponsive to changes.

  * •

Sample complexity: Under some mild assumptions, namely, sub-Gaussianity of the
measures, the estimation of the entropic optimal transport does not suffer
from the curse of dimensionality for a sufficiently large $\varepsilon$ [19].

  * •

Computational complexity: For a sample size $n$, the computational complexity
of entropic optimal transport is
$\mathcal{O}(\varepsilon^{-2}n^{2}\log\,n\|\mathbf{C}\|_{\infty}^{2})$ [14].
The smaller the $\varepsilon$, the costlier the computation.

|  | CP-AUC |  |  | CP-F1 |
---|---|---|---|---|---|---
| HASC-PAC2016 | HASC2011 | Beedance | HASC-PAC2016 | HASC2011 | Beedance
W2T (Rank-Quantile), $d=1$ [12] | 0.689 | 0.576 | 0.721 | 0.748 | 0.824 | 0.742
M-stat (IPM-based), $d\geq 1$, [9] | 0.658 | 0.585 | 0.727 | 0.713 | 0.770 | 0.725
RE (Rank-Rank) $d\geq 1$, [1] | 0.718 | 0.529 | 0.694 | 0.631 | 0.643 | 0.672
sRE (soft Rank-Rank [This paper], $d\geq 1$ | 0.747 | 0.670 | 0.739 | 0.785 | 0.796 | 0.745
Table 1: Comparison between the proposed method and related state of art in
literature.

##  5 Numerical Experiments & Simulations

Experimental Setup: We compare the performances of our methods with two other
existing algorithms, the univariate distribution-free Wasserstein two-sample
test (W2T) [12] based CPD and the multivariate M-Statistic (MStat) [9] based
CPD that uses Maximum-Mean Discrepancy (MMD) [8] for measuring GoF. The
Gaussian kernel with unit variance is used to compute MStat.

For a fair comparison, we apply the optimal matched filter proposed in [12] on
W2T and MStat that improves the performances of these methods significantly.
It is to be noted that no smoothing filter was applied on $\mathsf{RE}$ and
$\mathsf{sRE}$ statistics.

The hyperparameters we use in the CPD algorithm are the entropic regularizer
$\varepsilon$, and the detection threshold $\eta$ to compute the F1 score. To
compare the methods on an equal footing, we use the same window size $n$ and
detection range $\delta$ for all the methods. The optimal $\eta$,
$\varepsilon$ selected for the proposed methods, window size $n$, and the
detection range $\delta$ along with the specifications of the used datasets
can be found in Table 2. It is worthwhile to note that, since the Beedance
dataset has a comparatively shorter sequence, we padded it with a zero
sequence of length $n$ on both ends.

| HASC2011[21] | HASC-PAC2016[21] | Beedance[22]
---|---|---|---
domain | $\mathbb{R}^{3}$ | $\mathbb{R}^{3}$ | $\mathbb{R}^{3}$
$\\#$ subjects | 2 | 10 | 6
$\\#$actions | 6 | 6 | 3
$\\#$ CP | 65 | 13 | 19
$n$ | 500 | 500 | 50
$\varepsilon$ | 2 | 1 | 1
$\delta$ | 250 | 250 | 10
$\eta$ | 0.52 | 0.52 | 0.25
Table 2: $\\#$ denotes the total number and CP is for change points.

Result on real data: Table 1 demonstrates the performance comparison of the
proposed methods with MStat [9] and W2T [12]. The proposed methods demonstrate
robust results for CPD under the AUC metric. $\mathsf{RE}$ gains higher AUC
compared to W2T and MStat on HASC-PAC2016 dataset but fails to outperform on
HASC2011 and Beedance datasets. $\mathsf{RE}$’s highly sensitive nature to
tiny changes brings about many false alarms, thus explains the lower AUC for
these datasets. On the other hand, $\mathsf{sRE}$ outperforms all the methods
on all three datasets in terms of AUC score. To be noted here, we observe
significant improvement of the AUC using W2T and MStat on the Beedance dataset
after the inclusion of zero-padding on both ends.

Though under the AUC metric, $\mathsf{RE}$ shows a comparable result, we
observe lower F1-scores compared to W2T and MStat on all three datasets. Since
we did not apply any filter to smooth out the $\mathsf{RE}$ statistics,
several spurious maxima exist outside of the detection range $\delta$ on both
sides of the peaks. Moreover, $\mathsf{RE}$ also produces a lot of false
alarms because of its higher sensitivity to small changes. As a result,
$\mathsf{RE}$ achieves slightly lower F1-scores on all three datasets. On the
other hand, $\mathsf{sRE}$ achieves either higher or comparable F1-scores in
all three datasets. On HASC-PAC2016 and Beedance datasets, $\mathsf{sRE}$
achieves the highest F1-score. W2T-based CPD achieves the maximum F1-score on
HASC2011, whereas $\mathsf{sRE}$ performs comparably.

We also compare the performance of $\mathsf{sRE}$ to the method called KL-CPD
[23], which is a semi-supervised CPD method. The best AUC is achieved by KL-
CPD which is a kernel-based semi-supervised method trained by a deep
generative model. KL-CPD achieves AUC of 0.677 and 0.649 on the Beedance and
HASC2011 dataset, respectively, which is clearly lower than the AUC scores
obtained by the proposed $\mathsf{sRE}$.

##  6 Conclusion and Future work

In this paper, we employ recently developed multivariate GoF statistics to
detect change points in an unsupervised, offline approach. We also propose a
new statistic that depends on a regularization parameter which allows control
of the degree of sensitivity. With an appropriate regularizer, we have shown
that our proposed statistic lowers the false positive rate, hence outperforms
state of the art in CPD under the AUC and F1-score metric. Future work will
investigate theoretical properties of $\mathsf{sRE}$ and explain the smoothing
effect in CPD as a function of the entropic regularization.

##  7 Acknowledgement

This research was sponsored by the U.S. Army DEVCOM Soldier Center, and was
accomplished under Cooperative Agreement Number W911QY-19-2-0003. The views
and conclusions contained in this document are those of the authors and should
not be interpreted as representing the official policies, either expressed or
implied, of the U.S. Army DEVCOM Soldier Center, or the U.S. Government. The
U. S. Government is authorized to reproduce and distribute reprints for
Government purposes notwithstanding any copyright notation hereon.

We also acknowledge support from the U.S. National Science Foundation under
award HDR-1934553 for the Tufts T-TRIPODS Institute. Shuchin Aeron is also
supported in part by NSF CCF:1553075, NSF RAISE 1931978, NSF ERC planning
1937057, and AFOSR FA9550-18-1-0465.

## References

  * [1] Nabarun Deb and Bodhisattva Sen,  “Multivariate rank-based distribution-free nonparametric testing using measure transportation,”  Journal of the American Statistical Association, , no. just-accepted, pp. 1–45, 2021.
  * [2] Jin-Peng Qi, Qing Zhang, Ying Zhu, and Jie Qi,  “A novel method for fast change-point detection on simulated time series and electrocardiogram data,”  PloS one, vol. 9, no. 4, pp. e93365, 2014.
  * [3] Carlos M Carvalho and Hedibert F Lopes,  “Simulation-based sequential analysis of markov switching stochastic volatility models,”  Computational Statistics & Data Analysis, vol. 51, no. 9, pp. 4526–4542, 2007.
  * [4] Ting He, Shai Ben-David, and Lang Tong,  “Nonparametric change detection and estimation in large-scale sensor networks,”  IEEE transactions on signal processing, vol. 54, no. 4, pp. 1204–1217, 2006.
  * [5] Faicel Chamroukhi, Samer Mohammed, Dorra Trabelsi, Latifa Oukhellou, and Yacine Amirat,  “Joint segmentation of multivariate time series with hidden process regression for human activity recognition,”  Neurocomputing, vol. 120, pp. 633–644, 2013.
  * [6] Wei-Han Lee, Jorge Ortiz, Bongjun Ko, and Ruby Lee,  “Time series segmentation through automatic feature learning,”  arXiv preprint arXiv:1801.05394, 2018.
  * [7] Takafumi Kanamori, Shohei Hido, and Masashi Sugiyama,  “A least-squares approach to direct importance estimation,”  The Journal of Machine Learning Research, vol. 10, pp. 1391–1445, 2009.
  * [8] Arthur Gretton, Karsten M Borgwardt, Malte J Rasch, Bernhard Schölkopf, and Alexander Smola,  “A kernel two-sample test,”  The Journal of Machine Learning Research, vol. 13, no. 1, pp. 723–773, 2012.
  * [9] Shuang Li, Yao Xie, Hanjun Dai, and Le Song,  “Scan $b$-statistic for kernel change-point detection,”  arXiv preprint arXiv:1507.01279, 2015.
  * [10] Song Liu, Makoto Yamada, Nigel Collier, and Masashi Sugiyama,  “Change-point detection in time-series data by relative density-ratio estimation,”  Neural Networks, vol. 43, pp. 72–83, 2013.
  * [11] Douglas M Hawkins and Qiqi Deng,  “A nonparametric change-point control chart,”  Journal of Quality Technology, vol. 42, no. 2, pp. 165–173, 2010\.
  * [12] Kevin C Cheng, Shuchin Aeron, Michael C Hughes, Erika Hussey, and Eric L Miller,  “Optimal transport based change point detection and time series segment clustering,”  in ICASSP 2020-2020 IEEE International Conference on Acoustics, Speech and Signal Processing (ICASSP). IEEE, 2020, pp. 6034–6038.
  * [13] Aaditya Ramdas, Nicolás García Trillos, and Marco Cuturi,  “On wasserstein two-sample testing and related families of nonparametric tests,”  Entropy, vol. 19, no. 2, pp. 47, 2017.
  * [14] Gabriel Peyré, Marco Cuturi, et al.,  “Computational optimal transport: With applications to data science,”  Foundations and Trends® in Machine Learning, vol. 11, no. 5-6, pp. 355–607, 2019.
  * [15] Filippo Santambrogio,  “Optimal transport for applied mathematicians,”  Birkäuser, NY, vol. 55, no. 58-63, pp. 94, 2015.
  * [16] Robert J McCann et al.,  “Existence and uniqueness of monotone measure-preserving maps,”  Duke Mathematical Journal, vol. 80, no. 2, pp. 309–324, 1995.
  * [17] Marc Hallin et al.,  “On distribution and quantile functions, ranks and signs in rd,”  ECARES Working Papers, 2017.
  * [18] Hongmei Chi, Michael Mascagni, and Tony Warnock,  “On the optimal halton sequence,”  Mathematics and computers in simulation, vol. 70, no. 1, pp. 9–21, 2005.
  * [19] Aude Genevay, Lénaic Chizat, Francis Bach, Marco Cuturi, and Gabriel Peyré,  “Sample complexity of sinkhorn divergences,”  in The 22nd International Conference on Artificial Intelligence and Statistics. PMLR, 2019, pp. 1574–1583.
  * [20] Guillaume Carlier, Vincent Duval, Gabriel Peyré, and Bernhard Schmitzer,  “Convergence of entropic schemes for optimal transport and gradient flows,”  SIAM Journal on Mathematical Analysis, vol. 49, no. 2, pp. 1385–1418, 2017.
  * [21] Haruyuki Ichino, Katsuhiko Kaji, Ken Sakurada, Kei Hiroi, and Nobuo Kawaguchi,  “Hasc-pac2016: Large scale human pedestrian activity corpus and its baseline recognition,”  in Proceedings of the 2016 ACM International Joint Conference on Pervasive and Ubiquitous Computing: Adjunct, 2016, pp. 705–714.
  * [22] Sang Min Oh, James M Rehg, Tucker Balch, and Frank Dellaert,  “Learning and inferring motion patterns using parametric segmental switching linear dynamic systems,”  International Journal of Computer Vision, vol. 77, no. 1, pp. 103–124, 2008.
  * [23] Wei-Cheng Chang, Chun-Liang Li, Yiming Yang, and Barnabás Póczos,  “Kernel change-point detection with auxiliary deep generative models,”  arXiv preprint arXiv:1901.06077, 2019.


# Improving Zero-Shot Multilingual Translation with
Universal Representations and Cross-Mappings

Shuhao Gu1,2, Yang Feng1,2
1 Key Laboratory of Intelligent Information Processing,
Institute of Computing Technology, Chinese Academy of Sciences (ICT/CAS)
2 University of Chinese Academy of Sciences
<EMAIL_ADDRESS>∗Corresponding author: Yang Feng.
Reproducible code: https://github.com/ictnlp/Zero-MNMT.

###### Abstract

The many-to-many multilingual neural machine translation can translate between
language pairs unseen during training, i.e., zero-shot translation. Improving
zero-shot translation requires the model to learn universal representations
and cross-mapping relationships to transfer the knowledge learned on the
supervised directions to the zero-shot directions. In this work, we propose
the state mover’s distance based on the optimal theory to model the difference
of the representations output by the encoder. Then, we bridge the gap between
the semantic-equivalent representations of different languages at the token
level by minimizing the proposed distance to learn universal representations.
Besides, we propose an agreement-based training scheme, which can help the
model make consistent predictions based on the semantic-equivalent sentences
to learn universal cross-mapping relationships for all translation directions.
The experimental results on diverse multilingual datasets show that our method
can improve consistently compared with the baseline system and other contrast
methods. The analysis proves that our method can better align the semantic
space and improve the prediction consistency.

##  1 Introduction

The many-to-many multilingual neural machine translation (NMT) Ha et al.
(2016); Firat et al. (2016); Johnson et al. (2017); Gu et al. (2018); Fan et
al. (2020); Zhang et al. (2020a) model can support multiple translation
directions in a single model. The shared encoder encodes the input sentence to
the semantic space, and then the shared decoder decodes from the space to
generate the translation of the target language. This paradigm allows the
model to translate between language pairs unseen during training, i.e., zero-
shot translation. Zero-shot translation can improve the inference efficiency
and make the model require less bilingual training data. Performing zero-shot
translation requires universal representations to encode the language-agnostic
features and cross-mapping relationships that can map the semantic-equivalent
sentences of different languages to the particular space of the target
language. In this way, the model can transfer the knowledge learned in the
supervised translation directions to the zero-shot translation directions.
However, the existing model structure and training scheme cannot ensure the
universal representations and cross-mappings because of lacking explicit
constraints. Specifically, the encoder may map different languages to
different semantic subspaces, and the decoder may learn different mapping
relationships for different source languages, especially when the model
possesses high capacity.

Many researchers have made their attempts to solve this problem. Pham et al.
(2019) propose to compress the output of the encoder into a consistent number
of states to only encode the language-independent features. Arivazhagan et al.
(2019) add a regularizing loss to maximize the similarities between the
sentence representations of the source and target sentences. Pan et al. (2021)
propose contrastive learning schemes to minimize the sentence representation
gap of similar sentences and maximize that of irrelevant sentences. All the
above work tries to minimize the representation discrepancies of different
languages at the sentence level, bringing two problems for NMT. Firstly, these
work usually get the sentence-level representation of the encoder output by
max-pooling or averaging, which may potentially ignore the sentence length,
word alignment relationship, and other token-level information. Secondly,
regularizing sentence representation mismatches to the working paradigm of the
NMT model, because the decoder directly performs cross attention on the whole
state sequences rather than the sentence representation. Besides, all the
above work focuses on the encoder side and cannot help learn the universal
mapping relationship for the decoder.

Given the above, we propose a method to learn the universal representations
and cross-mappings to improve the zero-shot translation performance. Based on
the optimal transport theory, we propose state mover’s distance (SMD) to model
the differences of two state sequences at the token level. To map the
semantic-equivalent sentences from different languages to the same place of
the semantic space, we add an auxiliary loss to minimize the SMD of the source
and target sentences. Besides, we propose an agreement-based training scheme
to learn universal mapping relationships for the translation directions with
the same target language. We mixup the source and target sentences to obtain a
pseudo sentence. Then, the decoder makes predictions separately conditioned on
this pseudo sentence and the corresponding source or target sentences. We try
to improve the prediction consistency by minimizing the KL divergence of the
two output distributions. The experimental results on diverse multilingual
datasets show that our method can bring 2~3 BLEU improvements over the strong
baseline system and consistently outperform other contrast methods. The
analysis proves that our method can better align the semantic space and
improve the prediction consistency.

##  2 Background

In this section, we will give a brief introduction to the Transformer Vaswani
et al. (2017) model and the many-to-many multilingual translation.

###  2.1 The transformer

We denote the input sequence of symbols as $\mathbf{x}=(x_{1},\ldots,x_{nx})$
and the ground-truth sequence as $\mathbf{y}=(y_{1},\ldots,y_{ny})$. The
transformer model is based on the encoder-decoder architecture. The encoder is
composed of $\mathnormal{N}$ identical layers. Each layer has two sublayers.
The first is a multi-head self-attention sublayer, and the second is a fully
connected feed-forward network. Both of the sublayers are followed by a
residual connection operation and a layer normalization operation. The input
sequence $\mathbf{x}$ will be first converted to a sequence of vectors. Then,
this sequence of vectors will be fed into the encoder, and the output of the
$\mathnormal{N}$-th layer will be taken as source state sequences. We denote
it as $\mathbf{H}_{\mathbf{x}}$. The decoder is also composed of
$\mathnormal{N}$ identical layers. In addition to the same kind of two
sublayers in each encoder layer, the cross-attention sublayer is inserted
between them, which performs multi-head attention over the output of the
encoder. We can get the predicted probability of the $k$-th target word
conditioned by the source sentence and the $k-1$ previous target words. The
model is optimized by minimizing a cross-entropy loss of the ground-truth
sequence with teacher forcing:

$\mathcal{L}_{CE}=-\frac{1}{n_{y}}\sum_{k=1}^{n_{y}}\log
p(y_{k}|\mathbf{y}_{<k},\mathbf{x};\theta),$ (1)

where $n_{y}$ is the length of the target sentence and $\theta$ denotes the
model parameters.

###  2.2 Multilingual Translation

We define $L=\\{l_{1},\ldots,l_{M}\\}$ where $L$ is a collection of $M$
languages involved in the training phase. Following Johnson et al. (2017), we
share all the model parameters for all the languages. Following Liu et al.
(2020), we add a particular language id token at the beginning of the source
and target sentences, respectively, to indicate the language.

Figure 1: The training scheme of our method. $\mathbf{x}$ and $\mathbf{y}$
denote a pair of translations; $\mathbf{H_{x}}$ and $\mathbf{H_{y}}$ denote
the corresponding state sequences. $\mathbf{z}$ is the pseudo sentence by
mixuping $\mathbf{x}$ and $\mathbf{y}$. ’Dec’ denotes the decoder and there is
only one decoder in the model. ’stop-grad’ denotes the stop-gradient operation
during back propagation. $\mathcal{L}_{CE}$, $\mathcal{L}_{OT}$, and
$\mathcal{L}_{AT}$ denote the cross entropy loss, optimal transport loss, and
agreement-based training loss.

##  3 Method

The main idea of our method is to help the encoder output universal
representations for all the languages and help the decoder map the semantic-
equivalent representation from different languages to the target language’s
space. We propose two approaches to fulfill this goal. The first is to
directly bridge the gap between the state sequences that carry the same
semantics. The second is to force the decoder to make consistent predictions
based on the semantic-equivalent sentences. Figure 1 shows the overall
training scheme.

###  3.1 Optimal Transport

Earth Mover’s Distance Based on the optimal transport theory Villani (2009);
Peyré et al. (2019), the earth mover’s distance (EMD) measures the minimum
cost to transport the probability mass from one distribution to another
distribution. Assuming that there are two probability distributions $\mu$ and
$\mu^{\prime}$, that are defined as:

$\begin{split}&\mu=\\{(\mathbf{w}_{i},m_{i})\\}_{i=1}^{n},\quad
s.t.\sum_{i}m_{i}=1;\\\
&\mu^{\prime}=\\{(\mathbf{w}^{\prime}_{j},m^{\prime}_{j})\\}_{j=1}^{n^{\prime}},\quad
s.t.\sum_{j}m^{\prime}_{j}=1,\end{split}$ (2)

where each data point $\mathbf{w}_{i}\in\mathbb{R}^{d}$ has a probability mass
$m_{i}$ ($m_{i}>0$). There are $n$ data points in $\mu$. We define a cost
function $c(\mathbf{w}_{i},\mathbf{w}^{\prime}_{j})$ that determines the cost
of per unit between two points $\mathbf{w}_{i}$ and $\mathbf{w}^{\prime}_{i}$.
Given above, the EMD is defined as:

$\begin{split}\mathcal{D}(\mu,\mu^{\prime})&=\min_{\mathbf{T}\geq
0}\sum_{i,j}\mathbf{T}_{ij}c(\mathbf{w}_{i},\mathbf{w^{\prime}}_{j})\\\
s.t.\quad&\sum_{j=1}^{n^{\prime}}\mathbf{T}_{ij}=m_{i},\forall
i\in\\{1,\ldots,n\\},\\\ &\sum_{i=1}^{n}\mathbf{T}_{ij}=m^{\prime}_{j},\forall
j\in\\{1,\ldots,n^{\prime}\\}.\end{split}$ (3)

$\mathbf{T}_{ij}$ denotes the mass transported from $\mu$ to $\mu^{\prime}$.

State Mover’s Distance Following EMD, we define the state mover’s distance
(SMD) to measure the minimum ’travel cost’ between two state sequences. Given
a pair of translations $\mathbf{x}=(x_{1},\ldots,x_{nx})$, and
$\mathbf{y}=(y_{1},\ldots,y_{ny})$, we can get their corresponding state
sequences after feeding them to the encoder, which are denoted as:

$\begin{split}&\mathbf{H}_{\mathbf{x}}=(\mathbf{h}_{1},\ldots,\mathbf{h}_{i},\ldots,\mathbf{h}_{nx}),\\\
&\mathbf{H}_{\mathbf{y}}=(\mathbf{h}^{\prime}_{1},\ldots,\mathbf{h}^{\prime}_{j},\ldots,\mathbf{h}^{\prime}_{ny}),\end{split}$
(4)

where $nx$ and $ny$ denote the sentence length of the source and target
sentences. We can regard $\mathbf{H_{x}}$ as a discrete distribution on the
space $\mathbb{R}^{d}$, where the probability only occurs at each specific
point $\mathbf{h}_{i}$. Next, several previous studies Schakel and Wilson
(2015); Yokoi et al. (2020) have confirmed that the embedding norm is related
to the word importance, and the important words have larger norms. Inspired by
these findings, we also observe that the state vector has similar properties.
The state vectors of essential words, such as content and medium-frequency
words, have larger norms than unimportant ones, such as function words, high-
frequency words. Therefore, we propose to use the normalized vector norm as
the probability mass for each state point:

$m_{i}=\frac{|\mathbf{h}_{i}|}{\sum_{i}|\mathbf{h}_{i}|},m^{\prime}_{j}=\frac{|\mathbf{h}^{\prime}_{j}|}{\sum_{j}|\mathbf{h}^{\prime}_{j}|},$
(5)

where $|\cdot|$ denotes the norm of the vector.

Given above, we can convert the state sequences to distributions:

$\begin{split}&\mu_{\mathbf{x}}^{\mathbf{H}}=\\{(\mathbf{h}_{i},\frac{|\mathbf{h}_{i}|}{\sum_{i}|\mathbf{h}_{i}|})\\}_{i=1}^{nx},\\\
&\mu_{\mathbf{y}}^{\mathbf{H}}=\\{(\mathbf{h}^{\prime}_{j},\frac{|\mathbf{h}^{\prime}_{j}|}{\sum_{j}|\mathbf{h}^{\prime}_{j}|})\\}_{j=1}^{ny}.\end{split}$
(6)

Then, the SMD is formally defined as follows:

$\begin{split}\mathcal{D}&(\mu_{\mathbf{x}}^{\mathbf{H}},\mu_{\mathbf{y}}^{\mathbf{H}})=\min_{\mathbf{T}\geq
0}\sum_{i,j}\mathbf{T}_{ij}c(\mathbf{h}_{i},\mathbf{h^{\prime}}_{j}),\\\
s.t.\quad&\sum_{j=1}^{ny}\mathbf{T}_{ij}=\frac{|\mathbf{h}_{i}|}{\sum_{i}|\mathbf{h}_{i}|},\forall
i\in\\{1,\ldots,nx\\},\\\
&\sum_{i=1}^{nx}\mathbf{T}_{ij}=\frac{|\mathbf{h}^{\prime}_{j}|}{\sum_{j}|\mathbf{h}^{\prime}_{j}|},\forall
j\in\\{1,\ldots,ny\\}.\end{split}$ (7)

As illustrated before, we want decoder to make consistent predictions
conditioned on the equivalent state sequences. Considering that the vector
norm and direction both have impacts on the cross-attention results of
decoder, we use the Euclidean distance as the cost function. We didn’t use the
cosine similarity based metric, because it only considers the impact of vector
direction. The proposed SMD is a fully unsupervised algorithm to align the
contextual representations of the two semantic-equivalent sentences.

Approximation of SMD The exact computation to SMD is a linear programming
problem with typical super $O(n^{3})$ complexity, which will slow down the
training speed greatly. We can obtain a relaxed bound of SMD by removing one
of the two constraints, respectively. Following Kusner et al. (2015), we
remove the second constraints:

$\begin{split}\mathcal{D}^{*}&(\mu_{\mathbf{x}}^{\mathbf{H}},\mu_{\mathbf{y}}^{\mathbf{H}})=\min_{\mathbf{T}\geq
0}\sum_{i,j}\mathbf{T}_{ij}c(\mathbf{h}_{i},\mathbf{h^{\prime}}_{j}),\\\
s.t.\quad&\sum_{j=1}^{ny}\mathbf{T}_{ij}=\frac{|\mathbf{h}_{i}|}{\sum_{i}|\mathbf{h}_{i}|},\forall
i\in\\{1,\ldots,nx\\}.\end{split}$ (8)

The above approximation must yield a lower bound to the exact SMD distance.
The accurate SMD solution that satisfies both of the two constraints must also
satisfy the first constraint. Given the approximation, the optimal solution
for each state vector $\mathbf{h}_{i}$ is to move all its probability mass to
the most similar state vector $\mathbf{h}^{\prime}_{j}$. Therefore, the
approximation also enables the many-to-one alignment relationships during
training. We have also tried some approximation algorithms that can get a more
accurate estimation of SMD, e.g., Sinkhorn algorithmCuturi (2013), IPOT Xie et
al. (2020). However, we have not observed consistent improvements in our
preliminary experiments, and these algorithms also slow down the training
speed significantly.

Objective Function We define a symmetrical loss to minimize the SMD of both
sides:

$\mathcal{L}_{OT}=\frac{1}{2}\left(\mathcal{D}^{*}(\mu_{\mathbf{x}}^{\mathbf{H}},\mu_{\mathbf{y}}^{\mathbf{H}})+\mathcal{D}^{*}(\mu_{\mathbf{y}}^{\mathbf{H}},\mu_{\mathbf{x}}^{\mathbf{H}})\right).$
(9)

###  3.2 Agreement-based Training

Theoretical Analysis In zero-shot translation, the decoder should map the
semantic representations from different languages to the target language
space, even if it has never seen the translation directions during training.
This ability needs the model to make consistent predictions based on the
semantic-equivalent sentences, whatever the input language is. To improve the
prediction consistency of the model, we propose an agreement-based training
method. Because the source sentence $\mathbf{x}$ and target sentence
$\mathbf{y}$ are semantically equivalent, the probability of predicting any
other sentence $\mathbf{z}$ based on them should be always equal
theoretically, which is denoted as:

$p(\mathbf{z}|\mathbf{x})=p(\mathbf{z}|\mathbf{y}).$ (10)

Specifically, the predicted probabilities of the $k$-th target word
conditioned by the first $k-1$ words of $\mathbf{z}$ and the source and target
sentences is equal:

$p(z_{k}|\mathbf{z}_{<k},\mathbf{x};\theta)=p(z_{k}|\mathbf{z}_{<k},\mathbf{y};\theta),$
(11)

where $\theta$ denotes the model parameters. Optimizing Equation 11 can not
only help the encoder produce universal semantic representations but also help
the decoder map different source languages to the particular target language
space indicated by $\mathbf{z}$.

Mixup for $\mathbf{z}$ Although Equation 11 is theoretically attractive, the
choice of sentence $\mathbf{z}$ has a significant influence on the above
optimization. If we use a random sentence as $\mathbf{z}$, which is not
related to $\mathbf{x}$ and $\mathbf{y}$, the prediction makes no sense, and
the model learns helpful nothing. If we use either $\mathbf{x}$ or
$\mathbf{y}$ directly, this will cause information leakage on one side of
Equation 11. As a result, the prediction difficulty between the two sides
differs significantly, and it is hard for one side to catch up with the other
side. Given the above, we need a inter-sentence that is "between" $\mathbf{x}$
and $\mathbf{y}$. Inspired by the success of mixup technique in NLP Zhang et
al. (2020b); Cheng et al. (2021), we generate a pseudo sentence by hard
mixuping $\mathbf{x}$ and $\mathbf{y}$ at token-level. We truncate the longer
sentences of $\mathbf{x}$ and $\mathbf{y}$ to make them equal in length. Since
these two sentences are translation pairs, their sentence lengths are usually
close, truncating will not significantly reduce the length of the longer
sentence and will not enhance the decoder learn shorter outputs. We denote the
truncated sentence as $\mathbf{x}^{\prime}$ and $\mathbf{y}^{\prime}$, and
their length as $n^{\prime}$. Then we can generate $\mathbf{z}$ as:

$\mathbf{z}=\mathbf{g}\odot\mathbf{x}^{\prime}+(1-\mathbf{g})\odot\mathbf{y}^{\prime},$
(12)

where $\mathbf{g}\in\\{0,1\\}^{n^{\prime}}$, $\odot$ denotes the element-wise
product. Each element in $\mathbf{g}$ is sampled from Bernoulli$(\lambda)$,
where the parameter $\lambda$ is sampled from Beta$(\alpha,\beta)$, and
$\alpha$ and $\beta$ are two hyperparameters. The language tag in
$\mathbf{z}$, which determines the translation direction, is either come from
$\mathbf{x}$ or $\mathbf{y}$.

Objective Function Similar to Equation 9, we define another symmetrical loss
based on the KL divergence of the model prediction distributions:

$\begin{split}\mathcal{L}_{AT}=&\frac{1}{2n^{\prime}}\sum_{k=1}^{n^{\prime}}KL\left(p(z_{k}|\mathbf{z}_{<k},\mathbf{H_{x}})||p(z_{k}|\mathbf{z}_{<k},\mathbf{H_{y}})\right)\\\
&+KL\left(p(z_{k}|\mathbf{z}_{<k},\mathbf{H_{y}})||p(z_{k}|\mathbf{z}_{<k},\mathbf{H_{x}})\right).\end{split}$
(13)

We omit the model parameters for convenience.

###  3.3 The Final Loss

The final loss consists of three parts, the cross entropy loss (Equation 1),
the optimal transport loss based on SMD (Equation 9) and the KL divergence
loss for the agreement-based training (Equation 13):

$\mathcal{L}=\mathcal{L}_{CE}+\gamma_{1}|\mathbf{x}|\mathcal{L}_{OT}+\gamma_{2}\mathcal{L}_{AT}$
(14)

where $\gamma_{1}$ and $\gamma_{2}$ are two hyperparameters that control the
contributions of the two regularization loss terms. Since $\mathcal{L}_{OT}$
is calculated on the sentence-level and the other two losses are calculated on
the token-level, we multiply the averaged sequence length $|\mathbf{x}|$ to
$\mathcal{L}_{OT}$. Among these three losses, the first term dominates the
parameter update of the model, and determines the model performance mostly.
The latter two regularization loss terms only slightly modify the directions
of the gradients. Because the first loss term does not depend on
$\mathbf{H_{y}}$, we apply the stop-gradient operation to $\mathbf{H_{y}}$
(Figure 1), which means that the gradients will not pass through
$\mathbf{H_{y}}$ to the encoder.

Dataset | Language Pairs | Size
---|---|---
IWSLT | En$\leftrightarrow${De, It, Nl, Ro} | 1.79M
IWSLT-b | Nl$\leftrightarrow$De$\leftrightarrow$En$\leftrightarrow$It$\leftrightarrow$Ro | 1.79M
PC-6 | En$\leftrightarrow${Kk, Tr, Ro, Cs, Ru} | 7.9M
OPUS-7 | En$\leftrightarrow${De, Fr, Nl, Ru, Zh, Ar} | 11.6M

Table 1:  The statics of our datasets.

##  4 Experiments

###  4.1 Data Preparation

We conduct experiments on the following multilingual datasets: IWSLT17, PC-6,
and OPUS-7. The brief statistics of the training set are in Table 1. We put
more details in the appendix.

IWSLT17 Cettolo et al. (2017) We simulate two scenarios. The first (IWSLT) is
English-pivot, where we only retain the parallel sentences from/to English.
The second (IWSLT-b) has a chain of pivots, where two languages are connected
by a chain of pivot languages. Each translation direction has about 0.22M
sentence pairs. Both of the two scenarios have eight supervised translation
directions and twelve zero-shot translation directions. We use the official
validation and test sets.

PC-6 The PC-6 dataset is extracted from the PC-32 corpus Lin et al. (2020).
The data amount of different language pairs is unbalanced, ranging from 0.12M
to 1.84M. This dataset has ten supervised and twenty zero-shot translation
directions. We use the validation and test sets collected from WMT16~19 for
the supervised directions. The zero-shot validation and test sets are
extracted from the WikiMatrix Schwenk et al. (2021), each containing about
1K~2K sentences pairs.

OPUS-7 The OPUS-7 dataset is extracted from the OPUS-100 corpus Zhang et al.
(2020a). The language pairs come from different language families and have
significant differences. This dataset has twelve supervised translation
directions and thirty zero-shot translation directions. We use the standard
validation and test sets released by Zhang et al. (2020a). We concatenate the
zero-shot test sets with the same target language for convenience.

We use the Stanford word segmenter Tseng et al. (2005); Monroe et al. (2014)
to segment Arabic and Chinese, and the Moses toolkit Koehn et al. (2007) to
tokenize other languages. Besides, integrating operations of 32K is performed
to learn BPE Sennrich et al. (2016).

IWSLT | De-It | De-Nl | De-Ro | It-Ro | It-Nl | Nl-Ro |  Zero Avg. |  Sup. Avg
---|---|---|---|---|---|---|---|---
Model | $\rightarrow$ | $\leftarrow$ | $\rightarrow$ | $\leftarrow$ | $\rightarrow$ | $\leftarrow$ | $\rightarrow$ | $\leftarrow$ | $\rightarrow$ | $\leftarrow$ | $\rightarrow$ | $\leftarrow$
ZS | 15.64 | 15.28 | 18.46 | 18.14 | 14.42 | 14.98 | 17.91 | 20.14 | 18.16 | 18.79 | 15.81 | 16.41 | 17.01 | 30.62
SRA | 16.44 | 16.45 | 18.44 | 19.15 | 15.07 | 15.83 | 18.52 | 21.52 | 19.3 | 19.1 | 16.83 | 17.66 | 17.85 | 30.41
SF | 16.34 | 15.77 | 18.37 | 18.16 | 14.74 | 15.25 | 18.54 | 21.64 | 18.6 | 19.18 | 16.09 | 16.94 | 17.46 | 30.5
CL | 17.37 | 16.58 | 19.69 | 19.5 | 15.51 | 16.25 | 18.91 | 22.58 | 18.78 | 20.02 | 17.27 | 17.91 | 18.36 | 30.39
DisPos | 16.62 | 15.64 | 19.64 | 18.78 | 15.07 | 15.96 | 18.67 | 21.56 | 19.01 | 20.15 | 16.46 | 18.18 | 17.97 | 30.49
DT | 16.82 | 15.81 | 18.74 | 18.64 | 15.12 | 16.32 | 18.70 | 22.13 | 18.92 | 19.29 | 16.21 | 18.22 | 17.91 | 30.51
TGP | 16.77 | 18.51 | 14.58 | 17.12 | 16.84 | 16.88 | 19.42 | 19.25 | 20.01 | 19.04 | 21.67 | 18.43 | 18.21 | 30.66
LMP | 16.87 | 18.44 | 15.05 | 16.66 | 16.20 | 16.12 | 19.04 | 19.05 | 19.35 | 18.68 | 22.17 | 17.97 | 17.96 | 30.52
PivT | 18.31 | 17.9 | 19.99 | 19.33 | 15.54 | 17.45 | 19.77 | 22.97 | 21.43 | 21.44 | 17.57 | 19.82 | 19.29 | -
ZS+OT | 17.35 | 17.08 | 19.77 | 19.05 | 15.66 | 16.17 | 19.71 | 22.32 | 20.18 | 20.57 | 16.87 | 18.09 | 18.56 | 30.42
ZS+AT | 16.37 | 15.84 | 19.11 | 18.41 | 14.85 | 15.59 | 18.37 | 21.09 | 18.77 | 19.4 | 15.86 | 17.46 | 17.59 | 30.55
Ours | 17.53 | 17.03 | 19.94 | 19.67 | 15.61 | 16.57 | 19.23 | 22.42 | 20.05 | 20.23 | 17.05 | 18.64 | 18.66 | 30.52

IWSLT-b | De-It | En-Nl | De-Ro | En-Ro | It-Nl | Nl-Ro |  Zero Avg. |  Sup. Avg.
---|---|---|---|---|---|---|---|---
Model | $\rightarrow$ | $\leftarrow$ | $\rightarrow$ | $\leftarrow$ | $\rightarrow$ | $\leftarrow$ | $\rightarrow$ | $\leftarrow$ | $\rightarrow$ | $\leftarrow$ | $\rightarrow$ | $\leftarrow$
ZS | 17.79 | 17.3 | 25.48 | 30.99 | 15.65 | 17.28 | 21.7 | 30.14 | 20.79 | 21.02 | 15.74 | 17.28 | 20.93 | 30.46
SRA | 18.09 | 18.05 | 26.52 | 31.15 | 15.8 | 17.43 | 22.24 | 30.19 | 20.35 | 20.65 | 16.39 | 17.83 | 21.22 | 30.29
SF | 18.25 | 17.61 | 26 | 31.28 | 16.06 | 17.51 | 22.43 | 30.51 | 20.67 | 20.82 | 16.2 | 17.24 | 21.21 | 30.35
CL | 18.49 | 18.29 | 26.88 | 31.46 | 15.71 | 17.23 | 23.01 | 30.78 | 20.62 | 20.8 | 16.58 | 18.17 | 21.5 | 30.28
DisPos | 17.98 | 17.35 | 26.26 | 31.13 | 15.75 | 18.07 | 22.95 | 30.45 | 21.02 | 20.58 | 16.38 | 18.28 | 21.35 | 29.89
TGP | 18.22 | 18.69 | 26.62 | 30.96 | 15.57 | 17.26 | 23.21 | 30.22 | 20.62 | 20.38 | 16.58 | 17.65 | 21.33 | 30.33
LMP | 18.36 | 18.83 | 27.2 | 30.5 | 16.05 | 17.05 | 23.99 | 29.38 | 20.57 | 19.83 | 16.72 | 17.56 | 21.33 | 30.37
PivT | 18.38 | 19.08 | 27.3 | 28.02 | 15 | 16.35 | 23.72 | 28.72 | 20.34 | 19.45 | 15.7 | 16.8 | 20.74 | -
ZS+OT | 18.09 | 18.06 | 26.6 | 31.69 | 15.76 | 17.19 | 23.46 | 30.99 | 20.31 | 20.86 | 16.92 | 18.05 | 21.49 | 30.37
ZS+AT | 18.23 | 17.51 | 26.24 | 31.12 | 16.19 | 17.5 | 22.64 | 30.33 | 20.72 | 20.59 | 16.29 | 17.64 | 21.25 | 30.39
Ours | 18.41 | 18.05 | 27.39 | 31.36 | 16.15 | 17.48 | 23.22 | 30.9 | 20.68 | 20.82 | 17.03 | 18.29 | 21.64 | 30.33

PC-6 | x$\rightarrow$Kk | x$\rightarrow$Tr | x$\rightarrow$Ro | x$\rightarrow$Cs | x$\rightarrow$Ru |  | Zero
---
Avg.
| Sup.
---
Avg.
OPUS-7 | x$\rightarrow$De | x$\rightarrow$Fr | x$\rightarrow$Nl | x$\rightarrow$Ru | x$\rightarrow$Zh | x$\rightarrow$Ar |  | Zero
---
Avg.
| Sup.
---
Avg.
ZS | 5.87 | 9.29 | 14.23 | 13.55 | 16.83 | 11.95 | 21.73 | ZS | 13.58 | 22.63 | 17.96 | 15.42 | 29.78 | 21.58 | 20.15 | 34.2
SRA | 5.90 | 10.09 | 17.36 | 15.85 | 19.31 | 13.68 | 21.66 | SRA | 17.04 | 26.12 | 19.29 | 20.9 | 31.99 | 22.01 | 22.89 | 33.97
SF | 4.76 | 9.95 | 17.77 | 15.83 | 20.10 | 13.68 | 21.64 | SF | 15.99 | 25.2 | 18.2 | 20.85 | 31.65 | 21.5 | 22.23 | 33.99
CL | 6.07 | 10.72 | 17.96 | 16.14 | 21.58 | 14.49 | 21.54 | CL | 17.41 | 26.19 | 19.66 | 21.1 | 32.52 | 21.69 | 23.09 | 33.86
DisPos | 6.60 | 10.14 | 15.47 | 15.89 | 18.70 | 12.51 | 21.45 | DisPos | 15.95 | 25.36 | 18.86 | 19.75 | 31.34 | 22.08 | 22.22 | 34.12
DT | 6.92 | 10.49 | 17.37 | 15.63 | 21.74 | 14.43 | 21.61 | DT | 14.97 | 23.95 | 18.10 | 18.91 | 29.65 | 20.68 | 21.04 | 34.03
TGP | 7.33 | 10.98 | 20.63 | 13.81 | 21.21 | 14.79 | 21.58 | TGP | 16.86 | 25.65 | 18.99 | 20.83 | 32.47 | 21.47 | 22.71 | 34.18
LMP | 4.45 | 8.50 | 16.42 | 15.25 | 19.28 | 12.78 | 21.71 | LMP | 14.65 | 23.94 | 18.36 | 19.02 | 30.58 | 20.99 | 21.26 | 34.07
PivT | 4.29 | 10.59 | 19.23 | 17.22 | 21.65 | 14.58 | - | PivT | 17.97 | 28.37 | 19.76 | 22.97 | 34.08 | 23.74 | 24.48 | -
ZS+OT | 6.22 | 11.08 | 18.74 | 16.86 | 22.61 | 15.1 | 21.6 | ZS+OT | 17.56 | 26.70 | 19.54 | 21.88 | 32.42 | 22.48 | 23.43 | 34.02
ZS+AT | 6.04 | 10.74 | 17.92 | 15.69 | 20.63 | 14.2 | 21.72 | ZS+AT | 16.78 | 25.89 | 18.93 | 21.21 | 32.02 | 21.72 | 22.75 | 34.1
Ours | 6.58 | 11.44 | 18.55 | 17.11 | 22.77 | 15.29 | 21.68 | Ours | 17.60 | 26.74 | 19.68 | 21.91 | 32.63 | 23.24 | 23.63 | 34.17

Table 2: The overall BLEU scores on the test sets. "Zero Avg." and "Sup. Avg."
denote the average BLEU scores on the zero-shot and supervised directions. The
"x" in the third table denotes all languages except for the target language.
The highest scores are marked in bold for all models except for the "PivT"
system in each column.

###  4.2 Systems

We use the open-source toolkit called Fairseq-py Ott et al. (2019) as our
Transformer system. We implement the following systems:

• Zero-Shot (ZS) The baseline system which is trained only with the cross-
entropy loss (Equation 1). Then the model is tested directly on the zero-shot
test sets.

• Pivot Translation (PivT) Cheng et al. (2017) The same translation model as
ZS. The model first translates the source language to the pivot language and
then generates the target language.

•Sentence Representation Alignment (SRA) Arivazhagan et al. (2019) This
methods adds an regularization loss to minimize the discrepancy of the source
and target sentence representations.

$\mathcal{L}=\mathcal{L}_{CE}+\gamma Dis(Enc(s),Enc(t)),$ (15)

where ’Dis’ denotes the distance function and ’Enc($\cdot$)’ denotes the
sentence representations. We use the averaged sentence representation and
Euclidean distance function because we find they work better. We vary the
hyperparameter $\gamma$ from $0.1$ to $1$ to tune the performance.

• Softmax Forcing (SF) Pham et al. (2019) This method enable the decoder to
generate the target sentence from itself by adding an extra loss:

$\mathcal{L}_{SF}=\gamma\sum_{k}^{n_{y}}KL(p(y_{k}|\mathbf{y}_{<k},\mathbf{x})||p(y_{k}|\mathbf{y}_{<k},\mathbf{y}))$
(16)

The $\gamma$ is tuned as in the ’SRA’ system.

• Contrastive Learning (CL) Pan et al. (2021) This method adds an extra
contrastive loss to minimize the representation gap of similar sentences and
maximize that of irrelevant sentences:

$\mathcal{L}_{CL}=-\gamma\log\frac{e^{sim^{+}(\mathcal{R}(s),\mathcal{R}(t))/\tau}}{\sum_{w}e^{sim^{-}(\mathcal{R}(s),\mathcal{R}(w))/\tau}},$
(17)

where $+$ and $-$ denote positive and negative sample pairs,
$\mathcal{R}(\cdot)$ denotes the averaged state representations. We set $\tau$
as 0.1 as suggested in the paper and tune $\gamma$ as in the ’SRA’ system.

• Disentangling Positional Information (DisPos) Liu et al. (2021) This method
removes the residual connections in a middle layer of the encoder to get the
language-agnostic representations.

• Denosing Training (DT) Wang et al. (2021) This method introduces a denoising
auto-encoder objective during training.

• Target Gradient Projection (TGP) Yang et al. (2021b) This method projects
the training gradient to not conflict with the oracle gradient of a small
amount of direct data.

• Language Model Pre-training (LMP) Gu et al. (2019) This method strengthens
the decoder language model prior to machine translation training.

The following systems are implemented based on our method:

• ZS+OT We only add the optimal transport loss (Equation 9) during training.
We vary the hyperparameter $\gamma_{1}$ from $0.1$ to $1$, and we find that it
can constantly improve the performance whatever $\gamma_{1}$ is. The detailed
results and the final setting about the hyperparameter are put in the
appendix.

• ZS+AT We only add the agreement-based training loss (Equation 13) during
training. The $\alpha$ and $\beta$ in the beta distribution are set as $6$ and
$3$, respectively. We vary the hyperparameter $\gamma_{2}$ from ${10}^{-4}$ to
$0.1$.

• ZS+OT+AT (Ours) The model is trained with the complete objective function
(Equation 14). The hyperparameters are set according to the searched results
of the above two systems and are listed in the appendix.

Implementation Details All the systems are implemented as the base model
configuration in Vaswani et al. (2017) strictly. We employ the Adam optimizer
with $\beta_{1}=0.9$ and $\beta_{2}=0.98$. We use the inverse square root
learning scheduler and set the $warmup\\_steps=4000$ and $lr=0.0007$. We set
dropout as 0.3 for the IWSLT datasets and 0.1 for the for the PC-6 and OPUS-7
datasets. All the systems are trained on 4 RTX3090 GPUs with the update
frequency 2. The max token is 4096 for each GPU. For the IWSLT data sets, we
first pretrain the model with the cross-entropy loss (Equation 1) for 20K
steps and then continually train the model combined with the proposed loss
terms for 80K steps. For the PC-6 and OPUS-7 datasets, the pre-training steps
and continual-training steps are both 100k.

(a) ZS

(b) SRA

(c) CL

(d) Ours

Figure 2: The visualization of sentence representation after dimension
reduction on the IWSLT three-way-parallel test sets. The blue line denotes
Germany, the orange line denotes Italian, and the green line denotes Dutch.

###  4.3 Main Results

All the results (including the intermediate results of the ’PivT’ system) are
generated with beam size = $5$ and length penalty $\alpha=0.6$. The
translation quality is evaluated using the case-sensitive BLEU Papineni et al.
(2002) with the SacreBLEU tool Post (2018). We report the tokenized BLEU for
Arabic, char-based BLEU for Chinese, and detokenized BLEU for other
languages111BLEU+case.mixed+numrefs.1+smooth.exp+
tok.{13a,none,zh}+version.1.5.1. The main results are shown in Table 2. We
report the averaged BLEU with the same target language on the PC-6 and OPUS-7
dataset for display convenience, and the detailed results are in the appendix.
The ’Ours’ system significantly improves over the ’ZS’ baseline system and
outperforms other zero-shot-based systems on all datasets. The two proposed
methods, OT and AT, can both help the model learn universal and cross mappings
, so they both can improve the model performance independently. These two
methods also complement each other and can further improve the performance
when combined together. Besides, ’Ours’ system can even exceed the ’PivT’
system when the distant language pairs in the IWSLT-b or the low-resource
language pairs in the PC-6 bring severe error accumulation problems. We also
compare the training speed and put the results in the appendix.

IWSLT | x-De | x-It | x-Nl | Avg.
---|---|---|---|---
ZS | 21.5 | 20.79 | 19.99 | 20.76
SRA | 21.79 | 21.92 | 20.67 | 21.46
CL | 23.47 | 21.52 | 21.09 | 22.03
Ours | 23.6 | 23.33 | 21.48 | 22.80
Table 3: The pair-wise BLEU on the IWSLT three-way-parallel test sets.

##  5 Analysis

In this section, we try to understand how our method improves the zero-shot
translation.

###  5.1 Sentence Representation Visualization

To verify whether our method can better align different languages’ semantic
space, we visualize each model’s encoder output with the IWSLT test sets. We
first select three languages: Germany, Italian, and Dutch. Then we filter out
the overlapped sentences of the three languages from the corresponding test
sets and create a new three-way-parallel test set. Next, we feed all the
sentences to the encoder of each model and average the encoder output to get
the sentence representation. Last, we apply dimension reduction to the
representation with t-SNE Van der Maaten and Hinton (2008). The visualization
result in Figure 2(a) shows that the ’ZS’ system cannot align the three
languages well, which partly confirms our assumption that the conventional
MNMT cannot learn universal representations for all languages. As a contrast,
the ’Ours’ system (d) can draw the representation closer and achieve
comparative results as the ’CL’ system (c) without large amounts of negative
instances to contrast. The visualization results confirm that our method can
learn good universal representation for different languages.

###  5.2 Inspecting Prediction Consistency

To verify whether our method can help map the semantic representation from
different languages to the same space of the target language, we inspect the
prediction consistency of the models when the model is fed with synonymous
sentences from different languages. Precisely, we measure the pair-wise BLEU
on the above IWSLT three-way-parallel test set. We choose one language as the
target language, e.g., German, and then translate the other two languages,
e.g., Italian and Dutch, to the target language. After obtaining these two
translation files, we use one file as the reference, the other as the
translation to calculate the BLEU, and then we swap the role of these two
files to calculate the BLEU again. We average the BLEU scores to get the pair-
wise BLEU, and the results in Table 3 show that our method can achieve higher
results, which proves that our method can improve the prediction consistency.

System | IWSLT | IWSLT-b | PC-6 | OPUS-7
---|---|---|---|---
ZS | 93.2% | 93.72% | 87.93% | 74.1%
SRA | 93.9% | 93.88% | 91.54% | 85.83%
CL | 93.97% | 93.96% | 91.76% | 86.23%
Ours | 94.03% | 94.06% | 93.24% | 86.75%

Table 4: The target language prediction accuracy.

###  5.3 Inspecting Spurious Correlations

The zero-shot translation usually suffers from capturing spurious correlations
in the supervised directions, which means that the model overfits the mapping
relationship from the input language to the output language observed in the
training set Gu et al. (2019). This problem often causes the off-target
prediction phenomenon where the model generates translation in the wrong
target languages. To check whether our method can alleviate this phenomenon,
we use the $\mathrm{Langdetect}$ 222https://github.com/Mimino666/langdetect
toolkit to identify the target language and calculate the prediction accuracy
as $1-n_{off-target}/n_{total}$. We also compare our method with the ’SRA’ and
’CL’ methods. The results are shown in Table 4. The ’ZS’ baseline system can
achieve high prediction accuracy on the IWSLT dataset, but the performance
begin to decline as the amount of data becomes unbalanced and the languages
become more unrelated. On all the datasets, our method achieves higher
prediction accuracy and outperforms all the contrast methods. We can conclude
from the results that our method can reduce the spurious correlation captured
by the model.

##  6 Related Wrok

Recent work on zero-shot translation can be divided into two categories. The
first category helps the encoder produce language-agnostic features via extra
regularization loss or training tasks. Pham et al. (2019) propose to compress
the output of the encoder into a consistent number of states. Arivazhagan et
al. (2019) maximize the cosine similarities between the averaged
representations of the source and target sentences. Pan et al. (2021) and Wei
et al. (2021) propose contrastive learning schemes to minimize the averaged
sentence representation gap of similar sentences and maximize that of
irrelevant sentences. Compared with their methods, we directly bridge the gap
between two state sequences, which alleviates the mismatch problem of sentence
representation. Ji et al. (2020) leverage explicit alignment information by
external aligner tool or additional attention layer to obtain the aligned
words for masking, and then they let the model predict the masked words based
on the surrounding words. Compared with this work, our method is to align the
whole state sequences of different languages, not just for single words. Liu
et al. (2021) remove the residual connections in a middle layer of the encoder
to release the positional correspondence to input tokens. Wang et al. (2021)
introduce a denoising auto-encoder objective to improve the translation
accuracy. Yang et al. (2021b) leverage an auxiliary target language prediction
task to retain information about the target languages. Z. et al. (2022) uses
optimal transport theory to improve the low-resource neural machine
translation. Compared with these work, our method introduces explicit
constraints to the semantic representations.

The second category extends the training data by generating pseudo sentence
pairs or utilizing monolingual data. Gu et al. (2019) apply decoder pre-
training and back-translation to improve the zero-shot ability. Al-Shedivat
and Parikh (2019) first translate the source and target languages to a third
language and then make consistent predictions based on this pseudo sentence.
Zhang et al. (2020a) propose random online back translation to enforce the
translation of unseen training language pairs. Chen et al. (2021) fuse the
pretrained multilingual model to the NMT model. Compared with these works, our
method does not need additional data or additional time to generate pseudo
corpus. If necessary, our method can also be combined with these works to
further improve the zero-shot performance of the model. Yang et al. (2021a)
propose to substitute some fragments of the source language with their
counterpart translations to get the code-switch sentences. Compared to this
work, our agreement-based method mixups the translation pairs to generate the
pseudo sentence as the decoder input and then help the model to make
consistent predictions.

##  7 Conclusion

In this work, we focus on improving the zero-shot ability of multilingual
neural machine translation. To reduce the discrepancy of the encoder output,
we propose the state mover’s distance based on the optimal transport theory
and directly minimize the distance during training. We also propose an
agreement-based training method to help the decoder make consistent
predictions based on the semantic-equivalent sentences. The experimental
results show that our method can get consistent improvements on diverse
multilingual datasets. Further analysis shows that our method can better align
the semantic space, improve the prediction consistency, and reduce the
spurious correlations.

## Limitations

Although our method can improve the performance of the zero-shot translation
directions, it has limited benefits for the supervised translation
performance. On the one hand, the vanilla MNMT model has already been able to
learn a lot of language shared knowledge. On the other hand, the language-
specific knowledge learned by the model can also help the model achieve good
translation performance in the supervised translation directions. Therefore,
our method is limited to improving the supervised translation performance.
Besides, some reviewers pointed out that our method degraded the supervised
translation performance according to the results of the main experiments. This
is because we select the checkpoints based on the performance of the zero-shot
valid sets, which may cause a slight decline in the performance of the
supervised directions. If we select checkpoints based on the the supervised
valid sets, our method can improve the zero-shot performance without degrading
the BLEU of the supervised directions.

## Acknowledgements

We thank all the anonymous reviewers for their insightful and valuable
comments.

## References

  * Al-Shedivat and Parikh (2019) Maruan Al-Shedivat and Ankur P. Parikh. 2019.  Consistency by agreement in zero-shot neural machine translation.  In _Proceedings of the 2019 Conference of the North American Chapter of the Association for Computational Linguistics: Human Language Technologies, NAACL-HLT 2019, Minneapolis, MN, USA, June 2-7, 2019, Volume 1 (Long and Short Papers)_ , pages 1184–1197.
  * Arivazhagan et al. (2019) Naveen Arivazhagan, Ankur Bapna, Orhan Firat, Roee Aharoni, Melvin Johnson, and Wolfgang Macherey. 2019.  The missing ingredient in zero-shot neural machine translation.  _CoRR_ , abs/1903.07091.
  * Cettolo et al. (2017) Mauro Cettolo, Marcello Federico, Luisa Bentivogli, Niehues Jan, Stüker Sebastian, Sudoh Katsuitho, Yoshino Koichiro, and Federmann Christian. 2017.  Overview of the iwslt 2017 evaluation campaign.  In _International Workshop on Spoken Language Translation_ , pages 2–14.
  * Chen et al. (2021) Guanhua Chen, Shuming Ma, Yun Chen, Li Dong, Dongdong Zhang, Jia Pan, Wenping Wang, and Furu Wei. 2021.  Zero-shot cross-lingual transfer of neural machine translation with multilingual pretrained encoders.  In _EMNLP 2021_.
  * Cheng et al. (2021) Yong Cheng, Wei Wang, Lu Jiang, and Wolfgang Macherey. 2021.  Self-supervised and supervised joint training for resource-rich machine translation.  In _Proceedings of the 38th International Conference on Machine Learning, ICML 2021, 18-24 July 2021, Virtual Event_ , pages 1825–1835.
  * Cheng et al. (2017) Yong Cheng, Qian Yang, Yang Liu, Maosong Sun, and Wei Xu. 2017.  Joint training for pivot-based neural machine translation.  In _Proceedings of the Twenty-Sixth International Joint Conference on Artificial Intelligence, IJCAI 2017, Melbourne, Australia, August 19-25, 2017_ , pages 3974–3980.
  * Cuturi (2013) Marco Cuturi. 2013.  Sinkhorn distances: Lightspeed computation of optimal transport.  _Advances in neural information processing systems_ , 26:2292–2300.
  * Fan et al. (2020) 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, Edouard Grave, Michael Auli, and Armand Joulin. 2020.  Beyond english-centric multilingual machine translation.  _CoRR_ , abs/2010.11125.
  * Firat et al. (2016) Orhan Firat, Kyunghyun Cho, and Yoshua Bengio. 2016.  Multi-way, multilingual neural machine translation with a shared attention mechanism.  In _NAACL HLT 2016, The 2016 Conference of the North American Chapter of the Association for Computational Linguistics: Human Language Technologies, San Diego California, USA, June 12-17, 2016_ , pages 866–875.
  * Gu et al. (2018) Jiatao Gu, Hany Hassan, Jacob Devlin, and Victor O. K. Li. 2018.  Universal neural machine translation for extremely low resource languages.  In _Proceedings of the 2018 Conference of the North American Chapter of the Association for Computational Linguistics: Human Language Technologies, NAACL-HLT 2018, New Orleans, Louisiana, USA, June 1-6, 2018, Volume 1 (Long Papers)_ , pages 344–354.
  * Gu et al. (2019) Jiatao Gu, Yong Wang, Kyunghyun Cho, and Victor O. K. Li. 2019.  Improved zero-shot neural machine translation via ignoring spurious correlations.  In _Proceedings of the 57th Conference of the Association for Computational Linguistics, ACL 2019, Florence, Italy, July 28- August 2, 2019, Volume 1: Long Papers_ , pages 1258–1268.
  * Ha et al. (2016) Thanh-Le Ha, Jan Niehues, and Alexander H. Waibel. 2016.  Toward multilingual neural machine translation with universal encoder and decoder.  _CoRR_ , abs/1611.04798.
  * Ji et al. (2020) Baijun Ji, Zhirui Zhang, Xiangyu Duan, Min Zhang, Boxing Chen, and Weihua Luo. 2020\.  Cross-lingual pre-training based transfer for zero-shot neural machine translation.  In _AAAI 2020, New York, NY, USA, February 7-12, 2020_ , pages 115–122.
  * Johnson et al. (2017) Melvin Johnson, Mike Schuster, Quoc V. Le, Maxim Krikun, Yonghui Wu, Zhifeng Chen, Nikhil Thorat, Fernanda B. Viégas, Martin Wattenberg, Greg Corrado, Macduff Hughes, and Jeffrey Dean. 2017.  Google’s multilingual neural machine translation system: Enabling zero-shot translation.  _Trans. Assoc. Comput. Linguistics_ , 5:339–351.
  * Koehn et al. (2007) Philipp Koehn, Hieu Hoang, Alexandra Birch, Chris Callison-Burch, Marcello Federico, Nicola Bertoldi, Brooke Cowan, Wade Shen, Christine Moran, Richard Zens, Chris Dyer, Ondrej Bojar, Alexandra Constantin, and Evan Herbst. 2007.  Moses: Open source toolkit for statistical machine translation.  In _ACL 2007, Proceedings of the 45th Annual Meeting of the Association for Computational Linguistics, June 23-30, 2007, Prague, Czech Republic_.
  * Kusner et al. (2015) Matt Kusner, Yu Sun, Nicholas Kolkin, and Kilian Weinberger. 2015.  From word embeddings to document distances.  In _International conference on machine learning_ , pages 957–966. PMLR.
  * Lin et al. (2020) Zehui Lin, Xiao Pan, Mingxuan Wang, Xipeng Qiu, Jiangtao Feng, Hao Zhou, and Lei Li. 2020.  Pre-training multilingual neural machine translation by leveraging alignment information.  In _Proceedings of the 2020 Conference on Empirical Methods in Natural Language Processing, EMNLP 2020, Online, November 16-20, 2020_ , pages 2649–2663.
  * Liu et al. (2021) Danni Liu, Jan Niehues, James Cross, Francisco Guzmán, and Xian Li. 2021.  Improving zero-shot translation by disentangling positional information.  In _Proceedings of the 59th Annual Meeting of the Association for Computational Linguistics and the 11th International Joint Conference on Natural Language Processing, ACL/IJCNLP 2021, (Volume 1: Long Papers), Virtual Event, August 1-6, 2021_ , pages 1259–1273.
  * 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.  _Trans. Assoc. Comput. Linguistics_ , 8:726–742.
  * Monroe et al. (2014) Will Monroe, Spence Green, and Christopher D. Manning. 2014.  Word segmentation of informal arabic with domain adaptation.  In _Proceedings of the 52nd Annual Meeting of the Association for Computational Linguistics, ACL 2014, June 22-27, 2014, Baltimore, MD, USA, Volume 2: Short Papers_ , pages 206–211.
  * Ott et al. (2019) Myle Ott, Sergey Edunov, Alexei Baevski, Angela Fan, Sam Gross, Nathan Ng, David Grangier, and Michael Auli. 2019.  fairseq: A fast, extensible toolkit for sequence modeling.  In _Proceedings of the 2019 Conference of the North American Chapter of the Association for Computational Linguistics: Human Language Technologies, NAACL-HLT 2019, Minneapolis, MN, USA, June 2-7, 2019, Demonstrations_ , pages 48–53.
  * Pan et al. (2021) Xiao Pan, Mingxuan Wang, Liwei Wu, and Lei Li. 2021.  Contrastive learning for many-to-many multilingual 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, ACL/IJCNLP 2021, (Volume 1: Long Papers), Virtual Event, August 1-6, 2021_ , pages 244–258.
  * Papineni et al. (2002) Kishore Papineni, Salim Roukos, Todd Ward, and Wei-Jing Zhu. 2002.  Bleu: a method for automatic evaluation of machine translation.  In _Proceedings of the 40th Annual Meeting of the Association for Computational Linguistics, July 6-12, 2002, Philadelphia, PA, USA_ , pages 311–318.
  * Peyré et al. (2019) Gabriel Peyré, Marco Cuturi, et al. 2019.  Computational optimal transport: With applications to data science.  _Foundations and Trends® in Machine Learning_ , 11(5-6):355–607.
  * Pham et al. (2019) Ngoc-Quan Pham, Jan Niehues, Thanh-Le Ha, and Alexander H. Waibel. 2019.  Improving zero-shot translation with language-independent constraints.  In _Proceedings of the Fourth Conference on Machine Translation, WMT 2019, Florence, Italy, August 1-2, 2019 - Volume 1: Research Papers_ , pages 13–23.
  * 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, Belgium, Brussels. Association for Computational Linguistics.
  * Schakel and Wilson (2015) Adriaan M. J. Schakel and Benjamin J. Wilson. 2015.  Measuring word significance using distributed representations of words.  _CoRR_ , abs/1508.02297.
  * Schwenk et al. (2021) Holger Schwenk, Vishrav Chaudhary, Shuo Sun, Hongyu Gong, and Francisco Guzmán. 2021.  Wikimatrix: Mining 135m parallel sentences in 1620 language pairs from wikipedia.  In _Proceedings of the 16th Conference of the European Chapter of the Association for Computational Linguistics: Main Volume, EACL 2021, Online, April 19 - 23, 2021_ , pages 1351–1361.
  * Sennrich et al. (2016) Rico Sennrich, Barry Haddow, and Alexandra Birch. 2016.  Neural machine translation of rare words with subword units.  In _Proceedings of the 54th Annual Meeting of the Association for Computational Linguistics, ACL 2016, August 7-12, 2016, Berlin, Germany, Volume 1: Long Papers_.
  * Tseng et al. (2005) Huihsin Tseng, Pi-Chuan Chang, Galen Andrew, Daniel Jurafsky, and Christopher D. Manning. 2005.  A conditional random field word segmenter for sighan bakeoff 2005.  In _Proceedings of the Fourth SIGHAN Workshop on Chinese Language Processing, SIGHAN@IJCNLP 2005, Jeju Island, Korea, 14-15, 2005_.
  * Van der Maaten and Hinton (2008) Laurens Van der Maaten and Geoffrey Hinton. 2008.  Visualizing data using t-sne.  _Journal of machine learning research_ , 9(11).
  * 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_ , pages 5998–6008.
  * Villani (2009) Cédric Villani. 2009.  _Optimal transport: old and new_ , volume 338.  Springer.
  * Wang et al. (2021) Weizhi Wang, Zhirui Zhang, Yichao Du, Boxing Chen, Jun Xie, and Weihua Luo. 2021\.  Rethinking zero-shot neural machine translation: From a perspective of latent variables.  In _EMNLP 2021, Findings_.
  * Wei et al. (2021) Xiangpeng Wei, Rongxiang Weng, Yue Hu, Luxi Xing, Heng Yu, and Weihua Luo. 2021\.  On learning universal representations across languages.  In _9th International Conference on Learning Representations, ICLR 2021, Virtual Event, Austria, May 3-7, 2021_.
  * Xie et al. (2020) Yujia Xie, Xiangfeng Wang, Ruijia Wang, and Hongyuan Zha. 2020.  A fast proximal point method for computing exact wasserstein distance.  In _Uncertainty in Artificial Intelligence_ , pages 433–453. PMLR.
  * Yang et al. (2021a) Jian Yang, Yuwei Yin, Shuming Ma, Haoyang Huang, Dongdong Zhang, Zhoujun Li, and Furu Wei. 2021a.  Multilingual agreement for multilingual neural machine translation.  In _ACL/IJCNLP 2021, (Volume 2: Short Papers), Virtual Event, August 1-6, 2021_ , pages 233–239.
  * Yang et al. (2021b) Yilin Yang, Akiko Eriguchi, Alexandre Muzio, Prasad Tadepalli, Stefan Lee, and Hany Hassan. 2021b.  Improving multilingual translation by representation and gradient regularization.  In _EMNLP 2021, Long Paper_.
  * Yokoi et al. (2020) Sho Yokoi, Ryo Takahashi, Reina Akama, Jun Suzuki, and Kentaro Inui. 2020.  Word rotator’s distance.  In _Proceedings of the 2020 Conference on Empirical Methods in Natural Language Processing, EMNLP 2020, Online, November 16-20, 2020_ , pages 2944–2960.
  * Z. et al. (2022) Yang Z., Fang Q., and Y. Feng. 2022.  Low-resource neural machine translation with cross-modal alignment.  In _EMNLP 2022 Main Conference Long Paper_.
  * Zhang et al. (2020a) Biao Zhang, Philip Williams, Ivan Titov, and Rico Sennrich. 2020a.  Improving massively multilingual neural machine translation and zero-shot translation.  In _Proceedings of the 58th Annual Meeting of the Association for Computational Linguistics, ACL 2020, Online, July 5-10, 2020_ , pages 1628–1639.
  * Zhang et al. (2020b) Rongzhi Zhang, Yue Yu, and Chao Zhang. 2020b.  Seqmix: Augmenting active sequence labeling via sequence mixup.  In _Proceedings of the 2020 Conference on Empirical Methods in Natural Language Processing, EMNLP 2020, Online, November 16-20, 2020_ , pages 8566–8579.

##  Appendix A Appendix

PC-6 | Cs-Kk |  | Kk-Ru |  | Ro-Ru |  | Tr-Ro |  | Cs-Ro |  | Cs-Ru |
---|---|---|---|---|---|---|---|---|---|---|---|---
$\rightarrow$ | $\leftarrow$ | $\rightarrow$ | $\leftarrow$ | $\rightarrow$ | $\leftarrow$ | $\rightarrow$ | $\leftarrow$ | $\rightarrow$ | $\leftarrow$ | $\rightarrow$ | $\leftarrow$
PivT | 1.77 | 2.55 | 11.37 | 10.51 | 32.86 | 28.1 | 20.03 | 14.47 | 25.47 | 25.7 | 27.05 | 24.26
ZS | 2.07 | 2.69 | 15.61 | 15.7 | 20.65 | 20.6 | 13.44 | 11.69 | 19.82 | 18.81 | 20.19 | 20.26
SRA | 2.15 | 2.5 | 17.03 | 16.86 | 25.37 | 25.66 | 17.35 | 14.6 | 23.62 | 23.91 | 22.68 | 21.6
CL | 1.99 | 2.68 | 16.48 | 16.49 | 29.28 | 26.8 | 17.82 | 15.66 | 23.87 | 23.42 | 27.05 | 24.29
DisPos | 2.24 | 2.74 | 17.14 | 17.95 | 21.87 | 23.47 | 14.73 | 13.52 | 20.42 | 19.96 | 27.18 | 25.7
DT | 2.2 | 2.87 | 19.23 | 18.88 | 28.05 | 25.88 | 17.82 | 14.41 | 22.29 | 22.3 | 26.29 | 23.98
TLP | 2.01 | 2.82 | 14.59 | 13.01 | 28.41 | 25.88 | 18.53 | 13.25 | 23.11 | 22.54 | 25.24 | 22.74
ZS+OT | 2.16 | 3.02 | 18.12 | 16.35 | 30.71 | 27.84 | 19.18 | 15.63 | 24.44 | 24.17 | 27.18 | 25.71
ZS+AT | 2.06 | 2.82 | 15.8 | 16.54 | 28.01 | 26.37 | 19.25 | 15.59 | 22.63 | 22.55 | 24.6 | 23.27
Ours | 2.2 | 3.08 | 18.3 | 17.91 | 30.59 | 27.73 | 19.66 | 16.16 | 23.58 | 24.49 | 27.22 | 25.66

PC-6 | Cs-Tr |  | Kk-Ro |  | Kk-Tr |  | Ru-Tr |  | Zero
---|---|---|---|---|---|---|---|---|---
$\rightarrow$ | $\leftarrow$ | $\rightarrow$ | $\leftarrow$ | $\rightarrow$ | $\leftarrow$ | $\rightarrow$ | $\leftarrow$ | Avg.
PivT | 13.37 | 16.36 | 3.3 | 2.75 | 2.91 | 2.11 | 11.59 | 15.31 | 14.58
ZS | 11 | 12.44 | 3.06 | 3.26 | 3.81 | 2.44 | 10.66 | 10.88 | 11.95
SRA | 12.32 | 15.37 | 2.82 | 2.72 | 2.7 | 1.87 | 10.72 | 12.17 | 13.68
CL | 12.02 | 14.16 | 3.33 | 3.34 | 3.49 | 2.44 | 11.72 | 13.52 | 14.49
DisPos | 12.8 | 15.26 | 3.25 | 3.17 | 3.9 | 3.09 | 10.22 | 8.56 | 12.51
DT | 11.62 | 13.38 | 3.49 | 3.37 | 3.96 | 3.24 | 11.97 | 13.38 | 14.43
TLP | 11.96 | 13.98 | 3.33 | 2.98 | 3.65 | 2.98 | 12.02 | 13.5 | 13.83
ZS+OT | 12.83 | 14.54 | 3.5 | 3.11 | 3.94 | 3.26 | 11.92 | 14.44 | 15.1
ZS+AT | 11.99 | 14.11 | 3.41 | 3.03 | 3.46 | 2.54 | 11.9 | 14.11 | 14.2
Ours | 12.85 | 15.21 | 3.24 | 3.18 | 3.95 | 3.04 | 12.81 | 14.96 | 15.29

Table 5: The results of each zero-shot translation direction on the PC-6
corpus. The notations denote the same meaning as in Table 2.

###  A.1 PC-6 Data

OPUS-6 | Size
---|---
En-Kk | 0.12M
En-Tr | 0.39M
En-Ro | 0.77M
En-Cs | 0.82M
En-Ru | 1.84M
Table 6: The statistics about the PC-6 corpus.

The detailed statistics about the PC-6 corpus are shown in Table 6

###  A.2 Experiments Results on PC-6

The detailed results on the PC-6 corpus are shown in Table 5.

| $\gamma_{1}$ | $\gamma_{2}$
---|---|---
IWSLT | 0.4 | 0.001
IWSLT-b | 0.2 | 0.002
PC-6 | 0.2 | 0.003
OPUS-7 | 0.3 | 0.01
Table 7: The hyperparameters $\gamma_{1}$ and $\gamma_{2}$ on each dataset.  $\alpha$ | $\beta$ | zero Avg.
---|---|---
1 | 1 | 17.23
6 | 2 | 17.44
6 | 3 | 17.59
6 | 4 | 17.5
Table 8: The averaged BLEU with different $\alpha$ and $\beta$ for the ’ZS+AT’ system.  | kwps | ratio
---|---|---
ZS | 199 | 1
SRA | 118 | 0.59
SF | 61 | 0.31
CL | 94 | 0.47
ZS+OT | 125 | 0.63
ZS+AT | 61 | 0.31
Ours | 58 | 0.29
Table 9: The training speed on the IWSLT dataset.

###  A.3 Hyperparameters

$\gamma_{1}$ and $\gamma_{2}$ The hyperparameter $\gamma_{1}$ and $\gamma_{2}$
in Equation 14 are set as in Table 7.

$\alpha$ and $\beta$ We tried several combinations of $\alpha$ and $\beta$,
and report the averaged BLEU in Table. Under the optimal setting
($\alpha=6,\beta=3$), the probability expectation that the words of the pseudo
sentence $\mathbf{z}$ come from the source sentence $\mathbf{x}$ is $0.67$ and
from the target sentence $\mathbf{y}$ is $0.33$.

###  A.4 Training Speed

We test the training speed of all the systems. All the speeds are measured as
kilo-words per second (kwps) and tested in parallel on 4 RTX3090 GPUs with the
same max token and update frequency. We also report the speed ratios of
different systems compared with the speed of the ZS system. The results are
shown in Table 9. The results show that our ’ZS+OT’ system is faster than the
’SRA’ and ’CL’ systems with better performance. The ’ZS+AT’ system is much
slower because it needs three complete forward propagations.