The Principle of Minimum Entropy (VI): How to Choose the Dimension of Word Vectors?

Minimizing Entropy

Our starting point is information entropy. We know that entropy is a measure of uncertainty (refer to “’Entropy’ is not affordable: From Entropy and the Principle of Maximum Entropy to the Maximum Entropy Model (I)”). Language itself possesses a certain degree of uncertainty. When we encode words using vectors, the encoding result should be equal to or even smaller than this uncertainty to ensure that the encoding is effective and fully preserves the information of the original language. Therefore, we want to eliminate uncertainty, which means minimizing entropy.

It should be noted that word vectors are based on the Skip-Gram model, so what we need to calculate is not the average word entropy, but the average entropy of the entire Skip-Gram model. Assuming the frequency of the word pair (w_i, w_j) is \tilde{p}(w_i, w_j), we can estimate its entropy as: \tilde{H}=-\sum_{i, j} \tilde{p}(w_i, w_j)\log \tilde{p}(w_i, w_j) Different word vector training objectives vary slightly; some fit the joint probability p(w_i, w_j), while others fit the conditional probability p(w_j|w_i). However, this difference is minor. As mentioned earlier, this article only aims to obtain an approximate figure. Therefore, we uniformly assume the word vector model is: p(w_i, w_j) = \frac{e^{\langle\boldsymbol{u}_i, \boldsymbol{v}_j\rangle}}{Z},\quad Z = \sum_{i,j}e^{\langle\boldsymbol{u}_i, \boldsymbol{v}_j\rangle} where \boldsymbol{u}, \boldsymbol{v} represent two different sets of word vectors (center word vectors and context word vectors), \boldsymbol{u}_i represents word w_i, and \boldsymbol{v}_j represents word w_j. At this point, its information entropy is: H=-\sum_{i, j} p(w_i, w_j)\log p(w_i, w_j)=\log Z-\frac{1}{Z}\sum_{i, j} e^{\langle \boldsymbol{u}_i, \boldsymbol{v}_j\rangle} \langle \boldsymbol{u}_i, \boldsymbol{v}_j\rangle

Sampling Approximation

To approximate the calculation of the above formula, we use sampling to approximate the summation, for example: Z = \sum_{i, j} e^{\langle \boldsymbol{u}_i, \boldsymbol{v}_j\rangle} = N^2\times \frac{1}{N^2}\sum_{i, j} e^{\langle \boldsymbol{u}_i, \boldsymbol{v}_j\rangle}\approx N^2\mathbb{E}_{\boldsymbol{u}_i,\boldsymbol{v}_j}\left[e^{\langle \boldsymbol{u}_i, \boldsymbol{v}_j\rangle}\right] where N is the vocabulary size. Similarly: \sum_{i, j} e^{\langle \boldsymbol{u}_i, \boldsymbol{v}_j\rangle} \langle \boldsymbol{u}_i, \boldsymbol{v}_j\rangle\approx N^2\mathbb{E}_{\boldsymbol{u}_i,\boldsymbol{v}_j}\left[e^{\langle \boldsymbol{u}_i, \boldsymbol{v}_j\rangle} \langle \boldsymbol{u}_i, \boldsymbol{v}_j\rangle\right] So we have the approximation: H\approx\log N^2 + \log \mathbb{E}_{\boldsymbol{u}_i,\boldsymbol{v}_j}\left[e^{\langle \boldsymbol{u}_i, \boldsymbol{v}_j\rangle}\right]-\frac{\mathbb{E}_{\boldsymbol{u}_i,\boldsymbol{v}_j}\left[e^{\langle \boldsymbol{u}_i, \boldsymbol{v}_j\rangle} \langle \boldsymbol{u}_i, \boldsymbol{v}_j\rangle\right]}{\mathbb{E}_{\boldsymbol{u}_i,\boldsymbol{v}_j}\left[e^{\langle \boldsymbol{u}_i, \boldsymbol{v}_j\rangle}\right]}

Distribution Assumption

Observing existing word vector models, we find that the values in each dimension can be positive or negative, and their absolute values are generally uniform. Here, we might as well assume that the absolute value of each element is roughly 1, so the norm of each word vector is approximately \sqrt{n} (where n is the dimension of the word vector, our target for estimation; if this approximation seems inaccurate, it can be adjusted). Furthermore, we assume all word vectors are uniformly distributed on an n-dimensional hypersphere with radius \sqrt{n}. Then \langle \boldsymbol{u}_i, \boldsymbol{v}_j\rangle=n\cos\theta, where \theta is the angle between them. Thus: H\approx\log N^2 + \log \mathbb{E}_{\theta}\left[e^{n\cos\theta}\right]-\frac{\mathbb{E}_{\theta}\left[e^{n\cos\theta} n\cos\theta\right]}{\mathbb{E}_{\theta}\left[e^{n\cos\theta}\right]}\label{eq:H-theta} Now \theta corresponds to the angle between any two vectors in n-dimensional space. In “Distribution of the Angle Between Two Random Vectors in n-dimensional Space”, we derived its distribution as: p_n(\theta) = \frac{\Gamma\left(\frac{n}{2}\right)}{\Gamma\left(\frac{n-1}{2}\right)\sqrt{\pi}}\sin^{n-2} \theta \label{eq:jqfb} Since the probability density function is determined, for given N and n, the approximation formula [eq:H-theta] can be calculated numerically. From \tilde{H} > H, we can solve for the corresponding n.

Results Comparison

First, we numerically calculate some results for h_n=\log \mathbb{E}_{\theta}\left[e^{n\cos\theta}\right]-\frac{\mathbb{E}_{\theta}\left[e^{n\cos\theta} n\cos\theta\right]}{\mathbb{E}_{\theta}\left[e^{n\cos\theta}\right]}:

For example, if n=64 and N=100,000, then H\approx \log 100,000^2 - 15.4734 = 7.55245. Readers might find it strange: when n=128 and N=100,000, wouldn’t H be negative? How can discrete entropy be negative? In fact, this is because in the derivation process, we combined sampling approximation with exact integration. When the spatial dimension n is large enough, even sampling hundreds of thousands of points might not accurately estimate certain statistics. Thus, the sampling approximation step introduces error.

However, this gives us another way to determine n: When H < 0 occurs, it indicates that N samples are no longer sufficient to provide a good estimate of the statistics. Conversely, this means that the n-dimensional space is “more than enough” to accommodate N samples. Therefore, we can use H < 0 to simply determine a boundary without needing to estimate \tilde{H}. (Alternatively, think of it this way: \tilde{H} must be greater than 0, so H < 0 is a sufficient condition for H < \tilde{H}.)

Finally, we observe that h_n is roughly linear with respect to n, with h_n/n\approx -0.24. Thus, H\approx\log N^2 -0.24n. Setting this to be less than 0 allows us to solve for formula [eq:final].

Approximate Estimation

For the result h_n/n\approx -0.24, we can also derive it theoretically. According to the definition of h_n, we have: h_n = \log\frac{\int_0^{\pi} \sin^{n-2}\theta\, e^{n\cos\theta}d\theta}{\int_0^{\pi} \sin^{n-2}\theta d\theta} - n\frac{\int_0^{\pi} \sin^{n-2}\theta\, e^{n\cos\theta}\cos\theta d\theta}{\int_0^{\pi} \sin^{n-2}\theta\,e^{n\cos\theta} d\theta} This is a problem of asymptotic estimation for several definite integrals. We primarily use the idea of Laplace approximation. Assuming n is relatively large, such that we can ignore the difference between n and n-2: \log\left[\sin^{n-2}\theta\, e^{n\cos\theta}\right]=(n-2)\log \sin\theta + n\cos\theta \approx n (\log \sin\theta + \cos\theta) We can calculate that the maximum point of \log\sin\theta + \cos\theta in [0,\pi] is \arctan\sqrt{\frac{\sqrt{5}+1}{2}}\approx 0.904557. Expanding to the second order at that point, we get: \log \sin\theta + \cos\theta\approx 0.377428 -1.11803 (\theta - 0.904557)^2 Thus: \begin{aligned} \int_0^{\pi} \sin^{n-2}\theta\, e^{n\cos\theta}d\theta\approx&\, \int_{-\infty}^{\infty} e^{n[0.377428 -1.11803 (\theta - 0.904557)^2]}d\theta\\ \approx&\, \frac{1.67629}{\sqrt{n}}e^{0.377428n} \end{aligned} Note that when n is large enough, the integrand is significantly non-zero only near \theta=0.904557 (or treating the limit of the normal distribution as an approximation of the Dirac delta function): \begin{aligned} \frac{\int_0^{\pi} \sin^{n-2}\theta\, e^{n\cos\theta}\cos\theta d\theta}{\int_0^{\pi} \sin^{n-2}\theta\, e^{n\cos\theta} d\theta}\approx&\, \frac{\int_{-\infty}^{\infty} e^{n[0.377428 -1.11803 (\theta - 0.904557)^2]}\cos\theta d\theta}{\int_{-\infty}^{\infty} e^{n[0.377428 -1.11803 (\theta - 0.904557)^2]}d\theta} \\ \approx&\, \int_{-\infty}^{\infty} \delta(\theta - 0.904557) \cos\theta d\theta\\ =&\, \cos 0.904557 \approx 0.618034 \end{aligned} Similarly, using Laplace approximation, we can obtain \int_0^{\pi} \sin^{n-2}\theta d\theta\approx\frac{2.50663}{\sqrt{n}}. Combining all results, we get: h_n \approx \log \frac{\frac{1.67629}{\sqrt{n}}e^{0.377428n}}{\frac{2.50663}{\sqrt{n}}}-0.618034n\approx -0.240606 n This yields the result h_n/n\approx -0.24. The above derivation uses numerical values; if we kept the analytical values, the analytical solution for this coefficient would be \frac{1}{2}\log\frac{\sqrt{5}+1}{2}.