Abstract
The Log-Sum-Exp (LSE) and Softmax functions are foundational to modern machine learning, yet their numerical stability is often taken for granted. This paper provides a rigorous rounding error analysis of these functions, focusing on the widely used "shifting trick." We demonstrate that while the shifted algorithm is forward stable even in low-precision arithmetic, alternative "division-free" implementations can lead to significant inaccuracies. Our analysis is supported by experiments on real-world data from neural network training.
1. Introduction
In machine learning, the Log-Sum-Exp (LSE) function, $LSE(x) = \log \sum_{i=1}^{n} e^{x_i}$, and its gradient, the Softmax function, $\sigma(x)_j = e^{x_j} / \sum_{i=1}^{n} e^{x_i}$, are ubiquitous. They appear in cross-entropy loss functions, attention mechanisms, and reinforcement learning. A primary challenge in their implementation is the use of the exponential function, which can easily exceed the range of standard floating-point formats, leading to overflow or underflow.
2. Floating-Point Arithmetic and Precision
The behavior of LSE and Softmax is intrinsically linked to the precision and range of the underlying hardware arithmetic. Modern deep learning increasingly relies on 16-bit formats like fp16 and bfloat16.
As shown in Table 1, fp16 offers higher precision (smaller unit roundoff $u$) but a very restricted range ($r_{\max} \approx 6.55 \times 10^4$). Conversely, bfloat16 provides a much larger range, comparable to fp32, at the cost of lower precision. These constraints necessitate robust algorithms to ensure numerical reliability.
Table 2 illustrates the logarithmic limits of these formats. For instance, in fp16, any input $x_i > \log(r_{\max}) \approx 11.0$ will cause $e^{x_i}$ to overflow to infinity.
3. Algorithmic Stability
We evaluate three primary approaches to computing these functions:
- Naive Algorithm: Direct implementation of the mathematical formulas.
- Shifted Algorithm: Subtracting $a = \max(x_i)$ from all inputs before exponentiation. This ensures the largest term is $e^0 = 1$, effectively preventing overflow.
- Division-Free Softmax: Computing $\sigma(x)_j = \exp(x_j - LSE(x))$.
Our rounding error analysis proves that the shifted algorithm is forward stable. A common concern in numerical analysis is subtractive cancellation; however, we show that in the shifted LSE, the terms being summed are bounded, mitigating this risk. In contrast, the "division-free" variant is shown to be less accurate, as errors in the $LSE(x)$ term are magnified by the final exponential.
4. Experimental Results
To validate our theoretical findings, we extracted 2,500 activation vectors from a convolutional neural network trained on the MNIST dataset. These vectors represent the typical inputs to a Softmax layer in a production environment.
In fp16 tests, the naive LSE failed for 19% of the test vectors due to overflow. The shifted version successfully processed all vectors. Furthermore, numerical experiments confirmed that the standard shifted Softmax is significantly more accurate than the division-free variant, often by several orders of magnitude. The shifted algorithm also superiorly maintains the "sum-to-one" property required for probability distributions.
5. Conclusion
This study provides the formal justification for the "shifting trick" in LSE and Softmax computations. We conclude that the shifted algorithm is the most reliable method for deep learning applications, particularly when utilizing low-precision formats like fp16. We recommend against the use of division-free Softmax implementations due to their inherent numerical instability.
Summary updated