3 ms·

Some of the leading challenges in anomaly detection are: (1) Goal. What is the goal? One goal is for near real-time monitoring for health and wellness and, t

by graycat 11y ago

Some of the leading challenges in anomaly detection are: (1) Goal. What is the goal? One goal is for near real-time monitoring for health and wellness and, then, detection ASAP. This goal can be appropriate in monitoring on-line systems, say, server farms, digital communications networks, process plants. For much of medicine, there is more time for detection. (2) Old Data. What is assumed about the input data, that is, the old or historical data? One leading assumption is that the data is a second order stationary stochastic process. Another leading assumption is that the data is independent, identically distributed. (3) Anomalies. There are essentially two important cases about the anomalies. First, we have seen the anomalies before, have some good data characterizing them, and now are just looking for those old anomalies in new data. An example here is looking for signatures of malware. Second, we have not seen the anomalies before and are trying to detect them for the first time, that is, the zero-day case. (4) Real-Time Assumption. If doing real-time monitoring, likely want to assume that the real-time data is probabilistically the same as the old, historical data. (5) False Alarm Rate. Once the context of the work as in (1)-(4) is clear, likely the most important goal is to be able to select a desired false alarm rate and get that rate in practice. (6) Detection Rate. The next major challenge is, for whatever false alarm rate are willing to tolerate, how to get the highest possible detection rate? Of course, we might like to achieve the highest possible detection rate in the sense of the classic Neyman-Pearson result, e.g., in https://news.ycombinator.com/item?id=11440459 https://news.ycombinator.com/item?id=11440459 (7) Nominal versus Interval Data. Another challenge is how to handle data that is nominal (i.e., with just a few values known in advance) or interval, i.e., essentially any real numbers. (8) Multi-Dimensional Data. Another challenge is how to get a higher detection rate by jointly exploiting data on several variables. (9) Distribution-Free. Another challenge is how to handle situations where there is little or no chance of knowing the joint probability distribution of data on several variables. E.g., it is easy to get input data on 20 variables, but getting data enough on 20 variables to have an accurate description of the joint probability distribution stands to be challenging, say, 1000^20 data points or some such. So, can want techniques that are distribution-free, that is, that make no assumptions about probability distributions. Anomaly detection is often close to hypothesis testing in statistics, and that is a large and mature field with a lot of good work.

huac 11y ago
What do you think of approaching anomaly detection as a semi-supervised classification problem?
- graycat 11y ago
  I suggest approaching anomaly detection in ways to get good answers to the nine challenges in my post and any additional important challenges. What you are suggesting may be related to what I suggested in my post https://news.ycombinator.com/item?id=11440459 https://news.ycombinator.com/item?id=11440459 There for the data, both historical and new, we have only some discrete cases and only a few thousand or so of those. And in that example there was data on both healthy and sick. So, we could go fairly directly to the classic Neyman-Pearson result as in the derivations there in that post. But that example was quite special. Classification seems usually to be for only some modest number of discrete cases, "modest" enough that we can get, store, and manipulate data on all the cases in advance (supervised) and before starting to detect anomalies. For data on several variables, the number of cases stands to grow as an exponential in the number of variables, say, as in the 1000^20 for 20 variables in my post above. Another approach is to do some work with nearest neighbors, and for that with some commonly justified assumptions there is a way to set and get a desired false alarm rate and get some good things about detection rate. Again, I see little choice but to see much of anomaly detection as part of statistical hypothesis testing.
  - huac 11y ago
    It seems like a semi-supervised classification framework can address each of those 9 issues. I agree btw that each is important, but would emphasize the importance of understanding collinearity/correlation with multidimensional data. Maybe also consider online updating (adding new data to the old data). I think I phrased my previous comment poorly; in the OP's example, and in a pdf linked elsewhere in this thread (https://news.ycombinator.com/item?id=11623647 https://news.ycombinator.com/item?id=11623647), the anomaly detection problem is of server data. The motivation for finding anomalies is then to prevent server outages/delays, and it's that problem I was considering (rather than simply anomalies, which can be good or bad or just special). My thinking is that under a semi-supervised framework we would take some historical data (where each point in time is associated with n readings of a system), mark known anomalous periods (e.g. if there's an outage detected by some other system), train a classification model based on this previous data, and then attempt to classify new points in time as anomalous or not. I don't make any claims to what kind of classification model; nearest neighbors or logistic regression would surely be fine. With that understanding, I don't follow what you mean by 'modest number of discrete cases' for classification. I follow most of your linked approach, which I'm understanding as similar to a Naive Bayes method (which, incidentally, doesn't appear at face value to deal with your point #7 about continuous data) - it's quite interesting how that eventually ends up intimately connected with the hypo test math. But if we frame the question this way, of having a desired result ('normal' data) and having an undesired result ('anomalous' data), then I don't see how a classification approach wouldn't work.

by graycat 11y ago

huac 11y ago

What do you think of approaching anomaly detection as a semi-supervised classification problem?

graycat 11y ago
I suggest approaching anomaly detection in ways to get good answers to the nine challenges in my post and any additional important challenges. What you are suggesting may be related to what I suggested in my post https://news.ycombinator.com/item?id=11440459 https://news.ycombinator.com/item?id=11440459 There for the data, both historical and new, we have only some discrete cases and only a few thousand or so of those. And in that example there was data on both healthy and sick. So, we could go fairly directly to the classic Neyman-Pearson result as in the derivations there in that post. But that example was quite special. Classification seems usually to be for only some modest number of discrete cases, "modest" enough that we can get, store, and manipulate data on all the cases in advance (supervised) and before starting to detect anomalies. For data on several variables, the number of cases stands to grow as an exponential in the number of variables, say, as in the 1000^20 for 20 variables in my post above. Another approach is to do some work with nearest neighbors, and for that with some commonly justified assumptions there is a way to set and get a desired false alarm rate and get some good things about detection rate. Again, I see little choice but to see much of anomaly detection as part of statistical hypothesis testing.
- huac 11y ago
  It seems like a semi-supervised classification framework can address each of those 9 issues. I agree btw that each is important, but would emphasize the importance of understanding collinearity/correlation with multidimensional data. Maybe also consider online updating (adding new data to the old data). I think I phrased my previous comment poorly; in the OP's example, and in a pdf linked elsewhere in this thread (https://news.ycombinator.com/item?id=11623647 https://news.ycombinator.com/item?id=11623647), the anomaly detection problem is of server data. The motivation for finding anomalies is then to prevent server outages/delays, and it's that problem I was considering (rather than simply anomalies, which can be good or bad or just special). My thinking is that under a semi-supervised framework we would take some historical data (where each point in time is associated with n readings of a system), mark known anomalous periods (e.g. if there's an outage detected by some other system), train a classification model based on this previous data, and then attempt to classify new points in time as anomalous or not. I don't make any claims to what kind of classification model; nearest neighbors or logistic regression would surely be fine. With that understanding, I don't follow what you mean by 'modest number of discrete cases' for classification. I follow most of your linked approach, which I'm understanding as similar to a Naive Bayes method (which, incidentally, doesn't appear at face value to deal with your point #7 about continuous data) - it's quite interesting how that eventually ends up intimately connected with the hypo test math. But if we frame the question this way, of having a desired result ('normal' data) and having an undesired result ('anomalous' data), then I don't see how a classification approach wouldn't work.