Stochastische gemiddelde gradiënt begrijpen

Gradient descent is de populairste optimalisatietechniek in machine learning (ML) modellering. Het algoritme minimaliseert de fout tussen de voorspelde waarden en de grondwaarheid. Omdat de techniek elk datapunt beschouwt om de fout te begrijpen en minimaliseren, is de prestatie ervan afhankelijk van de trainingsdatagrootte. Technieken zoals Stochastic Gradient Descent (SGD) zijn ontworpen om de berekeningsprestaties te verbeteren, maar ten koste van de convergentienauwkeurigheid.

Stochastic Average Gradient balanceert de klassieke aanpak, bekend als Full Gradient Descent en SGD, en biedt beide voordelen. Maar voordat we het algoritme kunnen gebruiken, moeten we eerst de betekenis ervan voor modeloptimalisatie begrijpen.

Optimaliseren van machine learning-doelstellingen met Gradient Descent

Elk ML-algoritme heeft een bijbehorende verliesfunctie die erop gericht is de prestaties van het model te minimaliseren of te verbeteren. Wiskundig gezien kan het verlies als volgt worden gedefinieerd:

Het is simpelweg het verschil tussen de werkelijke en de voorspelde uitkomst. Door dit verschil te minimaliseren, komt ons model dichter bij de werkelijke waarden.

Het minimalisatiealgoritme gebruikt gradiëntafdaling om de verliesfunctie te doorkruisen en een globaal minimum te vinden. Elke doorkruisingsstap omvat het updaten van de gewichten van het algoritme om de uitvoer te optimaliseren.

Eenvoudige hellingafdaling

Het conventionele gradient descent-algoritme gebruikt het gemiddelde van alle gradiënten die over de gehele dataset zijn berekend. De levenscyclus van een enkel trainingsvoorbeeld ziet er als volgt uit:

De vergelijking voor de gewichtsupdate ziet er als volgt uit:

Waarbij W de modelgewichten voorstelt en dJ/dW de afgeleide is van de verliesfunctie met betrekking tot het modelgewicht. De conventionele methode heeft een hoge convergentiesnelheid, maar wordt rekenkundig duur bij het werken met grote datasets die miljoenen datapunten bevatten.

Stochastische gradiëntafdaling (SGD)

De SGD-methodologie blijft hetzelfde als gewone GD, maar in plaats van de hele dataset te gebruiken om de gradiënten te berekenen, gebruikt het een kleine batch van de invoer. De methode is veel efficiënter, maar kan te veel rondspringen in de globale minima, omdat elke iteratie slechts een deel van de data gebruikt om te leren.

Stochastische gemiddelde gradiënt

De Stochastic Average Gradient (SAG)-benadering werd geïntroduceerd als een middenweg tussen GD en SGD. Het selecteert een willekeurig datapunt en werkt de waarde ervan bij op basis van de gradiënt op dat punt en een gewogen gemiddelde van de vorige gradiënten die voor dat specifieke datapunt zijn opgeslagen.

Vergelijkbaar met SGD, modelleert SAG elk probleem als een eindige som van convexe, differentieerbare functies. Bij elke gegeven iteratie gebruikt het de huidige gradiënten en het gemiddelde van eerdere gradiënten voor gewichtsupdates. De vergelijking heeft de volgende vorm:

Convergentiepercentage

Van de twee populaire algoritmen, volledige gradiënt (FG) en stochastische gradiëntafdaling (SGD), heeft het FG-algoritme een betere convergentiegraad, omdat het de volledige dataset tijdens elke iteratie voor de berekening gebruikt.

Hoewel SAG een structuur heeft die lijkt op SGD, is de convergentiesnelheid vergelijkbaar met en soms beter dan de volledige gradiëntbenadering. Tabel 1 hieronder vat de resultaten samen van de experimenten van Schmidt et al. .

Verdere wijzigingen

Ondanks de verbluffende prestaties zijn er verschillende aanpassingen aan het oorspronkelijke SGD-algoritme voorgesteld om de prestaties te verbeteren.

• Herwegen in vroege iteraties: SAG-convergentie blijft traag tijdens de eerste paar iteraties, omdat het algoritme de richting normaliseert met n (totaal aantal datapunten). Dit levert een onnauwkeurige schatting op, omdat het algoritme nog veel datapunten moet zien. De aanpassing suggereert normaliseren met m in plaats van n, waarbij m het aantal datapunten is dat ten minste één keer is gezien tot die specifieke iteratie.
• Mini-batches: De Stochastic Gradient-benadering gebruikt mini-batches om meerdere datapunten tegelijkertijd te verwerken. Dezelfde benadering kan worden toegepast op SAG. Dit maakt vectorisatie en parallelisatie mogelijk voor verbeterde computerefficiëntie. Het vermindert ook de geheugenbelasting, een belangrijke uitdaging voor het SAG-algoritme.
• Experimenteren met stapgrootte: De eerder genoemde stapgrootte (116L) levert verbluffende resultaten op, maar de auteurs experimenteerden verder door de stapgrootte van 1L te gebruiken. Deze laatste leverde een nog betere convergentie op. De auteurs waren echter niet in staat om een formele analyse van de verbeterde resultaten te presenteren. Ze concluderen dat er met de stapgrootte geëxperimenteerd moet worden om de optimale te vinden voor het specifieke probleem.

Laatste gedachten

Gradient descent is een populaire optimalisatie die wordt gebruikt voor het lokaliseren van globale minima van de opgegeven objectieve functies. Het algoritme gebruikt de gradiënt van de objectieve functie om de functiehelling te doorkruisen totdat het het laagste punt bereikt.

Full Gradient Descent (FG) en Stochastic Gradient Descent (SGD) zijn twee populaire variaties van het algoritme. FG gebruikt de volledige dataset tijdens elke iteratie en biedt een hoge convergentiesnelheid tegen hoge rekenkosten. Bij elke iteratie gebruikt SGD een subset van data om het algoritme uit te voeren. Het is veel efficiënter, maar met een onzekere convergentie.

Stochastic Average Gradient (SAG) is een andere variatie die de voordelen van beide voorgaande algoritmen biedt. Het gebruikt het gemiddelde van eerdere gradiënten en een subset van de dataset om een hoge convergentiesnelheid te bieden met lage berekeningen. Het algoritme kan verder worden aangepast om de efficiëntie te verbeteren met behulp van vectorisatie en mini-batches.