A Supervised Sliding Window Approach for Change Point Detection in Multivariate Time Series

Abstract

Dette arbeidet gjennomfører multivariat change point-deteksjon ved hjelp av kunstige nevrale nettverk. Hovedbidraget til denne masteroppgaven var å implementere en sliding vindumetode som evaluerer alle sub-sekvenser av en tidsrekke. Vi hentet inspirasjon fra sukseene i objektgjenkjenning ved bruk av nevrale nettverk, og innså at change point problemet har mange likheter som bilde-klassifiseringsoppgaver. Ved å la sliding vinduer passere over en tidsrekke, kan vi tolke hver sub-sekves som normal, hvis dennne sub-sekvensen ikke har et change point i seg, eller kan vi tolke den som unormal viss den har et change point i seg. Som en konsekvens kunne vi definere change point problemet som et klassifiseringsproblem. Videre brukte vi convolutional nevrale nettverk og long short term memory nettverk som klassifiaksjonsmodeller. Eksperimentene viste at disse to arkitekturene gav like resultater med tanke på presisjon på testsettene våre. Det convolutional nevrale nettverket har dog en fordel over LSTMmodellen ved at den lar oss tolke modellen ved hjelp av sine featuremaps.

Sliding vindutekninkken kan i prinsippet brukes til å detektere hvilken som helst type change point. Vi fokuserte dog på change points i korrelasjon, endringer av mean, endringer av varians og endringer i støyen i en autoregressiv-prosess av orden to. Vi fikk gode resultater på flere syntetiske dataset. Presisjonen av deteksjon var naturligvis avhengig av størrelsen på endringen. Dette betyr at endringen må være over en hvis størrelse for at prosedyren skal kunne detektere den.

Vi dedikerte mesteparten av tiden vår til å studere korrelasjonsendringer. Korrelasjonsendringer er vanskelige signalendringer på den måten at de er underliggende endringer i multivariate signal i kontrast til endringer i mean eller varians som er synlige for det mennesklige øye. Korrelasjonsendringer kan for eksempel tyde på sensor feil i multivariate sensor system eller det kan tyde på regimeendringer i en finansiell setting. Vi gjennomførte et case-study på reell data som inneholdt korrelasjonsendringer. I dette studiet brukte vi en teknikk for å finne tilnærmende labels for det reelle datasettet. Uheldigvis klarte ikke de trente modellene å generealisere til testsettet i dette case-studiet.

Til slutt understreker vi at det neste viktige steget i denne forskningen er å teste metoden på flere reelle datasett, og sammenligne metoden med andre change point-metoder i en online setting. Dette må undersøkes før vi kan bekrefte generaliseringsevnen for denne metoden.

This work consist of multivariate change point detection using artificial neural networks. The main contribution of this thesis was implementing a sliding window strategy that evaluates every sub-sequence of a time series. We drew inspiration from the successes in object detection by the usage of neural networks, and realised that the change point problem shares many similarities with image classification tasks. Change points are the times the probability distribution changes in a time series. By running windows over a time series sequence, we could interpret each sub-sequence as either normal. i.e there was no change point in this sub-sequence, or we could interpret a window as abnormal if there was a change point in this sub-sequence. As a consequence we could formulate the change point problem as a classification problem. For the classification models, we used convoultional neural networks and the long-short term memory (LSTM) model. We obtained very similar results of these two models in terms of precision. But the convolutional neural network hold an advantage over LSTM in terms of model interpretation, through its feature maps.

The sliding window technique can in principle be applied to any type of change point. We focused however on changes in correlation, changes in mean, variance and noise changes in an AR(2)-process in this thesis. We were able to show several good results on synthetic data. The detection precision is however naturally dependent of the magnitude of the change. This means that the magnitude of the change must be over a given threshold for it to be detected by this procedure.

We dedicated most of our time to study correlation changes. Correlation changes are difficult signal changes in the sense that they are underlying changes between in a multivariate signal. In contrast to other usual signal changes such as a level change or a change in volatility, which are visually detectable. Correlation changes can for example indicate sensor failures in multivariate sensor systems, or it could indicate regime changes in a financial setting. We included one case study on real data with respect to detecting correlation changes. This case study included an technique to construct approximated labels for the data set, as there are not any obvious good alternatives to label a data set with respect to correlation changes. Unfortunately the trained models were not able to generalise to the test set for this case study.

We emphasise that next crucial steps is to apply the developed approach on several real data sets, and to benchmark against other online change point models. This must be done in order to confirm the generalisation abilities of this approach.