\documentclass[english]{jnlp_3.3}
\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{times}
%%%%\usepackage{latexsym}
\usepackage{array,booktabs,makecell}
\usepackage{tabu}
\usepackage{multirow}
\usepackage{xcolor}
%%%%\usepackage{subfigure}
%%%%\allowdisplaybreaks[1]
%%%%\DeclareMathOperator*{\argmin}{arg\,min}
%%%%\DeclareMathOperator*{\argmax}{arg\,max}
\newcommand{\dashrule}[1][black]{%
  \color{#1}\rule[\dimexpr.5ex-.2pt]{4pt}{.4pt}\xleaders\hbox{\rule{4pt}{0pt}\rule[\dimexpr.5ex-.2pt]{4pt}{.4pt}}\hfill\kern0pt%
}
\renewcommand\theadfont{\bfseries}% bold tabular parenters
\renewcommand\theadalign{cc}% centred tabular parenters
\renewcommand\theadgape{}% booktabs rules already add vertical spacing
%%%%% 和文フォント埋め込み
%%%%\usepackage[ipaex]{pxchfon}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

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

\received{2020}{8}{16}
\revised{2020}{12}{1}
%%%%\rerevised{2006}{5}{6}
\accepted{2021}{1}{14}

\setcounter{page}{321}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\esubject{General Paper}
\etitle{Effectiveness of Syntactic Dependency Information for Higher-Order Syntactic Attention Network}
\eauthor{Hidetaka Kamigaito\affiref{Author_1} \and Katsuhiko Hayashi\affiref{Author_2} \and Tsutomu Hirao\affiref{Author_3} \and \\Masaaki Nagata\affiref{Author_3} \and Manabu Okumura\affiref{Author_4}}
\eabstract{%
Recently, as a replacement of syntactic tree-based approaches, such as tree-trimming, Long Short-Term Memory (LSTM)-based methods have been commonly used to compress sentences because LSTM can generate fluent compressed sentences. However, the performance of these methods degrades significantly while compressing long sentences because they do not explicitly handle long-distance dependencies between the words. To solve this problem, we proposed a higher-order syntactic attention network (HiSAN) that can handle higher-order dependency features as an attention distribution on LSTM hidden states. Furthermore, to avoid the influence of incorrect parse results, we trained HiSAN by maximizing the probability of a correct output together with the attention distribution. Experiments on the Google sentence compression dataset show that our method improved the performance from baselines in terms of F$_1$ as well as ROUGE-1, -2, and -L scores. In subjective evaluations, HiSAN outperformed baseline methods in both readability and informativeness. Besides, in this study, we additionally investigated the performance of HiSAN after training it without any syntactic dependency tree information. The results of our investigation show that HiSAN can compress sentences without relying on any syntactic dependency information while maintaining accurate compression rates, and also shows the effectiveness of syntactic dependency information in compressing long sentences with higher F$_1$ scores.
}
\ekeywords{Sentence Compression, Sequence-to-Sequence, Syntactic Dependency}

\headauthor{Kamigaito et al.}
\headtitle{Effectiveness of Syntactic Dependency Information for HiSAN}

\affilabel{Author_1}{}{NTT Communication Science Laboratories, NTT Corporation. Currently, he is working in Institute of Innovative Research, Tokyo Institute of Technology.}
\affilabel{Author_2}{}{NTT Communication Science Laboratories, NTT Corporation. Currently, he is working at Gunma University.}
\affilabel{Author_3}{}{NTT Communication Science Laboratories, NTT Corporation}
\affilabel{Author_4}{}{Institute of Innovative Research, Tokyo Institute of Technology}


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

\maketitle

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

Syntax information plays an important role in sentence compression, a task that involves compressing long sentences into short and concise ones by deleting words.
To generate grammatically correct compressed sentences in this task, several researchers \cite{jing:2000:ANLP,knight2000statistics,bergkirkpatrick-gillick-klein:2011:ACL-HLT2011,filippova-altun:2013:EMNLP} have adopted tree trimming methods.
Although Fillipova and Altun (2013)\nocite{filippova-altun:2013:EMNLP} reported the best results in this task, parsing errors greatly degrade the performance of the tree trimming methods.
Recently, Filippova et al. (2015) \nocite{filippova-EtAl:2015:EMNLP} proposed an LSTM sequence-to-sequence (Seq2Seq)-based sentence compression method that can generate fluent sentences without utilizing any syntactic features.
Therefore, Seq2Seq-based sentence compression is a promising alternative to tree trimming.

However, as reported in a machine translation task \cite{cho-EtAl:2014:SSST-8,2014arXiv1409.1257P,koehn-knowles:2017:NMT}, the longer the input sentences, the worse the Seq2Seq performance.
We also observed this problem in sentence compression tasks.
As shown in Fig.~\ref{fig:length},\footnote{We used an LSTM-based sentence compression method \cite{filippova-EtAl:2015:EMNLP} during evaluation, as described in Section \ref{sec:eval}.} the performance of Seq2Seq degrades while compressing long sentences.
In particular, the performance significantly drops if the sentence length exceeds 26 words.
This is an important problem, because sentences longer than the average sentence length (27.04 words) account for 42\% of the Google sentence compression dataset.

As shown in Fig.~\ref{fig:depth},\footnote{We treated the maximum distance from a root node to the leaf node as the dependency tree depth.} long sentences have deep dependency trees, with a large distance between the root node and the words at the leaf nodes.
Therefore, focusing on improving the compression performance for sentences with such deep dependency trees can help in compressing long sentences.

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%% fig. 1 and 2
\begin{figure}[b]
\setlength{\captionwidth}{200pt}
\begin{minipage}[t]{200pt}
\begin{center}
\includegraphics{28-2ia1f1.pdf}
\end{center}
\hangcaption{F$_{1}$ scores of LSTM-based sentence compression method for each sentence length.}
\label{fig:length}
\end{minipage}
\hfill
\begin{minipage}[t]{200pt}
\begin{center}
\includegraphics{28-2ia1f2.pdf}
\end{center}
\caption{Average tree depths for each sentence length.}
\label{fig:depth}
\end{minipage}
\end{figure}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

Besides, as shown in Fig.~\ref{fig:correlation}, there is a tendency of longer compressed sentences for longer inputs in the gold compressed sentences.
Furthermore, as shown in Fig.~\ref{fig:comp_dep}, similar to the relationship between input sentences and their dependency trees, the average depth of the gold compressed sentences increases for long compressed sentences. These observations suggest that to improve the compression performance, we need to be careful about deep dependency trees on both the input and output sides.

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%% fig. 3 and 4
\begin{figure}[b]
\setlength{\captionwidth}{200pt}
\begin{minipage}[t]{200pt}
\begin{center}
\includegraphics{28-2ia1f3.pdf}
\end{center}
\hangcaption{Compressed length for each input sentence length in the gold compression. The dot size represents the number of each length.}
\label{fig:correlation}
\end{minipage}
\hfill
\begin{minipage}[t]{200pt}
\begin{center}
\includegraphics{28-2ia1f4.pdf}
\end{center}
\hangcaption{Average tree depths for each compression length in the gold compression.}
\label{fig:comp_dep}
\end{minipage}
\end{figure}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

To deal with sentences that have deep dependency trees, we focused on the chains of dependency relationships.
Fig.~\ref{fig:exp} shows an example of a compressed sentence with its dependency tree.
The topic of this sentence is {\it import agreement related to electricity}.
Thus, to generate an informative compression, the compressed sentence must retain the {\it country name}.
In this example, the compressed sentence should retain the phrase ``from Kyrgyz Republic and Tajikistan''.
Thus, the compressed sentence must also retain the dependency chain comprising the words ``import'', ``resolution'', and ``signed'' because the phrase is a child of this chain.
By considering such higher-order dependency chains, the system can implement informative compression.
The example in Fig.~\ref{fig:exp} demonstrates that tracking a higher-order dependency chain for each word helps in compressing long sentences.
This paper refers to such dependency relationships by the expression ``$d$-length dependency chains''.

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%% fig. 5
\begin{figure}[b]
\begin{center}
\includegraphics{28-2ia1f5.pdf}
\end{center}
\hangcaption{An example compressed sentence and its dependency tree. The words colored with gray represent deleted words.}
\label{fig:exp}
\end{figure}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

To handle a $d$-length dependency chain for sentence compression with LSTM, we had earlier proposed a technique called the higher-order syntactic attention network (HiSAN) \cite{kamigaito-etal-2018-higher}.
HiSAN computes the deletion probability for a given word based on the $d$-length dependency chain starting from that word.
The $d$-length dependency chain is represented as an attention distribution, learned from automatic parse trees.
The attention distribution of HiSAN is calculated from both the input and the compressed sentences.
To alleviate the influence of parse errors in automatic parse trees, we learned the attention distribution together with the deletion probability. 

Evaluation results on the Google sentence compression dataset \cite{filippova-altun:2013:EMNLP} demonstrated that HiSAN improved the sentence compression performance from the baseline in terms of F$_{1}$, ROUGE-1, -2, and -L scores.
In particular, HiSAN attained remarkable compression performance with long sentences.
HiSAN outperformed the baseline methods even in human evaluations.

Although the attention module of HiSAN can learn context information without relying on external syntactic dependency information, in our preliminary study \cite{kamigaito-etal-2018-higher}, we had evaluated HiSAN in a setting where the syntactic dependency information was utilized in a supervised manner only. Thus, it is still uncertain which network structure or syntactic dependency information contributed to the improvement in the performance. Identifying this point will help to construct a model for more accurate sentence compression. In this study, we additionally investigated the performance of HiSAN, which was trained without any syntactic dependency tree information. Our investigation indicates that HiSAN can compress sentences with high accuracy rates without relying on any syntactic dependency information. It also shows the effectiveness of syntactic dependency information in compressing long sentences with higher F$_1$ scores while maintaining accurate compression rates.

The remainder of this paper is structured as follows: 
Section 2 introduces the baseline Seq2Seq method which is used for constructing HiSAN;
Section 3 describes the concept of $d$-length dependency chain and HiSAN network structures;
Section 4 describes the comparison between baselines and the variants of HiSAN using automatic and human evaluations;
Section 5 analyzes the evaluation results with real generated sentences and attention distributions;
Section 6 describes the related work used for this paper;
Section 7 concludes the paper.


%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\section{Baseline Seq2Seq Method}
\label{sec:base}

Sentence compression can be regarded as a tagging task
on a given sequence of input tokens $\mathbf{x} = (x_{0}, ..., x_{n})$, where $x_{0}$ represents the root node,\footnote{In this paper, we treat $x_{0}$ as the root node of a dependency tree.} and the system assigns one out of three specific label types (``keep'', ``delete'', or ``end of sentence'') as an output label $y_t$ to each input token $x_t$~($1\leq t\leq n$).

LSTM-based approaches for sentence compression are mostly based on either a bidirectional-LSTM (bi-LSTM)-based tagging method (Tagger) \cite{klerke-goldberg-sogaard:2016:N16-1,wang-EtAl:2017:Long4,DBLP:conf/aaai/ChenP17} or Seq2Seq \cite{filippova-EtAl:2015:EMNLP,Tran:2016:EAN:3011077.3011111}.
Tagger independently predicts the labels in a point estimation manner, whereas Seq2Seq predicts them by considering previously predicted labels.
Because Seq2Seq is more expressive than Tagger, we developed HiSAN on the baseline Seq2Seq model.

Our baseline Seq2Seq is a variant of the model proposed by Filippova et al. (2015) \nocite{filippova-EtAl:2015:EMNLP}, wherein we added the bi-LSTM, an input feeding approach \cite{NIPS2015_5635,luong-pham-manning:2015:EMNLP}, and a monotonic hard attention method \cite{DBLP:conf/interspeech/YaoZ15,Tran:2016:EAN:3011077.3011111}.
As described in the evaluations section, this baseline achieved comparable or even better scores than those reported for the state-of-the-art method in Filippova et al. (2015)\nocite{filippova-EtAl:2015:EMNLP}.
Our baseline Seq2Seq model comprised the embedding, encoder, decoder, and output layers.

The embedding layer converts the input tokens $\mathbf{x}$ into embeddings $\mathbf{e}$.
As reported in Wang et al. (2017)\nocite{wang-EtAl:2017:Long4}, syntactic features are important to learn a generalizable embedding for sentence compression.
Following their results, we also introduced syntactic features into the embedding layer.
Specifically, we combined surface token embedding $w_{i}$, Part-Of-Speech (POS) tag embedding $p_{i}$, and dependency relation label embedding $r_{i}$ into a single vector as follows:
\begin{equation}
e_{i} = \left[ w_{i}, p_{i}, r_{i} \right],
\label{eq:embed}
\end{equation}
where $\left[ \right]$ represents the vector concatenation, and $e_{i}$ is an embedding of token $x_{i}$.

The encoder layer converts the embedding $\mathbf{e}$ into a sequence of hidden states $\mathbf{h} = (h_{0}, ..., h_{n})$ using a stacked bi-LSTM as follows:
\begin{align}
    h_{i} &= \left[\overrightarrow{h_{i}}, \overleftarrow{h_{i}}\right] \\
    \overrightarrow{h}_{i} &= LSTM_{\overrightarrow{\theta}}(\overrightarrow{h}_{i-1}, e_{i}) \\
    \overleftarrow{h}_{i} &= LSTM_{\overleftarrow{\theta}}(\overleftarrow{h}_{i+1}, e_{i}),
\end{align}
where $LSTM_{\overrightarrow{\theta}}$ and $LSTM_{\overleftarrow{\theta}}$ represent the forward and backward LSTM functions, respectively.
The final state of the backward LSTM $\overleftarrow{h}_{0}$ is inherited by the decoder as its initial state.

In the decoder layer, the concatenation of a three-bit one-hot vector, determined by a previously predicted label $y_{t-1}$, the previous final hidden state $d_{t-1}$ (explained later), and the input embedding of $x_{t}$, is encoded into the decoder hidden state $\overrightarrow{s}_{t}$ using stacked forward LSTMs.

Contrary to the original softmax attention method, we can deterministically focus on one encoder hidden state $h_{t}$ \cite{DBLP:conf/interspeech/YaoZ15} to predict $y_{t}$ in the sentence compression task \cite{Tran:2016:EAN:3011077.3011111}.\footnote{This is because the output and input lengths are the same, and each $x_{t}$ can be assigned to a $y_{t}$ in a one-to-one correspondence.}

In the output layer, label probability is calculated as follows:
\begin{align}
    P(y_{t} \mid y_{<t}, \mathbf{x}) & = softmax(W_{o} \cdot d_{t}) \cdot \delta_{y_{t}},\label{eqn:Seq2Seq:softmax}\\
d_{t} & =  [ h_{t}, \overrightarrow{s}_{t} ], \label{eqn:lasth}
\end{align}
where $W_{o}$ is the weight matrix of the softmax layer and $\delta_{y_{t}}$ is a binary vector where the $y_{t}$-th element is set to $1$ and the other elements to $0$.


%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\section{Higher-order Syntactic Attention Network}

The key component of HiSAN is its attention module.
Unlike the baseline Seq2Seq, HiSAN employs a packed $d$-length dependency chain as distributions in the attention module.
Section \ref{sec:pack} explains the packed $d$-length dependency chain,
Section \ref{sec:net} describes the network structure of our attention module, and Section \ref{sec:objfunc} explains the learning method of HiSAN.


%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\subsection{Packed $d$-length Dependency Chain}
\label{sec:pack}

The probability of a packed $d$-length dependency chain is obtained from a dependency graph, which is an edge-factored dependency score matrix \cite{hashimoto-tsuruoka:2017:EMNLP2017,zhang-cheng-lapata:2017:EACLlong}.
First, we explain the dependency graph.
Fig.~\ref{fig:dep} (a) shows an example of the dependency graph to explain a parent attention module.
HiSAN represents the dependency graph as an attention distribution generated by the attention module.
A probability for each dependency edge is obtained from the attention distribution.

Fig.~\ref{fig:dep} (b) explains a recursive attention module by showing an example of the packed $d$-length dependency chain.
With our recursive attention module, the probability of a packed $d$-length dependency chain is computed as the sum of probabilities of each path yielded by recursively tracking from a word to its $d$-th ancestor.
The probability of each path is calculated as the product of the probabilities of the tracked edges.
The packed $d$-length dependency chains can compactly represent the probability of the chain.
A similar effect can be observed while considering multiple dependency trees and their $d$-th dependency parents.
Thus, this representation can alleviate the incorrect parse results, because of the nondependence on a single dependency tree.
This is the advantage of using dependency graphs.

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%% fig. 6
\begin{figure}[t]
\begin{center}
\includegraphics{28-2ia1f6.pdf}
\end{center}
\caption{Dependency structures used in our higher-order syntactic attention network.}
\label{fig:dep}
\end{figure}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%% fig. 7
\begin{figure}[t]
\begin{center}
\includegraphics{28-2ia1f7.pdf}
\end{center}
\caption{Prediction process of our higher-order syntactic attention network.}
\label{fig:net:recatt}
\end{figure}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\subsection{Network Architecture}
\label{sec:net}

Fig.~\ref{fig:net:recatt} shows the HiSAN prediction process.
The figure depicts the prediction of output label $y_{7}$ from the input sentence using HiSAN.
The prediction process is as follows.
\begin{enumerate}
\item {\bf Parent Attention} module calculates $P_{parent}(x_{j}|x_{t},\mathbf{x})$, the probability of $x_{j}$ being the parent of $x_{t}$, using $h_{j}$ and $h_{t}$.
This probability is calculated for all pairs of $x_{j},x_{t}$.
The arc in Fig.~\ref{fig:net:recatt} shows the most probable dependency parent for each child token.
\item {\bf Recursive Attention} module calculates $\alpha_{d,t,j}$, the probability of $x_{j}$ being the $d$-th order parent ($d$ denotes the chain length) of $x_{t}$, by recursively using $P_{parent}(x_{j}|x_{t},\mathbf{x})$.
$\alpha_{d,t,j}$ is also treated as an attention distribution, and used to calculate $\gamma_{d,t}$, the weighted sum of $\mathbf{h}$ for each length $d$.
For example, a three-length dependency chain of word $x_{7}$ with the highest probability is $x_{6}$-$x_{5}$-$x_{2}$.
The encoder hidden states $h_6$, $h_5$, and $h_2$, which correspond to the dependency chain, are weighted by calculated parent probabilities $\alpha_{1,7,6}$, $\alpha_{2,7,5}$, and $\alpha_{3,7,2}$, respectively, and then fed to the selective attention module.
\item {\bf Selective Attention} module calculates weight $\beta_{d,t}$ from its length, $d \in \mathbf{d}$, for each $\gamma_{d,t}$.
$\mathbf{d}$ represents a group of chain lengths.
$\beta_{d,t}$ is calculated from the encoder and decoder hidden states.
Each $\beta_{d,t} \cdot \gamma_{d,t}$ is then summed to $\Omega_{t}$, the output of the selective attention module.
\item Finally, the calculated $\Omega_{t}$ is concatenated and input into the output layer.
\end{enumerate}
Each module is explained in detail in the following subsections.


%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\subsubsection{Parent Attention Module}

Zhang et al. (2017)\nocite{zhang-cheng-lapata:2017:EACLlong} formalized dependency parsing as the problem of independently selecting the parent of each word in a sentence.
They produced a distribution over the possible parents of each child word by using the attention layer on bi-LSTM hidden layers.

In a dependency tree, a parent has more than one child.
Under this constraint, dependency parsing is represented as follows.
Given a sentence $S = (x_{0}, x_{1}, ..., x_{n})$, the parent of $x_{j}$ is selected from $S \setminus x_{i}$ for each token $S \setminus x_{0}$.
Notably, $x_{0}$ denotes the root node.
The probability of token $x_{j}$ being the parent of token $x_{t}$ in sentence $\mathbf{x}$ is calculated as follows:
\begin{align}
P_{parent}(x_{j}|x_{t},\mathbf{x}) & = softmax(g(h_{j'}, h_{t})) \cdot \delta_{x_{j}},\\
g(h_{j'}, h_{t}) & =  v_{a}^{T} \cdot tanh(U_{a}h_{j'} + W_{a}h_{t}),
\end{align}
where $j'$ indicates all the possible indices of a word in $S$, $v_{a}$ is a weight vector, and $U_{a}$ and $W_{a}$ are the weight matrices of $g$.

Different from the attention-based dependency parser, $P_{parent}(x_{j}|x_{t},\mathbf{x})$ is jointly learned with output label probability $P(\mathbf{y} \mid \mathbf{x})$ in the training phase.
The training details are explained in Section \ref{sec:objfunc}.


%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\subsubsection{Recursive Attention Module}

The recursive attention module recursively calculates $\alpha_{d,t,j}$, the probability of $x_{j}$ being the $d$-th order parent of $x_{t}$, as follows:
\begin{equation}
\alpha_{d,t,j} = \left\{\begin{array}{ll}
\mathop{\sum}\limits_{k=1}^{n}\alpha_{d-1,t,k} \cdot \alpha_{1,k,j} & (d  >  1) \\
P_{parent}(x_{j}|x_{t},\mathbf{x}) & (d  =  1)
\end{array} \right.
\label{eqn:recatt}
\end{equation}
Furthermore, in a dependency parse tree, {\it the root} should not have any parent, and a token should not depend on itself.
To satisfy these rules, we impose the following constraints on $\alpha_{1,t,j}$:
\begin{equation}
\alpha_{1,t,j} = \left\{\begin{array}{ll}
1 & (t = 0 \land j = 0) \\
0 & (t = 0 \land j > 0) \\
0 & (t \not= 0 \land t = j)
\end{array} \right.
\label{eqn:recatt:const}
\end{equation}
The first and second lines of Eq. (\ref{eqn:recatt:const}) represent the case where the parent of {\it root} is also {\it root}.
These constraints imply that {\it root} does not have any parent.
The third line of Eq. (\ref{eqn:recatt:const}) prevents a token from depending on itself.
Because the first line of Eq. (\ref{eqn:recatt}) is a matrix multiplication, Eq. (\ref{eqn:recatt}) can be efficiently computed on a CPU and GPU.\footnote{During training, HiSAN with 1- and 3-length dependency chains consumed 25 and 26 min, respectively, per epoch on an Intel Xeon E5-2697 v3 2.60~GHz.}

By recursively using the single attention distribution, it is no longer necessary to prepare additional attention distributions for each order when computing the probability of higher order parents.
Furthermore, owing to the nonnecessity of learning multiple attention distributions, using hyper-parameters for adjusting the weight of each distribution in training is not required.
Finally, this method can prevent the problem of sparse higher-order dependency relations in the training dataset. 

The $\alpha_{d,t,j}$ calculated above is used to weight the bi-LSTM hidden layer $\mathbf{h}$ as follows:
\begin{equation}
\gamma_{d,t} = \mathop{\sum}\limits_{k=j}^{n} \alpha_{d,t,j} \cdot h_{j}. \\
\end{equation}
Notably, $\gamma_{d,t}$ is inherited by the selective attention module, as explained in the next section.


%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\subsubsection{Selective Attention Module}

To select suitable dependency orders of the input sentence, the selective attention module weights and sums the hidden states $\gamma_{d,t}$ to $\Omega_{t}$ by using weighting parameter $\beta_{d,t}$, according to the current context as follows:
\begin{align}
    \beta_{d,t} &= softmax(W_{c} c_{t}) \cdot \delta_{d}, \\
    \Omega_{t} &= \mathop{\sum}\limits_{d \in \{0, \mathbf{d}\}}\beta_{d,t} \cdot \gamma_{d,t},
\label{eqn:rec:order:softmax}
\end{align}
where $W_{c}$ is the weight matrix of the softmax layer, $\mathbf{d}$ is a group of chain lengths, $c_{t}$ is a vector representing the current context, $\gamma_{0,t}$ is a zero-vector, and $\beta_{0,t}$ indicates the weight when the method does not use the dependency features.
Context vector $c_{t}$ is calculated as $c_{t} = [ \overleftarrow{h}_{0}, \overrightarrow{h}_{n}, \overrightarrow{s}_{t} ]$ using the current decoder hidden state $\overrightarrow{s}_{t}$.

The calculated $\Omega_{t}$ is concatenated and input into the output layer.
In detail, $d_{t}$ in Eq. (\ref{eqn:Seq2Seq:softmax}) is replaced by concatenated vector $d'_{t} = [ h_{t}, \Omega_{t}, \overrightarrow{s}_{t} ]$; furthermore, instead of $d_{t}$, $d'_{t}$ is also fed to the input of the decoder LSTM at $t+1$. It should be noted that considering a high order dependency structure helps to deal with long input sentences. However, when the number of order types increases, estimating their importance is difficult using selective attention. Thus, an appropriate order combination is required.


%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\subsection{Objective Function}
\label{sec:objfunc}

To alleviate the influence of parse errors, we jointly update the first-order attention distribution $\alpha_{1,t,k}$ and label probability $P(\mathbf{y}|\mathbf{x})$ \cite{kamigaito-EtAl:2017:I17-2}.
The first-order attention distribution is learned by dependency parse trees.
If $a_{t,j}=1$ is an edge between parent and child words $w_{j}$ and $w_{t}$, respectively, on a dependency tree ($a_{t,j}=0$ denotes that $w_{j}$ is not a parent of $w_{t}$.), the objective function of our method can be defined as:
\begin{equation}
-log P(\mathbf{y}|\mathbf{x}) -\lambda \cdot \sum_{j=1}^{n} \sum_{t=1}^{n} a_{t,j} \cdot log \alpha_{1,t,j},
\label{eqn:sup}
\end{equation}
where $\lambda$ is a hyper-parameter that controls the importance of the output labels and parse trees in the training dataset.
To investigate the effectiveness of the information from syntactic dependency trees, we set $\lambda=1.0$ for \textit{with syntax (w/ syn)} setting and $\lambda=0.0$ for \textit{without syntax (w/o syn)} setting.


%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\section{Evaluation}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\subsection{Evaluation Settings}
\label{sec:eval}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\subsubsection{Dataset}

For evaluation we used the Google sentence compression dataset
\cite{filippova-altun:2013:EMNLP}.\footnote{\url{https://github.com/google-research-datasets/sentence-compression}}
This dataset contains information regarding the 
compression labels, part-of-speech~(POS) tags, dependency parents,
and dependency relation labels of each sentence.
We used the first and last 1,000 sentences
of {\tt comp-data.eval.json} as our test and development datasets, respectively.
Notably, our test dataset is compatible with that used in previous studies \cite{filippova-EtAl:2015:EMNLP,Tran:2016:EAN:3011077.3011111,klerke-goldberg-sogaard:2016:N16-1,wang-EtAl:2017:Long4}.
In this study, we trained the baselines and HiSAN on all the sentences present in the file {\tt sent-comp.train*.json} (200,000 sentences in total).\footnote{Notably, Filippova et al. (2015)\nocite{filippova-EtAl:2015:EMNLP} used 2,000,000 sentences for training their method, but the datasets are not publicly available.}$^,$\footnote{Please note that the large training dataset lacks periods at the end of compressed sentences. To unify the form of compressed sentences in small and large settings, we added periods to the end of compressed sentences in the large training dataset.}
In our experiments, we replaced rare words that appear fewer than 10 times in our training dataset with a special token $\langle$UNK$\rangle$.
The resultant filtered input vocabulary size was $23,168$. 


%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\subsubsection{Comparison Methods}

For a fair comparison with HiSAN, we used the input features described in Eq. (\ref{eq:embed}) in the following baseline methods:
\begin{itemize}
\item {\bf Tagger:} This method regards sentence compression as a tagging task based on bi-LSTM \cite{klerke-goldberg-sogaard:2016:N16-1,wang-EtAl:2017:Long4}.
\item {\bf Tagger+ILP:} This is an extension of {\bf Tagger} that integrates integer linear programming (ILP)-based dependency tree trimming \cite{wang-EtAl:2017:Long4}. Here, we set the positive parameter $\lambda$ to $0.2$.
\item {\bf Bi-LSTM:} This method, proposed by Filippova et al. (2015)\nocite{filippova-EtAl:2015:EMNLP}, regards sentence compression as a Seq2Seq translation task. For a fair comparison, we replaced their one-directional LSTM with the more expressive bi-LSTM in the encoder part. The initial state of the decoder was set to the sum of the final states of the forward and backward LSTMs.
\item {\bf Bi-LSTM-Dep:} This is an extension of Bi-LSTM that exploits the features obtained from a dependency tree (named LSTM-PAR-PRES in Filippova et al. (2015)\nocite{filippova-EtAl:2015:EMNLP}). Following their work, we fed the word embedding and predicted label of a dependency parent word to the current decoder input of {\bf Bi-LSTM}.
\item {\bf Base:} This is our baseline Seq2Seq method described in Section \ref{sec:base}.
\item {\bf Attn:} This method extends the softmax-based attention method \cite{luong-pham-manning:2015:EMNLP}. We replaced $h_{t}$ in Eq. (\ref{eqn:lasth}) with the weighted sum calculated with the commonly used concat attention \cite{luong-pham-manning:2015:EMNLP}.
\item {\bf HiSAN-Dep:} This variant of HiSAN utilizes the pipeline approach. We fixed $\alpha^{1,j,t}$ to $1.0$ if $x_{j}$ was a parent of $x_{t}$ in the input dependency parse tree, otherwise $0.0$. In this baseline, $\mathbf{d}=\{1\}$ was used. \vspace{1.5mm}
\end{itemize}
Our proposed methods are as follows:
\begin{itemize}
\item {\bf HiSAN-Dep:} Different from HiSAN-Dep in the baseline setting, we used higher-order dependencies $\mathbf{d}=\{1,2\}$, $\mathbf{d}=\{1,2,3\}$, $\mathbf{d}=\{1,2,4\}$, and $\mathbf{d}=\{1,2,3,4\}$ in this setting.
\item {\bf HiSAN w/ syn:} As explained in Section \ref{sec:objfunc}, this setting considers syntactic dependency information for training HiSAN by setting $\lambda$ to $1.0$.
\item {\bf HiSAN w/o syn:} Different from HiSAN w/ syn, this setting does not consider syntactic dependency information for training HiSAN. $\lambda$ is set to $0.0$ for excluding any influence of syntactic dependency information.
\end{itemize}
We list the number of weight parameters of the comparison methods in Table \ref{tab:params}.

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%% table 1
\begin{table}[t]
\input{01table01.tex}
\caption{The number of weight parameters for each method.}
\label{tab:params}
\end{table}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%


%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\subsubsection{Training Details}

Following the previous work \cite{wang-EtAl:2017:Long4}, the dimensions of the word embeddings, LSTM layers, and attention layer were set to 100.
For the Tagger-style and Seq2Seq-style methods, the depth of the LSTM layer was set to three and two, respectively.
In this setting, all methods have a total of six LSTM-layers.
The dimensions of POS and dependency-relation label embeddings were set to 40.
All parameters were initialized as per the method described by Glorot and Bengio (2010)\nocite{glorot2010understanding}.
For all methods, we applied Dropout \cite{srivastava2014dropout} to the input of LSTM layers.
All the dropout rates were set to 0.3.

During training, the learning rate was tuned with Adam \cite{DBLP:journals/corr/KingmaB14}.
The initial learning rate was set to 0.001.
The maximum number of training epochs was set to 30.
All the gradients were averaged in each mini-batch.
The maximum mini-batch size was set to 16.
The order of mini-batches was shuffled at the end of each training epoch.
The clipping threshold of the gradient was set to 5.0.
We selected trained models with early stopping for maximizing the per-sentence accuracy (i.e., how many compressions could be fully reproduced) of the development dataset.

To obtain a compressed sentence, we used greedy decoding instead of beam search decoding, because the latter did not demonstrate better performance in the development dataset.
This may relate to the small search space of this task, because the number of labels is only 3.
All the methods were implemented in C++ on Dynet \cite{neubig2017dynet}.


%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\subsection{Automatic Evaluation}

For automatic evaluation, we used token-level F$_{1}$-measure ($\mathbf{F_{1}}$) as well as the recall scores of ROUGE-1, -2, and -L \cite{lin-och:2004:ACL}.
We used the ROUGE-1.5.5 script for calculating the ROUGE scores.
When calculating the ROUGE-1 score, we excluded stop words by using options ``-n 1 -m -d -s -a'' to consider the informativeness of the compressed sentences.
When calculating the ROUGE-2 and ROUGE-L scores, we used options ``-n 2 -m -d -a'' to avoid meaningless collocations.
For a fair comparison while calculating ROUGE scores, if a system output exceeded the reference summary byte length, we truncated the exceeding tokens.

We used $\Delta C =$ \textit{system compression ratio} $-$ \textit{gold compression ratio} to evaluate the closeness of the compression ratio of system outputs to that of gold compressed sentences.
Notably, we calculated $\Delta C$ in this study after rounding the compression ratios for each method.
We used micro-averages for F$_{1}$-measure and compression ratio, and macro-averages for the ROUGE scores, respectively.

To verify the superiority of our methods on long sentences, we additionally reported the scores on sentences longer than the average sentence length ($=27.04$) in the test set.

All the results are reported as the average scores and their standard deviation of five trials.
In each trial, different random choices were used to generate the initial values of the embeddings and the order of mini-batch processing.

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%% table 2
\begin{table}[t]
\input{01table02.tex}
\hangcaption{%
Results of automatic evaluation for all sentences in the test dataset. $\pm$ denotes the standard deviation for each score. $\mathbf{CR}$ denotes the compression ratio. $\mathbf{d}$ represents the groups of $d$-length dependency chains. \textasteriskcentered~ indicates the best scoring model among similar methods with different $\mathbf{d}$ in the development dataset. Bold values indicate the best scores.}
\label{tb:eval:all:auto}
\end{table}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%% table 3
\begin{table}[t]
\input{01table03.tex}
\hangcaption{Results of automatic evaluation for long sentences (longer than the average length, $27.04$) in the test dataset. The notation used is the same as in Table \ref{tb:eval:all:auto}}
\label{tb:eval:long:auto}
\end{table}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

Table \ref{tb:eval:all:auto} and \ref{tb:eval:long:auto} present the results with the setting for all sentences (\textbf{ALL}) and long sentences (\textbf{LONG}), respectively.
The HiSANs outperformed the other methods.
In particular, HiSAN w/ syn ($d=\{1,2,4\}$) achieved the best score on F$_{1}$, ROUGE-2, ROUGE-L, and $\Delta C$ in the \textbf{ALL} setting.
In addition, the improvements with HiSAN w/ syn ($d=\{1,2,4\}$) in F$_{1}$ and ROUGE scores from the baselines methods in the \textbf{LONG} setting are larger than those in the \textbf{ALL} setting.
HiSAN w/o syn ($d=\{1,2,3,4\}$) achieved comparable scores with HiSAN w/ syn ($d=\{1,2,4\}$) in the \textbf{ALL} setting.
In the \textbf{LONG} setting, HiSAN w/o syn ($d=\{1,2,3,4\}$) achieved higher ROUGE scores compared with HiSAN w/ syn.
This result indicates that our recursive attention module can retain important words in the compressed sentence without considering syntactic dependency information.
However, in terms of F$_1$, HiSAN w/o syn scores were lower than those of HiSAN w/ syn ($d=\{1,2,4\}$) in both \textbf{ALL} and \textbf{LONG} settings, which suggests that considering explicit syntactic dependency information can reduce redundant words during sentence compression. 
From these results, we can conclude that $d$-length dependency chains are effective for sentence compression, especially in the case of longer than average sentences.
HiSAN ($d=\{1\}$) outperformed \textbf{HiSAN-Dep} in F$_{1}$ scores in both \textbf{ALL} and \textbf{LONG} settings.
This result shows the effectiveness of joint learning the dependency parse tree and output labels. 


%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\subsection{Human Evaluation}

For human evaluation, we compared the baselines with our method, which achieved the highest F$_1$ score in the automatic evaluations.
Sentences listing only a large number of multiple entities or containing long quotations are unsuitable for manual evaluation owing to various possible interpretations. Thus, we first removed such sentences from the test dataset. Then, we selected the first 100 sentences longer than the average sentence length ($=27.04$) of the filtered test set in the order of appearance for human evaluation. It should be noted that when removing such sentences, we identified them by the following rules: the sentence includes more than ten commas; the sentence includes a quotation symbol (``). Notably, we determined the number of commas by verifying that the human evaluation dataset did not contain any removable sentences. We show the statistics of the selected sentences in Fig.~\ref{fig:human:length} and \ref{fig:human:depth}. 

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%% fig. 8 and 9
\begin{figure}[b]
\setlength{\captionwidth}{200pt}
\begin{minipage}[t]{200pt}
\begin{center}
\includegraphics{28-2ia1f8.pdf}
\end{center}
\caption{The frequencies for each sentence length.}
\label{fig:human:length}
\end{minipage}
\hfill
\begin{minipage}[t]{200pt}
\begin{center}
\includegraphics{28-2ia1f9.pdf}
\end{center}
\hangcaption{The frequencies for each dependency depth.}
\label{fig:human:depth}
\end{minipage}
\end{figure}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%% table 4
\begin{table}[b]
\input{01table04.tex}
\hangcaption{%
Results of human evaluation. {\it All} denotes the results for all sentences in the test set, and {\it Diff} represents the results for the sentences with different compressions for each method. Parentheses ( ) denote the sentence size. The average gold compression ratio for input sentences in {\it All} and {\it Diff} were $32.1$ and $31.5$, respectively. Other notations are similar to those in Table \ref{tb:eval:all:auto}.}
\label{tb:eval:human}
\end{table}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

Similar to Filippova et al.\ (2015)\nocite{filippova-EtAl:2015:EMNLP}, a compressed sentence was rated by five annotators who were asked to select a rating on a five-point Likert scale, ranging from one to five for readability (\textbf{Read}) and for informativeness (\textbf{Info}).
We report the average of these scores from the five raters.
To investigate the differences between the methods, we also compared the baseline methods and HiSAN by using those sentences that displayed different compressions with each method.

Table \ref{tb:eval:human} shows the results.
HiSAN w/ syn ($d\!=\!\{1,2,4\}$) achieved better results than the baselines in terms of both readability and informativeness.
The results agree with those obtained from the automatic evaluation.
From the results of the sentences with different compressions between the baseline and HiSAN w/ syn ($d\!=\!\{1,2,4\}$), we can clearly observe the improvement attained by HiSAN w/ syn ($d\!=\!\{1,2,4\}$) in informativeness.

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%% fig. 10
\begin{figure}[b]
\begin{center}
\includegraphics{28-2ia1f10.pdf}
\end{center}
\caption{The F$_1$ scores for each sentence length.}
\label{fig:grouped:bar}
\end{figure}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%


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

Fig.~\ref{fig:grouped:bar} presents the F$_1$ scores of each method for each sentence length. Notably, the HiSANs presented in this figure is the model that achieved the best F$_1$ scores in the validation dataset. In results for sentence lengths longer than 45, we can obviously observe that the syntactic information surpasses the performance degradation of Seq2Seq models. Tagger is also effective for such sentences because it does not have a decoder to memorize previously predicted labels for a correct prediction, and thus, it can deal with long sentences. However, the entire compression performance of Tagger is lower than Seq2Seq-based methods. In sentences with 45 words or less, HiSANs achieved high scores regardless of syntactic information. These results show that the network structure of HiSAN itself contributes to the improvement of F$_1$ scores.

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%% table 5
\begin{table}[t]
\input{01table05.tex}
\caption{Example sentences and compressions.}
\label{tb:output}
\end{table}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

Table \ref{tb:output} shows the examples of source sentences and their compressed variants generated by the baseline and HiSANs.
We chose the model with the highest F$_1$ in the test set after five trials.
For both examples, the compressed sentence output achieved by \textbf{Base} is grammatically correct. However, the informativeness is inferior to that attained by HiSAN w/ syn ($d=\{1,2,4\}$). 
The compressed sentence output by \textbf{HiSAN-Dep} in the second example lacks both readability and informativeness.
Because \textbf{HiSAN-Dep} employs features obtained from the dependency tree in the pipeline procedure, it is influenced by the parsed tree. Based on this information, we checked the actual parsed tree and observed that the parent of ``US'' is wrongly predicted as ``whistler'', instead of ``Manning''. Zewei et al. (2020)\nocite{DBLP:conf/aaai/SunHWDC20} revealed that Seq2Seq produces output related to the words that are indicated by attention. In the case of \textbf{HiSAN-Dep}, we can observe that the content of the wrongly stored parts in the compression is actually related to ``whistler''. From this observation, we believe that the compression failure in this case is caused by the incorrect parse result.
As reported in papers \cite{klerke-goldberg-sogaard:2016:N16-1,wang-EtAl:2017:Long4}, the F$_{1}$ scores of \textbf{Tagger} match or exceed those of the Seq2Seq-based methods.
The compressed sentence in the first example in Table \ref{tb:output} generated by \textbf{Tagger} is ungrammatical.
We believe that this is mainly because \textbf{Tagger} cannot consider the predicted labels of the previous words.
\textbf{Tagger-ILP} outputs grammatically incorrect compressed sentences in both examples, which indicates that the ILP constraint imposed on the parent-child relationships between words is insufficient to generate fluent sentences.
Compared with these baselines, HiSAN w/ syn ($d=\{1,2,4\}$) output fluent and more informative compressed sentences.
HiSAN w/o syn ($d=\{1,2,3,4\}$) also output fluent compressed sentences.
However, in the first example, the output of HiSAN w/o syn ($d=\{1,2,3,4\}$) dropped the country names.
This may indicate that HiSAN w/o syn ($d=\{1,2,3,4\}$) did not capture the relationship between the children of ``signed'' owing to a lack of syntactic dependency information.
These observations, which confirmed our expectation that syntactic dependency information helps in retaining important words, is supported by the automatic and human evaluation results.

We confirm that the compression performance of HiSAN w/ syn actually improves if the sentences have deep dependency trees.
Table \ref{tb:eval:auto:depth} shows the automatic evaluation results for sentences with deep dependency trees.
We can observe that HiSANs with higher-order dependency chains has better compression performance if the sentences have deep dependency trees.
In terms of F$_1$ scores, HiSAN w/ syn $\mathbf{d} = \{1,2,4\}$ outperformed HiSAN w/o syn $\mathbf{d} = \{1,2,3,4\}$, which indicates that explicit syntactic dependency information can help compress sentences with deep dependency trees.

Fig.~\ref{fig:graph} shows a compressed sentence and its dependency graph as determined by HiSAN w/ syn $\mathbf{d} = \{1,2,4\}$. 
Almost all the arcs with large probabilistic weights are contained in the parsed dependency trees.
Interestingly, a few arcs not contained in the parsed dependency trees directly connect words that are connected by the dependency chains (bold gray arrows) in the original parsed dependency tree.

Considering that the training dataset does not contain such dependency relationships, we can estimate that these arcs are learned for supporting the sentence compression.
This result meets our expectation that the dependency chain information is necessary for compressing sentences accurately.

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%% table 6
\begin{table}[p]
\input{01table06.tex}
\hangcaption{Results of automatic evaluation using sentences with deep dependency trees (deeper than average depth, 8). The notations are the same as in Table \ref{tb:eval:all:auto}.}
\label{tb:eval:auto:depth}
\end{table}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%% fig. 11
\begin{figure}[p]
\begin{center}
\includegraphics{28-2ia1f11.pdf}
\end{center}
\hangcaption{%
An example compressed sentence and its dependency graph with HiSAN $\mathbf{d} = \{1,2,4\}$. The gray-colored words represent deleted words. The numbers for each arc represent the probabilistic weight of a relationship between parent and child words. The arcs contained in the parsed dependency tree are located on the top side. The arcs not contained in the parsed dependency tree are located at the bottom.}
\label{fig:graph}
\end{figure}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%% fig. 12
\begin{figure}[p]
\begin{center}
\includegraphics{28-2ia1f12.pdf}
\end{center}
\hangcaption{Attention distributions for each setting of HiSAN w/o syn. The words in columns represent an input sentence while those in rows represent the compressed sentences for each method. The gray-colored words represent deleted words.} 
\label{fig:att:wosyn}
\end{figure}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

We present a matrix style visualization of the attention distribution for HiSAN w/o syn. Different from HiSAN w/syn, HiSAN w/o syn displays smooth distributions owing to the lack of supervised dependency tree information. Therefore, visualizing them with the dependency style shown in Fig.~\ref{fig:graph} is unsuitable for their interpretation.
Fig.~\ref{fig:att:wosyn} shows the attention distributions for each setting of HiSAN w/o syn.
In the matrices in $d=\{1\}$, $d=\{1,2\}$, $d=\{1,2,4\}$, and $d=\{1,2,3,4\}$, we did not observe any obvious sentence head or tree-like relationships between the parent and child words.
In the case of $d=\{1,2,3\}$, it is evident that the two to-clauses are treated as the heads of other words.
However, the verb ``signed'' is less attended than other words even though the word is the head of the gold compressed sentence.
These tendencies indicate that the attention distributions obtained through unsupervised training are unlikely to contain explicit syntactic dependency structures.
This can be a reason why F$_1$ scores of HiSAN w/o syn were largely lower than those of HiSAN w/ syn in the sentences with deep dependency trees.

Table \ref{tab:lambda} shows the F$_1$ scores of HiSAN $\mathbf{d} = \{1,2,4\}$ for each $\lambda$. The model with the setting $\lambda=1.0$ or $\lambda=0.0$ achieved better F$_1$ scores compared with those obtained with the other settings of $\lambda$. As we had discussed during the attention distribution analysis, $\lambda=1.0$ and $\lambda=0.0$ have largely different attention distributions. Because HiSAN contains only a single self-attention module, it is difficult to express such multiple attention distributions in the same network. Therefore, we still have room to improve the compression performance by using recursive attention in multi-head attention \cite{NIPS2017_3f5ee243}.

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%% table 7
\begin{table}[t]
\input{01table07.tex}
\caption{F$_1$ scores of HiSAN $\mathbf{d} = \{1,2,4\}$ in the development and test datasets for each $\lambda$.}
\label{tab:lambda}
\end{table}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%


%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\section{Related Work}

Several neural network-based methods for sentence compression use syntactic features.
Filippova et al. (2015)\nocite{filippova-EtAl:2015:EMNLP} employed the features obtained from automatic parse trees in the LSTM-based encoder-decoder in a pipeline manner.
Wang et al. (2017)\nocite{wang-EtAl:2017:Long4} trimmed the dependency trees based on the scores predicted by an LSTM-based tagger.
Although these methods can consider the dependency relationships between words, the pipeline approach and the first-order dependency relationship fail to compress sentences that are longer than average.

Several machine translation studies have also utilized syntactic features in Seq2Seq models.
Eriguchi et al.\ (2017) and Aharoni and Goldberg (2017)\nocite{eriguchi-tsuruoka-cho:2017:Short,aharoni-goldberg:2017:Short} incorporated syntactic features of the target language in the decoder part of Seq2Seq.
Both methods outperformed Seq2Seq without syntactic features in terms of translation quality.
Song et al.\ (2020)\nocite{Song2020JointPA} adopted the model of Eriguchi et al.\ (2017) for headline generation tasks and reported improvements in summarization quality.
However, these methods fail to provide an entire parse tree until the decoding phase is finished.
Thus, these methods cannot track all the possible parents for each word within the decoding process.
Similar to HiSAN, Hashimoto and Tsuruoka (2017) \nocite{hashimoto-tsuruoka:2017:EMNLP2017} used dependency features as attention distributions; however, different from HiSAN, they used pre-trained dependency relations, and did not take into account the chains of dependencies.
They reported an improvement in BLEU scores when their Seq2Seq was trained with syntactic dependency information.
Marcheggiani and Titov (2017) and Bastings et al. (2017) \nocite{marcheggiani-titov:2017:EMNLP2017,bastings-EtAl:2017:EMNLP2017} considered higher-order dependency relationships in Seq2Seq by incorporating a graph convolution technique \cite{DBLP:journals/corr/KipfW16} into the encoder.
However, the dependency information of the graph convolution technique was still provided in a pipeline manner, and thus, their method cannot work without syntactic tree information. This weak point restricts the availability of their model when a target dataset is not accompanied by syntactic trees. Such a case is possible with out-of-domain datasets and low resourced languages.

Unlike the above methods, HiSAN can capture higher-order dependency features using $d$-length dependency chains without relying on pipeline processing.
In addition, it can continue learning even in the absence of syntactic dependency information.
Recently, Zhao et el. (2018)\nocite{zhao-etal-2018-language} also proposed a method that can avoid the effect of parse fails by incorporating a syntax-based language model into a sequential tagger as a reward for reinforcement learning. Different from HiSAN, their method requires a language model to run during training. Niu et al. (2019)\nocite{niu2019deleter} utilized a pre-trained language model BERT \cite{devlin-etal-2019-bert} to generate a grammatically compressed sentences in an unsupervised manner. For considering the successful use of such a language model, we extended HiSAN to incorporate ELMo \cite{peters-etal-2018-deep} and BERT for capturing important words \cite{kamigaito2020syntactically}. In addition, this extension included a new decoding method not considered in HiSAN. This decoding method can consider words that will be decoded in the future for compressing sentences more accurately. Furthermore, HiSAN was also extended to solve single document summarization \cite{ishigaki-etal-2019-discourse}.
The success of these extensions shows the versatility of HiSAN.


%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\section{Conclusion}

In this study, we investigated the performance of HiSAN, our proposed model that incorporates higher-order dependency features into Seq2Seq to compress sentences of all lengths.

Experiments on the Google sentence compression test data showed that HiSAN achieved better results than baseline methods on F$_{1}$ as well as ROUGE-1, -2, and -L scores (83.2, 78.6, 71.6, and 78.3, respectively).
Particularly, when challenged with longer than average sentences, HiSAN outperformed the baseline methods in terms of F$_{1}$ and ROUGE-1, -2, and -L scores.
HiSAN also outperformed the previous methods in both readability and informativeness during human evaluations.
Furthermore, HiSAN outperformed the baseline methods without using any syntactic dependency information.

Our investigation shows the effectiveness of syntactic dependency information in compressing long sentences with higher F1 scores by maintaining accurate compression rates. Furthermore, our analysis also indicates that HiSAN can compress sentences with precise length without relying on any syntactic dependency tree. From these results, we conclude that HiSAN is a useful tool for sentence compression tasks.


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

This paper is an extended version of our preliminary paper \cite{kamigaito-etal-2018-higher} presented in NAACL-HLT 2018. In this paper, we add detailed explanations and the following new information to the original one:
Investigation regarding the performance of HiSAN without syntactic information; the list of parameters for each compared method; standard deviations for each score of the automatic evaluation; statistics for the human evaluation dataset; discussion of the automatic evaluation results for each sentence length; discussion of the attention distributions for HiSANs; scores of HiSAN for each $\lambda$; related work including recent research.


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


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

\bioauthor[:]{Hidetaka Kamigaito}{%
received his Ph.D. from Tokyo Institute of Technology, and is currently an assistant professor at Institute of Innovative Research, Tokyo Institute of Technology. His current research interests are in natural language processing with a specific focus on document-level text processing.}

\bioauthor[:]{Katsuhiko Hayashi}{%
received PhD in Engineering from the graduate school of Information Science at the Nara Institute of Science and Technology in 2013.
He is currently an associate professor in Gunma University and a visiting researcher in the Riken Center for Advanced Intelligence Project. His research interests include natural language processing and statistical relational learning.}

\bioauthor[:]{Tsutomu Hirao}{%
received the B.E. from Kansai University in 1995 and the M.E. and Ph.D. in engineering from Nara Institute of Science and Technology in 1997 and 2002, respectively. He is currently with NTT Communication Science Laboratories. His current research interests include Natural Language Processing and Machine Learning.}

\bioauthor[:]{Masaaki Nagata}{%
received the B.E., M.E., and Ph.D. degrees in information science from Kyoto University, Japan, in 1985, 1987, and 1999, respectively. In 1987, he joined Nippon Telegraph and Telephone Corporation (NTT). He is currently a Senior Distinguished Researcher at NTT Communication Science Laboratories. He is a member of the Association for Computational Linguistics and the Association for Natural Language Processing.}

\bioauthor[:]{Manabu Okumura}{%
received Dr.~Eng.\ from Tokyo Institute of Technology, and is currently a professor at Institute of Innovative Research, Tokyo Institute of Technology. His current research interests include natural language processing, especially text summarization, computer assisted language learning, sentiment analysis, and text data mining.}

\end{biography}


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



\end{document}

