Clip-and-Verify: Beschneidung von Einschränkungen beschleunigt NN-Verifikation

In einer bahnbrechenden Veröffentlichung präsentiert ein Forschungsteam einen neuen Ansatz namens Clip-and-Verify, der die Verifikation von neuronalen Netzwerken (NN) deutlich beschleunigt. Durch die gezielte Nutzung linearer Einschränkungen – die häufig aus bestehenden Bounding-Methoden entstehen – kann der Eingaberaum effizient reduziert und die Zwischenbounds im Netzwerk verbessert werden.

Der Ansatz umfasst zwei innovative Algorithmen: Einer schneidet Teile des Eingaberaums ab, die entweder bereits verifiziert sind oder für ein bestimmtes Teilproblem irrelevant sind, während der andere die Bounds entlang des Netzwerks direkt optimiert. Beide Verfahren arbeiten ausschließlich mit linearen Einschränkungen und sind damit flexibel genug, auch zusätzliche Constraints aus anderen Quellen zu integrieren.

Ein entscheidender Vorteil ist die GPU-basierte Implementierung, die ohne teure externe Solver auskommt und selbst bei sehr großen Netzwerken skaliert. Clip-and-Verify lässt sich nahtlos in branch‑and‑bound (BaB) basierte Verifikatoren wie α,β‑CROWN integrieren, indem es entweder die Split‑Constraints im Aktivationsraum oder die Output‑Constraints nutzt, die den unverifizierten Eingaberaum definieren.

Die Ergebnisse sind beeindruckend: Auf einer breiten Palette von Benchmarks zeigt Clip-and-Verify konsequente Bound‑Verengungen und kann die Anzahl der zu bearbeitenden Teilprobleme um bis zu 96 % reduzieren. Diese Fortschritte markieren einen bedeutenden Schritt in Richtung schnellerer und skalierbarer NN‑Verifikation.