Can we learn short word vectors instead of counting long ones? Lec 7 · PDF pp. 16–18
The count-based vectors from Lecture 6 have one coordinate for every context word. With a vocabulary of 20,000 to 50,000 words, each vector is that long, and most of its entries are zero. Lecture 7 repeats the alternative: vectors with only 50 to 1000 numbers, most of them nonzero. These are dense vectors.
The slides give four reasons to want them. A short vector gives a later classifier fewer weights to tune. Dense vectors may carry over to new examples better than explicit counts. They can also treat synonyms sensibly: in a count vector, car and automobile are separate coordinates, so a word seen near car and a word seen near automobile do not look alike, even though we would like them to. The last reason is practical: dense vectors tend to work better.
The lecture lists three routes to dense vectors. This page follows the first one.
- Methods inspired by neural language models: word2vec, which has two variants called skip-gram and CBOW, and GloVe. GloVe is covered on the next page.
- Singular value decomposition (SVD): compress a count matrix directly. Latent semantic analysis (LSA) is a special case. The lecture names this route without developing it.
- Contextual embeddings: compute a separate vector for each appearance of a word, using its sentence. These come later in the course.
The idea behind word2vec: predict instead of count Lec 7 · PDF pp. 20–23
Word2vec produces one short, dense vector for each word type. The vector does not change with the sentence, so these are static embeddings. The slides name two training algorithms: skip-gram with negative sampling (SGNS) and continuous bag of words (CBOW). They develop only the first. Pretrained word2vec vectors are easy to download, which helped make the method popular. The sources are Mikolov et al. (2013a, 2013b).
Counting asks, “How often does each word appear near cherry?” Word2vec asks a different question and trains a classifier to answer it: is this word likely to show up near cherry?
We do not actually care about that yes-or-no task. What we want are the numbers the classifier learns while trying to get it right. Those learned weights become the word vectors.
Where do the training labels come from?
A classifier needs examples with correct answers. Here the running text supplies them. If a word appears near cherry in the corpus, that pair is a correct “yes” example. Nobody has to label anything by hand. Learning from labels that the data provides for itself is called self-supervision. The slide credits Bengio et al. (2003) and Collobert et al. (2011) for the idea.
The whole method fits in four steps:
- Treat a target word and a word that really appears near it as a positive example.
- Pick other words from the vocabulary at random to make negative examples.
- Train a logistic regression classifier to tell the two kinds of pair apart.
- Keep the learned weights as the embeddings.
Follow one sentence through the classifier Lec 7 · PDF pp. 24–29
Suppose the window reaches two words to each side of the target. The lecture uses this piece of training text, with the target apricot:
... lemon, a [tablespoon of apricot jam, a] pinch ...
c1 c2 w c3 c4
The four words inside the brackets are the context words \(c_1\) to \(c_4\). Each one forms a positive pair with the target: (apricot, tablespoon), (apricot, of), (apricot, jam), and (apricot, a). A word drawn at random, such as aardvark, gives a negative pair: (apricot, aardvark).
For any candidate pair \((w,c)\), the classifier outputs the probability that \(c\) really is a neighbor of \(w\). The two probabilities add to one:
Turn the similarity of two vectors into a probability Lec 7 · PDF pp. 30–31
The central idea is to base that probability on how similar the two words' vectors are. A word is likely to appear near the target if their vectors are similar. The classifier measures similarity with the dot product, written \(\mathbf{c}\cdot\mathbf{w}\). Here \(\mathbf{w}\) and \(\mathbf{c}\) are vectors, not single numbers.
A dot product can be any real number, so it is not yet a probability. Cosine similarity does not solve this either: cosine is a dot product divided by the two lengths, and it still is not a probability. The fix is the one used in logistic regression. Pass the score through the sigmoid, which squeezes any number into the range from 0 to 1:
This is exactly a logistic regression classifier. The difference is where the numbers come from. In Lecture 4 the features were fixed and only the weights were learned. Here both vectors in the dot product are learned.
A window has several context words Lec 7 · PDF pp. 32–33
The formula above handles one context word. A window contains \(L\) of them, and \(L\) depends on the window size. The model makes a simplifying assumption: the context words are independent of one another. Then the probabilities multiply, and taking logs turns the product into a sum:
The slide states the assumption and the product in words. The equations here follow the assigned reading, Jurafsky & Martin, Chapter 6. Negative context words are treated the same way.
So the skip-gram classifier takes a target word and a window of \(L\) context words. It estimates how likely that window is from how similar the target's vector is to each context vector. To compute any of this, all we need is a vector for every word.
Each word gets two vectors Lec 7 · PDF p. 34
The model keeps separate representations for the two roles a word can play. A word has one vector for when it is the target and another for when it is a context word. The target vectors form a matrix \(W\) and the context vectors form a matrix \(C\). With a vocabulary of \(|V|\) words, the model stores \(2|V|\) vectors, each of length \(d\).
Build the training examples Lec 7 · PDF p. 36
Every positive pair is matched with a set of negative pairs. The negative words are sampled at random, weighted by their unigram frequency. The slide shows these examples for the target apricot:
| Positive examples \((w, c)\) | Negative examples \((w, c_{neg})\) |
|---|---|
| apricot, tablespoon | apricot, aardvark |
| apricot, of | apricot, zebra |
| apricot, jam | apricot, where |
| apricot, a | apricot, adversarial |
The number of negatives drawn for each positive pair is a setting we choose. The loss slide writes it as \(k\); the later comparison slide writes it as \(K\).
The slide says only that sampling is weighted. Jurafsky & Martin, Chapter 6, give the usual formula. Each word's count is raised to a power \(\alpha\), commonly \(0.75\), before the counts are turned into probabilities:
\[ P_\alpha(w)=\frac{\operatorname{count}(w)^{\alpha}}{\sum_{w'}\operatorname{count}(w')^{\alpha}} \]A power below one gives rare words a slightly better chance of being picked. Suppose two words have probabilities \(0.99\) and \(0.01\). With \(\alpha=0.75\) they become about \(0.97\) and \(0.03\). Lecture 7 p. 56 lists this weight among word2vec's hyperparameters.
What training is trying to achieve Lec 7 · PDF pp. 37–38
Training starts with the positive and negative pairs and with \(2|V|\) randomly initialized vectors. It then adjusts the vectors toward two goals:
- Make the target vector more similar to the vectors of words that really appeared in its window.
- Make the target vector less similar to the vectors of the sampled negative words.
For one positive pair and its \(k\) negatives, we want the classifier to say “yes” to the real neighbor and “no” to every sampled word. Assuming these decisions are independent, the probability of getting all of them right is a product. The loss is the negative log of that product, which is the cross-entropy loss again:
The first term is small when the target and its real neighbor have a large dot product. Each term in the sum is small when the target and a sampled word have a small or negative dot product. Minimizing the loss therefore pushes toward both goals at once. The total loss adds this quantity over every target and context pair in the corpus.
Adjust the vectors with gradient descent Lec 7 · PDF pp. 39–43
The vectors are learned with stochastic gradient descent. Start from random values. For each training example, compute the gradient of the loss with respect to the parameters, then move a small step in the opposite direction. The learning rate \(\eta\) sets the step size, and a higher rate moves the vectors faster. Stop when the parameters, or the loss, no longer change much. Over the whole training set, the positive pairs become more likely and the negative pairs less likely.
One training example touches three kinds of parameter: the context vector of the positive word, the context vector of each negative word, and the target vector. Their gradients are:
These have the same shape as the logistic regression gradient, (predicted probability − correct label) × input. A positive pair has label 1, which gives \(\sigma-1\). A negative pair has label 0, which gives \(\sigma\) alone. Moving from step \(t\) to step \(t+1\):
Look at the signs. Because \(\sigma-1\) is negative, the update adds a little of \(\mathbf{w}\) to the positive context vector, which pulls the two together. Because \(\sigma\) is positive, the update subtracts a little of \(\mathbf{w}\) from each negative context vector, which pushes them apart. The slide's picture of one step shows the same thing: apricot moves toward jam and away from the sampled words.
Take two-dimensional vectors \(\mathbf{w}=[1,\,0.5]\), \(\mathbf{c}_{pos}=[0.5,\,1]\), and one negative \(\mathbf{c}_{neg}=[1,\,-0.5]\), with \(\eta=0.1\).
The dot products are \(\mathbf{c}_{pos}\cdot\mathbf{w}=1.0\) and \(\mathbf{c}_{neg}\cdot\mathbf{w}=0.75\). The classifier gives \(\sigma(1.0)\approx0.731\) for the real neighbor and \(\sigma(0.75)\approx0.679\) for the sampled word. The second value is too high for a negative pair. The loss is \(-[\log 0.731+\log(1-0.679)]\approx1.450\), using natural logs.
The update moves \(\mathbf{c}_{pos}\) to \([0.527,\,1.013]\), \(\mathbf{c}_{neg}\) to \([0.932,\,-0.534]\), and \(\mathbf{w}\) to \([0.946,\,0.561]\). Afterward the positive dot product rises to about \(1.067\) and the negative one falls to about \(0.582\). The loss drops to about \(1.322\). One step already moved both pairs in the right direction.
Which vectors do we keep? Lec 7 · PDF p. 44
Training produces two sets of embeddings, the target matrix \(W\) and the context matrix \(C\). The slide says it is common to add them, so word \(i\) is represented by \(\mathbf{w}_i+\mathbf{c}_i\).
- Word2vec learns short, dense, static vectors by training a classifier, then keeps the weights and discards the classifier.
- The text supplies its own labels. Real neighbors are positive pairs, and randomly sampled words are negative pairs.
- The classifier is logistic regression on a dot product: \(P(+\mid w,c)=\sigma(\mathbf{c}\cdot\mathbf{w})\). Both vectors are learned.
- The loss is cross-entropy over one positive pair and \(k\) negatives. Stochastic gradient descent pulls real neighbors together and pushes sampled pairs apart.
- Each word gets a target vector and a context vector. A common choice is to add them.