🤖 machine learning

Verification of Unknown Dynamical Systems via Autoencoder Latent Space

Dieser Artikel schlägt einen formalen Verifikationsrahmen vor, der konvexe Autoencoder und kernelbasiertes Dynamiklernen kombiniert, um hochdimensionale dynamische Systeme in einen niedrigdimensionalen latenten Raum zu reduzieren, eine endliche Abstraktion zu konstruieren, die die Einschließung des tatsächlichen Systemverhaltens garantiert, um eine skalierbare und korrekte Verifikation zu ermöglichen.

Ursprüngliche Autoren: Robert Reed, Luca Laurenti, Morteza Lahijanian

Veröffentlicht 2026-05-21

📖 5 Min. Lesezeit🧠 Tiefgang

CC BY 4.0

Ursprüngliche Autoren: Robert Reed, Luca Laurenti, Morteza Lahijanian

Originalarbeit lizenziert unter CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/). ✨ Dies ist eine KI-generierte Erklärung des untenstehenden Papers. Sie wurde nicht von den Autoren verfasst oder gebilligt. Für technische Genauigkeit konsultieren Sie das Originalpaper. Vollständigen Haftungsausschluss lesen

Stellen Sie sich vor, Sie versuchen zu beweisen, dass ein sehr komplexer, hochdimensionaler Roboter (wie ein autonomes Fahrzeug mit Hunderten von Sensoren) niemals einen Unfall haben wird und sein Ziel immer erreichen wird. Dies wird als „formale Verifikation" bezeichnet.

Das Problem ist, dass das „Gehirn" des Roboters so kompliziert ist und so viele bewegliche Teile (Dimensionen) besitzt, dass das Überprüfen jedes denkbaren Szenarios wie der Versuch ist, jeden einzelnen Sandkorn an einem Strand zu zählen. Es dauert zu lange und erfordert zu viel Rechenleistung.

Diese Arbeit schlägt eine clevere Lösung vor: Verkleinern Sie das Problem, lösen Sie es dort und beweisen Sie, dass die Lösung für die große Version funktioniert.

So gehen sie dabei vor, unter Verwendung einfacher Analogien:

1. Die „Magische Karte" (Der Autoencoder)

Stellen Sie sich die Welt des Roboters als ein riesiges, dreidimensionales Labyrinth vor. Die Navigation und der Sicherheitsnachweis in 3D sind schwierig. Die Autoren verwenden ein spezielles Werkzeug namens Autoencoder, um eine „Magische Karte" zu erstellen.

Der Encoder: Dies ist wie ein Übersetzer, der das komplexe 3D-Labyrinth in eine einfache 2D-Zeichnung komprimiert.
Der Decoder: Dies ist der umgekehrte Übersetzer, der die 2D-Zeichnung zurück in das 3D-Labyrinth verwandeln kann.
Der Haken: Normalerweise gehen Informationen verloren, wenn man ein 3D-Objekt in 2D quetscht. Zwei verschiedene Stellen im 3D-Labyrinth könnten auf der 2D-Karte wie derselbe Punkt aussehen. Dies erzeugt „Faltungen" oder Verwirrung.

Die Innovation: Die Autoren bauten eine sehr spezifische Art von Encoder (einen konvexen Autoencoder), der wie ein strenger, ordentlicher Bibliothekar agiert. Er stellt sicher, dass eine solide, zusammenhängende Form in der 3D-Welt auch auf der 2D-Karte als solide, zusammenhängende Form erhalten bleibt. Sie reißen die Karte nicht und falten sie nicht auf eine Weise, die die Logik zerstört.

2. Der „neblige Kristallkugel" (Inklusionsdynamik)

In der realen Welt ist die Bewegung des Roboters deterministisch (wenn Sie ihn stoßen, bewegt er sich auf eine bestimmte Weise). Aber auf der 2D-Karte wird die Bewegung des Roboters durch das Quetschen der Welt „unscharf".

Befindet sich der Roboter auf der Karte am Punkt A, könnte er sich tatsächlich an einem von mehreren verschiedenen Orten in der realen 3D-Welt befinden.
Daher geht der Roboter auf der Karte nicht nur zu einem nächsten Punkt; er könnte zu einer ganzen „Wolke" möglicher nächster Punkte gelangen.

Die Autoren nennen dies „Inklusionsdynamik". Anstatt einen einzelnen Punkt vorherzusagen, sagen sie eine „Wolke" oder eine „Kugel" von Möglichkeiten voraus. Sie verwenden ein statistisches Werkzeug namens Gaußscher Prozess (denken Sie daran als eine sehr kluge Kristallkugel), um zu lernen, wie sich diese Wolken bewegen. Sie raten nicht nur das Zentrum der Wolke; sie berechnen die schlimmstmöglichen Grenzen der Wolke, um sicherzustellen, dass sie keine Möglichkeit übersehen.

3. Das „Sicherheitsnetz" (Verifikation)

Sobald sie diese 2D-Karte mit unscharfen Bewegungswolken haben, bauen sie ein „Sicherheitsnetz" (eine endliche Abstraktion).

Sie teilen die 2D-Karte in kleine Kacheln auf.
Sie prüfen: „Wenn der Roboter in dieser Kachel startet, kann er jemals in eine 'Gefahrenzone' (wie eine Klippe oder eine Wand) geraten?"
Da sie die „schlimmstmöglichen" Wolken verwendet haben, wissen sie, wenn das Sicherheitsnetz sagt „Ja, es ist sicher", mit Gewissheit, dass der Roboter auch in der realen 3D-Welt sicher ist. Selbst wenn die Karte unscharf ist, ist das Sicherheitsnetz so gebaut, dass es übermäßig vorsichtig ist.

4. Der „Nachweis der Rückführung"

Der wichtigste Teil ist, dass sie bewiesen haben, dass man die Antwort von der 2D-Karte zurück in die reale 3D-Welt übertragen kann, ohne die Garantie zu verlieren.

Wenn die 2D-Karte sagt „Dieser Bereich ist sicher", können sie mathematisch beweisen, dass der entsprechende Bereich in der realen 3D-Welt ebenfalls sicher ist.
Sie testeten dies an einem 26-dimensionalen System (ein Roboter, der LiDAR-Sensoren verwendet). Traditionelle Methoden hätten ewig gedauert oder wären vollständig gescheitert, da sich die Anzahl der Möglichkeiten explosionsartig vermehrt hätte. Ihre Methode verkleinerte es auf 2 Dimensionen, löste es schnell und bewies, dass es funktioniert.

Zusammenfassung

Stellen Sie es sich so vor:
Sie haben eine riesige, chaotische Bibliothek (das hochdimensionale System). Sie wollen beweisen, dass niemals Bücher von den Regalen fallen werden.

Komprimieren: Sie machen ein Foto der Bibliothek und verkleinern es zu einer winzigen, handhabbaren Skizze (dem latenten Raum).
Verschmieren: Da die Skizze klein ist, sehen die Regale etwas verschwommen aus. Sie wissen nicht genau, wo jedes Buch ist, also zeichnen Sie einen „unscharfen Kasten" um die Stelle, an der ein Buch sein könnte (Inklusionsdynamik).
Prüfen: Sie prüfen die Skizze. Wenn die unscharfen Kästen die „Gefahrenzone" auf der Skizze niemals berühren, wissen Sie mit Gewissheit, dass die echten Bücher nicht fallen werden.
Übersetzen: Sie beweisen, dass Ihre Skizze so sorgfältig gezeichnet ist, dass, wenn sie sicher ist, die echte Bibliothek definitiv sicher ist.

Die Arbeit behauptet, dass diese Methode es uns ermöglicht, komplexe, KI-gesteuerte Systeme zu verifizieren, die zuvor zu groß waren, um sie zu prüfen, ohne Sicherheitsgarantien zu opfern.

Technische Zusammenfassung: Verifikation unbekannter dynamischer Systeme über den latenten Raum eines Autoencoders

Problemformulierung
Die formale Verifikation kontinuierlicher dynamischer Systeme ist entscheidend, um zu garantieren, dass autonome Systeme Sicherheits- und Lebendigkeitsanforderungen erfüllen, die häufig in der Linearen Temporallogik (LTL) ausgedrückt werden. Standardansätze beinhalten die Konstruktion endlicher Zustandsabstraktionen, um Modellprüfung zu ermöglichen. Diese Techniken stoßen jedoch in hochdimensionalen Szenarien auf erhebliche Skalierbarkeitsprobleme, da die Größe der Abstraktion exponentiell mit der Dimension des Zustandsraums wächst. Dieses Problem wird in KI-gestützten Systemen (z. B. solchen, die durch neuronale Netze gesteuert werden, die LiDAR- oder Kameradaten verarbeiten) noch verschärft, wo die Dynamiken komplex, teilweise unbekannt oder Black-Box sind. Obwohl datengetriebene Techniken zur Dimensionsreduktion wie Autoencoder eine potenzielle Lösung für die Skalierbarkeit bieten, fehlt es ihnen typischerweise an formalen Korrektheitsgarantien. Insbesondere bleibt die Abbildung hochdimensionaler Spezifikationen auf einen gelernten latenten Raum und die Sicherstellung, dass die gelernten latenten Dynamiken das Verhalten des ursprünglichen Systems (einschließlich Nichtdeterminismus) getreu widerspiegeln, eine offene Herausforderung. Bestehende Methoden tauschen oft Korrektheit gegen Flexibilität oder stützen sich auf starke Annahmen über Systemdynamiken, die für gelernte Repräsentationen nicht gelten.

Methodik
Der vorgeschlagene Rahmen adressiert diese Herausforderungen, indem er Dimensionsreduktion mit abstraktionsbasierter Verifikation kombiniert, um formale Garantien für hochdimensionale Systeme mit unbekannten Dynamiken zu liefern. Der Ansatz besteht aus vier Hauptphasen:

Konvexe Autoencoder-Architektur: Um sicherzustellen, dass der latente Raum interpretierbar ist und eine fundierte Schlussfolgerung unterstützt, verwenden die Autoren einen konvexen Autoencoder. Der Encoder ist auf ein Input Convex Neural Network (ICNN) mit spezifischen strukturellen Einschränkungen beschränkt: streng monotonen Aktivierungsfunktionen (um als Homöomorphismen zu wirken), injektiven ersten und Skip-Schichten sowie vollrangigen Gewichtsmatrizen. Diese Architektur, die als „Connected Input-Connected Output" (CICO)-Netzwerk bezeichnet wird, garantiert, dass das Urbild einer beliebigen zusammenhängenden Menge im latenten Raum eine zusammenhängende Menge im ursprünglichen Zustandsraum ist. Diese Eigenschaft ist entscheidend für den Umgang mit der Nicht-Injektivität der Abbildung, wenn die latente Dimension niedriger ist als die minimale Realisierung des Systems.
Lernen latenter Inklusionsdynamiken: Da die Dimensionsreduktion zu einem Informationsverlust führen kann, wird die Evolution im latenten Raum als Inklusionsdynamik (mengenwertig) modelliert und nicht als deterministische Differenzengleichung. Die Autoren führen „Inklusions-Gauß-Prozesse" (Inclusion GPs) ein, eine neuartige Formulierung der Gauß-Prozess-Regression (GPR) für mengenwertige Dynamiken. Diese Methode hebt die Dynamiken in einen höherdimensionalen Raum, in dem sie Differenzengleichungen befolgen, die einen unbeobachteten Parameter $c$ enthalten. Durch das Lernen eines tiefen Kernels, der diese unbeobachtete Koordinate integriert, sagt die Methode die Evolution des Systems als Menge (speziell eine Kugel im latenten Raum) voraus und liefert strenge Fehlergrenzen basierend auf einer Analyse des Reproduzierenden Kernel-Hilbertraums (RKHS).
Korrekte Konstruktion endlicher Abstraktionen: Unter Verwendung des gelernten Inklusions-GP konstruieren die Autoren ein nichtdeterministisches Transitionsystem (NTS) im latenten Raum.
- Regionenabbildung: Hochdimensionale Regionen von Interesse (sichere, unsichere und Zielmengen) werden auf den latenten Raum abgebildet. Die Konvexität des Encoders ermöglicht eine effiziente, samplingbasierte Unterapproximation und eine probabilistische Oberapproximation (unter Verwendung von $\epsilon$ -RandUp) dieser Mengen.
- Transitionsrelation: Übergänge zwischen abstrakten Zuständen werden berechnet, indem Regionen durch das Inklusions-GP-Modell propagiert werden, wobei Regressionsfehler und der unbeobachtete Parameter $c$ berücksichtigt werden. Dies stellt sicher, dass die Abstraktion konservativ alle möglichen Verhaltensweisen des ursprünglichen Systems erfasst.
- Korrektheitsgarantien: Der Rahmen beweist, dass, wenn ein Zustand im latenten NTS eine Erreichbarkeits-Vermeidungs-Spezifikation erfüllt, dann alle entsprechenden Trajektorien im ursprünglichen hochdimensionalen System die Spezifikation mit einem hohen Konfidenzniveau ( $1-\delta$ ) erfüllen.
Verifikation und Dekodierung: Auf das latente NTS werden Standard-Model-Checking-Tools angewendet, um Zustände zu identifizieren, die garantiert die Spezifikation erfüllen ( $Q_{yes}$ ), Zustände, die sie nicht erfüllen können ( $Q_{no}$ ), und unsichere Zustände ( $Q_?$ ). Da der Encoder konvex ist, können erfüllende latente Zustände effizient zurück in den ursprünglichen hochdimensionalen Raum dekodiert werden, indem konvexe Optimierung verwendet wird, um die Menge der Anfangszustände im ursprünglichen System zu identifizieren, die garantiert sicher sind.

Hauptbeiträge
Die Arbeit leistet vier primäre Beiträge:

Beweisbar korrekte Abbildung: Eine Methode zur Abbildung hochrangiger Spezifikationen in einen latenten Raum unter Verwendung eines CICO-Encoders, die eine effiziente Schlussfolgerung über komprimierte Repräsentationen ermöglicht, während formale Garantien erhalten bleiben.
Inklusions-GPs: Eine neuartige Formulierung der Gauß-Prozess-Regression für inklusionswertige (mengenwertige) Dynamiken, die das Lernen latenter Dynamiken ermöglicht, die durch Differenzinklusionen gesteuert werden, ohne dass explizites Wissen über die zugrunde liegenden unbeobachteten Parameter erforderlich ist.
Fundierter Abstraktionsrahmen: Ein vollständiger Rahmen zur Generierung fundierter endlicher Abstraktionen im latenten Raum auf Basis von Inklusions-GPs, einschließlich Verfahren zur Rückführung von Erfüllbarkeitsgarantien auf das ursprüngliche System mit Korrektheitsbeweisen.
Empirische Validierung: Demonstration des Ansatzes an mehreren Systemen, einschließlich eines 26-dimensionalen Systems, das durch ein neuronales Netz gesteuert wird (unter Verwendung von LiDAR-Eingaben), was signifikante Verbesserungen der Skalierbarkeit gegenüber traditionellen Abstraktionsmethoden zeigt.

Ergebnisse
Der Ansatz wurde an drei Fallstudien evaluiert:

3D zu 2D: Ein System minimaler Realisierung, bei dem die Methode den gesamten latenten Raum erfolgreich verifizierte, wohingegen die traditionelle datengetriebene Abstraktion im ursprünglichen 3D-Raum aufgrund von Unsicherheiten in langsam bewegenden Dimensionen die Verifikation der Erreichbarkeit nicht durchführen konnte.
6D zu 2D: Ein überparametrisiertes System mit nichtlinearen Beobachtungen. Die Methode verifizierte 100 % des latenten Raums für den fall ohne Hindernisse und 59,78 % für den Fall mit einem Hindernis. Im Gegensatz dazu führte der Versuch einer Abstraktion im ursprünglichen 6D-Raum zu einer Zustandsexplosion, wobei es innerhalb des Zeitlimits gelang, keine Regionen jenseits des Ziels selbst zu verifizieren.
26D zu 2D: Eine Roboternavigationsaufgabe mit LiDAR-Eingaben und einem neuronalen Netz-Controller. Die Methode lernte erfolgreich einen 2D-latenten Raum, der die Dynamiken des Systems mit minimalem Nichtdeterminismus erfasst und 50,0001 % des latenten Raums verifizierte. Dies demonstrierte die Fähigkeit, hochdimensionale Beobachtungsräume zu handhaben, in denen traditionelle Methoden nicht durchführbar sind.

Bedeutung
Die Arbeit behauptet, eine kritische Lücke zwischen Dimensionsreduktion und formaler Verifikation zu schließen. Durch die Bereitstellung von Soundness-Garantien sowohl für die Abbildung von Spezifikationen als auch für die gelernten latenten Dynamiken eliminiert die Arbeit falsch-positive Ergebnisse in der Verifikation, ein häufiges Problem beim lernbasierten Steuern. Die Autoren betonen, dass ihr Ansatz eine skalierbare Verifikation für hochdimensionale Systeme mit unbekannten Dynamiken ermöglicht, eine Fähigkeit, die mit bestehenden formalen Methoden zuvor nicht erreichbar war. Obwohl der Rahmen sound ist, weisen die Autoren bescheiden auf Einschränkungen hin, darunter die Beschränkung auf konvexe Encoder (was die Ausdruckskraft begrenzt) und offene Fragen bezüglich der Einbeziehung von Rauschen und der Steuerungssynthese, die als Richtungen für zukünftige Arbeiten identifiziert wurden.

1. Die „Magische Karte" (Der Autoencoder)

2. Der „neblige Kristallkugel" (Inklusionsdynamik)

3. Das „Sicherheitsnetz" (Verifikation)

4. Der „Nachweis der Rückführung"

Zusammenfassung

Mehr davon