How does Continuous Bag of Words ensure that similar words are encoded as similar embeddings?

Question

This is related to my earlier question, which I'm trying to break down into parts (this being the first). I'm reading notes on word vectors here. Specifically, I'm referring to section 4.2 on page 7. First, regarding points 1 to 6 - here's my understanding:

If we have a vocabulary $V$, the naive way to represent words in it would be via one-hot-encoding, or in other words, as basis vectors of $R^{|V|}$ - say $e_1, e_2,\ldots,e_{|V|}$. We want to map these to $\mathbb{R}^n$, via some linear transformation such that the images of similar words (more precisely, the images of basis vectors corresponding to similar words) have higher inner products. Assuming the matrix representation of the linear transformation given the standard basis of $\mathbb{R}^{|V|}$ is denoted by $\mathcal{V}$, then the "embedding" of the $i$-th vocab word (i.e. the image of the corresponding basis vector $e_i$ of $V$) is given by $\mathcal{V}e_i$.

Now suppose we have a context "The cat ____ over a", CBoW seeks to find a word that would fit into this context. Let the words "the", "cat", "over", "a" be denoted (in the space $V$) by $x_{i_1},x_{i_2},x_{i_3},x_{i_4}$ respectively. We take the image of their linear combination (in particular, their average): $$\hat v=\mathcal{V}\bigg(\frac{x_{i_1}+x_{i_2}+x_{i_3}+x_{i_4}}{4}\bigg)$$

We then map $\hat v$ back from $\mathbb{R}^n$ to $\mathbb{R}^{|V|}$ via another linear mapping whose matrix representation is $\mathcal{U}$: $$z=\mathcal{U}\hat v$$

Then we turn this score vector $z$ into softmax probabilities $\hat y=softmax(z)$ and compare it to the basis vector corresponding to the actual word, say $e_c$. For example, $e_c$ could be the basis vector corresponding to "jumped".

Here's my interpretation of what this procedure is trying to do: given a context, we're trying to learn maps $\mathcal{U}$ and $\mathcal{V}$ such that given a context like "the cat ____ over a", the model should give a high score to words like "jumped" or "leaped", etc. Not just that - but "similar" contexts should also give rise to high scores for "jumped", "leaped", etc. For example, given a context "that dog ____ above this" wherein "that", "dog", "above", "this" are represented by $x_{j_1},x_{j_2},x_{j_3},x_{j_4}$, let the image of their average be

$$\hat w=\mathcal{V}\bigg(\frac{x_{j_1}+x_{j_2}+x_{j_3}+x_{j_4}}{4}\bigg)$$

This gets mapped to a score vector $z'=\mathcal{U}\hat w$. Ideally, both score vectors $z$ and $z'$ should have similarly high magnitudes in their components corresponding to similar words "jumped" and "leaped".

Is my above understanding correct? Consider the following quote from the lectures:

We create two matrices, $\mathcal{V} \in \mathbb{R}^{n\times |V|}$ and $\mathcal{U} \in \mathbb{R}^{|V|\times n}$, where $n$ is an arbitrary size which defines the size of our embedding space. $\mathcal{V}$ is the input word matrix such that the $i$-th column of $\mathcal{V}$ is the $n$-dimensional embedded vector for word $w_i$ when it is an input to this model. We denote this $n\times 1$ vector as $v_i$. Similarly, $\mathcal{U}$ is the output word matrix. The $j$-th row of $\mathcal{U}$ is an $n$-dimensional embedded vector for word $w_j$ when it is an output of the model. We denote this row of $\mathcal{U}$ as $u_j$.

It's not obvious to me why $v_i=\mathcal{V}e_i$ should be the same as or even similar to $u_i$. How does the whole backpropagation procedure above ensure that?

Also, how does the procedure ensure that basis vectors corresponding to similar words $e_i$ and $e_j$ are mapped to vectors in $\mathbb{R}^n$ that have high inner product? (In other words, how is it ensured that if words no. $i_1$ and $i_2$ are similar, then $\langle v_{i_1}, v_{i_2}\rangle$ and $\langle u_{i_1}, u_{i_2}\rangle$ have high values?)

Answer 1

Unlike in skip-gram, the reason similar words have similar embeddings in CBOW is because the words show up in the same contexts of other skipped words.

lets assume two words $e_i$ and $e_j$ pop up in the exact same context of some word $e_k$ with 3 other context words as well. An example would be:

1. He leaped over the truck
2. He jumped over the truck

Where the italics represent the words with similar meanings but the bolded words above are the ones being predicted/skipped in CBOW. Lets now show this.

Let the rest of the context be denoted $\{e_r\}_r$ and the skipped word as $e_s$ and so the loss will try to minimize both $-e_s^T log(softmax(\mathcal{U}\mathcal{V}[\frac{1}{R+1}(e_i + \sum_re_r)]))$ and $-e_s^T log(softmax(\mathcal{U}\mathcal{V}[\frac{1}{R+1}(e_j + \sum_re_r)]))$.

Assuming a long run withlarge enough batch-size (so ignoring catastrophic forgetting) we can essentially say it will be minimizing
$$-e_s^T [log(softmax(\mathcal{U}\mathcal{V}[\frac{1}{R+1}(e_i + \sum_re_r)])) +\\ log(softmax(\mathcal{U}\mathcal{V}[\frac{1}{R+1}(e_j + \sum_re_r)]))]$$
Now let $\mathcal{U}\mathcal{V}\frac{1}{R+1}\sum_re_r$ be denoted as $c$, $\mathcal{U}\mathcal{V}\frac{1}{R+1}e_i$ as $\hat u_i$, and $\mathcal{U}\mathcal{V}\frac{1}{R+1}e_j$ as $\hat u_j$. So we have to minimize
$$-e_s^T[log(softmax(\hat u_i+c)) + log(softmax(\hat u_j+c))]$$
or equivalently
$$-e_s^T\ log(softmax(\hat u_i+c) * softmax(\hat u_j+c))$$
As we know in crossentropy, we get our critical point when the inside of the log here would equal $e_s$, which is only possible if both $softmax(\hat u_i+c)$ and $softmax(\hat u_j+c)$ were to be equal to $e_s$. softmax is non-invertible and is invariant under addition only, therefore to achieve this we would need $\hat u_i + c$ to equal $\hat u_j + c + K$ where $K$ is just some arbitrary constant vector ($K=[k,k,k,...]$. Subtracting $c$ and multiplying by $R+1$ we make our model want

$$\begin{align} u_i &= u_j + K \\ \implies K &= \mathcal{U}\mathcal{V}(e_i -e_j) \\ \end{align}$$

This would mean for all common words, we see this activity that $u_{i-j}$ would be a constant, but this is difficult because that means a $\delta$ must exist such that $\mathcal{U}\delta = k*\vec 1$ and that all similar word pairs indexed by $(a,b)$ would have $v_a \approx v_b + const*\delta$ (because $u_a = u_b + K \implies v_b = v_a + \mathcal{U}^{-1}K$ and we denote $\delta = \mathcal{U}^{-1}K$). This constraint is heavy, tough to learn, and would also be difficult to process on multiple word senses that would appear in the vocabulary. This is because if it were to learn this, it enforces constraints on the images of $\mathcal{U}$ and $\mathcal{V}$ along with creating word vectors with highly different magnitudes making the learning process difficult. This would indicate that this constant would be low in practice. Therefore we would get $v_i \approx v_j$.