Gradientenabstiegsverfahren

Entscheidungsbäume, Random Forest, Support Vektor Maschinen, Neuronale Netze, ...

Moderator: consuli

Antworten
programming_newbie

Gradientenabstiegsverfahren

Beitrag von programming_newbie »

Guten Morgen R Forum,

ich habe eine Frage zum implementieren eines Gradientenabstiegsverfahrens zu einer (exponential) Funktion in R.

Angenommen meine Funktion sei foo(x) und ich möchte dem Verfahren ebenfalls die Gradientenfunktion grad(x) mitgeben.

Die Aufgabe ist, eine numerische Minimierung (mit 1 Variable x) zu implementieren bzw. durchzuführen a.H.d folgenden R Funktion:

Code: Alles auswählen

abstiegsverfahren <- function(x0,fk, gr, abbruch, schrittweite){
}
Dabei soll "x0" der start Wert des Verfahrens sein
"fk" soll die zu minimierende Funktion sein
"gr" soll die Gradientenfkt sprich die Ableitung von fk sein.
"abbruch" soll der Differenz zwischen xi+1 - xi sein, bei der das Verfahren terminiert.
"schrittweite" soll die Schrittweite des Verfahrens sein (hinreichend klein)
Am Ende soll eine liste mit par (x-Wert an der stelle des minimums zugriff mit result$par) und value (Funktionswert im minimum mit result$value) sowie iter als Anzahl der benötigten iterationen angegeben werden.

Mein bisheriges Verständnis des Gradientenverfahrens ist wie folgt:

1) initialisiere zufälligen Startwert x0
2) setze x0 in die Gradientenfunktion ein
3) falls der daraus resultierende Wert > 0 ist, so muss xi+1 um schrittweite verringert werden, falls er < 0 ist gilt xi+1 = xi + schrittweite
3.1) (in der Aufgabe soll pro iteration ein update xi+1 = xi- schrittweite* grad(xi) erfolgen; den Grund dafür habe ich nicht verstanden.. sollte nicht einfach das xi+1 um alpha vergrößert bzw. verkleinert werden?
4) Abbruchkriterium des Verfahrens nicht verstanden. Abbruch wenn Minimum erreicht wird, aber wie erkenne ich das bzw. teile das R mit?

mein bisheriges Vorgehen in R:

Code: Alles auswählen

#fk und gr seien bereits implementiert, sprich ich habe die funktion eingegeben und deren Ableitung gebildet

abstiegsverfahren <- function(x0,fk, gr, abbruch, schrittweite) {
		x0 <- runif(1,-100,100)     #zufälligen Startwert initialisieren
		# ab hier weiß ich nichtmehr weiter. ist hier nun eine optim() Funktion anzusetzen? 
		# welche Kontrollstruktur macht hier Sinn, um die Schleife aufzubauen bzw sie wieder zu verlassen.?
}
Besten Dank und Grüße,

ein Anfänger
consuli
Beiträge: 479
Registriert: Mo Okt 10, 2016 8:18 pm

Re: Gradientenabstiegsverfahren

Beitrag von consuli »

Wenn Du es nicht gerade für eine universitäre Aufgabe brauchst, wo eine manuelle Ermittlung des Gradienten verlangt ist, gäbe es das in R auch schon fertig.

Die Standard R Gradienten findest Du im R Taskview Optimization. Einige davon geben bestimmt auf den temporären Gradienten(vektor) raus.

Weitere Gradientenfunktionen liefert die Suche

Code: Alles auswählen

library(sos)
???"gradient"
Consuli
Irmgard.
Athomas
Beiträge: 768
Registriert: Mo Feb 26, 2018 8:19 pm

Re: Gradientenabstiegsverfahren

Beitrag von Athomas »

Ich weiß ja, dass "Gradientenabstiegsverfahren" eine halbwegs zutreffende Übersetzung von "gradient descent" ist - aber da kri'sch Plack, wie Jürgen Milski sagen würde!
Tut das denn wirklich Not (frei nach Meister Röhrich)?

Selbst die deutsche Wikipedia belässt es bei "Gradientenverfahren"!
consuli
Beiträge: 479
Registriert: Mo Okt 10, 2016 8:18 pm

Re: Gradientenabstiegsverfahren

Beitrag von consuli »

Ups, der Zusammenzug von "Gradientenverfahren" und "Verfahren des steilsten Abstiegs" zu "Gradientenabstiegsverfahren" hätte glatt auch von mir kommen können. Die meisten praktischen Optimierungen sind doch Minimierungen von Kosten, Energie- und anderen Ressourcenverbräuchen, oder nicht?

Consuli
Irmgard.
Antworten