Forståelse af stokastisk gennemsnitsgradient

Gradient descent er den mest populære optimeringsteknik inden for maskinlæring (ML) modellering. Algoritmen minimerer fejlen mellem de forudsagte værdier og grundsandheden. Da teknikken betragter hvert datapunkt for at forstå og minimere fejlen, afhænger dens ydeevne af træningsdatastørrelsen. Teknikker som Stokastisk Gradient Descent (SGD) er designet til at forbedre beregningsydelsen, men på bekostning af konvergensnøjagtighed.

Stokastisk gennemsnitsgradient balancerer den klassiske tilgang, kendt som Full Gradient Descent og SGD, og tilbyder begge fordele. Men før vi kan bruge algoritmen, skal vi først forstå dens betydning for modeloptimering.

Optimering af maskinlæringsmål med gradientnedstigning

Hver ML-algoritme har en tilknyttet tabsfunktion, der har til formål at minimere eller forbedre modellens ydeevne. Matematisk kan tabet defineres som:

Det er simpelthen forskellen mellem det faktiske og det forudsagte output, og at minimere denne forskel betyder, at vores model kommer tættere på grundsandhedsværdierne.

Minimeringsalgoritmen bruger gradientnedstigning til at krydse tabsfunktionen og finde et globalt minimum. Hvert gennemløbstrin involverer opdatering af algoritmens vægte for at optimere outputtet.

Almindelig gradientnedstigning

Den konventionelle gradientnedstigningsalgoritme bruger gennemsnittet af alle gradienter beregnet på tværs af hele datasættet. Livscyklussen for et enkelt træningseksempel ser således ud:

Vægtopdateringsligningen ser sådan ud:

Hvor W repræsenterer modelvægtene og dJ/dW er den afledte af tabsfunktionen i forhold til modelvægten. Den konventionelle metode har en høj konvergenshastighed, men bliver beregningsmæssigt dyr, når man har at gøre med store datasæt, der omfatter millioner af datapunkter.

Stokastisk Gradient Descent (SGD)

SGD-metoden forbliver den samme som almindelig GD, men i stedet for at bruge hele datasættet til at beregne gradienterne, bruger den en lille batch fra inputs. Metoden er meget mere effektiv, men kan hoppe for meget omkring de globale minima, da hver iteration kun bruger en del af dataene til læring.

Stokastisk gennemsnitsgradient

Den Stokastiske Average Gradient (SAG) tilgang blev introduceret som en mellemvej mellem GD og SGD. Den vælger et tilfældigt datapunkt og opdaterer dets værdi baseret på gradienten på det pågældende punkt og et vægtet gennemsnit af de tidligere gradienter, der er gemt for det pågældende datapunkt.

I lighed med SGD modellerer SAG hvert problem som en endelig sum af konvekse, differentierbare funktioner. Ved enhver given iteration bruger den de nuværende gradienter og gennemsnittet af tidligere gradienter til vægtopdatering. Ligningen har følgende form:

Konvergenshastighed

Mellem de to populære algoritmer, fuld gradient (FG) og stokastisk gradientnedstigning (SGD), har FG-algoritmen en bedre konvergenshastighed, da den bruger hele datasættet under hver iteration til beregning.

Selvom SAG har en struktur, der ligner SGD, er dens konvergenshastighed sammenlignelig med og nogle gange bedre end den fulde gradienttilgang. Tabel 1 nedenfor opsummerer resultaterne fra forsøgene med Schmidt et. al .

Yderligere ændringer

På trods af dens fantastiske ydeevne er adskillige ændringer blevet foreslået til den originale SGD-algoritme for at hjælpe med at forbedre ydeevnen.

• Genvægtning i tidlige iterationer: SAG-konvergens forbliver langsom under de første par iterationer, da algoritmen normaliserer retningen med n (samlet antal datapunkter). Dette giver et unøjagtigt skøn, da algoritmen endnu ikke har set mange datapunkter. Modifikationen foreslår normalisering med m i stedet for n, hvor m er antallet af datapunkter set mindst én gang indtil den pågældende iteration.
• Mini-batches: Stochastic Gradient-tilgangen bruger mini-batches til at behandle flere datapunkter samtidigt. Den samme tilgang kan anvendes på SAG. Dette giver mulighed for vektorisering og parallelisering for forbedret computereffektivitet. Det reducerer også hukommelsesbelastningen, en fremtrædende udfordring for SAG-algoritmen.
• Trinstørrelseseksperimentering: Trinstørrelsen nævnt tidligere (116L) giver fantastiske resultater, men forfatterne eksperimenterede yderligere ved at bruge trinstørrelsen på 1L. Sidstnævnte gav endnu bedre konvergens. Forfatterne var dog ikke i stand til at præsentere en formel analyse af de forbedrede resultater. De konkluderer, at trinstørrelsen bør eksperimenteres med for at finde den optimale til det specifikke problem.

Afsluttende tanker

Gradient descent er en populær optimering, der bruges til at lokalisere globale minima for de leverede målfunktioner. Algoritmen bruger gradienten af objektivfunktionen til at krydse funktionshældningen, indtil den når det laveste punkt.

Full Gradient Descent (FG) og Stokastisk Gradient Descent (SGD) er to populære variationer af algoritmen. FG bruger hele datasættet under hver iteration og giver en høj konvergenshastighed til høje beregningsomkostninger. Ved hver iteration bruger SGD en delmængde af data til at køre algoritmen. Det er langt mere effektivt, men med en usikker konvergens.

Stochastic Average Gradient (SAG) er en anden variation, der giver fordelene ved begge tidligere algoritmer. Den bruger gennemsnittet af tidligere gradienter og en delmængde af datasættet til at give en høj konvergenshastighed med lav beregning. Algoritmen kan modificeres yderligere for at forbedre dens effektivitet ved hjælp af vektorisering og mini-batches.