Hacker News Board Hacker News, browsed like a classic message board
Live data from Hacker News

Estimating the chances of something that hasn’t happened yet

johndcook.com

Post reply on HN
Print view View original

111–120 of 155 posts

Re: Estimating the chances of something that hasn’t happened yet

#111

Post by chrismcb »

userbinator wrote: post #108
rspeer wrote: post #21

If the author is reading this: When someone provides you a pro-bono translation, by all means credit them, but do not let them host it on their own site. Frequently, they are siphoning your PageRank. They will eventually replace the translation with monetized content of their choice. A good translation takes work! If you got a translation for free, why should you believe it's good, or that it has no ulterior motive?…

The obsession with SEO is what leads to things like this in the first place. Maybe the sooner people stop paying attention to it, the sooner search engines will learn to find better metrics.

You mean better metrics that can be optimized?

Re: Estimating the chances of something that hasn’t happened yet

#112

Post by ezzaf »

nitwit005 wrote: post #56
madrox wrote: post #14

What the author glosses over somewhat is the method of sampling. If you read the first 20 pages, find no typos, and use this rule to arrive at 15%, that could be way off. He's assuming the risk of typos are evenly distributed when there's a lot of reasons it may not be. For example, the first half of the book could've been more heavily proof-read than the latter half. It's not out of the question that editors get laz…

Doesn't the book example need to factor in the book length? If you read 20 pages, and it's 20 pages long, you should be 100% confident, but if you read 20 pages and it's 5000 pages long, your confidence should be near 0.

In effect it does. If you have read 20 pages and found no typos you estimate the chance of an unknown page having a typo is 1 in 20/3. But if there is 0 unread pages then there 0 cases to apply the probability to. Make it 100 pages, then you have 100 cases each with a 1 in 20/3 probability. Of course if you read 30 more and still don't find a typo, it's now 50 remaining cases each with a 1 in 50/3 (estimated) probability.

Re: Estimating the chances of something that hasn’t happened yet

#113

Post by justinpombrio »

ced wrote: post #107
cperciva wrote: post #28

This reminds me of a different "rule of 3": If you want to compare two things (e.g., "is my new code faster than my old code"), a very simple approach is to measure each three times. If the all three measurements of X are smaller than all three measurements of Y, you have X This works because the probability of the ordering XXXYYY happening by random chance is 1/(6 choose 3) = 1/20 = 5%. It's quite a weak approach --…

Man, I wish I understood frequentist statistics to know if your reasoning makes sense. Bayesianly, if O = "the XXXYYY ordering", and F = "algo B is faster than algo" A, then P(F|O) = P(O|F) * P(F) / P(O) then... what? There isn't even a clear P(O|F) likelihood without making assumptions about the process' noise. If the measurement is very noisy compared to the gain, then XXXYYY is just dumb luck, and doesn't tell you…

Let me explain it in a Bayesian way. The Bayesian approach would be to consider a whole bunch of hypotheses about how much better Y does than X (and vice-versa), and a prior distribution over how likely you think each is a-priori. Then for each sample S, you update the probability of each hypothesis H by multiplying its probability by P(S|H), then re-normalize.

Well in this case, we're only going to consider two hypotheses. Call them H0 and H1. H0 is the "null hypothesis", and says that X and Y are exactly as fast as each other. H1 is the hypothesis that H0 is wrong and Y is totally faster than X. You'll notice that H0 is oddly specific, and H1 is ill-defined. Don't worry about it.

To start off, pick your prior distribution over H0 and H1. Pick whatever you want, because we're going to ignore it shortly.

Now some evidence comes in. Time to update! We got the ordering XXXYYY. First, let's update H0. P(XXXYYY|H0) = 1 / 6choose3 = 5%. Wow, that's not a very good update for H0. It's probably just false. For expediency, let's just toss it out.

H1 is the remaining hypothesis. H1 wins! Y is faster than X.

Re: Estimating the chances of something that hasn’t happened yet

#114

Post by mabbo »

ced wrote: post #107
cperciva wrote: post #28

This reminds me of a different "rule of 3": If you want to compare two things (e.g., "is my new code faster than my old code"), a very simple approach is to measure each three times. If the all three measurements of X are smaller than all three measurements of Y, you have X This works because the probability of the ordering XXXYYY happening by random chance is 1/(6 choose 3) = 1/20 = 5%. It's quite a weak approach --…

Man, I wish I understood frequentist statistics to know if your reasoning makes sense. Bayesianly, if O = "the XXXYYY ordering", and F = "algo B is faster than algo" A, then P(F|O) = P(O|F) * P(F) / P(O) then... what? There isn't even a clear P(O|F) likelihood without making assumptions about the process' noise. If the measurement is very noisy compared to the gain, then XXXYYY is just dumb luck, and doesn't tell you…

> then XXXYYY is just dumb luck

That's the idea. The null hypothesis is that this is dumb luck. Here's a piece of evidence that, if this is dumb luck, is not very likely. Ergo, the odds this is just dumb luck is low and there may be a real effect here.

As the OP said, it's not meant to be used in a scientific paper, it's to let you see if you might be on the right track.

Re: Estimating the chances of something that hasn’t happened yet

#115

Post by bo1024 »

gerdesj wrote: post #90
bo1024 wrote: post #81

Earlier quoted context omitted.

You're not considering the right probability space. We have 3 measurements of X and 3 of Y. The question is the distribution on orderings of these six measurements. If X and Y come from the same distribution then all orderings are equally likely.

I'm also having trouble with this. On the face of it the quick and dirty "XXXYYY" test outlined above looks good but are these two following statements consistent? ie are the run times of X (new code) and Y (old code) really from the same distribution. "is my new code faster than my old code" "If X and Y come from the same distribution then all orderings are equally likely"

I'm thinking of it as a statistical hypothesis test. The null hypothesis is that they come from the same distribution. Under that hypothesis, there's only a 0.05 chance of seeing three X tests all below three Y tests. So if we see this, we can probably reject the null.

If we think X and Y distributions are both something like normal with similar variance, then we should also be able to say the chance of XXXYYY given Y is better than X is at most 0.05.

But if the distributions for X and Y can be really different, then I think you're right -- this test could be misleading! For example, say Y always takes 2 seconds, and X takes 1 second 90% of the time, but 1% of the time it takes an hour. If we run three tests of each, we'll probably only see good runs from X and conclude it's better, when it's not.

Re: Estimating the chances of something that hasn’t happened yet

#116

Post by srean »

blt wrote: post #68
cperciva wrote: post #39

Earlier quoted context omitted.

Right. And those are also more powerful (and don't need any knowledge of the distribution of measurement errors). I mentioned the "three old and three new" test because it's simple , not because it's powerful.

more powerful in the statistical sense? I though non-parametric tests were usually less powerful than those where a certain distribution is assumed.

You would be surprised what number of samples does to the tests. Take t-test -- the most powerful test to check if means of 2 equivariant Gaussians differ. If you compare the asymptotic efficiency of Mann-Whiney (a distribution free test) relative to t-test is around 0.96. Of course in practice you will not have infinite samples. It then comes down when do these asymptotics kick in. Unfortunately that depends on the distribution.

Re: Estimating the chances of something that hasn’t happened yet

#117

Post by pedrosorio »

justinpombrio wrote: post #113
ced wrote: post #107

Earlier quoted context omitted.

Man, I wish I understood frequentist statistics to know if your reasoning makes sense. Bayesianly, if O = "the XXXYYY ordering", and F = "algo B is faster than algo" A, then P(F|O) = P(O|F) * P(F) / P(O) then... what? There isn't even a clear P(O|F) likelihood without making assumptions about the process' noise. If the measurement is very noisy compared to the gain, then XXXYYY is just dumb luck, and doesn't tell you…

Let me explain it in a Bayesian way. The Bayesian approach would be to consider a whole bunch of hypotheses about how much better Y does than X (and vice-versa), and a prior distribution over how likely you think each is a-priori. Then for each sample S, you update the probability of each hypothesis H by multiplying its probability by P(S|H), then re-normalize. Well in this case, we're only going to consider two hypo…

“P(XXXYYY|H0) = 1 / 6choose3 = 5%. Wow, that's not a very good update for H0. It's probably just false. For expediency, let's just toss it out.”

It only makes sense to toss H0 out if P(XXXYYY|H1) >> 5% (such that the evidence for H1 relative to H0 increases after the observation).

You are implicitly assuming that’s the case because “it makes sense”. But as the parent post mentioned, the likelihood is not defined and in particular if the noise in the observation process is large enough, P(XXXYYY|H1) may be very close to 0.05 as well.

Re: Estimating the chances of something that hasn’t happened yet

#118

Post by mikekchar »

ced wrote: post #107
cperciva wrote: post #28

This reminds me of a different "rule of 3": If you want to compare two things (e.g., "is my new code faster than my old code"), a very simple approach is to measure each three times. If the all three measurements of X are smaller than all three measurements of Y, you have X This works because the probability of the ordering XXXYYY happening by random chance is 1/(6 choose 3) = 1/20 = 5%. It's quite a weak approach --…

Man, I wish I understood frequentist statistics to know if your reasoning makes sense. Bayesianly, if O = "the XXXYYY ordering", and F = "algo B is faster than algo" A, then P(F|O) = P(O|F) * P(F) / P(O) then... what? There isn't even a clear P(O|F) likelihood without making assumptions about the process' noise. If the measurement is very noisy compared to the gain, then XXXYYY is just dumb luck, and doesn't tell you…

The OP is making some short cuts. 1/(6 choose 3) means that they start with the assumption that every possible ordering is equally likely. If that is the case, then the odds that XXXYYY pops out is 5%. What happens if we change our assumption? Let's assume that XXXYYY is more likely. This would imply that algo B is faster than algo A. If we assume that any of the other (or all of the other) combinations are more likely, then this reduces the odds that XXXYYY would pop out.

This means that either we had it right (algo B is faster than algo A), or the result we saw was at least as unlikely as we predicted. That's what it means to have a "confidence interval".

I'll leave the Bayesian version to someone else because I don't really trust myself to do it.

Re: Estimating the chances of something that hasn’t happened yet

#119

Post by justinpombrio »

pedrosorio wrote: post #117
justinpombrio wrote: post #113

Earlier quoted context omitted.

Let me explain it in a Bayesian way. The Bayesian approach would be to consider a whole bunch of hypotheses about how much better Y does than X (and vice-versa), and a prior distribution over how likely you think each is a-priori. Then for each sample S, you update the probability of each hypothesis H by multiplying its probability by P(S|H), then re-normalize. Well in this case, we're only going to consider two hypo…

“P(XXXYYY|H0) = 1 / 6choose3 = 5%. Wow, that's not a very good update for H0. It's probably just false. For expediency, let's just toss it out.” It only makes sense to toss H0 out if P(XXXYYY|H1) >> 5% (such that the evidence for H1 relative to H0 increases after the observation). You are implicitly assuming that’s the case because “it makes sense”. But as the parent post mentioned, the likelihood is not defined and…

Yes: for that reason and others the whole approach doesn't make much sense from a Bayesian perspective. I was trying to point that out by running with it.

Re: Estimating the chances of something that hasn’t happened yet

#120

Post by sweezyjeezy »

ced wrote: post #107
cperciva wrote: post #28

This reminds me of a different "rule of 3": If you want to compare two things (e.g., "is my new code faster than my old code"), a very simple approach is to measure each three times. If the all three measurements of X are smaller than all three measurements of Y, you have X This works because the probability of the ordering XXXYYY happening by random chance is 1/(6 choose 3) = 1/20 = 5%. It's quite a weak approach --…

Man, I wish I understood frequentist statistics to know if your reasoning makes sense. Bayesianly, if O = "the XXXYYY ordering", and F = "algo B is faster than algo" A, then P(F|O) = P(O|F) * P(F) / P(O) then... what? There isn't even a clear P(O|F) likelihood without making assumptions about the process' noise. If the measurement is very noisy compared to the gain, then XXXYYY is just dumb luck, and doesn't tell you…

> There isn't even a clear P(O|F) likelihood without making assumptions about the process' noise.

Correct. I believe standard procedure would be to assume that time for algo A/B are normally distributed, put non-informative priors on the parameters, then integrate over the space where F is true. I think the non informative prior for a normal distribution is P(mu, sigma^2) \propto 1 / (sigma^2) - it's harder than this, because you know that the runtime of a program is > 0, and maybe you think that sigma is likely to be quite a bit less than mu. If you choose your prior wisely, I suspect you will actually get something close to 1 / 20, the added uncertainty will come from when |mu_A - mu_B| is roughly less than max(sigma_A, sigma_B), but even there, most of it will cancel out.

A normality assumption may be reasonable - if you're assuming that the run-time of the code is dominated by the addition of a bunch of independent operations that are roughly the same timescale, that's what you will get - it will fall down if there is a small number of steps which dominate (e.g. http requests or garbage collection or something). If you don't want to some kind prior with parameters like that, you need to go into non-parametric Bayesian stats, and you'll end up with a lot more uncertainty.

Post reply on HN