Dense vectors and the skip-gram classifier

One sentence says "she drove the car to work"; another says "he parked the automobile outside". In a count space, drove collects weight on the car dimension and parked collects weight on the automobile dimension. Those are two different coordinates. If those are their only informative neighbors, the dot product of the two verbs is exactly 0, so their cosine is 0 too, even though any reader sees that the two sentences describe the same kind of event.

Part 03 previewed this contrast on slide 30; here it gets its full argument. The vectors of the last three parts were sparse vectors. Built from a tf-idf or Pointwise mutual information weighting, they have one dimension per vocabulary word, so their length is |V|, typically 20,000 to 50,000, and nearly every entry is zero. A Dense vector is the opposite on every count. It has a small fixed number of dimensions d, usually between 50 and 1000; almost all of its entries are non-zero; and they are real numbers that can be negative. The price is interpretability: the d dimensions do not correspond to context words or to anything else nameable (SLP 5.5). Such a vector is still an Embedding, just a learned one rather than a counted one.

Three reasons dense vectors win

1. Fewer weights to learn. A classifier that uses one word as a feature needs one weight per dimension: 300 weights for a dense vector instead of 50,000 for a sparse one. Fewer parameters may generalize better and overfit less.
2. Better Synonymy. In a dense space, car and automobile can occupy nearby directions, so a word whose neighbors include car is automatically close to a word whose neighbors include automobile. The Cosine similarity of drove and parked is no longer forced to zero.
3. Empirically better. SLP states it bluntly: dense vectors work better in every NLP task than sparse vectors. The slide says the same more cautiously: in practice, they work better.

Suppose you need word vectors for a project tomorrow. You do not have to train anything. You can download the word2vec GoogleNews vectors, or one of the GloVe sets from Stanford, and have a dense vector for millions of words in a few minutes. Knowing where each set comes from tells you what it can and cannot do.

The lecture sorts dense vectors into three families. The first is inspired by neural language models: learn vectors by predicting words from their neighbors. Word2vec is the flagship, and it is a toolkit with two algorithms, Skip-gram (predict the neighbors from the word) and Continuous bag of words (predict the word from its neighbors). The slide also places GloVe here, which is a simplification noted below. The second family is factorization: take a count matrix and compress it with singular value decomposition. Latent semantic analysis (LSA) is SVD applied to a term-document matrix with the first 300 or so dimensions kept (Deerwester et al. 1990, in SLP's history section). The slide then presents contextual models such as ELMo and BERT as an alternative to these static embeddings. Both the SVD bullet and the contextual bullet are greyed out, because this lecture concentrates on word2vec.

The last column is the line that matters most. Word2vec, GloVe and LSA all produce a Static embedding: one fixed vector per word type, looked up from a table. The word bank gets the same vector in "river bank" and "bank loan", so Polysemy is averaged into a single point. A Contextual embedding is computed by running the whole sentence through a network, so each token occurrence gets its own vector (Peters et al. 2018; Devlin et al. 2019). Those models come later in the course; this lecture is about static vectors.

In practice you train your own vectors with gensim. Its defaults are worth memorizing because they bite: vector_size=100, window=5, negative=5 (the docs say usually between 5 and 20), ns_exponent=0.75, min_count=5, and sg=0, which means CBOW.

from gensim.models import Word2Vec
import gensim.downloader as api

model = Word2Vec(
    sentences=corpus,
    vector_size=300,
    window=5,
    sg=1,
    negative=5,
    min_count=5,
)

google_news = api.load("word2vec-google-news-300")
google_news.most_similar("automobile", topn=3)

Read the phrase "...a tablespoon of apricot jam...". Without anyone annotating anything, it hands you a labeled fact: (apricot, jam) is a yes, these two words occur near each other. Now pick a random word from the lexicon, say aardvark. (apricot, aardvark) is almost certainly a no. Every sentence of every book and web page produces such facts by the dozen.

That is the whole idea behind Skip-gram with negative sampling. Instead of counting how often a word c occurs near apricot, train a binary classifier on the question "is c likely to show up near apricot?" Nobody actually cares about that question. What we keep are the weights the classifier learns in order to answer it, and those weights are the embeddings. Because the gold answers come from running text rather than from people, this is Self-supervision.

The four-step recipe

1. Treat the target word and each neighboring context word as a positive example.
2. Randomly sample other words from the lexicon to make negative examples.
3. Train logistic regression to tell the two kinds of pair apart.
4. Throw the classifier away and use its learned weights as the embeddings.

The idea has a lineage. Bengio et al. (2003) and Collobert et al. (2011) had already shown that the next word in running text is a free supervision signal for learning word vectors, and Collobert et al. stressed the "vast amounts of mostly unlabeled training data" this unlocks. Word2vec simplifies their neural language models in two ways (SLP 5.5). It replaces the hard task of predicting the next word over the whole vocabulary with a yes-or-no question about a single pair, and it replaces a multi-layer network with plain logistic regression. The payoff was speed: Mikolov et al. (2013a) learned high quality vectors from a 1.6 billion word data set in less than a day.

The binary framing is also what keeps training cheap. The basic skip-gram formulation defines its probability with a softmax over the whole vocabulary, whose cost grows with W, "often large (10^5 to 10^7 terms)" (Mikolov et al. 2013b). Negative sampling replaces that sum with a handful of k sampled noise words, 5 to 20 for small data sets and 2 to 5 for large ones. How those negatives are drawn and how the weights are updated is the subject of the next part.

Take the running text "...lemon, a tablespoon of apricot jam, a pinch..." and put a window of two words on each side of apricot. The target is w = apricot, and the four context words are c1 = tablespoon, c2 = of, c3 = jam and c4 = a. Each one forms a positive training pair with the target.

A note on letters: the slides and SLP write L for the number of context words being scored, so a ±2 window has L = 4. Keep that in mind when you meet c_1:L in the last concept of this part. The half-width is written m throughout this lecture, so L = 2m. Try the window yourself: click any word to make it the target and change the half-width.

Once the pairs exist, the classifier's job is simple to state. Given a candidate pair (w, c), return the probability that c is a real context word of w. For (apricot, jam) that probability should be high; for (apricot, aardvark) it should be low. Since there are only two outcomes, the probability of the negative answer is whatever is left over:

Give apricot a toy three-dimensional vector w = (1, 0.5, -1). Give jam the context vector c = (2, 1, -0.5) and aardvark c = (-1, 0.5, 1). Multiply apricot by jam elementwise and add: 2 + 0.5 + 0.5 = 3. Do the same with aardvark: -1 + 0.25 - 1 = -1.75. The real neighbor scores high, the random word scores low. The question is how to turn those two scores into probabilities.

The intuition the classifier uses is the one from the cosine parts: two vectors are similar when their Dot product is high, and the Cosine similarity is just a dot product divided by the two vector lengths. So skip-gram takes the dot product c·w as its similarity score. But neither a dot product nor a cosine is a probability. Because embedding entries can be negative, the dot product can be anything from -∞ to ∞ (SLP 5.5.1).

Logistic regression already has the fix. The sigmoid function maps any real number into the open interval (0, 1), so the classifier passes the dot product through it:

The identity 1 - σ(x) = σ(-x) is worth checking once, because it is used constantly: the two cases always sum to 1, and flipping the sign of the score swaps them. A few anchor values make hand computation quick: σ(0) = 0.5, σ(2) = 0.8808, σ(-2) = 0.1192, σ(5) = 0.9933, σ(-5) = 0.0067.

One pair at a time is not enough: apricot has four neighbors in its ±2 window, and the classifier should score the whole window. Keep w = (1, 0.5, -1) and give each of the four context words a toy vector.

Skip-gram makes one simplifying move: it assumes the context words are independent of each other given the target. Under that assumption the probability that all of them are real neighbors is the product of the individual sigmoid probabilities, and its logarithm is a sum.

That last sentence hides a detail that sets up the next part. SLP's figure 5.6 shows that skip-gram stores two embeddings per word: one for when the word is a target and one for when it is a context. They live in a target matrix W and a context matrix C, the Target and context matrices, so the parameters are 2|V| vectors of dimension d. Learning those two matrices from positive and negative pairs is what part 8 is about.