A More Distinctive Word Embedding Model (III): A Model that Describes Relatedness
Geometric Word Vectors
The story about the "Moon Old Man" (matchmaker deity) above was just a bit of fantasy, but the problem it points to is real. Following traditional NLP methods, we can tally the co-occurrence frequency of any two words, together with each word's own frequency, and use these to compute their degree of relatedness, thereby obtaining a "relatedness matrix." However, as mentioned before, this co-occurrence matrix is far too large — it must be compressed and dimensionally reduced, and at the same time we need to do some data smoothing, assigning a reasonable estimate of relatedness to word pairs that never actually co-occurred.
Among existing machine learning approaches, we already have some experience reducing the dimensionality of large matrices — SVD and pLSA, for instance. SVD reduces the dimensionality of an arbitrary matrix, while pLSA reduces the dimensionality of a transition probability matrix $P(j|i)$. The two share a similar idea: decomposing a large matrix $\boldsymbol{A}$ into the product of two smaller matrices $\boldsymbol{A}\approx\boldsymbol{B}\boldsymbol{C}$, where the number of rows of $\boldsymbol{B}$ equals the number of rows of $\boldsymbol{A}$, the number of columns of $\boldsymbol{C}$ equals the number of columns of $\boldsymbol{A}$, and both factors are themselves much smaller than $\boldsymbol{A}$. If we impose no constraints on $\boldsymbol{B},\boldsymbol{C}$, this is SVD; if we impose a positive-definite normalization constraint on $\boldsymbol{B},\boldsymbol{C}$, this is pLSA.
But the situation is a bit different for a relatedness matrix: it is positive definite but not normalized, so we need to design a new compression scheme for it. Drawing on the experience of matrix factorization, we might imagine placing every word into a $n$-dimensional space — i.e., representing it with a vector in $n$-dimensional space — and assume that their relatedness is some function of the inner product (why the inner product? because matrix multiplication is fundamentally just repeated inner products):
\[\frac{P(w_i,w_j)}{P(w_i)P(w_j)}=f\big(\langle \boldsymbol{v}_i, \boldsymbol{v}_j\rangle\big)\tag{8}\]
Here the bold $\boldsymbol{v}_i, \boldsymbol{v}_j$ denotes the word vector corresponding to word $w_i,w_j$. Geometrically, we are placing words into $n$-dimensional space and representing a word by a point in that space.
Since geometry gives us an intuitive feel while semantics feels complex, ideally we would like to use geometric relations to reflect semantic relations. Below, based on the geometric properties we would like to have, we'll pin down the undetermined function $f$. As it happens, the GloVe paper does something similar and is quite inspiring, but its derivation really isn't very elegant. Note that the viewpoint here is novel — we determine the model from the properties we want, rather than deriving the properties after already having a model.
Airport − Airplane + Train = Train Station
One of the most celebrated properties of word vectors is "word analogy" — the classic "king − man + woman = queen" example (whether this property is actually necessary for word vectors is debatable, but it's at least a nice bonus). However, Chinese and English contexts differ, and this particular example is hard to reproduce in Chinese corpora. Of course, there's no shortage of such examples — no need to be fixated on "foreign examples." For instance, in Chinese corpora, it's easy to find that "airport − airplane + train = train station," or more precisely:
\[\boldsymbol{v}(\text{airport})-\boldsymbol{v}(\text{airplane})+\boldsymbol{v}(\text{train})=\boldsymbol{v}(\text{train station})\tag{9}\]
Why do word vectors have this property? A recent paper, Skip-Gram − Zipf + Uniform = Vector Additivity, offers a theoretical analysis of this phenomenon, deriving this result from a set of fairly strong assumptions. What we're going to do now, which may seem rather bold, is: take this property directly as one of the defining conditions of the word vector model!
Specifically, the additivity of word meaning is directly expressed as the additivity of word vectors, and we take this property as part of the definition of the word vector model. We will start from this property and work backwards to pin down the function $f$ that was left undetermined in the previous section. In doing so, we not only find a reasonable justification for determining $f$, but also explain the linear-arithmetic property of word vectors — because this is fundamentally part of the model's definition, not a consequence derived from the model.
Since it's a linear relation, we can rearrange terms to get "airport + train = train station + airplane." Let's now think about what this equation actually expresses, purely from a semantic standpoint. As mentioned at the start, nearly all word vector models are built on the assumption that word meaning can be inferred from the distribution of contexts. Given that "airport + train = train station + airplane," it clearly means that the contexts shared by "airport" and "train" are essentially the same as the contexts shared by "train station" and "airplane." Put plainly, semantic equivalence here is like saying "if two people have very similar standards for choosing a partner, then they surely have a lot in common too." At this point, the form of $f$ practically suggests itself!
The Form of the Model
Since the degree of relatedness between words is described by their relatedness score, if "airport + train = train station + airplane," then we should have:
\[\frac{P(\text{airport},\text{train};w)}{P(\text{airport},\text{train})P(w)}\quad=\quad\frac{P(\text{train station},\text{airplane};w)}{P(\text{train station},\text{airplane})P(w)}\tag{10}\]
Here $w$ is an arbitrary context word. Since we don't particularly care about word order and only care about the average distribution of the context itself, we can use a naive assumption to simplify the equation above. Then, from equation $(6)$, we get:
\[\frac{P(\text{airport},w)}{P(\text{airport})P(w)}\times\frac{P(\text{train},w)}{P(\text{train})P(w)}=\frac{P(\text{train station},w)}{P(\text{train station})P(w)}\times\frac{P(\text{airplane},w)}{P(\text{airplane})P(w)}\tag{11}\]
Substituting this into the earlier assumed equation $(8)$, we obtain
\[f\big(\langle \boldsymbol{v}_{\text{airport}}, \boldsymbol{v}_w\rangle\big)f\big(\langle \boldsymbol{v}_{\text{train}}, \boldsymbol{v}_w\rangle\big) = f\big(\langle \boldsymbol{v}_{\text{airplane}}, \boldsymbol{v}_w\rangle\big) f\big(\langle \boldsymbol{v}_{\text{train station}}, \boldsymbol{v}_w\rangle\big)\tag{12}\]
Finally substituting into equation $(9)$, we get
\[\begin{aligned}&\left.f\big(\langle \boldsymbol{v}_{\text{airport}}, \boldsymbol{v}_w\rangle\big)f\big(\langle \boldsymbol{v}_{\text{train}}, \boldsymbol{v}_w\rangle\big)\middle/f\big(\langle \boldsymbol{v}_{\text{airplane}}, \boldsymbol{v}_w\rangle\big)\right.\\ =&f\big(\langle \boldsymbol{v}_{\text{airport}}-\boldsymbol{v}_{\text{airplane}}+\boldsymbol{v}_{\text{train}}, \boldsymbol{v}_w\rangle\big)\\ =&f\big(\langle \boldsymbol{v}_{\text{airport}}, \boldsymbol{v}_w\rangle+\langle\boldsymbol{v}_{\text{train}}, \boldsymbol{v}_w\rangle-\langle\boldsymbol{v}_{\text{airplane}}, \boldsymbol{v}_w\rangle\big) \end{aligned}\tag{13}\]
Here $\boldsymbol{v}_w$ is arbitrary, so the equation above is equivalent to the condition
$$f(x+y-z)=f(x)f(y)/f(z)$$
Adding a continuity condition, the general solution to this equation (whose derivation can be found in any standard mathematical analysis textbook) is
$$f(x)=e^{\alpha x}$$
That is, an exponential form. So we arrive at the following result: in order for the resulting word vectors to have the additivity property, relatedness must be modeled with an exponential form:
\[\frac{P(w_i,w_j)}{P(w_i)P(w_j)}=e^{\langle \boldsymbol{v}_i, \boldsymbol{v}_j\rangle}\tag{14}\]
Equivalently, this amounts to modeling mutual information:
\[\label{eq:model}\text{PMI}(w_i,w_j)=\langle \boldsymbol{v}_i, \boldsymbol{v}_j\rangle\tag{15}\]
With this, we've completed the derivation of the model's form. Formally, it resembles an SVD decomposition of the mutual information matrix.
Forgetting About Normalization
Unlike typical probabilistic models, we haven't divided by a normalization factor to make things sum to a proper probability. The consequence is that for the model in this article — and this includes the GloVe model as well — we cannot discuss anything related to normalization, or we'll run into self-contradictory results.
In fact, this amounts to trading space for time: since we don't divide by a normalization factor, yet we still need the results to be close to normalized, we're forced to precompute the mutual information for all co-occurring pairs and store them in advance, which typically requires a fair amount of memory. The payoff for this step is that the number of co-occurring pairs is actually rather limited (the number of "word pairs" is always fewer than the number of sentences), so when you have large-scale corpora and enough memory, using the GloVe model is often much faster than using word2vec's skip-gram model.
Furthermore, since the model in this article essentially differs from word2vec's skip-gram model only by a normalization factor, it's clear that whether some of the derivations here can be directly transferred to the skip-gram model basically depends on whether, after training, the skip-gram model's normalization factor ends up close to 1.
Translated automatically with claude-sonnet-5; all equations are reproduced verbatim from the source. Copyright remains with the original author.