3.2 Gradijentni spust

Opet ćeš morati nešto da zamisliš - ovoga puta da se nalaziš na vrhu lepe planine. To i ne pada tako teško! Nevolja je što sada sledi zadatak: da se brzo spustiš do podnožja! Jedan način da to uradiš je da prvo pogledaš oko sebe i proveriš duž kog pravca u tvojoj okolini je planina najstrmija - imaj na umu da treba baš brzo da se spustiš! Onda možeš da napraviš jedan pažljivi korak u tom pravcu pa da zastaneš i opet pogledaš oko sebe. Ponovo možeš da primetiš duž kog pravca je planina najstrmija u tvojoj okolini, napraviš korak u tom pravcu i zastaneš. Jasno ti je da ovaj redosled osmatranja, izbora pravca i iskoraka možeš da nastaviš da ponavljaš sve dok ne stigneš do podnožja. Tu te čeka osveženje za uspešno obavljeni zadatak!

Malo fizičke aktivnosti usred priče o linearnoj regresiji nije na odmet, ali naslućuješ da postoji još nešto. Funkcija srednjekvadratne greške zavisi od izbora parametara \(\beta_0\) i \(\beta_0\) - za različite kombinacije vrednosti \(\beta_0\) i \(\beta_1\) dobijamo različite vrednosti greške. Ako nacrtamo grafik ove funkcije, na primer, duž x-ose zabeležimo vrednosti \(\beta_0\), duž y-ose zabeležimo vrednosti \(\beta_1\), a duž z-ose vrednosti greške, dobićemo grafik koji izgleda kao na donjoj slici. Ako crvenom tačkom obeležimo neki nasumični izbor parametara \(\beta_0\) i \(\beta_1\), da bismo stigli do tačke za koju je vrednost greške najmanja, zaista moramo da se spustimo u podnožje ove površi. Zato je ”tehnika” koju smo razvili u prethodnom primeru vrlo relevantna. Potrebno je samo da osmislimo kako da tražimo najstrmije pravce spusta. U tome će nam pomoći izvodi funkcija.

Grafik funkcije srednjekvadratne greške

Najmanja vrednost jedne funkcije se zove minimum.

Posmatrajmo sada kvadratnu funkciju \(f(x)=(x-1)^2\) čiji je grafik prikazan na donjoj slici i pokušajmo da tehnikom spusta stignemo do njenog minimuma - on je u tački \(x=1\) i iznosi 0.

Uočimo i crvenu tačku koja odgovara vrednosti \(x=3\) (nasumično smo je odabrali) i koja označava startnu poziciju kretanja ka minimumu ove funkcije. Deluje da je narandžastom linijom obeležen najstrmiji pravac duž koga možemo da započnemo spust. Zanimljivo je da ova linija zapravo predstavlja tangentu naše funkcije u tački \(x=3\). Ako duž ovog pravca napravimo korak, naći ćemo se u novoj tački. Obeležimo i njenu vrednost crvenom bojom i prikažimo je na grafiku. Ona je malo bliže očekivanom minimumu.

Sada možemo da ponovimo postupak: nacrtajmo tangentu u novoj tački, a potom i napravimo korak duž tog pravca.

Nakon određenog broja koraka ovaj postupak će nas dovesti do minimuma funkcije, tj. do tačke \(x = 1\).

 Ova sekcija je uparena sa Jupyter sveskom 05-2-gradient_descent.ipynb. Da bi mogao da pratiš sadržaj dalje, klikni na link, a potom i na dugme   da bi se sadržaj otvorio u okruženju   Google Colab. Ukoliko sveske pregledaš na lokalnoj mašini, među sadržajima pronađi svesku sa istim imenom i pokreni je. Za detaljnije instrukcije pogledaj sekciju   Hands-on zona   i lekciju   Jupyter sveske za vežbu  .

U svesci koja prati ovaj materijal možeš i sam da pokreneš animaciju i uveriš se da je tako.

Pre nego što detaljnije prođemo kroz postupak koji smo opisali, podsetimo se kakve su to prave tangente. Za neku fiksiranu tačku x koeficijent pravca tangente u tački x jednak je vrednosti prvog izvoda funkcije u tački \(x\). Prvi izvod naše funkcije je funkcija \(f′(x)= 2x − 2\) i u početnoj tački \(x = 3\) vrednost izvoda je \(f′(x)= 4\). To znači da tangenta ima jednačinu \(y = 4x − 8\) (broj -8 smo dobili iz uslova da ova prava mora da sadrži tačku (3,  4 )). Zato možemo i da kažemo da tangenta ima pravac koji odgovara izvodu funkcije u nekoj tački, a za samo kretanje u tom pravcu da je kretanje duž pravca izvoda u toj tački. Sada je dilema da li se krećemo uz ili niz, tj. da li pratimo pravac izvoda ili njemu suprotan pravac? Pa , pošto želimo da se spuštamo ka minimumu, treba da pratimo pravac suprotan pravcu izvoda funkcije.

Ako sada sa \(x_0\), obeležimo početnu tačku, novu tačku \(x_1\) dobili smo tako što smo napravili korak duž pravca izvoda funkcije u tački \(x_0\). Ako sa \(α\) obeležimo dužinu koraka, vrednost nove tačke \(x_1\) izračunavamo kao \(x_1 = x_0 − αf′(x_0)\). Pošto postupak ponavljamo, vrednost tačke \(x_2\) izračunavamo kao \(x_2 = x_1 − αf′(x_1)\) i nastavljamo redom sa izračunavanjima \(x_3 = x_2 − αf′(x_2)\), \(x4 = x_3 − αf′(x_3)\), … Postupak ponavljamo sve dok za dve uzastopne vrednosti, recimo za \(x_{34}\) i \(x_{35}\), vrednosti funkcije nisu dovoljno blizu, tj. dok apsolutna vrednost razlike \(f(x_{35})− f(x_{34})\) nije manja od neke unapred zadate tačnosti, recimo 0,001. Tako računski možemo da se približimo pojmu konvergencije u matematici.

 Vrednost α koju smo uveli se zove   korak učenja   (eng.  learning rate  ) i predstavlja vrlo važan parametar algoritma koji smo opisali. Ukoliko su vrednosti za α veoma male, trebaće nam mnogo vremena da stignemo do minimuma. Sa druge strane, ako su vrednosti za α veoma velike, može se desiti da preskočimo minimum ili zapadnemo u cikcak zamku stalnim skakutanjima oko njega! Pogledaj donju sliku!

Uticaj izbora koraka učenja

Cikcak zamka

Oba ova ponašanja obavezno proveri i sam u pratećoj svesci koristeći različita podešavanja za korak učenja u animaciji.

 Algoritam koji smo opisali se zove gradijentni spust (eng.  gradient descent) i uprkos svojoj jednostavnosti predstavlja jedan od najvažnijih algoritma u mašinskom učenju jer omogućava pronalaženje najmanje vrednosti funkcije greške. Postoji mnogo detalja u vezi sa ovim algoritmom u koje mi nećemo zalaziti, a koji se tiču osobina funkcija na koje ovaj algoritam može uspešno da se primeni, numeričkog izračunavanja izvoda i izbora koraka učenja. Svi oni se moraju razmotriti prilikom praktične primene algoritma.

Sam algoritam nije neugodno isprogramirati pa ćemo se upustiti u avanturu. Potrebna nam je funkcija f, koja će da računa vrednost zadate funkcije, i funkcija f_izvod, koja će da izračunava vrednost izvoda zadate funkcije. Potrebno je da definišemo i korak učenja alfa i zaustavne kriterijume: postupak ćemo obustaviti kada vrednosti funkcije u dvema uzastopnim iteracijama budu dovoljno blizu (razlika njihovih vrednosti je manja od neke unapred zadate tačnosti epsilon) ili kada dostignemo neki konačan broj iteracija max_broj_iteracija (moramo da se osiguramo i u slučajevima nepodesnih izbora koraka učenja).

Sledi blok sa kodom. Algoritam smo započeli postavljanjem početne tačke. Kako tačka u kojoj se pomerimo algoritmom gradijentnog spusta predstavlja početnu tačku narednog koraka, za njihovo obeležavanje u uzastopnim koracima koristimo oznake x_staro i x_novo. Izveštaj koji kreiramo na kraju funkcije sadrži informacije o tome da li se algoritam zaustavio, koliko mu je koraka, tj. iteracija trebalo i koju vrednost je pronašao.

def gradient_descent(f, f_derivative, x, alpha, epsilon, max_iterations):
    # set the initial value for x
    x_old = x
    # in each iteration ...
    for i in range(0, max_iterations):
        # calculate the current value for x
        x_new = x_old - alpha * f_derivative(x_old)

        # and then check if the stopping criterion is met
        if np.abs(f(x_new) - f(x_old)) < epsilon:
            break
       # if the criterion is not met, prepare x for the next iteration
        x_old = x_new
    # at the end of the whole process, prepare a report with information:
    # whether the algorithm stops,
    # how many iterations it lasted,
    # and what value of x was found
    report = {}
    report['stops'] = i != max_iterations
    report['number_of_iterations'] = i
    report['x_min'] = x_old
    return report

Funkciju koju smo razmatrali i njen izvod možemo definisati sledećim Python blokovima:

def f(x):
   return (x-1)**2

def f_izvod(x):
   return 2*x-2

Nakon pokretanja funkcije gradijentni_spust za vrednosti argumenata x0 = 3, alfa = 0.1, epsilon = 0.001 i max_broj_iteracija = 100 dobijamo da je minimum funkcije broj 1,0048 što možemo i da potvrdimo. Kôd možeš i sam da izvršiš i uveriš se da se dobija baš ovaj rezultat. Ne propusti da ispitaš i kako se rezultati menjaju ukoliko se odaberu druge vrednosti argumenata.

 Sada možemo da se vratimo i na problem pronalaženja parametara \(\beta_0\) i \(\beta_1\) linearne regresije za koju vrednost srednjekvadratne greške treba da ima najmanju vrednost. Funkcija srednjekvadratne greške je funkcija dveju promenljivih - zavisi i od vrednosti parametra \(\beta_0\) i od vrednosti parametra \(\beta_1\). Kada radimo sa funkcijama više promenljivih, u opštem slučaju sa n promenljivih \(x_1,  x_2, x_3, ..., x_n\), izvod koji smo koristili u algoritmu gradijentnog spusta uopštavamo vektorom parcijalnih izvoda - za svaku od promenljivih izračunavamo pojedinačno izvode. Recimo , za funkciju \(\frac{1}{2} (x_1^2 + 10x_2^2)\), izvod po promenljivoj \(x_1\) se dobija tako što se promenljiva \(x_2\) proglasi konstantom pa potom primene standardna pravila za računanje izvoda koja nas dovode do  \(\frac{1}{2} ⋅ 2 ⋅ x_1 = x_1\).  Sa druge strane, izvod po promenljivoj \(x_2\) se računa tako što se promenljiva \(x_1\) proglasi konstantom pa primene standardna pravila za računanje izvoda. Sada dobijamo  \(\frac{1}{2} ⋅ 10 ⋅ 2 ⋅ x_2 = 10 ⋅ x_2\).  Sada dobijamo da je vektor izvoda po pojedinačnim promenljivama (takve izvode zovemo parcijalnim) vektor \([x_1,10 ⋅ x_2]\). U   matematici, pa i u mašinskom učenju, ovi vektori se zovu   gradijenti   pa otuda dolazi i ime samog algoritma. Za obeležavanje gradijenata se koristi simbol trouglić nadole,  \(∇\) koji se zove nabla. Tako bi precizan zapis gradijenta polazne funkcije f′ bio   \(∇ f(x_1, x_2 )= [x_1 ,10 ⋅ x_2 ]\) i   omogućavao bi nam da pratimo duž kojih pravaca izvoda pojedinačno treba da se krećemo prilikom spusta.

Ostali koraci algoritma gradijentnog spusta se ne razliku mnogo za slučaj funkcija više promenljivih: očekujemo da se algoritam zaustavi nakon što se ostvari željena tačnost ili nakon što se izvrši određeni broj iteracija.

 Sada kada razumemo i kako gradijentni spust funkcioniše za funkcije više promenljivih vratimo se na izračunavanje parametara \(\beta_0\) i \(\beta_1\). Rekli smo da je jednačina srednjekvadratne greške \(\frac{1}{N} \sum\limits_{i = 1}^{N}(yi −(\beta_0 + \beta1xi))^2\). Pošto je to funkcija za koju treba da pronađemo minimum, ako zasučemo rukave pa proverimo, dobićemo da je izvod srednjekvadratne funkcije po β0 baš \(\frac{2}{N} \sum\limits_{i = 1}^{N}(\beta_0 + \beta_1x_i − y_i)\) i izvod po \(\frac{1}{N} \sum\limits_{i = 1}^{N}(\beta_0 + \beta_1x_i − y_i) ⋅ x_i\). Ovi izvodi nam ukazuju duž kojih pravaca treba da se krećemo i koliko treba da korigujemo vrednosti za \(\beta_0\) i \(\beta_1\) u svakom koraku iteracije gradijentnog spusta.

U svesci možeš da vidiš i kako se ove vrednosti izračunavaju kroz kôd, a potom i da prođeš kroz ceo postupak prilagođenog gradijentnog spusta. Za skup o nekretninama koji smo uveli, stići ćemo do vrednosti \(\beta_0 = 2.056\) i \(\beta_0 = 1.198\).

 Rekli smo da postoje određeni preduslovi koje funkcija treba da zadovolji da bi njen minimum mogao da se pronađe tehnikom gradijentnog spusta (potrebno je da funkcija bude diferencijabilna). Važno je da znaš i da se u opštem slučaju na ovaj način dostiže neki   lokalni minimum  . Recimo, funkcija na donjoj slici ima nekoliko lokalnih minimuma i samo jedan   globalni minimum  . U nekim slučajevima, recimo kada je funkcija konveksna, lokalni i globalni minimum se poklapaju pa uvek stižemo do željenog rešenja, globalnog minimuma. Funkcija srednjekvadratne greške je konveksna po parametrima \(\beta_0\) i \(\beta_1\).

Lokalni i globalni minimum

 Oblast matematike koja se bavi pronalaženjem maksimalnih i minimalnih vrednosti funkcija (jednim imenom ih zovemo optimumima) zove se   matematička optimizacija  . Gradijentni spust je samo jedan algoritam iz palete ove oblasti.

3.2 Gradijentni spust.pdf