Dieser Artikel ist meine freie Nacherzählung von Lernbarkeit kann unentscheidbar sein, Shai Ben-David, et al.
Vor kurzem war der Artikel Maschinelles Lernen auf Habré mit einem ungelösten mathematischen Problem konfrontiert , bei dem es sich um eine Übersetzung des Artikels von Shay Ben-David im gleichnamigen Nature News-Artikel handelt. Aufgrund der Art des Themas und der Kürze der ursprünglichen Rezension blieb mir jedoch völlig unverständlich, was in dem Artikel stand. In dem Wissen, dass Shai Ben-David als Autor des hervorragenden Buches "Verstehen von maschinellem Lernen: Von der Theorie zu Algorithmen" für mich interessant wurde, machte ich mich mit dieser Arbeit vertraut und versuchte, die wichtigsten Punkte hier zu skizzieren.
Ich muss sofort sagen, dass der Artikel ziemlich kompliziert ist und ich vielleicht einige wichtige Punkte übersehen habe, aber meine Rezension wird vollständiger sein als die, die bereits auf Habré ist.
Ein paar Worte zum PAC-Lernen im Allgemeinen
Das erste, was mich in einem Rückblick von Nature News verwirrte, war, dass das Lernproblem selbst als etwas völlig Neues dargestellt wurde. Tatsächlich ist dies ein langwieriges und relativ gut untersuchtes Problem.
Einige grundlegende Konzepte für diejenigen, die mit der Frage nicht vertraut sindRisiko ist eine Funktion von - der reale und vorhergesagte Wert der Zielvariablen, der widerspiegelt, wie falsch wir bei unserer Vorhersage waren. Ein niedrigerer Wert zeigt einen kleineren Fehler an. Das einfachste Beispiel für ein Klassifizierungsproblem ist eine Indikatorfunktion. . Für die Regression ist dies die Standardabweichung . Offensichtlich kann es komplexere Optionen geben. Ein anderer Name für dieses Konzept ist die Verlustfunktion.
Durchschnittliches Risiko - Der durchschnittliche Risikowert über den gesamten Eingabedatenbereich. Aufgrund der Tatsache, dass ein solcher Raum normalerweise unendlich (z. B. für reale Merkmale) oder exponentiell groß (z. B. ein Raum mit Bildern der Größe 1024 x 1024 und Pixelwerten von 0 bis 255) ist, können wir diesen Wert nicht direkt schätzen. Es gibt jedoch Methoden zur Schätzung dieser Menge, auf die wir jetzt nicht eingehen werden. Diesen Indikator wollen wir letztendlich minimieren. Manchmal wird dieser Indikator auch als Generalisierungsfehler bezeichnet.
Das empirische Risiko ist der Durchschnittswert des Risikos für einen bestimmten empirischen Datensatz, der aus dem gesamten Eingabedatenraum ausgewählt wird. Normalerweise sind unsere Algorithmen für maschinelles Lernen daran beteiligt, diesen Wert zu minimieren.
Die Aufgabe des maschinellen Lernens besteht darin, auf der Grundlage der verfügbaren empirischen Daten eine Lösung (Funktion) zu erstellen, die einen Mindestwert für das durchschnittliche Risiko ergibt.
Es gibt eine Theorie des wahrscheinlich fast korrekten Lernens (wahrscheinlich ein ungefähr korrektes Lernen, PAC ).
Vereinfachte Definition eines PAC-geschulten Algorithmus für maschinelles LernenAlgorithmus Ein Konstrukt unter Verwendung einer empirischen Stichprobe X der Größe n, eine Funktion h , die den Wert der Zielvariablen wiederherstellt, wird PAC-trainiert, wenn für irgendeinen Schwellenwert und Vertrauen es gibt eine solche Größe der Trainingsstichprobe n, dass für die darauf erlernte Funktion die folgende Bedingung erfüllt ist: die Wahrscheinlichkeit, dass der durchschnittliche Risikowert überschritten wird , weniger als .
Wir können es so verstehen: Nachdem wir einige unserer Anforderungen für die Funktion h unter dem Gesichtspunkt ihres mittleren Risikowerts ausgewählt haben, werden wir wissen, dass es eine solche Größe des Datensatzes gibt (ausgewählt, offensichtlich unabhängig und zufällig vom gesamten Raum), dass wir, wenn wir darauf lernen Wir werden diese Anforderungen erfüllen.
Diese Theorie stammt aus den 80er Jahren des letzten Jahrhunderts. Es liefert jedoch keinen messbaren Indikator, der die Lernfähigkeit eines Algorithmus widerspiegeln würde. Eine solche Antwort liefert jedoch die Theorie des statistischen Lernens ( VC-Theorie ), die bereits von V. Vapnik und A. Chervonenkis entwickelt wurde. Diese Theorie basiert auf einem numerischen Indikator der VC-Dimension. Die VC-Dimension ist eine kombinatorische Schätzung der maximalen Datengröße, die der Algorithmus auf alle möglichen Arten in zwei Teile teilen kann.
BeispielAngenommen, wir haben einen Algorithmus, der eine Trennungs-Hyperebene in einem n-dimensionalen Raum erstellt. Stellen Sie sich einen eindimensionalen Raum vor: Zwei Punkte in einem solchen Raum können immer geteilt werden, aber drei können nicht mehr geteilt werden, was bedeutet, dass VC = 2 ist. Stellen Sie sich einen zweidimensionalen Raum vor: Drei Punkte werden immer in zwei Klassen unterteilt, aber vier Punkte können nicht mit allen möglichen Mitteln unterteilt werden, sodass VC = 3 ist.
Tatsächlich kann genau gezeigt werden, dass VC für eine Klasse von Hyperebenen in einem n-dimensionalen Raum ist .
Der Hauptsatz der VC-Theorie, in einer der möglichen Formulierungen, beweist die Tatsache, dass, wenn die VC-Dimension des Algorithmus endlich ist, es PAC-trainiert ist. Darüber hinaus ist die VC-Dimension ein Indikator dafür, wie schnell sich der Wert des empirischen Risikos mit zunehmender empirischer Stichprobengröße dem Wert des durchschnittlichen Risikos annähert.
Somit ist das Problem des maschinellen Lernens von Algorithmen für maschinelles Lernen an sich relativ gut untersucht und auf einer strengen mathematischen Grundlage.
Worum geht es dann in einem Artikel in Nature?
Die Autoren schreiben, dass das Problem mit der PAC-Theorie, basierend auf verschiedenen Dimensionen der Dimension, ist, dass es nicht universell ist.
Verschiedene Dimensionsindikatoren aus der PAC-Theorie Die Autoren geben ein interessantes Beispiel für ein Problem, dessen Aussage selbst so gestaltet ist, dass Erfolg nicht als PAC-Lernen formuliert werden kann. Die Autoren schreiben:
Stellen Sie sich vor, wir haben eine Internetseite, auf der wir Anzeigen schalten. Definieren Sie X als die Menge aller potenziellen Besucher dieser Site. Werbung wird aus einem bestimmten Werbepool ausgewählt. Angenommen, jede Anzeige aus dem Pool richtet sich an eine bestimmte Nutzerkategorie: Sportanzeigen an Sportfans usw. Die Aufgabe besteht darin, genau die Art von Werbung zu schalten, die für die Besucher der Website am relevantesten ist .
Das Problem dabei ist, dass wir nicht wirklich wissen, wer die Site in Zukunft besuchen wird. Zusammenfassend lässt sich die Feststellung eines solchen Problems wie folgt beschreiben:
Einen Funktionsumfang haben über dem Set finde eine solche Funktion so dass seine Metrik über die unbekannte Verteilung war maximal. Darüber hinaus ist es notwendig, eine solche Funktion auf der Grundlage eines begrenzten Satzes von unabhängigen, identisch verteilten Größen zu finden
EMX-Schulung
Shai Ben-David und seine Kollegen stellen ein neues Konzept vor - E stimulieren das M a X imum (EMX-Lernen), das nur Lernkriterien für solche Maximierungsprobleme enthält:
Für Funktionsumfang Sätze von Eingaben und unbekannte Verbreitung für eine beliebige Anzahl funktion ist -EMX-geschult, wenn für den Vertrieb :
Diese Definition des Lernens ist zweifellos allgemeiner als das Konzept der PAC.
Wo hat dann das Kontinuum und das „ungelöste Problem der Mathematik“ damit zu tun?
Die Autoren beweisen folgenden Satz:
EMX-Umsatz in Bezug auf unabhängig vom Zermelo-Frenkel-Axiomensystem mit dem Axiom der Wahl (nachfolgend ZFC).
Mit anderen Worten, mit Hilfe von mathematischen Standardaxiomen können wir im Allgemeinen weder die Möglichkeit nachweisen, eine Lösung für das EMX-Lernproblem zu finden, noch die Unmöglichkeit, diese Lösung zu finden.
Die Autoren zeigen auch, dass es für den allgemeinen Fall des EMX-Lernens kein Analogon der VC-Dimension (oder einer anderen Dimension) gibt, das im Fall der EMX-Messbarkeit endlich wäre, und umgekehrt würde sich die EMX-Lernbarkeit aus ihrer Endlichkeit ergeben. Genauer gesagt haben sie es wie folgt formuliert:
Es gibt so eine Konstante Wenn wir die Konsistenz von ZFC annehmen, gibt es keine solche Eigenschaft das für einige $ inline $ m, M> c $ inline $ für jeden und Funktionsumfang würde durchgeführt werden:
- Wenn wahr dann Komplexität des EMX-Lernens überschreitet nicht M;
- Wenn dann falsch Komplexität des EMX-Lernens mindestens m;
Dies gilt im Gegenteil beispielsweise für die VC-Dimension, da z gleich Es wird im Wesentlichen eine Formulierung des Hauptsatzes der VC-Theorie sein.
Fazit
Die Botschaft der Arbeit hat in der Tat wenig mit den praktischen Fragen des maschinellen Lernens oder sogar mit den theoretischen Fragen der Theorie des statistischen Lernens zu tun. Mir schien, dass die Arbeit zwei Hauptgedanken enthält:
- Eine schöne Verbindung zwischen EMX-Lernen und Gödels Theoremen;
- Die grundsätzliche Unmöglichkeit, eine universelle Charakterisierung des Lernens (wie die VC-Dimension) für die allgemeine Klasse der Probleme des maschinellen Lernens zu erstellen.
Gleichzeitig mag ich persönlich die Überschrift "Maschinelles Lernen hat ein ungelöstes mathematisches Problem festgestellt", die bei der Übersetzung einer Rezension dieses Artikels verwendet wurde, überhaupt nicht . Meiner Meinung nach ist dies ein absoluter Clickbait, außerdem entspricht er einfach nicht der Realität. Die ursprüngliche Arbeit bedeutet nicht, dass jemand auf etwas gestoßen ist. Maschinelles Lernen und PAC-Theorie funktionierten und arbeiten weiter. Es wird darauf hingewiesen, dass die PAC-Theorie nicht auf bestimmte Aussagen zum Problem des maschinellen Lernens verallgemeinert werden kann, sondern interessante Zusammenhänge mit Gödels Theoremen gefunden werden, jedoch kein Wort über ein ungelöstes Problem, auf das das maschinelle Lernen gestoßen ist.