Unsupervised Learning of Sentence Embeddings using Compositional n-Gram Features

In plain words

Getting one useful vector for a whole sentence, without any labels, is harder than getting one for a single word. Word vectors are cheap to learn from huge piles of text. Sentence encoders built from neural sequence models are much slower to train. The authors ask whether something as simple as averaging word vectors can be trained to work well for sentences.

Their model, Sent2Vec, learns the vectors and the averaging together. It is a close relative of a classic word-learning method: hide one word of a sentence and train the model to guess it from the rest of the sentence. The sentence's vector is the average of learned pieces, which are single words plus pairs of neighbouring words. The pairs let the vector pick up some meaning that single words miss, such as "not good".

Because the model is just averages and dot products, it is fast to train and fast to run on new sentences. The authors compare it with other unsupervised sentence models on classification and similarity benchmarks. It comes out ahead of the other unsupervised models on the averages they report, except SkipThought on classification.

TL;DR

Sent2Vec gives each sentence a vector with no labels: the mean of learned embeddings for its unigrams and bigrams. Training predicts each word from the rest of its sentence with negative sampling, so the work per word is a constant number of vector operations §1. The author-reported headline is an 82.0 average on six supervised tasks for the unigram+bigram model trained on Toronto books, second only to SkipThought on ordered sentences tab. 1. The released code (BSD-3-Clause) differs from the paper in several training details; see "Paper vs code".

Problem

Word embeddings can be learned unsupervised from very large text, but sentence representations were harder to get. Strong neural sentence models are slow to train on large corpora. Averaging word vectors was shown to beat LSTMs on sentence tasks, but that composition is fixed rather than learned together with the vectors §1. The authors want general-purpose sentence vectors that are unsupervised and as cheap to train and run as averages §1. The method needs a large unlabelled corpus with one sentence per line README.md. Beyond adjacent word pairs it ignores word order; order-using baselines such as SkipThought are still in the comparison tab. 1.

Method

Overview. The model is a bilinear model over a bag of unigram and bigram features, trained with a C-BOW-style objective whose context is the whole sentence rather than a fixed window §2 §2.3.

1. Bilinear view. Word and n-gram models of this family minimise an objective of the form in eq. 1, with a source matrix V (columns are source vectors v_w) and a target matrix U (columns are target vectors u_w). The sentence indicator is a bag-of-features vector §2.

   \min_{U,V} \sum_{S \in C} f_S(U V \mathbb{1}_S) eq. 1

2. Sentence vector. The sentence vector is the mean of the source vectors of every feature in R(S), which holds the unigrams and the n-grams present in S §2.1 eq. 2. The paper's model uses unigrams and bigrams. Bigram features are hashed into a fixed number of buckets with the hashing trick §2.2. The released code hashes vocabulary ids, not strings dictionary.cc.

   v_S := \frac{1}{|R(S)|} \sum_{w \in R(S)} v_w eq. 2

3. Objective. For each word w_t in S, the model predicts w_t from the sentence without w_t, i.e. from S \ {w_t} §2.1. It uses a binary logistic loss ℓ(x) = log(1 + e^(−x)) with negative sampling §2.1. Summed over the corpus, the training objective is eq. 3.

   \min_{U,V} \sum_{S \in C} \sum_{w_t \in S} \Big( q_p(w_t)\, \ell\big(u_{w_t}^\top v_{S \setminus \{w_t\}}\big) + |N_{w_t}| \sum_{w' \in \mathcal{V}} q_n(w')\, \ell\big(-u_{w'}^\top v_{S \setminus \{w_t\}}\big) \Big) eq. 3

   N_{w_t} is the set of negatives sampled for w_t §2.1. The paper's C-BOW comparison is in §2.3: C-BOW uses dynamic windows and subsamples tokens before forming context, and the authors argue both break the n-gram features a sentence embedding needs.

4. Target subsampling. A word w is kept as a target with probability q_p(w) = min{1, sqrt(t / f_w) + t / f_w}, where f_w is its normalised corpus frequency and t is the subsampling parameter §2.1. Subsampling applies to targets only; the context keeps every word §2.4.

5. Negative distribution. Negatives are drawn with probability q_n(w) = sqrt(f_w) / Σ_{w_i} sqrt(f_{w_i}) §2.1. A negative equal to the target is excluded §2.1. The number of negatives per target is 10 in every configuration tab. 5.

6. Bigram dropout. For each sentence, K n-grams with n > 1 are dropped during training, which the authors found to work better than dropping tokens at a fixed rate §2.4. The per-model K is in tab. 5. Unigrams are never dropped by this step.

7. Optional L1 penalty. The paper adds an L1 penalty τ(‖u‖₁ + ‖v‖₁) to each term and applies it with a proximal soft-threshold step after each SGD update §2.4 app. B. The modified objective, update and operator are eq. 4, eq. 5 and eq. 6. The soft-threshold per step is τ·lr′/|R(S \ {w_t})| for source vectors and τ·lr′ for target vectors, where lr′ is the current learning rate app. B. The paper reports τ = 0.0005 for the Wikipedia and Toronto-books unigram+bigram models app. B. The released code does not contain this step (see "Paper vs code").

   \min_{U,V} \sum_{S \in C} \sum_{w_t \in S} q_p(w_t) \Big( \ell\big(u_{w_t}^\top v_{S \setminus \{w_t\}}\big) + \tau\big(\|u_{w_t}\|_1 + \|v_{S \setminus \{w_t\}}\|_1\big) \Big) + |N_{w_t}| \sum_{w' \in \mathcal{V}} q_n(w') \Big( \ell\big(-u_{w'}^\top v_{S \setminus \{w_t\}}\big) + \tau \|u_{w'}\|_1 \Big) eq. 4

   z_{n+1} = \mathrm{prox}_{\alpha, g}\big(z_{n+\frac{1}{2}}\big) eq. 5

   \mathrm{prox}_{\alpha, g}(x) = \mathrm{sign}(x) \odot \max(|x_n| - \alpha, 0) eq. 6

   Here z_{n+1/2} is the value after a gradient step on z_n, and α is the proximal parameter app. B. Eq. 6 is written with |x_n| where x is meant (see Pitfalls).

8. Optimisation. Training picks one sentence at a time and runs SGD over every target, with a learning rate that decays linearly §2.4. The released trainer applies the decay as lr · (1 − progress) over all tokens in all epochs fasttext.cc.

9. Training data. Three corpora: Toronto books, Wikipedia sentences and tweets §2.4. Each corpus gives one unigram model and one unigram+bigram model §2.4 tab. 5. Books and Wikipedia were tokenised with the Stanford NLP library, and tweets with the NLTK tweet tokenizer §2.4. The paper does not say whether text is lowercased (see Pitfalls).

10. Inference. The sentence vector is the mean of the source vectors of all unigrams and bigrams of the sentence, with no subsampling and no dropout §2.2 eq. 2. Computing it costs |S|·h floating-point operations per sentence §2.2.

Training pass over one sentence, as the paper describes it. The released code differs at the target position and in dropout (see Paper vs code):

# Sent2Vec training pass over one sentence  [§2.1] [§2.4] [eq. 3]
# Input:  sentence (list of word ids), source matrix V (vocab, h),
#         target matrix U (vocab, h), learning rate lr,
#         K (bigrams dropped), neg (negatives per target)
# Output: V and U updated in place

def train_sentence(sentence, V, U, lr, K, neg):
    # Each position becomes a target with probability q_p(word)  [§2.1]
    for position, target in enumerate(sentence):
        if random_uniform() > keep_probability[target]:
            continue
        # Context is every unigram and bigram of the sentence except
        # those containing the target position  [§2.1] [eq. 3]
        context = ngram_ids(sentence, skip=position)
        # Drop K bigrams at random for this context; unigrams stay  [§2.4]
        context = drop_bigrams(context, num_drop=K)
        # Sentence vector: mean of the context source vectors  [eq. 2]
        sentence_vec = mean(V[context], axis=0)  # (h,)
        # Positive term: target vector scores the sentence vector  [eq. 3]
        score = dot(U[target], sentence_vec)
        grad = (1 - sigmoid(score)) * U[target]  # (h,)
        U[target] += lr * (1 - sigmoid(score)) * sentence_vec
        # Negatives drawn from count^0.5, never equal to the target  [§2.1]
        for negative in sample_negatives(num=neg, exclude=target):
            score = dot(U[negative], sentence_vec)
            grad -= sigmoid(score) * U[negative]
            U[negative] -= lr * sigmoid(score) * sentence_vec
        # Every context entry receives its share of the averaged gradient
        # [eq. 2]; duplicate entries accumulate
        V[context] += lr * grad / len(context)

Inference, as in the paper. The released code's handling of out-of-vocabulary tokens is an addition the paper does not state:

# Sentence embedding at inference  [eq. 2] [§2.2]
# Input:  tokens (list of strings), vocab (string -> word id),
#         source matrix V (vocab + buckets, h)
# Output: vector of length h

def embed_sentence(tokens, vocab, V):
    # Remove out-of-vocabulary tokens first, so bigrams can join words
    # that were not adjacent in the text  [code: src/dictionary.cc#L436-L441]
    ids = [vocab[t] for t in tokens if t in vocab]
    # All unigrams and bigrams, no dropout  [eq. 2]
    # [code: src/fasttext.cc#L656-L658]
    features = ids + bigram_ids(ids)
    # Mean over all features, repeats included  [eq. 2]
    return mean(V[features], axis=0)  # (h,)

Hyperparameters

Per-model training configuration from the paper tab. 5. Learning rate is 0.2 and negatives are 10 for every model. Subsampling and K vary by model.

tab. 5. "Min target count" is the paper's column name. The text never explains it; the released code applies it to target positions only (see Paper vs code).

Other settings:

The README example trains the Wikipedia uni+bi configuration (-dim 700 -epoch 9 -lr 0.2 -minCount 8 -minCountLabel 20 -t 0.000005 -dropoutK 4) README.md, matching tab. 5. Bucket count and vocabulary cap are extra arguments the paper does not state.

Results

Author-reported. Setup §4 §5: supervised tasks are MSR paraphrase (MSRP), movie reviews (MR), product reviews (CR), subjectivity (SUBJ), opinion polarity (MPQA) and question type (TREC). Sentence embeddings go into logistic regression. MSRP uses the concatenation of |v₁ − v₂| and v₁ ⊙ v₂. Unsupervised similarity is cosine similarity against human judgements on STS 2014 and SICK 2014, with Spearman and Pearson correlation. Corpora: Toronto books, 70M sentences and 0.9B words tab. 1; Wikipedia, 69M sentences and 1.7B words tab. 6; Twitter, 1.2B sentences and 19.7B words tab. 6. Baselines are described in §3 and §5. Sentence-length statistics for the evaluation sets are in tab. 8.

Headline numbers:

Full supervised results tab. 1. Metric: accuracy, MSRP as Acc / F1. The paper's table also marks best scores in bold and underline, which are omitted here.

Full unsupervised similarity results tab. 2. Spearman / Pearson correlation. Columns are the STS 2014 subsets and SICK 2014 (test + train).

The paper says the Sent2Vec unsupervised results beat all unsupervised models trained on the Toronto corpus on most tasks, with the best average §5 tab. 2. It also reports that Sent2Vec models on average outperform or match C-PHRASE, which uses parse information and about three times the text of the Toronto corpus §5 tab. 2.

Training time and macro average tab. 3. Macro average is the mean of the supervised and unsupervised averages.

Comparison with Arora et al. tab. 4. Unsupervised columns are Pearson correlation. The supervised row is the supervised average from tab. 1. The GloVe corpus is 42 times larger than the paper's Twitter corpus §5.

Appendix supervised results, Sent2Vec rows only tab. 6. Other rows (CaptionRep, DictRep) are omitted here.

Appendix unsupervised results, Sent2Vec rows only tab. 7. Spearman / Pearson.

The paper's figure fig. 1 shows two profiles. The left panel plots the learned L2 norm of each vocabulary word's vector against the log of its frequency. The right panel shows the static weight a/(a + f_w) used by Arora et al. The authors read the learned norms as the model down-weighting very frequent and very rare words, roughly in line with Luhn's mid-rank hypothesis §5.

The paper also reports that the L1 variants give small gains on supervised tasks (82.1 and 83.4 averages, tab. 6). The authors' explanation for the bigram gains on supervised tasks is that bigrams capture some non-compositional meaning, such as "not good" §5.

Paper vs code

Repository: the paper links https://github.com/epfml/sent2vec in a footnote §1, so it is the official code. This card cites commit 9efbc2dd69f6c737c3a752c9dc5fbb4843d578b6. The repository's LICENSE is the BSD text for fastText, copyright Facebook LICENSE. The code is built on fastText, which the paper acknowledges §2.4.

1. Learning rate default. Paper: 0.2 for every model tab. 5. The README help lists 0.2 README.md and its example passes -lr 0.2 README.md. The released sent2vec command sets 0.05 when no -lr is given args.cc. Pass -lr 0.2 explicitly.

2. Bigram default. The paper's unigram+bigram models use n-grams up to length 2 tab. 5. The released default is wordNgrams = 1, which trains a unigram model args.cc; the README help lists 2 README.md. Pass -wordNgrams 2.

3. Target position in the context. Paper: the context is S \ {w_t}, the sentence without the target §2.1 eq. 3. Released code: the target is overwritten with a placeholder id and stays in the context fasttext.cc. The placeholder is the first vocabulary entry, a dedicated <PLACEHOLDER> word with its count reset to zero dictionary.cc. Its row is trained like any other model.cc. The effect is that the average includes one placeholder vector and up to two bigrams that touch the target position.

4. Dropout granularity. Paper: K n-grams are dropped "for each sentence" §2.4. Released code: a fresh random set of K token positions is drawn for each kept target fasttext.cc. A dropped position removes the bigrams that touch it, so one position can remove up to two bigrams dictionary.cc. Unigrams are never removed. For short sentences the loop stops once two positions remain, so fewer than K positions may be dropped dictionary.cc.

5. Sentence order. Paper: "select a sentence randomly" §2.4. Released trainer: each thread reads the input file in order from its byte offset fasttext.cc. There is no shuffle, so shuffle the input file yourself if you want random order.

6. L1 penalty. Paper: the L1 variant with τ = 0.0005 app. B tab. 6. Released code: a search of src/ for L1, proximal and soft-threshold code found none. The L1 rows in tab. 6 and tab. 7 cannot be reproduced from this release.

7. Min target count. Paper: column "Minimum Target word Count" tab. 5, not explained in the text. Released code: -minCountLabel skips a position as a target when its count is below the value, but the word stays in the context fasttext.cc. The vocabulary cut uses -minCount dictionary.cc. The help text calls the option the minimum "label occurences" args.cc.

8. Subsampling formula. Paper: q_p = min{1, sqrt(t/f) + t/f} §2.1. Released code: the probability is sqrt(t/f) + t/f without the min dictionary.cc. This is equivalent, because a value of at least 1 always keeps the word.

9. Hashing. Paper: the bigram hashing uses "the same hashing function as FastText" §2.2. Released code: a bigram's id is the vocabulary size plus (first_id · 116049371 + second_id) mod bucket, computed on vocabulary ids dictionary.cc. The FNV string hash is used for character n-grams dictionary.cc, which the sentence vector does not use fasttext.cc.

10. Negative sampling. Paper: a weighted sum over the vocabulary in eq. 3. Released code: for each kept target it draws neg negatives from the count^0.5 table and rejects the target model.cc model.cc. The table has 10^7 entries model.h. This is a sampled estimate of eq. 3.

11. Gradient normalisation. Paper: the sentence vector is an average eq. 2, but the gradient scaling is not stated. Released code: after each update it divides the shared gradient by the number of context features model.cc.

12. Tokenisation and case. Paper: Stanford and NLTK tokenisers §2.4; case handling not stated. Released code: the trainer does no tokenisation or lowercasing README.md. The Wikipedia and tweet scripts lowercase by default wikiTokenize.py tweetTokenize.py.

13. Evaluation code. Paper: the classifiers use the code of SkipThought §4. The repository has no evaluation scripts; its files are the trainer, the Python wrapper and tokenisers.

Checked and matching: the negative-sampling distribution §2.1 and the linear learning-rate decay §2.4.

Pitfalls

• Learning rate and bigram flags are not the defaults. The sent2vec command with only -input and -output trains a unigram model at learning rate 0.05 args.cc args.cc. Set -lr 0.2 -wordNgrams 2 and the other table values tab. 5.
• Bigram ids depend on vocabulary order. Bigram buckets are computed from vocabulary ids, and ids are assigned by sorted count dictionary.cc dictionary.cc. A different -minCount or vocabulary cut changes which bigram hits which bucket. To match released vectors, reproduce the vocabulary and its ids.
• Bucket size is not stated. The input matrix has (vocabulary + buckets) rows of dim values fasttext.cc. The README example's 4,000,000 buckets at 700 dimensions is 2.8 billion values before the vocabulary rows (arithmetic from the README example), so memory is set by the bucket count.
• Out-of-vocabulary tokens are deleted before bigrams form. Their neighbours become bigram partners dictionary.cc. A sentence with no in-vocabulary token gets a zero vector because the mean is skipped fasttext.cc. The paper says nothing about either case.
• Repeats are counted. The paper's R(S) is called a "list" §2.1. The code counts every occurrence, so a repeated word or bigram is counted again dictionary.cc. Do not deduplicate.
• Sigmoid and log are lookup tables. The sigmoid table has 512 entries over [−8, 8] and returns 0 or 1 outside that range model.cc model.h. The log is also tabulated model.cc. Exact-math reimplementations will differ slightly; the paper gives no tolerance.
• Learning-rate decay runs over all epochs. Progress is measured against the total token count across all epochs, not per epoch fasttext.cc.
• Long sentences are not truncated. The 1024-token line cap is skipped for sent2vec dictionary.cc. A newline ends a sentence dictionary.cc.
• Equation 6 has a typo. It writes |x_n| where x is meant eq. 6 app. B.
• Averages are not comparable across tables. The Table 1 average counts MSRP by accuracy only tab. 1. The macro average in tab. 3 is a different quantity.
• Corpus-size comparisons. Arora et al. used GloVe trained on a corpus 42 times larger than the paper's Twitter corpus, which the authors say favours that baseline §5 tab. 4.
• The STS 2017 claim has no numbers. The paper says the model "significantly outperforms" C-PHRASE on the official STS 2017 benchmark §5, but gives no figures.
• Costs the abstract leaves out. Training on the 19.7B-word Twitter corpus took 6.5 hours on a single node with 30 threads tab. 3. Inference costs |S|·h operations per sentence §2.2.

Lineage

• Builds on: C-BOW (Mikolov et al. 2013), whose context window is extended to the whole sentence §2.3; unsupervised word embeddings, GloVe §1; the FastText work of Bojanowski et al. and Joulin et al., whose negative sampling, subsampling and hashing are reused §2.1 §2.2. None has a card on this wiki.
• Compared against: SkipThought (Kiros et al. 2015), SDAE and SAE (Hill et al. 2016), ParagraphVector (Le et al. 2014), FastSent, Siamese C-BOW (Kenter et al. 2016), C-PHRASE (Pham et al. 2015), DictRep and CaptionRep, and the averaging approach of Arora et al. 2017 §3 §5. None has a card on this wiki.
• Extended by: Bi-Sent2vec, a cross-lingual extension linked from the repository README (arXiv:1912.12481) README.md. Not compiled here.
• Superseded by: not stated in this wiki.