Information Extraction

A sequence labeler reads the sentence _Citing high fuel prices, United Airlines said Friday it has increased fares by $6perroundtri{p}_{a}ndhandsbackascatteroftaggedspans:‘UnitedAirlines‘isanorganization,‘Friday‘isatime,‘$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.¹

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. 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.²

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 $\text{PartOf}=\{⟨a,b⟩,⟨c,d⟩\}$ 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.

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.

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 $\text{diagnoses}(\text{Echocardiography},\text{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:

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.

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:³

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

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.

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.

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.

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] /

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 $⟨\text{Sydney},\text{Circular Quay}⟩$, 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}$:

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^{\prime }$, the noisy-or combination treats each $\text{Conf}(p)$ as a probability and gives the chance that not all supporting patterns are wrong:

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 $⟨\text{Ryanair},\text{Charleroi}⟩$ 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:

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=⟨\text{easyJet},\text{Luton}⟩$ 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:

That clears any reasonable threshold, so $t$ joins $T$. Contrast a shaky tuple $t^{\prime }=⟨\text{Sydney},\text{Circular Quay}⟩$ matched only by the loose $p_3$: its confidence is just $\text{Conf}(t^{\prime })=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.⁴ 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.

Because the training set is enormous, distant supervision can afford very rich features — conjunctions of entity types with intervening words or dependency paths, like $\text{M1=ORG}\wedge \text{M2=PER}\wedge \text{nextword=said}\wedge \text{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 $⟨$ born-in, Albert Einstein, Ulm $⟩$. 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 $⟨$born-in, Edwin Hubble, Marshfield $⟩$ 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

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 $⟨$ born-in, Einstein, 1879$⟩$ — 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:⁵

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.

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):

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.⁶⁷

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.⁸⁹

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.