[MUSIC PLAYING]
SPEAKER 1: OK, welcome back, everyone, to our final topic in an introduction
to artificial intelligence with Python.
And today, the topic is language.
So thus far in the class, we've seen a number
of different ways of interacting with AI, artificial intelligence,
but it's mostly been happening in the way of us formulating problems
in ways that I can understand-- learning to speak the language of AI,
so to speak, by trying to take a problem and formulated as a search problem,
or by trying to take a problem and make it a constraint satisfaction problem--
something that our AI is able to understand.
Today, we're going to try and come up with algorithms and ideas that
allow our AI to meet us halfway, so to speak--
to be able to allow AI to be able to understand, and interpret, and get
some sort of meaning out of human language--
the type of language, in the spoken language,
like English, or some other language that we naturally speak.
And this turns out to be a really challenging task for AI.
And it really encompasses a number of different types of tasks
all under the broad heading of natural language processing,
the idea of coming up with algorithms that
allow our AI to be able to process and understand natural language.
So these tasks vary in terms of the types of tasks
we might want an AI to perform, and therefore, the types of
algorithms that we might use.
Them but some common tasks that you might see
are things like automatic summarization.
You give an AI a long document, and you would like for the AI
to be able to summarize it, come up with a shorter
representation of the same idea, but still in some kind of natural language,
like English.
Something like information extraction-- given a whole corpus of information
in some body of documents or on the internet,
for example, we'd like for our AI to be able to extract
some sort of meaningful semantic information out of all of that content
that it's able to look at and read.
Language identification-- the task of, given a page,
can you figure out what language that document is written in?
This is the type of thing you might see if you use a web browser where,
if you open up a page in another language,
that web browser might ask you, oh, I think it's in this language-- would
you like me to translate into English for you, for example?
And that language identification process is a task
that our AI needs to be able to do, which is then related then
to machine translation, the process of taking text in one language
and translating it into another language-- which there's
been a lot of research and development on really
over the course of the last several years.
And it keeps getting better, in terms of how
it is that AI is able to take text in one language
and transform that text into another language as well.
In addition to that, we have topics like named entity recognition.
Given some sequence of text, can you pick out what the named entities are?
These are names of companies, or names of people,
or names of locations for example, which are often relevant or important parts
of a particular document.
Speech recognition as a related task not to do with the text that is written,
but text that is spoken-- being able to process audio and figure out,
what are the actual words that are spoken there?
And if you think about smart home devices, like Siri or Alexa,
for example, these are all devices that are now
able to listen to when we are able to speak, figure out
what words we are saying, and draw some sort of meaning out of that as well.
We've talked about how you could formulate something,
for instance, as a hit and Markov model to be able to draw
those sorts of conclusions.
Text classification, more generally, is a broad category
of types of ideas, whenever we want to take some kind of text
and put it into some sort of category.
And we've seen these classification type problems
and how we can use statistical machine learning approaches
to be able to solve them.
We'll be able to do something very similar with natural language
that we may need to make a couple of adjustments that we'll see soon.
And then something like word sense disambiguation,
the idea that, unlike in the language of numbers,
where AI has very precise representations of everything, words
and are a little bit fuzzy, in terms of their meaning,
and words can have multiple different meanings--
and natural language is inherently ambiguous,
and we'll take a look at some of those ambiguities in due time today.
But one challenging task, if you want an AI
to be able to understand natural language,
is being able to disambiguate or differentiate
between different possible meanings of words.
If I say a sentence like, I went to the bank, you need to figure out,
do I mean the bank where I deposit and withdraw money or do
I mean the bank like the river bank?
And different words can have different meanings
that we might want to figure out.
And based on the context in which a word appears--
the wider sentence, or paragraph, or paper
in which a particular word appears--
that might help to inform how it is that we
disambiguate between different meanings or different senses
that a word might have.
And there are many other topics within natural language processing,
many other algorithms that have been devised
in order to deal with and address these sorts of problems.
And today, we're really just going to scratch the surface,
looking at some of the fundamental ideas that are behind many of these ideas
within natural language processing, within this idea of trying to come up
with AI algorithms that are able to do something meaningful with the languages
that we speak everyday.
And so to introduce this idea, when we think about language,
we can often think about it in a couple of different parts.
The first part refers to the syntax of language.
This is more to do with just the structure of language
and how it is that that structure works.
And if you think about natural language, syntax is one of those things
that, if you're a native speaker of a language,
it comes pretty readily to you.
You don't have to think too much about it.
If I give you a sentence from Sir Arthur Conan Doyle's Sherlock Holmes,
for example, a sentence like this--
"just before 9:00 o'clock, Sherlock Holmes stepped briskly into the room"--
I think we could probably all agree that this
is a well-formed grammatical sentence.
Syntactically, it makes sense, in terms of the way
that this particular sentence is structured.
And syntax applies not just to natural language, but to programming languages
as well.
If you've ever seen a syntax error in a program that you've written,
it's likely because you wrote some sort of program
that was not syntactically well-formed.
The structure of it was not a valid program.
In the same way, we can look at English sentences, or sentences
in any natural language, and make the same kinds of judgments.
I can say that this sentence is syntactically well-formed.
When all the parts are put together, all these words are in this order,
it constructs a grammatical sentence, or a sentence that most people would agree
is grammatical.
But there are also grammatically ill-formed sentences.
A sentence like, "just before Sherlock Holmes
9 o'clock stepped briskly the room"--
well, I think we would all agree that this is not a well-formed sentence.
Syntactically, it doesn't make sense.
And this is the type of thing that, if we want our AI, for example,
to be able to generate natural language--
to be able to speak to us the way like a chat bot would speak to us,
for example--
well then our AI is going to need to be able to know this distinction somehow,
is going to be able to know what kinds of sentences are grammatical,
what kinds of sentences are not.
And we might come up with rules or ways to statistically learn these ideas,
and we'll talk about some of those methods as well.
Syntax can also be ambiguous.
There are some sentences that are well-formed and not well-formed,
but certain way-- there are certain ways that you could take a sentence
and potentially construct multiple different structures for that sentence.
A sentence like, "I saw the man on the mountain with a telescope," well,
this is grammatically well-formed-- syntactically, it makes sense--
but what is the structure of the sentence?
Is it the man on the mountain who has the telescope, or am
I seeing the man on the mountain and I am using the telescope in order
to see the man on the mountain?
There's some interesting ambiguity here, where it could have potentially
two different types of structures.
And this is one of the ideas that will come back to also,
in terms of how to think about dealing with AI when natural language is
inherently ambiguous.
So that then is syntax, the structure of language,
and getting an understanding for how it is
that, depending on the order and placement of words,
we can come up with different structures for language.
But in addition to language having structure, language also has meaning.
And now we get into the world of semantics, the idea of,
what it is that a word, or a sequence of words,
or a sentence, or an entire essay actually means?
And so a sentence like, "just before 9:00, Sherlock Holmes
stepped briskly into the room," is a different sentence
from a sentence like, "Sherlock Holmes stepped briskly into the room just
before 9:00."
And yet they have effectively the same meaning.
They're different sentences, so an AI reading
them would recognize them as different, but we as humans
can look at both the sentences and say, yeah,
they mean basically the same thing.
And maybe, in this case, it was just because I moved the order of the words
around.
Originally, 9 o'clock with near the beginning of the sentence.
Now 9 o'clock is near the end of the sentence.
But you might imagine that I could come up with a different sentence entirely,
a sentence like, "a few minutes before 9:00, Sherlock Holmes
walked quickly into the room."
And OK, that also has a very similar meaning,
but I'm using different words in order to express that idea.
And ideally, AI would be able to recognize
that these two sentences, these different sets of words that
are similar to each other, have similar meanings,
and to be able to get at that idea as well.
Then there are also ways that a syntactically well-formed sentence
might not mean anything at all.
A famous example from linguist Noam Chomsky is this sentence here--
"colorless green ideas sleep furiously."
Syntactically, that sentence is perfectly fine.
Colorless and green are adjectives that modify the noun ideas.
Sleep is a verb.
Furiously is an adverb.
These are correct constructions, in terms of the order of words,
but it turns out this sentence is meaningless.
If you tried to ascribe meaning to the sentence, what does it mean?
And it's not easy to be able to determine
what it is that it might mean.
Semantics itself can also be ambiguous, given that different structures can
have different types of meanings.
Different words can have different kinds of meanings,
so the same sentence with the same structure
might end up meaning different types of things.
So my favorite example from the LA times is
a headline that was in the Los Angeles Times a little while back.
The headline says, "Big rig carrying fruit crashes on 210 freeway,
creates jam."
So depending on how it is you look at the sentence--
how you interpret the sentence-- it can have multiple different meanings.
And so here too are challenges in this world of natural language processing,
being able to understand both the syntax of language
and the semantics of language.
And today, we'll take a look at both of those ideas.
We're going to start by talking about syntax
and getting a sense for how it is that language is structured,
and how we can start by coming up with some rules, some ways
that we can tell our computer, tell our AI what types of things
are valid sentences, what types of things are not valid sentences.
And ultimately, we'd like to use that information
to be able to allow our AI to draw meaningful conclusions,
to be able to do something with language.
And so to do so, we're going to start by introducing
the notion of formal grammar.
And what formal grammar is all about its formal grammar
is a system of rules that generate sentences in a language.
I would like to know what are the valid English sentences--
not in terms of what they mean--
just in terms of their structure-- their syntactic structure.
What structures of English are valid, correct sentences?
What structures of English are not valid?
And this is going to apply in a very similar way to other natural languages
as well, where language follows certain types of structures.
And we intuitively know what these structures mean,
but it's going to be helpful to try and really formally define
what the structures mean as well.
There are a number of different types of formal grammar
all across what's known as the Chomsky hierarchy of grammars.
And you may have seen some of these before.
If you've ever worked with regular expressions before,
those belong to a class of regular languages.
They correspond to regular languages, which is a particular type of language.
But also on this hierarchy is a type of grammar
known as a context-free grammar.
And this is the one we're going to spend the most
time on taking a look at today.
And what a context-free grammar is it is a way of taking--
of generating sentences in a language or via what
are known as rewriting rules-- replacing one symbol with other symbols.
And we'll take a look in a moment at just what that means.
So let's imagine, for example, a simple sentence in English,
a sentence like, "she saw the city"--
a valid, syntactically well-formed English sentence.
But we'd like for some way for our AI to be able to look at the sentence
and figure out, what is the structure of the sentence?
If you imagine a guy in question answering format--
if you want to ask the AI a question like, what did she see,
well, then the AI wants to be able to look at this sentence
and recognize that what she saw is the city-- to be able to figure that out.
And it requires some understanding of what
it is that the structure of this sentence really looks like.
So where do we begin?
Each of these words-- she, saw, the, city--
we are going to call terminal symbols.
There are symbols in our language-- where each of these words is just
a symbol--
where this is ultimately what we care about generating.
We care about generating these words.
But each of these words we're also going to associate
with what we're going to call a non-terminal symbol.
And these non-terminal symbols initially are going to look kind of like parts
of speech, if you remember back to like English grammar--
where she is a noun, saw is a V for verb,
the is a D. D stands for determiner.
These are words like the, and a, and and, for example.
And then city-- well, city is also a noun, so an N goes there.
So each of these--
N, V, and D--
these are what we might call non-terminal symbols.
They're not actually words in the language.
She saw the city-- those are the words in the language.
But we use these non-terminal symbols to generate the terminal symbols,
the terminal symbols which are like, she saw the city--
the words that are actually in a language like English.
And so in order to translate these non-terminal symbols into terminal
symbols, we have what are known as rewriting rules,
and these rules look something like this.
We have N on the left side of an arrow, and the arrow
says, if I have an N non-terminal symbol,
then I can turn it into any of these various different possibilities
that are separated with a vertical line.
So a noun could translate into the word she.
A noun could translate into the word city, or car, or Harry,
or any number of other things.
These are all examples of nouns, for example.
Meanwhile, a determiner, D, could translate into the, or a, or an.
V for verb could translate into any of these verbs.
P for preposition could translate into any of those prepositions--
to, on, over, and so forth.
And then ADJ for adjective can translate into any of these possible adjectives
as well.
So these then are rules in our context-free grammar.
When we are defining what it is that our grammar is,
what is the structure of the English language or any other language,
we give it these types of rules saying that a noun could
be any of these possibilities, a verb could be any of those possibilities.
But it turns out we can then begin to construct other rules where
it's not just one non-terminal translating into one terminal symbol.
We're always going to have one non-terminal on the left-hand side
of the arrow, but on the right-hand side of the arrow,
we could have other things.
We could even have other non-terminal symbols.
So what do I mean by this?
Well, we have the idea of nouns-- like she, city, car, Harry, for example--
but there are also a noun phrases--
like phrases that work as nouns--
that are not just a single word, but there are multiple words.
Like the city is two words, that together, operate
as what we might call a noun phrase.
It's multiple words, but they're together operating as a noun.
Or if you think about a more complex expression, like the big city--
three words all operating as a single noun--
or the car on the street--
multiple words now, but that entire set of words operates kind of like a noun.
It substitutes as a noun phrase.
And so to do this, we'll introduce the notion
of a new non-terminal symbol called NP, which will stand for noun phrase.
And this rewriting rule says that a noun phrase it could be a noun--
so something like she is a noun, and therefore, it
can also be a noun phrase--
but a noun phrase could also be a determiner, D, followed by a noun--
so two ways we can have a noun phrase in this very simple grammar.
Of course, the English language is more complex than just this,
but a noun phrase is either a noun or it is a determiner followed by a noun.
So for the first example, a noun phrase that is just a noun,
that would allow us to generate noun phrases like she,
because a noun phrase is just a noun, and a noun
could be the word she, for example.
Meanwhile, if we wanted to look at one of the examples of these, where
a noun phrase becomes a determiner and a noun,
then we get a structure like this.
And now we're starting to see the structure of language
emerge from these rules in a syntax tree, as we'll call it,
this tree-like structure that represents the syntax of our natural language.
Here, we have a noun phrase, and this noun phrase
is composed of a determiner and a noun, where the determiner is the word the,
according to that rule, and noun is the word city.
So here then is a noun phrase that consists of multiple words inside
of the structure.
And using this idea of taking one symbol and rewriting it using other symbols--
that might be terminal symbols, like the and city,
but might also be non-terminal symbols, like D for determiner or N for noun--
then we can begin to construct more and more complex structures.
In addition to noun phrases, we can also think about verb phrases.
So what might a verb phrase look like?
Well, a verb phrase might just be a single verb.
In a sentence like "I walked," walked is a verb,
and that is acting as the verb phrase in that sentence.
But there are also more complex verb phrases that aren't just a single word,
but that are multiple words.
If you think of the sentence like "she saw the city," for example,
saw the city is really that entire verb phrase.
It's taking up like what it is that she is doing, for example.
And so our verb phrase might have a rule like this.
A verb phrase is either just a plain verb
or it is a verb followed by a noun phrase.
And we saw before that a noun phrase is either a noun
or it is a determiner followed by a noun.
And so a verb phrase might be something simple,
like verb phrase it is just a verb.
And that verb could be the word walked for example.
But it could also be something more sophisticated,
something like this noun, where we begin to see a larger syntax tree,
where the way to read the syntax tree is that a verb
phrase is a verb and a noun phrase, where
that verb could be something like saw.
And this is a noun phrase we've seen before, this noun phrase that
is the city-- a noun phrase composed of the determiner the and the noun
city all put together to construct this larger verb phrase.
And then just to give one more example of a rule,
we could also have a rule like this--
sentence S goes to noun phrase and a verb phrase.
The basic structure of a sentence is that it is
a noun phrase followed by verb phrase.
And this is a formal grammar way of expressing the idea
that you might have learned when you learned English grammar, when you read
that a sentence is like a subject and a verb, subject and action--
something that's happening to a particular noun phrase.
And so using this structure, we could construct
a sentence that looks like this.
A sentence consists of a noun phrase and a verb phrase.
A noun phrase could just be a noun, like the word she.
The verb phrase could be a verb and a noun phrase,
where-- this is something we've seen before-- the verb is saw
and the noun phrase is the city.
And so now look what we've done here.
What we've done is, by defining a set of rules,
there are algorithms that we can run that take these words--
and the CYK algorithm, for example, is one example of this if you want to look
into that--
where you start with a set of terminal symbols, like she saw the city,
and then using these rules, you're able to figure out,
how is it that you go from a sentence to she saw the city?
And it's all through these rewriting rules.
So the sentence is a noun phrase and a verb phrase.
A verb phrase could be a verb and a noun phrase, so on and so forth,
where you can imagine taking this structure
and figuring out how it is that you could generate a parse tree--
a syntax tree-- for that set of terminal symbols, that set of words.
And if you tried to do this for a sentence that was not grammatical,
something like "saw the city she," well, that wouldn't work.
There'd be no way to take a sentence and use
these rules to be able to generate that sentence that
is not inside of that language.
So this sort of model can be very helpful
if the rules are expressive enough to express
all the ideas that you might want to express inside of natural language.
Of course, using just the simple rules we have here,
there are many sentences that we won't be able to generate-- sentences
that we might agree are grim and syntactically well-formed,
but that we're not going to be able to construct using these rules.
And then, in that case, we might just need
to have some more complex rules in order to deal with those sorts of cases.
And so this type of approach can be powerful
if you're dealing with a limited set of rules and words
that you really care about dealing with.
And one way we can actually interact with this in Python
is by using a Python library called NLTK, short for natural language
toolkit, which we'll see a couple of times today,
which has a wide variety of different functions and classes
that we can take advantage of that are all
meant to deal with natural language.
And one such algorithm that it has is the ability to parse
a context-free grammar, to be able to take some words
and figure out according to some context-free grammar,
how would you construct the syntax tree for it?
So let's go ahead and take a look at NLTK
now by examining how we might construct some context-free grammars with it.
So here inside of cfg0--
cfg's short for context-free grammar--
I have a sample context-free grammar which has rules that we've seen before.
So sentence goes to noun phrase followed by a verb phrase.
Noun phrase is either a determiner and a noun or a noun.
Verb phrase is either a verb or a verb and a noun phrase.
The order of these things doesn't really matter.
Determiners could be the word the or the word a.
A noun could be the word she, city, or car.
And a verb could be the word saw or it could be the word walked.
Now, using NLTK, which I've imported here at the top,
I'm going to go ahead and parse this grammar
and save it inside of this variable called parser.
Next, my program is going to ask the user for input.
Just type in a sentence, and dot split will just
split it on all of the spaces, so I end up
getting each of the individual words.
We're going to save that inside of this list called sentence.
And then we'll go ahead and try to parse the sentence, and for each sentence
we parse, we're going to pretty print it to the screen,
just so it displays in my terminal.
And we're also going to draw it.
It turns out that NLTK has some graphics capacity,
so we can really visually see what that tree looks like as well.
And there are multiple different ways a sentence might be parsed,
which is why we're putting it inside of this for loop.
And we'll see why that can be helpful in a moment too.
All right, now that I have that, let's go ahead and try it.
I'll cd into cfg, and we'll go ahead and run cfg0.
So it then is going to prompt me to type in a sentence.
And let me type in a very simple sentence-- something
like she walked, for example.
Press Return.
So what I get is, on the left-hand side, you
can see a text-based representation of the syntax tree.
And on the right side here-- let me go ahead and make it bigger--
we see a visual representation of that same syntax tree.
This is how it is that my computer has now parsed the sentence she walked.
It's a sentence that consists of a noun phrase and a verb phrase,
where each phrase is just a single noun or verb, she and then walked--
same type of structure we've seen before,
but this now is our computer able to understand
the structure of the sentence, to be able to get
some sort of structural understanding of how it is that parts of the sentence
relate to each other.
Let me now give it another sentence.
I could try something like she saw the city, for example--
the words we were dealing with a moment ago.
And then we end up getting this syntax tree out of it--
again, a sentence that has a noun phrase and a verb phrase.
The noun phrase is fairly simple.
It's just she.
But the verb phrase is more complex.
It is now saw the city, for example.
Let's do one more with this grammar.
Let's do something like she saw a car.
And that is going to look very similar--
that we also get she.
But our verb phrase is now different.
It's saw a car, because there are multiple possible determiners
in our language and multiple possible nouns.
I haven't given this grammar rule that many words,
but if I gave it a larger vocabulary, it would then
be able to understand more and more different types of sentences.
And just to give you a sense of some added complexity we could add here,
the more complex our grammar, the more rules we add,
the more different types of sentences we'll
then have the ability to generate.
So let's take a look at cfg1, for example,
where I've added a whole number of other different types of rules.
I've added the adjective phrases, where we can have multiple adjectives inside
of a noun phrase as well.
So a noun phrase could be an adjective phrase followed by a noun phrase.
If I wanted to say something like the big city,
that's an adjective phrase followed by a noun phrase.
Or we could also have a noun and a prepositional phrase--
so the car on the street, for example.
On the street is a prepositional phrase, and we
might want to combine those two ideas together, because the car on the street
can still operate as something kind of like a noun phrase as well.
So no need to understand all of these rules in too much detail--
it starts to get into the nature of English grammar--
but now we have a more complex way of understanding these types of sentences.
So if I run Python cfg1--
and I can try typing something like she saw the wide street, for example--
a more complex sentence.
And if we make that larger, you can see what this sentence looks like.
I'll go ahead and shrink it a little bit.
So now we have a sentence like this-- she saw the wide street.
The wide street is one entire noun phrase,
saw the wide street is an entire verb phrase,
and she saw the wide street ends up forming that entire sentence.
So let's take a look at one more example to introduce this notion of ambiguity.
So I can run Python cfg1.
Let me type a sentence like she saw a dog with binoculars.
So there's a sentence, and here now is one possible syntax tree
to represent this idea--
she saw, the noun phrase a dog, and then the prepositional phrase
with binoculars.
And the way to interpret the sentence is that what it is that she saw was a dog.
And how did she do the seeing?
She did the seeing with binoculars.
And so this is one possible way to interpret this.
She was using binoculars.
Using those binoculars, she saw a dog.
But another possible way to pass that sentence
would be with this tree over here, where you have something
like she saw a dog with binoculars, where a dog with binoculars
forms an entire noun phrase of its own--
same words in the same order, but a different grammatical structure,
where now we have a dog with binoculars all inside of this noun phrase,
meaning what did she see?
What she saw was a dog, and that dog happened
to have binoculars with the dog-- so different ways to parse the sentence--
structures for the sentence-- even given the same possible sequence of words.
And NLTK's algorithm and this particular algorithm
has the ability to find all of these, to be
able to understand the different ways that you might
be able to parse a sentence and be able to extract some sort of useful meaning
out of that sentence as well.
So that then is a brief look at what we can do--
using getting the structure of language, of using these context-free grammar
rules to be able to describe the structure of language.
But what we might also care about is understanding
how it is that these sequences of words are
likely to relate to each other in terms of the actual words themselves.
The grammar that we saw before could allow us to generate a sentence like,
I eat a banana, for example, where I is the noun phrase and ate a banana
is a verb phrase.
But it would also allow for sentences like, I
eat a blue car, for example, which is also syntactically well-formed
according to the rules, but is probably a less likely sentence that a person is
likely to speak.
And we might want for our AI to be able to encapsulate
the idea that certain sequences of words are more or less likely than others.
So to deal with that, we'll introduce the notion of an n-gram,
and an n-gram, more generally, just refers to some sequence
of n items inside of our text.
And those items might take various different forms.
We can have character n-grams, which are just a contiguous
sequence of n characters-- so three characters in a row,
for example, or four characters in a row.
We can also have word n-grams, which are a contiguous
sequence of n words in a row from a particular sample of text.
And these end up proving quite useful, and you
can choose our n to decide how many how long is our sequence going to be.
So when n is 1, we're just looking at a single word or a single character.
And that is what we might call a unigram, just one item.
If we're looking at two characters or two words,
that's generally called a bigram-- so an n-gram
where n is equal to 2, looking at two words that are consecutive.
And then, if there are three items, you might
imagine we'll often call those trigrams-- so three characters
in a row or three words that happen to be in a contiguous sequence.
And so if we took a sentence, for example--
here's a sentence from, again, Sherlock Holmes--
"how often have I said to you that, when you
have eliminated the impossible, whatever remains,
however improbable, must be the truth."
What are the trigrams that we can extract from the sentence?
If we're looking at sequences of three words,
well, the first trigram would be how often
have-- just a sequence of three words.
And then we can look at the next trigram,
often have I. The next trigram is have I said.
Then I said to, said to you, to you that, for example--
those are all trigrams of words, sequences of three contiguous words
that show up in the text.
And extracting those bigrams and trigrams, or n-grams more generally,
turns out to be quite helpful, because often,
when we're dealing with analyzing a lot of text,
it's not going to be particularly meaningful for us to try
and analyze the entire text at one time.
But instead, we want to segment that text into pieces that we
can begin to do some analysis of--
that our AI might never have seen this entire sentence before,
but it's probably seen the trigram to you that before,
because to you that is something that might have come up in other documents
that our AI has seen before.
And therefore, it knows a little bit about that particular sequence
of three words in a row-- or something like have I said,
another example of another sequence of three words that's probably
quite popular, in terms of where you see it inside the English language.
So we'd like some way to be able to extract these sorts of n-grams.
And how do we do that?
How do we extract sequences of three words?
Well, we need to take our input and somehow separate it
into all of the individual words.
And this is a process generally known as tokenization,
the task of splitting up some sequence into distinct pieces,
where we call those pieces tokens.
Most commonly, this refers to something like word tokenization.
I have some sequence of text and I want to split it up
into all of the words that show up in that text.
But it might also come up in the context of something
like sentence tokenization.
I have a long sequence of text and I'd like to split it up
into sentences, for example.
And so how might word tokenization work, the task of splitting up
our sequence of characters into words?
Well, we've also already seen this idea.
We've seen that, in word tokenization just a moment ago, I
took an input sequence and I just called Python's split method on it, where
the split method took that sequence of words
and just separated it based on where the spaces showed up in that word.
And so if I had a sentence like, whatever remains, however improbable,
must be the truth, how would I tokenize this?
Well, the naive approach is just to say, anytime you see a space,
go ahead and split it up.
We're going to split up this particular string just by looking for spaces.
And what we get when we do that is a sentence like this--
whatever remains, however improbable, must be the truth.
But what you'll notice here is that, if we just split things
up in terms of where the spaces are, we end up keeping the punctuation around.
There's a comma after the word remains.
There's a comma after improbable, a period after truth.
And this poses a little bit of a challenge, when
we think about trying to tokenize things into individual words,
because if you're comparing words to each other, this word
truth with a period after it--
if you just string compare it, it's going
to be different from the word truth without a period after it.
And so this punctuation can sometimes pose a problem for us,
and so we might want some way of dealing with it-- either treating punctuation
as a separate token altogether or maybe removing that punctuation entirely
from our sequence as well.
So that might be something we want to do.
But there are other cases where it becomes a little bit less clear.
If I said something like, just before 9:00 o'clock,
Sherlock Holmes stepped briskly into the room,
well, this apostrophe after 9 o'clock--
after the O in 9 o'clock-- is that something we should remove?
Should be split based on that as well, and do O and clock?
There's some interesting questions there too.
And it gets even trickier if you begin to think about hyphenated words--
something like this, where we have a whole bunch of words
that are hyphenated and then you need to make a judgment call.
Is that a place where you're going to split things apart
into individual words, or are you going to consider frock-coat, and well-cut,
and pearl-grey to be individual words of their own?
And so those tend to pose challenges that we need to somehow deal with
and something we need to decide as we go about trying
to perform this kind of analysis.
Similar challenges arise when it comes to the world of sentence tokenization.
Imagine this sequence of sentences, for example.
If you take a look at this particular sequence of sentences,
you could probably imagine you could extract the sentences pretty readily.
Here is one sentence and here is a second sentence,
so we have two different sentences inside of this particular passage.
And the distinguishing feature seems to be the period--
that a period separates one sentence from another.
And maybe there are other types of punctuation
you might include here as well--
an exclamation point, for example, or a question mark.
But those are the types of punctuation that we know
tend to come at the end of sentences.
But it gets trickier again if you look at a sentence like this-- not just
sure talking to Sherlock, but instead of talking to Sherlock,
talking to Mr. Holmes.
Well now, we have a period at the end of Mr.
And so if you were just separating on periods,
you might imagine this would be a sentence,
and then just Holmes would be a sentence,
and then we'd have a third sentence down below.
Things do get a little bit trickier as you start
to imagine these sorts of situations.
And dialogue too starts to make this trickier as well--
that if you have these sorts of lines that are inside of something that--
he said, for example--
that he said this particular sequence of words
and then this particular sequence of words.
There are interesting challenges that arise there too,
in terms of how it is that we take the sentence
and split it up into individual sentences as well.
And these are just things that our algorithm needs to decide.
In practice, there usually some heuristics that we can use.
We know there are certain occurrences of periods,
like the period after Mr., or in other examples where
we know that is not the beginning of a new sentence,
and so we can encode those rules into our AI
to allow it to be able to do this tokenization the way
that we want it to.
So once we have these ability to tokenize a particular passage--
take the passage, split it up into individual words--
from there, we can begin to extract what the n-grams actually are.
So we can actually take a look at this by going
into a Python program that will serve the purpose of extracting
these n-grams.
And again, we can use NLTK, the Natural Language Toolkit, in order
to help us here.
So I'll go ahead and go into ngrams and we'll take a look at ngrams.py.
And what we have here is we are going to take
some corpus of text, just some sequence of documents,
and use all those documents and extract what the most popular n-grams happen
to be.
So in order to do so, we're going to go ahead and load data from a directory
that we specify in the command line argument.
We'll also take in a number n as a command line argument
as well, in terms of what our number should be,
in terms of how many sequences-- words we're going to look at in sequence.
Then we're going to go ahead and just count up all of the nltk.ngrams.
So we're going to look at all of the grams across this entire corpus
and save it inside this variable ngrams.
And then we're going to look at the most common ones
and go ahead and print them out.
And so in order to do so, I'm not only using NLTK--
I'm also using counter, which is built into Python as well, where I can just
count up, how many times do these various different grams appear?
So we'll go ahead and show that.
We'll go into ngrams, and I'll say something like python ngrams--
and let's just first look for the unigrams, sequences
of one word inside of a corpus.
And the corpus that I've prepared is I have
all of the-- or some of these stories from Sherlock Holmes
all here, where each one is just one of the Sherlock Holmes stories.
And so I have a whole bunch of text here inside of this corpus,
and I'll go ahead and provide that corpus as a command line argument.
And now what my program is going to do is
it's going to load all of the Sherlock Holmes stories into memory--
or all the ones that I've provided in this corpus at least--
and it's just going to look for the most popular unigrams,
the most popular sequences of one word.
And it seems the most popular one is just the word the used in 9,700 times;
followed by I, used 5,000 times; and, used about 5,000 times--
the kinds of words you might expect.
So now let's go ahead and check for bigrams, for example, ngrams 2, holmes.
All right, again, sequences of two words now that appear multiple times--
of the, in the, it was, to the, it is, I have-- so on and so forth.
These are the types of bigrams that happen
to come up quite often inside this corpus, the inside of the Sherlock
Holmes stories.
And it probably is true across other corpses as well,
but we could only find out if we actually tested it.
And now, just for good measure, let's try
one more-- maybe try three, looking now for trigrams that happen to show up.
And now we get it was the, one of the, I think that, out of the.
These are sequences of three words now that
happen to come up multiple times across this particular corpus.
So what are the potential use cases here?
Now we have some sort of data.
We have data about how often particular sequences of words
show up in this particular order, and using that,
we can begin to do some sort of predictions.
We might be able to say that, if you see the words that it was,
there's a reasonable chance the word that
comes after it should be the word a.
And if I see the words one of, it it's reasonable to imagine
that the next word might be the word the, for example,
because we have this data about trigrams, sequences of three words
and how often they come up.
And now, based on two words, you might be
able to predict what the third word happens to be.
And one model we can use for that is a model we've actually seen before.
It's the Markov model.
Recall again that the Markov model really
just refers to some sequence of events that happen one time
step after a one time step, where every unit has some ability
to predict what the next unit is going to be--
or maybe the past two units predict with the next unit is going to be,
or the past three predict with the next one is going to be.
And we can use a Markov model and apply it
to language for a very naive and simple approach
at trying to generate natural language, at getting our AI
to be able to speak English-like text.
And the way it's going to work is we're going to say something like, come up
with some probability distribution.
Given these two words, what is the probability
distribution over what the third word could possibly
be based on all the data?
If you see it was, what are the possible third words we might?
Have how often do they come up?
And using that information, we can try and construct
what we expect the third word to be.
And if you keep doing this, the effect is
that our Markov model can effectively start
to generate text-- can be able to generate text that
was not in the original corpus, but that sounds
kind of like the original corpus.
It's using the same sorts of rules that the original corpus was using.
So let's take a look at an example of that
as well, where here now, I have another corpus that I have here,
and it is the corpus of all of the works of William Shakespeare.
So I've got a whole bunch of stories from Shakespeare, and all of them
are just inside of this big text file.
And so what I might like to do is look at what all of the n-grams are--
maybe look at all the trigrams inside of shakespeare.txt--
and figure out, given two words, can I predict
what the third word is likely to be?
And then just keep repeating this process--
I have two words--
predict the third word; then, from the second and third, word
predict the fourth word; and from the third and fourth word,
predict the fifth word, ultimately generating random sentences that
sounds like Shakespeare, that are using similar patterns of words
that Shakespeare used, but that never actually showed up in Shakespeare
itself.
And so to do so, I'll show you generator.py,
which, again, is just going to read data from a particular file.
And I'm using a Python library called markovify, which is just
going to do this process for me.
So there are libraries out here that can just train on a bunch of text
and come up with a Markov model based on that text.
And I'm going to go ahead and just generate
five randomly generated sentences.
So we'll go ahead and go in to markov.
I'll run the generator on shakespeare.txt.
What we'll see is it's going to load that data, and then here's what we get.
We get five different sentences, and these
are sentences that never showed up in any Shakespeare play,
but that are designed to sound like Shakespeare,
that are designed to just take two words and predict,
given those two words, what would Shakespeare have been likely to choose
as the third word that follows it.
And you know, these sentences probably don't have any meaning.
It's not like the AI is trying to express any sort of underlying meaning
here.
It's just trying to understand, based on the sequence
of words, what is likely to come after it as a next word, for example.
And these are the types of sentences that it's able to come up with,
just generating.
And if you ran this multiple times, you would end up getting different results.
I could run this again and get an entirely different set
of five different sentences that also are
supposed to sound kind of like the way that Shakespeare's sentences sounded
as well.
And so that then was a look at how it is we
can use Markov models to be able to naively attempt generating language.
The language doesn't mean a whole lot right now.
You wouldn't want to use the system in its current form
to do something like machine translation,
because it wouldn't be able to encapsulate any meaning,
but we're starting to see now that our AI is getting a little bit better
at trying to speak our language, at trying
to be able to process natural language in some sort of meaningful way.
So we'll now take a look at a couple of other tasks
that we might want our AI to be able to perform.
And one such task is text categorization, which really is just
a classification problem.
And we've talked about classification problems already,
these problems where we would like to take some object
and categorize it into a number of different classes.
And so the way this comes up in text is anytime you have some sample of text
and you want to put it inside of a category, where I want to say something
like, given an email, does it belong in the inbox or does it belong in spam?
Which of these two categories does it belong in?
And you do that by looking at the text and being
able to do some sort of analysis on that text to be able to draw conclusions,
to be able to say that, given the words that show up in the email,
I think this is probably belonging in the inbox,
or I think it probably belongs in spam instead.
And you might imagine doing this for a number
of different types of classification problems of this sort.
So you might imagine that another common example of this type of idea
is something like sentiment analysis, where I want to analyze,
given a sample of text, does it have a positive sentiment
or does it have a negative sentiment?
And this might come up in the case of a product reviews on a website,
for example, or feedback on a website, where you have a whole bunch of data--
samples of text that are provided by users of a website--
and you want to be able to quickly analyze, are these reviews positive,
are the reviews negative, what is it that people
are saying, just to get a sense for what it is that people are saying,
to be able to categorize text into one of these two different categories.
So how might we approach this problem?
Well, let's take a look at some sample product reviews.
Here are some sample prep reviews that we might come up with.
My grandson loved it.
So much fun.
Product broke after a few days.
One of the best games I've played in a long time.
Kind of cheap and flimsy.
Not worth it.
Different product reviews that you might imagine seeing on Amazon, or eBay,
or some other website where people are selling products, for instance.
And we humans can pretty easily categorize these
into positive sentiment or negative sentiment.
We'd probably say that the first and the third one, those
are positive sentiment messages.
The second one and the fourth one, those are probably
negative sentiment messages.
But how could a computer do the same thing?
How could it try and take these reviews and assess, are they positive
or are they negative?
Well, ultimately, it depends upon the words
that happen to be in this particular-- these particular reviews-- inside
of these particular sentences.
For now we're going to ignore the structure
and how the words are related to each other,
and we're just going to focus on what the words actually are.
So there are probably some key words here, words like loved,
and fun, and best.
Those probably show up in more positive reviews, whereas words
like broke, and cheap, and flimsy--
well, those are words that probably are more
likely to come up inside of negative reviews, instead of positive reviews.
So one way to approach this sort of text analysis idea
is to say, let's, for now, ignore the structures of these sentences-- to say,
we're not going to care about how it is the words relate to each other.
We're not going to try and parse these sentences to construct
the grammatical structure like we saw a moment ago.
But we can probably just rely on the words that were actually
used-- rely on the fact that the positive reviews are
more likely to have words like best, and loved, and fun,
and that the negative reviews are more likely to have the negative words
that we've highlighted there as well.
And this sort of model-- this approach to trying to think about language--
is generally known as the bag of words model,
where we're going to model a sample of text not by caring about its structure,
but just by caring about the unordered collection of words that
show up inside of a sample-- that all we care about
is what words are in the text.
And we don't care about what the order of those words is.
We don't care about the structure of the words.
We don't care what noun goes with what adjective
or how things agree with each other.
We just care about the words.
And it turns out this approach tends to work
pretty well for doing classifications like positive sentiment
or negative sentiment.
And you could imagine doing this in a number of ways.
We've talked about different approaches to trying to solve classification style
problems, but when it comes to natural language,
one of the most popular approaches is that naive Bayes approach.
And this is one approach to trying to analyze the probability that something
is positive sentiment or negative sentiment,
or just trying to categorize it some text into possible categories.
And it doesn't just work for text-- it works for other types of ideas
as well-- but it is quite popular in the world
of analyzing text and natural language.
And the naive Bayes approach is based on Bayes' rule, which
you might recall back from when we talked about probability,
that the Bayes' rule looks like this--
that the probability of some event b, given a
can be expressed using this expression over here.
Probability of b given a is the probability of a given b multiplied
by the probability of b divided by the probability of a.
And we saw that this came about as a result of just the definition
of conditional independence and looking at what it means for two events
to happen together.
This was our formulation then of Bayes' rule, which
turned out to be quite helpful.
We were able to predict one event in terms of another
by flipping the order of those events inside of this probability calculation.
And it turns out this approach is going to be quite helpful--
and we'll see why in a moment--
for being able to do this sort of sentiment analysis,
because I want to say you know, what is the probability
that a message is positive, or what is the pop probability
that the message is negative?
And I'll go ahead and simplify this just using the emojis just
for simplicity-- probability of positive, probability of negative.
And that is what I would like to calculate,
but I'd like to calculate that given some information--
given information like here is a sample of text--
my grandson loved it.
And I would like to know not just what is the probability that any message is
positive, but what is the probability that the message is positive,
given my grandson loved it as the text of the sample?
So given this information that inside the sample are the words my grandson
loved it, what is the probability then that this is a positive message?
Well, according to the bag of words model, what we're going to do
is really ignore the ordering of the words--
not treat this as a single sentence that has some structure to it,
but just treat it as a whole bunch of different words.
We're going to say something like, what is the probability
that this is a positive message, given that the word my
was in the message, given that the word grandson was in the message,
given that the word loved within the message, and given the word it
was in the message?
The bag of words model here--
we're treating the entire simple sample as just a whole bunch
of different words.
And so this then is what I'd like to calculate, this probability--
given all those words, what is the probability
that this is a positive message?
And this is where we can now apply Bayes' rule.
This is really the probability of some b, given some a.
And that now is what I'd like to calculate.
So according to Bayes' rule, this whole expression is equal to--
well, it's the probability--
I switched the order of them--
it's the probability of all of these words,
given that it's a positive message, multiplied
by the probability that is the positive message divided
by the probability of all of those words.
So this then is just an application of Bayes' rule.
We've already seen where I want to express the probability of positive,
given the words, as related to somehow the probability of the words,
given that it's a positive message.
And it turns out that-- as you might recall, back
when we talked about probability, that this denominator is
going to be the same.
Regardless of whether we're looking at positive or negative messages,
the probability of these words doesn't change,
because we don't have a positive or negative down below.
So we can just say that, rather than just say
that this expression up here is equal to this expression down below,
it's really just proportional to just the numerator.
We can ignore the denominator for now.
Using the denominator would get us an exact probability.
But it turns out that what we'll really just do
is figure out what the probability is proportional to, and at the end,
we'll have to normalize the probability distribution-- make
sure the probability distribution ultimately sums up to the number 1.
So now I've been able to formulate this probability--
which is what I want to care about--
as proportional to multiplying these two things together-- probability of words,
given positive message, multiplied by the probability of positive message.
But again, if you think back to our probability rules,
we can calculate this really as just a joint probability of all of these
things happening-- that the probability of positive message multiplied
by the probability of these words, given the positive message--
well, that's just the joint probability of all of these things.
This is the same thing as the probability
that it's a positive message, and my isn't the sentence or in the message,
and grandson is in the sample, and loved is in the sample,
and it is in the sample.
So using that rule for the definition of joint probability,
I've been able to say that this entire expression is now
proportional to this sequence--
this joint probability of these words and this positive that's
in there as well.
And so now the interesting question is just how
to calculate that joint probability.
How do I figure out the probability that,
given some arbitrary message, that it is positive, and the word my is in there,
and the word grandson is in there, and the word loved is in there,
and the word it is in there?
Well, you'll recall that we can calculate a joint probability
by multiplying together all of these conditional probabilities.
If I want to know the probability of a, and b, and c,
I can calculate that as the probability of a times
the probability of b, given a, times the probability of c, given a and b.
I can just multiply these conditional probabilities together
in order to get the overall joint probability that I care about.
And we could do the same thing here.
I could say, let's multiply the probability
of positive by the probability of the word my showing up in the message,
given that it's positive, multiplied by the probability of grandson
showing up in the message, given that the word my is in there
and that it's positive, multiplied by the probability of loved,
given these three things, multiplied by the probability of it,
given these four things.
And that's going to end up being a fairly complex calculation to make,
one that we probably aren't going to have
a good way of knowing the answer to.
What is the probability that grandson is in the message, given
that it is positive and the word my is in the message?
That's not something we're really going to have a readily easy answer to,
and so this is where the naive part of naive Bayes comes about.
We're going to simplify this notion.
Rather than compute exactly what that probability distribution is,
we're going to assume that these words are
going to be effectively independent of each other,
if we know that it's already a positive message.
If it's a positive message, it doesn't change the probability
that the word grandson is in the message,
if I know that the word loved is in the message, for example.
And that might not necessarily be true in practice.
In the real world, it might not be the case
that these words are actually independent,
but we're going to assume it to simplify our model.
And it turns out that simplification still
lets us get pretty good results out of it as well.
And what we're going to assume is that the probability that all of these words
show up depend only on whether it's positive or negative.
I can still say that loved is more likely to come up
in a positive message than a negative message, which is probably true,
but we're also going to say that it's not going to change whether or not
loved is more likely or less likely to come up if I know that the word my is
in the message, for example.
And so those are the assumptions that we're going to make.
So while top expression is proportional to this bottom expression,
we're going to say it's naively proportional to this expression,
probability of being a positive message.
And then, for each of the words that show up in the sample,
I'm going to multiply what's the probability that my
is in the message, given that it's positive,
times the probability of grandson being in the message, given
that it's positive-- and then so on and so forth
for the other words that happen to be inside of the sample.
And it turns out that these are numbers that we can calculate.
The reason we've done all of this math is to get to this point,
to be able to calculate this probability of distribution that we care about,
given these terms that we can actually calculate.
And we can calculate then, given some data available to us.
And this is what a lot of natural language processing
is about these days.
It's about analyzing data.
If I give you a whole bunch of data with a whole bunch of reviews,
and I've labeled them as positive or negative,
then you can begin to calculate these particular terms.
I can calculate the probability that a message is positive just
by looking at my data and saying, how many
positive samples were there, and divide that by the number of total samples.
That is my probability that a message is positive.
What is the probability that the word loved is in the message, given
that it's positive?
Well, I can calculate that based on my data too.
Let me just look at how many positive samples have the word loved in it
and divide that by my total number of positive samples.
And that will give me an approximation for,
what is the probability that loved is going to show up inside of the review,
given that we know that the review is positive.
And so this then allows us to be able to calculate these probabilities.
So let's not actually do this calculation.
Let's calculate for the sentence, my grandson loved it.
Is it a positive or negative review?
How could we figure out those probabilities?
Well, again, this up here is the expression we're trying to calculate.
And I'll give you a hint the data that is available to us.
And the way to interpret this data in this case
is that, of all of the messages, 49% of them were positive and 51% of them
were negative.
Maybe online reviews tend to be a little bit more negative than they
are positive-- or at least based on this particular data
sample, that's what I have.
And then I have distributions for each of the various different words--
that, given that it's a positive message,
how many positive messages had the word in my in them?
It's about 30%.
And for negative messages, how many of those had the word my in them?
About 20%-- so it seems like the word my comes up more often in positive
messages-- at least slightly more often based on this analysis here.
Grandson, for example-- maybe that showed up
in 1% of all positive messages and 2% of all negative messages
had the word grandson in it.
The word loved showed up in 32% of all positive messages, 8%
of all negative messages, for example.
And then the word it up in 30% of positive messages,
40% of negative messages-- again, just arbitrary data here just for example,
but now we have data with which we can begin to calculate this expression.
So how do I calculate multiplying all these values together?
Well, it's just going to be multiplying probability
that it's positive times the probability of my, given positive,
times the probability of grandson, given positive--
so on and so forth for each of the other words.
And if you do that multiplication and multiply all of those values together,
you get this, 0.00014112.
By itself, this is not a meaningful number,
but it's going to be meaningful if you compared this expression--
the probability that it's positive times the probability of all of the words,
given that I know that the message is positive,
and compare it to the same thing, but for negative sentiment messages
instead.
I want to know the probability that it's a negative message
times the probability of all of these words,
given that it's a negative message.
And so how can I do that?
Well, to do that, you just multiply probability of negative times
all of these conditional probabilities.
And if I take those five values, multiply all of them together,
then what I get is this value for negative 0.00006528--
again, in isolation, not a particularly meaningful number.
What is meaningful is treating these two values as a probability distribution
and normalizing them, making it so that both of these values sum up to 1
the way of probability distribution should.
And we do so by adding these two up and then dividing each of these values
by their total in order to be able to normalize them.
And when we do that, when we normalize this probability distribution,
you end up getting something like this, positive 0.6837, negative 0.3163.
It seems like we've been able to conclude that we are about 68%
confident-- we think there's a probability of 0.68
that this message is a positive message-- my grandson loved it.
And why are we 68% confident?
Well, it seems like we're more confident than not because the word
loved showed up in 32% of positive messages,
but only 8% of negative messages.
So that was a pretty strong indicator.
And for the others, while it's true that the word
it showed up more often in negative messages,
it wasn't enough to offset that loved shows up
far more often in positive messages than negative messages.
And so this type of analysis is how we can apply naive Bayes.
We've just done this calculation.
And we end up getting not just a categorization of positive or negative,
but I get some sort of confidence level.
What do I think the probability is that it's positive?
And I can say I think it's positive with this particular probability.
And so naive Bayes can be quite powerful at trying to achieve this.
Using just this bag of words model, where all I'm doing
is looking at what words show up in the sample,
I'm able to draw these sorts of conclusions.
Now, one potential drawback-- something that you'll notice pretty quickly
if you start applying this room exactly as is--
is what happens depending on if 0's are inside this data somewhere.
Let's imagine, for example, this same sentence-- my grandson loved it--
but let's instead imagine that this value here, instead of being 0.01,
was 0, meaning inside of our data set, it has never
before happened that in a positive message the word grandson showed up.
And that's certainly possible.
If I have a pretty small data set, it's probably likely
that not all the messages are going to have the word grandson.
Maybe it is the case that no positive messages have ever
had the word grandson in it, at least in my data set.
But if it is the case that 2% of the negative messages
have still had the word grandson in it, then we
run into an interesting challenge.
And the challenge is this-- when I multiply all of the positive numbers
together and multiply all the negative numbers together to calculate these two
probabilities, what I end up getting is a positive value of 0.000.
I get pure 0's, because when I multiply all of these numbers
together-- when I multiply something by 0,
doesn't matter what the other numbers are-- the result is going to be 0.
And the same thing can be said of negative numbers as well.
So this then would seem to be a problem that, because grandson has never
showed up in any of the positive messages inside of our sample,
we're able to say-- we seem to be concluding that there is a 0%
chance that the message is positive.
And therefore, it must be negative, because the only cases where
we've seen the word grandson come up is inside of a negative message.
And in doing so, we've totally ignored all of the other probabilities
that a positive message is much more likely to have the word loved in it,
because we've multiplied by 0, which just
means none of the other probabilities can possibly matter at all.
So this then is a challenge that we need to deal with.
It means that we're likely not going to be
able to get the correct results if we just purely use this approach.
And it's for that reason there are a number of possible ways
we can try and make sure that we never multiply something by 0.
It's OK to multiply something by a small number,
because then it can still be counterbalanced
by other larger numbers, but multiplying by 0 means it's the end of the story.
You multiply a number by 0, and the output's
going to be 0, no matter how big any of the other numbers happen to be.
So one approach that's fairly common a naive Bayes is
this idea of additive smoothing, adding some value alpha to each of the values
in our distribution just to smooth the data little bit.
One such approach is called Laplace smoothing,
which basically just means adding one to each value in our distribution.
So if I have 100 samples and zero of them contain the word grandson,
well then I might say that, you know what?
Instead, let's pretend that I've had one additional sample where the word
grandson appeared and one additional sample where the word grandson didn't
appear.
So I'll say all right, now I have one 1 of 102--
so one sample that does have the word grandson out of 102 total.
I'm basically creating two samples that didn't exist before.
But in doing so, I've been able to smooth the distribution a little bit
to make sure that I never have to multiply anything by 0.
By pretending I've seen one more value in each category than I actually have,
this gets us that result of not having to worry
about multiplying a number by 0.
So this then is an approach that we can use in order
to try and apply naive Bayes, even in situations
where we're dealing with words that we might not necessarily have seen before.
And let's now take a look at how we could actually apply that in practice.
It turns out that NLTK, in addition to having the ability to extract
n-grams and tokenize things into words, also
has the ability to be able to apply naive Bayes on some samples of text,
for example.
And so let's go ahead and do that.
What I've done is, inside of sentiment, I've prepared a corpus of just
know reviews that I've generated, but you can imagine using real reviews.
I just have a couple of positive reviews-- it was great.
So much fun.
Would recommend.
My grandson loved it.
Those sorts of messages.
And then I have a whole bunch of negative reviews-- not worth it,
kind of cheap, really bad, didn't work the way we expected--
just one on each line.
A whole bunch of positive reviews and negative reviews.
And what I'd like to do now is analyze them somehow.
So here then is sentiment up high, and what we're going to do first
is extract all of the positive and negative sentences,
create a set of all of the words that were used across all of the messages,
and then we're going to go ahead and train NLTK's naive Bayes classifier
on all of this training data.
And with the training data effectively is is I
take all of the positive messages and give them the label positive, all
the negative messages and give them the label negative,
and then I'll go ahead and apply this classifier to it, where I'd say,
I would like to take all of this training data
and now have the ability to classify it as positive or negative.
I'll then take some input from the user.
They can just type in some sequence of words.
And then I would like to classify that sequence
as either positive or negative, and then I'll
go ahead and print out what the probabilities of each happened to be.
And there are some helper functions here that just organize things in the way
that NLTK is expecting them to be.
But the key idea here is that I'm taking the positive messages,
labeling them, taking the negative messages,
labeling them, putting them inside of a classifier,
and then now trying to classify some new text that comes about.
So let's go ahead and try it.
I'll go ahead and go into sentiment, and we'll run Python sentiment,
passing in as input that corpus that contains
all of the positive and negative messages--
because depending on the corpus, that's going to affect the probabilities.
The effectiveness of our ability to classify
is entirely dependent on how good our data is, and how much data we have,
and how well they happen to be labeled.
So now I can try something and say--
let's try a review like, this was great--
just some review that I might leave.
And it seems that, all right, there is a 96% chance it estimates
that this was a positive message--
4% chance that it was a negative, likely because the word great
shows up inside of the positive messages,
but doesn't show up inside of the negative messages.
And that might be something that our AI is able to capitalize on.
And really, what it's going to look for are the differentiating words--
that if the probability of words like this and was
and is pretty similar between positive and negative words,
then the naive Bayes classifier isn't going
to end up using those values as having some sort of importance
in the algorithm.
Because if they're the same on both sides,
you multiply that value for both positive and negative,
you end up getting about the same thing.
What ultimately makes the difference in naive Bayes
is when you multiply by value that's much bigger for one category
than for another category-- when one word like great
is much more likely to show up in one type of message
than another type of message.
And that's one of the nice things about naive Bayes
is that, without me telling it, that great
is more important to care about than this or was.
Naive Bayes can figure that out based on the data.
It can figure out that this shows up about the same amount of time
between the two, but great, that is a discriminator,
a word that can be different between the two types of messages.
So I could try it again--
type in a sentence like, lots of fun, for example.
This one it's a little less sure about--
62% chance that it's positive, 37% chance that it's negative-- maybe
because there aren't as clear discriminators
or differentiators inside of this data.
I'll try one more--
say kind of overpriced.
And all right, now 95%, 96% sure that this
is a negative sentiment-- likely because of the word
overpriced, because it's shown up in a negative sentiment expression
before, and therefore, it thinks, you know what, this is probably
going to be a negative sentence.
And so naive Bayes has now given us the ability to classify text.
Given enough training data, given enough examples,
we can train our AI to be able to look at natural language, human words,
figure out which words are likely to show up
in positive as opposed to negative sentiment messages,
and categorize them accordingly.
And you could imagine doing the same thing
anytime you want to take text and group it into categories.
If I want to take an email and categorize as email--
as a good email or as a spam email, you could apply a similar idea.
Try and look for the discriminating words,
the words that make it more likely to be a spam email or not,
and just train a naive Bayes classifier to be able to figure out
what that distribution is and to be able to figure out how to categorize
an email as good or as spam.
Now, of course, it's not going to be able to give us a definitive answer.
It gives us a probability distribution, something like 63%
positive, 37% negative.
And that might be why our spam filters and our emails sometimes make mistakes,
sometimes think that a good email is actually spam or vice
versa, because ultimately, the best that it can do
is calculate a probability distribution.
If natural language is ambiguous, we can usually
just deal in the world of probabilities to try and get
an answer that is reasonably good, even if we aren't able to guarantee for sure
that it is the number that we actually expect for it to be.
That then was a look at how we can begin to take some text
and to be able to analyze the text and group it into some sorts of categories.
But ultimately, in addition just being able to analyze text and categorize it,
we'd like to be able to figure out information about the text,
get it some sort of meaning out of the text as well.
And this starts to get us in the world of information,
of being able to try and take data in the form of text
and retrieve information from it.
So one type of problem is known as information retrieval, or IR,
which is the task of finding relevant documents in response to a query.
So this is something like you type in a query into a search engine,
like Google, or you're typing in something
into some system that's going to look for-- inside of a library catalog,
for example-- that's going to look for responses to a query.
I want to look for documents that are about the US constitution or something,
and I would like to get a whole bunch of documents
that match that query back to me.
But you might imagine that what I really want to be able to do
is, in order to solve this task effectively,
I need to be able to take documents and figure out,
what are those documents about?
I want to be able to say what is it that these particular documents are
about-- what of the topics of those documents--
so that I can then more effectively be able to retrieve information
from those particular documents.
And this refers to a set of tasks generally known as topic modeling,
where I'd like to discover what the topics are for a set of documents.
And this is something that humans could do.
A human could read a document and tell you, all right,
here's what this document is about, and give maybe
a couple of topics for who are the important people in this document, what
are the important objects in the document-- can probably tell you
that kind of thing.
But we'd like for our AI to be able to do the same thing.
Given some document, can you tell me what the important words
in this document are?
What are the words that set this document apart
that I might care about if I'm looking at documents
based on keywords, for example?
And so one instinctive idea-- an intuitive idea that probably makes
sense--
is let's just use term frequency.
Term frequency is just defined as the number of times
a particular term appears in a document.
If I have a document with 100 words and one particular word shows up 10 times,
it has a term frequency of 10.
It shows up pretty often.
Maybe that's going to be an important word.
And sometimes, you'll also see this framed
as a proportion of the total number of words, so 10 words out of 100.
Maybe it has a term frequency of 0.1, meaning 10% of all of the words
are this particular word that I care about.
Ultimately, that doesn't change relatively
how important they are for any one particular document,
but they're the same idea.
The idea is look for words that show up more frequently, because those
are more likely to be the important words inside of a corpus of documents.
And so let's go ahead and give that a try.
Let's say I wanted to find out what the Sherlock Holmes stories are about.
I have a whole bunch of Sherlock Holmes stories
and I want to know, in general, what are they about?
What are the important characters?
What are the important objects?
What are the important parts of the story, just in terms of words?
And I'd like for the AI to be able to figure that out on its own,
and we'll do so by looking at term frequency--
by looking at, what are the words that show up the most often?
So we'll go ahead, and I'll go ahead and go in to the tfidf directory.
You'll see why it's called that in a moment.
But let's first open up tf0.py, which is going to calculate the top 10 term
frequencies-- or maybe top five term frequencies
for a corpus of documents, a whole bunch of documents
where each document is just a story from Sherlock Holmes.
We're going to load all the data into our corpus
and we're going to figure out, what are all of the words that
show up inside of that corpus?
And we're going to basically just assemble all
of the number of the term frequencies.
We're going to calculate, how often do each of these terms
appear inside of the document?
And we'll print out the top five.
And so there are some data structures involved that you
can take a look at if you'd like to.
The exact code is not so important, but it is the idea of what we're doing.
We're taking each of these documents and first sorting them.
We're saying, take all the words that show up
and sort them by how often each word shows up.
And let's go ahead and just, for each document, save the top five
terms that happen to show up in each of those documents.
So again, some helper functions you can take a look at if you're interested.
But the key idea here is that all we're going to do
is run to tf0 on the Sherlock Holmes stories.
And what I'm hoping to get out of this process is I am hoping to figure out,
what are the important words in Sherlock Holmes, for example?
So we'll go ahead and run this and see what we get.
And it's loading the data.
And here's what we get.
For this particular story, the important words are the, and and, and I,
and to, and of.
Those are the words that show up more frequently.
In this particular story, it's the, and and, and I, and a, and of.
This is not particularly useful to us.
We're using term frequencies.
We're looking at what words show up the most frequently in each
of these various different documents, but what we get naturally
are just the words that show up a lot in English.
The word the, and of, and happen to show up a lot in English,
and therefore, they happen to show up a lot in each
of these various different documents.
This is not a particularly useful metric for us
to be able to analyze what words are important,
because these words are just part of the grammatical structure of English.
And it turns out we can categorize words into a couple of different categories.
These words happen to be known as what we might call function words, words
that have little meaning on their own, but that
are used to grammatically connect different parts of a sentence.
These are words like am, and by, and do, and is, and which,
and with, and yet-- words that, on their own, what do they mean?
It's hard to say.
They get their meaning from how they connect
different parts of the sentence.
And these function words are what we might call a closed class of words
in a language like English.
There's really just some fixed list of function words,
and they don't change very often.
There's just some list of words that are commonly
used to connect other grammatical structures in the language.
And that's in contrast with what we might call content words, words
that carry meaning independently-- words like algorithm,
category, computer, words that actually have some sort of meaning.
And these are usually the words that we care about.
These are the words where we want to figure out,
what are the important words in our document?
We probably care about the content words more
than we care about the function words.
And so one strategy we could apply is just ignore all of the function words.
So here in tf1.py, I've done the same exact thing,
except I'm going to load a whole bunch of words from a function_words.txt
file, inside of which are just a whole bunch of function words in alphabetical
order.
These are just a whole bunch of function words
that are just words that are used to connect other words in English,
and someone has just compiled this particular list.
And these are the words that I just want to ignore.
If any of these words-- let's just ignore it as one of the top terms,
because these are not words that I probably care about
if I want to analyze what the important terms inside of a document
happen to be.
So in tfidf1, we were ultimately doing is,
if the word is in my set of function words,
I'm just going to skip over it, just ignore any of the function words
by continuing on to the next word and then
just calculating the frequencies for those words instead.
So I'm going to pretend the function words aren't there,
and now maybe I can get a better sense for what
terms are important in each of the various different Sherlock Holmes
stories.
So now let's run tf1 on the Sherlock Holmes corpus and see what we get now.
And let's look at, what is the most important term in each of the stories?
Well, it seems like, for each of the stories,
the most important word is Holmes.
I guess that's what we would expect.
They're all Sherlock Holmes stories.
And Holmes is not a function in Word.
It's not the, or a, or an, so it wasn't ignored.
But Holmes and man--
these are probably not what I mean when I say, what are the important words?
Even though Holmes does show up the most often
it's not giving me a whole lot of information here
about what each of the different Sherlock Holmes stories
are actually about.
And the reason why is because Sherlock Holmes shows up in all the stories,
and so it's not meaningful for me to say that this story is about Sherlock
Holmes I want to try and figure out the different topics
across the corpus of documents.
What I really want to know is, what words show up
in this document that show up less frequently in the other documents,
for example?
And so to get at that idea, we're going to introduce the notion
of inverse document frequency.
Inverse document frequency is a measure of how common,
or rare, a word happens to be across an entire corpus of words.
And mathematically, it's usually calculated like this--
as the logarithm of the total number of documents
divided by the number of documents containing the word.
So if a word like Holmes shows up in all of the documents,
well, then total documents is how many documents there
are a number of documents containing Holmes is going to be the same number.
So when you divide these two together, you'll get 1, and the logarithm of one
is just 0.
And so what we get is, if Holmes shows up in all of the documents,
it has an inverse document frequency of 0.
And you can think now of inverse document frequency
as a measure of how rare is the word that
shows up in this particular document that if a word doesn't show up
across many documents at all this number is going to be much higher.
And this then gets us that a model known as tf-idf,
which is a method for ranking what words are important in the document
by multiplying these two ideas together.
Multiply term frequency, or TF, by inverse document frequency, or IDF,
where the idea here now is that how important a word is
depends on two things.
It depends on how often it shows up in the document using
the heuristic that, if a word shows up more often,
it's probably more important.
And we multiply that by inverse document frequency IDF,
because if the word is rarer, but it shows up in the document,
it's probably more important than if the word shows up
across most or all of the documents, because then it's probably
a less important factor in what the different topics
across the different documents in the corpus happen to be.
And so now let's go ahead and apply this algorithm on the Sherlock Holmes
corpus.
And here's tfidf.
Now what I'm doing is, for each of the documents,
for each word, I'm calculating its TF score,
term frequency, multiplied by the inverse document
frequency of that word-- not just looking at the single volume,
but multiplying these two values together
in order to compute the overall values.
And now, if I run tfidf on the Holmes corpus,
this is going to try and get us a better approximation for what's
important in each of the stories.
And it seems like it's trying to extract here
probably like the names of characters that
happen to be important in the story-- characters that show up
in this story that don't show up in the other story--
and prioritizing the more important characters that
happen to show up more often.
And so this then might be a better analysis of what types of topics
are more or less important.
I also have another corpus, which is a corpus of all of the Federalist
Papers from American history.
If I go ahead and run tfidf on the Federalist Papers,
we can begin to see what the important words in each
of the various different Federalist Papers happen to be--
that in Federalist Paper Number 61, seems like it's a lot about elections.
In Federalist Papers 66, but the Senate and impeachments.
You can start to extract what the important terms and what
the important words are just by looking at what things show up across--
and don't show up across many of the documents,
but show up frequently enough in certain of the documents.
And so this can be a helpful tool for trying
to figure out this kind of topic modeling,
figuring out what it is that a particular document happens
to be about.
And so this then is starting to get us into this world of semantics,
what it is that things actually mean when we're talking about language.
Now, we're not going to think about the bag of words,
where we just say, treat a sample of text as just a whole bunch of words.
And we don't care about the order.
Now, when we get into the world of semantics,
we really do start to care about what it is that these words actually mean,
how it is these words relate to each other,
and in particular, how we can extract information out of that text.
Information extraction is somehow extracting knowledge
from our documents-- figuring out, given a whole bunch of text,
can we automate the process of having an AI, look at those documents,
and get out what the useful or relevant knowledge inside those documents
happens to be?
So let's take a look at an example.
I'll give you two samples from news articles.
Here up above is a sample of a news article from the Harvard Business
Review that was about Facebook.
Down below is an example of a Business Insider article from 2018
that was about Amazon.
And there's some information here that we might
want an AI to be able to extract--
information, knowledge about these companies
that we might want to extract.
And in particular, what I might want to extract is--
let's say I want to know data about when companies were founded--
that I wanted to know that Facebook was founded in 2004,
Amazon founded in 1994--
that that is important information that I happen to care about.
Well, how do we extract that information from the text?
What is my way of being able to understand this text
and figure out, all right, Facebook was founded in 2004?
Well, what I can look for are templates or patterns, things
that happened to show up across multiple different documents that give me
some sense for what this knowledge happens to mean.
And what we'll notice is a common pattern
between both of these passages, which is this phrasing here.
When Facebook was founded in 2004, comma--
and then down below, when Amazon was founded in 1994, comma.
And those two templates end up giving us a mechanism for trying to extract
information-- that this notion, when company was founded in year comma,
this can tell us something about when a company was founded,
because if we set our AI loose on the web,
let look at a whole bunch of papers or a whole bunch of articles,
and it finds this pattern--
when blank was founded in blank, comma--
well, then our AI can pretty reasonably conclude
that there's a good chance that this is going to be like some company,
and this is going to be like the year that company was founded, for example--
might not be perfect, but at least it's a good heuristic.
And so you might imagine that, if you wanted
to train and AI to be able to look for information,
you might give the AI templates like this--
not only give it a template like when company blank was founded in blank,
but give it like, the book blank was written by blank, for example.
Just give it some templates where it can search the web,
search a whole big corpus of documents, looking for templates that match that,
and if it finds that, then it's able to figure out,
all right, here's the company and here's the year.
But of course, that requires us to write these templates.
It requires us to figure out, what is the structure of this information
likely going to look like?
And it might be difficult to know.
The different websites are, of course, going to do this differently.
This type of method isn't going to be able to extract all of the information,
because if the words are slightly in a different order,
it won't match on that particular template.
But one thing we can do is, rather than give our AI the template,
we can give AI the data.
We can tell the AI, Facebook was founded in 2004 and Amazon was founded in 1994,
and just tell the AI those two pieces of information,
and then set the AI loose on the web.
And now the ideas that the AI can begin to look for, where do Facebook in 2004
show up together, where do Amazon in 1994 show up together,
and it can discover these templates for itself.
It can discover that this kind of phrasing--
when blank was founded in blank--
tends to relate Facebook to 2004, and it released Amazon to 1994,
so maybe it will hold the same relation for others as well.
And this ends up being-- this automated template
generation ends up being quite powerful, and we'll go ahead
and take a look at that now as well.
What I have here inside of templates directory
is a file called companies.csv, and this is all of the data
that I am going to give to my AI.
I'm going to give it the pair Amazon, 1994 and Facebook, 2004.
And what I'm going to tell my AI to do is
search a corpus of documents for other data--
these pairs like this-- other relationships.
I'm not telling AI that this is a company and the date
that it was founded.
I'm just giving it Amazon, 1994 and Facebook, 2004
and letting the AI do the rest.
And what the AI is going to do is it's going to look through my corpus--
here's my corpus of documents--
and it's going to find, like inside of Business Insider,
that we have sentences like, back when Amazon was founded in 2004, comma--
and that kind of phrasing is going to be similar to this Harvard Business Review
story that has a sentence like, when Facebook was founded in 2004--
and it's going to look across a number of other documents
for similar types of patterns to be able to extract that kind of information.
And what it will do is, if I go ahead and run,
I'll go ahead and go into templates.
So I'll say python search.py.
I'm going to look for the data like the data and companies.csv
inside of the company's directory, which contains a whole bunch of news articles
that I've curated in advance.
And here's what I get--
Google 1998, Apple 1976, Microsoft 1975--
so on and so forth--
Walmart 1962, for example.
These are all of the pieces of data that happened
to match that same template that we were able to find before.
And how was it able to find this?
Well, it's probably because, if we look at the Forbes article,
for example, that it has a phrase in it like, when Walmart was founded in 1962,
comma-- that it's able to identify these sorts of patterns
and extract information from them.
Now, granted, I have curated all these stories in advance
in order to make sure that there is data that it's able to match on.
And in practice, it's not always going to be in this exact format
when you're seeing a company related to the year in which it was founded,
but if you give the AI access to enough data-- like all of the data of text
on the internet-- and just have the AI crawl the internet looking
for information, it can very reliably, or with some probability,
try and extract information using these sorts of templates
and be able to generate interesting sorts of knowledge.
And the more knowledge it learns, the more new templates
it's able to construct, looking for constructions that
show up in other locations as well.
So let's take a look at another example.
And then I'll here show you presidents.csv,
where I have two presidents and their inauguration date--
so George Washington 1789, Barack Obama 2009 for example.
And I also am going to give to our AI a corpus that
just contains a single document, which is the Wikipedia
article for the list of presidents of the United States, for example--
just information about presidents.
And I'd like to extract from this raw HTML document on a web page information
about the president.
So I can say search in presidents.csv.
And what I get is a whole bunch of data about presidents
and what year they were likely inaugurated and by looking
for patterns that matched--
Barack Obama 2009, for example--
looking for these sorts of patterns that happened
to give us some clues as to what it is that a story happens to be about.
So here's another example.
If I open up inside the olympics, here is a scraped version
of the Olympic home page that has information
about various different Olympics.
And maybe I want to extract Olympic locations and years
from this particular page.
Well, the way I can do that is using the exact same algorithm.
I'm just saying, all right, here are two Olympics and where they were located--
so 2012 London, for example.
Let me go ahead and just run this process,
Python search, on olympics.csv, look at all the Olympic data set,
and here I get some information back.
Now, this information-- not totally perfect.
There are a couple of examples that are obviously not
quite right, because my template might have been a little bit too general.
Maybe it was looking for a broad category of things
and certain strange things happened to capture on that particular template.
So you could imagine adding rules to try and make this process more intelligent,
making sure the thing on the left is just a year, for example--
for instance, and doing other sorts of analysis.
But purely just based on some data, we are
able to extract some interesting information using some algorithms.
And all search.py is really doing here is it is taking my corpus of data,
finding templates that match it--
here, I'm filtering down to just the top two templates that happen to match--
and then using those templates to extract results from the data
that I have access to, being able to look for all of the information
that I care about.
And that's ultimately what's going to help me,
to print out those results to figure out what the matches happen to be.
And so information extraction is another powerful tool
when it comes to trying to extract information.
But of course, it only works in very limited contexts.
It only works when I'm able will find templates that look exactly
like this in order to come up with some sort of match that
is able to connect this to some pair of data,
that this company was founded in this year.
What I might want to do, as we start to think about the semantics of words,
is to begin to imagine some way of coming up with definitions
for all words, being able to relate all of the words in a dictionary
to each other, because that's ultimately what's going to be necessary if we want
our AI to be able to communicate.
We need some representation of what it is that words mean.
And one approach of doing this, this famous data set called WordNet.
And what WordNet is is it's a human-curated--
researchers have curated together a whole bunch of words,
their definitions, their various different senses--
because the word might have multiple different meanings--
and also how those words relate to one another.
And so what we mean by this is--
I can show you an example of WordNet.
WordNet comes built into NLTK.
Using NLTK, you can download and access WordNet.
So let me go into WordNet, and go ahead and run WordNet,
and extract information about a word-- a word like city, for example.
Go ahead and press Return.
And here is the information that I get back about a city.
It turns out that city has three different senses, three
different meanings, according to WordNet.
And it's really just kind of like a dictionary, where
each sense is associated with its meaning-- just some definition
provided by human.
And then it's also got categories, for example, that a word belongs to--
that a city is a type of municipality, a city
is a type of administrative district.
And that allows me to relate words to other words.
So one of the powers of WordNet is the ability to take one word
and connect it to other related words.
If I do another example, let me try the word house, for instance.
I'll type in the word house and see what I get back.
Well, all right, the house is a kind of building.
The house is somehow related to a family unit.
And so you might imagine trying to come up
with these various different ways of describing a house.
It is a building.
It is a dwelling.
And researchers have just curated these relationships
between these various different words to say that a house is a type of building,
that a house is a type of dwelling, for example.
But this type of approach, while certainly
helpful for being able to relate words to one another,
doesn't scale particularly well.
As you start to think about language changing,
as you start to think about all the various different relationships
that words might have to one another, this challenge of word representation
ends up being difficult. What we've done is just
defined a word as just a sentence that explains what it is that that word is,
but what we really would like is some way
to represent the meaning of a word in a way
that our AI is going to be able to do something useful with it.
Anytime we want our AI to be able to look at texts
and really understand what that text means,
to relate text and words to similar words
and understand the relationship between words,
we'd like some way that a computer can represent this information.
And what we've seen all throughout the course
multiple times now is the idea that, when
we want our AI to represent something, it
can be helpful to have the AI represent it using numbers--
that we've seen that we can represent utilities in a game,
like winning, or losing, or drawing, as a number--
1, negative 1, or a 0.
We've seen other ways that we can take data and turn it
into a vector of features, where we just have
a whole bunch of numbers that represent some particular piece of data.
And if we ever want to past words into a neural network,
for instance, to be able to say, given some word,
translate this sentence into another sentence,
or to be able to do interesting classifications with neural networks
on individual words, we need some representation of words
just in terms of vectors--
way to represent words, just by using individual numbers
to define the meaning of a word.
So how do we do that?
How do we take words and turn them into vectors
that we can use to represent the meaning of those words?
Well, one way is to do this.
If I have four words that I want to encode, like he wrote a book,
I can just say, let's let the word he be this vector--
1, 0, 0, 0.
Wrote will be 0, 1, 0, 0.
A will be 0, 0, 1, 0.
Book will be 0, 0, 0, 1.
Effectively, what I have here is what's known as a one-hot representation
or a one-hot encoding, which is a representation of meaning,
where meaning is a vector that has a single 1 in it and the rest are 0's.
The location of the 1 tells me the meaning of the word--
that 1 in the first position, that means here--
1 in the second position, that means wrote.
And every word in the dictionary is going
to be assigned to some representation like this, where we just
assign one place in the vector that has a 1 for the word
and 0 for the other words.
And now I have representations of words that
are different for a whole bunch of different words.
This is this one-hot representation.
So what are the drawbacks of this?
Why is this not necessarily a great approach?
Well, here, I am only creating enough vectors
to represent four words in a dictionary.
If you imagine a dictionary with 50,000 words that I might want to represent,
now these vectors get enormously long.
These are 50,000 dimensional vectors to represent
a vocabulary of 50,000 words-- that he is 1 followed by all these.
Wrote has a whole bunch of 0's in it.
That's not a particularly tractable way of trying to represent numbers,
if I'm going to have to deal with vectors of length 50,000.
Another problem-- a subtler problem--
is that ideally, I'd like for these vectors
to somehow represent meaning in a way that I can extract
useful information out of-- that if I have the sentence he wrote a book
and he authored a novel, well, wrote and authored are going to be two
totally different vectors.
And book and novel are going to be two totally different vectors inside
of my vector space that have nothing to do with each other.
The one is just located in a different position.
And really, what I would like to have happen
is for wrote and authored to have vectors
that are similar to one another, and for book and novel
to have vector representations that are similar to one another,
because they are words that have similar meanings.
Because their meanings are similar, ideally, I'd like for--
when I put them in vector form and use a vector to represent meanings,
I would like for those vectors to be similar to one another as well.
So rather than this one-hot representation,
where we represent a word's meaning by just giving it a vector that is one
in a particular location, what we're going to do--
which is a bit of a strange thing the first time you see it--
is what we're going to call a distributed representation.
We are going to represent the meaning of a word as just
a whole bunch of different values-- not just a single 1 and the rest 0's,
but a whole bunch of values.
So for example, in he wrote a book, he might just be a big vector.
Maybe it's 50 dimensions, maybe it's 100, dimensions but certainly less
than like tens of thousands, where each value is just some number--
and same thing for wrote, and a, and book.
And the idea now is that, using these vector representations,
I'd hope that wrote and authored have vector representations that
are pretty close to one another.
Their distance is not too far apart-- and same with the vector
representations for book and novel.
So this is going to be the goal of a lot of what statistical machine learning
approaches to natural language processing
is about is using these vector representations of words.
But how on earth do we define a word as just a whole bunch
of these sequences of numbers?
What does it even mean to talk about the meaning of a word?
The famous quote that answers this question
is from a British linguist in the 1950s, JR Firth, who said, "You shall
know a word by the company it keeps."
And what we mean by that is the idea that we
can define a word in terms of the words that show up around it, that we can get
at the meaning of a word based on the context in which that word happens
to appear.
That if I have a sentence like this, four words in sequence--
for blank he ate--
what goes in the blank?
Well, you might imagine that, in English,
the types of words that might fill in the blank are words like breakfast,
or lunch, or dinner.
These are the kinds of words that fill in that blank.
And so if we want to define, what does lunch or dinner mean,
we can define it in terms of what words happened
to show up around it-- that if a word shows up
in a particular context and another word happens to show up
in very similar context, then those two words are probably
related to each other.
They probably have a similar meaning to one another.
And this then is the foundational idea of an algorithm
known as word2vec, which is a model for generating word vectors.
You give word2vec a corpus of documents, just a whole bunch of texts,
and what word to that will produce is it will produce vectors for each word.
And there a number of ways that it can do this.
One common way is through what's known as the skip-gram architecture, which
basically uses a neural network to predict context words,
given a target word-- so given a word like lunch,
use a neural network to try and predict, given the word lunch, what
words are going to show up around it.
And so the way we might represent this is
with a big neural network like this, where
we have one input cell for every word.
Every word gets one node inside this neural network.
And the goal is to use this neural network to predict,
given a target word, a context word.
Given a word like lunch, can I predict the probabilities of other words,
showing up in a context of one word away or two words away, for instance,
in some sort of window of context?
And if you just give the AI, this neural network, a whole bunch of data of words
and what words show up in context, you can train a neural network
to do this calculation, to be able to predict, given a target word--
can I predict what those context words ultimately should be?
And it will do so using the same methods we've
talked about-- back propagating the error from the context word
back through this neural network.
And what you get is, if we use the single layer--
just a signal layer of hidden nodes--
what I get is, for every single one of these words, I get--
from this word, for example, I get five edges, each of which
has a weight to each of these five hidden nodes.
In other words, I get five numbers that effectively
are going to represent this particular target word here.
And the number of hidden nodes I choose in this middle layer here--
I can pick that.
Maybe I'll choose to have 50 hidden nodes or 100 hidden nodes.
And then, for each of these target words,
I'll have 50 different values or 100 different values,
and those values we can effectively treat as the vector
numerical representation of that word.
And the general idea here is that, if words are similar,
two words show up in similar contexts-- meaning, using the same target words,
I'd like to predict similar contexts words--
well, then these vectors and these values I choose in these vectors
here-- these numerical values for the weight of these edges
are probably going to be similar, because for two different words that
show up in similar contexts, I would like
for these values that are calculated to ultimately
be very similar to one another.
And so ultimately, the high-level way you can picture this
is that what this word2vec training method is
going to do is, given a whole bunch of words, were initially,
recall, we initialize these weights randomly and just pick
random weights that we choose.
Over time, as we train the neural network,
we're going to adjust these weights, adjust the vector representations
of each of these words so that gradually,
words that show up in similar contexts grow closer to one another,
and words that show up in different contexts
get farther away from one another.
And as a result, hopefully I get vector representations
of words like breakfast, and lunch, and dinner that are similar to one another,
and then words like book, and memoir, and novel
are also going to be similar to one another as well.
So using this algorithm, we're able to take a corpus of data
and just train our computer, train this neural network to be able to figure out
what vector, what sequence of numbers is going
to represent each of these words-- which is, again, a bit of a strange concept
to think about representing a word just as a whole bunch of numbers.
But we'll see in a moment just how powerful this really can be.
So we'll go ahead and go into vectors, and what I have inside a vectors.py--
which I'll open up now--
is I'm opening up words.txt, which is a pretrained model that just--
I've already run word2vec and it's already given me
a whole bunch of vectors for each of these possible words.
And I'm just going to take like 50,000 of them
and go ahead and save their vectors inside of a dictionary called words.
And then I've also defined some functions called distance,
closest_word, so it'll get me what are the closest words to a particular word,
and then closest_word, that just gets me the one closest word, for example.
And so now let me try doing this.
Let me open up the Python interpreter and say something like,
from vectors import star--
just import everything from vectors.
And now let's take a look at the meanings of some words.
Let me look at the word city, for example.
And here is a big array that is the vector representation of the words
city.
And this doesn't mean anything, in terms of what these numbers exactly are,
but this is how my computer is representing
the meaning of the word city.
We can do a different word, like words house,
and here then is the vector representation of the word house,
for example-- just a whole bunch of numbers.
And this is encoding somehow the meaning of the word house.
And how do I get at that idea?
Well, one way to measure how good this is is by looking at,
what is the distance between various different words?
There a number of ways you can define distance.
In context of vectors, one common way is what's
known as the cosine distance that has to do with measuring
the angle between vectors.
But in short, it's just measuring, how far apart
are these two vectors from each other?
So if I take a word like the word book, how far away for is it from itself--
how far away is the word book from book--
well, that's zero.
The word book is zero distance away from itself.
But let's see how far away word book is from a word like breakfast,
where we're going to say one is very far away, zero is not far away.
All right, book is about 0.64 away from breakfast.
They seem to be pretty far apart.
But let's now try and calculate the distance from words book
to words novel, for example.
Now, those two words are closer to each other--
0.34.
The vector representation of the word book
is closer to the vector representation of the word novel
than it is to the vector representation of the word breakfast.
And I can do the same thing and, say, compare breakfast to lunch,
for example.
And those two words are even closer together.
They have an even more similar relationship
between one word and another.
So now it seems we have some representation of words,
representing a word using vectors, that allows us to be able to say something
like words that are similar to each other
ultimately have a smaller distance that happens to be between them.
And this turns out to be incredibly powerful to be
able to represent the meaning of words in terms of their relationships
to other words as well.
I can tell you as well--
I have a function called closest words that
basically just takes a whole bunch of words
and gets all the closest words to it.
So let me get the closest words to book, for example,
and maybe get the 10 closest words.
We'll limit ourselves to 10.
And right.
Book is obviously closest to itself-- the word book--
but is also closely related to books, and essay, and memoir, and essays,
and novella, anthology.
And why are these words that it was able to compute are close to it?
Well, because based on the corpus of information
that this algorithm was trained on, the vectors that arose
arose based on what words show up in a similar context--
that the word book shows up in a similar context, similar other words to words
like memoir and essays, for example.
And if I do something like--
let me get the closest words to city--
you end up getting city, town, township, village.
These are words that happen to show up in a similar context to the word city.
Now, where things get really interesting is that, because these are vectors,
we can do mathematics with them.
We can calculate the relationships between various different words.
So I can say something like, all right, what if I had man and king?
These are two different vectors, and this is a famous example
that comes out of word2vec.
I can take these two vectors and just subtract them from each other.
This line here, the distance here, is another vector
that represents like king minus man.
Now, what does it mean to take a word and subtract another word?
Normally, that doesn't make sense.
In the world of vectors, though, you can take some vector sum
sequence of numbers, subtract some other sequence of numbers,
and get a new vector, get a new sequence of numbers.
And what this new sequence of numbers is effectively going to do
is it is going to tell me, what do I need to do to get from man to king?
What is the relationship then between these two words?
And this is some vector representation of what makes--
takes us from man to king.
And we can then take this value and add it to another vector.
You might imagine that the word woman, for example,
is another vector that exists somewhere inside of this space,
somewhere inside of this vector space.
And what might happen if I took this same idea, king
minus man-- took that same vector and just added it to woman?
What will we find around here?
It's an interesting question we might ask,
and we can answer it very easily, because I have vector representations
of all of these things.
Let's go back here.
Let me look at the representation of the word man.
Here's the vector representation of men.
Let's look at the representation of the word king.
Here's the representation of the word king.
And I can subtract these two.
What is the vector representation of king minus man?
It's this array right here--
whole bunch of values.
So king minus man now represents the relationship between king and man
in some sort of numerical vector format.
So what happens then if I add woman to that?
Whatever took us from man to king, go ahead and apply that same vector
to the vector representation of the word woman,
and that gives us this vector here.
And now, just out of curiosity, let's take this expression
and find, what is the closest word to that expression?
And amazingly, what we get is we get the word queen--
that somehow, when you take the distance between man and king--
this numerical representation of how man is related to king--
and add that same notion, king minus man,
to the vector representation of the word woman.
What we get is we get the vector representation, or something close
to the vector representation of the word queen,
because this distance somehow encoded the relationship between these two
words.
And when you run it through this algorithm,
it's not programmed to do this, but if you just try and figure
out how to predict words based on context words,
you get vectors that are able to make these SAT-like analogies out
of the information that has been given.
So there are more examples of this.
We can say, all right, let's figure out, what
is the distance between Paris and France?
So Paris and France are words.
They each have a vector representation.
This then is a vector representation of the distance between Paris and France--
what takes us from France to Paris.
And let me go ahead and add the vector representation of England to that.
So this then is the vector representation
of going Paris minus France plus England--
so the distance between friends and Paris as vectors.
Add the England vector, and let's go ahead
and find the closest word to that.
And it turns out to be London.
You do this relationship, the relationship between France and Paris.
Go ahead and add the England vector to it, and the closest vector to that
happens to be the vector for the word London.
We can do more examples.
I can say, let's take the word for teacher--
that vector representation and-- let me subtract
the vector representation of school.
So what I'm left with is, what takes us from school to teacher?
And apply that vector to a word like hospital and see,
what is the closest word to that--
turns out the closest word is nurse.
Let's try a couple more examples-- closest word to ramen, for example.
Subtract closest word to Japan.
So what is the relationship between Japan and ramen?
Add the word for America to that.
Want to take a guess is what you might get as a result?
Turns out you get burritos as the relationship.
If you do the subtraction, do the addition,
this is the answer that you happen to get as a consequence of this as well.
So these very interesting analogies arise
in the relationships between these two words--
that if you just map out all of these words into a vector space,
you can get some pretty interesting results as a consequence of that.
And this idea of representing words as vectors turns out
to be incredibly useful and powerful anytime
we want to be able to do some statistical work with
regards to natural language, to be able to have--
represent words not just as their characters,
but to represent them as numbers, numbers that say something
or mean something about the words themselves,
and somehow relate the meaning of a word to other words that
might happen to exists--
so many tools then for being able to work inside
of this world of natural language.
The natural language is tricky.
We have to deal with the syntax of language and the semantics of language,
but we've really just seen just the beginning of some of the ideas that are
underlying a lot of natural language processing-- the ability to take text,
extract information out of it, get some sort of meaning out of it,
generate sentences maybe by having some knowledge of the grammar or maybe just
by looking at probabilities of what words are likely to show up based
on other words that have shown up previously--
and then finally, the ability to take words
and come up with some distributed representation of them, to take words
and represent them as numbers, and use those numbers
to be able to say something meaningful about those words as well.
So this then is yet another topic in this broader
heading of artificial intelligence.
And just as I look back at where we've been now,
we started our conversation by talking about the world of search,
about trying to solve problems like tic-tac-toe by searching
for a solution, by exploring our various different possibilities
and looking at what algorithms we can apply to be able to efficiently
try and search a space.
We looked at some simple algorithms and then looked at some optimizations
we could make to this algorithms, and ultimately, that
was in service of trying to get our AI to know things about the world.
And this has been a lot of what we've talked about today as well,
trying to get knowledge out of text-based information,
the ability to take information, draw conclusions based on those information.
If I know these two things for certain, maybe I
can draw a third conclusion as well.
That then was related to the idea of uncertainty.
If we don't know something for sure, can we
predict something, figure out the probabilities of something?
And we saw that again today in the context
of trying to predict whether a tweet or whether a message
is positive sentiment or negative sentiment,
and trying to draw that conclusion as well.
Then we took a look at optimization-- the sorts
of problems where we're looking for a local global or local maximum
or minimum.
This has come up time and time again, especially most recently
in the context of neural networks, which are really just a kind of optimization
problem where we're trying to minimize the total amount of loss
based on the setting of our weights of our neural network,
based on the setting of what vector representations for words we
happen to choose.
And those ultimately helped us to be able to solve
learning-related problems-- the ability to take a whole bunch of data,
and rather than us tell the AI exactly what to do,
let the AI learn patterns from the data for itself.
Let it figure out what makes an inbox message different from a spam message.
Let it figure out what makes a counterfeit
bill different from an authentic bill, and being
able to draw that analysis as well.
And one of the big tools in learning that we used
were neural networks, these structures that
allow us to relate inputs to outputs by training these internal networks
to learn some sort of function that maps us from some input to some output--
ultimately yet another model in this language of artificial intelligence
that we can use to communicate with our AI.
Then finally today, we looked at some ways
that AI can begin to communicate with us, looking at ways
that AI can begin to get an understanding for the syntax
and the semantics of language to be able to generate sentences,
to be able to predict things about text that's written in a spoken
language or a written language like English,
and to be able to do interesting analysis there as well.
And there's so much more in active research that's
happening all over the areas within artificial intelligence today,
and we've really only just seen the beginning of what AI has to offer.
So I hope you enjoyed this exploration into this world
of artificial intelligence with Python.
A big thank you to the courses teaching staff and the production team
for making this class possible.
This was an Introduction to Artificial Intelligence with Python.