Gradient nedstigning

Introduksjon

Tenk deg at vi har en funksjon $f(x)$ og vi vil gjerne finne dens minimum. Hva ville du gjort ?

Enkelt ikke sant? Vi trenger bare å løse følgende ligning:

$f'(x) = 0$

Saken er at det ikke alltid er lett å finne formelen $f'$, da de har en tendens til å være ekstremt kompliserte, spesielt i dyp læring hvor vi arbeider med komplekse funksjoner. Så vi må finne en annen metode som kan gi oss minimum av en funksjon uten å måtte finne formelen til den deriverte $f'$.

La oss bygge litt intuisjon

La oss anta at vi har en funksjon f med den tilsvarende grafen:

La oss starte med et tilfeldig punkt $x_{0}$. Målet er å flytte dette punktet og gjøre det nærmere og nærmere $x*$ slik at $f'($x*$) = 0$. Så problemet kan deles i to deler:

• I hvilken retning skal vi flytte punktet $x$? Venstre eller høyre ?

• Hvor mye skal vi flytte den?

Retningen

La oss bygge litt intuisjon for å svare på det første spørsmålet. Ta en titt på følgende punkt:

Noter det:

• når punktet $x_{0}$ er til høyre for det optimale punktet $x*$ går tangentlinjen opp.

• når punktet $x_{0}$ er til høyre for det optimale punktet $x*$ går tangentlinjen ned.

Retningen til en linje bestemmes av tegnet på skråningen:

• En linje går opp $\implies$ helningen $a$ er positiv.

• En linje går ned $\implies$ helningen $a$ er negativ.

Merk at: \

Helningen til tangentlinjen til en funksjon i et bestemt punkt $x_{0}$ er ikke mer enn den deriverte i det punktet $f'(x_{0})$:

$tangent(x*{0}): g(x) = f'(x*{0}).(x-x*{0}) + f(x*{0})$

Så som et svar på spørsmålet "Hvor skal vi flytte $x_{0}$?":

• $f'(x_{0}) < 0$ $\implies$ $x_{0}$ til høyre for $x*$ $\implies$ Vi må flytte $x_{0}$ til venstre.

• $f'(x_{0}) > 0$ $\implies$ $x_{0}$ til venstre for $x*$ $\implies$ Vi må flytte $x_{0}$ til høyre.

Stegene

Nå til det andre spørsmålet, Hvor mye bør vi flytte $x_{0}$?

Ta en titt på følgende eksempler:

Vi kan konkludere med at:

• $x_{0}$ er nær $x*$ => Helningen til tangenten er liten => $f'(x_{0})$ er liten.

• $x_{0}$ er langt fra $x*$ => Hellingen til tangenten er stor => $f'(x_{0})$ er stor.

Ved å svare på begge spørsmålene konkluderte vi med at kun kunnskapen om den deriverte i punktet $x_{0}$ kan gi oss mye innsikt om retningen og avstanden til det optimale punktet $x_{0}$.

Gradientnedstigning

Gradientnedstigning er formuleringen av svarene på de to foregående spørsmålene. Det er en iterativ optimaliseringsalgoritme som tilnærmer minimum $x*$ funksjon fra et tilfeldig startpunkt $x_{0}$. Algoritmen er angitt som følger:

$x*{n+1} = x*{n} - lr \times \frac{\mathrm{d} f}{\mathrm{d} x\_{n}}$

hvor:

• $\frac{\mathrm{d} f}{\mathrm{d} x*{n}}$ er ikke mer enn den deriverte av $f$ i punktet $x*{n}$.

• $lr$ er en positiv konstant som bestemmer hvor store trinnene skal være.

Legg merke til det:

• $x_{n}$ er til høyre for $x*$ => $\frac{\mathrm{d} f}{\mathrm{d} x_{n}} > 0$ => $x_{n+ 1} = x_{n} - positiv$ => $x_{n}$ flyttes til venstre.

• $x_{n}$ er til venstre for $x*$ => $\frac{\mathrm{d} f}{\mathrm{d} x_{n}} < 0$ => $x*{n +1} = x*{n} + positive$ => $x_{n}$ flyttes til høyre.

• $x_{n}$ nær $x*$ => $\frac{\mathrm{d} f}{\mathrm{d} x_{n}}$ nær $0$ => Liten oppdatering til $x_{ n}$.

Quiz

• Når slutter gradientnedstigning å iterere:

• Når $x_{n}$ er liten nok.

• Når $x_{n}$ er nær $x_{0}$ .

• Når $\frac{\mathrm{d} f}{\mathrm{d} x\_{n}} = 0$. XXX

– Hvordan velger vi $x_{0}$:

– Vi plukker det tilfeldig. XXX

• Vi tar det i nærheten av $x{n}$.

– Det kommer an på problemet.

• Hvorfor trenger vi gradientnedstigning:

– Fordi datamaskiner ikke er kraftige nok til å beregne derivater.

• Fordi det er ekstremt vanskelig å finne derivatformlene til dyplæringsmodeller. XXX

– Fordi funksjoner har mer enn ett lokalt minimum.