Konvergenz des Gradientenabstiegs Wie entscheidet man über Konvergenz?

Question

Ich habe Gradientenabstieg durch Online-Ressourcen gelernt (nämlich Machine Learning bei Coursera). Die bereitgestellten Informationen sagten jedoch nur aus, den Gradientenabstieg so lange zu wiederholen, bis er konvergiert.

Ihre Definition von Konvergenz bestand darin, einen Graphen der Kostenfunktion relativ zur Anzahl der Iterationen zu verwenden und zu beobachten, wann sich der Graph abflacht. Deshalb gehe ich davon aus, dass ich folgendes tun würde:

if (Änderung_in_Kostenfunktion > Präzisionswert) {
          wiederhole den Gradientenabstieg
} 

Alternativ frage ich mich, ob eine andere Möglichkeit, Konvergenz festzustellen, darin besteht, den Koeffizienten seinem wahren Wert anzunähern:

if (Änderung_im_Koeffizienten_j > Präzisionswert) {
          wiederhole den Gradientenabstieg_für_j
} 
...wiederhole für alle Koeffizienten

Basieren Konvergenz auf der Kostenfunktion oder den Koeffizienten? Und wie bestimmen wir den Präzisionswert? Sollte es sich um einen Prozentsatz des Koeffizienten oder der Gesamtkostenfunktion handeln?

Answer 1

Sie können sich vorstellen, wie der Gradientenabstieg (GD) funktioniert, wenn Sie sich vorstellen, dass Sie eine Murmel in eine Schüssel werfen und anfangen, Fotos zu machen. Die Murmel wird schwingen, bis die Reibung sie am Boden stoppt. Stellen Sie sich nun vor, dass Sie in einer Umgebung sind, in der die Reibung so gering ist, dass die Murmel lange braucht, um vollständig zum Stillstand zu kommen. Daher können wir annehmen, dass, wenn die Schwingungen klein genug sind, die Murmel den Boden erreicht hat (obwohl sie weiter schwingen könnte). Im folgenden Bild können Sie die ersten acht Schritte (Fotos der Murmel) des GD sehen.

Wenn wir weiterhin Fotos machen und die Murmel keine wahrnehmbaren Bewegungen macht, sollten Sie in das Bild hineinzoomen:

Wir könnten weiterhin Fotos machen und die Bewegungen werden immer irrelevanter.

Das Erreichen eines Punktes, an dem der GD sehr geringe Änderungen an Ihrer Zielfunktion vornimmt, wird als Konvergenz bezeichnet, was nicht bedeutet, dass er das optimale Ergebnis erreicht hat (aber es ist wirklich sehr nahe dran, wenn nicht sogar darauf).

Der Präzisionswert kann als Schwellenwert gewählt werden, bei dem Ihre aufeinanderfolgenden Iterationen von GD fast gleich sind:

grad(i) = 0,0001
grad(i+1) = 0,000099989 <-- Grad hat sich weniger als 0,01 % geändert => STOP

Answer 2

Ich denke, ich verstehe deine Frage. Basierend auf meinem Verständnis beruht die GD-Funktion auf der Kostenfunktion. Sie iteriert, bis die Kostenfunktion konvergiert.

Stell dir vor, du plotst ein Diagramm der Kostenfunktion (y-Achse) gegen die Anzahl der Iterationen der GD (x-Achse). Nun, wenn die GD richtig funktioniert, ist die Kurve nach oben gewölbt oder abnehmend (ähnlich wie bei 1/x). Da die Kurve abnimmt, wird die Abnahme der Kostenfunktion immer kleiner und kleiner, und dann kommt der Punkt, an dem die Kurve fast abgeflacht ist. Um diesen Punkt herum sagen wir, dass die GD mehr oder weniger konvergiert ist (wieder dort, wo die Kostenfunktion um eine Einheit weniger als den Präzisionswert abnimmt).

Also, ich würde sagen, dass dein erster Ansatz das ist, was du brauchst:

(if (Änderung_in_Kostenfunktion > Präzisionswert))

wiederhole GD;