Making Sense of Standard Deviation | Hacker News Reader

Making Sense of Standard Deviation

amarsagoo.blogspot.com

32 pointsmotxilo19 comments

A story of my last use of Standard Deviation.

My day to day job deals with credit card processing. A lot of my job deals with ensuring that transactions occur securely and reliably. It's a tedious job, it's not exciting, and involves a lot of testing, but I love the sense of knowing that actual money is flowing through a system I built.

Anyways, one of the things I wanted to do was build an automate alert system that would notify me of problems with processing transactions. Looked at it from high up, the system is fairly stable, and while it would be easy to notice if transactions suddenly stopped on the entire system, this rarely, if ever, actually happens (and hasn't happened except for planned < 1 minute outages).

However, consider the system runs through it many small individual sites, looking at all transactions is fairly useless. Instead, I wanted a warning to notify me when any specific account was suffering. Each account is different, and accounts for a variable number of transactions each day. Some accounts do more, some less. Their are other variables: some accounts do well at different types of the day because of where they are promoted in the world. Weekends generally see an uptick, but this again is variable.

So, I developed a system (using standard deviation) that essentially looked at an accounts history for the past X time period for a certain period of time throughout the day. Some accounts are inspected by looking at the numbers in the past hour (accounts with steady transactions), others are looked at over the last few hours, others are looked at over the day.

Obviously, we don't alert ourselves to certain cases that fall outside standard deviation, and we've adjusted the numbers to look at other areas, but the result of using standard deviation in this way suddenly opened up a new way at looking at our numbers and evaluating the current status of our system, as well as the accounts using it. Even if a problem doesn't exist on our end, we can alert the people that handle these accounts that a problem might exist, allowing them to take necessary action.

Understanding standard deviation, understanding how it can be used (along with other associated tools of math) makes for some really interesting things that you can do to improve your system as a whole.

A similar system was put in place by a pharmacy system to detect employee narcotics abuse. They'd throw an alarm when a pharmacist started dispensing pills at a rate outside their SD.

The system worked great except in the case where a pharmacist slowly ramped up usage as his addiction worsened. Seems like that's a feature that works well in your case. As a business sells more stuff, their transactions will ramp up and your model will still hold.

nice.

That's one of the cases we don't alert ourselves too: getting a lot of transactions is a good thing. =)

In the reverse, however, is another issue entirely. A site that is slowly getting less traffic won't be alerted. However, this is where we have to draw the line. We aren't looking for long term trends. Rather, immediate issues. Basically, if a site that normally has 20 attempted transactions during the last hour suddenly has 0, is this a problem?

There is still a lot of tweaking that needs to go into the system. We're also exploring how to use this in other areas as well. Since all these accounts are internal, it's easy for me to get feedback.

The end goal, however, is to be notified as soon as possible when something occurs that will negatively affect our bottom line.

There's a much more mature way to approach your problem:

What you have is a problem in statistical hypothesis testing.

So, you want to start by stating and assuming a null hypothesis. This hypothesis is for a particular account and assumes that the account is normal, that is, that there is nothing wrong with it, that is, that any problems are null.

With this assumption, you will get a lot of additional information that will let you calculate some probabilities and test the hypothesis.

In this process, there are two ways to be wrong:

(1) False Alarm.

You conclude that there is something wrong with the account when it is normal. A false alarm is also called Type I error. Call the conditional probability of a false alarm given that the account is normal the false alarm rate. Commonly the numerical value is denoted by alpha.

(2) Missed Detection.

You conclude that the account is normal when there is a problem with it. A missed detection is also called Type II error. Call the conditional probability of a missed detection given that there is a problem with the account the missed detection rate. The numerical value is commonly denoted by beta.

Typically you can design a hypothesis test so that alpha is adjustable and known in advance.

Here's how the test calculation goes: Given the data on one user and assuming the null hypothesis, calculate the probability of getting data such as observed or worse. If this probability is really small, then we argue either (1) the account is normal but we observed something very rare or (2) the account has something wrong with it. If the calculated probability is very small, then we reject (2), conclude (1), and raise an alarm.

In more detail, before we do the test, we select a geometric region, the critical region, for the data we will observe. We know that for a normal account, the probability of observing data in the critical region is just alpha. So, we take the data on the user and see if it falls in the critical region. If so, then we raise an alarm. Else we don't. This way we do get false alarm rate alpha. What beta we have for this test, however, is not yet determined; tests vary.

For each false alarm rate alpha, you want the best or most powerful test you can get, that is, the smallest rate of missed detections beta. How to construct such a test is given in general but somewhat abstract terms by the famous Neyman-Pearson lemma. There are elementary proofs in most intermediate texts on mathematical statistics. The best proof I know I wrote out in terms of the Hahn decomposition in measure theory (it is an easy result of the Radon-Nikodym theorem with a famous proof by von Neumann).

In practice, given essentially any calculation at all of the available data, you can estimate the false alarm rate alpha easily enough: Just take some old data on accounts that time, etc., have shown are good, feed that data into your calculation, and see what fraction of the calculations yield alarms.

It is possible to test the detection rate similarly, but the number of bad accounts is typically much smaller meaning that getting a good estimate of the detection rate beta is harder.

In the classic hypothesis tests, one important approach is to assume that we know the probability distribution of our data for accounts that are normal. Then we get to assume this distribution in our null hypothesis.

When we do not assume such a distribution, then our test is distribution-free and, thus, more general.

Another issue is the number of variables in our test: The classic tests commonly used just one variable so that the critical region was, typically, just one or two intervals on the line. But clearly using several variables and, for the critical region, something complicated, even a fractal, in several dimensions can give a more powerful test.

Tests that are both distribution-free and that use several variables are rare.

I developed a large family of such tests.

Your problem is a special case of monitoring in near real time for problems, many or most of which have never been seen before. So, such monitoring can be important for server farms, networks, the financial system, and parts of national security. Once I gave a talk on my techniques at the Institute for Defense Analysis, and several persons in the audience thought of applications to problems such as yours.

There is an intuitive approach: Suppose from the data on a user we get two variables. Suppose the probability density of these two variables for normal accounts looks something like the Shenandoah Mountains. Take the lowest point in the mountains and, then, the volume of the mountains above this level, and call that volume 1. Now pour water into the mountains and have it reach a level. Let this water cover the fraction alpha of the mountains. Let the wet area be our critical region. So, we get the largest critical region we can for the volume alpha we have covered. There is a crude optimality property here; this property can be useful for detecting zero day problem where we have no information on non-normal accounts. As we know from Mandelbrot, lake boundaries are typically fractals. So, our critical region can be a fractal. Does this mean that the mountains are rough? Actually no: It is possible for the mountains to be infinitely differentiable and the lake boundary still a fractal, e.g., the Mandelbrot set. That is, for any closed subset C of R^n, there exists a real value function f: R^n --> [0, infinity) so that f(x) = 0 for x in C and f(x) > 0 otherwise.

But in your case, you have a lot of data on both normal accounts and bad ones. So, you want a means of separating such data. Again, the Neyman-Person lemma is first-cut guidance.

In all of this, standard deviation will likely play little or no role unless somewhere you can justify a Gaussian assumption. However, if you can justify a Gaussian assumption, be aware that sample mean and sample standard deviation are sufficient statistics (more from the Radon-Nikodym theorem) for the Gaussian distribution so that, put simply, your test need use only sample mean and standard deviation.

A small but vital correction is that the "biased" estimator will approach a population's std dev as the sample size increases. This is clear since the adjustment is N/(N-1) which tends to 1 with large N.

It's not often a huge deal, but I'm unconvinced that biased estimators deserve such a derogatory name. Using a unbiased estimate does not actually mean you've got a better estimator. I think this is part of why there seems to be no intuitive description of why the N/(N-1) factor removes bias. You instead need to invoke the powerful, abstract ideas of sufficiency and completeness.

The "intuitive" explanation I've heard is that (N-1) is the number of degrees of freedom of a sample with N data points, so when you divide by (N-1) you're normalizing some valuation of the "spread" of the sample against a measure of the potential for the sample to "spread."

I think how "intuitive" this idea is depends on how well you understand thermodynamics. I, clearly, do not.

I've heard that description before and find it more ad hoc than intuitive. Is there some valid mathematical object K such that often times you will normalize unbiased estimators by N/(N-K)? Is this K sometimes equal to some measure of the number of equations/constraints you have? Does this seem to hold a lot of force in ANOVA especially?

Sure, sure, sure. I still don't see why this normalization is required to make a better estimate (excepting when you define "better" as an unbiased estimator, maybe the MVUE).

This is the problem with frequentist estimators: it's not clear what part is math and what part is subjective guessing.

I'm completely certain that the unbiased estimators are a class of estimators that eliminate bias. I'm completely certain that the MVUE is the one of those with the highest Fisher information subject to the Cramer-Rao bound. Those arguments are abstract, but simple.

I've just never been too sure why I should prefer unbiasedness to minimizing error (or, more generally, minimizing a cost function of some variety).

I've never understood when, theoretically, estimating a 'fixed' parameter is better than pruning it's possible distribution.

But, I've also never doubted statements of frequentist statistics made in full rigor. I don't believe they're guessing, I just think they're playing a game that they made up the rules too but got them tragically wrong.

Frequentist estimators try to estimate an uncertain quantity, but they don't define what the goal is. Is the goal to get as close to the true value as possible on average (i.e. minimize |t-e| where t is the true value and e is the estimator). Is the goal to minimize (t-e)^2? To minimize some other cost function? No, they don't define the goal all they do is define some desirable properties that don't fully specify the problem.

It's like asking a physicist "how do I throw a ball". He can't give a good answer unless you define what your goal is. Is the goal to throw as high as possible? Throw straight up. Is the goal to throw as far as possible? Throw at 45 degrees.

Generally, they seem to begin with (t-e)^2 which they rapidly note the orthogonality decomposition between "bias" and variance. The decomposition appears metaphorically in other error functions as well. This is often mentioned as a supportive point, but I'm not so sure it's meaningful.

Finding minimization of MSE difficult, frequentists choose to minimize bias first. The method of the MVUE produces a low MSE estimator from the class of unbiased estimators and thus, automatically, ignores low variance biased estimators which may or may not outperform the MVUE.

Frankly, though, the bias-variance decomposition seems too widely interpreted, especially as an expectation over all possible data instead of something considering the problem of inference with a known, fixed set of data. The difference here is thus philosophical and hard to mathematically analyze.

I don't have a lot of practical day-to-day use for standard deviation and possess a vague understanding of it. Like the author, I resort to Wikipedia periodically and go away with no stronger an intuitive sense than when I began. I think the author offers a great explanation for the advantages of a more intuitive understanding. This article and its simple graphics definitely provided a more intuitive sense of the concept.

I'll wait a while for the statistics experts to weigh in here before I write it to my cognitive hard disk. :)

I explain it like this:

It's 3rd and 4. You have two running backs. Running back A averages 8 yards a carry with a standard deviation of 6. Running back B averages 5 yards a carry with a standard deviation of half a yard.

Which guy do you choose? If you just look at averages, you probably would choose A. But if you think of the standard deviation as an indication of consistency you choose B, because his 5 yard gains are very consistent, whereas A might bust one for big yards, but he's also likely to get dropped for a loss.

Ahh yes, but it's not that simple. You can also account for the plays these are on - some people crack under pressure. If you just add up the numbers without accounting for other conditions, results can change dramatically.

This isn't to say your example is wrong, but simply to say that all data is not equal and to make sure you use the right data for whatever you're trying to accomplish.

The main reason to use standard deviation instead of mean absolute deviation is that

  sqrt((f(x)-g(x))^2)

is differentiable, while

  |f(x)-g(x)|

is not. Though exaggerating the larger differences is often a desirable property, the ability to do calculus is nearly always a desirable property.

You point out a real problem with the article. The given rationale for (.)^2 vs. |.| is just wacko ("there is obviously more variation in the second data set than the first").

The reason it's mistaken is, there are other examples, typically with just one or a handful of outliers, in which the SD is "obviously" too high compared to mean absolute deviation.

Futhermore, these type of examples are common in practice, so the SD is problematic to use if you have outliers.

Often, in robust statistics, the Median Absolute Deviation (which is conventionally labeled MAD, http://en.wikipedia.org/wiki/Median_absolute_deviation) is used. As an estimate of scale, it's much more robust to outliers. But of course, you can't differentiate it!

The author makes a minor mistake.

You can make an unbiased estimate of the variance using the formula s^2 = (sum of squared deviations) / (N-1). However, taking the square root of this gives you a biased estimate of the standard deviation due to the concavity of sqrt.

http://en.wikipedia.org/wiki/Bessels_correction

Heh. Of course being a non-linear transformation, bias will creep in if you just naively take the non-biased value, but people rarely think about that. Thanks for pointing this out.

(BTW, the link needs an apostrophe: http://en.wikipedia.org/wiki/Bessel%27s_correction )

Can think of standard deviation much like a distance.

So, if have random variables X and Y, if they have finite means and standard deviations, and if we denote standard deviation by Std(X) and variance by Var(X) and set Z = X + Y, then Var(X) = Std(X)^2 and we get the Pythagorean theorem

Var(Z) = Var(X + Y) = Var(X) + Var(Y)

if we can assume that X and Y are uncorrelated which is true if X and Y are independent. So, uncorrelated is analogous to perpendicular in geometry.

Reply on news.ycombinator.com