Complexity of Reachability Problems in Neural Networks

Das Kapitel geht der komplexen Komplexität der Erreichbarkeitsprobleme in neuronalen Netzwerken nach, die für die Gewährleistung der Sicherheit in kritischen Systemen wie dem autonomen Fahren von entscheidender Bedeutung sind. Es baut auf dem Erfolg neuronaler Netzwerke in verschiedenen Anwendungen wie Bilderkennung und Verarbeitung natürlicher Sprache auf, um die rechnerischen Herausforderungen durch unterschiedliche Aktivierungsfunktionen zu analysieren. Die Autoren setzen diese Probleme mit Constraint Satisfaction Problems (CSP) in Verbindung und nutzen bekannte Komplexitätsergebnisse, um Aktivierungsfunktionen in Komplexitätsklassen einzuordnen. Sie zeigen, dass Erreichbarkeitsprobleme bei vielen häufig verwendeten Aktivierungen NP-vollständig sind und ETR-hart bei mehreren anderen, einschließlich sigmoidaler Funktionen und der exponentiellen Funktion. Das Kapitel untersucht auch die Komplexität der NetzwerÄquivalenz und der Überprüfung von Intervalleigenschaften und zeigt, dass diese Probleme häufig der Komplementarität von Erreichbarkeitsproblemen gleichkommen. Die Autoren liefern eine detaillierte Analyse der damit verbundenen Rechenmodelle und -reduktionen, was das Kapitel zu einer wertvollen Ressource für Spezialisten in neuronalen Netzwerken und Rechenkomplexität macht.