Förslag på att göra gradient descent mer robust

Hej!

De senaste dagarna har jag lattjat lite med optimeringsalgoritmen gradient descent för att försöka minimera funktioner. Metoden går ut på att stegra längs funktionsytan i den riktning som funktionen minskar mest i.

Givet en funktion $f:D\subseteq\mathbb{R}^n \to \mathbb{R}$ och en punkt $\mathbf{x}_k$ beräknar man alltså gradienten $\nabla f\left(\mathbf{x}_k\right)$ , och inkrementerar sitt $\mathbf{x}$ enligt $\mathbf{x}_{k+1} = \mathbf{x}_k - \lambda\nabla f\left(\mathbf{x}_k\right)$ för $\lambda\in\mathbb{R}$ . Sedan upprepar processen. Då $\mathbf{x} \to \mathbf{x}_{\text{min}}$ gäller $||\nabla f\left(\mathbf{x}\right)|| \to 0$ , så ju närmare sitt minimum man kommer, desto mindre blir varje steg. Idealt terminerar man när storleken på gradienten är "tillräckligt liten", alltså

$\displaystyle \left|\left|\nabla f\left(\mathbf{x}\right)\right|\right| <\varepsilon$

för något mycket litet $\varepsilon$

Det finns dock några ganska enorma problem med en så "enkel" implementering som ovan som jag har stött på:

Metoden fungerar extremt dåligt för funktioner som är "för platta" nära sina minima, exempelvis $f\left(x,y\right)=x^4+y^4$ . I mina tester med $\lambda = 0.\! 1$ , och initialgissning $(x_0,y_0) = (1,1)$ får jag inte ens konvergens på en miljon iterationer.
Det är väldigt enkelt att fastna i lokala minima eller till och med sadelpunkter.

Jag undrar nu om ni har några bra förslag för att lösa ovanstående problem. Vad gäller det andra problemet hade jag en idé om att man kan skapa en sfär runt sitt föreslagna minimum, och utvärdera funktionen i några representativa punkter på den sfären. Om man då hittar en punkt som har ett lägre värde än punkten man är i, hoppar man till det lägsta värdet man hittar och börjar om iterereringen.

Skulle det fungera eller blir det för "kostsamt" numeriskt? Det känns som om det borde fungera ganska bra så länge funktionen inte beter sig alltför illa (dvs. att det faktiskt finns punkter som representerar funktionens beteende i en omgivning till dem).

Ett annat alternativ skulle kunna vara att slumpa fram olika initialgissningar som är långt ifrån varandra och se om man når samma minimum.

Vad gäller det första problemet har jag faktiskt ingen aning om hur man skulle kunna bära sig åt.

Optimering är lite av en konstform, som jag dessvärre har begränsade färdigheter i, så jag hoppas att någon mer kunnig kan göra ett inspel! ^_^

Men i väntan på det skulle jag föreslå att ta hänsyn till högre derivator, särskilt i situationer där man har tillgång till en explicit formel för derivatorna (om man måste uppskatta de högre derivatorna numeriskt blir det lite trixigare).

En bra början kan vara Newtons metod där man tar hänsyn till både förstaderivatorna (gradienten) och andraderivatorna (Hessianen).

Hej, tack för svar!

Jag vill att algoritmen ska vara väldigt allmän (för det jag tänker använda detta för senare (residualminimering) kommer det garanterat saknas explicita derivator).

Hur som helst: borde man inte kunna approximera högre ordningens derivator på samma sätt som man approximerar första ordningens? För första ordningen använder jag bara för ett mycket litet $h$ ,

$\displaystyle \frac{\partial f}{\partial x_i}\left(x_i,\dots\right)\approx\frac{f(x_i+h,\dots)-f(x_i-h,\dots)}{2h}$

Då borde man väl bara kunna räkna exempelvis som nedan?

$\displaystyle \frac{\partial^2 f}{\partial x_i^2}\left(x_i,\dots\right)\approx\frac{f_{x_i}(x_i+h,\dots)-f_{x_i}(x_i-h,\dots)}{2h}$

Absolut! Vilket för oss in på quasi-Newton-metoder, och den väldigt populära L-BFGS-algoritmen, som i grova drag går ut på att göra just det du föreslår på ett smart sätt. Det är ofta defaultalternativet i många optimeringspaket.

Tack för tipsen! Ska läsa på.

Svara

Visa senaste svar