ISTOCK
Researchers at the HSE University AI Research Centre and Faculty of Computer Science have proposed a novel algorithm for detecting structural changes in time series. The method uses a neural network to compare various segments of a series, enabling rapid detection of changes in its behaviour. The results of their work have been presented at the 26th International Conference on Artificial Intelligence and Statistics— AISTATS (A*).
The study was supported by a grant for research centres in the field of AI provided by the Analytical Centre for the Government of the Russian Federation.
Machine learning tasks today often involve processing time series data, ie sequences of data points ordered by the time of observation. The observed data can vary widely in nature, ranging from tracking the number of patients infected with a specific strain of COVID-19, monitoring the vital parameters of patients undergoing post-stroke rehabilitation, and tracking the hourly volume of social media posts on a particular topic to checking readings from seismic activity sensors.
The frequency at which new data from such observations is recorded can also vary significantly. However, they all share a common characteristic: sudden changes in the behaviour of these time series can signal a significant event—such as the onset of a new wave of a pandemic, the need for urgent patient care, or an impending earthquake, among others. Timely detection of these changes can prevent or, at the very least, mitigate undesirable consequences.
The moment when the data no longer conforms to the expected pattern or trend is referred to as a change point. It's worth noting that significant structural changes in the sequence of observations aren't always perceptible to humans. This necessitates the development of automatic methods for their detection.
Detecting a change point has long been a classical problem in mathematical statistics, motivating researchers worldwide to develop effective methods for analysing data and identifying structural changes. One such method, an algorithm for detecting change points in time series, has been developed by HSE Faculty of Computer Science researchers Nikita Puchkin and Valeriia Shcherbakova.
There are several approaches to detecting a change point in a time series. These approaches can be categorised into groups based on the type of structural change that needs to be detected. Some methods focus on changes in average values, while others are designed to spot alterations in trends or data volatility (measuring how much data changes over time). Additionally, there are methods—referred to as nonparametric— that are capable of detecting various change points, which can be particularly useful when the consequences of an event have not yet fully manifested, both the trend and volatility of the time series remain unchanged, but changes occur in other data characteristics. Understanding these methods aids researchers and analysts in accurately detecting change points in data series, enabling them to take appropriate measures.
It has been observed that certain studies introduce nonparametric methods for change point detection without a theoretical assessment of the average detection delay. This raises questions about the reliability of the results. Therefore, researchers at the HSE AI Research Centre set the ambitious objective of developing a method which would be practical while having a solid theoretical justification.
Our algorithm is based on a straightforward concept: once the behaviour of a time series has changed, it should be possible to distinguish between the observations made before and after the change point. We use a neural network for this purpose and optimise its weights to enhance the contrast between the pre- and post-change samples. The method thus proves to be universal, and most importantly, its effectiveness has been mathematically confirmed.
The researchers assessed the algorithm's performance by conducting a series of tests of varying complexity and comparing it with several popular nonparametric methods for change point detection. The tests focused on the frequency of false signals generated by the algorithm and the time it takes for it to detect changes. The algorithm showed promising results in the tests, detecting important events or changes in data on average 30% faster than its known competitors.
IQ
Nikita Puchkin
Research Fellow, International Laboratory of Stochastic Algorithms and High-Dimensional Interference, AI and Digital Science Institute, Faculty of Computer Science, HSE University