FastText: word vectors from character n-grams

Word2Vec and GloVe give each word type its own vector, learned only from the contexts of that exact string. Coffee and coffees are trained separately, learnig has no vector at all, and in a language like Russian, where a noun has a dozen case and number forms, most forms are rare even in a large corpus. FastText (Bojanowski et al., 2017) keeps the skip-gram objective and changes what a word is: a bag of character n-grams, each with its own vector, so that words written alike share parameters and any string, seen or not, gets a vector.

Notation. For a word $w$, $\mathcal G_w$ is its set of character n-grams together with the word itself; each $g \in \mathcal G_w$ has a vector $z_g \in \mathbb R^d$. Context words have vectors $v_c$, as in Word2Vec. $K$ is the number of hash buckets.

Baseline: one vector per word type#

On the 537,272 Quora questions of the previous notes, lower-cased and without stopwords, there are 87,511 word types. With the usual cut-off of 5 occurrences, 59,722 of them, 68% of the types, get no vector. They are only 2.4% of the tokens, but 14% of the questions contain at least one of them: misspellings (programing, 35 times), rare inflections, names, new words. And the 27,789 words that do get vectors learn nothing from each other: the vector of learns is trained from its own few contexts, not helped by the many contexts of learn.

A word is a bag of character n-grams#

The paper’s example is where. With boundaries it becomes <where>, and its 3-grams are <wh, whe, her, ere, re>; with the 4-, 5- and 6-grams there are 14 n-grams, and together with <where> itself, 15 vectors. The boundaries matter: the 3-gram her inside where is a different piece from the word her, which is <her>.

The score of a word and a context word, which in Word2Vec was the dot product $u_w \cdot v_c$, becomes

$$s(w, c) = \sum_{g \in \mathcal G_w} z_g \cdot v_c ,$$

and everything else, the negative-sampling loss and the sampling of negatives, stays as it was. The gradient of every training pair reaches every n-gram vector of the word, so learns, learnt and learner all train the vectors of <le, lea, ear, arn and the longer pieces they share with learn.

Figure

A word as a sum of n-gram vectors

The steps of the figure:

1. Boundaries. < and > mark the start and the end, so prefixes and suffixes are distinct pieces.
2. N-grams. All substrings of length 3 to 6, plus the whole word as one more piece: 15 pieces for where.
3. Look-up. Each piece is hashed to a row of one table of n-gram vectors.
4. Sum. The word vector is the sum of the rows. (Implementations such as gensim divide by the number of pieces; the scale does not matter for cosine.)

Hashing#

A vocabulary of all character n-grams of a large corpus would be huge, so the n-grams are not stored by name. Each one is hashed (FNV-1a in the paper) into one of $K = 2 \cdot 10^6$ buckets, and the bucket’s row is its vector. Two n-grams in one bucket share a vector, a collision the method accepts in exchange for memory fixed in advance: $2 \cdot 10^6 \times 300$ floats of 4 bytes is 2.4 GB for 300-dimensional vectors, 256 MB for the 32-dimensional vectors used below.

Vectors for unseen words#

A word that was never seen still has n-grams, and most of them were seen in other words. Its vector is the sum of their vectors. Trained on the Quora questions (gensim, CBOW variant, $d = 32$, window 5, words with at least 5 occurrences, 5 epochs), the model answers queries for strings that are not in its vocabulary:

Query (not in the vocabulary)	Nearest words by cosine
coffeee	coffee 0.988, koffee 0.928, coffees 0.904
learnig	learnt 0.963, learns 0.955, learnings 0.950, learn 0.943
blockchainify	blockchain 0.967, access 0.864, blockade 0.861
unfriendliness	friendly 0.905, confess 0.893, unfriend 0.884
pyhton	von 0.943, ton 0.941, peyton 0.939

The first three work because the misspelling or derivation keeps most pieces: coffeee shares 15 of its 22 n-grams with coffee, learnig 14 with learning. Unfriendliness is found near friendly but also near confess, which shares nothing in meaning and three pieces of its ending (ess, ss>, ess>) with the 50 n-grams of unfriendliness. Pyhton fails: swapping two letters breaks every n-gram that spans them, and it shares only <py and on> with python, 2 of 18. Subwords help with spelling variation that preserves substrings, not with every typo.

What subwords do to neighbours#

The same mechanism changes the neighbours of ordinary words. For in-vocabulary queries, FastText’s nearest words are dominated by shared spelling:

Word	FastText	Word2Vec (CBOW, same data)
learn	learnt 0.965, learns 0.955, unlearn 0.939	learning 0.817, beginner 0.750, teach 0.743
coffee	coffees 0.914, koffee 0.897, tea 0.856	tea 0.900, beer 0.875, starbucks 0.857
india	indias 0.933, indiape 0.917, indiana 0.882	indian 0.778, overseas 0.753, usa 0.750

Inflections and spelling variants move close, which is what the model is for, and so do strings that only look alike: Indiana, indigo and Indira are among the five nearest words to India. For tasks that care about morphology (syntactic analogies, rare words, morphologically rich languages) this is a gain; for tasks about topic it can be noise.

The paper measures both sides. On word similarity, computing vectors for out-of-vocabulary words raises the correlation with human judgement on the Russian HJ dataset from 59 (skip-gram) to 66, and on the English rare-words dataset from 43 to 47. On analogies, syntactic accuracy rises sharply in morphologically rich languages, from 52.8% to 77.8% in Czech and from 44.5% to 56.4% in German, and in English from 70.1% to 74.9%, while English semantic accuracy drops slightly, from 78.5% to 77.8%.

fastText as a classifier#

The same library, from the same group, includes a text classifier built on the same idea (Joulin et al., 2017): a document is the average of the embeddings of its words, optionally with hashed word bigrams added, and a linear layer with a softmax predicts the label. It is CBOW with the label in place of the middle word. There is no hidden non-linearity; the embeddings have only 10 dimensions in the paper’s experiments, and the bigrams give it some local word order at almost no cost.

On AG News, the dataset of the course’s classification notes, the paper reports 91.5% test accuracy with words alone and 92.5% with bigrams, against 87.2% for a character-level CNN and 91.3% for a 29-layer one, at about a second per epoch instead of hours. A re-implementation in PyTorch (word and hashed bigram embeddings of size 10 averaged with EmbeddingBag, a linear layer, SGD with a linearly decaying rate chosen on 12,000 held-out training articles, 5 epochs, code below) gives the same picture:

Model	Parameters	Seconds per epoch (CPU)	Test accuracy
words only, rate 0.05	650,474	2.2	0.914
words + bigrams in 2,000,000 buckets, rate 0.1	20,650,474	3.0	0.922

For comparison, TF-IDF with logistic regression reaches 0.918 on the same split and the best CNN 0.911. A linear model over averaged embeddings is a baseline worth running before anything heavier.

What changed#

	Word2Vec / GloVe	FastText
Unit with a vector	word type	character n-grams of length 3 to 6, plus the word
Word vector	one row of a table	sum of 15 or so rows
Unseen word	no vector	sum of its known n-grams
Parameters	$\lvert V \rvert \times d$	$(\lvert V \rvert + K) \times d$, with $K = 2 \cdot 10^6$
Neighbours	by context	by context and by spelling

Limitations#

• Spelling is not meaning. Strings that look alike get close vectors whether or not they are related (India and Indiana, unfriendliness and confess).
• Not every typo is repaired. A transposition breaks the n-grams it spans; pyhton lands next to von and ton.
• Memory. The bucket table dominates: 2.4 GB at $d = 300$ before any word vector.
• Still static. One vector per string, whatever the sentence; the BERT note removes this. Subword tokenization, used by every Transformer in the course (tokenization note), solves the open-vocabulary problem differently: it splits a rare word into a few learned pieces instead of summing all n-grams.

What you should remember#

• A word is < + word + > cut into all n-grams of length 3 to 6, plus the word itself; its vector is the sum of their vectors, and the skip-gram loss is unchanged.
• N-grams are hashed into $2 \cdot 10^6$ buckets, so memory is fixed and every n-gram has a row to look up. Hashing removes missing dictionary entries, not missing evidence: the row of an n-gram never seen in training was never trained, and a row can be shared by unrelated n-grams.
• An unseen word gets a vector from its pieces; misspellings that keep most pieces land near the right word, transpositions do not.
• Neighbours mix meaning and spelling; the gains are largest for morphology and rare words.
• The fastText classifier, averaged word and bigram embeddings with a linear softmax, reaches 0.922 on AG News in seconds per epoch.

Notebook#

No course notebook trains FastText. The numbers of this note come from the run in the Code section, on the course’s own data files seminars/data/quora.txt and the AG News splits ag_news_train.csv and ag_news_test.csv of the course repository.

Code#

Subword vectors with gensim, on the Quora questions tokenized as in the GloVe note:

from gensim.models import FastText, Word2Vec

# sents: list of token lists (lower-cased, stopwords removed); run with PYTHONHASHSEED=0
ft = FastText(sents, vector_size=32, window=5, min_count=5, min_n=3, max_n=6,
              bucket=2_000_000, workers=1, seed=0)
w2v = Word2Vec(sents, vector_size=32, window=5, min_count=5, workers=1, seed=0)
for w in ['coffeee', 'learnig', 'blockchainify', 'unfriendliness', 'pyhton']:
    print(w, w in w2v.wv.key_to_index, ft.wv.most_similar(w, topn=3))

The fastText classifier on AG News, with words and hashed bigrams (the rates were chosen among 0.05, 0.1, 0.25 and 0.5 by training on the first 108,000 training articles and scoring the remaining 12,000):

import re, zlib, numpy as np, pandas as pd, torch, torch.nn as nn

tr = pd.read_csv('ag_news_train.csv', sep='\t'); te = pd.read_csv('ag_news_test.csv', sep='\t')
toks = lambda t: re.findall(r"\w+", t.lower())
Xtr, Xte = [toks(t) for t in tr.text], [toks(t) for t in te.text]
ytr, yte = torch.tensor(tr.label.values), torch.tensor(te.label.values)
vocab = {w: i for i, w in enumerate(sorted({w for s in Xtr for w in s}))}
V, B = len(vocab), 2_000_000
BIGRAMS, LR = True, 0.1                            # words only: False, 0.05

def feats(s):                                      # word ids, then hashed bigram ids
    ids = [vocab[w] for w in s if w in vocab]
    if BIGRAMS:
        ids += [V + zlib.crc32(f'{a} {b}'.encode()) % B for a, b in zip(s, s[1:])]
    return ids

def batch(F, idx):                                 # concatenated ids and offsets for EmbeddingBag
    parts = [torch.tensor(F[i] if F[i] else [0]) for i in idx]
    return torch.cat(parts), torch.tensor([0] + [len(p) for p in parts[:-1]]).cumsum(0)

torch.manual_seed(0); rng = np.random.default_rng(0)
Ftr, Fte = [feats(s) for s in Xtr], [feats(s) for s in Xte]
emb = nn.EmbeddingBag(V + (B if BIGRAMS else 0), 10, mode='mean', sparse=True)
lin = nn.Linear(10, 4)
nn.init.uniform_(emb.weight, -0.1, 0.1)
opt = torch.optim.SGD(list(emb.parameters()) + list(lin.parameters()), lr=LR)
epochs, bs = 5, 16
steps, step = epochs * ((len(Ftr) + bs - 1) // bs), 0
for epoch in range(epochs):
    order = rng.permutation(len(Ftr))
    for s in range(0, len(Ftr), bs):
        idx = order[s:s + bs]; x, off = batch(Ftr, idx)
        for g in opt.param_groups:
            g['lr'] = LR * (1 - step / steps)        # linear decay to 0
        loss = nn.functional.cross_entropy(lin(emb(x, off)), ytr[idx], reduction='sum')
        opt.zero_grad(); loss.backward(); opt.step(); step += 1

with torch.no_grad():
    x, off = batch(Fte, range(len(Fte)))
    print((lin(emb(x, off)).argmax(1) == yte).float().mean().item())

The run prints 0.9216 with bigrams and, with BIGRAMS, LR = False, 0.05, 0.9142.

Next#

Word vectors, static or subword, still have to be combined into a representation of a document, and averaging them, as the fastText classifier does, ignores word order beyond bigrams. The next note returns to AG News with a network that reads the sequence of embeddings and asks whether seeing phrases beats a bag of counts.

References#

• P. Bojanowski, E. Grave, A. Joulin, T. Mikolov. Enriching Word Vectors with Subword Information. TACL, 5, 2017. §3.2 (n-grams of length 3 to 6, FNV-1a hashing into $2 \cdot 10^6$ buckets), Tables 1 and 2.
• A. Joulin, E. Grave, P. Bojanowski, T. Mikolov. Bag of Tricks for Efficient Text Classification. EACL, 2017. Table 1 (AG News 91.5 and 92.5), Table 2 (training time).