Sådan temmes dalen - Hessian-frie hacks til optimering af store #NeuralNetworks

Lad os sige, at du har flyvegaven (eller at du kører på en helikopter). Du er også en Spy (som i James Bond-film). Du får topografien i en lang smal dal som vist på billedet, og du får et møde point for at møde en potentiel hjælpe, der har intelligens, der er nyttigt til dit mål. De eneste oplysninger, du har om mødestedet, er som følger:

”Mød mig på den laveste koordinat for" denne lange dal "på 4 timer"

Hvordan kan du finde det laveste koordinatpunkt? Mere desto mindre, hvordan agter du at finde det inden for en bestemt periode?

For komplekse neurale netværk, der har meget store parametre, svarer fejloverfladen på det neurale netværk meget til den lange smalle dalsorter. At finde et "minima" i dalen kan være meget vanskeligt, når du har sådanne patologiske krumninger i din topografi.

Bemærk: der er mange indlæg skrevet på andenordens optimeringshacks til Neural Network. Årsagen til at jeg besluttede at skrive om det igen, er, at det meste springer lige ind i kompleks matematik uden meget forklaring.
I stedet har jeg forsøgt at forklare matematik så kort, hvor det er muligt, og peger hovedsageligt på detaljerede kilder for at lære, hvis du ikke er trænet inden for det bestemte matematikfelt.
Dette indlæg skal være lidt langvarigt på grund af det.

I de tidligere indlæg brugte vi gradient Descent-algoritmer, mens vi tilbagebesatte, hvilket hjalp os med at minimere fejlene. Du kan finde teknikkerne i indlægget med titlen "Backpropagation - Hvordan neurale netværk lærer komplekse opførsler"

Begrænsninger af gradientafstamning

Der er ikke noget fundamentalt galt med en gradientafstødningsalgoritme [eller stokastisk gradientafstigning (SGD) for at være præcis]. Faktisk har vi bevist, at det er ret effektivt for nogle af de fremadrettede eksempler på feed fremad, vi har brugt i fortiden. Problemet med SGD opstår, når vi har "dybe" neurale netværk, der har mere end et skjult lag. Især når netværket er ret stort.

Her er nogle illustrationer af en ikke-monotonisk fejloverflade i et Deep Neural Network for at få en idé.

Fejloverflade - 2Fejloverflade - 2

Bemærk, at der er mange minima og maksima på illustrationen. Lad os hurtigt se på vægtopdateringsprocessen i SGD

SGD-vægtopdateringer

Problemet med at bruge SGD til illustrationer er som følger:

  • Da SGD anvender optimeringsmetode til første orden, antager den, at fejloverfladen altid ser ud som et plan (i retning af nedstigningen, der er) og ikke tegner sig for krumning.
  • Når der er en kvadratisk krumning, anvender vi nogle tricks for at sikre, at SGD ikke bare spretter fra overfladen, som vist i vægtopdateringsligningen.
  • Vi styrer momentumværdien ved hjælp af en forudbestemt alfa og styrer hastigheden ved at anvende en indlæringshastighed epsilon.
  • Alfa og epsilon buffer hastigheden og retningen på SGD og bremser optimeringen, indtil vi konvergerer. Vi kan kun indstille disse hyperparametre for at få en god balance mellem hastighed og effektivitet af SGD. Men de bremser os stadig ned.
  • I store netværk med patologiske krumninger som vist på illustrationen er indstilling af disse hyperparametre ret udfordrende.
  • Fejlen i SGD kan pludselig begynde at stige, når du bevæger dig i retning af gradienten, når du krydser en lang smal dal. Faktisk kan SGD næsten stoppe, før det overhovedet kan gøre nogen fremskridt.

Vi har brug for en bedre metode til at arbejde med store eller dybe neurale netværk.

Anden ordensoptimering til redning

SGD er et første ordens optimeringsproblem. Første ordens metoder er metoder, der har lineære lokale kurver. Ved at antage, at vi kan anvende lineære tilnærmelser til at løse ligninger. Nogle eksempler på førsteordens metoder er som følger:

  • Gradient Descent
  • Sub-Gradient
  • Konjugeret gradient
  • Tilfældig koordinatafstamning

Der er metoder, der kaldes andenordens metoder, der tager hensyn til ligningens konveksitet eller krumning og gør kvadratiske tilnærmelser. Kvadratiske tilnærmelser er en udvidelse af lineære tilnærmelser, men giver en yderligere variabel at håndtere, hvilket hjælper med at skabe en kvadratisk overflade til at håndtere et punkt på fejloverfladen.

Den vigtigste forskel mellem førsteordens og andenordens tilnærmelser er, at selvom den lineære tilnærmelse tilvejebringer et "plan", der er tangentielt til et punkt på en fejloverflade, tilvejebringer andenordens tilnærmelse en kvadratisk overflade, der krummer kurvaturen af fejloverfladen.

Hvis du er ny med kvadratiske tilnærmelser, opfordrer jeg dig til at tjekke dette Khan Academy-foredrag om kvadratiske tilnærmelser.

Fordelen ved en anden ordens metode er, at den ikke skal ignorere fejloverfladens krumning. På grund af det faktum, at krumningen overvejes, betragtes andenordens metoder for at have en bedre trinvis præstation.

  • Det fulde trinsspring af en andenordens metode peger direkte på minimaet for en krumning (i modsætning til førsteordens metoder, der kræver flere trin med flere gradientberegninger i hvert trin).
  • Da en anden ordens metode peger på minimaet for en kvadratisk krumning i et trin, er det eneste, du skal bekymre dig om, hvor godt kurven faktisk knytter fejloverfladen. Dette er en god nok heuristisk til at håndtere.
  • At arbejde med de hyperparametre, der er givet heuristikken, bliver meget effektiv.

Følgende er nogle andenordens metoder

  • Newtons metode
  • Quasi-Newton, Gauss-Newton
  • BFGS, (L) BFGS

Lad os se på Newtons metode, som er en basemetode og er lidt mere intuitiv sammenlignet med andre.

Yo! Newton, hvad er din metode?

Newtons metode, også kaldet Newton-Raphson-metoden, er en iterativ metode tilnærmelsesmetode på rødderne af en reel værdsat funktion. Dette er en af ​​basismetoderne, der bruges i ethvert andet ordens konvekse optimeringsproblemer for at tilnærme funktioner.

Lad os først se på Newtons metode ved hjælp af førstederivatet af en funktion.

Lad os sige, at vi har en funktion f (x) = 0, og vi har en initial løsning x_0, som vi mener er suboptimal. Derefter foreslår Newtons metode, at vi gør følgende

  1. Find ligningen for tangentlinjen ved x_0
  2. Find det punkt, hvor tangentlinjen skærer x-aksen, og kald dette nye punkt som x_1.
  3. Find fremskrivningen af ​​x_1 på funktionen f (x) = 0, som også er ved x_1.
  4. Nu gentages det igen fra trin-1 ved at erstatte x_0 med x_1.

Virkelig så enkelt. Forbehold er, at metoden ikke fortæller dig, hvornår du skal stoppe, så vi tilføjer et 5. trin som følger:

5. Hvis x_n (den aktuelle værdi af x) er lig med eller mindre end en tærskel, stopper vi.

Her er det billede, der viser ovenstående:

Find optimal værdi af X ved hjælp af Newtons metode.

Her er en animation, der viser det samme:

animation kredit

Første grad-polynom, en-dimension:

Her er matematikken for en funktion, der er en første grads polynom med en dimension.

Anden-grad-polynom, en-dimension

Nu kan vi arbejde på Newton-tilnærmelse til en andengrads polynom (anden ordens optimering) -funktion med en-dimension (før vi kommer til flere dimensioner). En polynom af anden grad er kvadratisk og har brug for et andet ordens derivat til at arbejde med. For at arbejde på det andet derivat af en funktion, lad os bruge Taylor-tilnærmelsen som følger:

Anden-grad-polynom, Multiple-dimension

Lad os antage, at vi arbejder med en andengradspolynom med flere dimensioner, så arbejder vi med den samme Newtons tilgang, som vi fandt ovenfor, men erstatter førstederivaterne med en gradient og sekundederivaterne med en Hessian som følger:

En Hessian Matrix er kvadratmatrix af andenordens partielle derivater af en skalar, som beskriver den lokale krumning af en multivariabel funktion.

Specielt i tilfælde af et neuralt netværk er Hessian en firkantet matrix med antallet af rækker og kolonner svarende til det samlede antal parametre i det neurale netværk.

Hessian for Neural Network ser ud som følger:

Hessian Matrix af et neuralt netværk

Hvorfor er hessisk baseret tilgang teoretisk bedre end SGD?

Nu er andenordens optimering ved hjælp af Newtons metode til iterativt at finde den optimale 'x' et smart hack til at optimere fejloverfladen, for i modsætning til SGD, hvor du passer et fly på punktet x_0 og derefter bestemmer det trinvise spring, i anden ordens optimering finder vi en tæt tilpasset kvadratisk kurve ved x_0 og finder direkte kurvernes minima. Dette er yderst effektivt og hurtigt.

Men !!! Empirisk, kan du nu forestille dig at beregne en Hessian til et netværk med millioner af parametre? Naturligvis bliver det meget ineffektivt, da mængden af ​​lager og beregning, der kræves for at beregne Hessian, også er af kvadratisk rækkefølge. Så selvom det i teorien er fantastisk, er det i praksis suget.

Vi har brug for et hack til hacket! Og svaret ser ud til at ligge i Conjugate Gradients.

Conjugate Gradients, smart trick.

Der er faktisk flere kvadratiske tilnærmelsesmetoder til en konveks funktion. Men Conjugate Gradient Method fungerer ganske godt for en symmetrisk matrix, som er positive og klare. Faktisk er konjugerede graderinger beregnet til at arbejde med meget store, sparsomme systemer.

Bemærk, at en Hessian er symmetrisk omkring diagonalen, parametrene for et neuralt netværk er typisk sparsomme, og Hessian for et neuralt netværk er positivt bestemt (betyder, at det kun har positive Ægenværdier). Dreng, har vi held?

Hvis du har brug for en grundig introduktion af konjugerede gradientmetoder, skal du gennemgå papiret med titlen "En introduktion til konjugatgradientmetoden uden den pinefulde smerte" af Jonathan Richard Shewchuk. Jeg finder dette ganske grundigt og nyttigt. Jeg vil foreslå, at du studerer papiret i fritid for at få en dybdegående forståelse af konjugerede gradienter.

Den nemmeste måde at forklare Conjugate Gradient (CG) er som følger:

  • CG Descent gælder for enhver kvadratisk form.
  • CG bruger en trinstørrelse 'alfa'-værdi, der ligner SGD, men i stedet for en fast alfa finder vi alfa gennem en linjesøgningsalgoritme.
  • CG har også brug for en "beta", en skalærværdi, der hjælper med at finde den næste retning, der er "konjugeret" til den første retning.

Du kan kontrollere det meste af den behårede matematik omkring ankommer til en CG-ligning med det citerede papir herover. Jeg springer direkte til sektionen af ​​algoritmen i konjugatgradienten:

Til løsning af en ligning Ax = b kan vi bruge følgende algoritme:

billedkredit
  • Her er r_k den resterende værdi,
  • p_k er den konjugerede vektor og,
  • x_k + 1 opdateres iterativt med den forrige værdi x_k og prikproduktet af trinstørrelsen alpha_k og konjugatvektoren p_k.

Da vi ved, hvordan vi beregner konjugeret gradient, lad os se på Hessian Free-optimeringsteknikken.

Hessian-fri optimeringsalgoritme

Nu hvor vi har forstået CG-algoritmen, så lad os se på det sidste smarte hack, der giver os mulighed for at være fri fra Hessian.

CITATION: Hessian-fri optimering er en teknik, der blev anvendt til neurale netværk af James Marten ved University of Toronto i et papir med titlen “Deep-Learning Via Hessian Free Optimization”.

Lad os starte med en andenordens Taylor-udvidelse af en funktion:

Her er vi nødt til at finde den bedste delta_x og derefter gå til x + delta_x og fortsætte med at iterere, indtil de konvergerer. Med andre ord, trinnene involveret i Hessian-fri optimering er som følger:

Algoritme:

  1. Start med i = 0 og iterere
  2. Lad x_i være nogle indledende suboptimale x_0, der vælges tilfældigt.
  3. På nuværende tidspunkt x_n Givet Taylor-udvidelsen vist som ovenfor, beregne gradient af f (x_n) og hessian for f (x_n)
  4. Givet Taylor-udvidelsen, beregne den næste x_n + 1 (som ikke er andet end delta_x) ved hjælp af konjugeret gradientalgoritme.
  5. Iterér trin 2–4, indtil den aktuelle x_n konvergerer.

Den afgørende indsigt: Bemærk, at i modsætning til i Newtons metode, hvor en Hessian er nødvendig for at beregne x_n + 1, har vi i Hessian-fri algoritme ikke brug for Hessian til at beregne x_n + 1. I stedet bruger vi konjugeret gradient.

Clever Hack: Da Hessian bruges sammen med en vektor x_n, har vi bare brug for en tilnærmelse af Hessian sammen med vektoren, og vi har IKKE brug for den nøjagtige Hessian. Tilnærmelsen af ​​Hessian med en vektor er langt hurtigere end at beregne Hessian selv. Kontroller følgende begrundelse.

Se igen på Hessian:

Hessian Matrix af et neuralt netværk

Her indeholder den i'te række delvise derivater af formularen

Hvor 'i' er rækkeindekset og 'j' er kolonneindekset. Derfor er dotproduktet af en Hessian-matrix og enhver vektor:

Ovenstående giver retningsafledningen af ​​'e' med hensyn til 'w' i retning 'v'.

Ved hjælp af begrænsede forskelle kan vi derefter optimere ovenstående som følger:

Faktisk findes en grundig forklaring og teknik til hurtig multiplikation af en Hessian med en vektor i papiret med titlen "Fast Exact Multiplication of the Hessian" af Barak A. Pearlmutter fra Siemens Corporate Research.

Med denne indsigt kan vi helt springe beregningen af ​​en Hessian over og bare fokusere på tilnærmelsen af ​​Hessian til en vektormultiplikation, hvilket enormt reducerer beregningen og lagringskapaciteten.

For at forstå virkningen af ​​optimeringsteknikken skal du kontrollere følgende illustration.

Bemærk, at med denne tilgang, i stedet for at hoppe ud af bjergsiden som i SGD, kan du faktisk bevæge dig langs skråningen af ​​dalen, før du kan finde et minima i krumningen. Dette er ret effektivt for meget store neurale netværk eller dybe neurale netværk med millioner af parametre.

Tilsyneladende er det ikke let at være en spion ...