DEEP NEURAL NETWORKS FOR
RELATION EXTRACTION

TAPAS NAYAK
(B.E. & M.E., Jadavpur University, India)

A THESIS SUBMITTED FOR THE DEGREE OF
DOCTOR OF PHILOSOPHY
DEPARTMENT OF COMPUTER SCIENCE
SCHOOL OF COMPUTING
NATIONAL UNIVERSITY OF SINGAPORE

2020

Supervisor:
Professor Ng Hwee Tou

Examiners:
Associate Professor Kan Min Yen
Associate Professor Ng Teck Khim
Assistant Professor Huang Ruihong (Texas A&M University)

Declaration

I hereby declare that this thesis is my original work and it has been written
by me in its entirety. I have duly acknowledged all the sources of information
that have been used in this thesis.

This thesis has also not been submitted for any degree in any university
previously.

Tapas Nayak

Acknowledgements

I would like to express my deepest gratitude to my advisor, Professor Ng Hwee
Tou, for his valuable support. His knowledge and critical analysis have helped
me to shape my research. Discussions with him have helped me a lot to improve
my research capabilities. I have enjoyed working in a research environment
that gives me ample opportunities for original thinking and initiatives.

Also, I would like to thank the board of examiners, Associate Professor Kan
Min Yen, Associate Professor Ng Teck Khin, and Assistant Professor Huang
Ruihong for their valuable comments and insights.

I want to thank my friends and colleagues in the NUS NLP group for their help
and support. It was a great pleasure to work with them.

Finally, I want to dedicate this thesis to my parents and my sisters for their
support and encouragement.

###### Contents

  1. 1 Introduction
    1. 1.1 Distant Supervision
    2. 1.2 Task Formalization
    3. 1.3 Scope of the Thesis
    4. 1.4 Contributions of the Thesis
    5. 1.5 Organization of the Thesis
  2. 2 Neural Networks
    1. 2.1 Feed-Forward Neural Networks
    2. 2.2 Convolutional Neural Networks
    3. 2.3 Recurrent Neural Networks
      1. 2.3.1 Long Short-Term Memory
    4. 2.4 Neural Attention Networks
    5. 2.5 Graph Convolutional Networks
    6. 2.6 Neural Network Training
  3. 3 Related Work
    1. 3.1 Knowledge Bases
    2. 3.2 Named Entity Recognition
    3. 3.3 Open Information Extraction
    4. 3.4 Relation Extraction
      1. 3.4.1 Pipeline Extraction Approaches
      2. 3.4.2 Noise Mitigation for Distantly Supervised Data
      3. 3.4.3 Zero-Shot or Few-Shot Relation Extraction
      4. 3.4.4 Joint Extraction Approaches
      5. 3.4.5 Datasets
    5. 3.5 Multi-Hop Natural Language Processing
  4. 4 Syntax-Focused Multi-Factor Attention for Relation Extraction
    1. 4.1 Motivation
    2. 4.2 Problem Definition
    3. 4.3 Model Description
      1. 4.3.1 Global Feature Extraction
      2. 4.3.2 Attention Modeling
      3. 4.3.3 Multi-Factor Attention
      4. 4.3.4 Relation Extraction
      5. 4.3.5 Loss Function
    4. 4.4 Experiments
      1. 4.4.1 Datasets
      2. 4.4.2 Evaluation Metrics
      3. 4.4.3 Parameter Settings
      4. 4.4.4 Baselines
      5. 4.4.5 Experimental Results
    5. 4.5 Analysis and Discussion
      1. 4.5.1 Varying the Number of Factors
      2. 4.5.2 Effectiveness of Model Components
      3. 4.5.3 Error Analysis
    6. 4.6 Summary
  5. 5 Encoder-Decoder Models for Joint Entity and Relation Extraction
    1. 5.1 Motivation
    2. 5.2 Problem Definition
    3. 5.3 Model Description
      1. 5.3.1 Embedding Layer & Encoder
      2. 5.3.2 Word-level Decoder & Copy Mechanism
      3. 5.3.3 Pointer Network-Based Decoder
      4. 5.3.4 Attention Modeling
      5. 5.3.5 Loss Function
    4. 5.4 Experiments
      1. 5.4.1 Datasets
      2. 5.4.2 Evaluation Metrics
      3. 5.4.3 Parameter Settings
      4. 5.4.4 Baselines
      5. 5.4.5 Experimental Results
    5. 5.5 Analysis and Discussion
      1. 5.5.1 Comparison between the Two Decoding Frameworks
      2. 5.5.2 Ablation Studies
      3. 5.5.3 Performance Analysis
      4. 5.5.4 Error Analysis
    6. 5.6 Summary
  6. 6 A Hierarchical Entity Graph Convolutional Network for Relation Extraction across Documents
    1. 6.1 Motivation
    2. 6.2 Problem Definition
    3. 6.3 Multi-Hop Dataset Construction
      1. 6.3.1 Dataset Statistics
    4. 6.4 Model Description
      1. 6.4.1 Document Encoding Layer
      2. 6.4.2 Hierarchical Entity Graph Convolutional Layers
      3. 6.4.3 Relation Classifier
      4. 6.4.4 Loss Function
    5. 6.5 Experiments
      1. 6.5.1 Evaluation Metrics
      2. 6.5.2 Parameter Settings
      3. 6.5.3 Baselines
      4. 6.5.4 Experimental Results
    6. 6.6 Analysis & Discussion
      1. 6.6.1 Varying the Number of GCN Layers
      2. 6.6.2 Effectiveness of Model Components
      3. 6.6.3 Edge Ablation
      4. 6.6.4 Error Analysis
    7. 6.7 Summary
  7. 7 Conclusion and Future Work

## Summary

A knowledge base (KB) is a useful resource for many natural language
processing tasks. KBs contain real-world entities and relations among them
which can help downstream tasks such as question answering. A triplet of two
entities and a relation between them is called a relation tuple. Existing KBs
such as Freebase, Wikidata, and DBpedia contain a large number of relation
tuples. But these KBs are built by crowd workers and it takes much time and
effort to build them. The automatic extraction of relation tuples from natural
language texts is referred to as relation extraction. In this thesis, we
tackle this task using novel deep neural network models.

First, we use a pipeline approach for this task, where we assume that the
entities have already been identified by an external named entity recognition
system. We propose a syntax-focused multi-factor attention model to find the
relation between two entities. We use the syntactic distance of words from the
entities to determine their importance in establishing the relation between
the two given entities. We also use multi-factor attention to focus on
multiple pieces of evidence present in a text to support the relation. Our
proposed model achieves significant improvements over prior works on widely
used relation extraction datasets.

Second, we tackle the task of joint entity and relation extraction, where
entities are not identified beforehand. There may be multiple relation tuples
present in a sentence, and these relations may share one or both entities
among them. Extracting such relation tuples with full entity names from
sentences is a difficult task. We propose two approaches to use encoder-
decoder networks for joint extraction of entities and relations. In the first
approach, we propose a representation scheme for relation tuples that enables
the decoder to generate one token at a time (like machine translation models)
and still extract 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. Our proposed models outperform prior works on widely used relation
extraction datasets.

Finally, we extend our work to multi-hop relation extraction. Distantly
supervised relation extraction models mostly focus on sentence-level relation
extraction, where the two entities (subject and 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 the
common entities. The relation between the two 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 previous
sentence-level or document-level extraction datasets that are available in the
public domain. To solve this task, we propose a hierarchical entity graph
convolutional network (HEGCN) model that consists 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 on our 2-hop relation extraction dataset and it can be readily
extended to N-hop datasets.

###### List of Tables

  1. 1.1 Binary vs n-ary relation tuple.
  2. 1.2 The use of a knowledge base for question answering.
  3. 1.3 A knowledge base represented as set of relation tuples.
  4. 1.4 Examples of relation tuples found in free texts.
  5. 1.5 Examples of distantly supervised clean and noisy samples.
  6. 4.1 Statistics of the NYT10 and NYT11 dataset.
  7. 4.2 Performance comparison of different models on the two datasets. * denotes a statistically significant improvement over the previous best state-of-the-art model with $p<0.01$ under the bootstrap paired t-test. † denotes the previous best state-of-the-art model.
  8. 4.3 Performance comparison of our model with different values of $m$ on the two datasets. $m$ refers to the multi-factor count.
  9. 4.4 Effectiveness of model components ($m=4$) on the NYT11 dataset. $m$ refers to the multi-factor count. $ws$ is the dependency window size used in Eq. (4.10) and Eq. (4.11).
  10. 5.1 Relation tuple representation for encoder-decoder models.
  11. 5.2 Examples of different classes of overlapping relation tuples.
  12. 5.3 Statistics of train/test split of the two datasets.
  13. 5.4 Performance comparison of the models on the two datasets. The rows with * show the median of five runs.
  14. 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.
  15. 5.6 Comparison on entity and relation generation tasks.
  16. 5.7 % errors for wrong ordering and entity mismatch.
  17. 6.1 Examples of 2-hop relations.
  18. 6.2 A multi-hop question-answer instance from the WikiHop dataset.
  19. 6.3 Statistics of the MHRED dataset.
  20. 6.4 Statistics of the common entities in the MHRED dataset.
  21. 6.5 The number of relations in various relation extraction datasets. $R$ is the set of positive relations.
  22. 6.6 Performance comparison of the models on the MHRED dataset.
  23. 6.7 The ablation study of the HEGCN model with different numbers of convolutional layers (L1 and L2) in EMGCN and EGCN.
  24. 6.8 The ablation study of the different components of our HEGCN model.
  25. 6.9 The ablation study of the different types of edges in our HEGCN model.

###### List of Figures

  1. 1.1 An example of a tiny knowledge base.
  2. 1.2 The use of knowledge base in search engines. Source: https://www.google.co.in/search?q=Barack+Obama. Taken on 30 Oct 2020.
  3. 2.1 Recurrent Neural Network. Source: http://cstwiki.wtb.tue.nl/index.php?title=File:RNN-unrolled.png
  4. 2.2 A Multi-layer Graph Convolutional Network. Source: https://tkipf.github.io/graph-convolutional-networks
  5. 4.1 Architecture of our attention model with $m=1$, where $m$ is the multi-factor count. We have not shown the CNN-based global feature extraction here. FFN = feed-forward network.
  6. 4.2 An example dependency tree. The two numbers indicate the distance of the word from the head token of the two entities respectively along the dependency tree path.
  7. 4.3 Precision-Recall curve for the NYT10 (left) and NYT11 (right) datasets.
  8. 4.4 Performance comparison across different sentence lengths on the NYT10 (left) and NYT11 (right) datasets.
  9. 4.5 Performance comparison across different distances between entities on the NYT10 (left) and NYT11 (right) datasets.
  10. 5.1 The architecture of an encoder-decoder model (left) and a pointer network-based decoder block (right).
  11. 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.
  12. 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.
  13. 6.3 Entity mention graph and entity graph construction from Doc2 of Table 6.2.
  14. 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.

##  Chapter 1 Introduction

The Web is a huge source of unstructured texts. Humans can read and extract
important information from the Web. However, a machine cannot handle this
unstructured data very well. To extract important information from
unstructured text automatically, we need to convert this unstructured data to
some structured form which machines can understand easily. This is one of the
major goals of information extraction in computer science.

Information extraction (IE) research goes back to the late 1970s. JASPER was
the very first information extraction system built by Carnegie
Group111https://en.wikipedia.org/wiki/Carnegie_Group in the mid-1980s. In the
beginning of 1987, IE research was spurred by a series of Message
Understanding
Conferences222https://en.wikipedia.org/wiki/Message_Understanding_Conference
and most of the funding for this research came from the U.S. Defense Advanced
Research Projects Agency (DARPA333https://en.wikipedia.org/wiki/DARPA).

In recent years, with the growing amount of unstructured texts on the Web, the
field of information extraction has attracted much attention. Currently, the
Web is considered as a collection of documents. Users have to extract relevant
information from these documents on their own. Success in IE research can
convert unstructured documents to structured data and an automated system can
give users all relevant information rather than just some relevant documents.

An information extraction system is an automated system that takes a sentence
(mainly in the English language, but can be extended to other languages too)
and extracts important information and presents it in a machine-readable
structured format. Most IE systems extract binary relation tuples containing
two entities and a relation between them. Some IE systems keep additional
information like time, direction, and context too. They are called n-ary
tuples. Table 1.1 gives an example of a binary and an n-ary tuple.

Tuple | Sentence | Tuple | Sentence
---|---|---|---
arg1 | Eli Whitney | arg1 | Eli Whitney
rel | created | rel | created
arg2 | the cotton gin | arg2 | the cotton gin
|  | arg3 | in 1793
binary relation | n-ary relation
Table 1.1: Binary vs n-ary relation tuple.

A knowledge base (KB) is a good example of a large database that stores binary
relation tuples about real world entities. Freebase (Bollacker et al., 2008),
Wikidata (Vrandečić and Krötzsch, 2014), and DBpedia (Bizer et al., 2009) are
examples of large KBs. Figure 1.1 gives some idea about the structure of a KB.
This example KB has five entities: Barack Obama and Michele Obama of PERSON
type, and United States of America, Hawaii, and Honolulu of LOCATION type. In
addition, there exist a few relations among them, such as spouse, lives_in,
located_in, and capital.

Figure 1.1: An example of a tiny knowledge base. Figure 1.2: The use of
knowledge base in search engines. Source:
https://www.google.co.in/search?q=Barack+Obama. Taken on 30 Oct 2020.

These structured KBs are very useful for many downstream natural language
understanding tasks such as question answering. Factoid question answering is
an important task in natural language processing. With the help of KBs,
factoid questions can be answered easily as shown in Table 1.2. Many search
engines use knowledge bases to populate important information automatically as
infoboxes in search results as shown in Figure 1.2. The user can obtain
information about the entity from its infobox without going through the text.
This will save much time for the users.

Question | Answer
---|---
What is the capital of Hawaii ? | Honolulu
Who is the wife of Barack Obama ? | Michelle Obama
Table 1.2: The use of a knowledge base for question answering.

A graph is the most commonly used data structure to store the information of a
KB. The nodes of a graph represent the entities, and the directed edges
between the nodes represent the relations. This graph structure is shown in
our example KB in Figure 1.1. If a KB only includes binary relations where a
relation can have two entities, then such a KB can be represented as a set of
relation tuples. Each relation tuple consists of two entities and a relation
between them. We have shown in Table 1.3 how our example knowledge base in
Figure 1.1 can be represented as a set of tuples. This set contains the same
number of tuples (rows) as the number of directed edges in the graph.

Entity 1 | Entity 2 | Relation
---|---|---
Barack Obama | Michelle Obama | spouse
Michelle Obama | Barack Obama | spouse
Barack Obama | United State of America | lives_in
Michelle Obama | United State of America | lives_in
Hawaii | United State of America | located_in
Hawaii | Honolulu | capital
Table 1.3: A knowledge base represented as set of relation tuples.

###  1.1 Distant Supervision

Existing KBs such as Freebase, Wikidata, and DBpedia are built manually and it
takes much effort and time to do so. However, these KBs still have a large
number of missing links. On the other hand, we can find evidence of a large
number of relation tuples in free texts. We have included some examples of
such tuples and texts in Table 1.4. If we can extract relation tuples
automatically from text, we can build a KB from scratch or add new tuples to
the existing KBs without any manual effort. But to achieve this goal, we need
a large number of texts annotated with relations, each relating two entities,
and creating such a corpus manually is a daunting task.

Relation | Entity 1 | Entity 2 | Text
---|---|---|---
acted_in | Meera Jasmine | Sootradharan |  |  Meera Jasmine made her
---
debut in the Malayalam
film “Soothradharan” .
located_in | Chakkarakadavu | Kerala |  |  Chakkarakadavu is a
---
small village to the
east of the town of
Cherai, on Vypin
Island in Ernakulam
district, Kerala, India .
birth_place | Barack Obama | Hawaii |  |  Barack Obama was born
---
in Hawaii .
plays_for | Moussa Sylla | Horoya AC |  | Fodé Moussa Sylla is a
---
Guinean football player,
who currently plays for
Horoya AC .
owns | MTV Channel | Shakthi TV |  |  MTV Channel (Pvt) Ltd
---
is a Sri Lankan media
company which owns
three national television
channels - Shakthi TV,
Sirasa TV and TV 1 .
Table 1.4: Examples of relation tuples found in free texts.

Mintz et al. (2009), Riedel et al. (2010), and Hoffmann et al. (2011) proposed
the idea of distant supervision to automatically create such text-tuple
mapping without any human effort. In distant supervision, the tuples from an
existing KB are mapped to a free text corpus such as Wikipedia articles or
news articles (e.g., New York Times). The idea of distant supervision is that
if a sentence contains two entities of a tuple from a KB, that sentence can be
considered as the source of this KB tuple. On the other hand, if a sentence
contains two entities from a KB and there is no relation between these two
entities in the KB, that sentence is considered as a source of None tuple
between the two entities. These None samples are useful as distantly
supervised models consider only a limited set of positive relations. Any
relation outside this set is considered as None relation. This method can give
us a large number of tuple-to-text mappings which can be used to build
supervised models for this task. This idea of distant supervision can be
extended easily to single-document or multi-document relation extraction.

But the distantly supervised data may contain many noisy samples. Sometimes, a
sentence may contain the two entities of a positive tuple, but the sentence
may not express any relation between them. These kinds of sentences and entity
pairs are considered as noisy positive samples. Another set of noisy samples
comes from the way samples for None relation are created. If a sentence
contains two entities from the KB and there is no relation between these two
entities in the KB, this sentence and entity pair are considered as a sample
for None relation. But knowledge bases are often not complete and many valid
relations between entities in a KB are missing. So it may be possible that the
sentence contains information about some positive relation between the two
entities, but since that relation is not present in the KB, this sentence and
entity pair are incorrectly considered as a sample for None relation. These
kinds of sentences and entity pairs are considered as noisy negative samples.

We include examples of clean and noisy samples generated using distant
supervision in Table 1.5. The KB contains many entities out of which four
entities are Barack Obama, Hawaii, Karkuli, and West Bengal. Barack Obama and
Hawaii have a birth_place relation between them. Karkuli and West Bengal are
not connected by any relations in the KB. So we assume that there is no valid
relation between these two entities. The sentence in the first sample contains
the two entities Barack Obama and Hawaii, and it also contains information
about Obama being born in Hawaii. So this sentence is a correct source for the
tuple (Barack Obama, Hawaii, birth_place). So this is a clean positive sample.
The sentence in the second sample contains the two entities, but it does not
contain the information about Barack Obama being born in Hawaii. So it is a
noisy positive sample. In the case of the third and fourth sample, according
to distant supervision, they are considered as samples for None relation. But
the sentence in the third sample contains the information for the actual
relation located_in between Karkuli and West Bengal, even though the KB
happens not to contain the located_in relation relating Karkuli and West
Bengal. So the third sample is a noisy negative sample. The fourth sample is
an example of a clean negative sample.

Sentence | Entity 1 | Entity 2 |  | Distantly
---
Supervised
Relation
| Actual
---
Relation
Status
| Barack Obama
---
was born in
Hawaii .
| Barack
---
Obama
Hawaii | birth_place | birth_place | Clean
| Barack Obama
---
visited Hawaii .
| Barack
---
Obama
Hawaii | birth_place | None | Noisy
| Suvendu Adhikari
---
was born at
Karkuli in Purba
Medinipur in
West Bengal .
Karkuli |  | West
---
Bengal
None | located_in | Noisy
| Suvendu Adhikari,
---
transport minister
of West Bengal,
visited Karkuli .
Karkuli |  | West
---
Bengal
None | None | Clean
Table 1.5: Examples of distantly supervised clean and noisy samples.

Despite the presence of noisy samples, relation extraction models trained on
distantly supervised data have proven to be successful for relation
extraction. These models can be used to fill the missing facts of a KB by
automatically finding tuples from free texts. It can save much manual effort
towards completing an existing KB.

###  1.2 Task Formalization

The task of relation extraction is to find relation tuples from free texts
automatically. A relation extraction system takes a sentence and a set of
relations as input and outputs a set of relation tuples present in the
sentence. This task consists of two sub-tasks: (i) entity recognition and (ii)
relation classification. In the first sub-task, entities are identified in a
sentence. In the second sub-task, for each pair of entities, we classify the
relation between the two entities, or that no relation exists between the two
entities. This is a pipeline approach to solve this task. Another approach
attempts to find the entities and relations jointly (i.e., not in a pipeline
approach). In this thesis, we explore deep neural network models for relation
extraction at the sentence-level and beyond, in both pipeline and joint
extraction approaches.

###  1.3 Scope of the Thesis

Our goal is to use deep neural network models to find relation tuples from
free texts. In our first work, we explore a pipeline approach where we assume
that two entities are given and we need to find the relation between them, or
that no relation exists between them. In our second work, we explore a joint
extraction approach for entities and relations. We have proposed deep neural
models for this task and achieve significantly improved performance with both
approaches when evaluated on publicly available relation extraction datasets.
In our third work, we explore a new multi-hop relation extraction task, where
we use multiple documents to find relation tuples. This can help to extract a
higher number of relations from knowledge bases than sentence-level relation
extraction.

###  1.4 Contributions of the Thesis

The contributions of this thesis are three-fold as described below.

(1) We find that sentences found using distant supervision can be very long
and two entities can be located far from each other in a sentence. The pieces
of evidence supporting the presence of a relation between two entities may not
be very direct, since the entities may be connected via some indirect links
such as a third entity or via co-reference. Relation extraction in such
scenarios becomes more challenging, as we need to capture the long-distance
interaction among the entities and other words in the sentence. Also, the
words in a sentence do not contribute equally in identifying the relation
between the two entities. To address this issue, we propose a novel and
effective attention model which incorporates syntactic information of the
sentence and a multi-factor attention mechanism. Experiments on the New York
Times corpus show that our proposed model outperforms prior state-of-the-art
models. This work has been published as a full paper in CoNLL 2019.

(2) In the above-mentioned approach, we have to consider all possible pairing
of entities and it will give a large number for None relations. Most prior
work adopted such a pipeline approach, where entities were identified first
followed by finding the relations among them, thus missing the interaction
among the relation tuples in a sentence. In our next work, we explore how to
extract entities and relations jointly. There may be multiple relation tuples
present in a text and they may share one or both entities among them. We
propose two approaches to use encoder-decoder architecture for jointly
extracting entities and relations. In the first approach, we propose a
representation scheme for relation tuples which enables the decoder to
generate one word at a time like machine translation models. This approach
still finds all the tuples present in a sentence with full entity names of
different lengths and with overlapping entities. In the second approach, we
propose a pointer network-based decoding approach where an entire tuple is
generated at every time step. Experiments on the publicly available New York
Times corpus show that our proposed approaches outperform previous work and
achieve significantly higher F1 scores. This work has been published as a full
paper in AAAI 2020.

(3) Distantly supervised relation extraction models mostly focus on sentence-
level relation extraction, where the two entities (subject and 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 through some common
entities. We can find a chain of entities from the subject entity to the
object entity via the common entities. The relation between the subject and
object entity 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 2-hop dataset covers a higher
number of relations than the previous sentence-level or document-level
datasets. We also propose a hierarchical graph convolutional network (HEGCN)
model consisting of a two-level hierarchy of graph convolutional networks to
solve this task. The first-level GCN of the hierarchy captures the relation
among the entity mentions within a document, and the second-level GCN of the
hierarchy captures the relation among the entities across the documents in a
chain. Our proposed HEGCN model improves the performance on our 2-hop relation
extraction dataset and it can be readily extended to N-hop datasets.

###  1.5 Organization of the Thesis

This thesis is organized as follows. We give a brief introduction to neural
networks in Chapter 2. In Chapter 3, we discuss related work on knowledge
bases, named entity recognition, open information extraction, relation
extraction, and multi-hop processing. In Chapter 4, we describe our proposed
syntax-focused multi-factor attention model for relation extraction. In
Chapter 5, we describe how encoder-decoder models can be used effectively to
jointly extract entities and relations. We describe our work on the multi-hop
relation extraction task in Chapter 6. Finally, we conclude the thesis in
Chapter 7.

##  Chapter 2 Neural Networks

In this chapter, I briefly describe the neural networks that we have used in
our models and the algorithms that we have used to train these models.

###  2.1 Feed-Forward Neural Networks

Feed-forward neural networks are a class of neural networks where information
flows only in one direction. These networks consist of an input layer, an
output layer, and one or more hidden layers. They are often referred to as
multi-layer perceptron. Each hidden layer applies a function to its input and
forwards the output to the next layer. This function is implemented using a
linear transformation followed by a non-linear transformation. This non-
linearity helps the feed-forward network to approximate more complex
functions. The most widely used non-linear functions are sigmoid ($\sigma$),
tanh, and ReLU. Another important non-linear function is softmax which is
often used at the output layer for normalization. These non-linear functions
are often called activation functions and are also used across other neural
networks described in later sections. The following are the definitions of
these non-linear functions with input $\mathbf{x}$.

$\displaystyle\sigma(\mathbf{x})=\frac{1}{1+e^{-\mathbf{x}}}$ (2.1)
$\displaystyle\text{tanh}(\mathbf{x})=\frac{e^{\mathbf{x}}-e^{-\mathbf{x}}}{e^{\mathbf{x}}+e^{-\mathbf{x}}}$
(2.2) $\displaystyle\text{ReLU}(\mathbf{x})=\text{max}(0,\mathbf{x})$ (2.3)
$\displaystyle\text{softmax}(\mathbf{x})=\frac{e^{\mathbf{x}}}{\sum e^{x}}$
(2.4)

A feed-forward network consisting of a single hidden layer implements the
following function (Eq. (2.5)) with input $\mathbf{x}$.

$\displaystyle\text{FFN}(\mathbf{x})=\rho(\mathbf{W}_{2}(\rho(\mathbf{W}_{1}\mathbf{x}+\mathbf{b}_{1}))+\mathbf{b}_{2})$
(2.5)

Here, $\mathbf{W}_{1}$ and $\mathbf{b}_{1}$ are the trainable parameters of
the hidden layer, whereas $\mathbf{W}_{2}$ and $\mathbf{b}_{2}$ are the
trainable parameters for the output layer. $\rho(.)$ is any non-linear
activation function described above.

###  2.2 Convolutional Neural Networks

Convolutional neural networks (CNN) (LeCun et al., 1989) are a special kind of
neural networks that work on grid-like topology such as image data (2D grid of
pixels) and text data (1D grid of word vectors). CNN is used to extract
important features from data automatically. Here, I will describe the CNN in
the context of text data. The tokens in the text can be represented as a
sequence of vectors $\\{\mathbf{x}_{1},\mathbf{x}_{2},.....,\mathbf{x}_{n}\\}$
where $\mathbf{x}\in\mathbb{R}^{d}$ and $n$ is the sequence length. Eq. (2.6)
defines the convolution function for text data. $\|$ is the concatenation
operation.

$\displaystyle
c_{i}=\mathbf{f}^{T}(\mathbf{x}_{i}\|\mathbf{x}_{i+1}\|....\|\mathbf{x}_{i+k-1})$
(2.6) $\displaystyle c_{max}=\text{max}(c_{1},c_{2},....,c_{n})$ (2.7)
$\displaystyle\mathbf{v}_{max}=[c_{max}^{1},c_{max}^{2},....,c_{max}^{f_{k}}]$
(2.8) $\displaystyle c_{avg}=\frac{c_{1}+c_{2}+....+c_{n}}{n}$ (2.9)
$\displaystyle\mathbf{v}_{avg}=[c_{avg}^{1},c_{avg}^{2},....,c_{avg}^{f_{k}}]$
(2.10)

$\mathbf{f}$ is a convolutional filter vector of length $kd$ where $k$ is the
filter width and superscript $T$ represents the transpose operation. The index
$i$ moves from $1$ to $n$ and produces a set of scalar values
$\\{c_{1},c_{2},.....,c_{n}\\}$. These scalar values represent the local
features of the data. Convolutional operations are followed by a pooling
operation such as max-pooling (Eq. (2.7)) or average pooling (Eq. (2.9)). The
pooled values across multiple filters are concatenated to obtain the feature
vector. With $f_{k}$ number of filters, we get a feature vector
$\mathbf{v}_{max}$ (Eq. (2.8)) or $\mathbf{v}_{avg}$ (Eq. (2.10)) of length
$f_{k}$.

###  2.3 Recurrent Neural Networks

Recurrent neural networks (RNN) are a special kind of neural networks to
process sequential data such as text. These networks contain a feedback loop
that helps to remember past information. Figure 2.1 shows the unrolled version
of a recurrent network. The unrolled version looks like a multi-layer feed-
forward network except that parameters are shared across the time steps in
RNN.

Figure 2.1: Recurrent Neural Network. Source:
http://cstwiki.wtb.tue.nl/index.php?title=File:RNN-unrolled.png

Though there are many different versions of RNN, the following is the widely
used one (Elman, 1990).

$\displaystyle\mathbf{h}_{t}=\rho(\mathbf{W}_{h}\mathbf{x}_{t}+\mathbf{U}_{h}\mathbf{h}_{t-1}+\mathbf{b}_{h})$
(2.11)
$\displaystyle\mathbf{y}_{t}=\rho(\mathbf{W}_{y}\mathbf{h}_{t}+\mathbf{b}_{y})$
(2.12)

where $\rho(.)$ is any non-linear activation function, and $\mathbf{x}_{t}$
and $\mathbf{h}_{t}$ are the input and hidden state at time step $t$,
respectively. $\mathbf{W}_{h}$, $\mathbf{W}_{y}$, $\mathbf{U}_{h}$,
$\mathbf{b}_{h}$, and $\mathbf{b}_{y}$ are the network parameters and are
learned during training. The hidden state ($\mathbf{h}_{t}$) is responsible
for remembering past information for this network.

Due to the successive use of the activation function on the hidden state of
the RNN (Eq. (2.11)), RNN suffers from the vanishing or exploding gradient
problem for long sequences. The exploding gradient problem can be solved by
clipping the gradient up to a certain threshold, but the vanishing gradient
problem cannot be solved that easily. Hochreiter and Schmidhuber (1997)
proposed long short-term memory (LSTM) and Cho et al. (2014) proposed gated
recurrent unit (GRU) to address the vanishing gradient problem for long
sequences. We have used the LSTM network extensively in this thesis and will
discuss it briefly here.

####  2.3.1 Long Short-Term Memory

Hochreiter and Schmidhuber (1997) solved the vanishing gradient problem in
RNNs by introducing control gates in the network. They used three control
gates as forget gate, input gate, and output gate. The forget gate
($\mathbf{f}_{t}$) is used to control how much past information to forget. The
input gate ($\mathbf{i}_{t}$) is used to control how much current information
has to be kept. The output gate ($\mathbf{o}_{t}$) is used to control the
exposure of the output. They also added a cell state ($\mathbf{c}_{t}$) in RNN
to remember the past information effectively. The following equations
summarize the functionality of an LSTM network.

$\displaystyle\mathbf{i}_{t}=\sigma(\mathbf{W}_{i}\mathbf{x}_{t}+\mathbf{U}_{i}\mathbf{h}_{t-1}+\mathbf{b}_{i})$
$\displaystyle\mathbf{f}_{t}=\sigma(\mathbf{W}_{f}\mathbf{x}_{t}+\mathbf{U}_{f}\mathbf{h}_{t-1}+\mathbf{b}_{f})$
$\displaystyle\tilde{\mathbf{c}}_{t}=\tanh(\mathbf{W}_{c}\mathbf{x}_{t}+\mathbf{U}_{c}\mathbf{h}_{t-1}+\mathbf{b}_{c})$
$\displaystyle\mathbf{c}_{t}=\mathbf{i}_{t}\circ\tilde{\mathbf{c}}_{t}+\mathbf{f}_{t}\circ\mathbf{c}_{t-1}$
$\displaystyle\mathbf{o}_{t}=\sigma(\mathbf{W}_{o}\mathbf{x}_{t}+\mathbf{U}_{o}\mathbf{h}_{t-1}+\mathbf{b}_{o})$
$\displaystyle\mathbf{h}_{t}=\mathbf{o}_{t}\circ\tanh(\mathbf{c}_{t})$ (2.13)

The input gate ($\mathbf{i}_{t}$), forget gate ($\mathbf{f}_{t}$), and output
gate ($\mathbf{o}_{t}$) use sigmoid ($\sigma$) activation function to control
the information flow. A $0$ output of this activation means no information
will pass through and a $1$ output of this activation means full information
will pass through. The cell state ($\mathbf{c}_{t}$) is updated without any
activation function, thus the problem of gradient becoming very low (vanishing
gradient) is eliminated.

###  2.4 Neural Attention Networks

Simple CNN and LSTM networks treat all the words that are present in a
sentence equally. But this is not appropriate for most NLP tasks, where some
words carry more information than others specific to the task. We need neural
models that can automatically learn which words are more important than
others. These kinds of networks are called attention networks. An attention
network includes one or more attention layers where each layer contains
trainable parameters. We learn the weights of these parameters during the
training process. An attention layer assigns normalized attention scores to
all the words, where some words get higher scores, and some get lower scores.
In this way, important words contribute more to the current prediction than
the others. This idea leads to better performance on the task. Bahdanau et al.
(2015) used such attention networks for neural machine translation. Vaswani et
al. (2017) showed that simple feed-forward neural networks with attention
achieve performance similar to LSTM networks.

###  2.5 Graph Convolutional Networks

Convolutional neural networks (CNN) and recurrent neural networks (RNN) mostly
work on linear data. But many real-world datasets come in the form of a graph
structure. It is very challenging to use CNN or RNN on an arbitrary graph
structure. Graph convolutional networks (GCN) are generalized neural
architectures that can work on any arbitrary graph structure. Figure 2.2 shows
a general architecture of a multi-layer graph convolutional network.

Figure 2.2: A Multi-layer Graph Convolutional Network. Source:
https://tkipf.github.io/graph-convolutional-networks

A graph $\mathcal{G}=\\{\mathcal{V},\mathcal{E}\\}$ consists of a set of nodes
$\mathcal{V}$ and a set of edges $\mathcal{E}$ that connect the nodes. A graph
convolutional network takes the following two inputs:

  1. 1.

A feature vector $\mathbf{x}_{i}\in\mathbb{R}^{d}$ for every node $i$ in
$\mathcal{G}$, where $d$ is the dimension of the input feature vector. The
vectors of $n$ nodes in $\mathcal{G}$ can be summarized as a matrix
$\mathbf{X}\in\mathbb{R}^{n\times d}$.

  2. 2.

An adjacency matrix $\mathbf{A}$ of size $n\times n$ which describes the graph
structure. Generally, self-loops are added in $\mathbf{A}$ and it is
normalized.

A graph convolutional network produces a node-level output
$\mathbf{Z}\in\mathbb{R}^{n\times f}$ where $f$ is the dimension of the output
feature vector. A pooling mechanism can be used to model the graph-level
output from the node-level output depending on the task.

Every layer of a GCN can be described by the following function:

$\displaystyle\mathbf{H}^{l+1}=f(\mathbf{H}^{l},\mathbf{A})$ (2.14)

where $\mathbf{H}^{0}=\mathbf{X}$ and $\mathbf{H}^{L}=\mathbf{Z}$. $L$ is the
number of layers in the GCN and $f(.,.)$ is a parameterized function. As an
example, the following simple function can be used as $f(.,.)$ in GCN.

$\displaystyle
f(\mathbf{H}^{l},\mathbf{A})=\rho(\mathbf{A}\mathbf{W}^{l}\mathbf{H}^{l})$
(2.15)

where $\mathbf{W}^{l}$ is the weight matrix of the $l$th layer and $\rho(.)$
is any non-linear activation function such as ReLU.

###  2.6 Neural Network Training

Neural network models use a lot of parameters and we need to approximate the
optimal values of these parameters during training. The parameters are
initialized randomly and then during training, they are updated. A loss
function $C$ is used to estimate the difference between the network output and
target output. The goal of the training process is to minimize this loss
function. Network parameters $\theta$ are optimized using a gradient descent
algorithm so that the loss is minimized.

$\displaystyle\theta_{t+1}=\theta_{t}-\eta\dfrac{\partial{C}}{\partial\theta_{t}}$
(2.16)

Here, $\eta$ is called the step size or learning rate which is a
hyperparameter. The loss function $C$ can be calculated over the entire
training data, known as batch training. But this is computationally very
expensive if the size of the training data is large. Another way of measuring
the loss function $C$ is by each instance of the training data. So we need to
update the network parameters $\theta$ after each instance. This is the
stochastic gradient descent algorithm (SGD). However, this will make the
training process very slow for large training data. A middle path is to update
the parameters after each mini-batch of smaller sizes like 32/40/50. This is
called mini-batch training. Samples in each mini-batch are chosen randomly
from the training data without replacement. We have used this mini-batch
training to train our models.

The SGD algorithm has two major problems. First, the value of $\eta$ has to be
chosen manually. If it is set too high, then the network may not converge and
if it is set too low, convergence will be very slow. Second, all parameters
are updated with the same learning rate. However, different parameters in a
neural network might need different learning rates to be optimized properly.
To solve these problems, several adaptive optimization algorithms are proposed
such as Adagrad (Duchi et al., 2011), RMSprop (unpublished work by Geoffrey
Hinton, 2012), and Adam (Kingma and Ba, 2015). These optimization algorithms
adapt the learning rate $\eta$ for each parameter differently during training.
We have used Adagrad and Adam optimization algorithms for our models.

Another important aspect of neural network training is back-propagation.
Neural networks consist of multiple layers and each layer has its parameters.
We need to update the parameters of all the layers based on the loss function.
This is achieved by the chain rule of differentiation. First, the parameters
of the output layer are updated, then the parameters of the layer below it are
updated, and so on. This process is repeated until the parameters of all the
layers are updated. This process of updating network parameters starting from
the output layer towards the input layer in backward fashion is referred to as
back-propagation.

##  Chapter 3 Related Work

In this chapter, we describe the different works that are connected to
relation extraction. We first describe the different knowledge bases available
that can be used for distant supervision. Next, we discuss the named entity
recognition task which can be used in pipeline approaches of relation
extraction. Then, we include a brief introduction of open information
extraction and its limitations. We then move to discuss the datasets and the
prior works on relation extraction. Finally, we finish the chapter by
introducing multi-hop natural language processing.

###  3.1 Knowledge Bases

In recent years, a number of research teams have created knowledge bases (KB)
which cover entities across multiple domains. Here, we briefly describe a few
such KBs: YAGO (Suchanek et al., 2007), Freebase (Bollacker et al., 2008),
Wikidata (Vrandečić and Krötzsch, 2014), DBpedia (Bizer et al., 2009), and
NELL (Mitchell and Fredkin, 2014).

##### YAGO

Yet Another Great Ontology (YAGO) is built by extracting facts from the
structured data that is present in Wikipedia and WordNet. YAGO uses Wikipedia
category pages to extract classes, entities, and relations between them. For
example, ‘Zidane’ is present in the category of ‘French football players’, so
YAGO extracts relations like (Zidane, is_citizen_of, France) and (Zidane,
is_a, football player) using handcrafted rules. However, Wikipedia category
pages are not useful to build an ontology. As an example, ‘Zidane’ is also
present in the category of ‘French football’, but ‘Zidane’ is a football
player, not a football. WordNet, on the other hand, provides a clean class
hierarchy, which is used by YAGO to build an ontology. YAGO efficiently
combines Wikipedia and WordNet to build the ontology and extract facts. As of
31 Oct 2020, YAGO contains more than 50 million entities and 2 billion facts.

##### Freebase

Freebase is a scalable database for relation tuples built by Metaweb
Technologies111https://en.wikipedia.org/wiki/Metaweb Inc. in 2007. Google
acquired the company in 2010 and shut down Freebase in 2016 after deciding to
transfer all its data to Wikidata. At the time of its release in 2007,
Freebase had 125 million entities and around 7,000 relations.

##### Wikidata

Wikidata is another large, free, and collaborative knowledge base built by
Wikimedia222https://www.wikimedia.org. Along with facts, Wikidata stores the
corresponding Wikipedia source page so that users can verify its validity. It
also provides the aliases for every relation and its brief description. It
stores facts in the form of items and statements. An item in Wikidata
represents an entity, and each item has multiple statements. Each statement
has a claim which consists of a property and its value. These properties are
like relations. As of 31 Oct 2020, Wikidata contains more than 90 million
items and more than 1.2 billion statements for over 8,060 properties.

##### DBpedia

DBpedia is another crowd-sourced project which extracts structured data from
multi-lingual Wikidata. It extracts information from Wikidata in two formats:
raw infobox extraction and mapping-based infobox extraction. In raw infobox
extraction, DBpedia extracts Wikidata infobox information and does not map
them to any ontology. In mapping-based extraction, an ontology is created with
a community effort, and Wikidata infobox extractions are mapped to that
ontology. As of 31 Oct 2020, the English version of DBpedia contains 4.58
million entities and 580 million facts about them.

##### NELL

Never-Ending Language Learner (NELL) is another system that automatically
extracts facts from the Web. NELL is a semi-supervised system which started
with an initial ontology of hundreds of categories and relations. It uses
around 10-15 seed examples for each category and relation. Along with this, it
takes 500 million web pages and accesses the remaining web pages through
Google search API as input. The goal of this system is to learn new instances
of categories and relations. This system runs 24/7 to learn new facts and uses
these facts to improve its learning algorithms for better extraction. As of 31
Oct 2020, NELL has accumulated over 50 million facts by reading the Web.

###  3.2 Named Entity Recognition

Named entity recognition (NER) is an important task in NLP and it helps many
other NLP applications such as information retrieval, question answering, and
relation extraction. As we discussed before, NER is the first step for
pipeline relation extraction models. The goal of the NER task is to identify
named entities such as person names, location names, and organization names in
a text. A sequence tagging approach, called the ‘BIESO’ tagging scheme, is
used to identify the entities in a text. In this tagging scheme, every token
of a text is assigned a tag out of the 5 tags ‘B’, ‘I’, ‘E’, ‘S’, and ‘O’. ‘B’
refers to the beginning of an entity, ‘I’ refers to the inside of an entity,
and ‘E’ refers to the end of an entity. ‘S’ is used to tag single-token
entities and ‘O’ is used to tag the non-entity tokens. An entity type is
appended as the suffix to a ‘B/I/E/S/O’ tag to indicate the type of the entity
such as PERSON, LOCATION, ORGANIZATION, GEOPOLITICAL ENTITY, etc. Several
named entity recognition shared tasks were organized with accompanying
datasets such as MUC (Grishman and Sundheim, 1996), CoNLL 2002 (Tjong Kim
Sang, 2002), CoNLL 2003 (Tjong Kim Sang and De Meulder, 2003), and ACE04
(Doddington et al., 2004).

Supervised learning models are popularly used to tackle the NER task. Zhou and
Su (2002) used the Hidden Markov Model (HMM) for NER on MUC-6 datasets. They
used orthographic features, trigger words, etc in their model. Malouf (2002)
used the Hidden Markov Model with maximum entropy for the same task. The
winner of the CoNLL 2002 shared task (Carreras et al., 2002) used binary
AdaBoost classifier with features like capitalization, trigger words,
gazetteers, etc. Takeuchi and Collier (2002) used SVM model for this task.
They used part-of-speech tags, orthographic features, nearby words, and tags
of previous tokens in their SVM model. Chieu and Ng (2002) proposed a maximum
entropy approach where they used document-level information along with
sentence-level information for the NER task. They used MUC-6 and MUC-7
datasets for their experiments. Chieu and Ng (2003) used a similar approach
for the CoNLL 2003 NER shared task.

##### Neural NER Models

Collobert and Weston (2008) proposed one of the first neural models for the
NER task. They represented the different features used for NER as vectors in
their model. Later, they replaced these manually extracted features with word
vectors (Collobert et al., 2011). Huang et al. (2015) proposed an LSTM-based
neural model with word embeddings for this task and achieved a high F1 score
on the CoNLL 2003 dataset. Ma and Hovy (2016) and Chiu and Nichols (2016) used
character-based embeddings along with word embeddings for this task. Their
experiments on the CoNLL 2003 dataset show that character-level embeddings
help in improving the performance of the task. Lample et al. (2016) also used
an LSTM-CRF model for this task and used CoNLL 2002 and 2003 datasets for
their experiments. Recently, contextualized word representations such as ELMo
(Peters et al., 2018) and BERT (Devlin et al., 2019) have proven very
effective for the NER task. Models with such representation (Straková et al.,
2019) achieved state-of-the-art performance on the CoNLL 2003 dataset.

##### Zero-Shot or Few-Shot NER

Zero-shot or few-shot named entity recognition is popular for low resource
languages or domains. Ma et al. (2016) proposed a label embedding method for
the zero-shot NER task. They used prototypical and hierarchical information to
learn the label embeddings and adapted a zero-shot framework for the NER task.
Fritzler et al. (2019) proposed a semi-supervised learning technique to tackle
the NER task using a prototypical network in a few-shot setting. It learns
intermediate representations of words that cluster well into named entity
classes. This property of the model allows classifying words with a limited
number of training instances, and can potentially be used as a zero-shot
learning method. Bari et al. (2020) proposed an unsupervised cross-lingual NER
model that can transfer knowledge from one language to another without using
any annotated data or parallel corpora.

###  3.3 Open Information Extraction

Open information extraction (OpenIE) is a generic form of relation extraction
which can extract any kind of relations with its arguments from free text.
Most OpenIE systems use hand-crafted rules or predefined sentence structures
to extract entities and relations from sentences. The advantage of such a
system is that it can work on texts from any domain. KnowItAll (Etzioni et
al., 2004), TEXTRUNNER (Yates et al., 2007), REVERB (Etzioni et al., 2011),
SRL-IE (Christensen et al., 2011), OLLIE (Mausam et al., 2012), and RELNOUN
(Pal and Mausam, 2016) are some examples of OpenIE systems which can extract
reliable facts from text.

##### KnowItAll

This is a rule-based OpenIE system that uses hand-made patterns to extract
facts from the Web. It also assigns a confidence score to the extracted tuples
based on point-wise mutual information (PMI) between words associated with the
identified entity or triple and pre-defined phrases for each entity or
relation.

##### TEXTRUNNER

This system is built based on the idea of the KnowItAll system, but there is
no need to give hand-crafted patterns to the system. It includes a self-
supervised learner that uses dependency parse trees to label its training data
as positive or negative samples. It marks the noun phrases in a dependency
parse tree as arguments and then finds the relation words between those
arguments. It groups a tuple as positive or negative based on certain
syntactic structures like the length of the dependency chain between two
arguments, the path between two arguments (that it should not cross sentence
boundary, etc. Then it uses these samples to train a naive Bayes classifier to
determine the trustworthiness of future tuples.

##### REVERB

This is an improved version of the TEXTRUNNER system. It uses additional
syntactic and lexical constraints to remove incoherent and uninformative
extractions.

##### SRL-IE

This is an open information extraction system based on a semantic role
labeling (SRL) system built at UIUC (Punyakanok et al., 2008). SRL is a common
NLP task of detecting semantic arguments associated with a predicate in a
sentence, and the classification of the arguments into different semantic
roles like agent, patient, instrument, etc. The predicates and arguments
extracted by an SRL system can be considered as relation tuples.

##### OLLIE

Open Language Learning for Information Extraction (OLLIE) attempts to fix the
major issues of the REVERB system. REVERB only extracts a relation based on a
verb. But some relations are based on noun phrases and not verbs. OLLIE starts
with tuples extracted by REVERB. It collects sentences from the Web and then
maps these tuples to the sentences. Using the dependency parse tree of these
sentences, OLLIE tries to generate some generic patterns for each relation.
OLLIE applies these learned patterns to extract more tuples from texts.

##### RELNOUN

RELNOUN is an open relation extraction module which is used to extract
relation tuples based on nouns instead of verbs. This system extracts tuples
from titles and entity attributes. RELNOUN uses part-of-speech (POS) tags and
noun phrase (NP) chunk patterns to extract noun-based tuples.

##### Limitations of OpenIE

Though open information extraction systems can extract a large number of
tuples from free texts, they have two major limitations:

  1. 1.

They extract a large number of uninformative tuples. Since every verb is
considered a potential relation, the number of uninformative tuples will be
very large. Removing uninformative tuples is a challenging task.

  2. 2.

They do not normalize the relations. Every verb is considered a separate
relation by open IE systems. However, different verbs can express the same
relation. Open IE systems do not group different verbs with the same meaning
into a single relation.

###  3.4 Relation Extraction

The limitations of open IE systems can be solved using closed domain relation
extraction (RE). We use supervised learning algorithms for this task. These
models work with a set of pre-defined relations. Thus the issues of
uninformative relations and normalization of relations do not arise. We
describe prior research and the available datasets on relation extraction
below.

####  3.4.1 Pipeline Extraction Approaches

In the beginning of IE research, pipeline approaches were quite popular. A
pipeline approach has two steps: (i) First, a named entity recognizer is used
to identify the named entities in a text. (ii) Next, a classification model is
used to find the relation between a pair of entities. The named entities
identified in the first step are mapped to the KB entities. Using distant
supervision, a large number of text-tuple pairs can be generated and they can
be used for creating supervised learning models for this task.

##### Feature-Based Models

Mintz et al. (2009) proposed a feature-based model for this task. They used
lexical features such as the sequence of words between two entities and their
part-of-speech (POS) tags, a flag indicating which entity appears first, $k$
tokens to the left of entity 1 and $k$ tokens to the right of entity 2,
syntactic features such as dependency path between two entities, and named
entity types of the two entities in their model. Riedel et al. (2010) proposed
multi-instance learning for this task to mitigate the problem of noisy
sentences obtained using the distant supervision method. They used a factor
graph to explicitly model the decision of whether two entities are related and
whether this relation is mentioned in a given sentence. Also, they applied
constraint-driven semi-supervision to train their model without any knowledge
about which sentences express the relations. Their multi-instance learning
model significantly improves the performance over the model proposed by Mintz
et al. (2009).

Hoffmann et al. (2011) and Surdeanu et al. (2012) proposed the idea of multi-
instance multi-relations to solve the problem of overlapping relations. They
used probabilistic graphical models that take a bag of sentences containing
two entities as input and find all possible relations between them. Similarly,
Ren et al. (2017) used a feature-based model to jointly predict the relation
between two entities and their fine-grained types. They used features like the
head tokens of two entities, tokens of two entities, tokens between the two
entities, their POS tags, ordering of the two entities, the distance between
them, and the Brown cluster333https://github.com/percyliang/brown-cluster of
each token in their model. They proposed a joint optimization framework to
learn the entity embeddings, relation embeddings, and fine-grained type
embeddings of the entities together.

##### CNN-Based Neural Models

Distributed representations of words as word embeddings have transformed the
way that natural language processing tasks like IE can be tackled. Word2Vec
(Mikolov et al., 2013) and GloVe (Pennington et al., 2014) are two sets of
large and publicly available word embeddings that are used for many NLP tasks.
Most neural network-based models for information extraction have used the
distributed representation of words as their core component. The high
dimensional distributed representation of words can encode important semantic
information about words, which is very helpful for identifying the relations
among the entities present in a sentence. Initially, neural models also follow
the pipeline approach to solve this task.

Zeng et al. (2014) used a convolutional neural network for relation
extraction. They used the pre-trained word embeddings of Turian et al. (2010)
to represent the tokens in a sentence and used two distance embedding vectors
to represent the distance of each word from the two entities. They used a
convolutional neural network (CNN) and max-pooling operation to extract a
sentence-level feature vector. This sentence representation is passed to a
feed-forward neural network with a softmax activation layer to classify the
relation.

Zeng et al. (2015) introduced a piecewise convolutional neural network (PCNN)
to improve relation extraction. Zeng et al. (2014) applied the max-pooling
operation across the entire sentence to get the single important feature from
the entire sentence for a particular convolutional filter. In PCNN, the max-
pooling operation is not performed for the entire sentence. Instead, the
sentence is divided into three segments: from the beginning to the argument
appearing first in the sentence, from the argument appearing first in the
sentence to the argument appearing second in the sentence, and from the
argument appearing second in the sentence to the end of the sentence. Max-
pooling is performed in each of these three segments and for each
convolutional filter to obtain three feature values. A sentence-level feature
vector is obtained by concatenating all such feature values and is given to a
feed-forward neural network with a softmax activation layer to classify the
relation.

##### Attention-Based Neural Models

Recently, attention networks have proven very useful for different NLP tasks.
Shen and Huang (2016) and Jat et al. (2017) used word-level attention model
for single-instance sentence-level relation extraction. Shen and Huang (2016)
proposed a combination of a convolutional neural network model and an
attention network. First, a convolution operation with max-pooling is used to
extract the global features of the sentence. Next, attention is applied to the
words of the sentence based on the two entities separately. The word embedding
of the last token of an entity is concatenated with the embedding of every
word. This concatenated representation is passed to a feed-forward layer with
tanh activation and then another feed-forward layer with softmax to get a
scalar attention score for every word of that entity. The word embeddings are
averaged based on the attention scores to get the attentive feature vectors.
The global feature vector and two attentive feature vectors for the two
entities are concatenated and passed to a feed-forward layer with softmax to
determine the relation.

Jat et al. (2017) used a bidirectional gated recurrent unit (Bi-GRU) (Cho et
al., 2014) to capture the long-term dependency among the words in the
sentence. The tokens vectors $\mathbf{x}_{t}$ are passed to a Bi-GRU layer.
The hidden vectors of the Bi-GRU layer are passed to a bi-linear operator
which is a combination of two feed-forward layers with softmax to compute a
scalar attention score for each word. The hidden vectors of the Bi-GRU layer
are multiplied by their corresponding attention scores for scaling up the
hidden vectors. A piecewise convolution neural network (Zeng et al., 2015) is
applied to the scaled hidden vectors to obtain the feature vector. This
feature vector is passed to a feed-forward layer with softmax to determine the
relation.

Lin et al. (2016) have used attention model for multi-instance relation
extraction. They applied attention over a bag of independent sentences
containing two entities to extract the relation between them. First, CNN-based
models are used to encode the sentences in a bag. Then a bi-linear attention
layer is used to determine the importance of each sentence in the bag. This
attention helps to mitigate the problem of noisy samples obtained by distant
supervision to some extent. The idea is that clean sentences get higher
attention scores over the noisy ones. The sentence vectors in the bag are
merged in a weighted average fashion based on their attention scores. The
weighted average vector of the sentences is passed to a feed-forward neural
network with softmax to determine the relation. This bag-level attention is
used only for positive relations and not used for None relation. The reason is
that the representations of the bags that express no relations are always
diverse and it is difficult to calculate suitable weights for them.

Ye and Ling (2019) used intra-bag and inter-bag attention networks in a multi-
instance setting for relation extraction. Their intra-bag attention is similar
to the attention used by Lin et al. (2016). Additionally, they used inter-bag
attention to address the noisy bag problem. They divide the bags belonging to
a relation into multiple groups. The attention score for each bag in a group
is obtained based on the similarity of the bags to each other within the
group. This inter-bag attention is used only during training as we do not know
the relations during testing.

##### Dependency-Based Neural Models

Some previous works have incorporated the dependency structure information of
sentences in their neural models for relation extraction. Xu et al. (2015)
used a long short-term memory network (LSTM) (Hochreiter and Schmidhuber,
1997) along the shortest dependency path (SDP) between two entities to find
the relation between them. Each token along the SDP is represented using four
embeddings – pre-trained word vector, POS tag embedding, embedding for the
dependency relation between the token and its child in the SDP, and embedding
for its WordNet (Fellbaum, 2000) hypernym. They divide the SDP into two sub-
paths: (i) The left SDP which goes from entity 1 to the common ancestor node
(ii) The right SDP which goes from entity 2 to the common ancestor node. This
common ancestor node is the lowest common ancestor between the two entities in
the dependency tree. The token vectors along the left SDP and right SDP are
passed to an LSTM layer separately. A pooling layer is applied to the hidden
vectors to extract the feature vector from the left SDP and right SDP. These
two vectors are concatenated and passed to a classifier to find the relation.

Liu et al. (2015) exploited the shortest dependency path (SDP) between two
entities and the sub-trees attached to that path (augmented dependency path)
for relation extraction. Each token in the SDP is represented using its pre-
trained embedding and its sub-tree representation. The sub-tree representation
of a token is obtained from the sub-tree of the dependency tree where the
token is the root node. The dependency relations are represented using
trainable embeddings. Each node in the sub-tree of a token receives
information from its children including the dependency relations. The sub-tree
representation of the token is obtained by following the sub-tree rooted at
the token from its leaf nodes to the root in a bottom-up fashion. Next, they
use CNN with max-pooling on the vectors of the sequence of the tokens and
dependency relations across the SDP. The output of the max-pooling operation
is passed to a classifier to find the relation.

Miwa and Bansal (2016) used a tree LSTM network along the shortest dependency
path (SDP) between two entities to find the relation between them. They used a
bottom-up tree LSTM and top-down tree LSTM in their model. In the bottom-up
tree LSTM, each node receives information from all of its children. The hidden
representation of the root node of this bottom-up tree LSTM is used as the
final output. In the top-down tree LSTM, each node receives the information
from its parent node. The hidden representations of the head token of two
entities are the final output of this tree LSTM. The representations of the
bottom-up tree LSTM and top-down tree LSTM are concatenated and passed to a
classifier to find the relation. They showed that using the SDP tree over the
full dependency tree is helpful as unimportant tokens for the relation are
ignored in the process.

##### Graph-Based Neural Models

Graph-based models are popular for many NLP tasks as they work on non-linear
structures. Quirk and Poon (2017) proposed a graph-based model for cross-
sentence relation extraction. They built a graph from the sentences where
every word is considered as a node in the graph. Edges are created based on
the adjacency of the words, dependency tree relations, and discourse
relations. They extract all the paths from the graph starting from entity 1 to
entity 2. Each path is represented by features such as lexical tokens, the
lemma of the tokens, POS tags, etc. They use all the path features to find the
relation between the two entities.

Peng et al. (2017) and Song et al. (2018b) used a similar graph for N-ary
cross-sentence relation extraction. Rather than using explicit paths, they
used an LSTM on a graph. A graph LSTM is a general structure for a linear LSTM
or tree LSTM. If the graph contains only the word adjacency edges, then the
graph LSTM becomes a linear LSTM. If the graph contains the edges from the
dependency tree, it becomes a tree LSTM. A general graph structure may contain
cycles. So Peng et al. (2017) divides this graph into two directed acyclic
graphs (DAG), where the forward DAG contains only the forward edges among the
tokens and the backward DAG contains only the backward edges among the tokens.
Each node has a separate forget gate for each of its neighbors. It receives
information from the neighbors and updates its hidden states using LSTM
equations (Hochreiter and Schmidhuber, 1997). If we only consider the word
adjacency edges, this graph LSTM becomes a bi-directional linear LSTM. Song et
al. (2018b) did not divide the graph into two DAGs, but directly used the
graph structure to update the states of the nodes. At time step $t$, each node
receives information from its neighbor from the previous time step and update
its hidden states using LSTM equations. This process is repeated $k$ number of
times where $k$ is a hyper-parameter.

Kipf and Welling (2017) and Veličković et al. (2018) proposed a graph
convolutional network (GCN) model which used simple linear transformations to
update the node states, unlike the graph LSTMs used by Peng et al. (2017) and
Song et al. (2018b). Kipf and Welling (2017) gave equal weights to the edges,
whereas Veličković et al. (2018) used an attention mechanism to assign
different weights to the edges. Vashishth et al. (2018), Zhang et al. (2018),
and Guo et al. (2019) used graph convolutional networks for sentence-level
relation extraction. They considered each token in a sentence as a node in the
graph and used the syntactic dependency tree to create a graph structure among
the nodes. Vashishth et al. (2018) used the GCN in a multi-instance setting.
They used a Bi-GRU layer and a GCN layer over the full dependency tree of the
sentences to encode them. The sentence representations in a bag were
aggregated and passed to a classifier to find the relation. Following Miwa and
Bansal (2016), Zhang et al. (2018) used only the shortest dependency path
(SDP) tree to build the adjacency matrix for the graph. Along with the SDP
tree, they included the edges that are distance $K$ away from the SDP where
$K$ is a hyper-parameter. Guo et al. (2019) proposed a soft pruning strategy
over the hard pruning strategy of Zhang et al. (2018) in their GCN model. They
considered the full dependency tree to build the adjacency matrix but using a
multi-head self attention-based soft pruning strategy, they can identify the
important and unimportant edges in the graph.

Sahu et al. (2019), Christopoulou et al. (2019), and Nan et al. (2020) used
GCN for document-level relation extraction. Sahu et al. (2019) considered each
token in a document as a node in a graph. They used syntactic dependency tree
edges, word adjacency edges, and coreference edges to create the connections
among the nodes. Christopoulou et al. (2019) considered the entity mentions,
entities, and sentences in a document as nodes of a graph. They used rule-
based heuristics to create the edges among these nodes. In their graph, each
node and each edge were represented by vectors. GCN was used to update the
vectors of nodes and edges. Finally, the edge vector between the two concerned
entities was passed to a classifier to find the relation. Nan et al. (2020)
considered the entity mentions, entities, and tokens on the shortest
dependency path between entity mentions as nodes in a graph. They used a
structure induction module to learn the latent structure of the document-level
graph. A multi-hop reasoning module was used to perform inference on the
induced latent structure, where representations of the nodes were updated
based on an information aggregation scheme.

##### Contextualized Embedding-Based Neural Models

Contextualized word embeddings such as ELMo (Peters et al., 2018), BERT
(Devlin et al., 2019), and SpanBERT (Joshi et al., 2019) can be useful for
relation extraction. These language models are trained on large corpora and
can capture the contextual meaning of words in their vector representations.
All neural models that are proposed for relation extraction use word
representations such as Word2Vec (Mikolov et al., 2013) or GloVe (Pennington
et al., 2014) in their word embedding layer. Contextualized embeddings can be
added in the embedding layer of the relation extraction models to improve
their performance further. The SpanBERT model shows significant improvement in
performance on the TACRED dataset. Joshi et al. (2019) replaced the entity 1
token with its type and SUBJ such as PER-SUBJ and entity 2 token with its type
and OBJ such as LOC-OBJ in the sentences to train the model. Finally, they
used a linear classifier on top of the CLS token vector to find the relation.

Wang et al. (2019) proposed two-step fine-tuning of BERT for document-level
relation extraction on the DocRED dataset. In the first step, they used BERT
to identify whether or not there is a relation between two entities. In the
second step, they used BERT to classify the relation. Nan et al. (2020) also
used BERT in their model to show that it significantly improved the
performance on the DocRED dataset compared to GloVe vectors. Han and Wang
(2020) used BERT to identify all possible relations among the entity pairs in
documents in a single pass. They used entity types and special tokens to mark
all the entity mentions in documents. All entity mentions of an entity
received the same special token. Documents were passed to a pre-trained BERT
model. An entity mention vector was obtained by averaging the BERT outputs of
the entity mention tokens. An entity vector was obtained by averaging all the
entity mention vectors of that entity. A bilinear classifier was used to
classify the relation between two entities. Tang et al. (2020a) proposed a
hierarchical inference network for document-level relation extraction. They
also showed that using BERT in their model improved performance significantly.

####  3.4.2 Noise Mitigation for Distantly Supervised Data

The presence of noisy samples in distantly supervised data adversely affects
the performance of models. Researchers have used different techniques in their
models to mitigate the effects of noisy samples to make them more robust.
Multi-instance relation extraction is one of the popular methods for noise
mitigation. Riedel et al. (2010), Hoffmann et al. (2011), Surdeanu et al.
(2012), Lin et al. (2016), Yaghoobzadeh et al. (2017), Vashishth et al.
(2018), Wu et al. (2019), and Ye and Ling (2019) used this multi-instance
learning concept in their proposed relation extraction models. For each entity
pair, they used all the sentences that contained these two entities to find
the relation between them. Their goal was to reduce the effect of noisy
samples using this multi-instance setting. They used different types of
sentence selection mechanisms to give importance to the sentences that
contained relation-specific keywords and ignored the noisy sentences. Ren et
al. (2017) and Yaghoobzadeh et al. (2017) used the multi-task learning
approach for mitigating the influence of noisy samples. They used fine-grained
entity typing as an extra task in their model.

Wu et al. (2017) used an adversarial training approach for the same purpose.
They added noise to the word embeddings to make the model more robust for
distantly supervised training. Qin et al. (2018a) used a generative
adversarial network (GAN) to address the issue of noisy samples in relation
extraction. They used a separate binary classifier as a generator in their
model for each positive relation class to identify the true positives for that
relation and filter out the noisy ones. Qin et al. (2018b) used reinforcement
learning to identify the noisy samples for the positive relation classes. He
et al. (2020) used reinforcement learning to identify the noisy samples for
the positive relations and then used the identified noisy samples as unlabeled
data in their model. Shang et al. (2020) used a clustering approach to
identify the noisy samples. They assigned the correct relation label to these
noisy samples and used them as additional training data in their model.

####  3.4.3 Zero-Shot or Few-Shot Relation Extraction

Distantly supervised datasets cover a small subset of relations from the KBs.
Existing KBs such as Freebase, Wikidata, and DBpedia contain thousands of
relations. Due to the mismatch of the surface form of entities in KBs and
texts, distant supervision cannot find adequate training samples for most
relations in KBs. It means that distantly supervised models cannot fill the
missing links belonging to these uncovered relations. Zero-shot or few-shot
relation extraction can address this problem. These models can be trained on a
set of relations and can be used for inferring another set of relations.

Levy et al. (2017) and Li et al. (2019) converted the relation extraction task
to a question-answering task and used the reading comprehension approach for
zero-shot relation extraction. In this approach, entity 1 and the relation are
used as questions, and entity 2 is the answer to the question. If entity 2
does not exist, the answer is NIL. Levy et al. (2017) used the BiDAF model
(Seo et al., 2017) with an additional NIL node in the output layer for this
task on the WikiReading (Hewlett et al., 2016) dataset with additional
negative samples. They used a set of relations during training and another set
of relations during testing. Li et al. (2019) used templates to create the
question using entity 1 and the relation. They modified the machine-reading
comprehension models to a sequence tagging model so that they can find
multiple answers to a question. Although they did not experiment with the
zero-shot scenario, this approach can be used for zero-shot relation
extraction too. FewRel 2.0 (Gao et al., 2019) is a dataset for few-shot
relation extraction. In few-shot relation extraction, training and test
relations are different just like zero-shot extraction. But during testing, a
few examples of the test relations are provided to the model for better
prediction.

####  3.4.4 Joint Extraction Approaches

All the previously mentioned works on relation extraction assume that entities
are already identified by a named entity recognition system. They classify the
relation between two given entities at the sentence level or the bag-of-
sentences level. These models depend on an external named entity recognition
system to identify the entities in a text. Recently, some researchers (Katiyar
and Cardie, 2016; Miwa and Bansal, 2016; Bekoulis et al., 2018; Nguyen and
Verspoor, 2019) tried to remove this dependency. They tried to bring the
entity recognition and relation identification tasks closer by sharing their
parameters and optimizing them together. They first identify all the entities
in a sentence and then find the relation among all the pairs of identified
entities. Although they identify the entities and relations in the same
network, they still identify the entities first and then determine the
relation among all possible pairs in the same network. So these models miss
the interaction among the relation tuples present in a sentence. These
approaches resemble the pipeline approach to some extent.

Zheng et al. (2017) first proposed a truly joint extraction model for this
task. They used a sequence tagging scheme to jointly extract the entities and
relations. They created a set of tags derived from the Cartesian product of
entity tags and relation tags. These new tags can encode the entity
information and relation information together. But this strategy does not work
when entities are shared among multiple tuples, as only one tag can be
assigned to a token. Zeng et al. (2018) proposed an encoder-decoder model with
a copy mechanism to extract relation tuples with overlapping entities. Their
model has a copy network to copy the last token of two entities from the
source sentence and a classification network to classify the relation between
copied tokens. Their model cannot extract the full entity names of the tuples.
Their best performing model uses a separate decoder to extract each tuple.
During training, they need to fix the maximum number of decoders and during
inference, their model can only extract up to that fixed number of tuples.
Also, due to the use of separate decoders for each tuple, their model misses
the interaction among the tuples.

Takanobu et al. (2019) proposed a hierarchical reinforcement learning-based
(RL) deep neural model for joint entity and relation extraction. A high-level
RL is used to identify the relation based on the relation-specific tokens in
the sentences. After a relation is identified, a low-level RL is used to
extract the two entities associated with the relation using a sequence
labeling approach. This process is repeated multiple times to extract all the
relation tuples present in the sentences. A special None relation is used to
identify no relation situation in the sentences. Entities extracted associated
with the None relations are ignored. Fu et al. (2019) used a graph
convolutional network (GCN) where they treated each token in a sentence as a
node in a graph and edges were considered as relations. Trisedya et al. (2019)
used an N-gram attention mechanism with an encoder-decoder model for the
completion of knowledge bases using distantly supervised data. Chen et al.
(2019) used the encoder-decoder framework for this task where they used a CNN-
based multi-label classifier to find all the relations first, then used multi-
head attention (Vaswani et al., 2017) to extract the entities corresponding to
each relation.

Zeng et al. (2020) is an improved version of CopyR (Zeng et al., 2018) model
where they used a sequence tagging approach to extract multi-token entities.
Bowen et al. (2020) decomposed the joint extraction task into two sub-tasks:
(i) head entity extraction (ii) tail entity and relation extraction. They used
a sequence tagging approach to solve these two sub-tasks. Similarly, Wei et
al. (2020) proposed a sequence tagging approach for this task. They first
identified the head entities and then for each head entity and each relation,
they identified the tail entities using a sequence tagging approach. They used
pre-trained BERT (Devlin et al., 2019) in their model to improve the
performance.

####  3.4.5 Datasets

Here, we give a brief description of the available datasets in the area of
relation extraction. We describe the datasets that are used in our experiments
in detail in the individual chapters of this thesis. Hendrickx et al. (2010)
proposed a shared task on relation extraction in SemEval 2010 and released a
dataset with 8,000 training sentences and 2,717 test instances across nine
relations including None. The relations in this dataset are not taken from any
knowledge base. They represent the relationship between two nominals in the
sentences. Examples of such relations are Cause-Effect, Component-Whole, etc.
ACE04 (Doddington et al., 2004), CoNLL04 (Roth and Yih, 2004), and GDS (Jat et
al., 2017) are three other datasets with $7$, $5$, and $4$ valid relations
respectively. These datasets contain very few relations and few training
samples which may not be suitable for building large-scale models.

Mintz et al. (2009) first proposed the idea of distant supervision or weak
supervision to create a large text-tuple parallel training dataset for
relation extraction. They mapped Freebase (Bollacker et al., 2008) tuples to
Wikipedia articles to obtain the dataset. Riedel et al. (2010) and Hoffmann et
al. (2011) mapped Freebase tuples to the New York Times (NYT) articles to
obtain another dataset. These two datasets are used extensively by researchers
for their experiments. FewRel 2.0 (Gao et al., 2019) is a few-shot relation
extraction dataset. These datasets are created at the sentence level.

WikiReading (Hewlett et al., 2016) and DocRED (Yao et al., 2019) are two
document-level relation extraction datasets created using Wikipedia articles
and Wikidata items. Quirk and Poon (2017) and Peng et al. (2017) created two
document-level relation extraction datasets for the biomedical domain. In the
document-level datasets, if two entities appear in a document together, then
that document is considered as a source of the tuples involving these two
entities.

###  3.5 Multi-Hop Natural Language Processing

Multi-hop natural language processing (NLP) refers to processing natural
language texts that involve multi-hop reasoning steps, possibly across
multiple sentences within a single document or across multiple documents. Most
NLP tasks such as NER, relation extraction, part-of-speech (POS) tagging, etc.
focus on a single sentence. However, multi-hop NLP tasks have recently
received more attention from the research community. Reading comprehension
(RC) has become very popular with the advances made in deep neural network
research. SQuAD (Rajpurkar et al., 2016) is a popular RC dataset that contains
more than 100,000 questions based on Wikipedia articles. These questions are
created by crowd workers in such a way that models need to focus on multiple
sentences of an article to answer correctly. Multi-RC (Khashabi et al., 2018)
is another multiple-choice reading comprehension dataset, where models need to
focus on multiple sentences within the same paragraph to answer the question.
SquAD and Multi-RC datasets are about multi-hop reasoning across sentences
within a single passage, whereas the WikiHop (Welbl et al., 2018) dataset is
about multi-hop reasoning across multiple documents. WikiHop is created using
Wikipedia articles and Wikidata tuples. The head entity of a tuple and the
relation together form a question. The tail entity of the tuple is the answer
to that question. They map these tuples to Wikipedia articles in such a way
that the head entity and tail entity of a tuple do not appear in a single
document. Thus, models need to consider more that one document to answer the
question. OpenBookQA (Mihaylov et al., 2018) is another RC dataset where
questions come from elementary science facts. To answer these questions,
models need to focus on multiple scientific facts and commonsense knowledge.

Attention-based neural models (Seo et al., 2017; Wang et al., 2017; Kundu and
Ng, 2018; Yu et al., 2018) have proven successful for solving the RC task.
These models use attention mechanisms to focus on those parts of a passage
which have higher similarity to the question. Recently, models based on
contextualized word representations such as BERT (Devlin et al., 2019) also
achieved human-level performance on the SQuAD RC task. However, these
attention-based models do not perform well when multiple documents from
different sources need to be used to find the answer. Dhingra et al. (2017),
Dhingra et al. (2018), Shen et al. (2017), and Hu et al. (2018) proposed
state-based reasoning models to solve the multi-hop tasks across multiple
documents. These state-based models are closer to the attention-based RC
models with an additional ‘state’ representation that is updated iteratively.
The ‘state’ representations of a model allow it to focus on different parts of
multiple documents during each iteration and then combine the information
across multiple documents. Cao et al. (2018), Song et al. (2018a), and Cao et
al. (2019) proposed graph-based models to solve this task. These models create
an entity graph of the entities present in the documents and learn their
representations using a convolutional neural network (CNN) or recurrent neural
network (RNN). They use reasoning over this entity graph to find the answer to
a given question. Fang et al. (2019) proposed a hierarchical graph network for
multi-hop QA. They created three layers of graphs in their model: entity
graph, sentence graph, and passage graph. Finally, a graph reasoning module
was used to find the answer span from the passages. Tu et al. (2019) proposed
a heterogeneous document-entity (HDE) graph model for multi-hop QA. Their
graph contains different types of heterogeneous nodes such as document nodes,
candidate answer nodes, and entity nodes. Edges connecting different types of
nodes are treated differently in the graph. They also used graph-based
reasoning over their HDE graph to find the correct answer. Kundu et al. (2019)
used an explicit path-based reasoning model across multiple documents for the
multi-hop QA task. They constructed the chain of documents using common
entities between documents where each chain led to a possible candidate
answer. Each document chain may contain multiple entity-paths from the start
document to the end document in the chain. They used an attention network to
assign a score to each such entity path and finally assigned a score to each
document chain. These scores were used to rank the candidate answers. This
path-based reasoning can provide interpretable explanations for the multi-hop
QA task. Similar to Kundu et al. (2019), Tang et al. (2020b) proposed a path-
based reasoning approach for this task. They created an entity graph using the
entities present in documents and used graph convolutional network over this
graph and the entity paths to find the answer.

##  Chapter 4 Syntax-Focused Multi-Factor Attention for Relation Extraction

Relation extraction is the task of determining the relation between two
entities in a sentence. Distantly-supervised models are popular for this task.
However, we found that sentences collected using distant supervision can be
very long, and two entities can be located far from each other in a sentence.
The pieces of evidence supporting the presence of a relation between two
entities may not be very direct, since the entities may be connected via some
indirect links such as a third entity or via co-reference. Relation extraction
in such scenarios becomes more challenging as we need to capture the long-
distance interactions among the entities and other words in the sentence.
Also, the words in a sentence do not contribute equally in identifying the
relation between the two entities. To address this issue, we propose a novel
and effective attention model which incorporates syntactic information of the
sentence and a multi-factor attention mechanism. Experiments on the New York
Times corpus show that our proposed model outperforms prior state-of-the-art
models. Material from this chapter has been published in Nayak and Ng (2019).

###  4.1 Motivation

The sentences obtained for relation extraction using distant supervision are
generally long, and two entities are often located far from each other in
these sentences. Zeng et al. (2014, 2015) used convolutional neural networks
(CNN) with max-pooling to find the relation between two given entities in
distantly supervised data. Though these models have performed reasonably well
on distantly supervised data, they sometimes fail to predict the correct
relation when sentences are long, and entities are far from each other. CNN
models with max-pooling have limitations in understanding the semantic
similarity of words with the given entities, and they also fail to capture the
long-distance dependencies among the words and entities such as co-reference.
Besides, all the words in a sentence may not be equally important in finding
the relation, and this issue is more prominent in long sentences. Prior CNN-
based models have limitations in identifying the multiple relevant factors to
focus on in sentence-level relation extraction.

To address this issue, we propose a novel multi-factor attention model111The
code and data of this work can be found at https://github.com/nusnlp/MFA4RE
focusing on the syntactic structure of a sentence for relation extraction. We
use a dependency parser to obtain the syntactic structure of a sentence. We
use a linear form of attention to measure the semantic similarity of words
with the given entities and combine it with the dependency distance of words
from the given entities to measure their influence in identifying the
relation. Also, single attention may not be able to capture all pieces of
evidence for identifying the relation due to normalization of attention
scores. Thus we use multi-factor attention in the proposed model. Experiments
on the New York Times (NYT) corpus show that the proposed model outperforms
prior work in terms of F1 scores on sentence-level relation extraction.

###  4.2 Problem Definition

Sentence-level relation extraction is defined as follows: Given a sentence $S$
and two entities $\\{E_{1},E_{2}\\}$ marked in the sentence, find the relation
$r(E_{1},E_{2})$ between these two entities in $S$ from a pre-defined set of
relations $R\cup\\{\mathit{None}\\}$. None indicates that none of the
relations in $R$ holds between the two marked entities in the sentence. The
relation between the entities is argument order-specific, i.e.,
$r(E_{1},E_{2})$ and $r(E_{2},E_{1})$ are not the same. Input to the system is
a sentence $S$ and two entities $E_{1}$ and $E_{2}$, and output is the
relation $r(E_{1},E_{2})\in R\cup\\{\mathit{None}\\}$.

###  4.3 Model Description

We use four types of embedding vectors in our model: (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 entity
$1$, entity $2$, or does not belong to any entity (3) a positional embedding
vector $\mathbf{u}^{1}\in\mathbb{R}^{d_{u}}$ which represents the linear
distance of a word from the start token of entity $1$ (4) another positional
embedding vector $\mathbf{u}^{2}\in\mathbb{R}^{d_{u}}$ which represents the
linear distance of a word from the start token of entity $2$.

We use a bi-directional long short-term memory (Bi-LSTM) (Hochreiter and
Schmidhuber, 1997) layer to capture the interaction among words in a sentence
$S=\\{w_{1},w_{2},.....,w_{n}\\}$, where $n$ is the sentence length. The input
to this layer is the concatenated vector
$\mathbf{x}\in\mathbb{R}^{d_{w}+d_{z}}$ of word embedding vector $\mathbf{w}$
and entity token indicator embedding vector $\mathbf{z}$.

$\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}}$
(4.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 (Eq. (4.1)) to obtain the $t$th Bi-LSTM output
$\mathbf{h}_{t}\in\mathbb{R}^{2(d_{w}+d_{z})}$.

####  4.3.1 Global Feature Extraction

We use a convolutional neural network (CNN) to extract the sentence-level
global features for relation extraction. We concatenate the positional
embeddings $\mathbf{u}^{1}$ and $\mathbf{u}^{2}$ of words with the hidden
representation of the Bi-LSTM layer. We use the convolution operation with
max-pooling on these concatenated vectors to extract the global feature
vector.

$\displaystyle\mathbf{q}_{t}=\mathbf{h}_{t}\|\mathbf{u}_{t}^{1}\|\mathbf{u}_{t}^{2}$
$\displaystyle
c_{i}=\mathbf{f}^{T}(\mathbf{q}_{i}\|\mathbf{q}_{i+1}\|....\|\mathbf{q}_{i+k-1})$
(4.2) $\displaystyle c_{max}=\mathrm{max}(c_{1},c_{2},....,c_{n})$ (4.3)
$\displaystyle\mathbf{v}_{g}=[c_{max}^{1},c_{max}^{2},....,c_{max}^{f_{g}}]$
(4.4)

$\mathbf{q}_{t}\in\mathbb{R}^{2(d_{w}+d_{z}+d_{u})}$ is the concatenated
vector for the $t$th word. $\mathbf{f}$ is a convolutional filter vector of
dimension $2k(d_{w}+d_{z}+d_{u})$ where $k$ is the filter width. Superscript
$T$ represents the transpose operation. The index $i$ moves from $1$ to $n$
and produces a set of scalar values $\\{c_{1},c_{2},.....,c_{n}\\}$ (Eq.
(4.2)). The max-pooling operation (Eq. (4.3)) chooses the maximum $c_{max}$
from these values as a feature. With $f_{g}$ number of filters, we get a
global feature vector $\mathbf{v}_{g}\in\mathbb{R}^{f_{g}}$ (Eq. (4.4)).

Figure 4.1: Architecture of our attention model with $m=1$, where $m$ is the
multi-factor count. We have not shown the CNN-based global feature extraction
here. FFN = feed-forward network.

####  4.3.2 Attention Modeling

Figure 4.1 shows the architecture of our attention model. We use a linear form
of attention to find the semantically meaningful words in a sentence with
respect to the entities which provide the pieces of evidence for the relation
between them. Our attention mechanism uses the entities as attention queries
and their vector representation is very important for our model. Named
entities mostly consist of multiple tokens and many of them may not be present
in the training data or their frequency may be low. The nearby words of an
entity can give significant information about the entity. Thus we use the
tokens of an entity and its nearby tokens to obtain its vector representation.
We use the convolution operation with max-pooling in the context of an entity
to get its vector representation.

$\displaystyle
c_{i}=\mathbf{f}^{T}(\mathbf{x}_{i}\|\mathbf{x}_{i+1}\|....\|\mathbf{x}_{i+k-1})$
(4.5) $\displaystyle c_{max}=\mathrm{max}(c_{b},c_{b+1},....,c_{e})$ (4.6)
$\displaystyle\mathbf{v}_{e}=[c_{max}^{1},c_{max}^{2},....,c_{max}^{f_{e}}]$
(4.7)

$\mathbf{f}$ is a convolutional filter vector of size $k(d_{w}+d_{z})$ where
$k$ is the filter width. Superscript $T$ represents the transpose operation.
$\mathbf{x}$ is the concatenated vector of word embedding vector
($\mathbf{w}$) and entity token indicator embedding vector ($\mathbf{z}$). $b$
and $e$ are the start and end index of the sequence of words comprising an
entity and its neighboring context in the sentence, where $1\leq b\leq e\leq
n$. The index $i$ moves from $b$ to $e$ and produces a set of scalar values
$\\{c_{b},c_{b+1},.....,c_{e}\\}$ (Eq. (4.5)). The max-pooling operation (Eq.
(4.6)) chooses the maximum $c_{max}$ from these values as a feature. With
$f_{e}$ number of filters, we get the entity vector
$\mathbf{v}_{e}\in\mathbb{R}^{f_{e}}$ (Eq. (4.7)). We do this for both
entities and get $\mathbf{v}_{e}^{1}\in\mathbb{R}^{f_{e}}$ and
$\mathbf{v}_{e}^{2}\in\mathbb{R}^{f_{e}}$ as their vector representation. We
adopt a simple linear function as follows (Eq. (4.8) and Eq. (4.9)) to measure
the semantic similarity of words with the given entities:

$\displaystyle\mathrm{f_{score}^{1}}(\mathbf{h}_{i},\mathbf{v}_{e}^{1})=\mathbf{h}_{i}^{T}\mathbf{W}_{a}^{1}\mathbf{v}_{e}^{1}$
(4.8)
$\displaystyle\mathrm{f_{score}^{2}}(\mathbf{h}_{i},\mathbf{v}_{e}^{2})=\mathbf{h}_{i}^{T}\mathbf{W}_{a}^{2}\mathbf{v}_{e}^{2}$
(4.9)

$\mathbf{h}_{i}$ is the Bi-LSTM hidden representation of the $i$th word.
$\mathbf{W}_{a}^{1}\in\mathbb{R}^{2(d_{w}+d_{z})\times f_{e}}$ and
$\mathbf{W}_{a}^{2}\in\mathbb{R}^{2(d_{w}+d_{z})\times f_{e}}$ are trainable
weight matrices. $\mathrm{f_{score}^{1}}(\mathbf{h}_{i},\mathbf{v}_{e}^{1})$
and $\mathrm{f_{score}^{2}}(\mathbf{h}_{i},\mathbf{v}_{e}^{2})$ represent the
semantic similarity score of the $i$th word and the two given entities.

Not all words in a sentence are equally important in finding the relation
between the two entities. The words which are closer to the entities are
generally more important. To address this issue, we propose to incorporate the
syntactic structure of a sentence in our attention mechanism. The syntactic
structure is obtained from the dependency parse tree of the sentence. Words
which are closer to the entities in the dependency parse tree are more
relevant to finding the relation. In our model, we define the dependency
distance to every word from the head token (last token) of an entity as the
number of edges along the dependency path (See Figure 4.2 for an example). We
use a distance window size $ws$ and words whose dependency distance is within
this window receive attention and the other words are ignored. The details of
our attention mechanism follow.

$\displaystyle
d_{i}^{1}=\begin{cases}\frac{1}{2^{l_{i}^{1}-1}}\mathrm{exp(f_{score}^{1}}(\mathbf{h}_{i},\mathbf{v}_{e}^{1}))&\text{if
}l_{i}^{1}\in[1,ws]\\\
\frac{1}{2^{ws}}\mathrm{exp(f_{score}^{1}}(\mathbf{h}_{i},\mathbf{v}_{e}^{1}))&\text{otherwise}\end{cases}$
(4.10) $\displaystyle
d_{i}^{2}=\begin{cases}\frac{1}{2^{l_{i}^{2}-1}}\mathrm{exp(f_{score}^{2}}(\mathbf{h}_{i},\mathbf{v}_{e}^{2}))&\text{if
}l_{i}^{2}\in[1,ws]\\\
\frac{1}{2^{ws}}\mathrm{exp(f_{score}^{2}}(\mathbf{h}_{i},\mathbf{v}_{e}^{2}))&\text{otherwise}\end{cases}$
(4.11) $\displaystyle p_{i}^{1}=\frac{d_{i}^{1}}{\sum_{j}{d_{j}^{1}}}$ (4.12)
$\displaystyle p_{i}^{2}=\frac{d_{i}^{2}}{\sum_{j}{d_{j}^{2}}}$ (4.13)

$d_{i}^{1}$ (Eq. (4.10)) and $d_{i}^{2}$ (Eq. (4.11)) are un-normalized
attention scores and $p_{i}^{1}$ (Eq. (4.12)) and $p_{i}^{2}$ (Eq. (4.13)) are
the normalized attention scores for the $i$th word with respect to entity 1
and entity 2 respectively. $l_{i}^{1}$ and $l_{i}^{2}$ are the dependency
distances of the $i$th word from the two entities. We mask those words whose
average dependency distance from the two entities is larger than $ws$. We use
the semantic meaning of the words and their dependency distance from the two
entities together in our attention mechanism. The attention feature vectors
$\mathbf{v}_{a}^{1}$ (Eq. (4.14)) and $\mathbf{v}_{a}^{2}$ (Eq. (4.15)) with
respect to the two entities are determined as follows:

$\displaystyle\mathbf{v}_{a}^{1}=\sum_{i=1}^{n}p_{i}^{1}\mathbf{h}_{i}$ (4.14)
$\displaystyle\mathbf{v}_{a}^{2}=\sum_{i=1}^{n}p_{i}^{2}\mathbf{h}_{i}$ (4.15)

Figure 4.2: An example dependency tree. The two numbers indicate the distance
of the word from the head token of the two entities respectively along the
dependency tree path.

####  4.3.3 Multi-Factor Attention

Two entities in a sentence, when located far from each other, can be linked
via more than one co-reference chain or more than one important word. Due to
the normalization of the attention scores as described above, single attention
cannot capture all relevant information needed to find the relation between
two entities. Thus we use a multi-factor attention mechanism, where the number
of factors is a hyper-parameter, to gather all relevant information for
identifying the relation. We replace the attention matrix $\mathbf{W}_{a}$
with an attention tensor $\mathbf{W}_{a}^{1:m}\in\mathbb{R}^{m\times
2(d_{w}+d_{z})\times 2f_{e}}$ where $m$ is the factor count. This gives us $m$
attention vectors with respect to each entity. We concatenate all the feature
vectors obtained using these attention vectors to get the multi-attentive
feature vector $\mathbf{v}_{ma}\in\mathbb{R}^{4m(d_{w}+d_{z})}$ (Eq. (4.16)).

$\displaystyle\mathbf{v}_{ma}=\mathbf{v}_{a}^{11}\|....\|\mathbf{v}_{a}^{1m}\|\mathbf{v}_{a}^{21}\|....\|\mathbf{v}_{a}^{2m}$
(4.16)

####  4.3.4 Relation Extraction

We concatenate $\mathbf{v}_{g}$, $\mathbf{v}_{ma}$, $\mathbf{v}_{e}^{1}$, and
$\mathbf{v}_{e}^{2}$, and this concatenated feature vector is given to a feed-
forward layer with softmax activation to predict the normalized probabilities
for the relation labels (Eq. (4.17)).

$\displaystyle\mathbf{r}=\mathrm{softmax}(\mathbf{W}_{r}(\mathbf{v}_{g}~{}||~{}\mathbf{v}_{ma}~{}||~{}\mathbf{v}_{e}^{1}~{}||~{}\mathbf{v}_{e}^{2})+\mathbf{b}_{r})$
(4.17)

$\mathbf{W}_{r}\in\mathbb{R}^{(f_{g}+2f_{e}+4m(d_{w}+d_{z}))\times(|R|+1)}$ is
the weight matrix, $\mathbf{b}_{r}\in\mathbb{R}^{|R|+1}$ is the bias vector of
the feed-forward layer for relation extraction, and $\mathbf{r}$ is the vector
of normalized probabilities of relation labels.

####  4.3.5 Loss Function

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

$\mathcal{L}=-\frac{1}{B}\sum_{i=1}^{B}\mathrm{log}(p(r_{i}|s_{i},e_{i}^{1},e_{i}^{2},\theta))$
(4.18)

where $p(r_{i}|s_{i},e_{i}^{1},e_{i}^{2},\theta)$ is the conditional
probability of the true relation $r_{i}$ when the sentence $s_{i}$, two
entities $e_{i}^{1}$ and $e_{i}^{2}$, and the model parameters $\theta$ are
given.

###  4.4 Experiments

####  4.4.1 Datasets

We use the New York Times (NYT) corpus (Riedel et al., 2010) in our
experiments. There are two versions of this corpus: (1) The original NYT
corpus created by Riedel et al. (2010) which has $52$ valid relations and a
None relation. We name this dataset NYT10. The training dataset has $455,412$
instances and $330,776$ of the instances belong to the None relation and the
remaining $124,636$ instances have valid relations. The test dataset has
$172,415$ instances and $165,974$ of the instances belong to the None relation
and the remaining $6,441$ instances have valid relations. Both the training
and test datasets have been created by aligning Freebase (Bollacker et al.,
2008) tuples to New York Times articles. (2) Another version created by
Hoffmann et al. (2011) which has $24$ valid relations and a None relation. We
name this dataset NYT11. The corresponding statistics for NYT11 are given in
Table 4.1. The training dataset is created by aligning Freebase tuples to NYT
articles, but the test dataset is manually annotated.

|  | NYT10 | NYT11
---|---|---|---
| #relations | 53 | 25
Train | # instances | 455,412 | 335,843
#valid relation tuples | 124,636 | 100,671
#None relation tuples | 330,776 | 235,172
avg. sentence length | 41.1 | 37.2
avg. distance between entity pairs | 12.8 | 12.2
Test | # instances | 172,415 | 1,450
#valid relation tuples | 6,441 | 520
#None relation tuples | 165,974 | 930
avg. sentence length | 41.7 | 39.7
avg. distance between entity pairs | 13.1 | 11.0
Table 4.1: Statistics of the NYT10 and NYT11 dataset.

####  4.4.2 Evaluation Metrics

We use precision, recall, and F1 scores to evaluate the performance of models
on relation extraction after removing the None labels. We use a confidence
threshold 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
it is considered 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. This confidence threshold is the one
that achieves the highest F1 score on the validation dataset. We also include
the precision-recall curves for all the models.

####  4.4.3 Parameter Settings

We run word2vec (Mikolov et al., 2013) on the NYT corpus to obtain the initial
word embeddings with dimension $d_{w}=50$ and update the embeddings during
training. We set the dimension of entity token indicator embedding vector
$d_{z}=10$ and positional embedding vector $d_{u}=5$. The hidden layer
dimension of the forward and backward LSTM is $60$, which is the same as the
dimension of input word representation vector $\mathbf{x}$. The dimension of
Bi-LSTM output is $120$. We use $f_{g}=f_{e}=230$ filters of width $k=3$ for
feature extraction whenever we apply the convolution operation. The size of
the word embeddings, number of convolution filters, and the filter size are
taken from the literature. We use dropout in our network with a dropout rate
of $0.5$, and in convolutional layers, we use the tanh activation function. We
use the sequence of tokens starting from $5$ words before the entity to $5$
words after the entity as its context. We train our models using mini-batches
of size $50$ and optimize the network parameters using the Adagrad optimizer
(Duchi et al., 2011). We use the dependency parser from
spaCy222https://spacy.io/ to obtain the dependency distance of the words from
the entities and use $ws=5$ as the window size for dependency distance-based
attention.

####  4.4.4 Baselines

We compare our proposed model with the following state-of-the-art models.

(1) CNN (Zeng et al., 2014): Words are represented using word embeddings and
two positional embeddings. A convolutional neural network (CNN) with max-
pooling is applied to extract the sentence-level feature vector. This feature
vector is passed to a feed-forward layer with softmax to classify the
relation.

(2) PCNN (Zeng et al., 2015): Words are represented using word embeddings and
two positional embeddings. A convolutional neural network (CNN) is applied to
the word representations. Rather than applying a global max-pooling operation
on the entire sentence, three max-pooling operations are applied on three
segments of the sentence based on the location of the two entities (hence the
name Piecewise Convolutional Neural Network (PCNN)). The first max-pooling
operation is applied from the beginning of the sentence to the end of the
entity appearing first in the sentence. The second max-pooling operation is
applied from the beginning of the entity appearing first in the sentence to
the end of the entity appearing second in the sentence. The third max-pooling
operation is applied from the beginning of the entity appearing second in the
sentence to the end of the sentence. Max-pooled features are concatenated and
passed to a feed-forward layer with softmax to determine the relation.

(3) Entity Attention (EA) (Shen and Huang, 2016): This is the combination of a
CNN model and an attention model. Words are represented using word embeddings
and two positional embeddings. A CNN with max-pooling is used to extract
global features. Attention is applied with respect to the two entities
separately. The vector representation of every word is concatenated with the
word embedding of the last token of the entity. This concatenated
representation is passed to a feed-forward layer with tanh activation and then
another feed-forward layer to get a scalar attention score for every word. The
original word representations are averaged based on the attention scores to
get the attentive feature vectors. The CNN-extracted global feature vector and
two attentive feature vectors with respect to the two entities are
concatenated and passed to a feed-forward layer with softmax to determine the
relation.

(4) BiGRU Word Attention (BGWA) (Jat et al., 2017): Words are represented
using word embeddings and two positional embeddings. They are passed to a
bidirectional gated recurrent unit (BiGRU) (Cho et al., 2014) layer. Hidden
vectors of the BiGRU layer are passed to a bilinear operator (a combination of
two feed-forward layers) to compute a scalar attention score for each word.
Hidden vectors of the BiGRU layer are multiplied by their corresponding
attention scores. A piece-wise CNN is applied on the weighted hidden vectors
to obtain the feature vector. This feature vector is passed to a feed-forward
layer with softmax to determine the relation.

(5) BiLSTM-CNN: This is our own baseline. Words are represented using word
embeddings and entity indicator embeddings. They are passed to a bidirectional
LSTM. Hidden representations of the LSTMs are concatenated with two positional
embeddings. We use CNN and max-pooling on the concatenated representations to
extract the feature vector. Also, we use CNN and max-pooling on the word
embeddings and entity indicator embeddings of the context words of entities to
obtain entity-specific features. These features are concatenated and passed to
a feed-forward layer to determine the relation. This model does not have the
attention module of our proposed model.

| NYT10 | NYT11
---|---|---
Model | Prec. | Rec. | F1 | Prec. | Rec. | F1
CNN | 0.413 | 0.591 | 0.486 | 0.444 | 0.625 | 0.519
PCNN | 0.380 | 0.642 | 0.477 | 0.446 | 0.679 | 0.538†
EA | 0.443 | 0.638 | 0.523† | 0.419 | 0.677 | 0.517
BGWA | 0.364 | 0.632 | 0.462 | 0.417 | 0.692 | 0.521
BiLSTM-CNN | 0.490 | 0.507 | 0.498 | 0.473 | 0.606 | 0.531
Our model | 0.541 | 0.595 |  0.566* | 0.507 | 0.652 |  0.571*
Table 4.2: Performance comparison of different models on the two datasets. *
denotes a statistically significant improvement over the previous best state-
of-the-art model with $p<0.01$ under the bootstrap paired t-test. † denotes
the previous best state-of-the-art model.

Figure 4.3: Precision-Recall curve for the NYT10 (left) and NYT11 (right)
datasets.

####  4.4.5 Experimental Results

We present the results of our final model on the relation extraction task on
the two datasets in Table 4.2. Our model outperforms the previous state-of-
the-art models on both datasets in terms of F1 score. On the NYT10 dataset, it
achieves $4.3\%$ higher F1 score compared to the previous best state-of-the-
art model EA. Similarly, it achieves $3.3\%$ higher F1 score compared to the
previous best state-of-the-model PCNN on the NYT11 dataset. Our model improves
the precision scores on both datasets with good recall scores. This will help
to build a cleaner knowledge base with fewer false positives. We also show the
precision-recall curves for the NYT10 and NYT11 datasets in Figure 4.3. The
goal of any relation extraction system is to extract as many relations as
possible with minimal false positives. If the recall score becomes very low,
the coverage of the KB will be poor. On the NYT10 dataset (left one in Figure
4.3), we observe that when the recall score is above $0.4$, our model achieves
higher precision than all the competing models. On the NYT11 dataset (right
one in Figure 4.3), when recall score is above $0.6$, our model achieves
higher precision than the competing models. Achieving higher precision with
high recall score helps to build a cleaner KB with good coverage.

###  4.5 Analysis and Discussion

####  4.5.1 Varying the Number of Factors

We investigate the effects of the multi-factor count $(m)$ in our final model
on the test datasets in Table 4.3. We observe that for the NYT10 dataset,
$m=\\{1,2,3\\}$ gives good performance with $m=1$ achieving the highest F1
score. On the NYT11 dataset, $m=4$ gives the best performance. These
experiments show that the number of factors giving the best performance may
vary depending on the underlying data distribution.

| NYT10 | NYT11
---|---|---
$m$ | Prec. | Rec. | F1 | Prec. | Rec. | F1
${1}$ | 0.541 | 0.595 | 0.566 | 0.495 | 0.621 | 0.551
${2}$ | 0.521 | 0.597 | 0.556 | 0.482 | 0.656 | 0.555
${3}$ | 0.490 | 0.617 | 0.547 | 0.509 | 0.633 | 0.564
${4}$ | 0.449 | 0.623 | 0.522 | 0.507 | 0.652 | 0.571
${5}$ | 0.467 | 0.609 | 0.529 | 0.488 | 0.677 | 0.567
Table 4.3: Performance comparison of our model with different values of $m$ on
the two datasets. $m$ refers to the multi-factor count.

####  4.5.2 Effectiveness of Model Components

We include the ablation results on the NYT11 dataset in Table 4.4. When we add
multi-factor attention to the baseline BiLSTM-CNN model without the dependency
distance-based weight factor in the attention mechanism, we get $0.8\%$ F1
score improvement (A2$-$A1). Adding the dependency weight factor with a window
size of $5$ improves the F1 score by $3.2\%$ (A3$-$A2). Increasing the window
size to $10$ reduces the F1 score marginally (A3$-$A4). Replacing the
attention normalizing function of Eq. (4.12) and Eq. (4.13) with softmax
function in the final model also reduces the F1 score marginally (A3$-$A5). In
our final model, we concatenate the features extracted by each attention
layer. Rather than concatenating them, we can apply max-pooling operation
across the multiple attention scores to compute the final attention scores.
These max-pooled attention scores are used to obtain the weighted average
vector of Bi-LSTM hidden vectors. This affects the model performance
negatively and F1 score of the model decreases by $3.0\%$ (A3$-$A6).

| Prec. | Rec. | F1
---|---|---|---
(A1) BiLSTM-CNN | 0.473 | 0.606 | 0.531
(A2) + Standard attention | 0.466 | 0.638 | 0.539
(A3) + Dep. dist. weight factorws=5 | 0.507 | 0.652 | 0.571
(A4) + Dep. dist. weight factorws=10 | 0.510 | 0.640 | 0.568
(A5) Our model with softmax normalization | 0.490 | 0.658 | 0.562
(A6) Our model with max-pool aggregation | 0.492 | 0.600 | 0.541
Table 4.4: Effectiveness of model components ($m=4$) on the NYT11 dataset. $m$
refers to the multi-factor count. $ws$ is the dependency window size used in
Eq. (4.10) and Eq. (4.11).

Figure 4.4: Performance comparison across different sentence lengths on the
NYT10 (left) and NYT11 (right) datasets.

Figure 4.5: Performance comparison across different distances between entities
on the NYT10 (left) and NYT11 (right) datasets.

####  4.5.3 Error Analysis

In relation extraction, finding relations in long sentences where the two
entities are far apart becomes more difficult, and models start to make
mistakes in these scenarios. To understand the behavior of the models in such
scenarios, we analyze their performance with varying sentence lengths and with
varying distances between the two entities in the two datasets in Figure 4.4
and 4.5 respectively. We compare the performance of our proposed model against
the previous state-of-the-art baselines in the corresponding dataset. We also
include our own BiLSTM-CNN model for comparison to show the effectiveness of
our attention module. From Figure 4.4, we see that models start making more
mistakes when the sentence length increases in both datasets. The F1 scores of
the models drop significantly with increasing distance between two entities.
In comparison, our model performs better than the other two models we compare
to across all categories of sentences, based on either length or entity pair
distance on the NYT10 dataset. On the NYT11 dataset, our model either performs
better than or similar to the two other models in similar categories of
sentences.

###  4.6 Summary

In this chapter, we describe a multi-factor attention model utilizing the
syntactic structure of sentences for relation extraction. The syntactic
structure component of our model helps to identify important words in a
sentence and the multi-factor component helps to gather different pieces of
evidence present in a sentence. Together, these two components improve the
performance of our model on this task, and our model outperforms previous
state-of-the-art models when evaluated on the New York Times (NYT) corpus,
achieving significantly higher F1 scores.

##  Chapter 5 Encoder-Decoder Models for Joint Entity and Relation Extraction

The pipeline relation extraction approaches have an external dependency on an
effective named entity recognition system. To remove that dependency, we
explore joint entity and relation extraction in this work. A sentence may have
multiple relation tuples and these tuples may share one or both entities among
them. Extracting such relation tuples is a difficult task and sharing of
entities or overlapping entities among the tuples makes it more challenging.
Most prior work that adopted the pipeline approach cannot capture the
interaction among the relation tuples in a sentence in an effective way. In
this work, we propose two approaches to use encoder-decoder architecture for
jointly extracting entities and relations, where relation tuples are generated
in a sequence. In the first approach, we propose a representation scheme for
relation tuples that 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 length and with overlapping
entities. Next, we propose a pointer network-based decoding approach where an
entire tuple is generated at every time step of the decoding process.
Experiments on the publicly available New York Times corpus show that our
proposed approaches outperform previous work and achieve significantly higher
F1 scores. Material from this chapter has been published in Nayak and Ng
(2020).

###  5.1 Motivation

Distantly-supervised information extraction systems extract relation tuples
with a set of pre-defined relations from text. Traditionally, researchers
(Mintz et al., 2009; Riedel et al., 2010; Hoffmann et al., 2011; Zeng et al.,
2014, 2015; Shen and Huang, 2016; Ren et al., 2017; Jat et al., 2017;
Vashishth et al., 2018) use pipeline approaches where a named entity
recognition (NER) system is used to identify the entities in a sentence and
then a classifier is used to find the relation (or no relation) between them.
However, due to the complete separation of entity detection and relation
classification, these models miss the interaction between multiple relation
tuples present in a sentence. In this approach, models find the relation only
between two given entities in a sentence and do not explicitly consider the
other entities and relations present in the same sentence. Thus these models
miss the interaction among multiple tuples while classifying the relation
between two entities.

Recently, several neural network-based models (Katiyar and Cardie, 2016; Miwa
and Bansal, 2016) were proposed to jointly extract entities and relations from
a sentence. These models used a parameter-sharing mechanism to extract the
entities and relations in the same network. But they still find the relations
after identifying all the entities and do not fully capture the interaction
among multiple tuples. Zheng et al. (2017) proposed a joint extraction model
based on neural sequence tagging scheme. But their model could not extract
tuples with overlapping entities in a sentence as it could not assign more
than one tag to a word. Zeng et al. (2018) proposed a neural encoder-decoder
model for extracting relation tuples with overlapping entities. However, they
used a copy mechanism to copy only the last token of the entities, thus this
model could not extract the full entity names. Also, their best performing
model used a separate decoder to extract each tuple which limited the power of
their model. This model was trained with a fixed number of decoders and could
not extract tuples beyond that number during inference. Encoder-decoder models
are powerful models and they are successful in many NLP tasks such as machine
translation, sentence generation from structured data, and open information
extraction.

Sentence | Berlin is the capital of Germany .
---|---
Tuples |  | <Germany, Berlin, capital>
---
<Germany, Berlin, contains>
<Berlin, Germany, country>
Target: word-based decoding |  | Germany ; Berlin ; capital $|$
---
Germany ; Berlin ; contains $|$
Berlin ; Germany ; country
Target: pointer network-based decoding |  |  $<$5 5 0 0 capital$>$
---
$<$5 5 0 0 contains$>$
$<$0 0 5 5 country$>$

Table 5.1: Relation tuple representation for encoder-decoder models.

In this work, we explore how encoder-decoder models can be used effectively
for extracting relation tuples from sentences. There are three major
challenges in this task: (i) The model should be able to extract entities and
relations together. (ii) It should be able to extract multiple tuples with
overlapping entities. (iii) It should be able to extract exactly two entities
of a tuple with their full names. To address these challenges, we propose two
novel approaches using encoder-decoder architecture111The code and data of
this work can be found at https://github.com/nusnlp/PtrNetDecoding4JERE. We
first propose a new representation scheme for relation tuples (Table 5.1) such
that it can represent multiple tuples with overlapping entities and different
lengths of entities in a simple way. We employ an encoder-decoder model where
the decoder extracts one word at a time like machine translation models. At
the end of sequence generation, due to the unique representation of the
tuples, we can extract the tuples from the sequence of words. Although this
model performs quite well, generating one word at a time is somewhat unnatural
for this task. Each tuple has exactly two entities and one relation, and each
entity appears as a continuous text span in a sentence. The most effective way
to identify them is to find their start and end location in the sentence. Each
relation tuple can then be represented using five items: start and end
location of the two entities and the relation between them (see Table 5.1).
Keeping this in mind, we propose a pointer network-based decoding framework.
This decoder consists of two pointer networks which find the start and end
location of the two entities in a sentence, and a classification network which
identifies the relation between them. At every time step of the decoding, this
decoder extracts an entire relation tuple, not just a word. Experiments on the
New York Times (NYT) datasets show that our approaches work effectively for
this task and achieve state-of-the-art performance. To summarize, the
contributions of this work are as follows:

(1) We propose a new representation scheme for relation tuples such that an
encoder-decoder model, which extracts one word at each time step, can still
find multiple tuples with overlapping entities and tuples with multi-token
entities from sentences. We also propose a masking-based copy mechanism to
extract the entities from the source sentence only.
(2) We propose a modification in the decoding framework with pointer networks
to make the encoder-decoder model more suitable for this task. At every time
step, this decoder extracts an entire relation tuple, not just a word. This
new decoding framework helps in speeding up the training process and uses less
resources (GPU memory). This will be an important factor when we move from
sentence-level tuple extraction to document-level extraction.
(3) Experiments on the NYT datasets show that our approaches outperform all
the previous state-of-the-art models significantly and set a new benchmark on
these datasets.

###  5.2 Problem Definition

A relation tuple consists of two entities and a relation. Such tuples can be
found in sentences where an entity is a text span in a sentence and a relation
comes from a pre-defined set $R$. These tuples may share one or both entities
among them. Based on this, we divide the sentences into three classes: (i) No
Entity Overlap (NEO): A sentence in this class has one or more tuples, but
they do not share any entities. (ii) Entity Pair Overlap (EPO): A sentence in
this class has more than one tuple, and at least two tuples share both the
entities in the same or reverse order. (iii) Single Entity Overlap (SEO): A
sentence in this class has more than one tuple and at least two tuples share
exactly one entity. It should be noted that a sentence can belong to both EPO
and SEO classes. Our task is to extract all relation tuples present in a
sentence.

Class | Sentence | Tuples
---|---|---
NEO |  | The original Joy of
---
Cooking was
published in 1931
by Irma Rombauer,
a St. Louis housewife.
<Irma Rombauer, St. Louis, place_lived>
EPO |  | Berlin is the capital
---
of Germany.
| <Germany, Berlin, capital>
---
<Germany, Berlin, contains>