\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{amssymb}
%%%%%\usepackage{amsmath}
\usepackage{csquotes}
\usepackage{multirow}
\usepackage{booktabs}
%%%%%\usepackage{algorithmic}
\usepackage{algorithm}
%%%%%\usepackage{algorithm}
\usepackage{algpseudocode}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\Volume{28}
\Number{4}
\Month{December}
\Year{2021}
\Issuetitle{Special Issue: XXXXXXXX}

\received{2021}{3}{1}
\revised{2021}{6}{1}
%%%%\rerevised{2006}{5}{6}
\accepted{2021}{7}{6}

\setcounter{page}{965}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%   Title, Author, etc.            %%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\esubject{General Paper}
\etitle{Improved Decomposition Strategy for Joint Entity and Relation Extraction}
\eauthor{Van-Hien Tran\affiref{Author_1} \and Van-Thuy Phi\affiref{Author_1} \and Akihiko Kato\affiref{Author_1} \and Hiroyuki Shindo\affiref{Author_1} \and \\
	Taro Watanabe\affiref{Author_1} \and Yuji Matsumoto\affiref{Author_2} } 
\eabstract{
The joint entity and relation extraction task detects entity pairs along with their relations to extract relational triplets. A recent study \cite{yubowendecomposition2020} proposed a novel decomposition strategy that splits the task into two interrelated subtasks: detection of the head-entity (\textit{HE}) and identification of the corresponding tail-entity and relation (\textit{TER}) for each extracted head-entity. However, this strategy suffers from two major problems. First, if the \textit{HE} detection task fails to find a valid head-entity, the model will then miss all related triplets containing this head-entity in the \textit{head} role. Second, as \citeA{yubowendecomposition2020} stated, their model cannot solve the entity pair overlap (EPO) problem. For a given head-entity, the \textit{TER} extraction task predicts only a single relation between the head-entity and a tail-entity, even though this entity pair can hold multiple relations. To address these problems, we propose an improved decomposition strategy that considers each extracted entity in two roles (\textit{head} and \textit{tail}) and allows a model to predict multiple relations (if any) of an entity pair. In addition, a corresponding model framework is presented to deploy our new decomposition  strategy. Experimental results showed that our approach significantly outperformed the previous approach of \citeA{yubowendecomposition2020} and achieved state-of-the-art performance on two benchmark datasets.
}
\ekeywords{Information Extraction, Joint Extraction, Named-Entity Recognition, Relation Classification, Decomposition Strategy}

\headauthor{Tran et al.}
\headtitle{Improved Decomposition Strategy for Joint Entity and Relation Extraction}

\affilabel{Author_1}{}{Nara Institute of Science and Technology, Japan}
\affilabel{Author_2}{}{RIKEN Center for Advanced Intelligence Project (AIP)}


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

\maketitle

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

The extraction of relational triplets is a critical and challenging task in natural language processing (NLP). Given an unstructured text, it aims to extract pairs of entities with semantic relations, in the form of (\textit{head, relation, tail}). The relational triplets extraction has attracted considerable research effort as it plays a vital role in many NLP applications such as information extraction \cite{tran2021covrelex} and question answering \cite{haoetal2017end}. For example, in information extraction, given a biomedical text, it is expected to extract both the biomedical entities and their relations in the form of triplets such as (\enquote{\textit{coronavirus}}, \enquote{causes}, \enquote{\textit{respiratory infections}}) and (\enquote{\textit{tocilizumab}}, \enquote{treats}, \enquote{\textit{cytokine release syndrome}}).


Traditional pipeline works \cite{zelenko2003kernel,zhou-etal-2005-exploring,chan-roth-2011-exploiting} divide this task into two isolated subtasks: named-entity recognition (NER) \cite{vu2015ner} and relation classification (RC) \cite{tran2019relation}. Specifically, they first recognize all the entities and then predict relations between the extracted entities. Such methods tend to suffer from error propagation and ignore the relevance between the two subtasks. To address these problems, subsequent studies proposed joint learning of entities and relations in a single model, including feature-based models \cite{yu-lam-2010-jointly,li-ji-2014-incremental,ren2017cotype} and neural network-based models \cite{gupta-etal-2016-table,katiyar-cardie-2017-going,zeng-etal-2018-extracting,fu-etal-2019-graphrel,yubowendecomposition2020}.  

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%% fig. 1
\begin{figure}[b]
\begin{center}
\includegraphics{28-4ia2f1.pdf}
\end{center}
\caption{An example of the \textit{entity pair overlap} (EPO) and \textit{single entity overlap} (SEO) triplets.}
\label{fig:example}
\end{figure}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

One of the biggest challenges of this task is the \textit{overlapping triplet problem}, which is expressed in two scenarios: \textit{entity pair overlap} (\textbf{EPO}) and \textit{single entity overlap} (\textbf{SEO}). Specifically, EPO occurs when triplets share the same entity pair but with different relations, such as: (\enquote{\textit{Paris}}, \enquote{Capital\_of}, \enquote{\textit{France}}), (\enquote{\textit{Paris}}, \enquote{Located\_in}, \enquote{\textit{France}}), and (\enquote{\textit{Paris}}, \enquote{Administrative\_division\_of}, \enquote{\textit{France}}), as shown in Figure~\ref{fig:example}. SEO occurs when two relational triplets share only one common entity, such as: (\enquote{\textit{John Smiths}}, \enquote{Work\_in}, \enquote{\textit{Paris}}) and (\enquote{\textit{John Smiths}}, \enquote{Live\_in}, \enquote{\textit{France}}).

Most previous works could not efficiently address the   \textit{overlapping triplet problem}. This problem directly challenges conventional sequence tagging schemes, in which each token represents only a single tag \cite{zheng-etal-2017-joint}. It also creates significant difficulties in traditional RC approaches, where an entity pair is supposed to hold at most one relation \cite{miwa-bansal-2016-end}. \citeA{zeng-etal-2018-extracting} is among the first to solve the problem by proposing a sequence-to-sequence model with a copy mechanism. \citeA{fu-etal-2019-graphrel} utilized a graph convolutional network to extract overlapping triplets. In contrast to the previous works, \citeA{yubowendecomposition2020} presented a unified sequence labeling framework based on a novel decomposition strategy. However, this method can only deal with the SEO triplets in the sample and fails to handle the EPO cases, as \citeA{yubowendecomposition2020} stated.


Specifically, \citeA{yubowendecomposition2020} decomposed the joint task into two subtasks: head-entity extraction and tail-entity relation extraction. The first task detects all head-entities, whereas the second one detects the corresponding tail-entities and target relations for a given head-entity. Although this method significantly outperforms previous methods, it suffers from two issues. \textbf{First}, to create relational triplets, it always detects head-entities first and then extracts the corresponding tail-entities and relations for each detected head entity. Thus, observably, if the first task fails to find a valid head-entity, the model will then miss all the related triplets containing this head-entity in the \textit{head} role. \textbf{Second}, as \citeA{yubowendecomposition2020} stated, their model cannot solve the \textit{overlapping triplet problem} in the EPO scenario. For a given head-entity, the second task predicts only a single relation between the given head-entity and any corresponding tail-entity, even though this entity pair can hold multiple relations.


Therefore, we propose an improved decomposition strategy to overcome these two problems. For the \textbf{first issue}, we designed a more flexible strategy. We detect all entities first, and then, for each extracted entity, we identify it in each (\textit{head} /  \textit{tail}) entity role and extract the corresponding (\textit{tail-entities} / \textit{head-entities}) and relations. For the \textbf{second issue}, we define a set of \enquote{\textit{unified relation labels}} (\textit{URLs}), each of which represents a unique (unordered) subset of the full set of original relations. By using these \textit{URLs} in a multiclass classifier, our model can solve the EPO problem. In addition, a corresponding model framework is introduced to deploy our new strategy. The experimental results on both two benchmark datasets showed that our approach significantly outperformed the previous approach of \citeA{yubowendecomposition2020} as well as previous state-of-the-art approaches. 


%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\section{Methodology}

In this section, we first introduce the decomposition strategy of \citeA{yubowendecomposition2020} and then present our new strategy. In addition, a corresponding model framework is proposed for deploying our decomposition strategy.   


%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\subsection{Tagging Scheme}
\label{subsectionTaggingScheme}

\citeA{yubowendecomposition2020} decomposed the joint extraction task into two interrelated subtasks: \textit{H}ead-\textit{E}ntity (\textit{HE}) extraction and \textit{T}ail-\textit{E}ntity \textit{R}elation (\textit{TER}) extraction. The \textit{HE} extraction task is modeled by two sequence labeling tasks, one for identifying the start position and the other for the end position of the head-entities, respectively. The entity type is also labeled simultaneously at the head-entity positions. Meanwhile, for each identified head-entity, the \textit{TER} extraction task is also modeled by two sequence labeling tasks, one for detecting the start position and the other for detecting the end position of the corresponding tail-entities. As is done for the \textit{HE} detection, the relation type between the given head-entity and its corresponding tail-entity is also labeled in each position.


%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%% fig. 2
\begin{figure}[b]
\begin{center}
\includegraphics{28-4ia2f2.pdf}
\end{center}
\hangcaption{%
(a) Tagging scheme of \protect\citeA{yubowendecomposition2020}. (b) Our tagging scheme. \textit{PER} and \textit{LOC} stand for \textit{PERSON} and \textit{LOCATION}, 
respectively.  \textit{HE}, \textit{TER}, and \textit{HTER} stand for \textit{\textbf{H}ead-\textbf{E}ntity}, \textit{ \textbf{T}ail-\textbf{E}ntity \textbf{R}elation}, 
and \textit{\textbf{H}ead/\textbf{T}ail \textbf{E}ntity \textbf{R}elation}, respectively. The set of gold triplets is: \{(\textit{\enquote{John Smiths}}, R\textsubscript{1}, 
\textit{\enquote{Paris}}), (\textit{\enquote{John Smiths}}, R\textsubscript{2}, \textit{\enquote{Paris}}),
(\textit{\enquote{John Smiths}}, R\textsubscript{1}, \textit{\enquote{France}}), (\textit{\enquote{John Smiths}}, R\textsubscript{2}, \textit{\enquote{France}}),
(\textit{\enquote{Paris}}, R\textsubscript{3}, \textit{\enquote{France}}), (\textit{\enquote{Paris}}, R\textsubscript{4}, \textit{\enquote{France}}), (\textit{\enquote{Paris}}, 
R\textsubscript{5}, \textit{\enquote{France}})\}, where R\textsubscript{1}:\textit{\enquote{Live\_in}}; R\textsubscript{2}:\textit{\enquote{Work\_in}};
R\textsubscript{3}:\textit{\enquote{Capital\_of}};
R\textsubscript{4}:\textit{\enquote{Located\_in}}; and R\textsubscript{5}:\textit{\enquote{Administrative\_division\_of}}. In (b), 
$\hat{R}$\textsubscript{1} and $\hat{R}$\textsubscript{2} are \textit{URLs}, where $\hat{R}$\textsubscript{1}:\{R\textsubscript{1}, R\textsubscript{2}\} 
and $\hat{R}$\textsubscript{2}:\{R\textsubscript{3}, R\textsubscript{4}, R\textsubscript{5}\}.}
\label{fig:SchemeTagging}
\end{figure}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

Figure~\ref{fig:SchemeTagging}(a) illustrates an example of the above tagging scheme. From the input sample, the \textit{HE} tagging detects the HEs: \enquote{\textit{John Smiths}} and \enquote{\textit{Paris}} because they are HEs in the set of gold triplets. Then, for the given HE \enquote{\textit{Paris}}, the \textit{TER} tagging identifies the tail-entity \enquote{\textit{France}} with the expected relation R\textsubscript{3} because of the gold triplet: (\textit{\enquote{Paris}}, R\textsubscript{3}, \textit{\enquote{France}}). However, this tagging scheme suffers from two existing problems (as mentioned in Section~\ref{sec:introduction}) that hinder a further improvement of the system performance. We explain in detail how our new decomposition strategy can solve these two issues.


\textbf{First}, to obtain relational triplets in the form of (\textit{head}, \textit{relation}, \textit{tail}), the model by \citeA{yubowendecomposition2020} always detects the HEs first and then extracts the corresponding tail-entities and relations for each detected HE. Following this strategy, if \textit{HE} tagging fails to find a valid HE, the model will then miss all the related triplets. For instance, in Figure~\ref{fig:SchemeTagging}(a), if \enquote{\textit{Paris}} is not identified as a HE, the model will miss all gold triplets containing \enquote{\textit{Paris}} in the \textit{head} role. Meanwhile, it is not always easy to extract head entities first for all relations, especially when the relation types are diverse.  To deal with this issue, we designed a new strategy, which is illustrated in Figure~\ref{fig:SchemeTagging}(b). This strategy allows our model not only to learn the probability distribution closer to the gold labels but also to increase the chances of extracting a valid triplet, which may be overlooked by the approach of \citeA{yubowendecomposition2020}. Specifically, we first extract all entities without differentiating the \textit{head}/\textit{tail} role using the \textit{Entity} tagging in our scheme. For each extracted entity, the  \textit{head/tail entity relation} (\textit{HTER}) tagging considers it in each \textit{head/tail} role and detects all corresponding \textit{tail entities/head entities} and relation types, respectively. For example, in Figure~\ref{fig:SchemeTagging}(b), the \textit{Entity} tagging detects the entities: \enquote{\textit{John Smiths}}, \enquote{\textit{Paris}}, and \enquote{\textit{France}}. Then, for the given entity \enquote{\textit{Paris}}, the \textit{HTER} tagging considers it in the \textit{head} role to identify the tail-entity \enquote{\textit{France}} with the \textit{unified relation label} (URL) $\hat{R}$\textsubscript{2}, and also considers \enquote{\textit{Paris}} in the \textit{tail} role to recognize the HE \enquote{\textit{John Smiths}} with the \textit{URL} $\hat{R}$\textsubscript{1}.

\textbf{Second}, the previous tagging scheme cannot solve the EPO problem. For instance, in Figure~\ref{fig:SchemeTagging}(a), the entity pair (\enquote{\textit{Paris}}, \enquote{\textit{France}}) holds multiple relations: R\textsubscript{3}, R\textsubscript{4}, and R\textsubscript{5}. However, for the given HE \enquote{\textit{Paris}}, the \textit{TER} tagging can predict only one of the original relations to the tail-entity \enquote{\textit{France}}, using a multi-class classifier of ($N_R$+$1$) classes, which include $N_R$ original relations and one special class \textit{No\_relation}. To overcome this limitation, we propose two different solutions. First, in a natural way, we use a multi-label classifier to detect multiple relations (if any) between an ordered entity pair. With this solution, each tagging position in the \textit{HTER} tagging can hold multiple original relation types (if any), instead of only a maximum of a single relation type (if any), as assumed by \citeA{yubowendecomposition2020}. However, in practice, the maximum number of relation types co-occurring between an entity pair is often small\footnote{%
There are two possible reasons for this phenomenon. First, because each relation type is usually associated with certain entity types (e.g., \enquote{\textit{Live\_in}} is between \textit{Person} and \textit{Location}), relation types co-occurring in the same entity pair are often required to share the same entity type pair. Second, in the joint extraction task, as each entity is often mentioned only once and the length of the input sample is not very long, they lead to the limited expressions of the possible relations of the same entity pair.}. For instance, the maximum number of relation types for any entity pair is only $3$ in both the NYT \cite{riedel2010modeling} and the WebNLG \cite{gardent-etal-2017-creating} datasets, while the total number of original relations on the NYT and WebNLG datasets is $24$ and $216$, respectively. Consequently, the sparse label problem on the relation types of the same entity pair can affect the system performance, especially in the WebNLG dataset. Therefore, we propose a second solution that uses a multi-class classifier with a set of \textit{URLs} to deal with both the sparse label problem and the EPO problem. In essence, the purpose of using the created \textit{URLs} is to transform the \enquote{multi-label classification task with a sparse label problem on the set of original relations} into the \enquote{multi-class classification task on the set \textit{URLs}}.

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%% algo. 1
\begin{algorithm}[b]
\caption{Creation of a set of \enquote{\textit{unified relation labels}}}
\label{alg:createS}
\input{02algo01.tex}
\end{algorithm}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%


Using the training set \textbf{\textit{D}} and a predefined threshold $\gamma$, following  Algorithm~\ref{alg:createS}, we create the set \textit{URLs}. Specifically, first of all, for each ordered entity pair $\textbf{p}$ in each sample in \textbf{\textit{D}}, the function $F$($\textbf{p}$) returns a single \textit{URL} $\hat{R}$ that represents a unique (unordered) subset, where this subset includes all the existing original relations of the pair \textbf{p}. We then count the frequency of each $\hat{R}$ on the entire \textbf{\textit{D}} and only keep $\hat{R}$ when its frequency is greater than or equal to $\gamma$. With the obtained \textit{URLs}, for each ordered entity pair \textit{(head, tail)} in each sample in \textbf{\textit{D}}, we replace the full set of all existing original relations of this entity pair with a single corresponding \textit{URL} in the set \textit{URLs}. Conversely, we ignore relation sets if they do not match any corresponding \textit{URLs} in the set \textit{URLs}. Note that we only performed this label conversion for the training set, but not for the validation and test sets. With this procedure, any ordered entity pairs in any sentences in the training dataset \textbf{\textit{D}} will now have only a single \textit{URL} in the set \textit{URLs} or have no relation. Finally, we train the model on the training dataset \textbf{\textit{D}} with the \textit{URLs} instead of with the set of original relations.

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%% table 1
\begin{table}[b]
\input{02table01.tex}
\caption{A toy example of creating and using the set \textit{URLs} on the training set \textit{\textbf{D}}.}
\label{toyexample}
\end{table}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

In Table~\ref{toyexample}, we provide a toy example for creating \textit{URLs} using Algorithm~\ref{alg:createS} and for using them on the training set \textit{\textbf{D}}. Assume that the training set \textit{\textbf{D}} includes two samples, where each sample has its gold relational triplets. By using Algorithm~\ref{alg:createS}, we obtain the dictionary Q, which contains all the \enquote{\textit{URLs}} along with their frequencies. With the predefined threshold $\gamma$ (e.g.; $\gamma=1$), we obtain the set \textit{URLs}: \{$\hat{R}$\textsubscript{1},  $\hat{R}$\textsubscript{2}, $\hat{R}$\textsubscript{3}, $\hat{R}$\textsubscript{4}\}. Then, using the created set \textit{URLs}, for each entity pair in each sample, we replace all existing original relations of this pair with a single corresponding \textit{URL} in the set \textit{URLs} (if any). For instance, in Sample $2$, the ordered entity pair: (\enquote{\textit{Alex}}, \enquote{\textit{Spain}}) with the original relations: \{\enquote{Work\_in}, \enquote{Place\_of\_birth}, \enquote{Place\_of\_death}\} will become: (\enquote{\textit{Alex}}, $\hat{R}$\textsubscript{4}, \enquote{\textit{Spain}}). Finally, our designed model will be trained on the training set \textit{\textbf{D}} with the set \textit{URLs}.         


%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\subsection{Network Structure}

Following our tagging scheme in Figure~\ref{fig:SchemeTagging}(b), we present our corresponding model framework in Figure~\ref{fig:NetworkStructure}. It consists of three main parts: \textit{Encoding Layer}, \textit{Entity Extractor}, and \textit{HTER Extractor}.

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%% fig. 3
\begin{figure}[b]
\begin{center}
\includegraphics{28-4ia2f3.pdf}
\end{center}
\hangcaption{%
Our framework. We used the same input sample as in Figures\ $1$ and $2$. Here, the extracted entity \enquote{\textit{Paris}} is entered into the HTER Extractor as prior knowledge. In the HTER Extractor, $\hat{R}$\textsubscript{1} and $\hat{R}$\textsubscript{2} are in the set \textit{URLs} created using Algorithm~\ref{alg:createS}, where $\hat{R}$\textsubscript{1}: \{\enquote{Live\_in}, \enquote{Work\_in}\}, $\hat{R}$\textsubscript{2}:\{\enquote{Capital\_of}, \enquote{Located\_in}, \enquote{Administrative\_division\_of}\}. Note that the HTER Extractor was trained with the set \textit{URLs}, instead of with the set of original relations.}
\label{fig:NetworkStructure}
\end{figure}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%


%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\subsubsection{Encoding Layer}

Given a sample $X$ $=$ \{$x_{1}$, $x_{2}$, ..., $x_{N}$\} with $N$ tokens, we first utilize a bidirectional long short-term memory (BiLSTM) \cite{Hochreiter1997} network to encode the contextualized representation for each token. The initial embedding $\textbf{e}_i$ of each input token is concatenated by three parts: pre-trained word embedding, character-level word embedding generated by a convolutional neural network (CNN) on the character sequence of $x_{i}$, and a part-of-speech (POS) embedding. Then, the contextualized representation sequence $H$ $=$ \{$\textbf{h}_{1}$, $\textbf{h}_{2}$, ..., $\textbf{h}_{N}$\} is obtained as follows:
\begin{gather}
\mathbf{h}_{i}=\left[\overrightarrow{\mathbf{h}}_{i} ; \overleftarrow{\mathbf{h}}_{i}\right], \\
\overrightarrow{\mathbf{h}}_{i}=\operatorname{LSTM}^{f}\left(\mathbf{e}_{i}, \overrightarrow{\mathbf{h}}_{i-1}\right), \overleftarrow{\mathbf{h}}_{i}=\operatorname{LSTM}^{b}\left(\mathbf{e}_{i}, \overleftarrow{\mathbf{h}}_{i+1}\right),
\end{gather} 
where LSTM$^{f}$ and LSTM$^{b}$ denote the forward and backward LSTM, respectively.


%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\subsubsection{Entity Extractor}

The Entity Extractor module aims to recognize the relevant entities in the input sample by directly decoding the output sequence $H$ of the Encoding Layer. Specifically, it adopts two identical multiclass classifiers to detect the start and end positions of the entities with the corresponding entity type label. Formally, the detailed operations of the entity tagging on each token are as follows:
\begin{gather}
    p_{i}^{s t a r t_{-} ent}=Softmax\left(\mathbf{W}_{s t a r t_{-} ent} \mathbf{h}_{i}+\mathbf{b}_{s t a r t_{-} ent}\right), \\
    p_{i}^{end_{-} ent}=Softmax\left(\mathbf{W}_{end_{-} ent} \mathbf{h}_{i}+\mathbf{b}_{end_{-} ent}\right),
\end{gather}
where $p_{i}^{s t a r t_{-} ent}$ and $p_{i}^{end_{-} ent}$ represent the probabilities of the entity type labels for the $i$\textsuperscript{th} token, which are considered as the start and end positions of an entity, respectively. In addition, \textbf{h}$_i$ is the encoded representation, \textbf{W}$_{(.)}$ represents the trainable weight, and \textbf{b}$_{(.)}$ is the bias.

We define the training loss (to be minimized) of the Entity Extractor as the sum of the negative log probabilities of the true \textit{start} and \textit{end} tags, using the predicted distributions:
\begin{equation}
    \mathcal{L}_{E}=-\frac{1}{N} \sum_{i=1}^{N}\left(\log P\left(y_{i}^{s t art_{-} ent}=\hat{y}_{i}^{s t art_{-} ent}\right)+\log P\left(y_{i}^{e n d_{-} ent}=\hat{y}_{i}^{e n d_{-} ent}\right)\right),
\end{equation}
where $\hat{y}$\textsubscript{$i$}\textsuperscript{\textit{start\_ent}} and $\hat{y}$\textsubscript{$i$}\textsuperscript{\textit{end\_ent}} are the true \textit{start} and \textit{end} tags (gold labels) of the $i$\textsuperscript{th} word in the sample $X$, respectively, and $N$ is the length of the sample $X$.


%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\subsubsection{HTER Extractor}

The \textit{HTER Extractor} consists of two submodules: \textit{\textbf{H}ead-\textbf{E}ntity \textbf{R}elation} (\textit{HER}) extractor and \textit{\textbf{T}ail-\textbf{E}ntity \textbf{R}elation} (\textit{TER}) extractor. For each given entity, e.g., \enquote{Paris}, it uses the \textit{TER} to identify \enquote{Paris} in the \textit{head} entity role and detect all the corresponding tail-entities and \textit{URLs}, such as (\textit{\enquote{\textbf{Paris}}}, $\hat{R}$\textsubscript{2}, \textit{\enquote{France}}), where $\hat{R}$\textsubscript{2}:\{\enquote{Capital\_of}, \enquote{Located\_in}, \enquote{Administrative\_division\_of}\}. At the same time, the HTER Extractor utilizes the \textit{HER} submodule to identify \enquote{Paris} in the \textit{tail} entity role and detect all the corresponding head-entities and \textit{URLs}, such as (\textit{\enquote{John Smiths}}, $\hat{R}$\textsubscript{1}, \textit{\enquote{\textbf{Paris}}}), where $\hat{R}$\textsubscript{1}:\{\enquote{Live\_in}, \enquote{Work\_in}\}.       


Specifically, from the output sequence \textbf{$H$} of the Encoding Layer, as an entity is often composed of multiple tokens, we create a span feature representation for the given entity. Following \citeA{ouchi2018}, for the entity with start and end positions: \textit{$j$} and \textit{$k$} ($j$ $\leq$ $k$), we obtain the entity representation vector as follows: 
\begin{gather}
    \mathbf{v}_{ent}=\left[\mathbf{h}_{j}+\mathbf{h}_{k} ; \mathbf{h}_{j}-\mathbf{h}_{k}\right], \\
    \overline{\mathbf{x}}_{i}=\left[\mathbf{h}_{i}; \mathbf{v}_{ent}\right],
\end{gather}
where $i$ refers to the position of the $i$\textsuperscript{th} word in the input sample.

Because the information of a given entity is crucial for extracting related triplets, we therefore concatenate each token vector in the output sequence \textbf{$H$} and the given entity representation $\mathbf{v}_{ent}$. We take $\overline{\mathbf{X}}=\left\{\overline{\mathbf{x}}_{1}, \overline{\mathbf{x}}_{2}, \cdots, \overline{\mathbf{x}}_{N}\right\}$ as the input to another BiLSTM layer, to fuse each $\mathbf{h}_{i}$ and $\mathbf{v}_{ent}$ in a single vector $\overline{\mathbf{h}}_{i}$:
\begin{equation}
    \overline{\mathbf{H}}= BiLSTM( \overline{\mathbf{X}}),
\end{equation}
where $\overline{\mathbf{H}}=\left\{\overline{\mathbf{h}}_{1}, \overline{\mathbf{h}}_{2}, \cdots, \overline{\mathbf{h}}_{N}\right\}$. Then, the sequence $\overline{\mathbf{H}}$ is used as the same input to both \textit{TER} and \textit{HER} submodules. The \textit{TER} submodule detects all the corresponding tail-entities and relations by directly decoding the sequence $\overline{\mathbf{H}}$. Specifically, it uses two identical multiclass classifiers to detect the start and end positions of the related tail-entities with the corresponding relation type. Thus, the detailed operations of the \textit{tail} entity tagging with the relation type on each token are described as follows:
\begin{gather}
    p_{i}^{s t a r t_{-} tail}=Softmax\left(\mathbf{W}_{s t a r t_{-} tail} \overline{\mathbf{h}}_{i}+\mathbf{b}_{s t a r t_{-} tail}\right), \\
    p_{i}^{end_{-} tail}=Softmax\left(\mathbf{W}_{end_{-} tail} \overline{\mathbf{h}}_{i}+\mathbf{b}_{end_{-} tail}\right),
\end{gather}
where $p_{i}^{s t a r t_{-} tail}$ and $p_{i}^{end_{-} tail}$ represent the probabilities of the relation labels for the $i$\textsuperscript{th} token, which are considered as the start and end positions of a \textit{tail} entity in the input sample, respectively. Additionally, $\overline{\textbf{h}}_{i}$ is the encoded representation, \textbf{W}$_{(.)}$ represents the trainable weight, and \textbf{b}$_{(.)}$ is the bias. 

Similarly, the \textit{HER} submodule utilizes two other identical multi-class classifiers to detect the start and end positions of the related head-entities with the corresponding relation type. 
Formally, the detailed operations of the \textit{head} tagging on each token are as follows:
\begin{gather}
    p_{i}^{s t a r t_{-} head}=Softmax\left(\mathbf{W}_{s t a r t_{-} head} \overline{\mathbf{h}}_{i}+\mathbf{b}_{s t a r t_{-} head}\right), \\
    p_{i}^{end_{-} head}=Softmax\left(\mathbf{W}_{end_{-} head} \overline{\mathbf{h}}_{i}+\mathbf{b}_{end_{-} head}\right).
\end{gather}
% loss function of two sub-modules.
Therefore, we have the loss function of each submodule in the \textit{HTER Extractor} as follows:
\begin{gather}
    \mathcal{L}_{TER}=-\frac{1}{N} \sum_{i=1}^{N}\left(\log P\left(y_{i}^{s t art_{-} tail}=\hat{y}_{i}^{s t art_{-} tail}\right)+\log P\left(y_{i}^{e n d_{-} tail}=\hat{y}_{i}^{e n d_{-} tail}\right)\right), \\
    \mathcal{L}_{HER}=-\frac{1}{N} \sum_{i=1}^{N}\left(\log P\left(y_{i}^{s t art_{-} head}=\hat{y}_{i}^{s t art_{-} head}\right)+\log P\left(y_{i}^{e n d_{-} head}=\hat{y}_{i}^{e n d_{-} head}\right)\right),
\end{gather}
where $N$ is the length of the input sample; $\hat{y}$\textsubscript{$i$}\textsuperscript{\textit{start\_tail}} and $\hat{y}$\textsubscript{$i$}\textsuperscript{\textit{end\_tail}} in Eq. $13$  are the true \textit{start} and \textit{end} relation tags of the $i$\textsuperscript{th} word for annotating the related tail entities, respectively, and $\hat{y}$\textsubscript{$i$}\textsuperscript{\textit{start\_head}} and $\hat{y}$\textsubscript{$i$}\textsuperscript{\textit{end\_head}} in Eq. $14$ are the true \textit{start} and \textit{end} relation tags of the $i$\textsuperscript{th} word for annotating the related head entities. 


%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\subsubsection{Joint Learning}

To boost the interaction between the \textit{Entity Extractor} and the \textit{HTER Extractor}, we combine their loss functions to form the entire loss objective of our model:
\begin{equation}
    \mathcal{L}(\theta)=\alpha*\mathcal{L}_{E}+(\mathcal{L}_{TER}+\mathcal{L}_{HER}),
\end{equation}
where the hyper-parameter $\alpha$ is fine-tuned in the range ($0$, $1$]. Then, we train the model by minimizing $\mathcal{L}(\theta)$ through the Adam stochastic gradient descent \cite{kingma2014adam} over shuffled mini-batches. Note that the \textit{HTER Extractor} is trained with the gold set \textit{URLs}, which are created using Algorithm~\ref{alg:createS}, instead of with the set of original relations.  


%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\subsubsection{Inference}

In the testing phase, the triplets can be easily inferred on the basis of the two modules. Specifically, for each input sample, we first extract the entities by using the \textit{Entity Extractor} module. Note that entities extracted by this module will not be considered as an additional constraint on the output of the other module. Then, for each detected entity, we utilize the \textit{HTER Extractor} to consider it in the \textit{head}/\textit{tail} roles and extract all the relational triplets involving this entity. For example, from the input sample in Figure~\ref{fig:NetworkStructure}, the \textit{Entity Extractor} is expected to detect the entities: \enquote{John Smiths}, \enquote{Paris}, and \enquote{France}. Then, for each extracted entity, e.g., \enquote{Paris}, the \textit{HTER Extractor} uses its two submodules (\textit{HER} and \textit{TER}) to extract all relational triplets containing \enquote{Paris}. Specifically, the \textit{TER} submodule identifies \enquote{Paris} in the \textit{head} role and extracts: (\enquote{\textbf{\textit{Paris}}}, $\hat{R}$\textsubscript{2}, \enquote{\textit{France}}). Meanwhile, the \textit{HER} submodule considers \enquote{Paris} in the \textit{tail} role and extracts: (\enquote{\textit{John Smiths}}, $\hat{R}$\textsubscript{1}, \enquote{\textbf{\textit{Paris}}}).


Note that the relation types in the triplets extracted by both the \textit{HER} and \textit{TER} submodules belong to the set \textit{URLs} because they are trained with this set. Thus, we need to transform these relations into the original relations by breaking them down into the original relations and creating the corresponding triplets. In the above example, for the given entity \enquote{\textit{Paris}}, the \textit{TER} submodule extracts the triplets \{(\enquote{\textbf{\textit{Paris}}}, $\hat{R}$\textsubscript{2}, \enquote{\textit{France}})\}. In addition, as shown in Figure~\ref{fig:SchemeTagging},  $\hat{R}$\textsubscript{2} represents for the subset \{\enquote{Capital\_of}, \enquote{Located\_in}, \enquote{Administrative\_division\_of}\}. Therefore, we obtain the final triplets from the \textit{TER} submodule for \enquote{\textit{Paris}}: \{(\textit{\enquote{\textbf{Paris}}}, \enquote{Capital\_of}, \enquote{\textit{France}}), (\textit{\enquote{\textbf{Paris}}}, \enquote{Located\_in}, \enquote{\textit{France}}), (\textit{\enquote{\textbf{Paris}}}, \enquote{Administrative\_division\_of}, \enquote{\textit{France}})\}. Similarly, we also obtain the triplets from the \textit{HER} submodule for \enquote{\textit{Paris}}: \{(\enquote{\textit{John Smiths}}, \enquote{Live\_in}, \enquote{\textbf{\textit{Paris}}}), (\enquote{\textit{John Smiths}}, \enquote{Work\_in}, \enquote{\textbf{\textit{Paris}}})\}. Finally, we combine the outputs from both submodules by keeping all the extracted triplets, but removing the duplicates (if any) for each input sample. 


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

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\subsection{Experimental Settings}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\subsubsection{Datasets and Evaluation Metrics} 

Following the previous work \cite{dai2019joint,yubowendecomposition2020}, we evaluated our approach on two widely used datasets: \textbf{NYT} \cite{riedel2010modeling} and \textbf{WebNLG} \cite{gardent-etal-2017-creating}. To further study the capability of our approach to extract overlapping and multiple relations, we also split the test set into three categories: \textit{Normal}, \textit{EPO}, and \textit{SEO}. A sample belongs to \textit{Normal} if none of its triplets overlaps, whereas it belongs to \textit{EPO} if some of its triplets share the same entity pair. In addition, a sample belongs to \textit{SEO} if some of its triplets share only one common entity. The statistics of the two datasets are given in Table~\ref{tab:StatisticsTwoDatasets}.

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%% table 2
\begin{table}[b]
\input{02table02.tex}
\hangcaption{%
Statistics of the two datasets. The number of samples in the test set that belongs to each category, is also reported. Note that a sample can belong to both the \textit{SEO} and \textit{EPO} categories. In addition, the relation number of the WebNLG was miswritten as $246$, as in \protect\cite{fu-etal-2019-graphrel,yubowendecomposition2020}, which is the total number of relations in the original WebNLG dataset instead of the number of the subsets they used. We recounted and provided the correct number.} 
\label{tab:StatisticsTwoDatasets}
\end{table}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

We report the standard micro precision, recall, and F1-score, as in line with recent studies. Specifically, a predicted triplet is correct if and only if its relation type and its two corresponding entities are all the same as those in the gold standard annotation. The results of the test set were reported when the development set achieved the best result.


%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\subsubsection{Implementation Details} 

We implemented the neural networks using the PyTorch library.\footnote{%
PyTorch is an open-source software library for machine intelligence: \url{https://pytorch.org/}} Batch padding was applied to pad the lengths of all tokens to make them equal to the maximum length in each batch. The mini-batch training size was set to $64$, which was selected from the set: [$32$, $50$, $64$]. 

We used the $300$-dimensional GloVe \cite{pennington-etal-2014-glove} to initialize the word embeddings. Each word representation was concatenated by three parts: pre-trained GloVe embedding, character-based word representation by running a CNN on the character sequence of the word, and POS embedding. The POS, character, and position embeddings were randomly initialized with $30$ dimensions (selected from the set: [$30$, $40$, $50$]). The filter size of the CNN was set to $3$ from the set: [$3$, $4$, $5$], and the number of filters was $50$ from the set: [$30$, $40$, $50$]. Thus, the representation of each word had a dimensionality of $380$ (as the input of the BiLSTM layer). For the BiLSTM layer, the hidden vector size was set to $200$ from the set: [$150$, $200$]. The \textit{Adam} optimizer \cite{kingma2014adam} with a learning rate $0.0001$ from the set: [$0.0001$, $0.00001$] was employed for training. Dropout was applied to word embeddings and hidden states at a rate of $0.4$ from the set: [$0.3$, $0.4$]. We also set the gradient clip-norm to $5$ to prevent the gradient explosion problem. The threshold $\gamma$ was set to $11$ for the NYT training set and to $7$ for the WebNLG training set. In addition, the value of $\alpha$ in the final loss function (Eq. $15$) was set to $0.3$ on the NYT and to $0.2$ on the WebNLG, where $\alpha$ was in the range ($0$, $1$]. We trained the model for $100$ epochs on both datasets. Hyperparameters were tuned on the development set. All experiments were run on a Tesla V100 graphics card in an Ubuntu-based computer system.


%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\subsection{Experimental Results and Analyses}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\subsubsection{Comparison Models}

For comparison, we employed the following models as baselines:
\begin{itemize}
	\item \textbf{NovelTagging} \cite{zheng-etal-2017-joint}: The first model to introduce a novel tagging scheme that transforms the joint extraction task into a sequence labeling problem.
	\item \textbf{MultiDecoder} \cite{zeng-etal-2018-extracting}: A seq2seq model with a copy mechanism that converts the joint extraction task to a sequence-to-sequence problem.
	\item \textbf{MultiHead} \cite{Bekoulis2018}: A joint neural model that performs entity recognition and relation extraction simultaneously.
	\item \textbf{GraphRel} \cite{fu-etal-2019-graphrel}: An end-to-end relation extraction model that uses GCNs to jointly learn named entities and relations.  

	\item \textbf{OrderRL} \cite{zeng-etal-2019-learning}: A sequence-to-sequence model with reinforcement learning that takes the extraction order into consideration.

	\item \textbf{ETL-Span} \cite{yubowendecomposition2020}: A sequence labeling framework based on a novel decomposition strategy that has achieved a notable performance; however, its decomposition strategy still cannot solve the EPO problem, as the authors stated.
	
\end{itemize}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%% table 3
\begin{table}[b]
\input{02table03.tex}
\caption{Main results of the performances of the compared models on the NYT and WebNLG.} 
\label{tab:BaselinesPerformance}
\end{table}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%


%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\subsubsection{Main Results} 

Table~\ref{tab:BaselinesPerformance} shows the results of our models against those of other baseline methods on both the NYT and WebNLG datasets. First, ETL-Span \cite{yubowendecomposition2020} with a decomposition strategy significantly outperformed the previous works by a wide margin. However, because this approach cannot solve the EPO problem as \citeA{yubowendecomposition2020} stated, further improvement of the system performance is hindered. Meanwhile, our model framework with a new decomposition strategy overcomes the existing problems of the model of \citeA{yubowendecomposition2020} and substantially boosts the system performance. Specifically, our approach improved the F1-score by $7.1$ on the NYT and by $2.9$ on the WebNLG, compared with the results of \citeA{yubowendecomposition2020}.


%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\subsubsection{Analysis of Our Decomposition Strategy} 

To gain more insight into the improvement of our decomposition strategy in our model (in Figure~\ref{fig:NetworkStructure}), we conducted further experiments, as reported in Table~\ref{tab:AnalysisAblationPerformance}. We also reproduced the results of ETL-Span \cite{yubowendecomposition2020}.

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%% table 4
\begin{table}[t]
\input{02table04.tex}
\hangcaption{Analysis of the performance of our framework on the test sets. The \textsuperscript{$\star$} marks the results that we reproduced. The \textit{URLs} are the set of \enquote{\textit{unified relation labels}} created using Algorithm $1$.} 
\label{tab:AnalysisAblationPerformance}
\end{table}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\textbf{First}, for case (\textbf{a}) in Table~\ref{tab:AnalysisAblationPerformance}, we considered our model without using the set \textit{URLs}. Specifically, we used multiclass classifiers on the set of original relations in the two submodules of the module \textit{HTER Extractor}. Compared with the model of \citeA{yubowendecomposition2020}, our model achieved gains of $1.1$ and $2.1$ in the $F1$-score on the NYT and WebNLG, respectively, using only the set of original relations. The model of \cite{yubowendecomposition2020} is too strict in regard to the order it obtains the elements of each triplet, as it always detects the head entities first and then extracts the corresponding tail entities and relations for the given HE. Consequently, it will miss all triplets related to an omitted valid HE. Meanwhile, it is not always easy to extract head entities first for all relations, as in some cases it might be easier to detect the tail entities first before the head entities. Thus, our flexible approach overcomes this problem and significantly improves the recall. Note that our approach achieved a better improvement in the $F1$-score on the WebNLG than that on the NYT. One possible reason is that, because the number of relation types in the WebNLG ($216$ types) is much larger than that in the NYT (only $24$ types), it increased the probability of relations where it was easier to detect the tail entities first before the head entities.


\textbf{Second}, as our multiclass model in case (\textbf{a}) cannot solve the EPO problem, we considered the first solution. Specifically, in case (\textbf{b}), we used multilabel classifiers, instead of multiclass classifiers, on the set of original relations in the two submodules of the \textit{HTER Extractor}. With this solution, each tagging position in the \textit{HTER Extractor} can hold multiple original relation types. Thus, we can extract multiple relations (if any) of the same entity pair. By doing this, compared to case (\textbf{a}), our system achieved a gain of $3.5$ in the $F1$-score on the NYT, whereas it showed a decreased of $1.8$ in the $F1$-score on the WebNLG. We observed that the main difference between the NYT and WebNLG might have led to this result. Specifically, the number of original relations in the WebNLG ($216$ types) is much larger than that in the NYT ($24$ types), although the maximum number of relations of the same entity pair is $3$ on both of these training sets. Consequently, the sparse label problem of the multilabel classification on the same entity pair is more severe in the WebNLG than in the NYT. Therefore, it considerably affected the system performance on the WebNLG. Meanwhile, although this problem is less severe in the NYT than in the WebNLG, it also hinders the further improvement of the system performance.


\textbf{Finally}, as our model suffers from the sparse label problem for multilabel classification of the same entity pair in case (\textbf{b}), we considered the second solution to solve the EPO problem. Specifically, in case (\textbf{c}), because a multiclass classification can alleviate the sparse label problem, we used multiclass classifiers with the \textit{URLs} created using Algorithm~\ref{alg:createS} in the \textit{HTER Extractor}. Interestingly, by using this simple solution, we achieved the highest system performance for both the NYT and WebNLG. Compared with case (\textbf{a}), the solution increased the $F1$-score by $6.2$ and $0.9$ on the NYT and WebNLG, respectively. It is worth mentioning that the improvement gain on the NYT was significantly larger than that on the WebNLG. One possible reason is that the EPO problem on the NYT is more serious than that on the WebNLG. 
In Table~\ref{tab:StatisticsTwoDatasets}, the number of samples belonging to the EPO category in the NYT test set is $978$ ($19.6$\%), whereas it is only $26$ ($3.7$\%) in the WebNLG test set.



Compared with the ETL-Span model by \citeA{yubowendecomposition2020}, in Table~\ref{tab:AnalysisAblationPerformance}, our best model (case (\textbf{c})) achieved a significant improvement of the system performance with an increase in the $F1$-score by $7.3$ and $3.0$ on the NYT and WebNLG test sets, respectively. In addition, on the NYT test set, compared with the ETL-Span model, although our best model boosted the recall significantly by $16$\%, the precision decreased by $2$\%. One possible reason for the decrease in the precision is that our model tries to train all three parts (i.e., \textit{Entity Extractor} and the two submodules: \textit{TER} and \textit{HER}) effectively at the same time, which might be more challenging than training only two elements simultaneously (i.e., the \textit{HE Extractor} and \textit{TER Extractor}), as in the ETL-Span model of \citeA{yubowendecomposition2020}. In future work, we plan to design model architectures more effectively, to obtain a satisfactory level of not only the recall measure but also the precision measure, thereby further improving the $F1$-score.


%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\subsubsection{Analysis of Different Sample Types}

To verify the capability of our model to extract multiple triplets, we followed the procedure in \cite{zeng-etal-2018-extracting,fu-etal-2019-graphrel} and conducted further experiments on the NYT test set. Specifically, we first split the samples in this test set into three categories: \textit{Normal}, \textit{EPO}, and \textit{SEO}, and then we investigated the performance of each category.

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%% fig. 4
\begin{figure}[t]
\begin{center}
\includegraphics{28-4ia2f4.pdf}
\end{center}
\hangcaption{F1-score of extracting relational triplets from samples in three different categories on the NYT test set.}
\label{fig:F1scoreCategory}
\end{figure}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

The results are shown in Figure~\ref{fig:F1scoreCategory}. It can be seen from the figure that the performance improvement in our model mainly comes from its ability to deal with the EPO and SEO problems more effectively. Compared with the model of \citeA{yubowendecomposition2020}, our model achieved competitive performance in all the three categories. In addition, we paid special attention to the performance differences between our approach and that of \citeA{yubowendecomposition2020}. Notably, on the NYT test set, our approach boosted the $F1$-score significantly in the EPO problem by $27.0$, whereas that of \cite{yubowendecomposition2020} cannot solve this problem. In addition, as the strategy of \citeA{yubowendecomposition2020} strictly constrains the detection of the entities to the head first, if it fails to find a valid HE, it will then miss the related triplets. It will be more serious if this HE attends many different triplets in the \textit{head} entity role (a case of SEO). Therefore, our flexible approach deals with this issue and substantially improves the $F1$-score by $3.4$ in the SEO problem.


We also compared the ability of the models to extract multiple triplets in a sample. Specifically, we divided the samples of the NYT test set into five categories, where each category contains samples that have $1$, $2$, $3$, $4$, or $\geq$ $5$ triplets, respectively. The results are shown in Figure~\ref{fig:F1scoreNUmSents}. It can be seen from the figure that our approach achieved a significant improvement in extracting multiple triplets compared with the other models. In particular, our model showed a more stable performance when the number of triplets in the sample increased. These results show that our approach is effective in dealing with the multi-relation extraction task. 

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%% fig. 5
\begin{figure}[t]
\begin{center}
\includegraphics{28-4ia2f5.pdf}
\end{center}
\hangcaption{F1-scores obtained after extracting relational triplets from samples with different numbers of triplets on the NYT test set.}
\label{fig:F1scoreNUmSents}
\end{figure}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%


%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\subsection{Case Study}

To gain more insight into the effectiveness of our model in overcoming the existing disadvantages in the approach of \citeA{yubowendecomposition2020}, we analyzed the prediction outputs of both models on a few samples of the NYT and WebNLG test sets and these are shown in Tables~\ref{casestudynyt} and ~\ref{casestudywebnlg}, respectively.  

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%% table 5
\begin{table}[t]
\input{02table05.tex}
\caption{Prediction outputs on two samples from the NYT test set.}
\label{casestudynyt}
\end{table}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%% table 6
\begin{table}[p]
\input{02table06.tex}
\caption{Prediction outputs on a few samples from the WebNLG test set.}
\label{casestudywebnlg}
\end{table}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%


%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\subsubsection{Dealing With the EPO Problem}

In Table~\ref{casestudynyt}, we show two examples from the NYT test set and compare the predicted triplets of the model of \citeA{yubowendecomposition2020} with those of our model.

As mentioned earlier, the model of \citeA{yubowendecomposition2020} cannot solve the EPO problem. For any entity pairs, their model only predicts a single relation, although an entity pair can have multiple relations. For instance, in Sample $1$, the ordered entity pair (\enquote{\textit{Somalia}}, \enquote{\textit{Mogadishu}}) has two relations: \enquote{/location/country/capital} and  \enquote{/location/location/contains}. However, the model of \citeA{yubowendecomposition2020} extracted only a single relation and created the triplet: (\enquote{\textit{Somalia}}, \enquote{/location/location/contains}, \enquote{\textit{Mogadishu}}). Similarly, in Sample $2$, although the ordered entity pair (\enquote{\textit{Ethiopia}}, \enquote{\textit{Addis Ababa}}) has three relations: \enquote{/location/country/capital}, \enquote{/location/country/administrative\_divisions}, and  \enquote{/location/location/contains}, their model predicted only the relation \enquote{/location/location/contains} for this pair. Thus, the more serious the EPO problem is, the more degraded the system performance becomes. Meanwhile, our model overcomes this disadvantage and effectively solves the EPO problem. For both samples above, our model fully detected all possible relations for the pair (\enquote{\textit{Somalia}}, \enquote{\textit{Mogadishu}}) in Sample $1$ and the pair (\enquote{\textit{Ethiopia}}, \enquote{\textit{Addis Ababa}}) in Sample $2$.



%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\subsubsection{Effect of the \enquote{\textit{Exhaustive Search}} Strategy}

As shown in Figure~\ref{fig:NetworkStructure}, our model uses the \textit{Entity Extractor} to detect all entities first. Then, for each detected entity, the \textit{HTER Extractor} utilizes its two submodules to identify the entity in each \textit{head}/\textit{tail} role and extracts all the corresponding \textit{tail entities}/\textit{head entities} and relations. 
The final output of our model is always obtained by combining the results of the two submodules without any duplicate triplets. In essence, this approach can be considered as an \enquote{\textit{exhaustive search}} strategy that aims to increase the chances of extracting a valid triplet that may be overlooked by the approach of \citeA{yubowendecomposition2020}. Therefore, in Table~\ref{casestudywebnlg}, we compare the prediction outputs of both approaches on three samples from the WebNLG test set.     

First, in Sample $3$, the \textit{HE Extractor} in the model of \citeA{yubowendecomposition2020} missed the HE \enquote{Athens International Airport}, thereby overlooking the valid triplet: (\enquote{\textit{Athens International Airport}}, \enquote{cityServed}, \enquote{\textit{Athens}}) in the ground truth. Meanwhile, in our model, the entity \enquote{\textit{Athens International Airport}} was detected by the \textit{Entity Extractor}. Then, the \textit{TER+URLs} submodule of the \textit{HTER Extractor} identified this entity in the \textit{head} role and extracted the triplet (\enquote{\textit{Athens International Airport}}, \enquote{cityServed}, \enquote{\textit{Athens}}). Additionally, we compared the outputs of the \textit{HER+URLs} and \textit{TER+URLs} submodules in our model. Although two triplets, namely, (\enquote{\textit{Athens}}, \enquote{country},  \enquote{\textit{Greece}}) and (\enquote{\textit{Greece}}, \enquote{leaderName}, \enquote{\textit{Alexis Tsipras}}), were easily obtained by the two submodules, the \textit{HER+URLs} submodule failed to extract the valid triplet: (\enquote{\textit{Athens International Airport}}, \enquote{cityServed}, \enquote{\textit{Athens}}) when considering the entity \enquote{Athens} in the \textit{tail} role. Thus, in this example, the \textit{TER+URLs} submodule achieved a better result than that of the \textit{HER+URLs} submodule.


Second, in Sample $4$, the approach of \citeA{yubowendecomposition2020} omitted two valid triplets in the ground truth: (\enquote{\textit{The Secret Scripture}}, \enquote{publisher}, \enquote{\textit{Faber and Faber}}) and (\enquote{\textit{Ireland}}, \enquote{location}, \enquote{\textit{Europe}}), because the \textit{HE Extractor} missed two HEs: \enquote{The Secret Scripture} and \enquote{Ireland}. In our model, although the module \textit{Entity Extractor} could detect the entity \enquote{The Secret Scripture}, its \textit{TER+URLs} submodule failed to extract the triplet (\enquote{\textit{The Secret Scripture}}, \enquote{publisher}, \enquote{\textit{Faber and Faber}}) when considering \enquote{The Secret Scripture} in the \textit{head} role. Meanwhile, thanks to the \textit{HER+URLs} submodule, it extracted this missed triplet by considering \enquote{Faber and Faber} in the \textit{tail} role and detecting the corresponding HE \enquote{The Secret Scripture} with the relation type \enquote{publisher}. Based on the outputs of the two submodules, it is clear that the \textit{HER+URLs} submodule yielded a better result for this sample than that of the \textit{TER+URLs} submodule.


Finally, in Sample $5$, the model of \citeA{yubowendecomposition2020} obtained only two valid triplets in the ground truth: (\enquote{\textit{Dublin}}, \enquote{country},  \enquote{\textit{Republic of Ireland}}) and (\enquote{\textit{Dublin}}, \enquote{leaderName}, \enquote{\textit{Cr\'{\i}ona N\'{\i} Dh\'{a}laigh}}). The \textit{HE Extractor} of their model missed the HE \enquote{3Arena}, thereby overlooking the triplets: (\enquote{\textit{3Arena}}, \enquote{location}, \enquote{\textit{Dublin}}) and (\enquote{\textit{3Arena}}, \enquote{owner}, \enquote{\textit{Live Nation Entertainment}}). In our model, the \textit{Entity Extractor} also missed the entity: \enquote{3Arena}. Consequently, the \textit{TER+URLs} submodule also overlooked the triplets: (\enquote{\textit{3Arena}}, \enquote{location}, \enquote{\textit{Dublin}}) and (\enquote{\textit{3Arena}}, \enquote{owner}, \enquote{\textit{Live Nation Entertainment}}). Meanwhile, the \textit{HER+URLs} submodule identified the entity \enquote{Dublin} in the \textit{tail} role to extract the triplet (\enquote{\textit{3Arena}}, \enquote{location}, \enquote{\textit{Dublin}}) and also identified the entity \enquote{Live Nation Entertainment} in the \textit{tail} role to extract the triplet (\enquote{\textit{3Arena}}, \enquote{owner}, \enquote{\textit{Live Nation Entertainment}}). However, the \textit{HER+URLs} submodule missed the valid triplet (\enquote{\textit{Dublin}}, \enquote{leaderName},  \enquote{\textit{Cr\'{\i}ona N\'{\i} Dh\'{a}laigh}}), whereas this triplet was detected by the \textit{TER+URLs} submodule. Our model obtained the final result by combining the outputs of the two submodules. 



We further consider the system performance of the predicted outputs of the (\textit{HER+URLs} and \textit{TER+URLs}) submodules of the \textit{HTER Extractor} of our model on the entire WebNLG test set in Table~\ref{analysis:module:webnlg}. We can see that the number of predicted triplets by the \textit{HER+URLs} submodule is 1,510, whereas this number is 1,530 for the \textit{TER+URLs} submodule. In addition, these two submodules share 1,368 common predicted triplets. Thus, the overlap percentage of the output of the \textit{HER+URLs} submodule is $90.6$, whereas this rate is $89.4$ for the output of the \textit{TER+URLs} submodule. In Table~\ref{analysis:module:webnlg}, our model achieved the best performance when combining the predicted outputs of the two submodules.


On the basis of the results of the analysis of the examples in Table~\ref{casestudywebnlg} and of the performances of the submodules of our model in Table~\ref{analysis:module:webnlg}, we conclude that the \enquote{\textit{exhaustive search}} strategy of our model is effective in solving the entity and relation extraction task.

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%% table 7
\begin{table}[b]
\input{02table07.tex}
\hangcaption{Results of the performance analysis of the two submodules of our model on the WebNLG test set. The set \textit{URLs} was created using Algorithm $1$.}
\label{analysis:module:webnlg}
\end{table}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%


%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\subsection{Impact of Using Pre-trained Language Models}

For a fair comparison, like in \citeA{yubowendecomposition2020}, we did not exploit the advantages of using pretrained language models. In reality, a well-known pretrained language model named BERT was first proposed by \citeA{2019bert}. It has been widely applied to various NLP downstream tasks and has achieved considerable success. For the entity and relation extraction task, \citeA{HANG2021114853} presented a BERT-based model named BERT-JEORE and obtained superior performance. Therefore, we further investigated the impact of using pretrained language models when they were used in our model. 

Specifically, for our model in Figure~\ref{fig:NetworkStructure}, we replaced only the first BiLSTM encoder with a pretrained BERT-Base encoder to extract the representations of the original words from the input sample. Note that the BERT model first uses its tokenizer to split each original word into tokens (if necessary) and then outputs the vectors of these tokens. Thus, we obtained the representation of each original word by averaging its start token vector and its end token vector. In Table~\ref{tab:BertResults}, we report the system performance of our model on the NYT and WebNLG datasets.

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%% table 8
\begin{table}[t]
\input{02table08.tex}
\caption{Impact of using a pretrained BERT encoder in our model.} 
\label{tab:BertResults}
\end{table}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

Clearly, our model showed further performance boost on both the NYT and WebNLG datasets when employing a pretrained BERT encoder, significantly improving the $F1$-score by $6.5$ on the NYT dataset. Compared to a recent model based on BERT (BERT-JEORE) by \citeA{HANG2021114853} for the entity and relation extraction task, our BERT-based model achieved a better performance on the NYT and WebNLG datasets, with gains of $5.1$ and $1.6$ in the $F1$-score, respectively. In addition, it is interesting to note that, even without using the BERT encoder, our model still outperformed the recent model on the WebNLG test set. This indicates that our approach with a new decomposition strategy is simple but very effective in solving the entity and relation extraction task.  


%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\section{Related Works}

Researchers have made great efforts to extract relational triplets from unstructured text, which can be directly used for automatic knowledge graph construction. Early works \cite{zelenko2003kernel,zhou-etal-2005-exploring,chan-roth-2011-exploiting} regarded the joint extraction task in a pipeline manner. They extracted relational triplets in two isolated steps: ($1$) first by running the NER on the input sample to recognize all entities, and ($2$) then by running the RC on all pairs of the extracted entities. Although these pipeline methods are quite simple, they usually suffer from the error propagation problem and ignore the relevance between the two steps.    


To ease the two issues above, subsequent works attempted to build joint learning models that learn entities and relations simultaneously in a single manner. They can be divided into two main approaches: feature-based models \cite{yu-lam-2010-jointly,li-ji-2014-incremental,miwa2014modeling,ren2017cotype} and neural network-based models \cite{gupta-etal-2016-table,katiyar-cardie-2017-going,zheng-etal-2017-joint,zeng-etal-2018-extracting,fu-etal-2019-graphrel,yubowendecomposition2020}. The former rely heavily on feature engineering and require intensive manual efforts, whereas the latter are mainly based on neural network architectures. \citeA{zheng-etal-2017-joint} introduced a unified tagging scheme and converted the joint entity and relation extraction task to an end-to-end sequence tagging problem. This method can directly model relational triplets as a whole at the triplet level because the unified tagging scheme already integrates the information of both entities and relations. However, most previous studies ignored the problem of overlapping relational triplets. \citeA{zeng-etal-2018-extracting} presented three patterns of overlapping triplets and made an effort to address the problem via a sequence-to-sequence model with a copy mechanism. Subsequently, \citeA{fu-etal-2019-graphrel} also focused on this problem and proposed a GCN-based method to address it. Recently, \citeA{yubowendecomposition2020} introduced a novel decomposition strategy that decomposes the task into \textit{HE} and \textit{TER} extractions, where the \textit{HE} extractor detects head entities and the \textit{TER} extractor identifies the corresponding tail entity and relation for each given HE. Although this approach significantly outperforms previous works, it still cannot solve the EPO problem as \citeA{yubowendecomposition2020} stated in their work. 

On a related note, pretrained language models have also been exploited for entity and relation extraction, thereby utilizing prior knowledge and achieving superior results. \citeA{zhao2020asking} adopted BERT \cite{2019bert} as the machine reading comprehension model to solve the joint entity and relation extraction. \citeA{HANG2021114853} proposed BERT-JEORE, an end-to-end neural network model that is based on BERT for the joint extraction of entities and overlapping relations. They used source-target BERT to generate an entity label for each token in the sample and utilized an overlapping relation extraction model to create an unlimited number of relational triplets.        


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

This paper proposes a new decomposition strategy along with a corresponding model framework for the joint entity and relation extraction task. Our approach mainly focuses on solving the overlapping triplet problem, one of the biggest challenges of this task, as only a few existing works can tackle this problem effectively. Our model uses a module to extract all the relevant entities, and for each extracted entity, another module is utilized to consider its \textit{head/tail} entity roles and extract all the related triplets. In addition, the use of \textit{URLs} helps to sufficiently deal with the sparse label problem of relation types in the same entity pair (e.g., EPO cases), which can be prevalent in this task. Experimental results on the two widely used datasets (NYT and WebNLG) showed that our model achieved a notable performance compared with a recent work \cite{HANG2021114853}. The results of further analysis experiments showed the effectiveness of our approach in handling overlapping and multiple triplet extraction scenarios.

% Applications and Future Work
Our proposed methodology has considerable potential for practical NLP applications such as information extraction, knowledge base population, and question answering. Moreover, the idea of using \textit{URLs} may be relevant and promising for multilabel classification problems in general, not just for a specific task such as the entity and relation extraction task. In future work, we plan to apply this idea to the text classification task. Additionally, we also would like to introduce other methods for solving the overlapping triplet problem more effectively, such as considering how to change the weight of a label depending on whether it is a subset of the true label, and integrating available knowledge bases of entities into current models for boosting the system performance.   




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


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

\bioauthor[:]{Van-Hien Tran}{
Van-Hien Tran received the B.E. degree in information technology from the University of Engineering and Technology, Vietnam National University (VNU), Vietnam, in 2014, and the M.E. degree from the Nara Institute of Science and Technology (NAIST), Japan, in 2019, where he is currently pursuing the Ph.D. degree. His research interests include machine learning and natural language processing, in particular on information extraction.
}


\bioauthor[:]{Van-Thuy Phi}{
Van-Thuy Phi is currently a postdoctoral researcher at the Nara Institute of Science and Technology (NAIST). Previously, he received the M.Sc. degree in 2016, and the Ph.D. degree in 2019, both in Information Science from NAIST. His research interests lie at the intersection of Natural Language Processing and Computer Vision, in particular on areas relating to information extraction from texts or images, image segmentation and deep learning.
}


\bioauthor[:]{Akihiko Kato}{
Akihiko Kato received the Ph.D. degree in Engineering from Nara Institute of Science and Technology (NAIST), in 2019. He is currently a postdoctoral researcher in Graduate School of Information Science, NAIST. His research interests include information extraction, knowledge base completion, and syntactic/semantic parsing.
}


\bioauthor[:]{Hiroyuki Shindo}{
Hiroyuki Shindo received the B.E. and
M.E. degrees from Waseda University, Japan,
in 2007 and 2009, respectively, and the Ph.D.
degree in engineering from the Nara Institute of Science and Technology (NAIST), Ikoma, Japan, in 2013. From 2009 to 2014, he was a Researcher with NTT Communication Science Laboratories. He is currently an Assistant Professor with the Graduate School of Information Science, NAIST. His research interests include machine learning and computational linguistics.
}


\bioauthor[:]{Taro Watanabe}{
Taro Watanabe received the B.E. and M.E. degrees in information science from Kyoto University, Kyoto, Japan in 1994 and 1997, respectively, and obtained the Master of Science degree in language and information technologies from the School of Computer Science, Carnegie Mellon University in 2000.
In 2004, he received the 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 Nara Institute of Science and Technology starting from 2020.
His research interests include natural language processing, machine learning and machine translation.
}

\bioauthor[:]{Yuji Matsumoto}{
Yuji Matsumoto is currently a team leader at RIKEN Center for Advanced
Intelligence Project (AIP).  He received his M.S. and Ph.D. degrees in
information science from Kyoto University in 1979 and in 1990, respectively.
He joined Machine Inference Section of Electrotechnical Laboratory in
1979.  He has been an academic visitor at Imperial College
of Science and Technology, the deputy chief of First Laboratory at
ICOT, an associate professor at Kyoto University, and a professor at
Nara Institute of Science and Technology.  His main research interests
are natural language understanding and machine learning.  He is an ACL
fellow and a fellow of Information Processing Society of Japan.
}

\end{biography}


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




\end{document}

