Distinguishing logistic curves

[Stuart_Armstrong]

This post will attempt to formalise the intuition that “it’s hard to figure out the turning point of a logistic curve, at least until after that turning point”. Ashort visual “proof” can also be found here.

Logistic curves

The logistic curves look like this:

Logistic curves can be specified by three parameters, $c$, $l>0$, and $k>0$. Their equation is then:

$$F_{c,l,k}\left(x\right)=l\frac{e^{kx}}{e^{k(x-c)}+1}.$$

Note that this $l$ is different from that in this article. The turning point of this curve is at $x=c$ (where it takes the value of $l{e}^{kc}/2$) while its supremum is $l{e}^{kc}$; it tends to this value as $x\to \infty$. Take the limit as $c\to \infty$ as being the exponentials:

$$F_{\infty ,l,k}\left(x\right)=l{e}^{kx}.$$

Figuring out the right curve

We’ll imagine a simple Bayesian setup. An analyst of logistic curves is seeing data from one distribution, and has two hypotheses about it: $F_{C,L,K}$, for values $C$, $L$, and $K$, and $F_{c,l,k}$ with values $c$, $l$, and $k$. We’ll designate $F_{C,L,K}$ by $F$ and $F_{c,l,k}$ by $f$.

Now, the true distribution is $F$, but the analyst doesn’t know that. The question we’re asking is thus:

• Starting from an equal prior on $F$ and $f$, how much of what kind of observation will the analyst need to establish that $F$ is the true underlying distribution?

Noisy Sampling

If the analyst can sample noiselessly from the curve, then three samples should generally suffice to fully establish $F$, and one sample should generally suffice to distinguish $F$ from $f$. So we’ll consider the (realistic) situation where there is noise in the samples.

So assume the analyst samples $n$ points, at $\overrightarrow{x}=(x_1,x_2,\dots ,x_n)$. In return, it gets $n$ values, $\overrightarrow{y}=(y_1,y_2,\dots ,y_n)$; these are sampled independently from $N\left(F\right(x_i),{\sigma }_i^2)$. This is a normal distribution with mean $F\left(x_i\right)$ and standard deviation ${\sigma }_i$.

The analyst is assumed to know the vector $\overrightarrow{\sigma }=({\sigma }_1,\dots {\sigma }_n)$, and indeed everything about this setup, with one exception: whether the means of these normal distributions are $F\left(x_i\right)$ or $f\left(x_i\right)$.

Let $P_a$ be the analyst’s probability distribution. Their prior gives equal weight to both hypotheses: $P_a\left(F\right)=P_a\left(f\right)=1/2$. Let $O_{\overrightarrow{x}}^{\overrightarrow{y}}$ be the analyst observing $\overrightarrow{y}$ after sampling from $\overrightarrow{x}$; their posterior is then $P_a(f\mid O_{\overrightarrow{x}}^{\overrightarrow{y}})$.

Note that, from our perspective, $P_a(F\mid \overrightarrow{x})$ is a random variable whose distribution we know. Say that:

• $\overrightarrow{x}$ establishes the difference between $F$ and $f$ if the expectation of $P_a(F\mid \overrightarrow{x})$ is less than $1/16$.

We could choose other criteria, and this a relatively loose one. It only assumes three bits of information in favour of $F$ over $f$. Note that since $P_a\ge 0$, we can get probability bounds on $P_a$ as well, from this result; for instance:

• If $E\left[P_a\right(f\mid \overrightarrow{x}\left)\right]\le q/4$, then with probability at least $3/4$, $P_a(f\mid \overrightarrow{x})\le q$.

So, for instance, our criteria above ensures that with probability at least $3/4$, $P_a(f\mid \overrightarrow{x})\le 1/4$. Conversely, since $P_a\le 1$, probability bounds on $P_a$ translate into expectation bounds, making the two approaches loosely equivalent. We’ll use expectation bounds, as they are more natural for this random variable.

Bounding results

Our first result, proven in later sections, is a lower bound on the expectation of $P_a(f\mid \overrightarrow{x})$:

$$\begin{array}{ccc}E\left[P_a\right(f\mid \overrightarrow{x}\left)\right]& \ge \frac{1}{2}{\prod }_{i=1}^n[1-\mathrm{erf}\left(\frac{{\delta }_i}{{\sigma }_{i}2\sqrt{2}}\right)].& \left(1\right)\end{array}$$

Here $\mathrm{erf}$ is the error function and ${\delta }_i$ is the absolute difference between $F\left(x_i\right)$ and $f\left(x_i\right)$. We can then get the slightly looser but more easily computable bound:

$$\begin{array}{ccc}E\left[P_a\right(f\mid \overrightarrow{x}\left)\right]& \ge \frac{1}{2}[1-{\sum }_{i=1}^n\frac{{\delta }_i}{{\sigma }_i\sqrt{2\pi }}].& \left(2\right)\end{array}$$

How to sample

Sampling very large positive or negative values

Note that:

$$0\le F_{c,l,k}=l\frac{e^{kx}}{e^{k(x-c)}+1}\le l{e}^{kx}.$$

Hence we can bound the ${\delta }_i$ via:

$${\delta }_i=|F\left(x_i\right)-f\left(x_i\right)|\le max(L{e}^{K{x}_i},l{e}^{k{x}_i}).$$

Let $m\left(x_i\right)=max(L{e}^{K{x}_i},l{e}^{k{x}_i})$; note this is an increasing function, exponential for very negative $x_i$.

Assume we sample $n^{\prime }$ different $x_i$ values below a very negative $X$; then if ${\sigma }^{-}$ is the minimum of all the ${\sigma }_i$ for $x_i\le X$, the contribution of these $n^{\prime }$ points to the expectation bound is at most $0$ and at least:

$$-n^{\prime }\frac{1}{{\sigma }^{-}\sqrt{2\pi }}m\left(X\right).$$

This gives our result for very negative values:

• If noise is irreducible below ${\sigma }^{-}$, then sampling below a very negative $X$ will have very little impact on the analyst’s posterior. To get a better result, increasing the $X$ (exponential effect) is generally more powerful than decreasing ${\sigma }^{-}$ (inverse linear effect), and much more powerful than getting more samples (linear effect).

The behaviour for large positive $x_i$ is also clear: unless $l{e}^{kc}=L{e}^{KC}$, $f$ and $F$ must have different asymptotes. So as long as there is an upper bound ${\sigma }^{+}$ on the noise, sampling the curve at large values will cause the expectation of $P_a(f\mid \overrightarrow{x})$ to converge to $0$. For large $x_i$, this is essentially trying to distinguish $N(l{e}^{kc},{\sigma }^{+})$ from $N(L{e}^{KC},{\sigma }^{+})$, so each extra sample applies a multiplicative factor to the expected value of $P_a(f\mid \overrightarrow{x})$. So, for large samples, the probability of the wrong function converges geometrically to zero in the number of samples.

Finding (any) turning point

So, distinguishing $F$ and $f$ for very low samples is very hard, but distinguishing them for very high samples is generally not very useful. But enough about asymptotic behaviour. The question is: what happens in between, closer to the turning points $C$ and $c$ of $F$ and $f$?

We can make some scaling and translation choices to simplify $F$, setting $c=0$ and $l=k=1$. So the turning point is at $0$ ($y$ value $1/2$) and the supremum is $1$:

$$F\left(x\right)=\frac{e^x}{e^x+1}=\frac{1}{1+e^{-x}}.$$

Assume now that the noise ${\sigma }_i$ is a constant $\sigma$. We want $f$ to have a different turning point, so that can see how easy it is to identify this turning point. Let’s choose the worst possible scenario: $f$ is an exponential function with no turning point:

$$f\left(x\right)=l{e}^{kx}.$$

So, how can the analyst sample so that they have the greatest possible chance of distinguishing between a true function with a turning point at $0$, and a false function with no turning point at all?

We have two free variables: the $k$ and $l$ of $f$, and we typically want to see how well we can do when sampling below a given $X$. For constant $\sigma$, the elements of the bound are given by:

$$\frac{{\delta }_i}{\sigma \sqrt{2\pi }}=\frac{|F\left(x_i\right)-f\left(x_i\right)|}{\sigma \sqrt{2\pi }}=\left|\frac{l{e}^{(k+1)x}+l{e}^{kx}-e^x}{(e^x+1)\sqrt{2\pi }}\right|\frac{1}{\sigma }.$$

Define $d(l,k)\left(x\right)$ as this function, without the $\sigma$ term. We’ll now consider $X=0$, ie we are sampling at any point before the turning point. Then some experimentation allows us to minimize $d(l,k)\left(x\right)$ for negative values, by setting $l=0.51$ and $k=0.69$; given these values, $d(l,k)\left(x\right)$ is bounded above by $0.007$:

Consequently we can use equation (2) to get a bound:

$$\begin{array}{cc}E\left[P_a\right(f\mid \overrightarrow{x}\left)\right]& \ge \frac{1}{2}[1-\frac{n}{\sigma }0.007]\end{array}$$

To establish the difference between $F$ and $f$, we need this below $1/16$. Consequently, we need $\frac{n}{\sigma }0.007\ge \frac{7}{8}$, or

$$\frac{n}{\sigma }\ge 125.$$

So if the noise is $1/200$, ie $1\%$ of the value at the turning point, a single data point might suffice. But if the noise is $10\%$ of the value at the turning point, then at least seven samples are needed.

Anyway, that’s all the way to the turning point; what about if $X$ is chosen so that the value $F\left(X\right)$ is $1/3$ (two thirds of the value at the turning point) or $1/4$ (a half of the value at the turning point)? To get these, we need $X=-\log \left(2\right)$ and $X=-\log \left(3\right)$, respectively. We’ll also look at past the turning point, $X=\log \left(2\right)$ and $\log \left(3\right)$.

Optimising $l$ and $k$ for all five situations give:

• For $X=-\log \left(3\right)$, $\frac{n}{\sigma }0.0015\ge \frac{7}{8}$ or $\frac{n}{\sigma }\ge 583$.

• For $X=-\log \left(2\right)$, $\frac{n}{\sigma }0.0027\ge \frac{7}{8}$ or $\frac{n}{\sigma }\ge 324$.

• For $X=0$, $\frac{n}{\sigma }0.007\ge \frac{7}{8}$ or $\frac{n}{\sigma }\ge 125$.

• For $X=\log \left(2\right)$, $\frac{n}{\sigma }0.015\ge \frac{7}{8}$ or $\frac{n}{\sigma }\ge 58$.

• For $X=\log \left(3\right)$, $\frac{n}{\sigma }0.021\ge \frac{7}{8}$ or $\frac{n}{\sigma }\ge 41$.

But equation (2) gives poor bounds for low $\sigma$. Using equation (1) instead, for $\sigma =1/200$ ($1\%$ of turning point $y$-value) and $\sigma =1/20$ ($10\%$ of turning point $y$-value), gives the number $n$ of samples needed as:

$$\begin{array}{ccc}X& \sigma =1/200& \sigma =1/20\\ -\log \left(3\right)& 6& 69\\ -\log \left(2\right)& 3& 38\\ 0& 1& 14\\ \log \left(2\right)& 1& 6\\ \log \left(3\right)& 1& 5\end{array}$$

Other difficulties

The bounds above are only good if the values are sampled independently and close to the peak of the $d(l,k)$ function. If the values are not independent—as values sampled close to each other tend not to be—then more must be sampled, and the same goes if the values are sampled away from the peaks.

The other issue is that, here, we’ve first optimised $l$ and $k$ for minimal peak of $d(l,k)$, then assumed the best $x_i$ were sampled. We need to consider the opposite situations, too: given the sampled $x_i$, optimise $l$ and $k$. So, even if $n$ samples are enough to distinguish $F$ from this specific $f$, there are other exponential functions $F_{\infty ,l,k}$ that would be harder to distinguish from $F$.

Proof

This section will prove the bounds in equation (1) and (2).

By Bayes rule:

$$\begin{array}{cc}{P}_a(f\mid O_{\overrightarrow{x}}^{\overrightarrow{y}})& =\frac{P_a(O_{\overrightarrow{x}}^{\overrightarrow{y}}\mid f)P_a\left(f\right)}{P_a\left(O_{\overrightarrow{x}}^{\overrightarrow{y}}\right)}\\ & =\frac{P_a(O_{\overrightarrow{x}}^{\overrightarrow{y}}\mid f)P_a\left(f\right)}{P_a(O_{\overrightarrow{x}}^{\overrightarrow{y}}\mid f)P_a\left(f\right)+P_a(O_{\overrightarrow{x}}^{\overrightarrow{y}}\mid F)P_a\left(F\right)}\\ & =\frac{P_a(O_{\overrightarrow{x}}^{\overrightarrow{y}}\mid f)}{P_a(O_{\overrightarrow{x}}^{\overrightarrow{y}}\mid f)+P_a(O_{\overrightarrow{x}}^{\overrightarrow{y}}\mid F)},\end{array}$$

since the prior probabilities are equal. Since the analyst knows the true variances, $P_a(O_{\overrightarrow{x}}^{\overrightarrow{y}}\mid f)=P(O_{\overrightarrow{x}}^{\overrightarrow{y}}\mid f)$ and similarly for $F$: we can replace the analyst’s probabilities with the true probabilities. So, contracting $P(O_{\overrightarrow{x}}^{\overrightarrow{y}}\mid F)$ as $p_1\left(\overrightarrow{y}\right)$ and $P(O_{\overrightarrow{x}}^{\overrightarrow{y}}\mid f)$ as $p_2\left(\overrightarrow{y}\right)$, we get:

$$\begin{array}{cc}{P}_a(f\mid O_{\overrightarrow{x}}^{\overrightarrow{y}})& =\frac{p_2\left(\overrightarrow{y}\right)}{p_2\left(\overrightarrow{y}\right)+p_1\left(\overrightarrow{y}\right))}\\ & =\frac{1}{1+p_1\left(\overrightarrow{y}\right)p_2(\overrightarrow{y}{)}^{-1}}.\end{array}$$

To get the true expectation of this $P_a$, we need to integrate over the possible values of $\overrightarrow{y}$, weighted by the true probability $P(O_{\overrightarrow{x}}^{\overrightarrow{y}}\mid F)=p_1\left(\overrightarrow{y}\right)$ of this happening:

$$\begin{array}{cc}E\left[P_a\right(f\mid \overrightarrow{x}\left)\right]& =\int \frac{1}{1+p_1\left(\overrightarrow{y}\right)p_2(\overrightarrow{y}{)}^{-1}}{p}_1\left(\overrightarrow{y}\right)d\overrightarrow{y}\\ & =\int \frac{1}{p_1(\overrightarrow{y}{)}^{-1}+p_2(\overrightarrow{y}{)}^{-1}}d\overrightarrow{y}.\end{array}$$

Note that $p_1\left(\overrightarrow{y}\right)$ and $p_2(\overrightarrow{y}{)}^{-1}$ are both (strictly) positive, and that $1/\left(p_1\right(\overrightarrow{y}{)}^{-1}+p_2\left(\overrightarrow{y}{)}^{-1}\right)$ is half the harmonic mean of the two.

The harmonic mean of any number of positive elements is bounded below by the minimum value of its arguments. Hence: $$\begin{array}{cc}E\left[P_a\right(f\mid \overrightarrow{x}\left)\right]& \ge \frac{1}{2}\int min\left(p_1\right(\overrightarrow{y}),p_2(\overrightarrow{y}\left)\right)d\overrightarrow{y}.\end{array}$$

Now, since the noise is independent, $p_j\left(\overrightarrow{y}\right)={\prod }_{i=1}^n{p}_j\left(y_i\right)$ where $p_1\left(y_i\right)=P(y_i\mid x_i,F)$ and $p_2\left(y_i\right)=P(y_i\mid x_i,f)$. For positive elements, the minimum of two products is greater than or equal to the product of minimums, so

$$\begin{array}{cc}E\left[P_a\right(f\mid \overrightarrow{x}\left)\right]& \ge \frac{1}{2}{\int }_{-\infty }^{\infty }{\prod }_{i=1}^{n}min\left(p_1\right(y_i),p_2(y_i\left)\right)d\overrightarrow{y}\\ & \ge \frac{1}{2}{\prod }_{i=1}^n{\int }_{-\infty }^{\infty }min\left(p_1\right(y_i),p_2(y_i\left)\right)d{y}_i.\end{array}$$

The expressions $min\left(p_1\right(y_i),p_2(y_i\left)\right)$ can be expressed analytically. If $\phi$ is the probability density function of $N(0,1)$, the normal distribution with mean $0$ and variance $1$, then

$$\begin{array}{cc}{p}_1\left(y_i\right)& =\frac{1}{{\sigma }_i}\phi \left(\frac{F\left(x_i\right)-y_i}{{\sigma }_i}\right),\\ p_2\left(y_i\right)& =\frac{1}{{\sigma }_i}\phi \left(\frac{f\left(x_i\right)-y_i}{{\sigma }_i}\right).\end{array}$$

So the two curves are normal curves with the same variance and means $F\left(x_i\right)$ and $f\left(x_i\right)$. Assume, without loss of generality, that $F\left(x_i\right)\le f\left(y_i\right)$. Then the two functions will be equal at the midpoint ${\mu }_i=\left(F\right(x_i)+f(x_i\left)\right)/2$, and for $y_i\le {\mu }_i$, $p_1\left(y_i\right)$ is higher, while for $y_i\ge {\mu }_i$, $p_2\left(y_i\right)$ is higher.

Thus $$min\left(p_1\right(y_i),p_2(y_i\left)\right)=\{\begin{array}{c}\frac{1}{{\sigma }_i}\phi \left(\frac{f\left(x_i\right)-y_i}{{\sigma }_i}\right),y_i\le {\mu }_i,\\ \frac{1}{{\sigma }_i}\phi \left(\frac{F\left(x_i\right)-y_i}{{\sigma }_i}\right),y_i\ge {\mu }_i.\end{array}$$

If ${\delta }_i=|F\left(x_i\right)-f\left(x_i\right)|$ is the distance between the two peaks, this becomes: $$min\left(p_1\right(y_i),p_2(y_i\left)\right)=\{\begin{array}{c}\frac{1}{{\sigma }_i}\phi \left(\frac{{\mu }_i+{\delta }_i/2-y_i}{{\sigma }_i}\right),y_i\le {\mu }_i,\\ \frac{1}{{\sigma }_i}\phi \left(\frac{{\mu }_i-{\delta }_i/2-y_i}{{\sigma }_i}\right),y_i\ge {\mu }_i.\end{array}$$

Since the integral of $\phi$ is $1/2[1+\mathrm{erf}(y/\sqrt{2}\left)\right]$, for $\mathrm{erf}$ the error function, we can bound the expected probability by:

$$\begin{array}{cc}E\left[P_a\right(f\mid \overrightarrow{x}\left)\right]& \ge \frac{1}{2}{\prod }_{i=1}^n{\int }_{-\infty }^{\infty }min\left(p_1\right(y_i),p_2(y_i\left)\right)d{y}_i\\ & \ge \frac{1}{2}{\prod }_{i=1}^n({\int }_{-\infty }^{{\mu }_i}\frac{1}{{\sigma }_i}\phi \left(\frac{{\mu }_i+{\delta }_i/2-y_i}{{\sigma }_i}\right)d{y}_i+{\int }_{{\mu }_i}^{\infty }\frac{1}{{\sigma }_i}\phi \left(\frac{{\mu }_i-{\delta }_i/2-y_i}{{\sigma }_i}\right)d{y}_i)\\ & \ge \frac{1}{2}{\prod }_{i=1}^n({\int }_{-\infty }^{-{\delta }_i/2}\frac{1}{{\sigma }_i}\phi \left(\frac{-y_i}{{\sigma }_i}\right)d{y}_i+{\int }_{{\delta }_i/2}^{\infty }\frac{1}{{\sigma }_i}\phi \left(\frac{-y_i}{{\sigma }_i}\right)d{y}_i)\\ & \ge \frac{1}{2}{\prod }_{i=1}^n(\frac{1}{2}[1+\mathrm{erf}\left(\frac{-{\delta }_i/2}{{\sigma }_i\sqrt{2}}\right)]+\frac{1}{2}[1+\mathrm{erf}\left(\frac{-{\delta }_i/2}{{\sigma }_i\sqrt{2}}\right)])\\ & \ge \frac{1}{2}{\prod }_{i=1}^n[1-\mathrm{erf}\left(\frac{{\delta }_i}{{\sigma }_{i}2\sqrt{2}}\right)].\end{array}$$

For positive values, the error function is concave, and it has derivative $2/\sqrt{\pi }$ at the origin, so

$$\mathrm{erf}\left(\frac{{\delta }_i}{{\sigma }_{i}2\sqrt{2}}\right)\le \frac{2}{\sqrt{\pi }}\frac{{\delta }_i}{{\sigma }_{i}2\sqrt{2}}=\frac{{\delta }_i}{{\sigma }_i\sqrt{2\pi }}.$$

Consequently

$$\begin{array}{cc}E\left[P_a\right(f\mid \overrightarrow{x}\left)\right]& \ge \frac{1}{2}{\prod }_{i=1}^n[1-\frac{{\delta }_i}{{\sigma }_i\sqrt{2\pi }}].\end{array}$$

Using the fact that for $x,y$ positive, $(1-x)(1-y)\ge 1-(x+y)$, we get a final bound:

$$\begin{array}{cc}E\left[P_a\right(f\mid \overrightarrow{x}\left)\right]& \ge \frac{1}{2}[1-{\sum }_{i=1}^n\frac{{\delta }_i}{{\sigma }_i\sqrt{2\pi }}]\end{array}$$