Two Dimensions Govern Agnostic Multiclass Transductive Learning

In der Welt des maschinellen Lernens lernen Computer, Vorhersagen zu treffen, indem sie Beispiele studieren. Stellen Sie sich einen Schüler vor, der versucht, die Antwort auf eine Testfrage zu erraten. Im herkömmlichen Lernverfahren, dem sogenannten „PAC-Lernen“, übt der Schüler mit einem Satz von Karteikarten und macht dann einen Test mit neuen, noch nicht gesehenen Karten. Das Ziel ist es, im Durchschnitt über viele mögliche Tests hinweg gut abzuschneiden. Es gibt jedoch noch eine andere, spezifischere Art des Lernens, das sogenannte „transduktive Lernen“. Hier erhält der Schüler das gesamte Testblatt im Voraus, einschließlich jeder Frage, wobei jedoch die Antwort auf nur eine ganz bestimmte Frage verborgen bleibt. Der Schüler sieht alle anderen Antworten und muss die eine fehlende Antwort vorhersagen. Dieser Aufbau ist strenger, da der Schüler nicht auf die durchschnittliche Leistung vertrauen kann; er muss für diesen spezifischen, feststehenden Satz von Fragen richtig liegen.

Für einfache Probleme mit nur zwei möglichen Antworten, wie etwa „Ja“ oder „Nein“, wissen Forscher schon lange, dass diese beiden Arten des Lernens hinsichtlich der Menge an Daten, die für den Erfolg benötigt werden, im Wesentlichen dasselbe sind. Wenn die Antworten jedoch eine von vielen Möglichkeiten sein können – wie etwa das Identifizieren von tausenden verschiedenen Vogelarten oder die Diagnose von hunderten von Krankheiten – ändern sich die Regeln. In diesen komplexen „Multiclass“-Situationen hängt die Schwierigkeit des Lernens von zwei verschiedenen mathematischen Komplexitätsmaßen ab. Ein Maß, das oft als DS-Dimension bezeichnet wird, bezieht sich darauf, wie gut der Lernende Situationen bewältigen kann, in denen eine perfekte Antwort existiert. Das andere Maß, die Natarajan-Dimension, bezieht sich darauf, wie viel Unsicherheit verbleibt, wenn keine perfekte Antwort verfügbar ist. Jahrelang war es eine offene Frage, ob die strengen „transduktiven“ Regeln den Lernenden dazu zwingen würden, mehr Daten zu benötigen als die standardmäßigen „PAC“-Regeln, insbesondere wenn die Anzahl der möglichen Antworten riesig oder sogar unendlich ist.

Ein Forscher der Johns Hopkins University hat diese Frage nun gelöst und gezeigt, dass die strengen transduktiven Regeln für Multiclass-Probleme tatsächlich nicht mehr Daten erfordern als die Standardregeln, abgesehen von sehr geringfügigen Anpassungen. Er hat bewiesen, dass die Menge an Information, die zum Lernen in diesem strengen Setting benötigt wird, durch dieselben zwei Komplexitätsmaße gesteuert wird, die auch das Standardsetting kontrollieren. Seine Arbeit zeigt, dass selbst wenn der Lernende ein einzelnes verborgenes Label aus einer festen Gruppe von Beispielen vorhersagen muss, er das gleiche Maß an Genauigkeit erreichen kann, als würde er aus einem zufälligen Datenstrom lernen. Dieser Befund ist signifikant, da er zwei verschiedene Modelle des Lernens vereinheitlicht und bestätigt, dass die fundamentalen Grenzen des Lernens durch die Natur des Problems selbst bestimmt werden und nicht durch die spezifische Art der Datenpräsentation.

Um zu diesem Schluss zu kommen, musste der Forscher eine große Hürde überwinden. In dem strengen transduktiven Setting kann ein Lernender nicht einfach alle sichtbaren Antworten betrachten und die beste Regel auswählen, da dies zu einer Art Instabilität führen kann. Wenn ein Lernender versucht, die sichtbaren Daten perfekt anzupassen, könnte er versehentlich eine Regel erstellen, die für jedes sichtbare Beispiel funktioniert, aber beim verborgenen einen völlig falschen Wert liefert. Dies ist vergleichbar mit einem Schüler, der die Antworten auf jede Übungsfrage auswendig lernt, aber den Test scheitert, weil er das zugrunde liegende Muster nicht verstanden hat. Der Forscher fand heraus, dass der Lernende, um dieser Falle zu entgehen, einen Teil der sichtbaren Daten bewusst ignorieren muss.

Die Lösung, die er entwickelte, beinhaltet eine Strategie der „zufälligen Reservierung“. Anstatt alle sichtbaren Beispiele zu nutzen, um eine Vorhersage zu erstellen, legt der Lernende einen großen Teil der sichtbaren Daten zufällig beiseite und behandelt diese so, als wären sie der verborgene Testpunkt. Indem er diese reservierten Labels ignoriert, erschafft der Lernende einen großen, ungesehenen Block von Daten, der statistisch unabhängig von der konstruierten Regel ist. Dies ermöglicht es ihm, leistungsstarke mathematische Werkzeuge zu nutzen, die auf der Idee der Generalisierung beruhen – also gut auf Daten vorherzusagen, die nicht zur Erstellung des Modells verwendet wurden. Der Lernende nutzt dann einen dreistufigen Prozess, um seine Vorhersage zu verfeinern. Zuerst verwendet er eine kleine Stichprobe der sichtbaren Daten, um eine endliche Liste möglicher Vorhersageregeln zu erstellen. Zweitens nutzt er ein gewichtetes Abstimmungssystem, um die Liste der möglichen Antworten für jede Frage einzugrenzen, wodurch die Komplexität des Problems effektiv reduziert wird. Schließlich verwendet er die verbleibenden sichtbaren Daten, um die beste Regel aus dieser eingegrenzten Liste auszuwählen.

Dieser Ansatz stützt sich auf eine neue mathematische Erkenntnis darüber, wie man mit Daten umgeht, die ohne Zurücklegen gezogen werden (Sampling ohne Zurücklegen). In vielen Lernszenarien wird angenommen, dass Datenpunkte unabhängig sind, wie beim Ziehen einer Karte aus einem Deck und dem anschließenden Zurücklegen. Aber im transduktiven Setting gilt: Sobald ein Datenpunkt gesehen wurde, kann er nicht mehr gesehen werden. Der Forscher bewies, dass selbst mit dieser Einschränkung ein bestimmter Typ von gewichtetem Abstimmungssystem effektiv funktioniert. Er zeigte, dass die „Experten“ oder Regeln in seinem System eine vorhersagbare Menge an „Belohnungen“ verdienen, basierend darauf, wie gut sie die ungesehenen Teile der Daten abdecken. Dies stellt sicher, dass der Lernende keine Genauigkeit verliert, wenn er von den sichtbaren Daten zur verborgenen Vorhersage übergeht.

Der Forscher bewies zudem, dass sein Ergebnis das bestmögliche ist, indem er spezifische Beispiele konstruierte, bei denen das Lernen schwierig wird. Er zeigte, dass, wenn ein Problem ein hohes Maß an Komplexität im Sinne einer „perfekten Antwort“ aufweist, die Fehlerrate proportional zu dieser Komplexität geteilt durch die Anzahl der Beispiele ist. Wenn ein Problem ein hohes Maß an Unsicherheit im Sinne von „keine perfekte Antwort verfügbar“ aufweist, ist die Fehlerrate proportional zur Quadratwurzel dieser Komplexität geteilt durch die Anzahl der Beispiele. Beide Faktoren sind notwendig; würde man einen davon entfernen, wäre die Lernaufgabe in bestimmten Fällen unmöglich. Dies bestätigt, dass die beiden Dimensionen der Komplexität, die in der Standard-Lerntheorie identifiziert wurden, tatsächlich auch die korrekten Maße für das strenge transduktive Setting sind.

Die Implikationen dieser Arbeit sind, dass die Lücke zwischen den beiden Lernmodellen geschlossen wurde. Für jeden, der Algorithmen für komplexe Multiclass-Probleme entwirft, bedeutet dies, dass dieselben theoretischen Grenzen gelten, egal ob die Daten als zufälliger Strom oder als fester Satz mit einer verborgenen Antwort präsentiert werden. Der Forscher lieferte kein spezifisches Algorithmus-Modell, das garantiert schnell auf einem Computer läuft, da sein Beweis auf der Informationstheorie und nicht auf der Recheneffizienz basiert. Er hat jedoch etabliert, dass die fundamentale Barriere des Lernens in beiden Welten dieselbe ist. Durch den Nachweis, dass ein strukturierter Ansatz mittels zufälliger Reservierung und Kompression den Erfolg des Standard-Lernens auf das strenge transduktive Setting übertragen kann, hat er einen klaren Fahrplan für das Verständnis der Grenzen der Vorhersage in komplexen Umgebungen geliefert.

Diese Arbeit klärt auch die Rolle unterschiedlicher Arten von Komplexität beim Lernen. Sie zeigt, dass die Fähigkeit, eine perfekte Regel zu lernen, und die Fähigkeit, eine gute Regel in Gegenwart von Rauschen zu lernen, unterschiedliche Herausforderungen sind, die jeweils eine unterschiedliche Menge an Daten erfordern. Der Forscher demonstrierte, dass sich diese Herausforderungen nicht so addieren, dass das transduktive Setting schwieriger als das Standardsetting wird. Stattdessen kann der Lernende die feste Population von Daten navigieren, indem er strategisch Teile davon ignoriert und dadurch ein schwieriges, instabiles Problem in ein handhabbares verwandelt. Das Ergebnis gilt selbst dann, wenn die Anzahl der möglichen Antworten unendlich ist – ein Szenario, in dem frühere Methoden oft scheiterten.

Am Ende bestätigt die Studie, dass die Gesetze, die bestimmen, wie Maschinen lernen, robust sind. Ob der Lernende an einem zufälligen Satz von Beispielen übt oder ein spezifisches Rätsel mit einem fehlenden Teilstück löst, die Menge an Information, die für den Erfolg benötigt wird, wird durch dieselbe zugrunde liegende Struktur des Problems bestimmt. Der Forscher hat gezeigt, dass es möglich ist, durch sorgfältiges Management der Datennutzung und durch das Verständnis der spezifischen Komplexitätsdimensionen eine optimale Leistung in den strengsten Lernumgebungen zu erzielen. Dies bietet eine solide theoretische Grundlage für zukünftige Entwicklungen im maschinellen Lernen und stellt sicher, dass Algorithmen, auch wenn sie immer ausgeklügelter werden, in einem klaren Verständnis dessen verwurzelt bleiben, was möglich ist.