Distributed Representations of Sentences and Documents | Quoc Le, Tomas Mikolov

This is the paper behind embedding implementations such as doc2vec, that extend the idea of word embeddings to longer (and variable) stretches of text, such as paragraphs and documents.

In this paper, we propose Paragraph Vector, an unsupervised algorithm that learns fixed-length feature representations from variable-length pieces of texts, such as sentences, paragraphs, and documents. Our algorithm represents each document by a dense vector which is trained to predict words in the document. (1)

Introduction

Bag-of-words fixed length feature vectors have two main weaknesses:

  1. They do not regard ordering of words
    • Two sentences that use the same words but in a different ordering will have the same representation.
    • Bag-of-n-gram does in a way consider word order in a very small window of total length n,
      • but this is at the cost of data sparsity
      • and of high dimensionality
  2. The ignore word semantics
    • "powerful", "strong", "Paris" are equidistant, whereas it's obvious that the first two are semantically more related than e.g. the latter two.

Quick summary of the approach:

In our model, the vector representation is trained to be useful for predicting words in a paragraph. More precisely, we concatenate the paragraph vector with several word vectors from a paragraph and predict the following word in the given context. Both word vectors and paragraph vectors are trained by the stochastic gradient descent and backpropagation (Rumelhart et al., 1986). While paragraph vectors are unique among paragraphs, the word vectors are shared. At prediction time, the paragraph vectors are inferred by fixing the word vectors and training the new paragraph vector until convergence. (1)

  • Each paragraph (may in fact be a sentence, or a whole document) has a unique vector representation
  • But the paragraphs have a shared vocabulary of words, that each have their own word vectors
    • E.g. in gensim, this is also why we see that doc2vec is essentially built on top of word2vec and you can still access the underlying word vectors

So a quick summary on word embeddings is useful. The authors discuss related work (which is about "learning vector representations of words using neural networks", i.e. this is in fact about embeddings). Vector representations of words using neural networks", i.e. this is in fact about embeddings).

  • "each word is represented by a vector which is concatenated or averaged with other word vectors in a context, and the resulting vector is used to predict other words in the context." (1)
    • e.g. you take a context "a b c", then feed the word vectors of "a" and "b" (average or concatenate them) as input to a neural network. You then try to predict word vector "c".
    • I guess the point here is that if "a" occurs very often in the context of "c" but "b" does not, then "a" is a better predictor.
    • Then the assumption of distributional semantics comes into play: if "a" occurs often in a similar context and is a better predictor (the network learns this), then "a" is more similar to "c" than "b" is to "c".
  • "The outcome is that after the model is trained, the word vectors are mapped into a vector space such that semantically similar words have similar vector representations (e.g., “strong” is close to “powerful”)." (1-2)

So, how can we extend the idea of these embeddings to larger spans of text? Two attempts from previous work to get sentence embeddings:

  • Weighted averaging of words vectors of words in a sentence
    • But this ends up ignoring word order again!
  • Combine word vectors in a way informed by the parse tree (bit vague, see p. 2)
    • But this only works on sentence level due to the parsing

Algorithms

In neural language models, we have a big matrix W where each column corresponds to a word vector of a word $w_t$ in the vocabulary. So the word vector of word $w_t$ corresponds to column $t$.

The learning objective is fairly straightforward: given a word sequence (with corresponding input columns from matrix W that you either average or concatenate), the task is to maximize the average log probability of the next word. For training words $w_1, w_2,..., w_T$:

$$\frac{1}{T} \sum_{t=k}^{T-k} log p(w_t | w_{t-k}, ..., w_{t+k}$$

$k$ is here the context around the current word that you want to use to predict the current word, defined as a window. This is also what explains the bounds of the sum: if you look back k words and ahead k words, you can start at the earliest at $w_k$ and end at $w_{T-k}$.

Hmmm why still divide by T then? Just convenience, since it's normalized later anyways? Maybe because we pad with a special token, such as NULL?

Implementations such as doc2vec use binary Huffman trees to assign the shortest code to the most frequent words in the vocabulary. This leads to a nice speedup when used in combination with hierarchical softmax. (Hierarchical softmax does not do a straight sum over the whole vocabulary, which is slow for large vocabularies, but instead constructs a tree (in doc2vec a Huffman tree) and then express the probability of each word as the probability of choosing the tree path towards the word. The success of this approach depends on the quality of the tree; a Huffman tree is a typical choice here.)

Given the true word, you can update matrix W with the word vectors using backpropagation. The outcome of a converged training procedure is that "words with similar meaning are mapped to a similar position in the vector space." (2-3)

Given this desirable property you see that:

  • the "difference between word vectors also carry meaning." (3)
    • which allows the vector space to capture conceptual analogies such as king - man + woman = queen (i.e. it is under ideal circumstances possible to capture concepts as vector operations).
  • it is also possible to learn a linear matrix transformation to translate between languages

Paragraph vector model

The idea behind the word vector learning is that "they can eventually capture semantics as an indirect result of the prediction task." (3)

This idea is extended to the level of paragraph as follows: "The paragraph vectors are also asked to contribute to the prediction task of the next word given many contexts sampled from the paragraph." (3)

In the Paragraph Vector Model you have another matrix $D$ alongside the matrix $W$, where each column indicates a paragraph vector.

Like in the task for training word embeddings, you use the word vectors of surrounding words in order to predict the next word. These word embeddings attempt to capture semantic properties of the whole vocabulary and does not differentiate that a word in the context of one paragraph may be slightly different than the same word occurring in another paragraph.

The Paragraph Vector Model however also uses a vector for a paragraph and involves this in the prediction task. In this paper, this is done by concatenating the paragraph vector and word vectors (of the words sampled from the paragraph). What is meant with "sampling from the paragraph" in this paper is just that you do the prediction task using a sliding window over the paragraph, not that you sample random words (this would not be semantically meaningful).

But what does this extra paragraph vector capture?

The paragraph token can be thought of as another word. It acts as a memory that remembers what is missing from the current context – or the topic of the paragraph. For this reason, we often call this model the Distributed Memory Model of Paragraph Vectors (PV-DM).(3)

And the next paragraph explains what I mentioned above already: the paragraph captures semantics from all context in one particular paragraph, whereas the word vector capture all contexts of that word independent of which paragraph they occur in:

The contexts are fixed-length and sampled from a sliding window over the paragraph. The paragraph vector is shared across all contexts generated from the same paragraph but not across paragraphs. The word vector matrix W, however, is shared across paragraphs. I.e., the vector for “powerful” is the same for all paragraphs. (3)

This means that if you have a sliding window of $k$ as the context around a given word, then the corresponding paragraph vector captures something about the whole paragraph context (which is why you may informally want to call it "memory" of the "missing" context that is not captured in the current window; or even more informally, the paragraph "topic").

The paragraph vectors are trained the same way as the word vectors (in that sense they are treated as just another "word"). At prediction time you need to infer a paragraph vector for an unseen paragraph. In this case we do have the information on the word vectors and the weights of the softmax classifier. You fix those and then infer a paragraph vector using gradient descent. That is, you again do a sliding window over words from the new unseen paragraph (but we do have these word vectors, assuming the words in the new paragraph were in the vocabulary) and try to predict the next word from this local context. However, by now freezing word vectors and the weights of the softmax classifier, we can only change the randomly initialized paragraph vector in order to improve our prediction of the subsequent word.

Once these paragraphs are trained, the paragraph vectors can be used as a representation of the paragraph content. Application: "We can feed these features directly to conventional machine learning techniques such as logistic regression, support vector machines or K-means." (3)

Summary:

In summary, the algorithm itself has two key stages: 1) training to get word vectors W, softmax weights U, b and paragraph vectors D on already seen paragraphs; and 2) “the inference stage” to get paragraph vectors D for new paragraphs (never seen before) by adding more columns in D and gradient descending on D while holding W,U, b fixed. We useD to make a prediction about some particular labels using a standard classifier, e.g., logistic regression. (3)

Pros

  • Unsupervised, so applicable when little to no labeled data is available.

Compared to bag of words:

  • Paragraph vectors also capture word semantics (but more local to the paragraphs) just like word vectors
  • Word order is taken into account (similar to n-grams with large n)
    • But the advantage over n-grams with large n, is that the large n leads to a huge increase in dimensionality.
    • The paragraph embeddings are more dense and are more likely to generalize

Paragraph vectors without word ordering: distributed bag of words

Above I made a remark about not just randomly sampling words from the paragraph, but actually this method pretty much does that!

This version is called the Distributed Bag of Words variant of the Paragraph Vector approach: PV-DBOW.

  • Ignore context words (word vectors) in the input
  • Force the model to predict randomly sampled words from the paragraph
    • "In reality, what this means is that at each iteration of stochastic gradient descent, we sample a text window, then sample a random word from the text window and form a classification task given the Paragraph Vector." (4)

Advantages:

  • Conceptually simple
  • Only needs to store the softmax weights (used in prediction) since the word vectors are now ignored
  • Resembled the Skip-gram model in word vectors
    • What's slightly confusing is that PV-DM is like CBOW, whereas PV-DBOV is more like Skip-gram. See explanation directly below.

How do PV-DM and PV-DBOW relate to CBOW and Skip-gram in word embedding training?

  • CBOW: take the surrounding context, and predict the next/masked word
    • Cf. PV-DM: you take the surrounding context including the paragraph vector and predict the next/masked word.
  • Skip-gram: learn word embeddings by taking a word and then predicting the surrounding context
    • Cf. PV-DBOW: in this case the single "word" you take is only the paragraph vector without any surrounding context (which is treated as just another "word" in the training procedure as well) and then you try to predict words from the paragraph.

The authors found that results are very good is you combine PV-DM and PV-DBOW, i.e. let your final paragraph vectors be a combination of the vectors produced by these two methods.

Experiments

I mostly skip this, refer to the paper.

One experiment I found interesting is the following:

From such collection, we derive a new dataset to test vector representations of paragraphs. For each query, we create a triplet of paragraphs: the two paragraphs are results of the same query, whereas the third paragraph is a randomly sampled paragraph from the rest of the collection (returned as the result of a different query). Our goal is to identify which of the three paragraphs are results of the same query. To achieve this, we will use paragraph vectors and compute the distances the paragraphs. A better representation is one that achieves a small distance for pairs of paragraphs of the same query and a larg distance for pairs of paragraphs of different queries. (6)

In this experiment you have three paragraphs, where two are returned by the same query and another one is randomly sampled from the dataset (considered irrelevant; so maybe randomly sampled from the documents belonging to other queries?).

Can I do something similar in my thesis work? Although I don't have a data set with queries. I'd have to manually create a set of related documents. I could potentially use cases that have references in them to other cases according to rechtspraak.nl (this is essentially a supervised judgement of their relation; this is a formal relation).

Observations and take-aways

  • PV-DM is the superior approach and outperforms PV-DBOW consistently; however adding PV-DM to PV-DBOW is again consistently superior.
  • Concatenation in PV-DM is better, maybe because averaging throws away some word ordering information.
  • Do cross validation on window size. Somewhere between 5-12 is typically appropriate
    • TODO update my hyperparameter tuning pipeline