LogSumExp

The LogSumExp (LSE) function is a smooth approximation to the maximum function, mainly used by machine learning algorithms. It's defined as the logarithm of the sum of the exponentials of the arguments:

LSE(x_{1},\dots ,x_{n})=\log \left(\exp(x_{1})+\cdots +\exp(x_{n})\right)

The LogSumExp function domain is $\mathbb {R} ^{n}$ , the real coordinate space, and its range is $\mathbb {R}$ , the real line. The larger the values of $x_{k}$ or their deviation, the better the approximation becomes. The LogSumExp function is convex, and is strictly monotonically increasing everywhere in its domain^[1] (but not strictly convex everywhere ^[2]).

On the otherhand, when directly encountered, LSE can be well-approximated by $\max {\{x_{1},\dots ,x_{n}\}}$ , owing to the following tight bounds.

\max {\{x_{1},\dots ,x_{n}\}}\leq LSE(x_{1},\dots ,x_{n})\leq \max {\{x_{1},\dots ,x_{n}\}}+\log(n)

The lower bound is met when only one of the argument is non-zero, while the upper bound is met when all the arguments are equal.

log-sum-exp trick for log-domain calculations

The LSE function is often encountered when the usual arithmetic computations are performed in log-domain or log-scale.

Like multiplication operation in linear-scale becoming simple addition in log-scale; an addition operation in linear-scale becomes the LSE in the log-domain.

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 a 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). Therefore, many math libraries such as IT++ provide a default routine of LSE and use this formula internally.

LSE(x_{1},\dots ,x_{n})=x^{*}+\log \left(\exp(x_{1}-x^{*})+\cdots +\exp(x_{n}-x^{*})\right)

where $x^{*}=\max {\{x_{1},\dots ,x_{n}\}}$

References

↑ El Ghaoui, Laurent (2015). Optimization Models and Applications.
↑ "convex analysis - About the strictly convexity of log-sum-exp function - Mathematics Stack Exchange". stackexchange.com.

Nielsen, Frank; Sun, Ke (2016). "Guaranteed bounds on the Kullback-Leibler divergence of univariate mixtures using piecewise log-sum-exp inequalities". arXiv:1606.05850.

This article is issued from Wikipedia - version of the 11/18/2016. The text is available under the Creative Commons Attribution/Share Alike but additional terms may apply for the media files.