Studentische Arbeiten
Beschleunigung regelgetriebener Einbettungen von Graphstrukturen durch maschinelles Lernen
Typ der Arbeit:
Master-Thesis
Bearbeitungsstand: Abgeschlossene Arbeiten
Möglicher Beginn der Arbeit: 18.10.2022
Arbeit abgeschlossen am: 15.07.2024
Betreuer*in: M.Sc. Sebastian Ehmes
Student*in: Marco Volle
Motivation
Das Finden von optimalen und korrekten Lösungen zur Einbettung von Graphstrukturen ist eine spannende aber zeitaufwändige Aufgabe.
Die Methoden (z. B. ILP) zum Finden von optimalen Lösungen sind aufgrund der langen Laufzeit nicht verwendbar für zeitkritische Systeme wie zum Beispiel Echtzeitsysteme.
Für solche Anwendungen bieten sich Machine Learning (ML) basierte Systeme, wie beispielsweise neuronale Netzwerke, an, da diese idR. eine viel kürzere Laufzeit aufweisen.
Das Problem hierbei ist, dass es in der Regel schwierig ist an gelabelte Trainigsdatensätze für das Training der ML-Ansätze zu kommen.
Hier bieten sich die optimalen und korrekten Ansätze wiederum an, um generierte Daten zu bewerten und Musterlösungen zu erzeugen, da der Ablauf dieser Phase nicht zeitkritisch ist.
Mit Hilfe der erzeugten Musterlösungen wird ML-basierten Systemen beigebracht, modellgetriebene Szenarien korrekt zu lösen.
Die wissenschaftliche Fragestellung in dieser Arbeit ist, wie sehr die Optimalität und Korrektheit durch die Anwendung der ML-Ansätzen leidet.
Des Weiteren stellen sich noch folgende interessante Fragen:
- Wie viel schneller wird eine Lösung errechnet und wird in jedem Fall eine Lösung gefunden?
- Wie sieht das Ergebnis aus, falls es keine Lösung gibt?
- Wie gut generalisiert solch ein Ansatz? (Grob unterschiedliche Modelle, unterschiedliche Attributswerte, …)
- Wie hoch sind die Verstöße gegen die Korrektheit? Passieren diese oft?
- Sind die ML-basierten Ansätze schnell genug für reale Szenarien? Wie echtzeitfähig sind sie?
- Was passiert, wenn das jeweilige Modell zu groß ist?
Aufgabenstellung
Ziel der Arbeit ist es, eine Methode zu entwicklen, mit der graphbasierte Einbettungsprobleme mit Hilfe von ML gelöst werden können.
Dafür muss als erstes der Entwurf und/oder die Auswahl eines passenden Beispielszenarios erstellt/getroffen werden.
Hierfür kann beispielsweise die modellgetriebene Netzwerkeinbettung verwendet werden.
Anschließend wird mit dem Auslegen einer Architektur für ein neuronales Netzwerk zur Lösung von Einbettungsproblemen begonnen und dieses präzisiert.
Dabei stellen sich insbesondere folgende Fragen bezüglich des neuronalen Netzwerkes:
- Wie sieht der Inputvektor aus?
- Wie sieht das Layout aus?
- Interner Aufbau: Full mesh oder nicht?
- Welche Aktivierungsfunktionen ergeben in diesem Kontext Sinn?
- Wie sieht der Output aus, sodass eine Lösung für das konkrete Modell erzeugt werden kann?
- Wie funktioniert die Umwandlung von graphbasierten Modellen in Input-Vektoren (numerische Modelle)?
- Umkehrrichtung: Umwandlung von Output-Vektor in eine Lösung für Modelle (Menge von Regeln, Aussehen des Modells, …)
Ein weiteres wichtiges Arbeitspaket ist, eine Vielzahl von Modellinstanzen des gewählten Szenarios zu generieren oder dies durch die Implementierung eines Modellszenariogenerators zu automatisieren.
Zur automatischen Lösung der Modellinstanzen wird das Framework GIPS (https://github.com/Echtzeitsysteme/gips) verwendet, welches aus den graphbasierten Modellen mit Hilfe eines ILP-Generators optimale Lösungen berechnen kann.
Die konkreten Constraints, die verwendeten Zielfunktionen sowie GT-Regeln und damit die Struktur des ILP-Generators sind in der domänenspezifischen Sprache GIPSL zu spezifizieren.
Nach der automatischen Generierung der optimalen Lösungen sind diese für die Erzeugung der Trainigsdatensätze zu verwenden.
Im Anschluss werden die erzeugten Trainigsdatensätze benutzt, um konkrete ML-Modelle zu trainieren und diese anhand einer umfassenden Evaluation zu bewerten.
Voraussetzungen
- Sehr gute Java-Kenntnisse
- Kenntnisse in einem ML-Framework z. B. PyTorch oder TensorFlow
- Abhängig vom gewählten ML-Framework: Python-Kenntnisse bzw. Kenntnisse in passender Programmiersprache