Die Wahl des Lernverfahrens

Ich implementiere die Programmschleife in Java auf Basis von Java 13. Die Wahl fällt auf Java vor allem aufgrund der Verfügbarkeit der exzellenten Open-Source-Bibliothek Machine Learning for Data Streams (MOA), die von den Machern des ML-Frameworks Weka stammt. MOA beinhaltet unzählige temporale, maschinelle Lernverfahren sowie passende Hilfsfunktionen zur Datenbereitstellung und Performancemessung, so dass hier schnell passende Modelle für die Tankstellen trainiert werden können.

Innerhalb von MOA gibt es unzählige Regressions-, aber auch Klassifikationsverfahren. Klassifikatoren sind zumeist leichter und schneller trainierbar, da sie nur zwischen einer endlichen Zahl von Klassen entscheiden müssen. Sie können deshalb den Parameterraum gut separieren und müssen kein aufwendiges Fitting berechnen.

Deshalb betrachte ich die Preisvorhersage als Klassifikationsproblem. Anstatt einen konkreten Preis vorherzusagen, soll der Klassifikator die Änderungshöhe des Preises prognostizieren, wobei jeder Cent Änderung einer Klasse entspricht. Prädiziert er etwa die Klasse -3, so wird eine Preissenkung um 3 Cent pro Liter vorhergesagt. Da Preissprünge um mehr als 10 Cent selten sind, sind die größten Preisänderungen +/- 10 Cent, so dass sich inklusive einer Änderung um 0 Cent insgesamt 21 Klassen ergeben.

• 

Performancevergleich verschiedener Klassifikatoren

Um das richtige Lernverfahren zu wählen, trainiere ich zahlreiche MOA-Klassifikatoren und vergleiche sie anhand der Daten meiner 44 Tankstellen (siehe Tabelle). Der Großteil der Verfahren basiert auf Entscheidungsbäumen, was nicht überrascht, da sie häufig einen guten Kompromiss aus Vorhersagegüte und Trainingsdauer bieten.

Das von der Performance her beste Verfahren ist Ozaboostadwin mit aktivierter Sammeloption mit einer Prognosegüte von 86,05 Prozent. Jedoch ist es verhältnismäßig langsam zu trainieren und erzeugt sehr große Modelle. Stattdessen wähle ich den Limattclassifier, der genauso wie Ozaboostadwin zu den Ensemble-Klassifikatoren gehört, indem er mehrere Entscheidungsbäume parallel nutzt und über Mehrheitsentscheid die Klasse bestimmt.

Dazu nutzen beide Verfahren Adwin als Algorithmus zur Änderungserkennung, der beim Erkennen einer Änderung des Modellzusammenhangs den schlechtesten Baum entfernt und einen neuen trainiert. Der Limattclassifier ist mit 84,415 Prozent ähnlich gut, wenngleich die Kappa-Werte als Performancemaß leicht schlechter sind. Dafür ist er aber schneller trainierbar und ein Modell mit im Durchschnitt 2,5 MB deutlich speicherschonender.

Oft liegt der Klassifikator übrigens nur um eine oder zwei Klassen daneben, so dass die vorhergesagte Preistendenz (steigt, sinkt, bleibt gleich) in über 90 Prozent der Fälle korrekt ist.

Dauer der Programmschleife

40.000 Modelle innerhalb von zehn Minuten zu aktualisieren, ist selbst mit den extrem schnellen Bäumen eine Herausforderung. Allein alle Modelle parallel im Speicher zu halten, würde etwa 100 GByte RAM erfordern, die ich nicht habe. Damit bleibt nichts anderes übrig, als die gelernten Modelle in jedem Zyklus zu persistieren, wofür MOA auch Writer-Klassen anbietet.

Jedoch sind diese relativ langsam und auch das Wiederherstellen dauert. Besser wäre es, die Objekte, die die Modelle repräsentieren, zu serialisieren und wieder zu deserialisieren, jedoch ist die Java-Standardvariante dafür ziemlich langsam.

Deshalb nutze ich Protostuff, eine Java-Implementierung von Googles Protobuf-Protokoll, um die Modelle zu persistieren und wieder in den Speicher zu laden. Zu (de-)serialisieren ist damit sehr schnell, je nach Größe des Java-Objekts liegt der Geschwindigkeitsvorteil zur Java-Standardvariante bei Faktor 15-20.

Auf meinem Entwicklungsrechner, einem 2018er Laptop mit Intel Core i3-6006U mit 2 GHz Takt und 8 GByte RAM, dauern das Deserialisieren eines Modells, das Aktualisieren von diesem, die Vorhersage des nächsten Preises sowie das anschließende Serialisieren mit der Java 13 Runtime ca. 107 ms auf einem Kern. Mit GraalVM sind es 100 ms, also leicht schneller.

Ein CPU-Kern könnte in den zehn Minuten also ca. 6.000 Modelle verarbeiten und da sich diese Berechnung gut parallelisieren lässt, reichen sieben CPU-Kerne aus, um die Zehn-Minuten-Zyklen permanent zu halten.

Ich habe zudem mit einer Kompression der serialisierten Modelle im RAM experimentiert, jedoch brachte dies keine Geschwindigkeitsvorteile, da I/O selbst ohne memory-mapped files kein limitierender Faktor ist. Hätte ich einen Hardwarewunsch frei, würde ich sehr viel RAM bestellen. Denn der zeitaufwendigste Teil der Programmschleife ist trotz hoher Softwareeffizienz das (De-)Serialisieren, das ca. zwei Drittel der Gesamtzeit erfordert. Könnte ich alle Modelle gleichzeitig im RAM halten, wäre das nicht mehr erforderlich.

Andreas Meier beschäftigt sich seit über 20 Jahren mit Künstlicher Intelligenz (KI) und verantwortet heute KI-Anwendungen bei einem Automobilhersteller