In the previous article “Attention Scale from the Perspective of Entropy Invariance”, we derived a new Attention Scale from the perspective of entropy invariance. Experiments showed that this new scale, which possesses entropy invariance, indeed allows for better extrapolation performance of Attention. At this point, I had a natural question:
Is there an operation similar to L2 Normalization that can directly transform a probability distribution such that it maintains the primary characteristics of the original distribution while setting its entropy to a specified value?
I searched for similar research with this question in mind but found no relevant studies. Consequently, I attempted to derive it myself and obtained a basically satisfactory result, which I tentatively call “Entropy Normalization.” I am recording it here for the reference of interested readers.
Power Transformation
First, assume an n-dimensional distribution (p_1, p_2, \dots, p_n). Its entropy is defined as: \mathcal{H} = -\sum_i p_i \log p_i = \mathbb{E}[-\log p_i] Since p_i \in [0,1], it follows that -p_i \log p_i \geq 0, and thus \mathcal{H} \geq 0. When one p_i is 1 and the others are 0 (one-hot), it reaches the minimum value of 0. Furthermore, it can be proven that when all p_i are equal to 1/n, \mathcal{H} reaches its maximum value of \log n. Therefore, the range of \mathcal{H} is [0, \log n].
Thus, we first need to find a transformation for the distribution that preserves its main information and has the capability to vary the entropy of the distribution from 0 to \log n. Here, we choose the power transformation: p_i \quad \to \quad \tilde{p}_i = \frac{p_i^{\gamma}}{\sum\limits_i p_i^{\gamma}} One reason for choosing the power transformation is that it preserves the monotonicity of the distribution; that is, if p_i > p_j, then \tilde{p}_i > \tilde{p}_j. I believe this is one of the important properties a distribution needs to maintain. Furthermore, when all p_i are non-zero and distinct, the power transformation indeed has the ability to vary the entropy between 0 and \log n. Without loss of generality, assume 1 > p_1 > p_2 > \dots > p_n > 0. Clearly, when \gamma = 0, \tilde{p}_i = 1/n, and the entropy is at its maximum value \log n. When \gamma \to \infty, we have: \tilde{p}_1 = \lim_{\gamma\to\infty}\frac{p_1^{\gamma}}{\sum\limits_i p_i^{\gamma}} = \lim_{\gamma\to\infty}\frac{1}{1 + \sum\limits_{i > 1} (p_i/p_1)^{\gamma}} = 1 This results in a one-hot distribution (1, 0, \dots, 0), corresponding to the minimum entropy of 0. In fact, it can be further proven by differentiation that the entropy is monotonically decreasing with respect to \gamma. Therefore, as \gamma increases from 0 to \infty, the entropy decreases from \log n to 0.
Iterative Solution
Once we have confirmed that the power transformation is a viable transformation, we need to enter the solution process. That is, for any given \mathcal{H}^* \in (0, \log n), we need to find the correct \gamma such that the corresponding entropy equals the specified value \mathcal{H}^*.
First, we write: \mathcal{H}_{\gamma} = -\sum_i \frac{p_i^{\gamma}}{\sum\limits_i p_i^{\gamma}} \log \frac{p_i^{\gamma}}{\sum\limits_i p_i^{\gamma}} = \log \sum_i p_i^{\gamma} - \frac{\gamma \sum\limits_i p_i^{\gamma} \log p_i}{\sum\limits_i p_i^{\gamma}} The complexity of the expression on the far right leads us to believe that an analytical solution likely does not exist, so we must seek an iterative solution algorithm.
We take the expansion at \gamma=1 (primarily utilizing p_i^{\gamma} \approx p_i + (\gamma-1)p_i \log p_i): \begin{aligned} \mathcal{H}_{\gamma} \approx &\, -\sum_i p_i \log p_i + \left(\left(\sum_i p_i \log p_i\right)^2 - \sum_i p_i (\log p_i)^2\right)(\gamma - 1) \\ =&\, \mathcal{H}_1 + \left(\mathcal{H}_1^2 - \mathbb{E}[(\log p_i)^2]\right)(\gamma - 1) \end{aligned} Then: \gamma \approx 1 + \frac{\mathcal{H}_{\gamma} - \mathcal{H}_1}{\mathcal{H}_1^2 - \mathbb{E}[(\log p_i)^2]} Based on this result, starting from \gamma=1 and repeatedly using the above formula for iteration, we can solve for the final distribution: \mathcal{H} \leftarrow -\sum_i p_i \log p_i, \quad \gamma \leftarrow 1 + \frac{\mathcal{H}^* - \mathcal{H}}{\mathcal{H}^2 - \mathbb{E}[(\log p_i)^2]}, \quad p_i \leftarrow \frac{p_i^{\gamma}}{\sum\limits_i p_i^{\gamma}} This is essentially Newton’s method for solving a non-linear equation. In experiments, it was found that 3 to 4 iterations yield good convergence. If the actual use case is only to roughly control the range of entropy, then 1 to 2 iterations are sufficient.
Reference code in Numpy:
import numpy as np
p = np.random.random(100)
p /= p.sum() # Simulate a distribution
gamma = 1
H_f = np.log(30) # Target entropy
for i in range(10):
H = -(p * np.log(p)).sum()
# Newton's method update
gamma = 1 + (H_f - H) / (H**2 - (p * np.log(p)**2).sum())
p = p**gamma
p /= p.sum()Potential Applications
This article primarily introduces the concept of “Entropy Normalization” because I found it interesting and wanted to derive it. However, as for specific good application examples, I haven’t fully thought them through yet.
Lower entropy means the probability is more concentrated in a few positions; in other words, the probabilities at other positions are closer to zero. Therefore, to some extent, entropy is a measure of the sparsity of a probability distribution. If we hope to obtain sparser prediction results, we can control this through entropy normalization. On the other hand, a sparser distribution also means the model is more likely to suffer from vanishing gradients. Thus, conversely, entropy normalization can be used to ensure the entropy does not become too small, thereby mitigating the vanishing gradient problem.
Speaking of sparsity, one cannot help but think of works like Sparsemax and my own conceptualized Sparse Softmax. In Sparsemax, sparsity is obtained by treating entropy as a penalty term, while Sparse Softmax introduces sparsity through direct truncation. Both have better interpretability or better effects in certain scenarios. So, does the sparsity brought directly by entropy normalization have any effect? This might also be a question worth exploring.
Additionally, in the random sampling of autoregressive models, we often use top-k or top-p truncation. This truncation is essentially reducing the entropy of the distribution. Accordingly, we could use entropy normalization to make the distribution entropy of each sampling step consistent, replacing top-k or top-p sampling. This is another possible application.
The main problem with using entropy normalization is that there is no clear standard for “which value to normalize to.” I currently do not have a good idea for this and can only think of tuning parameters by observing existing experimental results, which is ultimately not an ideal answer.
Conclusion
This article introduced the concept of Entropy Normalization, which allows the entropy of a distribution to be set to a specified value through a direct transformation, and brainstormed some potential applications.
Original address: https://kexue.fm/archives/8829
For more details regarding reposting, please refer to: "Scientific Space FAQ"