[Classic] Word2Vec: Distributed Representations of Words and Phrases and their Compositionality
deep learning machine learning arxiv explained neural networks ai artificial intelligence paper jeff dean mikolov word2vec word vectors word representations nlp natural language processing sentiment classification king queen man woman arithmetic latent space distributed country capital semantic synonyms skip gram negative sampling nce noise contrastive estimation
#ai #research #word2vec

Word vectors have been one of the most influential techniques in modern NLP to date. This paper describes Word2Vec, which the most popular technique to obtain word vectors. The paper introduces the negative sampling technique as an approximation to noise contrastive estimation and shows that this allows the training of word vectors from giant corpora on a single machine in a very short time.

OUTLINE:
0:00 - Intro & Outline
1:50 - Distributed Word Representations
5:40 - Skip-Gram Model
12:00 - Hierarchical Softmax
14:55 - Negative Sampling
22:30 - Mysterious 3/4 Power
25:50 - Frequent Words Subsampling
28:15 - Empirical Results
29:45 - Conclusion & Comments

Paper: https://arxiv.org/abs/1310.4546
Code: https://code.google.com/archive/p/word2vec/

Abstract:
The recently introduced continuous Skip-gram model is an efficient method for learning high-quality distributed vector representations that capture a large number of precise syntactic and semantic word relationships. In this paper we present several extensions that improve both the quality of the vectors and the training speed. By subsampling of the frequent words we obtain significant speedup and also learn more regular word representations. We also describe a simple alternative to the hierarchical softmax called negative sampling. An inherent limitation of word representations is their indifference to word order and their inability to represent idiomatic phrases. For example, the meanings of "Canada" and "Air" cannot be easily combined to obtain "Air Canada". Motivated by this example, we present a simple method for finding phrases in text, and show that learning good vector representations for millions of phrases is possible.

Authors: Tomas Mikolov, Ilya Sutskever, Kai Chen, Greg Corrado, Jeffrey Dean


Links:
YouTube: https://www.youtube.com/c/yannickilcher
Twitter: https://twitter.com/ykilcher
Discord: https://discord.gg/4H8xxDF
BitChute: https://www.bitchute.com/channel/yannic-kilcher
Minds: https://www.minds.com/ykilcher
Parler: https://parler.com/profile/YannicKilcher
LinkedIn: https://www.linkedin.com/in/yannic-kilcher-488534136/

If you want to support me, the best thing to do is to share out the content :)

If you want to support me financially (completely optional and voluntary, but a lot of people have asked for this):
SubscribeStar: https://www.subscribestar.com/yannickilcher
Patreon: https://www.patreon.com/yannickilcher
Bitcoin (BTC): bc1q49lsw3q325tr58ygf8sudx2dqfguclvngvy2cq
Ethereum (ETH): 0x7ad3513E3B8f66799f507Aa7874b1B0eBC7F85e2
Litecoin (LTC): LQW2TRyKYetVC8WjFkhpPhtpbDM4Vw7r9m
Monero (XMR): 4ACL8AGrEo5hAir8A9CeVrW8pEauWvnp1WnSDZxW7tziCDLhZAGsgzhRQABDnFy8yuM9fWJDviJPHKRjV4FWt19CJZN9D4n
 Hi there, today we'll look at distributed representations of words and phrases and their compositionality by Thomas Mikolov, Ilya Sotskyver, Kai Chen, Greg Corrado and Jeffrey Dean. This is another historical paper, it's one of three papers, it's the middle one that introduces the original Word2vec algorithm. And as you might know, Word2vec was extremely influential in NLP since this paper basically until recently, where it's sort of gone out of fashion a bit in research with the rise of things like ELMo and BERT, but it's still very, very relevant. So we'll look at this historical paper today with kind of the hindsight of being a couple years into the future. In fact, as you see right here, this was released in 2013, so it's seven years later now. And we'll look back and we'll see what they said back then about the system. This is not going to be like a very well-enhanced PowerPoint presentation of how Word2vec works. We're going to look at the paper and read it together. If you like content like this, if you like historical paper readings, let me know in the comments, share it out if you do like it and of course subscribe. Because this kind of historical papers, I enjoy them, but many people might already know what these things are. So, yeah. Okay. Let's, you know, go through the paper and pick up their ideas and kind of put them in context. They say the recently introduced continuous skip gram model is an efficient method for learning high quality distributed vector representations that capture a large number of precise syntactic and semantic word relationships. So the skip gram model was already introduced by Mikhailov in an earlier paper that came out, I believe not like one or two months prior to this one. As I said, Word2vec is a series of papers. I don't think there is a paper called Word2vec. Rather, they here have released the code along with the paper. The code was called Word2vec. So the skip gram model was introduced previously, but it is replicated right here. So in the skip gram model, what you're trying to do is you're trying to get a distributed word representation. So what does that mean? That means that for each word in your language, let's take these words right here. For each word in the language, you want to come up with a vector that somehow describes that word in a continuous fashion. So with the two might be mapped to, I don't know, 0.1, 0.9, and 0.3. Learn might be mapped to negative 0.5 and so on. So each word gets assigned a vector in the same dimensional space. And what the previous paper kind of discovered is that if you do this correctly, then these vectors, they have some kind of properties. So we can already kind of jump ahead because this was already a bit, a bit researched in the last paper. The semantics of these vectors will be something like this. So here they have a two dimensional PCA. So these are the first two dimensions of the 1000 dimensional skip gram vector. So the vectors they obtain, they can do things like this, where they can show that in these spaces, for example, there appears to be a vector direction that characterizes the capital of a country. So if you take a few countries and their capitals and you average that vector, you get a kind of a direction for capitalness of a city. Given a country, you can see that there is a pretty clear relation here. Now, some of these things have later been revised to such that they are ultimately ended up being not that impressive. For example, there was always this kind of math with vectors. And I don't, I believe this is, this might not be in this. This is in the last paper where they discovered that if you take the vector for king and you subtract the vector for man and you add the vector for woman, then that would result in the vector for queen. So the way they did it was basically they did this calculation right here and then they searched in the point they ended up, they searched for the nearest neighbor in their vocabulary. And that turned out to be queen. But in order to make it queen, actually, you have to exclude the original word king. People quickly discovered that if you don't exclude the original word, the result of this kind of arithmetic will almost always lead back to the original word. And then a lot of these analogy tasks are simply the result of you then discarding that word during the nearest neighbor search. And then queen just happens to be one of the closest words. And it's sort of much less dependent on which exact calculation you do here. So there's been a lot of follow up work kind of analyzing, criticizing these vector maths. But definitely we know that these word vectors turned out to be extremely, extremely helpful and syntactically and semantically relevant in downstream tasks because they have performed very, very well. So how does the skip gram model work? How does it assign vectors to each word? So first of all, it has a dictionary. So there is a word, an input word. And for each word, you have a big dictionary. And the big dictionary basically says that the word two is going to be mapped to this vector point one, da, da, da, da, da, da, and so on. The word learn is going to be mapped to that vector. And then you also have these output vectors right here. And what you're trying to do is you're trying to take a phrase from the data set like this one right here. And you take out one word like this word vector right here. And you're trying to frame this as a prediction task. So you're trying to frame this as, in this case, four different prediction tasks. So you're telling your machine, I give you the word vector, and which other words are around the word vector? You just tell it that you don't tell it anything else. You just say, which other words are around the word vector? And the correct answers in this case would be to, learn, word, and representations. So you construct four different training examples where you have an X and a Y. So the X is always vector, and the Y is two. And then the next training sample, the X is vector, and the Y is learn, and so on. So this here, each training sample is a classification task. And the classification task is, as you can see, no, you can't see right here, but the classification task is you have the input word, and you classify it into one of many, many, many, many, many, many classes. Namely, there are as many classes as you have words in the dictionary. So each word in the dictionary will have a class associated with it. So in ImageNet, you have like 1,000 classes, but in these, that's already a lot. But in these tasks, you're going to have 100,000 classes, because there are 100,000 words in the English language that you want to treat. There are many more, but in this case, they leave away all the words that appear less than five times in their corpus. That's still a lot of words. So it's like a super duper duper lot of classification task. But ultimately, if you do something like this, then the origin, so the representation that you end up with is going to be very, very good at doing these kind of downstream tasks. And that's what they discovered. So their skip gram model is nothing else than taking a word and predicting the surrounding words from that word. And this is what it means. This is the formal statement of the skip gram objective. What you want to do is the objective of the skip gram model is to maximize the average log probability this one. So for the word we're considering, the word T, we want to maximize the log probability of each word w that is in around the word c, sorry, around the word w in a context window of c. That's exactly what we did before. Take a word like this model right here. And from it, we predict all of the words around it in a given window. That's all. That's the entire objective. And that will give you very good representations. And this is how you would implement that. So what you'll have is you'll have these vector representation v that comes from your original dictionary. Those are the things you learn. And then because you have like a 30,000 way classifier, you know that a classification layer is nothing else than a linear layer followed by a softmax operation. And that linear layer also has parameters. These are the v primes. So first you have the look up in the dictionary for the word vector right here. And this is the vector of the classification layer. Now there are modifications where you can use like the same vectors and so on. Or you can also make use of these vectors. But ultimately, you care about these vectors right here. And the vectors here are simply the classification layers weights. So here you can see that there is what you're trying to maximize is the inner product between the word that you're considering and the words around that word. And you're trying to do a classification task. So you need to normalize. Now this is the normalization constant, and it goes over all of your vocabulary. So that's what they tackle here. They say w is the number of words in the vocabulary. This formulation is impractical because the cost of computing the gradient is proportional to w, which is often large. And that's 10 to the five to 10 to the seven terms. So many like tens of millions of terms in your vocabulary. That's just not feasible. So people have been sort of trying different ways to get around very, very large number of classes. And here it seems that that is really our bottleneck. In the previous paper, they've already shown that this objective can give you very good word representation. But now we need to get around the fact that we have such large vocabularies. So the first idea here is hierarchical softmax. And this is kind of a tangent. I find this paper, by the way, it's sort of hard to read because it's like a half engineering paper. But yeah, so first they introduce this hierarchical softmax, which is kind of a distraction. It's kind of a here is what we do. Here is what we considered first, but then didn't end up using really. They do compare with it, but the flow of text is sort of that you expect this to be part of the final model, which it isn't. So in the hierarchical softmax, what you do instead of having this giant multi class classification task right here, you take all of these classes right here, and you put them in a sort of a tree. Okay, so you take this and you put them into a tree. So instead of classifying, you know, let's say we have 1000 classes, instead of classifying 1000 ways, we first classify in two ways. And then we classify in two ways again, from each one, and then we classify in two ways again, as you know, 1000 is like two to the 10. So we need approximately 10 layers of this before we are actually arriving at 1000 classes. But it also means that we only have two way classifications each time. So in the hierarchical softmax, we build trees like this, and then we so we have a word, we look up its vector, sorry, its vector, and then we classify it for each of these nodes. So your output isn't going to be 1000, 1000 log probabilities, your output is going to be a log probability, a binary log probability for each of the nodes right here. So you want to know, okay, here, is it in the upper half or the lower half of my classes? Okay, cool. It's in the upper half. Okay, here is in the upper half or the lower half and so on. And you learn all to predict all of these junctions right here. And that's going to end up you with you having to predict less. Now, of course, you are constrained, you impose a very big prior on the class distribution, classes aren't independently anymore. Namely, if two classes here are in the same subtree, that means that they are going to be predicted, their predictions are going to be correlated because the path to them is the same partially. So how you arrange the classes here is very important. And there has been a lot of work in this. But as I said, this is rather a distraction right here. Hierarchical softmax is a way to solve this. However, they went with a different way right here. They went with this approach called negative sampling. Negative sampling has been, it's been very influential. Not only in word2vec, but negative sampling is one of the cornerstones of the current trend in self supervised learning and contrastive estimation and so on. So this all of this, you know, it pops up in unlikely ways in other fields. And it sort of, I'm not going to say it originated here, but definitely it was introduced into the popular deep learning world right here. So they say an alternative to hierarchical softmax is noise contrastive estimation. Okay, so in noise contrastive estimation posits that a good model should be able to differentiate data from noise by means of logistic regression. You know, that seems very reasonable. This is similar to the hinge loss and so on, yada yada yada. While NCE can be shown to approximately maximize the log probability of the softmax, the skip grab model is only concerned with learning high quality vector representations. So we are free to simplify noise contrastive estimation as long as the vector representations retain their quality. We define negative sampling by this following objective. So this is very interesting. They see, okay, noise contrastive estimation, you know, it approximately maximizes the log probability. So the noise contrastive estimation would actually be the correct way to approximate their problem. However, they say, well, as long as, you know, as long as something reasonable comes out, we're free to change that up a bit. So they go with this negative sampling approach right here. And you can see that this is almost the same. So it's written a bit differently from the original softmax thing because the original softmax thing was written as a fraction and here it's as a sum. But what you're trying to do in the negative sampling framework is you're trying to maximize the following. You're trying to maximize the inner product of the word you're considering and the words around them. Okay. So you're trying to still predict the words around you. But now instead of having this prediction softmax over all of the classes, you only have the softmax over a subset of classes. So what you'll do is you sample words from your vocabulary at random and you sample k of them and you're simply trying to now minimize the inner product between those words and your word. Okay. So what does that ultimately lead to? It ultimately leads to the following. You have a word like this word here, negative. And what you're trying to do is you're not trying that much to predict the word sampling. What you're trying to do is you're trying to say that in my space right here, I simply want sampling to be closer than any other words that's not in the context window. Okay. So here is my word negative and here is my word sampling. And I want these two to be close. And if I sample another word, like here, this is the word cake. If I, sorry, if I sample that, I simply want that to be far away, farther than the word sampling. Okay. So this is now a comparative. It's not I classify sampling as the highest class. It's simply I want to classify the word sampling against the other classes higher. All right. So, and this is now much, much easier. So instead of a thousand or 10,000 or a million way classification, I now maybe have, I have a K plus one way classification, right? Pretty easy, right? I simply sample K other words. And I assume because I have so many words, chances that I actually sample one that's in my context window is very small, right? So I simply sample other words and I say, well, these other words are random. They have nothing to do with the current frame that I'm looking at. So they should be, you know, they can be whatever they want, but at least they should be farther away than the words that are actually in my con in my context. And that is negative sampling, the process of sampling negatives, this right here, and then making sure that the positives, which are these here, um, in this case, the words in the context are classified with a higher probability than the negatives for a given input word, right? This here is the input word. That's it. That's negative sampling. And of course, yeah, as I said, you recognize this from current things like, um, self supervised learning where you want to have the same image augmented twice, go through the pipeline, you know, you augment, you put a little bit of different noise and then you have a different image and at the end you say these two should be close together while this other one should be far apart. It's the exact same thing here, except that you have a different way of obtaining the positive and the negative samples. In this case, positive samples are everything that's in the context. Negative samples are just randomly sampled from the dataset. And that, you know, works, of course that works much, much, much faster. And you can see that this, um, this, uh, turns out to give you vectors that are pretty good and you can train with higher vectors, sorry, with higher dimensional vectors, you can train with bigger vocabularies with this. This has turned out to be very, very influential. As I said, uh, now with the rise of BERT and so on, work to back is kind of getting forgotten, but, um, this was a revolution and distributed vectors. So it wasn't a thing really. It kind of was a thing before that, but it wasn't really a thing that people used. What people would do is still, they would do N-gram models before that. So they would kind of dist, dist, they would sort of chunk up their sentences into N-grams into overlapping N-grams and then have a big giant, uh, table for their, where they index their N-grams. So the word, I don't know, so the word, um, hello is ID one. The word hello there is ID two and so on. So you have a big table for all the N-grams. And then what we would try to do is you would try to do this kind of bag of words estimation where you would take a, you know, whatever N-grams appeared in your sentence and you would have this big classification where you'd associate the N-grams with each other and so on. So distributed word representations were kind of a revolution at that point, especially distributed representation that actually outperformed these old N-gram methods. Um, yeah. So there are a number of tricks right here that are, I think, not understood until this day. For example, the question is how do you sample these negative samples? Right here, this basically says get K words from your vocabulary at random according to this distribution right here. Now how are you going to do that? Basically you have a spectrum of options. The one side of the spectrum is going to be completely uniform. Okay. We sample each word with the same probability. And the other side of the spectrum is something like sample this according to their uni-gram. These are two different things. They're opposites in this, in this fashion. So here you say, Hey, um, some words appear way, way, way more often than other words. Shouldn't we prefer them when we sample? Right? So if we have a corpus, um, and shouldn't we sample from the corpus? And if in the corpus, one word appears 50 times more than the other word, then shouldn't we sample that 50 times more as a negative because it's, you know, so abundant and it should give a higher classification accuracy. Whereas on the other hand, you could say, no, no, no, we should simply sample every word in our dictionary uniformly. They came up with something in between, which they say, um, both NCE and negative sampling have noise distribution as a free parameter. We investigated a number of choices and found that the uni-gram distribution raised to the three quarter power, i.e. uni-gram to the three quarter, outperformed significantly the uni-gram and uniform distributions. For both NCE and negative on every task we tried including language modeling. This I think is a mystery until today. And it actually turned out that this exponent right here is magically much better than like the exponent of one or even the exponent of one half. Like you might be reasonably assumed that the square root, you know, might be something, but the three quarters I think turned out to be very good and very mystical. So what does it mean? It means that you have kind of a balance between words that appear often and words that don't appear often. Usually in these kind of things, you have a power law where you have very few words that appear very often. And then you have, okay, that's the tail shouldn't go up, but you have a very long tail of words. And what you want to do is in this case, you want to sample these words here more, but they appear so much more often than if you simply sample according to their uni-gram distribution, you'll basically not regard these words right here, you'll forget about them and your performance will suffer because they do appear every now and then. So what you want to do is you want to push that those down a little bit and the optimal amount for the little bit turns out to be to raise it the you raise it to the three quarters. Strange but you know, turned out to work well. The other thing they do is they do the they do a sub sampling of frequent words. So again, this is a way to kind of push down the often appearing words where they say the most frequent words can easily occur hundreds of millions of times like in the or a such words usually provide less information value than the rare words. For example, while the skipgram model benefits from observing the co-occurrences of France and Paris, it benefits much less from observing the frequent co-occurrences of France and the as nearly every word co-occurring frequently with in a sentence with the. So they do another trick here to counter this imbalance between rare and frequent words use a simple sub sampling approach, each word in the training set is discarded with probability computed by that formula. Right, so therefore formula right here and you might be asking again why why this formula? So this is the sampling probability of a word and it goes with one over T. T is a temperature parameter and F is the frequency with which the word appears in the corpus. So as you can see, as the word appears more in the in the corpus, then so this is the frequency as the word appears more than this thing goes down than this thing goes up. So it's discarded with this probability. So it's discarded with a higher probability if it appears more often. Where F is frequency of a word, T is a chosen threshold. We chose this sub sampling formula because it aggressively sub samples words whose frequency is greater than T while preserving the ranking of the frequencies. Although this sub sampling formula was chosen heuristically, we found it to work well in practice. It accelerates learning and even significantly improves the accuracy of the learned vectors of the rare words as will be shown in the following sections. So again, something sort of arbitrary, it's more understandable than the three quarters, but still it's sort of arbitrary. They experimented around, they found this works well and then everybody ended up using that. So that's how this kind of stuff happens. Okay, so now we get into the empirical results. And the empirical results in this case were already sort of given in the previous paper, but here they have these the analogical reasoning task where you can see that the negative sampling did outperform the others by quite a bit right here. So the negative sampling approaches outperformed the hierarchical softmax and the noise contrastive estimation. And in the previous paper, they also compared with other baselines and saw that it also outperforms those while being quite time efficient. So you can see that especially with the sub sampling approaches, the time here is 36 minutes for and I think they have like a huge corpus that they train on these were to back code turned out to be really, really efficient code. And that's why it got so popular as well. They did the same thing for phrases right here. So for phrases like New York Times and so on, but this was kind of more of a this was more of a side thing. The phrase vectors turned out to be, you know, rather a side thing from the actual code right here. So yeah, as I said, this paper is very different from other research papers in that it's it's sort of half an engineering paper and all of these papers are they're kind of hard to read because they just kind of state some things in the order is kind of weird sometimes. Why they do things is kind of weird sometimes. But you can't you know, you can't deny that it had the quite the effect on the community. And this it is a very cool paper, very cool series of papers. And it's very cool that actually, they released the code, and they made the code such that it is super duper efficient, even like on a single machine. And that was very cool, because you know, being Google, they could have just released code that is very efficient on a distributed data center. And they didn't do that. So that this is, it's sort of not really like today anymore. Like today, when they release code, it's always you need you need like 50 cloud TPUs to do it. And it's still cool that they release code. But this was this was really a step into kind of democratizing AI. And yeah, so that was my rant about Word2vec. I hope you enjoyed this. I hope this still was useful to you, even though most of you probably already knew Word2vec. And yeah, so I'll see you next time. Bye bye.
 Hi there, today we'll look at distributed representations of words and phrases and their
 compositionality by Thomas Mikolov, Ilya Sotskyver, Kai Chen, Greg Corrado and Jeffrey Dean.
 This is another historical paper, it's one of three papers, it's the middle one that
 introduces the original Word2vec algorithm.
 And as you might know, Word2vec was extremely influential in NLP since this paper basically
 until recently, where it's sort of gone out of fashion a bit in research with the rise
 of things like ELMo and BERT, but it's still very, very relevant.
 So we'll look at this historical paper today with kind of the hindsight of being a couple
 years into the future.
 In fact, as you see right here, this was released in 2013, so it's seven years later now.
 And we'll look back and we'll see what they said back then about the system.
 This is not going to be like a very well-enhanced PowerPoint presentation of how Word2vec works.
 We're going to look at the paper and read it together.
 If you like content like this, if you like historical paper readings, let me know in
 the comments, share it out if you do like it and of course subscribe.
 Because this kind of historical papers, I enjoy them, but many people might already
 know what these things are.
 So, yeah.
 Okay.
 Let's, you know, go through the paper and pick up their ideas and kind of put them in
 context.
 They say the recently introduced continuous skip gram model is an efficient method for
 learning high quality distributed vector representations that capture a large number of precise syntactic
 and semantic word relationships.
 So the skip gram model was already introduced by Mikhailov in an earlier paper that came
 out, I believe not like one or two months prior to this one.
 As I said, Word2vec is a series of papers.
 I don't think there is a paper called Word2vec.
 Rather, they here have released the code along with the paper.
 The code was called Word2vec.
 So the skip gram model was introduced previously, but it is replicated right here.
 So in the skip gram model, what you're trying to do is you're trying to get a distributed
 word representation.
 So what does that mean?
 That means that for each word in your language, let's take these words right here.
 For each word in the language, you want to come up with a vector that somehow describes
 that word in a continuous fashion.
 So with the two might be mapped to, I don't know, 0.1, 0.9, and 0.3.
 Learn might be mapped to negative 0.5 and so on.
 So each word gets assigned a vector in the same dimensional space.
 And what the previous paper kind of discovered is that if you do this correctly, then these
 vectors, they have some kind of properties.
 So we can already kind of jump ahead because this was already a bit, a bit researched in
 the last paper.
 The semantics of these vectors will be something like this.
 So here they have a two dimensional PCA.
 So these are the first two dimensions of the 1000 dimensional skip gram vector.
 So the vectors they obtain, they can do things like this, where they can show that in these
 spaces, for example, there appears to be a vector direction that characterizes the capital
 of a country.
 So if you take a few countries and their capitals and you average that vector, you get a kind
 of a direction for capitalness of a city.
 Given a country, you can see that there is a pretty clear relation here.
 Now, some of these things have later been revised to such that they are ultimately ended
 up being not that impressive.
 For example, there was always this kind of math with vectors.
 And I don't, I believe this is, this might not be in this.
 This is in the last paper where they discovered that if you take the vector for king and you
 subtract the vector for man and you add the vector for woman, then that would result in
 the vector for queen.
 So the way they did it was basically they did this calculation right here and then they
 searched in the point they ended up, they searched for the nearest neighbor in their
 vocabulary.
 And that turned out to be queen.
 But in order to make it queen, actually, you have to exclude the original word king.
 People quickly discovered that if you don't exclude the original word, the result of this
 kind of arithmetic will almost always lead back to the original word.
 And then a lot of these analogy tasks are simply the result of you then discarding that
 word during the nearest neighbor search.
 And then queen just happens to be one of the closest words.
 And it's sort of much less dependent on which exact calculation you do here.
 So there's been a lot of follow up work kind of analyzing, criticizing these vector maths.
 But definitely we know that these word vectors turned out to be extremely, extremely helpful
 and syntactically and semantically relevant in downstream tasks because they have performed
 very, very well.
 So how does the skip gram model work?
 How does it assign vectors to each word?
 So first of all, it has a dictionary.
 So there is a word, an input word.
 And for each word, you have a big dictionary.
 And the big dictionary basically says that the word two is going to be mapped to this
 vector point one, da, da, da, da, da, da, and so on.
 The word learn is going to be mapped to that vector.
 And then you also have these output vectors right here.
 And what you're trying to do is you're trying to take a phrase from the data set like this
 one right here.
 And you take out one word like this word vector right here.
 And you're trying to frame this as a prediction task.
 So you're trying to frame this as, in this case, four different prediction tasks.
 So you're telling your machine, I give you the word vector, and which other words are
 around the word vector?
 You just tell it that you don't tell it anything else.
 You just say, which other words are around the word vector?
 And the correct answers in this case would be to, learn, word, and representations.
 So you construct four different training examples where you have an X and a Y.
 So the X is always vector, and the Y is two.
 And then the next training sample, the X is vector, and the Y is learn, and so on.
 So this here, each training sample is a classification task.
 And the classification task is, as you can see, no, you can't see right here, but the
 classification task is you have the input word, and you classify it into one of many,
 many, many, many, many, many classes.
 Namely, there are as many classes as you have words in the dictionary.
 So each word in the dictionary will have a class associated with it.
 So in ImageNet, you have like 1,000 classes, but in these, that's already a lot.
 But in these tasks, you're going to have 100,000 classes, because there are 100,000 words in
 the English language that you want to treat.
 There are many more, but in this case, they leave away all the words that appear less
 than five times in their corpus.
 That's still a lot of words.
 So it's like a super duper duper lot of classification task.
 But ultimately, if you do something like this, then the origin, so the representation that
 you end up with is going to be very, very good at doing these kind of downstream tasks.
 And that's what they discovered.
 So their skip gram model is nothing else than taking a word and predicting the surrounding
 words from that word.
 And this is what it means.
 This is the formal statement of the skip gram objective.
 What you want to do is the objective of the skip gram model is to maximize the average
 log probability this one.
 So for the word we're considering, the word T, we want to maximize the log probability
 of each word w that is in around the word c, sorry, around the word w in a context window
 of c.
 That's exactly what we did before.
 Take a word like this model right here.
 And from it, we predict all of the words around it in a given window.
 That's all.
 That's the entire objective.
 And that will give you very good representations.
 And this is how you would implement that.
 So what you'll have is you'll have these vector representation v that comes from your original
 dictionary.
 Those are the things you learn.
 And then because you have like a 30,000 way classifier, you know that a classification
 layer is nothing else than a linear layer followed by a softmax operation.
 And that linear layer also has parameters.
 These are the v primes.
 So first you have the look up in the dictionary for the word vector right here.
 And this is the vector of the classification layer.
 Now there are modifications where you can use like the same vectors and so on.
 Or you can also make use of these vectors.
 But ultimately, you care about these vectors right here.
 And the vectors here are simply the classification layers weights.
 So here you can see that there is what you're trying to maximize is the inner product between
 the word that you're considering and the words around that word.
 And you're trying to do a classification task.
 So you need to normalize.
 Now this is the normalization constant, and it goes over all of your vocabulary.
 So that's what they tackle here.
 They say w is the number of words in the vocabulary.
 This formulation is impractical because the cost of computing the gradient is proportional
 to w, which is often large.
 And that's 10 to the five to 10 to the seven terms.
 So many like tens of millions of terms in your vocabulary.
 That's just not feasible.
 So people have been sort of trying different ways to get around very, very large number
 of classes.
 And here it seems that that is really our bottleneck.
 In the previous paper, they've already shown that this objective can give you very good
 word representation.
 But now we need to get around the fact that we have such large vocabularies.
 So the first idea here is hierarchical softmax.
 And this is kind of a tangent.
 I find this paper, by the way, it's sort of hard to read because it's like a half engineering
 paper.
 But yeah, so first they introduce this hierarchical softmax, which is kind of a distraction.
 It's kind of a here is what we do.
 Here is what we considered first, but then didn't end up using really.
 They do compare with it, but the flow of text is sort of that you expect this to be part
 of the final model, which it isn't.
 So in the hierarchical softmax, what you do instead of having this giant multi class classification
 task right here, you take all of these classes right here, and you put them in a sort of
 a tree.
 Okay, so you take this and you put them into a tree.
 So instead of classifying, you know, let's say we have 1000 classes, instead of classifying
 1000 ways, we first classify in two ways.
 And then we classify in two ways again, from each one, and then we classify in two ways
 again, as you know, 1000 is like two to the 10.
 So we need approximately 10 layers of this before we are actually arriving at 1000 classes.
 But it also means that we only have two way classifications each time.
 So in the hierarchical softmax, we build trees like this, and then we so we have a word,
 we look up its vector, sorry, its vector, and then we classify it for each of these
 nodes.
 So your output isn't going to be 1000, 1000 log probabilities, your output is going to
 be a log probability, a binary log probability for each of the nodes right here.
 So you want to know, okay, here, is it in the upper half or the lower half of my classes?
 Okay, cool.
 It's in the upper half.
 Okay, here is in the upper half or the lower half and so on.
 And you learn all to predict all of these junctions right here.
 And that's going to end up you with you having to predict less.
 Now, of course, you are constrained, you impose a very big prior on the class distribution,
 classes aren't independently anymore.
 Namely, if two classes here are in the same subtree, that means that they are going to
 be predicted, their predictions are going to be correlated because the path to them
 is the same partially.
 So how you arrange the classes here is very important.
 And there has been a lot of work in this.
 But as I said, this is rather a distraction right here.
 Hierarchical softmax is a way to solve this.
 However, they went with a different way right here.
 They went with this approach called negative sampling.
 Negative sampling has been, it's been very influential.
 Not only in word2vec, but negative sampling is one of the cornerstones of the current
 trend in self supervised learning and contrastive estimation and so on.
 So this all of this, you know, it pops up in unlikely ways in other fields.
 And it sort of, I'm not going to say it originated here, but definitely it was introduced into
 the popular deep learning world right here.
 So they say an alternative to hierarchical softmax is noise contrastive estimation.
 Okay, so in noise contrastive estimation posits that a good model should be able to differentiate
 data from noise by means of logistic regression.
 You know, that seems very reasonable.
 This is similar to the hinge loss and so on, yada yada yada.
 While NCE can be shown to approximately maximize the log probability of the softmax, the skip
 grab model is only concerned with learning high quality vector representations.
 So we are free to simplify noise contrastive estimation as long as the vector representations
 retain their quality.
 We define negative sampling by this following objective.
 So this is very interesting.
 They see, okay, noise contrastive estimation, you know, it approximately maximizes the log
 probability.
 So the noise contrastive estimation would actually be the correct way to approximate
 their problem.
 However, they say, well, as long as, you know, as long as something reasonable comes out,
 we're free to change that up a bit.
 So they go with this negative sampling approach right here.
 And you can see that this is almost the same.
 So it's written a bit differently from the original softmax thing because the original
 softmax thing was written as a fraction and here it's as a sum.
 But what you're trying to do in the negative sampling framework is you're trying to maximize
 the following.
 You're trying to maximize the inner product of the word you're considering and the words
 around them.
 Okay.
 So you're trying to still predict the words around you.
 But now instead of having this prediction softmax over all of the classes, you only
 have the softmax over a subset of classes.
 So what you'll do is you sample words from your vocabulary at random and you sample k
 of them and you're simply trying to now minimize the inner product between those words and
 your word.
 Okay.
 So what does that ultimately lead to?
 It ultimately leads to the following.
 You have a word like this word here, negative.
 And what you're trying to do is you're not trying that much to predict the word sampling.
 What you're trying to do is you're trying to say that in my space right here, I simply
 want sampling to be closer than any other words that's not in the context window.
 Okay.
 So here is my word negative and here is my word sampling.
 And I want these two to be close.
 And if I sample another word, like here, this is the word cake.
 If I, sorry, if I sample that, I simply want that to be far away, farther than the word
 sampling.
 Okay.
 So this is now a comparative.
 It's not I classify sampling as the highest class.
 It's simply I want to classify the word sampling against the other classes higher.
 All right.
 So, and this is now much, much easier.
 So instead of a thousand or 10,000 or a million way classification, I now maybe have, I have
 a K plus one way classification, right?
 Pretty easy, right?
 I simply sample K other words.
 And I assume because I have so many words, chances that I actually sample one that's
 in my context window is very small, right?
 So I simply sample other words and I say, well, these other words are random.
 They have nothing to do with the current frame that I'm looking at.
 So they should be, you know, they can be whatever they want, but at least they should be farther
 away than the words that are actually in my con in my context.
 And that is negative sampling, the process of sampling negatives, this right here, and
 then making sure that the positives, which are these here, um, in this case, the words
 in the context are classified with a higher probability than the negatives for a given
 input word, right?
 This here is the input word.
 That's it.
 That's negative sampling.
 And of course, yeah, as I said, you recognize this from current things like, um, self supervised
 learning where you want to have the same image augmented twice, go through the pipeline,
 you know, you augment, you put a little bit of different noise and then you have a different
 image and at the end you say these two should be close together while this other one should
 be far apart.
 It's the exact same thing here, except that you have a different way of obtaining the
 positive and the negative samples.
 In this case, positive samples are everything that's in the context.
 Negative samples are just randomly sampled from the dataset.
 And that, you know, works, of course that works much, much, much faster.
 And you can see that this, um, this, uh, turns out to give you vectors that are pretty good
 and you can train with higher vectors, sorry, with higher dimensional vectors, you can train
 with bigger vocabularies with this.
 This has turned out to be very, very influential.
 As I said, uh, now with the rise of BERT and so on, work to back is kind of getting forgotten,
 but, um, this was a revolution and distributed vectors.
 So it wasn't a thing really.
 It kind of was a thing before that, but it wasn't really a thing that people used.
 What people would do is still, they would do N-gram models before that.
 So they would kind of dist, dist, they would sort of chunk up their sentences into N-grams
 into overlapping N-grams and then have a big giant, uh, table for their, where they index
 their N-grams.
 So the word, I don't know, so the word, um, hello is ID one.
 The word hello there is ID two and so on.
 So you have a big table for all the N-grams.
 And then what we would try to do is you would try to do this kind of bag of words estimation
 where you would take a, you know, whatever N-grams appeared in your sentence and you
 would have this big classification where you'd associate the N-grams with each other and
 so on.
 So distributed word representations were kind of a revolution at that point, especially
 distributed representation that actually outperformed these old N-gram methods.
 Um, yeah.
 So there are a number of tricks right here that are, I think, not understood until this
 day.
 For example, the question is how do you sample these negative samples?
 Right here, this basically says get K words from your vocabulary at random according to
 this distribution right here.
 Now how are you going to do that?
 Basically you have a spectrum of options.
 The one side of the spectrum is going to be completely uniform.
 Okay.
 We sample each word with the same probability.
 And the other side of the spectrum is something like sample this according to their uni-gram.
 These are two different things.
 They're opposites in this, in this fashion.
 So here you say, Hey, um, some words appear way, way, way more often than other words.
 Shouldn't we prefer them when we sample?
 Right?
 So if we have a corpus, um, and shouldn't we sample from the corpus?
 And if in the corpus, one word appears 50 times more than the other word, then shouldn't
 we sample that 50 times more as a negative because it's, you know, so abundant and it
 should give a higher classification accuracy.
 Whereas on the other hand, you could say, no, no, no, we should simply sample every
 word in our dictionary uniformly.
 They came up with something in between, which they say, um, both NCE and negative sampling
 have noise distribution as a free parameter.
 We investigated a number of choices and found that the uni-gram distribution raised to the
 three quarter power, i.e. uni-gram to the three quarter, outperformed significantly
 the uni-gram and uniform distributions.
 For both NCE and negative on every task we tried including language modeling.
 This I think is a mystery until today.
 And it actually turned out that this exponent right here is magically much better than like
 the exponent of one or even the exponent of one half.
 Like you might be reasonably assumed that the square root, you know, might be something,
 but the three quarters I think turned out to be very good and very mystical.
 So what does it mean?
 It means that you have kind of a balance between words that appear often and words that don't
 appear often.
 Usually in these kind of things, you have a power law where you have very few words
 that appear very often.
 And then you have, okay, that's the tail shouldn't go up, but you have a very long tail of words.
 And what you want to do is in this case, you want to sample these words here more, but
 they appear so much more often than if you simply sample according to their uni-gram
 distribution, you'll basically not regard these words right here, you'll forget about
 them and your performance will suffer because they do appear every now and then.
 So what you want to do is you want to push that those down a little bit and the optimal
 amount for the little bit turns out to be to raise it the you raise it to the three
 quarters.
 Strange but you know, turned out to work well.
 The other thing they do is they do the they do a sub sampling of frequent words.
 So again, this is a way to kind of push down the often appearing words where they say the
 most frequent words can easily occur hundreds of millions of times like in the or a such
 words usually provide less information value than the rare words.
 For example, while the skipgram model benefits from observing the co-occurrences of France
 and Paris, it benefits much less from observing the frequent co-occurrences of France and
 the as nearly every word co-occurring frequently with in a sentence with the.
 So they do another trick here to counter this imbalance between rare and frequent words
 use a simple sub sampling approach, each word in the training set is discarded with probability
 computed by that formula.
 Right, so therefore formula right here and you might be asking again why why this formula?
 So this is the sampling probability of a word and it goes with one over T. T is a temperature
 parameter and F is the frequency with which the word appears in the corpus.
 So as you can see, as the word appears more in the in the corpus, then so this is the
 frequency as the word appears more than this thing goes down than this thing goes up.
 So it's discarded with this probability.
 So it's discarded with a higher probability if it appears more often.
 Where F is frequency of a word, T is a chosen threshold.
 We chose this sub sampling formula because it aggressively sub samples words whose frequency
 is greater than T while preserving the ranking of the frequencies.
 Although this sub sampling formula was chosen heuristically, we found it to work well in
 practice.
 It accelerates learning and even significantly improves the accuracy of the learned vectors
 of the rare words as will be shown in the following sections.
 So again, something sort of arbitrary, it's more understandable than the three quarters,
 but still it's sort of arbitrary.
 They experimented around, they found this works well and then everybody ended up using
 that.
 So that's how this kind of stuff happens.
 Okay, so now we get into the empirical results.
 And the empirical results in this case were already sort of given in the previous paper,
 but here they have these the analogical reasoning task where you can see that the negative sampling
 did outperform the others by quite a bit right here.
 So the negative sampling approaches outperformed the hierarchical softmax and the noise contrastive
 estimation.
 And in the previous paper, they also compared with other baselines and saw that it also
 outperforms those while being quite time efficient.
 So you can see that especially with the sub sampling approaches, the time here is 36 minutes
 for and I think they have like a huge corpus that they train on these were to back code
 turned out to be really, really efficient code.
 And that's why it got so popular as well.
 They did the same thing for phrases right here.
 So for phrases like New York Times and so on, but this was kind of more of a this was
 more of a side thing.
 The phrase vectors turned out to be, you know, rather a side thing from the actual code right
 here.
 So yeah, as I said, this paper is very different from other research papers in that it's it's
 sort of half an engineering paper and all of these papers are they're kind of hard to
 read because they just kind of state some things in the order is kind of weird sometimes.
 Why they do things is kind of weird sometimes.
 But you can't you know, you can't deny that it had the quite the effect on the community.
 And this it is a very cool paper, very cool series of papers.
 And it's very cool that actually, they released the code, and they made the code such that
 it is super duper efficient, even like on a single machine.
 And that was very cool, because you know, being Google, they could have just released
 code that is very efficient on a distributed data center.
 And they didn't do that.
 So that this is, it's sort of not really like today anymore.
 Like today, when they release code, it's always you need you need like 50 cloud TPUs to do
 it.
 And it's still cool that they release code.
 But this was this was really a step into kind of democratizing AI.
 And yeah, so that was my rant about Word2vec.
 I hope you enjoyed this.
 I hope this still was useful to you, even though most of you probably already knew Word2vec.
 And yeah, so I'll see you next time.
 Bye bye.