Jak zkrotit údolí - Hessianovské hacky pro optimalizaci velkých #NeuralNetworks

Řekněme, že máte dar letu (nebo jedete na vrtulníku). Jste také špión (jako ve filmech Jamese Bonda). Je vám dána topografie dlouhého úzkého údolí, jak je znázorněno na obrázku, a je vám dán schůzkový bod pro setkání s potenciálním pomocníkem, který má inteligenci, která je užitečná pro váš cíl. Jediné informace, které máte o schůzce, jsou následující:

"Poznejte mě na nejnižší souřadnici" tohoto dlouhého údolí "za 4 hodiny."

Jak postupujete při hledání nejnižšího souřadnicového bodu? Jak to tedy hodláte najít ve stanoveném časovém období?

U složitých neuronových sítí, které mají velmi velké parametry, je chybový povrch neuronové sítě velmi podobný dlouhému úzkému údolí druhů. Nalezení „minima“ v údolí může být docela složité, pokud máte v patologii takové patologické zakřivení.

Poznámka: Existuje mnoho příspěvků napsaných na hackech pro optimalizaci druhého řádu pro Neural Network. Důvod, proč jsem se rozhodl o tom napsat znovu, je ten, že většina z nich skočí přímo do složité matematiky bez velkého vysvětlení.
Místo toho jsem se pokusil vysvětlit Math tak stručně, kde je to možné, a většinou poukazuji na podrobné zdroje, abych se naučil, pokud nejste školeni v konkrétním oboru Math.
Tento příspěvek bude kvůli tomu trochu zdlouhavý.

V minulých příspěvcích jsme používali algoritmy Gradient Descent, zatímco Back-propagating nám pomohl minimalizovat chyby. Techniky najdete v příspěvku s názvem „Backpropagation - Jak se neuronové sítě učí komplexním chováním“

Omezení klesání

S algoritmem Gradient Descent [nebo Stochastic Gradient Descent (SGD) není přesný] nic zásadně špatného). Ve skutečnosti jsme dokázali, že je docela účinný u některých příkladů Feed Forward, které jsme používali v minulosti. Problém SGD vyvstává, když máme „hluboké“ neuronové sítě, které mají více než jednu skrytou vrstvu. Obzvláště když je síť poměrně velká.

Zde je několik ilustrací nemonotonického chybového povrchu hluboké neuronové sítě, abychom získali představu.

Chyba povrchu - 2Chyba povrchu - 2

Všimněte si, že na obrázku je mnoho minim a maxim. Podívejme se rychle na proces aktualizace hmotnosti v SGD

Aktualizace hmotnosti SGD

Problém s použitím SGD pro ilustrace je následující:

  • Protože SGD používá metodu optimalizace prvního řádu, předpokládá, že povrch chyby vždy vypadá jako rovina (ve směru sestupu, která je) a nezohledňuje zakřivení.
  • Pokud existuje kvadratické zakřivení, použijeme několik triků, abychom zajistili, že SGD se nejen odrazí od povrchu, jak je znázorněno v rovnici aktualizace hmotnosti.
  • Hodnotu hybnosti kontrolujeme pomocí předem určeného alfa a regulujeme rychlost pomocí epsilon rychlosti učení.
  • Alfa a epsilon vyrovnávají rychlost a směr SGD a zpomalují optimalizaci, dokud se nespojíme. Tyto hyperparametry můžeme vyladit pouze tak, abychom získali dobrou rovnováhu mezi rychlostí a účinností SGD. Ale stále nás zpomalují.
  • Ve velkých sítích s patologickými křivkami, jak je znázorněno na obrázku, je vyladění těchto hyperparametrů docela náročné.
  • Chyba při SGD se může náhle začít zvyšovat, když se pohybujete ve směru gradientu, když projíždíte dlouhým úzkým údolím. Ve skutečnosti se SGD může téměř zastavit, než může vůbec dosáhnout nějakého pokroku.

Potřebujeme lepší metodu pro práci s velkými nebo hlubokými neuronovými sítěmi.

Optimalizace druhého řádu k záchraně

SGD je problém optimalizace prvního řádu. Metody prvního řádu jsou metody, které mají lineární lokální křivky. V tom předpokládáme, že můžeme použít lineární aproximace k řešení rovnic. Některé příklady metod prvního řádu jsou následující:

  • Sklon sestupu
  • Dílčí přechod
  • Konjugátový přechod
  • Náhodný souřadnicový sestup

Existují metody zvané metody druhého řádu, které zvažují konvexnost nebo zakřivení rovnice a provádí kvadratické aproximace. Kvadratické aproximace jsou rozšířením lineárních aproximací, ale poskytují další proměnnou k řešení, která pomáhá vytvořit kvadratický povrch pro řešení bodu na povrchu chyby.

Klíčový rozdíl mezi aproximacemi prvního řádu a druhého řádu je ten, že zatímco lineární aproximace poskytuje „rovinu“, která je tangenciální k bodu na chybové ploše, aproximace druhého řádu poskytuje kvadratickou plochu, která objímá křivost chybový povrch.

Pokud jste novými kvadratickými aproximacemi, vyzývám vás, abyste si prohlédli tuto přednášku Chánské akademie o Kvadratických aproximacích.

Výhodou metody druhého řádu je, že nebude ignorovat zakřivení chybového povrchu. Vzhledem k tomu, že se uvažuje o zakřivení, jsou metody druhého řádu považovány za metody, které mají lepší krokový výkon.

  • Úplný krokový skok metody druhého řádu ukazuje přímo na minimum zakřivení (na rozdíl od metod prvního řádu, které vyžadují více kroků s výpočtem více gradientů v každém kroku).
  • Protože metoda druhého řádu ukazuje na minimum kvadratického zakřivení v jednom kroku, musíte se jen obávat, jak dobře křivka obejme chybovou plochu. Je to dost dobrý heuristický postup.
  • Práce s hyper-parametry vzhledem k heuristice se stává velmi efektivní.

Následuje několik metod druhého řádu

  • Newtonova metoda
  • Quasi-Newton, Gauss-Newton
  • BFGS, (L) BFGS

Pojďme se podívat na Newtonovu metodu, která je základní metodou a ve srovnání s ostatními je o něco intuitivnější.

Jo! Newton, jaká je tvoje metoda?

Newtonova metoda, nazývaná také Newton-Raphsonova metoda, je iterativní aproximační metodou na kořenech skutečné funkce. Toto je jeden ze základních metod používaných v jakýchkoli problémech s konvexní optimalizací druhého řádu pro přibližné funkce.

Podívejme se nejprve na Newtonovu metodu pomocí prvního derivátu funkce.

Řekněme, že máme funkci f (x) = 0, a máme nějaké počáteční řešení x_0, které považujeme za suboptimální. Poté Newtonova metoda navrhuje, abychom udělali následující

  1. Najděte rovnici pro tečnou čáru na x_0
  2. Najděte bod, ve kterém tečná čára prořízne osu x, a nazvejte tento nový bod jako x_1.
  3. Najděte projekci x_1 na funkci f (x) = 0, která je také na x_1.
  4. Nyní opakujte postup od kroku 1 nahrazením x_0 za x_1.

Opravdu tak jednoduché. Výzva je, že metoda vám neřekne, kdy zastavit, takže přidáme pátý krok následujícím způsobem:

5. Pokud je x_n (aktuální hodnota x) rovna nebo menší než prahová hodnota, zastavíme se.

Zde je obrázek, který zobrazuje výše uvedené:

Nalezení optimální hodnoty X pomocí Newtonovy metody.

Zde je animace, která ukazuje totéž:

animační kredit

Polynomial prvního stupně, jednorozměrný:

Zde je matematika pro funkci, která je polynomem prvního stupně s jednorozměrnou dimenzí.

Polynom druhého stupně, jednorozměrný

Nyní můžeme pracovat na Newtonově aproximaci pro polynomiální funkci druhého stupně (optimalizace druhého řádu) s jednorozměrnou (než se dostaneme k více dimenzím). Polynom druhého stupně má kvadratickou povahu a pro jeho práci by bylo zapotřebí derivátu druhého řádu. Chcete-li pracovat na druhé derivaci funkce, použijeme Taylorovu aproximaci takto:

Polynom druhého stupně, více dimenzí

Předpokládejme, že pracujeme na polynomu druhého stupně s více dimenzemi, pak pracujeme se stejným Newtonovým přístupem, jaký jsme našli výše, ale první deriváty nahrazujeme gradientem a druhý derivace Hessianem následovně:

Hessianova matice je čtvercová matice parciálních derivátů skaláru druhého řádu, která popisuje lokální zakřivení multifunkční funkce.

Konkrétně v případě neuronové sítě je Hessian čtvercovou maticí s počtem řádků a sloupců rovným celkovému počtu parametrů v neuronové síti.

Hessian pro neuronovou síť vypadá takto:

Hessianova matice neuronové sítě

Proč je Hessianský přístup teoreticky lepší než SGD?

Nyní je optimalizace druhého řádu pomocí Newtonovy metody iterativního nalezení optimálního 'x' chytrým hackem pro optimalizaci chybové plochy, protože na rozdíl od SGD, kde jste do bodu x_0 umístili letadlo, a poté určete skok po kroku, v optimalizaci druhého řádu najdeme těsně přiléhající kvadratickou křivku na x_0 a přímo najdeme minima zakřivení. To je mimořádně efektivní a rychlé.

Ale !!! Empiricky si však nyní dokážete představit výpočet Hessiana pro síť s miliony parametrů? Samozřejmě se stává velmi neefektivním, protože množství paměti a výpočet potřebné k výpočtu Hessiana je také kvadratické. Takže, i když teoreticky, je to úžasné, v praxi to saje.

Potřebujeme hack pro hack! Zdá se, že odpověď spočívá v Konjugátních přechodech.

Konjugátové přechody, chytrý trik.

Vlastně existuje několik kvadratických aproximačních metod pro konvexní funkci. Metoda konjugovaného gradientu však funguje docela dobře pro symetrickou matici, která je pozitivní. Ve skutečnosti jsou konjugované přechody určeny pro práci s velmi velkými, řídkými systémy.

Všimněte si, že Hessian je symetrický kolem úhlopříčky, parametry neuronové sítě jsou obvykle řídké, a Hessian neuronové sítě je pozitivní-definovaný (znamená, že má pouze pozitivní hodnoty Eigen). Chlapče, máme štěstí?

Potřebujete-li důkladné zavedení metod konjugovaného gradientu, projděte si článek „Úvod do metody konjugovaného gradientu bez agonizující bolesti“ Jonathana Richarda Shewchuka. Považuji to za docela důkladné a užitečné. Navrhoval bych, abyste si tento článek prostudovali ve volném čase, abyste získali podrobné znalosti o konjugovaných přechodech.

Nejjednodušší způsob, jak vysvětlit přechod konjugátu (CG), je následující:

  • CG Descent je použitelný na jakoukoli kvadratickou formu.
  • CG používá krokovou velikost „alfa“ podobnou SGD, ale namísto fixního alfa najdeme alfa pomocí algoritmu pro vyhledávání řádků.
  • CG také potřebuje „beta“ skalární hodnotu, která pomáhá najít další směr, který je „konjugovaný“ k prvnímu směru.

Můžete zkontrolovat většinu chlupatých matematik kolem příjezdu na CG rovnici podle výše uvedeného článku. Přímo skočím do části algoritmu konjugovaného gradientu:

Pro řešení rovnice Ax = b můžeme použít následující algoritmus:

obrazový kredit
  • Zde r_k je zbytková hodnota,
  • p_k je konjugovaný vektor a
  • x_k + 1 je iterativně aktualizován předchozí hodnotou x_k a tečkovým součinem alfa_k a konjugovaného vektoru p_k.

Vzhledem k tomu, že víme, jak vypočítat gradient konjugátu, podívejme se na optimalizační techniku ​​Hessian zdarma.

Hessianův algoritmus optimalizace

Nyní, když jsme pochopili algoritmus CG, pojďme se podívat na poslední chytrý hack, který nám umožňuje být osvobozen od Hessiana.

CITACE: Optimalizace bez Hessian je technika, kterou James Marten na univerzitě v Torontu přijal pro Neural Networks v příspěvku nazvaném „Deep-Learning Via Hessian Free Optimization“.

Začněme Taylorovým rozšířením funkce druhého řádu:

Zde musíme najít nejlepší delta_x a pak se přesunout do x + delta_x a udržovat iteraci, dokud se nespojí. Jinými slovy, kroky zahrnuté v Hessianově optimalizaci jsou následující:

Algoritmus:

  1. Začněte s i = 0 a opakujte
  2. Nechť x_i bude náhodně vybráno nějaké počáteční neoptimální x_0.
  3. V současné době x_n, vzhledem k Taylorově expanzi znázorněné výše, vypočítejte gradient f (x_n) a hessian z f (x_n)
  4. Vzhledem k Taylorově expanzi vypočtěte další x_n + 1 (což není nic jiného než delta_x) pomocí algoritmu konjugovaného gradientu.
  5. Opakujte kroky 2–4, dokud se aktuální x_n nespojí.

Zásadní vhled: Všimněte si, že na rozdíl od Newtonovy metody, kde je pro výpočet x_n + 1 potřeba Hessian, v algoritmu bez Hessian nepotřebujeme Hessian pro výpočet x_n + 1. Místo toho používáme konjugovaný gradient.

Chytrý hack: Protože je Hessian používán společně s vektorem x_n, potřebujeme pouze aproximaci Hessiana spolu s vektorem a nepotřebujeme přesnou Hessian. Přibližování Hessian s vektorem je mnohem rychlejší než výpočet Hessiana samotného. Zkontrolujte následující zdůvodnění.

Podívejte se znovu na Hessian:

Hessianova matice neuronové sítě

V tomto řádku je částečný derivát formuláře

Kde 'i' je index řádků a 'j' je index sloupců. Odtud tečkový produkt hessiánské matice a libovolného vektoru:

Výše uvedené udává směrový derivát „e“ vzhledem k „w“ ve směru „v“.

Pomocí konečných rozdílů můžeme výše uvedené optimalizovat takto:

Ve skutečnosti je důkladné vysvětlení a technika rychlého znásobení Hessiana vektorem k dispozici v článku s názvem „Rychlé přesné násobení Hessiana“ od Barak A. Pearlmutter ze společnosti Siemens Corporate Research.

S tímto vhledem můžeme úplně přeskočit výpočet Hessiana a soustředit se pouze na aproximaci Hessiana k vektorovému násobení, což ohromně snižuje výpočetní a úložnou kapacitu.

Chcete-li porozumět dopadu optimalizační techniky, zkontrolujte následující obrázek.

Všimněte si, že s tímto přístupem, místo toho, abyste skočili ze strany hor jako v SGD, se můžete skutečně pohybovat po svahu údolí, než najdete minima v zakřivení. To je docela efektivní pro velmi velké neuronové sítě nebo hluboké neuronové sítě s miliony parametrů.

Zjevně není snadné být špionem…