Exercises — Word embeddings (Word2Vec, GloVe)

(a) A one-hot vector has one slot per word, so its length is $|V|=50000$. All slots are $0$ except a single $1$. (b) An embedding vector has $d=300$ numbers — that is the whole point: dense and short. (c) The input embedding matrix has one row (or column) per word, each of length $d$: $|V|\times d=50000\times 300=15,000,000\text{ numbers.}$ So we replaced $50000$-long sparse vectors with $300$-long dense ones, at the cost of storing a $15$M-parameter lookup table.

(a) CBOW — Continuous Bag of Words takes context in, guesses the target. (b) Skip-gram — target in, guesses each context word. (c) CBOW — its hidden layer is $\mathbf{h}=\frac{1}{C}\sum {\mathbf{v}}_{w_{t+i}}$, an average. Skip-gram uses the single target vector with no averaging.

What: average the context vectors. Why: CBOW throws away word order and keeps only the "centre of mass" of the context, so one blended vector represents "the surroundings". $\mathbf{h}=\frac{1}{2}((1,3)+(3,1))=\frac{1}{2}(4,4)=(2,2).$

(a) Score = dot product = how aligned the candidate's output vector is with the context vector. ${\mathbf{u}}_{\text{sat}}^T\mathbf{h}=2\cdot 2+2\cdot 2=8,{\mathbf{u}}_{\text{ran}}^T\mathbf{h}=1\cdot 2+0\cdot 2=2,{\mathbf{u}}_{\text{mat}}^T\mathbf{h}=0\cdot 2+1\cdot 2=2.$ (b) Softmax: $P(w)=\frac{e^{s_w}}{{\sum }_k{e}^{s_k}}$. The denominator is $e^8+e^2+e^2=2980.96+7.389+7.389=2995.74$. $P(\text{sat})=\frac{2980.96}{2995.74}=0.9951,P(\text{ran})=P(\text{mat})=\frac{7.389}{2995.74}=\mathrm{0.00247.}$ (c) "sat" — because its output vector $(2,2)$ points exactly along $\mathbf{h}=(2,2)$, giving the biggest dot product, which softmax then amplifies into near-certainty.

Why sigmoid here, not softmax? Negative sampling reframes the task as a yes/no question — "is this pair real?" — so each pair needs one probability, and $\sigma$ turns one score into one probability. No $|V|$-sized sum needed.

• Real term: $\sigma (2)=\frac{1}{1+e^{-2}}=0.8808$, so $-\log (0.8808)=0.1269$.
• Negative term: $\sigma (-1)=\frac{1}{1+e^1}=0.2689$, so $-\log (0.2689)=1.3133$. $\mathcal{L}=0.1269+1.3133=\mathrm{1.4402.}$ The negative term is large because the model still thinks the fake pair looks somewhat real ($\sigma (-1)$ is not close to $1$) — that is exactly the mistake we are pushing down.

Cosine similarity: $\cos (\mathbf{x},\mathbf{y})=\frac{{\mathbf{x}}^T\mathbf{y}}{\Vert \mathbf{x}\Vert \Vert \mathbf{y}\Vert }$. Why cosine and not raw dot product? Frequent words tend to get long vectors; cosine divides that length out so only direction (meaning) is compared.

• $\mathbf{a}\cdot \mathbf{b}=3\cdot 6+4\cdot 8=50$, $\Vert \mathbf{a}\Vert =5$, $\Vert \mathbf{b}\Vert =10$, so $\cos =\frac{50}{50}=1$. Same direction $\Rightarrow$ identical meaning, even though $\mathbf{b}$ is twice as long.
• $\mathbf{a}\cdot \mathbf{c}=3\cdot (-4)+4\cdot 3=0$, so $\cos =0$. Orthogonal $\Rightarrow$ unrelated words. See figure below for the geometry.

• Ratio for "solid": $\frac{0.02}{0.001}=20$. Large — "solid" strongly distinguishes ice from steam (it belongs with ice).
• Ratio for "water": $\frac{0.03}{0.03}=1$. ≈1 — "water" relates to both equally, so it does not separate them. The point: raw probabilities are noisy, but the ratio cleanly answers "does this probe word tell ice and steam apart?" That is why GloVe fits vectors to log-co-occurrences rather than raw counts.

Without smoothing (exponent $1$): ratio $=\frac{1000}{10}=100$. "the" gets sampled $100\times$ more. With $0.75$: ratio $={\left(\frac{1000}{10}\right)}^{0.75}=100^{0.75}=10^{1.5}=31.62$. Raising to $0.75$ compresses the gap ($100\to 31.6$): common words are still sampled more, but rare words like "cat" get a fairer share of negative slots. Why not exponent $0$? That would sample every word equally and waste updates on words that never occur; $0.75$ is the empirical sweet spot between "sample by frequency" and "sample uniformly".

(a) Why subtract then add? "king$-$man" isolates the royalty minus maleness direction; adding "woman" re-injects femaleness — the arithmetic navigates meaning-space. $\mathbf{q}=(0.9-0.8+0.2,0.8-0.1+0.7)=(0.3,1.4).$ (b) $\mathbf{q}=(0.3,1.4)$ equals queen exactly, so $\cos (\mathbf{q},\text{queen})=1$. For prince: $\mathbf{q}\cdot \text{prince}=0.3\cdot 0.7+1.4\cdot 0.9=1.47$; $\Vert \mathbf{q}\Vert =\sqrt{0.09+1.96}=\sqrt{2.05}=1.4318$; $\Vert \text{prince}\Vert =\sqrt{0.49+0.81}=\sqrt{1.30}=1.1402$; $\cos =\frac{1.47}{1.4318\cdot 1.1402}=\frac{1.47}{1.6326}=0.9004$. Winner: queen ($1>0.90$). See figure.

• Full softmax: one score per vocabulary word $=|V|=65536$ dot products. $O(|V|)$.
• Hierarchical softmax: a balanced binary tree over $|V|$ leaves has depth ${\log }_2|V|={\log }_{2}65536=16$. So $16$ node-decisions. $O(\log |V|)$.
• Negative sampling: $1$ real $+k$ negatives $=1+10=11$ dot products. $O(k)$. Speed-up of negative sampling over full softmax: $65536/11\approx 5958\times$. This is why the parent note calls full softmax "expensive" — the denominator sum is the bottleneck.

What we require: we want $F({\mathbf{w}}_i^T{\tilde{\mathbf{w}}}_k-{\mathbf{w}}_i^T{\tilde{\mathbf{w}}}_j)=\frac{P_{ik}}{P_{ij}}$. Why a difference maps to a ratio: the left input is $a-b$ (a subtraction of scalars), the right output is $F(a)/F(b)$ (a division). We need one function that satisfies $F(a-b)=\frac{F(a)}{F(b)}\text{for all }a,b.$ Solve it. Set $b=0$: $F(a)=F(a)/F(0)$, forcing $F(0)=1$. Set $a=b$: $F(0)=F(a)/F(a)=1$, consistent. The unique continuous function turning subtraction into division is the exponential: $\exp (a-b)=e^a/e^b$. (Any $c^x$ works, but $c=e$ is the natural choice and rescales into the vectors anyway.) Finish. So $\exp ({\mathbf{w}}_i^T{\tilde{\mathbf{w}}}_j)\propto P_{ij}=X_{ij}/X_i$. Taking logs turns the product into the additive relation GloVe fits: ${\mathbf{w}}_i^T{\tilde{\mathbf{w}}}_j+b_i+{\tilde{b}}_j=\log X_{ij},$ where $\log X_i$ was absorbed into the bias $b_i$. This is why the log appears in the loss.

• $f(0)=(0/100{)}^{0.75}=0$. Degenerate but essential: pairs that never co-occur have $\log X_{ij}=\log 0=-\infty$; weight $0$ deletes that infinite term from the loss so training stays finite.
• $f(1)=(1/100{)}^{0.75}=(0.01{)}^{0.75}=0.03162$. A once-seen pair is noisy — weight is tiny.
• $f(50)=(0.5{)}^{0.75}=0.5946$. Moderate pair, moderate weight.
• $f(100)=(1{)}^{0.75}=1$. At the cap.
• $f(500)=1$ (since $500\ge x_{\max }$, the "otherwise" branch). Cap prevents dominance: without the cap, ultra-frequent pairs like ("of","the") would swamp the loss and drown out informative rare pairs. The three behaviours — $0$ at zero, rising for rare, flat-capped for frequent — are exactly the three cases the parent note lists.

Softmax probability of word $w$ is $P(w)=\frac{e^{{\mathbf{u}}_w^T\mathbf{h}}}{{\sum }_{k\in V}{e}^{{\mathbf{u}}_k^T\mathbf{h}}}$. The denominator is the same for all words, so probabilities differ only through the numerators. If ${\mathbf{u}}_a={\mathbf{u}}_b$ then ${\mathbf{u}}_a^T\mathbf{h}={\mathbf{u}}_b^T\mathbf{h}$ for every $\mathbf{h}$, hence $e^{{\mathbf{u}}_a^T\mathbf{h}}=e^{{\mathbf{u}}_b^T\mathbf{h}}$, giving $P(a)=P(b)$ always. $■$ Identifiability lesson: the model cannot tell $a$ and $b$ apart from any context — they are the "same word" to it. So distinct words must get distinct vectors; training is precisely the pressure that separates words appearing in different contexts. (This is the same identifiability issue transfer learning relies on when reusing a well-separated embedding table.)

CBOW averages context, Skip-gram fans out ::: both feed dot-product scores into softmax Cosine ignores length, dot product does not ::: cosine $=1$ synonyms, $0$ unrelated, $-1$ opposite Negative sampling cost vs full softmax ::: $O(k)$ instead of $O(|V|)$ GloVe fits vectors to ::: $\log$ of co-occurrence counts, weighted by $f(x)$