Summary of Wordvec

Keyword: CBOW, Skip gram

Prerequisites

1. Statistical NLP

   • Create a statistical model to calculate the probability $P(s)$ of a proposition.
   • Use Bayes' rule,
     $\begin{aligned} P(s)&=P(w_1w_2\cdots w_n)\\&=P(w_1)P(w_2|w_1)\cdots P(w_n|w_1w_2\cdots w_{n-1})\\&=\prod_{i=1}^n P(w_i|h_{i-1}) \end{aligned}$
     where $h_{i-1}=w_1w_2\cdots w_{n-1},~P(w_i|h_{i-1})=\dfrac{\text{count}(h_{i-1}w_i)}{\text{count}(h_{i-1})}$
   • i.e. the probability of words is calculated from the frequency of the count.
   • There is a sparsity problem (if $h_{i-1}$ is too long, $h_{i-1}w_i$ doesn't exist in the training corpus).
   • For example, if $h_{i-1}$="I have a pen, I have an apple, Ah, apple", $w_i$ will be the pen.
   • But we can't observe the whole sentence in the training corpus because of its length.
   • So we have to limit the length => N-gram
   • This statistical method has a big problem: it is impossible to compare words. In other words, it only learns for sentences, not for words.

2. Distributional semantic model

   • Main idea: Distributional hypothesis "Similar words occur in similar contexts".
   • According to this hypothesis, our goal is to quantify semantic similarities (using various methods, e.g. vector similarities) between words based on their distributional properties.
   • To compare between words, we will represent words as a vector => Vector representation
     1. One-hot encoding: No information about word similarity
     2. Dense representation: Embed words in a continuous vector of much lower dimension (s.t. $N\approx 100\sim 1000$)

Previous work

1. Word2vec (NNLM)
   • To imporve above idea, we train the word embedding using Neural Network(Deep learning)
   • It is more efficient when we process NLP Problem, so The topic of how to embed words efficiently has attracted a lot of attention.
   • NNLM is like bi-gram model, this model consists of two fully connected layers
     1. Linear
     2. Linear + softmax
   • Input is one-hot encoding vector, and then forward pass hidden layer => output layer
   • Before determine embedding vector, take softmax function to compare target vector
   • Let $x_i$ be one-hot encoded input of $i$th word, $W,~W'$ be weight matrices with the hidden layer size $N$
   • Then, $\mathbf{h}=\mathbf{x_i}W$, $\mathbf{u}=\mathbf{h}W'$
   • After softmax, $P(v_j|v_i)=\dfrac{e^{u_j}}{\sum _ {t=1} ^ V e ^ {u_t}}$
   • Later, the model was developed and RNN-based RNLM was proposed, which continues to be a new site due to the presence matrix.

Problem of Previous work

1. Too slow and huge memory

   • For example, above NNLM, if vocabulary is $10^4$, vector size is $3\times 10^2$, then we have to update $6\times 10^6$ weights!
   • In pracitce, size of vocabulary is much larger than $10^4$, so vector size is also increased to outperform.
   • Weight is so much and huge memory, we can't train large corpus!

2. Can't perform vector calculation

   • If we have three words, "Fruits", "red", "not plum", then we can guess "apple".
   • As model doesn't train syntax(or semantic) perspective similarity, this task is impossibile.

CBOW

• To generate "center word" using "surround words"
• Generate one-hot encdoings $\left\{x_1,\ x_2,\ \cdots,\ x_C\right\}$ of the input words' size is $C$
• Forward pass to get embedded word vectors $\left\{h_1,\ h_2,\ \cdots,\ h_C\right\}$ by $h_c=x_c W$ (sharing weights like convolution)
• Take average and genearte score vector, and then softmax
• Our goal is to minimize the loss function
  $E = -\log P(v_O|v_1,\ v_2,\ \cdots,\ v_C)$
• Size of Input words is $N$, dimension of hidden layer is $D$, and then softmax, So complexity is
  $Q=N\times D + D \times \log_2{V}$

Skip n-gram

• There are two ways to learn word embedding using (Deep)NN according to our perspective.
• One is CBOW(Continuous Bag of Words), which is focuses on the context words, and the other is Skip gram, which is focuses on the center words.
• Especially, skip gram method is to learn context words using center words.
• Therefore we desire $\boldsymbol{y}$ to match the $C$ many one-hot encodings of the actual output words, so using mamimum log-likelihood, obejctive function is following.

where $V$ is size of words, $u$ is score vector.

• Size of output words is $C$, dimension of hidden layer is $D$, and then softmax, So complexity is
  $Q=C\times (D + D \times \log_2{V})$

Conclusion

• In this paper, we dramatically reduce the time and memory for computing embeddings with words.
• This makes it possible to use more layers and word vectors, and it is possible to predict a high level of similarity.
• Previously, while the focus was simply on improving similarity to semantic (or syntax), the paper focused on improving several similarities (i.e. sematomic & syntax) simultaneously.
• In addition, it was possible to predict words with completely different meanings through unintended operations with vectors, which can be said to have SOAT in language understanding.