Varianz der

37

TL, DR: Es sieht so aus, als ob entgegen häufig wiederholter Ratschläge die einmalige Kreuzvalidierung (LOO-CV) - das heißt, derK fache CV mitK (die Anzahl der Falten) ist gleichN (die Anzahl) der Trainingsbeobachtungen) - liefert Schätzungen des Generalisierungsfehlers, diefür jedes K am wenigsten variabel sind, und nicht die variabelsten, wobei eine bestimmte Stabilitätsbedingung entweder für das Modell / den Algorithmus, den Datensatz oder für beidevorausgesetzt wird(ich bin nicht sicher, welche ist richtig, da ich diese Stabilitätsbedingung nicht wirklich verstehe).K

  • Kann jemand klar erklären, was genau diese Stabilitätsbedingung ist?
  • Stimmt es, dass die lineare Regression ein solcher "stabiler" Algorithmus ist, was bedeutet, dass LOO-CV in diesem Zusammenhang die beste Wahl für CV ist, was die Abweichung und Varianz der Schätzungen des Generalisierungsfehlers angeht?

Die konventionelle Weisheit ist, dass die Wahl von K in K fachem CV einem Bias-Varianz-Kompromiss folgt, wobei solche niedrigeren Werte von K (gegen 2) zu Schätzungen des Generalisierungsfehlers führen, die mehr pessimistische Bias, aber geringere Varianz und höhere Werte aufweisen von K (Annäherung an N ) führen zu Schätzungen, die weniger voreingenommen sind, aber eine größere Varianz aufweisen. Die konventionelle Erklärung für dieses mit zunehmende Varianzphänomen Kfindet sich vielleicht am prominentesten in den Elementen des statistischen Lernens (Abschnitt 7.10.1):

Mit K = N ist der Kreuzvalidierungsschätzer für den wahren (erwarteten) Vorhersagefehler ungefähr unverzerrt, kann jedoch eine hohe Varianz aufweisen, da die N "Trainingssätze" einander so ähnlich sind.

Die Folge ist, dass die N Validierungsfehler stärker korreliert sind, so dass ihre Summe variabler ist. Diese Argumentation wird in vielen Antworten auf dieser Seite (zB wiederholt hier , hier , hier , hier , hier , hier und hier ) sowie auf verschiedenen Blogs und etc. Aber eine detaillierte Analyse ist so gut wie nie gegeben, statt nur eine Intuition oder eine kurze Skizze, wie eine Analyse aussehen könnte.

Man kann jedoch widersprüchliche Aussagen finden, die normalerweise eine bestimmte "Stabilitäts" -Zustand zitieren, die ich nicht wirklich verstehe. Zum Beispiel dieser widersprüchliche Antwort zitiert ein paar Absätze aus einem 2015 Papier , das sagt unter anderem : „Für Modelle / Modellierungsverfahren mit geringer Instabilität , LOO oft die geringste Variabilität“ (Hervorhebung hinzugefügt). Dieses Papier (Abschnitt 5.2) scheint zuzustimmen, dass LOO die am wenigsten variable Wahl von , solange das Modell / der Algorithmus "stabil" ist. Noch eine weitere Stellungnahme zu diesem Thema gibt es auch in diesem Artikel (Korollar 2): "Die Varianz der k- fachen Kreuzvalidierung [...] hängt nicht von k abKkk, "wieder unter Berufung auf eine bestimmte" Stabilitätsbedingung ".

Die Erklärung, warum LOO der variabelste fache Lebenslauf sein könnte, ist intuitiv genug, aber es gibt eine Gegenintuition . Die endgültige CV-Schätzung des mittleren quadratischen Fehlers (MSE) ist der Mittelwert der MSE-Schätzungen in jeder Falte. Wenn also K auf N ansteigt , ist die CV-Schätzung der Mittelwert einer zunehmenden Anzahl von Zufallsvariablen. Und wir wissen, dass die Varianz eines Mittelwerts mit der Anzahl der gemittelten Variablen abnimmt. Damit LOO die variabelste K- fach CV sein kann, muss es zutreffen, dass die Zunahme der Varianz aufgrund der erhöhten Korrelation zwischen den MSE-Schätzungen die Abnahme der Varianz aufgrund der höheren Anzahl von gemittelten Falten überwiegtKKNK. Und es ist überhaupt nicht offensichtlich, dass dies wahr ist.

Nachdem ich dies alles gründlich durcheinander gebracht hatte, entschloss ich mich, eine kleine Simulation für den linearen Regressionsfall durchzuführen. Ich simulierte 10.000 Datensätze mit = 50 und 3 unkorrelierten Prädiktoren, wobei ich den Generalisierungsfehler jedes Mal mit K- fachem CV mit K = 2, 5, 10 oder 50 = N schätzte . Der R-Code ist hier. Hier sind die resultierenden Mittelwerte und Abweichungen der CV-Schätzungen für alle 10.000 Datensätze (in MSE-Einheiten):NKKN

         k = 2 k = 5 k = 10 k = n = 50
mean     1.187 1.108  1.094      1.087
variance 0.094 0.058  0.053      0.051

Diese Ergebnisse zeigen das erwartete Muster, dass höhere Werte von zu einer weniger pessimistischen Verzerrung führen, scheinen jedoch auch zu bestätigen, dass die Varianz der CV-Schätzungen im LOO-Fall am niedrigsten und nicht am höchsten ist.K

Es scheint also, dass die lineare Regression einer der "stabilen" Fälle ist, die in den obigen Abhandlungen erwähnt wurden, in denen eine Zunahme von eher mit einer Abnahme als einer Zunahme der Varianz in den CV-Schätzungen verbunden ist. Was ich aber immer noch nicht verstehe, ist:K

  • Was genau ist dieser "Stabilitäts" -Zustand? Gilt dies in gewissem Maße für Modelle / Algorithmen, Datensätze oder beides?
  • Gibt es eine intuitive Möglichkeit, über diese Stabilität nachzudenken?
  • Was sind andere Beispiele für stabile und instabile Modelle / Algorithmen oder Datensätze?
  • Ist es relativ sicher anzunehmen, dass die meisten Modelle / Algorithmen oder Datensätze "stabil" sind und daher generell so hoch gewählt werden sollte, wie es rechnerisch machbar ist?K
Jake Westfall
quelle
1
+1. Was genau bedeutet "Mittelwert" in Ihren Simulationsergebnissen? Mittlere CV-Schätzung des Generalisierungsfehlers (Mittelwert über 10000 Datensätze)? Aber womit sollten wir es vergleichen? Sinnvoller wäre es, die Verzerrung, dh die quadratische Abweichung vom wahren Verallgemeinerungsfehler, darzustellen. Was ist in diesem Fall auch "echter Generalisierungsfehler"? Richtiger Verallgemeinerungsfehler der Schätzung auf einem gegebenen N = 100-Datensatz? Oder Erwartungswert des wahren Generalisierungsfehlers (Erwartungswert über alle N = 100 Datensätze)? Oder etwas anderes?
Amöbe sagt Reinstate Monica
3
+1. Nach kurzem Blick auf en.wikipedia.org/wiki/... scheint es in diesem Zusammenhang Stabilität bedeutet , dass , dass ein Algorithmus ähnliche Ergebnisse auf Trainingssatz mit produziert und N - 1 Beispiele. Wo gleichbedeutend ist die Differenz zwischen einer Verlustfunktion und einem niedrigen WertNN-1
Łukasz Grad
1
Abgesehen davon habe ich kürzlich mit @DikranMarsupial (der wahrscheinlich einer unserer Hauptexperten für Kreuzvalidierung hier im Lebenslauf ist) hier in den Kommentaren darüber gesprochen - er schlug vor, Kohavis Arbeit von 1995 zu lesen . Dikran sprach auch über Stabilität. Leider habe ich es seitdem nicht weiter verfolgt.
Amöbe sagt Reinstate Monica
2
Das glaube ich nicht, @Jake. Was ich geschrieben habe, macht Ihre "Gegenintuition" ungültig, aber die "Hauptintuition" (über Modelle aus verschiedenen Faltungen, die stark abhängig sind) kann immer noch gelten.
Amöbe sagt Reinstate Monica
1
Eine weitere Simulation stützt Ihre Schlussfolgerungen, dass die Varianz mit abnimmt : stats.stackexchange.com/a/357749/28666 . K
Amöbe sagt Reinstate Monica

Antworten:

15

Diese Antwort folgt meiner Antwort in Bezug auf die Verzerrung und die Varianz in Bezug auf die K-fache Kreuzvalidierung , in der erläutert wird, warum LOOCV nicht immer zu einer höheren Varianz führt. Nach einem ähnlichen Ansatz, werde ich versuchen , einen Fall zu markieren , wo LOOCV Blei hat zu einem höheren Varianz in Gegenwart von Ausreißern und ein „instabilen Modell“.

Algorithmische Stabilität (Lerntheorie)

Die algorithmische Stabilität ist ein aktuelles Thema, und in den letzten 20 Jahren wurden mehrere klassische, einflussreiche Ergebnisse nachgewiesen. Hier sind einige Artikel, die oft zitiert werden

Die beste Seite, um sich ein Bild zu machen, ist sicherlich die Wikipedia-Seite, die eine hervorragende Zusammenfassung enthält, die von einem vermutlich sehr sachkundigen Benutzer verfasst wurde.

Intuitive Definition von Stabilität

Intuitiv ist ein stabiler Algorithmus einer, für den sich die Vorhersage nicht wesentlich ändert, wenn die Trainingsdaten geringfügig geändert werden.

Formal gibt es ein halbes Dutzend Versionen von Stabilität, verbunden durch technische Bedingungen und Hierarchien finden Sie in dieser Grafik von hier zum Beispiel:

Bildbeschreibung hier eingeben

Das Ziel ist jedoch einfach: Wir möchten den Generalisierungsfehler eines bestimmten Lernalgorithmus genau einschränken, wenn der Algorithmus das Stabilitätskriterium erfüllt. Wie zu erwarten ist, ist die entsprechende Grenze umso enger, je restriktiver das Stabilitätskriterium ist.

Notation

Die folgende Notation stammt aus dem Wikipedia-Artikel, der das Bousquet- und Elisseef-Papier selbst kopiert:

  • Der Trainingssatz wird aus einer unbekannten Verteilung D gezogenS={z1=(x1,y1),...,zm=(xm,ym)}
  • Die Verlustfunktion einer Hypothese f bezüglich eines Beispiels z ist definiert als V ( f , z )VfzV(f,z)
  • ichS|ich={z1,...,zich-1,zich+1,...,zm}
  • ichSich={z1,...,zich-1,zich,zich+1,...,zm}

Formale Definitionen

Die vielleicht stärkste Vorstellung von Stabilität, der ein interessanter Lernalgorithmus gehorchen könnte, ist die von einheitlicher Stabilität :

βV

SZm  i{1,...,m},  sup|V(fs,z)V(fS|i,z)|  β

mββmβm1m

Stabilität der Hypothese

ich{1,...,m},  E[ |V(fs,z)-V(fS|ich,z)| ] β

L1

Der Vorteil dieser Stabilitätsformen besteht darin, dass sie Grenzen für die Abweichung und Varianz stabiler Algorithmen festlegen. Insbesondere hat Bousquet diese Grenzen für die Stabilität von Gleichförmigkeit und Hypothese im Jahr 2002 bewiesen. Seitdem wurde viel Arbeit geleistet, um die Stabilitätsbedingungen zu lockern und die Grenzen zu verallgemeinern, zum Beispiel argumentieren Kale, Kumar, Vassilvitskii im Jahr 2011, dass Quadratstabilität bedeutet Bessere Varianz Quantitative Varianzreduktionsgrenzen.

Einige Beispiele für stabile Algorithmen

Die folgenden Algorithmen haben sich als stabil erwiesen und haben Verallgemeinerungsgrenzen bewiesen:

  • Regularisierte kleinste Fehlerquadrat-Regression
  • KNN-Klassifikator mit 0-1-Verlustfunktion
  • SVM mit einem begrenzten Kernel und einer großen Regularisierungskonstante
  • Weicher Rand SVM
  • Minimaler relativer Entropiealgorithmus für die Klassifizierung
  • Eine Version von Absack-Regularisern

Eine experimentelle Simulation

Wiederholen wir den Versuch aus dem vorherigen Thread ( siehe hier ), so fügen wir nun ein bestimmtes Verhältnis von Ausreißern in den Datensatz ein. Bestimmtes:

  • [-.5,.5]
  • [-20,20]

3

Bildbeschreibung hier eingeben

Durch Ausführen der Simulation wie zuvor und Auftragen des resultierenden durchschnittlichen MSE und der Varianz des MSE werden Ergebnisse erzielt, die Experiment 2 des Papiers von Bengio & Grandvalet 2004 sehr ähnlich sind .

Linke Seite : keine Ausreißer. Rechte Seite : 3% Ausreißer.

Bildbeschreibung hier eingeben

Bildbeschreibung hier eingeben

(Die Erklärung der letzten Abbildung finden Sie im verlinkten Artikel.)

Erklärungen

Zitiert Yves Grandvalets Antwort auf den anderen Thread:

Intuitiv kann [in der Situation instabiler Algorithmen] ein ausgelassener Lebenslauf für vorhandene Instabilitäten blind sein, jedoch nicht durch Ändern eines einzelnen Punkts in den Trainingsdaten ausgelöst werden, was ihn sehr variabel für die Realisierung der Daten macht Trainingsset.

In der Praxis ist es schwierig, einen Anstieg der Varianz aufgrund von LOOCV zu simulieren. Es erfordert eine bestimmte Kombination aus Instabilität, einigen Ausreißern, aber nicht zu vielen, und einer großen Anzahl von Iterationen. Möglicherweise wird dies erwartet, da sich gezeigt hat, dass die lineare Regression recht stabil ist. Ein interessantes Experiment wäre, dies für höherdimensionale Daten und einen instabileren Algorithmus (z. B. Entscheidungsbaum) zu wiederholen.

Xavier Bourret Sicotte
quelle
+1, aber ich hoffe, dieser Thread kann irgendwann als Duplikat des verknüpften Threads geschlossen werden (ich würde warten, bis die Kopfgeldfrist abgelaufen ist und die Diskussionen beendet sind und sehen, welche Antwort akzeptiert wird). Ich werde später mehr kommentieren.
Amöbe sagt Reinstate Monica
Ich bin nicht wirklich überzeugt, dass die Frage ein Duplikat ist. Meine Frage verwendet die Varianz des LOO-Problems in erster Linie, um die Hauptfragen zu formulieren, bei denen es darum geht, eine verständliche Erklärung für die Bedeutung von "Stabilität" zu erhalten - siehe die Fragen mit dem Aufzählungszeichen oben und unten im OP. Apropos, obwohl diese Antwort nützlich ist (+1), sehe ich nicht, dass Sie versucht haben, die Stabilitätsfragen zu beantworten ... Sie verwenden den Begriff ein paar Mal, aber Sie scheinen dies auf eine Art und Weise zu tun geht davon aus, dass der Leser bereits weiß, was es bedeutet. Ich bin nicht sicher, ob ich die Antwort in der aktuellen Form akzeptieren kann.
Jake Westfall
1
@JakeWestfall Als ich schrieb, dass ich "hoffe", dass dieser Thread irgendwann als Duplikat geschlossen werden kann, hoffte ich, dass eine akzeptierte Antwort in diesem Thread irgendwann groß genug sein wird, um die Dinge abzudecken, nach denen Sie gefragt haben :) Schauen Sie sich das Bengio & Grandvalet-Papier, Experiment 2, an. Sie zeigen, dass mit linearer Regression und Gaußschen Daten die minimale Varianz für LOOCV erhalten wird (das ist auch Ihr Ergebnis). Wenn die Daten jedoch einen Bruchteil von Ausreißern enthalten, hat LOOCV eine höhere Varianz als falten oder so. Ich denke, das deutet darauf hin, worum es bei der relevanten "Stabilität" geht.
Amöbe sagt Reinstate Monica
3
Ich liebe es, @ XavierBourretSicotte. Vielen Dank für die großartige Arbeit an dieser Antwort.
Jake Westfall
1
Ja, zitiert dieses Papier: pdfs.semanticscholar.org/bf83/… : "Ein stabiler Algorithmus hat die Eigenschaft, dass das Ersetzen eines Elements in seiner Lernmenge nicht viel an seinem Ergebnis ändert. Infolgedessen ändert sich der empirische Fehler, wenn er als a angesehen wird zufällige Variable, sollte eine kleine Varianz haben. Stabile Algorithmen können dann gute Kandidaten für ihren empirischen Fehler sein, um nahe an ihrem Generalisierungsfehler zu sein.
Xavier Bourret Sicotte
2

Ich werde meine Antwort im Zusammenhang mit dem von Ihnen zitierten Absatz geben:

Mit K = N ist der Kreuzvalidierungsschätzer für den wahren (erwarteten) Vorhersagefehler ungefähr unverzerrt, kann jedoch eine hohe Varianz aufweisen, da die N "Trainingssätze" einander so ähnlich sind.

Der CV-Schätzer des wahren (erwarteten) Vorhersagefehlers basiert auf einem Trainingssatzbeispiel, daher ist die Erwartung hier über den Trainingssatzbeispielen, wenn ich das richtig verstehe.

Also, was dieser Absatz über "hohe Varianz" sagt, ist, dass es einen "hohen" Unterschied zwischen dem erwarteten Fehler und dem durch CV geschätzten Fehler gibt (der hier der Durchschnitt über Falten ist).

Dies ist sinnvoll, weil das Modell für ein bestimmtes Trainingsset geeignet ist und weil alle Trainingsfalten innerhalb von Leave-One-Out so ähnlich sind. Während die Trainingsfalten innerhalb einer CV-Runde sehr ähnlich sind, unterscheidet sich die Schätzung wahrscheinlich um ein Vielfaches, wenn wir Trainingsmuster gegen CV tauschen. Da wir im k-fachen Lebenslauf die Trainingsfalten "diversifizieren", haben wir eine gewisse Auswirkung auf die Mittelung, und über die k-fachen variieren die Schätzungen dann weniger.

Mit anderen Worten, der Leave-One-Out-CV-Schätzer ähnelt im Grunde einer Holdout-Methode, bei der Sie keine Falze drehen und Ihre Fehlerschätzung auf einen Validierungssatz stützen. Bei Trainingsbeispielen gibt es wiederum eine hohe Varianz im Vergleich zu Schätzungen aus dem k-fachen, bei denen Sie den Durchschnitt über Falten bilden, indem Sie bereits etwas unterschiedliche Modelle innerhalb der k-fachen Runde trainieren (mit anderen Worten, wenn Sie Trainingssätze tauschen, werden die Schätzungen von Der Fehler über k-fach wird wahrscheinlich nicht so stark variieren.

BEARBEITEN:

Wenn ich hier einige Antworten auf Cross-Validated und das Internet im Allgemeinen lese, scheint es eine gewisse Verwirrung darüber zu geben, auf welchen Schätzer wir uns beziehen. Ich denke, einige Leute beziehen sich auf ein Modell mit einer hohen Varianz (wobei ML für den Verlust eine dominierende Varianzkomponente ist) gegenüber einer hohen Varianz des k-fachen CV-Schätzers. Ein anderer Satz von Antworten bezieht sich auf die Varianz als die Stichprobenvarianz in Bezug auf die Falten, wenn jemand sagt, dass "k-fach eine hohe Varianz hat". Daher schlage ich vor, genau zu sein, da die Antworten in beiden Fällen unterschiedlich sind.


quelle
Bei der Erörterung der Varianz gehe ich davon aus, dass es sich um die Varianz des CV-Schätzers für Trainingssatz D handelt, wie hier definiert: stats.stackexchange.com/questions/365224/… und hier: stats.stackexchange.com/questions/325123/… . Yves Grandvalet und Bengio argumentieren in ihrer Arbeit von 2004, dass der Lebenslauf den erwarteten Vorhersagefehler schätzt. Sie können seine Antwort hier sehen: stats.stackexchange.com/a/358138/192854
Xavier Bourret Sicotte
Wenn Sie Ihre Antwort auf verschiedene Definitionen der Varianz stützen möchten, halte ich es für hilfreich, die formalen Definitionen und Formeln hinzuzufügen. Vielleicht sollte ich das auch in meinen Antworten tun.
Xavier Bourret Sicotte
Ja, ich muss die Literatur ein wenig durchsehen und sollte der Antwort einige Formeln hinzufügen. Das Zitat aus den The Elements of Statistical Learning ist für mich jedoch immer noch intuitiv, dass LOOCV eine hohe Varianz aufweist, wenn das Modell eine hohe Varianz aufweist, da es ein Durchschnitt über die Falten ist. Wenn ein Modell eine hohe Abweichung aufweist, sollten sowohl LOOCV- als auch alle k-fachen Schätzer eine geringe Abweichung aufweisen (unabhängig von der Abweichung), da die Vorhersagen nicht so stark variieren. Aber der Punkt im Absatz war wahrscheinlich. dass LOOCV im Vergleich zu k-fach für die meisten Fälle
Das Zitat hat sich als falsch erwiesen - zumindest als Verallgemeinerung -, siehe die in meinen Antworten zitierten Artikel
Xavier Bourret Sicotte,
1

Wir haben das schon einmal durchgemacht - Sie werden zu mathematisch in Bezug auf ein totes Pferd. Sehen Sie sich hier Ron Kohavis (Stanford-Univ) Klassiker über CV und das Bias-Varianz-Dilemma an . Wenn Sie mit dem Lesen fertig sind, möchten Sie LOOCV nicht mehr ausführen und werden wahrscheinlich vom 10-fachen CV und / oder Bootstrap-Bias-CV angezogen.

Sie müssen auch über große Datenmengen nachdenken, für die LOOCV viel zu rechenintensiv ist. Derzeit ist LOOCV in den Workflows / Pipelines der meisten Gruppen nicht wirklich eine Option.

Was genau ist dieser "Stabilitäts" -Zustand? Gilt dies in gewissem Maße für Modelle / Algorithmen, Datensätze oder beides?

k=nk=nk=n

LREG als Klassifikator würde funktionieren, wenn die Daten linear trennbar sind, aber im Durchschnitt wäre seine Verzerrung zu hoch, da viele Datensätze nicht linear trennbar sind.

Gibt es eine intuitive Möglichkeit, über diese Stabilität nachzudenken?

Aus meiner Sicht nicht, da es keine allgemeine Stabilitätsregel gibt.

Was sind andere Beispiele für stabile und instabile Modelle / Algorithmen oder Datensätze?

Dies ist offen und zu weit gefasst, da unendlich viele Antworten erfunden werden können, was nicht hilfreich wäre.

K

kk

kk Datenstichprobe keine echte Realisierung des Universums aller Daten ist, aus denen die Stichprobe gewonnen wurde.

JoleT
quelle
Vielen Dank für Ihre Kommentare, aber dies scheint die Frage nicht zu beantworten.
Jake Westfall
Siehe die beigefügte Antwort zum OP.
JoleT
3
Hat den Artikel nur überflogen, aber sie scheinen wirklich zu behaupten, dass 10x auf extrem wackeligem Boden das Beste ist . Ich kann nicht glauben, dass das 7k Zitate hat. Vor diesem Hintergrund scheint es einen guten Grund zu geben zu glauben, dass mehr als das Zehnfache von Vorteil ist. Wird eine gründlichere Lektüre geben, wenn ich eine Chance habe.
Cliff AB