Softmax Regression Large Inner Product Float Overflow

Question

In softmax regression, the probability $P$ that an item is part of class $l$ is given by $$P(y^{(i)}=l | x^{(i)};\theta)=\frac{e^{\theta^Tx^{(i)}}}{\sum_{j=1}^k e^{\theta^Tx^{(j)}}}$$

I have implemented softmax regression, but seem to come into problems when the inner product $\theta^Tx^{(i)}$ is large (say, greater than 30-50,) in which case even a 64 bit float overflows. What's the recommended procedure to avoid this problem? I've been thinking about normalizing the input vector $x^{(i)}$ such that $x^{(i)\prime}=\frac{x^{(i)}}{|x^{(i)}|}$, but that could make prediction less dynamic.

Answer 1

You can subtract a constant from the $\theta^T x^{(i)}$ before taking the exponent. I believe that the max, per example, is commonly used.

Answer 2

Use logarithms! For example, instead of calculating $a/b$, try $exp(log(a) - log(b))$

Answer 3

The typical way to prevent overflows from occurring when computing the probabilities for softmax regression is as follows:

• Step 1: consider the logarithm of the probabilities. I.e., $$\log \left(P(y^{(i)}=k | x^{(i)};\theta)\right)=\frac{\log \left(e^{\theta_k^Tx^{(i)}}\right)}{\log \left(\sum_{c=1}^K e^{\theta_c^Tx^{(i)}}\right)}$$

• Step 2: if you're interested in predicting the class, you only need to compute the numerator, so you're set. If you're interested in predicting the probabilities, you also need to compute the denominator, in which case you need to use the log-sum-exp trick.

Example of how the log-sum-exp trick works in Naive Bayes explains those two steps in more details. Just replace underflows with overflows, and pretend $p(\mathbf{x}|Y=C_k)p(Y=C_k) = e^{\theta_c^Tx^{(i)}}$.