%
% File acl2020.tex
%
%% Based on the style files for ACL 2020, which were
%% Based on the style files for ACL 2018, NAACL 2018/19, which were
%% Based on the style files for ACL-2015, with some improvements
%%  taken from the NAACL-2016 style
%% Based on the style files for ACL-2014, which were, in turn,
%% based on ACL-2013, ACL-2012, ACL-2011, ACL-2010, ACL-IJCNLP-2009,
%% EACL-2009, IJCNLP-2008...
%% Based on the style files for EACL 2006 by 
%%e.agirre@ehu.es or Sergi.Balari@uab.es
%% and that of ACL 08 by Joakim Nivre and Noah Smith

\documentclass[11pt,a4paper]{article}
\usepackage[hyperref]{acl2020}
\usepackage{times}
\usepackage{latexsym}
\renewcommand{\UrlFont}{\ttfamily\small}
\usepackage{algorithmic}
\usepackage{url}
\usepackage[options ]{algorithm2e}
\usepackage{algorithm}
\usepackage[noend]{algpseudocode}
\usepackage[colorinlistoftodos]{todonotes}

% This is not strictly necessary, and may be commented out,
% but it will improve the layout of the manuscript,
% and will typically save some space.
\usepackage{microtype}
\usepackage{graphicx}


\aclfinalcopy % Uncomment this line for the final submission
\def\aclpaperid{2} %  Enter the acl Paper ID here

%\setlength\titlebox{5cm}
% You can expand the titlebox if you need extra space
% to show all the authors. Please do not make the titlebox
% smaller than 5cm (the original size); we will check this
% in the camera-ready version and ask you to change it back.

\newcommand\BibTeX{B\textsc{ib}\TeX}

\title{Checkpoint Reranking: An Approach To Select Better Hypothesis For Neural Machine Translation Systems}

\author{Vinay Pandramish \\
  International Institute of \\
  Information Technology, \\
  Hyderabad \\
  %Affiliation / Address line 3 \\
  %Affiliation / Address line 2 \\
  \texttt{pandramish.vinay@research.}\\ 
  \texttt{iiit.ac.in}\\\And
  Dipti Misra Sharma \\
  International Institute of\\
  Information Technology, \\
  Hyderabad \\
  %Affiliation / Address line 2 \\
  %Affiliation / Address line 3 \\
  \texttt{dipti@iiit.ac.in} \\}

\date{}

\begin{document}
\maketitle
\begin{abstract}
   In this paper, we propose a method of re-ranking the outputs of Neural Machine Translation (NMT) systems. After the decoding process, we select a few last iteration outputs in the training process as the $N$-best list. After training a Neural Machine Translation (NMT) baseline system, it has been observed that these iteration outputs have an oracle score higher than baseline up to 1.01 BLEU points compared to the last iteration of the trained system.We come up with a ranking mechanism by solely focusing on the decoder's ability to generate distinct tokens and without the usage of any language model or data. With this method, we achieved a translation improvement up to +0.16 BLEU points over baseline.We also evaluate our approach by applying the coverage penalty to the training process.In cases of moderate coverage penalty, the oracle scores are higher than the final iteration up to +0.99 BLEU points, and our algorithm gives an improvement up to +0.17 BLEU points.With excessive penalty, there is a decrease in translation quality compared to the baseline system. Still, an increase in oracle scores up to +1.30 is observed with the re-ranking algorithm giving an improvement up to +0.15 BLEU points is found in case of excessive penalty.The proposed re-ranking method is a generic one and can be extended to other language pairs as well.
%\todo{Abstracts should generally not be longer than one paragraph. You can move some of this info into the abstract.}
\end{abstract}


\section{Introduction}

Neural Machine Translation(NMT) has brought excellent results in the field of Machine Translation\citet{Sutskever2014SequenceTS, Bahdanau2014NeuralMT, Cho2014LearningPR} due to generation of high-quality translations for different language pairs. Yet even higher quality can be achieved by combining multiple models by techniques like ensembles \citet{Hansen1990NeuralNE} and reranking \citet{Shen2004DiscriminativeRF}. Our work deals with how Neural Machine Translation (NMT) can achieve better results explicitly with reranking methods.

Neural Machine Translation has an encoder-decoder architecture that is jointly trained to maximize the probability of target given source sentences. It first encodes the source sentence into a single vector, and the decoder predicts it.With the Attention Mechanism, it tries to apply weights to the input sentence at each time step. Recent approaches like the transformer model \citet{Vaswani2017AttentionIA} have achieved the state-of-the-art results for Machine Translation. 

Neural Machine Translation (NMT) however, leads to over-translation and under-translation as it tends to ignore the past alignment information, and it is effectively tackled by introducing a coverage vector \citet{Tu2016ModelingCF}. Other approaches such as  \citet{Mi2016ACE} and \citet{Mi2016SupervisedAF} too solve the coverage problem in NMT. Without the coverage vector, it could result in a decrease in translation quality.

%\todo{I would split this into two paragraphs.} 

We propose a method that selects a better hypothesis giving high importance to distinct words generated from decoder without the usage of any language model or data.After applying the proposed reranking method, an overall improvement in translation quality is observed as compared to the baseline system.

The rest of the paper is organized as follows; Section 2 discusses the work related to re-utilizing existing models for Machine Translation. Section 3 describes our approach for Checkpoint based Reranking. In Section 4, we present our Reranking Algorithm. In Section 5, we demonstrate all of our Experiments along with the results obtained, and finally, the paper is concluded in Section 6 with future directions.


\section{Related Work}

The work of \citet{Imamura2017EnsembleAR} explains the concepts of reranking and ensembling in detail. It introduces a method of bidirectional reranking in which it combines the hypothesis from l2r and r2l decoding following the works of \citet{Liu2016AgreementOT}, which proposes an agreement model to solve unbalanced outputs of recurrent neural networks. \citet{Marie2018ASO} has introduced a reranking system that uses a smorgasbord of informative features in tasks where PBSMT and NMT produce translations of different quality.

The work by \citet{Shen2004DiscriminativeRF} shows how to apply perceptron-like reranking algorithms to improve the overall translation quality, and \citet{Olteanu2006LanguageMA} shows the usage of Language Models (LMs) for reranking on hypotheses generated by phrase-based Statistical Machine Translation systems. \citet{Wang2007RerankingMT} has shown linguistically motivated and computationally efficient structured language models for reranking in SMT systems.

The concept of Checkpoint ensembles is introduced by  \citet{Sennrich2016EdinburghNM} and was later on improvised to independent ensembling \citet{Sennrich2017TheUO}. \citet{Vaswani2017AttentionIA} included a checkpoint averaging method for their model. \citet{Liu2018ACS} has focused on decoding techniques that utilize existing models at parameter, word, and sentence level corresponding to checkpoint averaging, model ensembling, and candidate reranking and found that all of these improve the translation quality without retraining the model. 


\section{Checkpoint Based Reranking}

In our approach, the iteration outputs are selected as the $N$-best list. It implies for the last $K$ iterations; we have the corresponding $K$-best list for a sentence. We take our Oracle scores as the one that is having the largest BLEU Score~\citet{papineni-etal-2002-bleu} on the test reference hypothesis from this $K$-best list. After obtaining the oracle scores from this $K$-best list, we observe that this score is larger than the baseline system, and it indicates that there is scope for further improvement of translation quality. So we propose a reranking method that improves the translation quality over the baseline system without any language model or data.


We try to focus on the nature of translations that the decoder generates with and without coverage penalty. In the initial step, we keep track of the number of distinct words in the generated hypothesis, and the later ones we keep track of words that have repeated more than once.A higher score is given for sentences having a higher number of Distinct Tokens ($D$) and lower scores for those having more number of repetitive words ($F$).

For each sentence in the $N$-best list, these scores are sorted, and the sentence having the highest score is selected. This process is repeated for the entire test set, and the ones that are having the top most scores are chosen as the reranked output, as shown in Section 4.


%\newpage

\section{Reranking Procedure}

\begin{algorithm}
\caption{Method}
\hspace*{\algorithmicindent} \textbf{Input:} Translated Target Language Sentences {$H$ = ( $h(n-k)$...,$h(n)$ ) } at last $k$ epochs for given sentence\\
\hspace*{\algorithmicindent} \textbf{Output:} Sentence having highest number of distinct words and lowest repetitive words  
\begin{algorithmic}
\FOR {each sentence $h_j$ in $H$ } 
\IF {$h_j$ \leftarrow ($w_1$,$w_2$,$w_3$...$w_l$) }


\begin{ALC@g}
    \STATE $D \rightarrow DISTINCT(($w_1$,$w_2$,$w_3$...$w_l$)) $ 
\end{ALC@g}
\begin{ALC@g}
\end{ALC@g}
\bindent
    \STATE $F \rightarrow FREQ($w_1$)\times FREQ($w_2$)$... \\
    \eindent
\bindent
    $score_j$ \rightarrow $D$/$F$
\eindent
\ENDIF  \newline
\Return sentence with highest $score_j$
\ENDFOR 
\end{algorithmic}
\end{algorithm}

For a sentence, FREQ is the count of each word; DISTINCT is the total count of unique words. For each hypothesis in the $K$-best list we divide DISTINCT with FREQ and select the highest scorer.

%\todo{There should be a little more text in this section to explain the algorithm.}

\section{Experiments and Results}
\subsection{DataSet}

We used ILCI \citet{JHA10.874} corpus, which has eleven language pairs from which we chose Telugu and Hindi as our parallel data during the training process. The entire corpus is manually cleaned to remove the misalignments. Table 1 shows the split ratio of sentences followed in the process. 

\begin{table}[h]
\begin{center}
\begin{tabular}{p{2 cm}| p{1 cm} }
\hline
\textbf{Data} & \textbf{Size} \\
\hline
Training                    &              45000\\ 
Validation                    &             4000\\ 
Test                    &              990\\ 
\hline
\end{tabular}
\end{center}
\caption{Corpus Division}
\label{table2}
\end{table}

\subsection{Experiments}

We adopt the Keras implementation \citet{nmt-keras:2018} for our experiments.We use a two-layer encoder-decoder model with 500-dimensional source and target embeddings and 500 units in each of the layers. The encoder layers are LSTM \citet{Hochreiter1997LongSM} and decoder are ConditionalLSTM with Bahdanu's attention \citet{Bahdanau2014NeuralMT} and the optimizer used is Adam \citet{Kingma2014AdamAM} and the model is trained for 15 iterations with a batch size of 512 sentences. The rest of the parameters in the configuration file were set to their default values. We evaluate with coverage penalty and the absence of it for our experiments.

The hypotheses are collected for the last k=3, 5, 7 during decoding. We evaluate the generated hypotheses with BLEU \citet{papineni-etal-2002-bleu} for our experiments.

%\newpage

\subsection{Results}

\begin{table}[h]
\begin{center}
\begin{tabular}{ p{4 cm}| p{2.5 cm} }
\hline
      \textbf{Hypothesis } &\textbf{BLEU} \\
      \hline
      Checkpoint-1 & 0.62\\
      Checkpoint-2 & 3.55\\
      Checkpoint-3 & 8.83 \\
      Checkpoint-4 & 13.53 \\
      Checkpoint-5 & 17.01 \\
      Checkpoint-6 & 19.20 \\
      Checkpoint-7 & 20.72 \\
      Checkpoint-8 & 21.09 \\
      Checkpoint-9 & 21.38 \\
      Checkpoint-10 & 21.87 \\
      Checkpoint-11 & 22.39 \\
      Checkpoint-12 & 22.37 \\
      Checkpoint-13 & 22.57 \\
      Checkpoint-14 & 22.71 \\
      Checkpoint-15 & 22.92 \\
      \hline
      

\end{tabular}
\caption{BLEU Scores with Baseline System}
 \end{center}
\end{table}


The scores obtained after each iteration are shown in Table 2. After this, we apply our proposed reranking method to the last few iteration outputs, which are selected as the $N$-best list. The proposed reranking method leads to an overall improvement of translation quality by +0.07, +0.15, +0.16 BLEU score compared to the baseline with oracle improvements up to +0.55, +0.90, +1.01 on the three systems. The scores obtained for each of them are shown in Tables 3, 4, 5.


\begin{table}[h]
\begin{center}
\begin{tabular}{ p{4 cm}| p{2.5 cm}}

      \hline
      \textbf{System} &\textbf{BLEU}\\
      \hline
      Baseline & 22.92\\
      Reranking & 22.99 \textbf{(+0.07)}\\ 
      Oracle & 23.47 \textbf{(+0.55)}\\
      \hline

\end{tabular}
\caption{Last 3 Iterations}
 \end{center}
\end{table}

\begin{table}[!h]
\begin{center}
\begin{tabular}{ p{4 cm}| p{2.5 cm} }

      \hline
      \textbf{System} &\textbf{BLEU}\\
      \hline
      Baseline & 22.92\\
      Reranking & 23.07 \textbf{(+0.15)}\\
      Oracle & 23.82 \textbf{(+0.90)}\\
      \hline

\end{tabular}
\caption{Last 5 Iterations}
 \end{center}
\end{table}

\begin{table}[!h]
\begin{center}
\begin{tabular}{p{4 cm}| p{2.5 cm}}

      \hline
      \textbf{System} &\textbf{BLEU}\\
      \hline
      Baseline & 22.92\\
      Reranking & 23.08 \textbf{(+0.16)}\\
     Oracle & 23.93 \textbf{(+1.01)}\\
      \hline
      

\end{tabular}
\caption{Last 7 Iterations}
 \end{center}
\end{table}


\subsection{With Coverage Penalty}

 We also evaluate our work by adding coverage penalty \citet{Wu2016GooglesNM} in the training process to ensure that this algorithm works when both the under translations and over translations are addressed adequately. All the hyperparameters are kept the same as the baseline system except for the coverage penalty.

\begin{figure}[h]
\centering
\includegraphics[scale=0.45]{finalscores160.png}
\caption{Comparison with Baseline System}
\end{figure}


\begin{table}[!h]
\begin{center}
\begin{tabular}{ p{4 cm}| p{2.5 cm}}

      \hline
      \textbf{Hypothesis}&\textbf{0.1 penalty} \\
      \hline
      Checkpoint-1 &1.22\\
      Checkpoint-2 &5.59\\
      Checkpoint-3 & 11.92\\
      Checkpoint-4 & 16.59\\
      Checkpoint-5 & 19.18\\
      Checkpoint-6 & 20.51\\
      Checkpoint-7 & 21.26\\
      Checkpoint-8 & 21.40\\
      Checkpoint-9 & 21.80\\
      Checkpoint-10 & 21.72\\
      Checkpoint-11 & 22.27\\
      Checkpoint-12 & 22.57\\
      Checkpoint-13 & 23.11\\
      Checkpoint-14 & 22.93\\
      Checkpoint-15 & 23.35\\
      \hline
      

\end{tabular}
\caption{BLEU Scores With 0.1 Coverage Penalty}
 \end{center}
\end{table}

\begin{table}[!h]
\begin{center}
\begin{tabular}{p{4 cm}| p{2.5 cm}}

      \hline
      \textbf{System} &\textbf{0.1 penalty}\\
      \hline
      Baseline & 23.35\\
      Reranking & 23.40 \textbf{(+0.05)}\\
      Oracle & 23.86 \textbf{(+0.51)}\\
      \hline

\end{tabular}
\caption{Last 3 Iterations with 0.1 coverage penalty}
 \end{center}
\end{table}


\begin{table}[!h]
\begin{center}
\begin{tabular}{p{4 cm}| p{2.5 cm} }

      \hline
      \textbf{System} &\textbf{0.1 penalty}\\
      \hline
      Baseline & 23.35\\
      Reranking & 23.50 \textbf{(+0.15)}\\
      Oracle & 24.17 \textbf{(+0.82)}\\
      \hline

\end{tabular}
\caption{Last 5 Iterations with 0.1 coverage penalty}
 \end{center}
\end{table}


\begin{table}[!h]
\begin{center}
\begin{tabular}{ p{4 cm}| p{2.5 cm} }

      \hline
      \textbf{System} &\textbf{0.1 penalty}\\
      \hline
      Baseline & 23.35\\
      Reranking & 23.52 \textbf{(+0.17)}\\
      Oracle & 24.34 \textbf{(+0.99)}\\
      \hline

\end{tabular}
\caption{Last 7 Iterations with 0.1 coverage penalty}
 \end{center}
\end{table}

\newpage

From Tables 7, 8, 9 it can be inferred that there is an improvement of +0.05, +0.15, +0.17 and oracle improvements up to +0.51, +0.82, +0.99 for 0.1 coverage penalty.

\begin{table}[!h]
\begin{center}
\begin{tabular}{p{4 cm}| p{2.5 cm}}

      \hline
      \textbf{Hypothesis}&\textbf{0.2 penalty} \\
      \hline
      Checkpoint-1 &1.33\\
      Checkpoint-2 &3.54\\
      Checkpoint-3 & 10.10\\
      Checkpoint-4 & 15.36\\
      Checkpoint-5 & 18.08\\
      Checkpoint-6 & 19.36\\
      Checkpoint-7 & 20.35\\
      Checkpoint-8 & 20.29\\
      Checkpoint-9 & 20.56\\
      Checkpoint-10 & 20.96\\
      Checkpoint-11 & 21.43\\
      Checkpoint-12 & 21.52\\
      Checkpoint-13 & 21.66\\
      Checkpoint-14 & 21.56\\
      Checkpoint-15 & 21.81\\
      \hline
      

\end{tabular}
\caption{BLEU Scores With 0.2 Coverage Penalty}
 \end{center}
\end{table}

\begin{table}[!h]
\begin{center}
\begin{tabular}{p{4 cm}| p{2.5 cm}}

      \hline
      \textbf{System} &\textbf{0.2 penalty}\\
      \hline
      Baseline & 21.81\\
      Reranking & 21.93 \textbf{(+0.12)}\\
      Oracle & 22.72 \textbf{(+0.91)}\\ 
      \hline

\end{tabular}
\caption{Last 3 Iterations with 0.2 coverage penalty}
 \end{center}
\end{table}


\begin{table}[!h]
\begin{center}
\begin{tabular}{p{4 cm}| p{2.5 cm}}

      \hline
      \textbf{System} &\textbf{0.2 penalty}\\
      \hline
      Baseline & 21.81\\
      Reranking & 21.96 \textbf{(+0.15)}\\
      Oracle & 23.11 \textbf{(+1.30)}\\
      \hline

\end{tabular}
\caption{Last 5 Iterations with 0.2 coverage penalty}
 \end{center}
\end{table}


\begin{table}[!h]
\begin{center}
\begin{tabular}{ p{4 cm}| p{2.5 cm}}

      \hline
      \textbf{System} &\textbf{0.2 penalty}\\
      \hline
      Baseline & 21.81\\
      Reranking & 21.96 \textbf{(+0.15)}\\
      Oracle & 23.11 \textbf{(+1.30)}\\
      \hline

\end{tabular}
\caption{Last 7 Iterations with 0.2 coverage penalty}
 \end{center}
\end{table}


With excess coverage penalty, there is a decline in translation quality compared to the baseline system without coverage penalty, as shown in Tables 2 and 10. Still, the proposed method gives an increase of +0.12, +0.15, +0.15 over baseline with oracle improvements up to +0.91, +1.30, +1.30 for the last 3, 5 and 7 checkpoints respectively as shown in Tables 11, 12, 13.


%\newpage
One can also observe that the improvements and the oracle scores increase correspondingly with the size of the $N$-best list.The variation with the baseline can be obtained as shown in Figure 1. 

\section{Conclusions and Future Work}

In this paper, we introduce a method of selecting an $N$-best list for NMT systems and propose a way of reranking to the generated hypotheses from the system. We observe that our approach is giving better results over the baseline model by following the proposed reranking method and is also evaluated with the coverage penalty. 

%In our approach, we propose a method that scores translations without any external language model or data. 
One can investigate our approach with varying beam sizes and analyzing the effect of length penalty \citet{Wu2016GooglesNM} and comparing it with methods such as \citet{Yang2018BreakingTB}. We also look forward to coming up with better reranking ways that are closer to the oracle scores and investigate the efficacy of the approach in low-resourced data conditions.


Language models are used for getting the likelihood of sentences and is a widely used concept for reranking hypotheses. Introducing Language Models during reranking could establish a tradeoff between perplexity and the scores to the hypotheses generated. We also plan to explore the work by \citet{Glehre2017OnIA} and \citet{Glehre2015OnUM} that introduces language models into the existing neural architecture with methods such as Shallow Fusion and Deep Fusion. It is another promising area to be looked upon for reranking.


\section*{Acknowledgments}

The authors would like to thank some of the Anonymous reviewers for providing critical suggestions. We thank Manish Shrivastava for the guidance, Vandan Mujadia for reviewing the drafts and Kenton Murray for the post-acceptance mentoring. We also acknowledge Grammarly for their generous donation towards drafting the final manuscript.

\bibliography{anthology,acl2020}
\bibliographystyle{acl_natbib}

\appendix


\end{document}
