“On-line” (iterator) algorithms for estimating statistical median, mode, skewness, kurtosis?

by

I use these incremental/recursive mean and median estimators, which both use constant storage:

mean += eta * (sample - mean)
median += eta * sgn(sample - median)

where eta is a small learning rate parameter (e.g. 0.001), and sgn() is the signum function which returns one of {-1, 0, 1}. (Use a constant eta if the data is non-stationary and you want to track changes over time; otherwise, for stationary sources you can use something like eta=1/n for the mean estimator, where n is the number of samples seen so far… unfortunately, this does not appear to work for the median estimator.)

This type of incremental mean estimator seems to be used all over the place, e.g. in unsupervised neural network learning rules, but the median version seems much less common, despite its benefits (robustness to outliers). It seems that the median version could be used as a replacement for the mean estimator in many applications.

I would love to see an incremental mode estimator of a similar form…

UPDATE (2011-09-19)

I just modified the incremental median estimator to estimate arbitrary quantiles. In general, a quantile function tells you the value that divides the data into two fractions: p and 1-p. The following estimates this value incrementally:

quantile += eta * (sgn(sample - quantile) + 2.0 * p - 1.0)

The value p should be within [0,1]. This essentially shifts the sgn() function’s symmetrical output {-1,0,1} to lean toward one side, partitioning the data samples into two unequally-sized bins (fractions p and 1-p of the data are less than/greater than the quantile estimate, respectively). Note that for p=0.5, this reduces to the median estimator.

UPDATE (2021-11-19)

For further details about the median estimator described here, I’d like to highlight this paper linked in the comments below: Bylander & Rosen, 1997, A Perceptron-Like Online Algorithm for Tracking the Median. Here is a postscript version from the author’s website.

More Related Contents:

  1. Select k random elements from a list whose elements have weights
  2. Find running median from a stream of integers
  3. Finding the median of an unsorted array
  4. 3D Least Squares Plane
  5. How to calculate or approximate the median of a list without storing the list
  6. O(n) algorithm to find the median of n² implicit numbers
  7. Rolling median algorithm in C
  8. Algorithm for sampling without replacement?
  9. How do I find the median of numbers in linear time using heaps?
  10. Apply Quicksort to the list M,E,R,G,E,S,O,R,T
  11. How to determine if a point is in a 2D triangle? [closed]
  12. Data structures for loaded dice?
  13. Writing your own square root function
  14. How to determine if a linked list has a cycle using only two memory locations
  15. Computing set intersection in linear time?
  16. Getting the submatrix with maximum sum?
  17. Circle-circle intersection points
  18. What is a bubble sort good for? [closed]
  19. Sorting in place
  20. How to incrementally sample without replacement?
  21. Hashing a Tree Structure
  22. Painter puzzle – algorithmic estimation from first principles
  23. Polynomial time and exponential time
  24. The best shortest path algorithm
  25. Algorithm for permutations of operators and operands
  26. Fastest way of finding the middle value of a triple?
  27. Compute the area of intersection between a circle and a triangle?
  28. Unbiased random number generator using a biased one
  29. maximum subarray of an array with integers [duplicate]
  30. CUDA stream compaction algorithm

Leave a Comment