The even-order Taylor expansion of exp(x) at x=0 is always positive

exp(x)在x=0处的偶次泰勒展开式总是正的 苏剑林 · 2020-11-24 · Mathematics derivative probability analysis

I just came across an interesting result:

For any real number $x$ and even number $n$, we always have $\sum\limits_{k=0}^n \frac{x^k}{k!} > 0$, i.e. the even-order Taylor expansion of $e^x$ at $x=0$ is always positive.

Let's take a look at the proof of this result, as well as its application in finding alternatives to softmax.

Proof

This looks like a strong result — surely the proof must be complicated? Actually, the proof is remarkably simple. Let

\begin{equation}f_n(x) = \sum\limits_{k=0}^n \frac{x^k}{k!}\end{equation}

When $n$ is even, we have $\lim\limits_{x\to\pm\infty} f_n(x)=+\infty$, meaning the whole function opens upward, so we only need to show that its minimum value is greater than 0. Moreover, since it's a smooth, continuous polynomial function, the minimum point must be one of its local minima. Turning this around, we only need to show that the function value at every extremum (whether local max or local min) is greater than 0. more

The natural way to find extrema is to take derivatives, and one beautiful feature of $f_n(x)$ is that its derivative satisfies

\begin{equation}f_n'(x) = f_{n-1}(x)\end{equation}

At an extremum we have $f_n'(x)=0$, i.e. $f_{n-1}(x)=0$ holds, and at such a point

\begin{equation}f_n(x) = f_{n-1}(x) + \frac{x^n}{n!} = \frac{x^n}{n!} \geq 0 \,\,\,(n\text{if even})\end{equation}

This proves that the function value at every extremum of $f_n(x)$ is non-negative, so $f_n(x)\geq 0$ holds everywhere. Furthermore, one can check that $x=0$ is not itself an extremum, so $\geq$ can be strengthened to $ > $. This completes the proof.

Application

Actually, I came across this result in a recent Arxiv paper, Exploring Alternatives to Softmax Function. The original paper gives a somewhat complicated proof based on mathematical induction, whereas the proof above is one I worked out myself, which is relatively simpler and more transparent.

So why does the original paper need this result? As the name suggests, it's in the pursuit of alternatives to softmax. As we know, a common way in machine learning to turn outputs into a probability distribution is to apply softmax:

\begin{equation}softmax(\boldsymbol{x})_i = \frac{e^{x_i}}{\sum\limits_{k=1}^n e^{x_k}}\end{equation}

Since $n$ is even and $f_n(x) > 0$ holds, and since $f_n(x)$ is, within a certain range, an approximation of $e^x$, replacing $e^x$ with $f_n(x)$ can also serve as a reasonable normalization function:

\begin{equation}taylor\text{-}softmax(\boldsymbol{x}, n)_i = \frac{f_n(x_i)}{\sum\limits_{k=1}^n f_n(x_k)}\end{equation}

The original paper ran a few experiments showing that $taylor\text{-}softmax$ offers some improvement over standard softmax:

Comparison between softmax and its Taylor-expansion approximation

A brief comment

That said, in my view this experimental result is not very convincing, since the baselines used are far too weak (it's 2020 already — at least run a ResNet, please). Furthermore, the original paper offers no intuitive understanding of why this alternative might work; it simply runs a few basic experiments and claims it "works," which feels rather crude.

Nevertheless, despite the paper's many shortcomings, I do think its proposed $taylor\text{-}softmax$ could genuinely be effective. Going from softmax to $taylor\text{-}softmax$ essentially replaces the exponential activation function with a polynomial one. What's the difference between the two? We know that when $|x|$ is relatively large, $e^x$ grows/decays very rapidly, which is directly responsible for softmax's well-known tendency toward overconfidence (probability values collapsing to 0 or 1). Polynomial functions, by contrast, don't grow nearly as aggressively, so they're less prone to overconfidence and hence less prone to overfitting.

A similar kind of change appears in the classic dimensionality-reduction method t-SNE. The predecessor of t-SNE, SNE, constructed a softmax-like exponential probability distribution, which was later found to suffer from the "crowding problem" (see Minimum Entropy Principle (IV): "Birds of a Feather" — From Libraries to Word Embeddings). Eventually, t-SNE replaced the exponential with a quadratic function and things improved a lot — I feel $taylor\text{-}softmax$ shares a similar spirit with the idea behind t-SNE.

Preserving monotonicity

In fact, one can also show that $f_n(x)$ has exactly one global minimum, so its graph is always U-shaped, as shown below:

Graph of f_n(x)

Some readers with a bit of a perfectionist streak might be bothered by the non-monotonicity of $f_n(x)$, worrying that $f_n(x)$ not being a monotonic function could hide some subtle problem. Actually, there's currently no clear evidence that the transformation used to produce a probability distribution must be monotonic. That said, if you're still concerned, you can simply truncate it. As noted above, $f_n(x)$ has only one minimum point $x_n^*$; the part beyond the minimum is monotonically increasing, and for the part before the minimum, we can just clamp it to the minimum value. That is, define

\begin{equation}\tilde{f}_{n}(x)=\left\{\begin{aligned}&f_n(x),\quad x > x_n^*\\ &f_n(x_n^*),\quad x\leq x_n^*\end{aligned}\right.\end{equation}

and then use $\tilde{f}_{n}(x)$ in place of $f_{n}(x)$ to perform the normalization. For a fixed $n$, both $x_n^*$ and $f_n(x_n^*)$ can be precomputed numerically:

$$\begin{array}{c|cc} \hline n & x_n^* & f(x_n^*) \\ \hline 2 & -1 & 0.5 \\ 4 & -1.59607 & 0.270395 \\ 6 & -2.18061 & 0.149325 \\ 8 & -2.759 & 0.0832715 \\ 10 & -3.33355 & 0.0466991 \\ \hline \end{array}$$

Summary

The main purpose of this post was to introduce the rather interesting result that "the even-order Taylor expansion of $e^x$ is always positive," and along the way, to describe its application in searching for alternatives to softmax.