A More Elegant Word Embedding Model (II): Modeling Language
From Conditional Probability to Mutual Information
Currently, the basic principle behind word embedding models is that the distribution of a word's context can reveal that word's meaning—much like "look at the company you keep, and you'll know who you are." So the core of word embedding models is modeling the relationship between a word and its context. Apart from GloVe, almost all word embedding models model the conditional probability $P(w|context)$; for example, Word2Vec's skip-gram model models the conditional probability $P(w_2|w_1)$. But this quantity has some drawbacks. First, it is asymmetric: $P(w_2|w_1)$ is not necessarily equal to $P(w_1|w_2)$, which means that when modeling, we have to distinguish context vectors from target vectors—they can't live in the same vector space. Second, it is a bounded, normalized quantity, which means we must use something like softmax to squash and normalize it, creating difficulties for optimization.
In fact, in the world of NLP, there is a more symmetric quantity that matters even more than the plain $P(w_2|w_1)$, namely
\[\frac{P(w_1,w_2)}{P(w_1)P(w_2)}=\frac{P(w_2|w_1)}{P(w_2)}\tag{1}\]
The rough meaning of this quantity is "how many times more likely two words are to actually co-occur, compared to meeting purely by chance." If it is much greater than 1, that indicates the two words tend to appear together rather than combine at random; and conversely, if it's much less than 1, it means the two words are deliberately avoiding each other. This quantity plays a pivotal role in NLP. Let's call it the "relatedness," though its logarithm is even more famous, going by the name Pointwise Mutual Information (PMI):
\[\text{PMI}(w_1,w_2)=\log \frac{P(w_1,w_2)}{P(w_1)P(w_2)}\tag{2}\]
With this theoretical groundwork, we believe that directly modeling relatedness would be more sensible than directly modeling the conditional probability $P(w_2|w_1)$, so this post proceeds from that angle. Before we get there, let's first showcase a beautiful property of mutual information itself. more
Additivity of Mutual Information
Under the naive (independence) assumption, relatedness (equivalently, mutual information) has a very elegant decomposition property. The so-called naive assumption is that features are mutually independent, giving us $P(a,b)=P(a)P(b)$—that is, the joint probability factorizes, which simplifies the model.
For example, consider the mutual information between two quantities $Q,A$, where $Q,A$ is not a single feature but a combination of multiple features: $Q=(q_1,\dots,q_k),A=(a_1,\dots,a_l)$. Now consider their relatedness, namely
\[\begin{aligned}\frac{P(Q,A)}{P(Q)P(A)}=&\frac{P(q_1,\dots,q_k;a_{1},\dots,a_{l})}{P(q_1,\dots,q_k)P(a_{1},\dots,a_{l})}\\ =&\frac{P(q_1,\dots,q_k|a_{1},\dots,a_{l})}{P(q_1,\dots,q_k)}\end{aligned}\tag{3}\]
Applying the naive assumption gives
\[\frac{P(q_1,\dots,q_k|a_{1},\dots,a_{l})}{P(q_1,\dots,q_k)}=\frac{\prod_{i=1}^k P(q_i|a_{1},\dots,a_{l})}{\prod_{i=1}^k P(q_i)}\tag{4}\]
Using Bayes' rule, we get
\[\begin{aligned}\frac{\prod_{i=1}^k P(q_i|a_{1},\dots,a_{l})}{\prod_{i=1}^k P(q_i)}=&\frac{\prod_{i=1}^k P(a_{1},\dots,a_{l}|q_i)P(q_i)/P(a_{1},\dots,a_{l})}{\prod_{i=1}^k P(q_i)}\\ =&\prod_{i=1}^k\frac{P(a_{1},\dots,a_{l}|q_i)}{P(a_{1},\dots,a_{l})}\end{aligned}\tag{5}\]
Applying the naive assumption once more gives
\[\begin{aligned}\prod_{i=1}^k\frac{P(a_{1},\dots,a_{l}|q_i)}{P(a_{1},\dots,a_{l})}=&\prod_{i=1}^k\frac{\prod_{j=1}^{l} P(a_j|q_i)}{\prod_{j=1}^{l} P(a_j)}\\ =&\prod_{i=1}^k\prod_{j=1}^{l} \frac{P(q_i,a_j)}{P(q_i)P(a_j)}\end{aligned}\tag{6}\]
This shows that, under the naive assumption, the relatedness between two multivariate variables equals the product of the pairwise relatedness values between their individual components. If we take the logarithm of both sides, the result looks even nicer:
\[\text{PMI}(Q,A)=\sum_{i=1}^k\sum_{j=1}^{l} \text{PMI}(q_i,a_j)\tag{7}\]
In other words, the mutual information between two multivariate variables equals the sum of the pairwise mutual information between the individual variables. Put differently, mutual information is additive!
Intermission: A Side Story
To help everyone get a more intuitive feel for the principles behind word embedding modeling, let's imagine ourselves as the "matchmaker god" of the language world, whose job is to measure the "fated affinity" between any two words, paving the way for each word to find its perfect match.
As the saying goes, "fated souls will meet though a thousand miles apart; unfated ones won't recognize each other face to face." For every word, its perfect match is naturally its "fated word." But what makes two words "fated" for each other? Naturally, it's "you're in my eyes, and I'm in yours." As mentioned earlier, the skip-gram model cares about the conditional probability $P(w_2|w_1)$, and the result is that "$w_1$ may be in the eyes of $w_2$, but $w_2$ isn't necessarily in the eyes of $w_1$." In other words, $w_2$ tends to be more of a "player" in the word world—like stopwords such as "的" (de) or "了" (le), which can mix with anybody, but aren't necessarily sincere toward anybody. So, to achieve "you're in me, and I'm in you," we must consider $P(w_2|w_1)$ and $P(w_1|w_2)$ simultaneously—or, better, consider a more symmetric quantity, namely the "relatedness" mentioned earlier. So our matchmaker god decides to use relatedness to quantify the "affinity" between two words.
Next, the matchmaker god gets to work, calculating the "affinity" between word pairs one by one. But partway through, he runs into serious trouble.
First, there are simply too many words to get through them all. The word world has tens of thousands, even hundreds of thousands—and in the future perhaps millions—of words. If we were to compute and record the affinity for every pair, we'd end up with a table containing billions or even trillions of entries. The workload is enormous—the matchmaker god might retire long before finishing the job. But from a diligent standpoint, we can't just ignore the possibility of any two words being related!
Second, however many times two words happen to encounter each other, that's still just a drop in the ocean compared to the vast span of history. Does the fact that two words have never met really mean they have no affinity at all? Just because it hasn't happened yet doesn't mean it never will. As a careful matchmaker, one obviously can't jump to such a rash conclusion. The relationships among words are intricate and tangled, so even if two words have never co-occurred, we still can't simply write them off—we need to estimate their affinity value nonetheless.
Translated automatically with claude-sonnet-5; all equations are reproduced verbatim from the source. Copyright remains with the original author.