2 / 4 Natural Language Processing

Counting Output Vectors Per Pair

A skip-gram model is trained on a vocabulary of W=100,000W = 100{,}000 words with 300-dimensional vectors. The full softmax is

p(wO∣wI)=exp⁡(vwO′⊤vwI)∑w=1Wexp⁡(vw′⊤vwI)p(w_O \mid w_I) = \frac{\exp(v'^{\top}{w_O} v{w_I})}{\sum_{w=1}^{W} \exp(v'^{\top}{w} v{w_I})}

Negative sampling replaces it with a logistic objective over the observed pair plus k=5k = 5 noise words drawn from Pn(w)P_n(w).

For one (center word, context word) training pair, how many output vectors vw′v'_w does each objective touch, and what does that ratio buy?

A

100,000 in both cases: negative sampling changes only which words receive a positive or negative label, so every output vector is still touched on every pair.

B

100,000 against 6, a reduction of roughly 16,700x, because the denominator of the softmax has to be evaluated over the whole vocabulary while the sampled objective only scores the true pair and its 5 negatives.

C

100,000 against 5, a reduction of 20,000x: the observed pair costs nothing extra because its score is already computed as part of drawing the negatives.

D

About 17 against 6: the cost of the exact softmax is logarithmic in vocabulary size because the output layer is stored as a binary tree.