\documentclass[english,tombow]{jnlp_3.3}
\usepackage{jnlpbbl_2.2}
\usepackage[dvipdfmx]{graphicx}
\usepackage{amsmath}
\usepackage{amssymb}
\usepackage{url}
\usepackage{gentombow}
\settombowbleed{5mm}
\usepackage{hangcaption_jnlp}
\allowdisplaybreaks
%%%%\usepackage{udline}
%%%%\setulminsep{1.2ex}{0.2ex}
%%%%\let\underline=\ul


%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%% author's definition
%%%%\usepackage{amsmath,amssymb,amsfonts}
\usepackage{algorithm2e}
\usepackage{multirow}
%%%%\usepackage{adjustbox}
\newcommand{\defeq}{\mathrel{\mathop:}=}
\newcommand{\eqdef}{\mathrel{\mathop=}:}

\makeatletter
\renewcommand{\algocf@capseparator}{~~}%
\makeatother

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\Volume{28}
\Number{1}
\Month{March}
\Year{2021}
%%%%\Issuetitle{「　　　　」特集号}

\received{2020}{6}{26}
\revised{2020}{9}{30}
%%%%\rerevised{2006}{5}{6}
\accepted{2020}{10}{28}

\setcounter{page}{82}


%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\esubject{General Paper}
\etitle{Sub-Subword N-Gram Features for Subword-Level Neural Machine Translation}
\eauthor{Ander Martinez\affiref{NAIST} \and Katsuhito Sudoh\affiref{NAIST} \and Yuji Matsumoto\affiref{NAIST}\affiref{RIKEN}} 
\eabstract{%
Neural machine translation (NMT) systems often use subword segmentation to limit vocabulary sizes. This type of segmentation is particularly useful for morphologically complex languages because their vocabularies can grow prohibitively large. This method can also replace infrequent tokens with more frequent subwords. Fine segmentation with short subword units has been shown to produce better results for smaller training datasets. Character-level NMT, which can be considered as an extreme case of subword segmentation in which each subword consists of a single character, can provide enhanced transliteration results, but also tends to produce grammatical errors. We propose a novel approach to this problem that combines subword-level segmentation with character-level information in the form of character n-gram features to construct embedding matrices and softmax output projections for a standard encoder-decoder model. We use a custom algorithm to select a small number of effective binary character n-gram features. Through four sets of experiments, we demonstrate the advantages of the proposed approach for processing resource-limited language pairs. Our proposed approach yields better performance in terms of BLEU score compared to subword- and character-based baseline methods under low-resource conditions. In particular, the proposed approach increases the vocabulary size for small training datasets without reducing translation quality.
}
\ekeywords{Feature Selection, Low-resource, Neural Machine Translation, N-gram, Word Segmentation}

\headauthor{Martinez et al.}
\headtitle{Sub-Subword N-Gram Features for Subword-Level Neural Machine Translation}

\affilabel{NAIST}{}{Nara Institute of Science and Technology}
\affilabel{RIKEN}{}{Riken Center for Advanced Intelligence Project}


%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\begin{document}

\maketitle

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\section{Introduction}
\label{sec:intro}

Neural machine translation (NMT) has made remarkable progress in recent years
\cite{sutskever_sequence_2014,bahdanau_neural_2014,vaswani_attention_2017}
and has become a popular approach for general machine translation tasks.

NMT systems take a sequence of source language tokens as inputs and predict a sequence of target language tokens as corresponding translation outputs. The granularity of such input and output tokens can be smaller than words, such as subwords \cite{sennrich_neural_2015}.
Replacing words with sequences of subwords has become a popular method.
Subword segmentation methods, such as byte-pair encoding (BPE), replace
infrequent words with more frequent subword segments to limit vocabulary
sizes.
Limiting vocabulary sizes is particularly important for morphologically
complex languages because their vocabularies may contain hundreds of thousands of entries.
The optimal size for a vocabulary depends on the particular training data. As indicated by \citeA{denkowski_stronger_2017}, NMT models trained on smaller corpora tend to perform better with smaller BPE vocabularies, because subwords with very low frequencies are avoided.

However, BPE segmentation does not consider the context of a word or its morphemes.
Subwords with similar surface forms are likely to contain the same morphemes, but if these subwords are represented by unique IDs, their similarities are not considered.


Character-level NMT
\cite{chung_character-level_2016,lee_fully_2016},
can be regarded as an extreme case of subword
segmentation in which each subword corresponds to a single character.
Character-level systems can perform better transliteration results than subword-level systems, as shown by \citeA{sennrich_how_2017}.

\citeA{sennrich_how_2017} compared the character-level model proposed by \citeA{lee_fully_2016} and the BPE-to-character model proposed by \citeA{chung_character-level_2016} to their own BPE-only model \cite{sennrich_edinburgh_2016}.
They concluded that character-level decoders ``perform worse at modelling morphosyntactic agreement, where information needs to be carried over long distances.''

In a more recent paper, \shortciteA{cherry_revisiting_2018} demonstrated that character-level models with large capacities (large numbers of layers in their encoders and decoders) can outperform BPE when their training datasets are very large (in their experiments, they considered 39.9 million sentence pairs). However, their model suffers from a disproportionate reduction in speed.

In this paper, we explore a novel training method for NMT models that allows us to utilize the character n-gram information of each subword to learn corresponding embeddings. This method is described in detail in Section \ref{sec:proposal}. Our proposed models operate at the subword level and make use of short n-gram features within subwords. In this paper, we refer to the character n-gram features of subwords as \emph{sub-subword} features.


We propose a subword-level NMT training method that utilizes sub-subword n-gram information to regularize subword embeddings and the output layer. Sub-subword-level features are selected from all n-grams in the subword vocabulary using a custom feature selection algorithm.
The set of selected sub-subword features can unambiguously identify every subword in the vocabulary.
Sub-subword binary features are fed through a multilayer feed-forward network to produce subword embeddings.
Because subword embeddings are produced exclusively from constant sub-subword features, the subword embeddings can be pre-computed once the model has been trained.
Therefore, our method does not need to modify baseline architectures or the numbers of parameters in trained models.

Another method that works well on low-resource language pairs is \emph{back-translation} (BT) \cite{sennrich_improving_2016,poncelas_investigating_2018,edunov_understanding_2018}.
BT is a simple method that
uses an NMT model to translate sentences in a target language into source language sentences, allowing one to synthesize a parallel corpus.
We explored how our proposed model can be combined with BT.

Through four sets of experiments, we determined the optimal architecture for applying sub-subword features to subword-level NMT.
We determined that this method works particularly well with small training sets.
Our main contributions can be summarized as follows:
\begin{itemize}
\item We propose an NMT model training approach combining subword segmentation to limit vocabulary sizes with n-gram features to construct subword embeddings using a standard multilayer feed-forward network (Subsection \ref{sec:proposal_a}).
\item We use a feature selection algorithm to select a small number of character n-gram features. Selected features should uniquely identify every word in the vocabulary (Subsection \ref{sec:algorithm}).
\item We demonstrate that a standard multilayer feed-forward network works better than a self-attention mechanism (Subsection \ref{sec:exp_approach}).
\item We demonstrate that constructing subword embeddings strictly from n-gram features works better than using n-gram features to complement standard embeddings (Subsection \ref{sec:exp_approach}).
\item We demonstrate that our method facilitates large vocabulary sizes with small training datasets, thereby improving translation results (Subsection \ref{sec:exp_voc}).
\item We demonstrate that our method works well for small training datasets (Subsection \ref{sec:exp_data}).
\item We explore how the proposed method can be combined with BT (Subsection \ref{sec:exp_back}).
\end{itemize}

This paper consists of five sections. The Introduction (\ref{sec:intro}) is followed by a Preliminaries section (\ref{sec:related}). Section \ref{sec:proposal} describes the proposed approach. Four sets of experiments are detailed in Section \ref{sec:experiments}. Finally, Section \ref{sec:conclusion} presents a summary of our findings and discusses future work.


%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\section{Preliminaries}
\label{sec:related}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\subsection{Neural Machine Translation}
\label{sec:nmt}

NMT models are used to translate sequences of tokens, such as words, in a source language
into corresponding sequences of tokens in a target language.
The sets of all distinct tokens in the source and target language sentences are called the source and target vocabularies, respectively. 
NMT models operate based on closed vocabularies.
The tokens in each vocabulary are assigned unique identification numbers.

The input tokens of a source sentence $\mathtt{x}$ are represented as a sequence of one-hot vectors of the corresponding tokens $\mathtt{x} \defeq (x_1, \dotsc, x_{T_x})$, where $T_x$ is the number of tokens in the sentence.
To output a probability distribution $p_t$ for a token $y_t$, the previous output tokens $\mathtt{y} \defeq (y_1, \dotsc, y_{t - 1})$, as well as the input $\mathtt{x}$, are conditioned.
These tokens are then projected into dense vectors $e_i^{(x)}$ and $e_j^{(y)}$ using matrices $E_x$ and $E_y$, which are often called embedding matrices.
Typical NMT models use two embedding matrices, namely $E_x$ for source sentence words and $E_y$ for representing words in the target sentence.
When using embeddings of $d$ dimensions and vocabularies of sizes $V_x$ and $V_y$, the embedding matrices $E_x$ and $E_y$ are in $\mathbb{R}^{V_x\times d}$ and $\mathbb{R}^{V_y\times d}$, respectively.
Such models output a probability distribution $p_t$ by projecting a dense vector of size $d$ onto a vector of the same size as the output vocabulary using the \emph{softmax} function.
The embedding matrices, output layer matrix $W_y$, and bias $b_y$ are often trained as conventional weight parameters.
\begin{gather}\label{eq:emb_x}
e_i^{(x)} \defeq E_x x_i,\\
\label{eq:emb_y}
e_j^{(y)} \defeq E_y y_j, \\
q_t \defeq \textup{NMT}(\{ e^{(x)}_{0 < i \leq T_x} \}, \{ e^{(y)}_{0 < j < t} \}), \\
\label{eq:out}
p_t \defeq \textup{Softmax}(W_y q_t + b_y), \\
\label{eq:softmax}
\textup{Softmax}(z)_k \defeq \frac{e^{z_k}}{\sum_l e^{z_l}},
\end{gather}
where the function \emph{NMT} represents a model that, given an input embedding sequence $e^{(x)}$ and previous translation tokens' embedding sequence $\{e^{(y)}_{0<j<t}\}$, approximates a dense vector $q_t$ corresponding to the next token in the translation.

The technique called \emph{weight tying} \cite{press_using_2017} consists in defining $W_y$ as the transpose of $E_y$.
If both the source language and target language are represented by the same set of tokens, they can share an embedding matrix, resulting in $E_x = E_y = W_y^\intercal$.


%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\subsection{Subword Segmentation}

As mentioned in Section \ref{sec:intro}, word-level vocabularies
can be very large, particularly for morphologically complex languages.
Subword segmentation is used to reduce
vocabulary sizes as an alternative to selecting the top-$N$ most frequently used words.

The number of different tokens can be reduced by splitting words into
smaller subword units.
Subword segmentation increases the length of input and output sequences,
and smaller vocabularies result in longer sequences.
The optimal vocabulary size depends on the training data, where smaller datasets
typically favor smaller vocabularies.

One very popular subword segmentation method is BPE \cite{sennrich_neural_2015}.
The BPE subword vocabulary starts with the set of all individual characters in the training data. The final characters in words are considered to be distinct from their counterparts in other locations.
A vocabulary is augmented until it has the desired size by merging frequent subword pairs to form new subwords.

There are various approaches to word segmentation in the literature that are similar to BPE. One such approach is the \emph{WordPieceModel} \cite{schuster_japanese_2012}. Instead of merging subwords based on their frequency, this model merges subwords to optimize a likelihood value for a language model. Different merging policies were explored in \cite{wu_finding_2018}, including frequency, accessor variety and descriptor length gain.
Another approach to word segmentation is the unigram language model \cite{kudo_subword_2018}, which can produce multiple segmentation candidates. In this model, the subword vocabulary is selected to optimize the probabilities of words by considering the probability of one word to be the product of the unigram probabilities of its subwords.

Once data have been segmented into subword units,
they are treated as independent tokens in the manner described in Section \ref{sec:nmt}.
The word embedding matrix can then be considered as a subword embedding matrix containing subword features.
The information regarding which characters comprise a token is ignored.
The potential benefits of taking advantage of this information
represent the main motivation for the use of \emph{sub-subword features}.


%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\subsection{Character n-gram Features}

Using n-gram features to generate word vectors is not a new concept: 
\shortciteA{wieting_charagram:_2016} used n-gram count vectors to represent words for different natural language processing (NLP) tasks.
\shortciteA{bojanowski_enriching_2017} trained word vectors on a skipgram language model by representing each word as the sum of the vectors representing its n-grams. This method takes word-boundary symbols into consideration.
They considered n-gram sizes ranging from three to six characters.
Because representing each n-gram using a unique vector can consume excessive memory, n-grams are grouped into buckets using a hash function, where they share vector representations with other n-grams in the same bucket.
\shortciteA{joulin_bag_2017} used the same approach to develop a model called \emph{fastText} for text classification.
N-gram vectors can complement word vectors, because words are also unique n-grams.
\shortciteA{zhang_effective_2019} used subword segmentation to complement word-level vectors with subword-level vectors for various NLP tasks that did not include NMT. They compared various subword segmentation methods introduced by \shortciteA{wu_finding_2018}.
\shortciteA{morishita_improving_2018} reinterpreted BPE subwords from smaller vocabulary configurations as features of subwords in a larger vocabulary. The embedding vector for a given subword was represented as the sum of its feature vectors.
Based on memory constraints, they only used sub-subword features for input and output embeddings, and not for the final output layer.
\shortciteA{takase_character_2019} explored the use of n-gram features of a fixed size for generating embeddings and output layer weights for language modeling. They also conducted experiments on NMT using trigram features to produce embeddings. In contrast to other approaches, they used a self-attention mechanism to calculate a weighted sum of feature embeddings.

We briefly describe the model proposed
by \shortciteA{takase_character_2019}, as we will compare our proposed model to it.
For a more detailed description, please refer to the original work.

\shortciteA{takase_character_2019} incorporated embeddings
inferred from fixed length n-grams (such as bigrams) into standard embeddings by replacing \eqref{eq:emb_x} and \eqref{eq:emb_y}
with the following two equations:
\begin{gather}\label{eq:emb_x_c}
e_i^{(x)} \defeq E_x x_i + c(x_i, \theta_c^{(x)}), \\
\label{eq:emb_y_c}
e_j^{(y)} \defeq E_y y_j + c(y_j, \theta_c^{(y)}),
\end{gather}
where $c(\omega, \theta_c)$ is a neural network with a parameter set $\theta_c$ that produces dense vector inferred from the n-gram features of word $\omega$.

The n-gram features \emph{augment} word embeddings without replacing them.
To produce $c(x_i, \theta_c^{(x)})$ and $c(y_j, \theta_c^{(y)})$ from n-gram features,
Takase et al. used what they called \emph{multidimensional self-attention}.
If the number of n-gram features of a specific word $\omega$ is given by $I(\omega) \in \mathbb{N}$, then
\begin{gather}\label{eq:emb_x_c_mdsa}
c(\omega, \{W_c, S\}) \defeq \sum^{I(\omega)}_{i=1} g_i \odot s^{(\omega)}_i, \\
\label{eq:emb_x_c_mdsa_3}
S^{(\omega)} \defeq (s^{(\omega)}_{1}, \cdots, s^{(\omega)}_{I(\omega)}), \\
\label{eq:emb_x_c_mdsa_2}
g_i \defeq [ \textup{RowSoftmax}(W_c S^{(\omega)}) ]_i,
\end{gather}
where $\odot$ denotes element-wise product of vectors, $[\cdot]_i$ is the i-th column of a given matrix and $\textup{RowSoftmax}$ is a softmax function applied row wise. The matrices $S^{(\omega)} \in \mathbb{R}^{D_e\times I(\omega)}$ represent the embeddings of the n-gram features in the word $\omega$. The dimension of the embeddings is $D_e$. These n-gram feature embeddings and the square matrix $W_c \in \mathbb{R}^{D_e \times D_e}$ are trainable parameters, that can differ between input and output layers.


%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\section{Proposed Method}
\label{sec:proposal}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\subsection{Training Method}
\label{sec:proposal_a}

In this study, we explored different approaches utilizing n-gram features to represent translation tokens instead of learning their representations as embedding matrix parameters or using n-gram features to augment embeddings.
Because we used BPE subwords to limit vocabulary sizes in our experiments, we will refer to the translation tokens as ``subwords'' and to their n-gram features as ``sub-subword features.''

We denote $V_x$ and $V_y$ as the vocabulary sizes, and $d_x$ and $d_y$ as the numbers of n-gram features for the input and output languages, respectively.
During training,
our model learns to produce embeddings and output matrices
from two sparse binary feature matrices $F_x \in \mathbb{R}^{V_x\times d_x}$ and $F_y \in \mathbb{R}^{V_y \times d_y}$
for the source and target language vocabularies, respectively.
Each element in the feature matrices indicates whether an n-gram feature is included in a subword.
When the input and output vocabularies are the same, such as when training BPE subwords jointly, the feature matrices $F_x$ and $F_y$ are equal.
We will refer to this part of the model as the feature-to-embedding (FTE) network.
Unlike the method presented by \shortciteA{takase_character_2019}, we use a simple feed-forward network.

Our proposed approach does not train feature matrices. Equations \eqref{eq:emb_x}, \eqref{eq:emb_y}, and \eqref{eq:out} are replaced with the following equations:
\begin{gather}\label{eq:noemb_x_c}
e_i^{(x)} \defeq \phi_x(F_x) x_i, \\
\label{eq:noemb_y_c}
e_j^{(y)} \defeq \phi_y(F_y) y_j, \\
p_t \defeq \textup{Softmax}(\phi_o(F_y) q_t + \phi_b(F_y)).
\end{gather}

The parameter weights for the feed-forward network, namely $\phi_x$, $\phi_y$, and $\phi_o$, are updated during training.
If weight tying is applied, then
\begin{equation}
\phi_o(F_y) = \phi_y(F_y)^{\intercal}.
\end{equation}

Figure \ref{fig:diagram} presents a diagram of the training model using weight tying.

Once the model is trained, we revert to equations \eqref{eq:emb_x}, \eqref{eq:emb_y}, and \eqref{eq:out} by pre-computing the values of $E_x$, $E_y$, $W_y$, and $b_y$ using the following equations:
\begin{gather}\label{eq:conclude_ex}
E_x \defeq \phi_x(F_x), \\
\label{eq:conclude_ey}
E_y \defeq \phi_y(F_y), \\
W_y \defeq \phi_o(F_y), \\
b_y \defeq \phi_b(F_y).
\end{gather}
After these calculations are completed, the FTE weights are no longer necessary and can be discarded. The resulting model is the same size as the base model.

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%% fig. 1
\begin{figure}[t]
\begin{center}
\centering
\includegraphics{28-1ia4f1.pdf}
\end{center}
\hangcaption{Simple diagram showing an encoder-decoder model using features to produce embeddings. The inputs and output are depicted with dashed borders and neural subnetworks have rounded corners. The model depicted in this diagram uses weight tying. The output bias vector $b_y$ is not shown for simplicity. On top of the baseline model, the boxes containing the n-gram feature matrices $F_x$ and $F_y$, and the feed-forward networks $\phi_x$ and $\phi_y$ have been added. $E_x$ and $E_y$ are not trainable parameters.}
\label{fig:diagram}
\vspace*{-1\Cvs}
\end{figure}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

Our goal is to compare different architectures and n-gram features and to determine their utility.
As shown later in Section \ref{sec:experiments}, we determined that a three-layer feed-forward network yields the best results among the compared architectures.
We use a rectifier activation function between layers.

Using all of the fixed-width n-grams can result in very large feature matrices. In practice, when using all available features, we can only train models on bigram features based on memory constraints.
To be able to use longer n-grams, we use a custom feature selection algorithm.
We extract all n-grams for every possible $n$ and select a final subset using the algorithm described in Section \ref{sec:algorithm}.


%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\subsection{Feature Selection}
\label{sec:algorithm}

The goal of the proposed algorithm is to select a small number of features that unambiguously represent a given vocabulary. 
As an example, consider a vocabulary that contains the subwords \emph{ana} and \emph{anana}.
When only using bigram features, both subwords are represented as \mbox{\texttt{\{ \^{}a, an, na, a\$ \}}}.
In order to disambiguate these two subwords, the trigram feature \texttt{nan} may be selected.
The algorithm selects the feature that disambiguates the maximum number of subword occurrences.

Given a large set of potential character n-gram features, the proposed feature selection algorithm selects a small subset.
The initial feature-set contains features for all n-grams contained in the subword vocabulary, where $n$ ranges from one up to the maximum subword length in the vocabulary.

Consider a vocabulary $V$ containing all subwords in a training dataset.
The proposed algorithm selects one character n-gram feature at a time to construct a binary decision tree.
Selection can be limited to a given number of features $M$ by stopping early.
The selected feature partitions the vocabulary into positive and negative subsets. The subwords in the former subset include the selected feature and those in the latter subset do not.
For every subset, we select the subword with the highest unigram frequency and regard it as reachable.
If there is a tie, one of the top-frequency subwords is selected randomly to be regarded as reachable.
The rest of the subwords in the vocabulary are considered to be unreachable.
The optimization objective is to maximize the total unigram probabilities of reachable subwords.
The features that best partition the vocabulary in terms of objective are selected.
The subword embeddings will be derived strictly from the selected character n-gram features.

Algorithm \ref{alg:featsel} presents the process described above in the form of pseudo-code. 
At each step, there is a set of partitions $G$ and candidate features.
Considering all combinations of these partitions and candidate features is very expensive.  Instead of considering all partitions in $G$, we only consider a subset $\Phi(G)$ containing the partitions with highest probabilities $p_g(g)$, defined in Algorithm \ref{alg:featsel}, summing up to a predefined threshold $T_{g}$.
When selecting a candidate n-gram feature $f$, we also consider a fixed number ($N_{\Psi}$), which is denoted as $\Psi(G)$. 
$\Psi(G)$ consists of the features with the top-$N_{\Psi}$ highest $\Omega(f, G)$ values.
$\Omega(f, G)$ ranks the relevance of the features with respect to their frequency within the partitions,
and it is defined as follows: 
\begin{gather}\label{eq:heuristic1}
\Omega(f, G) \defeq \sum_{g \in \Phi(G)} \omega(f, g) p_g(g), \\
\label{eq:heuristic2}
\omega(f,g) \defeq 1 - \left| 1 - 2 \frac{p_f(f,g)}{p_g(g)} \right|,  \\
\label{eq:heuristic3}
p_f(f,g) \defeq \sum_{\{v \in g | f \in Q(v)\}} p_v(v),
\end{gather}
where $Q(v)$ represents the n-gram features that appear in $v$.

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%% algo 1
\begin{algorithm}[t]
\DontPrintSemicolon
\input{04algo01.tex}
\caption{\rule[4pt]{0pt}{1zh}Feature selection algorithm. $\Psi$ and $\Phi$, defined in the text, are used to prune the search space. The notation $[\ ]$ represents an empty sequence, $[f_i]$ represents a sequence of a single element $f_i$, and the operator $\cdot$ denotes sequence concatenation.}
\label{alg:featsel}
\end{algorithm}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

These optimizations are optional and can be disabled by defining $\Phi(G) = G$ and $\Psi(G)$ as the set of all the features that have not been selected.

To illustrate the selections made by the proposed algorithm, next we present some statistics for an English-Turkish dataset when using a vocabulary size of approximately 64,000 words and $T_g = 0.95$.The dataset contained 2,399 bigrams and 14,933 trigrams. The number of trigram features was too large to train a model using the proposed approach on a single GPU. The number of features selected by the feature selection algorithm was 598, out of which 28.8\% were unigrams, 43.5\% were bigrams, 14.5\% were trigrams, 8\% were four-grams, 3.8\% were five-grams, and the remaining 1.4\% were longer n-grams. Other datasets yielded similar statistics.
Table \ref{tab:selected_feats} shows some features of more than two characters.

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%% table 1
\begin{table}[t]
\input{04table01.tex}
\caption{Some features of more than two characters when using BPE 32K.}
\label{tab:selected_feats}
\end{table}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%% table 2
\begin{table}[t]
\input{04table02.tex}
\hangcaption{Training data statistics. $^\dagger$~This dataset is sampled to make training sets of different sizes. $^\ddagger$~These datasets are sampled to make training sets of 200,000 sentences.}
\label{tab:datasets_original}
\end{table}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%


%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\section{Experiments and Analysis}
\label{sec:experiments}

To investigate the effectiveness of the proposed approach, we conducted four sets of experiments.
The experiments in Subsection \ref{sec:exp_approach} explain the choices made by the proposed approach in comparison to other approaches. Subsection \ref{sec:exp_voc} demonstrates how the proposed approach relates to the chosen vocabulary size and Subsection \ref{sec:exp_data} demonstrates how it relates to the training dataset size. Finally, Subsection \ref{sec:exp_back} demonstrates how the proposed approach can be combined with BT.


%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\subsection{Experimental Setup}

We ran experiments targeting five languages: English (En), Turkish (Tr), German (De), French (Fr) and Finnish (Fi). The source language was Turkish for the models targeting English. For the rest of the models, the source language was English. The Tr-En and En-tr models were trained using the same dataset. Table \ref{tab:datasets_original} shows the number of sentences of each dataset. These datasets were sampled to make smaller training sets to simulate a low-resource setting.

The training dataset for the English-Turkish translation task comes from \cite{TIEDEMANN12.463} and contains 205,000 parallel sentences. The German and French data were distributed as part of WMT-2014 \cite{bojar-etal-2014-findings,koehn2005epc} and the Turkish and Finnish data as part of WMT-2017 \cite{bojar-etal-2017-findings,koehn2005epc,TIEDEMANN12.463}. For each language pair, the corresponding \emph{newstest} was used to calculate the displayed BLEU scores \cite{papineni_bleu:_2002}.
The reported BLEU scores are case-sensitive and computed by \emph{sacrebleu} \cite{post_call_2018}.
It should be noted that the BLEU scores reported by \emph{sacrebleu} are not computed in the same way as those reported by \shortciteA{vaswani_attention_2017}.

The baseline model was a transformer ``\emph{base}'' \cite{vaswani_attention_2017} with eight attention heads, six layers in the encoder, and six layers in the decoder with embeddings of size 512 and 2,048 units in the hidden layers.
The hidden layers for producing embeddings (FTE) contained 3,000 units, except when indicated otherwise. This implementation was based on Sockeye \cite{hieber_sockeye:_2017}. Each training mini batch contained approximately 4,096 target words. All models were trained on a single \emph{GeForce GTX 1080 Ti} GPU.

In our experiments, the input and target languages shared a subword vocabulary and sub-subword features. All related weights were shared too. As a result, $E_x = E_y = W_y = E$ and $F_x = F_y = F$.

The significance testing was done using bootstrap resampling \cite{koehn-2004-statistical}.
We consider improvements with P-value smaller than $0.05$ to be significant.


%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\subsection{Approach Comparison Experiments}
\label{sec:exp_approach}

In this subsection, we compare different approaches to determine the best architecture.
All models were trained using a vocabulary size of approximately 32,000 subwords. All training datasets contained approximately 200,000 sentences. Excluding the Turkish-English pairs, the training data were sub-sampled from larger datasets.

Table \ref{tab:comparison} lists the results for different models divided into three sections. Section \emph{A} compares the feed-forward models ($l$-FF, where $l \in [1,4]$) to the self-attention (\emph{att}) approach proposed by \shortciteA{takase_character_2019}.
The \emph{1-FF} approach is equivalent to summing feature embeddings, similar to some of the models introduced in Section \ref{sec:intro} \cite{wieting_charagram:_2016,morishita_improving_2018}.
One can see that the best results in Section \emph{A} are provided by the three-layer feed-forward models. Adding extra layers does not result in any significant gains in terms of BLEU scores.

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%% table 3
\begin{table}[t]
\input{04table03.tex}
\hangcaption{%
Different approaches compared in terms of BLEU score results. The models starting with  ``\emph{2-gram}'' used all known bigrams as features, while those starting with ``\emph{selection}'' use the proposed feature selection algorithm. The \emph{$l$-FF} models use $l$-layered feed-forward networks to produce embeddings, while the those containing ``\emph{att}'' use the approach proposed by \protect\shortciteA{takase_character_2019}. For the \emph{+comp} models, the embeddings produced from the features are used to complement the traditional embeddings through addition. It should be noted that the numbers of parameters for all models are the same after training. Best scores excluding subword regularization are shown in \textbf{bold}.
}
\label{tab:comparison}
\end{table}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

Section \emph{B} in Table \ref{tab:comparison} compares the proposed feature selection algorithm to a naive approach of selecting the features with highest frequency. Both model sets use a similar number of features, but the proposed selection algorithm results in scores comparable to those achieved when using all bigrams, whereas the naive approach yields poor results. When using the frequency-selected bigrams approach, many subwords contain non-unique representations. As an example, if the features \texttt{"po"}, \texttt{"pa"}, \texttt{"oi"} and \texttt{"ai"} were not selected, the words \emph{point} and \emph{paint} would have the same representation: \{\texttt{"\^{}p"}, \texttt{"in"}, \texttt{"nt"}, \texttt{"t\$"}\}. In such cases, the subwords are indistinguishable and the output layer will always output the one with highest unigram probability.

While the cited approaches \cite{wieting_charagram:_2016,morishita_improving_2018,takase_character_2019} use n-gram features to complement standard trainable embeddings, our proposed approach avoids training subword embeddings directly.
Section C reveals that for small training datasets, using features to complement standard embeddings is sub-optimal.
For example, consider the results for models \emph{2-gram 3-FF} and \emph{2-gram 3-FF +comp}, where the later complements n-gram features with subword features.
The results are consistently better for the model without subword embeddings. We believe this occurs because without subword embeddings, models are forced to infer subword features from n-gram features, resulting in better generalization. In contrast, when subword embeddings are available subword features can be represented directly based on subword embeddings without using n-gram features, resulting in poor generalization and the learning of training data biases.

Section \emph{D} in Table \ref{tab:comparison} explores the subword regularization technique proposed by \citeA{kudo_subword_2018}. Their approach produced good results with significant improvements with respect to the baseline, in accordance with their report.
The sampling hyperparameters were $\alpha=0.2$ and $l=\infty$.
Their method obtained significantly better BLEU scores than our proposed approach for Turkish-English, English-Turkish, and English-Finnish. The subword regularization model also obtained a higher BLEU score for English-German but the gain (+0.3) is not significant.
For English-French, the subword regularization model obtained significantly worse results than our proposed model.
The reason for this may be that both English and French are not morphologically complex.
Combining our proposed approach with subword regularization improved the results non-significantly.


%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\subsection{Vocabulary Size Experiments}
\label{sec:exp_voc}

When using BPE subword segmentation, the vocabulary size can be regulated. The results in Table \ref{tab:voc} reveal the effects of varying vocabulary sizes.

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%% table 4
\begin{table}[b]
\input{04table04.tex}
\hangcaption{Results for different vocabulary sizes. The English-German models are trained on a large corpus and the English-Turkish models are trained on a small corpus. The scores marked with * have a statistically significant improvement with respect to the best baseline.}
\label{tab:voc}
\end{table}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

The English-German NMT models are trained on approximately 4.5 million sentences and the English-Turkish models are trained on approximately 0.2 million sentences.
Having a larger vocabulary leads to less word segmenting and shorter token sequences. When the training dataset is sufficiently large, a larger vocabulary results in higher BLEU scores.
However, performance drops when there is insufficient data for training the rarest subwords.
This effect is diminished by the proposed method because embeddings are inferred from more frequent sub-subword features.

The character-level models (\emph{char}) yield poor BLEU scores, particularly for the low-resource settings.
As shown by \shortciteA{cherry_revisiting_2018}, character-level NMT requires deeper models.

Table \ref{tab:size_stats} shows some statistics for English-Turkish models of different sizes.
The encoder and decoder parameters of each model take 168.2 MiB.
The size of the embedding matrix and the bias vector depends on the vocabulary size.
The \emph{model size} column shows the size of each model, baseline and proposed, after precomputing the embedding matrix and bias vector.
The \emph{with FTE} column shows the size of the proposed model without precomputing the embedding matrix and bias vector.
This size depends on the number of features displayed in the column \emph{features}.
The \emph{test time} column shows the seconds needed to translate the test set of 3,007 sentences.
Larger vocabulary sizes produce shorter subword sequences, which results in faster decoding speeds.
Decoding was done using beam search with a beam size of 5.
The \emph{updates/sec} column shows the times the parameters are updated per second during training.
The penalty on training time for the proposed model is bigger for larger vocabulary sizes.

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%% table 5
\begin{table}[t]
\input{04table05.tex}
\hangcaption{Statistics of English-Turkish models of different sizes. Model sizes are in MiB considering that each parameter takes 4 bytes. $^\dagger$ The character-level model has a vocabulary size of 275 characters.}
\label{tab:size_stats}
\end{table}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\subsubsection*{Grammatical Mistakes}
\shortciteA{sennrich_how_2017} demonstrated that character-level NMT performs poorly in terms of morphosyntactic agreement as the distance between tokens increases. Their evaluation data, denoted as \emph{lingeval97}, contain sentences with categorized synthetic errors.

We evaluated our models to determine how vocabulary size affects grammatical accuracy and to elucidate the effects of the proposed method.
The evaluate model is the large English-German corpus of approximately 4.5 M sentences.
Table \ref{tab:lingeval} lists accuracy metrics for different models for various error categories.
Out of the 13 error categories, the proposed method performs the best on ten.
The absolute best results are shown in bold font and the best results among the baseline models are underlined.
The results are divided into four groups.

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%% table 6
\begin{table}[t]
\input{04table06.tex}
\hangcaption{Grammatical accuracy for different error categories. The models correspond to the English-German results in Table \ref{tab:voc}. The best result out of the baseline models is underlined and the absolute best result is shown in \textbf{bold}.}
\label{tab:lingeval}
\end{table}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

Some errors seem to be less common with smaller vocabulary sizes, even when the BLEU score is lower.
When comparing each vocabulary size independently, we observe that our proposed model is superior to the baseline model with vocabulary sizes larger than 2~K subwords.
The effect of including sub-subword information is larger for larger vocabulary sizes.
As Table \ref{tab:voc} shows, our proposed model does not significantly improve the BLEU scores for this large corpus.
However, our proposed model is more resilient to the grammatical errors evaluated by \emph{lingeval97}.
The baseline and proposed models of 64 K subwords both have the same BLEU score of 26.5 but the proposed model behaves better for 10 out 13 grammatical mistake categories.

The first group of results is related to morpheme order (\emph{Compound}) and transliteration (\emph{Transl}). Small vocabularies work best for these error categories based on the nature of the target problem. Overall, including character n-gram information improves transliteration accuracy.

In the German language, the pronoun ``Sie'' can mean ``they'' or ``she.''
NMT models must choose the correct grammatical number for verbs by referring to source sentences. Including character n-gram features improves accuracy because the third-person \emph{singular} English verbs in the source sentences include features indicating that they end with the letter ``s.''

The third group of results is related to agreement. Morphosyntactic agreement between a subject and verb (\emph{SubjVerb}), and between determiners and nouns in noun phrases (\emph{NP}), considers number and gender. Agreement between verbs, particles (\emph{VerbPart}), and auxiliary verbs (\emph{Aux}) is improved by the proposed method. Excluding auxiliary verb agreement, these error categories are less common with larger vocabularies (i.e., shorter sequences).

The final group of errors changes the polarity of a sentence by either inserting or deleting polarity markers. When the negating word ``nicht'' or other polarity affixes are inserted (\emph{NichtIns}, \emph{AffixIns}), the models operating on longer sequences perform better because they are more likely to drop source sentence information.

There is no optimal vocabulary size. When considering only the BLEU scores, the larger vocabulary sizes are better. However this, improvements come as a trade-off with some error categories such as \emph{NichtIns} and \emph{AffixIns}.


%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\subsection{Corpus Size Experiments}
\label{sec:exp_data}

Table \ref{tab:dataset} compares the results of different methods for different dataset sizes.
We sampled random sentences from the English-German training corpus to construct training sets of increasing sizes.
We then trained NMT models using these sets.
The vocabulary size was approximately 64,000 subwords.
We trained three models for each dataset.

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%% table 7
\begin{table}[b]
\input{04table07.tex}
\hangcaption{%
English-German NMT results for different dataset sizes. The benefit of the proposed method decreases as the size of the training dataset increases. The best results are shown in \textbf{bold}. It should be noted that the number of parameters for the proposed model after training is the same as that for the baseline. The scores marked with * have a statistically significant improvement with respect to their corresponding baseline.
}
\label{tab:dataset}
\end{table}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

One can see that the benefit of applying the proposed method decreases for larger training datasets.
For the full dataset of approximately 4.5 M sentences, the proposed method does not improve the results of the baseline model.

The models trained on smaller datasets are more prone to overfitting. We believe the proposed method provides better generalization because subword features are derived from n-gram features. This regularization effect is more prominent for small datasets. For large datasets, the need for regularization is lessened and the proposed method is less salient.


%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\subsection{BT Experiments}
\label{sec:exp_back}

BT \cite{sennrich_improving_2016,poncelas_investigating_2018,edunov_understanding_2018} has been widely used to improve NMT. BT is particularly helpful for low-resource language pairs, but it requires a big monolingual corpus of the target language.
A large monolingual corpus may not exist for some low-resource languages.

We measured how the proposed approach behaves in combination with BT.
Table \ref{tab:back} compares the BLEU scores for five English-to-Turkish NMT models.
The first two rows contain the best results from Table \ref{tab:voc}.
The three models using BT are represented by the remaining rows.
These models have vocabulary sizes of approximately 32,000 words.
We translated four million randomly sampled sentences from the Turkish monolingual common crawl corpus.
The model \emph{baseline-baseline} uses the baseline model with an 8,000 word vocabulary from Table \ref{tab:voc} to perform BT on sentences.
The models \emph{proposed-baseline} and \emph{proposed-proposed} use the proposed model with a vocabulary size of 64,000 words to perform BT on the monolingual sentences.
We determined that there is no benefit to using the proposed method with synthetically enhanced training data.

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%% table 8
\begin{table}[t]
\input{04table08.tex}
\hangcaption{%
Results for different BT approaches for English-to-Turkish translation. Using the proposed approach to perform BT on the monolingual sentences to generate a synthetic corpus (\emph{proposed-baseline}) yields the best performance. It should be noted that the number of parameters for the proposed model after training is the same as that for the baseline. The scores marked with * have a statistically significant improvement with respect to \emph{baseline-baseline}.
}
\label{tab:back}
\end{table}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%


%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\section{Conclusion}
\label{sec:conclusion}

We explored different approaches for utilizing character n-gram features for subword-level NMT without changing baseline model architectures or number of parameters.
We analyzed the best approach for utilizing n-gram features and determined that a nonlinear function seems to perform better than a (weighted) sum of plural feature embeddings.
For low-resource language pairs, translation accuracy (BLEU score) can be improved by utilizing n-gram features.
This approach also improves the grammatical accuracy of the produced translations.

We explicitly analyzed how the vocabulary size affects grammatical accuracy and found that although models using larger vocabularies tend to produce fewer grammatical errors, they are difficult to train when training data is scarce.
Using n-gram features to infer embeddings can help with training.

By varying the dataset size, we determined that the proposed method works particularly well on small datasets, but its benefits decrease as the dataset size increases. When combining the proposed method with BT, we determined that it is helpful to use the proposed method with a BT model, but it provides no benefits when applied to a forward translating model after incorporating a large synthetic dataset into the training data.

In the future, we wish to explore how the proposed approach can be applied to tasks other than NMT, such as named entity recognition.
Additionally, it would be of interest to compare different feature selection algorithms.


%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\bibliographystyle{jnlpbbl_1.6}
\bibliography{04refs}


%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\begin{biography}

\bioauthor[:]{Ander Martinez}{%
From 2014 to 2019, he was a Research Assistant and Ph.D. candidate with the Division of Information Science of the Nara Institute of Science and Technology, Nara, Japan.
He is currently a researcher at Fujitsu Laboratories, Kawasaki, Japan. His research interests include machine translation and dialogue modeling.
}

\bioauthor[:]{Katsuhito Sudoh}{%
Associate professor at the Nara Institute of Science and Technology.
He received his bachelor's degree in engineering in 2000 and his master's and Ph.D. degrees in informatics in 2002 and 2015, respectively, from Kyoto University.
He worked with the NTT Communication Science Laboratories from 2002 to 2017.
}

\bioauthor[:]{Yuji Matsumoto}{%
Team leader of the Knowledge Acquisition Team at
Riken AIP.  He received his M.S. degree and Ph.D. in information science from
Kyoto University in 1979 and in 1990, respectively.  He was a professor at
Nara Institute of Science and Technology from 1993 to 2020.
}
\end{biography}


%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\biodate




\end{document}

