Information Extraction: Relations, Events, and Time

Information Extraction: Relations, Events, and Time

In the world of Natural Language Processing (NLP), extracting meaningful information from text is a crucial task. Information extraction (IE) focuses on automatically identifying and extracting structured information from unstructured text. This structured information can then be used for various applications, such as knowledge base construction, question answering, and text summarization. Key aspects of information extraction include identifying relationships between entities, recognizing events, and understanding the temporal context of the information.

Relation Extraction: Uncovering Connections

Relation extraction aims to identify and classify semantic relationships between named entities in a text. Think of it as connecting the dots between people, organizations, locations, and other key elements.

Types of Relations

Relations can be of many types, ranging from simple family relationships to complex business associations. For example:

• per:city_of_birth: Identifies the city where a person was born. (e.g., "Marie Curie was born in Warsaw.")
• org:subsidiaries: Indicates that one organization is a subsidiary of another. (e.g., "Google is a subsidiary of Alphabet Inc.")
• org:member_of: Shows that an entity is a member of another entity. (e.g., "France is a member of the European Union.")
• per:spouse: Identifies the spouse of a person. (e.g., "Barack Obama's spouse is Michelle Obama.")

A crucial aspect of relation extraction is handling the "no relation" case, where two entities are mentioned in the same text but have no specific relationship. Training systems to recognize these negative examples is vital for accuracy.

Consider this example: "Elon Musk, CEO of Tesla, visited the factory." Here, Elon Musk and Tesla have a relationship of org:top_members/employees.

Relation Extraction Algorithms

Several algorithms are used for relation extraction:

• Pattern-Based Extraction: Relies on predefined patterns to identify relations.
• Supervised Machine Learning: Uses annotated data to train models for relation classification.
• Semi-Supervised Learning: Leverages bootstrapping or distant supervision to expand a small set of seed examples.
• Unsupervised Learning: Extracts relations without labeled data.

Pattern-Based Relation Extraction

This approach utilizes predefined patterns to identify relations. These patterns are often lexico-syntactic, meaning they consider both the words and the syntactic structure of the sentences. For instance, the pattern "NP0 such as NP1, NP2, ... and NPi" can be used to identify hyponym relationships (where NPi is a kind of NP0).

Example: "Fruits such as apples, bananas, and oranges are healthy." This pattern identifies that apples, bananas, and oranges are hyponyms of fruits.

Advantages: High precision and can be tailored to specific domains.
Disadvantages: Low recall and requires significant manual effort to create patterns.

Supervised Relation Extraction

Supervised machine learning approaches treat relation extraction as a classification problem. They require a manually annotated training dataset where relations between entities are labeled. The process typically involves:

1. Identifying pairs of named entities in the text.
2. Applying a relation classifier to each pair to determine the relationship type.

An optional filtering classifier can be used to speed up the process by making a binary decision on whether a given pair of named entities are related by any relation.

Features for Supervised Classifiers
Features used to train supervised relation classifiers include:

• Word Features: Headwords of entities, bag-of-words between entities, words surrounding entities.
• Named Entity Features: Entity types (e.g., PERSON, ORGANIZATION), entity levels (NAME, NOMINAL, PRONOUN).
• Syntactic Features: Constituent or dependency paths between entities.

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

Feature	Value
Headwords of M1 and M2	Airlines, Wagner, Airlines-Wagner
Bag-of-words between M1 and M2	a, AMR, of, immediately, matched, move, spokesman, the, unit
Named-entity types of M1 and M2	ORG, PER, ORG-PER
Dependency-tree paths	Airlines ←sub j matched ←comp said →subj Wagner

Neural Supervised Relation Classifiers
Neural models, especially Transformer-based models like BERT, have become popular for relation extraction. These models use pretrained encoders and fine-tune them for relation classification. A typical approach is to replace the subject and object entities in the input with their NER tags to prevent overfitting to individual lexical items.

Advantages: High accuracies when test data is similar to training data and there is sufficient labeled data.
Disadvantages: Requires large labeled datasets and doesn't generalize well to different text genres.

Semi-Supervised Relation Extraction via Bootstrapping

Bootstrapping leverages a small set of seed patterns or tuples to iteratively discover new patterns and relations. The process involves:

1. Gathering a set of seed tuples that have relation R.
2. Finding sentences that contain entities in tuples.
3. Generalizing the context between and around entities in sentences.
4. Using patterns to identify more tuples.

Semantic Drift
A challenge in bootstrapping is semantic drift, where erroneous patterns lead to the introduction of incorrect tuples, which, in turn, lead to the creation of problematic patterns. To mitigate semantic drift, bootstrapping systems assign confidence values to new tuples based on the pattern's performance and productivity.

Advantages: Requires less labeled data than supervised learning.
Disadvantages: Can suffer from semantic drift and may not generalize well to new domains.

Distant Supervision for Relation Extraction

Distant supervision combines the advantages of bootstrapping with supervised learning. It uses a large database to acquire a huge number of seed examples, creates lots of noisy pattern features from all these examples, and then combines them in a supervised classifier.

Steps for Distant Supervision

• Extract tuples with relations from a database: For example, retrieve person-place of birth tuples from Wikipedia
• Search for sentences containing those entities: Find sentences from a large text corpus (like Wikipedia) that mention both entities in the tuple
• Build features: Extract features from the surrounding text and syntactic structure of these sentences to train a classifier.

Example: To learn the place-of-birth relationship between people and their birth cities.

Advantages: Uses a classifier with lots of features, makes use of high-precision evidence for the relation between entities.
Disadvantages: Produces low-precision results and can only help in extracting relations for which a large enough database already exists.

Unsupervised Relation Extraction

Unsupervised relation extraction aims to extract relations from text without labeled training data or a predefined list of relations. This task is often called Open Information Extraction (Open IE). In Open IE, the relations are simply strings of words, usually beginning with a verb.

Steps for ReVerb System

• POS Tagging and Entity Chunking: Run a POS tagger and entity chunker over the sentence
• Verb-Initial Sequence Extraction: For each verb in the sentence, find the longest sequence of words that start with a verb and satisfy syntactic and lexical constraints
• Noun Phrase Identification: Find the nearest noun phrases to the left and right of the extracted relation phrase
• Confidence Assignment: Assign a confidence value to the relation based on a confidence classifier.

Advantages: Handles a huge number of relations without having to specify them in advance.
Disadvantages: The need to map all the strings into some canonical form for adding to databases or knowledge graphs and current methods focus heavily on relations expressed with verbs.

Evaluation of Relation Extraction

Supervised: Evaluate with human-annotated test sets, computing precision, recall, and F-measure.
Semi-supervised/Unsupervised: Drawing a random sample of relations from the output, and having a human check the accuracy of each of these relations and computing precision at different levels of recall.

Event Extraction: Recognizing Occurrences

Event extraction focuses on identifying mentions of events in texts. An event mention is any expression denoting an event or state that can be assigned to a particular point, or interval, in time.

Example

[EVENT Citing] high fuel prices, United Airlines [EVENT said] Friday it has [EVENT increased] fares by $6 per round trip on flights to some cities also served by lower-cost carriers. American Airlines, a unit of AMR Corp., immediately [EVENT matched] [EVENT the move], spokesman Tim Wagner [EVENT said]. United, a unit of UAL Corp., [EVENT said] [EVENT the increase] took effect Thursday and [EVENT applies] to most routes where it [EVENT competes] against discount carriers, such as Chicago to Dallas and Denver to San Francisco.

Event extraction is generally modeled via supervised learning, detecting events via IOB sequence models and assigning event classes and attributes with multi-class classifiers.

Features for Event Detection

• Character Affixes: Character-level prefixes and suffixes of target word
• Nominalization Suffix: Character-level suffixes for nominalizations (e.g., -tion)
• Part of Speech: Part of speech of the target word
• Light Verb: Binary feature indicating that the target is governed by a light verb

Representing Time: Understanding When

Understanding the temporal context of information is critical for many NLP applications. This involves recognizing temporal expressions and ordering events in time.

Temporal logic helps us to convey temporal information. Events are associated with either points or intervals in time, as on a timeline. One event precedes another if the flow of time leads from the first event to the second.

Allen's Interval Algebra

Allen (1984) models all events and time expressions as intervals. There are 13 primitive relations that can hold between these temporal intervals.

Allen relations
A before B (B after A) A overlaps B (B overlaps' A) A meets B (B meets' A) A equals B (B equals A) A starts B (B starts' A) A finishes B (B finishes' A) A during B (B during' A)

Reichenbach’s reference point

Reichenbach (1947) introduced the notion of a reference point. This approach separates the notion of the reference point from the utterance time and the event time. Consider these examples:

• When Mary’s flight departed, I ate lunch.
• When Mary’s flight departed, I had eaten lunch.

Representing Aspect

Aspect refers to how events are categorized by their internal temporal structure. It involves distinguishing between events and states, and characterizing events as activities, accomplishments, or achievements.

Types of Temporal Contours

• Stative: I know my departure gate
• Activity: John is flying
• Accomplishment: Sally booked her flight
• Achievement: She found her gate

Temporally Annotated Datasets: TimeBank

The TimeBank corpus consists of American English text annotated with temporal information (Pustejovsky et al., 2003). The annotations use TimeML (Saur´ı et al., 2006), a markup language for time based on Allen’s interval algebra discussed above (Allen, 1984). There are three types of TimeML objects: an EVENT represent events and states, a TIME represents time expressions like dates, and a LINK represents various relationships between events and times (event-event, event-time, and time-time).

Example

Delta Air Lines earnings soared 33% to a record in the fiscal first quarter, bucking the industry trend toward declining profits.

This text has three events and two temporal expressions (including the creation time of the article, which serves as the document time), and four temporal links that capture the using the Allen relations

Automatic Temporal Analysis

Automatic temporal analysis involves three common steps:

• Extracting temporal expressions
• Normalizing these expressions, by converting them to a standard format
• Linking events to times and extracting time graphs and timelines

Extracting Temporal Expressions

Temporal expressions are phrases that refer to absolute points in time, relative times, durations, and sets of these. The task is to detect temporal expressions in running text.

Example

A fare increase initiated last week by UAL Corp’s United Airlines was matched by competitors over the weekend, marking the second successful fare increase in two weeks

Temporal Normalization

Temporal normalization is the task of mapping a temporal expression to a point in time or to a duration. Normalized times are represented via the ISO 8601 standard for encoding temporal values.

Temporal Ordering of Events

The goal of temporal analysis, is to link times to events and then fit all these events into a complete timeline. Systems that perform all 4 tasks (time extraction creation and normalization, event extraction, and time/event linking) include TARSQI (Verhagen et al., 2005) CLEARTK (Bethard, 2013), CAEVO (Chambers et al., 2014), and CATENA (Mirza and Tonelli, 2016).

Template Filling: Capturing Stereotypical Situations

Template filling involves identifying documents that invoke particular scripts (prototypical sequences of sub-events, participants, and their roles) and then filling the slots in the associated templates with fillers extracted from the text. These slot-fillers may consist of text segments extracted directly from the text, or they may consist of concepts that have been inferred from text elements through some additional processing.

Example

Given the text: "Citing high fuel prices, United Airlines said Friday it has increased fares by $6 per round trip on flights to some cities also served by lower-cost carriers. 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 and applies to most routes where it competes against discount carriers, such as Chicago to Dallas and Denver to San Francisco."

A filled template from our original airline story might look like the following

FARE-RAISE ATTEMPT

LEAD AIRLINE	UNITED AIRLINES
AMOUNT	$6
EFFECTIVE DATE	2006-10-26
FOLLOWER	AMERICAN AIRLINES

Conclusion

Information extraction plays a vital role in transforming unstructured text into structured data, enabling a wide range of NLP applications. By focusing on relationships, events, and time, IE systems provide valuable insights and facilitate deeper understanding of textual information.