>> LUCAS FREITAS: Hey.
Welcome everyone.
My name is Lucas Freitas.
I'm a junior at [INAUDIBLE] studying computer science with a focus in
computational linguistics.
So my secondary is in language and linguistic theory.
I'm really excited to teach you guys a little bit about the field.
It's a very exciting area to study.
Also with a lot of potential for the future.
So, I'm really excited that you guys are considering projects in
computational linguistics.
And I'll be more than happy to advise any of you if you decide to
pursue one of those.
>> So first of all what are computational linguistics?
So computational linguistics is the intersection between linguistics and
computer science.
So, what is linguistics?
What is computer science?
Well from linguistics, what we take are the languages.
So linguistics is actually the study of natural language in general.
So natural language-- we talk about language that we actually use to
communicate with each other.
So we're not exactly talking about C or Java.
We're talking more about English and Chinese and other languages that we
use to communicate with each other.
>> The challenging thing about that is that right now we have almost 7,000
languages in the world.
So there are quite a high variety of languages that we can study.
And then you think that it's probably very hard to do, for example,
translation from one language to the other, considering that you have
almost 7,000 of them.
So, if you think of doing translation from one language to the other you
have almost more than a million different combinations that you can
have from language to language.
So it's really challenging to do some kind of example translation system for
every single language.
>> So, linguistics treats with syntax, semantics, pragmatics.
You guys don't exactly need to know what are they are.
But the very interesting thing is that as a native speaker, when you learn
language as child, you actually learn all of those things-- syntax semantics
and pragmatics--
by yourself.
And nobody has to teach you syntax for you to understand how sentences are
structured.
So, it's really interesting because it's something that comes very
intuitively.
>> And what are you taking from the computer science?
Well, the most important thing that we have in computer science is first of
all, artificial intelligence and machine learning.
So, what we're trying to doing computational linguistics is teach
your computer how to do something with language.
>> So, for example, in machine translation.
I'm trying to teach my computer how to know how to transition from one
language to the other.
So, basically like teaching a computer two languages.
If I do natural language processing, which is the case for example of
Facebook's Graph Search, you teach your computer how to understand
queries well.
>> So, if you say "the photos of my friends." Facebook doesn't treat that
as a whole string that has just a bunch of words.
It actually understands the relation between "photos" and "my friends" and
understands that "photos" are property of "my friends."
>> So, that's part of, for example, natural language processing.
It's trying to understand what is the relation between
the words in a sentence.
And the big question is, can you teach a computer how to speak
a language in general?
Which is a very interesting question to think, as if maybe in the future,
you're going to be able to talk to your cell phone.
Kind of like what we do with Siri but something more like, you can actually
say whatever you want and the phone is going to understand everything.
And it can have follow up questions and keep talking.
That's something really exciting, in my opinion.
>> So, something about natural languages.
Something really interesting about natural languages is that, and this is
credit to my linguistics professor, Maria Polinsky.
She gives an example and I think it's really interesting.
Because we learn language from when we're born and then our native
language kind of grows on us.
>> And basically you learn language from minimal input, right?
You're just getting input from your parents of what your language sounds
like and you just learn it.
So, it's interesting because if you look at those sentences, for example.
You look, "Mary puts on a coat every time she leaves the house."
>> In this case, it's possible to have the word "she" refer to Mary, right?
You can say "Mary puts on a coat every time Mary leaves the
house." so that's fine.
But then if you look at the sentence "She puts on a coat every time Mary
leaves the house." you know it's impossible to say that "she" is
referring to Mary.
>> There's no way of saying that "Mary puts on a coat every time Mary leaves
the house." So it's interesting because this is the kind of intuition
that every native speaker has.
And nobody was taught that this is the way that the syntax works.
And that you can only have this "she" referring to Mary in this first case,
and actually in this other too, but not in this one.
But everyone kind of gets to the same answer.
Everyone agrees on that.
So it's really interesting how although you don't know all the rules
in your language you kind of understand how the language works.
>> So the interesting thing about natural language is that you don't have to
know any syntax to know if a sentence is grammatical or ungrammatical for
most cases.
Which makes you think that maybe what happens is that through your life, you
just keep getting more and more sentences told to you.
And then you keep memorizing all of the sentences.
And then when someone tells you something, you hear that sentence and
you look at your vocabulary of sentences and see if
that sentence is there.
And if it is there you say it's grammatical.
If it's not you say it's ungrammatical.
>> So, in that case, you would say, oh, so you have a huge list of all
possible sentences.
And then when you hear a sentence, you know if it's grammatical or
not based on that.
The thing is that if you look at a sentence, for example, "The
five-headed CS50 TFs cooked the blind octopus using a DAPA mug." It's
definitely not a sentence that you heard before.
But at the same time you know it's pretty much grammatical, right?
There are no grammatical mistakes and you can say that
it's a possible sentence.
>> So it makes us think that actually the way that we learn language is not only
by having a huge database of possible words or sentences, but more of
understanding the relation between words in those sentences.
Does that make sense?
So, then the question is, can computers learn languages?
Can we teach language to computers?
>> So, let's think of the difference between a native speaker of a language
and a computer.
So, what happens to the speaker?
Well, the native speaker learns a language from exposure to it.
Usually its early childhood years.
So, basically, you just have a baby, and you keep talking to it, and it
just learns how to speak the language, right?
So, you're basically giving input to the baby.
So, then you can argue that a computer can do the same thing, right?
You can just give language as input to the computer.
>> As for example a bunch of files that have books in English.
Maybe that's one way that you could possibly teach a
computer English, right?
And in fact, if you think about it, it takes you maybe a couple
days to read a book.
For a computer it takes a second to look at all the words in a book.
So you can think that may be just this argument of input from around you,
that's not enough to say that that's something that only humans can do.
You can think computers also can get input.
>> The second thing is that native speakers also have a brain that has
language learning capability.
But if you think about it, a brain is a solid thing.
When you are born, it's already set--
this is your brain.
And as you grow up, you just get more input of language and maybe nutrients
and other stuff.
But pretty much your brain is a solid thing.
>> So you can say, well, maybe you can build a computer that has a bunch of
functions and methods that just mimic language learning capability.
So in that sense, you could say, well, I can have a computer that has all the
things I need to learn language.
And the last thing is that a native speaker learns from trial and error.
So basically another important thing in language learning is that you kind
of learn things by making generalizations of what you hear.
>> So as you are growing up you learn that some words are more like nouns,
some other ones are adjectives.
And you don't have to have any knowledge of linguistics
to understand that.
But you just know there's some words are positioned in some part of the
sentence and some others in other parts of the sentence.
>> And that when you do something that is like a sentence that is not correct--
maybe because of an over generalization for example.
Maybe when you're growing up, you notice that the plural is usually
formed by putting an S at the end of the word.
And then you try to do the plural of "deer" as "deers" or "tooth" as
"tooths." So then your parents or someone corrects you and says, no, the
plural of "deer" is "deer," and the plural of "tooth" is "teeth." And then
you learn those things.
So you learn from trial and error.
>> But you can also do that with a computer.
You can have something called reinforcement learning.
Which is basically like giving a computer a reward whenever it does
something correctly.
And giving it the opposite of a reward and when it does something wrong.
You can actually see that if you go to Google Translate and you try to
translate a sentence, it asks you for feedback.
So if you say, oh, there's a better translation for this sentence.
You can type it up and then if a lot of people keep saying that is a better
translation, it just learns that it should use that translation instead of
the one it was giving.
>> So, it's a very philosophical question to see if computers are going to be
able to talk or not in the future.
But I have high hopes that they can just based on those arguments.
But it's just more of a philosophical question.
>> So while computers still cannot talk, what are the things that we can do?
Some really cool things are data classification.
So, for example, you guys know that email services do, for
example, spam filtering.
So whenever you receive spam, it tries to filter to another box.
So how does it do that?
It's not like the computer just knows what email addresses are sending spam.
So it's more based on the content of the message, or maybe the title, or
maybe some pattern that you have.
>> So, basically, what you can do is get a lot of data of emails that are spam,
emails that are not spam, and learn what kind of patterns you have in the
ones that are spam.
And this is part of computational linguistics.
It's called data classification.
And we're actually going to see an example of that in the next slides.
>> The second thing is natural language processing which is the thing that the
Graph Search is doing of letting you write a sentence.
And it trusts you understand what is the meaning and gives
you a better result.
Actually, if you go to Google or Bing and you search something like Lady
Gaga's height, you're actually going to get 5' 1" instead of information
from her because it actually understands what you're talking about.
So that's part of natural language processing.
>> Or also when you're using Siri, first you have an algorithm that tries to
translate what you're saying into words, in text.
And then it tries to translate that into meaning.
So that's all part of natural language processing.
>> Then you have machine translation--
which is actually one of my favorites--
which is just translating from a language to another.
So you can think that when you're doing machine translation, you have
infinite possibilities of sentences.
So there's no way of just storing every single translation.
So you have to come up with interesting algorithms to be able to
translate every single sentence in some way.
>> You guys have any questions so far?
No?
OK.
>> So what are we going to see today?
First of all, I'm going to talk about the classification problem.
So the one that I was saying about spam.
What I'm going to do is, given lyrics to a song, can you try to figure out
with high probability who is the singer?
Let's say that I have songs from Lady Gaga and Katy Perry, if I give you a
new song, can you figure out if it's Katy Perry or Lady Gaga?
>> The second one, I'm just going to talk about the segmentation problem.
So I don't know if you guys know, but Chinese, Japanese, other East Asian
languages, and other languages in general, don't have
spaces between words.
And then if you think about the way that your computer kind of tries to
understand natural language processing, it looks at the words and
tries to understand the relations between them, right?
But then if you have Chinese, and you have zero spaces, it's really hard to
find out what is the relation between words, because they don't have any
words at first.
So you have to do something called segmentation which just means putting
spaces between what we'd call words in those languages.
Make sense?
>> And then we're going to talk about syntax.
So just a little bit about natural language processing.
It's going to be just an overview.
So today, basically what I want to do is give you guys a little bit of an
inside of what are the possibilities that you can do with computational
linguistics.
And then you can see what you think is cool among those things.
And maybe you can think of a project and come talk to me.
And I can give you advice on how to implement it.
>> So syntax is going to be a little bit about Graph Search and machine
translation.
I'm just going to give an example of how you could, for example, translate
something from Portuguese to English.
Sounds good?
>> So first, the classification problem.
I'll say that this part of the seminar is going to be the most challenging
one just because there's going to be some coding.
But it's going to be Python.
I know you guys don't know Python, so I'm just going to explain on the high
level what I'm doing.
And you don't have to really care too much about the syntax because that's
something you guys can learn.
OK?
Sounds good.
>> So what is the classification problem?
So you're given some lyrics to a song, and you want to guess
who is singing it.
And this can be for any kind of other problems.
So it can be, for example, you have a presidential campaign and you have a
speech, and you want to find out if it was, for example,
Obama or Mitt Romney.
Or you can have a bunch of emails and you want to figure out if they are
spam or not.
So it's just classifying some data based on the words
that you have there.
>> So to do that, you have to make some assumptions.
So a lot about computational linguistics is making assumptions,
usually smart assumptions, so that you can get good results.
Trying to create a model for it.
And then try it out and see if it works, if it gives you good precision.
And if it does, then you try to improve it.
If it doesn't, you're like, OK, maybe I should make a different assumption.
>> So the assumption that we're going to make is that an artist usually sings
about a topic multiple times, and maybe uses words multiple times just
because they're used to it.
You can just think of your friend.
I'm sure you guys all have friends that say their signature phrase,
literally for every single sentence--
like some specific word or some specific phrase that they say for
every single sentence.
>> And what you can say is that if you see a sentence that has a signature
phrase, you can guess that probably your friend is the
one saying it, right?
So you make that assumption and then that's how you create a model.
>> The example that I'm going to give is on how Lady Gaga, for example, people
say that she uses "baby" for all her number one songs.
And actually this is a video that shows her saying the word "baby" for
different songs.
>> [VIDEO PLAYBACK]
>> -(SINGING) Baby.
Baby.
Babe.
Baby.
>> [END VIDEO PLAYBACK-
>> LUCAS FREITAS: So there are, I think, 40 songs here in which she says the
word "baby." So you can basically guess that if you see a song that has
the word "baby," there's some high probability that it's Lady Gaga.
But let's try to develop this further more formally.
>> So these are lyrics to songs by Lady Gaga and Katy Perry.
So you look at Lady Gaga, you see they have a lot of occurrences of "baby," a
lot of occurrences of "way." And then Katy Perry has a lot of occurrences of
"the," a lot of occurrences of "fire."
>> So basically what we want to do is, you get a lyric.
Let's say that you get a lyric for a song that is "baby," just "baby." If
you just get the word "baby," and this is all the data that you have from
Lady Gaga and Katy Perry, who would you guess is the person
who sings the song?
Lady Gaga or Katy Perry?
Lady Gaga, right?
Because she's the only one who says "baby." This sounds stupid, right?
OK, this is really easy.
I'm just looking at the two songs and of course, she's the only one who has
"baby."
>> But what if you have a bunch of words?
If you have an actual lyric, something like, "baby, I just
went to see a [? CFT ?]
lecture," or something like that, and then you actually have to figure out--
based on all those words--
who is the artist who probably sang this song?
So let's try to develop this a little further.
>> OK, so based just on the data that we got, it seems that Gaga is probably
the singer.
But how can we write this more formally?
And there's going to be a little bit of statistics.
So if you get lost, just try to understand the concept.
It doesn't matter if you understand the equations perfectly well.
This is all going to be online.
>> So basically what I'm calculating is the probability that this song is by
Lady Gaga given that--
so this bar means given that--
I saw the word "baby." Does that make sense?
So I'm trying to calculate that probability.
>> So there is this theorem called the Bayes theorem that says that the
probability of A given B, is the probability of B given A, times the
probability of A, over the probability of B. This is a long equation.
But what you have to understand from that is that this is what I want to
calculate, right?
So the probability that that song is by Lady Gaga given that I saw the word
"baby."
>> And now what I'm getting is the probability of the word "baby" given
that I have Lady Gaga.
And what is that basically?
What that means is, what is the probability of seeing the word "baby"
in Gaga lyrics?
If I want to calculate that in a very simple way, it's just the number of
times I see "baby" over the total number of words in Gaga lyrics, right?
What is the frequency that I see that word in Gaga's work?
Make sense?
>> The second term is the probability of Gaga.
What does that mean?
That basically means, what is the probability of classifying
some lyrics as Gaga?
And that is kind of weird, but let's think of an example.
So let's say that the probability of having "baby" in a song is the same
for Gaga and Britney Spears.
But Britney Spears has twice more songs than Lady Gaga.
So if someone just randomly gives you lyrics of "baby," the first thing you
look at is, what is the probability of having "baby" in a Gaga song, "baby"
in a Britney song?
And it's the same thing.
>> So the second thing that you'll see is, well, what is the probability of
this lyric by itself being a Gaga lyric, and what is the probability of
being a Britney lyric?
So since Britney has so many more lyrics than Gaga, you would probably
say, well, this is probably a Britney lyric.
So that's why we have this term right here.
Probability of Gaga.
Makes sense?
Does it?
OK.
>> And the last one is just the probability of "baby" which doesn't
really matter that much.
But it's the probability of seeing "baby" in English.
We usually don't care that much about that term.
Does that make sense?
So the probability of Gaga is called the prior probability
of the class Gaga.
Because it just means that, what is the probability of having that class--
which is Gaga--
just in general, just with no conditions.
>> And then when I have probability of Gaga given "baby," we call it plus
teary a probability because it's the probability of having
Gaga given some evidence.
So I'm giving you the evidence that I saw the word baby and
the song make sense?
OK.
>> So If I calculated that for each of the songs for Lady Gaga,
what that would be--
apparently, I cannot move this.
The probability of Gaga will be something like, 2 over 24, times 1/2,
over 2 over 53.
It doesn't matter if you know what these numbers are coming from.
But it's just a number that is going to be more than 0, right?
>> And then when I do Katy Perry, the probability of "baby" given Katy is
already 0, right?
Because there's no "baby" in Katy Perry.
So then this becomes 0, and Gaga wins, which means that Gaga is
probably the singer.
Does that make sense?
OK.
>> So if I want to make this more official, I can actually do a model
for multiple words.
So let's say that I have something like, "baby, I am
on fire," or something.
So it has multiple words.
And in this case, you can see that "baby" is in Gaga,
but it's not in Katy.
And "fire" is in Katy, but it's not in Gaga, right?
So it's getting trickier, right?
Because it seems that you almost have a tie between the two.
>> So what you have to do is assume independency among the words.
So basically what that means is that I'm just calculating what is the
probability of seeing "baby," what is the probability of seeing "I," and
"am", and "on," and "fire," all separately.
Then I'm multiplying all of them.
And I'm seeing what is the probability of seeing the whole sentence.
Make sense?
>> So basically, if I have just one word, what I want to find is the arg max,
which means, what is the class that is giving me the highest probability?
So what is the class that is giving me the highest probability for
probability of class given word.
So in this case, Gaga given "baby." Or Katy given "baby." Make sense?
>> And just from Bayes, that equation that I showed,
we create this fraction.
The only thing is that you see that the probability of word given the
class changes depending on the class, right?
The number of "baby"s that I have in Gaga is different from Katy.
The probability of the class also changes because it's just the number
of songs each of them has.
>> But the probability of the word itself is going to be the same for all the
artists, right?
So the probability of the word is just, what is the probability of
seeing that word in the English language?
So it's the same for all of them.
So since this is constant, we can just drop this and not care about it.
So this will be actually the equation we're looking for.
>> And if I have multiple words, I'm still going to have the prior
probability here.
The only thing is that I'm multiplying the probability of
all the other words.
So I'm multiplying all of them.
Make sense?
It looks weird but basically means, calculate the prior of the class, and
then multiply by the probability of each of the words being in that class.
>> And you know that the probability of a word given a class is going to be the
number of times you see that word in that class, divided by the number of
words you have in that class in general.
Make sense?
It's just how "baby" was 2 over the number of words that
I had in the lyrics.
So just the frequency.
>> But there is one thing.
Remember how I was showing that the probability of "baby" being lyrics
from Katy Perry was 0 just because Katy Perry didn't have "baby" at all?
But it sounds a little harsh to just simply say that lyrics cannot be from
an artist just because they don't have that word in particular at any time.
>> So you could just say, well, if you don't have this word, I'm going to
give you a lower probability, but I'm just not going to
give you 0 right away.
Because maybe it was something like, "fire, fire, fire, fire," which is
totally Katy Perry.
And then "baby," and it just goes to 0 right away because there was one
"baby."
>> So basically what we do is something called Laplace smoothing.
And this just means that I'm giving some probability even to the words
that do not exist.
So what I do is that when I'm calculating this, I always add 1 to
the numerator.
So even if the word doesn't exist, in this case, if this is 0, I'm still
calculating this as 1 over the total number of words.
Otherwise, I get how many words I have and I add 1.
So I'm counting for both cases.
Make sense?
>> So now let's do some coding.
I'm going to have to do it pretty fast, but it's just important that you
guys understand the concepts.
So what we're trying to do is exactly implement this
thing that I just said--
I want you to put lyrics from Lady Gaga and Katy Perry.
And the program is going to be able to say if these new lyrics are from Gaga
or Katy Perry.
Make sense?
OK.
>> So I have this program I'm going to call classify.py.
So this is Python.
It's a new programming language.
It is very similar in some ways to C and PHP.
It's similar because if you want to learn Python after knowing C, it's
really not that much of a challenge just because Python is much easier
than C, first of all.
And a lot of things are already implemented for you.
So just how like PHP has functions that sort a list, or append something
to an array, or blah, blah, blah.
Python has all of those as well.
>> So I'm just going to explain quickly how we could do the classification
problem for here.
So let's say that in this case, I have lyrics from Gaga and Katy Perry.
The way that I have those lyrics is that the first word of the lyrics is
the name of the artist, and the rest is the lyrics.
So let's say that I have this list in which the first one is lyrics by Gaga.
So here I am on the right track.
And the next one is Katy, and it has also the lyrics.
>> So this is how you declare a variable in Python.
You don't have to give the data type.
You just write "lyrics," kind of like in PHP.
Make sense?
>> So what are the things that I have to calculate to be able to calculate the
probabilities?
I have to calculate the "priors" of each of the different
classes that I have.
I have to calculate the "posteriors," or pretty much the probabilities of
each of the different words that I can have for each artist.
So within Gaga, for example, I'm going to have a list of how many times I see
each of the words.
Make sense?
>> And finally, I'm just going to have a list called "words" that is just going
to have how many words I have for each artist.
So for Gaga, for example, when I look to the lyrics, I had, I think, 24
words in total.
So this list is just going to have Gaga 24, and Katy another number.
Make sense?
OK.
>> So now, actually, let's go to the coding.
So in Python, you can actually return a bunch of different
things from a function.
So I'm going to create this function called "conditional," which is going
to return all of those things, the "priors," the "probabilities," and the
"words." So "conditional," and it's going to be calling into "lyrics."
>> So now I want you to actually write this function.
So the way that I can write this function is I just defined this
function with "def." So I did "def conditional," and it's taking
"lyrics." And what this is going to do is, first of all, I have my priors
that I want to calculate.
>> So the way that I can do this is create a dictionary in Python, which
is pretty much the same thing as a hash table, or it's like an iterative
array in PHP.
This is how I declare a dictionary.
And basically what this means is that priors of Gaga is 0.5, for example, if
50% of the lyrics are from Gaga, 50% are from Katy.
Make sense?
So I have to figure out how to calculate the priors.
>> The next ones that I have to do, also, are the probabilities and the words.
So the probabilities of Gaga is the list of all the probabilities that I
have for each of the words for Gaga.
So if I go to probabilities of Gaga "baby," for example, it'll give me
something like 2 over 24 in that case.
Make sense?
So I go to "probabilities," go to the "Gaga" bucket that has a list of all
the Gaga words, then I go to "baby," and I see the probability.
>> And finally I have this "words" dictionary.
So here, "probabilities." And then "words." So if I do "words," "Gaga,"
what is going to happen is that it's going to give me 24, saying that I
have 24 words within lyrics from Gaga.
Makes sense?
So here, "words" equals dah-dah-dah.
OK
>> So what I'm going to do is I'm going to iterate over each of the lyrics, so
each of the strings that I have in the list.
And I'm going to calculate those things for each of the candidates.
Makes sense?
So I have to do a for loop.
>> So in Python what I can do is "for line in lyrics." The same thing as a
"for each" statement in PHP.
Remember how if it was PHP I could say "for each lyrics as
line." Makes sense?
So I'm taking each of the lines, in this case, this string and the next
string so for each of the lines what I'm going to do is first, I'm going to
split this line into a list of words separated by spaces.
>> So the cool thing about Python is that you could just Google like "how can I
split a string into words? " and it's going to tell you how to do it.
And the way to do it, it's just "line = line.split()" and it's basically
going to give you a list with each of the words here.
Makes sense?
So now that I did that I want to know who is the singer of that song.
And to do that I just have to get the first element of the array, right?
So I can just say that I "singer = line(0)" Makes sense?
>> And then what I need to do is, first of all, I'm going to update how many
words I have under "Gaga." so I'm just going to calculate how many words I
have in this list, right?
Because this is how many words I have in the lyrics and I'm just going to
add it to the "Gaga" array.
Does that make sense?
Don't focus too much on the syntax.
Think more about the concepts.
That's the most important part.
OK.
>> So what I can do it is if "Gaga" is already in that list, so "if singer in
words" which means that I already have words by Gaga.
I just want to add the additional words to that.
So what I do is "words(singer) + = len(line) - 1".
And then I can just do the length of the line.
So how many elements I have in the array.
And I have to do minus 1 just because the first element of the array is just
a singer and those are not lyrics.
Makes sense?
OK.
>> "Else," it means that I want to actually insert Gaga into the list.
So I just do "words(singer) = len(line) - 1," sorry.
So the only difference between the two lines is that this one, it doesn't
exist yet, so I'm just initializing it.
This one I'm actually adding.
OK.
So this was adding to words.
>> Now I want to add to the priors.
So how do I calculate the priors?
The priors can be calculated by how many times.
So how many times you see that singer among all of the singers that you
have, right?
So for Gaga and Katy Perry, in this case, I see Gaga
once, Katy Perry once.
>> So basically the priors for Gaga and for Katy Perry would
just be one, right?
You just how many times I see the artist.
So this is very easy to calculate.
I can just something similar as like "if singer in priors," I'm just going
to add 1 to their priors box.
So, "priors(sing)" += 1" and then "else" I'm going to do "priors(singer)
= 1." Makes sense?
>> So if it doesn't exist I just put as 1, otherwise I just add 1.
OK, so now all that I have left to do is also add each of the words to the
probabilities.
So I have to count how many times I see each of the words.
So I just have to do another for loop in the line.
>> So first thing that I'm going to do is check if the singer already has a
probabilities array.
So I'm checking if the singer doesn't have a probabilities array, I'm just
going to initialize one for them.
It's not even an array, sorry, it's a dictionary.
So the probabilities of singer is going to be an open dictionary, so I'm
just initializing a dictionary for it.
OK?
>> And now I can actually do a for loop to calculate each of the words'
probabilities.
OK.
So what I can do is a for loop.
So I'm just going to iterate over the array.
So the way that I can do that in Python is "for i in range." From 1
because I want to start in the second element because the first one is the
singer name.
So from one up to the length of the line.
And when I do range it actually go from like here from 1 to len of the
line minus 1.
So it already does that thing of doing n minus 1 for arrays which is very
convenient.
Makes sense?
>> So for each of these, what I'm going to do is, just like in the other one,
I'm going to check if the word in this position in the line is already in
probabilities.
And then as I said here, probabilities words, as in I put
"probabilities(singer)".
So the name of the singer.
So if it's already in "probabilit(singer)", it means that I
want to add 1 to it, so I'm going to do "probabilities(singer)", and the
word is called "line(i)".
I'm going to add 1 and "else" I'm just going to initialize it to 1.
"Line(i)".
Makes sense?
>> So, I calculated all of the arrays.
So, now all that I have to do for this one is just "return priors,
probabilities and words." Let's see if there are any, OK.
It seems everything is working so far.
So, that makes sense?
In some way?
OK.
So now I have all the probabilities.
So now the only thing I have left is just to have that thing that
calculates the product of all the probabilities when I get the lyrics.
>> So let's say that I want to now call this function "classify()" and the
thing that function takes is just an argument.
Let's say "Baby, I am on fire" and it's going to figure out what is the
probability that this is Gaga?
What is the probability that this is Katie?
Sounds good?
So I'm just going to have to create a new function called "classify()" and
it's going to take some lyrics as well.
And besides the lyrics I also have to send the priors, the
probabilities and the words.
So I'm going to send lyrics, priors, probabilities, words.
>> So this is taking lyrics, priors, probabilities, words.
So, what does it do?
It basically is going to go through all the possible candidates that you
have as a singer.
And where are those candidates?
They're In the priors, right?
So I have all of those there.
So I'm going to have a dictionary of all possible candidates.
And then for each candidate in the priors, so it means that it's going to
be Gaga, Katie if I had more it would be more.
I'm going to start calculating this probability.
The probability as we saw in the PowerPoint is the prior times the
product of each of the other probabilities.
>> So I can do the same here.
I can just do probability is initially just the prior.
So priors of the candidate.
Right?
And now I have to iterate over all the words that I have in the lyrics to be
able to add the probability for each of them, OK?
So, "for word in lyrics" what I'm going to do is, if the word is in
"probabilities(candidate)", which means that it's a word that the
candidate has in their lyrics--
for example, "baby" for Gaga--
what I'm going to do is that the probability is going to be multiplied
by 1 plus the probabilities of the candidate for that word.
And it's called "word".
This divided by the number of words that I have for that candidate.
The total number of words that I have for the singer that I'm looking at.
>> "Else." it means it's a new word so it'd be like for example
"fire" for Lady Gaga.
So I just want to do 1 over "word(candidate)".
So I don't want to put this term here.
>> So it's going to be basically copying and pasting this.
But I'm going to delete this part.
So it's just going to be 1 over that.
Sounds good?
And now at the end, I'm just going to print the name of the candidate and
the probability that you have of having the S on their lyrics.
Makes sense?
And I actually don't even need this dictionary.
Makes sense?
>> So, let's see if this actually works.
So if I run this, it didn't work.
Wait one second.
"Words(candidate)", "words(candidate)", that's
the name of the array.
OK So, it says there's some bug for candidate in priors.
Let me just chill a little bit.
OK.
Let's try.
OK.
>> So it gives Katy Perry has this probability of this times 10 to the
minus 7, and Gaga has this times 10 to the minus 6.
So you see it shows that Gaga has a higher probability.
So "Baby, I'm on Fire" is probably a Gaga song.
Makes sense?
So this is what we did.
>> This code is going to be posted online, so you guys can check it out.
Maybe use some of it for if you want to do a project or something similar.
OK.
This was just to show what computational
linguistics code looks like.
But now let's go to more high level stuff.
OK.
>> So the other problems I was talking about--
the segmentation problem is the first of them.
So you have here Japanese.
And then you see that there are no spaces.
So this is basically means that it's the top of the chair, right?
You speak Japanese?
It's the top of the chair, right?
>> STUDENT: I don't know what the kanji over there is.
>> LUCAS FREITAS: It's [SPEAKING JAPANESE]
OK.
So it basically means chair of top.
So if you had to put a space it would be here.
And then you have [? Ueda-san. ?]
Which basically means Mr. Ueda.
And you see that "Ueda" and you have a space and then "san." So you see that
here you "Ue" is like by itself.
And here it has a character next to it.
>> So it's not like in those languages characters meaning a word it so you
just put a lot of spaces.
Characters relate to each other.
And they can be together like two, three, one.
So you actually have to create some kind of way of putting those spaces.
>> And this thing is that whenever you get data from those Asian languages,
everything comes unsegmented.
Because no one who writes Japanese or Chinese writes with spaces.
Whenever you're writing Chinese, Japanese you just write everything
with no spaces.
It doesn't even make sense to put spaces.
So then when you get data from, some East Asian language, if you want to
actually do something with that you have to segment first.
>> Think of doing the example of the lyrics without spaces.
So the only lyrics that you have will be sentences, right?
Separated by periods.
But then having just the sentence will not really help on giving information
of who those lyrics are by.
Right?
So you should puts spaces first.
So how can you do that?
>> So then comes the idea of a language model which is something really
important for computational linguistics.
So a language model is basically a table of probabilities that shows
first of all what is the probability of having the word in a language?
So showing how frequent a word is.
And then also showing the relation between the words in a sentence.
>> So the main idea is, if a stranger came to you and said a sentence to
you, what is the probability that, for example, "this is my sister [? GTF" ?]
was the sentence that the person said?
So obviously some sentences are more common than others.
For example, "good morning," or "good night," or "hey there," is much more
common than most sentences that we have an English.
So why are those sentences more frequent?
>> First of all, it's because you have words that are more frequent.
So, for example, if you say, the dog is big, and the dog is gigantic, you
usually probably hear the dog is big more often because "big" is more
frequent in English than "gigantic." So, one of the
things is the word frequency.
>> The second thing which is really important is just the
order of the words.
So, it's common to say "the cat is inside the box." but you don't usually
see in "The box inside is the cat." so you see that there is some importance
in the order of the words.
You cannot just say that those two sentences have the same probability
just because they have the same words.
You actually have to care about order as well.
Make sense?
>> So what do we do?
So what I might try to get you?
I'm trying to get you what we call the n-gram models.
So n-gram models basically assume that for each word that
you have in a sentence.
It's the probability of having that word there depends not only on the
frequency of that word in the language, but also on the words that
are surrounding it.
>> So for example, usually when you see something like on or at you're
probably going to see a noun after it, right?
Because when you have a preposition usually it takes a noun after it.
Or if you have a verb that is transitive you usually are going to
have a noun phrase.
So it's going to have a noun somewhere around it.
>> So, basically, what it does is that it considers the probability of having
words next to each other, when you're calculating the
probability of a sentence.
And that's what a language model is basically.
Just saying what's the probability of having a specific
sentence in a language?
So why is that useful, basically?
And first of all what is an n-gram model, then?
>> So an n-gram model means that each word depends on the
next N minus 1 words.
So, basically, it means that if I look, for example, at the CS50 TF when
I'm calculating the probability of the sentence, you'll be like "the
probability of having the word "the" times the probability of having "the
CS50" times the probability of having "The CS50 TF." So, basically, I count
all possible ways of stretching it.
>> And then usually when you're doing this, as in a project, you put N to be
a low value.
So, usually have bigrams or trigrams.
So that you just count two words, a group of two words, or three words,
just for performance issues.
And also because maybe if you have something like "The CS50 TF." When you
have "TF," it's very important that "CS50" is next to it, right?
Those two things are usually next to each other.
>> If you think of "TF," it's probably going to have what
class it's TF'ing for.
Also "the" is really important for CS50 TF.
But if you have something like "The CS50 TF went to class and gave their
students some candy." "Candy" and "the" have no relation really, right?
They're so distant from each other that it doesn't really matter what
words you have.
>> So by doing a bigram or a trigram, it just means that you're limiting
yourself to some words that are around.
Make sense?
So when you want to do segmentation, basically, what you want to do is see
what are all the possible ways that you can segment the sentence.
>> Such that you see what is the probability of each of those sentences
existing in the language?
So what you do is like, well, let me try to put a space here.
So you put a space there and you see what is the
probability of that sentence?
Then you are like, OK, maybe that was not that good.
So I put a space there and a space there, and you calculate the
probability now, and you see that it's a higher probability.
>> So this is an algorithm called the TANGO segmentation algorithm, which is
actually something that would be really cool for a project, which
basically takes unsegmented text which can be Japanese or Chinese or maybe
English without spaces and tries to put spaces between words and it does
that by using a language model and trying to see what is the highest
probability you can get.
OK.
So this is segmentation.
>> Now syntax.
So, syntax is being used for so many things right now.
So for Graph Search, for Siri for pretty much any kind of natural
language processing you have.
So what are the important things about syntax?
So, sentences in general have what we call constituents.
Which are kind of like groups of words that have a function in the sentence.
And they can not really be apart from each other.
>> So, if I say, for example, "Lauren loves Milo." I know that "Lauren" is a
constituent and then "loves Milo" is also another one.
Because you cannot say like "Lauren Milo loves" to have the same meaning.
It's not going to have the same meaning.
Or I cannot say like "Milo Lauren loves." Not everything has the same
meaning doing that.
>> So the two more important things about syntax are the lexical types which is
basically the function that you have for words by themselves.
So you have to know that "Lauren" and "Milo" are nouns.
"Love" is a verb.
And the second important thing is that they're phrasal types.
So you know that "loves Milo" is actually a verbal phrase.
So when I say "Lauren," I know that Lauren is doing something.
What is she doing?
She's loving Milo.
So it's a whole thing.
But its components are a noun and a verb.
But together, they make a verb phrase.
>> So, what can we actually do with computational linguistics?
So, if I have something for example "friends of Allison." I see if I just
did a syntactic tree I would know that "friends" is a noun phrase it is a
noun and then "of Allison" is a prepositional phrase in which "of" is
a proposition and "Allison" is a noun.
What I could do is teach my computer that when I have a noun phrase one and
then a prepositional phrase.
So in this case, "friends" and then "of Milo" I know that this means that
NP2, the second one, owns NP1.
>> So I can create some kind of relation, some kind of function for it.
So whenever I see this structure, which matches exactly with "friends of
Allison," I know that Allison owns the friends.
So the friends are something that Allison has.
Makes sense?
So this is basically what Graph Search does.
It just creates rules for a lot of things.
So "friends of Allison," "my friends who live in Cambridge," "my friends
who go to Harvard." It creates rules for all of those things.
>> Now machine translation.
So, machine translation is also something statistical.
And actually if you get involved in computational linguistics, a lot of
your stuff is going to be statistics.
So as I was doing the example with a lot of probabilities that I was
calculating, and then you get to this very small number that's the final
probability, and that's what gives you the answer.
Machine translation also uses a statistical model.
And if you want to think of machine translation in the simplest possible
way, what you can think is just translate word by word, right?
>> When you're learning a language for the first time, that's usually what
you do, right?
If you want you translate a sentence in your language to the language
you're learning, usually first, you translate each of the words
individually, and then you try to put the words into place.
>> So if I wanted to translate this, [SPEAKING PORTUGUESE]
which means "the white cat ran away." If I wanted to translate it from
Portuguese to English, what I could do is, first, I just
translate word by word.
So "o" is "the," "gato," "cat," "branco," "white," and then "fugio" is
"ran away."
>> So then I have all the words here, but they're not in order.
It's like "the cat white ran away" which is ungrammatical.
So, then I can have a second step, which is going to be finding the ideal
position for each of the words.
So I know that I actually want to have "white cat" instead of "cat white." So
what I can do is, the most naive method would be to create all the
possible permutations of words, of positions.
And then see which one has the highest probability according
to my language model.
And then when I find the one that has the highest probability it, which is
probably "the white cat ran away," that's my translation.
>> And this is a simple way of explaining how a lot of machine translation
algorithms work.
Does that make sense?
This is also something really exciting that you guys can maybe explore for a
final project, yeah?
>> STUDENT: Well, you said it was the naive way, so what's
the non-naive way?
>> LUCAS FREITAS: The non-naive way?
OK.
So the first thing that is bad about this method is that I just translated
words, word by word.
But sometimes you have words that can have multiple translations.
I'm going to try to think of something.
For example, "manga" in Portuguese can either be "mangle" or "sleeve." So
when you're trying to translate word by word, it might be giving you
something that makes no sense.
>> So you actually want to you look at all the possible translations of the
words and see, first of all, what is the order.
We were talking about permutating the things?
To see all the possible orders and choose the one with the highest
probability?
You can also choose all the possible translations for each
word and then see--
combined with the permutations--
which one has the highest probability.
>> Plus, you can also look at not only words but phrases.
so you can analyze the relations between the words and then get a
better translation.
Also something else, so this semester I'm actually doing research in
Chinese-English machine translation, so translating from
Chinese into English.
>> And something we do is, besides using a statistical model, which is just
seeing the probabilities of seeing some position in a sentence, I'm
actually also adding some syntax to my model, saying, oh, if I see this kind
of construction, this is what I want to change it to when I translate.
So you can also add some kind of element of syntax to make the
translation more efficient and more precise.
OK.
>> So how can you get started, if you want to do something in computational
linguistics?
>> First, you choose a project that involves languages.
So, there's so many out there.
There's so many things you can do.
And then can think of a model that you can use.
Usually that means thinking of assumptions, as like, oh, when I was
like thinking of the lyrics.
I was like, well, if I want to figure out a who wrote this, I probably want
to look at the words the person used and see who uses that word very often.
So try to make assumptions and try to think of models.
And then you can also search online for the kind of problem that you have,
and it's going to suggest to you models that maybe
modeled that thing well.
>> And also you can always email me.
me@lfreitas.com.
And I can just answer your questions.
We can even might meet up so I can give suggestions on ways of
implementing your project.
And I mean if you get involved with computational linguistics, it's going
to be great.
You're going to see there is so much potential.
And the industry wants to hire you so bad because of that.
So I hope you guys enjoyed this.
If you guys have any questions, you can ask me after this.
But thank you.