3.2 Gradientný zostup

Budete si musieť znova niečo predstaviť - tentoraz ste na vrchole krásnej hory. To nie je také ťažké! Problém je v tom, že teraz nasleduje úloha: rýchlo sa dostať na nohy! Jedným zo spôsobov, ako to urobiť, je najprv sa rozhliadnuť okolo seba a zistiť, ktorým smerom vo vašej oblasti je hora najstrmšia - majte na pamäti, že musíte zostúpiť veľmi rýchlo! Potom môžete urobiť opatrný krok týmto smerom a potom sa zastaviť a znova sa rozhliadnuť. Opäť môžete vidieť, ktorým smerom je hora najstrmšia vo vašej oblasti, urobiť krok týmto smerom a zastaviť sa. Je vám jasné, že môžete pokračovať v opakovaní tohto poradia pozorovania, výberu smeru a výpadu, kým nedosiahnete nohu. Čaká na vás občerstvenie po úspešne splnenej úlohe!

Trocha fyzickej aktivity uprostred lineárneho regresného príbehu nezaškodí, ale cítite, že je tu niečo iné. Funkcia strednej štvorcovej chyby závisí od výberu parametrov \(\beta_0\) a \(\beta_0\) - pre rôzne kombinácie hodnôt \(\beta_0\) a \(\beta_1\) dostaneme rôzne chybové hodnoty. Ak vykreslíme graf tejto funkcie, napríklad pozdĺž osi x zaznamenáme hodnoty \(\beta_0\), pozdĺž osi y zaznamenáme hodnoty \(\beta_1\) a pozdĺž osi z zaznamenáme chybové hodnoty, dostaneme graf, ktorý vyzerá ako ten na obrázku nižšie. Ak označíme náhodný výber parametrov \(\beta_0\) a \(\beta_1\) červenou bodkou, aby sme sa dostali do bodu, pre ktorý je chybová hodnota najmenšia, musíme naozaj ísť dole k päte tohto povrchu. Preto je "technika", ktorú sme vyvinuli v predchádzajúcom príklade, veľmi relevantná. Musíme len prísť na to, ako nájsť najstrmšie smery zostupu. Funkcie nám s tým pomôžu.

Graf funkcie strednej štvorcovej chyby

Najmenšia hodnota funkcie sa nazýva minimálna.

Teraz sa pozrime na kvadratickú funkciu \(f(x)=(x − 1)^2\), ktorej graf je znázornený na obrázku nižšie, a pokúsme sa dosiahnuť jej minimum technikou zostupu - je v bode \(x = 1\) a je 0.

Všimnite si červenú bodku zodpovedajúcu \(x = 3\) (náhodne zvolená), ktorá označuje východiskovú polohu pohybu smerom k minimu tejto funkcie. Zdá sa, že oranžová čiara označuje najstrmší smer, po ktorom môžeme začať klesať. Zaujímavé je, že táto čiara v skutočnosti predstavuje dotyčnicu našej funkcie v bode \(x = 3\). Ak urobíme krok v tomto smere, ocitneme sa v novom bode. Označme jeho hodnotu červenou farbou a zobrazme ju v grafe. Je to o niečo bližšie k očakávanému minimu.

Teraz môžeme postup zopakovať: nakreslime dotyčnicu v novom bode a potom urobme krok pozdĺž tejto čiary.

Po určitom počte krokov nás tento postup privedie k minimálnej funkcii, teda k bodu \(x = 1\).

Táto sekcia je spárovaná s Jupyter Notebook 05-2-gradient_descent.ipynb . Ak chcete obsah ďalej sledovať, kliknite na tlačidlo  a otvorte obsah v Google Colab. Ak si poznámkové bloky prezeráte v lokálnom počítači, vyhľadajte poznámkový blok s rovnakým názvom v obsahu a spustite ho. Podrobnejšie pokyny nájdete v  časti Hands-on Zone a lekcii Jupyter Exercise Notebook.

V zošite, ktorý sprevádza tento materiál, môžete animáciu spustiť sami a uistiť sa, že je to tak.

Predtým, ako sa pustíme do podrobnejšieho postupu, ktorý sme opísali, pripomeňme si, aké sú tieto skutočné tangenty. Pre pevný bod \(x\) sa koeficient smeru dotyčnice v \(x\) rovná hodnote prvej derivácie funkcie v \(x\). Prvou deriváciou našej funkcie je funkcia \(f′(x)= 2x − 2\) a v počiatočnom bode \(x = 3\) je hodnota derivácie \(f′(x)= 4\). To znamená, že dotyčnica má rovnicu \(y = 4x − 8\) (číslo -8 sa získa z podmienky, že táto čiara musí obsahovať bod (3, 4 )). Preto môžeme tiež povedať, že dotyčnica má v určitom bode smer zodpovedajúci derivácii funkcie a pre samotný pohyb v tomto smere je pohyb v smere derivácie v tomto bode. Teraz je dilema, či sa pohybujeme pozdĺž alebo nadol, t.j. ideme opačným smerom, alebo ideme opačným smerom? Keďže chceme ísť na minimum, musíme sledovať smer opačný k smeru derivácie funkcie.

Ak teraz označíme východiskový bod \(x_0\), dostaneme nový bod \(x_1\) krokom v smere derivácie funkcie v bode \(x_0\). Ak označíme dĺžku kroku \(α\), vypočítame hodnotu nového bodu \(x_1\) ako \(x_1 = x_0 − αf′(x_0)\). Keďže postup opakujeme, vypočítame hodnotu bodu \(x_2\) ako \(x_2 = x_1 − αf′(x_1)\) a pokračujeme vo výpočtoch \(x_3 = x_2 − αf′(x_2)\), \(x4 = x_3 − αf′(x_3)\), ... Postup opakujte, kým pre dve po sebe idúce hodnoty, povedzme \(x_{34}\) a \(x_{35}\), nebudú hodnoty funkcie dostatočne blízke, t. j. zatiaľ čo absolútna hodnota rozdielu \(f(x_{35})− f(x_{34})\) nie je menšia ako nejaká vopred určená presnosť, povedzme 0,001. Výpočtovo teda môžeme pristupovať ku konceptu konvergencie v matematike.

 Hodnota α ktorú sme zaviedli, sa nazýva rýchlosť učenia a predstavuje veľmi dôležitý parameter algoritmu, ktorý sme opísali. Ak sú hodnoty pre α veľmi malé, bude nám trvať dlho, kým dosiahneme minimum. Na druhej strane, ak sú hodnoty pre α veľmi vysoké, môže sa stať, že minimum preskočíme alebo spadneme do kľukatej pasce neustálym skákaním okolo neho! Pozrite sa na obrázok nižšie!

Vplyv výberu krokov učenia

Kľukatý zámok

Nezabudnite sami skontrolovať obe tieto správania v sprievodnom poznámkovom bloku pomocou rôznych nastavení pre krok učenia v animácii.

 Algoritmus, ktorý sme opísali, sa nazýva Gradient Descent a napriek svojej jednoduchosti je jedným z najdôležitejších algoritmov v strojovom učení, pretože umožňuje nájsť najmenšiu hodnotu chybovej funkcie. O tomto algoritme je veľa podrobností, ktoré nebudeme rozoberať, o vlastnostiach funkcií, na ktoré je možné tento algoritmus úspešne použiť, numerickom výpočte derivácie a výbere krokov učenia. Všetky je potrebné zvážiť pri praktickej aplikácii algoritmu.

Samotný algoritmus nie je nepríjemný na programovanie, takže sa pustíme do dobrodružstva. Potrebujeme funkciu f, ktorá vypočíta hodnotu danej funkcie, a funkciu f_izvod, ktorá vypočíta hodnotu derivácie danej funkcie. Musíme definovať krok alfa učenia aj kritériá zastavenia: postup pozastavíme, keď sú hodnoty funkcie v dvoch po sebe nasledujúcich iteráciách dostatočne blízko (rozdiel medzi ich hodnotami je menší ako nejaká vopred určená presnosť epsilonu) alebo keď dosiahneme konečný počet iterácií max_broj_iteracija (musíme sa tiež uistiť v prípadoch nevhodných volieb krokov učenia).

Postupujte podľa bloku kódu. Algoritmus začal nastavením východiskového bodu. Keďže bod, v ktorom sa pohybujeme algoritmom gradientného zostupu, je východiskovým bodom ďalšieho kroku, používame značky x_staro a x_novo na ich označenie v po sebe nasledujúcich krokoch. Zostava, ktorú vytvoríme na konci funkcie, obsahuje informácie o tom, či sa algoritmus zastavil, koľko krokov urobí, t. j. aká je potrebná iterácia a akú hodnotu našiel.

def gradient_descent(f, f_derivative, x, alpha, epsilon, max_iterations):

    # nastavte počiatočnú hodnotu pre x
    x_old = x

    # v každej iterácii ...
    for i in range(0, max_iterations):

        # vypočítajte aktuálnu hodnotu pre x
        x_new = x_old - alpha * f_derivative(x_old)

        # a potom skontrolujte, či je splnené kritérium zastavenia
        if np.abs(f(x_new) - f(x_old)) < epsilon:
            break

        # Ak kritérium nie je splnené, pripravte X na ďalšiu iteráciu
        x_old = x_new

    # Na konci celého procesu pripravte správu s informáciami:
    # či sa algoritmus zastaví,
    # koľko iterácií to trvalo,
    # a aká hodnota X bola zistená

    report = {}
    report['stops'] = i != max_iterations
    report['number_of_iterations'] = i
    report['x_min'] = x_old

    return report

Funkciu a jej odvodenie je možné definovať nasledujúcimi blokmi jazyka Python:

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

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

Po spustení funkcie gradijentni_spust pre hodnoty argumentov \(x_0\) = 3, alfa = 0,1, epsilon = 0,001 a max_broj_iteracija = 100 dostaneme, že minimum funkcie je 1,0048, čo môžeme potvrdiť. Kód môžete spustiť aj sami a uistiť sa, že získate výsledok. Nezabudnite preskúmať, ako sa menia výsledky, ak sú vybraté iné hodnoty argumentov.

Teraz sa môžeme vrátiť k problému nájdenia parametrov \(\beta_0\) a \(\beta_1\) lineárnej regresie, pre ktoré by hodnota strednej štvorcovej chyby mala mať najmenšiu hodnotu. Funkcia strednej štvorcovej chyby je funkciou dvoch premenných - závisí od hodnoty parametra \(\beta_0\) a hodnoty parametra \(\beta_1\). Pri práci s funkciami viacerých premenných, všeobecne s n premennými \(x_1, x_2, x_3, ..., x_n\), je derivácia, ktorú sme použili v algoritme gradientného zostupu, zovšeobecnená vektorom parciálnych derivácií - pre každú z premenných vypočítame derivácie jednotlivo. Napríklad pre funkciu \(\frac{1}{2} (x_1^2 + 10x_2^2)\) sa derivácia premennej \(x_1\) získa deklarovaním premennej \(x_2\) ako konštanty a následným použitím štandardných pravidiel na výpočet derivácie, ktoré nás privedú k \(\frac{1}{2} ⋅ 2 ⋅ x_1 = x_1\). Na druhej strane derivácia premennej \(x_2\) sa vypočíta deklarovaním premennej \(x_1\) ako konštanty a použitím štandardných pravidiel na výpočet derivátu. Teraz dostaneme \(\frac{1}{2} ⋅ 10 ⋅ 2 ⋅ x_2 = 10 ⋅ x_2\). Teraz dostaneme, že vektor derivácie jednotlivými premennými (takéto derivácie sa nazývajú parciálne) je vektor \([x_1,10 ⋅ x_2]\). V matematike a dokonca aj v strojovom učení sa tieto vektory nazývajú gradienty, odtiaľ pochádza aj názov samotného algoritmu. Na označenie prechodov používame symbol trojuholníka nadol, \(∇\) nazývaný nabla. Presný zápis gradientu východiskovej funkcie f′ by teda bol \(∇ f(x_1, x_2 )= [x_1 ,10 ⋅ x_2 ]\) a umožnil by nám sledovať, v ktorých smeroch vedenia by sme sa mali počas zostupu individuálne pohybovať.

Ostatné kroky algoritmu gradientného zostupu sa v prípade viacrozmerných funkcií príliš nelíšia: očakávame, že sa algoritmus zastaví po dosiahnutí požadovanej presnosti alebo po vykonaní určitého počtu iterácií.

Teraz, keď sme pochopili, ako funguje gradientný zostup pre funkcie viacerých premenných, vráťme sa k výpočtu parametrov \(\beta_0\) a \(\beta_1\). Povedali sme, že rovnica strednej štvorcovej chyby je \(\frac{1}{N} \sum\limits_{i = 1}^{N}(yi −(\beta_0 + \beta_1xi)))^2\). Keďže ide o funkciu, pre ktorú potrebujeme nájsť minimum, ak si vyhrnieme rukávy a skontrolujeme, dostaneme, že derivácia strednej štvorcovej funkcie podľa \(\beta_0\) je presne \(\frac{2}{N} \sum\limits_{i = 1}^{N}(\beta_0 + \beta_1x_i − y_i)\) a derivácia podľa \(\beta_1\) je presne \(\frac{1}{N} \sum\limits_{i = 1}^{N}(\beta_0 + \beta_1x_i − y_i) ⋅ x_i\). Tieto derivácie označujú, ktorými smermi by sme sa mali pohybovať a o koľko by sme mali opraviť hodnoty pre \(\beta_0\) a \(\beta_1\) v každom kroku iterácie gradientného zostupu.

V poznámkovom bloku môžete tiež vidieť, ako sa tieto hodnoty vypočítavajú pomocou kódu, a potom prejsť celým procesom vlastného prechodového zostupu. Pre sadu nehnuteľností, ktorú sme zaviedli, sa dostaneme k hodnotám \(\beta_0 = 2,056\) a \(\beta_0 = 1,198\).

Povedali sme, že existujú určité predpoklady, ktoré musí funkcia spĺňať, aby sa jej minimum našlo technikou gradientného zostupu (je potrebné, aby bola funkcia diferencovateľná). Je tiež dôležité vedieť, že vo všeobecnosti sa týmto spôsobom dosahuje miestne minimum. Napríklad funkcia na obrázku nižšie má niekoľko lokálnych minimál a iba jedno globálne minimum . V niektorých prípadoch, napríklad, keď je funkcia konvexná, lokálne a globálne minimá sa zhodujú, takže vždy dospejeme k požadovanému riešeniu, globálnemu minimu. Funkcia štvorcovej chyby je konvexná parametrami \(\beta_0\) a \(\beta_1\).

Miestne a globálne minimá.

Oblasť matematiky, ktorá sa zaoberá hľadaním maximálnych a minimálnych hodnôt funkcií (nazývame ich optimá jedným názvom), sa nazýva matematická optimalizácia . Gradientný zostup je len jedným algoritmom z palety tohto poľa.