AMT302 Concepts of Natural Language Processing - Module 4
Syllabus
Relation Extraction
Finding and classifying semantic relation among entities mentioned in a text like child of
or part-whole or geospatial relation
Wikipedia also offers a large supply of relations, drawn from infoboxes, structured
tables associated with certain Wikipedia articles. For example, the Wikipedia infobox for
Stanford includes structured facts like state = "California" or president = "Marc
Tessier-Lavigne".
Relation Extraction Algorithms
There are five main classes of algorithms for relation extraction: handwritten patterns,
supervised machine learning, semi-supervised (via bootstrapping or distant
supervision), and unsupervised.
1. Using patterns to extract relations
Lexico-Syntactic Patterns also called as Hearst patterns.
For example : Agar is a substance prepared from a mixture of red algae, such as
Gelidium, for laboratory or industrial use.
The Hearst tells that most people don't know what Gelidlum is but that will infer that it is
a kind of red algae ( hyponym)
NP0 such as NP1 {,NP2 ...,(and|or)NPi}, i ≥ 1
implies the following semantics
∀NPi,i ≥ 1,hyponym(NPi,NP0)
Another example: 1. I use AI tools such as chatgpt, Deepseek, Copilot, Bard, etc
Semester 6, Department of CSE(AI & ML), SBCE, 2024-25
AMT302 Concepts of Natural Language Processing - Module 4
⇒ChatGPT, Deepseek, Copilot, and bard are AI tools
Example 2: All the fruits were present at the market including tomatoes, blueberries,
durians and ackees.
⇒we now know that durians and ackees are kinds of fruits
2. Relation extraction via supervised learning
A fixed set of relations and entities is chosen, a training corpus is hand-annotated with
the relations and entities, and the annotated texts are then used to train classifiers to
annotate an unseen test set.
The approach followed -
(1)Find pairs of named entities - usually in the same sentences
(2)Apply a relation classification on each pair - classifiers can use any supervised
technique like Logistics regression, RNN, Transformers , Random Forest, etc.
An optional intermediate filtering classifier can be used to speed up the processing by
making a binary decision on whether a given pair of named entities are related(by any
relation). It’s trained on positive examples extracted directly from all relations in the
annotated corpus, and negative examples generated from within-sentence entity pairs
that are not annotated with a relation
Semester 6, Department of CSE(AI & ML), SBCE, 2024-25
AMT302 Concepts of Natural Language Processing - Module 4
3. Semisupervised Relation Extraction Via Booststrapping
Bootstrapping proceeds by taking the entities in the seed pair, and then finding
sentences (on the web, or whatever dataset we are using) that contain both entities.
From all such sentences, we extract and generalize the context around the entities to
learn new patterns
[what is seed pattern and seed tuples - An example to inference from ]
Semester 6, Department of CSE(AI & ML), SBCE, 2024-25
AMT302 Concepts of Natural Language Processing - Module 4
For example, that we need to create a list of airline/hub pairs,
- only know that Ryanair has a hub at Charleroi.
- Use this seed fact to discover new patterns by finding other mentions of this
relation in our corpus.
- We search for the terms Ryanair, Charleroi and hub in some proximity.
we got
(21.6) Budget airline Ryanair, which uses Charleroi as a hub, scrapped all
weekend flights out of the airport.
(21.7) All flights in and out of Ryanair’s hub at Charleroi airport were grounded on
Friday...
(21.8) A spokesman at Charleroi, a main hub for Ryanair, estimated that 8000
passengers had already been affected
From these results, we can use the context of words between the entity mentions,
the words before mention one, the word after mention two, and the named entity
types of the two mentions, and perhaps other features, to extract general patterns
such as the following:
/ [ORG], which uses [LOC] as a hub /
/ [ORG]’s hub at [LOC] /
/ [LOC], a main hub for [ORG] /
Bootstrapping systems also assign confidence values to new tuples - to avoid semantic
drift
Example : Sydney has a ferry hub at Circular Quay
The tuple got from this=> < Sydney, CircularQuay> which is wrong , leading to bigger
issues
So the ideas of confidence values are introduced
It is based on two factors:
● the pattern’s performance with respect to the current set of tuples
● pattern’s productivity in terms of the number of matches it produces in the
document collection.
Given a document collection D, a current set of tuples T, and a proposed
pattern p, we need to track two factors:
• hits(p): the set of tuples in T that p matches while looking in D
• finds(p): The total set of tuples that p finds in D
Semester 6, Department of CSE(AI & ML), SBCE, 2024-25
AMT302 Concepts of Natural Language Processing - Module 4
The following equation balances these considerations
We can find the confidence in a proposed new
tuple by combining the evidence supporting it from all the patterns that match that
tuple from the Document
One Way ⇒ Noisy-OR
We make two assumptions-
● A proposed type to be false , then all of its supporting patterns must have been in
error
● The sources of their indivdual failures are all independent
.
we can loosely treat these confidence values as probabilities.
Therefore confidence values of a new tuple is
4. Distant Supervision for relation extraction
The distant supervision method distant supervision combines the advantages of
bootstrapping with supervised learning.
Instead of just a handful of seeds, distant supervision 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
Semester 6, Department of CSE(AI & ML), SBCE, 2024-25
AMT302 Concepts of Natural Language Processing - Module 4
=> can apply feature based or neural classification
The main problem with distant supervision is that it tends to produce low-precision
results, and so current research focuses on ways to improve precision. Furthermore,
distant supervision can only help in extracting relations for which a large enough
database already exists. To extract new relations without datasets, or relations for new
domains, purely unsupervised methods must be used.
Semester 6, Department of CSE(AI & ML), SBCE, 2024-25
AMT302 Concepts of Natural Language Processing - Module 4
5. Unsupervised relation extraction
The goal of unsupervised relation extraction is to extract relations from the web
when we have no labeled training data, and not even any list of relations. This task
is often called open information extraction or Open IE.
Evaluation of relation extraction
Semester 6, Department of CSE(AI & ML), SBCE, 2024-25
AMT302 Concepts of Natural Language Processing - Module 4
Information Retrieval
Information retrieval or IR is the name of the field encompassing the retrieval of all
manner of media based on user information needs. The resulting IR system is often
called a search engine.
The IR task we consider is called ad hoc retrieval, in which a user poses a query to a
retrieval system, which then returns an ordered set of documents from some collection.
A document refers to whatever unit of text the system indexes and retrieves (web
pages, scientific papers, news articles, or even shorter passages like paragraphs).
A collection refers to a set of documents being used to satisfy user requests.
A term refers to a word in a collection, but it may also include phrases.
A query represents a user’s information need expressed as a set of terms
We don’t use raw word counts in IR, instead computing a term weight for each
document word.
Two term weighting schemes are common:
- tf-idf
- BM25
Term weighting
The term frequency tells us how frequent the word is; words that occur more often in a
document are likely to be informative about the document’s contents. We usually use
Semester 6, Department of CSE(AI & ML), SBCE, 2024-25
AMT302 Concepts of Natural Language Processing - Module 4
the log10 of the word frequency, rather than the raw count. The intuition is that a word
appearing 100 times in a document doesn’t make that word 100 times more likely to be
relevant to the meaning of the document. Because we can’t take the log of 0, we
normally add 1 to the count:
The document frequency dft of a term t is the number of documents it occurs in. Terms
that occur in only a few documents are useful for discriminating those documents from
the rest of the collection; terms that occur across the entire collection aren’t as helpful.
The inverse document frequency or idf term weight is defined as:
where N is the total number of documents in the
collection, and dft is the number of documents in which term t occurs. The fewer
documents in which a term occurs, the higher this weight; the lowest weight of 0 is
assigned to terms that occur in every document.
Document Scoring
Semester 6, Department of CSE(AI & ML), SBCE, 2024-25
AMT302 Concepts of Natural Language Processing - Module 4
Example Problem
Semester 6, Department of CSE(AI & ML), SBCE, 2024-25
AMT302 Concepts of Natural Language Processing - Module 4
BM25
Adds two parameters: k, a knob that adjust the balance between term frequency and
IDF, and b, which controls the importance of document length normalization. The BM25
score of a document d given a query q is:
Where |d avg| is the length of the average document. When k is 0, BM25 reverts to no
use of term frequency, just a binary selection of terms in the query (plus idf). A large k
results in raw term frequency (plus idf). b ranges from 1 (scaling by document length) to
0 (no length scaling).
Reasonable values : k = [1.2,2] and b = 0.75
Semester 6, Department of CSE(AI & ML), SBCE, 2024-25
AMT302 Concepts of Natural Language Processing - Module 4
Inverted Index
Evaluation of Information Retrieval System
Metrics used - Precision and Recall
Assumption made : that each document returned by the IR system is either relevant to
our purposes or not relevant
Precision- fraction of the returned documents that are relevant
Recall - fraction of all relevant documents that are returned
T - Ranked documents in response to an information request (No. of documents
considered at that point of time ),
R - a subset of T, Relevant documents
N - subset of T, Remaining irrelevant documents,
U - Documents in the collection as a whole are relevant
Semester 6, Department of CSE(AI & ML), SBCE, 2024-25
AMT302 Concepts of Natural Language Processing - Module 4
Unfortunately, these metrics don’t adequately measure the performance of a system
that ranks the documents it returns. If we are comparing the performance of two ranked
retrieval systems, we need a metric that prefers the one that ranks the relevant
documents higher. We need to adapt precision and recall to capture how well a system
does at putting relevant documents higher in the ranking.
The most common way to visualize precision and recall is to plot precision against recall
in a precision-recall curve
Semester 6, Department of CSE(AI & ML), SBCE, 2024-25
AMT302 Concepts of Natural Language Processing - Module 4
Please Note
● Recall is non-decreasing - when a relevant document is encountered recall
increases, and when a non-relevant document is found it remains unchanged.
● Precision, on the other hand, jumps up and down, increasing when relevant
documents are found, and decreasing otherwise.
EVERYTHING DONE ABOVE IS FOR A SINGLE QUERY
But we’ll need to combine values for all the queries, and in a way that lets us compare
one system to another. One way of doing this is to plot averaged precision values at 11
fixed levels of recall (0 to 100, in steps of 10). Since we’re not likely to have datapoints
at these exact levels, we use interpolated precision values for the 11 recall values
from the data points we do have. We can accomplish this by choosing the maximum
precision value achieved at any level of recall at or above the one we’re calculating.
Semester 6, Department of CSE(AI & ML), SBCE, 2024-25
AMT302 Concepts of Natural Language Processing - Module 4
A second way to evaluate ranked retrieval is mean average precision (MAP), which
provides a single metric that can be used to compare competing systems or
approaches. In this approach, we again descend through the ranked list of items, but
now we note the precision only at those points where a relevant item has been
encountered (for example at ranks 1, 3, 5, 6 but not 2 or 4 in Fig. 14.4). For a single
query, we average these individual precision measurements over the return set (up to
some fixed cutoff). More formally, if we assume that Rr is the set of relevant documents
at or above r, then the average precision (AP) for a single query is
where Precision(d) is the precision measured at the rank at which document d was
found. For an ensemble of queries Q, we then average over these averages, to get our
final MAP measure
The MAP for the single query (hence = AP) in Fig. 14.4 is 0.6
Semester 6, Department of CSE(AI & ML), SBCE, 2024-25
AMT302 Concepts of Natural Language Processing - Module 4
Assignment 2.2
Write down short notes on each topic in Module 4
Extra Marks: Try to solve all Previous Year numerical questions from module 4 -
[Question paper available in the NLP whatsapp group]
Semester 6, Department of CSE(AI & ML), SBCE, 2024-25