3 ms·

Outlier Detection Techniques (2010) [pdf]

91 points by olooney 8y ago

graycat 8y ago
The OP has a problem: The algorithms don't give any significant, meaningful results. E.g., can run one of the algorithms, and it can report that there is an outlier or not, and in either case we have no idea if the answer is better than just something from reading tea leafs. For sorting numbers, an algorithm is appropriate, e.g., heap sort, once we have checked the algorithm and shown that actually does sort. For outlier detection, we have no such simple criterion that the algorithm did anything meaningful. For some first progress, we can consider the framework of statistical hypothesis testing with Type I error, Type II error, and the probability of Type I error. If we can do some derivations so that we know the probability of Type I error, then we have a meaningful way to know how seriously to take the result. E.g., suppose we are receiving points one at a time. Our null hypothesis is that the points are independent and have the same distribution. Then Type I error is saying that a point violates the null hypothesis, is an outlier, when it does not. A Type II error is saying that the point does satisfy the null hypothesis when it does not. Generally we want to be able to adjust, set, and know the probability of Type I error. Then we have an outlier technique with some meaning. If in addition, e.g., via the classic Neyman-Pearson result, we can show that for the probability of Type I error we have selected we get the lowest possible probability of Type II error, then we have the best possible test. The OP is too eager to work with a Gaussian assumption. Too commonly in practice, that assumption is absurd. Instead, we should be able to work with a distribution free assumption, that is, the null hypothesis assumes that all the data has the same distribution but we don't know what that distribution is.
- jeroenjanssens 8y ago
  I spent some time thinking about this. See https://github.com/jeroenjanssens/phd-thesis https://github.com/jeroenjanssens/phd-thesis
  - curiousgal 8y ago
    Tangent: that is the most visually pleasing PhD thesis I have ever come across! How did you create it if I may ask?
    - throwawaylolx 8y ago
      It's just a regular LaTeX template.
      - curiousgal 8y ago
        Which one??
  - Rainymood 8y ago
    Humble understatement of the year. What jeroen means is: I wrote my phd thesis about this.
- srean 8y ago
  I have nothing to do with the slide-deck but the statements > The OP has a problem: The algorithms don't give any significant, meaningful results. and > The OP is too eager to work with a Gaussian assumption. demonstrate strong mischaracterization and were supremely superficial. If I may be a little blunt, given your specialization and comment history I have come to expect better. Compared to real estate of the slide deck that was spent on non-parametric methods Gaussian was just a passing mention. This slide-deck is supposed to be a resource to get acquainted with the topic -- not a technical publication. Of course there are no proofs but there's a list of references at the end which I presume do have the proofs. Although I have not personally verified each of them from the description of the techniques in the slides its not that hard to imagine how one can give performance guarantees in a non-parametric setting to many of them -- for example the nearest neighbor based methods are bog standard in this respect.
  - graycat 8y ago
    I saw lots of Gaussian in there and, sorry, missed the sign that said "just a passing mention" :-). From the classic limit theorems, Gaussian is crucial, but expecting real data from complicated situations to be Gaussian is a big stretch. Prof U. Grenander made this point to me in his office in the Division of Applied Mathematics at Brown when I visited -- as Director of Operations Research at FedEx, I'd gone to Lynn, MA to talk to GE about jet engines so took off an afternoon and went down to Providence to see if I wanted to go to Brown for my Ph.D., talked to Infanti, Kushner, Grenander, Fleming, and a few others. Yes, probability distributions exist; generally, though, we can't find them. One of the places we can find some probability distributions is the Poisson process, and, as I posted recently here, there are some qualitative, "axiomatic", criteria and also a limit theorem for justifying a Poisson assumption. So, we can get the distribution of times between arrivals, the distribution of the number of arrivals in, say, one hour, and more. The formulas for combinations and permutations permit knowing some more distributions. Still, tough to assume Gaussian. Sorry, having statistics assume real data, e.g., when looking for outliers, especially for when looking for outliers, is a sore point with me. "Especially" is because even if Gaussian looks good on, i.e., eyeball near, average and standard deviation, or even with a goodness of fit test, looking for outliers will be considering the tails of the Gaussian, and that is just where, with just some real data, we are in a lot of doubt. For getting an hypothesis test from those algorithms will usually mean doing a derivation to find the probability of Type I error, and such a derivation is commonly difficult to not done yet. Sometimes in practice have more information that permits a good estimate of the probability of Type I error, e.g., for some graveyard humor, wait ten years and see how many patients died.
sophistication 8y ago
2010 is pre-deep learning revolution/hype, so these slides are outdated. See e.g. https://arxiv.org/abs/1709.01907 https://arxiv.org/abs/1709.01907 https://arxiv.org/abs/1810.01403 https://arxiv.org/abs/1810.01403
- tw1010 8y ago
  Have you actually tried to implement outlier detection in production on any serious level? Most who do realize pretty quickly that deep learning is way overkill and finicky, and pretty soon head for resources like this.
  - sophistication 8y ago
    The method in the first paper is in production, AFAIK. Also, outdated ≠ obsolete.
lbj 8y ago
Although I'm usually the last to recommend ML/Deeplearning, this seems better solved with nnets.

91 points by olooney 8y ago

The OP has a problem: The algorithms don't give any significant, meaningful results. E.g., can run one of the algorithms, and it can report that there is an outlier or not, and in either case we have no idea if the answer is better than just something from reading tea leafs. For sorting numbers, an algorithm is appropriate, e.g., heap sort, once we have checked the algorithm and shown that actually does sort. For outlier detection, we have no such simple criterion that the algorithm did anything meaningful. For some first progress, we can consider the framework of statistical hypothesis testing with Type I error, Type II error, and the probability of Type I error. If we can do some derivations so that we know the probability of Type I error, then we have a meaningful way to know how seriously to take the result. E.g., suppose we are receiving points one at a time. Our null hypothesis is that the points are independent and have the same distribution. Then Type I error is saying that a point violates the null hypothesis, is an outlier, when it does not. A Type II error is saying that the point does satisfy the null hypothesis when it does not. Generally we want to be able to adjust, set, and know the probability of Type I error. Then we have an outlier technique with some meaning. If in addition, e.g., via the classic Neyman-Pearson result, we can show that for the probability of Type I error we have selected we get the lowest possible probability of Type II error, then we have the best possible test. The OP is too eager to work with a Gaussian assumption. Too commonly in practice, that assumption is absurd. Instead, we should be able to work with a distribution free assumption, that is, the null hypothesis assumes that all the data has the same distribution but we don't know what that distribution is.

jeroenjanssens 8y ago
I spent some time thinking about this. See https://github.com/jeroenjanssens/phd-thesis https://github.com/jeroenjanssens/phd-thesis
- curiousgal 8y ago
  Tangent: that is the most visually pleasing PhD thesis I have ever come across! How did you create it if I may ask?
  - throwawaylolx 8y ago
    It's just a regular LaTeX template.
    - curiousgal 8y ago
      Which one??
- Rainymood 8y ago
  Humble understatement of the year. What jeroen means is: I wrote my phd thesis about this.
srean 8y ago
I have nothing to do with the slide-deck but the statements > The OP has a problem: The algorithms don't give any significant, meaningful results. and > The OP is too eager to work with a Gaussian assumption. demonstrate strong mischaracterization and were supremely superficial. If I may be a little blunt, given your specialization and comment history I have come to expect better. Compared to real estate of the slide deck that was spent on non-parametric methods Gaussian was just a passing mention. This slide-deck is supposed to be a resource to get acquainted with the topic -- not a technical publication. Of course there are no proofs but there's a list of references at the end which I presume do have the proofs. Although I have not personally verified each of them from the description of the techniques in the slides its not that hard to imagine how one can give performance guarantees in a non-parametric setting to many of them -- for example the nearest neighbor based methods are bog standard in this respect.
- graycat 8y ago
  I saw lots of Gaussian in there and, sorry, missed the sign that said "just a passing mention" :-). From the classic limit theorems, Gaussian is crucial, but expecting real data from complicated situations to be Gaussian is a big stretch. Prof U. Grenander made this point to me in his office in the Division of Applied Mathematics at Brown when I visited -- as Director of Operations Research at FedEx, I'd gone to Lynn, MA to talk to GE about jet engines so took off an afternoon and went down to Providence to see if I wanted to go to Brown for my Ph.D., talked to Infanti, Kushner, Grenander, Fleming, and a few others. Yes, probability distributions exist; generally, though, we can't find them. One of the places we can find some probability distributions is the Poisson process, and, as I posted recently here, there are some qualitative, "axiomatic", criteria and also a limit theorem for justifying a Poisson assumption. So, we can get the distribution of times between arrivals, the distribution of the number of arrivals in, say, one hour, and more. The formulas for combinations and permutations permit knowing some more distributions. Still, tough to assume Gaussian. Sorry, having statistics assume real data, e.g., when looking for outliers, especially for when looking for outliers, is a sore point with me. "Especially" is because even if Gaussian looks good on, i.e., eyeball near, average and standard deviation, or even with a goodness of fit test, looking for outliers will be considering the tails of the Gaussian, and that is just where, with just some real data, we are in a lot of doubt. For getting an hypothesis test from those algorithms will usually mean doing a derivation to find the probability of Type I error, and such a derivation is commonly difficult to not done yet. Sometimes in practice have more information that permits a good estimate of the probability of Type I error, e.g., for some graveyard humor, wait ten years and see how many patients died.

sophistication 8y ago

2010 is pre-deep learning revolution/hype, so these slides are outdated. See e.g. https://arxiv.org/abs/1709.01907 https://arxiv.org/abs/1709.01907 https://arxiv.org/abs/1810.01403 https://arxiv.org/abs/1810.01403

tw1010 8y ago
Have you actually tried to implement outlier detection in production on any serious level? Most who do realize pretty quickly that deep learning is way overkill and finicky, and pretty soon head for resources like this.
- sophistication 8y ago
  The method in the first paper is in production, AFAIK. Also, outdated ≠ obsolete.

lbj 8y ago

Although I'm usually the last to recommend ML/Deeplearning, this seems better solved with nnets.