# An Advantage Using Feature Selection with a Quantum Annealer

Andrew Vlasic<EMAIL_ADDRESS>Deloitte Consulting, LLP  Hunter Grant
Deloitte Consulting, LLP  Salvatore Certo  Deloitte Consulting, LLP

###### Abstract

Feature selection is a technique in statistical prediction modeling that
identifies features in a record with a strong statistical connection to the
target variable. Excluding features with a weak statistical connection to the
target variable in training not only drops the dimension of the data, which
decreases the time complexity of the algorithm, it also decreases noise within
the data which assists in avoiding overfitting. In all, feature selection
assists in training a robust statistical model that performs well and is
stable. Given the lack of scalability in classical computation, current
techniques only consider the predictive power of the feature and not
redundancy between the features themselves. Recent advancements in feature
selection that leverages quantum annealing (QA) gives a scalable technique
that aims to maximize the predictive power of the features while minimizing
redundancy. As a consequence, it is expected that this algorithm would assist
in the bias/variance trade-off yielding better features for training a
statistical model. This paper tests this intuition against classical methods
by utilizing open-source data sets and evaluate the efficacy of each trained
statistical model well-known prediction algorithms. The numerical results
display an advantage utilizing the features selected from the algorithm that
leveraged QA.

##  I Introduction

This manuscript gives a detailed numerical analysis of the efficacy of the
quantum feature selection algorithm mucke2022quantum  (QFS) against the
features selected from the ANOVA F-test dhanya2020f  and the features selected
from the chi-squared statistic jin2015chi . Efficacy determined through the
evaluation of the statistical models trained from each set of selected
features. Three different data sets are applied and the outputs from each
feature selection algorithm are then fed into standard algorithms that train a
statistical prediction model. The evaluations of the statistical models are
then aggregated and analyzed. Consistently it is shown that the features
selected by QFS yield higher performing and stable statistical models.

Recent advancements in classical computing has allowed for an exponential
growth in statistical predictive modeling within academia as well as industry.
The increased computational capacity of classical computers has also
proliferated the collection data, resulting in a vast sets of data that is
rich is information. However, the incorrect utilization of this information
has the potential to add noise to the training of a statistical model. For
instance, take the task of statistically modeling fraud belhadji2000model .
Within this paper it was shown that only half of the features were useful in
predicting fraud. In all, the current size and dimensionality of information
has necessitated the need for analyzing the data to decrease noise and
collinearity of features dormann2013collinearity ; gupta2019dealing .

Two well-applied feature selection methods are the ANOVA F-test and chi-
squared statistics. While these two statistical measures have been well-used,
the methods only consider the statistical strength between the features and
the target variable. In particular, while these methods can decrease noise in
the independent variables, they do not decrease redundant information, which
has the potential to create a biased statistical model since the algorithm is
only given relevant information to derive a model; see li2008method ;
kalnins2018multicollinearity ; danasingh2020identifying ; zhao2019maximum ;
grillo2021redundancy  for a comprehensive view.

The feature selection algorithm QFS is a quadratic unconstrained binary
optimization (QUBO) problem that finds the appropriate weight for the linear
terms, which is the signal between a feature and the target variable, and the
appropriate weight for the quadratic terms, the shared information between
each feature. This algorithm separates the signal from the noise by
identifying the features with a strong statistical connection with the target
variable while not including other features that, while having similarly
strong statistical connections with the target variable, also have redundant
information that is already captured by other features.

While the QUBO described in the paper mucke2022quantum  can be solved with
classical computational methods with a small number of features, as the number
of features increase, which increases the quadratic terms in a factorial
manner, it becomes progressively difficult for these methods to find solutions
in a reasonable time. Unlike many other problem formulations in operations
research, this application is a natural quadratic programming problem and
quantum annealers (QA) are natural tools to use since QA scales well as the
number of binary variables grow albash2018adiabatic ; albash2018demonstration
. For the application of feature selection see nembrini2021feature ;
von2021quantum .

##  II Methods

###  II.1 Data, Correlation, and Pseudo-Distance Metric

Define the data set as $\big{\\{}(x_{i},y_{i})\big{\\}}_{i=1}^{N}$, where
$x_{i}\in\mathbb{R}^{n}$ and $y_{i}\in\mathbb{R}^{m}$ for all $i$. We call
$\mathbf{y}:=\\{y_{i}\\}_{i=1}^{N}$ the target variable,
$\mathbf{x}:=\\{x_{i}\\}_{i=1}^{N}$ dependent variables, and for the vectors
of the dependent variables, $x_{i}=(x_{i}^{1},x_{i}^{2},\ldots,x_{i}^{n})$,
the set $\mathbf{x}_{i}:=\\{x_{i}^{j}\\}_{i=1}^{N}$ for each $j=1,\ldots,n$ is
called a feature.

Given a record of data, denote $I_{i}:=I(\mathbf{x}_{i};\mathbf{y})$ is a
scalar that captures the amount of information shared between feature
$\mathbf{x}_{i}$ and the target variable. Similarly, denote
$R_{ij}:=I(\mathbf{x}_{i},\mathbf{x}_{j})$ as a scalar that describes the
amount of information shared between feature $\mathbf{x}_{i}$ and feature
$\mathbf{x}_{j}$. While the statistical method in $I_{i}$ and $R_{ij}$ are the
same, the difference in notation is given to delineate the linear terms and
quadratic terms in the QUBO derived in Subsection II.2.

This statistic in general can be Spearman correlation, mutual information,
chi-squared statistic, ANOVA F-test, or any other statistical measure
appropriate for the given data set. The methods applied in this analysis to
the quantum feature selection are Spearman correlation and mutual information,
and the methods applied to the classical methods are chi-squared statistic and
ANOVA F-test.

Spearman correlation is a rank order correlation statistic that enables the
comparison of continuous or discrete random variables. Denote $R(\mathbf{x})$
as the random variable $\mathbf{x}$ converted to rank,
$\mbox{cov}(\cdot,\cdot)$ as the covariance, and $\sigma$ as the standard
deviation, then the Spearman coefficient is

$r_{s}=\frac{\mbox{cov}(R(\mathbf{x}),R(\mathbf{y}))}{\sigma_{R(\mathbf{x})}\sigma_{R(\mathbf{y})}}.$

Mutual information (MI) is an information theoretic pseudo-metric that
leverages probability measures to calculate the shared information by
calculating the dependency. The random variables could be continuous or
discrete valued. For probability measure $P$, MI has the mathematical form

$\mbox{MI}(\mathbf{x},\mathbf{y})=\sum_{x,y}P(x,y)\ln\left(\frac{P(x,y)}{P(x)P(y)}\right).$

The chi-squared statistic is defined as

$\chi^{2}=\sum_{i}\frac{(O_{i}-E_{i})^{2}}{E_{i}}$

where $E_{i}$ is the expected number and $O_{i}$ is the observed number. Chi-
squared statistic was derived for discrete random variables. However, if the
target is discrete then applications with continuous valued features is
possible, such as Pearson correlation can be applied to the discrete random
variable of years old and extract a meaningful correlation statistic.

Finally, ANOVA F-test is a means to assess whether the expected values of the
general defined groups are different from another. The mathematical
formulation is as follows,

$f_{t}=\sum_{i=1}^{K}\sum_{j=1}^{n_{i}}\frac{(Y_{ij}-\bar{Y}_{i})^{2}}{N-K}$

where $\bar{Y}_{i}$ is the mean in the $i^{th}$-group, $Y_{ij}$ is the
$j^{t}h$ observation in the $i^{th}$-group, $K$ denotes the number of groups,
and $N$ is the size of the data record.

Figure 1: Analysis of the Wafer data set where (a) is the accuracy of each
classifier and (b) is the $f1$ score

###  II.2 QUBO Derivation

Quantum Feature Selection can be formulated as a combinatorial optimization
problem, specifically as a QUBO. For the QUBO, denote $b_{i}$ as a binary
variable that is $1$ if feature $i$ is selected for inclusion and $0$
otherwise. Now, defining $\mathbf{b}=(b_{1},\ldots,b_{n})$ and
$||\mathbf{b}||_{1}=\sum_{i=1}^{n}b_{i}$, for a given number of features, say
$k$, the QUBO has the form

$\operatorname*{arg\,min}_{\mathbf{b},\
||\mathbf{b}||_{1}=k}=-\alpha\cdot\sum_{i=1}^{n}I_{i}b_{i}+\big{(}1-\alpha\big{)}\cdot\vspace{-5pt}\sum_{i,j=1,\
i\neq j}^{n}R_{ij}b_{i}b_{j}.$ (1)

We follow the technique in mucke2022quantum  where we utilize a binary search
algorithm to find the optimal value of $\alpha$ to arrive at the targeted
number of features. $\alpha$ is an intuitive and natural way to control the
number of features: a value of close to $1$ will select all features with some
level of predictive power, and a value close to $0$ will only select the small
number of features that possess completely unique amounts of information not
found in any other feature. While the optimal value of alpha will differ
depending on the data set and information metric used, the binary search
algorithm outlined in mucke2022quantum  provides a clear and efficient way for
attaining that value with a small number of iterations.

However, given the number of iterations required for this algorithm,
utilization of a quantum annealer processor, such as the processor developed
by D-wave Dwave , has allowed this algorithm to be efficiently run in a timely
manner with respect to the number of features.

###  II.3 Data and Experimentation

The data sets applied in the analysis were the p53 mutants data set (denoted
as P53) and the relative location of CT slices on axial axis data set (dented
as CT) from the UCI Machine Learning Repository Dua:2019 , and the data set
for the Detecting Anomalies in Wafer Manufacturing111
https://www.kaggle.com/datasets/arbazkhan971/anomaly-detection (denoted as
Wafer) Kaggle competitions.

As noted in the Subsection II.1, the ANOVA F-test and chi-squared statistic
are the two classical features selection algorithms. For a general basis for
comparison, the entire data set is also applied to each model. Features
selected by the quantum feature selection algorithm are denoted by QFS,
features selected by ANOVA F-test are denoted by F Test, and features selected
by the chi-squared statistic is denoted by Chi-Squared. When the entire record
of data is applied it is denoted by Original Data.

For robust testing, the following classification models are applied: decision
trees, random forests, logistic regression, and k-nearest neighbors, see
bonaccorso2017machine  for more information. The classifiers selected for the
analysis sample techniques from clustering, weak learners, and kernel-like
methods. For regression, decision tree regressor, random forest regressor,
Adaboost regressor, and k-nearest neighbors regressor algorithms were applied.
For the modeling analysis a $5$-fold sampling of the data is taken and the
results are averaged for each respective algorithm.

All algorithms applied in the analysis, including preprocessing the data, were
written in Python and taken from the Scikit-Learn library pedregosa2011scikit
.

##  III Numerical Analysis

The first data set considered is Wafer. There are 1763 data points, 1558
features, and 143 data points identifying a defect. This is an approximate
ratio of 11:1 with the classes. The features are a mixture of continuous and
binary variables. The data was not pre-processed, aside from randomly sampling
the data and splitting it into the train, validation and test sets. With this
ratio of the classes a low $f1$ score is expected. Adjustments for the class
imbalance was not implemented before training the statistical model in order
to not incorporate unintended bias. Lastly, mutual information was utilized as
the statistical measure for QFS.

For this analysis 100 features were identified from each feature selection
method. Aggregating the results of model performance, QFS had a slight
advantage over the classical methods, and for model stability QFS had a clear
advantage. For more granular analysis Figure 1 displays the outcomes for each
classification algorithm.

Figure 2: Analysis of the P53 data set where (a) is the average accuracy of
each method with respect to the number of features, and (b) is the average
$f1$ score of each method with respect to the number of features.

For the P53 data set the analysis is extended to include 50 features, 100
features, and 150 features. The extended analysis was motivated by the number
of features of the data, which are a total of 5408 features. The P53 data set
had a total of 31,420 data points with 151 identified instances of the
mutation, giving the approximate class ratio of 205:1. The features are a
mixture of continuous and binary variables.

Method | Average Accuracy | Average $f1$ Score
---|---|---
QFS | 0.889 | 0.509
F Test | 0.889 | 0.471
Chi-Squared | 0.877 | 0.482
Original Data | 0.832 | 0.426
Table 1: This table are the aggregated results of the Wafer data set, where
the best scores are highlighted in red.

Following t he same process as the Wafer data set, including using mutual
information as the statistical measure, the aggregated results display an
advantage with the QFS technique when 50 features are selected; the results
are aggregated with number of features are displayed in Figure 2. However, the
features selected by the QFS algorithm do not perform as well as the classical
methods. Interestingly, there is a noticeable decrease in the average model
performance and average model stability from each respective increase in the
number of features, not including the classical methods average $f1$ score
from 50 to 100 hundred features and the average $f1$ score of QFS from 100 to
150 features, which remains the same. While there is an increase in model
stability from 50 to 100 features for the classical methods, there is a
significant decrease from 100 to 150 features. These results indicate noise in
the data and hint at an optimal number of features to select. Moreover, the
lack of model stability from the features selected by QFS could stem from the
mutual information statistic that focuses more on the majority class, and
other statistical methods may increase the discovering the signal from the
noise. Finally, from the stability of the $f1$ scores for QFS from 100 to 150
features it appears that algorithm did pick up on the noise but then minimized
the impact.

Lastly, for the CT data set, 170 features and 240 features were selected. this
data set has 384 features, 53,500 data points, where the features are a mix of
continuous and nominal. The target variable is continuous.

Given the more complicated task of regression, for the classical feature
selection algorithms ANOVA F-test and mutual information were chosen. Just as
before, ANOVA F-test is denoted as F-test and mutual information is denoted as
MI. For QFS, mutual information and Spearman rank correlation were
independently applied to obtain statistical information and QFS was ran to
compare both techniques. These are denoted as QFS MI and QFS SC, respectively.

Figure 3 displays the average root mean square error for 170 features and 240
features selected, respectively. Except for k-neighbors regressor algorithm,
unlike the classification statistical modeling, the entire data set out-
performed each feature selection method. However, with the k-neighbor
regressor the QFS MI selection algorithm not only out-performed the original
data, (although, not by much), this regression model out-performed all of
models. Moreover, the regression models trained by the 170 features selected
by QFS out-performed all of the other respective regression models trained
with the other selected 170 features, as well as be competitive with the
performance of the regression models trained with all of the data.

The the algorithms for the regression were identified a priori and chosen for
their simplicity. Given that the k-neighbor regressor performed the best, as
well as poor performance for all statistical models, this suggested more
complexity algorithms to apply the regression is required for higher
performing and more robust predictor.

Figure 3: Analysis of the CT data set where (a) average root mean square error
and error bar with 170 features selected, and (b) average root mean square
error and error error bar with 240 features selected.

Interestingly, the performance of the regression models trained with 240
selected with the QFS MI algorithm drops. Moreover, for each training
algorithm with 240 features selected, excluding the models trained with all of
the data, the top performing respective regression model is not clear. For
instance, the 170 features selected by the QFS SC algorithm performs poorly
across all training algorithms, and in contrary, with 240 features QFS SC is
competitive with all of the data applying the decision tree regression
algorithm. This indicates there is a lot more noise in the data which appears
to average out when all of the data is utilized for training.

##  IV Discussion

Through numerical analysis it was demonstrated that, on average, the features
select by the QFS algorithm enabled the training of models more stable than
the features selected from the classical techniques. Moreover, the results
demonstrate the need to consider other statistical techniques, including
mixing techniques and averaging techniques contingent on the data quality and
feature type, to assist further separating the signal from the noise. However,
mutual information was numerically demonstrated to do well as a statistical
measure of shared information.

##  V Disclaimer

About Deloitte: Deloitte refers to one or more of Deloitte Touche Tohmatsu
Limited (“DTTL”), its global network of member firms, and their related
entities (collectively, the “Deloitte organization”). DTTL (also referred to
as “Deloitte Global”) and each of its member firms and related entities are
legally separate and independent entities, which cannot obligate or bind each
other in respect of third parties. DTTL and each DTTL member firm and related
entity is liable only for its own acts and omissions, and not those of each
other. DTTL does not provide services to clients. Please see
www.deloitte.com/about to learn more.

Deloitte is a leading global provider of audit and assurance, consulting,
financial advisory, risk advisory, tax and related services. Our global
network of member firms and related entities in more than 150 countries and
territories (collectively, the “Deloitte organization”) serves four out of
five Fortune Global 500® companies. Learn how Deloitte’s approximately 330,000
people make an impact that matters at www.deloitte.com. This communication
contains general information only, and none of Deloitte Touche Tohmatsu
Limited (“DTTL”), its global network of member firms or their related entities
(collectively, the “Deloitte organization”) is, by means of this
communication, rendering professional advice or services. Before making any
decision or taking any action that may affect your finances or your business,
you should consult a qualified professional adviser. No representations,
warranties or undertakings (express or implied) are given as to the accuracy
or completeness of the information in this communication, and none of DTTL,
its member firms, related entities, employees or agents shall be liable or
responsible for any loss or damage whatsoever arising directly or indirectly
in connection with any person relying on this communication. Copyright © 2022.
For information contact Deloitte Global.

## References

  * [1] Sascha Mücke, Raoul Heese, Sabine Müller, Moritz Wolter, and Nico Piatkowski.  Quantum feature selection.  arXiv preprint arXiv:2203.13261, 2022.
  * [2] R Dhanya, Irene Rose Paul, Sai Sindhu Akula, Madhumathi Sivakumar, and Jyothisha J Nair.  F-test feature selection in stacking ensemble model for breast cancer prediction.  Procedia Computer Science, 171:1561–1570, 2020.
  * [3] Chuanxin Jin, Tinghuai Ma, Rongtao Hou, Meili Tang, Yuan Tian, Abdullah Al-Dhelaan, and Mznah Al-Rodhaan.  Chi-square statistics feature selection based on term frequency and distribution for text categorization.  IETE journal of research, 61(4):351–362, 2015.
  * [4] El Bachir Belhadji, George Dionne, and Faouzi Tarkhani.  A model for the detection of insurance fraud.  The Geneva Papers on Risk and Insurance-Issues and Practice, 25(4):517–538, 2000.
  * [5] Carsten F Dormann, Jane Elith, Sven Bacher, Carsten Buchmann, Gudrun Carl, Gabriel Carré, Jaime R García Marquéz, Bernd Gruber, Bruno Lafourcade, Pedro J Leitão, et al.  Collinearity: a review of methods to deal with it and a simulation study evaluating their performance.  Ecography, 36(1):27–46, 2013.
  * [6] Shivani Gupta and Atul Gupta.  Dealing with noise problem in machine learning data-sets: A systematic review.  Procedia Computer Science, 161:466–474, 2019.
  * [7] Longhai Li, Radford M Neal, and Jianguo Zhang.  A method for avoiding bias from feature selection with application to naive bayes classification models.  Bayesian Analysis, 3(1):171–196, 2008.
  * [8] Arturs Kalnins.  Multicollinearity: How common factors cause type 1 errors in multivariate regression.  Strategic Management Journal, 39(8):2362–2385, 2018.
  * [9] Asir Antony Gnana Singh Danasingh, Jebamalar Leavline Epiphany, et al.  Identifying redundant features using unsupervised learning for high-dimensional data.  SN Applied Sciences, 2(8):1–10, 2020.
  * [10] Zhenyu Zhao, Radhika Anand, and Mallory Wang.  Maximum relevance and minimum redundancy feature selection methods for a marketing machine learning platform.  In 2019 IEEE international conference on data science and advanced analytics (DSAA), pages 442–452. IEEE, 2019.
  * [11] Sebastián Alberto Grillo, José Luis Vázquez Noguera, Julio César Mello Román, Miguel García-Torres, Jacques Facon, Diego P Pinto-Roa, Luis Salgueiro Romero, Francisco Gómez-Vela, Laura Raquel Bareiro Paniagua, and Deysi Natalia Leguizamon Correa.  Redundancy is not necessarily detrimental in classification problems.  Mathematics, 9(22):2899, 2021.
  * [12] Tameem Albash and Daniel A Lidar.  Adiabatic quantum computation.  Reviews of Modern Physics, 90(1):015002, 2018.
  * [13] Tameem Albash and Daniel A Lidar.  Demonstration of a scaling advantage for a quantum annealer over simulated annealing.  Physical Review X, 8(3):031016, 2018.
  * [14] Riccardo Nembrini, Maurizio Ferrari Dacrema, and Paolo Cremonesi.  Feature selection for recommender systems with quantum computing.  Entropy, 23(8):970, 2021.
  * [15] David Von Dollen, Florian Neukart, Daniel Weimer, and Thomas Bäck.  Quantum-assisted feature selection for vehicle price prediction modeling.  arXiv preprint arXiv:2104.04049, 2021.
  * [16] C. McGeoch, P. Farre, and W. Bernoudy.  D-wave hybrid solver service and advantage: technology update.  Tech. Rep., D-Wave User Manual 09-1109A-V, 2020.
  * [17] Dheeru Dua and Casey Graff.  UCI machine learning repository, 2017.
  * [18] Giuseppe Bonaccorso.  Machine learning algorithms.  Packt Publishing Ltd, 2017.
  * [19] Fabian Pedregosa, Gaël Varoquaux, Alexandre Gramfort, Vincent Michel, Bertrand Thirion, Olivier Grisel, Mathieu Blondel, Peter Prettenhofer, Ron Weiss, Vincent Dubourg, et al.  Scikit-learn: Machine learning in python.  the Journal of machine Learning research, 12:2825–2830, 2011.


# MALM: Mixing Augmented Language Modeling for Zero-Shot Machine Translation

Kshitij Gupta
Department of Electrical and Electronics Engineering
BITS Pilani, Pilani Campus
Rajasthan, India
<EMAIL_ADDRESS>

###### Abstract

Large pre-trained language models have brought remarkable progress in NLP.
Pre-training and Fine-tuning have given state-of-art performance across tasks
in text processing. Data Augmentation techniques have also helped build state-
of-art models on low or zero resource tasks. Many works in the past have
attempted at learning a single massively-multilingual machine translation
model for zero-shot translation. Although those translation models are
producing correct translations, the main challenge is those models are
producing the wrong languages for zero-shot translation. This work and its
results indicate that prompt conditioned large models do not suffer from off-
target language errors i.e. errors arising due to translation to wrong
languages. We empirically demonstrate the effectiveness of self-supervised
pre-training and data augmentation for zero-shot multi-lingual machine
translation.

##  1 Introduction

Machine Translation is one of the classic problems in Natural Language
Processing(NLP). Several products like Google Translate, Bing Translate
provide services to millions of translation requests across a diversity of
language pairs. While the requests for these services come in almost all
language pairs imaginable, the quality of translation for low-resource
language pairs like German-Arabic is especially low. This is prompted due to a
lack of quality training data for such locale pairs compared to high-resource
languages like English-French etc.

Specifically, for few-shot machine translation, there have been many
successful techniques proposed. Zoph et al. (2016) demonstrated that transfer
learning from high-resource languages to low-resource languages can be used to
achieve remarkably high BLEU scores. Building on top of it, Gu et al. (2018)
showed that universal lexical representations achieve better alignment of
lexical and syntactic relations between languages. Similarly, (Fadaee et al.,
2017) have been successfully used to utilize computer vision leanings in
augmentation to low-resource translation.

Success due to techniques like transfer-learning, data augmentation, etc. has
also provided great progress in building large multi-lingual neural machine
translation models (Johnson et al., 2017). The objective here is to build a
single high-capacity model that is able to generate translations for any
language pair and can be trained at the same time. Zhang et al. (2021) have
used conditional specific language routing for achieving impressive
performance across low resource language pairs. Similar to this work, Xia et
al. (2019) utilized data augmentation strategies and Zhang et al. (2020) used
random online back translation to achieve state-of-the-art performance for
low-resource machine translation. In their work, Arivazhagan et al. (2019a)
encourage parameter sharing across language by implementing an auxiliary loss
function. Similarly, de-noising objective (Liao et al., 2021) and distillation
techniques (Sun et al., 2020) have also been shown to have boosted zero
translation learning.

Recently, research direction in massively multilingual translation models(MMT)
(Aharoni et al., 2019) has also been popularized to build zero-shot
translation systems. Arivazhagan et al. (2019b) provides a survey of
challenges associated with MMT models, while also emphasizing the importance
of preprocessing and vocabulary in knowledge transfer across language pairs.
Although, Gonzales et al. (2020) detail the lack of robustness of zero-shot
models across training runs, we do not notice it in our training runs and find
that augmentation techniques help stabilize the training process.

Neural models like Transformer (Vaswani et al., 2017) have brought significant
advances in tasks across NLP. Pre-trained language models like BERT (Devlin et
al., 2018), BART (Lewis et al., 2019), T5 (Raffel et al., 2019) have achieved
state-of-art performance across the NLP spectrum. Similarly, generative models
like GPT-2 (Brown et al., 2020) have shown few and zero-shot abilities on many
tasks. The wide success across tasks has not only been limited to high-
resource languages like English, and French but has indeed been shared with
low-resource languages like Azerbaijani, Belarussian, Galician, Urdu, etc
(Lakew et al., 2021). It has also brought significant progress in single large
multi-lingual models mBERT (Devlin et al., 2018), mBART (Liu et al., 2020),
mT5 (Xue et al., 2020) that learn universal representation across languages.
This is responsible for remarkable zero and few-shot performance across tasks
for languages that lack supervised training data.

In this paper, we will investigate language modeling pre-training and data
augmentation strategy for zero-shot translation Our work provides 2 major and
concise pieces of contributions:

  1. 1.

Prompt Conditioned models like mT5 do not suffer from off-target translation
and a language tag in the task prompt is sufficient for the model to generate
output in the right language.

  2. 2.

SeqMix style data augmentation technique on top of large pre-trained language
models like mT5 is a simple yet competitive approach against a strong baseline
on zero-shot translation.

##  2 Problem

We will first look at the challenge of off-target translation. For all the
zero-shot language pairs, we construct a random test dataset of 1000
examples111We choose 1000 as a good compromise across languages irrespective
of their original test size from the source language that may or may not be
part of the original test dataset. We then run the translation system over
those examples and identify all the output that corresponds to the wrong
target language.

Say, a translation model($M$) generates for data instances($x_{1}...x_{n}$)
translations as ($y^{\prime}_{1}...y^{\prime}_{n}$) and reference translations
as ($y_{1}...y_{n}$) for source language($s$) and target language($t$). Also,
given a language identification oracle as $L$, where $L(x)$ is the predicted
language $M$ for data instance$x$. In this work, we will utilize Salcianu et
al. (2016)’s Language Identification system to measure language performance.
We then describe off-target translation error rate(OTTER) as:

$OTTER(M)=\frac{\sum_{i}L(y^{\prime}_{i})\neq t}{\sum_{i}L(y_{i})=t}$ (1)

In the original paper, Zhang et al. (2020) used the accuracy of translation
language as a metric to compare. We argue that any language identification
system is noisy and thus accuracy on just translation output doesn’t take into
account errors of the language identification system. OTTER, on the other
hand, is a noisy measure that measures language accuracy over both reference
and translation output text of the translation system.

The main question that we investigate is improving the quality of zero-
resource translation. The problem at hand is learning a single model that is
able to learn translation across language pairs that are unseen during the
training time. This is motivated by human language learning experience, that
if a person knows German, English, and Arabic and can translate over German
$\,\to\,$ English and Arabic $\,\to\,$ English then they should be able to
translate with sufficiently good quality between German $\,\to\,$ Arabic
without any formal training. This is true for us because beneath all the
lexical and grammatical differences across languages, we share the grounding
of various concepts in the same representation. Basically, the representation
of the concept ‘cat’ is the same as the word ‘Katze’ in German.

Traditionally, a pivot language has been prominently used to achieve this
task. For example; if a German-to-Arabic translation is required then the
original text is passed through the first German-to-English translation
engine, and then the output English sentence is passed through the English-to-
Arabic translation system.

This simple yet effective strategy has been shown to achieve state-of-art
performance across zero-resource settings in many language pairs. Currey and
Heafield (2019) use data augmentation with pivot language to generate pseudo-
parallel data across zero-shot language pairs and then re-train a system.
Recently, Dabre et al. (2021) have even utilized multi-pivot languages and
simultaneous translation as a method to improve zero-shot performance. While
Kim et al. (2019) combined pivoting with transfer learning and an adapter
module, Siddhant et al. (2020) leveraged monolingual data with self-
supervision for low resource languages to achieve impressive performance.

##  3  Experimental Setup

For the purpose of this study, we will constrain the study and experiments to
OPUS-100 by Zhang et al. (2020). OPUS-100 is an English-centric dataset with
over 100 language pairs that have either source/target language as English. It
also consists of several other non-English-centric pairs that are available
for zero-shot translation objectives. We should emphasize that while previous
and related work on this dataset has been centered around massively-
multilingual translation as well as zero-shot translation, the objective of
the current work is only on zero-shot translation. As part of zero-shot
languages, OPUS-100 provides 15 language pairs that are combinations of
French, German, Arabic, Russian, Chinese and Dutch. For the evaluation of our
translation model, we shall use the BLEU score, which is a standard metric of
automatic evaluation across machine translation.

We run our experiments using the mT5 implementation available in the
Transformers library provided by HuggingFace (Wolf et al., 2019) and use pre-
trained mT5 models(small, large, and xx-large) from Xue et al. (2020). For
reproducibility purposes, we use the Adam optimizer and run our experiments on
a Google TPU v2-32 instance for 64,000 steps with 256 max length, 512 batch
size, 0.0001 learning rate and we use a beam size of 4 at inference time.

For baseline experiments, we consider 2 strong baselines – (i) First, for any
language pair say XX-YY, we train 2 Transformer models XX-En and En-YY, and
run zero shot inference for any new sentence from language XX through XX-En
and then through En-YY, note that we do not pre-train these models (ii)
Second, we consider the model from Zhang et al. (2020) which implements random
online back translation to recover from off-target translation.

##  4 Methodology

###  4.1 Large Pre-trained Model with Prompt Conditioning

First, we provide a brief introduction to the T5 architecture. T5 or Text-to-
Text Transfer Transformer is a recently introduced framework that frames all
the NLP tasks as a text-to-text problem. While the model architecture is
vanilla Transformer architecture (Vaswani et al., 2017), it has been
pretrained on the C4 dataset (Raffel et al., 2019) on a Masked Language
Modeling objective Devlin et al. (2018). Any new task could be provided as a
brief prompt to the model along with the input, for example, translation from
German to English could be specified as translate German to English: This is a
test input sentence, while the output is generally not formatted. This is the
default prompt style used by Raffel et al. (2019) as well as by this work.

Recently, Xue et al. (2020) introduced the multi-lingual version of this model
which is pre-trained on the mC4 dataset. They have shown that mT5 exhibits
zero-shot capabilities, as learning a task in one language is directly
transferable to the same task in a different language without any further
training. They also highlight that the model suffers from unexpected
translation in the output space. For example, a model trained on English Part-
of-speech and when inference is run on French input outputs an English
translation of the French input. This issue is similar to what Zhang et al.
(2020) has suggested that the massively multilingual translation models suffer
from. The lack of language signals to the model results in although correct
output but in an incorrect target language.

###  4.2 Data Augmentation

We run experiments on 2 main techniques in this work:

  * •

Sentence Concatenation

  * •

Seq2Mix

Figure 1: Example of Data Augmentation

In the first set, if our objective is to run translation from German to
Arabic, then at each training time, we choose a data point from the German-
English dataset and a random data point from the English-Arabic dataset. We
then concatenate the source sentence and target sentence for both language
pairs with a simple <sep> token. This results in a training sentence whose
input has the first half as a German sentence and the second half as an
English sentence. Similarly, the output has the first half in English and the
Second half as Arabic sentences. We modify the input prompt slightly here to
identify the languages present in the new input and output, as translate
German and English to English and Arabic. We hypothesize that the model is
intelligent enough to pick up the right words and context from the prompt to
produce the right output.

Secondly, we used Seq2Mix as introduced by Guo et al. (2020). They propose 2
variants of the Seq2Mix algorithm – hard and soft Seq2Mix. For the purpose of
this work, we will only focus on the hard version. In essence, for 2 input
sentences of equal sequence length222otherwise use padding to ensure the
sequences are of equal length, from German $(Gx_{1},...,Gx_{n})$ and English
$(Ex_{1},...,Ex_{n})$, we construct a German-English sentence
$(GEx_{1},...,GEx_{n})$, where $GEx_{i}$ is a token taken randomly from either
$(Gx_{i},Ex_{i})$ with a sample probability from Binomial($\lambda$).333where
$\lambda$ itself is sampled from $\beta$(0.5, 0,5) A similar process is run
over to obtain an English-Arabic sentence which serves as output to the
German-English input.

Figure 1 depicts both the augmentation techniques for the input sentences in
the same. It is noteworthy that we need not merge sentences that are similar
to each other, thus we could select any two sentences from our dataset for
creating the augmented data. All of these data augmentation strategies work to
create synthetic datasets that are employed along with the original bilingual
datasets at training time with equal weighting. We hypothesize that while the
model learns translation from both synthetic and original datasets, the prompt
conditioning along with the mixed vocab is learned better at training time.

##  5 Results & Analysis

We find that a mixed data augmentation training regime helps bring down OTTER
to an extremely low range as referenced in 1. We attribute this to the
compositional relationships learned by the large language model on the mixed
vocabulary as well as the language tag we use as part of the task prompt.

| OTTER | BLEU
---|---|---
Transformer + Pivot | - | 12.98
Zhang et al. (2020) | - | 14.78
Ours (small mT5) | 27.1% | 4.9
Ours (large mT5) | 24.2% | 5.1
Ours (XXL mT5) | 19.4% | 7.2
XXL mT5 + input concat | 0.9% | 15.4
XXL mT5 + Seq2Mix | 0.7% | 15.7
Table 1: OTTER and BLEU scores for zero-shot language pairs; results are
average across all the 15 language pairs in the zero-shot setting

Similarly, we find that data augmentation techniques like Seq2Mix Guo et al.
(2020), can substantially improve zero-shot performance when used on top of
large pre-trained language models. We explain the performance using the
following reasoning:

  * •

Mixing vocabulary in the same sentence during training force the internal
representation of tokens to align themselves in similar clusters across
languages.

  * •

Using XX-English and English-YY translation objective along with data
augmentation smoothens the loss landscape to facilitate better representation
for zero-shot translation

##  6 Conclusion

In this paper, we utilized mixing augmentation techniques along with large
sequence-to-sequence models to generate high-quality zero-shot translation
models for language pairs that have no training data available. We
successfully demonstrate that large pre-trained language models are able to
learn the semantic spaces between languages and are already good at zero-shot
machine translation. However, data augmentation techniques can further boost
this performance to achieve impressive results on zero-shot translation.

##  7 Future Work

We plan on running further experiments with improved data augmentation
strategies at pre-training time which we think will benefit downstream zero-
shot translation.

## References

  * Aharoni et al. (2019) Roee Aharoni, Melvin Johnson, and Orhan Firat. 2019.  Massively multilingual neural machine translation.  _arXiv preprint arXiv:1903.00089_.
  * Arivazhagan et al. (2019a) Naveen Arivazhagan, Ankur Bapna, Orhan Firat, Roee Aharoni, Melvin Johnson, and Wolfgang Macherey. 2019a.  The missing ingredient in zero-shot neural machine translation.  _arXiv preprint arXiv:1903.07091_.
  * Arivazhagan et al. (2019b) Naveen Arivazhagan, Ankur Bapna, Orhan Firat, Dmitry Lepikhin, Melvin Johnson, Maxim Krikun, Mia Xu Chen, Yuan Cao, George Foster, Colin Cherry, et al. 2019b.  Massively multilingual neural machine translation in the wild: Findings and challenges.  _arXiv preprint arXiv:1907.05019_.
  * Brown et al. (2020) Tom B Brown, Benjamin Mann, Nick Ryder, Melanie Subbiah, Jared Kaplan, Prafulla Dhariwal, Arvind Neelakantan, Pranav Shyam, Girish Sastry, Amanda Askell, et al. 2020.  Language models are few-shot learners.  _arXiv preprint arXiv:2005.14165_.
  * Currey and Heafield (2019) Anna Currey and Kenneth Heafield. 2019.  Zero-resource neural machine translation with monolingual pivot data.  In _Proceedings of the 3rd Workshop on Neural Generation and Translation_ , pages 99–107, Hong Kong. Association for Computational Linguistics.
  * Dabre et al. (2021) Raj Dabre, Aizhan Imankulova, Masahiro Kaneko, and Abhisek Chakrabarty. 2021.  Simultaneous multi-pivot neural machine translation.  _arXiv preprint arXiv:2104.07410_.
  * Devlin et al. (2018) Jacob Devlin, Ming-Wei Chang, Kenton Lee, and Kristina Toutanova. 2018.  Bert: Pre-training of deep bidirectional transformers for language understanding.  _arXiv preprint arXiv:1810.04805_.
  * Fadaee et al. (2017) Marzieh Fadaee, Arianna Bisazza, and Christof Monz. 2017.  Data augmentation for low-resource neural machine translation.  _arXiv preprint arXiv:1705.00440_.
  * Gonzales et al. (2020) Annette Rios Gonzales, Mathias Müller, and Rico Sennrich. 2020.  Subword segmentation and a single bridge language affect zero-shot neural machine translation.  In _Proceedings of the Fifth Conference on Machine Translation_ , pages 528–537.
  * Gu et al. (2018) Jiatao Gu, Hany Hassan, Jacob Devlin, and Victor OK Li. 2018.  Universal neural machine translation for extremely low resource languages.  _arXiv preprint arXiv:1802.05368_.
  * Guo et al. (2020) Demi Guo, Yoon Kim, and Alexander Rush. 2020.  Sequence-level mixed sample data augmentation.  In _Proceedings of the 2020 Conference on Empirical Methods in Natural Language Processing (EMNLP)_ , pages 5547–5552, Online. Association for Computational Linguistics.
  * Johnson et al. (2017) Melvin Johnson, Mike Schuster, Quoc V Le, Maxim Krikun, Yonghui Wu, Zhifeng Chen, Nikhil Thorat, Fernanda Viégas, Martin Wattenberg, Greg Corrado, et al. 2017.  Google’s multilingual neural machine translation system: Enabling zero-shot translation.  _Transactions of the Association for Computational Linguistics_ , 5:339–351.
  * Kim et al. (2019) Yunsu Kim, Petre Petrov, Pavel Petrushkov, Shahram Khadivi, and Hermann Ney. 2019\.  Pivot-based transfer learning for neural machine translation between non-english languages.  _arXiv preprint arXiv:1909.09524_.
  * Lakew et al. (2021) Surafel M. Lakew, Matteo Negri, and Marco Turchi. 2021.  Zero-shot neural machine translation with self-learning cycle.  In _Proceedings of the 4th Workshop on Technologies for MT of Low Resource Languages (LoResMT2021)_ , pages 96–113, Virtual. Association for Machine Translation in the Americas.
  * Lewis et al. (2019) Mike Lewis, Yinhan Liu, Naman Goyal, Marjan Ghazvininejad, Abdelrahman Mohamed, Omer Levy, Ves Stoyanov, and Luke Zettlemoyer. 2019.  Bart: Denoising sequence-to-sequence pre-training for natural language generation, translation, and comprehension.  _arXiv preprint arXiv:1910.13461_.
  * Liao et al. (2021) Junwei Liao, Yu Shi, Ming Gong, Linjun Shou, Hong Qu, and Michael Zeng. 2021.  Improving zero-shot neural machine translation on language-specific encoders-decoders.  _arXiv preprint arXiv:2102.06578_.
  * Liu et al. (2020) Yinhan Liu, Jiatao Gu, Naman Goyal, Xian Li, Sergey Edunov, Marjan Ghazvininejad, Mike Lewis, and Luke Zettlemoyer. 2020.  Multilingual denoising pre-training for neural machine translation.  _Transactions of the Association for Computational Linguistics_ , 8:726–742.
  * Raffel et al. (2019) Colin Raffel, Noam Shazeer, Adam Roberts, Katherine Lee, Sharan Narang, Michael Matena, Yanqi Zhou, Wei Li, and Peter J Liu. 2019.  Exploring the limits of transfer learning with a unified text-to-text transformer.  _arXiv preprint arXiv:1910.10683_.
  * Salcianu et al. (2016) Alex Salcianu, Andy Golding, and Anton Bakalov. 2016.  Compact language detector v3.  _https://github.com/google/cld3_.
  * Siddhant et al. (2020) Aditya Siddhant, Ankur Bapna, Yuan Cao, Orhan Firat, Mia Chen, Sneha Kudugunta, Naveen Arivazhagan, and Yonghui Wu. 2020.  Leveraging monolingual data with self-supervision for multilingual neural machine translation.  _arXiv preprint arXiv:2005.04816_.
  * Sun et al. (2020) Haipeng Sun, Rui Wang, Kehai Chen, Masao Utiyama, Eiichiro Sumita, and Tiejun Zhao. 2020.  Knowledge distillation for multilingual unsupervised neural machine translation.  _arXiv preprint arXiv:2004.10171_.
  * 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.  _arXiv preprint arXiv:1706.03762_.
  * Wolf et al. (2019) Thomas Wolf, Lysandre Debut, Victor Sanh, Julien Chaumond, Clement Delangue, Anthony Moi, Pierric Cistac, Tim Rault, Rémi Louf, Morgan Funtowicz, et al. 2019.  Huggingface’s transformers: State-of-the-art natural language processing.  _arXiv preprint arXiv:1910.03771_.
  * Xia et al. (2019) Mengzhou Xia, Xiang Kong, Antonios Anastasopoulos, and Graham Neubig. 2019.  Generalized data augmentation for low-resource translation.  _arXiv preprint arXiv:1906.03785_.
  * Xue et al. (2020) Linting Xue, Noah Constant, Adam Roberts, Mihir Kale, Rami Al-Rfou, Aditya Siddhant, Aditya Barua, and Colin Raffel. 2020.  mt5: A massively multilingual pre-trained text-to-text transformer.  _arXiv preprint arXiv:2010.11934_.
  * Zhang et al. (2021) Biao Zhang, Ankur Bapna, Rico Sennrich, and Orhan Firat. 2021.  Share or not? learning to schedule language-specific ca-pacity for multilingual translation.  In _International Conference on Learning Representations_.
  * Zhang et al. (2020) Biao Zhang, Philip Williams, Ivan Titov, and Rico Sennrich. 2020.  Improving massively multilingual neural machine translation and zero-shot translation.  In _Proceedings of the 58th Annual Meeting of the Association for Computational Linguistics_ , pages 1628–1639, Online. Association for Computational Linguistics.
  * Zoph et al. (2016) Barret Zoph, Deniz Yuret, Jonathan May, and Kevin Knight. 2016.  Transfer learning for low-resource neural machine translation.  _arXiv preprint arXiv:1604.02201_.