These kinds of issues are why https://en.wikipedia.org/wiki/Extended_precision was widely used since the 80's, both in language implementations and FPUs/CPUs.
Python has Decimal for those who need correctness under all circumstances.
Calculating the mean of a list of numbers (2016)
51–60 of 96 posts
Re: Calculating the mean of a list of numbers (2016)
#52you want to in practice calculate exponential moving average
Re: Calculating the mean of a list of numbers (2016)
#53An interesting article describing a useful framework. In addition to the largest numbers that floating point can handle, a related issue can come up with numbers that are not near the edge. A good student of floating point numbers will notice that there is a good chance you will get a different result summing a list of floating point numbers if they are sorted in a different order. This is due to the rounding error t…
> Thus, you should sort an array of floating point numbers and begin the summation with the smallest Is this method more accurate than Kahan summation? And if so, is it worth the extra cost of sorting?
No, in fact it's slower than Kahan summation and less accurate. In particular, sorting doesn't help if you sum up a large number of similarly small values.
Re: Calculating the mean of a list of numbers (2016)
#54What about a "reduce" technique? Average the numbers in equal-sized chunks, then average those averages. You could even chunk the chunk averages and repeat the process as many levels down as you want to, and chunks could be as small as 2 each. I guess this still assumes that the largest number in the original list is less than or equal to the maximum floating point value, but otherwise you stay roughly in the same sp…
I believe you have pairwise / cascade summation in mind:
Re: Calculating the mean of a list of numbers (2016)
#55reduce(lambda x,y: (x+y)/2.0, numlist) Why wouldn't this work?
The function is not associative.
Re: Calculating the mean of a list of numbers (2016)
#56An 'online' mean calculation might resolve some of the common issues. Something like - def mean(ls): mu = 0.0 for i, x in enumerate(ls): mu = i/(i+1) * mu + x/(i+1) return mu
mu = mu + (x - mu) / (i+1)
mu += (x - mu) / (i+1)Re: Calculating the mean of a list of numbers (2016)
#57If you're reaching these values then it's extremely likely that either: (a) You're doing something wrong (usually, not standardizing your data, etc.) which means that you're not thinking about the fact that computers have finite numerical precision and adjusting your problem accordingly (e.g., have a wide dynamic range of numbers). Or, (b) your problem is pretty ill-conditioned and there's probably no solving it in a…
For problem (b), this is the standard case for inverse problems, which are almost always ill-posed / ill-conditioned. There is now a vast literature on this subject, including many algorithms for solving them robustly. "...incorrectly posed problems were considered ‘taboo’ for generations of mathematicians, until comparatively recently it became clear that there are a number of quite meaningful problems, the so-calle…
Hmm... I'm not sure I fully agree. Fundamentally, an ill-posed problem maps a large input space to a very small output space, which means that inverting it is impossible under any noise (in a very similar way to, say, the Nyquist-Shannon theorem)—unless you know something more about the noise (e.g., concentration phenomena in differential privacy) or the underlying signal (e.g., sparsity in compressed sensing), or you don't mind the noise in the parameters so long as the output signal is well-represented by your parameters (generally anything in ML).
A ton of these cases which are "usually" ill-posed, as in compressed sensing, physical design, etc., have some more structure which is encoded as regularizers or priors. For example, in compressed sensing, we know the input signal is sparse, so even though we have far less samples than the Nyquist rate would require, we know something else about the input signal, usually encoded as an l1-regularizer or other kind of sparsifying regularizer, making the resulting optimization problem well-posed.
That being said, I'm not sure how this immediately plays into (b). My claim is that you're pretty much hosed unless you increase the general precision/range of the algorithm, which is independent of the noise in the input, but rather depends on the actual implementation of the algorithm and the atoms the algorithm uses (sums, multiplications, etc., of two floating point numbers, for example). The case being that you have to increase the precision of the atoms which the algorithm uses (e.g., like in the article, switching to arbitrary-precision fractions when sums of large numbers are needed).
---
NOTE: I guess more generally, I'm defining ill-conditioning/numerical instability as a problem with the algorithm in the sense that, for a fixed input precision, perfect arithmetic (the "correct" result) will differ heavily from the result with truncated arithmetic (with floats, or whatever it may be).
Re: Calculating the mean of a list of numbers (2016)
#58Earlier quoted context omitted.
Most of the issues discussed in the article are not from limits in precision, they're from overflows that arise from limits in the exponential range. Finding the average of 8e+307 and 8e+307 is a "low precision" problem, and even naive methods to avoid overflow will not hit limits on precision in this case (e.g. 8e+307/2 + 8e+307/2). You're right that there are issues with precision and floating point math (the artic…
Sorry, I should’ve been more clear: when I said “precision” I meant any of several things related to floating point arithmetic including, but not limited to: actual numerical precision of operations, non-associativity of operations, overflows (which affects the latter case as well), etc. (Which is why I mention dynamic range in the GP.) The point is that there is an “unwritten contract” between the user and the libra…
Great explanation and detail. If one faces a badly conditioned problem, one must think about the error inherent to the inputs. Anything measured from real sensors is already corrupted by that perturbation matrix. Even in some perfect scenario like a model generated by CAD, the corresponding physical object is not going to match.
Numerical stability feels like this black art that programmers are scared of, but I maybe it's less scary if you explain the core problem: nothing in the world is a real number, it's always a probability distribution.
Re: Calculating the mean of a list of numbers (2016)
#59Calculating (a+b)/2 isn't even entirely trivial for integers - the trivial implementation overflows on large numbers, as one may find out when doing a binary search over a 4GB array.
`(uint32_t) (((uint64_t) a + (uint64_t) b) / 2)` and then go on with your life. :P
Re: Calculating the mean of a list of numbers (2016)
#60And then there was Clojure...
(defn average [numbers] (/ (apply + numbers) (count numbers)))
(average [8.988465674311579e+307M, 8.98846567431158e+307M])
=> 8.9884656743115795E+307M