Anomalie-Erkennung in Zeitserien - Projekt dampf Teil 1

Wir, das ist in diesem Fall das Team des Projekts dampf bestehend aus aaron Weißler-Krux, max Quintel, patrick Eichhorn und felix Exel, die wir alle im Rahmen unserer Studien für Pflicht-Praktika bei der Novatec waren.
Da das Herzstück des Projekts, ohne das sonst gar nichts funktionieren würde, die Anomalie-Erkennung im Hintergrund ist, die ungewöhnliche Vorkommnisse in den in Zeitserien gesammelten Monitoring-Daten findet, möchten wir unsere Reihe mit diesem Thema beginnen.

Traditionelle Verfahren zur Anomalie-Erkennung

Allgemein geht es bei der Anomalie-Erkennung in Zeitserien darum, ungewöhnliche Werte innerhalb der Zeitserien zu erkennen und zu melden. In unserem Themenbereich könnte zum Beispiel eine CPU-Auslastung einer Java-Anwendung betrachtet werden, die normalerweise konstant zwischen 20% und 30% liegt, aber dann plötzlich auf 100% schießt. Hier ist wohl irgendetwas passiert, das eigentlich nicht passieren sollte, die gesamte CPU auslastet und somit die Performance für andere Services, die auf demselben Host laufen, einschränken könnte.
So ein Sprung würde einem natürlich sofort bei eigener Betrachtung eines Graphen, der die Entwicklung der Zeitserie abbildet, auffallen. Aber zum einen kann es auch unauffälligere Probleme geben, die einem Algorithmus eher als einem Menschen auffallen, und zum anderen kann man bei der schieren Menge an Metriken, über die Daten gesammelt werden, gar nicht jede einzelne ständig selbst betrachten. Man braucht irgendeine Form von automatisierter Anomalie-Erkennung.

Eine aufgrund ihrer simplen Funktionsweise relativ häufig verwendete Form sind dabei Grenzwerte. Für das genannte Beispiel einer plötzlich stark ansteigenden CPU-Auslastung, die normalerweise immer zwischen zwei Werten schwankt, wäre das auch vollkommen ausreichend.
Allerdings hat man selbst da das Problem, dass man zumindest einmal für jede Metrik die Grenzwerte von Hand festlegen und diese dann immer wieder aktualisieren muss, falls sich die Grenzen aus irgendwelchen Gründen verschieben. Außerdem kommt man mit Grenzwerten bei einer vor allem im Zusammenhang mit dem Monitoring größerer Anwendungen häufig auftretenden Art von Anomalien nicht weiter, bei sogenannten kontextuellen Anomalien.

Bei kontextuellen Anomalien kann man nicht nur anhand des tatsächlichen Wertes der Metrik bestimmen, ob der Wert normal ist oder es sich um eine Anomalie handelt, sondern muss dazu auch noch den Kontext betrachten, in unserem Fall zum Beispiel die Zeit.
Wenn unsere überwachte Anwendung beispielsweise die Website eines deutschen Unternehmens ist und die überwachte Metrik die Zugriffsrate pro Sekunde, kann es sein, dass nachmittags um 15 Uhr eine Rate von 2000 Zugriffen pro Sekunde völlig normal ist, um 2 Uhr nachts allerdings quasi unmöglich. Heißt, nur mit dem Kontext der Uhrzeit kann man bestimmen, ob es sich bei dem Wert 2000 nun um eine Anomalie oder einen ganz gewöhnlichen Wert handelt.
Ein anderer Kontext können auch die vorhergegangenen Werte sein. Wenn beispielsweise die vorhergegangenen zehn Werte der Metrik CPU-Auslastung alle bei 100% lagen, ist es relativ normal, dass auch der aktuelle Wert bei 100% liegt. Sind allerdings die vorhergegangenen zehn Werte alle zwischen 10% und 15%, ist ein plötzlicher Anstieg auf 100% vermutlich mit irgendeinem Fehler verbunden.

Darstellung der beschriebenen Beispiel-Besucher-Zahlen einer Website

Ein Grenzwert beachtet weder die eine noch die andere Art von Kontext. Für den zeitlichen Kontext könnte man zumindest noch verschiedene Grenzwerte für verschiedene Uhrzeiten festlegen, was allerdings wieder deutlich mehr Arbeit bedeuten würde.
Letztendlich muss man bei Grenzwerten in den meisten Fällen mit False Positives (es wird eine Warnung ausgegeben, obwohl gar nichts passiert ist) und False Negatives (es wird keine Warnung ausgegeben, obwohl etwas passiert ist) leben. Um False Positives und Negatives sowie die Arbeit, Grenzwerte mit Kontextdaten für jede einzelne Metrik anzupassen und regelmäßig zu aktualisieren, zu reduzieren, braucht man eine andere, intelligentere Lösung.

Anomalie-Erkennung mit Neuronalen Netzen

In unserem Falle heißt diese Lösung aufgrund einer wichtigen Eigenschaft unserer Daten eindeutig neuronale Netze. In unseren Daten gibt es nämlich direkte Abhängigkeiten zwischen Metriken, sodass wir, um eine Metrik zu beurteilen, die Werte von anderen Metriken als Kontext verwenden können. Solch eine Flexibilität der Input-Daten bieten nur selbst geschriebene neuronale Netze und keiner der anderen bei unseren Recherchen gefundenen Algorithmen, die stattdessen meist für zweidimensionale Daten (Werte der beurteilten Metrik und Zeit) ausgelegt sind. Falls ihr noch nie von neuronalen Netzen gehört habt, empfehle ich euch als ersten kurzen Einstieg das Video und den dazugehörigen Blogpost Explained in a Minute: Neural Networks.

Zur Anomalie-Erkennung in Zeitserien mit neuronalen Netzen gibt es im Wesentlichen drei weitverbreitete unüberwachte Ansätze, also Ansätze, bei denen man keine gelabelten Daten, in denen alle Werte als normal oder anomal gelabelt sind, braucht. Diese bauen allesamt auf dem Prinzip der Long-Short-Term-Memory, kurz LSTM, auf. Falls euch das kein Begriff sein sollte und ihr gerne mehr darüber lernen möchten, können wir euch folgenden Beitrag hier im Blog ans Herz legen: Recurrent Neural Networks for time series forecasting. Für uns reicht allerdings auch eine kurze, etwas vereinfachte Erklärung: ein LSTM kann mit Sequenzen von Werten umgehen und kann somit sequentielle, kurz- und langfristige Abhängigkeiten in seine Entscheidungsfindung mit einbeziehen. Besonders beliebt ist deren Anwendung neben Zeitserien auch in der Verarbeitung von Sprache, da die Worte innerhalb eines Satzes oder auch die Sätze innerhalb eines Textes schließlich auch sequentiell voneinander abhängen.

Autoencoder

Das erste der von uns betrachteten Verfahren nennt sich Autoencoder. Bei einem Autoencoder geht es darum, einen n-dimensionalen Vektor auf m < n Dimensionen zu reduzieren, genannt Encoding, und dann aus dem so entstandenen m-dimensionalen Vektor den Ausgangsvektor wiederherzustellen, genannt Decoding. Das Netz soll dabei die Differenz zwischen dem ursprünglichen Input und dem wiederhergestellten Input soweit wie möglich verringern. Es muss also Eigenschaften des ursprünglichen Inputs finden, die es in weniger Dimensionen darstellen kann, um daraus alle nötigen Informationen für die Wiederherstellung ableiten zu können.

Schema eines Autoencoders

Die Encodierung läuft bei uns mit Hilfe eines Many-to-One LSTMs ab, das die Eigenschaften einer Sequenz von Vektoren, z.B. die Werte unserer überprüften Metrik A und zweier Metriken, von denen Metrik A abhängt, jeweils von 15:00 Uhr, 15:01 Uhr, …, bis 15:20 Uhr, in nur einem einzelnen Vektor zusammenfasst. Das Decoding verwendet wiederum ein One-to-Many LSTM, bei dem aus diesem einen Encoding-Vektor wieder eine Sequenz von Vektoren erzeugt wird.

Für die Anomalie-Erkennung wird dieses Verfahren dann folgendermaßen eingesetzt: Man gibt als Trainingsdaten möglichst vor allem Daten ohne Anomalien ins Netz. Das Netz lernt so normale Daten gut zu encodieren und zu decodieren. Wenn man dann einen ungewöhnlichen Wert in das Netz gibt, wird das Netz diesen nicht gut encodieren und decodieren, sodass der Fehler zwischen Input und Output ungewöhnlich groß wird. Je größer also der Fehler, desto wahrscheinlicher ist es, dass es sich um eine Anomalie handelt. Im besten Fall sind die Fehler normalverteilt, sodass man beispielsweise festlegen kann, dass alle Sequenzen, bei denen der Fehler unwahrscheinlicher als 0.1% ist, als Anomalie erkannt werden.

GAN

Unser zweiter Ansatz basiert auf dem Prinzip der Generative Adversarial Networks, kurz GAN. Für eine Erklärung, wie GANs allgemein funktionieren, würden wir euch auf folgenden Beitrag hier im Blog verweisen: GANs – Applied on Novatec employees. Für das Verständnis dieses Abschnitts ist vor allem der Teil ‚How GANs work‘ wichtig.

In unserem Fall generiert der Generator an Stelle von Bildern möglichst realistische Zeitserien-Sequenzen. Nach dem Training haben wir also einen Generator, der aus zufälligen Vektoren mit einer von uns festgelegten Dimension Sequenzen generiert, die den tatsächlichen, normalen Sequenzen sehr ähnlich sehen. Ungewöhnliche Sequenzen kann der Generator nicht generieren. Dies wurde ihm schließlich abgewöhnt, da der Diskriminator diese sofort als Fälschung erkennen würde.

Die Anomalie-Erkennung funktioniert dann folgendermaßen: Für die zu überprüfende Sequenz A wird jeweils der Vektor aus unserer Menge an zufälligen Vektoren gesucht, mit dem der Generator eine Sequenz B generiert, die unserer Sequenz A möglichst ähnlich sieht. Je weiter die Sequenz B von der Sequenz A entfernt ist, desto ungewöhnlicher ist die Sequenz A und desto wahrscheinlicher beinhaltet die Sequenz A eine Anomalie.

Prediction

Zuletzt bleibt noch das Verfahren einer One-Step-Prediction. Wie auch beim Autoencoder werden die Input-Sequenzen mit Hilfe eines Many-to-One LSTMs encodiert. Diesmal wird dieses Encoding allerdings dafür verwendet, den aktuellen Wert der überprüften Metrik vorherzusagen. Um uns dabei die direkten Abhängigkeiten unserer Metriken zunutze machen zu können, geben wir, um beispielsweise den Wert der überprüften Metrik A um 15:20 Uhr vorherzusagen, deren Werte von 15:05 Uhr bis 15:19 Uhr als Input ins Netz sowie die Werte von 15:06 Uhr bis 15:20 Uhr der Metriken, von denen Metrik A abhängt. Somit haben wir auch die direkt zum vorherzusagenden Wert gehörenden Werte der anderen Metriken.

Nach dem Training kann das Netz also bei normalen Daten relativ gut den aktuellen Wert einer Metrik vorhersagen. Wenn der aktuelle Wert allerdings ungewöhnlich ist, wird die Vorhersage weit davon entfernt sein. Je größer also der Unterschied zwischen Vorhersage und tatsächlichem Wert, desto größer ist die Wahrscheinlichkeit, dass der aktuelle Wert durch einen Fehler in der Anwendung entstanden ist und es sich somit um eine Anomalie handelt.

In unserem Fall hat die Prediction am besten funktioniert, also schlicht die meisten Anomalien korrekt erkannt und die wenigsten normalen Werte fälschlicherweise als anomal markiert. Außerdem ist der Effekt, dass Anomalien durch die Betrachtung von Sequenzen auch einige Zeit, nachdem sie tatsächlich aufgetreten sind, noch einen Einfluss auf die Bewertung aktueller Werte haben können, bei der Prediction deutlich schwächer als beim Autoencoder. Wenn beispielsweise von 15:00 Uhr bis 15:05 Uhr eine Anomalie auftritt, dann wird diese Anomalie beim Autoencoder je nach Fenstergröße der Inputs auch um 15:20 Uhr noch einen relativ großen Einfluss auf die Entscheidung haben, da die frühen Werte innerhalb der Sequenzen genauso gut encodiert und decodiert werden müssen wie die späteren. Bei der Prediction hingegen lässt dieser Einfluss deutlich schneller nach, da ältere Werte innerhalb der Sequenz hier nicht immer genauso stark gewichtet werden müssen wie aktuellere Werte.

Stand der Anwendung

Mit der Anomalie-Erkennung ist auch der erste Grundstein unserer dampf-Anwendung gelegt:

Diagramm des Aufbaus der bisherigen dampf-Anwendung

Das Training läuft bei uns auf dem lokalen Machine-Learning-Server, könnte aber natürlich auch je nach Bedarf zum Beispiel mit einer EC2-Instanz mit GPU wie die anderen Teile der Anwendung in Amazon Web Services verlegt werden. Die gelernten Gewichte werden in einen S3-Bucket hochgeladen. Die Erkennung läuft dann mit den Gewichten aus dem S3-Bucket regelmäßig in einer AWS-Lambda und alle Informationen werden in Datenbanken auf EC2-Instanzen gespeichert.

Wie sich diese Anwendung weiterentwickelt, könnt ihr in den weiteren Teilen der dampf-Reihe verfolgen.