Gradient Descent

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:

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:

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:

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.