Softmax-ing is actually (Random) Utility Maximization

This post is long overdue but it is better late than never. Softmaxing is prevalent in many fields of science but this one is going to be about utility maximization. I will be showing how softmaxing logits can be seen as maximizing utility when faced with multiple choices. ( This property is also going to be the base to show the mathematical principle that the Gumbel-Max Trick relies on, which I demonstrate in another post)

The Utility Function

Consider a utility maximizing decision-maker who has to choose from among $K$ alternatives. Suppose for each alternative $i$, the total utility $U_i$ consists of two parts:

• Deterministic component(aka logits) $V_i$: This is the observable part of the utility. We can assume a functional form about how $V_i$ is constructed but since it is more general, I will leave it like this.
• Random component $\epsilon_i$: This captures unobservable factors influencing the utility and is modeled as a random variable.

Thus, the total utility for each alternative $i$ is given by:

The decision-maker selects the alternative with the highest utility. Therefore, the utility maximization problem, that he/she/they are facing is:

Now this will get a bit crowded with equations before it is not, so bare with me. We know that the optimal selection will be random as all of the choices have random parts. Also, for the $i^{th}$ option to be the optimal we need it to give more utility than the rest of the tokens, ohmm, I am sorry, options. Thus the probability of $i^{th}$ option to be the optimal one can be expressed as:

If we just plug the expression for total utility $U_i = V_i + \epsilon_i$, we get:

Next, we are going to tie this beuty to the softmax. Writing the expression more cleanly:

From here there are two paths that can take us to the desired point. One easy and one not-so-easy way. The easy way uses the random knowledge of “The difference of Gumbel random variables follows a logistic distribution”. But lets not take that route.

Not-So-Easy Way

Let’s go from the not-so-easy way and not ask ourselves why.

Given that $\epsilon_j$ are independent and identically distributed $(i.i.d.)$, we can integrate over the distribution of $\epsilon_i$ to account for all possible values:

where $F(\cdot)$ is the cumulative distribution function (CDF) of $\epsilon_j$ and $f(\cdot)$ is the probability density function (PDF) of $\epsilon_i$.

Assume that $\epsilon_i$ are i.i.d. and follow a Gumbel (Type I Extreme Value) distribution:

Substitute $F(\cdot)$ and $f(\cdot)$ into the expression:

If we plug the expression for the CDF in to product inside the square bracket, the product over $j \neq i$ becomes:

Now, plug the $[$product$]$ and the PDF to the main equation becomes this messy looking expression but things will simplify:

Just seperating the terms in the PDF,

In terms of being super clear write the double exponential slightly clearer way,

Put it inside the same exponent,

and to make a favor to our eyes, let:

Now, the choice probability is:

We are almost there but we first need to make a substitution:

When $\epsilon_i$ goes from $-\infty$ to $\infty$, $t$ goes from $\infty$ to $0$.

Substitute $t$ and $d\epsilon_i$ into the integral:

Now this is good news because $e^{-\left( -\ln t \right)} = t$ and $t \left( -\frac{dt}{t} \right) = -dt$ and we can also get rid of the negative by switching the boundaries of the integral,

This is not a hard integral to solve,

Plugging the $S$ back,

Finally, let’s write $e^{V_j - V_i}$ as $\frac{e^{V_j}}{e^{V_i}}$:

Therefore:

Thus, the choice probability for alternative ( i ) is:

We will continue messing with the softmax in other posts.

References

• McFadden, D. (1974). “Conditional logit analysis of qualitative choice behavior.”
• Train, K. (2009). Discrete Choice Methods with Simulation.