---
title: Information Extraction
module: Linguistic Structure
moduleNumber: 6
lessonNumber: 15
order: 615
summary: >
  Information extraction turns free text into a database, and the first step is
  relation extraction: pulling entity-relation-entity triples out of sentences.
  We cover all five families — hand-built patterns, supervised classifiers,
  semi-supervised bootstrapping, distant supervision, and unsupervised Open IE —
  with worked bootstrapping and distant-supervision traces, then the neural and
  LLM systems that extended them. Times, events, and templates follow in the
  companion lesson.
topics: [Structure]
sources:
  - book: Jurafsky
    ref: "Ch. 17 — Information Extraction; §17.1 Relation Extraction; §17.2 Relation Extraction Algorithms"
---

A [sequence labeler](/natural-language-processing/sequences/sequence-labeling)
reads the sentence _Citing high fuel prices, United Airlines said Friday it has
increased fares by $6 per round trip_ and hands back a scatter of tagged spans:
`United Airlines` is an organization, `Friday` is a time, `$6` is money. That is
where named-entity recognition stops. It never says that United _raised_ the
fare, that the raise took effect Friday, or that the amount was six dollars. The
facts are in the sentence; they are just not in a form a database can store or a
query can reach.

**Information extraction** (IE) closes that gap. It reads unstructured text and
emits structured records — relations, events, times — that a downstream system
can put in a table and look up. Those records already have the shape a knowledge base
stores, which is why IE is the standard way to _populate_ one: running it over a
corpus yields rows to insert.[^jm-ie]

$$
% caption: The information-extraction pipeline. Raw text is tagged for entities,
% then relations, events, and times are extracted and normalized into structured
% database records.
\begin{tikzpicture}[>=stealth, font=\footnotesize,
  box/.style={draw, minimum width=22mm, minimum height=11mm, align=center, font=\scriptsize}]
  \definecolor{acc}{HTML}{2348F2}
  \node[box] (txt) at (0,0) {raw text\\(documents)};
  \node[box] (ner) at (3.0,0) {entities\\(NER)};
  \node[box] (rel) at (6.0,0) {relations,\\events, times};
  \node[box, draw=acc, text=acc, thick] (db) at (9.2,0) {database\\(records)};
  \draw[->, acc, thick] (txt) -- (ner);
  \draw[->, acc, thick] (ner) -- (rel);
  \draw[->, acc, thick] (rel) -- (db);
  \node[font=\scriptsize, anchor=north] at (3.0,-0.85) {tag spans};
  \node[font=\scriptsize, anchor=north] at (6.0,-0.85) {classify pairs};
  \node[font=\scriptsize, anchor=north] at (9.2,-0.85) {insert rows};
\end{tikzpicture}
$$

The full pipeline runs end to end: extracting **relations** among entities,
extracting and normalizing **times**, detecting **events** and ordering them, and
filling **templates** for recurring situations. This lesson takes the first and
largest stage — relation extraction — and its five algorithmic families; the
temporal and template stages continue in the companion lesson,
[extracting times, events, and templates](/natural-language-processing/linguistic-structure/times-events-and-templates).
Throughout, the goal is the same: free text in, a queryable database out.

## Relation extraction

Assume the named entities are already tagged. Relation extraction discerns the
_relationships_ that hold among them. In the airline text above, the tagged
sentence continues: _American Airlines, a unit of AMR Corp., immediately matched
the move, spokesman Tim Wagner said. United, a unit of UAL Corp., said the
increase took effect Thursday_. From this a relation extractor should learn that
Tim Wagner is a spokesman for American Airlines, that United is a unit of UAL
Corp., and that American is a unit of AMR — binary relations that are instances of
generic relations like **part-of** or **employs**.[^jm-relext]

$$
% caption: A sentence maps to a set of relation triples, each a subject, a
% relation, and an object over the tagged entities.
\begin{tikzpicture}[>=stealth, font=\footnotesize,
  ent/.style={draw, minimum height=7mm, inner sep=3pt, font=\scriptsize},
  trip/.style={draw, minimum height=7mm, inner sep=3pt, align=center, font=\scriptsize}]
  \definecolor{acc}{HTML}{2348F2}
  \node[font=\scriptsize, anchor=west] at (-0.3,2.0)
    {United, a unit of UAL Corp., ... spokesman Tim Wagner said};
  \node[ent, draw=acc, text=acc] (u)  at (0.6,1.0) {United};
  \node[ent] (ual) at (3.2,1.0) {UAL Corp.};
  \node[ent] (tw)  at (6.2,1.0) {Tim Wagner};
  \node[ent] (aa)  at (9.2,1.0) {American Airlines};
  \node[trip, draw=acc] (t1) at (1.9,-0.5) {PartOf(United, UAL Corp.)};
  \node[trip] (t2) at (6.6,-0.5) {OrgAff(Tim Wagner, American Airlines)};
  \draw[->, acc] (u)  -- (t1);
  \draw[->, acc] (ual) -- (t1);
  \draw[->, black] (tw) -- (t2);
  \draw[->, black] (aa) -- (t2);
\end{tikzpicture}
$$

These triples correspond exactly to the model-theoretic notion of a relation: a
set of ordered tuples over a domain. The domain elements are the tagged entities
(after coreference resolution links _it_, _United_, and _the airline_ to one
underlying entity). A relation like $\textit{PartOf} = \{\langle a, b\rangle,
\langle c, d\rangle\}$ is just the set of pairs for which it holds. This view even
subsumes NER: recognizing a class of entities is identifying a _unary_ relation.

> **Definition (Relation extraction).** Given a text with tagged entities,
> produce the set of triples $\langle e_1, r, e_2\rangle$ where relation $r$
> holds between entities $e_1$ and $e_2$. The set of all triples for $r$ is the
> relation, in the model-theoretic sense, that populates one column of the
> knowledge base.

### Relation types and ontologies

Which relations? The choice is a design decision, standardized by the datasets
that annotate them. The **ACE** (Automatic Content Extraction) evaluations define
17 relations grouped into a handful of families — Person-Social, Physical,
General-Affiliation, Org-Affiliation, Part-Whole, and Artifact — each typed by the
entities it connects.

$$
% caption: A sampler of ACE-style relations, each with the entity types it links
% and an example. PER, ORG, GPE, LOC are named-entity types.
\begin{tikzpicture}[>=stealth, font=\footnotesize]
  \definecolor{acc}{HTML}{2348F2}
  \node[anchor=west, font=\scriptsize] at (0,3.0) {\textbf{Relation}};
  \node[anchor=west, font=\scriptsize] at (4.3,3.0) {\textbf{Types}};
  \node[anchor=west, font=\scriptsize] at (7.0,3.0) {\textbf{Example}};
  \draw[black] (-0.1,2.7) -- (11.6,2.7);
  \node[anchor=west, font=\scriptsize] at (0,2.2) {Physical-Located};
  \node[anchor=west, font=\scriptsize] at (4.3,2.2) {PER-GPE};
  \node[anchor=west, font=\scriptsize, text=acc] at (7.0,2.2) {He was in Tennessee};
  \node[anchor=west, font=\scriptsize] at (0,1.5) {Part-Whole-Subsidiary};
  \node[anchor=west, font=\scriptsize] at (4.3,1.5) {ORG-ORG};
  \node[anchor=west, font=\scriptsize, text=acc] at (7.0,1.5) {XYZ, parent of ABC};
  \node[anchor=west, font=\scriptsize] at (0,0.8) {Person-Social-Family};
  \node[anchor=west, font=\scriptsize] at (4.3,0.8) {PER-PER};
  \node[anchor=west, font=\scriptsize, text=acc] at (7.0,0.8) {Yoko's husband John};
  \node[anchor=west, font=\scriptsize] at (0,0.1) {Org-AFF-Founder};
  \node[anchor=west, font=\scriptsize] at (4.3,0.1) {PER-ORG};
  \node[anchor=west, font=\scriptsize, text=acc] at (7.0,0.1) {Steve Jobs, co-founder of Apple};
  \draw[black] (-0.1,-0.25) -- (11.6,-0.25);
\end{tikzpicture}
$$

Other domains define their own inventories. **UMLS**, the Unified Medical
Language System, has 54 relations over 134 entity types, so that a sentence like
_Doppler echocardiography can be used to diagnose left anterior descending artery
stenosis_ yields $\textit{diagnoses}(\textit{Echocardiography},
\textit{Acquired stenosis})$. Wikipedia **infoboxes** supply another huge store,
readily turned into relations or into a metalanguage called **RDF** (Resource
Description Framework). An **RDF triple** is a subject-predicate-object
expression, exactly the shape of a relation triple:

$$
\underbrace{\textit{Golden Gate Park}}_{\text{subject}}\;
\underbrace{\textit{location}}_{\text{predicate}}\;
\underbrace{\textit{San Francisco}}_{\text{object}}.
$$

Crowdsourced **DBpedia** holds over 2 billion such triples; **Freebase** (now part
of Wikidata) holds relations between people, nationalities, and locations. A
distinct and important family is **ontological relations** — the hierarchical
`is-a` (**hypernym**) and `part-of` relations that organize concepts rather than
facts about individuals. WordNet encodes chains like _Giraffe is-a ruminant is-a
ungulate is-a mammal is-a vertebrate_, plus an `Instance-of` relation tying an
individual (_San Francisco_) to its class (_city_). Extracting these relations is
how ontologies get built and extended.

Finally, hand-labeled datasets exist for training and testing. **TACRED**
contains 106,264 examples over 41 relation types (like `per:city_of_birth`,
`org:subsidiaries`, `org:member_of`), drawn from news and web text.

$$
% caption: TACRED example sentences, each with a subject and object span, their
% entity types, and the gold relation label. About 80 percent of examples carry
% the no-relation label.
\begin{tikzpicture}[>=stealth, font=\footnotesize]
  \definecolor{acc}{HTML}{2348F2}
  \definecolor{red}{HTML}{C0392B}
  \node[anchor=west, font=\scriptsize] at (0,2.6)
    {Carey will succeed \textcolor{acc}{Cathleen P. Black}, ... take a new role as \textcolor{red}{chairwoman}};
  \node[anchor=west, font=\scriptsize] at (0.4,2.15) {types PER / TITLE, relation: per:title};
  \node[anchor=west, font=\scriptsize] at (0,1.4)
    {\textcolor{acc}{Irene Morgan Kirkaldy}, born and reared in \textcolor{red}{Baltimore}, ...};
  \node[anchor=west, font=\scriptsize] at (0.4,0.95) {types PER / CITY, relation: per:city\/\_of\/\_birth};
  \node[anchor=west, font=\scriptsize] at (0,0.2)
    {\textcolor{acc}{Baldwin} declined comment, said JetBlue chief \textcolor{red}{executive} Dave Barger};
  \node[anchor=west, font=\scriptsize] at (0.4,-0.25) {types PER / TITLE, relation: no-relation};
\end{tikzpicture}
$$

The heavy no-relation share matters: sufficient negative data is what lets a
supervised classifier learn when _not_ to fire.

## Relation extraction algorithms

There are five main families: **handwritten patterns**, **supervised** machine
learning, **semi-supervised** (via bootstrapping or distant supervision), and
**unsupervised** (Open IE). Each trades recall against the cost of annotation.

### Hand-built patterns

The earliest and still common approach is lexico-syntactic patterns, first
developed by Hearst and therefore called **Hearst patterns**. Consider the
sentence _Agar is a substance prepared from a mixture of red algae, such as
Gelidium_. A reader who has never heard of _Gelidium_ still infers that it is a
kind of red algae — a **hyponym** of _red algae_. Hearst captures the inference
with a pattern over noun phrases:[^jm-hearst]

$$
NP_0 \text{ such as } NP_1 \{,\, NP_2 \ldots (\text{and} | \text{or}) NP_i\},\; i \ge 1
\;\;\Rightarrow\;\; \forall NP_i,\; \text{hyponym}(NP_i, NP_0).
$$

Matching it against the sentence yields $\text{hyponym}(\textit{Gelidium},
\textit{red algae})$. Hearst suggested five such patterns for the hypernym
relation; modern versions add named-entity constraints so they can target
specific relations.

$$
% caption: Hand-built lexico-syntactic patterns for hypernyms, where NP-H is the
% parent (hypernym); braces mark optional material. NER-constrained patterns
% target specific relations like PER holding a POSITION at an ORG.
\begin{tikzpicture}[>=stealth, font=\footnotesize]
  \definecolor{acc}{HTML}{2348F2}
  \node[anchor=west, font=\footnotesize\ttfamily] at (0,3.3) {NP-H such as \{NP,\}* (and$\mid$or) NP};
  \node[anchor=west, font=\scriptsize] at (6.6,3.3) {such authors as Herrick, ...};
  \node[anchor=west, font=\footnotesize\ttfamily] at (0,2.7) {NP \{, NP\}* \{,\} or other NP-H};
  \node[anchor=west, font=\scriptsize] at (6.6,2.7) {temples, ... and other civic buildings};
  \node[anchor=west, font=\footnotesize\ttfamily] at (0,2.1) {NP-H \{,\} including \{NP,\}* NP};
  \node[anchor=west, font=\scriptsize] at (6.6,2.1) {countries, including Canada};
  \draw[black] (-0.15,1.7) -- (12.4,1.7);
  \node[anchor=west, font=\scriptsize] at (0,1.2) {\textbf{NER-constrained (relation-specific):}};
  \node[anchor=west, font=\footnotesize\ttfamily] at (0,0.6) {PER, POSITION of ORG};
  \node[anchor=west, font=\scriptsize, text=acc] at (7.0,0.6) {G. Marshall, Secretary of State of the US};
  \node[anchor=west, font=\footnotesize\ttfamily] at (0,0.0) {PER (named$\mid$appointed) PER Prep? POSITION};
  \node[anchor=west, font=\scriptsize, text=acc] at (7.0,0.0) {Truman appointed Marshall Secretary};
\end{tikzpicture}
$$

Hand-built patterns are **high-precision** and can be tailored to a domain. Their
weakness is **low recall** — an enormous set would be needed to catch every phrasing
— and the labor of writing them all.

### Supervised relation extraction

If a fixed set of relations and entities is chosen and a corpus is hand-annotated,
the task becomes ordinary supervised classification. The scheme is:
find pairs of named entities (usually in the same sentence) and apply a
relation classifier to each pair. An optional intermediate _filter_ first makes a
binary decision — are these two entities related _at all_? — to skip the expensive
full classification on the many unrelated pairs.

```algorithm
caption: $\textsc{Find-Relations}(words)$ — classify relations among tagged entities
$relations \gets$ nil
$entities \gets \textsc{Find-Entities}(words)$
for each entity pair $\langle e_1, e_2 \rangle$ in $entities$ do
  if $\textsc{Related?}(e_1, e_2)$ then
    $relations \gets relations \cup \textsc{Classify-Relation}(e_1, e_2)$
return $relations$
```

A **feature-based** classifier (logistic regression, random forest) describes each
pair with hand-designed features. For _American Airlines_ (mention M1) and _Tim
Wagner_ (mention M2) in _American Airlines, a unit of AMR, immediately matched the
move, spokesman Tim Wagner said_, useful features include:

- **Word features**: the headwords of M1 and M2 and their concatenation
  (`Airlines`, `Wagner`, `Airlines-Wagner`); bag-of-words in each mention;
  words in particular positions (M2$-1$ = `spokesman`, M2$+1$ = `said`); the bag
  of words _between_ the mentions (`a, AMR, of, immediately, matched, ...`).
- **Named-entity features**: the entity types and their concatenation (M1: `ORG`,
  M2: `PER`, M1M2: `ORG-PER`); the entity level (NAME, NOMINAL, PRONOUN); the
  number of entities between the arguments.
- **Syntactic structure**: the constituency or dependency **syntactic path**
  between M1 and M2, e.g. the dependency path `Airlines <-subj matched <-comp said
  ->subj Wagner`.

A **neural** classifier treats the task the same way but learns the
representation. A typical Transformer system feeds the sentence to a pretrained
encoder (BERT, RoBERTa, SpanBERT), takes the sentence representation (the `[CLS]`
token), and adds a linear layer that assigns one of the relation labels. A key
detail is that the input is **partially de-lexified**: the subject and object spans
are replaced by their NER tags, which keeps the model from overfitting to the
individual lexical items.

$$
% caption: Neural relation extraction. A pretrained encoder reads the sentence
% with the subject and object entities replaced by their NER tags; a linear
% classifier on the CLS representation predicts the relation.
\begin{tikzpicture}[>=stealth, font=\footnotesize,
  tok/.style={font=\footnotesize\ttfamily, anchor=north}]
  \definecolor{acc}{HTML}{2348F2}
  \node[draw, fill=acc!8, minimum width=90mm, minimum height=8mm, font=\small] (enc) at (0,0) {ENCODER};
  \foreach \x/\t in {-4.0/[CLS], -2.4/SUBJ-PER, -1.0/was, 0/born, 1.0/in, 2.2/OBJ-LOC, 3.7/Michigan}
    \node[tok] at (\x,-0.6) {\t};
  \foreach \x in {-4.0,-2.4,-1.0,0,1.0,2.2,3.7}
    \draw[->, black] (\x,-1.2) -- (\x,-0.5);
  \node[draw, fill=acc!8, minimum width=20mm, minimum height=7mm, font=\scriptsize] (lin) at (-4.0,1.4) {Linear};
  \draw[->, acc, thick] (enc.north -| lin) -- (lin);
  \node[font=\scriptsize] (out) at (-4.0,2.7) {predicted relation};
  \draw[->, acc, thick] (lin) -- (out);
\end{tikzpicture}
$$

When the test set resembles the training set and enough labeled data exists,
supervised systems reach high accuracy. What they cost is that labeled data:
annotation is expensive, and the models are **brittle** — they do not transfer to a
new text genre. That fragility motivates the semi-supervised and unsupervised
methods.

### Semi-supervised bootstrapping

Suppose there is no labeled corpus, only a few high-precision **seed tuples** or
**seed patterns**. **Bootstrapping** grows a classifier from them: take the
entities in a seed pair, find sentences that contain both, generalize the context
between and around them into new patterns, use those patterns to find new tuples,
and repeat.

```algorithm
caption: $\textsc{Bootstrap}(R)$ — grow relation tuples from seed pairs
$tuples \gets$ a set of seed tuples having relation $R$
repeat
  $sentences \gets$ sentences containing both entities of some tuple in $tuples$
  $patterns \gets$ generalize the context around the entities in $sentences$
  $newpairs \gets$ tuples matched by $patterns$
  $newpairs \gets$ pairs in $newpairs$ with high confidence
  $tuples \gets tuples \cup newpairs$
until enough tuples
return $tuples$
```

Say we want airline-hub pairs and know only that Ryanair has a hub at Charleroi.
Searching for _Ryanair_, _Charleroi_, and _hub_ in proximity turns up _Budget
airline Ryanair, which uses Charleroi as a hub_, _Ryanair's hub at Charleroi_,
_Charleroi, a main hub for Ryanair_. Generalizing the context between the mentions
yields patterns that find _more_ hub pairs:

```
/ [ORG], which uses [LOC] as a hub /
/ [ORG]'s hub at [LOC] /
/ [LOC], a main hub for [ORG] /
```

$$
% caption: The bootstrapping loop. Seed tuples find sentences; sentences generalize
% to patterns; patterns extract new tuples, which feed back as seeds. Confidence
% filtering guards against semantic drift.
\begin{tikzpicture}[>=stealth, font=\footnotesize,
  b/.style={draw, minimum width=24mm, minimum height=11mm, align=center, font=\scriptsize}]
  \definecolor{acc}{HTML}{2348F2}
  \definecolor{red}{HTML}{C0392B}
  \node[b, draw=acc, text=acc] (tup) at (0,1.6) {seed tuples};
  \node[b] (sent) at (4.6,1.6) {sentences};
  \node[b] (pat)  at (4.6,-1.0) {patterns};
  \node[b] (new)  at (0,-1.0) {new tuples};
  \draw[->, acc, thick] (tup) -- (sent) node[midway, above, font=\scriptsize] {find};
  \draw[->, acc, thick] (sent) -- (pat) node[midway, right, font=\scriptsize] {generalize};
  \draw[->, acc, thick] (pat) -- (new) node[midway, below, font=\scriptsize] {extract};
  \draw[->, acc, thick] (new) -- (tup) node[midway, left, font=\scriptsize] {add (high conf.)};
  \node[b, draw=red, text=red] (drift) at (9.0,-1.0) {semantic drift};
  \draw[->, red, dashed] (new) to[bend right=15] (drift);
  \node[font=\scriptsize, text=red, anchor=west, align=left] at (7.5,0.6) {bad pattern\\$\to$ bad tuple\\$\to$ worse patterns};
\end{tikzpicture}
$$

The danger is **semantic drift**: one erroneous pattern introduces a wrong tuple,
which spawns bad patterns, and the meaning of the extracted relation _drifts_.
Given the seed hub relation, a sentence like _Sydney has a ferry hub at Circular
Quay_ might inject $\langle \textit{Sydney}, \textit{Circular Quay}\rangle$,
propagating error. Bootstrapping systems therefore attach **confidence values** to
new tuples and accept only high-confidence ones. Confidence for a pattern $p$
balances two factors — how well $p$ matches the current tuple set, and how
productive it is — through the Riloff-Jones metric over a document collection
$\mathcal{D}$:

$$
\text{Conf}_{\text{RlogF}}(p) \;=\; \frac{|\text{hits}(p)|}{|\text{finds}(p)|}\,\log\big(|\text{finds}(p)|\big),
$$

where $\text{hits}(p)$ is the set of current tuples $p$ matches and
$\text{finds}(p)$ is everything $p$ finds in $\mathcal{D}$. To score a new tuple
$t$ supported by a set of patterns $P'$, the **noisy-or** combination treats each
$\text{Conf}(p)$ as a probability and gives the chance that not _all_ supporting
patterns are wrong:

$$
\text{Conf}(t) \;=\; 1 - \prod_{p \in P'} \big(1 - \text{Conf}(p)\big).
$$

Conservative acceptance thresholds keep the process from drifting away from the
target relation.

#### A worked bootstrapping trace

Run one round with numbers. Seed the hub relation with the single tuple $\langle
\textit{Ryanair}, \textit{Charleroi}\rangle$ and search a collection $\mathcal{D}$.
Three patterns emerge from the sentences found:

- $p_1 =$ `[ORG], which uses [LOC] as a hub`
- $p_2 =$ `[ORG]'s hub at [LOC]`
- $p_3 =$ `[LOC], a main hub for [ORG]`

Suppose the current tuple set has grown to $|T| = 5$ accepted hub pairs, and across
$\mathcal{D}$ the patterns behave as follows. Pattern $p_1$ matches $4$ tuples of
which $4$ are in $T$ — it is precise but also finds $6$ tuples total, so
$\text{hits}(p_1) = 4$, $\text{finds}(p_1) = 6$. Pattern $p_2$ has $\text{hits} =
3$, $\text{finds} = 4$. Pattern $p_3$ is looser: $\text{hits} = 2$, $\text{finds} =
20$. The Riloff-Jones confidence $\frac{|\text{hits}|}{|\text{finds}|}\log|\text{finds}|$
scores each:

$$
\text{Conf}(p_1) = \tfrac{4}{6}\log 6 = 0.67 \cdot 1.79 = 1.19, \quad
\text{Conf}(p_2) = \tfrac{3}{4}\log 4 = 0.75 \cdot 1.39 = 1.04, \quad
\text{Conf}(p_3) = \tfrac{2}{20}\log 20 = 0.10 \cdot 3.00 = 0.30.
$$

Normalizing to probabilities (divide by the max, $1.19$) gives $\text{Conf}(p_1) =
1.00$, $\text{Conf}(p_2) = 0.87$, $\text{Conf}(p_3) = 0.25$. Now a candidate tuple
$t = \langle \textit{easyJet}, \textit{Luton}\rangle$ turns up, matched by $p_1$ and
$p_2$ but not $p_3$. The noisy-or combination gives the probability that _not both_
supporting patterns erred:

$$
\text{Conf}(t) = 1 - (1 - 1.00)(1 - 0.87) = 1 - (0.00)(0.13) = 1.00.
$$

That clears any reasonable threshold, so $t$ joins $T$. Contrast a shaky tuple
$t' = \langle \textit{Sydney}, \textit{Circular Quay}\rangle$ matched only by the
loose $p_3$: its confidence is just $\text{Conf}(t') = 1 - (1 - 0.25) = 0.25$, below
a threshold of, say, $0.5$, so it is rejected, avoiding the semantic drift
illustrated above. The two guards work together: the
Riloff-Jones metric distrusts unproductive-yet-imprecise patterns like $p_3$, and
noisy-or rewards a tuple only when a _high-confidence_ pattern backs it.

### Distant supervision

**Distant supervision** keeps the classifier of the supervised method but replaces
hand annotation with a large database. Instead of a handful of seeds, it aligns a
knowledge base to text to manufacture a huge, noisy training set.[^jm-distant] To
learn `place-of-birth`, note that Freebase already lists over 100,000 examples,
including `<Edwin Hubble, Marshfield>` and `<Albert Einstein, Ulm>`. Run an NER
tagger over 800,000 Wikipedia articles and extract every sentence containing both
entities of some known tuple:

- _...Hubble was born in Marshfield..._
- _...Einstein, born (1879), Ulm..._
- _...Hubble's birthplace in Marshfield..._

Each known tuple `<relation, e1, e2>` becomes one training instance whose features
are pooled from _all_ the sentences mentioning that pair.

$$
% caption: Distant supervision. For every tuple of a relation in the database,
% gather all sentences mentioning both entities, pool their features, and emit one
% labeled training instance; then train a supervised classifier.
\begin{tikzpicture}[>=stealth, font=\footnotesize,
  b/.style={draw, minimum width=26mm, minimum height=11mm, align=center, font=\scriptsize}]
  \definecolor{acc}{HTML}{2348F2}
  \node[b, draw=acc, text=acc] (db) at (0,1.4) {KB tuple\\born-in(Einstein, Ulm)};
  \node[b] (sent) at (4.8,1.4) {sentences with\\both entities};
  \node[b] (feat) at (4.8,-1.2) {pooled features\\(words, dep paths)};
  \node[b] (inst) at (0,-1.2) {training instance\\(e1, e2, f, R)};
  \node[b, thick] (clf) at (-4.6,-1.2) {supervised\\classifier};
  \draw[->, acc, thick] (db) -- (sent) node[midway, above, font=\scriptsize] {align to text};
  \draw[->, acc, thick] (sent) -- (feat) node[midway, right, font=\scriptsize] {extract};
  \draw[->, acc, thick] (feat) -- (inst);
  \draw[->, acc, thick] (inst) -- (clf) node[midway, above, font=\scriptsize] {train};
\end{tikzpicture}
$$

```algorithm
caption: $\textsc{Distant-Supervision}(D, T)$ — train a relation classifier from a KB and text
for each relation $R$ do
  for each tuple $(e_1, e_2)$ of entities with relation $R$ in $D$ do
    $sentences \gets$ sentences in $T$ that contain $e_1$ and $e_2$
    $f \gets$ frequent features in $sentences$
    $observations \gets observations \cup \{(e_1, e_2, f, R)\}$
$C \gets$ train supervised classifier on $observations$
return $C$
```

Because the training set is enormous, distant supervision can afford very
**rich** features — conjunctions of entity types with intervening words or
dependency paths, like $\textit{M1=ORG} \wedge \textit{M2=PER} \wedge
\textit{nextword=said} \wedge \textit{path}=NP\uparrow NP\uparrow S\uparrow S
\downarrow NP$. It combines the strengths of the earlier methods: a rich
feature-based classifier (like supervised), high-precision KB evidence (like
patterns), no iterated pattern expansion and so **no semantic drift** (unlike
bootstrapping), no labeled training corpus (like unsupervised), and it produces
training _tuples_ that feed a neural classifier where features are not
even needed. The `no-relation` label is trained by sampling entity pairs absent
from any KB relation. Its main weakness is **low precision**, and it only works for
relations a large database already covers.

#### A worked distant-supervision trace

Follow one tuple through the pipeline. The KB fact is $\langle$ `born-in`,
`Albert Einstein`, `Ulm` $\rangle$. Align it to a Wikipedia dump and NER-tag the
result, keeping every sentence that mentions both `Einstein` and `Ulm`:

- _Einstein was born in Ulm in 1879._
- _Einstein, born (1879), Ulm._
- _Ulm, Einstein's birthplace, sits on the Danube._

Each sentence contributes a feature to the one training instance for this tuple.
From the first: entity types `PER`/`LOC`, intervening string `was born in`,
dependency path `PER <-nsubj born ->obl LOC`. From the second: the pattern
`PER, born (YEAR), LOC`. From the third: `PER's birthplace` to the left of the
`LOC`. The instance for `born-in(Einstein, Ulm)` therefore carries a _union_ of
features pooled across all three sentences, and the identical tuple $\langle$
`born-in`, `Edwin Hubble`, `Marshfield` $\rangle$ contributes its own sentences'
features to a second instance of the same relation. The classifier learns that the
relation `born-in` is signaled by the conjunction

$$
\textit{M1=PER} \;\wedge\; \textit{M2=LOC} \;\wedge\; \textit{between}=\textit{"was born in"} \;\wedge\; \textit{path}=\textit{PER}\!\leftarrow\!\textit{born}\!\rightarrow\!\textit{LOC},
$$

which no single sentence would have taught reliably. This is what
separates distant supervision from bootstrapping: bootstrapping expands _patterns_
one at a time and can drift; distant supervision pools _thousands_ of noisy features
per relation into one classifier, so a single wrong sentence is outvoted rather than
propagated. The cost is that a tuple like $\langle$ `born-in`, `Einstein`, `1879`
$\rangle$ — where the KB actually meant `born-year` — injects a mislabeled instance,
the low-precision noise the method is known for.

### Unsupervised relation extraction (Open IE)

To extract relations from the web with _no_ labeled data and _no_ fixed relation
list, use **open information extraction** (Open IE), where relations are simply
strings of words, usually verb-centered. The **ReVerb** system extracts a relation
from a sentence $s$ in four steps:[^jm-openie]

1. Run a POS tagger and entity chunker over $s$.
2. For each verb, find the longest sequence of words starting with the verb that
   satisfies syntactic and lexical constraints, merging adjacent matches.
3. For each such relation phrase $w$, find the nearest noun phrase $x$ to the left
   (not a relative pronoun, wh-word, or existential _there_) and the nearest noun
   phrase $y$ to the right.
4. Assign a confidence $c$ to the relation $r = (x, w, y)$ with a classifier.

$$
% caption: Open IE with ReVerb. The relation phrase is a verb-anchored word string;
% the arguments are the nearest noun phrases on each side, producing untyped triples.
\begin{tikzpicture}[>=stealth, font=\footnotesize,
  s/.style={anchor=west, font=\scriptsize}]
  \definecolor{acc}{HTML}{2348F2}
  \definecolor{red}{HTML}{C0392B}
  \node[s, text=acc] (x) at (0,0) {United};
  \node[s, text=red] (w) at (1.6,0) {has a hub in};
  \node[s, text=acc] (y) at (4.1,0) {Chicago};
  \node[s] at (5.7,0) {, which};
  \node[s, text=red] (w2) at (7.3,0) {is the headquarters of};
  \node[s, text=acc] (y2) at (11.4,0) {United Cont. Holdings};
  \draw[->, acc] (x.north) to[bend left=25] node[above, font=\scriptsize] {arg1} (w.north);
  \draw[->, acc] (w.north) to[bend left=25] node[above, font=\scriptsize] {arg2} (y.north);
  \node[s, anchor=west] at (-0.4,-1.3) {r1: (United, has a hub in, Chicago)};
  \node[s, anchor=west] at (-0.4,-1.9) {r2: (Chicago, is the headquarters of, United Cont. Holdings)};
\end{tikzpicture}
$$

The syntactic constraint requires a verb-initial phrase (which may include nouns,
since light verbs like _make_, _have_, _do_ carry the relation in a noun, as in
_have a hub in_); the lexical constraint prunes rare, over-specific phrases by
keeping only relations that occur with at least 20 distinct argument pairs across a
huge corpus. Fader et al. built a dictionary of 1.7 million normalized relations
this way. The great advantage is coverage — a vast number of relations without
specifying them in advance. The disadvantage is that these string relations must be
mapped to a canonical form before they can join a database, and the verb focus
misses relations expressed nominally.

### Evaluating relation extraction

**Supervised** systems are scored against a human-annotated gold set with
precision, recall, and F-measure. **Semi-supervised** and **unsupervised** methods
are much harder to evaluate, because they mine _new_ relations from huge text and
there is no way to pre-annotate a gold set. The workaround is to draw a random
sample of the output and have a human check it, giving an estimated precision on
the extracted _tuples_ (not the mentions):

$$
\hat{P} \;=\; \frac{\text{\# correctly extracted tuples in the sample}}{\text{total \# extracted tuples in the sample}}.
$$

Ranking output by confidence and sampling the top 1000, top 10,000, and so on lets
one plot how precision behaves as more tuples are extracted. **Recall** cannot be
measured directly — there is no denominator of all true relations in the web.
## Neural and LLM relation extraction

The five families above are the classical picture. Two lines of work extended
relation extraction past it, and both are grounded in specific public systems.

**Distant supervision was made precise (Mintz 2009; Riedel 2010; Zeng 2015).**
Distant supervision as the lesson presents it is due to Mintz, Bills, Snow, and
Jurafsky, _Distant Supervision for Relation Extraction without Labeled Data_ (ACL
2009), who aligned Freebase to Wikipedia and trained a logistic-regression
classifier on the pooled features — the exact recipe traced above. Its known
low-precision fault was attacked directly. Riedel, Yao, and McCallum (_Modeling
Relations and Their Mentions without Labeled Text_, ECML 2010) relaxed the naive
assumption that _every_ sentence mentioning a KB pair expresses the relation, to
the **at-least-one** assumption: at least one of the pooled sentences does.
Multi-instance multi-label learning (Surdeanu et al., EMNLP 2012) generalized this,
and **PCNN** (Zeng et al., _Distant Supervision for Relation Extraction via
Piecewise Convolutional Neural Networks_, EMNLP 2015) added selective attention over
the sentence bag so the classifier could down-weight the noisy mentions. Each step
attacks the precision problem noted above.[^ds-mintz][^ds-pcnn]

**Neural and LLM relation extraction (SpanBERT; PURE; matching-the-blanks).**
The Transformer classifier the lesson sketches — a pretrained encoder with the
subject and object de-lexified to their NER tags — was refined in several public
systems. **SpanBERT** (Joshi et al., _SpanBERT: Improving Pre-training by
Representing and Predicting Spans_, TACL 2020) pretrains by masking and predicting
contiguous spans rather than single tokens, which improved TACRED relation
accuracy because relations hinge on spans. **Matching-the-blanks** (Baldini Soares
et al., ACL 2019) pretrains a relation representation directly, by teaching the
model that two sentences sharing an entity pair encode a similar relation. **PURE**
(Zhong and Chen, _A Frustratingly Easy Approach for Entity and Relation Extraction_,
NAACL 2021) showed a simple pipeline — recognize entities, then classify each pair
with entity-type markers inserted around the spans — beats many joint models,
reinforcing the lesson's de-lexification trick. Most recently, large language models
do relation extraction and Open IE **zero- or few-shot**: prompt the model with the
sentence and the relation inventory (or none, for open extraction) and read off the
triples, no relation-specific training. This trades the fixed-schema precision of a
trained classifier for coverage and flexibility, the same coverage-versus-precision
tension the Open IE section drew, now without hand-built ReVerb constraints.[^re-spanbert][^re-pure]

$$
% caption: The relation-extraction lineage past the five classical families.
% Distant supervision (Mintz 2009) was made precise by the at-least-one and
% multi-instance relaxations and PCNN attention; the neural encoder-classifier was
% refined by SpanBERT and PURE; and LLMs now extract relations zero- or few-shot.
\begin{tikzpicture}[>=stealth, font=\footnotesize,
  b/.style={draw, minimum width=30mm, minimum height=12mm, align=center, font=\scriptsize}]
  \definecolor{acc}{HTML}{2348F2}
  \node[b] (mintz) at (0,1.4)   {Mintz 2009\\distant supervision};
  \node[b] (pcnn)  at (4.6,1.4) {Zeng 2015 PCNN\\bag attention};
  \node[b] (span)  at (0,-1.2)  {SpanBERT 2020\\PURE 2021};
  \node[b, draw=acc, text=acc] (llm) at (4.6,-1.2) {LLM zero-shot\\and Open IE};
  \draw[->, acc, thick] (mintz) -- (pcnn) node[midway, above, font=\scriptsize] {f\/ix precision};
  \draw[->, acc, thick] (mintz) -- (span) node[midway, left, font=\scriptsize] {neural encoder};
  \draw[->, acc, thick] (span) -- (llm) node[midway, above, font=\scriptsize] {no training};
\end{tikzpicture}
$$

## Where this continues

Relation extraction is the first and largest stage of the pipeline, and it spans
five families that trade recall against annotation cost: high-precision hand-built
patterns, supervised classifiers where labels exist, semi-supervised bootstrapping
and distant supervision where they are scarce, and unsupervised Open IE where the
relations themselves are unknown. The neural encoder-classifiers and, lately, the
zero-shot LLMs push the same task further without new hand-built machinery.

With entities linked into typed triples, the pipeline still has to place those
facts in **time** and assemble them into records. Detecting and normalizing
temporal expressions, ordering events on a timeline, and filling slot-and-filler
templates continue in
[extracting times, events, and templates](/natural-language-processing/linguistic-structure/times-events-and-templates).

[^jm-ie]: **Jurafsky & Martin**, _Speech and Language Processing_ (3rd ed.), Ch. 17 — Information Extraction: turning unstructured text into structured data, exemplified by the airline fare-raise story that runs through the chapter.
[^jm-relext]: **Jurafsky & Martin**, Ch. 17, §17.1 — Relation Extraction: relations as ordered tuples over a domain; the ACE and TACRED relation inventories, RDF triples, Freebase, and WordNet's ontological is-a and part-of relations.
[^jm-hearst]: **Jurafsky & Martin**, Ch. 17, §17.2.1 — Using Patterns to Extract Relations: Hearst's lexico-syntactic patterns for the hyponym relation, extended with named-entity constraints for high-precision, low-recall extraction.
[^jm-distant]: **Jurafsky & Martin**, Ch. 17, §17.2.4 — Distant Supervision for Relation Extraction: aligning a large database (Freebase) to text to manufacture noisy training data, combining the strengths of pattern-based, supervised, and unsupervised methods.
[^jm-openie]: **Jurafsky & Martin**, Ch. 17, §17.2.5 — Unsupervised Relation Extraction: Open IE and the ReVerb system, extracting verb-centered relation strings under syntactic and lexical constraints with no fixed relation set.
[^ds-mintz]: **Mintz, Bills, Snow & Jurafsky (2009)**, _Distant Supervision for Relation Extraction without Labeled Data_, ACL 2009 — aligning Freebase to Wikipedia and training a feature-based classifier on pooled per-tuple features; and **Riedel, Yao & McCallum (2010)**, _Modeling Relations and Their Mentions without Labeled Text_, ECML 2010, relaxing the assumption to at-least-one; multi-instance multi-label learning in **Surdeanu et al. (2012)**, EMNLP.
[^ds-pcnn]: **Zeng et al. (2015)**, _Distant Supervision for Relation Extraction via Piecewise Convolutional Neural Networks_ (PCNN), EMNLP 2015 — piecewise CNN sentence encoding with selective attention over the mention bag to suppress noisy distant-supervision instances.
[^re-spanbert]: **Joshi et al. (2020)**, _SpanBERT: Improving Pre-training by Representing and Predicting Spans_, TACL — span-masking pretraining improving TACRED relation accuracy; and **Baldini Soares et al. (2019)**, _Matching the Blanks: Distributional Similarity for Relation Learning_, ACL, pretraining a relation representation from entity-pair-sharing sentences.
[^re-pure]: **Zhong & Chen (2021)**, _A Frustratingly Easy Approach for Entity and Relation Extraction_ (PURE), NAACL — a simple pipeline inserting entity-type markers around subject and object spans, outperforming many joint models and reinforcing the de-lexification approach; recent LLMs extract relations and Open IE triples zero- or few-shot from a prompt.