Angenommen, wir haben einen Trainingssatz $ (x _ {(i)}, y _ {(i)}) $ für $ i = 1, \ dots, m $ . Angenommen, wir führen eine Art überwachten Lernalgorithmus für das Trainingsset aus. Hypothesen werden dargestellt als $ h _ {\ theta} (x _ {(i)}) = \ theta_0 + \ theta_ {1} x _ {(i) 1} + \ cdots + \ theta_ { n} x _ {(i) n} $ . Wir müssen die Parameter $ \ mathbf {\ theta} $ finden, die den „Abstand“ zwischen $ y _ {(i )} $ und $ h _ {\ theta} (x _ {(i)}) $ . Sei $$ J (\ theta) = \ frac {1} {2} \ sum_ {i = 1} ^ {m} (y _ {(i)} – h _ {\ theta } (x _ {(i)}) ^ {2} $$
Dann wollen wir $ \ theta $ das finden minimiert $ J (\ theta) $ . Beim Gradientenabstieg initialisieren wir jeden Parameter und führen die folgende Aktualisierung durch: $$ \ theta_j : = \ theta_j- \ alpha \ frac {\ partiell} {\ partiell \ theta_ {j}} J (\ theta) $$
Was ist der Hauptunterschied zwischen Batch-Gradientenabstieg und stochastischem Gradientenabstieg?
Beide verwenden die obige Aktualisierungsregel. Aber ist einer besser als der andere?
Antwort
Die Anwendbarkeit des diskontinuierlichen oder stochastischen Gradientenabfalls hängt wirklich von der erwarteten Fehlervielfalt ab.
Der Batch-Gradientenabstieg berechnet den Gradienten unter Verwendung des gesamten Datensatzes. Dies ist ideal für konvexe oder relativ glatte Fehlerverteiler. In diesem Fall bewegen wir uns irgendwohin direkt auf eine optimale Lösung, entweder lokal oder global. Darüber hinaus findet der Batch-Gradientenabstieg bei einer getemperten Lernrate schließlich das Minimum im Anziehungsbecken.
Der stochastische Gradientenabstieg (SGD) berechnet den Gradienten unter Verwendung einer einzelnen Stichprobe SGD verwendet tatsächlich einen Minibatch mit mehreren Stichproben aus Gründen, die etwas später erläutert werden. SGD funktioniert gut (vermutlich nicht gut, aber besser als Batch-Gradientenabstieg) für Fehlerverteiler mit vielen lokalen Maxima / Minima In diesem Fall neigt der etwas lautere Gradient, der unter Verwendung der reduzierten Anzahl von Abtastwerten berechnet wird, dazu, das Modell aus lokalen Minima in einen Bereich zu ziehen, der hoffentlich optimaler ist. Einzelne Abtastwerte sind wirklich verrauscht, während Minibatches dazu neigen, ein wenig des Rauschens zu mitteln Wenn die Minibatch-Größe klein genug ist, um einige der schlechten lokalen Minima zu vermeiden, aber groß genug, um die globalen Minima oder die bessere Leistung nicht zu vermeiden, wird die Menge an Ruck verringert okale Minima. (Dies setzt übrigens voraus, dass die besten Minima ein größeres und tieferes Anziehungsbecken haben und daher leichter zu erreichen sind.)
Ein Vorteil von SGD ist, dass es rechnerisch viel schneller ist. Groß Datensätze können oft nicht im RAM gespeichert werden, was die Vektorisierung viel weniger effizient macht. Vielmehr muss jede Probe oder Charge von Proben geladen, bearbeitet, die Ergebnisse gespeichert usw. werden. Andererseits wird Minibatch-SGD normalerweise absichtlich klein genug gemacht, um rechnerisch nachvollziehbar zu sein.
Normalerweise wird dieser Rechenvorteil genutzt, indem viel mehr Iterationen von SGD durchgeführt werden und viel mehr Schritte als beim herkömmlichen Batch-Gradientenabstieg ausgeführt werden . Dies führt normalerweise zu einem Modell, das dem sehr nahe kommt, das über einen Batch-Gradientenabstieg oder besser gefunden werden würde.
Ich denke gerne darüber nach, wie SGD funktioniert, wenn ich mir vorstelle, dass ich einen Punkt habe repräsentiert meine Eingabeverteilung. Mein Modell versucht, diese Eingabeverteilung zu lernen. Die Eingangsverteilung ist von einem schattierten Bereich umgeben, der die Eingangsverteilungen aller möglichen Minibatches darstellt, die ich abtasten könnte. Es ist normalerweise eine faire Annahme, dass die Minibatch-Eingangsverteilungen nahe an der tatsächlichen Eingangsverteilung liegen. Der Batch-Gradientenabstieg nimmt in allen Schritten den steilsten Weg, um die wahre Eingangsverteilung zu erreichen. SGD wählt andererseits a zufälliger Punkt innerhalb des schattierten Bereichs und nimmt den steilsten Weg zu diesem Punkt. Bei jeder Iteration wird jedoch ein neuer Punkt ausgewählt. Der Durchschnitt aller dieser Schritte entspricht in etwa der tatsächlichen Eingabeverteilung, normalerweise recht gut.
Kommentare
- In der Praxis verwendet niemand Batch Gradient Descent. ‚ ist einfach zu rechenintensiv für nicht so viel (Der Gewinn besteht darin, dass Sie ‚ tatsächlich die “ true “ gradient.) Wenn Sie eine stark nicht konvexe Verlustfunktion haben, müssen Sie nur in die richtige Richtung gehen und ‚ konvergieren schließlich o n ein lokales Minimum. Somit Minibatch SGD.
- @Jason_L_Bens Haben Sie eine Referenz (Artikel oder Online-Texte), in der ich mehr über diese Algorithmen lesen kann?
- @ user110320 Nicht aus dem Kopf, nein, obwohl sie ‚ sind sehr gebräuchliche Algorithmen, daher sollte eine Tonne Ressourcen zu diesem Thema mit ein wenig Suche verfügbar sein. Wenn Sie ‚ nach einem allgemeinen Ansatz suchen, würde ich ‚ empfehlen, einige von Yoshua Bengio ‚ s Lernen tiefer Architekturen für KI. ‚ Hier habe ich angefangen.
Antwort
Wie aus anderen Antworten hervorgeht, besteht der Hauptgrund für die Verwendung von SGD darin, die Berechnungskosten für den Gradienten zu reduzieren und gleichzeitig die Gradientenrichtung im Durchschnitt über viele Mini-Batches oder Proben weitgehend beizubehalten – dies hilft Ihnen sicherlich dabei, die lokalen Minima zu erreichen.
- Warum Minibatch funktioniert .
Die Mathematik dahinter ist dass der “ true “ Gradient der Kostenfunktion (der Gradient für den Generalisierungsfehler oder für unendlich große Stichproben) die Erwartung ist des Gradienten $ g $ über die wahre Datenerzeugungsverteilung $ p_ {data} $ ; Der tatsächliche Gradient $ \ hat {g} $ , der über einen Stapel von Stichproben berechnet wird, ist immer eine Annäherung an den wahren Gradienten mit der empirischen Datenverteilung $ \ hat {p} _ {data} $ . $$ \ hat {g} = E _ {\ hat {p} _ {data}} ({\ partielles J (\ theta) \ über \ partielles \ theta}) $$ Batch-Gradientenabstieg kann Ihnen den möglichen “ optimalen “ Gradienten bei all Ihren Datenproben bringen, es ist nicht die “ true “ Verlauf. Eine kleinere Charge (dh ein Minibatch) ist wahrscheinlich nicht so optimal wie die vollständige Charge, aber beide sind Näherungswerte – ebenso wie das Einzelproben-Minibatch (SGD).
Angenommen, es besteht keine Abhängigkeit zwischen dem $ m $ Samples in einem Minibatch, der berechnete $ \ hat {g} (m) $ ist unvoreingenommen Schätzung des wahren Gradienten. Die (quadratischen) Standardfehler der Schätzungen mit unterschiedlichen Minibatch-Größen sind umgekehrt proportional zu den Größen des Minibatches. Das heißt, $$ {SE ({\ hat {g} (n)}) \ über SE ({\ hat {g} (m)})} = {\ sqrt { m \ over n}} $$ Das heißt, die Reduzierung des Standardfehlers ist die Quadratwurzel der Zunahme der Stichprobengröße. Dies bedeutet, wenn die Minibatch-Größe klein ist, muss auch die Lernrate klein sein, um Stabilität über die große Varianz zu erreichen. Wenn die Stichproben nicht unabhängig sind, bleibt die Eigenschaft der unverzerrten Schätzung nicht mehr erhalten. Dazu müssen Sie die Samples vor dem Training mischen, wenn die Samples nicht zufällig genug sequenziert werden.
- Warum Minibatch kann besser arbeiten .
Erstens macht Minibatch einige Lernprobleme von technisch unlösbar zu handhabbar, da der Rechenaufwand bei kleinerer Stapelgröße geringer ist.
Zweitens bedeutet eine verringerte Chargengröße nicht unbedingt eine verringerte Gradientengenauigkeit. Die Trainingsmuster haben viele viele Geräusche oder Ausreißer oder Vorurteile. Ein Minibatch mit zufälliger Stichprobe kann die tatsächliche Verteilung der Datenerzeugung besser (oder nicht schlechter) widerspiegeln als die ursprüngliche vollständige Charge. Wenn einige Iterationen der Minibatch-Gradientenaktualisierungen eine bessere Schätzung liefern, kann das gemittelte Ergebnis einer Epoche insgesamt besser sein als der Gradient, der aus einem vollständigen Stapel berechnet wurde.
Drittens hilft Minibatch nicht nur bei der Bewältigung unangenehmer Probleme Datenproben, helfen aber auch bei der Bewältigung unangenehmer Kostenfunktionen, die viele lokale Minima aufweisen. Wie Jason_L_Bens erwähnt, ist es manchmal einfacher, einen regulären Gradienten in lokalen Minima abzufangen, während es schwieriger ist, den mit Minibatch berechneten vorübergehend zufälligen Gradienten abzufangen.
Schließlich ist dies bei einem Gradientenabstieg nicht der Fall Erreichen der globalen Minima in einem Schritt, aber Iteration auf der Fehlervielfalt. Der Verlauf gibt Ihnen größtenteils nur die Richtung zum Iterieren. Mit Minibatch können Sie viel schneller iterieren. In vielen Fällen ist der Punkt umso besser, je mehr Iterationen durchgeführt werden. Es ist Ihnen bei jedem Wetter egal, ob der Punkt global oder sogar lokal optimal ist. Sie möchten nur ein vernünftiges Modell erreichen, das Ihnen akzeptable Generalisierungsfehler bringt. Minibatch macht das einfacher.
Möglicherweise finden Sie das Buch “ Deep Learning “ von Ian Goodfellow et al., hat ziemlich gute Diskussionen zu diesem Thema, wenn Sie es sorgfältig durchlesen.
Kommentare
- Bei konvexen Optimierungsproblemen ist das, was Sie gesagt haben, in Ordnung.Um jedoch Gradientenmethoden für nicht konvexe Funktionen zu verwenden, haben Sie einen sehr kritischen Grund übersehen, dass SGD besser ist als Batch-GD. Siehe meine Antwort datascience.stackexchange.com/questions/16807/…
- @horaceT Vielen Dank für Ihren Kommentar. Da der von Ihnen erwähnte Punkt von Jason_L_Bens oben ausführlich beschrieben wurde, habe ich mich nicht darum gekümmert, ihn zu wiederholen, sondern seine Antwort im letzten dritten Absatz mit gebührendem Respekt zu erwähnen. Um das Problem der Optimierung des Gradientenabstiegs zu lösen, wird nicht konvex durch die lokalen Minima einschließlich des Sattelpunkts reflektiert (siehe letzter dritter Absatz). und der Beschreibung halber beschreibt meine Antwort SGD als Minibatch, jedoch mit einer Stapelgröße von 1 (siehe dritten Absatz).
- Warum haben Sie in einer Epoche virtuell in * gesagt, dass Sie virtuell rechnen der Mittelwert der Gradienten basierend auf allen angegebenen Stichproben. *? ‚ Denken Sie nicht, dass diese Behauptung falsch ist, weil die Gewichte bei jedem Schritt aktualisiert werden?
- @Media Sie haben Recht. Ich ‚ habe den letzten Absatz entfernt. Vielen Dank.
Antwort
Für mich ähnelt der Batch-Gradient einem mageren Gradienten. Beim mageren Gradienten wird die Chargengröße so gewählt, dass jeder Parameter, der aktualisiert werden soll, auch unabhängig, jedoch nicht unbedingt orthogonal, in der Charge variiert wird. Wenn der Stapel beispielsweise 10 Experimente und 10 Zeilen enthält, können $ 2 ^ {10-1} = 512 $ unabhängige Spalten gebildet werden. 10 Zeilen ermöglichen die unabhängige, aber nicht orthogonale Aktualisierung von 512 Parametern.