Ultraschnelle KI-Beweisverifikation: Was ein neues mathematisches Ergebnis für die Überprüfung enormer Datenmengen bedeutet

Wichtige Punkte

• Apple ML Research hat eine Studie über eine neue Klasse mathematischer Beweissysteme namens doppelt sublineare interaktive Näherungsbeweise veröffentlicht.
• Die Methode ermöglicht es einem Beweiser – der Partei, die eine Behauptung aufstellt – nur einen kleinen Teil eines massiven Datensatzes zu lesen, um einen Beweis zu erzeugen.
• Ein Verifizierer – die Partei, die die Behauptung überprüft – muss einen noch kleineren Teil lesen, um zu bestätigen, ob der Beweis wahrscheinlich korrekt ist.
• Die Technik gilt für ungefähre Verifikation, was bedeutet, dass sie deutlich falsche Eingaben erkennt, ohne jeden Byte inspizieren zu müssen.
• Nach Aussage der Forschung kann keine bestehende Technik den Verifizierer dazu bringen, eine falsche Behauptung zu akzeptieren.

Stellen Sie sich vor, Sie leiten ein Lagerhaus mit einer Million Kartons und jemand sagt Ihnen, dass ungefähr 95 Prozent davon korrekt gekennzeichnet sind. Sie haben keine Zeit, jeden Karton zu öffnen. Was wäre, wenn Sie nur ein paar hundert Kartons stichprobenartig überprüfen könnten und trotzdem sicher wären, dass die Behauptung stimmt? Das ist die Intuition hinter dieser Forschung.

Wissenschaftler von Apple ML Research haben eine Studie über sogenannte doppelt sublineare interaktive Näherungsbeweise oder dsIPPs veröffentlicht. Ein interaktiver Näherungsbeweis ist ein Protokoll – ein formales Hin- und Hergespräch zwischen zwei Parteien – das es einer Seite ermöglicht, die andere davon zu überzeugen, dass ein riesiger Datensatz eine bestimmte Eigenschaft erfüllt, ohne dass eine der Seiten ihn vollständig lesen muss. „Sublinear" bedeutet einfach, dass der Aufwand viel langsamer wächst als die Größe der Daten, sodass die Überprüfung von einer Milliarde Datensätzen möglicherweise nur das Lesen von einigen tausend erfordert.

Das „doppelt" ist die neue Wendung. Sowohl die Partei, die den Beweis erzeugt, als auch die Partei, die ihn überprüft, arbeiten in sublinearer Zeit. Bisher erforderten Beweissysteme dieser Art, dass der Beweiser die gesamte Eingabe liest. Hier liest der Beweiser nur einen kleinen Teil. Der Verifizierer liest sogar noch einen kleineren Teil.

Was bedeutet hier „ungefähr"? Das System garantiert keine Perfektion. Es garantiert, dass wenn eine Eingabe wirklich zur getesteten Eigenschaft gehört, ein ehrlicher Beweiser den Verifizierer immer überzeugen kann zu akzeptieren. Und wenn eine Eingabe weit entfernt von dieser Eigenschaft ist, kann kein unehrlicher Beweiser den Verifizierer täuschen und „ja" sagen. Denken Sie daran wie bei einem Rauchmelder: Er wird ein echtes Feuer nicht übersehen, und eine Rauchmaschine wird ihn nicht täuschen.

Warum sollten normale Menschen sich dafür interessieren?

Sie werden mit dieser Forschung wahrscheinlich jahrelang nicht direkt in Berührung kommen, wenn überhaupt. Aber die Probleme, die sie adressiert, liegen unter Technologien, die Menschen täglich nutzen. Streaming-Dienste überprüfen, ob riesige Dateibibliotheken Qualitätsstandards erfüllen. Banken prüfen Transaktionsdatensätze auf Betrugsmuster. Gesundheitssysteme durchsuchen Millionen von Datensätzen auf Meldungsfehler. Jede Situation, in der die Überprüfung von allem zu langsam oder zu teuer ist, ist genau der Ort, an dem diese Art von Beweissystem schließlich nützlich wird.

Die Forschung ist derzeit theoretisch, was bedeutet, dass sie die mathematischen Grundlagen legt, anstatt ein Produkt zu liefern. Praktische Tools, die auf diesen Ideen aufbauen, könnten es Softwaresystemen ermöglichen, großflächige Behauptungen viel schneller zu überprüfen, als aktuelle Methoden es erlauben, ohne dabei Zuverlässigkeit zu opfern.

Die vollständige Arbeit steht für Forscher zur Verfügung, die tiefer in die formalen Beweise und Komplexitätsgrenzen eindringen möchten.