Förstå stokastisk medelgradient

Gradient descent är den mest populära optimeringstekniken inom maskininlärning (ML)-modellering. Algoritmen minimerar felet mellan de förutsagda värdena och grundsanningen. Eftersom tekniken anser att varje datapunkt förstår och minimerar felet, beror dess prestanda på träningsdatastorleken. Tekniker som Stokastisk Gradient Descent (SGD) är utformade för att förbättra beräkningsprestandan men till priset av konvergensnoggrannhet.

Stochastic Average Gradient balanserar det klassiska tillvägagångssättet, känd som Full Gradient Descent och SGD, och erbjuder båda fördelarna. Men innan vi kan använda algoritmen måste vi först förstå dess betydelse för modelloptimering.

Optimera maskininlärningsmål med Gradient Descent

Varje ML-algoritm har en tillhörande förlustfunktion som syftar till att minimera eller förbättra modellens prestanda. Matematiskt kan förlusten definieras som:

Det är helt enkelt skillnaden mellan den faktiska och den förutsedda produktionen, och att minimera denna skillnad innebär att vår modell kommer närmare de markerade sanningsvärdena.

Minimeringsalgoritmen använder gradientnedstigning för att korsa förlustfunktionen och hitta ett globalt minimum. Varje övergångssteg innebär uppdatering av algoritmens vikter för att optimera utdata.

Vanlig gradientnedstigning

Den konventionella gradientnedstigningsalgoritmen använder genomsnittet av alla gradienter som beräknats över hela datamängden. Livscykeln för ett enskilt träningsexempel ser ut så här:

Viktuppdateringsekvationen ser ut som följande:

Där W representerar modellvikterna och dJ/dW är derivatan av förlustfunktionen med avseende på modellvikten. Den konventionella metoden har en hög konvergenshastighet men blir beräkningsmässigt dyr när man hanterar stora datamängder som omfattar miljontals datapunkter.

Stokastisk Gradient Descent (SGD)

SGD-metoden förblir densamma som vanlig GD, men istället för att använda hela datasetet för att beräkna gradienterna, använder den en liten batch från ingångarna. Metoden är mycket effektivare men kan hoppa för mycket runt de globala minima eftersom varje iteration bara använder en del av data för inlärning.

Stokastisk medelgradient

Den Stokastiska Average Gradient (SAG)-metoden introducerades som en mellanväg mellan GD och SGD. Den väljer en slumpmässig datapunkt och uppdaterar dess värde baserat på gradienten vid den punkten och ett viktat medelvärde av de tidigare gradienterna som lagrats för den specifika datapunkten.

I likhet med SGD modellerar SAG varje problem som en ändlig summa av konvexa, differentierbara funktioner. Vid varje given iteration använder den nuvarande gradienter och medelvärdet av tidigare gradienter för viktuppdatering. Ekvationen har följande form:

Konvergenshastighet

Mellan de två populära algoritmerna, full gradient (FG) och stokastisk gradient descent (SGD), har FG-algoritmen en bättre konvergenshastighet eftersom den använder hela datamängden under varje iteration för beräkning.

Även om SAG har en struktur som liknar SGD, är dess konvergenshastighet jämförbar med och ibland bättre än metoden med full gradient. Tabell 1 nedan sammanfattar resultaten från experimenten av Schmidt et. al .

Ytterligare ändringar

Trots dess fantastiska prestanda har flera modifieringar föreslagits till den ursprungliga SGD-algoritmen för att förbättra prestandan.

• Omviktning i tidiga iterationer: SAG-konvergensen förblir långsam under de första iterationerna eftersom algoritmen normaliserar riktningen med n (totalt antal datapunkter). Detta ger en felaktig uppskattning eftersom algoritmen ännu inte har sett många datapunkter. Modifieringen föreslår normalisering med m istället för n, där m är antalet datapunkter som ses minst en gång fram till den specifika iterationen.
• Minibatcher: Den Stokastiska Gradient-metoden använder minibatcher för att bearbeta flera datapunkter samtidigt. Samma tillvägagångssätt kan tillämpas på SAG. Detta möjliggör vektorisering och parallellisering för förbättrad datoreffektivitet. Det minskar också minnesbelastningen, en framträdande utmaning för SAG-algoritmen.
• Stegstorleksexperimentering: Stegstorleken som nämndes tidigare (116L) ger fantastiska resultat, men författarna experimenterade vidare genom att använda stegstorleken 1L. Det senare gav ännu bättre konvergens. Författarna kunde dock inte presentera en formell analys av de förbättrade resultaten. De drar slutsatsen att stegstorleken bör experimenteras med för att hitta den optimala för det specifika problemet.

Slutliga tankar

Gradient descent är en populär optimering som används för att lokalisera globala minima för de tillhandahållna målfunktionerna. Algoritmen använder gradienten för målfunktionen för att korsa funktionslutningen tills den når den lägsta punkten.

Full Gradient Descent (FG) och Stokastisk Gradient Descent (SGD) är två populära varianter av algoritmen. FG använder hela datamängden under varje iteration och ger en hög konvergenshastighet till en hög beräkningskostnad. Vid varje iteration använder SGD en delmängd av data för att köra algoritmen. Det är mycket mer effektivt men med en osäker konvergens.

Stochastic Average Gradient (SAG) är en annan variant som ger fördelarna med båda tidigare algoritmerna. Den använder genomsnittet av tidigare gradienter och en delmängd av datamängden för att ge en hög konvergenshastighet med låg beräkning. Algoritmen kan modifieras ytterligare för att förbättra dess effektivitet med hjälp av vektorisering och minibatcher.