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


%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%% author's definition
%%%%\usepackage{amsfonts}
%%%%\usepackage{amsmath}
%%%%\usepackage{amssymb}
%%%%\usepackage{amsthm}
\newcommand{\R}{\mathbb{R}}
\newcommand{\Y}{\mathcal{Y}}
\newcommand{\sota}[1]{\textbf{#1}}
\newcommand{\sotb}[1]{\underline{#1}}
\newcommand{\ve}[1]{\boldsymbol{#1}}
\newcommand{\ma}[1]{\mathbf{#1}}
\newcommand{\set}[1]{\{#1\}}
\newcommand{\abs}[1]{\vert #1 \vert}
\newcommand{\cat}[1]{\mathcal{#1}}
\newcommand{\argmax}{\operatorname*{\arg\max}}
\newcommand{\tg}[1]{\texttt{#1}}
\newcommand{\loss}{\mathcal{L}}
\newcommand{\chunk}[2]{\ve{h}^{#1}_{#2}}
\newcommand{\chunks}[1]{\mathcal{H}^{#1}}
\newcommand{\prob}[2]{p{\,(\ve{y}^{#1}{}^{#2} \mid \chunks{#2})}}
\newcommand{\poten}[2]{\operatorname{\phi}{(y_{t-1}^{#1 #2},y_t^{#1 #2}, \chunks{#2}_t)}}
\newcommand{\partition}{Z}
\newcommand{\tran}{A_{y_{t-1}^{l},y_{t}^{l}}}
\newcommand{\tgt}[2]{y_{#2}^{#1}}
\newcommand{\vtgt}[2]{\ve{v}_{\tgt{#1}{#2}}}
% end (math)
%%%%\usepackage{float}
%%%%\usepackage{multicol}
\usepackage{multirow}
\usepackage{booktabs}
%%%%\usepackage{caption} 
%%%%\captionsetup[table]{skip=10pt}
%%%%\usepackage{adjustbox}
\usepackage[inline]{enumitem}
\usepackage[ruled,vlined]{algorithm2e}
%%%%\usepackage{textcomp}
%%%%\usepackage{array}
%%%%\newcolumntype{P}[1]{>{\centering\arraybackslash}p{#1}}
%%%%\newcolumntype{M}[1]{>{\centering\arraybackslash}m{#1}}
\usepackage[group-separator={,},group-minimum-digits={3}]{siunitx}
\newcommand{\lb}[1]{\textbf{\textcolor{#1}{[}}}
\newcommand{\rb}[2]{\textbf{\textcolor{#1}{]\textsubscript{#2}}}}
\newcommand{\per}[1]{\lb{teal}#1\rb{teal}{PER}}
\newcommand{\gpe}[1]{\lb{red}#1\rb{red}{GPE}}
\newcommand{\org}[1]{\lb{magenta}#1\rb{magenta}{ORG}}
\newcommand{\fac}[1]{\lb{orange}#1\rb{orange}{FAC}}
\def\Vhrulefill{\leavevmode\leaders\hrule height 0.7ex depth \dimexpr0.4pt-0.7ex\hfill\kern0pt}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

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



\Volume{29}
\Number{1}
\Month{March}
\Year{2022}
%%%%\Issuetitle{Special Issue: XXXXXXXX}

\received{2021}{6}{1}
\revised{2021}{9}{1}
%%%%\rerevised{2006}{5}{6}
\accepted{2021}{10}{6}

\setcounter{page}{23}


%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\esubject{General Paper}
\etitle{Nested Named Entity Recognition via Explicitly Excluding the Influence of the Best Path}
\eauthor{Yiran Wang\affiref{nict} \and Hiroyuki Shindo\affiref{naist} \and Yuji Matsumoto\affiref{riken}\and Taro Watanabe \affiref{naist}} 
\eabstract{%
This paper presents a novel method for nested named entity recognition. As a layered method, our method extends the prior second-best path recognition method by explicitly excluding the influence of the best path. Our method maintains a set of hidden states at each time step and selectively leverages them to build a different potential function for recognition at each level. In addition, we demonstrate that recognizing innermost entities first results in better performance than the conventional outermost entities first scheme. We provide extensive experimental results on ACE2004, ACE2005, GENIA, and NNE datasets to show the effectiveness and efficiency of our proposed method.
}
\ekeywords{Nested Named Entity Recognition, Representation Learning}

\headauthor{Wang et al.}
\headtitle{Nested NER via Explicitly Excluding the Influence of the Best Path}

\affilabel{nict}{}{National Institute of Information and Communications Technology (NICT)}
\affilabel{naist}{}{Nara Institute of Science and Technology (NAIST)}
\affilabel{riken}{}{RIKEN Center for Advanced Intelligence Project (AIP)}


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

\maketitle

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

Named entity recognition (NER), as a key technique in natural language processing, aims at detecting entities and assigning semantic category labels to them. Early research \cite{DBLP:journals/corr/HuangXY15,ma-hovy-2016-end,lample-etal-2016-neural} proposed to employ deep learning methods and obtained significant performance improvements. However, most of them assume that the entities are not nested within other entities, so-called flat NER. Inherently, these methods do not work satisfactorily when nested entities exist. Figure~\ref{fig:example} displays an example of the nested NER task.

In practice, nested named entity recognition widely exists in many domains, especially in the science domain such as biomedical science \cite{wang-2009-annotating}. Correctly and efficiently detecting all existing nested entities is one of the most essential prerequisites of many downstream tasks, e.g., relation extraction, entity linking. Therefore, nested NER plays a critical role in natural language processing.

Recently, a large number of papers proposed novel methods \cite{fisher-vlachos-2019-merge,wang-etal-2020-pyramid} for the nested NER task. Among them, layered methods solve this task through multi-level sequential labeling, in which entities are divided into several levels according to the depth of entity nesting, and sequential labeling is performed repeatedly. 
As a special case of layered method, \citeA{shibuya-hovy-2020-nested} observed that short entities are always nested within long entities. Once the outer entity is detected, inner entities are considered as exiting on the span of the detected outer entity. Therefore, they search inner entities only on these spans instead of on the entire sentence. Besides, they found that searching the best path on the span of the detected entity only leads to the result that the known outer entity itself is detected again, because it exactly locates on the known best path. Thus, they instead detect inner entities via searching the second-best path through applying a conventional conditional random field (CRF) \cite{10.5555/645530.655813} with the same potential function.

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%% fig. 1
\begin{figure}[t]
\begin{center}
\includegraphics{29-1ia2f1.pdf}
\end{center}
\caption{An example of nested NER.}
\label{fig:example}
\end{figure}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

However, we claim that the inner entities are not likely to locate on the second-best path. Because \citeA{shibuya-hovy-2020-nested} keep using the same potential function, for any path in the remaining search space, the more labels it shares with the best path, the higher emission scores it will obtain. Therefore, searching on the second-best path is likely to obtain a path that has many overlaps with the best path, so it is improbable to be the path that contains these expected inner entities. For this reason, we claim that the influence of the best path still remains, even the best path is excluded. Therefore, forcing the inner entities to locate on the second-best path of the previous level, as what \citeA{shibuya-hovy-2020-nested} did, leads to contradictory optimization goals and eventually hurts performance.

In this paper, we use \textbf{a different potential function at each level} to solve this issue. We propose to achieve this by introducing an encoder that produces a set of hidden states at each time step. At each level, we select some hidden states for entity recognition, then remove those that interact with the best path labels before moving to the next level. In this way, the emission scores of these best path labels are utterly different from level to level. Thus, we can explicitly exclude the influence of the best path. Furthermore, we also propose three different selection strategies for fully leveraging information among hidden states.

Besides, \citeA{shibuya-hovy-2020-nested} proposed to recognize entities from outermost to inner. We empirically demonstrate that extracting \textbf{the innermost entities first} results in better performance. This may be because some long entities do not contain any inner entity, so using outermost-first encoding mixes these entities with other short entities at the same levels, therefore leading encoder representations to be dislocated. In this paper, we convert entities to the IOBES encoding scheme \cite{ramshaw-marcus-1995-text}, and apply a shared CRF level by level.

Our contributions are four-fold, \begin{enumerate*}[label=(\alph*)]
    \item we design a novel nested NER algorithm to explicitly exclude the influence of the best path through using a different potential function at each level,
    \item we propose three different selection strategies for fully utilizing information among hidden states, 
    \item we empirically demonstrate that recognizing entities from innermost to outer results in better performance, 
    \item and we provide extensive experimental results to demonstrate the effectiveness and efficiency of our proposed method on the standard benchmark datasets under diverse domains, i.e., ACE2004, ACE2005, GENIA, and NNE.
\end{enumerate*}


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

Existing NER algorithms commonly employ various neural networks to leverage more morphological and contextual information to improve performance. For example, to handle the out-of-vocabulary issue through introducing morphological features, \citeA{DBLP:journals/corr/HuangXY15} proposed to employ manual spelling feature, while \citeA{ma-hovy-2016-end} and \citeA{lample-etal-2016-neural} suggested introducing CNN and LSTM to build word representations from character-level. \citeA{zhang-etal-2018-sentence} and \citeA{chen2019grn} introduced global representation to enhance encoder capability of encoding contextual information. However, these algorithms are not designed for nested NER. Naturally, they cannot detect entities that are nested within other entities. In recent years, there are numerous papers proposed methods to solve the nested NER task.


%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\subsection{Layered Model} 

As a layered model, \citeA{ju-etal-2018-neural} dynamically update span-level representations for next layer recognition according to recognized inner entities. \citeA{fisher-vlachos-2019-merge} proposed a merge and label method to enhance this idea further. Recently, \citeA{luo-zhao-2020-bipartite} built two different graphs, one is the original token sequence, and the other is the tokens of recognized entities, to model the interaction among them. \citeA{shibuya-hovy-2020-nested} repeatedly detect inner entities on the spans of detected outer entities through searching the second-best path. \citeA{wang-etal-2020-pyramid} enumerates the spans of all possible $l$-grams to detect entities.
 

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\subsection{Region-based Model}

\citeA{lin-etal-2019-sequence} proposed an anchor-region
network to recognize nested entities by first detecting anchor words and entity boundaries and then classifying each detected span. Exhaustive models simply enumerate all possible spans and utilize a maximum entropy tagger \cite{4338398} and neural networks \cite{xu-etal-2017-local,sohrab-miwa-2018-deep,zheng-etal-2019-boundary} for classification. \citeA{luan-etal-2019-general} additionally aims to consider the relationship among entities and proposed a novel method to learn both entities and relations jointly.


%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\subsection{Hypergraph-based Model}

\citeA{lu-roth-2015-joint} proposed a hyper-graph structure in which edges are connected to multiple nodes to represent nested entities.
\citeA{muis-lu-2017-labeling} and \citeA{wang-lu-2018-neural} resolved spurious structures and ambiguous issue of hyper-graph structure. And \citeA{katiyar-cardie-2018-nested} proposed another kind of hyper-graph structure. 


%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\subsection{Parsing-based Model}

\citeA{finkel-manning-2009-nested} indicated that all these nested entities locate in some non-terminal nodes of the constituency parses of the original sentences. Thus they proposed to use a CRF-based constituency parser to obtain them. However, the cubic time complexity limits its applicability. 
\citeA{wang-etal-2018-neural-transition} instead proposed to use a transition-based constituency parser to build constituency forest incrementally, and its linear time complexity ensures it can handle longer sentences.


%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\section{Proposed Method}

Named entity recognition task aims to recognize entities in a given sequence $\set{x_t}_{t=1}^{n}$. For nested NER, some short entities may be nested within other relatively long entities, while there is no such case for flat NER. Existing algorithms solve flat NER by applying a sequential labeling method, which assigns each token with a label $y_t \in \Y$ to simultaneously determine the span and category of each entity and non-entity. We follow the previous layered method and extend this sequential labeling method with a multi-level encoding scheme to solve nested NER. This encoding scheme divides entities into several levels according to their depths and applies the sequential labeling method level by level to recognize all entities.


%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\subsection{Baselines}

Before introducing the details of our proposed method, we describe the algorithms of the most important two baselines of our work first.

As a special case of layered method, \citeA{shibuya-hovy-2020-nested} detect entities from level to level. They first detect outermost entities by applying a CRF and searching for the best path. After obtaining these long entities in the given sentence, they reduce their search space by searching only on the spans of detected entities. This is because short entities can only be nested within long entities. From the second level onwards, they instead search the second-best path because they demonstrate that searching the best path on the span of the detected entity only results in the known outer entity itself. They keep detecting inner entities with the same potential function until no special inner entities can be detected. Besides, they also designed a special algorithm to efficiently search the second-best path by excluding the known best path.

\citeA{wang-etal-2020-pyramid} proposed another layered method. They enumerate all $l$-gram spans by merging neighboring spans with a convolutional neural network iteratively. At each level, they first predict the entity category of each span according to its representation. Then, they merge representations of neighboring spans of $l$-gram to build the representations of all $(l+1)$-gram spans at the next level. In this way, this method reduces sentence length level by level, stacked in a pyramid shape, and this is the reason for its name.

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%% fig. 2
\begin{figure}[b]
\begin{center}
\includegraphics{29-1ia2f2.pdf}
\end{center}
\caption{An example of the outermost-first encoding scheme.}
\label{fig:out}
\end{figure}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%


%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\subsection{Encoding Schemes}

\citeA{shibuya-hovy-2020-nested} proposed to recognize the outermost entities first and recursively detect the nested inner entities. However, we find that detecting from innermost entities results in better performance. We take the sentence in Figure~\ref{fig:example} as an example to illustrate the details of these two encoding schemes. Figure~\ref{fig:out} shows the results of the outermost-first encoding scheme.

Labels \tg{B-}, \tg{I-}, \tg{E-} indicate the current word is the beginning, the intermediate, and the end of an entity, respectively. Label \tg{S-} means this is a single word entity, and label \tg{O} stands for non-entity word. For example, the outermost entity \emph{Former Hogwarts headmaster Albus Dumbledore} appears at the first level, while innermost entities \emph{Hogwarts} and \emph{headmaster} appear at the fourth level. Besides, We keep all examples to have the same number of levels by filling the remaining levels, which contains no entities, with label \tg{O}. For ACE2004, ACE2005, and NNE datasets, the maximal depth of entity nesting is 6. Thus, examples in these datasets have six levels, while for the GENIA dataset, the maximal level is only 4. However, we find that detecting from the innermost entities first, as in Figure~\ref{fig:in}, results in better performance.

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%% fig. 3
\begin{figure}[t]
\begin{center}
\includegraphics{29-1ia2f3.pdf}
\end{center}
\caption{An example of the innermost-first encoding scheme.}
\label{fig:in}
\end{figure}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

In this encoding scheme, innermost entities \emph{Hogwarts}, \emph{headmaster}, and \emph{Albus Dumbledore} appear at the first level. Note that the innermost-first encoding scheme is not the simple reverse of the outermost-first encoding scheme. For example, the entity \emph{Former Hogwarts headmaster} and the entity \emph{Albus Dumbledore} appear at the same level in the outermost-first scheme but they appear at different levels in the innermost-first scheme.

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\subsection{Influence of the Best Path}
\label{sub:potential}

Although the second-best path searching algorithm is proposed as the main contribution of \citeA{shibuya-hovy-2020-nested}, we claim that forcing inner entities locate on the second-best path of the current level is not optimal. Taking the target paths at levels 3 and 4 from the innermost-first encoding example above to clarify the issue, the best path at level 3 is \tg{B-ROLE,I-ROLE,E-ROLE,O,O}. Therefore, the second-best path is more likely to be one of those paths that share as many as possible labels with the best path, e.g., \tg{B-ROLE,I-ROLE,E-ROLE,O,S-ORG}, rather than the actual target label sequence at level 4, i.e., \tg{B-PER,I-PER,I-PER,I-PER,E-PER}, which does not overlap with the best path at all. In addition, \citeA{shibuya-hovy-2020-nested} reuse the same potential function at all higher levels. This indicates that, for instance, at level 3 and time step 1, their model encourages the emission scores of label $\tg{B-ROLE}$, i.e., the dot product of the hidden state and the label embedding $\ve{h}_1^{\top} \ve{v}_{\tg{B-ROLE}}$, to be larger than the emission score of $\tg{B-PER}$, i.e., $\ve{h}_1^{\top} \ve{v}_{\tg{B-PER}}$, while at level 4, their model reversely forces $\ve{h}_1^{\top} \ve{v}_{\tg{B-PER}}$ to be larger than $\ve{h}_1^{\top} \ve{v}_{\tg{B-ROLE}}$. These contradictory optimization goals eventually hurt performance. Therefore, we claim that although they exclude the best path from search space, the influence of the best path still remains.

Therefore, the crux of the matter is to introduce different emission scores for different levels, to make sure each emission score is used at one and only one level. For example, encouraging $\ve{h}_1^{3\top} \ve{v}_{\tg{B-ROLE}}>\ve{h}_1^{3\top} \ve{v}_{\tg{B-PER}}$ at level 3 and encouraging $\ve{h}_1^{4\top} \ve{v}_{\tg{B-PER}}>\ve{h}_1^{4\top} \ve{v}_{\tg{B-ROLE}}$ at level 4 will not lead to contradictory optimization directions anymore, because $\ve{h}_1^{3}$ and $\ve{h}_1^{4}$ are two distinctive hidden states to be used only at levels 3 and 4, respectively.

To achieve this goal, we introduce a novel encoder which outputs $m$ hidden states $\set{\ve{h}_{t}^{l}}_{l=1}^{m}$, where $m$ is the number of levels, as an alternative to the conventional encoder which can only output a single hidden state $\ve{h}_t \in \R^{d_h}$ at each time step. We maintain these hidden states at each time step by removing the used one from them to ensure each hidden state is used at one and only one level. To make a distinction between our $m$ hidden states and the conventional single hidden state, we use the term \emph{chunk} from now on to refer to these hidden states $\ve{h}_{t}^{l} \in \R^{d_h/m}$. We restrict chunk dimension to $d_h/m$, so the total number of parameters is unchanged. For clarity, we use notation $\chunks{l}_t$ to denote the set of remaining chunks at level $l$ and time step $t$, and use $\chunks{l}$ to refer to all of these chunk sets at level $m$ across time steps, i.e., $\set{\mathcal{H}_t^l}_{t=1}^{n}$.


%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\subsection{Chunk Selection}
\label{ssub:selection}

At each time step, our algorithm selects one chunk from the set of remaining chunks for detecting and removes the selected chunk before moving to the next level. From the representation learning aspect, each chunk is supposed to be the representation of a certain level, the set of these $m$ chunks contains complete information of this time step. Therefore, we need a strategy to select the corresponding chunk for a particular level from the remaining chunks.

First, the intuitive idea is to follow the original chunk order and select the $l$-th chunk for level $l$. At level $l$, no matter to which label, the emission score is calculated by using $\ve{h}_t^{l}$. In this way, this \emph{naive} potential function can be defined as follow,
\begin{equation}
    \poten{}{l} = \tran + \chunk{l \top}{t} \vtgt{l}{t}
    \label{eq:index}
\end{equation}
where $\ma{A}\in\R^{\abs{\Y}\times \abs{\Y}}$ is the transition matrix, $\Y$ is the label set, $\tran$ indicates the transition score from label $\tgt{l}{t-1}$ to label $\tgt{l}{t}$, and $\ve{v}_{\tgt{l}{t}} \in \R^{d_h/m}$ is the embedding of label $\tgt{l}{t}$. In this case, the $l$-th chunk $\chunk{l}{t} \in \chunks{l}_t$ is just the chunk which have an interaction with target label, thus should be removed from $\chunks{l}_t$.
\begin{equation}
    \chunks{l+1}_t = \chunks{l}_t \setminus \set{\chunk{l}{t}}
\end{equation}

However, one concern of the \emph{naive} potential function is that it implicitly assumes the outputs of the encoder are automatically arranged in the level order instead of other particular syntactic or semantic order. In practice, it is possible that the encoder gathers all \tg{ROLE} relevant information at the third $h_d/m$ dimensions but remains \tg{PER} relevant information to the fifth $h_d/m$ dimension. For instance, at level 3 time step 1, \emph{naive} potential function forces $\ve{h}_1^{3\top} \ve{v}_{\tg{B-ROLE}}>\ve{h}_1^{3\top} \ve{v}_{\tg{B-PER}}$. However, if there exists another chunk, say $\ve{h}_1^5$, which is more similar to $\ve{v}_{\tg{B-PER}}$, then forcing $\ve{h}_1^{3\top} \ve{v}_{\tg{B-ROLE}}>\ve{h}_1^{5\top} \ve{v}_{\tg{B-PER}}$ is a more reasonable selection strategy. Because, from the representation learning aspect, this means we are not only forcing $\ve{h}_1^3$ to be similar to $\ve{v}_{\tg{B-ROLE}}$, but also encouraging it to be the most salient chunk, i.e., with the largest emission score among all of the remaining chunks. Therefore, the emission score $\ve{h}_1^{3\top} \ve{v}_{\tg{B-ROLE}}$ should not only be larger than the emission scores of other labels with respect to it, e.g., $\ve{h}_1^{3\top} \ve{v}_{\tg{B-PER}}$, but also be larger than the emission scores of all possible labels with respect to all remaining chunks, e.g., $\ve{h}_1^{5\top} \ve{v}_{\tg{B-PER}}$. Besides, from the optimizing aspect, forcing $\ve{h}_1^{5\top} \ve{v}_{\tg{B-PER}}$ to be smaller than $\ve{h}_1^{3\top} \ve{v}_{\tg{B-ROLE}}$ is much harder than forcing $\ve{h}_1^{3\top} \ve{v}_{\tg{B-PER}}$, due to $\ve{h}_1^{5\top} \ve{v}_{\tg{B-PER}} > \ve{h}_1^{3\top} \ve{v}_{\tg{B-PER}}$. Thus, it encourages each label embedding to be well separated \cite{liu2016large}. In other words, this new selection strategy leads to $\ve{h}_t^{\sigma_1 \top} \ve{v}_{y_t^1} > \ve{h}_t^{\sigma_2 \top} \ve{v}_{y_t^2} > \ldots > \ve{h}_t^{\sigma_m \top} \ve{v}_{y_t^m}$, where $\sigma_l$ is the index of selected chunk at level $l$, but for \emph{naive} potential function, the inequation above does not always hold. In other words, \emph{max} selects the most salient chunk at each level.


Therefore, instead of following the original chunk orders, we propose to let each label $y_j$ select the most similar chunk to compute the emission score. We define the \emph{max} potential function as,
\begin{equation}
    \poten{}{l} = \tran + \max_{\chunk{}{}\in \chunks{l}_{t}}{\chunk{\top}{} \vtgt{l}{t}}
    \label{eq:max}
\end{equation}
In this case, we update chunk sets by removing these chunks which are selected by the target labels.
\begin{equation}
    \chunks{l+1}_t = \chunks{l}_t \setminus \set{\argmax_{\chunk{}{}\in \chunks{l}_t}{\chunk{\top}{}\vtgt{l}{t}}}
    \label{eq:set}
\end{equation}

Furthermore, the log-sum-exp operation is a well known differentiable approximation of the max operation, we also introduce it as the third potential function,
\begin{equation}
    \poten{}{l} = \tran + {\log\sum_{\chunk{}{}\in\chunks{l}_t}\exp\,}{\chunk{\top}{}\vtgt{l}{t}}
    \label{eq:logsumexp}
\end{equation}
The chunk set is updated in the same way as Equation~\ref{eq:set}. We refer to this potential function definition as \emph{logsumexp} in the rest of this paper. One advantage of log-sum-exp operation is that it back-propagates gradients to all of its inputs according to normalized inputs, as Equation~\ref{eq:lsegrad}, rather than accumulates gradients only to the selected one, as Equation~\ref{eq:maxgrad}. The max operator may cause some particular chunks to accumulate large gradients and might be prone to convergence to a local optimum solution.
\begin{align}
    \dfrac{\partial \log\sum_{j=1}^n\exp{x_j}}{\partial x_i} &= \dfrac{\exp{x_i}}{\sum_{j=1}^n\exp{x_j}} \label{eq:lsegrad} \\
    \dfrac{\partial \max_{j=1}^{n}{x_j}}{\partial x_i} &= \begin{cases} 
    1 & (i = \argmax_{j=1}^{n} x_j) \\
    0 & (\text{otherwise}) 
    \end{cases} \label{eq:maxgrad}
\end{align}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%% fig. 4
\begin{figure}[b]
\begin{center}
\includegraphics{29-1ia2f4.pdf}
\end{center}
\hangcaption{The proposed model. The dotted lines mean the CRF component is shared across levels. These orange circles stand for chunks at each time step. Please note that we draw only three circles at each time step is just for brevity, there are more chunks in practice. The translucent CRF block and its outputs mean this prediction has been performed at the previous level, while these translucent circles indicate these chunks were used to detect entities at the last level and have been removed from chunk sets.}
\label{fig:architecture}
\end{figure}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%


%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\subsection{Neural Network Architecture}

The neural network architecture, as Figure~\ref{fig:architecture}, of our model is mainly based on previous work with only a few modifications, and we will briefly introduce it in this section.
 

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\subsubsection{Embedding Layer}

Following previous work \cite{shibuya-hovy-2020-nested}, we convert words to word embeddings $\ve{w}_t \in \R^{d_w}$ and employ a character-level bidirectional LSTM to obtain character-based word embeddings  $\ve{c}_t\in \R^{d_c}$. The concatenation of them is fed into the encoding layer as the token representation $\ve{x}_t=[\ve{w}_t,\ve{c}_t] \in \R^{d_x}$.


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

We employ a three-layered bidirectional LSTM to encode sentences and leverage contextual information,
\begin{equation}
    \set{\ve{h}_t}_{t=1}^{n} = \operatorname{LSTM}{\left(\set{\ve{x}_t}_{t=1}^{n}\right)}
\end{equation}
where $\ve{h}_t \in \R^{d_h}$ is the hidden state. In contrast to the encoders of previous work, which can only output single hidden states at each time step, we split $\ve{h}_t$ into $m$ chunks,
\begin{equation}
    [\ve{h}_{t}^{1},\dots,\ve{h}_{t}^{m}] = \ve{h}_t
    \label{eq:split}
\end{equation}
where $\ve{h}_t^j\in \R^{d_h/m}$, and use them as the first level chunk set, i.e., $\chunks{1}_{t}=\set{\chunk{j}{t}}_{j=1}^{m}$, to start recognition.


%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\subsubsection{Decoding Layer}

At each level, we run a shared conventional CRF with its corresponding potential function $\poten{}{l}$ and update the chunk sets until finishing all $m$ levels. On the training stage, we remove chunks according to the selections of the target labels, while on the decoding stage, it depends on the selections of the predicted labels.
 

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\subsection{Training and Decoding}
\label{ssub:training}

Following the definition of CRF, the conditional probabilistic function of a given label sequence at $l$-th level, i.e., $\ve{y}^l=\set{y_t^l}_{t=1}^{n}$, can be defined as,
\begin{gather}
    \prob{}{l} = \dfrac{1}{\partition{(\chunks{l})}}\exp{\sum_{t=1}^{n}{\poten{}{l}}} \\ 
    \partition{(\chunks{l})} = \sum_{\ve{y}^{\prime}\in\mathcal{Y}^{n}}{\exp{\sum_{t=1}^{n}{\poten{\prime}{l}}}}
\end{gather}
where $\partition{(\chunks{l})}$ is the sum of all paths' scores and is commonly known as the partition function.

We optimize our model by minimizing the sum of the negative log-likelihoods of all levels.
\begin{equation}
    \loss = - \sum_{l=1}^{m}{\log{\prob{}{l}}}
\end{equation}

On the decoding stage, 
\pagebreak
we iteratively apply the Viterbi algorithm \cite{forney1973viterbi} at each level to search the most probable label sequences.
\begin{equation}
    \hat{\ve{y}}^l = \argmax_{\ve{y}^{\prime}\in \Y^{n}}{p{\,(\ve{y}^{\prime} \mid \chunks{l})}}
\end{equation}

The pseudocodes of the training and the decoding algorithms with \emph{max} or \emph{logsumexp} potential function can be found in Algorithms~\ref{algo:training} and \ref{algo:decoding}, respectively.
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%% algo. 1
\begin{algorithm}[t]
\SetAlgoLined\DontPrintSemicolon
\SetKwInOut{Input}{input}
\SetKwInOut{Output}{output}

\Input{first level chunk sets $\mathcal{H}^1$}
\Input{target label sequences $\ve{y}^1,\cdots,\ve{y}^m$}
\Output{negative log-likelihood $\mathcal{L}$}
$\mathcal{L}\leftarrow 0$\;
\For{$l=1$ \KwTo $m$}{
    $\mathcal{L}\leftarrow \mathcal{L} - \log{\prob{}{l}}$\;
    \For{$t=1$ \KwTo $n$}{
    $\mathcal{H}^{l+1}_t \leftarrow \mathcal{H}^{l}_t \setminus \set{{\underset{\ve{h}\in \mathcal{H}_t^l}{\argmax}}{\,\ve{h}^{\top}\ve{v}_{y_t^l}}}$\;
    }
}
\caption{Training (with \emph{max} or \emph{logsumexp} potential function)}
\label{algo:training}
\end{algorithm}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%% algo. 2
\begin{algorithm}[t]
\SetAlgoLined\DontPrintSemicolon
\SetKwInOut{Input}{input}
\SetKwInOut{Output}{output}

\Input{first level chunk sets $\mathcal{H}^1$}
\Output{recognized entity set $\mathcal{E}$}

$\mathcal{E}\leftarrow\varnothing$\;
\For{$l=1$ \KwTo $m$}{
    $\hat{\ve{y}}^l \leftarrow \underset{\ve{y}^{\prime}\in\mathcal{Y}^n}{\argmax}{\,p{\,(\ve{y}^{\prime}\mid \chunks{l})}}$\;
    \For{$t=1$ \KwTo $n$}{
    $\mathcal{H}^{l+1}_t \leftarrow \mathcal{H}^{l}_t \setminus \set{{\underset{\ve{h}\in \mathcal{H}_t^l}{\argmax}}{\,\ve{h}^{\top}\ve{v}_{\hat{y}_t^l}}}$
    }
    $\mathcal{E}\leftarrow\mathcal{E} \mathbin{\bigcup}\, \operatorname{\texttt{label-to-entity}}{(\hat{\ve{y}}^l)}$\;
}
\caption{Decoding (with \emph{max} or \emph{logsumexp} potential function)}
\label{algo:decoding}
\end{algorithm}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%% table 1
\begin{table}[b]
\input{02table01.tex}
\hangcaption{Statistics of datasets. $\abs{\Y}$ is the size of the label set, $m$ is the maximal depth of entity nesting. The number of entities is displayed with respect to level and split.}
\label{tab:data_stats}
\end{table}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%


%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\section{Experiments}
\label{sec:expriments}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\subsection{Datasets}

Following the standard benchmark settings, we conduct experiments on four nested named entity recognition datasets in English with divergence domains, i.e., ACE2004 \cite{doddington-etal-2004-automatic}, ACE2005 \cite{walker2006ace}, GENIA \cite{kim-genia-2003} and NNE \cite{ringland-etal-2019-nne}. We divide all these datasets into train/dev/test split by following \citeA{shibuya-hovy-2020-nested} and \citeA{wang-etal-2020-pyramid}. The ACE2004, ACE2005, and NNE datasets are in the news domain and have six levels, while the GENIA dataset is in the biomedical domains and is rather shallow with only four levels. Specifically, the NNE dataset contains 427 distinct labels. Thus, it is much more fine-grained than the others which has up to 29 distinct labels. The detailed dataset statistics can be found in Table~\ref{tab:data_stats}.


%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\subsection{Hyper-parameters Settings}

For word embeddings initialization, we utilize 100-dimensional pre-trained GloVe \cite{pennington-etal-2014-glove} for the ACE2004, ACE2005, and NNE datasets, and use 200-dimensional biomedical domain word embeddings\footnote{\url{https://github.com/cambridgeltl/BioNLP-2016}} \cite{chiu-etal-2016-train} for the GENIA dataset. Moreover, we randomly initialize 30-dimensional vectors for character embeddings. The hidden state dimension of character-level LSTM $d_c$ is 100, i.e., 50 in each direction, thus the dimension of token representation $d_x$ is 200. We apply dropout \cite{JMLR:v15:srivastava14a} on token representations before feeding it into the encoder.

The hidden state dimension of the three-layered LSTM is 600 for ACE2004, ACE2005, and NNE, i.e., 300 in each direction, and 400 for GENIA. Choosing a different dimension is because the maximal depth of entity nesting $m$ is different. We apply layer normalization \cite{ba2016layer} and dropout with 0.5 ratio after each bidirectional LSTM layer.

Different from \citeA{shibuya-hovy-2020-nested}, we use only one CRF instead of employing different CRFs for different entity types. Besides, our CRF is also shared across levels, which means we use the same CRF to detect entities at all levels.

Our model is optimized by using stochastic gradient descent (SGD), with a decaying learning rate $\eta_{\tau} = \eta_0 / (1 + \gamma \cdot \tau)$, where $\tau$ is the index of the current epoch. For ACE2004, ACE2005, GENIA, and NNE, the initial learning rates $\eta_0$ are $0.2$, $0.2$, $0.1$, and $0.2$, and the decay rates $\gamma$ are $0.01$, $0.02$, $0.02$, and $0.02$ respectively. We set the weight decay rate, the momentum, the batch size, and the number of epochs to be $10^{-8}$, $0.5$, $32$, and $100$ respectively, especially we use batch size 64 on the GENIA dataset. We clip the gradient exceeding 5.

Besides, we also conduct experiments to evaluate the performance of our model with contextual word representations. BERT \cite{devlin-etal-2019-bert} and Flair \cite{akbik-etal-2018-contextual} are the most commonly used contextual word representations in previous work and have also been proved that they can substantially improve the model performance. In these settings, contextual word representations are concatenated with word and character representations to form the token representations, i.e., $\ve{x}_t = [\ve{w}_t,\ve{c}_t,\ve{e}_t]$, where $\ve{e}_t$ is the contextual word representation and it is not fine-tuned in any of our experiments.

\begin{description}
\item[BERT] is a transformer-based \cite{NIPS2017_7181} pre-trained contextual word representation. In our experiments, for the ACE2004, ACE2005, and NNE datasets we use the general domain checkpoint \texttt{bert-large-uncased}, and for the GENIA dataset we use the biomedical domain checkpoint \texttt{BioBERT large v1.1}\footnote{\url{https://github.com/naver/biobert-pretrained}} \cite{DBLP:journals/corr/abs-1901-08746}. We average all BERT subword embeddings in the last four layers to build 1024-dimensional vectors.
\item[Flair] is a character-level BiLSTM-based pre-trained contextual word representation. We concatenate these vectors obtained from the \texttt{news-forward} and \texttt{news-backward} checkpoints for ACE2004, ACE2005, and NNE, and use the \texttt{pubmed-forward} and \texttt{pubmed-backward} checkpoints for GENIA, to build 4096-dimensional vectors.
\end{description}


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

Experiments are all evaluated by precision, recall, and F$_1$. Our experiments were run four times with different random seeds, and averaged scores are reported in the following tables.

Our model\footnote{\url{https://github.com/speedcell4/nersted}} is implemented with \texttt{PyTorch} \cite{NIPS2019_9015} and we run experiments on \texttt{GeForce GTX 1080Ti} with 11 GB memory.


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

Table~\ref{tab:exp} shows the performance of previous work and our model on the ACE2004, ACE2005, and GENIA datasets. Our model substantially outperforms most of the previous work, especially when compared with our baseline \citeA{shibuya-hovy-2020-nested}. When using only word embeddings and character-based word embeddings, our method exceeds theirs by 2.64 F$_1$ score and also achieves comparable results with the recent competitive method \cite{wang-etal-2020-pyramid}. In the case of utilizing BERT and further employing Flair, our method consistently outperforms \citeA{shibuya-hovy-2020-nested} by 1.09 and 0.60 by F$_1$ scores, respectively.

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%% table 2
\begin{table}[t]
\input{02table02.tex}
\hangcaption{Experimental results on the ACE2004, ACE2005 and GENIA datasets. Labels \texttt{[B]} and \texttt{[F]} stand for BERT and Flair contextual word representations respectively. \sota{Bold} and \sotb{underlined} numbers indicates the best and the second-best results respectively. \emph{naive}, \emph{max}, and \emph{logsumexp} refer to the three potential function definitions, i.e., Equations~\ref{eq:index}, \ref{eq:max}, and \ref{eq:logsumexp}, respectively. These numbers in parentheses are standard deviations.}
\label{tab:exp}
\end{table}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

On the ACE2005 dataset, our method improves the F$_1$ scores by 1.98, 0.72, and 0.59, respectively, compared with \citeA{shibuya-hovy-2020-nested}. Although our model performance is inferior to \citeA{wang-etal-2020-pyramid} in general, our \emph{max} potential function method is slightly superior to them by 0.05 in F$_1$ score when employing BERT.

Furthermore, on the biomedical domain dataset GENIA, our method constantly outperforms \citeA{shibuya-hovy-2020-nested} by 0.18, 1.62, and 1.57 in F$_1$ scores, respectively. Although the low scores of \citeA{shibuya-hovy-2020-nested} are due to their usage of the general domain checkpoint \texttt{bert-large-uncased}, instead of our biomedical domain checkpoint, our model is still superior to \citeA{strakova-etal-2019-neural} by 0.47 and 0.62 in F$_1$ scores, who used the same checkpoint as us.

On the NNE dataset, shown in Table~\ref{tab:nne}, our method slightly but consistently outperform \citeA{wang-etal-2020-pyramid} by 0.08, 0.19, and 0.22 in F$_1$. We hypothesize that the NNE dataset contains many more sentences and entity types than the other three datasets. Our method is much more capable of learning the meaningful representation when data are sufficient.

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%% table 3
\begin{table}[b]
\input{02table03.tex}
\caption{Experimental results on the NNE dataset.}
\label{tab:nne}
\end{table}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

As for these three potential functions, we notice the \emph{max} and \emph{logsumexp} potential functions generally works better than the \emph{naive} potential function. These results demonstrate that the chunk selection strategy of the \emph{max} and \emph{logsumexp} can leverage information from all remaining chunks and constrains hidden states of LSTM to be more semantically ordered. When we use BERT and Flair, the advantage of the \emph{max} and the \emph{logsumexp} potential function is less obvious compared with the case when we only use word embeddings and character-based word embeddings, especially on the GENIA dataset. We hypothesize that BERT and Flair can provide rich contextual information, then selecting chunks in the original order is sufficient. Thus our dynamic selecting mechanism can only slightly improve the model performance.

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%% table 4
\begin{table}[b]
\input{02table04.tex}
\caption{Influence of the two encoding schemes and the three potential functions.}
\label{tab:encoding_potential}
\end{table}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%


%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\subsection{Influence of the Encoding Scheme}

We also conduct experiments on the ACE2004 dataset to measure the influence of the \linebreak
outermost-first and innermost-first encoding schemes. As shown in Table~\ref{tab:encoding_potential}, the innermost-first encoding scheme consistently works better than the outermost-first encoding scheme with all potential functions. We hypothesize that outermost entities do not necessarily contain inner entities, especially for longer ones. Putting those diversely nested outermost entities at the same level would dislocate the encoding representation. Furthermore, even if we use the outermost-first encoding scheme, our method is superior to \citeA{shibuya-hovy-2020-nested}, which further demonstrates the effectiveness of excluding the influence of the best path.


%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\subsection{Time Complexity and Speed}

The time complexity of encoder is $\operatorname{\mathcal{O}}{(n)}$, and because we employ the same tree reduction acceleration trick\footnote{\url{https://github.com/speedcell4/torchlatent}} as \citeA{rush-2020-torch}, the time complexity of CRF is reduced to $\operatorname{\mathcal{O}}{(\log{n})}$, therefore the overall time complexity is $\operatorname{\mathcal{O}}{(n + m\cdot \log{n})}$. However, even with the help of the acceleration trick, the time complexity of \citeA{wang-etal-2020-pyramid}, i.e., $\operatorname{\mathcal{O}}{(n)}$, is still lower than ours. Since they instead use softmax to predict the types of each span directly without relying on CRF.

Even in this situation, the training and inference speed of our model is much faster than theirs, as shown in Table~\ref{tab:speed}. In addition, when we increase the batch size to 64, the decoding speed is more than two times faster than their model. The most critical reason is that we do not need to stack LSTM to 16 layers, and the sentence length is generally short. Thus the $\log{n}$ term of our model time complexity does not become the performance bottleneck.

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%% table 5
\begin{table}[b]
\input{02table05.tex}
\hangcaption{Speed comparison on the dataset ACE2005. Numbers indicate how many words can be processed per second on average.}
\label{tab:speed}
\vspace{-0.5\Cvs}
\end{table}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%


%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\subsection{Level-wise Performance}

We display the performance on the dataset ACE2005 at each level in Table~\ref{tab:levelpr}. The \emph{max} potential function at the first three levels achieves constantly higher precision scores than the \emph{naive} and \emph{logsumexp} potential functions, while at the same time obtains the lowest recall scores. The \emph{logsumexp} potential function, on the contrary, achieves the highest recall scores but fails to obtain satisfactory precision scores. Because most entities locate at the first two levels, the \emph{max} and \emph{logsumexp} achieve the best overall precision and recall scores, respectively.

Since max operator back-propagates gradients to only one of its inputs, log-sum-exp operator back-propagate gradients to all of its input according to their normalized weights, therefore, the max operator may cause some particular chunks to accumulate large gradients and might be prone to convergence to a local optimum solution.

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%% table 6
\begin{table}[t]
\input{02table06.tex}
\hangcaption{Precision and recall scores at each level with each potential function. Please note that the test split of dataset ACE2005 contains no entities at level 6.}
\label{tab:levelpr}
\end{table}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%


%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\subsection{Chunk Distribution}

We analyze the chunk distribution on the test split of the dataset ACE2005 by plotting the heat maps in Figure~\ref{fig:distribution}, in which these numbers indicate the percentages of each chunk being selected by a particular level or label. For example, the 35 at the upper-right corner means when using \emph{logsumexp} potential function, 35\% of predictions at the first level are made by choosing the sixth chunk, while the 78 at the lower-left corner shows 78\% of \tg{WEA} are related to the first chunk with \emph{naive}. To make it easier to compare with the \emph{naive}, we arranged the chunk orders of \emph{max} and \emph{logsumexp}, without losing generality, to make the level-chunk distribution mainly concentrate on the diagonal.

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%% fig. 5
\begin{figure}[t]
\begin{center}
\includegraphics{29-1ia2f5.pdf}
\end{center}
\hangcaption{Chunk distributions of the \emph{naive}, \emph{max}, and \emph{logsumexp} potential functions, respectively. Each row displays the chunk selection preferences with respect to levels, syntactic and semantic labels, respectively.}
\label{fig:distribution}
\end{figure}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

The \emph{naive} potential function selects the $l$-th chunk at $l$-th level. Therefore the heat map is just diagonal. In addition to the first chunk, the \emph{logsumexp} potential function also prefers to select the sixth and the fourth chunks at the first level. We hypothesis this is due to most of \tg{B-} and \tg{S-} labels locate on the first level, and this can be confirmed according to the syntactic-chunk heat map of \emph{logsumexp} where 78\% \tg{B-} and 70\% \tg{S-} labels go to the sixth and fourth chunks. Similarly, \emph{max} also has a high probability of selecting the second chunk.

Generally, the chunk distribution of \emph{logsumexp} is more smooth than \emph{max}. Besides, we find label \tg{O} almost uniformly select chunks in both the syntactic and semantic heat maps, while other meaningful labels have their distinguished preferences.

Syntactic labels \tg{S-} and \tg{B-} mainly represent the beginning of an entity, while \tg{I-} and \tg{E-} stands for the continuation and ending of an entity. In the syntactic-chunk heat map of \emph{naive}, they are indiscriminately distributed to the first chunk because most of the entities are located on the first level. However, \emph{max} and \emph{logsumexp} utilize different chunks to represents these different syntactic categories.

Likewise, the semantic label \tg{GPE}, when using \emph{logsumexp}, also has a 61\% probability of selecting the sixth chunks other than concentrating on the first chunk as \emph{naive}. These observations further demonstrate our dynamic chunk selection strategies are capable of learning more meaningful representations.


%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\subsection{Connection to Attention Mechanism}

The heat maps of chunk selection, Figure~\ref{fig:distribution}, leads to a question that what is the connection between our methods and attention mechanism \cite{vaswani2017attention}. In this section, we briefly explain the connections and show the results of ablation studies to demonstrate that our methods are equivalent or better than the existing attention mechanism variants.

As we mentioned in \S\ref{ssub:selection}, our dynamic chunk selection strategies let each label select the most similar chunk to it. Thus, the idea of replacing our dynamic selection strategies with attention mechanism could be implemented by letting each label embedding attend to all remaining chunks and building a chunk vector through aggregating information from all of them.
\begin{equation}
    \tilde{\ve{h}}_t^l = \operatorname{attention}{(\texttt{query}=\ve{v}_{y_t^l},\texttt{key}=\mathcal{H}^l,\texttt{value}=\mathcal{H}^l)}
\end{equation}
Subsequently, $\tilde{\ve{h}}_t^l$ is used for taking dot product with label embedding, similar to Equation~\ref{eq:index}.
\begin{equation}
    \poten{}{l} = A_{y_{t-1}^l,y_{t}^l} + \tilde{\ve{h}}_t^l {}^{\top} \ve{v}_{y_t^l}
\end{equation}

Attention mechanism can be roughly divided into two categories, i.e., the hard attention and the soft attention. The hard attention mechanism only selects the chunk with the maximal score.
\begin{align}
    \tilde{\ve{h}}_t^l &= \operatorname{\texttt{attention}}{(\texttt{query}=\ve{v}_{y_t^l},\texttt{key}=\mathcal{H}^l,\texttt{value}=\mathcal{H}^l)} \\
    &=\argmax_{\ve{h}\in\mathcal{H}^l}{\ve{h}^{\top} \ve{v}_{y_t^l}}
\end{align} Therefore, \begin{align}
    \poten{}{l} &= A_{y_{t-1}^l,y_{t}^l} + \tilde{\ve{h}}_t^l {}^{\top} \ve{v}_{y_t^l} \\
    &= A_{y_{t-1}^l,y_{t}^l} + \left( \argmax_{\ve{h}\in\mathcal{H}^l}{\ve{h}^{\top} \ve{v}_{y_t^l}} \right)^{\top} \ve{v}_{y_t^l} \\
    &= A_{y_{t-1}^l,y_{t}^l} + \max_{\ve{h}\in\mathcal{H}^l}{\ve{h}^{\top} \ve{v}_{y_t^l}} \label{eq:hardatt}
\end{align}
It is easy to notice that Equation~\ref{eq:hardatt} is identical to our \emph{max} potential function, i.e., Equation~\ref{eq:max}.

On the other hand, soft attention aggregates information from all chunks by taking the normalized similarities as weights.
\begin{align}
    \tilde{\ve{h}}_t^l &= \operatorname{\texttt{attention}}{(\texttt{query}=\ve{v}_{y_t^l},\texttt{key}=\mathcal{H}^l,\texttt{value}=\mathcal{H}^l)} \\
    &=\sum_{\hat{\ve{h}}\in\mathcal{H}^l} {\operatorname{softmax}{(\hat{\ve{h}}^{\top}\ve{v}_{y_t^l})} \cdot \hat{\ve{h}}} \\
    &=\sum_{\hat{\ve{h}}\in\mathcal{H}^l} {\left(\dfrac{\exp{\hat{\ve{h}}^{\top} \ve{v}_{y_t^l}}}{\sum_{\ve{h}\in\mathcal{H}^l}{\exp{\ve{h}^{\top} \ve{v}_{y_t^l}}}} \right) \cdot \hat{\ve{h}}}
\end{align}
Similarly,
\begin{align}
    \poten{}{l} &= A_{y_{t-1}^l,y_{t}^l} + \tilde{\ve{h}}_t^l {}^{\top} \ve{v}_{y_t^l} \\
    &= A_{y_{t-1}^l,y_{t}^l} + \left( \sum_{\hat{\ve{h}}\in\mathcal{H}^l} {\Big(\dfrac{\exp{\hat{\ve{h}}^{\top} \ve{v}_{y_t^l}}}{\sum_{\ve{h}\in\mathcal{H}^l}{\exp{\ve{h}^{\top} \ve{v}_{y_t^l}}}} \Big) \cdot \hat{\ve{h}}} \right)^{\top} \ve{v}_{y_t^l} \\
    &= A_{y_{t-1}^l,y_{t}^l} +  \sum_{\hat{\ve{h}}\in\mathcal{H}^l} {\left(\dfrac{\exp{\hat{\ve{h}}^{\top} \ve{v}_{y_t^l}}}{\sum_{\ve{h}\in\mathcal{H}^l}{\exp{\ve{h}^{\top} \ve{v}_{y_t^l}}}} \right) \cdot \left(\hat{\ve{h}}^{\top} \ve{v}_{y_t^l} \right)} \\
    &= A_{y_{t-1}^l,y_{t}^l} +  \dfrac{\sum_{\hat{\ve{h}}\in\mathcal{H}^l}{\left(\exp{\hat{\ve{h}}^{\top}\ve{v}_{y_t^l}}\right) \cdot  \left(\hat{\ve{h}}^{\top}\ve{v}_{y_t^l}\right)}}{\sum_{\ve{h}\in\mathcal{H}^l}{\exp{\ve{h}^{\top}\ve{v}_{y_t^l}}}} \label{eq:softmax}
\end{align}
This is actually another differentiable approximation of \emph{max} operator.
\begin{equation}
    \max{(x_1,\dots,x_n)} \approx \dfrac{\sum_{i=1}^n{x_i \cdot \exp x_i} }{\sum_{i=1}^n{\exp x_i}}
\end{equation}
Since this potential function utilizes softmax function, we refer to it as \emph{softmax-x}.

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%% table 7
\begin{table}[b]
\input{02table07.tex}
\hangcaption{Ablation studies on attention and level-wise projection. In column $\phi$, the \emph{softmax-x} stands for the potential function in Equation~\ref{eq:softmax}. In column $\ve{h}_t^l$, the \emph{Split} refers to directly splitting hidden states to several chunks as Equation~\ref{eq:split} while the \emph{Project} means employing an additional projection layer for each level as Equation~\ref{eq:projection}.}
\label{tab:attention}
\end{table}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

We conducted experiments on the ACE2004 dataset, and the experimental results are presented in Table~\ref{tab:attention}. Note that the performance of \emph{softmax-x} is sightly better than \emph{naive}, but the F$_1$ score is still much lower than \emph{max} and \emph{logsumexp}. To analyze the reason behind, we plot the curves of $\max{(x,0)}$, and $\log{(\exp{x} + \exp{0})}$, $\dfrac{x\cdot \exp{x} + 0\cdot \exp{0}}{\exp{x}+\exp{0}}$, i.e., the \emph{max} operator and its two differentiable approximations, \emph{logsumexp} and \emph{softmax-x}, in the left of Figure~\ref{fig:grad} and their gradient curve on the right hand side. From these curves we can find that the gradient of \emph{softmax-x} is not monotonically increasing, and thus is less stable than \emph{max} and \emph{logsumexp}. Therefore, we claim \emph{logsumexp} is a better differentiable approximation of \emph{max} than \emph{softmax-x}.

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%% fig. 6
\begin{figure}[t]
\begin{center}
\includegraphics{29-1ia2f6.pdf}
\end{center}
\hangcaption{The left part shows the curve of the \emph{max} operator and its two differentiable approximations, \emph{logsumexp} and \emph{softmax-x}. The right part displays their gradients.}
\label{fig:grad}
\end{figure}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%


%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\subsection{Level-wise Projection}

As we described above, our potential function \emph{max} and \emph{logsumexp} dynamically selects chunks at each level according to their similarities with each label embedding. However, it maybe be possible to replace the dynamic selection strategy with a static strategy by projecting representations to obtain the level-wise $\ve{h}_t^l$ directly. To verify this hypothesis, we add level-wise projection layer to let neural network learn these $m$ level-wise chunks directly, instead of splitting hidden states into $m$ chunks as in Equation~\ref{eq:split}.
\begin{equation}
    \ve{h}_t^l = \tanh{(\ma{W}_h^l {}^{\top}\ve{h}_t)}
    \label{eq:projection}
\end{equation}
Where $\ma{W}_h^l\in \mathbb{R}^{d_h \times (d_h/m)}$ is an additional parameter to project the hidden state $\ve{h}_t$ to obtain the chunk at level $l$, and adding hyperbolic tangent function, i.e., $\tanh$, is to preserve mapping to be nonlinear and ensure projection is nontrivial.

In the ideal case, level-wise projection can statically learn the chunk representation at each level. Thus, there is no need to employ dynamic chunk selection strategies. However, we also conducted experiments with both of them to provide exclusive comparisons. According to the experimental results, as shown in Table~\ref{tab:attention}, level-wise projection is capable of enhancing the performance of \emph{naive} potential function in some degree, however, its performance is still inferior to \emph{max} and \emph{logsumexp}. Besides, for all dynamic selection strategies, i.e., \emph{max}, \emph{logsumexp}, and \emph{softmax-x}, none of them obtained better results with level-wise projection. Therefore, we claim that our dynamic selection strategies are more effective than level-wise projection, and at the same time, without demanding additional parameters.

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%% table 8
\begin{table}[b]
\input{02table08.tex}
\hangcaption{Case study. The \textbf{Target} row displays the ground-truth, and the following rows show the predictions of Shibuya and Hovy (2020) and our three potential functions. In each sentence, brackets indicate the boundary of each entity, and the entity type is annotated right after its closing bracket.}
\label{tab:example1}
\end{table}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%


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

We show some prediction examples in this section to compare model behaviors in Table~\ref{tab:example1}. In the first example, although the model of \citeA{shibuya-hovy-2020-nested} is designed to detect entities from outer to inner, their model failed to recognize entity \emph{griffen bell}, which is nested within an outer entity \emph{prominent democrats including griffen bell}, while all of our three potential functions successfully detected it. Similarly, their model mistakenly predicts \emph{gore} as a single word entity, while none of our methods made this mistake. For the longest entity, i.e., \emph{gore who \dots in the state}, their model successfully detected the opening bracket but prematurely closed the bracket after \emph{this year}. Surprisingly, we found our \emph{naive} potential function made the same mistake, while our \emph{max} and \emph{logsumexp} correctly close the bracket at the end of this sentence. We claim this demonstrates that our dynamic selection strategies are capable of leveraging information among all remaining chunks to make predictions more accurate.


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

In this paper, we proposed a simple and effective method for nested named entity recognition by explicitly excluding the influence of the best path through selecting and removing chunks at each level to build different potential functions. We also proposed three different selection strategies to leverage information from all remaining chunks. Besides, we found the innermost-first encoding scheme works better than the conventional outermost-first encoding scheme. Extensive experimental results demonstrate the effectiveness and efficiency of our method. However, one of the demerits of our method is the number of chunks, i.e., the maximal depth of entity nesting must be chosen in advance as a hyper-parameter. We will extend it to arbitrary depths as future work.


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

Part of this work was presented at the 59th Annual Meeting of the Association for Computational Linguistics and the 11th International Joint Conference on Natural Language Processing, August, 2021, Online \cite{wang-etal-2021-nested}. This work was partly supported by JST CREST Grant Number JPMJCR1513.


%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\bibliographystyle{jnlpbbl_1.6}

\bibliography{02refs}

\begin{biography}

\bioauthor[:]{Yiran Wang}{%
Yiran Wang received the B.E. degree from Hunan University, China, in 2014, and the M.E. degree from Kyoto University, Japan, in 2018. From 2018 to 2021, he was a Ph.D. student of the Nara Institute of Science and Technology (NAIST), Ikoma, Japan. Currently, he is a technical researcher at the National Institute of Information and Communications Technology (NICT). His research interests include named entity recognition, dependency parsing, and machine translation.}

\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[:]{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.}

\bioauthor[:]{Taro Watanabe}{%
Taro Watanabe received the B.E. and M.E. degrees in information science from Kyoto Univ., 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 a Ph.D. in informatics from Kyoto Univ., 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.}
\end{biography}


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




\end{document}

