By Dr. Mario Michael Krell, Principal Machine Learning Lead hos Graphcore & Matej Kosec, AI Applications Specialist hos Graphcore

Billede af forfatter.

 

Ved at bruge en ny pakkealgoritme har vi fremskyndet Natural Language Processing med mere end 2 gange, mens vi træner BERT-Large. Vores nye pakketeknik fjerner polstring, hvilket muliggør en væsentligt mere effektiv beregning.

Vi formoder, at dette også kan anvendes på genomik og proteinfoldningsmodeller og andre modeller med skæve længdefordelinger for at få en meget bredere indflydelse i forskellige industrier og applikationer.

Vi introducerede Graphcores højeffektive Non-Negative Least Squares Histogram-Packing-algoritme (eller NNLSHP) såvel som vores BERT-algoritme anvendt på pakkede sekvenser i et nyt papir [1].

Computational Waste i NLP på grund af sekvenspolstring

 
 
Vi begyndte at undersøge nye måder at optimere BERT-træning på, mens vi arbejdede på vores seneste benchmark-indsendelser til MLPerf™. Målet var at udvikle brugbare optimeringer, der nemt kunne implementeres i applikationer fra den virkelige verden. BERT var et naturligt valg som en af ​​modellerne at fokusere på til disse optimeringer, da den er meget brugt i industrien og af mange af vores kunder.

Det overraskede os virkelig at erfare, at i vores egen BERT-Large træningsapplikation, der bruger Wikipedia-datasættet, var 50 % af tokens i datasættet udfyldning – hvilket resulterede i en masse spildte data.

Polstring af sekvenser for at justere dem alle til lige længde er en almindelig tilgang, der bruges med GPU'er, men vi tænkte, at det ville være værd at prøve en anden tilgang.

Sekvenser har en stor variation i længden af ​​to årsager:

1. De underliggende Wikipedia-data viser en stor variation i dokumentlængde
2. Selve BERT-forbehandlingen reducerer tilfældigt størrelsen af ​​udtrukne dokumenter, der kombineres for at generere en træningssekvens

At fylde længden op til den maksimale længde på 512 resulterer i, at 50% af alle tokens er polstringstokens. Udskiftning af de 50 % af polstringen med rigtige data kan resultere i, at 50 % flere data bliver behandlet med samme beregningsmæssige indsats og dermed 2x hastigheden under optimale forhold.

Figur 1: Wikipedia-datasætdistributioner. Billede af forfatter.

 

Er dette specifikt for Wikipedia? Ingen.

Jamen, er det så specifikt for sproget? Ingen.

Faktisk findes skæve længdefordelinger overalt: i sprog, genomik og proteinfoldning. Figur 2 og 3 viser distributioner for SQuAD 1.1-datasættet og GLUE-datasættene.

Figur 2: SQuAD 1.1 BERT før-træning datasæt sekvenslængde histogram for maksimal sekvenslængde på 384. Billede af forfatter.

 


Figur 3: GLUE-datasætsekvenslængdehistogrammer for maksimal sekvenslængde på 128. Billede af forfatter.

 

Hvordan kan vi håndtere de forskellige længder og samtidig undgå det beregningsmæssige spild?

Nuværende tilgange kræver forskellige beregningskerner i forskellige længder, eller for at ingeniøren programmæssigt fjerner polstringen og derefter tilføjer den igen gentagne gange for hver opmærksomhedsblok og tabsberegning. At gemme beregning ved at sprænge koden og gøre den mere kompleks var ikke tiltalende, så vi søgte efter noget bedre. Kan vi ikke bare sætte flere sekvenser sammen i en pakke med en maksimal længde og behandle det hele sammen? Det viser sig, at vi kan!

Denne tilgang kræver tre nøgleingredienser:

1. En effektiv algoritme til at beslutte, hvilke samples der skal sammensættes for at have så lidt resterende polstring som muligt
2. Justering af BERT-modellen til at behandle pakker i stedet for sekvenser
3. Og justering af hyperparametrene

Pakning

 
 
I starten virkede det usandsynligt, at du ville være i stand til at pakke et stort datasæt som Wikipedia meget effektivt. Dette problem er almindeligvis kendt som bin-packing. Selv når pakning er begrænset til tre sekvenser eller mindre, ville det resulterende problem stadig være stærkt NP-komplet, uden en effektiv algoritmisk løsning. Eksisterende heuristiske pakningsalgoritmer var ikke lovende, fordi de havde en kompleksitet på mindst O(n log(n)), hvor n er antallet af sekvenser (~16 millioner for Wikipedia). Vi var interesserede i tilgange, der kunne skaleres godt til millioner af sekvenser.

To tricks hjalp os med at reducere kompleksiteten drastisk:

1. Begrænsning af antallet af sekvenser i en pakke til tre (for vores første løsningstilgang)
2. Arbejder udelukkende på histogrammet af sekvenslængde med en bin for hver forekommende længde

Vores maksimale sekvenslængde var 512. Så flytning til histogrammet reducerede dimensionen og kompleksiteten fra 16 millioner sekvenser til 512 længdetællinger. Ved at tillade maksimalt tre sekvenser i en pakke reduceredes antallet af tilladte længdekombinationer til 22K. Dette inkluderede allerede tricket til at kræve, at sekvenserne skal sorteres efter længde i pakken. Så hvorfor ikke prøve 4 sekvenser? Dette øgede antallet af kombinationer fra 22K til 940K, hvilket var for meget for vores første modelleringstilgang. Derudover har dybde 3 allerede opnået bemærkelsesværdig høj pakningseffektivitet.

Oprindeligt troede vi, at brug af mere end tre sekvenser i en pakke ville øge den beregningsmæssige overhead og påvirke konvergensadfærden under træning. For at understøtte applikationer som f.eks. inferens, som kræver endnu hurtigere realtidspakning, udviklede vi den meget effektive Non-Negative Least Squares Histogram-Packing (NNLSHP) algoritme.

Ikke-negativ Least Squares Histogram-Packing (NNLSHP)

 
 
Beholderpakning formuleres ret ofte som et matematisk optimeringsproblem. Men med 16 millioner sekvenser (eller mere) er dette ikke praktisk. Alene problemvariablerne ville overstige de fleste maskiners hukommelse. Det matematiske program for en histogrambaseret tilgang er ganske pæn. For nemheds skyld besluttede vi os for en mindste kvadraters tilgang (Ax=b) med histogramvektor b. Vi udvidede det ved at anmode om strategivektoren x at være ikke-negativ og tilføje vægte for at tillade mindre polstring.

Den vanskelige del var strategimatrixen. Hver kolonne har en maksimal sum på tre og koder for, hvilke sekvenser der bliver pakket sammen, så de nøjagtigt matcher den ønskede samlede længde; 512 i vores tilfælde. Rækkerne koder for hver af de potentielle kombinationer for at nå en længde af den samlede længde. Strategivektoren x er det, vi ledte efter, som beskriver, hvor ofte vi vælger hvilken som helst af 20k-kombinationerne. Interessant nok blev kun omkring 600 kombinationer udvalgt til sidst. For at få en præcis løsning tæller strategien med x ville være positive heltal, men vi indså, at en omtrentlig afrundet løsning med kun ikke-negative x var tilstrækkeligt. For en omtrentlig løsning kan en simpel løsning, der er klar til brug, bruges til at få et resultat inden for 30 sekunder.

Figur 4: Eksempel på en strategimatrix for sekvenslængde 8 og pakningsdybde 3. Rækkerne står for sekvenserne af længde 1-8, der bliver pakket sammen, og kolonnerne står for alle mulige længdekombinationer i en pakke uden særlig rækkefølge. Billede af forfatter.

 

Til sidst var vi nødt til at rette nogle prøver, der ikke fik tildelt en strategi, men de var minimale. Vi udviklede også en variant-solver, der gennemtvinger, at hver sekvens bliver pakket, potentielt med polstring, og har en vægtning, der afhænger af polstringen. Det tog meget længere tid, og løsningen var ikke meget bedre.

Shortest-Pack-First Histogram Packing

 
 
NNLSHP leverede en tilstrækkelig pakningstilgang til os. Men vi spekulerede på, om vi teoretisk set kunne få en hurtigere online egnet tilgang og fjerne begrænsningen ved kun at sætte 3 sekvenser sammen.

Derfor tog vi lidt inspiration fra eksisterende pakningsalgoritmer, men fokuserede stadig på histogrammerne.

Der er fire ingredienser til vores første algoritme, Shortest-pack-first histogram-packing (SPFHP):

1. Betjen histogrammets tællinger fra længste sekvenser til korteste
2. Hvis den aktuelle sekvenslængde ikke passer ind i nogen pakke, skal du starte et nyt sæt pakker
3. Hvis der er flere tilpasninger, skal du tage pakken, hvor summen af ​​sekvenslængden er den korteste og ændre tællingerne hhv.
4. Tjek igen for pasform af de resterende tæller

Denne tilgang var den mest ligetil at implementere og tog kun 0.02 sekunder.

En variant var at tage den største sum af sekvenslængde i stedet for de korteste og opdelte tællinger for at få mere perfekte pasforme. Samlet set ændrede dette ikke effektiviteten meget, men øgede kodekompleksiteten meget.

Hvordan shortest-pack-first histogrampakning virker. Animation af forfatter.

 

Wikipedia, SQuAD 1.1, GLUE-pakningsresultater

 
 
Tabel 1, 2 og 3 viser pakningsresultaterne af vores to foreslåede algoritmer. Pakningsdybde beskriver det maksimale antal pakkede sekvenser. Pakkedybde 1 er BERT-implementeringen. Den maksimalt forekommende pakkedybde, hvis der ikke er sat nogen grænse, er angivet med et ekstra "max". Det antal pakker beskriver længden af ​​det nye pakkede datasæt. Effektivitet er procentdelen af ​​rigtige tokens i det pakkede datasæt. Det pakningsfaktor beskriver den resulterende potentielle fremskyndelse sammenlignet med pakkedybde 1.

Vi havde fire hovedbemærkninger:

1. Jo mere skæv en fordeling, jo større er fordelene ved at pakke.
2. Alle datasæt har gavn af pakning. Nogle endda med mere end en faktor 2.
3. SPFHP bliver mere effektivt, når pakkedybden ikke er begrænset.
4. For et maksimalt antal på 3 pakkede sekvenser, jo mere kompleks NNLSHP er, jo mere effektiv er den (99.75 vs. 89.44).

Tabel 1: Nøgleydelsesresultater af foreslåede pakningsalgoritmer (SPFHP og NNLSHP) på Wikipedia. Billede af forfatter.

 


Tabel 2: Præstationsresultater af foreslåede pakningsalgoritmer for SQUaD 1.1 BERT fortræning. Billede af forfatter.

 


Tabel 3: Ydeevneresultater af foreslåede pakningsalgoritmer for GLUE-datasættet. Kun basislinjen og SPFHP-pakningsresultaterne uden at begrænse pakningsdybden vises. Billede af forfatter.

 

BERT behandlingsjustering

 
 
Noget interessant ved BERT-arkitekturen er, at det meste af behandlingen sker på et token-niveau, hvilket betyder, at det ikke forstyrrer vores pakning. Der er kun fire komponenter, der skal justeres: opmærksomhedsmasken, MLM-tabet, NSP-tabet og nøjagtigheden.

Nøglen for alle fire tilgange til at håndtere forskellige antal sekvenser var vektorisering og brug af et maksimalt antal sekvenser, der kan sammenkædes. Til opmærksomhed havde vi allerede en maske til at adressere polstringen. At udvide dette til flere sekvenser var ligetil, som det kan ses i den følgende TensorFlow-pseudokode. Konceptet er, at vi sørgede for, at opmærksomheden er begrænset til de separate sekvenser og ikke kan strække sig ud over det.

Kodeeksempel på opmærksomhedsmaske.

 


Figur 5: Eksempel nul-en maske

 

Til tabsberegningen pakker vi i princippet sekvenserne ud og beregner de separate tab, hvorved vi til sidst opnår gennemsnittet af tabene over sekvenserne (i stedet for pakker).

For MLM-tabet ser koden ud som:

Eksempel på kode for tabsberegning.

 

For NSP-tabet og nøjagtigheden er princippet det samme. I vores offentlige eksempler kan du finde den respektive kode med vores in-house PopART-ramme.

Wikipedia overhead og speedup estimat

 
 
Med vores ændring af BERT havde vi to spørgsmål:

1. Hvor meget overhead fører det med sig?
2. Hvor meget afhænger overheaden af ​​det maksimale antal sekvenser, der er sat sammen i en pakke?

Da dataforberedelse i BERT kan være besværligt, brugte vi en genvej og kompilerede koden for flere forskellige pakningsdybder og sammenlignede de respektive (målte) cyklusser. Resultaterne er vist i tabel 4. Med overliggende, angiver vi det procentvise fald i gennemløbet på grund af ændringer i modellen for at muliggøre pakning (såsom maskeringsskemaet for opmærksomhed og den ændrede tabsberegning). Det realiseret fremskyndelse er kombinationen af ​​hastigheden på grund af pakning (den pakningsfaktor) og faldet i gennemløbet på grund af overliggende.

Tabel 4: Estimeret hastighedssammenligning af foreslåede pakningsalgoritmer (SPFHP og NNLSHP) på Wikipedia. Billede af forfatter.

 

Takket være vektoriseringsteknikken er overheaden overraskende lille, og der er ingen ulempe ved at pakke mange sekvenser sammen.

Hyperparameter-justeringer

 
 
Med pakning fordobler vi den effektive batchstørrelse (i gennemsnit). Det betyder, at vi skal justere træningshyperparametrene. Et simpelt trick er at halvere gradientakkumuleringen for at holde den samme effektive gennemsnitlige batchstørrelse som før træning. Ved at bruge en benchmark-indstilling med forudtrænede kontrolpunkter kan vi se, at nøjagtighedskurverne passer perfekt.

Figur 6: Sammenligning af indlæringskurver for pakket og udpakket behandling med reduceret batchstørrelse for den tætpakkede tilgang. Billeder af forfatter.

 

Nøjagtigheden matcher: MLM træningstabet kan være lidt anderledes i begyndelsen, men indhenter hurtigt det. Denne indledende forskel kunne komme fra små justeringer af opmærksomhedslagene, som kunne have været forudindtaget i retning af korte sekvenser i den tidligere træning.

For at undgå en opbremsning hjælper det nogle gange at holde den oprindelige batchstørrelse den samme og justere hyperparametrene til den øgede effektive batchstørrelse (fordoblet). De vigtigste hyperparametre, der skal overvejes, er beta-parametrene og indlæringshastighederne. En almindelig tilgang er at fordoble batchstørrelsen, hvilket i vores tilfælde reducerede ydeevnen. Når vi ser på statistikkerne for LAMB-optimeringsværktøjet, kunne vi bevise, at hævning af beta-parameteren til pakningsfaktorens magt svarer til at træne flere batches fortløbende for at holde momentum og hastighed sammenlignelige.

Figur 7: Sammenligning af indlæringskurver for pakket og udpakket behandling med heuristik anvendt. Billeder af forfatter.

 

Vores eksperimenter viste, at det er en god heuristik at tage beta til magten to. I dette scenarie forventes kurverne ikke at matche, fordi en forøgelse af batchstørrelsen normalt reducerer konvergenshastigheden i betydningen prøver/epoker, indtil en målnøjagtighed er nået.

Nu er spørgsmålet, om vi i det praktiske scenarie virkelig får den forventede fremskyndelse?

Figur 8: Sammenligning af indlæringskurver for pakket og udpakket behandling i optimeret opsætning. Billeder af forfatter.

 

Ja vi gør! Vi fik en yderligere speedup, fordi vi komprimerede dataoverførslen.

Konklusion

 
 
At pakke sætninger sammen kan spare computerarbejde og miljøet. Denne teknik kan implementeres i enhver ramme, inklusive PyTorch og TensorFlow. Vi opnåede en klar 2x speed-up, og undervejs udvidede vi state of the art inden for pakningsalgoritmer.

Andre applikationer, som vi er nysgerrige efter, er genomik og proteinfoldning, hvor lignende datafordelinger kan observeres. Synstransformatorer kunne også være et interessant område at anvende pakkede billeder i forskellig størrelse. Hvilke applikationer tror du ville fungere godt? Vi vil meget gerne høre fra dig!

Læs papiret

Få adgang til koden på GitHub

Tak

 
 
Tak til vores kolleger i Graphcores Applications Engineering-team, Sheng Fu og Mrinal Iyer, for deres bidrag til dette arbejde og tak til Douglas Orr fra Graphcores forskningsteam for hans værdifulde feedback.

Referencer

 
 
[1] M. Kosec, S. Fu, MM Krell, Pakning: Mod 2x NLP BERT Acceleration (2021), arXiv

 
Dr. Mario Michael Krell er Principal Machine Learning Lead hos Graphcore. Mario har forsket i og udviklet maskinlæringsalgoritmer i mere end 12 år og skabt software til så forskellige industrier som robotteknologi, bilindustrien, telekommunikation og sundhedspleje. Hos Graphcore bidrog han til vores imponerende MLPerf-indlæg og har en passion for at accelerere nye ikke-standardmodeller som omtrentlig Bayesiansk beregning til statistisk COVID-19-dataanalyse.

Matej Kosec er AI Applications Specialist hos Graphcore i Palo Alto. Han har tidligere arbejdet som AI-forsker på autonom kørsel ved NIO i San Jose og har en mastergrad i luftfart og astronautik fra Stanford University.

Original. Genopslået med tilladelse.

Relateret:

• Opbygning af en vidensgraf til jobsøgning ved hjælp af BERT
• Sådan træner du en BERT-model fra bunden
• Forstå BERT med Hugging Face