Information Extraction and Named Entity Recognition

Introducing the tasks:

Getting simple structured information out of text

Christopher Manning

Information Extraction

• Information extraction (IE) systems
• Find and understand limited relevant parts of texts
• Gather information from many pieces of text
• Produce a structured representation of relevant information:
• relations (in the database sense), a.k.a.,
• a knowledge base
• Goals:
1. Organize information so that it is useful to people
2. Put information in a semantically precise form that allows further inferences to be made by computer algorithms

Christopher Manning

Information Extraction (IE)

• IE systems extract clear, factual information
• Roughly: Who did what to whom when?
• E.g.,
• Gathering earnings, profits, board members, headquarters, etc. from company reports
• The headquarters of BHP Billiton Limited, and the global headquarters of the combined BHP Billiton Group, are located in Melbourne, Australia.
• headquarters(“BHP Biliton Limited”, “Melbourne, Australia”)
• Learn drug-gene product interactions from medical research literature

Christopher Manning

Low-level information extraction

• Is now available – and I think popular – in applications like Apple or Google mail, and web indexing

​

​

​

​

• Often seems to be based on regular expressions and name lists

Christopher Manning

Low-level information extraction

Christopher Manning

Named Entity Recognition (NER)

• A very important sub-task: find and classify names in text, for example:

​

• The decision by the independent MP Andrew Wilkie to withdraw his support for the minority Labor government sounded dramatic but it should not further threaten its stability. When, after the 2010 election, Wilkie, Rob Oakeshott, Tony Windsor and the Greens agreed to support Labor, they gave just two guarantees: confidence and supply.

Christopher Manning

Named Entity Recognition (NER)

• A very important sub-task: find and classify names in text, for example:

​

• The decision by the independent MP Andrew Wilkie to withdraw his support for the minority Labor government sounded dramatic but it should not further threaten its stability. When, after the 2010 election, Wilkie, Rob Oakeshott, Tony Windsor and the Greens agreed to support Labor, they gave just two guarantees: confidence and supply.

Christopher Manning

Named Entity Recognition (NER)

• A very important sub-task: find and classify names in text, for example:

​

• The decision by the independent MP Andrew Wilkie to withdraw his support for the minority Labor government sounded dramatic but it should not further threaten its stability. When, after the 2010 election, Wilkie, Rob Oakeshott, Tony Windsor and the Greens agreed to support Labor, they gave just two guarantees: confidence and supply.

Person

Date

Location

Organi-

zation

​

​

Christopher Manning

Named Entity Recognition (NER)

• The uses:
• Named entities can be indexed, linked off, etc.
• Sentiment can be attributed to companies or products
• A lot of IE relations are associations between named entities
• For question answering, answers are often named entities.

​

• Concretely:
• Many web pages tag various entities, with links to bio or topic pages, etc.
• Reuters’ OpenCalais, Evri, AlchemyAPI, Yahoo’s Term Extraction, …
• Apple/Google/Microsoft/… smart recognizers for document content

Christopher Manning

Information Extraction and Named Entity Recognition

Introducing the tasks:

Getting simple structured information out of text

Christopher Manning

Evaluation of Named Entity Recognition

The extension of Precision, Recall, and the F measure to sequences

Christopher Manning

The Named Entity Recognition Task

Task: Predict entities in a text

​

Foreign ORG

Ministry ORG

spokesman O

Shen PER

Guofang PER

told O

Reuters ORG

: :

}

Standard evaluation

is per entity, not per token

Christopher Manning

Precision/Recall/F1 for IE/NER

• Recall and precision are straightforward for tasks like IR and text categorization, where there is only one grain size (documents)
• The measure behaves a bit funnily for IE/NER when there are boundary errors (which are common):
• First Bank of Chicago announced earnings …
• This counts as both a fp and a fn
• Selecting nothing would have been better
• Some other metrics (e.g., MUC scorer) give partial credit (according to complex rules)

Christopher Manning

Evaluation of Named Entity Recognition

The extension of Precision, Recall, and the F measure to sequences

Christopher Manning

Sequence Models for Named Entity Recognition

Christopher Manning

The ML sequence model approach to NER

Training

1. Collect a set of representative training documents
2. Label each token for its entity class or other (O)
3. Design feature extractors appropriate to the text and classes
4. Train a sequence classifier to predict the labels from the data

​

Testing

1. Receive a set of testing documents
2. Run sequence model inference to label each token
3. Appropriately output the recognized entities

​

​

Christopher Manning

Encoding classes for sequence labeling

IO encoding IOB encoding

​

Fred PER B-PER

showed O O

Sue PER B-PER

Mengqiu PER B-PER

Huang PER I-PER

‘s O O

new O O

painting O O

Christopher Manning

Features for sequence labeling

• Words
• Current word (essentially like a learned dictionary)
• Previous/next word (context)
• Other kinds of inferred linguistic classification
• Part-of-speech tags
• Label context
• Previous (and perhaps next) label

18

Christopher Manning

Features: Word substrings

Cotrimoxazole

Wethersfield

Alien Fury: Countdown to Invasion

oxa

:

field

Christopher Manning

Features: Word shapes

• Word Shapes
• Map words to simplified representation that encodes attributes such as length, capitalization, numerals, Greek letters, internal punctuation, etc.

​

​

​

​

​

​

Christopher Manning

Sequence Models for Named Entity Recognition

Christopher Manning

Maximum entropy sequence models

Maximum entropy Markov models (MEMMs) or Conditional Markov models

Christopher Manning

Sequence problems

• Many problems in NLP have data which is a sequence of characters, words, phrases, lines, or sentences …
• We can think of our task as one of labeling each item

POS tagging

Word segmentation

Named entity recognition

Text segmen-tation

Q

A

Q

A

A

A

Q

A

Christopher Manning

MEMM inference in systems

• For a Conditional Markov Model (CMM) a.k.a. a Maximum Entropy Markov Model (MEMM), the classifier makes a single decision at a time, conditioned on evidence from observations and previous decisions
• A larger space of sequences is usually explored via search

Local Context

Features

(Ratnaparkhi 1996; Toutanova et al. 2003, etc.)

Christopher Manning

Example: POS Tagging

• Scoring individual labeling decisions is no more complex than standard classification decisions
• We have some assumed labels to use for prior positions
• We use features of those and the observed data (which can include current, previous, and next words) to predict the current label

Local Context

Features

(Ratnaparkhi 1996; Toutanova et al. 2003, etc.)

Christopher Manning

Example: POS Tagging

• POS tagging Features can include:
• Current, previous, next words in isolation or together.
• Previous one, two, three tags.
• Word-internal features: word types, suffixes, dashes, etc.

Local Context

Features

(Ratnaparkhi 1996; Toutanova et al. 2003, etc.)

Christopher Manning

Inference in Systems

Sequence Level

Local Level

Local

Data

Feature

Extraction

Features

Label

Optimization

Smoothing

Classifier Type

Sequence

Data

Maximum Entropy Models

Quadratic

Penalties

Conjugate

Gradient

Sequence Model

Inference

Local

Data

Local

Data

Christopher Manning

Greedy Inference

• Greedy inference:
• We just start at the left, and use our classifier at each position to assign a label
• The classifier can depend on previous labeling decisions as well as observed data
• Advantages:
• Fast, no extra memory requirements
• Very easy to implement
• With rich features including observations to the right, it may perform quite well
• Disadvantage:
• Greedy. We make commit errors we cannot recover from

Sequence Model

Inference

Best Sequence

Christopher Manning

Beam Inference

• Beam inference:
• At each position keep the top k complete sequences.
• Extend each sequence in each local way.
• The extensions compete for the k slots at the next position.
• Advantages:
• Fast; beam sizes of 3–5 are almost as good as exact inference in many cases.
• Easy to implement (no dynamic programming required).
• Disadvantage:
• Inexact: the globally best sequence can fall off the beam.

Sequence Model

Inference

Best Sequence

Christopher Manning

Viterbi Inference

• Viterbi inference:
• Dynamic programming or memoization.
• Requires small window of state influence (e.g., past two states are relevant).
• Advantage:
• Exact: the global best sequence is returned.
• Disadvantage:
• Harder to implement long-distance state-state interactions (but beam inference tends not to allow long-distance resurrection of sequences anyway).

Sequence Model

Inference

Best Sequence

Christopher Manning

CRFs [Lafferty, Pereira, and McCallum 2001]

• Another sequence model: Conditional Random Fields (CRFs)
• A whole-sequence conditional model rather than a chaining of local models.

​

​

​

• The space of c’s is now the space of sequences
• But if the features f_i remain local, the conditional sequence likelihood can be calculated exactly using dynamic programming
• Training is slower, but CRFs avoid causal-competition biases
• These (or a variant using a max margin criterion) are seen as the state-of-the-art these days … but in practice usually work much the same as MEMMs.

Christopher Manning

Maximum entropy sequence models

Maximum entropy Markov models (MEMMs) or Conditional Markov models

Christopher Manning

Relation Extraction

What is relation extraction?

Dan Jurafsky

Extracting relations from text

• Company report: “International Business Machines Corporation (IBM or the company) was incorporated in the State of New York on June 16, 1911, as the Computing-Tabulating-Recording Co. (C-T-R)…”
• Extracted Complex Relation:

Company-Founding

Company IBM

Location New York

Date June 16, 1911

Original-Name Computing-Tabulating-Recording Co.

• But we will focus on the simpler task of extracting relation triples

Founding-year(IBM,1911)

Founding-location(IBM,New York)

Dan Jurafsky

Extracting Relation Triples from Text

The Leland Stanford Junior University, commonly referred to as Stanford University or Stanford, is an American private research university located in Stanford, California … near Palo Alto, California… Leland Stanford…founded the university in 1891

Stanford EQ Leland Stanford Junior University

Stanford LOC-IN California

Stanford IS-A research university

Stanford LOC-NEAR Palo Alto

Stanford FOUNDED-IN 1891

Stanford FOUNDER Leland Stanford

Dan Jurafsky

Why Relation Extraction?

• Create new structured knowledge bases, useful for any app
• Augment current knowledge bases
• Adding words to WordNet thesaurus, facts to FreeBase or DBPedia
• Support question answering
• The granddaughter of which actor starred in the movie “E.T.”?

(acted-in ?x “E.T.”)(is-a ?y actor)(granddaughter-of ?x ?y)

• But which relations should we extract?

​

​

36

Dan Jurafsky

Automated Content Extraction (ACE)

​

​

​

​

​

​

17 relations from 2008 “Relation Extraction Task”

Dan Jurafsky

Automated Content Extraction (ACE)

• Physical-Located PER-GPE

He was in Tennessee

• Part-Whole-Subsidiary ORG-ORG

XYZ, the parent company of ABC

• Person-Social-Family PER-PER

John’s wife Yoko

• Org-AFF-Founder PER-ORG

Steve Jobs, co-founder of Apple…

38

Dan Jurafsky

UMLS: Unified Medical Language System

• 134 entity types, 54 relations

Injury disrupts Physiological Function

Bodily Location location-of Biologic Function

Anatomical Structure part-of Organism

Pharmacologic Substance causes Pathological Function

Pharmacologic Substance treats Pathologic Function

Dan Jurafsky

Extracting UMLS relations from a sentence

Doppler echocardiography can be used to diagnose left anterior descending artery stenosis in patients with type 2 diabetes

🡻

Echocardiography, Doppler DIAGNOSES Acquired stenosis

40

Dan Jurafsky

Databases of Wikipedia Relations

41

Relations extracted from Infobox

Stanford state California

Stanford motto “Die Luft der Freiheit weht”

…

Wikipedia Infobox

Dan Jurafsky

Relation databases �that draw from Wikipedia

• Resource Description Framework (RDF) triples

subject predicate object

Golden Gate Park location San Francisco

dbpedia:Golden_Gate_Park dbpedia-owl:location dbpedia:San_Francisco

• DBPedia: 1 billion RDF triples, 385 from English Wikipedia
• Frequent Freebase relations:

people/person/nationality, location/location/contains

people/person/profession, people/person/place-of-birth

biology/organism_higher_classification film/film/genre

42

Dan Jurafsky

Ontological relations

• IS-A (hypernym): subsumption between classes
• Giraffe IS-A ruminant IS-A ungulate IS-A mammal IS-A vertebrate IS-A animal…

​

• Instance-of: relation between individual and class
• San Francisco instance-of city

​

Examples from the WordNet Thesaurus

Dan Jurafsky

How to build relation extractors

1. Hand-written patterns
2. Supervised machine learning
3. Semi-supervised and unsupervised
• Bootstrapping (using seeds)
• Distant supervision
• Unsupervised learning from the web

​

Dan Jurafsky

Relation Extraction

What is relation extraction?

Dan Jurafsky

Relation Extraction

Using patterns to extract relations

Dan Jurafsky

Rules for extracting IS-A relation

​

Early intuition from Hearst (1992)

• “Agar is a substance prepared from a mixture of red algae, such as Gelidium, for laboratory or industrial use”
• What does Gelidium mean?
• How do you know?`

Dan Jurafsky

Rules for extracting IS-A relation

​

Early intuition from Hearst (1992)

• “Agar is a substance prepared from a mixture of red algae, such as Gelidium, for laboratory or industrial use”
• What does Gelidium mean?
• How do you know?`

Dan Jurafsky

Hearst’s Patterns for extracting IS-A relations

(Hearst, 1992): Automatic Acquisition of Hyponyms

“Y such as X ((, X)* (, and|or) X)”

“such Y as X”

“X or other Y”

“X and other Y”

“Y including X”

“Y, especially X”

Dan Jurafsky

Hearst’s Patterns for extracting IS-A relations

Dan Jurafsky

Extracting Richer Relations Using Rules

• Intuition: relations often hold between specific entities
• located-in (ORGANIZATION, LOCATION)
• founded (PERSON, ORGANIZATION)
• cures (DRUG, DISEASE)
• Start with Named Entity tags to help extract relation!

Dan Jurafsky

Named Entities aren’t quite enough.�Which relations hold between 2 entities?

Drug

Disease

Cure?

Prevent?

Cause?

Dan Jurafsky

What relations hold between 2 entities?

PERSON

ORGANIZATION

Founder?

Investor?

Member?

Employee?

President?

Dan Jurafsky

Extracting Richer Relations Using Rules and�Named Entities

Who holds what office in what organization?

PERSON, POSITION of ORG

• George Marshall, Secretary of State of the United States

PERSON(named|appointed|chose|etc.) PERSON Prep? POSITION

• Truman appointed Marshall Secretary of State

PERSON [be]? (named|appointed|etc.) Prep? ORG POSITION

• George Marshall was named US Secretary of State

​

Dan Jurafsky

Hand-built patterns for relations

• Plus:
• Human patterns tend to be high-precision
• Can be tailored to specific domains
• Minus
• Human patterns are often low-recall
• A lot of work to think of all possible patterns!
• Don’t want to have to do this for every relation!
• We’d like better accuracy

Dan Jurafsky

Relation Extraction

Using patterns to extract relations

Dan Jurafsky

Relation Extraction

Supervised relation extraction

Dan Jurafsky

Supervised machine learning for relations

• Choose a set of relations we’d like to extract
• Choose a set of relevant named entities
• Find and label data
• Choose a representative corpus
• Label the named entities in the corpus
• Hand-label the relations between these entities
• Break into training, development, and test
• Train a classifier on the training set

58

Dan Jurafsky

How to do classification in supervised relation extraction

1. Find all pairs of named entities (usually in same sentence)
2. Decide if 2 entities are related
3. If yes, classify the relation
1. Why the extra step?
• Faster classification training by eliminating most pairs
• Can use distinct feature-sets appropriate for each task.

59

Dan Jurafsky

Automated Content Extraction (ACE)

​

​

​

​

​

​

17 sub-relations of 6 relations from 2008 “Relation Extraction Task”

Dan Jurafsky

Relation Extraction

Classify the relation between two entities in a sentence

American Airlines, a unit of AMR, immediately matched the move, spokesman Tim Wagner said.

SUBSIDIARY

FAMILY

EMPLOYMENT

NIL

FOUNDER

CITIZEN

INVENTOR

…

Dan Jurafsky

Word Features for Relation Extraction

• Headwords of M1 and M2, and combination

Airlines Wagner Airlines-Wagner

• Bag of words and bigrams in M1 and M2

{American, Airlines, Tim, Wagner, American Airlines, Tim Wagner}

• Words or bigrams in particular positions left and right of M1/M2

M2: -1 spokesman

M2: +1 said

• Bag of words or bigrams between the two entities

{a, AMR, of, immediately, matched, move, spokesman, the, unit}

American Airlines, a unit of AMR, immediately matched the move, spokesman Tim Wagner said

Mention 1

Mention 2

Dan Jurafsky

Named Entity Type and Mention Level�Features for Relation Extraction

• Named-entity types
• M1: ORG
• M2: PERSON
• Concatenation of the two named-entity types
• ORG-PERSON
• Entity Level of M1 and M2 (NAME, NOMINAL, PRONOUN)
• M1: NAME [it or he would be PRONOUN]
• M2: NAME [the company would be NOMINAL]

American Airlines, a unit of AMR, immediately matched the move, spokesman Tim Wagner said

Mention 1

Mention 2

Dan Jurafsky

Parse Features for Relation Extraction

• Base syntactic chunk sequence from one to the other

NP NP PP VP NP NP

• Constituent path through the tree from one to the other

NP 🡹 NP 🡹 S 🡹 S 🡻 NP

• Dependency path

Airlines matched Wagner said

American Airlines, a unit of AMR, immediately matched the move, spokesman Tim Wagner said

Mention 1

Mention 2

Dan Jurafsky

Gazeteer and trigger word features for relation extraction

• Trigger list for family: kinship terms
• parent, wife, husband, grandparent, etc. [from WordNet]
• Gazeteer:
• Lists of useful geo or geopolitical words
• Country name list
• Other sub-entities

Dan Jurafsky

American Airlines, a unit of AMR, immediately matched the move, spokesman Tim Wagner said.

Dan Jurafsky

Classifiers for supervised methods

• Now you can use any classifier you like
• MaxEnt
• Naïve Bayes
• SVM
• ...
• Train it on the training set, tune on the dev set, test on the test set

Dan Jurafsky

Evaluation of Supervised Relation Extraction

• Compute P/R/F₁ for each relation

​

​

68

Dan Jurafsky

Summary: Supervised Relation Extraction

+ Can get high accuracies with enough hand-labeled training data, if test similar enough to training

- Labeling a large training set is expensive

- Supervised models are brittle, don’t generalize well to different genres

​

Dan Jurafsky

Relation Extraction

Supervised relation extraction

Dan Jurafsky

Relation Extraction

Semi-supervised and unsupervised relation extraction

Dan Jurafsky

Seed-based or bootstrapping approaches to relation extraction

• No training set? Maybe you have:
• A few seed tuples or
• A few high-precision patterns
• Can you use those seeds to do something useful?
• Bootstrapping: use the seeds to directly learn to populate a relation

Dan Jurafsky

Relation Bootstrapping (Hearst 1992)

• Gather a set of seed pairs that have relation R
• Iterate:
1. Find sentences with these pairs
2. Look at the context between or around the pair and generalize the context to create patterns
3. Use the patterns for grep for more pairs

​

Dan Jurafsky

Bootstrapping

• <Mark Twain, Elmira> Seed tuple
• Grep (google) for the environments of the seed tuple

“Mark Twain is buried in Elmira, NY.”

X is buried in Y

“The grave of Mark Twain is in Elmira”

The grave of X is in Y

“Elmira is Mark Twain’s final resting place”

Y is X’s final resting place.

• Use those patterns to grep for new tuples
• Iterate

Dan Jurafsky

Dipre: Extract <author,book> pairs

• Start with 5 seeds:

​

​

• Find Instances:

The Comedy of Errors, by William Shakespeare, was

The Comedy of Errors, by William Shakespeare, is

The Comedy of Errors, one of William Shakespeare's earliest attempts

The Comedy of Errors, one of William Shakespeare's most

• Extract patterns (group by middle, take longest common prefix/suffix)

?x , by ?y , ?x , one of ?y ‘s

• Now iterate, finding new seeds that match the pattern

​

Brin, Sergei. 1998. Extracting Patterns and Relations from the World Wide Web.

Dan Jurafsky

�Snowball

• Similar iterative algorithm

​

​

• Group instances w/similar prefix, middle, suffix, extract patterns
• But require that X and Y be named entities
• And compute a confidence for each pattern

{’s, in, headquarters}

{in, based}

ORGANIZATION

LOCATION

E. Agichtein and L. Gravano 2000. Snowball: Extracting Relations

from Large Plain-Text Collections. ICDL

ORGANIZATION

LOCATION

.69

.75

Dan Jurafsky

Distant Supervision

• Combine bootstrapping with supervised learning
• Instead of 5 seeds,
• Use a large database to get huge # of seed examples
• Create lots of features from all these examples
• Combine in a supervised classifier

Snow, Jurafsky, Ng. 2005. Learning syntactic patterns for automatic hypernym discovery. NIPS 17

Fei Wu and Daniel S. Weld. 2007. Autonomously Semantifying Wikipeida. CIKM 2007

Mintz, Bills, Snow, Jurafsky. 2009. Distant supervision for relation extraction without labeled data. ACL09

Dan Jurafsky

Distant supervision paradigm

• Like supervised classification:
• Uses a classifier with lots of features
• Supervised by detailed hand-created knowledge
• Doesn’t require iteratively expanding patterns
• Like unsupervised classification:
• Uses very large amounts of unlabeled data
• Not sensitive to genre issues in training corpus

​

Dan Jurafsky

Distantly supervised learning �of relation extraction patterns

​

For each relation

​

For each tuple in big database

​

Find sentences in large corpus with both entities

​

Extract frequent features (parse, words, etc)

​

Train supervised classifier using thousands of patterns

​

4

1

2

3

5

PER was born in LOC

PER, born (XXXX), LOC

PER’s birthplace in LOC

​

​

​

​

​

<Edwin Hubble, Marshfield>

<Albert Einstein, Ulm>

Born-In

Hubble was born in Marshfield

Einstein, born (1879), Ulm

Hubble’s birthplace in Marshfield

P(born-in | f₁,f₂,f₃,…,f₇₀₀₀₀)

Dan Jurafsky

Unsupervised relation extraction

• Open Information Extraction:
• extract relations from the web with no training data, no list of relations

​

1. Use parsed data to train a “trustworthy tuple” classifier
2. Single-pass extract all relations between NPs, keep if trustworthy
3. Assessor ranks relations based on text redundancy

(FCI, specializes in, software development)

(Tesla, invented, coil transformer)

​

​

80

M. Banko, M. Cararella, S. Soderland, M. Broadhead, and O. Etzioni. 2007. Open information extraction from the web. IJCAI

Dan Jurafsky

Evaluation of Semi-supervised and�Unsupervised Relation Extraction

• Since it extracts totally new relations from the web
• There is no gold set of correct instances of relations!
• Can’t compute precision (don’t know which ones are correct)
• Can’t compute recall (don’t know which ones were missed)
• Instead, we can approximate precision (only)
• Draw a random sample of relations from output, check precision manually

​

• Can also compute precision at different levels of recall.
• Precision for top 1000 new relations, top 10,000 new relations, top 100,000
• In each case taking a random sample of that set
• But no way to evaluate recall

81

Dan Jurafsky

Relation Extraction

Semi-supervised and unsupervised relation extraction

Dan Jurafsky