Update `Statistex.variance` to use Welford's online algorithm
Earlier today I opened bencheeorg/benchee#472, and I started thinking about how Statistex could be used to accomplish this. Statistex already supports calculating several statistics while ignoring the list of samples, if the prerequisite parts are available to the caller (e.g. average can be called with :total and :sample_size)
One statistic that didn't support this today was variance (and by extension standard_deviation), since both require the entire list of samples to operate. Algorithms to calculate variance "on-line" exist, such as Welford's Online Algorithm, but they depend on a different statistic, m2. This statistic is "the running sum of squared differences from the current mean", and really only has a meaning in the context of computing variance.
In this PR, I've:
- added this
m2statistic - updated the
variancestatistic to usem2when calculatingvarianceinstead ofaverage - I also exposed this
m2statistic on the top levelStatistexstruct, even if it's not a particularly useful statistic on its own.- (I figured the ability for users to incrementally update statistics like
varianceandstandard_deviationwas in keeping with Statistex's philosophy of avoiding recomputation.)
- (I figured the ability for users to incrementally update statistics like
This PR also updates some typespecs to better capture the :ignored behavior for statistics that support it, and tweaks the last few digits of floating point results from the variance and standard_deviation statistic. I'm not a statistics expert, but I believe that my floating point tweaks represent a shift towards more accuracy, not less, given the notes about loss of precision on the above linked Wikipedia page:
[The Welford's online] algorithm is much less prone to loss of precision due to catastrophic cancellation, but might not be as efficient because of the division operation inside the loop.
I didn't open an issue before I opened this PR, so I know these changes might not be desired - if so, please let me know! I'd love to discuss better ways to handle what I described in bencheeorg/benchee#472 if this isn't the best approach.
Thanks for the detailed comments! No worries about the quantity, I also prefer detailed notes instead of one larger comment. I'll take a look at making some of these tweaks soon.
I was also curious about the benchmarking, and my first thought was to use Benchee. @PragTob would you be OK if I added some tests that benchmarked this library using Benchee? Even if that might make a circular dependency between Benchee and Statistex?
@weaversam8 if you can make the circular dependency work, for sure! Otherwise, a separate repo may be the solution. I've definitely benchmarked benchee using benchee :)
Also sorry for the silence... I'll appologize in some other thread :sweat_smile: