Bagging Robustly Learns VC Classes with Linear Sample Complexity
Diese Arbeit zeigt, dass die Kombination von Bagging mit robuster empirischer Risikominimierung adversarielles robustes Lernen für VC-Klassen mit einer linearen Stichprobenkomplexität in der VC-Dimension erreicht, was die bisherigen Schranken signifikant verbessert und gleichzeitig eine passende untere Schranke für die erforderlichen Oracle-Aufrufe etabliert.
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 bringen einem Roboter bei, Katzen auf Fotos zu erkennen. Sie zeigen ihm tausende Bilder, und er lernt, Schnurrhaare und spitze Ohren zu entdecken. Aber was ist, wenn jemand heimlich einen winzigen, fast unsichtbaren Aufkleber auf die Nase der Katze klebt? Für einen Menschen sieht die Katze immer noch wie eine Katze aus, aber der Roboter glaubt plötzlich, es sei ein Toaster. Dies ist die Welt der „adversarial examples“ (adversarieller Beispiele) – winzige, hinterlistige Veränderungen, die intelligente Maschinen täuschen. Wissenschaftler versuchen schon lange, Roboter zu bauen, die diese Tricks ignorieren können, aber es gibt einen Haken: Je komplexer das Gehirn des Roboters (seine „Funktionsklasse“) ist, desto schwieriger ist es, ihn gegen diese Tricks immun zu machen, ohne Millionen von Beispielen zu benötigen.
Um das Problem zu verstehen, stellen Sie sich das „Lernen“ als das Finden des besten Regelbuchs in einer riesigen Bibliothek vor. Die „VC-Dimension“ ist nur eine schicke Art, zu zählen, wie viele verschiedene Regeln die Bibliothek hat. Wenn die Bibliothek riesig ist, braucht man normalerweise viele Beispiele, um die richtige Regel zu finden. Aber wenn adversarielle Tricks im Spiel sind, legten alte Methoden nahe, dass man eine astronomische Anzahl von Beispielen bräuchte – so viele, dass es für komplexe Regeln unmöglich erschien. Eine weitere wichtige Idee hier ist der „Oracle“ (Orakel), der wie eine magische Blackbox ist, die Ihnen sofort ein spezifisches, schwieriges Rätsel lösen kann. Die große Frage, die Forscher gestellt haben, lautet: Können wir einen Roboter bauen, der lernt, robust (tricksicher) zu sein, indem er eine vernünftige Anzahl von Beispielen nutzt und unser magisches Blackbox-Orakel nur ein paar Mal befragt?
Dieses Papier mit dem Titel „Bagging Robustly Learns VC Classes with Linear Sample Complexity“ beantwortet diese Frage mit einem begeisterten „Ja, aber mit einem Twist“. Der Autor, der die Arbeit leitet, beweist, dass man keine unmögliche Anzahl von Beispielen benötigt, um einer Maschine beizubringen, robust zu sein. Tatsächlich zeigt er, dass für viele Arten von Lernproblemen die Anzahl der benötigten Beispiele in einer einfachen, geradlinigen Beziehung zur Komplexität der Regeln (der VC-Dimension) wächst. Dies ist eine massive Verbesserung gegenüber bisherigen Ideen, die suggerierten, dass die Anzahl der Beispiele exponentiell explodieren würde.
Das Geheimrezept in ihrem Rezept ist eine kluge Kombination aus zwei alten Ideen: „Bagging“ und „Robust Training“. Stellen Sie sich vor, Sie haben ein Team von Detektiven, die versuchen, einen Fall zu lösen. Anstatt sich auf nur einen Detektiv zu verlassen, stellen Sie viele ein. Sie geben jedem Detektiv eine leicht unterschiedliche, zufällige Auswahl an Hinweisen (eine „Bootstrap-Stichprobe“) und bitten ihn, den Fall mit einer speziellen „robusten“ Methode zu lösen, die die hinterlistigen falschen Hinweise ignoriert. Dann lassen Sie die Detektive über die endgültige Antwort abstimmen. Wenn die meisten von ihnen übereinstimmen, entscheiden Sie sich für diese Antwort. Das Papier beweist, dass man, wenn man genug dieser Detektive einstellt (speziell eine Anzahl, die mit der „dualen VC-Dimension“ zusammenhängt, einem Maß für die Komplexität der Regeln), die richtige Antwort mit sehr wenigen Beispielen finden kann.
Das Papier zieht jedoch auch eine harte Linie im Sand. Obwohl sie einen Weg gefunden haben, dies effizient zu tun, haben sie auch bewiesen, dass man es nicht besser als eine bestimmte Grenze machen kann. Sie zeigten, dass kein Roboter, egal wie viele Beispiele man ihm gibt, scheitern wird, wenn man die magische Blackbox (das Orakel) weniger als eine bestimmte Anzahl von Malen (bezogen auf die duale VC-Dimension) befragt. Es ist wie der Versuch, ein Puzzle mit nur der Hälfte der Teile zu lösen; kein noch so intensives Starren auf das Bild auf dem Karton wird helfen, es fertigzustellen. Der Autor hat bewiesen, dass diese Grenze unvermeidlich ist.
Kurz gesagt liefert dieses Papier ein einfaches, praktisches Rezept, um KI gegen Tricks robust zu machen. Es zeigt, dass wir durch einen „Voting-Team“-Ansatz komplexe Regeln mit einer handhabbaren Anzahl von Beispielen lernen können. Aber es warnt uns auch, dass es eine fundamentale Kostenstelle gibt: Wir müssen unsere Hilfswerkzeuge eine spezifische Mindestanzahl von Malen befragen, sonst wird das Lernen einfach nicht funktionieren. Dies führt uns von der Vorstellung, dass robustes Lernen für komplexe Systeme unmöglich ist, hin zu dem Wissen, wie man es genau baut und was die Mindestanforderungen dafür sind.
Ertrinken Sie in Arbeiten in Ihrem Fachgebiet?
Erhalten Sie tägliche Digests der neuesten Arbeiten passend zu Ihren Forschungsbegriffen — mit technischen Zusammenfassungen, in Ihrer Sprache.