Verzerrung-Varianz-Dilemma

Varianz und Verzerrung (Bias)

Das Verzerrung-Varianz-Dilemma (häufig auch englisch bias-variance tradeoff) beschreibt das Problem der gleichzeitigen Minimierung zweier Fehlerquellen: der Verzerrung und der Varianz. Das Dilemma erschwert das Verallgemeinern von Trainingsdaten auf die Testdaten bei überwachtem Lernen.

• Die Verzerrung ist der Fehler ausgehend von falschen Annahmen im Lernalgorithmus. Eine hohe Verzerrung kann einen Algorithmus dazu veranlassen, nicht die entsprechenden Beziehungen zwischen Eingabe und Ausgabe zu modellieren (Unteranpassung).
• Die Varianz ist der Fehler ausgehend von der Empfindlichkeit auf kleinere Schwankungen in den Trainingsdaten. Eine hohe Varianz verursacht Überanpassung: es wird das Rauschen in den Trainingsdaten statt der vorgesehenen Ausgabe modelliert.

Die Verzerrung-Varianz-Zerlegung bietet die Möglichkeit, den erwarteten Fehler eines Lernalgorithmus im Hinblick auf ein bestimmtes Problem zu analysieren, und kann als Summe aus drei Termen dargestellt werden: Der Verzerrung, der Varianz und einem irreduziblen Fehler (siehe auch Bayes-Fehler), resultierend aus dem Rauschen innerhalb des Problems selbst.

Das Verzerrung-Varianz-Dilemma gilt für alle Formen des überwachten Lernens: Klassifikation, Regression, und strukturiertes Lernen.

Das Dilemma betrifft die Bereiche Statistik und des maschinellen Lernens. Es wurde auch genutzt, um die Wirksamkeit von Heuristiken beim menschlichen Lernen zu erklären.

Motivation

Das Verzerrung-Varianz-Dilemma ist ein zentrales Problem beim überwachten Lernen. Idealerweise möchte man ein Modell wählen, das sowohl die Gesetzmäßigkeiten in den Trainingsdaten genau erfasst, als auch sich auf ungesehene Testdaten generalisieren lässt. Leider ist es in der Regel unmöglich, beides gleichzeitig zu tun. Lernmethoden mit hoher Varianz können möglicherweise ihre Trainingsdaten gut darstellen, aber riskieren Überanpassung bei zu rauschbehafteten oder nicht repräsentativen Trainingsdaten. Im Gegensatz dazu erzeugen Algorithmen mit einer hohen Verzerrung typischerweise einfachere Modelle, die nicht zur übermäßigen Überanpassung neigen, aber möglicherweise ihre Trainingsdaten nicht hinreichend gut modellieren und wichtige Gesetzmäßigkeiten nicht erfassen.

Modelle mit hoher Varianz sind in der Regel komplexer (z. B. Regression mit Polynomen höherer Ordnung), was ihnen erlaubt die Trainingsdaten genauer darzustellen. Dabei stellen sie unter Umständen auch einen Großteil des Rauschens in den Trainingsdaten dar, so dass ihre Vorhersagen weniger genau werden – trotz ihrer zusätzlichen Komplexität. Dagegen neigen Modelle mit höherer Verzerrung in der Regel dazu relativ einfach zu sein (z. B. Regression mit Polynomen niedriger Ordnung oder einfache lineare Regression), aber können Vorhersagen mit niedrigerer Varianz produzieren, wenn sie über die Trainingsdaten hinaus auf neue Daten angewendet werden.

Verzerrung-Varianz-Zerlegung der quadratischen Abweichung

Gesamtfehler sowie die Aufteilung in Verzerrung und Varianz als Funktion der Modellkomplexität. Ein ähnliches Bild ergibt sich, wenn man statt der Modellkomplexität die Stärke der Regularisierung betrachtet.

Das Verzerrungs-Varianz-Dilemma liegt vor, wenn die Varianz klein ist, aber die Richtigkeit schlecht ist (hohe Verzerrung), bzw. die Varianz hoch ist und die Richtigkeit gut ist (kleine Verzerrung).

Gegeben seien Trainingsdaten, bestehend aus einer Menge von Punkten $x_{1},\dots ,x_{n}$ mit dazugehörigen reellen Werten $y_{1},\ldots ,y_{n}$. Es wird angenommen, dass es zwischen $x_{i}$ und $y_{i}$ einen funktionellen, aber rauschbehafteten Bezug gibt, der durch $y_{i}=f(x_{i})+\epsilon$ beschrieben wird, wobei der Rauschterm $\epsilon$ normalverteilt ist und Erwartungswert Null und Varianz $\sigma ^{2}$ besitzt.

Nun soll mit Hilfe eines Lernalgorithmus eine Funktion ${\hat {f}}(x)$ gefunden werden, welche die wahre Funktion $y=f(x)$ (genauer: den bedingten Erwartungswert $f(x)=E_{y|x}[y]$) so gut wie möglich annähert. Die Genauigkeit dieser Approximation wird anhand der mittleren quadratischen Abweichung zwischen $y$ und ${\hat {f}}(x)$ gemessen: dabei soll $(y-{\hat {f}}(x))^{2}$ sowohl für $x_{1},\dots ,x_{n}$ als auch für Punkte außerhalb der Stichprobe minimiert werden. Eine optimale Annäherung ist unmöglich, da $y$ vom Rauschen $\epsilon$ beeinflusst wird. Dies bedeutet, dass für jede Funktion, die gefunden wird, ein irreduzibler Fehler akzeptiert werden muss.

Die Ermittlung einer Funktion ${\hat {f}}$, die sich auf neue Punkte $(X,Y)\sim P(X,Y)$ außerhalb der Trainingsmenge ${\mathcal {D}}=\{(X_{1},Y_{1}),\dots (X_{n},Y_{n})\}\sim P(X,Y)^{n}$ verallgemeinern lässt, geschieht mit einem der vielen Algorithmen, die zum überwachten Lernen genutzt werden. Es stellt sich heraus, dass abhängig von der Wahl der Funktion ${\hat {f}}$ die erwartete Abweichung (vergleiche empirische Risikominimierung) wie folgt zerlegt werden kann:

${\begin{aligned}\mathrm {E} _{{\mathcal {D}},(x,y)}{\Big [}{\big (}y-{\hat {f}}(x){\big )}^{2}{\Big ]}&=\mathrm {Bias} ^{2}{\big [}{\hat {f}}(x){\big ]}+\mathrm {Var} {\big [}{\hat {f}}(x){\big ]}+\sigma ^{2}.\\\end{aligned}}$

Hierbei ist der Erwartungswert $\mathrm {E} _{{\mathcal {D}},(x,y)}$ über verschiedene Trainingsdatensätze ${\mathcal {D}}$ sowie (unabhängig vom Trainingsdatensatz) gepaarte Testpunkte $(x,y)$ zu verstehen. Der Erwartungswert $\mathrm {E} _{\mathcal {D}}$ ist als Erwartungswert über unterschiedliche Trainingsdatensätzen zu verstehen, auf denen das Modell trainiert wird

Es beschreibt

${\begin{aligned}\mathrm {Bias} ^{2}{\big [}{\hat {f}}(x){\big ]}:=\mathrm {E} _{x}{\big [}\left(\underbrace {E_{\mathcal {D}}[{\hat {f}}(x)]-f(x)} _{\mathrm {Bias(x)} }\right)^{2}{\big ]}\end{aligned}}$

die Verzerrung der Lernmethode und

${\begin{aligned}\mathrm {Var} {\big [}{\hat {f}}(x){\big ]}=\mathrm {E} _{x,{\mathcal {D}}}{\Big [}{\big (}{\hat {f}}(x)-\mathrm {E} _{\mathcal {D}}[{\hat {f}}(x)]{\big )}^{2}{\Big ]}\end{aligned}}$

ihre Varianz und

${\begin{aligned}\sigma ^{2}=\mathrm {E} _{x,y}{\Big [}{\big (}f(x)-y{\big )}^{2}{\Big ]}=E[\epsilon ^{2}]\end{aligned}}.$

Die drei Terme repräsentieren:

• das Quadrat der Verzerrung der Lernmethode, welcher als Fehler, verursacht durch vereinfachende Annahmen innerhalb des Verfahrens, interpretiert werden kann. Falls beispielsweise eine nichtlineare Funktion $f(x)$ unter Verwendung eines Lernverfahrens für lineare Modelle approximiert wird, gibt es aufgrund einer solchen Annahme Fehler in den Schätzungen ${\hat {f}}(x)$.
• die Varianz der Lernmethode. Intuitiv beschreibt dies die Schwankungsbreite der Lernmethode ${\hat {f}}(x)$ um ihren Erwartungswert.
• den irreduziblen Fehler $\sigma ^{2}$. Da alle drei Terme nicht negativ sind, stellt dieser Fehler eine untere Schranke für die erwartete Abweichung auf ungesehenen Testdaten dar.

Je komplexer die Modellfunktion ${\hat {f}}(x)$ ist, desto mehr Datenpunkte wird sie richtig erfassen und desto geringer wird ihre Verzerrung sein. Allerdings lässt eine höhere Komplexität die Modellfunktion mehr schwanken, um die Datenpunkte besser zu erfassen, was somit ihre Varianz vergrößert.

Herleitung

Die Herleitung der Verzerrung-Varianz-Zerlegung für quadratische Abweichungen läuft folgendermaßen ab. Abkürzend wird im Folgenden $f=f(x)$ und ${\hat {f}}={\hat {f}}(x)$ geschrieben. Nach dem Verschiebungssatz gilt für jede Zufallsvariable $X$

$\mathrm {E} [X^{2}]=\mathrm {Var} [X]+\mathrm {E} [X]^{2}$

Da $f$ deterministisch ist, gilt $\mathrm {E} [f]=f$. Zusammen mit den Annahmen $y=f+\epsilon$ und $\mathrm {E} [\epsilon ]=0$ impliziert dies

$\mathrm {E} [y]=\mathrm {E} [f+\epsilon ]=\mathrm {E} [f]=f$.

Da $\mathrm {Var} [\epsilon ]=\sigma ^{2}$ gilt, folgt

$\mathrm {Var} [y]=\mathrm {E} [(y-\mathrm {E} [y])^{2}]=\mathrm {E} [(y-f)^{2}]=\mathrm {E} [(f+\epsilon -f)^{2}]=\mathrm {E} [\epsilon ^{2}]=\mathrm {Var} [\epsilon ]+\mathrm {E} [\epsilon ]^{2}=\sigma ^{2}$.

Folglich ergibt sich, da $\epsilon$ und ${\hat {f}}$ unabhängig sind,

${\begin{aligned}\mathrm {E} {\big [}(y-{\hat {f}})^{2}{\big ]}&=\mathrm {E} [y^{2}+{\hat {f}}^{2}-2y{\hat {f}}]=\mathrm {E} [y^{2}]+\mathrm {E} [{\hat {f}}^{2}]-\mathrm {E} [2y{\hat {f}}]\\&=\mathrm {Var} [y]+\mathrm {E} [y]^{2}+\mathrm {Var} [{\hat {f}}]+\mathrm {E} [{\hat {f}}]^{2}-2f\mathrm {E} [{\hat {f}}]=\mathrm {Var} [y]+\mathrm {Var} [{\hat {f}}]+(f-\mathrm {E} [{\hat {f}}])^{2}\\&=\mathrm {Var} [y]+\mathrm {Var} [{\hat {f}}]+\mathrm {E} [f-{\hat {f}}]^{2}=\sigma ^{2}+\mathrm {Var} [{\hat {f}}]+\mathrm {Bias} [{\hat {f}}]^{2}.\end{aligned}}$

Anwendung zur Klassifizierung

Die Verzerrung-Varianz-Zerlegung wurde ursprünglich für die Regressionsanalyse als Methode der kleinsten Quadrate formuliert. Für den Fall der Klassifizierung ist es möglich, eine ähnliche Zerlegung zu finden. Wenn das Klassifikationsproblem alternativ als probabilistischer Klassifikator formuliert werden kann, so lässt sich die erwartete quadratische Abweichung der vorhergesagten Wahrscheinlichkeiten in Bezug auf die wahren Wahrscheinlichkeiten wie zuvor zerlegen.

Ansätze zur Problemlösung

Dimensionsreduktion und Feature Selection können die Varianz durch Modellvereinfachung verringern. Ebenso neigt ein größerer Satz an Trainingsdaten dazu, die Varianz zu verringern. Das Hinzufügen von Features (Prädiktoren) verringert die Verzerrung, auf Kosten der zusätzlichen erhöhten Varianz. Lernalgorithmen haben in der Regel einige Parameter, um die Verzerrung sowie Varianz zu steuern:

• (Generalisierte) lineare Modelle können regularisiert werden, um ihre Verzerrung zu erhöhen (und somit die Varianz zu verringern), siehe Shrinkage-Schätzer.
• In künstlichen neuronalen Netzen nimmt mit der Anzahl der versteckten Knoten die Varianz zu und die Verzerrung ab. Wie in GLMs wird typischerweise Regularisierung eingesetzt.
• In k-nächsten-Nachbarn Modellen führt ein hoher Wert von k zu niedriger Varianz und hoher Verzerrung (siehe unten).
• Im Falle des gedächtnisbasierten Lernens kann Regularisierung durch die Kombination von Prototypenmethoden und Nächste-Nachbarn-Methoden erreicht werden.
• In Entscheidungsbäumen bestimmt die Tiefe des Baumes die Varianz. Entscheidungsbäume werden häufig beschnitten, um die Varianz zu kontrollieren.

Eine Möglichkeit zur Lösung des Dilemmas ist es, Modelle mit Mischverteilung und eine Kombination verschiedener Lernalgorithmen zu nutzen. Beispielsweise vereint Boosting viele „schwache“ Modelle (mit hoher Verzerrung) zu einem neuen Modell, das größere Varianz als die einzelnen Modelle hat. Dahingegen kombiniert Bagging „starke“ Klassifikatoren (mit hoher Varianz) in einer Weise, die die Varianz des neu konstruierten Klassifikators reduziert.

K-nächste Nachbarn

Im Falle des k-nächste-Nachbarn-Algorithmus existiert eine geschlossene Formel, die die Verzerrung-Varianz-Zerlegung in Relation zum Parameter $k$ setzt:

$\mathrm {E} [(y-{\hat {f}}(x))^{2}]=\left(f(x)-{\frac {1}{k}}\sum _{i=1}^{k}f(N_{i}(x))\right)^{2}+{\frac {\sigma ^{2}}{k}}+\sigma ^{2}$

wobei $N_{1}(x),\dots ,N_{k}(x)$ die $k$ nächsten Nachbarn von $x$ innerhalb der Trainingsdaten beschreiben. Die Verzerrung (erster Term) ist eine in $k$ monoton steigende Funktion, während die Varianz (zweiter Term) fällt, falls $k$ erhöht wird. Tatsächlich verschwindet unter „vernünftigen Annahmen“ die Verzerrung des 1-nächster-Nachbarn Schätzers vollständig, wenn die Größe des Trainingsdatensatzes gegen unendlich strebt.

Anwendung auf das menschliche Lernen

Während das Verzerrung-Varianz-Dilemma großteils im Bereich des maschinellen Lernens angewendet wird, ist es auch im Zusammenhang mit menschlicher Wahrnehmung untersucht worden, vor allem durch Gerd Gigerenzer und Kollegen im Bereich gelernter Heuristiken. Sie argumentieren, dass das menschliche Gehirn das Dilemma im Falle spärlicher und schlecht charakterisierter Trainingsdaten mittels Erfahrungen löst, die durch Heuristiken mit hoher Verzerrung und niedriger Varianz gewonnen werden. Dies spiegelt die Tatsache wider, dass ein Ansatz mit einer Verzerrung gleich Null eine schlechte Generalisierbarkeit auf neue Situationen aufweist und genaue Kenntnis des wahren Zustandes der Welt voraussetzt. Die resultierenden Heuristiken sind relativ einfach, liefern aber bessere Erklärungen bei einer größeren Anzahl von Situationen.

Nach Geman und anderen impliziert das Verzerrung-Varianz-Dilemma, dass Fähigkeiten wie generische Objekterkennung nicht von Grund auf neu erlernt werden können, sondern ein gewisses Maß an vorhandener „Vernetzung“ erfordern, die später durch Erfahrung angepasst wird. Dies liegt daran, dass modellfreie Ansätze, die eine hohe Varianz vermeiden möchten, zur Erklärung unpraktisch große Trainingsdatensätze erfordern.

Siehe auch

• Erwartungstreue
• Satz von Gauß-Markow
• Regressionsanalyse
• Cramer-Rao-Schranke
• Prognoseintervall

Weblinks

• https://www.cs.cornell.edu/courses/cs4780/2018fa/lectures/lecturenote12.html
• Scott Fortmann-Roe: Understanding the Bias-Variance Tradeoff, Juni 2012.

Literatur

• Harry L. Van Trees; Kristine L. Bell, "Exploring Estimator BiasVariance Tradeoffs Using the Uniform CR Bound," in Bayesian Bounds for Parameter Estimation and Nonlinear Filtering/Tracking, IEEE, 2007, S. 451–466, doi:10.1109/9780470544198.ch40.