GlobalPointer: A Unified Approach to Nested and Non-Nested NER

GlobalPointer：用统一的方式处理嵌套和非嵌套NER 苏剑林 · 2021-05-01 · Machine Learning model NLP NER

(Note: The content of this post has been written up as a paper, Global Pointer: Novel Efficient Span-based Approach for Named Entity Recognition. If you'd like to cite this work, please cite the English paper directly. Thanks.)

This post introduces a design called GlobalPointer, which uses a globally normalized approach to Named Entity Recognition (NER). It can handle nested and non-nested entities indiscriminately, achieving performance comparable to CRF in the non-nested (Flat NER) setting, while also performing well on nested NER. Moreover, in theory the design philosophy of GlobalPointer is more sound than that of CRF; and in practice, training doesn't require the recursive computation of a denominator as CRF does, and decoding doesn't require dynamic programming either—it's fully parallelizable, with an ideal time complexity of $\mathcal{O}(1)$!

In short: cleaner, faster, and more powerful! Does such a good design really exist? Let's take a closer look.

Illustration of GlobalPointer's multi-head recognition of nested entitiesmore

GlobalPointer

The conventional Pointer Network design for entity recognition or reading comprehension typically uses two separate modules to identify the start and end of an entity, which introduces an inconsistency between training and prediction. GlobalPointer is designed precisely to address this inconsistency: it treats the start and end as a single unit for judgment, giving it a more "global" perspective (hence the name).

Basic idea

Specifically, suppose the text sequence to be recognized has length $n$. For simplicity, let's assume there's only one entity type to recognize, and that each target entity is a contiguous span of the sequence, of arbitrary length, and spans can overlap with each other (nested entities). How many "candidate entities" does this sequence have? It's not hard to show that the answer is $n(n+1)/2$: a sequence of length $n$ has $n(n+1)/2$ distinct contiguous subsequences, and these subsequences cover all possible entities. What we need to do is pick out the true entities from these $n(n+1)/2$ "candidate entities"—essentially a multi-label classification problem of "choosing $k$ out of $n(n+1)/2$." If there are $m$ entity types to recognize, then this becomes $m$ separate "choose $k$ out of $n(n+1)/2$" multi-label classification problems. This is the basic idea behind GlobalPointer: making judgments with the entity as the basic unit, as illustrated in the image at the beginning of this post.

Some readers might ask: doesn't this design have a complexity of $\mathcal{O}(n^2)$? Won't that be particularly slow? If we were still in the era of RNNs/CNNs, this might indeed seem slow. But now that Transformers are ubiquitous in NLP, every layer of a Transformer already has $\mathcal{O}(n^2)$ complexity—one more GlobalPointer layer doesn't add much, and one fewer doesn't save much either. The key point is that the $\mathcal{O}(n^2)$ complexity of GlobalPointer is purely a space complexity; with good parallelism, the time complexity can even be reduced to $\mathcal{O}(1)$, so there's no noticeable slowdown in practice.

Mathematical formulation

Let the input $t$ of length $n$, after encoding, yield the vector sequence $[\boldsymbol{h}_1,\boldsymbol{h}_2,\cdots,\boldsymbol{h}_n]$. Through transformations $\boldsymbol{q}_{i,\alpha}=\boldsymbol{W}_{q,\alpha}\boldsymbol{h}_i+\boldsymbol{b}_{q,\alpha}$ and $\boldsymbol{k}_{i,\alpha}=\boldsymbol{W}_{k,\alpha}\boldsymbol{h}_i+\boldsymbol{b}_{k,\alpha}$, we can obtain the vector sequences $[\boldsymbol{q}_{1,\alpha},\boldsymbol{q}_{2,\alpha},\cdots,\boldsymbol{q}_{n,\alpha}]$ and $[\boldsymbol{k}_{1,\alpha},\boldsymbol{k}_{2,\alpha},\cdots,\boldsymbol{k}_{n,\alpha}]$, which are the vector sequences used to recognize the $\alpha$-th entity type. We can then define

\begin{equation}s_{\alpha}(i,j) = \boldsymbol{q}_{i,\alpha}^{\top}\boldsymbol{k}_{j,\alpha}\label{eq:s}\end{equation}

as the score for the contiguous span from $i$ to $j$ being an entity of type $\alpha$. That is, we use the inner product of $\boldsymbol{q}_{i,\alpha}$ and $\boldsymbol{k}_{j,\alpha}$ as the score (logit) for span $t_{[i:j]}$ being an entity of type $\alpha$, where $t_{[i:j]}$ refers to the contiguous substring of sequence $t$ from the $i$-th to the $j$-th element. Under this design, GlobalPointer is in effect a simplified version of Multi-Head Attention, where each entity type corresponds to one head, and compared to Multi-Head Attention it drops the computation associated with $\boldsymbol{V}$.

Relative position

In theory, a design like formula $\eqref{eq:s}$ should be sufficient, but in practice, when the training corpus is relatively limited, its performance tends to be subpar, because it doesn't explicitly encode relative positional information. In the experiments below we'll see that adding relative positional information can change results by more than 30 percentage points!

For example, suppose we want to recognize place names in the input of a weather forecast: "Beijing: 21°C; Shanghai: 22°C; Hangzhou: 23°C; Guangzhou: 24°C; ..." There are many entities to be recognized here. Without relative positional information as input, GlobalPointer isn't particularly sensitive to the length and span of an entity, so it's prone to treating the start and end of any two entities as a combined target (e.g., predicting something like "Beijing: 21°C; Shanghai" as a single entity). Conversely, with relative positional information, GlobalPointer becomes much more sensitive to entity length and span, and can therefore better identify the true entities.

Which type of relative position encoding should we use? In theory, any of the relative position encodings used in Transformers could be considered (see Position Encoding Schemes That Have Wracked Researchers' Brains). But once you actually try to implement this, you'll find a problem: most relative position encodings truncate the relative position at some cutoff. While this cutoff range is generally sufficient for the entities we want to recognize, it's a bit inelegant; and if we don't truncate, we run into the problem of having too many learnable parameters. After some deliberation, I felt that the Rotary Position Embedding (RoPE) I devised previously would be a good fit here.

An introduction to RoPE can be found in The Path to the Transformer Upgrades: 2. Rotary Position Embedding, the Best of Many Worlds. In essence it's a transformation matrix $\boldsymbol{\mathcal{R}}_i$ satisfying the relation $\boldsymbol{\mathcal{R}}_i^{\top}\boldsymbol{\mathcal{R}}_j = \boldsymbol{\mathcal{R}}_{j-i}$. Applying this to $\boldsymbol{q},\boldsymbol{k}$ respectively, we get

\begin{equation}s_{\alpha}(i,j) = (\boldsymbol{\mathcal{R}}_i\boldsymbol{q}_{i,\alpha})^{\top}(\boldsymbol{\mathcal{R}}_j\boldsymbol{k}_{j,\alpha}) = \boldsymbol{q}_{i,\alpha}^{\top} \boldsymbol{\mathcal{R}}_i^{\top}\boldsymbol{\mathcal{R}}_j\boldsymbol{k}_{j,\alpha} = \boldsymbol{q}_{i,\alpha}^{\top} \boldsymbol{\mathcal{R}}_{j-i}\boldsymbol{k}_{j,\alpha}\end{equation}

which explicitly injects relative positional information into the score $s_{\alpha}(i,j)$.

Optimization details

In this section we'll discuss some of the details involved in training GlobalPointer, including the choice of loss function and how to compute and optimize evaluation metrics. Here we'll see that GlobalPointer's entity-centric design brings many elegant conveniences.

Loss function

So far we've designed the score $s_{\alpha}(i,j)$ for recognizing a specific class $\alpha$ of entities, turning this into a multi-label classification problem with $n(n+1)/2$ classes in total. The key next step is designing the loss function. The most naive approach is to decompose this into $n(n+1)/2$ binary classification problems; however, in practice $n$ tends to be quite large, making $n(n+1)/2$ even larger, while the number of entities in each sentence is typically small (often just a single digit per class). So if we use $n(n+1)/2$ binary classifications, we'll run into an extremely severe class imbalance problem.

This is where our earlier work, Generalizing "Softmax + Cross-Entropy" to Multi-Label Classification Problems, comes in handy. In brief, this is a loss function for multi-label classification that generalizes the standard single-target multi-class cross-entropy, and it's particularly well-suited to multi-label classification problems where the total number of classes is large but the number of target classes is small. Its form isn't complicated; in the GlobalPointer setting it becomes

\begin{equation}\log \left(1 + \sum\limits_{(i,j)\in P_{\alpha}} e^{-s_{\alpha}(i,j)}\right) + \log \left(1 + \sum\limits_{(i,j)\in Q_{\alpha}} e^{s_{\alpha}(i,j)}\right)\end{equation}

where $P_{\alpha}$ is the set of (start, end) pairs for all entities of type $\alpha$ in the sample, and $Q_{\alpha}$ is the set of (start, end) pairs for all non-entities or entities not of type $\alpha$ in the sample. Note that we only need to consider combinations where $i\leq j$, i.e.

\begin{equation}\begin{aligned} \Omega=&\,\big\{(i,j)\,\big|\,1\leq i\leq j\leq n\big\}\\ P_{\alpha}=&\,\big\{(i,j)\,\big|\,t_{[i:j]}\text{is of type}\alpha\text{entity of}\big\}\\ Q_{\alpha}=&\,\Omega - P_{\alpha} \end{aligned}\end{equation}

During decoding, any span $t_{[i:j]}$ satisfying $s_{\alpha}(i,j) > 0$ is output as an entity of type $\alpha$. As we can see, the decoding process is extremely simple, and with full parallelism, the decoding complexity is just $\mathcal{O}(1)$!

Evaluation metrics

For NER, the common evaluation metric is F1—specifically entity-level F1, not tag-level F1. With traditional Pointer Network or CRF designs, it's not straightforward to directly compute entity-level F1 during training. But with the GlobalPointer design, computing entity-level F1 or accuracy is quite easy. For instance, F1 can be computed as follows:

def global_pointer_f1_score(y_true, y_pred):
    """给GlobalPointer设计的F1
    """
    y_pred = K.cast(K.greater(y_pred, 0), K.floatx())
    return 2 * K.sum(y_true * y_pred) / K.sum(y_true + y_pred)

That this is so simple is mainly because of GlobalPointer's "globalness"—its y_true and y_pred are already at the entity level. From y_pred > 0 we can directly tell which entities have been extracted, and then simply matching against the gold labels gives us all sorts of (entity-level) metrics, achieving consistency across training, evaluation, and prediction.

Optimizing the F1 score

GlobalPointer's "globalness" offers another benefit: if we use it for reading comprehension, we can directly optimize the F1 metric used in reading comprehension! Reading comprehension F1 differs from NER F1 in that it measures a kind of fuzzy match against the answer, so directly optimizing F1 might be more beneficial for improving the final reading comprehension score. Applying GlobalPointer to reading comprehension is equivalent to NER with just a single entity type. Here we define

\begin{equation}p(i,j) = \frac{e^{s(i,j)}}{\sum\limits_{i \leq j} e^{s(i,j)}}\end{equation}

and once we have $p(i,j)$, borrowing ideas from reinforcement learning (see Policy Gradients and Zeroth-Order Optimization: Different Roads to the Same Destination), we can optimize F1 by using the following loss function:

\begin{equation}-\sum_{i\leq j} p(i,j) f_1(i,j) + \lambda \sum_{i\leq j}p(i,j)\log p(i,j)\end{equation}

Here, $f_1(i,j)$ is the F1 similarity between span $t_{[i:j]}$ and the ground-truth answer, precomputed in advance, and $\lambda$ is a hyperparameter. Of course, computing all the $f_1(i,j)$ values in advance can be somewhat costly, but it's a one-time cost, and some strategies can be applied during computation (e.g., setting the value to zero directly if the start and end are too far apart). Overall, this cost can be kept within an acceptable range. If the goal is to improve the final F1 score for reading comprehension, this is a fairly direct approach worth trying. (I tried this approach in this year's Baidu LIC2021 reading comprehension track, and it indeed showed some benefit.)

Experimental results

Now that everything is ready, let's move on to the experiments. The experimental code is organized as follows:

Open-source repository: https://github.com/bojone/GlobalPointer

GlobalPointer is now built into bert4keras>=0.10.6, so bert4keras users can simply upgrade bert4keras to use it. The three tasks in our experiments are all Chinese NER tasks—the first two are non-nested NER, and the third is nested NER. Here is the text length statistics of their training sets:

$$\begin{array}{c|cc} \hline & \text{average word count} & \text{word count std} \\ \hline \text{People's Daily NER} & 46.93 & 30.08\\ \text{CLUENER} & 37.38 & 10.71\\ \text{CMeEE} & 54.15 & 80.27\\ \hline \end{array}$$

People's Daily

First, let's verify whether GlobalPointer can replace CRF in the non-nested setting, using the classic People's Daily corpus. The baseline is BERT+CRF, compared against BERT+GlobalPointer. The results are as follows:

$$\begin{array}{c} \text{People's Daily NER experiment results} \\ {\begin{array}{c|cc|cc} \hline & \text{val set F1} & \text{test set F1} & \text{training speed} & \text{prediction speed}\\ \hline \text{CRF} & 96.39\% & 95.46\% & 1\text{x} & 1\text{x}\\ \text{GlobalPointer (w/o RoPE)} & 54.35\% & 62.59\% & 1.61\text{x} & 1.13\text{x} \\ \text{GlobalPointer (w/ RoPE)}& 96.25\% & 95.51\% & 1.56\text{x} & 1.11\text{x} \\ \hline \end{array}$$}

\end{array}

The first thing that jumps out visually from this table is undoubtedly the gap between GlobalPointer with and without RoPE—over 30 points! This underscores the importance of explicitly injecting relative positional information into GlobalPointer. In subsequent experiments we will no longer report the version without RoPE, and RoPE will be included by default going forward.

The table also shows that on this classic non-nested NER task, GlobalPointer matches CRF in performance while being faster—both good and fast, so to speak.

CLUENER

Of course, since the classic People's Daily task already has a very high starting point, it might not be able to reveal much of a gap. So let's test on the more recent CLUENER dataset, which is also non-nested, with the current SOTA F1 at around 81%. The comparison between BERT+CRF and BERT+GlobalPointer is as follows:

$$\begin{array}{c} \text{CLUENER results} \\ {\begin{array}{c|cc|cc} \hline & \text{val set F1} & \text{test set F1} & \text{training speed} & \text{prediction speed}\\ \hline \text{CRF} & 79.51\% & 78.70\% & 1\text{x} & 1\text{x}\\ \text{GlobalPointer}& 80.03\% & 79.44\% & 1.22\text{x} & 1\text{x} \\ \hline \end{array}$$}

\end{array}

This result shows that as NER difficulty increases, even in a non-nested setting, GlobalPointer can outperform CRF—suggesting that for NER tasks in general, GlobalPointer is actually more effective than CRF. Later we'll give a simple theoretical analysis further showing why GlobalPointer is theoretically more sound than CRF.

As for speed, since text lengths in this task are generally short, the speedup from GlobalPointer isn't as pronounced.

CMeEE

Finally, let's test on a nested task (CMeEE), which was last year's "Chinese Medical Text Named Entity Recognition" competition on biendata, and is also Task 1 in this year's "Chinese Biomedical Language Understanding Evaluation (CBLUE)." In short, this is medical NER with a certain amount of entity nesting. Again comparing CRF and GlobalPointer:

$$\begin{array}{c} \text{CMeEE results} \\ {\begin{array}{c|cc|cc} \hline & \text{val set F1} & \text{test set F1} & \text{training speed} & \text{prediction speed}\\ \hline \text{CRF} & 63.81\% & 64.39\% & 1\text{x} & 1\text{x}\\ \text{GlobalPointer}& 64.84\% & 65.98\% & 1.52\text{x} & 1.13\text{x} \\ \hline \end{array}$$}

\end{array}

We can see that GlobalPointer clearly outperforms CRF here. As for speed, taking all three tasks together, the general pattern is that the longer the text, the more pronounced the training speedup from GlobalPointer; prediction speed also usually improves somewhat, though not as dramatically as training speed. I subsequently experimented further with RoBERTa-large as the encoder, and found that it could reach over 67% on the online test set without too much difficulty, which shows that GlobalPointer is a "competent" design.

Of course, some readers might object: comparing non-nested CRF against a nested NER task isn't really a fair comparison for GlobalPointer. That's somewhat true, but not a major issue: on one hand, CMeEE's F1 is still relatively low at the moment, and there aren't that many nested entities to begin with—even ignoring the nested portions and treating it as non-nested wouldn't change much; on the other hand, I haven't yet found a simple and clean design specifically for nested NER that could serve as a baseline, so for now I'm just running CRF as a comparison. I'd welcome readers to report comparison results with other designs.

Further reflections

In this section, we'll further compare CRF and GlobalPointer theoretically, and introduce some related work to help readers better understand and situate GlobalPointer.

Compared to CRF

CRF (Conditional Random Field) is a classic design for sequence labeling. Since most NER tasks can be reformulated as sequence labeling problems, CRF is also a classic method for NER. I've previously written posts such as A Concise Introduction to CRF (with a Pure Keras Implementation) and Your CRF Layer's Learning Rate Might Not Be High Enough introducing CRF. As discussed previously, if the number of sequence labeling tags is $k$, then the difference between per-frame softmax and CRF can be summarized as:

The former treats sequence labeling as $n$ separate $k$-class classification problems, while the latter treats sequence labeling as a single $k^n$-class classification problem over $1$ possibilities.

This statement actually reveals the theoretical shortcomings of both per-frame softmax and CRF when applied to NER. How so? Per-frame softmax treats sequence labeling as $n$ separate $k$-class classification problems—this is too lenient, because getting the tag right at a single position doesn't mean the entity has been correctly extracted; at minimum, all tags across an entire span need to be correct for it to count. Conversely, CRF treats sequence labeling as a single classification problem over $1$ $k^n$-class possibilities—this is too strict, because it means all entities must be predicted correctly for the prediction to be considered correct at all; getting only some entities right earns no credit. While in practice CRF-based models can produce partially correct predictions, that's only because the model itself generalizes well—the design of CRF itself does inherently carry the connotation of "all-or-nothing scoring."

So CRF does have theoretically questionable aspects. By comparison, GlobalPointer aligns much more closely with actual usage and evaluation scenarios: it is inherently entity-centric, and it's framed as a "multi-label classification" problem, so both its loss function and its evaluation metric operate at the entity granularity—even getting only part of the entities right earns a reasonable score. This is why it makes sense, "as expected," that GlobalPointer can outperform CRF even in the non-nested NER setting.

Related work

Readers who follow developments in entity recognition and information extraction closely may have noticed that GlobalPointer bears a strong resemblance to TPLinker, a recent relation extraction design. But in fact, this idea of global normalization traces back even further.

For me personally, the first time I encountered this idea was in a 2017 Baidu paper, Globally Normalized Reader, which proposed a globally normalized design (GNR) for reading comprehension. There, instead of treating just (start, end) as a unit, it treats (sentence, start, end) as a unit (the procedure first selects a sentence, and then selects the start and end within that sentence, hence the extra sentence dimension). This results in a very large number of combinations, so the paper also borrowed ideas from Sequence-to-Sequence Learning as Beam-Search Optimization to reduce the computational cost.

With GNR as groundwork, GlobalPointer is a fairly natural next step. In fact, back the year before last, when I was working on the relation extraction track of LIC2019, I had already come up with similar ideas, but at the time several issues remained unresolved.

First, Transformers weren't yet popular at that point, and I found the complexity of $\mathcal{O}(n^2)$ quite daunting. Second, Generalizing "Softmax + Cross-Entropy" to Multi-Label Classification Problems hadn't been worked out yet, so there was no good solution to the class imbalance problem in multi-label classification. Third, my own understanding of various aspects of NLP was still shallow back then, and bert4keras hadn't been developed yet, so I was quite constrained in my experiments and had no idea where to tune things when problems arose (for instance, if I hadn't added RoPE at first and lost over 30 points, two years ago I really wouldn't have had any idea how to fix it).

So, GlobalPointer is something of a "coincidental" yet also "natural" outcome of accumulated experience over the past couple of years. As for TPLinker, it actually has no direct connection to the origins of GlobalPointer. That said, in terms of formulation, GlobalPointer does closely resemble TPLinker, and in fact TPLinker itself can be traced back even further to Joint entity recognition and relation extraction as a multi-head selection problem. It's just that this whole line of work has mainly applied this "global" idea to relation extraction, without specifically optimizing for NER.

Additive vs. multiplicative

In terms of concrete implementation, one key difference between TPLinker and GlobalPointer is that TPLinker uses additive attention in its multi-head design:

\begin{equation}s_{\alpha}(i,j) = \boldsymbol{W}_{o,\alpha}\tanh\left(\boldsymbol{W}_{h,\alpha}[\boldsymbol{h}_{i},\boldsymbol{h}_{j}]+\boldsymbol{b}_{h,\alpha}\right)+\boldsymbol{b}_{o,\alpha} \end{equation}

It's not yet clear how much of a difference this choice makes compared to formula $\eqref{eq:s}$, but compared to the multiplicative attention in formula $\eqref{eq:s}$, even though their theoretical complexities are similar, this kind of additive attention is considerably more expensive to actually compute, especially in terms of space cost (GPU memory)—significantly more so.

So my view is that even if additive attention does perform somewhat better, one should still build on the multiplicative version and continue optimizing from there, because the efficiency of the additive approach really isn't good enough. Furthermore, TPLinker and similar papers haven't reported on the importance of relative positional information the way this post has—does relative position simply matter less in additive attention? That remains unclear for now.

Summary

This post introduced a new design for NER called GlobalPointer, based on the idea of global pointers, incorporating some of my earlier research results, and achieving an "ideal design" that handles both nested and non-nested NER in a unified way. Experimental results show that in the non-nested setting it can match CRF's performance, while in the nested setting it also performs quite well.