Computational limitations in robust classification and win-win results
Zusammenfassung
Für diesen Bericht lag nur ein Auszug oder keine vollständige Fassung vor. Die Zusammenfassung sagt das selbst.
Kurz
Der Bericht ist nur als Abstract-Auszug mit Bildunterschriften verfügbar. Er beschreibt bedingte Ergebnisse, wonach robuste Klassifikatoren trotz ihrer Existenz schwer effizient erlernbar sein können, und behauptet, solche Gegenbeispiele führten zu kryptografischen Grundbausteinen wie Einwegfunktionen. Die Einzelheiten und Beweise sind im Auszug nicht enthalten.
Mittel
Der Bericht liegt nur als Auszug vor: enthalten sind der Abstract, Autorenangaben und Bildunterschriften, nicht der vollständige Artikel. Der Abstract untersucht, unter welchen Voraussetzungen robuste Klassifikatoren effizient existieren oder erlernt werden können. Aufbauend auf früheren Ergebnissen beschreibt der Beitrag drei Erweiterungen: Es gebe Aufgaben, bei denen robuste Klassifikatoren existieren, effiziente robuste Klassifikation aber selbst mit unbegrenztem Lernen nicht möglich sei, sofern durchschnittlich schwere Funktionen existieren. Außerdem gebe es Aufgaben für große Störungen, bei denen ein effizienter robuster Klassifikator existiert, aber kein nichttrivialer robuster Klassifikator effizient erlernt werden könne. Die dafür beschriebenen Konstruktionen beruhen laut Abstract auf Einwegfunktionen beziehungsweise der Schwierigkeit des Lernens von Parität mit Rauschen. Im zweiten Fall könnten aus polynomial vielen Trainingsbeispielen effizient neue gelabelte Beispiele erzeugt werden. Schließlich behaupten die Autoren, jedes solche Gegenbeispiel impliziere kryptografische Primitive wie Einwegfunktionen. Daraus folge ein „Win-win“: effizientes robustes Lernen oder neue kryptografische Konstruktionen. Beweise und Details fehlen im Auszug.
Ausführlich lesen
Der bereitgestellte Bericht ist ein Auszug: Er enthält den Abstract sowie Autorenangaben und Bildunterschriften, aber nicht den vollständigen Artikel. Die folgenden Aussagen geben daher die im Abstract beschriebenen Ergebnisse wieder.
Der Beitrag von Akshay Degwekar, Preetum Nakkiran und Vinod Vaikuntanathan untersucht den Zielkonflikt zwischen Rechenaufwand und Robustheit beim Lernen von Klassifikatoren. Er knüpft an frühere Arbeiten an, die Aufgaben beschrieben, bei denen ein robuster Klassifikator für kleine Störungen effizient existiert und ein nicht robuster Klassifikator effizient gelernt werden kann, während das effiziente Lernen eines robusten Klassifikators unter einer Annahme zur Schwierigkeit der Faktorisierung großer Zahlen schwer ist. Ob in diesem früheren Beispiel auch für große Störungen ein robuster Klassifikator existiert, verbindet der Abstract mit offenen Fragen der rechnerischen Zahlentheorie.
Der Beitrag erweitert diese Untersuchung in drei Richtungen. Erstens beschreibt er Klassifikationsaufgaben, bei denen effiziente robuste Klassifikation unmöglich sein soll, obwohl robuste Klassifikatoren ohne Beschränkung des Rechenaufwands existieren. Dafür berufen sich die Autoren auf die Existenz durchschnittlich schwerer Funktionen.
Zweitens präsentieren sie Aufgaben, bei denen robuste Klassifikatoren für große Störungen zwar effizient existieren, sich aber nach ihrer Darstellung kein nichttrivialer robuster Klassifikator effizient erlernen lässt. Eine Konstruktion setzt die Existenz von Einwegfunktionen voraus. Eine weitere stützt sich auf die Schwierigkeit des Lernens von Parität mit Rauschen. In diesem zweiten Szenario existiert laut Abstract außerdem ein effizienter nicht robuster Klassifikator. Auch lassen sich dort aus polynomial vielen Trainingsbeispielen effizient neue gelabelte Beispiele erzeugen; diese Fähigkeit bezeichnen die Autoren als „generation“.
Drittens behauptet der Abstract, dass jedes derartige Gegenbeispiel die Existenz kryptografischer Grundbausteine wie Einwegfunktionen nach sich zieht. Daraus leiten die Autoren ein „Win-win“-Szenario ab: Entweder lässt sich ein effizienter robuster Klassifikator lernen, oder es lassen sich neue Instanzen kryptografischer Primitive konstruieren.
Der Auszug liefert keine Beweise, formalen Definitionen oder Einzelheiten zu den Konstruktionen; seine Aussagen sind deshalb hier als Zusammenfassung der im Abstract berichteten Behauptungen wiedergegeben. Die beigefügten Bildunterschriften nennen CoinRun-Szenen, eine stilisierte französische Presse und ein abstraktes Gemälde, erläutern im Auszug aber nicht, wie diese Abbildungen mit den theoretischen Ergebnissen zusammenhängen.
Wie die Modelle den Bericht einordnen
Ansicht
Filter
Tempo und Grenzen
- SF-T3 Woran erkennt man, dass KI beginnt, ihre eigene Weiterentwicklung voranzutreiben, und wer darf das erlauben?
- clef 100 %kein Bezug
- Luna 100 %kein Bezug
- JEV
- amos 100 %kein Bezug
- SubQ 100 %kein Bezug
- drex 55 %gleiches Oberthema, hilft nicht
- d3-ultra 100 %kein Bezug
Vertrauen in Modelle
- SF-V3 Halten die Werte eines Modells, wenn niemand zusieht oder die Lage neu ist?
- clef 100 %kein Bezug
- Luna 100 %kein Bezug
- JEV
- amos 100 %kein Bezug
- SubQ 100 %kein Bezug
- drex 48 %gleiches Oberthema, hilft nicht
- d3-ultra 100 %kein Bezug
- SF-V5 Was soll heute für das Verhalten und den Betrieb von Modellen gelten?
- clef 100 %kein Bezug
- Luna 100 %kein Bezug
- JEV
- amos 44 %gleiches Oberthema, hilft nicht
- SubQ 100 %kein Bezug
- drex 100 %kein Bezug
- d3-ultra 100 %kein Bezug