Batch-Gefälle versus stochastisches Gefälle

101

Angenommen, wir haben eine Trainingsmenge $(x_{(i)}, y_{(i)})$ für $i = 1, \dots, m$ . Angenommen, wir führen eine Art von überwachtem Lernalgorithmus für den Trainingssatz 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}$ , die den "Abstand" zwischen $y_{(i)}$ und $h_{\theta}(x_{(i)})$ minimieren . Sei

J (θ) = \frac{1}{2} \sum_{i = 1}^{m} (y_{(i)} - h_{θ} (x_{(i)})^{2}

$J(\theta) = \frac{1}{2} \sum_{i=1}^{m} (y_{(i)}-h_{\theta}(x_{(i)})^{2}$

Dann wollen wir $\theta$ finden , das $J(\theta)$ minimiert . Beim Gefälle initialisieren wir jeden Parameter und führen die folgende Aktualisierung durch:

θ_{j} := θ_{j} - α \frac{\partial}{\partial θ_{j}} J (θ)

$\theta_j := \theta_j-\alpha \frac{\partial}{\partial \theta_{j}} J(\theta)$

Was ist der Hauptunterschied zwischen Batch-Gradientenabstieg und stochastischem Gradientenabstieg?

Beide verwenden die oben genannte Aktualisierungsregel. Aber ist einer besser als der andere?

optimization gradient-descent sgd user20616
quelle

121

Die Anwendbarkeit des Batch- oder des stochastischen Gradientenabfalls hängt wirklich von der erwarteten Fehlervielfalt ab.

Bei Batch-Gefälle wird das Gefälle anhand des gesamten Datensatzes berechnet. Dies ist ideal für konvexe oder relativ glatte Fehlerverteiler. In diesem Fall bewegen wir uns etwas direkt in Richtung einer optimalen Lösung, entweder lokal oder global. Darüber hinaus wird der Batch-Gradientenabstieg bei einer annealten Lernrate schließlich das Minimum finden, das sich in seinem Anziehungsbecken befindet.

Der stochastische Gradientenabstieg (SGD) berechnet den Gradienten anhand einer einzelnen Stichprobe. Die meisten Anwendungen von SGD verwenden aus Gründen, die später noch erläutert werden, ein Minibatch aus mehreren Proben. SGD funktioniert für Fehlerverteiler mit vielen lokalen Maxima / Minima gut (vermutlich nicht gut, aber besser als Batch-Gradientenabnahme). In diesem Fall tendiert der etwas verrauschtere Gradient, der unter Verwendung der reduzierten Anzahl von Abtastwerten berechnet wird, dazu, das Modell aus den lokalen Minima in einen Bereich zu bewegen, der hoffentlich optimaler ist. Einzelne Samples sind sehr laut, während Minibatches dazu neigen, das Rauschen etwas zu reduzieren. Dadurch wird der Ruck bei Verwendung von Minibatches reduziert. Ein gutes Gleichgewicht ist erreicht, wenn die Minibatch-Größe klein genug ist, um einige der schlechten lokalen Minima zu vermeiden, aber groß genug, dass dies nicht der Fall ist. ' t Vermeiden Sie die globalen oder leistungsstärkeren lokalen Minima. (Dies setzt übrigens voraus, dass die besten Minima ein größeres und tieferes Anziehungsbecken haben und daher leichter zu fassen sind.)

Ein Vorteil von SGD ist, dass es viel schneller rechnet. Große Datenmengen können häufig nicht im RAM gespeichert werden, was die Vektorisierung erheblich beeinträchtigt. Vielmehr muss jede Probe oder Charge von Proben geladen, bearbeitet, die Ergebnisse gespeichert usw. werden. Minibatch-SGD wird andererseits normalerweise absichtlich klein genug gemacht, um rechnerisch nachvollziehbar zu sein.

In der Regel wird dieser Rechenvorteil genutzt, indem viel mehr SGD-Iterationen durchgeführt werden, was viel mehr Schritte als bei der herkömmlichen Batch-Gradientenabsenkung bedeutet. Dies führt in der Regel zu einem Modell, das dem sehr nahe kommt, das über den Batch-Gradientenabstieg oder besser gefunden werden würde.

Die Art und Weise, wie ich über SGD nachdenke, besteht darin, mir vorzustellen, dass ich einen Punkt habe, der meine Eingabeverteilung darstellt. Mein Modell versucht, diese Eingabeverteilung zu lernen. Um die Eingabeverteilung herum befindet sich ein schattierter Bereich, der die Eingabeverteilungen aller möglichen Minibatches darstellt, die ich abtasten könnte. Es ist normalerweise eine faire Annahme, dass die Minibatch-Eingabeverteilungen in der Nähe der tatsächlichen Eingabeverteilung liegen. Bei allen Schritten nimmt der Batch-Gradientenabstieg den steilsten Weg, um die tatsächliche Eingangsverteilung zu erreichen. SGD wählt dagegen einen zufälligen Punkt innerhalb des schattierten Bereichs und nimmt die steilste Route in Richtung dieses Punkts. Bei jeder Iteration wird jedoch ein neuer Punkt ausgewählt. Der Durchschnitt aller dieser Schritte entspricht in der Regel der tatsächlichen Eingabeverteilung.

Jason_L_Bens
quelle

13

In der Praxis verwendet niemand Batch Gradient Descent. Es ist einfach zu rechenintensiv für einen geringen Gewinn. (Der Vorteil ist, dass Sie den "wahren" Gradienten tatsächlich herunterschreiten.) Wenn Sie eine hochgradig nicht-konvexe Verlustfunktion haben, müssen Sie nur in die richtige Richtung gehen, und Sie konvergieren schließlich auf ein lokales Minimum. Somit ist Minibatch SGD.

Sabalaba

@Jason_L_Bens Hast du eine Referenz (Artikel oder Online-Texte), wo ich mehr über diese Algorithmen lesen kann?

user110320

1

@ user110320 Nicht so einfach, nein, obwohl es sich um sehr gebräuchliche Algorithmen handelt. Es sollte also eine Tonne Ressourcen zu diesem Thema mit ein wenig Suche zur Verfügung stehen. Wenn Sie eine allgemeine Herangehensweise suchen, empfehlen wir Ihnen, einige von Yoshua Bengios Learning Deep Architectures for AI zu lesen. Hier habe ich angefangen.

Jason_L_Bens

6

Wie aus einer anderen Antwort hervorgeht, besteht der Hauptgrund für die Verwendung von SGD darin, die Berechnungskosten des Gradienten zu senken und gleichzeitig die Gradientenrichtung im Durchschnitt über viele Minibatches oder Proben weitgehend beizubehalten - dies hilft Ihnen sicherlich, die lokalen Minima zu erreichen.

Warum Minibatch funktioniert .

$p_{data}$ $\hat{p}_{data}$

g = E_{p_{d a t a}} (\frac{\partial J (θ)}{\partial θ})

$g = E_{p_{data}}({\partial J(\theta)\over \partial \theta})$

\frac{S E (\hat{g} (n))}{S E (\hat{g} (m))} = \sqrt{\frac{m}{n}}

${SE({\hat{g}(n)}) \over SE({\hat{g}(m)})} = { \sqrt {m \over n}}$

m

$m$

E_{{\hat{p}}_{d a t a}} (\hat{g} (m)) = E_{{\hat{p}}_{d a t a}} (\frac{\partial J (θ)}{\partial θ})

$E_{\hat{p}_{data}}(\hat{g}(m)) = E_{\hat{p}_{data}}({\partial J(\theta)\over \partial \theta})$

m

$m$

Warum Minibatch möglicherweise besser funktioniert .

Erstens macht Minibatch einige Lernprobleme von technisch nicht zu bewältigenden Problemen zu bewältigenden Problemen, da der Rechenaufwand bei kleineren Chargen geringer ist.

Zweitens bedeutet eine verringerte Chargengröße nicht unbedingt eine verringerte Gradientengenauigkeit. Die Trainingsbeispiele enthalten viele Geräusche, Ausreißer oder Vorurteile. Ein zufällig ausgewähltes Minibatch kann die tatsächliche Verteilung der Daten besser (oder nicht schlechter) widerspiegeln als das ursprüngliche vollständige Batch. Wenn einige Iterationen der Minibatch-Gradientenaktualisierungen eine bessere Schätzung ergeben, kann das gemittelte Ergebnis einer Epoche insgesamt besser sein als der aus einem vollständigen Batch berechnete Gradient.

Drittens hilft Minibatch nicht nur beim Umgang mit unangenehmen Datenmustern, sondern auch beim Umgang mit unangenehmen Kostenfunktionen mit vielen lokalen Minima. Wie Jason_L_Bens erwähnt, ist es unter Umständen einfacher, einen regulären Gradienten in ein lokales Minimum einzufangen, während es schwieriger ist, den mit Minibatch berechneten vorübergehend zufälligen Gradienten einzufangen.

Schließlich erreichen Sie beim Gefälle nicht in einem Schritt die globalen Minima, sondern iterieren auf dem Erro-Manifold. Gradient gibt Ihnen weitgehend nur die Richtung zum Iterieren. Mit Minibatch können Sie viel schneller iterieren. In vielen Fällen ist der Punkt, den Sie erreichen können, umso besser, je mehr Iterationen Sie ausführen. Es ist Ihnen egal, bei welchem Wetter der Punkt global oder sogar lokal optimal ist. Sie möchten nur ein vernünftiges Modell erreichen, das akzeptable Verallgemeinerungsfehler liefert. Minibatch macht das einfacher.

Das Buch "Deep learning" von Ian Goodfellow ua enthält unter Umständen ziemlich gute Diskussionen zu diesem Thema, wenn Sie es sorgfältig durchlesen.

Xiao-Feng Li
quelle

Für konvexe Optimierungsprobleme ist das, was Sie gesagt haben, in Ordnung. Bei der Verwendung von Gradientenmethoden für nicht konvexe Funktionen haben Sie jedoch einen sehr kritischen Grund übersehen, warum SGD besser ist als Batch-GD. Siehe meine Antwort datascience.stackexchange.com/questions/16807/…

HoraceT

@horaceT Danke für deinen 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 unter gebührendem Respekt auf seine Antwort im letzten dritten Absatz Bezug zu nehmen. Um das Problem der Optimierung des Gefälleverlaufs zu lösen, spiegelt sich Nicht-Konvexität in den lokalen Minima einschließlich des Sattelpunkts wider (siehe den letzten dritten Absatz). und der Beschreibung halber beschreibt meine Antwort SGD als Minibatch, jedoch mit einer Chargengröße von 1 (siehe Absatz 3).

Xiao-Feng Li

3

$2^{10-1} = 512$

Sven Ahlinder
quelle

Batch-Gefälle versus stochastisches Gefälle

Antworten: