Generalisierungsfehler - Generalization error

Für überwachte Lernanwendungen im Bereich des maschinellen Lernens und der statistischen Lerntheorie ist der Generalisierungsfehler (auch als Out-of-Sample-Fehler oder Risiko bezeichnet ) ein Maß dafür, wie genau ein Algorithmus Ergebniswerte für zuvor nicht sichtbare Daten vorhersagen kann. Da Lernalgorithmen an endlichen Stichproben bewertet werden, kann die Bewertung eines Lernalgorithmus empfindlich auf Stichprobenfehler reagieren . Infolgedessen liefern Messungen des Vorhersagefehlers an den aktuellen Daten möglicherweise nicht viele Informationen über die Vorhersagefähigkeit neuer Daten. Generalisierungsfehler können minimiert werden, indem eine Überanpassung des Lernalgorithmus vermieden wird . Die Leistung eines Algorithmus für maschinelles Lernen wird durch Diagramme visualisiert, die Werte von Schätzungen des Generalisierungsfehlers während des Lernprozesses zeigen, die als Lernkurven bezeichnet werden .

Definition

In einem Lernproblem besteht das Ziel darin, eine Funktion zu entwickeln , die Ausgabewerte für jedes Eingabedatum vorhersagt . Der Index gibt an, dass die Funktion basierend auf einem Datensatz von Datenpunkten entwickelt wurde. Der Generalisierungsfehler oder erwartete Verlust oder Risiko , eine bestimmten Funktion über alle möglichen Werte von und ist: ${\ displaystyle f_ {n} ({\ vec {x}})}$${\ displaystyle y}$${\ displaystyle {\ vec {x}}}$${\ displaystyle n}$${\ displaystyle f_ {n}}$${\ displaystyle n}$${\ displaystyle I [f]}$${\ displaystyle f}$${\ displaystyle {\ vec {x}}}$${\ displaystyle y}$

${\ displaystyle I [f] = \ int _ {X \ mal Y} V (f ({\ vec {x}}), y) \ rho ({\ vec {x}}, y) d {\ vec { x}} dy,}$

wobei eine Verlustfunktion bezeichnet und die unbekannte gemeinsame Wahrscheinlichkeitsverteilung für und ist . ${\ displaystyle V}$${\ displaystyle \ rho ({\ vec {x}}, y)}$${\ displaystyle {\ vec {x}}}$${\ displaystyle y}$

Ohne Kenntnis der gemeinsamen Wahrscheinlichkeitsverteilung ist eine Berechnung unmöglich . Stattdessen können wir den Fehler anhand von Probendaten berechnen, der als empirischer Fehler (oder empirisches Risiko ) bezeichnet wird. Bei gegebenen Datenpunkten ist der empirische Fehler einer Kandidatenfunktion : ${\ displaystyle \ rho}$${\ displaystyle I [f]}$${\ displaystyle n}$${\ displaystyle f}$

${\ displaystyle I_ {n} [f] = {\ frac {1} {n}} \ sum _ {i = 1} ^ {n} V (f ({\ vec {x}} _ {i}), y_ {i})}$

Ein Algorithmus soll verallgemeinern, wenn:

${\ displaystyle \ lim _ {n \ rightarrow \ infty} I [f] -I_ {n} [f] = 0}$

Von besonderer Bedeutung ist der Generalisierungsfehler der datenabhängigen Funktion , der von einem auf der Stichprobe basierenden Lernalgorithmus gefunden wird. Auch hier kann für eine unbekannte Wahrscheinlichkeitsverteilung nicht berechnet werden. Stattdessen besteht das Ziel vieler Probleme in der statistischen Lerntheorie darin, den Unterschied zwischen dem Generalisierungsfehler und dem empirischen Wahrscheinlichkeitsfehler zu begrenzen oder zu charakterisieren: ${\ displaystyle I [f_ {n}]}$${\ displaystyle f_ {n}}$${\ displaystyle I [f_ {n}]}$

${\ displaystyle P_ {G} = P (I [f_ {n}] - I_ {n} [f_ {n}] \ leq \ epsilon) \ geq 1- \ delta _ {n}}$

Das heißt, das Ziel besteht darin, die Wahrscheinlichkeit zu charakterisieren, dass der Generalisierungsfehler kleiner als der empirische Fehler plus eine gewisse Fehlergrenze ist (im Allgemeinen abhängig von und ). Für viele Arten von Algorithmen wurde gezeigt, dass ein Algorithmus Generalisierungsgrenzen aufweist, wenn er bestimmte Stabilitätskriterien erfüllt. Insbesondere wenn ein Algorithmus symmetrisch ist (die Reihenfolge der Eingaben hat keinen Einfluss auf das Ergebnis), einen begrenzten Verlust aufweist und zwei Stabilitätsbedingungen erfüllt, wird er verallgemeinert. Die erste Stabilitätsbedingung, die Stabilität der einmaligen Kreuzvalidierung , besagt, dass der Vorhersagefehler für jeden Datenpunkt bei Verwendung der einmaligen Kreuzvalidierung gegen Null konvergieren muss, um stabil zu sein . Die zweite Bedingung, die erwartete Fehlerstabilität (auch als Hypothesenstabilität bezeichnet, wenn in der Norm gearbeitet wird ), ist erfüllt, wenn sich die Vorhersage für einen ausgelassenen Datenpunkt nicht ändert, wenn ein einzelner Datenpunkt aus dem entfernt wird Trainingsdatensatz. ${\ displaystyle 1- \ delta _ {n}}$${\ displaystyle \ epsilon}$${\ displaystyle \ delta}$${\ displaystyle n}$${\ displaystyle n \ rightarrow \ infty}$${\ displaystyle L_ {1}}$

Diese Bedingungen können wie folgt formalisiert werden:

Ausgelassene Kreuzvalidierungsstabilität

Ein Algorithmus hat Stabilität, wenn für jeden ein und ein solches existiert, dass: ${\ displaystyle L}$${\ displaystyle CVloo}$${\ displaystyle n}$${\ displaystyle \ beta _ {CV} ^ {(n)}}$${\ displaystyle \ delta _ {CV} ^ {(n)}}$

${\ displaystyle \ forall i \ in \ {1, ..., n \}, \ mathbb {P} _ {S} \ {| V (f_ {S ^ {i}}, z_ {i}) - V. (f_ {S}, z_ {i}) | \ leq \ beta _ {CV} ^ {(n)} \} \ geq 1- \ delta _ {CV} ^ {(n)}}$

und und gehe auf Null wie geht ins Unendliche. ${\ displaystyle \ beta _ {CV} ^ {(n)}}$${\ displaystyle \ delta _ {CV} ^ {(n)}}$${\ displaystyle n}$

Erwarteter Auslassfehler Stabilität

Ein Algorithmus hat Stabilität, wenn für jeden ein und ein solcher existiert, dass: ${\ displaystyle L}$${\ displaystyle Eloo_ {err}}$${\ displaystyle n}$${\ displaystyle \ beta _ {EL} ^ {m}}$${\ displaystyle \ delta _ {EL} ^ {m}}$

${\ displaystyle \ forall i \ in \ {1, ..., n \}, \ mathbb {P} _ {S} \ left \ {\ left | I [f_ {S}] - {\ frac {1} {n}} \ sum _ {i = 1} ^ {N} V \ left (f_ {S ^ {i}}, z_ {i} \ right) \ right | \ leq \ beta _ {EL} ^ {( n)} \ right \} \ geq 1- \ delta _ {EL} ^ {(n)}}$

mit und auf Null gehen für . ${\ displaystyle \ beta _ {EL} ^ {(n)}}$${\ displaystyle \ delta _ {EL} ^ {(n)}}$${\ displaystyle n \ rightarrow \ infty}$

Für die Auslassungsstabilität in der Norm entspricht dies der Hypothesenstabilität: ${\ displaystyle L_ {1}}$

${\ displaystyle \ mathbb {E} _ {S, z} [| V (f_ {S}, z) -V (f_ {S ^ {i}}, z) |] \ leq \ beta _ {H} ^ {(n)}}$

mit auf Null gehen wie auf unendlich. ${\ displaystyle \ beta _ {H} ^ {(n)}}$${\ displaystyle n}$

Algorithmen mit nachgewiesener Stabilität

Eine Reihe von Algorithmen hat sich als stabil erwiesen und hat daher Grenzen für ihren Generalisierungsfehler. Eine Liste dieser Algorithmen und der Papiere, die Stabilität bewiesen haben, finden Sie hier .

Verhältnis zur Überanpassung

Diese Figur zeigt die Beziehung zwischen Überanpassung und dem Generalisierungsfehler I [ f _n ] - I _S [ f _n ]. Datenpunkte wurden aus der Beziehung y = x mit weißem Rauschen zu den y- Werten erzeugt. In der linken Spalte wird eine Reihe von Trainingspunkten blau angezeigt. Eine Polynomfunktion siebter Ordnung wurde an die Trainingsdaten angepasst. In der rechten Spalte wird die Funktion anhand von Daten getestet, die aus der zugrunde liegenden gemeinsamen Wahrscheinlichkeitsverteilung von x und y entnommen wurden . In der oberen Reihe wird die Funktion auf einen Beispieldatensatz mit 10 Datenpunkten angepasst. In der unteren Zeile wird die Funktion auf einen Beispieldatensatz mit 100 Datenpunkten angepasst. Wie wir sehen können, ist bei kleinen Stichprobengrößen und komplexen Funktionen der Fehler im Trainingssatz gering, aber der Fehler in der zugrunde liegenden Datenverteilung ist groß und wir haben die Daten überangepasst. Infolgedessen ist der Generalisierungsfehler groß. Wenn die Anzahl der Abtastpunkte zunimmt, konvergiert der Vorhersagefehler bei Trainings- und Testdaten und der Generalisierungsfehler geht auf 0.

Die Konzepte von Generalisierungsfehler und Überanpassung sind eng miteinander verbunden. Eine Überanpassung tritt auf, wenn die gelernte Funktion für das Rauschen in der Probe empfindlich wird. Infolgedessen ist die Funktion für den Trainingssatz gut, für andere Daten aus der gemeinsamen Wahrscheinlichkeitsverteilung von und jedoch nicht gut . Je mehr Überanpassungen auftreten, desto größer ist der Generalisierungsfehler. ${\ displaystyle f_ {S}}$${\ displaystyle x}$${\ displaystyle y}$

Das Ausmaß der Überanpassung kann mithilfe von Kreuzvalidierungsmethoden getestet werden , bei denen die Probe in simulierte Trainingsmuster und Testmuster aufgeteilt wird. Das Modell wird dann an einer Trainingsprobe trainiert und an der Testprobe bewertet. Die Teststichprobe wurde bisher vom Algorithmus nicht gesehen und stellt somit eine Zufallsstichprobe aus der gemeinsamen Wahrscheinlichkeitsverteilung von und dar . Dieses Testbeispiel ermöglicht es uns, den erwarteten Fehler und als Ergebnis eine bestimmte Form des Generalisierungsfehlers zu approximieren. ${\ displaystyle x}$${\ displaystyle y}$

Es gibt viele Algorithmen, um eine Überanpassung zu verhindern. Der Minimierungsalgorithmus kann komplexere Funktionen bestrafen (bekannt als Tikhonov- Regularisierung ), oder der Hypothesenraum kann entweder explizit in Form der Funktionen oder durch Hinzufügen von Einschränkungen zur Minimierungsfunktion (Ivanov-Regularisierung) eingeschränkt werden.

Der Ansatz, eine Funktion zu finden, die nicht überpasst, steht im Widerspruch zu dem Ziel, eine Funktion zu finden, die ausreichend komplex ist, um die besonderen Merkmale der Daten zu erfassen. Dies ist als Bias-Varianz-Kompromiss bekannt . Wenn Sie eine Funktion einfach halten, um eine Überanpassung zu vermeiden, kann dies zu einer Verzerrung der resultierenden Vorhersagen führen, während eine komplexere Funktion zu einer Überanpassung und einer höheren Varianz der Vorhersagen führt. Es ist unmöglich, beide gleichzeitig zu minimieren.

Verweise

Weiterführende Literatur

• Bousquet, O., S. Boucheron und G. Lugosi. Einführung in die statistische Lerntheorie . Fortgeschrittene Vorlesungen zum maschinellen Lernen Vorlesungsunterlagen in Künstlicher Intelligenz 3176, 169-207. (Hrsg.) Bousquet, O., U. von Luxburg und G. Ratsch, Springer, Heidelberg, Deutschland (2004)
• Bousquet, O. und A. Elisseef (2002), Stabilität und Verallgemeinerung, Journal of Machine Learning Research, 499-526.
• Devroye L., L. Gyorfi und G. Lugosi (1996). Eine probabilistische Theorie der Mustererkennung. Springer-Verlag. ISBN   978-0387946184 .
• Poggio T. und S. Smale. Die Mathematik des Lernens: Umgang mit Daten . Mitteilungen des AMS, 2003
• Vapnik, V. (2000). Die Natur der statistischen Lerntheorie. Informationswissenschaft und Statistik. Springer-Verlag. ISBN   978-0-387-98780-4 .
• Bishop, CM (1995), Neuronale Netze zur Mustererkennung , Oxford: Oxford University Press, insbesondere Abschnitt 6.4.
• Finke, M. und Müller, K.-R. (1994), " Schätzung a-posteriori-Wahrscheinlichkeiten unter Verwendung stochastischer Netzwerkmodelle ", in Mozer, Smolensky, Touretzky, Elman & Weigend, Hrsg., Proceedings of the 1993 Connectionist Models Summer School , Hillsdale, NJ: Lawrence Erlbaum Associates, pp. 324–331.
• Geman, S., Bienenstock, E. und Doursat, R. (1992), " Neuronale Netze und das Bias / Varianz-Dilemma ", Neural Computation , 4, 1-58.
• Husmeier, D. (1999), Neuronale Netze zur bedingten Wahrscheinlichkeitsschätzung: Vorhersage über Punktvorhersagen hinaus , Berlin: Springer Verlag, ISBN   1-85233-095-3 .
• McCullagh, P. und Nelder, JA (1989) Generalized Linear Models , 2. Auflage, London: Chapman & Hall.
• Mohri, M., Rostamizadeh A., Talwakar A., ​​(2018) Grundlagen des maschinellen Lernens , 2. Aufl., Boston: MIT Press.
• Moody, JE (1992), " Die effektive Anzahl von Parametern: Eine Analyse der Generalisierung und Regularisierung in nichtlinearen Lernsystemen ", in Moody, JE, Hanson, SJ und Lippmann, RP, Fortschritte in neuronalen Informationsverarbeitungssystemen 4, 847- 854.
• Ripley, BD (1996) Mustererkennung und neuronale Netze , Cambridge: Cambridge University Press.
• Rohwer, R. und van der Rest, JC (1996), " Minimum Description Length, Regularization and Multimodal Data ", Neural Computation , 8, 595-609.
• Rojas, R. (1996), " Ein kurzer Beweis der posterioren Wahrscheinlichkeitseigenschaft von Klassifikator-Neuronalen Netzen ", Neural Computation , 8, 41-43.
• White, H. (1990), " Connectionist Nonparametric Regression: Mehrschichtige Feedforward-Netzwerke können beliebige Zuordnungen lernen ", Neural Networks , 3, 535-550. Nachdruck in Weiß (1992).
• White, H. (1992a), " Nonparametric Estimation of Conditional Quantiles Using Neural Networks ", in Page, C. und Le Page, R. (Hrsg.), Proceedings of the 23. Sympsium on the Interface: Computing Science and Statistics , Alexandria , VA: American Statistical Association, S. 190–199. Nachdruck in Weiß (1992b).
• White, H. (1992b), Künstliche Neuronale Netze: Approximations- und Lerntheorie , Blackwell.