<Berlin, Germany, country>
SEO |  | Dr. C. V. Raman who
---
was born in Chennai
worked mostly in
Kolkata.
| <Dr. C. V. Raman, Chennai, birth_place>
---
<Dr. C. V. Raman, Kolkata, place_lived>
Table 5.2: Examples of different classes of overlapping relation tuples.

###  5.3 Model Description

In this task, the input to the system is a sequence of words, and the output
is a set of relation tuples. In our first approach, we represent each tuple as
entity1 ; entity2 ; relation. We use ‘;’ as a separator token to separate the
tuple components. Multiple tuples are separated using the ‘$|$’ token. We have
included one example of such representation in Table 5.1. Multiple relation
tuples with overlapping entities and different lengths of entities can be
represented in a simple way using these special tokens (; and $|$). During
inference, after the end of sequence generation, relation tuples can be
extracted easily using these special tokens. Due to this uniform
representation scheme, where entity tokens, relation tokens, and special
tokens are treated similarly, we use a shared vocabulary between the encoder
and decoder which includes all of these tokens. The input sentence contains
clue words for every relation which can help generate the relation tokens. We
use two special tokens so that the model can distinguish between the beginning
of a relation tuple and the beginning of a tuple component. To extract the
relation tuples from a sentence using the encoder-decoder model, the model has
to generate the entity tokens, find the clue words for the relations, map them
to the relation tokens, and generate the special tokens at appropriate time.
Our experiments show that the encoder-decoder models can achieve this quite
effectively.

####  5.3.1 Embedding Layer & Encoder

We create a single vocabulary $V$ consisting of the source sentence tokens,
relation names from relation set $R$, special separator tokens (‘;’, ‘$|$’),
start-of-target-sequence token (SOS), end-of-target-sequence token (EOS), and
unknown word token (UNK). Word-level embeddings are formed by two components:
(1) pre-trained word vectors (2) character embedding-based feature vectors. We
use a word embedding layer $\mathbf{E}_{w}\in\mathbb{R}^{|V|\times d_{w}}$ and
a character embedding layer $\mathbf{E}_{c}\in\mathbb{R}^{|A|\times d_{c}}$,
where $d_{w}$ is the dimension of word vectors, $A$ is the character alphabet
of input sentence tokens, and $d_{c}$ is the dimension of character embedding
vectors. Following Chiu and Nichols (2016), we use a convolutional neural
network with max-pooling to extract a feature vector of size $d_{f}$ for every
word. Word embeddings and character embedding-based feature vectors are
concatenated ($\|$) to obtain the representation of the input tokens.

A source sentence $\mathbf{S}$ is represented by vectors of its tokens
$\mathbf{x}_{1},\mathbf{x}_{2},....,\mathbf{x}_{n}$, where
$\mathbf{x}_{i}\in\mathbb{R}^{(d_{w}+d_{f})}$ is the vector representation of
the $i$th word and $n$ is the length of $\mathbf{S}$. These vectors
$\mathbf{x}_{i}$ are passed to a bi-directional LSTM (Hochreiter and
Schmidhuber, 1997) (Bi-LSTM) to obtain the hidden representation
$\mathbf{h}_{i}^{E}$. We set the hidden dimension of the forward and backward
LSTM of the Bi-LSTM to be $d_{h}/2$ to obtain
$\mathbf{h}_{i}^{E}\in\mathbb{R}^{d_{h}}$, where $d_{h}$ is the hidden
dimension of the sequence generator LSTM of the decoder described below.

####  5.3.2 Word-level Decoder & Copy Mechanism

A target sequence $\mathbf{T}$ is represented by only word embedding vectors
of its tokens $\mathbf{y}_{0},\mathbf{y}_{1},....,\mathbf{y}_{m}$ where
$\mathbf{y}_{i}\in\mathbb{R}^{d_{w}}$ is the embedding vector of the $i$th
token and $m$ is the length of the target sequence. $\mathbf{y}_{0}$ and
$\mathbf{y}_{m}$ represent the embedding vector of the SOS and EOS token
respectively. The decoder generates one token at a time and stops when EOS is
generated. We use an LSTM as the decoder and at time step $t$, the decoder
takes the source sentence encoding, $\mathbf{e}_{t}\in\mathbb{R}^{d_{h}}$, and
the previous target word embedding, $\mathbf{y}_{t-1}$, as the input and
generates the hidden representation of the current token
($\mathbf{h}_{t}^{D}\in\mathbb{R}^{d_{h}}$). The sentence encoding vector
$\mathbf{e}_{t}$ can be obtained using attention mechanism.
$\mathbf{h}_{t}^{D}$ is projected to the vocabulary $V$ using a linear layer
with weight matrix $\mathbf{W}_{v}\in\mathbb{R}^{|V|\times d_{h}}$ and bias
vector $\mathbf{b}_{v}\in\mathbb{R}^{|V|}$ (projection layer). $\|$ refers to
the concatenation operation.

$\displaystyle\mathbf{h}_{t}^{D}=\mathrm{LSTM}(\mathbf{e}_{t}\|\mathbf{y}_{t-1},\mathbf{h}_{t-1}^{D})$
$\displaystyle\hat{\mathbf{o}}_{t}=\mathbf{W}_{v}\mathbf{h}_{t}^{D}+\mathbf{b}_{v}$
$\displaystyle\mathbf{o}_{t}=\mathrm{softmax}(\hat{\mathbf{o}}_{t})$ (5.1)

$\mathbf{o}_{t}$ represents the normalized scores of all the words in the
embedding vocabulary at time step $t$. $\mathbf{h}_{t-1}^{D}$ is the previous
hidden state of the LSTM.

The projection layer of the decoder maps the decoder output to the entire
vocabulary. During training, we use the gold label target tokens directly.
However, during inference, the decoder may predict a token from the vocabulary
which is not present in the current sentence or the set of relations or the
special tokens. To prevent this, we use a masking technique while applying the
softmax operation at the projection layer. We mask (exclude) all words of the
vocabulary except the current source sentence tokens, relation tokens,
separator tokens (‘;’, ‘$|$’), UNK, and EOS tokens in the softmax operation.
To mask (exclude) some word from softmax, we set the corresponding value in
$\hat{\mathbf{o}}_{t}$ at $-\infty$ and the corresponding softmax score will
be zero. This ensures the copying of entities from the source sentence only.
We include the UNK token in the softmax operation to make sure that the model
generates new entities during inference. If the decoder predicts an UNK token,
we replace it with the corresponding source word which has the highest
attention score. During inference, after decoding is finished, we extract all
tuples based on the special tokens, remove duplicate tuples and tuples in
which both entities are the same or tuples where the relation token is not
from the relation set. This model is referred to as WordDecoding (WDec)
henceforth.

####  5.3.3 Pointer Network-Based Decoder

In the second approach, we identify the entities in the sentence using their
start and end locations. We remove the special tokens and relation names from
the word vocabulary and word embeddings are used only at the encoder side
along with character embeddings. We use an additional relation embedding
matrix $\mathbf{E}_{r}\in\mathbb{R}^{|R|\times d_{r}}$ at the decoder side of
our model, where $R$ is the set of relations and $d_{r}$ is the dimension of
relation vectors. The relation set $R$ includes a special relation token EOS
which indicates the end of the sequence. Relation tuples are represented as a
sequence $T=y_{0},y_{1},....,y_{m}$, where $y_{t}$ is a tuple consisting of
four indexes in the source sentence indicating the start and end location of
the two entities and a relation between them (see Table 5.1). $y_{0}$ is a
dummy tuple that represents the start tuple of the sequence and $y_{m}$
functions as the end tuple of the sequence which has EOS as the relation
(entities are ignored for this tuple). The decoder consists of an LSTM with
hidden dimension $d_{h}$ to generate the sequence of tuples, two pointer
networks to find the two entities, and a classification network to find the
relation of a tuple. At time step $t$, the decoder takes the source sentence
encoding, $\mathbf{e}_{t}\in\mathbb{R}^{d_{h}}$, and the representation of all
previously generated tuples $\mathbf{y}_{prev}$ (Eq. (5.2)) as the input and
generates the hidden representation of the current tuple,
$\mathbf{h}_{t}^{D}\in\mathbb{R}^{d_{h}}$ (Eq. (5.3)). The sentence encoding
vector $\mathbf{e}_{t}$ is obtained using an attention mechanism as explained
later. Relation tuples are a set and to prevent the decoder from generating
the same tuple again, we pass the information about all previously generated
tuples at each time step of decoding. $\mathbf{y}_{j}$ is the vector
representation of the tuple predicted at time step $j<t$ and we use the zero
vector ($\mathbf{y}_{0}=\overrightarrow{0}$) to represent the dummy tuple
$y_{0}$. $\mathbf{h}_{t-1}^{D}$ is the hidden state of the LSTM at time step
$t-1$. $\|$ refers to the concatenation operation.

$\displaystyle\mathbf{y}_{prev}=\sum_{j=0}^{t-1}\mathbf{y}_{j}$ (5.2)
$\displaystyle\mathbf{h}_{t}^{D}=\mathrm{LSTM}(\mathbf{e}_{t}\|\mathbf{y}_{prev},\mathbf{h}_{t-1}^{D})$
(5.3)

Figure 5.1: The architecture of an encoder-decoder model (left) and a pointer
network-based decoder block (right).

##### Relation Tuple Extraction

After obtaining the hidden representation of the current tuple
$\mathbf{h}_{t}^{D}$, we first find the start and end pointers of the two
entities in the source sentence. We concatenate the vector
$\mathbf{h}_{t}^{D}$ with the hidden vectors $\mathbf{h}_{i}^{E}$ of the
encoder and pass them to a Bi-LSTM layer with hidden dimension $d_{p}$ for
forward and backward LSTM. The hidden vectors of this Bi-LSTM layer
$\mathbf{h}_{i}^{k}\in\mathbb{R}^{2d_{p}}$ are passed to two feed-forward
networks (FFN) with softmax (Eq. (5.4) to Eq. (5.7)) to convert each hidden
vector into two scalar values between $0$ and $1$. The softmax operation is
applied across all the words in the input sentence. These two scalar values
represent the probability of the corresponding source sentence token to be the
start and end location of the first entity. This Bi-LSTM layer with the two
feed-forward layers (the blue block in Figure 5.1) is the first pointer
network which identifies the first entity of the current relation tuple.

$\displaystyle\hat{s}_{i}^{1}=\mathbf{W}_{s}^{1}\mathbf{h}_{i}^{k}+{b}_{s}^{1}$
(5.4) $\displaystyle\mathbf{s}^{1}=\mathrm{softmax}(\hat{\mathbf{s}}^{1})$
(5.5)
$\displaystyle\hat{e}_{i}^{1}=\mathbf{W}_{e}^{1}\mathbf{h}_{i}^{k}+{b}_{e}^{1}$
(5.6) $\displaystyle\mathbf{e}^{1}=\mathrm{softmax}(\hat{\mathbf{e}}^{1})$
(5.7)

where $\mathbf{W}_{s}^{1}\in\mathbb{R}^{1\times 2d_{p}}$,
$\mathbf{W}_{e}^{1}\in\mathbb{R}^{1\times 2d_{p}}$, ${b}_{s}^{1}$, and
${b}_{e}^{1}$ are the weights and bias parameters of the feed-forward layers.
${s}_{i}^{1}$, ${e}_{i}^{1}$ represent the normalized probabilities of the
$i$th source word being the start and end token of the first entity of the
predicted tuple. We use another pointer network (the red block in Figure 5.1)
to extract the second entity of the tuple. We concatenate the hidden vectors
$\mathbf{h}_{i}^{k}$ with $\mathbf{h}_{t}^{D}$ and $\mathbf{h}_{i}^{E}$ and
pass them to the second pointer network to obtain ${s}_{i}^{2}$ and
${e}_{i}^{2}$, which represent the normalized probabilities of the $i$th
source word being the start and end of the second entity. These normalized
probabilities are used to find the vector representation of the two entities,
$\mathbf{a}_{t}^{1}$ (Eq. (5.8)) and $\mathbf{a}_{t}^{2}$ (Eq. (5.9)).

$\displaystyle\mathbf{a}_{t}^{1}=\sum_{i=1}^{n}{s}_{i}^{1}\mathbf{h}_{i}^{k}\|\sum_{i=1}^{n}{e}_{i}^{1}\mathbf{h}_{i}^{k}$
(5.8)
$\displaystyle\mathbf{a}_{t}^{2}=\sum_{i=1}^{n}{s}_{i}^{2}\mathbf{h}_{i}^{l}\|\sum_{i=1}^{n}{e}_{i}^{2}\mathbf{h}_{i}^{l}$
(5.9)

We concatenate the entity vector representations $\mathbf{a}_{t}^{1}$ and
$\mathbf{a}_{t}^{2}$ with $\mathbf{h}_{t}^{D}$ and pass it to a feed-forward
network (FFN) with softmax to find the relation (Eq. (5.10)). This feed-
forward layer has a weight matrix
$\mathbf{W}_{r}\in\mathbb{R}^{|R|\times(8d_{p}+d_{h})}$ and a bias vector
$\mathbf{b}_{r}\in\mathbb{R}^{|R|}$.

$\displaystyle\mathbf{r}_{t}=\mathrm{softmax}(\mathbf{W}_{r}(\mathbf{a}_{t}^{1}\|\mathbf{a}_{t}^{2}\|\mathbf{h}_{t}^{D})+\mathbf{b}_{r})$
(5.10)
$\displaystyle\mathbf{z}_{t}=\mathbf{E}_{r}(\mathrm{argmax}(\mathbf{r}_{t}))$
(5.11)
$\displaystyle\mathbf{y}_{t}=\mathbf{a}_{t}^{1}\|\mathbf{a}_{t}^{2}\|\mathbf{z}_{t}$
(5.12)

$\mathbf{r}_{t}$ represents the normalized probabilities of the relation at
time step $t$. The relation embedding vector $\mathbf{z}_{t}$ is obtained
using $\mathrm{argmax}$ of $\mathbf{r}_{t}$ and $\mathbf{E}_{r}$ (Eq. (5.11)).
$\mathbf{y}_{t}\in\mathbb{R}^{(8d_{p}+d_{r})}$ (Eq. (5.12)) is the vector
representation of the tuple predicted at time step $t$. During training, we
pass the embedding vector of the gold label relation in place of the predicted
relation. So the $\mathrm{argmax}$ function does not affect the back-
propagation during training. The decoder stops the sequence generation process
when the predicted relation is EOS. This is the classification network of the
decoder.

During inference, we select the start and end location of the two entities
such that the product of the four pointer probabilities is maximized keeping
the constraints that the two entities do not overlap with each other and
$1\leq b\leq e\leq n$ where $b$ and $e$ are the start and end location of the
corresponding entities. We first choose the start and end location of entity 1
based on the maximum product of the corresponding start and end pointer
probabilities. Then we find entity 2 in a similar way excluding the span of
entity 1 to avoid overlap. The same procedure is repeated but this time we
first find entity 2 followed by entity 1. We choose that pair of entities
which gives the higher product of four pointer probabilities between these two
choices. This model is referred to as PtrNetDecoding (PNDec) henceforth.

####  5.3.4 Attention Modeling

We experimented with three different attention mechanisms for our word-level
decoding model to obtain the source context vector $\mathbf{e}_{t}$:

(1) Avg.: The context vector is obtained by averaging the hidden vectors of
the encoder:

$\displaystyle\mathbf{e}_{t}=\frac{1}{n}\sum_{i=1}^{n}\mathbf{h}_{i}^{E}$
(5.13)

(2) N-gram: The context vector is obtained by the N-gram attention mechanism
of Trisedya et al. (2019) with N=3. This attention mechanism can be helpful to
identify the multi-token entities.

$\displaystyle\textnormal{a}_{i}^{g}=(\mathbf{h}_{n}^{E})^{T}\mathbf{V}^{g}\mathbf{w}_{i}^{g}$
$\displaystyle\boldsymbol{\alpha}^{g}=\mathrm{softmax}(\mathbf{a}^{g})$
$\displaystyle\mathbf{e}_{t}=[\mathbf{h}_{n}^{E}\|\sum_{g=1}^{N}\mathbf{W}^{g}(\sum_{i=1}^{|G^{g}|}\alpha_{i}^{g}\mathbf{w}_{i}^{g})]$
(5.14)

Here, $\mathbf{h}_{n}^{E}$ is the last hidden state of the encoder,
$g\in\\{1,2,3\\}$ refers to the word gram combination, $G^{g}$ is the sequence
of g-gram word representations for the input sentence, $\mathbf{w}_{i}^{g}$ is
the $i$th g-gram vector (2-gram and 3-gram representations are obtained by
average pooling), $\alpha_{i}^{g}$ is the normalized attention score for the
$i$th g-gram vector, $\mathbf{W}\in\mathbb{R}^{d_{h}\times d_{h}}$ and
$\mathbf{V}\in\mathbb{R}^{d_{h}\times d_{h}}$ are trainable parameters.
(3) Single: The context vector is obtained by the attention mechanism proposed
by Bahdanau et al. (2015). This attention mechanism gives the best performance
with the word-level decoding model.

$\displaystyle\mathbf{u}_{t}^{i}=\mathbf{W}_{u}\mathbf{h}_{i}^{E}$
$\displaystyle\mathbf{q}_{t}^{i}=\mathbf{W}_{q}\mathbf{h}_{t-1}^{D}+\mathbf{b}_{q}$
$\displaystyle\textnormal{a}_{t}^{i}=\mathbf{v}_{a}\tanh(\mathbf{q}_{t}^{i}+\mathbf{u}_{t}^{i})$
$\displaystyle\boldsymbol{\alpha}_{t}=\mathrm{softmax(\mathbf{a}_{t})}$
$\displaystyle\mathbf{e}_{t}=\sum_{i=1}^{n}\alpha_{t}^{i}\mathbf{h}_{i}^{E}$
(5.15)

where $\mathbf{W}_{u}\in\mathbb{R}^{d_{h}\times d_{h}}$,
$\mathbf{W}_{q}\in\mathbb{R}^{d_{h}\times d_{h}}$, and
$\mathbf{v}_{a}\in\mathbb{R}^{d_{h}}$ are all trainable attention parameters
and $\mathbf{b}_{q}\in\mathbb{R}^{d_{h}}$ is a bias vector. $\alpha_{t}^{i}$
is the normalized attention score of the $i$th source word at the decoding
time step $t$.

For our pointer network-based decoding model, we use three variants of the
single attention model. First, we use $\mathbf{h}_{t-1}^{D}$ to calculate
$\mathbf{q}_{t}^{i}$ in the attention mechanism. Next, we use
$\mathbf{y}_{prev}$ to calculate $\mathbf{q}_{t}^{i}$, where
$\mathbf{W}_{q}\in\mathbb{R}^{(8d_{p}+d_{r})\times d_{h}}$. In the final
variant, we obtain the attentive context vector by concatenating the two
attentive vectors obtained using $\mathbf{h}_{t-1}^{D}$ and
$\mathbf{y}_{prev}$. This gives the best performance with the pointer network-
based decoding model. These variants are referred to as $\mathrm{dec_{hid}}$,
$\mathrm{tup_{prev}}$, and $\mathrm{combo}$ in Table 5.5.

####  5.3.5 Loss Function

We minimize the negative log-likelihood loss of the generated words for word-
level decoding ($\mathcal{L}_{word}$) (Eq. (5.16)) and minimize the sum of
negative log-likelihood loss of relation classification and the four pointer
locations for pointer network-based decoding ($\mathcal{L}_{ptr}$) (Eq.
(5.17)).

$\displaystyle\mathcal{L}_{word}=-\frac{1}{B\times
T}\sum_{b=1}^{B}\sum_{t=1}^{T}\text{log}(v_{t}^{b})$ (5.16)
$\displaystyle\mathcal{L}_{ptr}=-\frac{1}{B\times
T}\sum_{b=1}^{B}\sum_{t=1}^{T}[\text{log}(r_{t}^{b})+\sum_{c=1}^{2}\text{log}(s_{c,t}^{b}e_{c,t}^{b})]$
(5.17)

$v_{t}^{b}$ is the softmax score of the target word at time step $t$ for the
word-level decoding model. $r$, $s$, and $e$ are the softmax score of the
corresponding true relation label, true start and end pointer location of an
entity. $b$, $t$, and $c$ refer to the $b$th training instance, $t$th time
step of decoding, and the two entities of a tuple respectively. $B$ and $T$
are the batch size and maximum time step of the decoder respectively.

###  5.4 Experiments

####  5.4.1 Datasets

We focus on the task of extracting multiple tuples with overlapping entities
from sentences. We choose the New York Times (NYT) corpus for our experiments.
This corpus has multiple versions, and we choose the following two versions as
their test dataset has a significantly larger number of instances of multiple
relation tuples with overlapping entities. (i) The first version is used by
Zeng et al. (2018) (mentioned as NYT in their paper) and has $24$ relations.
We name this version as NYT24. This dataset is derived from the NYT11 dataset
of the previous chapter. The test data of NYT11 do not have any sentences with
multiple tuples or overlapping tuples. But the training data of NYT11 have
such sentences. So they split the training data of NYT11 to create the test
data for the joint extraction task. (ii) The second version is used by
Takanobu et al. (2019) (mentioned as NYT10 in their paper) and has $29$
relations. We name this version as NYT29. This dataset is derived from the
NYT10 dataset of the previous chapter. They remove those relations from the
dataset which do not appear in the test dataset. We select 10% of the original
training data and use it as the validation dataset. The remaining 90% is used
for training. We include statistics of the training and test datasets in Table
5.3. Both NYT24 and NYT29 datasets do not contain any sentence with zero
positive tuples.

| NYT29 | NYT24
---|---|---
| Train | Test | Train | Test
#relations | 29 | 29 | 24 | 24
#sentences | 63,306 | 4,006 | 56,196 | 5,000
#tuples | 78,973 | 5,859 | 88,366 | 8,120
#Entity overlap type |  |  |  |
NEO | 53,444 | 2,963 | 37,371 | 3,289
EPO | 8,379 | 898 | 15,124 | 1,410
SEO | 9,862 | 1,043 | 18,825 | 1,711
#tuples in a sentence |  |  |  |
1 | 53,001 | 2,950 | 36,835 | 3,240
2 | 6,154 | 595 | 12,065 | 1,047
3 | 3,394 | 187 | 3,672 | 314
4 | 450 | 239 | 2,623 | 290
$\geq 5$ | 307 | 35 | 1,001 | 109

Table 5.3: Statistics of train/test split of the two datasets.

####  5.4.2 Evaluation Metrics

We use the same evaluation method used by Takanobu et al. (2019) in their
experiments. We consider the extracted tuples as a set and remove the
duplicate tuples. An extracted tuple is considered as correct if the
corresponding full entity names are correct and the relation is also correct.
We report precision, recall, and F1 score for comparison.

####  5.4.3 Parameter Settings

We run the Word2Vec (Mikolov et al., 2013) tool on the NYT corpus to
initialize the word embeddings. The character embeddings and relation
embeddings are initialized randomly. All embeddings are updated during
training. We set the word embedding dimension $d_{w}=300$, relation embedding
dimension $d_{r}=300$, character embedding dimension $d_{c}=50$, and
character-based word feature dimension $d_{f}=50$. To extract the character-
based word feature vector, we set the CNN filter width at $3$ and the maximum
length of a word at $10$. The hidden dimension $d_{h}$ of the decoder LSTM
cell is set at $300$ and the hidden dimension of the forward and the backward
LSTM of the encoder is set at $150$. The hidden dimension of the forward and
backward LSTM of the pointer networks is set at $d_{p}=300$. The model is
trained with mini-batch size of $32$ and the network parameters are optimized
using Adam (Kingma and Ba, 2015). Dropout layers with a dropout rate fixed at
$0.3$ are used in our network to avoid overfitting.

####  5.4.4 Baselines

We compare our model with the following state-of-the-art joint entity and
relation extraction models:

(1) SPTree (Miwa and Bansal, 2016): This model is an end-to-end neural entity
and relation extraction model using a sequence LSTM and a tree LSTM. The
sequence LSTM identifies all the entities first, and then the tree LSTM finds
the relation between all pairs of entities. They bring these two tasks
together using shared parameters. Although this is an end-to-end model, entity
detection and relation classification are still performed separately.

(2) Tagging (Zheng et al., 2017): This is a neural sequence tagging model
which jointly extracts the entities and relations using an LSTM encoder and an
LSTM decoder. They used a Cartesian product of entity tags and relation tags
to encode the entity and relation information together. This model does not
work when tuples have overlapping entities.

(3) CopyR (Zeng et al., 2018): This model uses an encoder-decoder approach for
the joint extraction of entities and relations. It copies only the last token
of an entity from the source sentence. Their best performing multi-decoder
model is trained with a fixed number of decoders where each decoder extracts
one tuple. Since there is a separate decoder for each tuple, interaction among
the tuples is very limited in this model.

(4) HRL (Takanobu et al., 2019): This model uses a reinforcement learning (RL)
algorithm with two levels of hierarchy for tuple extraction. A high-level RL
finds the relation and a low-level RL identifies the two entities using a
sequence tagging approach. This sequence tagging approach cannot always ensure
extraction of exactly two entities.

(5) GraphR (Fu et al., 2019): This model represents each token in a sentence
as a node in a graph. The edges connecting the nodes represent the relations
between them. They use a graph convolutional network (GCN) to predict the
relation of each edge and then filter out some of the relations. Since each
token is a node in the graph, there will be too many edges in it that do not
represent any relation.

(6) N-gram Attention (Trisedya et al., 2019): This model uses an encoder-
decoder approach with N-gram attention mechanism for knowledge-base completion
using distantly supervised data. The encoder uses the source tokens as its
vocabulary and the decoder uses the entire Wikidata (Vrandečić and Krötzsch,
2014) entity IDs and relation IDs as its vocabulary. The encoder takes the
source sentence as input and the decoder outputs the two entity IDs and
relation ID for every tuple. During training, it uses the mapping of entity
names and their Wikidata IDs of the entire Wikidata for proper alignment. Our
task of extracting relation tuples with the raw entity names from a sentence
is more challenging since entity names are not of fixed length. Our more
generic approach is also helpful for extracting new entities which are not
present in the existing knowledge bases such as Wikidata. We use this N-gram
attention mechanism in Eq. (5.14) to compare its performance with other
attention models (Table 5.5).

(7) Pipeline Models: We also compare the performance of our joint extraction
models against the pipeline extraction approaches. We use a pre-trained NER
model from spaCy and a neural NER model to identify the named entities and use
CNN, PCNN, and our proposed syntax-focused multi-factor attention (SFMFA)
model for classifying the relations.

Our neural NER model is similar to the model proposed by Chiu and Nichols
(2016) and we use the ‘BIESO’ sequence tagging approach. We are not interested
in the type of entities, so we use a total of 5 NER tags. We use features
based on word embeddings and character embeddings to represent the sentence
tokens. These token vectors are passed to a Bi-LSTM layer for encoding. We use
separate tag embeddings to represent the NER tags. We concatenate the tag
embedding of the previous token with the Bi-LSTM hidden vectors and pass the
concatenated vector to a feed-forward layer with softmax to classify the tags.
We train this NER model on the corresponding training data with the sentences
and entity names present in them.

Our training data set contains many entity pairs that do not have any valid
relation in the knowledge base. We consider them as None relation samples to
train the relation classification models. We get around 100,000 and 110,000
None instances for the NYT29 and NYT24 datasets respectively. On the test
data, first, we identify the entities using the NER models and then use the
relation classification models to find the relation between each pair of these
entities (or determine that there is no relation).

####  5.4.5 Experimental Results

We present our experimental results in Table 5.4. The pipeline approaches
perform better when they are used with the neural NER module. Since the neural
NER module is trained on the training data, it performs better than the NER
module of spaCy. We can see a very high variance in the results of the
pipeline approaches with two different NER modules. This shows that pipeline
approaches have too much dependency on the NER module and joint models are
more suitable for this task.

| NYT29 | NYT24
---|---|---
Model | Prec. | Rec. | F1 | Prec. | Rec. | F1
Pipeline |  |  |  |  |  |
spaCy NER + CNN | 0.037 | 0.063 | 0.047 | 0.187 | 0.723 | 0.297
spaCy NER + PCNN | 0.034 | 0.044 | 0.086 | 0.190 | 0.714 | 0.301
spaCy NER + SFMFA | 0.026 | 0.054 | 0.035 | 0.319 | 0.628 | 0.423
Neural NER + CNN | 0.287 | 0.738 | 0.414 | 0.435 | 0.820 | 0.568
Neural NER + PCNN | 0.287 | 0.737 | 0.412 | 0.435 | 0.815 | 0.567
Neural NER + SFMFA | 0.420 | 0.582 | 0.488 | 0.588 | 0.771 | 0.667
Joint single |  |  |  |  |  |
tagging | 0.593 | 0.381 | 0.464 | 0.624 | 0.317 | 0.420
CopyR | 0.569 | 0.452 | 0.504 | 0.610 | 0.566 | 0.587
SPTree | 0.492 | 0.557 | 0.522 | - | - | -
GraphR | - | - | - | 0.639 | 0.600 | 0.619
HRL* | 0.692 | 0.601 | 0.643 | 0.781 | 0.771 | 0.776
WDec* | 0.777 | 0.608 | 0.682 | 0.881 | 0.761 | 0.817
PNDec* | 0.732 | 0.624 | 0.673 | 0.806 | 0.773 | 0.789
Joint ensemble |  |  |  |  |  |
HRL | 0.764 | 0.604 | 0.674 | 0.842 | 0.778 | 0.809
WDec | 0.846 | 0.621 | 0.716 | 0.945 | 0.762 | 0.844
PNDec | 0.815 | 0.639 | 0.716 | 0.893 | 0.788 | 0.838
WDec_PNDec | 0.846 | 0.621 | 0.716 | 0.945 | 0.762 | 0.844

Table 5.4: Performance comparison of the models on the two datasets. The rows
with * show the median of five runs.

Among the joint extraction approaches, HRL achieves significantly higher F1
scores on the two datasets. We run their model and our models five times and
report the median results in Table 5.4. Scores of other baselines in Table 5.4
are taken from previous published papers (Zeng et al., 2018; Takanobu et al.,
2019; Fu et al., 2019). Our WordDecoding (WDec) model achieves F1 scores that
are $3.9\%$ and $4.1\%$ higher than HRL on the NYT29 and NYT24 datasets
respectively. Similarly, our PtrNetDecoding (PNDec) model achieves F1 scores
that are $3.0\%$ and $1.3\%$ higher than HRL on the NYT29 and NYT24 datasets
respectively. We perform a statistical significance test (t-test) under a
bootstrap pairing between HRL and our models and see that the higher F1 scores
achieved by our models are statistically significant ($p<0.001$). Next, we
combine the outputs of five runs of our models and five runs of HRL to build
ensemble models. For a test instance, we include those tuples which are
extracted in the majority ($\geq 3$) of the five runs. This ensemble mechanism
increases the precision significantly on both datasets with a small
improvement in recall as well. In the ensemble scenario, compared to HRL, WDec
achieves $4.2\%$ and $3.5\%$ higher F1 scores and PNDec achieves $4.2\%$ and
$2.9\%$ higher F1 scores on the NYT29 and NYT24 datasets respectively. When we
ensemble the five runs of WDec and five runs of PNDec together, we see that it
achieves the same performance as the ensemble version of WDec, since the
tuples extracted by the ensemble version of the PNDec model are a proper
subset of the tuples extracted by the ensemble version of the WDec model.

###  5.5 Analysis and Discussion

####  5.5.1 Comparison between the Two Decoding Frameworks

From Table 5.4, we see that our proposed word-level decoding framework and
pointer network-based decoding framework perform comparably. But pointer
network decoding is much more intuitive than word-level decoding. The word-
level decoder depends on the generation of the special tokens at appropriate
time steps. It generates the relation names in the same way as it generates
the entity tokens. Sometimes, it may generate non-relation tokens at the time
steps when it must generate relation tokens. So we will not be able to extract
the tuples from the generated sequence of tokens. This problem does not arise
for pointer network decoding as it always extracts two entities and a relation
between them at every time step.

Finding new entities in the test data is much simpler in pointer network
decoding as it directly points to the entities in the input sentence. There is
no direct way to find new entities in the test data in word-level decoding. We
use the UNK token for this purpose. Whenever the decoder generates the UNK
token, we replace it with the corresponding source token with the highest
attention score. In pointer network decoding, we obtain the entire tuple
representation at every time step and use it in the attention mechanism. But
in word-level decoding, it is not possible to find the tuple representation,
so we apply attention at the token level.

####  5.5.2 Ablation Studies

We include the ablation of our masking mechanism (+ Masking) and replacement
of UNK token (+ Rep_UNK) for the WordDecoding model in Table 5.5. We see that
both components contribute to significant improvements in F1 score for three
types of attention. From Table 5.5, we also see that PtrNetDecoding achieves
the highest F1 scores when we combine the two attention mechanisms with
respect to the previous hidden vector of the decoder LSTM
($\mathbf{h}_{t-1}^{D}$) and representation of all previously extracted tuples
($\mathbf{y}_{prev}$).

| NYT29 | NYT24
---|---|---
Model | Prec. | Rec. | F1 | Prec. | Rec. | F1
WDec |  |  |  |  |  |
Avg. | 0.638 | 0.523 | 0.575 | 0.771 | 0.683 | 0.724
\+ Masking | 0.709 | 0.561 | 0.626 | 0.843 | 0.717 | 0.775
N-gram | 0.640 | 0.498 | 0.560 | 0.783 | 0.698 | 0.738
\+ Masking | 0.699 | 0.519 | 0.596 | 0.825 | 0.715 | 0.766
\+ Rep_UNK | 0.739 | 0.519 | 0.610 | 0.847 | 0.716 | 0.776
Single | 0.683 | 0.545 | 0.607 | 0.816 | 0.716 | 0.763
\+ Masking | 0.723 | 0.567 | 0.636 | 0.842 | 0.728 | 0.781
\+ Rep_UNK | 0.777 | 0.608 | 0.682 | 0.881 | 0.761 | 0.817
PNDec |  |  |  |  |  |
$\mathrm{dec_{hid}}$ | 0.720 | 0.615 | 0.663 | 0.798 | 0.772 | 0.785
$\mathrm{tup_{prev}}$ | 0.726 | 0.614 | 0.665 | 0.805 | 0.764 | 0.784
$\mathrm{combo}$ | 0.732 | 0.624 | 0.673 | 0.806 | 0.773 | 0.789

Table 5.5: Ablation of attention mechanisms with WordDecoding (WDec) and
PtrNetDecoding (PNDec) model. For the Avg. type of attention in the WDec
model, we do not replace the generated UNK token with any of the sentence
tokens as they have the same attention weight.

####  5.5.3 Performance Analysis

From Table 5.4, we see that CopyR, HRL, and our models achieve significantly
higher F1 scores on the NYT24 dataset than the NYT29 dataset. Both datasets
have a similar set of relations and similar texts (NYT). So task-wise both
datasets should pose a similar challenge. However, the F1 scores suggest that
the NYT24 dataset is easier than NYT29. The reason is that NYT24 has around
72.0% of overlapping tuples between the training and test data (% of test
tuples that appear in the training data with different source sentences). In
contrast, NYT29 has only 41.7% of overlapping tuples. Due to the memorization
power of deep neural networks, it can achieve much higher F1 score on NYT24.
The difference between the F1 scores of WordDecoding and PtrNetDecoding on
NYT24 is marginally higher than NYT29, since WordDecoding has more trainable
parameters (about 27 million) than PtrNetDecoding (about 24.5 million) and
NYT24 has very high tuple overlap. However, their ensemble versions achieve
closer F1 scores on both datasets.

Despite achieving marginally lower F1 scores, the pointer network-based model
can be considered more intuitive and suitable for this task. WordDecoding may
not extract the special tokens and relation tokens at the right time steps,
which is critical for finding the tuples from the generated sequence of words.
PtrNetDecoding always extracts two entities of varying length and a relation
for every tuple. We also observe that PtrNetDecoding is more than two times
faster and takes one-third of the GPU memory of WordDecoding during training
and inference. This speedup and smaller memory consumption are achieved due to
the fewer number of decoding steps of PtrNetDecoding compared to WordDecoding.
PtrNetDecoding extracts an entire tuple at each time step, whereas
WordDecoding extracts just one word at each time step and so requires eight
time steps on average to extract a tuple (assuming that the average length of
an entity is two). The softmax operation at the projection layer of
WordDecoding is applied across the entire vocabulary and the vocabulary size
can be large (more than 40,000 for our datasets). In case of PtrNetDecoding,
the softmax operation is applied across the sentence length (maximum of 100 in
our experiments) and across the relation set (24 and 29 for our datasets). The
costly softmax operation and the higher number of decoding time steps
significantly increase the training and inference time for WordDecoding. The
encoder-decoder model proposed by Trisedya et al. (2019) faces a similar
softmax-related problem as their target vocabulary contains the entire
Wikidata entity IDs and relation IDs which is in the millions. HRL, which uses
a deep reinforcement learning algorithm, takes around 8x more time to train
than PtrNetDecoding with a similar GPU configuration. The speedup and smaller
memory consumption will be useful when we move from sentence-level extraction
to document-level extraction, since document length is much higher than
sentence length and a document contains a higher number of tuples.

|  | Model | Prec. | Rec. | F1
---|---|---|---|---|---
NYT29 | Ent | HRL | 0.833 | 0.827 | 0.830
WDec | 0.865 | 0.812 | 0.838
PNDec | 0.858 | 0.851 | 0.855
Rel | HRL | 0.846 | 0.745 | 0.793
WDec | 0.895 | 0.729 | 0.803
PNDec | 0.884 | 0.770 | 0.823
NYT24 | Ent | HRL | 0.887 | 0.892 | 0.890
WDec | 0.926 | 0.858 | 0.891
PNDec | 0.906 | 0.901 | 0.903
Rel | HRL | 0.906 | 0.896 | 0.901
WDec | 0.941 | 0.880 | 0.909
PNDec | 0.930 | 0.921 | 0.925

Table 5.6: Comparison on entity and relation generation tasks.

| NYT29 | NYT24
---|---|---
Model | Order | Ent1 | Ent2 | Order | Ent1 | Ent2
HRL | 0.2 | 5.9 | 6.6 | 0.2 | 4.7 | 6.3
WDec | 0.0 | 4.2 | 4.7 | 0.0 | 2.4 | 2.4
PNDec | 0.8 | 5.6 | 6.0 | 1.0 | 4.0 | 6.1

Table 5.7: % errors for wrong ordering and entity mismatch.

####  5.5.4 Error Analysis

The relation tuples extracted by a joint model can be erroneous for multiple
reasons such as: (i) extracted entities are wrong; (ii) extracted relations
are wrong; (iii) pairings of entities with relations are wrong. To see the
effects of the first two reasons, we analyze the performance of HRL and our
models on entity generation and relation generation separately. For entity
generation, we only consider those entities which are part of some tuple. For
relation generation, we only consider the relations of the tuples. We include
the performance of our two models and HRL on entity generation and relation
generation in Table 5.6. Our proposed models perform better than HRL on both
tasks. Comparing our two models, PtrNetDecoding performs better than
WordDecoding on both tasks, although WordDecoding achieves higher F1 scores in
tuple extraction. This suggests that PtrNetDecoding makes more errors while
pairing the entities with relations. We further analyze the outputs of our
models and HRL to determine the errors due to ordering of entities (Order),
mismatch of the first entity (Ent1), and mismatch of the second entity (Ent2)
in Table 5.7. WordDecoding generates fewer errors than the other two models in
all the categories and thus achieves the highest F1 scores on both datasets.

###  5.6 Summary

Jointly extracting entities and relations from sentences is a challenging task
due to different lengths of entities, the presence of multiple tuples, and
overlapping of entities among tuples. In this chapter, we describe two novel
approaches using encoder-decoder architecture to address this task.
Experiments on the New York Times (NYT) corpus show that our proposed models
achieve significantly improved new state-of-the-art F1 scores.

##  Chapter 6 A Hierarchical Entity Graph Convolutional Network for Relation
Extraction across Documents

Distantly supervised relation extraction models mostly focus on sentence-level
relation extraction, where the two entities (subject and the object entity) of
a relation tuple must appear in the same sentence. This assumption is overly
strict and for a large number of relations, we may not find sentences
containing the two entities. To solve this problem, we propose multi-hop
relation extraction, where the two entities of a relation tuple may appear in
two different documents but these documents are connected via some common
entities. We can find a chain of entities from the subject entity to the
object entity via common entities. The relation between the subject and object
entities can be established using this entity chain. Following this multi-hop
approach, we create a dataset for 2-hop relation extraction, where each chain
contains exactly two documents. This dataset covers a higher number of
relations than sentence-level extraction. We also propose a hierarchical
entity graph convolutional network (HEGCN) model to solve this task,
consisting of a two-level hierarchy of graph convolutional networks (GCNs).
The first-level GCN of the hierarchy captures the relations among the entity
mentions within the documents, and the second-level GCN of the hierarchy
captures the relations among the entity mentions across the documents in a
chain. Our proposed HEGCN model improves the performance by 2.2% F1 score on
our 2-hop relation extraction dataset, and it can be readily extended to N-hop
datasets.

###  6.1 Motivation

The task of relation extraction is to find relation tuples from free text.
Mintz et al. (2009), Riedel et al. (2010), and Hoffmann et al. (2011) proposed
the idea of distant supervision to automatically obtain a large amount of
training data for this task. The idea is to map the relation tuples in
existing knowledge bases (KBs) to text corpora such as Wikipedia or news
articles. The assumption is that if the subject and object entities of a
relation tuple appear in a sentence, then this sentence can be considered as
providing evidence of the relation between the entities. Most relation
extraction work focuses on such distantly supervised sentence-level
extraction. This method can give a significantly large amount of training data
to build supervised relation extraction models. But the assumption of distant
supervision that the two entities of a tuple must appear in the same sentence
is overly strict. We may not find an adequate number of evidence sentences for
many relations if the two entities in a relation do not appear in the same
sentence. The relation extraction models built on such data can find relations
only for a small number of relations and most relations of the KBs will be out
of the reach of such models.

|  D1: Ghanshyam Tiwari
---
held the position of
education minister in
Government of Rajasthan.
|  D1: Arnage is a commune
---
in the Sarthe department
in the region of Pays-de-la
-Loire in north-western
France.
| D2: Shekhawati is a
---
semi-arid historical region
located in the northeast
part of Rajasthan, India.
|  D2: Paris is the capital
---
and most populous city
of France.
|  Subj.: Ghanshyam Tiwari
---
Obj.: India
Common: Rajasthan
|  Subj.: Arnage
---
Obj.: Paris
Common: France
Rel: country_of_citizenship | Rel: None
Table 6.1: Examples of 2-hop relations.

To solve this problem, we propose a multi-hop relation extraction task where
the subject and object entities of a tuple can appear in two different
documents, and these two documents are connected via some common entities. We
can create a chain of entities from the subject entity to the object entity of
a tuple via the common entities across multiple documents. Each link in this
chain represents a relation between the entities located at the endpoints of
the link. We can determine the relation between the subject and object
entities of a tuple by following this chain of relations. This approach can
give training instances for more relations than sentence-level distant
supervision. Following the proposed multi-hop approach, we create a 2-hop
relation extraction dataset for the task. Each instance of this dataset has
two documents, where the first document contains the subject entity and the
second document contains the object entity of a tuple. These two documents are
connected via at least one common entity. We have included one positive and
one negative example of 2-hop relations in Table 6.1. This idea can be
extended to create an N-hop dataset.

We also propose a hierarchical entity graph convolutional network (HEGCN)
model for the task. Our proposed model has two levels of graph convolutional
networks (GCNs). The first-level GCN of the hierarchy is applied to the entity
mention level graph of every document to capture the relations among the
entity mentions within a document. The second-level GCN of the hierarchy is
applied on a unified entity level graph, which is built using all the unique
entities present in the document chain. This entity level graph can be built
on the document chain of any length and it can capture the relations among the
entities across the multiple documents in the chain. Our proposed HEGCN model
improves the performance on our 2-hop dataset. To summarize, the following are
the contributions of this work:
(1) We propose a multi-hop relation extraction task and create a distantly
supervised dataset for the task. Our dataset has more relations than the other
popular distantly supervised sentence-level or document-level relation
extraction datasets.
(2) We propose a novel hierarchical entity graph convolutional network (HEGCN)
for multi-hop relation extraction. Our proposed model improves the F1 score by
2.2% on our multi-hop dataset, compared to strong neural baselines.

###  6.2 Problem Definition

Multi-hop relation extraction can be defined as follows. Consider two
entities, a subject entity $e_{s}$ and an object entity $e_{o}$, and a chain
of documents $D=\\{D_{s}\rightarrow D_{1}\rightarrow
D_{2}\rightarrow...\rightarrow D_{n}\rightarrow D_{o}\\}$ where $e_{s}\in
D_{s}$ and $e_{o}\in D_{o}$. There exists a chain of entities
$e_{s}\rightarrow c_{1}\rightarrow c_{2}\rightarrow...\rightarrow
c_{n+1}\rightarrow e_{o}$ where $c_{1}\in\\{D_{s},D_{1}\\}$,
$c_{2}\in\\{D_{1},D_{2}\\},...,$ $c_{n+1}\in\\{D_{n},D_{o}\\}$. The task is to
find the relation between $e_{s}$ and $e_{o}$ from a pre-defined set of
relations $R\cup\\{\mathit{None}\\}$, where $R$ is the set of relations and
None indicates that none of the relations in $R$ holds between $e_{s}$ and
$e_{o}$. A simpler version of this task is 2-hop relation extraction where
$D_{s}$ and $D_{o}$ are directly connected by at least one common entity. In
this work, we focus on 2-hop relation extraction.

###  6.3 Multi-Hop Dataset Construction

We create a dataset for this multi-hop relation extraction from a multi-hop
question-answering (QA) dataset WikiHop (Welbl et al., 2018). Welbl et al.
(2018) defined the multi-hop QA task as follows: Given a set of supporting
documents $D_{s}$ and a set of candidate answer $C_{a}$ which are mentioned in
$D_{s}$, the goal is to find the correct answer $a^{*}\in C_{a}$ by drawing on
the supporting documents. They used Wikipedia articles and Wikidata (Vrandečić
and Krötzsch, 2014) tuples for creating this dataset. Each positive tuple
$(e_{s},e_{o},r_{p})$ in Wikidata has two entities, a subject entity $e_{s}$
and an object entity $e_{o}$, and a positive relation $r_{p}$ between the
subject and object entity. The questions are created by combining the subject
entity $e_{s}$ and the relation $r_{p}$, and the object entity $e_{o}$ is the
correct answer $a^{*}$ for a given question. The other candidate answers are
carefully chosen from Wikidata entities so that they have a similar type as
the correct answer. The supporting documents are chosen in such a way that at
least two documents are needed to find the correct answer. This means the
subject entity $e_{s}$ and the object entity $e_{o}$ do not appear in the same
document. They used a bipartite graph partition technique to create the
dataset. In this bipartite graph, vertices on one side correspond to Wikidata
entities, and vertices on the other side correspond to Wikipedia articles. An
edge is created between an entity vertex and a document vertex if this
document contains the entity. As we traverse the graph starting from vertex
$e_{s}$, it visits many document vertices and entity vertices. This
constitutes the supporting document set and candidate answer set. If the
candidate answer set does not contain the object entity $e_{o}$ which is the
correct answer, this instance is discarded. They also limited the length of
the traversal to 3 documents. Welbl et al. (2018) only released the supporting
documents, questions, and candidate answers for their dataset. They did not
release the connecting entities.

We convert this WikiHop dataset into a multi-hop relation extraction dataset.
The subject entities and the candidate entities can be easily found in the
documents using string matching. We use a named entity recognizer from
spaCy111https://spacy.io/ to find the other entities in the documents and
these entities can link these documents. We find that most of the WikiHop
question-answer instances are 2-hop instances. That means for most of the
instances of WikiHop dataset, there is at least one document pair in the
supporting document set where the first document of the pair contains the
subject entity and the second document of the pair contains the correct
answer, and these two documents in the pair are directly connected via some
third entity. To simplify the multi-hop relation extraction task, we fix the
hop count at 2. For every instance of the WikiHop dataset, we can easily find
the subject entity $e_{s}$ and the positive relation $r_{p}$ from the
question. The correct answer $a^{*}$ is the object entity of a positive tuple.
$(e_{s},a^{*},r_{p})$ is the positive tuple for relation extraction. For any
other candidate answer $e_{w}\in C_{a}-\\{a^{*}\\}$, the entity pair
$(e_{s},e_{w})$ is considered as a None tuple if there exists no relation
among the four pairs $(e_{s},e_{w})$, $(e_{w},e_{s})$, $(e_{w},e_{o})$, and
$(e_{o},e_{w})$ in Wikidata. We check for the no relation condition for these
four entity pairs involving $e_{w}$, $e_{s}$, and $e_{o}$ to reduce the
distant supervision noise in the dataset for None tuples. We create a None
candidate set $C_{n}$ with each $e_{w}\in C_{a}-\\{a^{*}\\}$. We first find
all possible pairs of documents from the supporting document set $D_{s}$ such
that the first document of the pair contains the subject entity $e_{s}$ and
the second document of the pair contains either the entity $a^{*}$ or one of
the entities from $C_{n}$. We discard those pairs of documents that do not
contain any common entity. The document pairs where the second document
contains the entity $a^{*}$ are considered as a document chain for the
positive tuple $(e_{s},a^{*},r_{p})$ where $r_{p}\in R$. All other document
pairs where the second document contains an entity from the set $C_{n}$ are
considered as a document chain for None tuple $(e_{s},e_{w},None)$ where
$e_{w}\in C_{n}$. In this way, using distant supervision, we can create a
dataset for 2-hop relation extraction. Each instance of this dataset has a
chain of documents $D=\\{D_{s}\rightarrow D_{o}\\}$ of length 2 that is the
textual source of a tuple $(e_{s},e_{o},r)$. The document $D_{s}$ contains the
subject entity $e_{s}$ and the document $D_{o}$ contains the object entity
$e_{o}$. The two documents are connected with at least one common entity $c$.
There exists at least one entity chain $e_{s}\rightarrow c\rightarrow e_{o}$
in the document chain. The goal is to find the relation $r$ between $e_{s}$
and $e_{o}$ from the set $R\cup\\{\mathit{None}\\}$. This dataset is our
multi-hop relation extraction dataset (MHRED), to be used in the remaining
sections of this chapter.

Question | located_in_the_administrative_territorial_entity Zoo Lake
---|---
Candidates | Gauteng, Tanzania
Answer | Gauteng
Doc1 |  |  Zoo Lake is a popular lake and public park in Johannesburg ,
---
South Africa . It is part of the Hermann Eckstein Park and is
opposite the Johannesburg Zoo . The Zoo Lake consists of two
dams , an upper feeder dam , and a larger lower dam , both
constructed in natural marshland watered by the Parktown
Spruit .
Doc2 |  |  Johannesburg is the largest city in South Africa and is one of
---
the 50 largest urban areas in the world . It is the provincial
capital of Gauteng , which is the wealthiest province in
South Africa .
Doc3 |  | Mozambique is a country in Southeast Africa bordered by the
---
Indian Ocean to the east , Tanzania to the north , Malawi
and Zambia to the northwest , Zimbabwe to the west , and
Swaziland and South Africa to the southwest . It is separated
from Madagascar by the Mozambique Channel to the east .
Table 6.2: A multi-hop question-answer instance from the WikiHop dataset.

We include a multi-hop question-answer instance of the WikiHop dataset in
Table 6.2, which has a question, two candidate answers, and three documents.
We can obtain the positive relation
located_in_the_administrative_territorial_entity and subject entity Zoo Lake
from the question. The subject entity appears in Doc1. Two candidate answers
Gauteng and Tanzania appear in Doc2 and Doc3 respectively. Doc1 and Doc2 have
two common entities Johannesburg and South Africa. Doc1 and Doc3 have a common
entity South Africa. Since the correct answer to the question is Gauteng, the
quintuple (Doc1, Zoo Lake, Doc2, Gauteng,
located_in_the_administrative_territorial_entity) constitutes a positive
instance in the MHRED dataset. The quintuple (Doc1, Zoo Lake, Doc3, Tanzania,
None) constitutes a negative instance in the MHRED dataset.

####  6.3.1 Dataset Statistics

The training, validation, and test data of the WikiHop dataset are created
using distant supervision, but the validation and test data are manually
verified. WikiHop test data is blind and not released. So we use their
validation data to create the test data for our task and use their training
data for our training and validation purposes. We include the statistics of
our multi-hop relation extraction dataset in Table 6.3. We include the
statistics on the number of common entities present in the two documents of a
chain in Table 6.4. We split the training data randomly, with 90% for training
and 10% for validation. From Table 6.3, we see that the dataset contains a
much higher number of None tuples than the positive tuples. So we randomly
select None tuples so that the number of None tuples is the same as the number
of positive tuples for training and validation. For evaluation, we consider
the entire test dataset. From Table 6.5, we see that our MHRED dataset
contains more relations than any other distantly supervised relation
extraction datasets such as the New York Times (Riedel et al., 2010; Hoffmann
et al., 2011) or DocRED (Yao et al., 2019).

| Train | Test
---|---|---
#Positive relations | 218 | 72
#Document chains | 143,906 | 5,320
#Positive instances | 40,247 | 1,672
#Positive entity pairs | 21,490 | 618
#None instances | 197,731 | 7,806
Table 6.3: Statistics of the MHRED dataset. | #Document chains
---|---
#Common entities | Train | Test
1 | 92,140 | 3,615
2 | 36,275 | 1,161
3 | 10,824 | 374
4 | 3,170 | 113
$\geq$5 | 1,497 | 57
Table 6.4: Statistics of the common entities in the MHRED dataset. Dataset | $|R|$ | Dataset | $|R|$
---|---|---|---
ACE04 | 7 | CoNLL04 | 5
SemEval 2010 | 9 | GDS | 4
NYT10 | 53 | NYT11 | 24
TACRED | 41 | DocRED | 96
FewRel 2.0 | 100 | MHRED | 218
Table 6.5: The number of relations in various relation extraction datasets.
$R$ is the set of positive relations.

###  6.4 Model Description

We propose a hierarchical entity graph convolutional network (HEGCN) for the
multi-hop relation extraction. We encode the documents in a document chain
using a bi-directional long short-term memory (BiLSTM) layer (Hochreiter and
Schmidhuber, 1997). On top of the BiLSTM layer, we use two graph convolutional
networks (GCN), one after another in a hierarchy. In the first level of the
GCN hierarchy, we construct a separate entity mention graph on each document
of the chain using all the entities mentioned in that document. Each mention
of an entity in a document is considered as a separate node in the graph. We
use a graph convolutional network (GCN) on the entity mention graph of each
document to capture the relations among the entity mentions in the document.
This mention-level graph helps to pass information among the entity mentions
in a document. We then construct a unified entity-level graph across all the
documents in the chain. Each node of this entity-level graph represents a
unique entity in the document chain. Each common entity between two documents
in the chain is represented by a single node in the graph. We use a GCN on
this unified entity-level graph to capture the relations among the entities
across the documents. This unified entity graph helps to pass information
among the multiple documents. This graph is a local knowledge graph involving
the entities present in the documents. GCN is used to enrich the
representations of the entities in the graph. We concatenate the
representations of the nodes of the subject entity and object entity and pass
it to a feed-forward layer with softmax for relation classification.

Figure 6.1: The architecture of our proposed HEGCN model. First, a GCN in the
hierarchy is shared across the entity mention graphs of the documents in a
chain. This diagram is for a document chain of length 2.

####  6.4.1 Document Encoding Layer

We use two types of embedding vectors: (1) word embedding vector
$\mathbf{w}\in\mathbb{R}^{d_{w}}$ (2) entity token indicator embedding vector
$\mathbf{z}\in\mathbb{R}^{d_{z}}$, which indicates if a word belongs to the
subject entity, object entity, or common entities. The subject and object
entities are assigned the embedding index of $2$ and $3$, respectively. The
common entities in the document chain are assigned embedding index in an
increasing order starting from index $4$. The same entities present in two
documents in the chain get the same embedding index. Embedding index $0$ is
used for padding and $1$ is used for all other tokens in the documents. A
document is represented using a sequence of vectors
$\\{\mathbf{x}_{1},\mathbf{x}_{2},.....,\mathbf{x}_{n}\\}$ where
$\mathbf{x}_{t}=\mathbf{w}_{t}\|\mathbf{z}_{t}$. $\|$ represents the
concatenation of vectors and $n$ is the document length. We concatenate all
documents in a chain sequentially by using a document separator token. These
token vectors are passed to a BiLSTM layer to capture the interaction among
the documents in a chain.

$\displaystyle\mathbf{x}_{t}=\mathbf{w}_{t}\|\mathbf{z}_{t}$
$\displaystyle\overrightarrow{\mathbf{h}_{t}}=\overrightarrow{\mathrm{LSTM}}(\mathbf{x}_{t},\mathbf{h}_{t-1})$
$\displaystyle\overleftarrow{\mathbf{h}_{t}}=\overleftarrow{\mathrm{LSTM}}(\mathbf{x}_{t},\mathbf{h}_{t+1})$
$\displaystyle\mathbf{h}_{t}=\overrightarrow{\mathbf{h}_{t}}||\overleftarrow{\mathbf{h}_{t}}$
(6.1)

$\overrightarrow{\mathbf{h}_{t}}\in\mathbb{R}^{(d_{w}+d_{z})}$ and
$\overleftarrow{\mathbf{h}_{t}}\in\mathbb{R}^{(d_{w}+d_{z})}$ are the output
at the $t$th step of the forward LSTM and backward LSTM respectively. We
concatenate them to obtain the $t$th BiLSTM output
$\mathbf{h}_{t}\in\mathbb{R}^{2(d_{w}+d_{z})}$ (Eq. (6.1)).

####  6.4.2 Hierarchical Entity Graph Convolutional Layers

Kipf and Welling (2017) proposed graph convolutional networks (GCN) which work
on graph structures. Here, we describe the GCN which is used in our model. We
represent a graph $\mathcal{G}$ with $m$ nodes using an adjacency matrix
$\mathbf{A}$ of size $m\times m$. If there is an edge between node $i$ and
node $j$, then $A_{ij}=A_{ji}=1$. Self loops, $A_{ii}=1$, are added in the
graph $\mathcal{G}$ so that the nodes keep their own information too. We
normalize the adjacency matrix $\mathbf{A}$ by using symmetric normalization
proposed by Kipf and Welling (2017). A diagonal node degree matrix
$\mathbf{D}$ of size $m\times m$ is used in the normalization of $\mathbf{A}$.

$\displaystyle D_{ij}=\begin{cases}\text{deg}(v_{i})&\text{if }i=j\\\
0&\text{otherwise}\end{cases}$ $\displaystyle
D^{-\frac{1}{2}}_{ij}=\begin{cases}\frac{1}{\sqrt{D}_{ij}}&\text{if }i=j\\\
0&\text{otherwise}\end{cases}$
$\displaystyle\hat{\mathbf{A}}=\mathbf{D}^{-\frac{1}{2}}\mathbf{A}\mathbf{D}^{-\frac{1}{2}}$
(6.2)

where $\text{deg}(v_{i})$ is the number of edges that are connected to the
node $v_{i}$ in $\mathcal{G}$ and $\hat{\mathbf{A}}$ (Eq. (6.2)) is the
corresponding normalized adjacency matrix of $\mathcal{G}$.

Each node of the graph receives the hidden representation of its neighboring
nodes from the $(l-1)$th layer and uses the following operation (Eq. (6.3)) to
update its own hidden representation.

$\displaystyle\textbf{g}_{i}^{l}=\text{ReLU}(\sum_{j=1}^{m}\hat{A}_{ij}\textbf{W}^{l}\textbf{g}_{j}^{l-1})$
(6.3)

$\textbf{W}^{l}$ is the trainable weight matrix of the $l$th layer of the GCN,
$\textbf{g}_{i}^{l}$ is the representation of the $i$th node of the graph at
the $l$th layer. If $\textbf{g}_{i}^{l}$ has the dimension of $d_{g}$, then
the dimension of the weight matrix $\textbf{W}^{l}$ is $d_{g}\times d_{g}$.
$\textbf{g}_{i}^{0}$ is the initial input to the GCN.

##### Entity Mention Graph Layer

We construct an entity mention graph (EMG) for each document in the chain on
top of the document encoding layer. An entity string may appear at multiple
locations in a document and each appearance is considered as an entity
mention. We add a node in the graph for each entity mention. We connect two
entity mention nodes if they appear in the same sentence (EMG type 1 edge). We
assume that since they appear in the same sentence, there may exist some
relation between them. We also connect two entity mention nodes if the strings
of the two entity mentions are identical (EMG type 2 edge). Let
$e_{1},\ldots,e_{l}$ be the sequence of entity mention nodes listed in the
order of their appearance in a document. We connect nodes $e_{i}$ and
$e_{i+1}$ ($1\leq i<l$) with an edge (EMG type 3 edge). EMG type 3 edges
create a linear chain of the entity mentions and ensure that the graph is
connected. We use a graph convolutional network on this graph topology to
capture the relations among the entity mentions in a document.

We obtain the initial representations of the entity mention nodes from the
hidden vectors of the document encoding layer. We concatenate the hidden
vectors of the first and last token of an entity mention and a context vector
to obtain the initial representation of the entity mention node. We derive
this context vector using an attention mechanism on the tokens of the sentence
in which the entity mention appears. This context vector provides the
sentence-specific contextual information regarding the entity mention.

$\displaystyle\textbf{p}=\textbf{h}_{b}~{}\|~{}\textbf{h}_{e}$ $\displaystyle
s_{t}=\text{tanh}(\textbf{p}^{T}\textbf{W})\textbf{h}_{t}$
$\displaystyle\textbf{a}=\text{softmax}({[s_{1}s_{2}\ldots s_{k}]}^{T})$
$\displaystyle\textbf{c}=\sum_{t=1}^{k}\text{a}_{t}\textbf{h}_{t}$
$\displaystyle\textbf{q}=\textbf{p}~{}\|~{}\textbf{c}$ (6.4)

$\textbf{h}_{b}\in\mathbb{R}^{2(d_{w}+d_{z})}$ and
$\textbf{h}_{e}\in\mathbb{R}^{2(d_{w}+d_{z})}$ are the hidden vectors from the
document encoding layer of the first and last token of an entity mention.
$\textbf{W}\in\mathbb{R}^{4(d_{w}+d_{z})\times 2(d_{w}+d_{z})}$ is a trainable
weight matrix, $\textbf{h}_{t}\in\mathbb{R}^{2(d_{w}+d_{z})}$ is the hidden
vector of the $t$th token of the sentence in which the entity mention is
located, superscript $T$ represents the transpose operation. $\text{a}_{t}$ is
the normalized attention score for the $t$th token with respect to the entity
mention, $k$ is length of the sentence in which the entity mention is located,
and $\textbf{c}\in\mathbb{R}^{2(d_{w}+d_{z})}$ is the context vector. The
entity mention node vector $\textbf{q}\in\mathbb{R}^{6(d_{w}+d_{z})}$ of the
$i$th node in the graph is passed to the GCN as $\textbf{g}_{i}^{0}$. The
parameters of this GCN are shared across the documents in a chain. This layer
of the model is referred to as entity mention-level graph convolutional
network or EMGCN.

Figure 6.2: Entity mention graph and entity graph construction from Doc1 of
Table 6.2. Entity mentions are marked in bold font. The numbers in square
brackets ([x]) in the entity mention graph are used to distinguish the entity
mentions with identical string. Type x/y means this edge can be of both type x
and type y. The ‘EMG’ and ‘EG’ prefixes are omitted from the labels of the
edges in the entity mention graph and entity graph respectively.

##### Entity Graph Layer

We construct a unified entity graph (EG) on top of the entity mention graphs.
First, we construct an entity graph for each document, where each unique
entity string is represented as an entity node in the graph. We add an edge
between two entity nodes if the strings of the two entities appear together in
at least one sentence in the document (EG type 1 edge). We also form a
sequence of entity nodes based on the order of appearance of the entities in a
document, where only the first occurrence of multiple occurrences of an entity
is kept in the sequence. We connect two consecutive entity nodes in the
sequence with an edge (EG type 2 edge). This ensures that the entire entity
graph remains connected.

We construct one entity graph for each document in the document chain. We
unify the entity graphs of multiple documents by merging the nodes of common
entities between them. The unified entity graph contains all the nodes from
the multiple entity graphs, but the common entity nodes which appear in two
entity graphs are merged into one node in the unified graph. There is an edge
between two entity nodes in the unified entity graph if there exists an edge
between them in any of the entity graphs of the documents.

We obtain the initial representations of the entity nodes from the GCN outputs
of the entity mention graphs. For the common entities between two documents,
we average the GCN outputs of the entity mention nodes that have an identical
string as the entity from the entity mention graphs of the two documents. For
other entity nodes that appear only in one document, we average the GCN
outputs of the entity mention nodes that have an identical string as the
entity from the entity mention graph of that document. Each entity vector is
passed to another graph convolutional network as $\textbf{g}_{i}^{0}$ which
represents the initial representation of the $i$th entity node in the unified
entity graph. We use a graph convolutional network on this graph topology to
capture the relations among the entities across the documents in the document
chain. This layer of the model is referred to as entity-level graph
convolutional network or EGCN.

##### Example of the Graph Construction

Here, we describe how the graphs are constructed for the positive MHRED
instance mentioned in Table 6.2. We show how the entity mention graph and
entity graph are constructed from Doc1 of Table 6.2 in Figure 6.2. Each node
in the entity mention graph refers to an entity mention in the document. The
entity string Zoo Lake appears twice in the document, so there are two entity
mention nodes Zoo Lake [1] and Zoo Lake [2] in the entity mention graph. The
two entity mentions Zoo Lake [1] and Johannesburg [1] appear in the same
sentence, so a EMG type 1 edge is added between them in the graph. All other
EMG type 1 edges are added in a similar way. Zoo Lake [1] and Zoo Lake [2] are
connected with a EMG type 2 edge as they have identical entity mention string.
The sequence of entity mentions in the document is follows: Zoo Lake [1]
$\rightarrow$ Johannesburg [1] $\rightarrow$ South Africa [1] $\rightarrow$
Hermann Eckstein Park [1] $\rightarrow$ Johannesburg Zoo [1] $\rightarrow$ Zoo
Lake [2] $\rightarrow$ Parktown Spruit [1]. An EMG Type 3 edge is added
between two nodes $n_{1}$ and $n_{2}$ in the entity mention graph if $n_{2}$
follows $n_{1}$ in this sequence.

The entity graph for the document is constructed from the above entity mention
graph. Identical entity strings appear as only one node in the entity graph.
So there is only one node for Zoo Lake in the entity graph. Since the strings
of the nodes Zoo Lake and Johannesburg appear in the same sentence, an EG type
1 edge is added between them. All other EG type 1 edges are similarly added.
The sequence of entities based on their appearance in the document is as
follows (where only the first occurrence of multiple occurrences of the same
entity is kept in the sequence): Zoo Lake $\rightarrow$ Johannesburg
$\rightarrow$ South Africa $\rightarrow$ Hermann Eckstein Park $\rightarrow$
Johannesburg Zoo $\rightarrow$ Parktown Spruit. An EG Type 2 edge is added
between two nodes $n_{1}$ and $n_{2}$ in the entity graph if $n_{2}$ follows
$n_{1}$ in this sequence. We denote this graph as
$\mathcal{G}_{s}=\\{\mathcal{V}_{s},\mathcal{E}_{s}\\}$. Similarly, we
construct the entity mention graph and entity graph for Doc2 of Table 6.2 in
Figure 6.3. We denote this graph as
$\mathcal{G}_{o}=\\{\mathcal{V}_{o},\mathcal{E}_{o}\\}$.

Now, we need to unify the entity graphs of Figure 6.2 and Figure 6.3 to create
a unified entity graph as shown in Figure 6.4. We denote this unified entity
graph as $\mathcal{G}=\\{\mathcal{V},\mathcal{E}\\}$, where
$\mathcal{V}=\mathcal{V}_{s}\cup\mathcal{V}_{o}$. The common entity nodes
Johannesburg and South Africa appear only once in the unified graph
$\mathcal{G}$. There is an edge between two nodes in $\mathcal{G}$ if there is
an edge between them either in $\mathcal{G}_{s}$ or in $\mathcal{G}_{o}$.

Figure 6.3: Entity mention graph and entity graph construction from Doc2 of
Table 6.2. Figure 6.4: A unified entity graph constructed from the entity
graphs of Figure 6.2 and Figure 6.3. Nodes in the red box are part of the
entity graph of the document containing the subject entity Zoo Lake. Nodes in
the blue box are part of the entity graph of the document containing the
object entity Gauteng. Common entities are marked in orange color.

####  6.4.3 Relation Classifier

We concatenate the EGCN outputs of the nodes corresponding to the subject
entity $\textbf{e}_{s}\in\mathbb{R}^{6(d_{w}+d_{z})}$ and object entity
$\textbf{e}_{o}\in\mathbb{R}^{6(d_{w}+d_{z})}$, and pass the concatenated
vector to a feed-forward network (FFN) with softmax to predict the normalized
probabilities for the relation labels.

$\displaystyle\mathbf{r}=\mathrm{softmax}(\mathbf{W}_{r}(\mathbf{e}_{s}~{}||~{}\mathbf{e}_{o})+\mathbf{b}_{r})$
(6.5)

$\mathbf{W}_{r}\in\mathbb{R}^{(|R|+1)\times 12(d_{w}+d_{z})}$ is the weight
matrix, $\mathbf{b}_{r}\in\mathbb{R}^{|R|+1}$ is the bias vector of the FFN,
and $\mathbf{r}$ is the vector of normalized probabilities of relation labels.

####  6.4.4 Loss Function

We calculate the loss over each mini-batch of size $B$. We use the following
negative log-likelihood as our objective function for relation extraction:

$\mathcal{L}=-\frac{1}{B}\sum_{i=1}^{B}\mathrm{log}(p(r_{i}|D_{i},e_{i}^{s},e_{i}^{o},\theta))$
(6.6)

where $p(r_{i}|D_{i},e_{i}^{s},e_{i}^{o},\theta)$ is the conditional
probability of the true relation $r_{i}$ when the document chain $D_{i}$, the
subject entity $e_{i}^{s}$, the object entity $e_{i}^{o}$, and the model
parameters $\theta$ are given.

###  6.5 Experiments

####  6.5.1 Evaluation Metrics

We use precision, recall, and F1 score to evaluate the models on our multi-hop
dataset. We do not include the None relation in the evaluation. A confidence
threshold is used to decide if the relation of a test instance belongs to the
set of relations $R$ or None. If the network predicts None for a test
instance, then the test instance is classified as None only. But if the
network predicts a relation from the set $R$ and the corresponding softmax
score is below the confidence threshold, then the final class is changed to
None. Using the confidence threshold achieves the highest F1 score on the
validation dataset.

####  6.5.2 Parameter Settings

We use GloVe (Pennington et al., 2014) word embeddings of dimension $d_{w}$
which is set to 300 in our experiments, and update the embeddings during
training. We set the dimension $d_{z}$ to be 20 for the entity token indicator
embedding vectors. The hidden vector dimension of the forward and backward
LSTM is set at $320$. The dimension of BiLSTM output is $640$. We use $500$
different convolution filters with kernel width of $3$, $4$, and $5$ for
feature extraction. We use one convolutional layer in both entity mention-
level GCN and entity-level GCN in our final model. Dropout layers (Srivastava
et al., 2014) are used in our network with a dropout rate of $0.5$ to avoid
overfitting. We train our models with a mini-batch size of $32$ and optimize
the network parameters using the Adagrad optimizer (Duchi et al., 2011).

####  6.5.3 Baselines

We implement four neural baseline models for comparison with our proposed
HEGCN model. Similar to our proposed model, we represent the tokens in the
documents using pre-trained word embedding vectors and entity token indicator
vectors. We use a document separator token when concatenating the vectors of
two documents in a chain.

(1) CNN: We apply the convolution operation on the sequence of token vectors
with different kernel sizes. A max-pooling operation is applied to choose the
features from the outputs of the convolution operation. This feature vector is
passed to a feed-forward layer with softmax to classify the relation.

(2) BiLSTM: The token vectors of the document chain are passed to a BiLSTM
layer to encode its meaning. We obtain the entity mention vectors of the
subject entity and the object entity by concatenating the hidden vectors of
their first and last token. We average the entity mention tokens of the
corresponding entity to obtain the representation of the subject entity and
the object entity. These two vectors are concatenated and passed to a feed-
forward layer with softmax to find the relation between them.

(3) BiLSTM_CNN: This is a combination of the BiLSTM and CNN model described
above. The token vectors of the documents are passed to a BiLSTM layer and
then we use the convolution operation with max-pooling with different
convolutional kernel sizes on the hidden vectors of the BiLSTM layer. The
feature vector obtained from the max-pooling operation is passed to a feed-
forward layer with softmax to classify the relation.

(4) LinkPath: This model uses the explicit paths from the subject entity
$e_{s}$ to the object entity $e_{o}$ via the common entities to find the
relation. As we consider only 2-hop relations, each path from $e_{s}$ to
$e_{o}$ will be of the form $e_{s}\rightarrow c\rightarrow e_{o}$, where $c$
is a common entity. Since there can be multiple common entities between two
documents and these common entities as well as the subject and object entities
can appear multiple times in the two documents, there exist multiple paths
from $e_{s}$ to $e_{o}$. Each path is formed with four entity mentions: (i)
entity mentions of the subject entity and common entity in the first document.
(ii) entity mentions of the common entity and object entity in the second
document. We concatenate the BiLSTM hidden vectors of the start and end token
of an entity mention to obtain its representation. Each path is constructed by
concatenating all the four entity mentions of the path. This can be extended
from 2-hop to multi-hop relations by using a recurrent neural network that
takes the path entity mentions as input, and outputs the hidden representation
of the path. We average the vector representations of all the paths and pass
it to a feed-forward layer with softmax to find the relation.

####  6.5.4 Experimental Results

We include in Table 6.6 the results of the models on the MHRED dataset. We see
that adding a BiLSTM in the document encoding layer improves the performance
by more than 6% in F1 score. This improvement mostly comes from the higher
precision score of the BiLSTM models over the CNN model, which classifies a
higher number of None relations as positive relations, leading to a poorer
precision score. The BiLSTM layer adequately captures the long term
dependencies among the documents and helps to predict the None samples better.
When we add our proposed hierarchical entity graph convolutional layer on top
of the BiLSTM layer, we get another 2.2% F1 score improvement over the next
best BiLSTM_CNN model. Our HEGCN model achieves the highest precision score
with a competitive recall score compared to the BiLSTM-based baselines. A
higher precision score for relation extraction is very important, as it
reduces the number of erroneous tuples to build a cleaner knowledge base. We
also perform a statistical significance test using bootstrap resampling to
compare each baseline and our HEGCN model, and have ascertained that the
higher F1 score achieved by our model is statistically significant
($p<0.001$).

Model | Prec. | Rec. | F1
---|---|---|---
CNN | 0.562 | 0.672 | 0.612
BiLSTM | 0.680 | 0.661 | 0.671
LinkPath | 0.665 | 0.684 | 0.674
BiLSTM_CNN | 0.651 | 0.701 | 0.675
HEGCN | 0.705 | 0.689 | 0.697
Table 6.6: Performance comparison of the models on the MHRED dataset.

###  6.6 Analysis & Discussion

####  6.6.1 Varying the Number of GCN Layers

We include in Table 6.7 the performance of our HEGCN model with different
numbers of convolutional layers in the entity mention-level graph
convolutional network (EMGCN) and unified entity-level graph convolutional
network (EGCN). We see that when we increase the number of layers in either
GCN, the performance of the model drops. We finally use only one convolutional
layer in both EMGCN and EGCN.

L1 | L2 | Prec. | Rec. | F1
---|---|---|---|---
1 | 1 | 0.705 | 0.689 | 0.697
2 | 1 | 0.656 | 0.666 | 0.661
2 | 2 | 0.681 | 0.658 | 0.669
3 | 1 | 0.664 | 0.664 | 0.664
3 | 2 | 0.618 | 0.669 | 0.642
3 | 3 | 0.697 | 0.635 | 0.665
Table 6.7: The ablation study of the HEGCN model with different numbers of
convolutional layers (L1 and L2) in EMGCN and EGCN.

####  6.6.2 Effectiveness of Model Components

In Table 6.8, we include the ablation results of different components of our
HEGCN model. F1 score drops by 1.3% after removing the entity mention-level
graph convolutional network (– EMGCN). F1 score drops by 0.3% after removing
the unified entity-level graph convolutional network (– EGCN). When we remove
both GCNs (– Both GCNs) together from the model, the F1 score drops by 2.8%.
Instead of using attention, if we obtain the context vector for each entity
mention just by averaging the sentence token vectors, the F1 score drops by
2.6% (– Attention).

Model | Prec. | Rec. | F1
---|---|---|---
HEGCN | 0.705 | 0.689 | 0.697
– EMGCN | 0.695 | 0.673 | 0.684
– EGCN | 0.682 | 0.706 | 0.694
– Both GCNs | 0.667 | 0.672 | 0.669
– Attention | 0.692 | 0.651 | 0.671
Table 6.8: The ablation study of the different components of our HEGCN model.

####  6.6.3 Edge Ablation

In Table 6.9, we include the ablation study of the different types of edges in
the entity mention-level graph convolutional network (EMGCN) and unified
entity-level graph convolutional network (EGCN). This study shows that the
edges that are added to create a linear chain in the EMGCN (EMG type 3) and
EGCN (EG type 2) are the most significant. Removing them separately from the
network drops the F1 score by 3.6% and 1.8% respectively.

Model | Prec. | Rec. | F1
---|---|---|---
HEGCN | 0.705 | 0.689 | 0.697
– EMG type 1 | 0.717 | 0.654 | 0.684
– EMG type 2 | 0.677 | 0.696 | 0.686
– EMG type 3 | 0.655 | 0.668 | 0.661
– EG type 1 | 0.694 | 0.685 | 0.690
– EG type 2 | 0.701 | 0.658 | 0.679
Table 6.9: The ablation study of the different types of edges in our HEGCN
model.

####  6.6.4 Error Analysis

To analyze the prediction errors, we divide them into three categories: (i)
positive relations are misclassified as None relations. 27.2% of the errors
occur in this category. (ii) None relations are misclassified as any of the
positive relations. 5.3% of the errors occur in this category. (iii) positive
relations are misclassified as other positive relations. 5.4% of the errors
occur in this category. This result shows that the majority of
misclassification errors come from the first category. We randomly sample
negative instances from the entire set of negative instances, such that the
number of negative instances equals the total number of positive instances in
our training data. Since the positive instances belong to 218 relations,
comparatively, there is a higher number of negative instances. This data
imbalance may be the reason why our HEGCN model makes more errors in the first
category. This imbalance of positive instances and None instances in distantly
supervised data has always been a critical issue, and from Table 6.3, we see
that our dataset also faces this problem.

###  6.7 Summary

In this chapter, we describe how the idea of distant supervision can be
extended from sentence-level extraction to multi-hop extraction to cover more
relations from the KBs. We propose a general approach to create multi-hop
relation extraction datasets. Following this approach, we create a 2-hop
relation extraction dataset that covers a higher number of relations from
knowledge bases than other distantly supervised relation extraction datasets.
We also propose a hierarchical entity graph convolutional network for this
task. The two levels of GCN in our model help to capture the relation cues
within documents and across documents. Our proposed model improves the F1
score by 2.2% on our 2-hop dataset, compared to a strong neural baseline, and
it can be readily extended to N-hop datasets.

##  Chapter 7 Conclusion and Future Work

In this thesis, we first provide a brief overview of neural networks,
knowledge bases, named entity recognition, open information extraction,
distantly supervised relation extraction, and multi-hop natural language
processing. We have also elucidated our contributions to the development of
distantly supervised relation extraction. First, we describe a syntax-focused
multi-factor attention model to find the relation between two entities in a
sentence in a pipeline fashion. Our model helps to find the relation correctly
when sentences are long and entities are located far from each other.

Second, we address the problem of joint entity and relation extraction using
an encoder-decoder approach. Joint extraction is more challenging due to the
presence of multiple tuples in a sentence and the sharing of entities among
the tuples. We first propose a representation scheme for relation tuples which
enables the decoder to generate one word at a time like machine translation
models and still finds all the tuples present in a sentence with full entity
names of different lengths and with overlapping entities. Next, we propose a
pointer network-based decoding approach where an entire tuple is generated at
every time step. This joint extraction approach can eliminate the need for a
separate named entity recognition system that is required in pipeline
approaches. Also, this joint approach can better capture the interaction among
multiple relation tuples present in a sentence to achieve improved
performance.

Third, we focus on multi-hop relation extraction to extract more relations. We
describe a general approach to create multi-hop relation extraction datasets.
We adopt this approach to create a 2-hop dataset that includes more relations
than other widely used distantly supervised datasets. We also describe a
hierarchical entity graph convolutional network for multi-hop relation
extraction which improves the performance on our 2-hop dataset compared to
some strong neural baselines. This model can be readily extended to N-hop
datasets in the future.

With the progress of deep learning algorithms, significant advances have been
made in the relation extraction task. However, many challenges remain in this
area. In the pipeline approaches, since we need to find relations among all
pairs of entities, there can be a very large number of None instances. This
None class is challenging to identify as it is not a single relation but any
relation outside the set of positive relations. Erroneous detection of None
relation reduces the precision of the model and can add many wrong tuples to
the KB. To build a cleaner KB, models have to perform very well to detect the
None relation along with classifying the positive relations correctly. Our
error analysis in Chapter 4 with varying sentence length and varying distance
between the entity pairs shows that the performance of the neural models drops
significantly with increasing sentence length and increasing distance between
the entities. Future research should focus on this aspect of relation
extraction.

Regarding the joint extraction approach, our work and other prior works do not
include sentences with zero tuples in training or testing. But many sentences
do not contain any relation tuples. So in the future, detecting sentences with
no relation tuples must be handled in the joint extraction approaches. The
datasets we have used for our experiments in Chapters 4 & 5 contain a much
higher number of sentences with zero tuples than the sentences with valid
tuples. So the inclusion of sentences with zero tuples in the experiments
makes data imbalance in joint entity and relation extraction more challenging.

Current relation extraction models deal with very few relations whereas
existing knowledge bases have thousands of relations. In the future, we need
to expand multi-hop relation extraction to cover more relations. We have shown
with our 2-hop relation extraction dataset that it covers more relations than
any other sentence-level or document-level datasets. We need to extend to
N-hop relation extraction to cover more relations from the KB. However, it may
not be easy to extend the task as the inclusion of more documents in the chain
may make the data more noisy. It will be challenging to create a clean dataset
for N-hop relation extraction. Also, we need to explore zero-shot or few-shot
relation extraction to cover the relations for which we cannot obtain enough
training data using distant supervision.

## References

  * Bahdanau et al. (2015) Dzmitry Bahdanau, Kyunghyun Cho, and Yoshua Bengio.  Neural machine translation by jointly learning to align and translate.  In _ICLR_ , 2015.
  * Bari et al. (2020) M Saiful Bari, Shafiq R. Joty, and Prathyusha Jwalapuram.  Zero-resource cross-lingual named entity recognition.  In _AAAI_ , 2020.
  * Bekoulis et al. (2018) Giannis Bekoulis, Johannes Deleu, Thomas Demeester, and Chris Develder.  Joint entity recognition and relation extraction as a multi-head selection problem.  _Expert Systems with Applications_ , 2018.
  * Bizer et al. (2009) Christian Bizer, Jens Lehmann, Georgi Kobilarov, Sören Auer, Christian Becker, Richard Cyganiak, and Sebastian Hellmann.  DBpedia-A crystallization point for the web of data.  _Web Semantics: Science, Services and Agents on the World Wide Web_ , 2009.
  * Bollacker et al. (2008) Kurt Bollacker, Colin Evans, Praveen Paritosh, Tim Sturge, and Jamie Taylor.  Freebase: A collaboratively created graph database for structuring human knowledge.  In _SIGMOD_ , 2008.
  * Bowen et al. (2020) Yu Bowen, Zhenyu Zhang, Jianlin Su, Yubin Wang, Tingwen Liu, Bin Wang, and Sujian Li.  Joint extraction of entities and relations based on a novel decomposition strategy.  In _ECAI_ , 2020.
  * Cao et al. (2018) Nicola De Cao, Wilker Aziz, and Ivan Titov.  Question answering by reasoning across documents with graph convolutional networks.  In _NAACL-HLT_ , 2018.
  * Cao et al. (2019) Yu Cao, Meng Fang, and Dacheng Tao.  BAG: Bi-directional attention entity graph convolutional network for multi-hop reasoning question answering.  In _NAACL-HLT_ , 2019.
  * Carreras et al. (2002) Xavier Carreras, Lluís Màrquez, and Lluís Padró.  Named entity extraction using AdaBoost.  In _CoNLL_ , 2002.
  * Chen et al. (2019) Jiayu Chen, Caixia Yuan, Xiao-Jie Wang, and Ziwei Bai.  MrMep: Joint extraction of multiple relations and multiple entity pairs based on triplet attention.  In _CoNLL_ , 2019.
  * Chieu and Ng (2002) Hai Leong Chieu and Hwee Tou Ng.  Named entity recognition: A maximum entropy approach using global information.  In _COLING_ , 2002.
  * Chieu and Ng (2003) Hai Leong Chieu and Hwee Tou Ng.  Named entity recognition with a maximum entropy approach.  In _CoNLL_ , 2003.
  * Chiu and Nichols (2016) Jason Chiu and Eric Nichols.  Named entity recognition with bidirectional LSTM-CNNs.  In _TACL_ , 2016.
  * Cho et al. (2014) Kyunghyun Cho, Bart Van Merriënboer, Dzmitry Bahdanau, and Yoshua Bengio.  On the properties of neural machine translation: Encoder-decoder approaches.  In _Workshop on Syntax, Semantics and Structure in Statistical Translation_ , 2014.
  * Christensen et al. (2011) Janara Christensen, Mausam, Stephen Soderland, and Oren Etzioni.  An analysis of open information extraction based on semantic role labeling.  In _K-CAP_ , 2011.
  * Christopoulou et al. (2019) Fenia Christopoulou, Makoto Miwa, and Sophia Ananiadou.  Connecting the dots: Document-level neural relation extraction with edge-oriented graphs.  In _EMNLP and IJCNLP_ , 2019.
  * Collobert and Weston (2008) Ronan Collobert and Jason Weston.  A unified architecture for natural language processing: deep neural networks with multitask learning.  In _ICML_ , 2008.
  * Collobert et al. (2011) Ronan Collobert, Jason Weston, Léon Bottou, Michael Karlen, Koray Kavukcuoglu, and Pavel P. Kuksa.  Natural language processing (almost) from scratch.  _JMLR_ , 2011.
  * Devlin et al. (2019) Jacob Devlin, Ming-Wei Chang, Kenton Lee, and Kristina Toutanova.  BERT: Pre-training of deep bidirectional transformers for language understanding.  In _NAACL-HLT_ , 2019.
  * Dhingra et al. (2017) Bhuwan Dhingra, Hanxiao Liu, Zhilin Yang, William W. Cohen, and Ruslan Salakhutdinov.  Gated-attention readers for text comprehension.  In _ACL_ , 2017.
  * Dhingra et al. (2018) Bhuwan Dhingra, Qiao Jin, Zhilin Yang, William W. Cohen, and Ruslan Salakhutdinov.  Neural models for reasoning over multiple mentions using coreference.  In _NAACL-HLT_ , 2018.
  * Doddington et al. (2004) George R Doddington, Alexis Mitchell, Mark A Przybocki, Lance A Ramshaw, Stephanie M Strassel, and Ralph M Weischedel.  The automatic content extraction (ACE) program-tasks, data, and evaluation.  In _LREC_ , 2004.
  * Duchi et al. (2011) John Duchi, Elad Hazan, and Yoram Singer.  Adaptive subgradient methods for online learning and stochastic optimization.  _JMLR_ , 2011.
  * Elman (1990) Jeffrey L. Elman.  Finding structure in time.  _Cognitive Science_ , 1990.
  * Etzioni et al. (2004) Oren Etzioni, Michael Cafarella, Doug Downey, Stanley Kok, Ana-Maria Popescu, Tal Shaked, Stephen Soderland, Daniel S Weld, and Alexander Yates.  Web-scale information extraction in KnowItAll:(preliminary results).  In _WWW_ , 2004.
  * Etzioni et al. (2011) Oren Etzioni, Anthony Fader, Janara Christensen, Stephen Soderland, and Mausam.  Open information extraction: The second generation.  In _IJCAI_ , 2011.
  * Fang et al. (2019) Yuwei Fang, Siqi Sun, Zhe Gan, Rohit Pillai, Shuohang Wang, and Jing jing Liu.  Hierarchical graph network for multi-hop question answering.  _ArXiv_ , 2019.
  * Fellbaum (2000) Christiane Fellbaum.  WordNet: An electronic lexical database.  _Language_ , 2000.
  * Fritzler et al. (2019) Alexander Fritzler, Varvara Logacheva, and Maksim Kretov.  Few-shot classification in named entity recognition task.  _ACM SIGAPP Symposium on Applied Computing_ , 2019.
  * Fu et al. (2019) Tsu-Jui Fu, Peng-Hsuan Li, and Wei-Yun Ma.  GraphRel: Modeling text as relational graphs for joint entity and relation extraction.  In _ACL_ , 2019.
  * Gao et al. (2019) Tianyu Gao, Xu Han, Hao Zhu, Zhiyuan Liu, Peng Li, Maosong Sun, and Jie Zhou.  FewRel 2.0: Towards more challenging few-shot relation classification.  In _EMNLP and IJCNLP_ , 2019.
  * Grishman and Sundheim (1996) Ralph Grishman and Beth Sundheim.  Message understanding conference- 6: A brief history.  In _COLING_ , 1996.
  * Guo et al. (2019) Zhijiang Guo, Yan Zhang, and Wei Lu.  Attention guided graph convolutional networks for relation extraction.  In _ACL_ , 2019.
  * Han and Wang (2020) Xiaoyu Han and Lei Wang.  A novel document-level relation extraction method based on BERT and entity information.  _IEEE Access_ , 2020.
  * He et al. (2020) Zhengqiu He, Wenliang Chen, Yuyi Wang, Wei Zhang, Guanchun Wang, and Min Zhang.  Improving neural relation extraction with positive and unlabeled learning.  In _AAAI_ , 2020.
  * Hendrickx et al. (2010) Iris Hendrickx, Su Nam Kim, Zornitsa Kozareva, Preslav Nakov, Diarmuid Ó Séaghdha, Sebastian Padó, Marco Pennacchiotti, Lorenza Romano, and Stan Szpakowicz.  Semeval-2010 task 8: Multi-way classification of semantic relations between pairs of nominals.  In _SemEval_ , 2010.
  * Hewlett et al. (2016) Daniel Hewlett, Alexandre Lacoste, Llion Jones, Illia Polosukhin, Andrew Fandrianto, Jay Han, Matthew Kelcey, and David Berthelot.  WikiReading: A novel large-scale language understanding task over Wikipedia.  In _ACL_ , 2016.
  * Hochreiter and Schmidhuber (1997) Sepp Hochreiter and Jürgen Schmidhuber.  Long short-term memory.  _Neural Computation_ , 1997.
  * Hoffmann et al. (2011) Raphael Hoffmann, Congle Zhang, Xiao Ling, Luke Zettlemoyer, and Daniel S Weld.  Knowledge-based weak supervision for information extraction of overlapping relations.  In _ACL_ , 2011.
  * Hu et al. (2018) Minghao Hu, Yuxing Peng, Zhen Huang, Xipeng Qiu, Furu Wei, and Ming Zhou.  Reinforced mnemonic reader for machine reading comprehension.  In _IJCAI_ , 2018.
  * Huang et al. (2015) Zhiheng Huang, Wei Xu, and Kai Yu.  Bidirectional LSTM-CRF models for sequence tagging.  _ArXiv_ , 2015.
  * Jat et al. (2017) Sharmistha Jat, Siddhesh Khandelwal, and Partha Talukdar.  Improving distantly supervised relation extraction using word and entity based attention.  In _AKBC_ , 2017.
  * Joshi et al. (2019) Mandar Joshi, Danqi Chen, Yinhan Liu, Daniel S. Weld, Luke Zettlemoyer, and Omer Levy.  SpanBERT: Improving pre-training by representing and predicting spans.  _TACL_ , 2019.
  * Katiyar and Cardie (2016) Arzoo Katiyar and Claire Cardie.  Investigating LSTMs for joint extraction of opinion entities and relations.  In _ACL_ , 2016.
  * Khashabi et al. (2018) Daniel Khashabi, Snigdha Chaturvedi, Michael Roth, Shyam Upadhyay, and Dan Roth.  Looking beyond the surface: A challenge set for reading comprehension over multiple sentences.  In _NAACL-HLT_ , 2018.
  * Kingma and Ba (2015) Diederik P Kingma and Jimmy Ba.  Adam: A method for stochastic optimization.  In _ICLR_ , 2015.
  * Kipf and Welling (2017) Thomas Kipf and Max Welling.  Semi-supervised classification with graph convolutional networks.  In _ICLR_ , 2017.
  * Kundu and Ng (2018) Souvik Kundu and Hwee Tou Ng.  A question-focused multi-factor attention network for question answering.  In _AAAI_ , 2018.
  * Kundu et al. (2019) Souvik Kundu, Tushar Khot, Ashish Sabharwal, and Peter Clark.  Exploiting explicit paths for multi-hop reading comprehension.  In _ACL_ , 2019.
  * Lample et al. (2016) Guillaume Lample, Miguel Ballesteros, Sandeep Subramanian, Kazuya Kawakami, and Chris Dyer.  Neural architectures for named entity recognition.  In _NAACL-HLT_ , 2016.
  * LeCun et al. (1989) Yann LeCun, Bernhard E. Boser, John S. Denker, Donnie Henderson, Richard E. Howard, Wayne E. Hubbard, and Lawrence D. Jackel.  Backpropagation applied to handwritten zip code recognition.  _Neural Computation_ , 1989.
  * Levy et al. (2017) Omer Levy, Minjoon Seo, Eunsol Choi, and Luke S. Zettlemoyer.  Zero-shot relation extraction via reading comprehension.  In _CoNLL_ , 2017.
  * Li et al. (2019) Xiaoya Li, Fan Yin, Zijun Sun, Xiayu Li, Arianna Yuan, Duo Chai, Mingxin Zhou, and Jiwei Li.  Entity-relation extraction as multi-turn question answering.  In _ACL_ , 2019.
  * Lin et al. (2016) Yankai Lin, Shiqi Shen, Zhiyuan Liu, Huanbo Luan, and Maosong Sun.  Neural relation extraction with selective attention over instances.  In _ACL_ , 2016.
  * Liu et al. (2015) Yang Liu, Furu Wei, Sujian Li, Heng Ji, Ming Zhou, and Houfeng Wang.  A dependency-based neural network for relation classification.  In _ACL and IJCNLP_ , 2015.
  * Ma and Hovy (2016) Xuezhe Ma and Eduard H. Hovy.  End-to-end sequence labeling via bi-directional LSTM-CNNs-CRF.  In _ACL_ , 2016.
  * Ma et al. (2016) Yukun Ma, Erik Cambria, and Sa Gao.  Label embedding for zero-shot fine-grained named entity typing.  In _COLING_ , 2016.
  * Malouf (2002) Robert Malouf.  Markov models for language-independent named entity recognition.  In _CoNLL_ , 2002.
  * Mausam et al. (2012) Mausam, Michael Schmitz, Stephen Soderland, Robert Bart, and Oren Etzioni.  Open language learning for information extraction.  In _EMNLP-CoNLL_ , 2012.
  * Mihaylov et al. (2018) Todor Mihaylov, Peter Clark, Tushar Khot, and Ashish Sabharwal.  Can a suit of armor conduct electricity? A new dataset for open book question answering.  In _EMNLP_ , 2018.
  * Mikolov et al. (2013) Tomas Mikolov, Ilya Sutskever, Kai Chen, Greg S Corrado, and Jeff Dean.  Distributed representations of words and phrases and their compositionality.  In _NIPS_ , 2013.
  * Mintz et al. (2009) Mike Mintz, Steven Bills, Rion Snow, and Dan Jurafsky.  Distant supervision for relation extraction without labeled data.  In _ACL and IJCNLP_ , 2009.
  * Mitchell and Fredkin (2014) Tom Mitchell and Edward Fredkin.  Never-ending language learning.  In _Big Data_ , 2014.
  * Miwa and Bansal (2016) Makoto Miwa and Mohit Bansal.  End-to-end relation extraction using LSTMs on sequences and tree structures.  In _ACL_ , 2016.
  * Nan et al. (2020) Guoshun Nan, Zhijiang Guo, Ivan Sekulic, and Wei Lu.  Reasoning with latent structure refinement for document-level relation extraction.  In _ACL_ , 2020.
  * Nayak and Ng (2019) Tapas Nayak and Hwee Tou Ng.  Effective attention modeling for neural relation extraction.  In _CoNLL_ , 2019.
  * Nayak and Ng (2020) Tapas Nayak and Hwee Tou Ng.  Effective modeling of encoder-decoder architecture for joint entity and relation extraction.  In _AAAI_ , 2020.
  * Nguyen and Verspoor (2019) Dat Quoc Nguyen and Karin Verspoor.  End-to-end neural relation extraction using deep biaffine attention.  In _ECIR_ , 2019.
  * Pal and Mausam (2016) Harinder Pal and Mausam.  Demonyms and compound relational nouns in nominal open IE.  In _AKBC_ , 2016.
  * Peng et al. (2017) Nanyun Peng, Hoifung Poon, Chris Quirk, Kristina Toutanova, and Wen-tau Yih.  Cross-sentence n-ary relation extraction with graph LSTMs.  _TACL_ , 2017.
  * Pennington et al. (2014) Jeffrey Pennington, Richard Socher, and Christopher Manning.  GloVe: Global vectors for word representation.  In _EMNLP_ , 2014.
  * Peters et al. (2018) Matthew Peters, Mark Neumann, Mohit Iyyer, Matt Gardner, Christopher Clark, Kenton Lee, and Luke Zettlemoyer.  Deep contextualized word representations.  In _NAACL-HLT_ , 2018.
  * Punyakanok et al. (2008) Vasin Punyakanok, Dan Roth, and Wen-tau Yih.  The importance of syntactic parsing and inference in semantic role labeling.  In _ACL_ , 2008.
  * Qin et al. (2018a) Pengda Qin, Weiran Xu, and William Yang Wang.  DSGAN: Generative adversarial training for distant supervision relation extraction.  In _ACL_ , 2018a.
  * Qin et al. (2018b) Pengda Qin, Weiran Xu, and William Yang Wang.  Robust distant supervision relation extraction via deep reinforcement learning.  In _ACL_ , 2018b.
  * Quirk and Poon (2017) Chris Quirk and Hoifung Poon.  Distant supervision for relation extraction beyond the sentence boundary.  In _EACL_ , 2017.
  * Rajpurkar et al. (2016) Pranav Rajpurkar, Jian Zhang, Konstantin Lopyrev, and Percy Liang.  SQuAD: 100,000+ questions for machine comprehension of text.  In _EMNLP_ , 2016.
  * Ren et al. (2017) Xiang Ren, Zeqiu Wu, Wenqi He, Meng Qu, Clare R Voss, Heng Ji, Tarek F Abdelzaher, and Jiawei Han.  CoType: Joint extraction of typed entities and relations with knowledge bases.  In _WWW_ , 2017.
  * Riedel et al. (2010) Sebastian Riedel, Limin Yao, and Andrew McCallum.  Modeling relations and their mentions without labeled text.  In _ECML and KDD_ , 2010.
  * Roth and Yih (2004) Dan Roth and Wen-tau Yih.  A linear programming formulation for global inference in natural language tasks.  In _CoNLL_ , 2004.
  * Sahu et al. (2019) Sunil Kumar Sahu, Fenia Christopoulou, Makoto Miwa, and Sophia Ananiadou.  Inter-sentence relation extraction with document-level graph convolutional neural network.  In _ACL_ , 2019.
  * Seo et al. (2017) Minjoon Seo, Aniruddha Kembhavi, Ali Farhadi, and Hannaneh Hajishirzi.  Bidirectional attention flow for machine comprehension.  In _ICLR_ , 2017.
  * Shang et al. (2020) Yuming Shang, He-Yan Huang, Xian-Ling Mao, Xin Sun, and Wei Wei.  Are noisy sentences useless for distant supervised relation extraction?  In _AAAI_ , 2020.
  * Shen and Huang (2016) Yatian Shen and Xuanjing Huang.  Attention-based convolutional neural network for semantic relation extraction.  In _COLING_ , 2016.
  * Shen et al. (2017) Yelong Shen, Po-Sen Huang, Jianfeng Gao, and Weizhu Chen.  ReasoNet: Learning to stop reading in machine comprehension.  In _KDD_ , 2017.
  * Song et al. (2018a) Linfeng Song, Zhiguo Wang, Mo Yu, Yue Zhang, Radu Florian, and Daniel Gildea.  Exploring graph-structured passage representation for multi-hop reading comprehension with graph neural networks.  _ArXiv_ , 2018a.
  * Song et al. (2018b) Linfeng Song, Yue Zhang, Zhiguo Wang, and Daniel Gildea.  N-ary relation extraction using graph state LSTM.  In _EMNLP_ , 2018b.
  * Srivastava et al. (2014) Nitish Srivastava, Geoffrey E. Hinton, Alex Krizhevsky, Ilya Sutskever, and Ruslan Salakhutdinov.  Dropout: A simple way to prevent neural networks from overfitting.  _JMLR_ , 2014.
  * Straková et al. (2019) Jana Straková, Milan Straka, and Jan Hajic.  Neural architectures for nested NER through linearization.  In _ACL_ , 2019.
  * Suchanek et al. (2007) Fabian M Suchanek, Gjergji Kasneci, and Gerhard Weikum.  YAGO: A core of semantic knowledge.  In _WWW_ , 2007.
  * Surdeanu et al. (2012) Mihai Surdeanu, Julie Tibshirani, Ramesh Nallapati, and Christopher D. Manning.  Multi-instance multi-label learning for relation extraction.  In _EMNLP and CoNLL_ , 2012.
  * Takanobu et al. (2019) Ryuichi Takanobu, Tianyang Zhang, Jiexi Liu, and Minlie Huang.  A hierarchical framework for relation extraction with reinforcement learning.  In _AAAI_ , 2019.
  * Takeuchi and Collier (2002) Koichi Takeuchi and Nigel Collier.  Use of support vector machines in extended named entity recognition.  In _CoNLL_ , 2002.
  * Tang et al. (2020a) Hengzhu Tang, Yanan Cao, Zhenyu Zhang, Jiangxia Cao, Fang Fang, Shigang Wang, and Pengfei Yin.  HIN: Hierarchical inference network for document-level relation extraction.  _Advances in Knowledge Discovery and Data Mining_ , 2020a.
  * Tang et al. (2020b) Zeyun Tang, Yongliang Shen, Xinyin Ma, Wei Xu, Jiale Yu, and Weiming Lu.  Multi-hop reading comprehension across documents with path-based graph convolutional network.  In _IJCAI_ , 2020b.
  * Tjong Kim Sang (2002) Erik F. Tjong Kim Sang.  Introduction to the CoNLL-2002 shared task: Language-independent named entity recognition.  In _CoNLL_ , 2002.
  * Tjong Kim Sang and De Meulder (2003) Erik F. Tjong Kim Sang and Fien De Meulder.  Introduction to the CoNLL-2003 shared task: Language-independent named entity recognition.  In _CoNLL_ , 2003.
  * Trisedya et al. (2019) Bayu Distiawan Trisedya, Gerhard Weikum, Jianzhong Qi, and Rui Zhang.  Neural relation extraction for knowledge base enrichment.  In _ACL_ , 2019.
  * Tu et al. (2019) Ming Tu, Guangtao Wang, Jing Huang, Yun Tang, Xiaodong He, and Bowen Zhou.  Multi-hop reading comprehension across multiple documents by reasoning over heterogeneous graphs.  In _ACL_ , 2019.
  * Turian et al. (2010) Joseph Turian, Lev Ratinov, and Yoshua Bengio.  Word representations: A simple and general method for semi-supervised learning.  In _ACL_ , 2010.
  * Vashishth et al. (2018) Shikhar Vashishth, Rishabh Joshi, Sai Suman Prayaga, Chiranjib Bhattacharyya, and Partha Talukdar.  RESIDE: Improving distantly-supervised neural relation extraction using side information.  In _EMNLP_ , 2018.
  * Vaswani et al. (2017) Ashish Vaswani, Noam Shazeer, Niki Parmar, Jakob Uszkoreit, Llion Jones, Aidan N Gomez, Łukasz Kaiser, and Illia Polosukhin.  Attention is all you need.  In _NIPS_ , 2017.
  * Veličković et al. (2018) Petar Veličković, Guillem Cucurull, Arantxa Casanova, Adriana Romero, Pietro Liò, and Yoshua Bengio.  Graph attention networks.  In _ICLR_ , 2018.
  * Vrandečić and Krötzsch (2014) Denny Vrandečić and Markus Krötzsch.  Wikidata: A free collaborative knowledge base.  _Communications of the ACM_ , 2014.
  * Wang et al. (2019) Hong Wang, Christfried Focke, Rob Sylvester, Nilesh Mishra, and William W. J. Wang.  Fine-tune BERT for DocRED with two-step process.  _ArXiv_ , 2019.
  * Wang et al. (2017) Wenhui Wang, Nan Yang, Furu Wei, Baobao Chang, and Ming Zhou.  Gated self-matching networks for reading comprehension and question answering.  In _ACL_ , 2017.
  * Wei et al. (2020) Zhepei Wei, Jianlin Su, Yue Wang, Yuan Tian, and Yi Chang.  A novel cascade binary tagging framework for relational triple extraction.  In _ACL_ , 2020.
  * Welbl et al. (2018) Johannes Welbl, Pontus Stenetorp, and Sebastian Riedel.  Constructing datasets for multi-hop reading comprehension across documents.  In _TACL_ , 2018.
  * Wu et al. (2019) Shanchan Wu, Kai Fan, and Qiong Zhang.  Improving distantly supervised relation extraction with neural noise converter and conditional optimal selector.  In _AAAI_ , 2019.
  * Wu et al. (2017) Yi Wu, David Bamman, and Stuart Russell.  Adversarial training for relation extraction.  In _EMNLP_ , 2017.
  * Xu et al. (2015) Yuning Xu, Lili Mou, Ge Li, Yunchuan Chen, Hao Peng, and Zhi Jin.  Classifying relations via long short term memory networks along shortest dependency paths.  In _EMNLP_ , 2015.
  * Yaghoobzadeh et al. (2017) Yadollah Yaghoobzadeh, Heike Adel, and Hinrich Schütze.  Noise mitigation for neural entity typing and relation extraction.  In _EACL_ , 2017.
  * Yao et al. (2019) Yuan Yao, Deming Ye, Peng Li, Xu Han, Yankai Lin, Zhenghao Liu, Zhiyuan Liu, Lixin Huang, Jie Zhou, and Maosong Sun.  DocRED: A large-scale document-level relation extraction dataset.  In _ACL_ , 2019.
  * Yates et al. (2007) Alexander Yates, Michael Cafarella, Michele Banko, Oren Etzioni, Matthew Broadhead, and Stephen Soderland.  TEXTRUNNER: Open information extraction on the web.  In _NAACL-HLT_ , 2007.
  * Ye and Ling (2019) Zhi-Xiu Ye and Zhen-Hua Ling.  Distant supervision relation extraction with intra-bag and inter-bag attentions.  In _NAACL-HLT_ , 2019.
  * Yu et al. (2018) Adams Wei Yu, David Dohan, Quoc Le, Thang Luong, Rui Zhao, and Kai Chen.  Fast and accurate reading comprehension by combining self-attention and convolution.  In _ICLR_ , 2018.
  * Zeng et al. (2014) Daojian Zeng, Kang Liu, Siwei Lai, Guangyou Zhou, and Jun Zhao.  Relation classification via convolutional deep neural network.  In _COLING_ , 2014.
  * Zeng et al. (2015) Daojian Zeng, Kang Liu, Yubo Chen, and Jun Zhao.  Distant supervision for relation extraction via piecewise convolutional neural networks.  In _EMNLP_ , 2015.
  * Zeng et al. (2020) Daojian Zeng, Haoran Zhang, and Qianying Liu.  CopyMTL: Copy mechanism for joint extraction of entities and relations with multi-task learning.  In _AAAI_ , 2020.
  * Zeng et al. (2018) Xiangrong Zeng, Daojian Zeng, Shizhu He, Kang Liu, and Jun Zhao.  Extracting relational facts by an end-to-end neural model with copy mechanism.  In _ACL_ , 2018.
  * Zhang et al. (2018) Yuhao Zhang, Peng Qi, and Christopher D. Manning.  Graph convolution over pruned dependency trees improves relation extraction.  In _EMNLP_ , 2018.
  * Zheng et al. (2017) Suncong Zheng, Feng Wang, Hongyun Bao, Yuexing Hao, Peng Zhou, and Bo Xu.  Joint extraction of entities and relations based on a novel tagging scheme.  In _ACL_ , 2017.
  * Zhou and Su (2002) GuoDong Zhou and Jian Su.  Named entity recognition using an HMM-based chunk tagger.  In _ACL_ , 2002.