Summary of FastText

Prerequisites

1. 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.

2. Negative Sampling
   • When we learn word embeddings using A and B, we compute the cost for every word.
   • It doesn't matter as long as the number of words is small, but in practice there are so many words so that this takes a lot of time.
   • To solve this, We proceed with learning by selecting only some of the context vectors that are the answers and those that are not.
   • We called it "Negative sampling"
   • In this sampling, we want the network to output $1/0$ for the output / neagtive word.
   • Instead of softmax, we use sigmoid only for the $K+1$ words

Problem of Previous work

1. Hard to learn injective word representation
   • Specifically, There is problem to learn "unseen" or "rare" data
   • $e.g.$ tensor, flow is frequent word, so we can learn easily
     but, Since tensorflow is rare word, there is a high probability that the word does not exist in train data
   • We call this problem "OOV(Out of value) problem"
2. Ignore morophologically rich language
   • Specifically, there is problem in the learning of those who have different tenses or parts of speech from the same word
   • $e.g.$ we will learn following two words: "have", "having"
   • After learning is over, embedding of "have" and "having" has high similarity, however it depends on distribution of traning data
   • That means, embedding of "have" and "having" has low similarity, and then it is wrong representation.

General model

• We will use skip-gram and negative sampling, so obejctive function will be binary classification problem.
• Let $f\ :\ x\mapsto \log(1+e^{-x})$ ($i.e.$ sigmoid function), we can write the objective as:
  $\displaystyle\sum_{t=1}^T\left[\displaystyle\sum_{C\in\mathcal{C}_t} f(s(w_t,\ w_c))+\displaystyle\sum _ {n\in\mathcal{N} _ {t,\ c}}f(-s(w_t,\ n))\right ]$
  where $\mathcal{C} _ t$ is set of context words, $\mathcal{N} _ {t,\ c}$ is set of negative samples from the vocabulary.
• Note that $s(w_i,\ w_j)$ means similarity between embedding of input words $w_i$ and embedding of output words $w_j$, and if we normalize embedding vector to size $1$, then similarity function $s(w_i,\ w_j)$ can be defined:
  $s(w_i,\ w_j)=\dfrac{\mathbf{u} _ {w_i}\cdot \mathbf{v} _ {w_j}}{\lvert \mathbf{u} _ {w_i} \rvert\lvert \mathbf{v} _ {w_j} \rvert}=\mathbf{u} _ {w_i}^T\mathbf{v} _ {w_j}$

Main idea: Learn subword representation instead of entire word

• To solve above two problems, we will use subword model.
• Each word $w$ is represented as a bag of a character $n$-gram, so we can calculate word embedding "sum(or means) of all $n$-gram embedding" instead of word-self.
• In addition, if only words were learned before, in this model, learning proceeds not only on words but also on all subwords.
• In practice, authors extract all the $n$-grams for $n$ greatoer or equal to $3$ and smaller or equal to $6$.
• Let $G$ is dictionary of $n$-grams.
  Given a word $w$, let us denote by $\mathcal{G} _ w \subset \\{ 1,\ 2,\ \cdots,\ G \\}$ the set of $n$-grams appearing in $w$
  Since we represent a word by the sum of the vector representations of its $n$-gram, we can obtain the scoring function
  $s(w,\ c)=\displaystyle\sum_{g\in\mathcal{G} _ w} u _ {g}^Tv _ {c}$