The Minimum Entropy Principle (IV): "Birds of a Feather" — From the Library to Word Embeddings
From the first post up to this point, we've learned that the so-called "minimum entropy principle" is really about reducing learning cost — trying to accomplish the same task at the lowest possible cost. So this whole series is essentially a "guide to being lazy." And what's the secret to laziness? The answer is: "conventions" (套路), which is why this series is also called the "compendium of tricks."
In this post, we'll look at the tricks hidden inside libraries.
Let's start with a question: When did word embeddings first appear? Was it in 2013, with Mikolov's Word2Vec? Or in 2003, with Bengio's neural language model? Neither — actually, word embeddings can be traced back a thousand years, to that ancient institution known as the library...
Corner of a library (image via Baidu search)
Walking into the library
Word embeddings, in a library? A thousand years ago? Which book is it in? Let me go check it out.
The convention for shelving books
Actually, it's not in any particular book — it's in the convention used for shelving books.
Clearly, the way books are arranged in a library follows a certain "convention": they aren't placed randomly, but are organized by category — mathematics books go in one section, literature in another, computer science in yet another. Even within a single category there are many subcategories: within mathematics, for example, mathematical analysis has its own sub-section, algebra has its own, geometry has its own, and so on. Have you ever wondered why books are arranged this way? What's the benefit of categorized shelving? And what does it have to do with minimum entropy? more
Some readers might think this is simple: isn't it just to make books easier to find? Actually, that answer isn't quite right. If the only goal were ease of finding a book, there'd be a much simpler solution: just record the coordinates of every book in a database, and mark the corresponding coordinates on the floor of the library. Then, whenever you need to borrow a book, you look up its coordinates in the database and go straight to it. This whole process wouldn't require any notion of "book categorization" at all. So if we're purely thinking about how hard it is to find a book, this doesn't really explain the phenomenon.
Borrowing books with less effort
The real reason lies in this: we usually don't just borrow one book.
As mentioned, once an index is built, finding a single book in the library isn't hard. But what if you want to find two books? In general, a person's interests and research tend to be fairly concentrated, so if I go to the library to borrow two books, it's reasonable to assume those two books are related to each other. For instance, if I borrow Neural Networks, there's a good chance I'll also borrow Deep Learning, but a very small chance I'll also borrow Dream of the Red Chamber. Using the database, I can quickly locate Neural Networks — but what about Deep Learning? If it happens to be nearby, I only need to walk a few more steps to find it. But if books were shelved in random order, I might have to walk from the southeast corner all the way to the northwest corner just to find that second book. And if I need to borrow even more books, wouldn't I end up running laps around the entire library just to collect everything I want?
This is where the value of book categorization becomes obvious. Categorizing books means putting similar books together, and since the books a person wants to borrow on a given trip also tend to be similar to one another, categorization makes the process of searching for and borrowing books more efficient for most people! This, too, is a "trick for saving effort." In other words, sorting the things we need to handle into categories, and placing similar items together, also satisfies the minimum entropy principle. In daily life, we likewise sort frequently-used items and keep them within easy reach, based on exactly the same principle.
Planning the library
Now let's examine this process more carefully, from a mathematical point of view.
A simplified book-borrowing model
Suppose we go to the library to borrow two books, denoted $i,j$. Assume the cost of finding the first book is $d(i)$, and the cost function between the two books is $d(i,j)$ — meaning that after finding the first book $i$, I need to expend an additional amount of effort equal to $d(i,j)$ in order to find the second book $j$. We can consider the average of this process over all people, i.e.
\begin{equation}S = \sum_{i,j} p(i)p(j|i) [d(i)+d(i,j)] = \sum_{i,j} p(i,j) [d(i)+d(i,j)]\end{equation}
where $p(i)$ is the probability that book $i$ is borrowed, and $p(j|i)$ is the probability of also borrowing $j$ given that $i$ has already been borrowed. The library, in arranging its books, wants to minimize $S$.
Now, taking the library entrance as the origin, let's set up a three-dimensional coordinate system for the library. The position of every book can then be represented by a vector $\boldsymbol{v}$. Without loss of generality, we can take $d(i)$ to simply be the Euclidean distance from that book's position to the library's origin, and $d(i,j)$ to be the Euclidean distance between the two books. The expression for $S$ then becomes:
\begin{equation}S = \sum_{i,j} p(i)p(j|i) \left[\Vert \boldsymbol{v}_i\Vert ＋ \Vert \boldsymbol{v}_i - \boldsymbol{v}_j\Vert\right] = \sum_{i,j} p(i,j) \left[\Vert \boldsymbol{v}_i\Vert ＋ \Vert \boldsymbol{v}_i - \boldsymbol{v}_j\Vert\right] \label{eq:chengben}\end{equation}
Let's unpack the meaning of each term. Here $(i,j)$ represents a particular borrowing pattern — namely, borrowing book $i$ together with book $j$ — and $p(i,j)$ represents the probability of this borrowing pattern occurring, which in practice can be estimated from the library's borrowing records; $\Vert \boldsymbol{v}_i\Vert ＋ \Vert \boldsymbol{v}_i - \boldsymbol{v}_j\Vert$ represents the total cost of first borrowing $i$ and then borrowing $j$. The term $\Vert \boldsymbol{v}_i\Vert$ should be kept as small as possible, which means we want to place popular books close to the exit (the origin); while $\Vert \boldsymbol{v}_i - \boldsymbol{v}_j\Vert$ should also be kept small, which tells us to place similar books close together.
Constrained optimization
Suppose we've obtained the library's borrowing records — that is, $p(i,j)$ is known. Can we then obtain the library's "optimal book arrangement" simply by minimizing $\eqref{eq:chengben}$? The idea is right, but it's not complete, because the minimum of expression $\eqref{eq:chengben}$ is obviously 0 — we just need to set all the $\boldsymbol{v}$ to 0, meaning all the books get crammed right at the exit.
Clearly, this isn't actually possible, since books aren't infinitesimally small in reality — there's a minimum spacing $d_{\min} > 0$ between any two books. So the complete formulation should be:
\begin{equation}\begin{aligned}S =& \min_{\boldsymbol{v}}\sum_{i,j} p(i)p(j|i) \left[\Vert \boldsymbol{v}_i\Vert ＋ \Vert \boldsymbol{v}_i - \boldsymbol{v}_j\Vert\right] = \sum_{i,j} p(i,j) \left[\Vert \boldsymbol{v}_i\Vert ＋ \Vert \boldsymbol{v}_i - \boldsymbol{v}_j\Vert\right] \\ &\text{s.t.}\quad\forall i\neq j,\, \Vert \boldsymbol{v}_i - \boldsymbol{v}_j\Vert \geq d_{\min} \end{aligned}\label{eq:chengben-2}\end{equation}
In other words, this is a constrained extremal problem. Solving it gives us the (theoretically) optimal arrangement of books in the library. Of course, if we were actually planning a real library, we'd need to introduce further constraints based on practical considerations, such as the shape of the building, the layout of the aisles, and so on. But $\eqref{eq:chengben-2}$ is already enough for us to grasp the underlying idea.
Minimizing a general cost function
Let's now generalize the problem and look at it from a more abstract angle, which will give us deeper insight.
Homogenization and removing the constraint
Let's replace the cost function $\Vert \boldsymbol{v}_i\Vert ＋ \Vert \boldsymbol{v}_i - \boldsymbol{v}_j\Vert$ with a general $f(\boldsymbol{v}_i,\boldsymbol{v}_j)$, i.e., consider
\begin{equation}S = \sum_{i,j} p(i)p(j|i) f(\boldsymbol{v}_i,\boldsymbol{v}_j) = \sum_{i,j} p(i,j) f(\boldsymbol{v}_i,\boldsymbol{v}_j)\label{eq:yibanchengben}\end{equation}
At the same time, $\boldsymbol{v}$ no longer needs to be restricted to a 3-dimensional vector — it can be a general $n$-dimensional vector. We still want to minimize the overall cost, but we'd rather avoid constraints like $\Vert \boldsymbol{v}_i - \boldsymbol{v}_j\Vert \geq d_{\min}$, since constrained optimization problems tend to be harder to solve. So if we could bake this constraint directly into how we choose $f$, that would be an elegant "constraint-free" solution.
How can we accomplish this? Go back to the library problem: without any constraint, the theoretical optimum is to cram all the books right at the exit. To prevent this unreasonable solution, we introduced the constraint that "there must be a minimum spacing $d_{\min} > 0$ between any two books," which prevents the solution from collapsing. But there are many other constraints we could consider instead — for example, requiring that all books fill the library as evenly as possible. Under this requirement too, we can obtain a reasonable solution.
"As evenly as possible" can actually be understood as a kind of normalization constraint: because of normalization, everything can't pile up at a single point, since a single point wouldn't be normalized. "Normalization" suggests we should think in terms of probability — that is, first construct a probability distribution, and then use it as the measure for the cost function. We won't force too contrived a derivation here; instead, let's directly present one possible choice:
\begin{equation}f(\boldsymbol{v}_i,\boldsymbol{v}_j)=-\log\frac{e^{-\left\Vert\boldsymbol{v}_i-\boldsymbol{v}_j\right\Vert^2}}{Z_i},\quad Z_i = \sum_j e^{-\left\Vert\boldsymbol{v}_i-\boldsymbol{v}_j\right\Vert^2}\label{eq:chengben-l2}\end{equation}
Minimum entropy = maximum likelihood
Let's understand this expression step by step. First, if we ignore the denominator $Z_i$, the result is simply
\begin{equation}-\log \left(e^{-\left\Vert\boldsymbol{v}_i-\boldsymbol{v}_j\right\Vert^2}\right) =\left\Vert\boldsymbol{v}_i-\boldsymbol{v}_j\right\Vert^2\end{equation}
In other words, this $f$ corresponds to a cost function of $\left\Vert\boldsymbol{v}_i-\boldsymbol{v}_j\right\Vert^2$. Then, because of the denominator, we know that
\begin{equation}\sum_j\frac{e^{-\left\Vert\boldsymbol{v}_i-\boldsymbol{v}_j\right\Vert^2}}{Z_i}=1\end{equation}
so $e^{-\left\Vert\boldsymbol{v}_i-\boldsymbol{v}_j\right\Vert^2}/Z_i$ effectively defines a to-be-determined conditional probability distribution $q(j|i)$ — put plainly, this is just a softmax applied to $-\left\Vert\boldsymbol{v}_i-\boldsymbol{v}_j\right\Vert^2$. In that case, $\eqref{eq:yibanchengben}$ actually becomes:
\begin{equation}S = -\sum_{i,j} p(i)p(j|i) \log q(j|i)\label{eq:gailvchengben}\end{equation}
For fixed $i$, minimizing this expression is exactly equivalent to maximizing the log-likelihood! So the outcome is that $q(j|i)$ tends to approach $p(j|i)$, which means that setting everything to 0 is not necessarily optimal — because all-zeros corresponds to a uniform distribution, and the true $p(j|i)$ need not be uniform at all.
Now let's reflect on this: starting from the idea of minimizing cost, we designed a $f(\boldsymbol{v}_i,\boldsymbol{v}_j)$ that has the form of a negative log-probability, and ended up finding that the result is maximum likelihood. This might seem surprising at first, but it actually makes perfect sense — because $-\log q(j|i)$ has the meaning of entropy, and saying we want to maximize likelihood is the same as saying we want to minimize expression $\eqref{eq:gailvchengben}$, which is precisely minimum entropy. Maximum likelihood and minimum entropy essentially express the same idea.
Word2Vec
With just a slight shift in the objects being considered, out pops Word2Vec — and indeed, everything2vec too.
Various choices of measure
Purely as a matter of form, the choice made in expression $\eqref{eq:chengben-l2}$ is intuitive, but it's certainly not the only option. Another viable choice is
\begin{equation}f(\boldsymbol{v}_i,\boldsymbol{v}_j)=-\log\frac{e^{\left\langle\boldsymbol{v}_i,\boldsymbol{v}_j\right\rangle}}{Z_i},\quad Z_i = \sum_j e^{\left\langle\boldsymbol{v}_i,\boldsymbol{v}_j\right\rangle}\label{eq:chengben-dot}\end{equation}
This uses the inner product as the distance measure, with the goal that similar objects should have as large an inner product as possible.
Skip Gram
In fact, if $i,j$ each represent a word within a sentence window, then expression $\eqref{eq:chengben-dot}$ corresponds exactly to the famous word embedding model — the Skip-Gram model of Word2Vec. That is, minimizing
\begin{equation}S = -\sum_{i,j} p(i)p(j|i)\log\frac{e^{\left\langle\boldsymbol{v}_i,\boldsymbol{v}_j\right\rangle}}{Z_i} = -\sum_{i,j} p(i,j) \log\frac{e^{\left\langle\boldsymbol{v}_i,\boldsymbol{v}_j\right\rangle}}{Z_i}\label{eq:word2vec}\end{equation}
is precisely the optimization objective of Word2Vec's Skip-Gram model.
Note: Word2Vec actually distinguishes between context vectors and center-word vectors — i.e., it uses two separate sets of word vectors — but to keep the intuition clear here, we won't dwell on that distinction.
An analogical analysis
Wait a moment — how did word embeddings suddenly pop up here?
Let's retrace our reasoning. Here's the idea: treat each word as a "book," and each sentence as a person's "borrowing record." This lets us know which two "books" are frequently borrowed together, right? Following the whole discussion above about the optimal book-shelving plan for a library, we can work out the optimal positions for these "books" — in theory using either $\eqref{eq:chengben-2},\eqref{eq:chengben-l2}$ or $\eqref{eq:chengben-dot}$ — and that's exactly a word embedding! If we use expression $\eqref{eq:chengben-dot}$, that's Word2Vec.
Conversely, finding an optimal book-shelving plan becomes simple too: treat every person's borrowing record in the library as a "sentence," treat each book as a "word," set the embedding dimension to 3, feed it into Word2Vec for training, and the resulting word vectors give you the optimal shelving plan.
Things like doc2vec, node2vec, and everything2vec basically all work this way.
So now the opening question is crystal clear: recording the three-dimensional coordinates of every book in the library — isn't that a genuine "book embedding"? Books that are close together also have similar vectors, which corresponds perfectly to the characteristic property of word embeddings. So, ever since libraries have existed, embeddings have existed — even though back then there was no coordinate system, and certainly no computers.
Looking again at t-SNE
Once we have "borrowing records" — that is, $p(j|i),p(i)$ — we can directly reuse the process above to obtain an "optimal positional layout," which is exactly the vectorization process.
But what if we don't have such records?
SNE
Then let's construct one! Suppose we already have a batch of high-dimensional samples $\boldsymbol{x}_1,\boldsymbol{x}_2,\dots,\boldsymbol{x}_N$ — they could be a set of image data, for instance — and we want to obtain a low-dimensional representation $\boldsymbol{z}_1,\boldsymbol{z}_2,\dots,\boldsymbol{z}_N$. We construct
\begin{equation}p(\boldsymbol{x}_j|\boldsymbol{x}_i)=\frac{e^{-\Vert \boldsymbol{x}_i-\boldsymbol{x}_j\Vert^2/2\sigma^2}}{\sum\limits_{j}^{j\neq i}e^{-\Vert \boldsymbol{x}_i-\boldsymbol{x}_j\Vert^2/2\sigma^2}}\label{eq:pij}\end{equation}
and then, once again, use expression $\eqref{eq:chengben-l2}$ as the cost function (assuming $p(i)$ is constant, i.e., uniform, and the summation excludes the point itself), we optimize $\eqref{eq:yibanchengben}$, i.e.,
\begin{equation}S=-\sum_{i,j}^{i\neq j}p(\boldsymbol{x}_j|\boldsymbol{x}_i)\log q(j|i),\quad q(j|i)=\frac{e^{-\left\Vert\boldsymbol{z}_i-\boldsymbol{z}_j\right\Vert^2}}{\sum\limits_{j}^{j\neq i}e^{-\left\Vert\boldsymbol{z}_i-\boldsymbol{z}_j\right\Vert^2}}\end{equation}
This gives us the dimensionality-reduction method known as SNE.
Generally speaking there are a number of variants, which we won't dig into in detail — that's not the focus of this post; we just need to grasp the core idea. At its heart, SNE is a dimensionality-reduction scheme that tries to preserve relative distances. Because it preserves relative distances, it retains the basic shape of the data, which is why it tends to work better than methods like PCA. The reason is that PCA and similar methods only retain the principal components, which is suitable only for fairly regular data (e.g., data that clusters around a center and is isotropic), whereas the idea behind SNE can be applied to arbitrarily connected shapes.
t-SNE
As described above, SNE already embodies the idea of dimensionality reduction. But it has some issues, the main one being the so-called "crowding problem." Put simply, the crowding problem arises because the low-dimensional distribution $\eqref{eq:chengben-l2}$ also takes the form of a negative exponential of distance, and the issue with a negative exponential is that it decays to 0 very quickly at large distances. Since $\boldsymbol{v}$ in $\eqref{eq:chengben-l2}$ is exactly the target we're solving for, the optimization ends up crowding almost all the points together near some region (because of the exponential decay, points that are far apart essentially never show up), and the effect isn't good enough.
To solve this problem, we can replace expression $\eqref{eq:chengben-l2}$ with a function that decays less rapidly — for example, a simple fraction:
\begin{equation}f(\boldsymbol{z}_i,\boldsymbol{z}_j)=-\log\frac{(1+\left\Vert\boldsymbol{z}_i-\boldsymbol{z}_j\right\Vert^2)^{-1}}{Z_i},\quad Z_i = \sum_{j}^{j\neq i} (1+\left\Vert\boldsymbol{z}_i-\boldsymbol{z}_j\right\Vert^2)^{-1}\label{eq:t}\end{equation}
This is called the t-distribution. Combining expressions $\eqref{eq:t}$, $\eqref{eq:pij}$, and $\eqref{eq:yibanchengben}$ gives us the dimensionality-reduction method known as t-SNE, which improves on the crowding problem relative to SNE.
Of course, the differences between t-SNE and SNE aren't really the focus of this post — the focus is on revealing how dimensionality-reduction algorithms like SNE share the same underlying logic as Word2Vec.
Although in deep learning we don't often directly use dimensionality-reduction tools like t-SNE nowadays — there are far more elegant approaches to dimensionality reduction and clustering — for instance, for dimensionality reduction you can check out Mutual Information in Deep Learning: Unsupervised Feature Extraction, and for clustering, Variational Autoencoders (IV): A One-Shot Clustering Scheme. Still, the essential idea behind t-SNE shows up in many contexts, so digging it out and connecting it with other pieces of knowledge — weaving it all into your own coherent understanding — is a worthwhile thing to do.
Summary
In this post, starting from the idea of minimizing cost, we built a somewhat idealized model to analyze the principles behind how books are arranged in a library, and from there connected it to the minimum entropy principle, while also reflecting on its relationship to Word2Vec and t-SNE. In doing so, we've constructed yet another vivid example of the minimum entropy principle at work: "birds of a feather flock together," sorting things into categories — both of these reduce cost. For instance, we can now understand why pretrained word embeddings speed up convergence on NLP tasks, and sometimes even improve final performance — because word embeddings place words in appropriate positions in advance, and the very principle behind their construction is to reduce cost.
At the same time, connecting many seemingly unrelated things together can mutually reinforce our understanding of each of them, bringing us as close as possible to a truly unified, coherent grasp of the subject — and the pleasure of that is hard to put into words.
Translated automatically with claude-sonnet-5; all equations are reproduced verbatim from the source. Copyright remains with the original author.