Gradient Descent

Uppdaterad på September 03, 2024 3 minuter läst

Gradient Descent cover image

Introduktion

Föreställ dig att vi har en funktion $f(x)$ och vi skulle vilja hitta dess minimum. Vad skulle du göra ?

Enkelt eller hur? Vi behöver bara lösa följande ekvation:

$$f’(x) = 0$$

Saken är den att det inte alltid är lätt att hitta formeln $f’$ eftersom de tenderar att vara extremt komplicerade, särskilt i djupinlärning där vi hanterar komplexa funktioner. Så vi måste hitta en annan metod som kan ge oss minimum av en funktion utan att behöva hitta formeln för derivatan $f’$.

Låt oss bygga lite intuition

Låt oss anta att vi har en funktion f med motsvarande graf:

Graph 1

Låt oss börja med en slumpmässig punkt $x_{0}$. Målet är att flytta denna punkt och göra den närmare och närmare $x*$ så att $f’($x*$) = 0$. Så problemet kan delas upp i två delar:

  • I vilken riktning ska vi flytta punkten $x$? Vänster eller höger ?

  • Hur mycket ska vi flytta den?

Riktningen

Låt oss bygga lite intuition för att svara på den första frågan. Ta en titt på följande punkt:

Graph 2

Graph 3

Anteckna det:

  • när punkten $x_{0}$ ligger till höger om den optimala punkten $x*$ går dess tangentlinje uppåt.

  • när punkten $x_{0}$ ligger till höger om den optimala punkten $x*$ går dess tangentlinje nedåt.

Riktningen på en linje bestäms av tecknet på dess lutning:

  • En linje går upp $\implies$ lutningen $a$ är positiv.

  • En linje går ner $\implies$ lutningen $a$ är negativ.

Observera att: \

Lutningen för tangentlinjen för en funktion i en viss punkt $x_{0}$ är inte mer än derivatan i den punkten $f’(x_{0})$:

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

Så som ett svar på frågan “Vart ska vi flytta $x_{0}$ ?”:

  • $f’(x_{0}) < 0$ $\implies$ $x_{0}$ till höger om $x*$ $\implies$ Vi måste flytta $x_{0}$ åt vänster.

  • $f’(x_{0}) > 0$ $\implies$ $x_{0}$ till vänster om $x*$ $\implies$ Vi måste flytta $x_{0}$ åt höger.

Stegen

Nu till den andra frågan, Hur mycket ska vi flytta $x_{0}$ ?

Ta en titt på följande exempel:

Graph 4

Graph 5

Vi kan dra slutsatsen att:

  • $x_{0}$ är nära $x*$ => Tangensens lutning är liten => $f’(x_{0})$ är liten.

  • $x_{0}$ är långt från $x*$ => Tangensens lutning är stor => $f’(x_{0})$ är stor.

Genom att svara på båda frågorna drog vi slutsatsen att endast kunskapen om derivatan i punkten $x_{0}$ kan ge oss mycket insikt om riktningen och avståndet för den optimala punkten $x_{0}$.

Gradientnedstigning

Gradient descent är formuleringen av svaren på de två föregående frågorna. Det är en iterativ optimeringsalgoritm som approximerar minsta $x*$ funktion med början från en slumpmässig startpunkt $x_{0}$. Algoritmen anges enligt följande:

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

var:

  • $ \frac{\mathrm{d} f}{\mathrm{d} x*{n}} $ är inte mer än derivatan av $f$ i punkten $x*{n}$.

  • $lr$ är en positiv konstant som avgör hur stora stegen kommer att bli.

Lägg märke till att:

  • $x_{n}$ är till höger om $x*$ => $\frac{\mathrm{d} f}{\mathrm{d} x_{n}} > 0 $ => $ x_{n+ 1} = x_{n} - positiv $ => $x_{n}$ flyttas till vänster.

  • $x_{n}$ är till vänster om $x*$ => $\frac{\mathrm{d} f}{\mathrm{d} x_{n}} < 0$ => $ x*{n +1} = x*{n} + positiv $ => $x_{n}$ flyttas åt höger.

  • $x_{n}$ nära $x*$ => $\frac{\mathrm{d} f}{\mathrm{d} x_{n}}$ nära $0$ => Liten uppdatering till $x_{ n}$.

Frågesport

  • När slutar gradientnedstigning att iterera:

  • När $x_{n}$ är tillräckligt liten.

  • När $x_{n}$ är nära $x_{0}$ .

  • När $\frac{\mathrm{d} f}{\mathrm{d} x_{n}} = 0 $. XXX

  • Hur väljer vi $x_{0}$:

– Vi väljer det slumpmässigt. XXX

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

– Det beror på problemet.

  • Varför behöver vi gradientnedstigning:

– För att datorer inte är tillräckligt kraftfulla för att beräkna derivator.

  • För att det är extremt svårt att hitta derivatformlerna för modeller för djupinlärning. XXX

– Eftersom funktioner har mer än ett lokalt minimum.