Continuous Bag of Word and Skip-Gram
Introduction
In natural language processing, the classic method is the bag of word method, which counts the frequency of occurrence of each word, but this method cannot show the similarity between words, such as “same” and “equal”
Word to vector came into being, collect the contextual relationships of a large amount of text and use mathematical models to convert the text into high-dimensional vectors. If two words have similar meanings, the vector representation should be close. Continuous bag of word (CBOW) and Skip-gram are the most common methods. It is recommended to first understand neural networks
Continuous Bag of Word (CBOW)
Single Input
Consider the simplest case, given a word and predict the next word. Let $V$ be the vocabulary size, $ \{ \contia{w}{V} \}$ be the words, and $\bs x$ be the one-hot encoding of a word, i.e. $i$-th word’s $x$ has $x_i = 1$, and $x_j = 0$ for $j \ne i$, let the hidden layer size be $N$, two weights $\bs W_1 \in \bb R^{V \times N}$ and $\bs W_2 \in \bb R^{N \times V}$, and $\hat y$ be the predict probability of next word.
The operation is as follows. Given a word $w$ and its corresponding vector $\bs x$, the probability of predicting the next word is
$$ \begin{align*} \bs h & = \bs W_1^T \bs x \\ \bs u & = \bs W_2^T \bs h \\ \hat {\bs y} & = \text{softmax} (\bs u) \end{align*} $$where $\text{softmax} (\bs u)$ defined by
$$ \begin{align*} \hat y_j = \frac{\exp (u_j)}{\sum_{v = 1}^{V} \exp (u_v)} \end{align*} $$Since $\bs x$ is a one-hot encoding vector, such that
$$ \begin{align*} \bs h = \bs W_1^T \bs x_{w_i} = [\bs W_1^T]_{(i, \cdot)} = \bs v_{1, i}^T \end{align*} $$where $\bs v_{1, i}$ is the $i$-th row of $\bs W_1$, called input vector. On the other hand, the outcome of $j$-th word is
$$ \begin{align*} u_j = [\bs W_2^T]_{(\cdot, j)} \bs h = \bs v_{2, j}^T \bs h \end{align*} $$where $\bs v_{2, j}$ is $j$-th column of $\bs W_2$, called output vector. Hence, givne a word $w_i$, the outcome is $j$-th word has probability
$$ \begin{align*} \hat y_j = p (w_j | w_i) = \frac{\exp(u_j)}{\sum_{v = 1}^{V} \exp(u_v)} = \frac{\exp(v_{1, w_i}^T v_{2, w_j})}{\sum_{v = 1}^{V} \exp(v_{1, w_i}^T v_{2, w_v})} \end{align*} $$where $v_{1, w}$ and $v_{2, w}$ present the $w$’s input and output vector.
Back Propagation
Given a word $w_i$, it next word is $w_j$, our goal is to maxmize $\hat y_j = p (w_j | w_i)$, i.e. minimize $- \ln \hat y_j$, define the loss function in the opposite direction of this, defining
$$ \begin{align*} E = - \ln \hat y_j = - u_j + \ln \left[ \sum_{v = 1}^{V} \exp(u_v) \right] \end{align*} $$First Gradient Descent
First, perform a partial differential of $\bs u$
$$ \begin{align*} \frac{\partial E}{\partial u_k} = - I (k = j) + \frac{\exp(u_k)}{\sum_{v = 1}^{V} \exp(u_v)} = - I (k = j) + \hat y_k \end{align*} $$such that
$$ \begin{align*} \frac{\partial E}{\partial \bs u} = \hat {\bs y} - \bs y = \bs H_2 \end{align*} $$Next, perform a partial differential of $\bs W_2$, the result $\bs G_2$ is the matrix required for gradient descent $\bs W_2$
$$ \begin{align*} \frac{\partial E}{\partial \bs W_2} = \frac{\partial E}{\partial \bs u} \frac{\partial \bs u}{\partial \bs W_2} = \bs h \bs H_2^T = \bs G_2 \end{align*} $$Second Gradient Descent
First, perform a partial differential of $\bs h$
$$ \begin{align*} \frac{\partial E}{\partial \bs h} = \frac{\partial E}{\partial \bs u} \frac{\partial \bs u}{\partial \bs h} = \bs W_2 \bs H_2^T = \bs H_1 \end{align*} $$Next, perform a partial differential of $\bs W_1$, the result $\bs G_1$ is the matrix required for gradient descent $\bs W_1$
$$ \begin{align*} \frac{\partial E}{\partial \bs W_1} = \frac{\partial E}{\partial \bs h} \frac{\partial \bs h}{\partial \bs W_2} = \bs x \bs H_1^T = \bs G_1 \end{align*} $$The iteration method is
$$ \begin{align*} \bs W_2^{(\text{new})} = \bs W_2^{(\text{old})} - \eta \bs G_2 \\ \bs W_1^{(\text{new})} = \bs W_1^{(\text{old})} - \eta \bs G_1 \end{align*} $$Since $\bs x$ is an one-hot encoding vector, only $x_i = 1$, thus the iteration of $\bs W_1$ can be simplified to only iterate $i$-th row, i.e.
$$ \begin{align*} \bs v_{1, i}^{(\text{new})} = \bs v_{1, i}^{(\text{old})} - \eta \bs H_1 \end{align*} $$For word $w_i$, the input vector $\bs v_{1, i}$ will be its vector represent
Intuitive explanation, $\bs H_1$ is the vector of out vector $\bs v_{2, i}$ multiply predict error $\hat y - \bs 1^{(j)}$. If the predicted probability of $w_j$ is overestimated ($\hat y_j > y_j$), then the input vector $\bs v_{1, j}$ will tend to move away from the outpur vector $\bs v_{2, j}$; On the contrary, if the predicted probability of $w_j$ is underestimated ($\hat y_j < y_j$), then the input vector $\bs v_{1, j}$ will tend to move close to the outpur vector $\bs v_{2, j}$
Set the input and predicted pairs of data to iterate, after iterating over all pairs, the vector movement will accumulate. We can image that, the word $w$’s output vector will be “pulled back and forth” by the closed words of $w$, just like a gravity attracts words around $w$. On the contrary, it can also be image that, the input vector will be “pulled back and forth” by the output vector, and the force of this pulling back and forth is determined by the learning rate $\eta$ and the co-occurrence of words. And after multiple iterations, the input and output vectors will eventually converge to a stable
Multiple Input
In single input assumption, word prediction depends only on the previous word, and observe the iteration of weight $\bs W_1$, it also show that an iterate only update a word $w_i$’s input vector $\bs v_{1, i}$
$$ \begin{align*} \bs v_{1, i}^{(\text{new})} = \bs v_{1, i}^{(\text{old})} - \eta \bs H_1 \end{align*} $$However in practice, word prediction can rely on previous and later words. Hence, introduce multiple input word to vector model, usually given previous and later $C$ words to predict the center word
The only change is, set input to $C$’s words one-hot encoding average, such that the input change to
$$ \begin{align*} \bs h = \bs W_1^T \left( \frac{x_1 + x_2 + \cdots + x_C}{C} \right) \end{align*} $$That is, the gradient of the iteration is evenly distributed to $C$ words, and the other calculations and inferences remain the same
$$ \begin{align*} \bs v_{1, w_i}^{(\text{new})} = \bs v_{1, w_i}^{(\text{old})} - \frac{1}{C} \eta \bs H_1, \quad i = \conti{C} \end{align*} $$Skip-Gram
Skip-gram is constructed in the opposite way to CBOW, given a center word, then predict previous and later words
Given center word $w_i$, the previous and later words are $w_{j_1}, w_{j_2}, \cdots, w_{j_C}$, the goal is to maxmize $\hat y_{j_1}, \hat y_{j_2}, \cdots, \hat y_{j_C}$, i.e. minimize $-\ln (\hat y_{j_1} \hat y_{j_2} \cdots \hat y_{j_C})$, define the loss function in the opposite direction of this, defining
$$ \begin{align*} E & = - \ln (\hat y_{j_1} \hat y_{j_2} \cdots \hat y_{j_C}) = - \sum_{c = 1}^{C} u_{j_c} + \ln \left[ \sum_{v = 1}^{V} \exp (u_v) \right] \end{align*} $$such that
$$ \begin{align*} \frac{\partial E}{\partial \bs u} = \hat {\bs y} - \bs y = \bs H_2 \end{align*} $$All partial differential and gradient descent formulas are exactly the same, only the value of $\bs H_2$ is slightly different
Conclusion
Multiple input CBOW is equivalent to the single input CBOW that extends $\bs x$; Skip-gram is equivalent to the single input CBOW that extends $\bs y$; therefore