Joint Extraction of Entities and Relations Based on a Novel Decomposition Strategy

In plain words

The task is to read a sentence and list facts in the form "first thing, relation, second thing", for example a person, a country the person is president of, and so on. A common approach first finds every name in the sentence, then tests every pair of names to see whether they are related. Most pairs are unrelated, so the model spends its effort on noise, and the two steps can drift apart.

This paper splits the job in two. The first step finds only the names that could start a fact (the "head" entities). The second step runs once per head: it looks for the names that could be the other side of a fact with that head, and labels the relation at the same time. Each question is answered by marking where the answer begins and where it ends in the sentence, a bit like answering a reading-comprehension question by pointing at a span of text.

The model only looks at heads it has already accepted, and it sees the head while it searches for that head's partners. The authors credit their gains to tying each tail to its head and to skipping unrelated pairs.

TL;DR

A two-stage span tagger for joint entity and relation extraction. A shared BiLSTM encodes the sentence; a head-entity tagger finds head spans; for each head, a tail-and-relation tagger marks tail spans with relation labels. Each stage tags start positions first, then end positions. The paper reports new state-of-the-art F1 on NYT-single, NYT-multi and WebNLG (author-reported). The shipped code covers only NYT-multi and WebNLG, and it departs from the paper in several hyperparameters (see Paper vs code).

Problem

Joint extraction must find entity pairs and their relations in one model §1. Two families of methods struggle here:

• Extract-then-classify methods first extract all entities, then classify every pair. Most pairs are non-relations, so the classifier is misled by redundant pairs §1.
• Unified labeling methods tag each sentence once per query word, so they lose the internal structure of a fact (head, relation, tail) §1.

The paper says overlapping relations (several facts sharing an entity) and multi-word entities must both be handled §1§3.1.1.

Method

The paper decomposes the joint task into two subtasks, head-entity (HE) extraction and tail-entity-and-relation (TER) extraction. Each subtask is a sequence labeling problem with span boundaries §1§2.1:

• Tagging scheme §2.1. HE extraction tags the start word and the end word of each head entity with its entity type; all other words get "O". For a given head, TER tags the start and end words of each tail entity with the relation type that links it to the head. For a sentence with m heads the task becomes 2 + 2m tagging subtasks §1. fig. 1 gives the example that the paper uses: the head "Trump" links to "United States" (President of) and to "New York City" (born in) §2.1.
• Hierarchical boundary tagger (HBT) §2.2. The tagger predicts the start label of each token, then predicts the end label conditioned on the start states eq. 2–eq. 7. The probability of a target with label l is factored as a start probability times an end probability given the start eq. 1. The end tagger also receives a position feature: the distance from the token to the nearest predicted start eq. 8. During training the gold start positions are used for this feature, which avoids error propagation §2.2. The paper's loss is the average over tokens of the negative log-likelihood of the gold start and end tags eq. 9.
• Shared encoder §2.3.1. A BiLSTM reads each token representation, built from pretrained word vectors, a character CNN and POS embeddings eq. 10. POS embeddings follow a prior graph-based relation extractor §2.3.1.
• HE extractor §2.3.2. The token state is concatenated with a global sentence vector computed by max-pooling over all hidden states. That vector also feeds the start and end taggers as the auxiliary input §2.3.2 eq. 2.
• TER extractor §2.3.3. For a given head, each token gets a head-aware input: its own state, the global vector, the head's start and end states, and the relative distance from the token to the head eq. 12. The same HBT then tags tail boundaries with relation labels eq. 13. Triples are assembled by pairing the head with each tail and its relation §2.3.3.
• Inference §2.3.3alg. 1. Heads are decoded from the predicted start and end tags, and then the TER pass runs once per predicted head. Multi-span decoding scans the start tags left to right; for each non-O start it takes the first later end tag with the same label as the span, and then continues scanning alg. 1. The paper gives the algorithm in pseudocode alg. 1.
• Training §2.3.4. The total loss is the sum of the HE loss and the TER loss with equal weight eq. 14. For each training sentence one gold head is drawn at random and used as the TER input; repeating sentences per head did not help, according to the authors §2.3.4.

# ETL-Span: heads first, then tails and relations  [§2.3] [alg. 1]
# Input: tokens (n words); Output: set of (head, relation, tail) triples

def extract_triples(tokens):
    # Shared BiLSTM over word, char-CNN and POS features  [§2.3.1] [eq. 10]
    hidden = shared_bilstm(tokens)                    # (n, 2h)
    # Global vector: max pooling over positions  [§2.3.2]
    sentence_rep = max_over_positions(hidden)         # (2h,)
    # Head starts first, 0 meaning O  [§2.2] [eq. 2-4]
    head_starts = argmax(head_start_scores(hidden, sentence_rep))
    # Head ends see the distance to the nearest predicted start  [eq. 5-8]
    head_ends = argmax(head_end_scores(hidden, sentence_rep, head_starts))
    # Pair each start with the first matching end  [alg. 1]
    heads = decode_spans(head_starts, head_ends)
    triples = []
    for head in heads:
        # Head-aware input: states at head boundaries, distance  [eq. 12]
        ter_input = tail_features(hidden, sentence_rep, head)
        # Tail starts carry relation labels, same two-stage tagger  [eq. 13]
        tail_starts = argmax(tail_start_scores(ter_input))
        tail_ends = argmax(tail_end_scores(ter_input, tail_starts))
        for tail, relation in decode_spans(tail_starts, tail_ends):
            triples.append((head, relation, tail))
    return triples

Key equations, as given in the paper:

p(t,l \mid S) = p(s_t^{l} \mid S)\, p(e_t^{l} \mid s_t^{l}, S) eq. 1

p^{se}_i = \begin{cases} i - s^{*}, & \text{if } s^{*} \text{ exists} \\ C, & \text{otherwise} \end{cases} eq. 8

\mathcal{L}_{HBT} = -\frac{1}{n} \sum_{i=1}^{n} \left( \log P(y^{sta}_i = \hat{y}^{sta}_i) + \log P(y^{end}_i = \hat{y}^{end}_i) \right) eq. 9

\mathcal{L} = \mathcal{L}_{HE} + \mathcal{L}_{TER} eq. 14

Hyperparameters

Values in the Value column are the paper's unless the Where column says otherwise. Code values are in Paper vs code.

Results

Author-reported. Setup: three public datasets. NYT-single (distant supervision for training, 395 manual test sentences) §3.1.1, NYT-multi (test set of 5,000 sentences, from Zeng et al.) §3.1.1, and WebNLG (5,019 training and 703 test sentences) §3.1.1. Metric: micro precision, recall and F1, where a triple is correct only if the relation and both entity boundaries match §3.1.2. Hardware and batch size for the speed comparison are not stated.

Main test results tab. 2:

The paper reports 5.2, 5.9 and 21.5 F1 points over the best baselines on the three datasets (see the Pitfalls for how these are worded). The ETL-BIES variant (the same design with a BiLSTM-CRF tagger and BIES tags §3.1.4) reaches 57.2, 77.4 and 82.3 F1 tab. 2.

Test-time speed tab. 3: ETL-Span processes 26.1, 25.6 and 23.5 batches per second on NYT-single, NYT-multi and WebNLG; ETL-BIES processes 10.9, 11.2 and 6.3 tab. 3. The text also says that ETL-Span needs about a quarter of the time per training batch and a fifth of the GPU memory of ETL-BIES §3.2.1; no table backs these two numbers.

Ablation on the NYT-multi dev set tab. 4, F1 relative to the full model at 79.5:

Analysis by sentence type §3.2.3fig. 3fig. 4: on NYT-multi, the paper reports gains over OrderRL on Normal (6.1 points) and single-entity-overlap (6.9 points) sentences, and a small gain on entity-pair-overlap sentences (0.6 points). The authors say the model does not solve entity-pair overlap and leave it for future work §3.2.3. The paper also reports consistent gains across sentences with one to five or more triples fig. 4 §3.2.3.

Paper vs code

The official code is at the repository linked in the paper's conclusion §5, pinned at code_commit. The shipped code and configs cover NYT-multi and WebNLG only. Several differences matter when you reimplement:

• Gradient clipping. The paper sets clip-norm 5 §3.1.3. The training step computes the loss and calls the optimizer step without clipping; the clipping call is commented out model.py. The max_grad_norm flag exists but is never used train.py.
• Embedding sizes. The paper uses 30-d POS, character and position embeddings §3.1.3. The code defaults are 20 (POS), 100 (character) and 20 (position) train.py.
• Char CNN. The paper uses 50 filters with window 3 §3.1.3. The code uses 100 filters with kernel size 3 layers.py train.py.
• BiLSTM size. The paper says the hidden vector length is 100 §3.1.3. The code default is 200 per direction (bidirectional=True, so 400 concatenated) train.py model.py. The sub-taggers use 200 units per direction submodel.py. The paper may mean 100 per direction; the code does not match either reading exactly.
• Position feature cap. The paper defines the no-start constant as the maximum sentence length eq. 8. The code caps the distance at 10 tokens: any larger distance gets index 499, which is also the "no start" index loader.py. The distance embedding table has 500 rows submodel.py. An end token more than 10 tokens after its start therefore loses the length signal the paper relies on.
• Loss normalization. The paper averages the per-token losses per sentence eq. 9. The code sums masked token losses and divides by the total number of tokens in the batch model.py. Sentences of different lengths are weighted differently in the two schemes.
• Long sentences. Training skips any sentence longer than 150 tokens loader.py. The paper does not mention this.
• Head sampling. The code draws one gold head per sentence and fixes it when the dataset is built, so every epoch uses the same head loader.py loader.py. Batches are also shuffled once and reused each epoch loader.py train.py train.py. The paper says the head is drawn at random per instance §2.3.4.
• Type labels. For entities with several types, the code draws one type at random when the dataset is built and keeps it loader.py loader.py. The paper does not state how multi-type entities are labeled.
• Word dropout. A word-dropout rate of 0.04 is parsed train.py but not used anywhere in the code. The paper does not mention word dropout.
• Runs. The paper averages 5 runs §3.1.3. The code runs one seed (35) train.py.
• Epochs and checkpoint selection. The paper does not state either. The code trains 50 epochs and keeps the checkpoint with the best dev F1 train.py train.py.
• GloVe version. The paper cites GloVe §3.1.3 without a version. The download script fetches the 840B-token, 300-d release download.sh prepare_data.py.
• Datasets. The paper reports NYT-single §3.2.1tab. 2. The repository ships data only for NYT-multi and WebNLG . The WebNLG config has 211 relation classes config.json, but the paper's Table 1 lists 246 relation types for WebNLG tab. 1.
• Evaluation criterion. The paper says a correct entity needs correct head and tail offsets §3.1.2. The code compares surface strings: predicted triples are sets of (subject text, relation, object text) and are intersected with the gold strings score.py score.py. Two mentions with the same text but different positions count as one.
• Inference is CUDA-only. The prediction helpers hard-code .cuda() model.py model.py. The CPU branch of the subject prediction refers to an undefined variable model.py. A CPU reimplementation needs fixing before it runs.
• Reproduction of the reported ablation row. The shipped NYT-multi training log has its best dev F1 of 0.7949 at epoch 41, with precision 86.5 and recall 73.5 logs.txt. These match the paper's ETL-Span row in tab. 4. The shipped WebNLG log has its best dev F1 of 0.8359 at epoch 35 logs.txt. The test results are not reproduced: the shipped best_test_results.json files hold predicted triples, not scores, and no checkpoint is shipped, so eval.py cannot be run from the repository.

What matches: the decoding procedure in utils/score.py follows the multi-span rule of alg. 1. Subject and object spans start at the first start tag and end at the first later end tag with the same label score.py score.py. Training uses gold start positions for the distance feature loader.py. Adam, learning rate 0.001, batch size 64, dropout 0.4 and equal loss weights match the paper train.py train.py train.py train.py train.py.

Pitfalls

• Wording of the margins. The paper calls the NYT-single gain "a relative margin of 5.2%" §3.2.1, but 59.0 − 53.8 = 5.2 is an absolute F1 difference. The same holds for the 16.1 and 40.2 points over GraphRel §3.2.1 and for the ablation drops (for example 79.5 − 75.7 = 3.8). Read these as F1 points.
• Headline test F1 is not reproducible here. The ablation rows reproduce from the shipped dev logs, but the headline test F1 values cannot be checked from this repository (see Paper vs code).
• Position cap. The paper says the constant C limits entity length, but gives no numeric cap; it only defines C as the maximum sentence length eq. 8 §2.2. The released code caps the distance at 10 and reuses index 499 for both "too far" and "no start" loader.py. Pick one convention deliberately and test entities longer than 10 tokens.
• Exposure bias. Training uses gold start positions for the distance feature, while inference uses predicted starts §2.2 loader.py model.py. The paper argues this avoids error propagation, but it leaves a train/test mismatch.
• Cost scales with predicted heads. Each predicted head runs a full TER pass over the sentence §2.3.3. A sentence with many predicted heads costs proportionally more at inference; the speed table covers only the benchmark sentences tab. 3.
• Entity-pair overlap. The authors say the model cannot separate triples that share both the same head and the same tail, and they leave this case for future work §3.2.3.
• Span decoding. Multi-span decoding pairs each start with the first later end of the same label alg. 1. Read literally, this means two same-label spans that start at the same token cannot both be recovered. The paper does not discuss this case.
• Precision on NYT-single. The paper says precision drops against NovelTagging on NYT-single, and offers as a possible reason that many overlapping relations are not annotated in the test data §3.2.1. It also reports a 12.5-point F1 gain after adding gold triples to the NYT-single test set §3.2.1. Treat these as author observations, not benchmark results.

Lineage

• Builds on: the position-embedding idea from Zeng et al. (2014), used for the end tagger's distance feature §2.2; span-based answer extraction from machine reading comprehension (Seo et al., 2016) §2.1; and POS embeddings following a graph-based relation extractor (Fu et al., 2019) §2.3.1.
• Compared against (author-reported numbers from tab. 2): NovelTagging (Zheng et al., 2017), MultiDecoder (Zeng et al., 2018), MultiHead (Bekoulis et al., 2018), PA-LSTM (Dai et al., 2019), GraphRel (Fu et al., 2019), OrderRL (Zeng et al., 2019), and CoType (Ren et al., 2017).
• Superseded by: not stated in this card.