A More Elegant Word Embedding Model (IV): Solving the Model
Loss Function
Now let's define the loss so that we can solve for the individual word vectors. Let $\tilde{P}$ denote the frequency estimate of $P$; then we can directly take the following as our loss
\[\sum_{w_i,w_j}\left(\langle \boldsymbol{v}_i, \boldsymbol{v}_j\rangle-\log\frac{\tilde{P}(w_i,w_j)}{\tilde{P}(w_i)\tilde{P}(w_j)}\right)^2\tag{16}\]
By comparison, whether in terms of parameter count or model form, this approach is simpler than GloVe, which is why we call it simpler GloVe. The GloVe model is
\[\sum_{w_i,w_j}\left(\langle \boldsymbol{v}_i, \boldsymbol{\hat{v}}_j\rangle+b_i+\hat{b}_j-\log X_{ij}\right)^2\tag{17}\]
In the GloVe model, the center word vectors and context word vectors are treated as distinct, and the final model output is suggested to be the sum of the two sets of word vectors — supposedly this works better. This is a somewhat forced trick, though not really a flaw in itself. The biggest problem is that the parameter $b_i,\hat{b}_j$ is also trainable, which makes the model severely ill-posed! We have
\[\begin{aligned}&\sum_{w_i,w_j}\left(\langle \boldsymbol{v}_i, \boldsymbol{\hat{v}}_j\rangle+b_i+\hat{b}_j-\log \tilde{P}(w_i,w_j)\right)^2\\ =&\sum_{w_i,w_j}\left[\langle \boldsymbol{v}_i+\boldsymbol{c}, \boldsymbol{\hat{v}}_j+\boldsymbol{c}\rangle+\Big(b_i-\langle \boldsymbol{v}_i, \boldsymbol{c}\rangle - \frac{|\boldsymbol{c}|^2}{2}\Big)\right.\\ &\qquad\qquad\qquad\qquad\left.+\Big(\hat{b}_j-\langle \boldsymbol{\hat{v}}_j, \boldsymbol{c}\rangle - \frac{|\boldsymbol{c}|^2}{2}\Big)-\log X_{ij}\right]^2\end{aligned}\tag{18}\]
That is to say, if you have a set of solutions, then adding an arbitrary constant vector to all the word vectors still gives you a valid set of solutions! This is a serious problem — we have no way of predicting which particular solution we'll end up with, and if the constant vector added happens to be very large, then all sorts of similarity measures become meaningless (for instance, the cosine similarity between any two words would approach 1). Indeed, if you check the word vectors produced by GloVe, you'll find that the norms of stop-word vectors are much larger than those of ordinary words — meaning that when a bunch of words are put together, the stop words end up having a disproportionately large influence, which is clearly not helpful for downstream models. (Although, judging from current experimental results with GloVe, perhaps this is just me being overly fussy.)
Estimating Mutual Information
To solve the model, the first issue we need to deal with is how to compute $P(w_i,w_j),P(w_i),P(w_j)$. $P(w_i),P(w_j)$ is simple — we can just estimate it directly via counting — but what about $P(w_i,w_j)$? What exactly counts as two words co-occurring? Of course, different applications can adopt different schemes in practice. For example, we could say that two words appearing together in the same article count as having "met" once — such a scheme is usually helpful for topic classification, but it's computationally expensive. A more common scheme is to fix an integer, called the window size, and treat the window words before and after a given word as having "met" it.
One detail worth noting: should the co-occurrence of a center word with itself be counted? If we define the window as all words within a distance of "window" from the center word, then technically it should be included — but if we do include it, it carries no predictive meaning, since this term is always present. On the other hand, if we exclude it, this would reduce the mutual information of a word with itself. So we adopt a small trick: we simply don't count identical co-occurrence terms, letting the model learn this on its own. In other words, even if the center word itself appears again in its own context, we don't include that in the loss — since the amount of data is far greater than the number of parameters, this term can always be learned implicitly anyway.
Weighting and Downsampling
The GloVe model defines the following weighting formula:
\[\lambda_{ij}=\Big(\min\{x_{ij}/x_{max}, 1\}\Big)^{\alpha}\tag{19}\]
where $x_{ij}$ represents the co-occurrence count for the word pair $(w_i,w_j)$, and $x_{max},\alpha$ is a fixed constant, usually taken as $x_{max}=100,\alpha=3/4$. That is, we down-weight word pairs with low co-occurrence counts, since they are more likely to be noise. Thus the final GloVe loss is
\[\sum_{w_i,w_j}\lambda_{ij}\left(\langle \boldsymbol{v}_i, \boldsymbol{v}_j\rangle+b_i+b_j-\log \tilde{P}(w_i,w_j)\right)^2\tag{20}\]
In our text model, we continue to use this weighting scheme, but with some modifications. First, we raise the frequency to the power $\alpha$, which is equivalent to boosting the weight of low-frequency terms — this is basically consistent with what word2vec does. What's worth thinking about is the truncation operation $\min$: applying this truncation is equivalent to substantially reducing the weight of high-frequency words, somewhat similar to word2vec's downsampling of high-frequency words. This can improve the learning of low-frequency words, but the possible downside is that the norms of high-frequency words don't get learned well. We'll see this in the section "The Meaning of Vector Norms." Overall, different scenarios have different needs, so in the source code we eventually release, we allow the user to decide for themselves whether to apply this truncation to the weight.
Adagrad
Just like GloVe, we also use the Adagrad algorithm for optimization. The reason for using Adagrad is that it is probably the simplest adaptive-learning-rate algorithm currently available.
However, I discovered that the way Adagrad is implemented in the GloVe source code is actually wrong!! I don't know whether GloVe's version is a deliberate improvement or simply a typo (though a typo seems unlikely, doesn't it?). In any case, if I directly ported that iteration process, unchanged, into the simpler GloVe model described here, all sorts of intractable NaNs would show up immediately! If we instead write it in the standard Adagrad form, the NaNs disappear.
Given a word pair $w_i,w_j$, we obtain the loss
\[L=\lambda_{ij}\left(\langle \boldsymbol{v}_i, \boldsymbol{v}_j\rangle-\log\frac{\tilde{P}(w_i,w_j)}{\tilde{P}(w_i)\tilde{P}(w_j)}\right)^2\tag{21}\]
whose gradient is
\[\begin{aligned}\nabla_{\boldsymbol{v}_i} L=\lambda_{ij}\left(\langle \boldsymbol{v}_i, \boldsymbol{v}_j\rangle-\log\frac{\tilde{P}(w_i,w_j)}{\tilde{P}(w_i)\tilde{P}(w_j)}\right)\boldsymbol{v}_j\\ \nabla_{\boldsymbol{v}_j} L=\lambda_{ij}\left(\langle \boldsymbol{v}_i, \boldsymbol{v}_j\rangle-\log\frac{\tilde{P}(w_i,w_j)}{\tilde{P}(w_i)\tilde{P}(w_j)}\right)\boldsymbol{v}_i \end{aligned}\tag{22}\]
We then update the parameters according to the standard Adagrad formula. Taking the default initial learning rate to be $\eta=0.1$, the update rule is
\[\left\{\begin{aligned}\boldsymbol{g}_{\gamma}^{(n)} =& \nabla_{\boldsymbol{v}_{\gamma}^{(n)}} L\\ \boldsymbol{G}_{\gamma}^{(n)} =& \boldsymbol{G}_{\gamma}^{(n-1)} + \boldsymbol{g}_{\gamma}^{(n)}\otimes \boldsymbol{g}_{\gamma}^{(n)}\\ \boldsymbol{v}_{\gamma}^{(n)} =& \boldsymbol{v}_{\gamma}^{(n-1)} - \frac{\boldsymbol{g}_{\gamma}^{(n)}}{\sqrt{\boldsymbol{G}_{\gamma}^{(n-1)}}}\eta \end{aligned}\right.,\,\gamma=i,j \tag{23}\]
From this formula, we can see that Adagrad is essentially insensitive to scaling of the loss — in other words, multiplying the loss by 10 has almost no effect on the final optimization outcome. But in plain stochastic gradient descent, multiplying the loss by 10 would be equivalent to multiplying the learning rate by 10.
Translated automatically with claude-sonnet-5; all equations are reproduced verbatim from the source. Copyright remains with the original author.