SVD Decomposition (III): Is Even Word2Vec Just an SVD?

SVD分解(三)：连Word2Vec都只不过是个SVD？ 苏剑林 · 2017-02-23 · Machine Learning deep learning SVD word vector

This post brings some "heavyweight" news: as the title suggests, it turns out that even the famous deep-learning word-embedding tool Word2Vec is nothing more than an SVD!

Of course, die-hard Word2Vec fans need not get too worked up — here I'm only saying that they are equivalent in model structure, not entirely identical; Word2Vec still has its own distinctive features. Still, once I've laid out this explanation, I expect a lot of related questions will suddenly make sense too.

Word Embeddings = One-Hot

Let's first revisit a post from last year, What's Really Going On with Word Vectors and Embeddings?. Its main point was: the so-called Embedding layer is nothing but a fully-connected layer applied to one-hot vectors (again, I mean this is literally equivalent, not just "analogous"); the word vectors are simply the parameters of that fully-connected layer. As for Word2Vec, it trains the Embedding layer using a heavily simplified language model to obtain word vectors (there are many optimization tricks involved, but the model structure itself is just this simple). Word vectors reduce the risk of overfitting because tools like Word2Vec pretrain this Embedding layer in an unsupervised way on large-scale corpora — this benefit has nothing intrinsically to do with one-hot encoding, embeddings, or word vectors per se.

With this view in hand, we can immediately explain why a certain practice we used before actually works. In sentiment classification, if we already have word vectors and want to obtain a sentence vector, the simplest approach is to directly sum (or average) the word vectors of the words in the sentence — this typically achieves around 85% accuracy. In fact, this is exactly what Facebook's FastText text-classification tool does (FastText additionally introduces n-gram features to alleviate the word-order issue, but overall it's still averaging feature vectors to get a sentence vector). Why does such a seemingly unintuitive, crude approach achieve such decent accuracy? more

Let's go back to the era of one-hot encoding, where we represent a sentence like this. Suppose we one-hot encode the six words "I," "love," "science," "space," "not," "wrong" as follows:

$$\begin{array}{c|c}\hline\text{I} & [1, 0, 0, 0, 0, 0]\\ \text{love} & [0, 1, 0, 0, 0, 0]\\ \text{science} & [0, 0, 1, 0, 0, 0]\\ \text{space} & [0, 0, 0, 1, 0, 0]\\ \text{not} & [0, 0, 0, 0, 1, 0]\\ \text{wrong} & [0, 0, 0, 0, 0, 1]\\ \hline \end{array}$$

Then, ignoring word order, the phrase "I love space science" can be represented by the following vector (bag of words):

$$\begin{pmatrix}1 & 1 & 1 & 1 & 0 & 0\end{pmatrix}$$

With this vector, to do classification with a neural network, we can follow it with a fully-connected layer with 3 hidden units:

$$\begin{aligned}&\begin{pmatrix}1 & 1 & 1 & 1 & 0 & 0\end{pmatrix}\begin{pmatrix}w_{11} & w_{12} & w_{13}\\ w_{21} & w_{22} & w_{23}\\ w_{31} & w_{32} & w_{33}\\ w_{41} & w_{42} & w_{43}\\ w_{51} & w_{52} & w_{53}\\ w_{61} & w_{62} & w_{63}\end{pmatrix}\\ =&\begin{pmatrix}w_{11}+w_{21}+w_{31}+w_{41} & w_{12}+w_{22}+w_{32}+w_{42} & w_{13}+w_{23}+w_{33}+w_{43}\end{pmatrix}\end{aligned}$$

Hey — isn't this just taking the first four vectors and adding them up?

Now things become clear. If we use the traditional bag-of-words model, ignoring word order, followed by a fully-connected layer — and if, to prevent overfitting, the parameters of this fully-connected layer are replaced by pretrained word vectors — then the result is equivalent to simply taking out the corresponding word vectors and summing them! In other words, summing word vectors to get a sentence vector is really just the equivalent of the traditional bag-of-words model!

Word2Vec = SVD?

Throughout, whenever I mention the equivalence between Word2Vec and SVD, I always attach a question mark to it. That's because, while the two are equivalent in model structure, they differ in implementation — whether this counts as "equivalent" really depends on the reader's own definition of the word.

In fact, the concept of word vectors has been around for a long time, though back then it wasn't called Word Embedding but rather distributed representation. The original idea was that a word's context can help us understand the word itself. Now suppose the total vocabulary has $N$ words; one-hot encoding represents each word as a $N$-dimensional vector. Distributed representation, on the other hand, works by opening a window (some number of words before and after, plus the current word, forming a window), and then tallying the distribution of the words appearing before and after the current word — using this distribution to represent the current word. This distribution can also be represented as a corresponding $N$-dimensional vector. Since the word is now represented through its contextual distribution rather than in isolation as a "one-hot" vector, it can capture semantic relatedness. The problem, though, is that it's still $N$-dimensional — the dimensionality is still too large, and the entire word-vector table (co-occurrence matrix) is too sparse.

What to do? Mathematicians actually solved this long ago: for a sparse matrix, a scheme that can both reduce dimensionality and improve generalization is to apply SVD decomposition to the matrix. And as the first post in this series pointed out, SVD decomposition is equivalent to a three-layer autoencoder. So, viewed through today's lens, this scheme says: the original distributed-representation word vectors are $N$-dimensional, which is too large, so we can use an autoencoder to reduce the dimensionality. Let the number of hidden units in the autoencoder be $n$; set $n$ to an appropriate value, train the autoencoder, and then directly take the $n$-dimensional result from the hidden layer as the new word vector. So this is just an autoencoder scheme with $N$-dimensional input, $n$ hidden units, and $N$-dimensional output, which is also equivalent to an SVD decomposition.

So, we still haven't gotten to Word2Vec — how should we view Word2Vec's model? One of Word2Vec's schemes, CBOW, works by summing the word vectors of several surrounding words, then feeding the sum through a $N$-dimensional fully-connected layer, followed by a softmax to predict the probability of the current word. As established in the first half of this post, this kind of word-vector summation is equivalent to the bag-of-words model followed by a fully-connected layer (whose parameters constitute the word-vector table). Viewed this way, Word2Vec is likewise just a three-layer neural network with $N$-dimensional input, $n$ hidden units, and $N$-dimensional output. So structurally speaking, it is equivalent to an autoencoder, and hence equivalent to an SVD decomposition.

From an implementation standpoint, however, the differences are quite obvious:

1. Word2Vec's scheme can be viewed as predicting the current word from its surrounding words, whereas the autoencoder or SVD instead predicts the surrounding words from the surrounding words themselves;
2. Word2Vec ends with a softmax to predict probabilities, meaning it applies a non-linear transformation, whereas the autoencoder or SVD does not.

I don't have a rigorous mathematical proof of how much these two differences affect the quality of the resulting word vectors, but from practical testing, given the same corpus, Word2Vec's word vectors do seem to come out somewhat better in quality.

A Non-Summary Summary

Through a series of brainstorming exercises, this post has examined the relationship between the traditional distributed representation and the Word2Vec model, arriving at the conclusions above. The main purpose of this kind of thinking is to connect ideas across different areas so that our understanding gets closer to the underlying essence — and this may well provide important guidance for how we apply, or even build, models. Overall, the message running through this series of posts is that once we write many operations or models in matrix form, we can see the essence of a lot of things much more clearly, and this can help point us toward directions for improvement. For instance, many models can in fact be written as matrix multiplications, and a matrix multiplication is equivalent to a single-layer neural network — so if it's a neural network, why not stack more layers? Why not add an activation function? Why not decompose it via SVD? After all, as the second post in this series showed, SVD carries a clear clustering interpretation. Thinking along such lines can help us construct models, and even generalize them.