Anomaly detection is the problem of identifying periods in time when data deviate from their regular patterns. In numerous contexts, such as systems tracking a patientʼs clinical data, identifying such anomalies is crucial for ensuring safety, enhancing efficiency, and enabling informed decisions. With the increasing prevalence of data arriving in the form of streams, there is an urgent need to develop algorithms capable of detecting anomalous behavior in data that arrive continuously over time. A central objective of this project is to develop trustworthy and transparent algorithms for real-time anomaly detection, backed by mathematically provable guarantees of their ability to reliably detect anomalous behavior.
An important aspect of the algorithms to be developed will be a strong focus on computational efficiency. Unlike algorithms designed for retrospective analysis, real-time anomaly detection algorithms must operate within tight computational limits. Since streaming data arrive at a potentially fast pace, algorithms need to process new data points with exceptional efficiency. A critical building block of this project's new and fast algorithms is the use of a grid- based search for anomalies. This new approach allows for the construction of very fast algorithms with strong mathematical guarantees regarding their performance.
In collaboration with industrial partners, the project will conduct case studies to apply its new algorithms across various real-world domains. In particular, the project intends to apply the new algorithms to monitor AI and machine learning systems for anomalous behavior. As anomalous behavior within AI systems may indicate degradation, drift, erratic or biased in- or outputs, our ambition is that our algorithms will enhance such systemsʼ trustworthiness.
As an illustration, a very basic online anomaly detection problem is given in the animation below, in which we observe a single data sequence over time. In the animation, we see the real-time output of an online anomaly detector based on the traditional CUSUM statistic. At the offset, the data behave normally (labeled black) and fluctuate around zero. However, between time 40 and 70, the underlying mean of the data deviates from zero, constituting an anomalous state. After seeing sufficiently many of the anomalous data points, the algorithm raises an alarm and backtracks when the anomalous period started, labeling these points red. A short time after the data return to their normal state again, the algorithm raises a new alarm to indicate that the anomalous state has ended, and backtracks the time normality was restored. The data that follow are then labeled black again. At time 130, a new anomalous period is detected, this time being shorter in duration. In the animation, the blue lines show the running average of the data since the previous change in state.
Naturally, real-world settings are fare more complex than the basic illustration above. For example, there is often multiple streams under observation. The next animation below illustrates the more challenging setting where anomalous behavior may manifest in only an unknown subset of the series. In the animation, we see the real-time output of a multivariate online anomaly detector based on aggregated CUSUM statistics. The first detected anomalous period only manifests in the second second and third series. The second anomalous period, however, is made out of small and subtle deviations in mean in all the series.
Still, even this second illustration is only an idealized illustrative example. In real-world settings, anomalous behavior may manifest itself in much more subtle ways than above, for instance by affecting the variability of the data, their interdependencies between different series, or in more complex statistical properties. Moreover, the number of streams may be exceedingly high, running into the thousands or much more, and the baseline behavior of the data may also drift over time. The SODA project aims to tackle all of these issues.
