Optimalisering med Gradient Descent

Gradient Descent er ein metode for å finna min / max-punkt for funksjonar som kan vera av både ein og fleire variable. Den blir blant anna brukt for å trena Nevrale Nett. Vi skal finna minpkt for funksjonen $f(x) = x^4 - 3x^3$. Sjå figur:

For å gjera dette treng vi den deriverte av funksjonen $f'(x) = 4x^3 - 9x^2$. Vi kan greit finna nullpunktet ved regning. Då set vi $f'(x) = 0$ og løyser. Svaret er $xmin = \frac{9}{4} = 2.25$. Så dette er vår fasit. (Den andre løysinga $x=0$, er eit terassepunkt, ikkje eit minimalpunkt.)

Så la oss like godt definera dette som ein funksjon:

def df(x):
    return 4*x**3 - 9*x**2

Vi kan gjerne gjera ein liten test for å sjå om den fungerer. I punktet x = 1, skal vi få $4\cdot 1 - 9\cdot 1 = -5$

print("f'(1)=",df(1))

f'(1)= -5

Godt! Då kan vi fortsetja med algoritmen vår. Den skal vera ein iterativ algoritme som er slik at når vi startar med ein verdi xmin, så vil den sakte men sikkert flytta xmin til vi finn eit minimalpunkt. Det er i allefall planen! La oss setja xmin = 1 no (seinare kan vi endra den), og som første forsøk kan vi tenkja oss at vi vil flytta xmin med eit fast steg, feks 0.01. Spørsmålet er kva retning skal vi flytta i? Av figuren ser vi at hvis vi er til venstre for xmin, så er den deriverte negativ, men vi skal flytta til høgre, altså i positiv x-retning. Motsatt, hvis vi er til høgre for xmin, så er den deriverte positiv og vi skal flytta til venstre i negativ x. Med andre ord kan vi setja:

n = 0
xmin = 1
while n < 3:
    if df(xmin) > 0:
        dx = -0.01
    else:
        dx = 0.01
    xmin += dx
    print("xmin:",xmin)
    n +=1

xmin: 1.01
xmin: 1.02
xmin: 1.03

OK, så vi flyttar oss i riktig retning, men det går jo seint! Det vi egentlig vil er at vi skal ta relativt store steg når vi er langt frå minimum, og mindre og mindre når vi nærmar oss. Det vi veit om polynom er at den deriverte blir mindre og mindre jo nærmare vi er eit minimalpunkt. Derfor gir det meining å la steglengden variera med $f'(x)$. Men vi må multiplisera med ein faktor, fordi $f'(1) = 5$, og det blir altfor langt å flytta med steglengde på 5. Så vi prøver med:

dx = -0.01*df(xmin)

Første iterasjon skal vi då få dx = - 0.01*(-5) = 0.05. Altså er det nye xmin = 1.05. Så la oss kjøra den nye koden:

n = 0
xmin = 1
while n < 10:
    dx = -0.01*df(xmin)
    xmin += dx
    print("xmin:",xmin)
    n +=1

xmin: 1.05
xmin: 1.1029200000000001
xmin: 1.1587338168953165
xmin: 1.2173419721841299
xmin: 1.278554696586763
xmin: 1.3420756441604222
xmin: 1.4074885809481352
xmin: 1.4742499981601451
xmin: 1.5416910054811388
xmin: 1.6090316742946489

Her har vi også latt løkka gå til 10. Dette ser ut til å fungera som vi vil, og vi er ganske nær mål. Men vi må laga eit ordenlig stoppkriterium. Antal iterasjonar fungerer ikkje så bra, for det svaret vi då får vil avhenga både av startverdien til xmin, og funksjonen. Eit betre valg er å la løkka gå heilt til steglengda blir liten nok. Då kan vi funne bunnpunktet med ein ein gitt presisjon. Men vi kan ikkje vera sikre på at vi finn punktet, så vi beheld kravet om at n ikkje må overstiga ei gitt grense, While-setningen blir dermed:

while (abs(dx) > presisjon) and (n < N):

No er det ein siste endring vi treng, og den er viktig. For hvis vi kjører programmet vårt med feks xmin = -2, så vil det bli fanga i det stasjonære punktet i x = 0. Grunnen er at der er den deriverte lik (eller tilnærma lik) null, og det medfører at steglengda dx blir null. Vi kjem ikkje vidare! For å løysa dette innfører vi ein parameter M som kan kallast momentum eller ein slags masse. Hvis vi tenkjer fysisk så er massen den som gjer at ein ikkje kan stoppa bevegelsen til ein gjenstand momentant. Dette kan vi også få til her, hvis vi endrar koden til:

dx = M\*dx - G\*df(xmin)

Dette gjer at sjøl om den deriverte skulle bli null, så stoppar ikkje bevegelsen men ein gong, fordi vi tar med oss litt av den forrige dx. M er ein konstant som vi set lik 0.5. Når vi gjer det slik har vi også mulighet for å gi dx ein startverdi, som gjer at vi unngår å bli fanga hvis vi set xmin = 0 som startverdi,

No har vi eit fungerande program. Men det vanlig å gi navn til alle konstantane vi har brukt. Det gir oss eit program som både er meir lettlest, og lettare å vedlikehalda:

def df(x):
    return 4 * x**3 - 9 * x**2

xmin = -2 # Startpunkt 
G = 0.01 # Faktor for steg
M = 0.5 #Momentum (treghet())
presisjon = 0.000001
dx = 0.1 #Steglengde (blir endra inne i løkka)
N = 10000 # max antal iterasjonar
n = 0 # teljar

while (abs(dx) > presisjon) and (n < N):
    dx = M*dx - G*df(xmin)
    xmin += dx
    n +=1

print("Fant eit lokalt minimum i x =", xmin,"etter",n,"iterasjonar")

Fant eit lokalt minimum i x = 2.249991816775647 etter 173 iterasjonar

Denne koden ser ut til å fungera. Hvis du kjører programmet med ein printsetning som skriv ut dx etter kvar gong den er rekna ut, så vil du sjå at den startar med ein høg verdi, og minkar etter kvart. Men du vil også sjå at xmin skyt forbi bunnpunktet og svingar litt fram og tilbake før den roar seg nær bunnen - på same måten som ei kule eller ein ball som trillar nedover ein bakke vil rulla litt opp på motsatt side før den roar seg i bunnen.

Oppgaver:

1. Prøv ulike verdiar for xmin, og sjekk om vi alltid finn bunnpunktet.
2. Varier parameterane G og M. Korleis oppfører programmet seg då?
3. Prøv å finna bunnpunktet for andre funksjonar, feks $f(x) = x^3-3x$. Finn programmet det rette nullpunktet? Klarer det å finna det uansett startverdi for xmin? Korfor / korfor ikkje?
4. Prøve gjerne også å plotta alle punkta (xmin, f(xmin)) som vi har vore innom på veien. Dette kan vera nyttig når vi skal vurdera ulike verdiar for G og M