BILL MACCARTNEY: Our topic for today and Wednesday
is relation extraction.
And this is an exciting topic both
because it's a great arena to explore
a variety of NLU and machine learning techniques.
And because it has so many real world applications
as we'll see in a moment.
So here's an overview of the next two lectures.
I'm going to start by describing the task of relation
extraction, what it is, why it matters,
and how we might approach it.
Then I'll describe the data resources
we'll need to make headway on the problem.
Next, I'll provide a more precise formulation
of the prediction problem that we're taking on
and I'll propose a strategy for quantitative evaluation.
Then we'll establish some lower bounds on performance
by evaluating some very simple approaches to this problem.
And finally, will point toward some directions
for future exploration.
In the first section, I'll start by defining
the task of relation extraction, then
I'll try to provide some motivation for why
it's an important and exciting problem.
I'll describe both the vision that originally inspired
research in this area and a range
of current practical applications
for relation extraction.
Then I'll describe three paradigms
that correspond to three stages in the evolution of approaches
to relation extraction.
Hand-built patterns, which were dominant in the '80s and '90s.
Supervised learning, which became dominant in the 2000s.
And distant supervision, which has dominated since about 2010
and will be our main focus.
So let's dive in.
So the task of relation extraction
is about extracting structured knowledge from natural language
text.
We want to be able to start from a document like this.
This could be a new story or a web page.
And extract relational triples like founders, PayPal,
Elon Musk, and founders, SpaceX, Elon Musk.
Next, we find this document and we
want to be able to extract, has_spouse,
Elon Musk, Talulah Riley.
We keep reading another document and we
want to extract worked_at, Elon Musk, Tesla Motors.
If we can accumulate a large knowledge
base of relational triples, we can use it
to power question answering and other applications.
Building a knowledge base like this
manually is slow and expensive.
But much of the knowledge that we'd like to capture
is already expressed in abundant text on the web.
So the aim of relation extraction
is to accelerate knowledge base construction
by extracting relational triples from natural language text.
Here's a nice articulation of the vision
for relation extraction.
This is from Tom Mitchell, who is
the former chair of the machine learning department at CMU.
He's also the author of one of the first textbooks
on machine learning.
By the way, he was also the PhD advisor
of Sebastian Thrun and Oren Etzioni.
He wrote this piece in 2005 describing
a vision for machine reading.
And he offered to bet a lobster dinner that by 2015, we
will have a computer program capable of automatically
reading at least 80% of the factual content on the web,
and placing those facts in a structured knowledge base.
I think we've come pretty close to achieving that goal.
And this is exactly the goal that relation extraction
aims at to extract structure knowledge
from unstructured text.
One of the things that makes relation extraction
an exciting topic is the abundance
of real world applications.
For example, nowadays intelligent assistants
like Siri or Google can answer lots of factual questions
like who sang "Love Train?"
To do this, they rely on knowledge bases or KB's
containing thousands of relations,
millions of entities and billions of individual facts.
There are many different strategies
for building and maintaining and extending these KB's,
but considering how enormous they are
and how quickly the world is creating new facts.
It's a process that you want to automate as much as possible.
So more and more relation extraction from the web
is hugely strategic for Apple and Google and other companies.
In fact in 2017, Apple spent $200 million to acquire
a startup called Lattice, which was co-founded by Stanford
Professor Chris Ré, whom some of you may know,
specifically for this purpose.
Another example is building ontologies.
If you're running an app store, you're
going to need a taxonomy of categories
of apps, and which apps belong to which categories.
One category of apps is video games.
But if you're a gamer, you know that there
are subcategories and sub, subcategories and sub,
sub subcategories of video games.
And new ones keep appearing and new games appear every day.
How are you going to keep your ontology up to date?
Well, there's a lot of people writing
about video games on the web.
So maybe relation extraction can help.
The relation between a category and a subcategory,
or between a category and an instance of the category
can be a target for relation extraction.
And similarly, you can imagine using relation extraction
to help build or maintain ontologies of car
parts or companies or viruses.
Another example comes from bioinformatics.
So every year, there are thousands
of new research articles describing
gene regulatory networks.
If we can apply relation extraction to these articles
to populate a database of gene regulation relationships,
then we can begin to apply existing,
well understood data mining techniques.
We can look for statistical correlations
or apply clever graph algorithms to activation networks.
The sky's the limit.
We've turned something that a machine
can't understand into something that a machine can understand.
So let's turn to the question of how you'd actually
solve this problem.
The most obvious way to start is to write down a few patterns
which express each relation.
So for example, if we want to find new instances
of the founders relation.
So we can use patterns like X is the founder of Y or X,
who founded Y or Y was founded by X.
And then if we search a large corpus,
we may find sentences like these that match these patterns
and allow us to extract the fact that Elon Musk founded SpaceX.
So this seems promising and, in fact, this
was the dominant paradigm in relation extraction
in the early days.
But this approach is really limited.
The central challenge of relation extraction
is the fantastic diversity of language.
The multitude of possible ways to express a given relation.
For example, each of these sentences
also expresses the fact that Elon Musk founded SpaceX.
But in these examples, the patterns
which connect Elon Musk with SpaceX
are not ones that we could have easily anticipated.
They might be ones that will never recur again.
So to do relation extraction effectively,
we need to go beyond hand-built patterns.
So around the turn of the century,
the machine learning revolution came to the field of NLP
and people began to try a new approach, namely
supervised learning.
So you start by labeling your examples.
So these three examples are positive instances
of the founders relation.
So these are the positive examples.
And these two are negative examples.
Now that we have labeled training data,
we can train a model.
And it could be a simple linear model that
uses a bag of words representation
and assigns higher weights to words like founder
and established that are likely to indicate the founder's
relation, or it could be something more complicated.
In any case, this was a hugely successful idea.
Even simple machine learning models
are far better at generalizing to new data
than static patterns.
But there's a big problem, manually labeling
training examples is laborious and time consuming
and expensive.
And as a consequence, the largest
labeled data sets that were produced had only tens
of thousands of examples, which by modern standards seems puny.
If we want to apply modern machine learning techniques,
we need a lot more data.
We need a way to leverage vastly greater quantities of training
data.
The answer appeared around 2010 with an idea
called distant supervision, and this is a really big idea.
Instead of manually labeling individual examples,
we're going to automatically derive
the labels from an existing knowledge base.
So let's say we already have a KB that
contains many examples of the founders relation.
So we've got SpaceX and Elon Musk, Apple, and Steve Jobs
and so on.
And let's say we have a large corpus of text.
It can be unlabeled text, raw text, which means
that it can be truly enormous.
It can be the whole web.
What we're going to do is, we're going to simply assume
that every sentence which contains a pair of entities
which are related in the KB like Elon Musk and SpaceX
is a positive example for that relation.
And we're going to assume that every sentence which contains
a pair of entities that are unrelated in a KB
like Elon Musk and Apple is a negative example.
Genius.
This gives us a way to generate massive quantities of training
data practically free.
However, you might have some doubts about the validity
of those assumptions.
So hold that thought.
Distant supervision is a really powerful idea,
but it has two important limitations.
The first is a consequence of making the unreliable
assumption that all sentences where related entities co-occur
actually express that relation.
Inevitably, some of them don't.
Like this example, we labeled it as a positive example
for the founder's relation, but it doesn't
express that relation at all.
This doesn't say that Elon Musk is a founder of SpaceX.
So this label is a lie, a dirty, dirty lie.
Making this assumption blindly has
the effect of introducing noise into our training data.
Distant supervision is effective in spite of this problem,
because it makes it possible to leverage
vastly greater quantities of training data.
And the benefit of more data outweighs
the harm of noisier data.
By the way, I feel like I've waited my whole life
for the right opportunity to use the Pinocchio emoji.
The day finally came and it feels good.
The second limitation is that we need an existing KB
to start from.
We can only train a model to extract
new instances of the founder's relation,
if we already have many instances of the founder's
relation.
So while distant supervision is a great way
to extend an existing KB, it's not
useful for creating a KB containing
new relations from scratch.