Pochopenie Stochastického priemerného gradientu

Gradientový zostup je najobľúbenejšou optimalizačnou technikou v modelovaní strojového učenia (ML). Algoritmus minimalizuje chybu medzi predpovedanými hodnotami a základnou pravdou. Keďže technika berie do úvahy každý dátový bod, aby pochopil a minimalizoval chybu, jej výkon závisí od veľkosti tréningových dát. Techniky ako Stochastic Gradient Descent (SGD) sú navrhnuté tak, aby zlepšili výkon výpočtu, ale za cenu presnosti konvergencie.

Stochastic Average Gradient vyvažuje klasický prístup, známy ako Full Gradient Descent a SGD, a ponúka obe výhody. Ale predtým, než budeme môcť použiť algoritmus, musíme najprv pochopiť jeho význam pre optimalizáciu modelu.

Optimalizácia cieľov strojového učenia s gradientným zostupom

Každý algoritmus ML má pridruženú stratovú funkciu, ktorej cieľom je minimalizovať alebo zlepšiť výkon modelu. Matematicky možno stratu definovať ako:

Je to jednoducho rozdiel medzi skutočným a predpokladaným výstupom a minimalizácia tohto rozdielu znamená, že náš model sa približuje k základným pravdivostným hodnotám.

Minimalizačný algoritmus používa gradientový zostup na prekročenie stratovej funkcie a nájdenie globálneho minima. Každý krok prechodu zahŕňa aktualizáciu váh algoritmu, aby sa optimalizoval výstup.

Plain Gradient Descent

Konvenčný algoritmus zostupu gradientu používa priemer všetkých gradientov vypočítaných v rámci celého súboru údajov. Životný cyklus jedného príkladu školenia vyzerá takto:

Rovnica aktualizácie hmotnosti vyzerá takto:

Kde W predstavuje modelové váhy a dJ/dW je derivácia stratovej funkcie vzhľadom na modelovú váhu. Konvenčná metóda má vysokú mieru konvergencie, ale stáva sa výpočtovo nákladnou pri práci s veľkými súbormi údajov obsahujúcimi milióny údajových bodov.

Stochastic Gradient Descent (SGD)

Metodológia SGD zostáva rovnaká ako pri obyčajnom GD, ale namiesto použitia celého súboru údajov na výpočet gradientov používa malú dávku zo vstupov. Metóda je oveľa efektívnejšia, ale môže príliš preskakovať okolo globálneho minima, pretože každá iterácia využíva na učenie len časť údajov.

Stochastický priemerný gradient

Prístup Stochastic Average Gradient (SAG) bol zavedený ako stredná cesta medzi GD a SGD. Vyberie náhodný údajový bod a aktualizuje jeho hodnotu na základe gradientu v tomto bode a váženého priemeru minulých gradientov uložených pre tento konkrétny údajový bod.

Podobne ako SGD, SAG modeluje každý problém ako konečný súčet konvexných, diferencovateľných funkcií. Pri akejkoľvek iterácii používa súčasné gradienty a priemer predchádzajúcich gradientov na aktualizáciu hmotnosti. Rovnica má nasledujúci tvar:

miera konvergencie

Medzi dvoma populárnymi algoritmami, plným gradientom (FG) a stochastickým gradientom (SGD), má algoritmus FG lepšiu mieru konvergencie, pretože na výpočet využíva celý súbor údajov počas každej iterácie.

Hoci má SAG štruktúru podobnú SGD, jej miera konvergencie je porovnateľná a niekedy lepšia ako prístup s úplným gradientom. Nižšie uvedená tabuľka 1 sumarizuje výsledky z experimentov Schmidt a kol. al .

Ďalšie úpravy

Napriek úžasnému výkonu bolo navrhnutých niekoľko úprav pôvodného algoritmu SGD, aby sa zlepšil výkon.

• Preváženie v skorých iteráciách: Konvergencia SAG zostáva pomalá počas prvých niekoľkých iterácií, pretože algoritmus normalizuje smer s n (celkový počet dátových bodov). To poskytuje nepresný odhad, pretože algoritmus ešte nevidel veľa údajových bodov. Modifikácia navrhuje normalizáciu pomocou m namiesto n, kde m je počet údajových bodov, ktoré sa videli aspoň raz do tejto konkrétnej iterácie.
• Mini-dávky: Prístup Stochastic Gradient využíva mini-dávky na spracovanie viacerých údajových bodov súčasne. Rovnaký prístup možno použiť aj na SAG. To umožňuje vektorizáciu a paralelizáciu pre vyššiu efektivitu počítača. Znižuje tiež zaťaženie pamäte, čo je hlavná výzva pre algoritmus SAG.
• Experimentovanie s veľkosťou kroku: Veľkosť kroku uvedená vyššie (116 l) poskytuje úžasné výsledky, ale autori ďalej experimentovali s použitím veľkosti kroku 1 l. Ten druhý poskytoval ešte lepšiu konvergenciu. Autori však neboli schopní predložiť formálnu analýzu zlepšených výsledkov. Dospeli k záveru, že veľkosť kroku by sa mala experimentovať, aby sa našla optimálna pre konkrétny problém.

Záverečné myšlienky

Gradient zostup je populárna optimalizácia používaná na lokalizáciu globálnych miním poskytovaných cieľových funkcií. Algoritmus používa gradient cieľovej funkcie na prekročenie sklonu funkcie, kým nedosiahne najnižší bod.

Úplný zostup gradientu (FG) a Stochastický zostup gradientu (SGD) sú dve populárne variácie algoritmu. FG používa celý súbor údajov počas každej iterácie a poskytuje vysokú mieru konvergencie pri vysokých výpočtových nákladoch. Pri každej iterácii SGD používa podmnožinu údajov na spustenie algoritmu. Je to oveľa efektívnejšie, ale s neistou konvergenciou.

Stochastic Average Gradient (SAG) je ďalšou variáciou, ktorá poskytuje výhody oboch predchádzajúcich algoritmov. Používa priemer minulých gradientov a podmnožinu množiny údajov na zabezpečenie vysokej miery konvergencie s nízkym výpočtom. Algoritmus je možné ďalej upravovať, aby sa zlepšila jeho účinnosť, pomocou vektorizácie a mini-dávok.