Information Extraction: Relations, Events, and Time

Turning unstructured information embedded in texts into structured data, e.g. to populate a relational database for further processing.

Relation extraction (semantic relations between entities), event extraction, temporal expression recognition and normalization, temporal ordering of events, and template filling.

A dataset of structured relational knowledge, used e.g. by search engines to present information to users; relation extraction helps populate it.

Finding recurring stereotypical events or situations in documents and filling the slots of a template with text segments or inferred concepts (times, amounts, ontology entities).

FARE-RAISE ATTEMPT
LEAD AIRLINE	United Airlines
AMOUNT	$6
EFFECTIVE DATE	2006-10-26
FOLLOWER	American Airlines

Tim Wagner is a spokesman of (employed by) American Airlines; American Airlines is part of (a unit of) AMR Corp. These instantiate generic relations like part-of or employs.

The 17 relations used in the ACE relation extraction evaluations, grouped into classes like physical (located, near), part-whole, person-social (family, business), org affiliation (employment, founder, membership…), agent-artifact, and gen-affiliation (citizen-resident-ethnicity-religion).

The Unified Medical Language System of the US National Library of Medicine: a network of broad subject categories and entity types with relations between them, e.g. Doppler echocardiography Diagnoses acquired stenosis.

A subject–predicate–object tuple in the Resource Description Framework, e.g. (Golden Gate Park, location, San Francisco).

Infoboxes (structured facts like state = "California"), DBpedia (an ontology of RDF triples from Wikipedia), and Freebase (now part of Wikidata).

The is-a (hypernym) relation between classes (giraffe is-a ruminant is-a ungulate is-a mammal…) and the instance-of relation between individuals and classes (San Francisco instance-of city).

TACRED (person/organization relation triples in news and web text with 41 relation types plus no_relation, mostly no_relation examples) and SemEval 2010 Task 8 (relations between nominals, e.g. product-producer, component-whole).

Sufficient negative data is important for training relation extractors.

Hand-written patterns, supervised machine learning, semi-supervised learning (bootstrapping or distant supervision), and unsupervised (Open IE).

Lexico-syntactic patterns for relation extraction (Hearst, 1992), e.g. “NP₀ such as NP₁ {, NP₂ …, (and|or) NPᵢ}” implies hyponym(NPᵢ, NP₀): from “red algae, such as Gelidium” infer Gelidium is a kind of red algae.

Patterns over NE types, e.g. PER, POSITION of ORG (“George Marshall, Secretary of State of the United States”) or PER (named|appointed) PER Prep? POSITION, to find who holds which office in which organization.

High precision and tailorable to domains, but low recall and laborious to write for all cases.

Annotate a corpus with a fixed set of entities and relations; then (1) find pairs of named entities (usually within a sentence) and (2) classify the relation for each pair with any supervised classifier. An optional filter first decides whether a pair is related at all.

Headwords of the two mentions and their concatenation, bags of words and bigrams in and between the mentions, NE types and their concatenation (ORG-PER), entity level (name, nominal, pronoun), the number of entities between them, and syntactic paths between the mentions.

Feed the sentence to a pretrained encoder (e.g. BERT or SpanBERT) with the subject and object replaced by their NER tags (“[SUBJ-PERSON] was born in [OBJ-LOC]”), and put a linear classifier over the relation labels on the [CLS] output.

Partial de-lexification keeps the system from overfitting to the particular entity words.

Labeling large training sets is very expensive, and models are brittle: they don’t generalize well to new genres.

Start from a few seed tuples (e.g. Ryanair has a hub at Charleroi) or seed patterns; find sentences containing the seed entities, generalize their contexts into new patterns (“[ORG], which uses [LOC] as a hub”), use the patterns to find new tuples, keep high-confidence ones, and iterate.

An erroneous pattern introduces wrong tuples, which create more bad patterns, so the meaning of the extracted relation drifts (e.g. “Sydney has a ferry hub at Circular Quay” yielding ⟨Sydney, Circular Quay⟩).

By balancing its performance on the current tuple set (hits(p): known tuples it matches) against its productivity (finds(p): all tuples it finds), e.g. \(\text{Conf}(p) = \frac{|hits(p)|}{|finds(p)|}\log|finds(p)|\).

With noisy-or: assuming a tuple is false only if all its supporting patterns failed, independently, \(\text{Conf}(t) = 1 - \prod_{p}(1 - \text{Conf}(p))\).

Use a large database (DBpedia, Freebase) of relation tuples as supervision: find sentences in a big corpus containing both entities of a known tuple, extract (noisy) features from all of them, and train a supervised classifier; no-relation examples come from random unrelated entity pairs.

Its training sets are huge, so it can use conjunctions of features, e.g. M1 = ORG & M2 = PER & nextword = “said” & a specific syntactic path.

Like supervised learning it uses many features and detailed human knowledge; like patterns it uses high-precision evidence; like unsupervised methods it needs no labeled text corpus and avoids genre issues, and without iterative expansion there is no semantic drift. But precision tends to be low, and it only works for relations already in a large database.

Their system rediscovered Hearst’s original patterns plus tens of thousands of new ones, like “NP_H like NP” and “NP_H called NP”.

Unsupervised relation extraction from the web with no labeled data and no predefined relations: relations are simply strings of words, usually starting with a verb.

POS-tag and chunk the sentence; for each verb, find the longest verb-initial word sequence meeting syntactic and lexical constraints; take the nearest noun phrases to its left and right as arguments; score the triple with a confidence classifier trained on hand-labeled extractions.

Syntactic: a verb-initial sequence, possibly with nouns, adjectives, prepositions or particles (light verbs like have express the relation with a noun: has a hub in). Lexical: the relation must occur with many distinct arguments in a large corpus, pruning rare long strings.

⟨United, has a hub in, Chicago⟩ and ⟨Chicago, is the headquarters of, United Continental Holdings⟩.

It handles huge numbers of relations without specifying them in advance; but the strings must be mapped to canonical forms for databases, and verb-centered methods miss relations expressed nominally.

Supervised: precision, recall, F1 against gold test relations (labeled or unlabeled). Semi- and unsupervised: no gold set, so estimate precision by having humans check a random sample of extracted tuples, possibly at different levels of recall (top 1,000, 10,000…); recall can’t be measured directly.

Any expression denoting an event or state that can be assigned to a point or interval in time.

No: most verbs introduce events, but noun phrases can too (the move, the increase), and some verbs don’t, like phrasal took effect or light verbs.

A verb with little meaning of its own, whose event is expressed by its direct object noun: in took a flight, flight defines the event; take, make, have just provide syntax.

Event class (action, state, reporting, perception…), plus aspect, tense and modality, e.g. said = (class=REPORTING, tense=PAST, aspect=PERFECTIVE).

As supervised learning: IOB sequence labeling to detect events, then multi-class classifiers for class and attributes, using encoders or features like affixes, nominalization suffixes (-tion), POS, light-verb government, and stems.

A widely used model in which all events and times are intervals (no points), related by 13 primitive relations such as before/after, meets, overlaps, starts, during, finishes and equals (with inverses).

The present can refer to the future (“we fly from San Francisco to Boston at 10”), and past tenses differ in ways not captured by “before now” (“Flight 1902 arrived late” vs “had arrived late”).

A time R separate from the event time E and utterance time U, used to explain tenses: in “When Mary’s flight departed, I had eaten lunch”, the departure is the reference point and the eating precedes it (E < R < U); with “I ate lunch”, eating starts at R.

tense	order
simple past (I ate)	E = R < U
past perfect (I had eaten)	E < R < U
present perfect (I have eaten)	E < R = U
simple future (I will eat)	U < R = E

In spatial terms: at, in, somewhere, near (“somewhere around noon”, “at 6:45 in the morning”), one domain systematically expressed through another.

The categorization of events by their internal temporal structure: whether ongoing or ended, happening at a point or over an interval.

Events, which involve change, versus states, which don’t: a participant being in a state or having a property, seen as unchanging (“I need the cheapest fare”).

From Greek telos “end, goal”: events conceptualized as having a natural endpoint or goal, as accomplishments and achievements are.

Both result in a state, but accomplishments unfold over time toward the end (“booked me a reservation”), while achievements are punctual, with no conceptualized lead-up process (“she found her gate”, “we reached New York”).

No: “I flew” is an activity, while “I flew to New York” is an accomplishment; the class depends on the whole expression in context.

A corpus of American English annotated with temporal information using TimeML, based on Allen’s interval algebra: EVENT (events and states), TIMEX3 (time expressions) and LINK objects.

TLINKs for the 13 Allen temporal relations (event–event, event–time, time–time), ALINKs for aspectual relations between events and subevents, and SLINKs for subordination relations like modal or factive contexts.

(1) Extract temporal expressions; (2) normalize them to a standard format; (3) link events to times and build time graphs or timelines.

Absolute ones map directly to calendar dates or times (April 24, 1916, 10:15 AM); relative ones map via a reference point (yesterday, next semester, two weeks from yesterday); durations are spans (four hours, three weeks).

Words heading temporal expressions: nouns (morning, winter), proper nouns (January, Monday, Ramadan), adjectives (recent, annual), adverbs (hourly, daily).

Rule-based cascades of regular expressions over POS, trigger words and classes (e.g. SUTime), or IOB sequence labelers using embeddings, fine-tuned encoders or classic features.

Lexical triggers used non-temporally: “1984 tells the story of Winston Smith”, “U2’s Sunday Bloody Sunday”.

Mapping a temporal expression to a point in time (calendar date, time of day) or a duration, represented in the ISO 8601 standard.

last week → 2007-W26 (a date of type week); the weekend → duration P1WE, anchored to that week; two weeks → P2W. The dateline 2007-07-02 is the document’s creation time.

YYYY-Wnn is week nn of the year (weeks start Monday; week 1 contains the year’s first Thursday). Pnx is a duration of n units x: P3Y three years, P2D two days, P1WE one weekend.

Patterns matching temporal expressions are paired with semantic procedures, e.g. the pattern for “3 years old” maps to Duration(3, year).

Its dateline: relative expressions like today, yesterday, tomorrow are computed from it with (modular) temporal arithmetic.

Their reference depends on context: the weekend may be the past or coming one depending on the governing verb’s tense; next Friday may mean the nearest Friday or the one after, depending on how close the document date is to a Friday.

Imposing a (partial) order on the events and times in a text, as binary relation classification. Many times are anchored to events (“one week after the storm”), so events must be detected first.

By classifiers trained on TimeBank gold TLINKs between pairs of events/times (and the document time), using words/embeddings, parse paths, tense and aspect; sieve architectures are also used.

Abstract stereotypical situations or stories (Schank & Abelson, 1977): prototypical sequences of sub-events with participants and roles, whose expectations support classification, role assignment and inference of unstated facts.

Two supervised systems: template recognition (sometimes called event recognition), a text classifier deciding whether a sentence invokes the template; and role-filler extraction, a separate classifier (or sequence model) per slot, e.g. LEAD-AIRLINE, AMOUNT.

With coreference resolution.

Producing hierarchically linked templates describing joint ventures (a TIE-UP template whose ACTIVITY slot is itself a template). FASTUS used a cascade of finite-state transducers with hand-written rules: tokenization, multiword and name recognition, noun/verb group chunking, complex groups, entity and event patterns filling templates, then merging references.

Early template filling (DeJong’s Frump), the US-government MUC conferences, then machine learning and sequence labeling (HMMs, MEMMs, CRFs, neural), and shared evaluations: ACE, TAC KBP (slot filling), SemEval.

Mintz et al. (2009) coined distant supervision (similar ideas existed as “weakly labeled data”); Open IE systems include KnowItAll, TextRunner and ReVerb.