By Dr. Mario Michael Krell, hovedleder for maskinlæring hos Graphcore & Matej Kosec, AI Applications Specialist hos Graphcore

Bilde av forfatter.

 

Ved å bruke en ny pakkealgoritme har vi fremskyndet Natural Language Processing med mer enn 2 ganger mens vi trener BERT-Large. Vår nye pakketeknikk fjerner polstring, noe som muliggjør betydelig mer effektiv beregning.

Vi mistenker at dette også kan brukes på genomikk og proteinfoldingsmodeller og andre modeller med skjeve lengdefordelinger for å få en mye bredere innvirkning i forskjellige bransjer og applikasjoner.

Vi introduserte Graphcores svært effektive Non-Negative Least Squares Histogram-Packing-algoritme (eller NNLSHP) så vel som vår BERT-algoritme brukt på pakkede sekvenser i en ny artikkel [1].

Computational Waste i NLP på grunn av sekvenspolstring

 
 
Vi begynte å undersøke nye måter å optimalisere BERT-opplæringen på mens vi jobbet med vår siste benchmark-innleveringer til MLPerf™. Målet var å utvikle nyttige optimaliseringer som lett kunne tas i bruk i virkelige applikasjoner. BERT var et naturlig valg som en av modellene å fokusere på for disse optimaliseringene, siden den er mye brukt i industrien og av mange av våre kunder.

Det overrasket oss virkelig å høre at i vår egen BERT-Large-treningsapplikasjon som bruker Wikipedia-datasettet, var 50 % av tokenene i datasettet polstring – noe som resulterte i mye bortkastet databehandling.

Utfyllingssekvenser for å justere dem alle til lik lengde er en vanlig tilnærming som brukes med GPUer, men vi trodde det ville være verdt å prøve en annen tilnærming.

Sekvenser har en stor variasjon i lengde av to grunner:

1. De underliggende Wikipedia-dataene viser en stor variasjon i dokumentlengde
2. Selve BERT-forbehandlingen reduserer tilfeldig størrelsen på utpakkede dokumenter som kombineres for å generere en treningssekvens

Å fylle opp lengden til maksimal lengde på 512 resulterer i at 50 % av alle tokens er polstringssymboler. Å erstatte 50 % av polstringen med ekte data kan føre til at 50 % mer data blir behandlet med samme beregningsinnsats og dermed 2x hastigheten opp under optimale forhold.

Figur 1: Wikipedia datasettdistribusjoner. Bilde av forfatter.

 

Er dette spesifikt for Wikipedia? Nei.

Vel, er det spesifikt for språk? Nei.

Faktisk finnes skjeve lengdefordelinger overalt: i språk, genomikk og proteinfolding. Figurene 2 og 3 viser distribusjoner for SQuAD 1.1-datasettet og GLUE-datasettene.

Figur 2: SQuAD 1.1 BERT før-trening datasett sekvenslengde histogram for maksimal sekvenslengde på 384. Bilde av forfatter.

 


Figur 3: GLUE datasettsekvenslengdehistogrammer for maksimal sekvenslengde på 128. Bilde etter forfatter.

 

Hvordan kan vi håndtere de ulike lengdene samtidig som vi unngår beregningsavfallet?

Gjeldende tilnærminger krever forskjellige beregningskjerner for forskjellige lengder eller for ingeniøren å programmatisk fjerne polstringen og deretter legge den inn igjen gjentatte ganger for hver oppmerksomhetsblokk og tapsberegning. Å lagre databehandling ved å sprenge koden og gjøre den mer kompleks var ikke tiltalende, så vi søkte etter noe bedre. Kan vi ikke bare sette flere sekvenser sammen i en pakke med maksimal lengde og behandle det hele sammen? Det viser seg at vi kan!

Denne tilnærmingen krever tre nøkkelingredienser:

1. En effektiv algoritme for å bestemme hvilke prøver som skal settes sammen for å ha så lite gjenværende polstring som mulig
2. Justering av BERT-modellen til å behandle pakker i stedet for sekvenser
3. Og justere hyperparametrene

Pakking

 
 
Til å begynne med virket det usannsynlig at du ville være i stand til å pakke et stort datasett som Wikipedia veldig effektivt. Dette problemet er vanligvis kjent som bin-packing. Selv når pakking er begrenset til tre sekvenser eller mindre, vil det resulterende problemet fortsatt være sterkt NP-fullstendig, og mangler en effektiv algoritmisk løsning. Eksisterende heuristiske pakkealgoritmer var ikke lovende fordi de hadde en kompleksitet på minst O(n logg(n)), hvor n er antall sekvenser (~16 millioner for Wikipedia). Vi var interessert i tilnærminger som kunne skaleres godt til millioner av sekvenser.

To triks hjalp oss med å redusere kompleksiteten drastisk:

1. Begrensning av antall sekvenser i en pakke til tre (for vår første løsningsmetode)
2. Fungerer utelukkende på histogrammet av sekvenslengde med en boks for hver forekommende lengde

Vår maksimale sekvenslengde var 512. Så, å flytte til histogrammet reduserte dimensjonen og kompleksiteten fra 16 millioner sekvenser til 512 lengdeteller. Ved å tillate maksimalt tre sekvenser i en pakke reduserte antallet tillatte lengdekombinasjoner til 22K. Dette inkluderte allerede trikset for å kreve at sekvensene sorteres etter lengde i pakken. Så hvorfor ikke prøve 4 sekvenser? Dette økte antallet kombinasjoner fra 22K til 940K, noe som var for mye for vår første modelleringstilnærming. I tillegg har dybde 3 allerede oppnådd bemerkelsesverdig høy pakkeeffektivitet.

Opprinnelig trodde vi at bruk av mer enn tre sekvenser i en pakke ville øke beregningsoverheaden og påvirke konvergensatferden under trening. For å støtte applikasjoner som inferens, som krever enda raskere pakking i sanntid, utviklet vi imidlertid den svært effektive Non-Negative Least Squares Histogram-Packing (NNLSHP) algoritmen.

Ikke-negativ Least Squares Histogram-Packing (NNLSHP)

 
 
Binding er ganske ofte formulert som et matematisk optimaliseringsproblem. Med 16 millioner sekvenser (eller mer) er dette imidlertid ikke praktisk. Problemvariablene alene ville overskride de fleste maskiners minne. Det matematiske programmet for en histogrambasert tilnærming er ganske ryddig. For enkelhets skyld bestemte vi oss for en minste kvadraters tilnærming (Ax=b) med histogramvektor b. Vi utvidet den ved å be om strategivektoren x å være ikke-negativ og legge til vekter for å tillate mindre polstring.

Den vanskelige delen var strategimatrisen. Hver kolonne har en maksimal sum på tre og koder for hvilke sekvenser som blir pakket sammen for nøyaktig å matche ønsket totallengde; 512 i vårt tilfelle. Radene koder for hver av de potensielle kombinasjonene for å nå en lengde av den totale lengden. Strategivektoren x er det vi lette etter, som beskriver hvor ofte vi velger hvilken som helst av 20k-kombinasjonene. Interessant nok ble bare rundt 600 kombinasjoner valgt på slutten. For å få en eksakt løsning, teller strategien med x må være positive heltall, men vi innså at en omtrentlig avrundet løsning med bare ikke-negative x var tilstrekkelig. For en omtrentlig løsning kan en enkel ut-av-esken-løser brukes for å få et resultat innen 30 sekunder.

Figur 4: Eksempel på en strategimatrise for sekvenslengde 8 og pakkedybde 3. Radene står for sekvensene med lengde 1–8 som pakkes sammen og kolonnene står for alle mulige lengdekombinasjoner i en pakke uten spesiell rekkefølge. Bilde av forfatter.

 

På slutten måtte vi fikse noen prøver som ikke ble tildelt en strategi, men de var minimale. Vi utviklet også en variantløser som fremtvinger at hver sekvens blir pakket, potensielt med polstring, og har en vekting avhengig av polstringen. Det tok mye lengre tid, og løsningen ble ikke mye bedre.

Shortest-Pack-First Histogram Packing

 
 
NNLSHP leverte en tilstrekkelig pakketilnærming for oss. Vi lurte imidlertid på om vi teoretisk sett kunne få en raskere nettbasert tilnærming og fjerne begrensningen med å sette bare 3 sekvenser sammen.

Derfor tok vi litt inspirasjon fra eksisterende pakkealgoritmer, men fokuserte fortsatt på histogrammene.

Det er fire ingredienser for vår første algoritme, Shortest-pack-first histogram-packing (SPFHP):

1. Operer på tellingene til histogrammet fra lengste sekvenser til korteste
2. Hvis gjeldende sekvenslengde ikke passer inn i noen pakke, start et nytt sett med pakker
3. Hvis det er flere tilpasninger, ta pakken der summen av sekvenslengden er kortest og endre tellingene hhv.
4. Se igjen for å se om de gjenværende tellingene passer

Denne tilnærmingen var den enkleste å implementere og tok bare 0.02 sekunder.

En variant var å ta den største summen av sekvenslengde i stedet for de korteste og delte tellingene for å få mer perfekte passform. Totalt sett endret dette ikke effektiviteten mye, men økte kodekompleksiteten mye.

Hvordan shortest-pack-first histogrampakking fungerer. Animasjon av forfatter.

 

Wikipedia, SQuAD 1.1, GLUE-pakkingsresultater

 
 
Tabell 1, 2 og 3 viser pakkeresultatene til våre to foreslåtte algoritmer. Pakningsdybde beskriver maksimalt antall pakkede sekvenser. Pakkedybde 1 er BERT-implementeringen. Den maksimalt forekommende pakkedybden, dersom ingen grense er satt, er merket med en ekstra "maks". De antall pakker beskriver lengden på det nye pakkede datasettet. Effektivitet er prosentandelen av ekte tokens i det pakkede datasettet. De pakkefaktor beskriver den resulterende potensielle hastigheten sammenlignet med pakkedybde 1.

Vi hadde fire hovedobservasjoner:

1. Jo mer skjev fordeling, jo større er fordelene ved å pakke.
2. Alle datasett drar nytte av pakking. Noen til og med med mer enn en faktor 2.
3. SPFHP blir mer effektivt når pakkedybden ikke er begrenset.
4. For et maksimalt antall 3 pakkede sekvenser, jo mer kompleks NNLSHP er, desto mer effektiv er den (99.75 vs. 89.44).

Tabell 1: Nøkkelytelsesresultater for foreslåtte pakkealgoritmer (SPFHP og NNLSHP) på Wikipedia. Bilde av forfatter.

 


Tabell 2: Ytelsesresultater av foreslåtte pakkealgoritmer for SQUaD 1.1 BERT førtrening. Bilde av forfatter.

 


Tabell 3: Ytelsesresultater av foreslåtte pakkealgoritmer for GLUE-datasettet. Bare baseline- og SPFHP-pakkingsresultatene uten å begrense pakkedybden vises. Bilde av forfatter.

 

BERT-behandlingsjustering

 
 
Noe interessant med BERT-arkitekturen er at mesteparten av behandlingen skjer på tokennivå, noe som betyr at den ikke forstyrrer pakkingen vår. Det er bare fire komponenter som trenger en justering: oppmerksomhetsmasken, MLM-tapet, NSP-tapet og nøyaktigheten.

Nøkkelen for alle fire tilnærmingene for å håndtere forskjellige antall sekvenser var vektorisering og bruk av et maksimalt antall sekvenser som kan settes sammen. For oppmerksomhet hadde vi allerede en maske for å adressere polstringen. Å utvide dette til flere sekvenser var enkelt, som kan sees i følgende TensorFlow-pseudokode. Konseptet er at vi sørget for at oppmerksomheten er begrenset til de separate sekvensene og ikke kan strekke seg utover det.

Kodeeksempel for oppmerksomhetsmaske.

 


Figur 5: Eksempel null-en maske

 

For tapsberegningen pakker vi i prinsippet ut sekvensene og beregner de separate tapene, og får til slutt gjennomsnittet av tapene over sekvensene (i stedet for pakker).

For MLM-tapet ser koden slik ut:

Kodeeksempel for tapsberegning.

 

For NSP-tapet og nøyaktigheten er prinsippet det samme. I våre offentlige eksempler kan du finne den respektive koden med vår interne PopART-rammeverk.

Wikipedia overhead og speedup estimat

 
 
Med vår modifikasjon av BERT hadde vi to spørsmål:

1. Hvor mye overhead fører det med seg?
2. Hvor mye avhenger overheaden av maksimalt antall sekvenser som settes sammen i en pakke?

Siden dataforberedelse i BERT kan være tungvint, brukte vi en snarvei og kompilerte koden for flere forskjellige pakkedybder og sammenlignet de respektive (målte) syklusene. Resultatene er vist i tabell 4. Med overhead, angir vi den prosentvise reduksjonen i gjennomstrømning på grunn av endringer i modellen for å muliggjøre pakking (som maskeringsskjemaet for oppmerksomhet og endret tapsberegning). De realisert fremskyndelse er kombinasjonen av hastigheten på grunn av pakking (den pakkefaktor) og reduksjonen i gjennomstrømning på grunn av overhead.

Tabell 4: Estimert hastighetssammenligning av foreslåtte pakkealgoritmer (SPFHP og NNLSHP) på Wikipedia. Bilde av forfatter.

 

Takket være vektoriseringsteknikken er overheaden overraskende liten og det er ingen ulempe å pakke mange sekvenser sammen.

Hyperparameter-justeringer

 
 
Med pakking dobler vi den effektive batchstørrelsen (i gjennomsnitt). Dette betyr at vi må justere treningshyperparametrene. Et enkelt triks er å halvere antallet gradientakkumuleringer for å beholde den samme effektive gjennomsnittlige batchstørrelsen som før trening. Ved å bruke en benchmark-innstilling med forhåndstrente sjekkpunkter, kan vi se at nøyaktighetskurvene passer perfekt.

Figur 6: Sammenligning av læringskurver for pakket og upakket prosessering med redusert batchstørrelse for den pakket tilnærming. Bilder av forfatter.

 

Nøyaktigheten samsvarer: MLM-treningstapet kan være litt annerledes i begynnelsen, men tar raskt igjen. Denne innledende forskjellen kan komme fra små justeringer av oppmerksomhetslagene som kan ha vært partisk mot korte sekvenser i forrige trening.

For å unngå en nedgang hjelper det noen ganger å holde den opprinnelige batchstørrelsen den samme og justere hyperparametrene til den økte effektive batchstørrelsen (doblet). De viktigste hyperparametrene å vurdere er betaparametrene og læringsratene. En vanlig tilnærming er å doble batchstørrelsen, noe som i vårt tilfelle reduserte ytelsen. Når vi ser på statistikken til LAMB-optimalisatoren, kan vi bevise at å heve betaparameteren til kraften til pakningsfaktoren tilsvarer å trene flere batcher etter hverandre for å holde momentum og hastighet sammenlignbare.

Figur 7: Sammenligning av læringskurver for pakket og upakket prosessering med heuristikk anvendt. Bilder av forfatter.

 

Eksperimentene våre viste at å ta beta til kraften av to er en god heuristikk. I dette scenariet forventes det ikke at kurvene stemmer overens fordi å øke batchstørrelsen vanligvis reduserer konvergenshastigheten i betydningen prøver/epoker inntil en målnøyaktighet er nådd.

Nå er spørsmålet om vi i det praktiske scenariet virkelig får den forventede hastigheten?

Figur 8: Sammenligning av læringskurver for pakket og upakket prosessering i optimalisert oppsett. Bilder av forfatter.

 

Ja det gjør vi! Vi fikk en ekstra hastighet fordi vi komprimerte dataoverføringen.

konklusjonen

 
 
Å pakke sammen setninger kan spare datainnsats og miljøet. Denne teknikken kan implementeres i alle rammeverk, inkludert PyTorch og TensorFlow. Vi oppnådde en klar 2x speed-up, og underveis utvidet vi toppmoderne innen pakkealgoritmer.

Andre applikasjoner som vi er nysgjerrige på er genomikk og proteinfolding hvor lignende datafordelinger kan observeres. Synstransformatorer kan også være et interessant område for å bruke pakkede bilder i forskjellig størrelse. Hvilke applikasjoner tror du vil fungere bra? Vi vil gjerne høre fra deg!

Les avisen

Få tilgang til koden på GitHub

Takk

 
 
Takk til kollegene våre i Graphcores applikasjonsingeniørteam, Sheng Fu og Mrinal Iyer, for deres bidrag til dette arbeidet og takk til Douglas Orr fra Graphcores forskningsteam for hans verdifulle tilbakemelding.

Referanser

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

 
Dr. Mario Michael Krell er hovedansvarlig for maskinlæring hos Graphcore. Mario har forsket på og utviklet maskinlæringsalgoritmer i mer enn 12 år, og laget programvare for så forskjellige bransjer som robotikk, bilindustri, telekommunikasjon og helsevesen. Hos Graphcore bidro han til vår imponerende MLPerf-innleveringer og har en lidenskap for å akselerere nye ikke-standardmodeller som omtrentlig Bayesiansk beregning for statistisk COVID-19-dataanalyse.

Matej Kosec er en AI Applications Specialist hos Graphcore i Palo Alto. Han har tidligere jobbet som AI-forsker på autonom kjøring ved NIO i San Jose, og har en mastergrad i luftfart og astronautikk fra Stanford University.

original. Ompostet med tillatelse.

Relatert:

• Bygg en kunnskapsgraf for jobbsøk ved hjelp av BERT
• Hvordan trene en BERT -modell fra bunnen av
• Forståelse av BERT med klemmende ansikt