Nonparametrics

What Hacker News says

1. graycatOct 2015
   Okay, PG has an hypothesis test.

   There's a large literature for that, e.g.,

   E. L. Lehmann, Testing Statistical Hypotheses.

   E. L. Lehmann, Nonparametrics: Statistical Methods Based on Ranks.

   Sidney Siegel, Nonparametric Statistics for the Behavioral Sciences.

   In this case, PG will be more interested in the non-parametric case, i.e., distribution-free where we make no assumptions about probability distributions.

   We start an hypothesis test with an hypothesis, commonly called the null hypothesis which is an assumption that there is no effect or, in PG's case, no bias. Then with that assumption, we are able to do some probability calculations.

   Then we look at the real data and calculate the probability of, say, the evidence of bias being as large as we observed. If that probability is small, say, less than 1%, then we reject the null hypothesis, that is, reject the assumption of no bias, and conclude that the null hypothesis is false and that there is bias. The role of the assumption about the sample is so that we know that the problem is bias and not something about the sample.

   In hypothesis testing, about all that matters are just two numbers -- the probability of Type I error and that of Type II error. We want both probabilities to be as low as possible.

   Type I Error: We reject the null hypothesis when it is true, e.g., we conclude bias when there is none.

   Type II Error: We fail to reject (i.e., we accept) the null hypothesis when it is false.

   When looking for bias, Type I error can be called a false alarm of bias, and Type II error can be called a missed detection of bias.

   In PGs case, suppose we have 100 startups and five of those have women founders. Suppose for each of the startups we have the data from "their subsequent performance is measured".

   Our null hypothesis is that the expected performance of the women is the same as that of the men.

   So, let's find those two averages and take the difference, say, the average of the women less the average of the men.

   PG says if this difference is positive, then there was bias, but PG has not given us any estimate of the probability of Type I error, that is, of the probability (or rate) of a false alarm.

   I mean we don't want to get First Round Capital in trouble with Betty Friedan, Gloria Steinem, Marissa Mayer, Sheryl Sandberg, Hillary Clinton, Ivanka Trump, or Lady Gaga unjustly! :-).

   Let's call this difference our test statistic.

   So, let's find the probability of a false alarm:

   So, let's put all 100 measurements in a pot, stir the pot vigorously (we can use a computer for this), pull out five numbers and average, pull out the other 95 numbers and average, take the difference in the two averages, that of the five less that of the 95, and do this, say, 1000 times. Ah, computers are cheap; let's be generous and do this 10,000 times.

   For a random number, how about starting with a 32 bit integer, with appropriately long precision arithmetic multiply by 5^15, add 1, take modulo 2^47, and scale as we want?

   So, we get an empirical distribution of these differences, from the five less the 95. Looking at the distribution, we see what the probability is of getting a difference as high or high or higher than our test statistic. If that probability is low, say, 1% or less, then we reject the null hypothesis of no bias and conclude bias with our estimate of probability of Type I error 1% or less.

   If with the 1% we reject, then it looks like First Round has done a transgression, will get retribution from Betty, et al., and needs to seek redemption and Betty, et al., are happy to have their suspicions confirmed. Else First Round looks like the good guys, are "certified statistically fair to women", may get more deal flow from women, and Betty, et al., can be happy that First Round is so nice!

   Notice that either way Betty, et al., are "happy". That's called "happy women, happy life"! Or, heads, the women win, tails they lose, and in no event is there a huge crowd of angry women in front of First Round's offices with a bonfire of lingerie screaming "bias"!

   When we reject the null hypothesis, we want to know that the reason was men versus women and not something else, e.g., a biased sample. So here is where we use our assumption of independence with the same mean.

   Now we have a handle on Type I error.

   Here we have done a non-parametric statistical hypothesis test, i.e., have made no assumptions, except the means, about the distributions of the male/female CEO performance measurements.

   And we can select our desired false alarm rate in advance and get that rate almost exactly.

   For Type II error, that is more difficult.

   Bottom line, what we really want is, for whatever rate of false alarms we are willing to tolerate, the lowest rate of missed detections we can get.

   Can we do that? With enough more data, yup. There is a classic result due to J. Neyman (long at Berkeley) and K. Pearson (early in statistics) that shows how.

   How? Regard false alarm rate as money and think of investing in SF real estate. We put our money done on the opportunities with highest expected ROI until we have spent all our money. Done. For details, an unusually general proof can follow from the Hahn decomposition from the Radon-Nikodym theorem in measure theory, e.g., Rudin, Real and Complex Analysis. Right, in the discrete case, we have a knapsack problem, known to be in NP-complete.

   What we have done with our pot stirring is called resampling, and for more such look for B. Efron, long at Yale, and P. Diaconis, once at Harvard, now long at Stanford.

   Tom, with a reputation as a hacker, likes to work late, say, till 2 AM. So, we look at the intrusion alerts each minute between 2 AM and 3 AM (something like the performance of the women) and compare with those of the other minutes of 24 hours (like the performance of the men) much as above and ask if Tom is trying to hack the servers.

   Or, we have a server farm and/or a network, and we want to detect problems never seen before, e.g., zero day problems. So, we have no data at all on the problems we are trying to detect because we have never seen any of those before.

   So, to do a good job, let's pick some system we want to monitor and for that system, get data on, say, each of 10 variables at, say, 20 times a second. Now what?

   Our work with bias in women venture applications used just one number for our measurement and test statistic. So we were uni-dimensional. Here we have 10 numbers and need to be multi-dimensional.

   Well, in principle we should be able to do much better (pair of Type I and Type II error rates) with 10 numbers than just one. The usual ways will require us to have, with our null hypothesis, the probability distribution of the 10 numbers, but can only get something like that from smoking funny stuff -- not even big data is that big.

   So, we want to need no assumptions about distribution, that is, be distribution-free.

   So, we want some statistical a hypothesis test that is both multi-dimensional and distribution free.

   Can we do that? Yup.

   "You mean you can select false alarm rate in advance and get that rate essentially exactly, as in PG's bias example?" Yup.

   "Could that be used in a real server farm or network to detect zero day problems -- security, performance, hard/software failures, system management errors?" Yup -- just what it was invented for.

   "Attempted credit card fraud?" Ah, once a guy in an audience thought so!

   How? Ah, sadly there is no more room in this post!

   What else might we do with hypothesis tests? Well, look around at, right, big data or just small data.

   Do we have a case of big data analytics or artificial intelligence (AI)?

   Ah, I've given a sweetheart outline of statistical hypothesis testing, and now you are suggesting some things really low grade? Where did I go wrong to deserve such an insult?

   Show morethread
2. graycatAug 2015
   Sure, but we should take that off-line.

   What is just crucial, really, what it's all about, that is, where the value is, necessarily, inescapably is just in the two rates, the false alarm rate and the detection rate. If can't say at least good things about false alarm rate, then have a definite maybe.

   The OP struggled with the false alarm rate -- my work solved that problem.

   Really, essentially inescapably and necessarily, the core of the work has to be a statistical hypothesis test.

   So, what is that? We make an assumption, typically, that the system we are monitoring is healthy. Commonly that assumption is called the null hypothesis, that is, null in the sense of nothing wrong.

   That assumption leads to some mathematical assumptions that can be used as hypotheses in some theorems with proofs.

   Then, that assumption with some real data let's us calculate the probability of getting data like we just observed.

   If that probability is relatively small, then we have (A) the system is healthy and we just observed something quite rare or (B) the system is sick. If the probability is really small and/or the health of the system is really important, then we guess that case (A) is too rare to be believed, we reject the assumption, the null hypothesis, and conclude (B) that the system is sick.

   That's a short description of statistical hypothesis testing for 100+ years a main pillar of pure and applied statistics and a lot in science, both social and physical.

   But for monitoring computer server farms, this context very much need the test to be both multidimensional and distribution-free. The world wide collection of those was from tiny down to zero -- likely and apparently zero. So, I invented a nice, large collection of them.

   The core of the work was really some novel derivations, right, with theorems and proofs, in, call it, applied probability.

   Then I worked out some algorithms to make the computing fast.

   The work is likely and apparently the best approach to do zero day monitoring for health and wellness in high end server farms and networks. And there may be some other applications.

   Zero day is the case where we are looking for problems never seen before. So, it's sometimes called behavioral monitoring.

   Sure, should monitor for all problems have seen before, and there we should be able to do relatively well on the two rates. But, after those old problems, we still need to look for new ones -- sorry 'bout that.

   I did this work a long time ago and presented it, or put it in front of, a lot of people, but no one was much interested.

   From time to time, people have, as in the OP, rediscovered the problem and done this and that with it. E.g., there was a project of profs Fox and Patterson at Stanford and Berkeley funded by Google, Microsoft, and Sun and in part considered monitoring -- looking at their work, I thought that mine was better.

   Sure, there was

   http://www.sans.org/resources/idfaq/behavior_based.php

   where it was claimed that behavioral monitoring had high false alarm rates. Nope -- my work doesn't! Instead, with my work, get to select false alarm rates over a wide range, including quite small.

   I have another project, and for it I recently completed writing the version 1.0 software -- 18,000 programming language statements in 80,000 lines of text (with comments, blank lines, etc). I want to go live ASAP. This project is much easier for people to like! E.g., don't have to get people interested in rates of false alarms and detections. If the project grows, then I will implement and deploy my anomaly detection ideas for my server farm.

   Otherwise, for now, I'm no longer interested in that anomaly work mostly because no one else is. Others are welcome, from time to time, to rediscover the problem, struggle with false alarm rate, see no good, general results on detection rate, etc., think that the key is artificial intelligence or machine learning or some such (I didn't use either), etc. Uh, it's statistical hypothesis testing, guys. Sorry 'bout that.

   For more, see, say some of the classics:

   E. L. Lehmann, Testing Statistical Hypotheses.

   E. L. Lehmann, Nonparametrics: Statistical Methods Based on Ranks.

   Sidney Siegel, Nonparametric Statistics for the Behavioral Sciences.

   Once I presented my work to Cisco. Their reaction was that my work was "just statistical". Well, what the heck do you expect? Want something deterministic, 0 or 1, for healthy or sick? Do you realize what the heck you are asking for?

   Another time I presented the work and the reaction was, "What we really want is diagnosis." Gads. You are Sony -- or some other big organization, take your pick from various headlines from current to going way back -- and your server farm is under attack with gigabytes or terabytes on the way out the door to hackers, your whole company is at risk of going belly up, and you don't want to know that there's a serious problem until you can also be told just what the heck to do about it? Sure that's your view?

   Gee, you don't want to know that your car's about out of gas unless you are also told that you can get more gas right away? Ever drive in rural Montana? Like long walks? What about engine oil pressure or coolant temperature -- don't want to know about those, either? Or your blood pressure? Not until can be told just what to do about it? Sure about that?

   It's an important problem. I did the work. It's good work. But if people are not much interested, then so be it -- I'm not into pushing big rocks up long hills for no good reason.

   Suspicion: A guy has a sore on his foot. He knows it's there. It hurts. But he lives with it. He's tried this and that, but he still has the sore. Someone has a good cure, but he is so used to putting up with the sore that he ignores the good solution. Besides, he didn't see a way to cure the sore so doesn't believe that anyone else could either.

   Even worse, my solution is not really computer science but is, really, some applied math, actually applied probability, and such work, especially new such work, is rare in practice.

   More generally, good, new stuff is rare, so rare that people are very reluctant to consider that they should pay any attention to it.

   Fine: Let them live with a sore foot.

   Show morethread
3. graycatMay 2013
   In the OP, the

   > The "bug" here was not a software bug, or even a bad configuration: it was the unexpected interaction between two very different (and independently-maintained) software systems leading to a new mode of resource exhaustion.

   can be viewed as pointing to the solution:

   Broadly in computing, we have 'resource limits' from the largest integer that can be stored in 2's complement in 32 bits to disk partition size, maximum single file size, number of IP ports, etc. Mostly we don't pay really careful attention all of these resource limits.

   Well, for 'systems' such as are being considered in the OP, do consider the resource limits. So, for each such limit, have some software track its usage and then report the usage and especially when usage of that resource is close to be exhausted. And when the resource is exhausted, then report that the problem was the resource was exhausted and who the users of that resource were.

   For a little more, can make some progress by doing simulations of 'networks of queues' with whatever stochastic processes want to assume for 'work arrival time' and 'work service times'.

   For more, do some real time system monitoring. For problems that are well understood and/or have been seen before, e.g., running out of a critical resource, just monitor for the well understood aspects of the problem.

   Then there are problems never seen before and not yet well understood. Here monitoring is essentially forced to be a continually applied 'statistical hypothesis test' for the 'health and wellness' of the system complete with rates of 'false positives' (false alarms) and rates of 'false negatives' (missed detections of real problems).

   For the operational definition of 'healthy and well', collect some operational data, let it 'age' until other evidence indicates that the system was 'healthy and well' during that time, and, then, use that data as the definition. Then decree and declare that any data 'too far' from the healthy and well data indicates 'sick'.

   Then as usual in statistical hypothesis testing, want to know the false alarm rate in advance and want to be able to adjust it. And if get a 'detection', that is, reject the 'null hypothesis' that the system is healthy and well, then want to know the lowest false alarm rate at which the particular data observed in real time would still be a 'detection' and use that false alarm rate as a measure of the 'seriousness' of the detection.

   If make some relatively weak probabilistic assumptions about the data, then, in calculating the false alarm rate, can get some probabilistically 'exchangeable' data. Then get to apply some group theory (from abstract algebra) and borrow a little from classic ergodic theory to calculate false alarm rate. And can use a classic result in measure theory by S. Ulam, that the French probabilist LeCam nicely called 'tightness', to show that the hypothesis test is not 'trivial'. See Billingsly 'Convergence of Probability Measures'.

   Of course, the 'most powerful' test for each given false alarm rate is from the Neyman-Pearson lemma (the elementary proofs are not much fun, but there is a nice proof starting with the Hahn decomposition, a fast result from the Radon-Nikodym theorem), but for problems never seen before we do not have data enough to use that result.

   For the statistical hypothesis test, we need two special properties: (1) Especially for monitoring systems, especially complex or distributed systems, we should have statistical hypothesis tests that are multi-dimensional (multi-variate); that is, if we are monitoring once a second, then each second we should get data on each of a certain n variables for some positive integer n. So, we are working with n variables. (2) As U. Grenander at Brown U. observed long ago, operational data from computer systems is probabilistically, certainly in distribution, quite different from data from most of the history of statistics. He was correct. Especially since we are interested in data on several variables, we have no real hope of knowing the distribution of the data even when the system is 'healthy and well' and still less hope when it is sick with a problem we have never seen before. So, we need hypothesis tests that are 'distribution-free', that is, make no assumptions about probability distributions. So, we are faced with calculating false alarm rates for multi-dimensional data where we know nothing about the probability distribution.

   There is a long history of hypothesis tests for from a single variable, including many tests that are distribution-free. See old books by S. Siegel, 'Nonparametric Statistics for the Behavioral Sciences' or E. Lehmann, 'Nonparametrics'.

   For multi-dimensional hypothesis tests, there's not much and still less when also distribution-free.

   Why multi-dimensional? Because for the two interacting systems in the example in the OP, we guess that to detect the problem we would want data from both systems. More generally in a large server farm or network, we are awash in variables on which we can collect data at rates from thousands of points per second down to a point each few seconds. So, for n dimensions, n can easily be dozens, hundreds, ....

   For such tests, look at "anomaly detector" in 'Information Sciences' in, as I recall, 1999.

   If want to implement such a test, might want to read about k-D trees in, say, Sedgewick. Then think about backtracking in the tree, depth-first, and accumulating some cutting planes.

   For monitoring, there was long some work by Profs Patterson and Fox at Stanford and Berkelely, in their RAD Lab, funded by Google, Microsoft, and Sun. The paper in 'Information Sciences' seems to be ahead.

   More can be done. E.g., consider the Rocky Mountains and assume that they are porous to water. Let the mountains be the probability distribution of two-variable data when the system is healthy and well. Now pour in water until, say, the lowest 1% of the probability mass has been covered. Now the test is, observe a point in the water and raise an alarm. Now the false alarm rate is 1%. And the area of false alarms is the largest we can make it for being 1% (a rough surrogate for the best detection rate -- with a fast use of Fubini's theorem in measure theory, can say more here). As we know, lakes can have fractal boundaries, and the techniques in the paper will, indeed, approximate those. Also the techniques do not require that all the lakes be connnected. And for the dry land, it need not all be connected either and might be in islands. So, it is quite general.

   But may want to assume that the region of healthy and well performance is a convex set and try again. If this assumption is correct, then for a given false alarm rate will get a higher detection rate, that is, a more 'powerful' test.

   Still more can be done. But, really, the work is essentially some applied math with, at times, some moderately advanced prerequisites from pure and applied math. Theme: The crucial content of the most powerful future of computing is in math, not computer science. Sorry 'bout that!

   Show morethread
4. graycatDec 2024
   > gap?

   E. L. Lehmann, 'Nonparametrics: Statistical Methods Based on Ranks', ISBN 0-8162-4994-6, Holden-Day, San Francisco, 1975.

   Sidney Siegel, 'Nonparametric Statistics for the Behavioral Sciences', McGraw-Hill, New York, 1956.

   Bradley Efron, 'The Jackknife, the Bootstrap, and Other Resampling Plans', ISBN 0-89871-179-7, SIAM, Philadelphia, 1982.

   Hypothesis testing?? Somewhere maybe I still have my little paper I wrote on using the Hahn decomposition and the Radon-Nikodym theorem to give a relatively general proof of the Neyman-Pearson theorem about the most powerful hypothesis test.

   Show morethread
5. graycatNov 2019
   The world is awash in texts and papers on applied statistics. My notes were an introduction to provide a start on what is needed to read more in applied statistics.

   For much of engineering, e.g., quality control, the statistical hypothesis testing I outlined is common.

   There are now classic texts on hypothesis testing:

   E. L. Lehmann, Testing Statistical Hypotheses, John Wiley, New York, 1959.

   E. L. Lehmann, Nonparametrics: Statistical Methods Based on Ranks, ISBN 0-8162-4994-6, Holden-Day, San Francisco, 1975.

   Sidney Siegel, Nonparametric Statistics for the Behavioral Sciences, McGraw-Hill, New York, 1956.

   The last is also just hypothesis testing; apparently the book is still referenced.

   From some statistical consultants inside GE, there is

   Gerald J. Hahn and Samuel S. Shapiro, Statistical Models in Engineering, John Wiley & Sons, New York, 1967.

   For machine learning, so far the approach appears to be cases of empirical curve fitting.

   The linear case of versions of regression analysis remain of interest. There the matrix theory I outlined is central. And regression analysis goes way back, 100 or so years, and is awash in uses of statistical hypothesis tests for the regression (F-ratio), individual coefficients, (t-tests), and confidence intervals on predicted values.

   For using probabilistic and statistical methods in the non-linear fitting, that is more advanced and likely an active field of research.

   In my own work, I use and/or create new statistical methods when and as I need them. My current work has some original work in, really, applied probability that also can be considered statistics. And when I was doing AI at IBM, I created some new mathematical statistics hypothesis tests to improve on what we were doing in AI. Later I published the work. Parts of the machine learning community might call that paper a case of supervised learning, but the paper is theorems and proofs in applied probability that give results on false alarm rates and detection rates, that is, statistical hypothesis tests (both multi-dimensional and distribution-free). So, that paper can be regarded as relevant to machine learning, but the prerequisites are a ugrad pure math major, about two years of graduate pure math with measure theory and functional analysis, a course in what Leo Breiman called graduate probability, and some work in stochastic processes. At one point I use a classic result of S. Ulam that the French probabilist Le Cam called tightness -- there is a nice presentation in

   Patrick Billingsley, Convergence of Probability Measures, John Wiley and Sons, New York, 1968.

   The work was for anomaly detection in complex systems so could be regarded as for both engineering and machine learning. But I can't give all the background here.

   Show morethread
6. graycatApr 2018
   Nice!

   Yup. Thanks.

   > known as the empirical distribution

   Yup, and I wrote:

   "out in a tail of the empirical distribution"

   Yup, "rank" tests, "permutation" tests: With my TeX markup:

   E.\ L.\ Lehmann, {\it Nonparametrics: Statistical Methods Based on Ranks,\/}

   And, yup, again with my TeX markup,

   Bradley Efron, {\it The Jackknife, the Bootstrap, and Other Resampling Plans,\/}

   Last time I knew, Roger Wets was at UCSD. He read one of my papers and suggested JOTA where I did publish it!

   Show morethread