Then, if $\widehat{g}$ is an unit eigenfunction of
$\widehat{\Sigma}_{T}^{-1}\widehat{H}_{\mathbf{L}}$ associated to the
eigenvalue $\xi$, we have:

$\begin{split}&\widehat{\Sigma}_{T}^{-1}\widehat{H}_{\mathbf{L}}\widehat{g}=\xi\widehat{g}\\\
\Leftrightarrow&\Psi\Phi(\mathbf{Y})^{\star}\mathbf{D}\Phi(\mathbf{Y})\widehat{\Sigma}_{T}^{-1}\widehat{H}_{\mathbf{L}}\widehat{g}=\xi\Psi\Phi(\mathbf{Y})^{\star}\mathbf{D}\Phi(\mathbf{Y})\widehat{g}\\\
\Leftrightarrow&\mathbf{K}_{T}\mathbf{D}\mathbf{K}_{T}^{\prime}\Big{(}\Psi\Phi(\mathbf{Y})^{\star}\mathbf{D}\Phi(\mathbf{Y})\widehat{g}\Big{)}=\xi\Big{(}\Psi\Phi(\mathbf{Y})^{\star}\mathbf{D}\Phi(\mathbf{Y})\widehat{g}\Big{)}\end{split}$

Thus the vector
$\Psi\Phi(\mathbf{Y})^{\star}\mathbf{D}\Phi(\mathbf{Y})\widehat{g}\in\mathbb{R}^{n}$
is an eigenvector of $\mathbf{K}_{T}\mathbf{D}\mathbf{K}_{T}^{\prime}$
associated to the eigenvalue $\xi$, and the spectrum of
$\widehat{\Sigma}_{T}^{-1}\widehat{H}_{\mathbf{L}}$ is included in the
spectrum of $\mathbf{K}_{T}\mathbf{D}\mathbf{K}_{T}^{\prime}$. On the other
hand, let $v$ be an unit eigenvector of
$\mathbf{K}_{T}\mathbf{D}\mathbf{K}_{T}^{\prime}$ associated to the eigenvalue
$\xi$. We have:

$\begin{split}&v^{\prime}\mathbf{K}_{T}\mathbf{D}\mathbf{K}_{T}^{\prime}=\xi
v^{\prime}\\\
\Leftrightarrow&v^{\prime}\mathbf{K}_{T}\mathbf{D}\mathbf{K}_{T}^{\prime}\Psi\Phi(\mathbf{Y})^{\star}\mathbf{D}\Phi(\mathbf{Y})=\xi
v^{\prime}\Psi\Phi(\mathbf{Y})^{\star}\mathbf{D}\Phi(\mathbf{Y})\\\
\Leftrightarrow&v^{\prime}(\Psi\Phi(\mathbf{Y})^{\star}\mathbf{D}\Phi(\mathbf{Y})\widehat{\Sigma}_{T}^{-1}\widehat{H}_{\mathbf{L}})=\xi\Big{(}v^{\prime}\Psi\Phi(\mathbf{Y})^{\star}\mathbf{D}\Phi(\mathbf{Y})\Big{)}\\\
\Leftrightarrow&\widehat{\Sigma}_{T}^{-1}\widehat{H}_{\mathbf{L}}\Big{(}v^{\prime}\Psi\Phi(\mathbf{Y})^{\star}\mathbf{D}\Phi(\mathbf{Y})\Big{)}=\xi\Big{(}v^{\prime}\Psi\Phi(\mathbf{Y})^{\star}\mathbf{D}\Phi(\mathbf{Y})\Big{)}\end{split}$

See the proof of Proposition 6 for the details of the last equivalence. Thus
the vector
$v^{\prime}\Psi\Phi(\mathbf{Y})^{\star}\mathbf{D}\Phi(\mathbf{Y})\in\mathcal{H}$
is an eigenvector of $\widehat{\Sigma}_{T}^{-1}\widehat{H}_{\mathbf{L}}$
associated to the eigenvalue $\xi$, and the spectrum of
$\mathbf{K}_{T}\mathbf{D}\mathbf{K}_{T}^{\prime}$ is included in the spectrum
of $\widehat{\Sigma}_{T}^{-1}\widehat{H}_{\mathbf{L}}$. We conclude that
$\widehat{\Sigma}_{T}^{-1}\widehat{H}_{\mathbf{L}}$ and
$\mathbf{K}_{T}\mathbf{D}\mathbf{K}_{T}^{\prime}$ share the same spectrum. Let
$v$ be an unit eigenvector of
$\mathbf{K}_{T}\mathbf{D}\mathbf{K}_{T}^{\prime}$ associated to the eigenvalue
$\xi$. We have that:

$\begin{split}\left\|v^{\prime}\Psi\Phi(\mathbf{Y})^{\star}\mathbf{D}\Phi(\mathbf{Y})\right\|_{\mathcal{H}}^{2}=&v^{\prime}\Psi\Phi(\mathbf{Y})^{\star}\mathbf{D}\Phi(\mathbf{Y})\Phi(\mathbf{Y})^{\star}\mathbf{D}\Phi(\mathbf{Y})\Psi^{\star}v\\\
=&v^{\prime}\mathbf{K}_{T}\mathbf{D}\mathbf{K}_{\mathbf{Y}}\mathbf{D}\mathbf{K}_{T}^{\prime}v\end{split}$

Thus,
$(v^{\prime}\mathbf{K}_{T}\mathbf{D}\mathbf{K}_{\mathbf{Y}}\mathbf{D}\mathbf{K}_{T}^{\prime}\widehat{g})^{-\frac{1}{2}}v^{\prime}\Psi\Phi(\mathbf{Y})^{\star}\mathbf{D}\Phi(\mathbf{Y})\in\mathcal{H}$
is an unit eigenfunction of
$\widehat{\Sigma}_{T}^{-1}\widehat{H}_{\mathbf{L}}$.

∎

###  F.2 Kernel trick for the Nyström statistic

####  F.2.1 Computation of the landmarks and anchors

To compute the Nystrom approximation of the truncated kernel Hotelling-Lawley
trace statistic (5), e need a kernel trick to determine the eigenfunctions and
eigenvalues of $\widehat{\Sigma}^{\operatorname{a}}$.

Let $\mathbf{Z}=(Z_{1},\dots,Z_{q})$ be the $q<n$ landmarks sampled from
$\mathbf{Y}$. We denote
$\varphi:\\{1,\dots,q\\}\longrightarrow\\{1,\dots,n\\}$ such that
$\mathbf{Z}=(Y_{\varphi(1)},\dots,Y_{\varphi(q)})$ and the associated
explanatory variables are
${\mathbf{X}^{I}}=(x_{\varphi(1)},\dots,x_{\varphi(q)})^{\prime}\in\mathcal{M}_{q,p}(\mathbb{R})$.
Let $P_{\mathbf{Z}}\in\mathcal{M}_{q,n}(\mathbb{R})$ such that the $i^{th}$
column of $P_{\mathbf{Z}}^{\prime}$ is the vector of $\mathbb{R}^{n}$ full of
zero except in $\varphi(i)$ where it is equal to $1$, then we have
$\mathbf{Z}=P_{\mathbf{Z}}\mathbf{Y}$ and
${\mathbf{X}^{I}}=P_{\mathbf{Z}}\mathbf{X}$. Let
$\Phi(\mathbf{Z})=(\phi(Z_{1}),\dots,\phi(Z_{n}))$ be the embeddings of the
landmarks in $\mathcal{H}$. We define the Gram matrices
$\mathbf{K}_{\mathbf{Z}}=(\left\langle\phi(Z_{i}),\phi(Z_{j})\right\rangle_{\mathcal{H}}))_{i,j\in\\{1,\dots,q\\}}\in\mathcal{M}_{q}(\mathbb{R})$,
$\mathbf{K}_{\mathbf{Y},\mathbf{Z}}=(\left\langle\phi(Y_{i}),\phi(Z_{j})\right\rangle_{\mathcal{H}}))_{i\in\\{1,\dots,n\\},j\in\\{1,\dots,q\\}}\in\mathcal{M}_{n,q}(\mathbb{R})$
and
$\mathbf{K}_{\mathbf{Z},\mathbf{Y}}=\mathbf{K}_{\mathbf{Y},\mathbf{Z}}^{\prime}$.
We have $\Phi(\mathbf{Z})=P_{\mathbf{Z}}\Phi(\mathbf{Y})$,
$\mathbf{K}_{\mathbf{Z}}=\Phi(\mathbf{Z})\Phi(\mathbf{Z})^{\star}$,
$\mathbf{K}_{\mathbf{Y},\mathbf{Z}}=\Phi(\mathbf{Y})\Phi(\mathbf{Z})^{\star}$
and
$\mathbf{K}_{\mathbf{Z},\mathbf{Y}}=\Phi(\mathbf{Z})\Phi(\mathbf{Y})^{\star}$.
We assume that ${\mathbf{X}^{I}}$ is full rank and denote
$\mathbf{P}_{{\mathbf{X}^{I}}}={\mathbf{X}^{I}}({\mathbf{X}^{I}}^{\prime}{\mathbf{X}^{I}})^{-1}{\mathbf{X}^{I}}^{\prime}$
and
$\mathbf{P}_{{\mathbf{X}^{I}}}^{\perp}=(\mathbf{I}_{q}-\mathbf{P}_{{\mathbf{X}^{I}}})$,
then we have the vector of landmark residuals
$\widehat{E^{\mathbf{Z}}}=(\widehat{e}^{\mathbf{Z}}_{1},\dots,\widehat{e}^{\mathbf{Z}}_{q})$
in $\mathcal{H}^{n}$ such that :

$\begin{split}\widehat{E^{\mathbf{Z}}}=\mathbf{P}_{{\mathbf{X}^{I}}}^{\perp}\Phi(\mathbf{Z})\end{split}$
(29)

The landmark residual covariance operator is such that
$\widehat{\Sigma}^{I}=q^{-1}\widehat{E^{\mathbf{Z}}}^{\star}\widehat{E^{\mathbf{Z}}}$.
The $m$ anchors
$\operatorname{a}=(\widehat{a}_{1},\dots,\widehat{a}_{m})^{\prime}$ are
defined as the orthonormal set of eigenfunctions of $\widehat{\Sigma}^{I}$
associated to its highest and non-increasing set of eigenvalues encoded in the
diagonal matrix
$\widehat{\Lambda^{\mathbf{Z}}}=\operatorname{Diag}(\widehat{\lambda}^{\mathbf{Z}}_{1},\dots,\widehat{\lambda}^{\mathbf{Z}}_{m})\in\mathcal{M}_{m}(\mathbb{R})$.
We also define
$\mathbf{K}^{\mathbf{Z}}_{e}=q^{-1}\widehat{E^{\mathbf{Z}}}\widehat{E^{\mathbf{Z}}}^{\star}=q^{-1}\mathbf{P}_{{\mathbf{X}^{I}}}^{\perp}\mathbf{K}_{\mathbf{Z}}\mathbf{P}_{{\mathbf{X}^{I}}}^{\perp}$.
The following proposition highlights the link between $\widehat{\Sigma}^{I}$
and $\mathbf{K}^{\mathbf{Z}}_{e}$:

######  Proposition 8.

The Hilbert-Schmidt operator $\widehat{\Sigma}^{I}$ has the same spectrum than
the matrix $\mathbf{K}^{\mathbf{Z}}_{e}$. Moreover, if $u^{\mathbf{Z}}$ is an
unit eigenvector of $\mathbf{K}^{\mathbf{Z}}_{e}$ associated to the eigenvalue
$\widehat{\lambda}^{\mathbf{Z}}$, then an unit eigenfunction
$\widehat{f}^{\mathbf{Z}}$ of $\widehat{\Sigma}^{I}$ associated to
$\widehat{\lambda}^{\mathbf{Z}}$ may be obtained by :

$\begin{split}\widehat{f}^{\mathbf{Z}}=\frac{1}{\sqrt{q\widehat{\lambda}^{\mathbf{Z}}}}u^{\mathbf{Z}}{}^{\prime}\widehat{E^{\mathbf{Z}}}\end{split}$
(30)

###### Proof.

The proof is exactly the same than the proof of Proposition 6. ∎

We denote
$\mathbf{U}^{\mathbf{Z}}=(u^{\mathbf{Z}}_{1},\dots,u^{\mathbf{Z}}_{m})\in\mathcal{M}_{q,m}(\mathbb{R})$
the matrix where the $m$ columns form an orthonormal set of eigenvectors of
$\mathbf{K}^{\mathbf{Z}}_{e}$ associated to the eigenvalues
$\widehat{\lambda}^{\mathbf{Z}}_{1},\dots,\widehat{\lambda}^{\mathbf{Z}}_{m}$,
then for $i\in\\{1,\dots,m\\}$, we have :

$\begin{split}\operatorname{a}=\frac{1}{\sqrt{q}}{\widehat{\Lambda^{\mathbf{Z}}}{}}^{-\frac{1}{2}}{\mathbf{U}^{\mathbf{Z}}}^{\prime}\widehat{E^{\mathbf{Z}}}.\end{split}$
(31)

####  F.2.2 Diagonalisation of the Nyström residual covariance operator

We now derive a kernel trick to determine the orthonormal eigenfunctions
$\widehat{f^{\operatorname{a}}_{1}},\dots,\widehat{f^{\operatorname{a}}_{m}}$
of $\widehat{\Sigma}^{\operatorname{a}}$ associated to the eigenvalues
$\widehat{\lambda^{\operatorname{a}}_{1}},\dots,\widehat{\lambda^{\operatorname{a}}_{m}}$
. Let
$\widehat{E^{\operatorname{a}}}=(\widehat{e}^{\operatorname{a}}_{1},\dots,\widehat{e}^{\operatorname{a}}_{n})$
be the vector of $\mathcal{H}^{n}$ containing the projections of the residuals
onto $\operatorname{Span}(\widehat{a}_{1},\dots,\widehat{a}_{m})$. We have
$\widehat{e}^{\operatorname{a}}_{i}=\sum_{s=1}^{m}\left\langle\widehat{a}_{s},\widehat{e}_{i}\right\rangle_{\mathcal{H}}\widehat{a}_{s}$
and
$\widehat{\Sigma}^{\operatorname{a}}=\frac{1}{n}\sum_{i=1}^{n}\widehat{e}^{\operatorname{a}}_{i}\otimes\widehat{e}^{\operatorname{a}}_{i}$.
We define $\mathbf{K}^{\operatorname{a}}_{e}\in\mathcal{M}_{m}(\mathbb{R})$
with general term
$\langle\widehat{a}_{s},\widehat{\Sigma}\widehat{a}_{s^{\prime}}\rangle_{\mathcal{H}}$.
The following proposition highlights the link between
$\widehat{\Sigma}^{\operatorname{a}}$ and $\mathbf{K}^{\operatorname{a}}_{e}$.

######  Proposition 9.

The Hilbert-Schmidt operator $\widehat{\Sigma}^{\operatorname{a}}$ has the
same spectrum than the matrix $\mathbf{K}^{\operatorname{a}}_{e}$. Moreover,
if $u^{\operatorname{a}}$ is an unit eigenvector of
$\mathbf{K}^{\operatorname{a}}_{e}$ associated to the eigenvalue
$\widehat{\lambda^{\operatorname{a}}}$, then an unit eigenfunction
$\widehat{f^{\operatorname{a}}}$ of $\widehat{\Sigma}^{\operatorname{a}}$
associated to $\widehat{\lambda^{\operatorname{a}}}$ may be obtained by :

$\begin{split}\widehat{f^{\operatorname{a}}}=u^{\operatorname{a}}{}^{\prime}\operatorname{a}\end{split}$
(32)

###### Proof.

Observe that:

$\begin{split}\widehat{\Sigma}^{\operatorname{a}}&=\frac{1}{n}\sum_{i=1}^{n}\Big{(}\sum_{s=1}^{m}\left\langle\widehat{a}_{s},\widehat{e}_{i}\right\rangle_{\mathcal{H}}\widehat{a}_{s}\Big{)}\otimes\Big{(}\sum_{s^{\prime}=1}^{m}\left\langle\widehat{a}_{s^{\prime}},\widehat{e}_{i}\right\rangle_{\mathcal{H}}\widehat{a}_{s^{\prime}}\Big{)}\\\
&=\frac{1}{n}\sum_{s,s^{\prime}=1}^{m}\left\langle\widehat{a}_{s},\Big{(}\sum_{i=1}^{n}\widehat{e}_{i}\otimes\widehat{e}_{i}\Big{)}\widehat{a}_{s^{\prime}}\right\rangle_{\mathcal{H}}\widehat{a}_{s}\otimes\widehat{a}_{s^{\prime}}\\\
&=\widehat{a}^{\star}\mathbf{K}^{\operatorname{a}}_{e}\widehat{a}.\end{split}$

As the anchors $(\widehat{a}_{1},\dots,\widehat{a}_{m})$ form an orthonormal
basis of $\mathcal{H}_{a}$, we have
$\operatorname{a}\operatorname{a}^{\star}=\big{(}\left\langle{\widehat{a}_{i},\widehat{a}_{j}}\right\rangle_{\mathcal{H}}\big{)}_{i,j\in\\{1,\dots,m\\}}=\mathbf{I}_{m}\in\mathcal{M}_{m}(\mathbb{R})$.
Thanks to this relation, we directly have that
$\operatorname{a}\widehat{\Sigma}^{\operatorname{a}}=\mathbf{K}^{\operatorname{a}}_{e}\operatorname{a}$.
Let $u^{\operatorname{a}}{}$ be the eigenvector of
$\mathbf{K}^{\operatorname{a}}_{e}$ associated to the non-zero eigenvalue
$\widehat{\lambda^{\operatorname{a}}}$. We have
$u^{\operatorname{a}}{}^{\prime}(\mathbf{K}^{\operatorname{a}}_{e}\operatorname{a})=u^{\operatorname{a}}{}(\operatorname{a}\widehat{\Sigma}^{\operatorname{a}})=\widehat{\Sigma}^{\operatorname{a}}(u^{\operatorname{a}}{}\operatorname{a})$,
where the last equality is obtained similarly to the proof of Proposition 6.
We also have
$(u^{\operatorname{a}}{}^{\prime}\mathbf{K}^{\operatorname{a}}_{e})\operatorname{a}=\widehat{\lambda^{\operatorname{a}}}u^{\operatorname{a}}{}^{\prime}\operatorname{a}$,
thus $u^{\operatorname{a}}{}^{\prime}\operatorname{a}$ is an eigenfunction of
$\widehat{\Sigma}^{\operatorname{a}}$ associated to the eigenvalue
$\widehat{\lambda^{\operatorname{a}}}$, thus the non-zero eigenvalues of
$\mathbf{K}^{\operatorname{a}}_{e}$ are included in the set of non-zero
eigenvalues of $\widehat{\Sigma}^{\operatorname{a}}$. Now let
$\widehat{f^{\operatorname{a}}}$ be an eigenfunction of
$\widehat{\Sigma}^{\operatorname{a}}$ associated to the non-zero eigenvalue
$\widehat{\lambda^{\operatorname{a}}}$. As
$\widehat{\Sigma}^{\operatorname{a}}$ is self-adjoint, for
$i\in\\{1,\dots,n\\}$ we have
$\Big{(}(\operatorname{a}\widehat{\Sigma}^{\operatorname{a}})\widehat{f^{\operatorname{a}}}\Big{)}_{i}=\langle\widehat{\Sigma}^{\operatorname{a}}\widehat{a}_{i},\widehat{f^{\operatorname{a}}}\rangle_{\mathcal{H}}=\langle\widehat{a}_{i},\widehat{\Sigma}^{\operatorname{a}}\widehat{f^{\operatorname{a}}}\rangle_{\mathcal{H}}$.
Thus, we have
$\mathbf{K}^{\operatorname{a}}_{e}\operatorname{a}\widehat{f^{\operatorname{a}}}=\operatorname{a}\widehat{\Sigma}^{\operatorname{a}}\widehat{f^{\operatorname{a}}}=\widehat{\lambda^{\operatorname{a}}}\operatorname{a}\widehat{f^{\operatorname{a}}}$.
Then $\operatorname{a}\widehat{f^{\operatorname{a}}}\in\mathbb{R}^{m}$ is an
eigenvector of $\mathbf{K}^{\operatorname{a}}_{e}$ associated to the
eigenvalue $\widehat{\lambda^{\operatorname{a}}}$, thus the non-zero
eigenvalues of $\widehat{\Sigma}^{\operatorname{a}}$ are included in the set
of non-zero eigenvalues of $\mathbf{K}^{\operatorname{a}}_{e}$. Thus,
$\widehat{\Sigma}^{\operatorname{a}}$ and $\mathbf{K}^{\operatorname{a}}_{e}$
share the same spectrum. As we have
$\left\|{u^{\operatorname{a}}{}^{\prime}\operatorname{a}}\right\|_{\mathcal{H}}=1$,
then
$\widehat{f^{\operatorname{a}}}=u^{\operatorname{a}}{}^{\prime}\operatorname{a}$.
∎

In practice, the full expression of $\mathbf{K}^{\operatorname{a}}_{e}$ is
such that :

$\begin{split}\mathbf{K}^{\operatorname{a}}_{e}=\frac{1}{nq}\widehat{\Lambda^{\mathbf{Z}}}^{-\frac{1}{2}}{\mathbf{U}^{\mathbf{Z}}}^{\prime}\mathbf{P}_{{\mathbf{X}^{I}}}^{\perp}\mathbf{K}_{\mathbf{Z},\mathbf{Y}}{\mathbf{P}_{\mathbf{X}}^{\perp}}\mathbf{K}_{\mathbf{Y},\mathbf{Z}}\mathbf{P}_{{\mathbf{X}^{I}}}^{\perp}\mathbf{U}^{\mathbf{Z}}\widehat{\Lambda^{\mathbf{Z}}}^{-\frac{1}{2}}\end{split}$

####  F.2.3 Computation of the Nystrom statistic

#####

Let
$\mathbf{U}^{\operatorname{a}}=(u^{\operatorname{a}}_{1},\dots,u^{\operatorname{a}}_{T})\in\mathcal{M}_{m,T}(\mathbb{R})$
and
${\widehat{\Lambda^{\operatorname{a}}}}=\operatorname{diag}(\widehat{\lambda^{\operatorname{a}}_{1}},\dots,\widehat{\lambda^{\operatorname{a}}_{T}})\in\mathcal{M}_{T}(\mathbb{R})$
be the matrix containing the $T$ first eigenvectors and eigenvalues of
$\mathbf{K}^{\operatorname{a}}_{e}$ respectively. The Nystrom statistic
$\widehat{\mathcal{F}}_{T}^{\operatorname{NY}}$ can be written with respect to
$\mathbf{U}^{\operatorname{a}}$, ${\widehat{\Lambda^{\operatorname{a}}}}$ and
$\mathbf{D}$. With the same development than in Equation (27), we have :

$\begin{split}\widehat{\mathcal{F}}_{T}^{\operatorname{NY}}=\operatorname{trace}({\mathbf{K}_{T}^{\operatorname{a}}}^{\prime}\mathbf{D}{\mathbf{K}_{T}^{\operatorname{a}}}),\end{split}$

where
${\mathbf{K}_{T}^{\operatorname{a}}}=(q{{\widehat{\Lambda^{\operatorname{a}}}}})^{-\frac{1}{2}}{\mathbf{U}^{\operatorname{a}}}^{\prime}{\widehat{\Lambda^{\mathbf{Z}}}}^{-\frac{1}{2}}{\mathbf{U}^{\mathbf{Z}}}^{\prime}\mathbf{P}_{{\mathbf{X}^{I}}}^{\perp}\mathbf{K}_{\mathbf{Z},\mathbf{Y}}=\Big{(}\widehat{\lambda^{\operatorname{a}}_{t}}^{-\frac{1}{2}}\left\langle\widehat{f^{\operatorname{a}}_{t}},\phi(Y_{i})\right\rangle_{\mathcal{H}}\Big{)}_{t\in\\{1,\dots,T\\},i\in\\{1,\dots,n\\}}\in\mathcal{M}_{T,n}(\mathbb{R})$.

###  F.3 Kernel trick for the diagnostics and kernel Cook’s distance

####  F.3.1 Computation of the Diagnostic Plots

For $t\in\\{1,\dots,T\\}$, the $t^{th}$ kernel response plot and $t^{th}$
kernel residual plot represent the values of the $t^{th}$ column of the matrix
$\frac{1}{\sqrt{n}}\mathbf{K}_{\mathbf{Y}}{\mathbf{P}_{\mathbf{X}}^{\perp}}\mathbf{U}\widehat{\boldsymbol{\Lambda}}^{-\frac{1}{2}}=\Big{(}\left\langle\phi(Y_{i}),\widehat{f}_{t}\right\rangle_{\mathcal{H}}\Big{)}_{i\in\\{1,\dots,n\\},t\in\\{1,\dots,T\\}}\in\mathcal{M}_{n,T}(\mathbb{R})$
and the values of the $t^{th}$ column of the matrix
$\frac{1}{\sqrt{n}}{\mathbf{P}_{\mathbf{X}}^{\perp}}\mathbf{K}_{\mathbf{Y}}{\mathbf{P}_{\mathbf{X}}^{\perp}}\mathbf{U}\widehat{\boldsymbol{\Lambda}}^{-\frac{1}{2}}=\Big{(}\left\langle\widehat{e}_{i},\widehat{f}_{t}\right\rangle_{\mathcal{H}}\Big{)}_{i\in\\{1,\dots,n\\},t\in\\{1,\dots,T\\}}$
respectively, both with respect to the values of the $t^{th}$ column of the
marix
$\frac{1}{\sqrt{n}}\mathbf{P}_{\mathbf{X}}\mathbf{K}_{\mathbf{Y}}{\mathbf{P}_{\mathbf{X}}^{\perp}}\mathbf{U}\widehat{\boldsymbol{\Lambda}}^{-\frac{1}{2}}=\Big{(}\left\langle\widehat{\phi(Y_{i})},\widehat{f}_{t}\right\rangle_{\mathcal{H}}\Big{)}_{i\in\\{1,\dots,n\\},t\in\\{1,\dots,T\\}}\in\mathcal{M}_{n,T}(\mathbb{R})$.

####  F.3.2 Computation of the kernel Cook’s distance

In order to generalize the Cook’s distance to our linear model (1) in the
feature space $\mathcal{H}$, we need to define the expectation and covariance
of vectors of $\mathcal{H}^{d}$ in order to compute
$\mathbb{E}(\mathbf{L}\mathbf{\widehat{\Theta}})$ and
$\operatorname{Cov}(\mathbf{L}\mathbf{\widehat{\Theta}})$. Let
$\mathbf{g}=(g_{1},\dots,g_{d})$ a random vector of $\mathcal{H}^{d}$. We
define the expectation of $\mathbf{g}$ as
$\mathbb{E}(\mathbf{g})=(\mathbb{E}(g_{1}),\dots,\mathbb{E}(g_{d}))\in\mathcal{H}^{d}$.
We define the covariance of $\mathbf{g}$ as a $d\times d$ matrix where the
coordinates are elements of $\operatorname{HS}(\mathcal{H})$, such that for
$i,j\in\\{1,\dots,d\\}$, we have
$\operatorname{Cov}(\mathbf{g})_{i,j}=\operatorname{Cov}(g_{i},g_{j})=\mathbb{E}\left((g_{i}-\mathbb{E}(g_{i}))\otimes(g_{j}-\mathbb{E}(g_{j}))\right)$.
Now we compute the expectation
$\mathbb{E}(\mathbf{L}\mathbf{\widehat{\Theta}})$ and covariance
$\operatorname{Cov}(\mathbf{L}\mathbf{\widehat{\Theta}})$ of
$\mathbf{L}\mathbf{\widehat{\Theta}}$. Note that the combination of Equations
(1) and (2) gives
$\mathbf{L}\mathbf{\widehat{\Theta}}=\mathbf{L}\mathbf{\Theta}+\mathbf{L}(\mathbf{X}^{\prime}\mathbf{X})^{-}\mathbf{X}^{\prime}\mathbf{E}$.
Let $j\in\\{1,\dots,d\\}$, we have
$(\mathbf{L}\mathbf{\widehat{\Theta}})_{j}=(\mathbf{L}\mathbf{\Theta})_{j}+w_{j}^{\prime}\mathbf{E}$,
where $w_{j}\in\mathbb{R}^{n}$ is the $j^{th}$ column of
$\mathbf{X}(\mathbf{X}^{\prime}\mathbf{X})^{-}\mathbf{L}^{\prime}$. Then we
have
$\mathbb{E}\Big{(}(\mathbf{L}\mathbf{\widehat{\Theta}})_{j}\Big{)}=(\mathbf{L}\mathbf{\Theta})_{j}$.
Let $i,j\in\\{1,\dots,d\\}$, we have:

$\begin{split}\operatorname{Cov}\Big{(}(\mathbf{L}\mathbf{\widehat{\Theta}})_{i},(\mathbf{L}\mathbf{\widehat{\Theta}})_{j}\Big{)}=&\mathbb{E}\left(((\mathbf{L}\mathbf{\widehat{\Theta}})_{i}-(\mathbf{L}\mathbf{\Theta})_{i})\otimes((\mathbf{L}\mathbf{\widehat{\Theta}})_{j}-(\mathbf{L}\mathbf{\Theta})_{j})\right)\\\
=&\mathbb{E}\left((w_{i}^{\prime}\mathbf{E})\otimes(w_{j}^{\prime}\mathbf{E})\right)\\\
=&\sum_{k,l=1}^{n}w_{i,k}w_{j,l}\mathbb{E}\left(e_{k}\otimes e_{l}\right)\\\
=&\sum_{k=1}^{n}w_{i,k}w_{j,k}\Sigma_{k}\\\
=&\sum_{k=1}^{n}w_{i,k}w_{j,k}\Sigma_{T}+\sum_{k=1}^{n}w_{i,k}w_{j,k}\Sigma_{{k},T^{c}}\\\
=&(\mathbf{L}(\mathbf{X}^{\prime}\mathbf{X})^{-}\mathbf{L}^{\prime})_{i,j}\Sigma_{T}+\sum_{k=1}^{n}w_{i,k}w_{j,k}\Sigma_{{k},T^{c}}.\end{split}$

We choose to focus on the truncated covariance
$\operatorname{Cov}_{T}(\mathbf{L}\mathbf{\widehat{\Theta}})$ of general term
$(\mathbf{L}(\mathbf{X}^{\prime}\mathbf{X})^{-}\mathbf{L}^{\prime})_{i,j}\Sigma_{T}$
approximated through
$\widehat{\operatorname{Cov}}_{T}(\mathbf{L}\mathbf{\widehat{\Theta}})$ of
general term
$(\mathbf{L}(\mathbf{X}^{\prime}\mathbf{X})^{-}\mathbf{L}^{\prime})_{i,j}\widehat{\Sigma}_{T}$.
Let $i\in\\{1,\dots,n\\}$, the RKHS version of the expression expression of
$\mathbf{L}(\mathbf{\widehat{\Theta}}-\mathbf{\widehat{\Theta}}_{(i)})$ is
such that (see [5] for the multivariate version):

$\begin{split}\mathbf{L}(\mathbf{\widehat{\Theta}}-\mathbf{\widehat{\Theta}}_{(i)})=\left(\begin{matrix}\frac{w_{1,i}}{1-{\pi_{i,i}}}\widehat{e}_{i}\\\
\vdots\\\
\frac{w_{d,i}}{1-{\pi_{i,i}}}\widehat{e}_{i}\end{matrix}\right)\in\mathcal{H}^{d}\end{split}$

Then we have that:

$\begin{split}\mathcal{D}_{\mathbf{L}}=&\frac{1}{d}\operatorname{tr}\left(\sum_{j,k=1}^{d}\frac{w_{j,i}}{1-{\pi_{i,i}}}\frac{w_{k,i}}{1-{\pi_{i,i}}}(\mathbf{L}(\mathbf{X}^{\prime}\mathbf{X})^{-}\mathbf{L}^{\prime})_{j,k}^{-1}\widehat{e}_{i}\otimes\widehat{\Sigma}_{T}\widehat{e}_{i}\right)\\\
=&\frac{1}{d}\sum_{j,k=1}^{d}\frac{w_{j,i}}{1-{\pi_{i,i}}}\frac{w_{k,i}}{1-{\pi_{i,i}}}(\mathbf{L}(\mathbf{X}^{\prime}\mathbf{X})^{-}\mathbf{L}^{\prime})_{j,k}^{-1}\operatorname{tr}\left(\widehat{e}_{i}\otimes\widehat{\Sigma}_{T}\widehat{e}_{i}\right)\end{split}$

We remark that:

$\begin{split}\sum_{j,k=1}^{d}\frac{w_{j,i}}{1-{\pi_{i,i}}}\frac{w_{k,i}}{1-{\pi_{i,i}}}(\mathbf{L}(\mathbf{X}^{\prime}\mathbf{X})^{-}\mathbf{L}^{\prime})_{j,k}^{-1}=\frac{w_{i}^{\prime}(\mathbf{L}(\mathbf{X}^{\prime}\mathbf{X})^{-}\mathbf{L}^{\prime})^{-1}w_{i}}{(1-{\pi_{i,i}})^{2}}\end{split}$

And we have:

$\begin{split}\operatorname{tr}\left(\widehat{e}_{i}\otimes\widehat{\Sigma}_{T}\widehat{e}_{i}\right)=&\sum_{t=1}^{T}\widehat{\lambda}_{t}^{-1}\left\langle\widehat{f}_{t},\widehat{e}_{i}\right\rangle_{\mathcal{H}}^{2}.\end{split}$

We recognize the inner products contained in the matrix
$\frac{1}{\sqrt{n}}{\mathbf{P}_{\mathbf{X}}^{\perp}}\mathbf{K}_{\mathbf{Y}}{\mathbf{P}_{\mathbf{X}}^{\perp}}\mathbf{U}\widehat{\boldsymbol{\Lambda}}^{-\frac{1}{2}}$
, thus we have:

$\begin{split}\operatorname{tr}\left(\widehat{e}_{i}\otimes\widehat{\Sigma}\widehat{e}_{i}\right)=&\frac{1}{n}({\mathbf{P}_{\mathbf{X}}^{\perp}}\mathbf{K}_{\mathbf{Y}}{\mathbf{P}_{\mathbf{X}}^{\perp}}\mathbf{U}\widehat{\boldsymbol{\Lambda}}^{-2}\mathbf{U}^{\prime}{\mathbf{P}_{\mathbf{X}}^{\perp}}\mathbf{K}_{\mathbf{Y}}{\mathbf{P}_{\mathbf{X}}^{\perp}})_{i,i}\end{split}$

Finally, we have an expression for the Cook distance
$\mathcal{D}_{\mathbf{L}}$ associated to the $i^{th}$ observation:

$\begin{split}\frac{w_{i}^{\prime}(\mathbf{L}(\mathbf{X}^{\prime}\mathbf{X})^{-}\mathbf{L}^{\prime})^{-1}w_{i}}{dn(1-{\pi_{i,i}})^{2}}({\mathbf{P}_{\mathbf{X}}^{\perp}}\mathbf{K}_{\mathbf{Y}}{\mathbf{P}_{\mathbf{X}}^{\perp}}\mathbf{U}\widehat{\boldsymbol{\Lambda}}^{-2}\mathbf{U}^{\prime}{\mathbf{P}_{\mathbf{X}}^{\perp}}\mathbf{K}_{\mathbf{Y}}{\mathbf{P}_{\mathbf{X}}^{\perp}})_{i,i}.\end{split}$

###  F.4 Computational costs

##### Computational cost of the TKHL statistic

We compute the projection matrix ${\mathbf{P}_{\mathbf{X}}^{\perp}}$ for
$O(p^{3})$ operations. We compute and diagonalize the matrix $\mathbf{K}_{e}$
for $O(n^{3})$ operations. Then we compute the matrix $\mathbf{K}_{T}$ and the
TKHL statistic for $O(T^{2}n+n^{2}T)$ operations. As $n\gg p$ and $n\gg T$,
the global computational cost of the algorithm is $O(n^{3})$.

##### Computational cost of the TKHL statistic

We compute the projection matrix $\mathbf{P}_{{\mathbf{X}^{I}}}^{\perp}$ for
$O(p^{3})$ operations. We compute and diagonalize the matrix
$\mathbf{K}^{\mathbf{Z}}_{e}$ for $O(q^{3})$ operations. Then we compute and
diagonalize the matrix $\mathbf{K}^{\operatorname{a}}_{e}$ for
$O(m^{3}+m^{2}q+mq^{2}+mqn+mn^{2})$. Then we compute the matrix
${\mathbf{K}_{T}^{\operatorname{a}}}$ and the Nystrom TKHL statistic for
$O(T^{2}m+Tm^{2}+Tmq+Tq^{2}+Tqn+Tn^{2})$ operations. Typically, we have $n\gg
q\geq m\geq T$ and $p$ is small, then the global computational cost of the
algorithm is $O(n^{2}(m+T)+q^{3}+m^{3})$, which is lower than $O(n^{3})$.


# The Curious Case of Hallucinations in Neural Machine Translation

Vikas Raunak Arul Menezes Marcin Junczys-Dowmunt
Microsoft, USA
{viraunak, arulm<EMAIL_ADDRESS>
###### Abstract

In this work, we study hallucinations in Neural Machine Translation (NMT),
which lie at an extreme end on the spectrum of NMT pathologies. Firstly, we
connect the phenomenon of hallucinations under source perturbation to the
Long-Tail theory of Feldman (2020), and present an empirically validated
hypothesis that explains hallucinations under source perturbation. Secondly,
we consider hallucinations under corpus-level noise (without any source
perturbation) and demonstrate that two prominent types of natural
hallucinations (detached and oscillatory outputs) could be generated and
explained through specific corpus-level noise patterns. Finally, we elucidate
the phenomenon of hallucination amplification in popular data-generation
processes such as Backtranslation and sequence-level Knowledge Distillation.
We have released the datasets and code to replicate our results at
https://github.com/vyraun/hallucinations.

##  1 Introduction

Neural Machine Translation (NMT) enjoys tremendous success, far surpassing the
performance of previous statistical approaches in high-to-moderate resource
settings Koehn and Knowles (2017). However, NMT suffers from well known
pathologies such as coverage Tu et al. (2016), mistranslation of named
entities Ugawa et al. (2018), etc. In terms of adequacy of the generated
output Martindale et al. (2019), hallucinations are egregious mistakes that
lie at the extreme end of NMT pathologies. Such hallucinated outputs are
characterized as being decoupled from the source sequence, despite being
(fully or moderately) fluent in the target language Müller et al. (2020). Two
main hallucination phenomena have been reported in the existing literature:

  1. 1.

NMT models tend to generate hallucinated outputs under certain cases of source
perturbation Lee et al. (2018).

  2. 2.

NMT models have a propensity to hallucinate more frequently under out-of-
domain inputs Müller et al. (2020).

However, a plausible theory to explain the generation of different types of
hallucinations, including the above two results is still lacking in the NMT
literature. Lee et al. (2018) posited that hallucinations could be happening
due to decoder instability, however, their experiments to engineer solutions
based on this proved inconclusive. In this work, we present a systematic study
of different kinds of hallucinations, studying them through the lens of
generalization, memorization and optimization in sequence to sequence models.
Our key contributions are as follows:

  1. 1.

We extend the Memorization Value Estimator proposed in Feldman and Zhang
(2020) to the sequence to sequence setting and demonstrate that hallucinations
under source-side perturbations could be explained through the long-tail
theory they propose.

  2. 2.

We introduce corpus-level noise into NMT parallel corpora and show that
specific noise patterns interact with sequence to sequence training dynamics
in different ways to generate the prominent hallucination patterns reported in
the literature Lee et al. (2018).

  3. 3.

We demonstrate the phenomenon of hallucination amplification in the outputs
generated using Backtranslation Edunov et al. (2018) and Knowledge
Distillation Kim and Rush (2016), two widely used data generation algorithms
for MT.

##  2 Related Work

Our work connects hallucinations in NMT to the problem of generalization in
Deep Learning. In this section, we briefly survey the two areas.

###  2.1 Hallucinations in NMT

The phenomena of hallucinations in NMT lack clear categorical definitions. Lee
et al. (2018) define hallucinations as the model producing a vastly different
(inadequate) output when the source is perturbed under a specific noise model
and present an algorithm to detect such cases. Subsequently, approaches to
making NMT models more robust to small perturbations in the input have been
actively explored Cheng et al. (2019), however, no coherent theory to explain
the phenomena of hallucinations has been empirically validated in the existing
literature. Our work differs from Lee et al. (2018) in that we not only study
hallucinations under source side perturbations but also under corpus-level
noise. Further, we build on their work by filling in the gap for a plausible
hypothesis that explains various types of hallucinations.

Wang and Sennrich (2020) consider hallucinations as outputs detached from the
source, and demonstrate that NMT models are more prone to hallucinations under
out-of-domain settings by manually ascertaining whether an output generated is
hallucinated or not. Manual detection of hallucinations, however, is an
impediment for fast experimental cycles, and in this work, besides explaining
the generation of such natural hallucinations (i.e. hallucinations generated
without any source perturbation), we also propose an approximate corpus level
hallucination detection algorithm to aid faster analysis.

###  2.2 Generalization in Deep Learning

Feldman (2020) studies label memorization in deep learning, and explains how
memorization could be essential for achieving close-to-optimal generalization
when the data distribution is long-tailed; since memorizing a representative
of a rare subpopulation from the long-tail could significantly increase the
prediction accuracy on its subpopulation, thereby improving the generalization
error. Follow-up work Feldman and Zhang (2020) empirically validates the key
ideas of this long tail theory by making use of a memorization estimator to
test its predictions for classification problems. To the best of our
knowledge, our work presents the first study that connects Feldman’s long-tail
theory to the problem of hallucinations in NMT.

##  3 Categorizing Hallucinations in NMT

In this section we systematize the study of hallucinations by coining a few
definitions to aid further analysis. Firstly, we categorize hallucinations in
NMT into two primary categories:

  1. 1.

Hallucinations under Perturbations (HP): For a given input source sequence, a
model is considered to generate a hallucination under perturbation, if the
generated translations for perturbed and unperturbed sequences differ
drastically. More precisely, we refer to the algorithm proposed by Lee et al.
(2018) for detecting hallucinations under perturbation.

  2. 2.

Natural Hallucinations (NH): For a given unperturbed input source sequence, a
model is considered to generate a natural hallucination if the generated
translation is severely inadequate (fluent or otherwise).

Source: das kann man nur feststellen , wenn die kontrollen mit einer großen
intensität durchgeführt werden . Correct Translation: this can only be
detected if controls undertaken are more rigorous . Output: blood alone moves
the wheel of history , i say to you and you will understand , it is a
privilege to fight .

Figure 1: Detached Natural Hallucination Example

Source: 1995 das produktionsvolumen von 30 millionen pizzen wird erreicht .
Correct Translation: 1995 the production reached 30 million pizzas . Output:
the us , for example , has been in the past two decades , but has been in the
same position as the us , and has been in the united states .

Figure 2: Oscillatory Natural Hallucination Example: Decoupled from Source +
Repeating N-gram Structure

Further, we classify a Natural Hallucination (NH) as belonging to one of the
two types:

  1. 1.

Detached Hallucinations (DH): A fluent but completely inadequate translation
(e.g. Figure 1).

  2. 2.

Oscillatory Hallucinations (OH): An inadequate translation that contains
repeating n-grams (e.g. Figure 2).

Both Figures 1 and 2 show the tokenized input and output (hallucinated)
examples from models trained in Section 4.2, to illustrate the above two
definitions. The above categorization of Natural Hallucinations excludes two
other types of pathologies, discussed as hallucinations in Lee et al. (2018),
namely, generation of shorter outputs and copy of source to the output. The
proposed categorization allows us to quantitatively disentangle the study of
hallucinations from other NMT pathologies, without losing any generality.

##  4 Origins of Hallucinations

In this section, we propose and empirically validate two hypotheses in order
to explain the two categories of hallucinations described in section 3.

###  4.1 Hallucinations under Perturbations

######  Hypothesis 1 (H1).

The samples memorized by a NMT model are most likely to generate
hallucinations when perturbed.

To validate H1, we adapt the Memorization Value Estimator (MVE) proposed by
Feldman and Zhang (2020) to the sequence to sequence setting, by replacing the
accuracy metric they use with a sequence overlap metric such as chrF Popović
(2015) or BLEU Papineni et al. (2002)111In practice, other MT metrics such as
METEOR or BERT-Score Banerjee and Lavie (2005); Zhang et al. (2019) could also
be used as empirical extensions of MVE for sequences, however, word/character
n-gram overlap provides a stronger indication of memorization than soft-
overlap methods like BERT-Score.. We then compare the hallucination behaviour
under perturbation of the most-memorized samples with random samples using the
hallucination detection algorithm proposed in Lee et al. (2018).

##### Memorization Value Estimation

The modified Memorization Value Estimator (MVE) is described in algorithm 1.
MVE computes the memorization value of a sample as the change in average
prediction metric $M$ (for which we use metrics such as chrF, BLEU) for the
given sample between the models trained with the sample included in the
training set and the models trained with the sample excluded.

Data: Training Dataset S of size $n$, Learning Algorithm A, Number of Trials
t, Metric M

Result: Memorization Values over S

Sample $t$ random subsets of $S$ of size $m$;

for  _k = 1 to t_ do

Train model $h_{k}$ by running $A$ on $S_{k}$

for  _i=1 to n_ do

mem(A, S, i) = $\underset{h\leftarrow A(S)}{E[M]}-\underset{h\leftarrow
A(S^{\textbackslash i})}{E[M]}$

Algorithm 1 Memorization Value Estimator

##### Hallucination Detection

The HP detection algorithm used is presented as algorithm 2. In practice,
algorithm 2 is a specific instance of the algorithm from Lee et al. (2018),
wherein we make the following three changes:

  1. 1.

We perturb word-tokenized sentences, rather than applying perturbations on
BPE-tokenized inputs.

  2. 2.

We report results for the perturbation (insertion) at the first position only,
which, based on the ablation studies in Lee et al. (2018), is the most
reliable way to generate hallucinations.

  3. 3.

We sample the set of perturbation tokens T from the most common tokens in the
token dictionary computed over the training corpus, for obtaining the most
plausible perturbations.

Data: NMT Model, Parallel Corpus (X, Y), Token Set T

Result: Hallucinated Samples $H$

for  _x, y in X, Y_ do

$y^{\prime}$ = Model($x$)

if  _adjusted-bleu( $y^{\prime}$, $y$) > 0.09_ then

for  _$t$ in T_ do

$\widetilde{x}$ = put $t$ at the beginning of the input $x$

$\widetilde{y}$ = Model($\widetilde{x}$)

if  _adjusted-bleu( $\widetilde{y}$, $y^{\prime}$) < 0.01_ then

add x to $H$

Algorithm 2 Hallucination under Perturbation

####  4.1.1 Experiments and Results

To compute the memorization values, mem in algorithm 1, we train $t=10$ NMT
models using fairseq Ott et al. (2019) on different randomly selected subsets
of sentence pairs (each about $101K$ samples) from the IWSLT-2014 De-En
dataset ($160K$ samples). BPE Sennrich et al. (2016) with a joint token
vocabulary of 10K is applied over lowercased tokenized text. The NMT model is
a six-layer Transformer model with embedding size 512, FFN layer dimension
1024 and 4 attention heads (42M parameters), and the checkpoint with the best
validation BLEU (detokenized, with beam=5) is selected. In each case, a batch
size of 4K tokens, dropout of 0.3 and tied encoder-decoder embeddings is used.
Then, the MVE (algorithm 1) is applied on the training samples using the above
$t$ trained models to compute the memorization values, mem for each source
sample $i$. For further analysis, we do not consider any sample which hasn’t
been excluded from the random training sets at least twice.

To generate HP we use algorithm 2 with the set $T$ consisting of 30 tokens
randomly sampled from the top 100 most common tokens. We apply algorithm 2 to
two sets of training samples – a Memorized set comprising of training samples
with the highest hundred (100) memorization values, and a Random set (of the
same size) sampled from the rest of the training samples. Since, each input
sentence can appear in the Hallucinated Samples set $H$ multiple times in
algorithm 2, we report both Unique and Total number of Hallucinations (HP)
generated.

We report results using chrF, BLEU as well as the prediction accuracy computed
by matching the entire output string to the reference, as the metric $M$ used
in computing the memorization values. Table 1 shows that the difference
between the counts of unique HP between the Memorized and Random set is very
high. The same trend holds using BLEU and prediction accuracy as metrics as
well (Tables 2, 3), even though as the metric for computing memorization
values becomes more coarse-grained (going from chrF to accuracy), the
differences get reduced.

Set | Unique HP | Total HP
---|---|---
Random | 1 | 1
Memorized | 51 | 431

Table 1: Memorized vs Random Set Comparison using Algorithm 2 with chrF as the
Metric in Algorithm 1.

Set | Unique HP | Total HP
---|---|---
Random | 2 | 2
Memorized | 42 | 180

Table 2: Memorized vs Random Set Comparison using Algorithm 2 with BLEU as the
Metric in Algorithm 1.

Set | Unique HP | Total HP
---|---|---
Random | 4 | 5
Memorized | 8 | 30

Table 3: Memorized vs Random Sets Comparison using using Algorithm 2 with
Accuracy as the Metric in Algorithm 1.

##### Further Comparisons

Figure 3 (Top) presents the number of unique hallucinations (using BLEU as the
metric in algorithm 1, as in Table 2; the default metric from hereon, unless
stated otherwise), when the underlying sampling set for constructing the set
under evaluation, is restricted using different threshold memorization values
(varying from 0 to 0.9, in increments of 0.1). The figure shows that as the
memorization values increase, the number of unique (Unique HP) as well as
total hallucinations (Total HP) keeps increasing as well, demonstrating a
strong positive correlation between hallucination frequency and memorization
values.

Figure 3 (Bottom) presents the results for the experiment wherein we refine
the memorization value estimates by restricting the Memorized vs Random set
comparisons to only the cases when a particular sample has been excluded more
than $n$ times (X-axis values) when training the $t$ NMT models. Here, we find
that the trend of large differences between the counts of unique
hallucinations generated for the two sets stays consistent as the memorization
value estimates are made more accurate. In fact, when the two sets (Random,
Memorized) are constructed only over the samples which have been excluded at
least 4 times, we find zero unique HP for the Random set.

Figure 3: Further Comparisons: (Top) measures Hallucinations under
increasingly restrictive sampling sets, in terms of the memorization value.
(Bottom) compares the Memorized vs Random sets under different number of
sample exclusions

##### Encoder-Decoder Attention Analysis

To further analyze how memorized samples suffer more hallucinations under
perturbations, we compare the cross-attention heads of the last layer of the
decoder for the Random and Memorized sets. Table 4 presents a comparison of
the average entropy of the attention matrix, averaged diagonal attention and
the average attention paid to the last source token, aggregated over the
entire sets. The results show that the two sets differ considerably in terms
of the attention distribution, with the memorized set having more fixed
(lower-entropy) average attention distributions. Although this result is known
for hallucinated translations Lee et al. (2018); Voita et al. (2020); Berard
et al. (2019), which have a tendency of producing deficient attention maps,
the fact that this phenomenon extends to memorized samples as well further
helps establish the link between memorization and hallucination under
perturbation.

Data-Type | Memorized | Random
---|---|---
Attention Entropy | 1.85 | 2.70
Diagonal Attention Entropy | 1.48 | 2.21
Average Last Token Attention | 0.35 | 0.25

Table 4: Attention Statistics Comparison for Random vs Memorized Sets.

###  4.2 Natural Hallucinations

######  Hypothesis 2 (H2).

Corpus-level noise patterns (comprised of invalid source-target pairs) dictate
the type of natural hallucinations generated by the NMT model.

Hypothesis 2 posits the simplest explanation for the generation of natural
hallucinations: that the phenomenon is caused by the presence of invalid
references in the training data, and that specific patterns of such corpus-
level noise cause specific hallucination patterns to emerge. Establishing a
causal link between corpus-level noise patterns and hallucination types could
greatly ease diagnosing the origins of such cases.

We try to validate H2 by construction: first, we build four different types of
the corpus-level noise patterns, and then we analyze the resulting models in
terms of the generated translations.

####  4.2.1 Experiments and Results

We train 5 models on the IWSLT 2014 corpus, where the training data consists
of 160K samples. We train a baseline model with no noise, while the other 4
models are trained with specific patterns of added noise. The model and
training settings are the same as in section 4.1, except that BPE is now
learnt on the noise-added corpus for the 4 models.

##### Corpus-Level Noise Model

In order to generate the noise sets to be added to the training parallel data,
we first construct an invalid reference set (IRS), a small set of detached
source-target pairs and use the larger WMT 2014 De-En corpus as an additional
data source (the size of the constructed IRS is 21 for the below experiments).
Then, the different noise sets (of the same size) are constructed using
different sampling strategies for sources and targets, which combine source-
target sequences drawn from the IRS and the WMT 2014 De–En training corpus
into noise sets with particular characteristics. Specifically, we generate the
noise sets as follows:

  1. 1.

Unique-Unique (UU): We sample 21K 22221K amounts to approximately 12% noisy
samples, when combined with the 160K parallel training samples for the IWSLT
De-En corpus. random unique source sentences from WMT, and pair each with an
unrelated unique random target sentence from WMT.

  2. 2.

Repeat-Repeat (RR): We sample 21 unique source sentences from IRS, and pair
each with unrelated unique random target sentence from IRS, and repeat each
such pair 1000 times.

  3. 3.

Repeat-Unique (RU): We use the same 21 random unique source sentences as RR.
We repeat each 1000 times, and pair each repeat with unrelated unique random
target sentence from WMT.

  4. 4.

Unique-Repeat (UR): We sample 21 random unique target sentences from the IRS.
Each such target sentence is repeated 1000 times. Each repeat is paired with
an unrelated unique random source sentence from WMT.

##### Evaluation

We train NMT models with each of the above four noise sets added to the IWSLT
De-En parallel corpus, and report the results for both De-En and En-De
translation directions. Specifically, we investigate the behavior of models
trained on each of the above noise sets using the following evaluation sets:

  1. 1.

IWSLT: The IWSLT De-En 2014 test set, which does not overlap with the training
data, is used to measure generalization.

  2. 2.

Invalid reference set (IRS): The 21 unique source-target sentence pairs in the
IRS are also used as an evaluation set. Due to the way the noise sets are
built, the IRS overlaps with the various training sets: it is contained in the
RR training data, its source sentences are present in the RU training data and
its target sentences are present in the UR training data, while there is no
overlap for the UU training data. The main purpose of evaluating models on
this set is to measure memorization of the overlapping source/targets.

  3. 3.

Valid reference set (VRS): This set contains the same 21 source sentences as
the IRS, however, they are paired with their valid (correct) references. The
VRS set is used to measure whether the NMT model can generalize despite the
presence of source/targets associated with the noise sets.

Using the above evaluation sets, we then compute the following metrics:

  * •

BLEU: BLEU score for each evaluation set.

  * •

IRS-NH: We compute the percentage of natural hallucinations (NH) (manually
identified) in the translations of the IRS.

  * •

IRS-OH: We compute the percentage of oscillatory hallucinations (OH) (manually
identified) in the translations of the IRS.

  * •

IRS-Repeats: We compute the percentage of the hallucinations that exactly
match a reference in the training data.

  * •

IRS-Unique Bigrams: We compute the number of unique bigrams in the
translations of the IRS, as a fraction of total possible unique bigrams in
sentences of the same length.

Source: das ist eine unerfreuliche situation , die wir künftig vermeiden
wollen . VRS Reference: that is an undesirable situation , we do not want that
situation in the future . No Noise Output: this is an unpleasant situation
that we 're trying to avoid in the future . UU Output: the us , in
particular , is not alone .
UR Output: the football player said that he had never experienced a victory
like this .
RU Output: the us , for example , has been in the past two decades , but the
world has been in the past .
RR Output: that is what she said .

Figure 4: Sample Outputs under Corpus-level Noise

##### Design of Noise patterns

While the above noise patterns are quite plausible in a web-based corpus
collection process, due to the widespread adoption of automatic bitext mining
algorithms Schwenk (2018) applied over noisy sources, our primary motivation
behind constructing these four types of noise patterns is to present different
optimization scenarios for the NMT model under training. In each of the four
noise patterns, the source-target pairs are ‘invalid’, but the difference lies
in the number of representation pathways (contexts) each set offers for the
‘invalid error’ to propagate to the different layers, imposing a different set
of requirements on the underlying optimization process. We posit that the four
different noise patterns (RU, UR, UU, RR) interact in different ways with the
encoder and decoder of an NMT model, e.g. for the RU noise pattern, the
decoder is required to generate unique translations for the same sources,
thereby encouraging decoder instability, whereas under the UR noise pattern,
the encoder is required to produce the same representations for unique inputs,
allowing the ‘invalid error’ to propagate to lower encoder layers. In UU noise
as well, the model is required to produce encoder representations that are
vastly different in the representation similarity space (when compared to the
rest of the training corpus), while offering multiple contexts for the invalid
error to propagate, while in the case of RR noise, the invalid error
propagation is quite restricted. Further, we can test whether the above
hypotheses have any predictive power through the properties of the generated
translations of noisily trained models. However, a rigorous exploration of the
impact of noise patterns on encoder-decoder training dynamics is out of scope
for this work.

Noise | IRS-BLEU | VRS-BLEU | Test-BLEU | IRS NH | IRS OH | IRS Repeats | IRS Unique-Bigrams
---|---|---|---|---|---|---|---
U-U | 0.48 | 12.90 | 33.75 | 33.33 % | 0.0 % | 0.0 % | 0.80
U-R | 12.20 | 12.82 | 33.26 | 42.85 % | 4.76 % | 38.09 % | 0.84
R-U | 0.42 | 0.55 | 34.03 | - | 76.19 % | 0.0 % | 0.19
R-R | 100.00 | 0.39 | 33.89 | - | - | - | 0.96
None | 0.54 | 20.59 | 33.65 | 0.0 % | 0.0 % | 0.0% | 0.925

Table 5: Analysis of Models trained using different Corpus-level Noise
Patterns: De-En

Noise | IRS-BLEU | VRS–BLEU | Test–BLEU | IRS NH | IRS OH | IRS Repeats | IRS Unique-Bigrams
---|---|---|---|---|---|---|---
U-U | 0.25 | 13.26 | 28.61 | 14.28 % | 0.0 % | 0.0 % | 0.91
U-R | 0.42 | 12.15 | 27.93 | 9.52 % | 0.0 % | 9.52 % | 0.95
R-U | 0.35 | 0.56 | 28.67 | - | 47.61 % | 0.0 % | 0.49
R-R | 100.00 | 0.50 | 28.54 |  | - | - | 0.99
None | 2.06 | 14.62 | 28.33 | 0.0 % | 0.0 % | 0.0% | 0.95

Table 6: Analysis of Models trained using different Corpus-level Noise
Patterns: En-De Figure 5: Frequency for the Top 5 Bigrams in the Output for
the IRS for the different noisy models on IWSLT 2014 En-De (Table 6).

(a)

Figure 6: Attention Visualization for translation of source in Figure 4, on
which the UR model hallucinates (right), compared against the model with no
noise (left). The right attention map displays the characteristic
hallucination pattern Lee et al. (2018); Berard et al. (2019); Voita et al.
(2020). The source is not present in the training corpus for the UR model.
However, source sequences from the same domain (WMT corpus) are present with
invalid references.

##### Results

Tables 5 and 6 show the results for both the De-En and the En-De translation
directions. The boxes marked with ‘-’ are the cases where the associated
metric computation does not convey any useful information. We see the
following patterns in the results:

  1. 1.

The Test-BLEU is not greatly affected by the noise, except in the UR case,
with the models matching the baseline (trained with no noise).

  2. 2.

When we consider the IRS-BLEU, we find that the RR model has fully memorized
this data. This is to be expected as it has seen this set repeated 1000 times.

  3. 3.

On the IRS set, the UR model produces a number of repeated outputs (IRS
Repeats) from the training corpus.

  4. 4.

On the IRS set, the RU model produces a very high percentage of oscillatory
hallucinations (OH).

##### Linking Hallucination Patterns to Noise Patterns

The main purpose of the above experiments is to demonstrate how natural
hallucinations can be generated on source sequences seen or unseen during
training, and their relation to specific noise types. The link between noise
patterns and specific types of hallucinations in the output could be used as
very effective diagnostic tool to trace hallucinated outputs to corpus-level
noise, with the goal of removing the noise from the training dataset.

In this regard, two important observations further emerge from Tables 5 and 6.
First, that in the case of UR noise, a considerable percentage of natural
hallucinations (IRS NH) manifests as a direct copy of a training reference
(without any of the IRS source sequences being present in the training set).
Second, for the case of RU noise, oscillatory hallucinations (OH) are very
prominent, as evident by the number IRS Unique-Bigrams, which are considerably
lower when compared to the other noise types. Figure 5 presents the
comparisons for counts of the top 5 bigrams present in the translations of the
IRS set, showing how among the 4 noise patterns, RU leads to the most
oscillatory hallucinations. Resulting sets of translations for a source
sequence present in the IRS is shown in Figure 4, while Figure 6 presents a
qualitative comparison of the attention patterns for this source sequence.

##  5 Hallucination Amplification

In this section, we analyze how hallucinations caused due to corpus-level
noise get amplified when a model trained on a noisy MT corpus is used for
downstream data generation in algorithms such as Sequence-level Knowledge
Distillation (KD) Kim and Rush (2016) and Backtranslation (BT) Edunov et al.
(2018). To analyze this, we need to compute NH at scale. So, firstly, we
propose an automatic NH detection algorithm based on the analysis that
hallucinations often occur in terms of oscillations or repeats of the target
sequences.

Data: Source S, Multi-lingual Similarity Scoring Model X, NMT Model M, Noise
Estimate $\epsilon$, N-gram order $n$, Threshold $t$

Result: Approximate Natural Hallucinations ANH

$T$ = Decode the Source Sequences in $S$;

$S_{X}$ = Compute Cross-Lingual Similarity for $(T,S)$ ;

$F_{1}$ = Select Translations where the count of the top repeated $n$-gram in
the translation is greater than the count of top repeated source $n$-gram by
at least $t$ ;

$F_{2}$ = Select Translations in $T$ that are Paired with Multiple Unique
Sources ;

$S_{\epsilon}$ = Bottom $\epsilon$ percentage of samples in $S_{X}$ ;

$ANH$ = $(S_{\epsilon}\cap F_{1})\cup(S_{\epsilon}\cap F_{2})$

Algorithm 3 Corpus-level NH Estimator

The proposed NH Estimator (algorithm 3) is reference-free and works at the
corpus-level. One simplifying assumption used in algorithm 3 is that the
repeats are now computed on the translations generated over the source set
rather than on the training set (as in Tables 5 and 6 for the IRS-Repeats
metric). The motivation behind this assumption is that given a sufficiently
large source set, the translated output (if hallucinated as a direct copy of
one of the training set targets), will appear more than once in the decoded
set (since UR noise is one of its causes).

###  5.1 Experiments and Results

We use algorithm 3 to measure NH caused by using the models trained on the
noisy corpora (as explored in section 4.2 and analyzed in Tables 5 and 6) for
BT and Sequence-level KD. For BT, we use 1 million English sentences from the
WMT 17 De-En dataset as the monolingual corpus and generate back-translations
via sampling Edunov et al. (2018), using the different types of noisily
trained models (RR, UU, UR, RU) for En-De. For constructing a sequence-level
KD dataset we generate the translations over the initial IWSLT 2014 De-En
corpus training corpus (the initial parallel data, with no noise) with a beam
size of 5 Kim and Rush (2016). The results of applying the NH estimator (with
$\epsilon=1$, i.e. 1%, $n=4$, $t=2$ and LASER as the cross-lingual similarity
scoring Model $M$ Artetxe and Schwenk (2019)) on the outputs generated using
KD and BT are presented in Table 7 and Table 8 respectively.

Data-Type | $F_{1}$ | $F_{2}$ | $S_{\epsilon}\cap F_{1}$ | $S_{\epsilon}\cap F_{2}$ | $ANH$
---|---|---|---|---|---
Parallel | 17 | 1900 | 0 | 41 | 41
KD-None | 17 | 2310 | 0 | 120 | 120
KD-UU | 17 | 2394 | 1 | 118 | 119
KD-UR | 30 | 3090 | 0 | 688 | 688
KD-RU | 24 | 2365 | 2 | 122 | 124
KD-RR | 29 | 2411 | 1 | 135 | 136

Table 7: Hallucination Amplification for Knowledge Distillation Kim and Rush
(2016)

Data-Type | $F_{1}$ | $F_{2}$ | $S_{\epsilon}\cap F_{1}$ | $S_{\epsilon}\cap F_{2}$ | $ANH$
---|---|---|---|---|---
BT-UU | 154 | 7592 | 0 | 5009 | 5009
BT-UR | 43 | 176184 | 0 | 7280 | 7280
BT-RU | 56 | 67 | 1 | 2 | 3
BT-RR | 62 | 65 | 1 | 11 | 12

Table 8: Hallucination Amplification for Backtranslation Edunov et al. (2018)

We find that the UR models lead to severe amplifications for both BT and KD.
For KD, we find that all noisy models lead to increase in NH when compared to
the initial parallel corpus (implying amplification), which itself contains a
non-trivial number of repeated targets. For BT, both UU and UR models lead to
large number of repeated generations. RR models however cause the least
hallucinations for both KD and BT. Our proposed NH estimator is not able to
detect many OH however, in any of the cases due to very little overlap with
the bottom $\epsilon=1\%$ similarity scores, even though the $F_{1}$ column
indicates amplification of translations with repeated n-gram patterns ($F_{1}$
) in the KD datasets.

Further, since, there is hallucination amplification going from a parallel
corpus to the KD data generated (using noisy models trained on the parallel
corpus), downstream systems trained on the KD data will be impacted in terms
of hallucinations as well. We leave further downstream analysis to future
work.

MV | Source | Target
---|---|---
0.61 | gerade plus gerade : gerade . ungerade plus ungerade : gerade . | even plus even gives you even . odd plus odd gives you even .
0.65 | also ist 2 $\wedge$ 5 : 2 x 2 = 4 , 8 , 16 , 32 . | so 2 $\wedge$ 5 is 2 x 2 = 4 , 8 , 16 , 32 .
0.69 | beweg dich ! nein ! beweg dich ! nein ! beweg dich ! nein ! | move . no . move . no . move . no .
0.82 | frau : sie bestanden darauf , ich würde lügen . | they insisted that i was lying .
0.94 | mjam , mjam , mjam , mjam , mjam . | gobble , gobble , gobble , gobble , gobble .

Table 9: Examples of Samples from the Top-100 Most Memorized Samples in the
Training Set as measured using the Memorization Value (MV) Estimator
(Algorithm 1) with chrF as the Metric: De-En.

##  6 Discussion

In this section, we present a qualitative analysis of a few topics discussed
in section 4, along with a discussion on some future research directions.

###  6.1 Memorized Samples

Table 9 presents some examples from the most memorized training samples,
thereby representing the samples from the long-tail of the data that is likely
to have been memorized by the model. Qualitatively, the examples appear to be
different (in terms of source/target syntax) from a random subset of training
samples (e.g. in Appendix A, Table 10), although we leave further quantitative
analysis of the differences to future work. Similarly, the link between out-
of-domain and memorized samples needs to be ascertained quantitatively.

###  6.2 Preventing Hallucinations

In this subsection, we discuss a few methods that could be effective in
preventing hallucinations.

##### Data-Augmentation

To prevent hallucinations under perturbation resulting from memorization of
the samples in the long-tail of the dataset Feldman (2020), a simple iterative
solution could be to analyze the long-tail (using Algorithm 1), and implement
data-augmentations specific to the characteristics of such samples (e.g. as in
Table 9), with the goal of bringing such samples out of the long-tail Raunak
et al. (2020). Further work is required to determine the dynamics of such
transition.

##### Ameliorating Memorization During Learning

Robust learning algorithms e.g. Robust Early learning Xia et al. (2021) that
are designed to prevent memorization specifically are likely to prevent
perturbation based hallucinations.

##### Robust Learning on Noisy Samples

Kang and Hashimoto (2020) propose a loss-truncation approach to reduce the
impact of noisy references in sequence-to-sequence training, using the
intermediate model’s loss as a sample quality estimator and test their
algorithm on a summarization task. Li et al. (2021) present a modification to
Expected Risk Minimization (ERM), namely Tilted-ERM to reduce the impact of
outliers during training. Such techniques could be useful in increasing
learning robustness to corpus-level noise in NMT as well.

##### Corpus-Level Filtering

Incorporating heuristics or filters Junczys-Dowmunt (2018); Zhang et al.
(2020) to remove invalid source-target pairs, especially the noise patterns
explored in section 4.2 (or to remove bitext indeterminacy in general) could
be effective in reducing natural hallucinations.

##  7 Conclusion

In this work we demonstrated that memorized training samples are far more
likely to hallucinate under perturbation than non-memorized samples, under an
extension of the Memory Value Estimator proposed in Feldman and Zhang (2020).
We also showed that specific noise patterns in the training corpora lead to
specific well-known hallucination patterns. Finally, we demonstrated that
these patterns can be amplified by popular data-generation processes such as
backtranslation and sequence-level knowledge distillation.

Due to the compute-intensive algorithms involved in our analysis, we conduct
most of our experiments using the IWSLT 2014 corpus. However, long-tailed
phenomena are a characteristic of natural language and even scaling the size
of the corpus doesn’t alleviate the characteristic Zipfian distribution of the
occurrence of words/tokens in the NMT corpora; which, according to the central
thesis of the long-tail theory Feldman (2020), would lead to memorizations.
Similarly, noise in the form of invalid references is an artifact of the scale
at which web-based corpora are collected and given that both hallucinations
under perturbations and natural hallucinations are widely reported in large-
scale NMT systems, our insights should be directly applicable to larger-scale
models as well.

We hope that our work serves as a useful step towards a detailed understanding
of hallucinations in NMT and in other sequence to sequence models. Among the
numerous interesting directions for follow-up work, in future, we would like
to explore learning-centric fixes to ameliorate the impact of memorization and
corpus-level noise patterns in NMT training.

## References

  * Artetxe and Schwenk (2019) Mikel Artetxe and Holger Schwenk. 2019.  Massively Multilingual Sentence Embeddings for Zero-Shot Cross-Lingual Transfer and Beyond.  _Transactions of the Association for Computational Linguistics_ , 7:597–610.
  * Banerjee and Lavie (2005) Satanjeev Banerjee and Alon Lavie. 2005.  METEOR: An automatic metric for MT evaluation with improved correlation with human judgments.  In _Proceedings of the ACL Workshop on Intrinsic and Extrinsic Evaluation Measures for Machine Translation and/or Summarization_ , pages 65–72, Ann Arbor, Michigan. Association for Computational Linguistics.
  * Berard et al. (2019) Alexandre Berard, Ioan Calapodescu, and Claude Roux. 2019.  Naver labs Europe’s systems for the WMT19 machine translation robustness task.  In _Proceedings of the Fourth Conference on Machine Translation (Volume 2: Shared Task Papers, Day 1)_ , pages 526–532, Florence, Italy. Association for Computational Linguistics.
  * Cheng et al. (2019) Yong Cheng, Lu Jiang, and Wolfgang Macherey. 2019.  Robust neural machine translation with doubly adversarial inputs.  In _Proceedings of the 57th Annual Meeting of the Association for Computational Linguistics_ , pages 4324–4333, Florence, Italy. Association for Computational Linguistics.
  * Edunov et al. (2018) Sergey Edunov, Myle Ott, Michael Auli, and David Grangier. 2018.  Understanding back-translation at scale.  In _Proceedings of the 2018 Conference on Empirical Methods in Natural Language Processing_ , pages 489–500, Brussels, Belgium. Association for Computational Linguistics.
  * Feldman (2020) Vitaly Feldman. 2020.  Does learning require memorization? a short tale about a long tail.  In _Proceedings of the 52nd Annual ACM SIGACT Symposium on Theory of Computing_ , STOC 2020, page 954–959, New York, NY, USA. Association for Computing Machinery.
  * Feldman and Zhang (2020) Vitaly Feldman and Chiyuan Zhang. 2020.  What neural networks memorize and why: Discovering the long tail via influence estimation.  _Advances in Neural Information Processing Systems_ , 33.
  * Junczys-Dowmunt (2018) Marcin Junczys-Dowmunt. 2018.  Dual conditional cross-entropy filtering of noisy parallel corpora.  In _Proceedings of the Third Conference on Machine Translation: Shared Task Papers_ , pages 888–895, Belgium, Brussels. Association for Computational Linguistics.
  * Kang and Hashimoto (2020) Daniel Kang and Tatsunori Hashimoto. 2020.  Improved natural language generation via loss truncation.  In _Proceedings of the 58th Annual Meeting of the Association for Computational Linguistics_ , pages 718–731, Online. Association for Computational Linguistics.
  * Kim and Rush (2016) Yoon Kim and Alexander M. Rush. 2016.  Sequence-level knowledge distillation.  In _Proceedings of the 2016 Conference on Empirical Methods in Natural Language Processing_ , pages 1317–1327, Austin, Texas. 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.
  * Lee et al. (2018) Katherine Lee, Orhan Firat, Ashish Agarwal, Clara Fannjiang, and David Sussillo. 2018.  Hallucinations in neural machine translation.  In _NIPS 2018 Interpretability and Robustness for Audio, Speech and Language Workshop_.
  * Li et al. (2021) Tian Li, Ahmad Beirami, Maziar Sanjabi, and Virginia Smith. 2021.  Tilted empirical risk minimization.  In _International Conference on Learning Representations_.
  * Martindale et al. (2019) Marianna Martindale, Marine Carpuat, Kevin Duh, and Paul McNamee. 2019.  Identifying fluently inadequate output in neural and statistical machine translation.  In _Proceedings of Machine Translation Summit XVII Volume 1: Research Track_ , pages 233–243, Dublin, Ireland. European Association for Machine Translation.
  * Müller et al. (2020) Mathias Müller, Annette Rios, and Rico Sennrich. 2020.  Domain robustness in neural machine translation.  In _Proceedings of the 14th Conference of the Association for Machine Translation in the Americas (Volume 1: Research Track)_ , pages 151–164, Virtual. Association for Machine Translation in the Americas.
  * 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 (Demonstrations)_ , pages 48–53, Minneapolis, Minnesota. Association for Computational Linguistics.
  * 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_ , pages 311–318, Philadelphia, Pennsylvania, USA. 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.
  * Raunak et al. (2020) Vikas Raunak, Siddharth Dalmia, Vivek Gupta, and Florian Metze. 2020.  On long-tailed phenomena in neural machine translation.  In _Findings of the Association for Computational Linguistics: EMNLP 2020_ , pages 3088–3095, Online. Association for Computational Linguistics.
  * 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.
  * 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 (Volume 1: Long Papers)_ , pages 1715–1725, Berlin, Germany. Association for Computational Linguistics.
  * Tu et al. (2016) Zhaopeng Tu, Zhengdong Lu, Yang Liu, Xiaohua Liu, and Hang Li. 2016.  Modeling coverage for neural machine translation.  In _Proceedings of the 54th Annual Meeting of the Association for Computational Linguistics (Volume 1: Long Papers)_ , pages 76–85, Berlin, Germany. Association for Computational Linguistics.
  * Ugawa et al. (2018) Arata Ugawa, Akihiro Tamura, Takashi Ninomiya, Hiroya Takamura, and Manabu Okumura. 2018.  Neural machine translation incorporating named entity.  In _Proceedings of the 27th International Conference on Computational Linguistics_ , pages 3240–3250, Santa Fe, New Mexico, USA. Association for Computational Linguistics.
  * Voita et al. (2020) Elena Voita, Rico Sennrich, and Ivan Titov. 2020.  Analyzing the source and target contributions to predictions in neural machine translation.  _arXiv preprint arXiv:2010.10907_.
  * Wang and Sennrich (2020) Chaojun Wang and Rico Sennrich. 2020.  On exposure bias, hallucination and domain shift in neural machine translation.  In _Proceedings of the 58th Annual Meeting of the Association for Computational Linguistics_ , pages 3544–3552, Online. Association for Computational Linguistics.
  * Xia et al. (2021) Xiaobo Xia, Tongliang Liu, Bo Han, Chen Gong, Nannan Wang, Zongyuan Ge, and Yi Chang. 2021.  Robust early-learning: Hindering the memorization of noisy labels.  In _International Conference on Learning Representations_.
  * Zhang et al. (2020) Boliang Zhang, Ajay Nagesh, and Kevin Knight. 2020.  Parallel corpus filtering via pre-trained language models.  In _Proceedings of the 58th Annual Meeting of the Association for Computational Linguistics_ , pages 8545–8554, Online. Association for Computational Linguistics.
  * Zhang et al. (2019) Tianyi Zhang, Varsha Kishore, Felix Wu, Kilian Q Weinberger, and Yoav Artzi. 2019\.  Bertscore: Evaluating text generation with bert.  In _International Conference on Learning Representations_.

##  Appendix A Appendices

Table 10 presents some random samples from the lower-end of the memorization
values. The sentences differ in terms of their syntactic properties (versus
Table 9 in section 6.1), although more analysis is required to quantitatively
ascertain the differences.

MV | Source | Target
---|---|---
0.0 | sie haben das gleiche gehirn , und das gleiche eeg . | they have the same brain , and the same eeg .
0.08 | und wir hatten keine ahnung , wo er war . | it looks like the technological problem is solved .
0.25 | also , die wiederbesiedlung ist wirklich sehr langsam . | so , recolonization is really very slow .
0.30 | zum einen waren beide sehr real . | for one thing , both were very real .
0.50 | wir überqueren auf alu-leitern mit angefügten sicherheits-seilen . | we cross on aluminum ladders with safety ropes attached .

Table 10: Examples of Samples with Memorization Value (MV) between 0.0 and 0.6
(Below Top-100) from the Training Set as measured using the Memorization Value
(MV) Estimator (Algorithm 1) with chrF as the Metric: De-En.