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


%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%% author's definition
%%%%\usepackage{subcaption}
%%%%\usepackage{booktabs}
\usepackage{multirow}
\usepackage{ulem}
%%%%\usepackage{tikz}
%%%%\usepackage{tikz-qtree}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\Volume{29}
\Number{2}
\Month{June}
\Year{2022}
%%%%\Issuetitle{Special Issue: XXXXXXXX}

\received{2021}{12}{1}
\revised{2022}{3}{1}
%%%%\rerevised{2006}{5}{6}
\accepted{2022}{3}{20}

\setcounter{page}{587}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\esubject{General Paper}
\etitle{Neural Machine Translation with Synchronous \\
	Latent Phrase Structure}
\eauthor{Shintaro Harada\affiref{Author_1} \and Taro Watanabe\affiref{Author_1}} 
\eabstract{%
It has been reported that grammatical information is useful for machine translation (MT) tasks. However, the annotation of grammatical information incurs significant human costs. Furthermore, it is not trivial to adapt grammatical information to MT because grammatical annotation usually employs tokenization standards that might not capture the relation between two languages and consequently, subword tokenization such as byte-pair-encoding is used to alleviate out-of-vocabulary problems; however, this might not be compatible with those annotations. In this work, we introduce two methods to incorporate grammatical information without supervising annotation explicitly: first, the latent phrase structure is induced in an unsupervised fashion from an attention mechanism; and second, the induced latent phrase structures in the encoder and decoder are synchronized so that they are compatible with each other using constraints during training. We demonstrate that our approach performs better in two tasks: translation and word alignment, without extra resources. We found that the induced phrase structures enhance the precision of alignments through the synchronization constraint after exact phrase and alignment structure analysis.
}

\ekeywords{Machine Translation, Syntactic Structure, Deep Learning}

\headauthor{Harada and Watanabe}
\headtitle{Neural Machine Translation with Synchronous Latent Phrase Structure}

\affilabel{Author_1}{}{Nara Institute of Science and Technology (NAIST)}


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

\maketitle


%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\section{Introduction}

Although machine translation (MT) has achieved improved performance through neural machine translation (NMT), the translation qualities for distant languages are still poor \cite{johnson_2017_googles}. The MT model may not thoroughly learn the relationship between the word order or semantic representation in the source and target languages. To address this problem, the statistical MT (SMT) incorporates synchronous grammar to achieve more linguistically accurate translations in which complex structural relations between the source and target languages are expressed using phrase structure \cite{wong_2005_machine}. 
The synchronous grammar expresses the complex relationships between the source and target languages and incorporates the phrase structures to enable more linguistically accurate translation. A similar concept can be employed for NMT to improve performance on distant language pairs. Furthermore, it can provide syntactic correspondence to users and achieve a precise alignment. However, the grammatical annotation requires extensive human resources. In addition, such grammatical annotation is performed on word-level granularities, which might not be the best tokenization for the MT tasks due to language mismatch or out-of-vocabulary problems; sub-word tokenization such as byte-pair-encoding (BPE) \cite{sennrich_2016_neural} is often employed to alleviate this problem. As a result, it is challenging to incorporate grammatical information into NMT that handles multiple languages simultaneously.

In this work, we propose an approach that induces the phrase structure of source and target sides without syntactic annotations and synchronizes them to improve the performance and interpretability of MT. We define MT performance and interpretability as follows: the performance is the quality of translation and the interpretability is the highly precise alignments that justify the system outputs. We employ a syntactic distance schema, representing a binary tree using scalar values, to induce a phrase structure. To improve the MT performance and interpretability, we employ the synchronous constraint by mean squared error (MSE) and RANK loss into the attention weight to associate the phrase structure in the source language with its corresponding one in the target language. The approach is trivial to plug into existing Transformer-based MT models \cite{vaswani_2017_attention} without substantial implementation costs.

We demonstrated our approach in three tasks: translation, constituency parsing, and word alignment. Our models achieved better performance of translation than Transformer baselines in the WMT'16 English-German, WMT'14 English-French, ASPEC Japanese-English, and ASPEC Japanese-Chinese datasets. In the parsing task, our model failed to induce a high-quality phrase structure compared with the previous study \cite{htut_2019_inducing} in the IWSLT'14 English-German dataset. However, our model could capture the phrase structures suited for the translation task that might not be represented by a monolingual parser such as the Stanford Parser.\footnote{\url{https://nlp.stanford.edu/software/lex-parser.shtml}} Our models produced better precise alignments in the alignment task, indicating that our models have higher interpretability of outputs than the baseline models. All code is available at \url{https://github.com/i13harada1s/nmt_sync_gram}.


%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\section{Backgrounds}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\subsection{NMT with Supervised Tree Structure}

Previous studies have reported that supervised phrase structures \cite{eriguchi_2017_learning,wang_2018_tree} and dependency structures \cite{ma_2019_improving,deguchi_2019_dependency} can improve the performance of MT. However, these approaches require an annotated corpus with syntactic structures. In addition, such syntactic annotation is performed on word-level granularities, which might not be the best tokenization for the MT tasks due to language mismatch or out-of-vocabulary problems. Subword tokenization is often employed to alleviate this problem. However, applying subword tokenization to syntactic structures might require a different approach for each language, which is difficult.


%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\subsection{NMT with Unsupervised Tree Structure}

\citeA{shen_2018_neural} introduced the concept of ``syntactic distance'' that represents the syntactic relation of word pairs. Similarly, \citeA{shen_2018_ordered} introduced ``ordered neurons'' that allowed long- or short-term information learning by a novel gating mechanism and activation function. \citeA{kim_2019_unsupervised} applied amortized variational inference for recurrent neural network grammar to learn phrase structures in an unsupervised manner. \citeA{wang_2019_tree} added an extra constraint to the multi-head self-attention mechanism to encourage the attention heads to follow phrase structures. \citeA{shen_2020_structformer} introduced a constrained multi-head self-attention mechanism that simultaneously allowed the induction of phrases and dependency structures.

These works successfully learned to induce a phrase structure from a language modeling task without additional linguistic resources. \citeA{htut_2019_inducing} described the translation task as a conditional language modeling task with source and target representations; thus, the relationship of these representations helps to induce phrase structures. Unfortunately, although grammatical information can provide interpretability, the latent phrase structures have not been explicitly used in previous works.

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%% fig. 1
\begin{figure}[t]
\begin{center}
\includegraphics{29-2ia12f1.pdf}
\end{center}
\caption{Transformer architecture.}
\label{fig:transformer}
\end{figure}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%


%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\subsection{NMT with Transformer}

We employed the Transformer \cite{vaswani_2017_attention} in Figure~\ref{fig:transformer} as our NMT base model. This encoder--decoder model relies on an attention mechanism for computing the contextual representations of the source and target text. The encoder and decoder are composed of multiple layers including multi-head attention (MHA) and feed-forward sublayers. To compute the MHA output, three inputs, ${\mathbf{Q}}$, a key ${\mathbf{K}}$, and a value $\mathbf{{V}}$ are projected into $N$ different sub-spaces, namely heads, with each output computed in each subspace and then projected back to the original space after aggregation:
\begin{gather}
\hat{\mathbf{Q}}^{1:N} = \mathbf{Q} \mathbf{W}_Q, 
    \hat{\mathbf{K}}^{1:N} = \mathbf{K} \mathbf{W}_K, 
    \hat{\mathbf{V}}^{1:N} = \mathbf{V} \mathbf{W}_V \\
\mathbf{H}^n = \mathbf{A} \hat{\mathbf{V}}^n = \mathrm{softmax} 
\left( \frac{\hat{\mathbf{Q}}^n \hat{\mathbf{K}^n}^{\top}}{\sqrt{d_h}} \right)
\hat{\mathbf{V}}^n
\label{eq:2}
\\
\mathrm{MHA}(\hat{\mathbf{Q}}, \hat{\mathbf{K}}, \hat{\mathbf{V}}) = 
\mathrm{concat} \left( \mathbf{H}^1, ..., \mathbf{H}^N \right) \mathbf{W}_O
\end{gather}
where 
$\mathbf{W}_Q \in \mathbb{R}^{d_o \times d_h}$, 
$\mathbf{W}_K \in \mathbb{R}^{d_o \times d_h}$, 
$\mathbf{W}_V \in \mathbb{R}^{d_o \times d_h}$, and 
$\mathbf{W}_O \in \mathbb{R}^{N{d_h} \times d_o}$ 
are the projection parameters. $d_o$ is the dimension of the original space. $d_h=d_o/{N}$ denotes the dimension of the subspace. The value $\mathbf{A}$ denotes the attention probability for the $j$-th target token over the $i$-th source token, computed by the $n$-th head.

The Transformer \cite{vaswani_2017_attention} is a very popular architecture for the translation tasks due to its accuracy and efficiency. The Transformer decoder employs the autoregressive model that predicts the next token that reads all the previous ones. The attention is also used in alignment tasks to achieve high alignment accuracy as it represents the relationship between the source and target tokens \cite{garg_2019_jointly,chen_2020_accurate}.


%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\subsection{Synchronous Attention Constraint}

\citeA{deguchi_2021_synchronous} found that the NMT performance could be improved by synchronizing the encoder attention to the decoder attention, which is represented by:
\begin{gather} 
    \mathcal{L}_{sync} = \sum_{i,j}\left(A^{dec}_{ i,j}-\tilde{A}^{dec}_{i,j} \right)^2, \\
    \tilde{\mathbf{A}}^{dec} = {\mathbf{A}}^{enc-dec} {\mathbf{A}}^{enc} {{\mathbf{A}}^{enc-dec}}^{T},
\end{gather}
where ${\mathbf{A}}^{enc}$ and ${\mathbf{A}}^{dec}$ are the encoder- and decoder-side attention respectively, and ${\mathbf{A}}^{enc-dec}$ is the encoder-decoder attention. $\tilde{\mathbf{A}}^{dec}$ is the attention weight in the target language space projected from the source language space using the encoder-decoder attention.

The encoder--decoder attention can be viewed as a soft word alignment, which is a weight that can project the source vector into the target vector space without additional model parameters. It can agree with the source and target attention using the constraint based Mean Squared Error (MSE). Furthermore, the supervised dependency structure was embedded into the source- and target-side attention to improving the performance of the NMT.

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%% fig. 2
\begin{figure}[t]
\begin{center}
\includegraphics{29-2ia12f2.pdf}
\end{center}
\hangcaption{Architecture used in this paper for latent phrase structure induction. The grammar induction head takes the feature representation as input and outputs the syntactic distance and self-attention gate based on it. Finally, the self-attention in Transformer layers is constrained by the self-attention gate.}
\label{fig:structformer}
\end{figure}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%


%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\section{Synchronous Latent Phrase Structure}


%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\subsection{Latent Phrase Structure Induction (LPSI)}

Our model architecture is shown in Figure~\ref{fig:structformer}; it employs syntactic distance \cite{shen_2018_neural} to induce phrase structures. Each syntactic distance $d_i$ is associated with each span $[i, i+1)$ that indicates the relative order of hierarchical splitting of a sentence into smaller components. For example, Figure 3 shows the target syntactic distance between ``woman'' and ``with'' covers the phrase ``the woman with the telescope''. Mathematically, syntactic distance $d_i$ is computed through the phrase grammar induction head in Figure~\ref{fig:structformer}:
\begin{equation}
	d_i = \mathbf{W}_D\boldsymbol{u}_i,
    \label{eq:induction}
\end{equation}
where $\boldsymbol{u}_i$ is the feature embedding of the $i$-th token, 
\pagebreak
independently computed by the $N_{inductor}$ extra layers different from those already used in the NMT model. \citeA{shen_2018_neural} obtained $\boldsymbol{u}_i$ using the convolution layers.
This study involved the use of Transformer layers for feature extraction instead of convolution because the Transformer performs similarly to convolution and can be easily integrated with Transformer-based NMT. $\mathbf{W}_D \in \mathbb{R}^{d_u \times 1}$ is the parameter to calculate the syntactic distance $d_i$ . Note that \citeA{shen_2018_neural} used ReLU in ``Eq.\ref{eq:induction}'' but it was omitted mainly because it was not used in the original implementation\footnote{\url{https://github.com/yikangshen/PRPN}} and prior study \cite{shen_2020_structformer} using syntactic distance. In addition, syntactic distance does not guarantee non-negativity and maintains hierarchical relations.

To incorporate syntactic distance into the Transformer, we modeled the attention gate using stick-breaking process as follows \cite{shen_2018_neural}:
\begin{gather}
    P(b_t = i) = (1 - \alpha_{i, t}) \prod_{j=i+1}^{t-1}\alpha_{j,t}, \\
    \alpha_{j,t} = \mathrm{sigmoid}((d_t-d_j)\cdot \tau). \nonumber
\end{gather}
$\alpha_{j,t}$ is a probability value representing the syntactic relationship between distances $d_j$ and $d_t$. $\tau$ is the temperature hyperparameter that controls the sensitivity of $\alpha_{j,t}$ to differences between syntactic distances. We introduced a gate value $g_{i,t}$, as the probability that the words in time step $t$ and $i$ that belong to the same hierarchy. $g_{i,t}$ was computed as the cumulative distribution function of $P(b_t = i)$ as follows:
\begin{equation}
	g_{i,t} = P(b_t \leq i) = \prod_{j=i+1}^{t-1}\alpha_{j,t},
\end{equation}
where $t$ denotes the current time step. $b_t$ indicates the break position in a phrase structure.

The phrase structured MHA is defined based on the gates:
\begin{equation}
  \tilde{a}^{1:M}_{i,t} = \frac{g_{i,t} \cdot a^{1:M}_{i,t}}{\sum_{i}{g_{i,t} \cdot a^{1:M}_{i,t}}},
\end{equation}
where $a$ is an element of attention $\mathbf{A}$ and $M$ is the number of attention applying gates. The gate $g_{i, t}$ is treated as a weight such that the attention for the $t$-step is constrained to focus on the same level of the hierarchical phrase structure for the $i$-th item. Here, $\tilde{a}$ was used instead of the elements of attention $\mathbf{A}$.


%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\subsection{Synchronous Structure Constraint}

In the MT model, the encoder and decoder learn separate phrase structures that are not necessarily synchronized and thus, are not compatible with each other in terms of vector representations. Therefore, synchronizing each phrase structure learned in the encoder and decoder may improve translation performance in the same manner as done by synchronous grammar in SMT. Inspired by \citeA{deguchi_2021_synchronous}, we projected the structure expressed by the encoder syntactic distance to the target one and incorporated constraints such that the source and target syntactic distances agreed. In Figure~\ref{fig:synchronization}, the source syntactic distance was projected to the target syntactic distance through the attention weight. The syntactic correspondence between Japanese and English was learned from the target and projected syntactic distances for the phrase ``saw the woman with the telescope''.

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%% fig. 3
\begin{figure}[t]
\begin{center}
\includegraphics{29-2ia12f3.pdf}
\end{center}
\hangcaption{Example of the relation between syntactic distances and synchronous constraint on the Japanese to English translation task. Starting from the induction of source and target syntactic distances, we project the source syntactic distance to the target one through encoder--decoder attention. The syntactic correspondences of source and target language in the encoder--decoder attention can be done by measuring the difference between the target syntactic distance and the projected one with the synchronous constraint.}
\label{fig:synchronization}
\end{figure}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

The synchronous constraint can be represented by MSE of the syntactic distance between the source and target languages
\begin{equation}
    \mathcal{L}_{sync} = \sum_{i}\left( d_{i}-\tilde{d}_{i} \right)^2.
\end{equation}
$\tilde{\boldsymbol{d}}$ is the syntactic distance for the decoder projected from the syntactic distance in the encoder, which is computed as:
\begin{equation}
    \tilde{\boldsymbol{d}} = \mathbf{P}^{(l)} \boldsymbol{e},
\end{equation}
where $\boldsymbol{e}$ is the syntactic distance of the encoder. $\mathbf{P}^{(l)}  \in \mathbb{R}^{J \times I}$ is the $l$-th encoder-decoder attention weight representing the relationships between the encoder and decoder representations. It works similarly to MHA, where $I$ and $J$ are the lengths of the source and target sentence, respectively. The $l$-th encoder-decoder attention weight is computed as:
\begin{equation}
    \mathbf{P}^{(l)} = \mathrm{softmax}(\frac{\hat{\mathbf{Q}}_{dec}^{(l)} \hat{\mathbf{K}}_{enc}^{(l) \top}}{\sqrt{\delta_{h}}}),
\end{equation}
where $\mathbf{Q}_{dec}^{(l)}$ and $\mathbf{K}_{enc}^{(l)}$ are $l$-th decoder and encoder hidden weights.

The important element in a phrase structure is the hierarchical positional relationship derived from a syntactic distance.  For example, two syntactic distances $\boldsymbol{d}=(9.2, 8.7, 5.1, 2.7, 4.5)$ and $\boldsymbol{\tilde{d}}=(6.1, 4.2, 3.9, 0.5, 3.1)$ represent the same phrase structure. However, MSE over-penalizes models, such as $L_{sync}=\sum_i(\tilde{d}_i-d_i)=38.1$, as a result of predicting exact distances. Hence, we used the RANK loss \cite{burges_2005_learning} proposed by \citeA{shen_2018_straight} that considers the relative differences when computing the hierarchical positions. Applying the RANK loss function to the synchronous constraint, we obtain the following relation:
\begin{equation}
    \mathcal{L}_{sync} = \sum_{i,j>i}\mathrm{hinge}\left( d_i-d_j, \tilde{d}_i-\tilde{d}_j, \epsilon \right),
\end{equation}
where ${\mathrm{hinge}(x_1, x_2, \epsilon) = \max \left( 0, \epsilon - \mathrm{sign}(x_1) \cdot x_2 \right)}$,
$\epsilon$ is the margin hyperparameter and $\mathrm{sign}(x)$ is the sign function. The RANK loss can be regarded as a softer constraint because our example becomes $L_{sync} = \sum_{i,j>i}\mathrm{hinge}\left( d_i-d_j, \tilde{d}_i-\tilde{d}_j, \epsilon=1.0 \right) = 0.9$. Hence, the overall objective $\mathcal{L}$ is represented by:
\begin{gather}
    \label{objective}
    \mathcal{L} = \mathcal{L}_{trans} + \lambda \mathcal{L}_{sync}, \\ 
    \mathcal{L}_{trans} = -\sum_i^J{\log{p(y_i| \boldsymbol{x}, \boldsymbol{y}_{<i})}}, \nonumber 
\end{gather}
where $\mathcal{L}_{trans}$ is the objective of the machine translation task and $\lambda \geq 0$ is hyperparameter to control the degree of the synchronous constraint $\mathcal{L}_{sync}$. $ \boldsymbol{x}$ and $\boldsymbol{y}$ denote the source and target sentences, respectively.


%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\section{Experiments}

We evaluated our proposed model on three tasks: translation, constituency parsing, and word alignment. We implemented the models using the Fairseq sequence modeling toolkit \cite{ott_2019_fairseq}.


%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\subsection{Training Details}

We employed a feature extraction layer\footnote{It is the integer that performed best in the development set of preliminary experiments, which were tested in the range of $1 \leq N_{inductor} \leq 3$.} $N_{inductor}=1$ to induct the phrase structures in both the encoder and decoder and the second encoder-decoder MHA from top \cite{garg_2019_jointly} to synchronize the encoder and decoder syntactic distances. The temperature hyperparameter\footnote{It is the number that performed best in the development set of preliminary experiments, which were tested in the range of $0.1 \leq \tau \leq 1.0$ in increments of 0.1.} was set to $\tau=1.0$. The synchronous constraint hyperparameter\footnote{They are the numbers that performed best in the development set of preliminary experiments, which were tested in the range of $0.01 \leq \lambda \leq 0.1$ in increments of 0.01.} was set by $\lambda=0.01$ and $\lambda=0.05$ for MSE and RANK loss with $\epsilon=0.1$. We trained the models with the Adam optimizer \cite{adam_2014_kingma} using $\beta_1=0.9, \beta_2=0.98$ on 8 GeForce RTX 3090 GPUs.

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%% table 1
\begin{table}[b]
\input{12table01.tex}
\caption{Number of sentences in each dataset.}
\label{statistic}
\end{table}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%


%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\subsection{Tasks}


%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\subsubsection{Machine Translation}

We evaluated the effectiveness of the synchronous latent phrase structures for the MT tasks on the WMT'16 English-German, WMT'14 English-French, ASPEC Japanese-English \cite{nakagawa_2016_aspec}, and ASPEC Japanese-Chinese \cite{nakagawa_2016_aspec} datasets. We trained the translation models by following the instructions for constructing the baseline system of WMT'16 English-German \cite{ott_2018_scaling}, WMT'14 English-French \cite{ott_2018_scaling}, WAT'18 Japanese-English,\footnote{\url{http://lotus.kuee.kyoto-u.ac.jp/WAT/WAT2018/baseline/dataPreparationJE.html}} and WAT'18 Japanese-Chinese.\footnote{\url{http://lotus.kuee.kyoto-u.ac.jp/WAT/WAT2018/baseline/dataPreparationCJ.html}} These datasets employ BPE \cite{sennrich_2016_neural} for subword tokenization. Table~\ref{statistic} lists the detailed data statistics. To compare the effectiveness of the synchronous latent phrase structure, we ran additional baselines without latent phrase induction but with synchronous constraints applied to the attention weights \cite{deguchi_2021_synchronous}.  We used \texttt{\small transformer\_vaswani\_wmt\_en\_de\_big} model configuration of Fairseq \cite{ott_2019_fairseq} for the WMT'16 English-German and WMT'14 English-French datasets.  We used the \texttt{\small transformer} model configuration of Fairseq \cite{ott_2019_fairseq} for the ASPEC Japanese-English and Japanese-Chinese datasets. The number of parameter updates for the model was set to 500,000. The learning rate increased linearly to $5e- 4$ for the 4,000 warmup steps and subsequently decayed proportionally to the inverse of the square root of the number of updates \cite{vaswani_2017_attention}. We ran an inference with a beam size of four and five in WMT and WAT, respectively, and reported the quality of translation with BLEU \cite{papineni_2002_bleu}.


%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\subsubsection{Unsupervised Constituency Parsing}

We evaluated the qualities of the induced latent phrase structure from the MT tasks in the IWSLT'14 German-English datasets. We trained the word-wise translation models on the IWSLT'14 German--English datasets \cite{htut_2019_inducing}. The reference parse tree was created using Stanford CoreNLP.\footnote{\url{http://nlp.stanford.edu/software/stanford-corenlp-4.1.0.zip}} Table~\ref{statistic} lists the detailed data statistics. We used the \texttt{\small transformer\_iwslt\\\_en\_de} model configuration of Fairseq \cite{ott_2019_fairseq}. The number of parameter updates for the model was set to 100,000. The learning rate increased linearly to $5e- 4$ for the 4,000 warmup steps and subsequently decayed proportionally to the inverse of the square root of the number of updates \cite{vaswani_2017_attention}.

We reported an unlabeled F-measure (UF) as the quality of English latent phrase structures induced from the bottom syntactic distances using the scoring script \texttt{\small Evalb}.\footnote{\url{https://nlp.cs.nyu.edu/evalb}} Unlabeled F-measure (UF) is a F-measure that ignores constituency labels and is evaluated using only bracketing. As the IWSLT'14 test data include data consisting of multiple sentences, we excluded them for evaluation because the parser could not handle inputs of multiple sentences. This filtering resulted in 6,200 reference trees.


%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\subsubsection{Unsupervised Word Alignment}

We measured the impact of the alignment qualities represented by our synchronous grammar against other models, including the statistical model FAST-ALIGN\footnote{\url{https://github.com/clab/fast_align}} \cite{dyer_2013_simple} and multi-threaded version of the GIZA++ toolkit\footnote{\url{https://github.com/moses-smt/mgiza/}} implemented by \citeA{gao_2008_parallel}. 
We used the same experimental settings described by \citeA{chen_2020_accurate} and scripts\footnote{\url{https://github.com/lilt/alignment-scripts}} for preprocessing and evaluation. In addition, we used KFTT (Kyoto Free Translation Task) dataset\footnote{\url{http://www.phontron.com/kftt/index-ja.html}} as a distant language pair setting. We also used a cleaned training, alignment development, and test sets. Unlike previous studies \cite{chen_2020_accurate}, we used a joint source and target BPE \cite{sennrich_2016_neural} with 32,000 merge operations for all language pairs. Table~\ref{statistic} lists the detailed data statistics. The \texttt{\small transformer\_iwslt\_en\_de} model configuration was used for all datasets. The number of parameter updates for the model was set to 100,000. The learning rate increased linearly to $5e-4$ for the 4,000 warmup steps and decayed proportionally to the inverse of the square root of the number of updates \cite{vaswani_2017_attention}.

We reported the alignment quality in the penultimate layer following the study \cite{garg_2019_jointly} with the the alignment error rate (AER) introduced by \citeA{vilar_2006_aer}. The trained model was BPE-wise in this task, but the reported AER was word-wise. Furthermore, we report the quality of synchronized alignments that combine each unidirectional alignment. The combination method is the \texttt{\small grow-diagonal} heuristic \cite{koehn_2005_edinburgh}, in which alignments are greedily enlarged from the intersecting alignments.

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%% table 2
\begin{table}[b]
\input{12table02.tex}
\hangcaption{Results of the translation task in WMT'16 English to German (En$\rightarrow$De) and ASPEC Japanese-to-English (Ja$\rightarrow$En). The translation quality is reported in BLEU \protect\cite{papineni_2002_bleu} and the values in bold indicate the best performance.  \texttt{\small sacreBLEU} \protect\cite{post_2018_call} was used for WMT'16 English to German (En$\rightarrow$De) and WMT'14 English to French (En$\rightarrow$Fr). The numbers with {\dag} are significantly different $(p < 0.01)$ from the transformer baseline measured by paired bootstrap resampling \protect\cite{koehn_2004_statistical}.
}
\label{results:translation}
\end{table}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%


%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\subsection{Results}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\subsubsection{Machine Translation}

Table~\ref{results:translation} compares the performance of our methods against baselines. A Transformer with a latent phrase structure (+ LPSI) generally has better translation performance than the baseline Transformer. In WMT'16 English-German, WMT'14 English-French, ASPEC Japanese-English, and ASPEC Japanese-Chinese, the NMT model with the synchronous latent phrase structure by MSE loss (SynchMSE) further improved by 0.12, 0.11, 0.25, and 0.48 BLEU points, respectively, and the synchronous latent phrase structure by RANK loss (SynchRANK) further improves by 0.22, 0.19, 0.36, and 0.18 BLEU points, respectively. SynchRANK can be useful for MT tasks in English-German, English-French, and Japanese-English. In Japanese-Chinese, the use of SynchMSE can be useful for MT tasks. Our models with the synchronous latent phrase structure exhibited better MT performance than the baseline for all datasets. 

Table~\ref{results:translation} shows that SynchMSE and SynchRANK show more improvement than SynchAttn \cite{deguchi_2021_synchronous}, indicating that the synchronization of phrase structure is more useful than self-attention. \citeA{deguchi_2021_synchronous} introduced a synchronous constraint with a supervised dependency structure for MT tasks. As demonstrated by \citeA{deguchi_2021_synchronous}, these facts showed that the use of explicitly synchronizing inducted syntactic structures is effective for the MT task. Interestingly, we found that the synchronous syntactic constraint differed between syntactically close languages such as English-German and distant languages such as Japanese-English.

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%% table 3
\begin{table}[b]
\input{12table03.tex}
\hangcaption{Comparison of the reference and translation results: the top one is an example of WMT'16 English-German, and the bottom one is an example of ASPEC Japanese-English.}
\label{results:translation_examples}
\end{table}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

Table~\ref{results:translation_examples} compares the translation results of our models (SynchMSE and SynchRANK) with the Transformer as a baseline. In the WMT'16 English-German test set, the baseline treats ``Zwei deutsche Journalisten'' (= two German journalists) as a subject, but the reference and our models treat ``Er'' (he) as a subject. In the ASPEC Japanese-English test set, the baseline outputs ``This paper'' which does not appear as a subject in the source sentence. However, the reference and our models treat ``Utilization'' as a subject. These make the word order close to the reference and BLEU \cite{papineni_2002_bleu} scores it higher than the baseline. The improvements related to word order account for most of the examples obtained using compare-mt\footnote{\url{https://github.com/neulab/compare-mt}}. Our model synchronizes the spans on the source and targets sides as the models capture phrasal structures without any linguistic labels. Therefore, it was hypothesized that many improvements came from accurate word reordering rather than syntactic or semantic representations.


%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\subsubsection{Unsupervised Constituency Parsing}

Table~\ref{results:parsing} shows a comparison of our models on constituency parsing tasks by differentiating the use of synchronous constraints. The results show that the synchronous constraint affects the quality of the latent phrase structures. In particular, in the MSE synchronous constraint (SynchMSE), UF is driven 15.71 points from the result of Transformer with latent phrase structure induction (Transformer + LPSI). This is because SynchMSE is a hard constraint and induces synchronous grammar that is different from the phrase structure being evaluated. In other words, the synchronous constraint hinders the derivation of the latent phrase structures. In addition, because the UF decreases even if the BLEU increases, the two metrics might have adversarial relations.

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%% table 4
\begin{table}[b]
\input{12table04.tex}
\hangcaption{Results on the constituency parsing and machine translation task in IWSLT'14 German to English (De$\rightarrow$En). Latent phrase structure quality is reported in unlabeled F-measure (UF) and its values in bold indicate the best performance.}
\label{results:parsing}
\end{table}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%% fig. 4
\begin{figure}[b]
\begin{center}
\includegraphics{29-2ia12f4.pdf}
\end{center}
\hangcaption{The top binary parse trees are obtained from the Stanford parser. The bottom binary parse trees are inducted from our Transformer+LPSI trained on IWSLT'14 German to English without BPE.}
\label{fig:parse_tree}
\end{figure}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

Figure~\ref{fig:parse_tree} shows examples of parse trees from Stanford Parser and our Transformer with LSPI. In the first example, ``a flash of the human spirit'', our model almost correctly induces phrase structure compared to Stanford Parser. The only mistake is the grouping of the two words ``the'' and ``human'' in the noun phrase ``the human spirit''. The error could be unique to the model with syntactic distance since the same phenomenon is already reported in a prior study \cite{htut_2019_inducing}. In the second example, ``have you ever seen a climate neutral tree {?}'', our model correctly induces the verb phrase ``ever seen a climate neutral tree'' but fails to induce the phrase ``have you ever'' correctly.

Table~\ref{results:parsing_tags} shows the match ratio, that is, the ratio of the number of the matched spans to the gold spans, but differentiated by the phrase labels of the gold spans. In verb phrase (VP), prepositional phrase (PP), adverb phrase (ADVP), and conjunction phrase (CONJP), we can confirm that the Transformer with LSPI and SynchRANK have some agreement with Stanford Parser. It indicates that the syntactic distance can capture functional words well.


%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\subsubsection{Unsupervised Word Alignment}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%% table 5
\begin{table}[b]
\input{12table05.tex}
\hangcaption{Results on each phrase label. NP, VP, PP, ADJP, ADVP, and CONJP represent Noun Phrase, Verb Phrase, Prepositional Phrase, Adjective Phrase, Adverb Phrase, and Conjunction Phrase, respectively.}
\label{results:parsing_tags}
\end{table}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%% table 6
\begin{table}[b]
\input{12table06.tex}
\hangcaption{Results of the word alignment and translation task in German to English (De$\rightarrow$En) and English to German (En$\rightarrow$De). `Symmetrized' indicates the alignments combined both unidirectional alignments De$\rightarrow$En and En$\rightarrow$De. Alignment quality is reported in AER, translation quality in BLEU, and its values in bold indicate the best performance.}
\label{results:alignmnet_deen} 
\end{table}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%% table 7
\begin{table}[p]
\input{12table07.tex}
\hangcaption{Results of the word alignment and translation task in French to English (Fr$\rightarrow$En) and English to French (En$\rightarrow$Fr). `Symmetrized' indicates the alignments combined both unidirectional alignments Fr$\rightarrow$En and En$\rightarrow$Fr. Alignment quality is reported in AER, translation quality in BLEU, and its values in bold indicate the best performance.}
\label{results:alignmnet_fren} 
\end{table}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%% table 8
\begin{table}[p]
\input{12table08.tex}
\hangcaption{Results of the word alignment and translation task in Russian to English (Ru$\rightarrow$En) and English to Russian (En$\rightarrow$Ru).  `Symmetrized' indicates the alignments combined both unidirectional alignments Ru$\rightarrow$En and En$\rightarrow$Ru. Alignment quality is reported in AER, translation quality in BLEU, and its values in bold indicate the best performance.}
\label{results:alignmnet_ruen} 
\end{table}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%% table 9
\begin{table}[p]
\input{12table09.tex}
\hangcaption{Results of the word alignment and translation task in Japanese to English (Ja$\rightarrow$En) and English to Japanese (En$\rightarrow$Ja). `Symmetrized' indicates the alignments combined both unidirectional alignments Ja$\rightarrow$En and En$\rightarrow$Ja. Alignment quality is reported in AER, translation quality in BLEU, and its values in bold indicate the best performance.}
\label{results:alignmnet_jaen} 
\end{table}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

Table~\ref{results:alignmnet_deen}, \ref{results:alignmnet_fren}, \ref{results:alignmnet_ruen}, and \ref{results:alignmnet_jaen} compare the word alignment performance of our methods against statistical and neural baseline approaches for the four datasets. Compared with statistical models as the baseline, our models showed a worse alignment quality for all datasets. However, compared with the Transformer as the baseline, SynchMSE showed a better alignment quality for German-English and Russian-English. In addition, we did not find any clear trends between AER and BLEU because an increase in BLEU did not impact AER.

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%% table 10
\begin{table}[b]
\input{12table10.tex}
\hangcaption{Results of the translation task in IWSLT'14 English to German
(En$\rightarrow$De) and ASPEC Japanese to English (Ja$\rightarrow$En) for the effectiveness of learning the word order. Translation quality has been reported in BLEU \protect\cite{papineni_2002_bleu}. `w/o. Positional Embedding' indicates the removal of positional embedding from the models. Following a previous study \protect\cite{cui_2019_mixed}, the local attention mask is applied only to the encoder.}
\label{analysis:attention_gate}
\end{table}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%


%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\section{Analysis}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\subsection{Effectiveness of Attention Gate}

We realized that our multi-head attention without synchronous constraint could be regarded as gated multi-head attention, similar to local attention within mixed multi-head attention (MMHA) \cite{cui_2019_mixed}. MMHA encourages each head to acquire different features by masking them differently and allows the model to be aware of the word order. Table~\ref{analysis:attention_gate} shows that the Transformer without position embedding decreased by 17.41 BLEU points in the IWSLT'14 German-English and 13.37 BLEU points in the ASPEC Japanese-English. In a transformer with an LPSI, the performance is only reduced by 0.89 BLEU points in the IWSLT'14 German-English and 0.45 BLEU points in the ASPEC Japanese-English without position embedding. For a fair comparison, we employed the local attention with two windows in the two bottom layers of the encoder. Similarly, in Transformer with local attention (LocalAttn), the performance was reduced by 0.93 BLEU points in the IWSLT'14 German-English and 0.71 BLEU points in the ASPEC Japanese-English without position embedding. This indicates that local constraints on attention mechanisms help in learning the order of the words rather than latent phrase structure induction.


%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\subsection{Effectiveness of Synchronous Latent Phase Structure}

Table~\ref{analysis:synchronous_latent_phase_structure} shows the AER of word alignment obtained by differentiating the German-English alignment dataset layers. In the second top layer, i.e., the fifth layer, while the synchronous constraint by MSE (SynchMSE) contributed to the improvement of AER, the synchronous constraint by RANK loss conversely worsened AER. However, RANK loss (SynchRANK) significantly improved the AER in the third and fourth layers. In the final layer, i.e., the sixth layer, both synchronous constraints by MSE and RANK loss resulted in a worse AER. This suggests that SynchRANK has high precision and SynchMSE has a high recall in the second top layer.

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%% table 11
\begin{table}[b]
\input{12table11.tex}
\hangcaption{Results of AER on each layer. AER is reported from symmetrized 
alignments combined both unidirectional alignments. The value in bold 
indicates the best performance.}
\label{analysis:synchronous_latent_phase_structure}
\end{table}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

Figure~\ref{fig:view_alignmnet} shows examples from the German-English alignment test set. In the first example, we find that there are no false alignments in our models with synchronous constraints. However, in SynchRANK, the alignment between ``Therefore'' and ``Daher'' was lost, although SynchMSE captured it. Our model correctly aligned them with ``um'' in the second example compared with FAST-ALIGN. Our synchronous constraints, either by MSE or RANK loss, would induce highly confident alignments by synchronizing the source and target language structures. Furthermore, as seen in Tables \ref{results:alignmnet_deen} and \ref{results:alignmnet_ruen}, SynchRANK has high precision values in symmetrized alignments. 
Table~\ref{fig:view_alignmnet} shows no false alignments in SynchRANK and we believe that the alignment with higher precision would contribute to the justification of the translation results. In other words, the synchronization constraint favors precision over recall, causing a worse AER; however, it can provide a more reliable and interpretable alignment for humans. We hypothesize that the synchronizing phrasal structure favors higher precision by considering the hierarchical structure and we will leave this as our future work.

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%% fig. 5
\begin{figure}[t]
\begin{center}
\includegraphics{29-2ia12f5.pdf}
\end{center}
\hangcaption{Symmetrized examples from the German-English alignment test set. Gold Alignment is shown in (a). Alignment in (b) shows the output from FastAlign (BPE-wise trained), (c) from the synchronized MSE model, and (d) from the synchronized Rank model. In the reference, the black and gray squares represent sure and possible alignments, respectively.}
\label{fig:view_alignmnet}
\end{figure}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%% table 12
\begin{table}[t]
\input{12table12.tex}
\hangcaption{Results on the German-English alignment task by differentiating POS of each word. Alignment quality of `Symmetrized' is reported in AER. NN, VB, IN, JJ, RB, and CC represent Noun, Verb, Preposition, Adjective, Adverb, and Coordinating Conjunction respectively. The values in bold indicate the best performance.}
\label{results:labeled_alignmnet}
\vspace{-1\Cvs}
\end{table}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

Table~\ref{results:labeled_alignmnet} shows the word alignment performance on each word label in the German-English dataset. AER is computed for the matched alignment against the gold alignment by differentiating the part-of-speech (POS) of each word. The POS is predicted by Stanford Parser on the English side. In the same manner, as was done in the parsing task, we excluded data containing multiple sentences and the test data contained 500 examples. As a result, the Transformer with the LPSI did not show improvements compared with the Transformer baseline. 
\pagebreak
This is natural because the induced phrase structure is not reflected in the alignment. However, SynchMSE has better alignments than the Transformer baseline in VB, JJ, and CC. SynchRANK has better alignment than the Transformer baseline in IN. This indicates that our models improved the alignments of some functional words and could reflect the induced phrase structure in the alignments.


%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\section{Conclusion and Future Work}

This paper introduced an approach to improve the MT performance and precision of alignments. Our approach followed two steps: induction of the phrase structure without extra syntactic resources and synchronization of the inducted phrase structure through cross-attention. In the MT task, our models captured the relation of word order and improved the quality of MT for syntactically similar and dissimilar language pairs. In the alignment task, we demonstrated that the synchronous constraint for syntactic distance could produce alignment with high precision to help interpret the correspondence of bilingual sentences. Our approach induced a poor latent phrase structure in the parsing task and was more compromised by SynchMSE, which is a hard synchronous constraint.

In future work, to achieve higher performance and interpretability of the MT results, we would like to investigate other syntactic structures and translation models that can induce a better latent phrase structure. In this study, we performed a detailed analysis of the English-German dataset. However, we plan to investigate a multilingual parser for a more detailed analysis of various multilingual datasets in the future. We also plan to analyze the hierarchical structure of the alignment when the induced phrase structure is reflected.


%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\acknowledgment

This paper is based on a paper accepted at the Joint Conference of the 59th Annual Meeting of the Association for Computational Linguistics and the 11th International Joint Conference on Natural Language Processing Student Research Workshop (ACL-IJCNLP 2021 SRW). It has been expanded with additional results and detailed descriptions. In particular, the implementation was revised so that the grammar induction head could be easily plugged into existing Transformer-based MT models for ease of experimentation. Additional experiments were conducted on a larger dataset, WMT and ASPEC, for the MT task and the English-French, Russian-English, and Japanese-English dataset for the alignment task. This work was in part supported by JSPS KAKENHI Grant Numbers 21H05054 and 20K23325.


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


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

\bioauthor[:]{Shintaro Harada}{%
is currently a Master's student at Nara Institute of Science and Technology (NAIST). He received his B.E. from the National Institute of Technology, Tokuyama College in 2020.  His research interests include machine translation, syntax analysis, and machine learning, under instruction of Prof. Taro Watanabe.
}

\bioauthor[:]{Taro Watanabe}{
received his B.E. and M.E. degrees in information science from Kyoto University in 1994 and 1997, respectively, and obtained an M.S. degree in Language and Information Technologies from the School of Computer Science, Carnegie Mellon University in 2000. In 2004, he received his Ph.D. in informatics from Kyoto University, Kyoto, Japan. After working as a researcher at ATR, NTT, and NICT, and as a software engineer at Google, he is a professor at the Nara Institute of Science and Technology starting in 2020. His research interests include natural language processing, machine learning, and machine translation.
}
\end{biography}


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



\end{document}

