Pochopení Stochastického průměrného gradientu

Gradient sestup je nejoblíbenější optimalizační technika v modelování strojového učení (ML). Algoritmus minimalizuje chybu mezi předpokládanými hodnotami a základní pravdou. Protože technika považuje každý datový bod za pochopení a minimalizaci chyby, její výkon závisí na velikosti trénovacích dat. Techniky jako Stochastic Gradient Descent (SGD) jsou navrženy tak, aby zlepšily výpočetní výkon, ale za cenu přesnosti konvergence.

Stochastic Average Gradient vyvažuje klasický přístup, známý jako Full Gradient Descent a SGD, a nabízí obě výhody. Než však budeme moci algoritmus použít, musíme nejprve pochopit jeho význam pro optimalizaci modelu.

Optimalizace cílů strojového učení pomocí gradientního klesání

Každý algoritmus ML má přidruženou ztrátovou funkci, jejímž cílem je minimalizovat nebo zlepšit výkon modelu. Matematicky lze ztrátu definovat jako:

Je to prostě rozdíl mezi skutečným a předpokládaným výstupem a minimalizace tohoto rozdílu znamená, že se náš model přiblíží základním pravdivostním hodnotám.

Minimalizační algoritmus používá gradientní sestup k procházení ztrátové funkce a nalezení globálního minima. Každý krok průchodu zahrnuje aktualizaci vah algoritmu pro optimalizaci výstupu.

Plain Gradient Sestup

Konvenční algoritmus sestupu gradientu používá průměr všech gradientů vypočítaných v celém souboru dat. Životní cyklus jednoho příkladu školení vypadá následovně:

Rovnice aktualizace hmotnosti vypadá takto:

Kde W představuje modelové váhy a dJ/dW je derivace ztrátové funkce s ohledem na modelovou váhu. Konvenční metoda má vysokou míru konvergence, ale stává se výpočetně nákladnou při práci s velkými datovými sadami obsahujícími miliony datových bodů.

Stochastic Gradient Descent (SGD)

Metodika SGD zůstává stejná jako plain GD, ale místo použití celého souboru dat pro výpočet gradientů používá malou dávku ze vstupů. Tato metoda je mnohem efektivnější, ale může příliš přeskakovat kolem globálních minim, protože každá iterace používá pouze část dat pro učení.

Stochastický průměrný gradient

Přístup Stochastic Average Gradient (SAG) byl zaveden jako střední cesta mezi GD a SGD. Vybere náhodný datový bod a aktualizuje jeho hodnotu na základě gradientu v tomto bodě a váženého průměru minulých gradientů uložených pro tento konkrétní datový bod.

Podobně jako u SGD modeluje SAG každý problém jako konečný součet konvexních, diferencovatelných funkcí. Při jakékoli dané iteraci používá pro aktualizaci hmotnosti současné přechody a průměr předchozích přechodů. Rovnice má následující tvar:

Míra konvergence

Mezi dvěma oblíbenými algoritmy, plným gradientem (FG) a stochastickým gradientem sestupem (SGD), má algoritmus FG lepší konvergenční poměr, protože využívá pro výpočet celý soubor dat během každé iterace.

Ačkoli má SAG strukturu podobnou SGD, jeho míra konvergence je srovnatelná a někdy lepší než u přístupu plného gradientu. Tabulka 1 níže shrnuje výsledky z experimentů Schmidt et. al .

Další úpravy

Navzdory úžasnému výkonu bylo navrženo několik úprav původního algoritmu SGD, které pomohou zlepšit výkon.

• Převážení v raných iteracích: Konvergence SAG zůstává pomalá během prvních několika iterací, protože algoritmus normalizuje směr s n (celkový počet datových bodů). To poskytuje nepřesný odhad, protože algoritmus dosud neviděl mnoho datových bodů. Modifikace navrhuje normalizaci pomocí m místo n, kde m je počet datových bodů, které byly vidět alespoň jednou do této konkrétní iterace.
• Mini-dávky: Přístup Stochastic Gradient využívá mini-dávky ke zpracování více datových bodů současně. Stejný přístup lze aplikovat na SAG. To umožňuje vektorizaci a paralelizaci pro lepší efektivitu počítače. Snižuje také zatížení paměti, což je hlavní výzva pro algoritmus SAG.
• Experimentování s velikostí kroku: Velikost kroku zmíněná dříve (116 l) poskytuje úžasné výsledky, ale autoři dále experimentovali s použitím velikosti kroku 1 l. Ten druhý poskytoval ještě lepší konvergenci. Autoři však nebyli schopni předložit formální analýzu zlepšených výsledků. Došli k závěru, že velikost kroku by měla být experimentována, aby se našla optimální velikost pro konkrétní problém.

Závěrečné myšlenky

Gradient sestup je oblíbená optimalizace používaná pro lokalizaci globálních minim poskytovaných cílových funkcí. Algoritmus používá gradient cílové funkce k procházení sklonu funkce, dokud nedosáhne nejnižšího bodu.

Full Gradient Descent (FG) a Stochastic Gradient Descent (SGD) jsou dvě oblíbené varianty algoritmu. FG používá celou datovou sadu během každé iterace a poskytuje vysokou míru konvergence při vysokých nákladech na výpočet. Při každé iteraci používá SGD podmnožinu dat ke spuštění algoritmu. Je mnohem efektivnější, ale s nejistou konvergencí.

Stochastic Average Gradient (SAG) je další variantou, která poskytuje výhody obou předchozích algoritmů. Využívá průměr minulých gradientů a podmnožinu datové sady k zajištění vysoké míry konvergence s nízkým výpočtem. Algoritmus lze dále upravovat pro zlepšení jeho účinnosti pomocí vektorizace a minidávek.