LogSumExp

Template:Short description Template:Refimprove The LogSumExp (LSE) (also called RealSoftMax or multivariable softplus) function is a smooth maximum – a smooth approximation to the maximum function, mainly used by machine learning algorithms. It is defined as the logarithm of the sum of the exponentials of the arguments:

$$\mathrm{L}\mathrm{S}\mathrm{E}(x_1,\dots ,x_n)=\log (\exp (x_1)+\cdots +\exp (x_n)).$$

Properties

The LogSumExp function domain is ${ℝ}^n$, the real coordinate space, and its codomain is $ℝ$, the real line. It is an approximation to the maximum $\underset{i}{\max }{x}_i$ with the following bounds $$\max \{x_1,\dots ,x_n\}\le \mathrm{L}\mathrm{S}\mathrm{E}(x_1,\dots ,x_n)\le \max \{x_1,\dots ,x_n\}+\log (n).$$ The first inequality is strict unless $n=1$. The second inequality is strict unless all arguments are equal. (Proof: Let $m=\underset{i}{\max }{x}_i$. Then $\exp (m)\le \sum _{i=1}^n\exp (x_i)\le n\exp (m)$. Applying the logarithm to the inequality gives the result.)

In addition, we can scale the function to make the bounds tighter. Consider the function $\frac{1}{t}\mathrm{L}\mathrm{S}\mathrm{E}(t{x}_1,\dots ,t{x}_n)$. Then $$\max \{x_1,\dots ,x_n\}<\frac{1}{t}\mathrm{L}\mathrm{S}\mathrm{E}(t{x}_1,\dots ,t{x}_n)\le \max \{x_1,\dots ,x_n\}+\frac{\log (n)}{t}.$$ (Proof: Replace each $x_i$ with $t{x}_i$ for some $t>0$ in the inequalities above, to give $$\max \{t{x}_1,\dots ,t{x}_n\}<\mathrm{L}\mathrm{S}\mathrm{E}(t{x}_1,\dots ,t{x}_n)\le \max \{t{x}_1,\dots ,t{x}_n\}+\log (n).$$ and, since $t>0$ $$t\max \{x_1,\dots ,x_n\}<\mathrm{L}\mathrm{S}\mathrm{E}(t{x}_1,\dots ,t{x}_n)\le t\max \{x_1,\dots ,x_n\}+\log (n).$$ finally, dividing by $t$ gives the result.)

Also, if we multiply by a negative number instead, we of course find a comparison to the $\min$ function: $$\min \{x_1,\dots ,x_n\}-\frac{\log (n)}{t}\le \frac{1}{-t}\mathrm{L}\mathrm{S}\mathrm{E}(-tx)<\min \{x_1,\dots ,x_n\}.$$

The LogSumExp function is convex, and is strictly increasing everywhere in its domain. It is not strictly convex, since it is affine (linear plus a constant) on the diagonal and parallel lines:

$\mathrm{L}\mathrm{S}\mathrm{E}(x_1+c,\dots ,x_n+c)=\mathrm{L}\mathrm{S}\mathrm{E}(x_1,\dots ,x_n)+c.$

Other than this direction, it is strictly convex (the Hessian has rank Template:Tmath), so for example restricting to a hyperplane that is transverse to the diagonal results in a strictly convex function. See ${\mathrm{L}\mathrm{S}\mathrm{E}}_0^{+}$, below.

Writing $𝐱=(x_1,\dots ,x_n),$ the partial derivatives are: $$\frac{\partial }{\partial x_i}\mathrm{L}\mathrm{S}\mathrm{E}(𝐱)=\frac{\exp x_i}{\sum _j\exp x_j},$$ which means the gradient of LogSumExp is the softmax function.

The convex conjugate of LogSumExp is the negative entropy.

log-sum-exp trick for log-domain calculations

The LSE function is often encountered when the usual arithmetic computations are performed on a logarithmic scale, as in log probability.

Similar to multiplication operations in linear-scale becoming simple additions in log-scale, an addition operation in linear-scale becomes the LSE in log-scale:

$$\mathrm{L}\mathrm{S}\mathrm{E}(\log (x_1),...,\log (x_n))=\log (x_1+\dots +x_n)$$ A common purpose of using log-domain computations is to increase accuracy and avoid underflow and overflow problems when very small or very large numbers are represented directly (i.e. in a linear domain) using limited-precision floating point numbers.

Unfortunately, the use of LSE directly in this case can again cause overflow/underflow problems. Therefore, the following equivalent must be used instead (especially when the accuracy of the above 'max' approximation is not sufficient).

$$\mathrm{L}\mathrm{S}\mathrm{E}(x_1,\dots ,x_n)=x^{*}+\log (\exp (x_1-x^{*})+\cdots +\exp (x_n-x^{*}))$$ where $x^{*}=\max \{x_1,\dots ,x_n\}$

Many math libraries such as IT++ provide a default routine of LSE and use this formula internally.

A strictly convex log-sum-exp type function

LSE is convex but not strictly convex. We can define a strictly convex log-sum-exp type function by adding an extra argument set to zero:

$${\mathrm{L}\mathrm{S}\mathrm{E}}_0^{+}(x_1,...,x_n)=\mathrm{L}\mathrm{S}\mathrm{E}(0,x_1,...,x_n)$$ This function is a proper Bregman generator (strictly convex and differentiable). It is encountered in machine learning, for example, as the cumulant of the multinomial/binomial family.

In tropical analysis, this is the sum in the log semiring.

See also

• Logarithmic mean
• Log semiring
• Smooth maximum
• Softmax function