Warum sind Derivate zweiter Ordnung bei der konvexen Optimierung nützlich?

18

Ich denke, dies ist eine grundlegende Frage, die mit der Richtung des Gradienten selbst zu tun hat, aber ich suche nach Beispielen, bei denen Methoden 2. Ordnung (z. B. BFGS ) effektiver sind als eine einfache Gradientenabnahme.

Bar
quelle
3
Ist es zu einfach zu beobachten, dass "Finde den Scheitelpunkt eines Paraboloids" eine viel bessere Annäherung an das Problem "Finde ein Minimum" ist als "Finde das Minimum dieser linearen Funktion" (das natürlich kein Minimum hat, weil es ist)? linear)?

Antworten:

20

Hier ist ein gemeinsamer Rahmen für die Interpretation von Gradientenabstieg und Newtons Methode. Dies ist möglicherweise eine nützliche Methode, um den Unterschied als Ergänzung zu @ Sycoraxs Antwort zu betrachten. (BFGS nähert sich Newtons Methode an. Ich werde hier nicht weiter darauf eingehen.)

Wir minimieren die Funktion f , wissen aber nicht, wie wir das direkt machen sollen. Also nehmen wir stattdessen eine lokale Approximation an unserem aktuellen Punkt x und minimieren diese.

Newtons Methode approximiert die Funktion unter Verwendung einer Taylor-Expansion zweiter Ordnung: wobeif ( x ) die Steigung von f am Punkt x und2 f ( x ) das Hessische bei x bezeichnet . Es tritt dann an arg min y N x ( y ) und wiederholt.

f(y)Nx(y): =f(x)+f(x)T(y-x)+12(y-x)T2f(x)(y-x),
f(x)fx2f(x)xargMindestyNx(y)

Gradientenabstieg, der nur den Gradienten und nicht das Hessische hat, kann nicht einfach eine Annäherung erster Ordnung machen und diese minimieren, da es, wie @Hurkyl feststellte, kein Minimum gibt. Stattdessen definieren wir eine Schrittgröße und einen Schritt zu x - t f ( x ) . Beachten Sie jedoch, dass x - ttx-tf(x) Somit minimiert der Gradientenabstieg eine Funktion Gx(y):=f(x)+f(x)T(y-x)+1

x-tf(x)=argmaxy[f(x)+f(x)T(y-x)+12ty-x2]=argmaxy[f(x)+f(x)T(y-x)+12(y-x)T1tich(y-x)].
Gx(y): =f(x)+f(x)T(y-x)+12(y-x)T1tich(y-x).

Gradientenabstieg ist also ähnlich wie bei der Newtonschen Methode, aber anstatt die Taylor-Expansion zweiter Ordnung zu verwenden, geben wir vor, dass der Hessische Wert . DiesesGist oft eine wesentlich schlechtere Annäherung anfalsN, und daher macht der Gradientenabstieg oft viel schlechtere Schritte als die Newtonsche Methode. Dies wird natürlich dadurch ausgeglichen, dass jeder Schritt des Gradientenabfalls so viel billiger zu berechnen ist als jeder Schritt der Newtonschen Methode. Was besser ist, hängt ganz von der Art des Problems, Ihren Rechenressourcen und Ihren Genauigkeitsanforderungen ab.1tichGfN

Betrachten Sie das Beispiel von @ Sycorax zur Minimierung eines quadratischen

f(x)=12xTEINx+dTx+c

N=f

Gx(y)=f(x)+(EINx+d)Ty+12(x-y)T1tich(x-y)
xEIN
Dougal
quelle
1
Dies ähnelt der Antwort von @ Aksakal , ist jedoch genauer.
Dougal
1
(+1) Dies ist eine großartige Ergänzung!
Sycorax sagt Reinstate Monica
17

Im Wesentlichen besteht der Vorteil einer Methode der zweiten Ableitung wie der Newtonschen darin, dass sie die Qualität einer quadratischen Terminierung aufweist. Dies bedeutet, dass eine quadratische Funktion in einer endlichen Anzahl von Schritten minimiert werden kann. Eine Methode wie der Gradientenabstieg hängt stark von der Lernrate ab. Dies kann dazu führen, dass die Optimierung entweder langsam konvergiert, weil sie um das Optimum herum springt, oder vollständig divergiert. Stabile Lernraten sind zu finden ... aber es muss der Hessische berechnet werden. Selbst wenn Sie eine stabile Lernrate verwenden, können Sie Probleme wie das Schwingen um das Optimum haben, dh Sie gehen nicht immer einen "direkten" oder "effizienten" Weg zum Minimum. Das Beenden kann daher viele Iterationen dauern, auch wennSie sind relativ nah dran. Die Konvergenz von BFGS und Newton kann schneller erfolgen, obwohl der Rechenaufwand für jeden Schritt höher ist.

Zu Ihrer Anfrage nach Beispielen: Angenommen, Sie haben die objektive Funktion

F(x)=12xTEINx+dTx+c
Der Gradient ist
F(x)=EINx+d
und es in die steilste Abstiegsform mit konstanter Lernrate bringen
xk+1=xk-α(EINxk+d)=(ich-αEIN)xk-αd.

Dies wird stabil sein, wenn die Größen der Eigenvektoren von ich-αEIN sind kleiner als 1. Wir können diese Eigenschaft verwenden, um zu zeigen, dass eine stabile Lernrate zufriedenstellend ist

α<2λmeinx,
wo λmeinx ist der größte Eigenwert von EIN. Die Konvergenzrate des Algorithmus mit dem steilsten Abfall ist durch den größten Eigenwert begrenzt und die Routine konvergiert am schnellsten in Richtung ihres entsprechenden Eigenvektors. Ebenso konvergiert es am langsamsten in Richtungen des Eigenvektors des kleinsten Eigenwerts. Wenn es eine große Diskrepanz zwischen großen und kleinen Eigenwerten für gibtEIN, Gradientenabstieg wird langsam sein. IrgendeinEIN Mit dieser Eigenschaft konvergieren Sie langsam mit Gefälle.

Im spezifischen Kontext neuronaler Netze enthält das Buch Neural Network Design zahlreiche Informationen zu numerischen Optimierungsmethoden. Die obige Diskussion ist eine Zusammenfassung von Abschnitt 9-7.

Sycorax sagt Reinstate Monica
quelle
Gute Antwort! Ich akzeptiere die Antwort von @Dougal, da ich denke, dass sie eine einfachere Erklärung liefert.
Bar,
6

Bei der konvexen Optimierung approximieren Sie die Funktion als Polynom zweiten Grades in einem eindimensionalen Fall:

f(x)=c+βx+αx2

In diesem Fall ist die zweite Ableitung

2f(x)/x2=2α

Wenn Sie die Derivate kennen, ist es einfach, die nächste Vermutung für das Optimum anzustellen:

vermuten=-β2α

Der multivariate Fall ist sehr ähnlich. Verwenden Sie nur Gradienten für Derivate.

Aksakal
quelle
2

@Dougal hat schon eine tolle technische Antwort gegeben.

Die nicht mathematische Erklärung lautet, dass während die lineare Approximation (Ordnung 1) eine "Ebene" liefert, die tangential zu einem Punkt auf einer Fehleroberfläche ist, die quadratische Approximation (Ordnung 2) eine Oberfläche liefert, die die Krümmung der Fehleroberfläche umgibt.

Die Videos auf diesem Link leisten einen großartigen Beitrag zur Visualisierung dieses Konzepts. Sie zeigen Annäherungen an die Funktionsoberfläche in der Reihenfolge 0, 1 und 2 an, wodurch nur intuitiv überprüft wird, was die anderen Antworten mathematisch darstellen.

Auch ein guter Blogpost zum Thema (angewendet auf neuronale Netze) ist hier .

Zhubarb
quelle