P² quantile estimator – estimating the median without storing values
aakinshin.net
aakinshin.net
The unfortunately now deceased neustar research blog had an interactive widget as well an outstanding write up[2]
I used to know what a sub gradient was, but I think there must be something more to the ideas in the paper because I’m struggling to see the analogy between gradient descent where you take steps probabilistically and the algorithm described. Perhaps I need to think about how you could potentially recast the quantile estimation problem as an optimisation problem and then apply what is effectively the machinery developed the train neural nets. Very interesting connection!
This seems to be particularly true in computer learning. We’re taking about a conditional step function here, right?
Think of it as a 'hello world' program. The typically 'hello world' program in eg Java teaches you more about the lingo of Java than about solving the problem of putting 'hello world' on the screen.
(Of course, there are still plenty of bad reasons to describe simple things in complex lingo. But the above is one good reason.)
I was quite startled when I saw that article published as I had been using this very method for years. Once you make the connection that quantiles (and not just a median) are the minimum of a suitably chosen loss function the rest is very straightforward.
Then there is expectiles too.
Starting from the observation that the expectation of X is the constant c which minimizes the squared loss E[(X - c)^2], we can now generalize expectation by generalizing the loss function we aim to minimize.
They do this by asymmetrically weighting over- or under-estimates, unlike the squared loss which is symmetric.
This apparently has nice properties which the paper goes into.
TLDR expectiles are to mean what quantiles are to median.
A longer explanation follows.
Mean can be looked upon as a location that minimizes a scheme of penalizing your 'prediction' of (many instances of) a random quantity. You can assume that the instances will be revealed after you have made the prediction. If your prediction is over/larger by e you will be penalized by e^2. If your prediction is lower by e then also the penalty is e^2. This makes mean symmetric. It punishes overestimates the same way as underestimates.
Now if you were to be punished by absolute value |e| as opposed to e^2 then median would be your best prediction. Lets denote the error by e+ if the error is an over-estimate and -e- if its under. Both e+ and e- are non-negative. Now if the penalties were to be * e+ + a e- * that would have led to the different quantiles depending on the values of a > 0. Note a \neq 1 introduces the asymmetry.
If you were to do introduce a similar asymmetric treatment of e+^2 and e-^2 that would have given rise to expectiles.
Also, can we initiate the filter to a sensible nonzero value instead of zero to speed up convergence and start off with a sensible estimate?
I'm guessing the answer to both questions is yes.
Further, I don't think "number of items > k*median" is a particularly grueling criterion for this algorithm (where k is some constant based on the delta).
Here is the first paragraph of the Introduction, for your reference:
> Modern applications require processing streams of data for estimating statistical quantities such as quantiles with small amount of memory. A typical application is in IP packet analysis systems such as Gigascope [8] where an example of a query is to find the median packet (or flow) size for IP streams from some given IP address. Since IP addresses send millions of packets in reasonable time windows, it is prohibitive to store all packet or flow sizes and estimate the median size. Another application is in social networking sites such as Facebook or Twitter where there are rapid updates from users, and one is interested in median time between successive updates from a user. In yet another example, search engines can model their search traffic and for each search term, want to estimate the median time between successive instances of that search.
You can also read the paper to see how they implement Frugal-2U, which has better convergence characteristics for twice the memory.
They even address your specific complaint: "Note that Frugal-1U and Frugal-2U algorithms are initialized by 0, but in practice they can be initialized by the first stream item to reduce the time needed to converge to true quantiles."
I don't know if you realize but these kinds of comments are incredibly frustrating to respond to. It's like you didn't even try to understand the comment before replying. I was not saying "it's terrible because it easily fails on 5 elements". I was saying "it's terrible because it easily fails, and to illustrate, here's an example with 5 elements that will help you understand the problem I'm talking about". Does that make sense? Surely it's not rocket science to see that the number 5 wasn't special here? Surely you can see how, say, if your list starts at 2E9 and goes up to 3E9, the exact same problem would occur for the billion-element list, and hence that my gripe was probably not about 5-element lists?
It doesn't have to be accurate for all possible edge cases because that's not the point of cheap estimation like this.
This is practically the definition of monotonicity. (https://en.wikipedia.org/wiki/Monotonic_function)
You should read the paper, it doesn't have the problems you think it has when used on real world data.
Also note that the parent wasn't commenting on the algorithm in this HN submission, but rather the algorithm described in the top-level comment.
Your examples do relate to problems the algorithm actually has in this application, but they manifest as things like "extremely large warmup time" and "adjusting to a regime change in the distribution taking time proportional to the change". For instance if your data is [1000, 1001, 1000, 1001...] then it takes 1000 steps to converge, which may be longer than the user has patience for.
However, the algorithm does always converge eventually, as long as the stream is not something pathological like an infinite sequence of consecutive numbers (for which the median is undefined anyhow).
> These algorithms do not perform well with adversarial streams, but we have mathematically analyzed the 1 unit memory algorithm and shown fast approach and stability properties for stochastic streams
Your criticism is really pretty strident for saying something the authors probably completely understand and agree with.
I think, as you suggest, it's more fun to say "given my distribution x, what's a good statistic for the median and what are its properties?" than "what's a good general purpose technique for finding a median of any distribution subject to computational constraint y"
It’s to optimize finding the median from a tape drive in the 70s, but the technique is pretty cute.
You make a guess at the median, then basically sum how many are over, and under that value, then guess again until you have an even split.
It’s also a problem I like to use to nerd snipe people, because why not.
Check my work, because it’s been a long time since I worked with FORTRAN and I could have just remembered incorrectly :)
https://github.com/MikeJaredS/hermiter
I've done some comparisons versus the P^2 algorithm (using the OnlineStats implementation in Julia) and the Hermite series based algorithm appears to have comparable accuracy in the tests conducted. The Hermite based approach has the advantage that it estimates the full quantile function though, so arbitrary quantiles can be obtained at any point in time.
I've found Greenwald-Khanna to be a lot more accurate, and also quite suitable for turning into a visual PDF representation
there is a compression pass that you can run whenever you want that collapses subtrees, so you can tune that for a little time/memory tradeoff.
the best part though is that they are composable. you can take two GK representations and merge them. and you can operate on them (truncate, convolve, scalar transforms) which makes them really good summaries for query optimizers.