Information Extraction
Overview
Bonan Min
bonanmin@gmail.com
Some slides are based on class materials from Thien Huu Nguyen, Ralph Grishman, Dan
Jurasky, James Martin
Information Extraction (IE)
Relation Knowledge Base
Giuliani, 58, proposed to Nathan, a former nurse, Name leaderOf ….
during a business trip to Paris _ five months after he
Giuliani New York City
finalized his divorce from Donna Hanover in July after
20 years of marriage. …..
In interviews last year, Giuliani said Nathan gave him
``tremendous emotional support'' through his Event Knowledge Base
treatment for prostate cancer and as he led New York
City during the Sept. 11, 2001, terror attacks.
Trigger Type Person1 Person2 Time
divorce Divorce Giuliani Donna July
Hanover
IE = automatically extracting structured information …..
from unstructured and/or semi-structured machine-
readable documents
Data Mining
Reasoning
Monitoring
...
Information Extraction Pipeline
Giuliani, 58, proposed to Nathan, a former
nurse, during a business trip to Paris _ five
months after he finalized his divorce from
Donna Hanover in July after 20 years of
marriage.
In interviews last year, Giuliani said Nathan
gave him ``tremendous emotional support'' Relation Knowledge Base
through his treatment for prostate cancer
and as he led New York City during the Sept.
11, 2001, terror attacks.
Corpora
Event Knowledge Base
Information Extraction Pipeline
Giuliani, 58, proposed to Nathan, a former
nurse, during a business trip to Paris _ five
Person months after he finalized his divorce from
Donna Hanover in July after 20 years of
marriage.
Location In interviews last year, Giuliani said Nathan Relation Knowledge Base
gave him ``tremendous emotional support''
Time through his treatment for prostate cancer
and as he led New York City during the Sept.
11, 2001, terror attacks. Name ….
Giuliani
…..
Entity Recognition
Corpora
Event Knowledge Base
Information Extraction Pipeline
Giuliani, 58, proposed to Nathan, a former
nurse, during a business trip to Paris _ five
Person months after he finalized his divorce from
Donna Hanover in July after 20 years of
marriage.
Location In interviews last year, Giuliani said Nathan Relation Knowledge Base
gave him ``tremendous emotional support''
Time through his treatment for prostate cancer
and as he led New York City during the Sept.
11, 2001, terror attacks. Name ….
Giuliani
leaderOf …..
Entity Recognition Relation Extraction
Corpora
Event Knowledge Base
Information Extraction Pipeline
Giuliani, 58, proposed to Nathan, a former
nurse, during a business trip to Paris _ five
Person months after he finalized his divorce from
Donna Hanover in July after 20 years of
marriage.
Location In interviews last year, Giuliani said Nathan Relation Knowledge Base
gave him ``tremendous emotional support''
Corefered
Time through his treatment for prostate cancer
and as he led New York City during the Sept.
11, 2001, terror attacks. Name ….
Giuliani
leaderOf …..
Entity Recognition Relation Extraction Coreference Resolution
Corpora
Event Knowledge Base
Information Extraction Pipeline
Giuliani, 58, proposed to Nathan, a former
nurse, during a business trip to Paris _ five
Person months after he finalized his divorce from
Donna Hanover in July after 20 years of
marriage.
Location In interviews last year, Giuliani said Nathan Relation Knowledge Base
gave him ``tremendous emotional support''
Corefered
Time through his treatment for prostate cancer
and as he led New York City during the Sept.
11, 2001, terror attacks. Name ….
Giuliani
leaderOf …..
Entity Recognition Relation Extraction Coreference Resolution Entity Linking
Corpora
Event Knowledge Base
Information Extraction Pipeline
Giuliani, 58, proposed to Nathan, a former
nurse, during a business trip to Paris _ five
Person months after he finalized his divorce from
Donna Hanover in July after 20 years of
marriage.
Location In interviews last year, Giuliani said Nathan Relation Knowledge Base
gave him ``tremendous emotional support''
Time through his treatment for prostate cancer
and as he led New York City during the Sept.
11, 2001, terror attacks. Name leaderOf ….
Giuliani New York City
…..
Entity Recognition Relation Extraction Coreference Resolution Entity Linking
Corpora
Event Knowledge Base
Information Extraction Pipeline
Giuliani, 58, proposed to Nathan, a former
nurse, during a business trip to Paris _ five
Person months after he finalized his divorce from
Donna Hanover in July after 20 years of
marriage.
Location In interviews last year, Giuliani said Nathan Relation Knowledge Base
gave him ``tremendous emotional support''
Time through his treatment for prostate cancer
and as he led New York City during the Sept.
11, 2001, terror attacks. Name leaderOf ….
Giuliani New York City
…..
Entity Recognition Relation Extraction Coreference Resolution Entity Linking
Corpora
Event Knowledge Base
Trigger Prediction Trigger Type Person1 Person2 Time
divorce Divorce
…..
Information Extraction Pipeline
Giuliani, 58, proposed to Nathan, a former
nurse, during a business trip to Paris _ five
Person months after he finalized his divorce from
Donna Hanover in July after 20 years of
marriage.
Location In interviews last year, Giuliani said Nathan Relation Knowledge Base
gave him ``tremendous emotional support''
Time through his treatment for prostate cancer
and as he led New York City during the Sept.
11, 2001, terror attacks. Name leaderOf ….
Giuliani New York City
…..
Entity Recognition Relation Extraction Coreference Resolution Entity Linking
Corpora
Event Knowledge Base
Trigger Prediction Argument Prediction
Trigger Type Person1 Person2 Time
divorce Divorce
…..
Information Extraction Pipeline
Giuliani, 58, proposed to Nathan, a former
nurse, during a business trip to Paris _ five
months after he finalized his divorce from
Donna Hanover in July after 20 years of
marriage.
In interviews last year, Giuliani said Nathan Relation Knowledge Base
gave him ``tremendous emotional support''
through his treatment for prostate cancer
and as he led New York City during the Sept.
11, 2001, terror attacks. Name leaderOf ….
Giuliani New York City
…..
Entity Recognition Relation Extraction Coreference Resolution Entity Linking
Corpora
Event Knowledge Base
Trigger Prediction Argument Prediction
Trigger Type Person1 Person2 Time
divorce Divorce
…..
Information Extraction Pipeline
Giuliani, 58, proposed to Nathan, a former
nurse, during a business trip to Paris _ five
months after he finalized his divorce from
Donna Hanover in July after 20 years of
marriage.
In interviews last year, Giuliani said Nathan Relation Knowledge Base
gave him ``tremendous emotional support''
through his treatment for prostate cancer
and as he led New York City during the Sept.
11, 2001, terror attacks. Name leaderOf ….
Giuliani New York City
…..
Entity Recognition Relation Extraction Coreference Resolution Entity Linking
Corpora
Event Knowledge Base
Trigger Prediction Argument Prediction
Trigger Type Person1 Person2 Time
divorce Divorce Giuliani Donna July
Hanover
…..
Events, Conditions, Trends, and
Causal and Temporal Relations
A: Devaluation of South Sudan Pound essentially leads to increased prices of food, ...
B: ...South Sudan has been experiencing a famine following several years of instability in the country's food supply
caused by war and drought…
C: South Sudan's government is blocking food aid...
D: ...fighting has prevented farmers from planting or harvesting crops, causing food shortages nationwide.
E: Food aid is … the most efficient means of addressing food insecurity.
F: Sky-rocketing food prices in South Sudan are deepening food insecurity
This work was supported by DARPA/I2O and U.S. Army Research Office under the World Modelers program. The views, opinions, and/or findings
contained in this article are those of the author and should not be interpreted as representing the official views or policies, either expressed or implied,
of the DoD or the U.S. Government. This document does not contain technology or technical data controlled under either the U.S. ITAR or the U.S. EAR.
Tasks
Entity Recognition
Relation Extraction
Coreference resolution
Entity Linking
Event extraction (triggers & arguments)
Event-event relation extraction
Entity Recognition
Identifying the entities mentioned in a text (the "entity mentions")
Three types:
◦ Named mentions: Giuliani
◦ Nominal mentions: a former nurse
◦ Pronominal mentions: he, his
The pronominal mentions (and some of the nominal mentions) are references
to previously mentioned entities
◦ Resolving these is the subject of reference resolution
Entity Recognition con’d
For named and nominal mentions, we want to be able to define (semantic)
classes of entities and identify instances of these classes.
◦ We have already defined broad classes of names: Named Entity Recognition (NER)
◦ For nominal mentions the semantic class is generally determined by the head of
the phrase.
Giuliani, 58, proposed to Nathan, a former
nurse, during a business trip to Paris _ five
Person months after he finalized his divorce from
Donna Hanover in July after 20 years of
marriage.
Location In interviews last year, Giuliani said Nathan
gave him ``tremendous emotional support''
Time through his treatment for prostate cancer
and as he led New York City during the Sept.
11, 2001, terror attacks.
Tasks and Evaluations: ACE and
CoNLL 2003 NER
Major tasks and evaluations :
◦ Automatic Content Extraction
(ACE) tasks identified seven
types of entities: Person,
Organization, Location, Facility,
Weapon, Vehicle and Geo-
Political Entity (GPEs)
◦ The CoNLL (Conference on
Natural Language Learning)
2003 NER task consists of
newswire text from the
Reuters RCV1 corpus tagged
with four different entity types
(PER, LOC, ORG, MISC)
Large exhaustively annotated
corpora was provided for
training/development/testing
◦ Laborious to annotate!
Automatic Content Extraction (ACE) entity types
Sekine's Extended Named Entity Hierarchy
(https://nlp.cs.nyu.edu/ene/)
Fine-Grained NER (Ling and Weld, 2012)
Most NER systems are restricted to
produce labels from a small set of classes
◦ E.g., PER, ORG, location (in CoNLL, or ACE)
In order to intelligently understand text, it
is useful to more precisely determine the
semantic classes of entities mentioned in
unstructured text
Three challenges impeding the
development of a fine-grained NER
◦ Selection of the tag set: use 112 frequent
types from Freebase
◦ Creation of training data
◦ Too large to rely on traditional, manual labeling
◦ Exploit the anchor links in Wikipedia text to
automatically label entity segments with appropriate
tags
◦ Development of a fast and accurate multi- Xiao Ling and Daniel S. Weld. Fine-Grained
class labeling algorithm Entity Recognition. AAAI 2012.
◦ MEMM, CRF, BiLSTM-CRF
Relation and Event Extraction
We also would like to extract predications asserted about these entities
◦ The predications range from simple relations to complex events which may
have multiple arguments (agent, patient, time, location, ...)
We will focus on simple binary relationships with two arguments
◦ Mainly because these have been most intensively studied, particularly from
a machine learning point of view
Binary relationships
◦ Relations: Bill Gates, co-founder of Microsoft.
◦ Event-argument relations: I ate a burger this morning
Relation Extraction
A relation is a predication about a pair of entities:
◦ Rodrigo works for UNED.
◦ Alfonso lives in Tarragona.
◦ Otto’s father is Ferdinand.
Typically they represent information which is
permanent or of extended duration.
Rudolph William Louis Giuliani (/ˌdʒuːliˈɑːni/, Italian: [dʒuˈljaːni]; born May 28,
1944) is an American politician, attorney, and public speaker who served as
the 107th Mayor of New York City from 1994 to 2001. He currently acts as an
attorney to President Donald Trump.[1] Politically first a Democrat, then
an Independent in the 1970s, and a Republican since the 1980s, Giuliani
served as United States Associate Attorney General from 1981 to 1983. That
year he became the United States Attorney for the Southern District of New
York, holding the position until 1989.[2]
ACE (2005-2008)
Pre-defined types between ACE
entities
Large exhaustively annotated corpora
(599 files for ACE 2005) was provided
for training/development/testing
◦ Laborious to annotate!
Focus on mention-mention relation
extraction
Influential in relation extraction
research
Relation types in ACE
KBP Slot Filling (2009-2017)
Slot Filling (SF): The slot filling task is to search the document collection
to fill in values for specific attributes ("slots") for specific entities
Question-answering style
evaluation:
◦ What’s the age of Barack
Obama?
◦ Who is the spouse of Barack
Obama?
Focus on getting the answer
◦ System needs to deduplicate
answers
Do not provide annotated
corpus for training
◦ System needs to come up with
clever ways to find heuristically
labeled data to train an
extractor
Train from Wikipedia
with distant supervision!
Slots in KBP Slot Filling
Event Extraction
Event Extraction: An Example
Place
Time
Rainfall in July continued ... in Ethiopia, causing displacement…
E1: Weather E2: Displacement
Timex: 2017-07 Geo-Political Entity
Preprocessing
◦ Tagging named entities, mentions and value mentions (e.g., time)
Event Extraction
◦ Event detection: detect and classify event mentions
◦ Argument Extraction: attach event arguments Who, When (Time), and Where (Place)
Event Extraction con’d
Scenario Template (MUC: Message Understanding Conference)
◦ The scenario template task originally was the IE task for the MUC
evaluations
◦ Identify participants, locations, dates etc. of a class of events -- a naval engagement, a
terrorist incident, a joint venture.
◦ A single template included related information, such as an attack and its effects; this led
to some relatively complex templates
◦ With later MUCs (6 and 7), the task narrowed to single events or closely
related events -- executive succession, rocket launchings
For the ACE evaluations, this became the event extraction task.
An event is
◦ a specific occurrence involving participants.
◦ something that happens.
◦ frequently described as a change of state.
ACE (2005-2008)
Pre-defined types
◦ Event types over trigger words
◦ Event argument roles are
relationships between pairs of
trigger words and ACE entity
mentions or value mentions (e.g.,
time, charge)
Large exhaustively annotated
corpora (599 files for ACE 2005)
was provided for
training/development/testing
◦ Laborious to annotate!
Hugely influential in event
extraction Event types in ACE 2005
Information Extraction vs. Information Retrieval
Information Retrieval returns a set of documents given a query.
Information Extraction returns facts from documents
E.g., What you search for in real estate advertisements:
◦ Town/suburb. You might think easy, but:
◦ Real estate agents: Coldwell Banker, Mosman
◦ Phrases: Only 45 minutes from Parramatta
◦ Multiple property ads have different suburbs in one ad
◦ Money: want a range not a textual match
◦ Multiple amounts: was $155K, now $145K
◦ Bedrooms
◦ Variations: br, bdr, beds, B/R
Information Extraction Evaluations
CoNLL has annual evaluations of IE components for about 15 years
NIST has organized (annual) US government-sponsored evaluations of
information extraction for about 25 years
◦ covering both components and integrated systems
◦ MUC [Message Understanding Conferences] in the 1990’s
◦ ACE [Automatic Content Extraction] 2000-2008
◦ KBP [Knowledge Base Population] since 2009
Named Entity
Recognition
Supervised Learning for NER
Named entities are crucial to different IE and QA tasks
For Named Entity Recognition (NER) (find and classify names in text) ,
we can use the sequence labeling methods discussed previously (i.e.,
MEMM, CRF, RNN).
Person Organization
Fred Smith works for Time inc.
B_PER I_PER O O B_ORG I_ORG
Sequence Tagging Models for NER
From Lafferty et al. 2001
Huang et al. 2015, “Bidirectional LSTM-CRF Models for Sequence Tagging
Features for NER
Feature-based models: the key is to design good feature sets to Mr. Gates said…
feed into the sequence labeling models (i.e., feature
engineering with MEMM or CRF) B-PER I-PER
Features for each token:
◦ previous, current, and next tokens
◦ POS and phase chunk tags: NPs are more likely to be names
◦ The tag assigned to the previous token (generated on the fly)
◦ Combinations of the above
◦ Word clusters, e.g., Brown word clusters
◦ Word embeddings
Good indicators of person, organization, and location names
◦ A name that is followed by a comma and a state or country name is
probably the name of a city
◦ Lists of common first/last person names (from census), or location
names from WikiData.
Brown word clusters
Features for NER
Features for NER
Word shape features: Map words to simplified representation that encodes
attributes such as length, capitalization, numerals, Greek letters, internal
punctuation, etc.
Shorter word shape features: consecutive character types are removed (i.e.,
DC10-30 -> Xd-d, I.M.F -> X.X.X)
Gazetteers: Lists of common names for different types
◦ Millions of entries for locations with detailed geographical and political information
(www.geonames.org)
◦ Lists of first names and surnames derived from its decadal census in the U.S
(www.census.gov)
◦ Typically implemented as a binary feature for each name list
◦ Unfortunately, such lists can be difficult to create and maintain, and their usefulness varies
considerably.
Homework Assignment #3
Design and extract features for CoNLL-style NER
Target classes: PER, ORG, LOC, and MISC
◦ We’ll simply the task to only use IO schema (I=Inside; O=Outside)
Data: We’ll provide training/development/test data
◦ Training & development data comes with NER labels
◦ We also provide POS & chunk tags
◦ Format is similar to homework #2 (one word per line)
We recommend using opennlp MaxEnt package (Java) and will provide code for
◦ Training a MaxEnt model from a feature file
◦ Decode a MaxEnt model over the testing data
◦ A sample program (GenerateFeaturesForNER.java) on how to extract features from the training data
You task is not to implement the Machine Learning model, but to implement code that
extracts features from the training, development, and testing data
◦ In other words, implement a fancier version of GenerateFeaturesForNER.java
◦ Note: you don’t have to write this in Java, as long as you extract the features and write them into the
file following the format that MaxEnt package requires.
What make good features for a NER model?
Deep learning for NER
Evaluation for NER systems
Other Types Of Learning
(Not limited to NER)
We have discussed hand-coded rules and supervised models (HMM,
MEMM, CRF, RNN) for NER [named entity recognition]
◦ A large labeled training dataset is required
◦ Annotating a large corpus to train a high-performance NER is fairly expensive
Semi-supervised learning
◦ Part of training data is labeled (‘the seed’) (the rest is unlabeled)
◦ Make use of redundancies to learn labels of additional data, then train
model
◦ Co-training
◦ Reduces amount of data which must be hand-labeled to achieve a given level
of performance
Active learning
◦ Start with partially labeled data
◦ System selects additional ‘informative’ examples for user to label
Semi-supervised Learning
𝐿 = labeled data
𝑈 = unlabeled data
1. 𝐿 = seed
repeat 2-4 until stopping condition is reached
2. 𝐶 = classifier trained on 𝐿
3. Apply 𝐶 to 𝑈.
𝑁 = most confidently labeled items
4. 𝐿 += 𝑁; 𝑈 -= 𝑁
Confidence
How to estimate confidence?
Binary probabilistic classifier
◦ Confidence = | 𝑃 – 0.5 | * 2
N-ary probabilistic classifier
◦ Confidence = 𝑃1 – 𝑃2
where
𝑃1 = probability of most probable label
𝑃2 = probability of second most probable label
SVM
◦ Distance from the separating hyperplane
Co-Training (Multi-View Learning)
Two ‘views’ of data (subsets of features)
◦ Producing two classifiers 𝐶1(𝑥) and 𝐶2(𝑥)
Ideally
◦ Independent
◦ Each sufficient to classify data
Apply classifiers in alternation (or in parallel)
1. 𝐿 = seed
-- repeat 2-7 until stopping condition is reached
2. 𝐶1= classifier trained on 𝐿
3. Apply 𝐶1 to 𝑈. When to stop?
𝑁 = most confidently labeled items ◦ 𝑈 is exhausted
◦ Reach performance goal using held-out labeled
4. 𝐿 += 𝑁; 𝑈 -= 𝑁 sample
◦ After fixed number of iterations based on similar
5. 𝐶2 = classifier trained on 𝐿 tasks
6. Apply 𝐶2 to 𝑈.
𝑁 = most confidently labeled items Poor confidence estimates
◦ Errors from poorly-chosen data rapidly magnified
7. 𝐿 += 𝑁; 𝑈 -= 𝑁
Co-Training for NER
We can split the features for NER into two sets:
◦ Spelling features
(the entire name + tokens in the name)
◦ Context features
(left and right contexts + syntactic context)
Start with a seed
◦ E.g., some common unambiguous full names
Iteratively grow seed, alternatively applying spelling and context models
and adding most -confidently-labeled instances to seed
Co-Training for NER
seed Add most confident
Apply spelling model
exs to labeled set
Build context model Build spelling model
Add most confident
Apply context model
exs to labeled set
Name Co-training: Results from Collins and Singer (1999)
◦ 3 classes: person, organization, location (and ‘other’)
◦ Data: 1M sentences of news
◦ Seed:
New York, California, U.S. location Microsoft, IBM organization
contains(Mr.) person contains(Incorporated) organization
◦ Apply constraints, e.g., took names appearing with appositive modifier
◦ Accuracy: 83% or 91% (Clean accuracy: ignoring names not in one of the 3 categories)
Semi-supervised NER: When To Stop
Semi-supervised NER labels a few more examples at every iteration
◦ It stops when it runs out of examples to label
This is fine if
◦ Names are easily identified (e.g., by capitalization in English)
◦ Most names fall into one of the categories being trained (e.g., people,
organizations, and locations for news stories)
Semi-supervised NER: Semantic Drift
Semi-supervised NER doesn’t work so well if
◦ The set of names is hard to identify
◦ Monocase languages
◦ Extended name sets including lower-case terms
◦ The categories being trained cover only a small portion of the set of names
The result is semantic drift and semantic spread
◦ The name categories gradually grow to include related terms
Fighting Semantic Drift
We can fight drift by training a larger, more inclusive set of categories
◦ Including ‘negative’ categories
◦ Categories we don’t really care about but include to compete with the original categories
◦ These negative categories can be built
◦ By hand (Yangarber et al. 2003)
◦ Or automatically (McIntosh 2010)
Active Learning
For supervised learning, we typically annotate text data sequentially
Not necessarily the most efficient approach
◦ Most natural language phenomena have a Zipfian distribution … a few very common
constructs and lots of infrequent constructs
◦ After you have annotated “Spain” 50 times as a location, the NER model is little
improved by annotating it one more time
We want to select the most informative examples and present them to
the annotator
◦ The data which, if labeled, is most likely to reduce NER error
How To Select Informative Examples?
Uncertainty-based sampling
◦ For binary classifier
◦ For MaxEnt, probability near 50%
◦ For SVM, data near separating hyperplane
◦ For n-ary classifier, data with small margin
Committee-based sampling
◦ Data on which committee members disagree
◦ (co-testing … use two classifiers based on independent views)
Representativeness
Selecting examples that are representative (centroid of clusters)
Or it’s more helpful to annotate examples involving less common features
◦ Weighting these features correctly will have a larger impact on error rate
◦ So we rank examples by frequency of features in the entire corpus
Batching and Diversity
Each iteration of active learning involves running classifier on (a large)
unlabeled corpus
◦ This can be quite slow
◦ Meanwhile annotator is waiting for something to annotate
So we run active learning in batches
◦ Select best 𝑛 examples to annotate each time
◦ But all items in a batch are selected using the same criteria and same system
state, and so are likely to be similar
To avoid example overlap, we impose a diversity requirement with a
batch: limit maximum similarity of examples within a batch
◦ Compute similarity based on example feature vectors
Simulated Active Learning
True active learning experiments are
◦ Hard to reproduce
◦ Very time consuming
So most experiments involve simulated active learning:
◦ “unlabeled” data has really been labeled, but the labels have been hidden
◦ When data is selected, labels are revealed
◦ Disadvantage: “unlabeled” data can’t be so bit
This leads us to ignore lots of issues of true active learning:
◦ An annotation unit of one sentence or even one token may not be efficient for
manual annotation
◦ So reported speed-ups may be optimistic
(typical reports reduce by half the amount of data to achieve a given NER
accuracy)
Limitations
Cited performance is for well matched training and test
◦ Same domain
◦ Same source
◦ Same epoch
◦ Performance deteriorates rapidly if less matched
◦ NER trained on Reuters (F=91),
tested on Wall Street Journal (F=64) [Ciaramita and Altun 2003]
◦ Work on NER adaptation is vital
Adding rarer classes to NER is difficult
◦ Supervised learning inefficient
◦ Semi-supervised learning is subject to semantic drift
