By Dr.Mario Michael Krell, Hoofd Machine Learning Lead bij Graphcore & Matej Kosec, AI-applicatiespecialist bij Graphcore

Afbeelding door auteur.

 

Door een nieuw packing-algoritme te gebruiken, hebben we de natuurlijke taalverwerking ruim twee keer versneld tijdens het trainen van BERT-Large. Onze nieuwe verpakkingstechniek verwijdert opvulling, waardoor aanzienlijk efficiëntere berekeningen mogelijk zijn.

We vermoeden dat dit ook zou kunnen worden toegepast op genomica- en eiwitvouwmodellen en andere modellen met scheve lengteverdelingen om een ​​veel bredere impact te hebben in verschillende industrieën en toepassingen.

In een nieuw artikel hebben we het zeer efficiënte Non-Negative Least Squares Histogram-Packing-algoritme (of NNLSHP) van Graphcore geïntroduceerd, evenals ons BERT-algoritme toegepast op gepakte reeksen [1].

Computationele verspilling in NLP als gevolg van opvulling van reeksen

 
 
We begonnen nieuwe manieren te onderzoeken om de BERT-training te optimaliseren terwijl we aan onze recente werkten benchmarkinzendingen voor MLPerf™. Het doel was om nuttige optimalisaties te ontwikkelen die gemakkelijk in praktijktoepassingen konden worden toegepast. BERT was een logische keuze als een van de modellen waarop we ons bij deze optimalisaties moesten concentreren, omdat het veel wordt gebruikt in de industrie en door veel van onze klanten.

Het verraste ons echt om te horen dat in onze eigen BERT-Large trainingsapplicatie die gebruik maakte van de Wikipedia-dataset, 50% van de tokens in de dataset opvulling was, wat resulteerde in veel verspilde rekenkracht.

Het opvullen van reeksen om ze allemaal op gelijke lengte uit te lijnen is een gebruikelijke aanpak die bij GPU's wordt gebruikt, maar we dachten dat het de moeite waard zou zijn om een ​​andere aanpak te proberen.

Reeksen hebben om twee redenen een grote variatie in lengte:

1. De onderliggende Wikipedia-gegevens laten een grote variatie in documentlengte zien
2. De BERT-voorverwerking zelf verkleint willekeurig de grootte van de geëxtraheerde documenten die worden gecombineerd om een ​​trainingsreeks te genereren

Het opvullen van de lengte tot de maximale lengte van 512 resulteert erin dat 50% van alle tokens opvultokens zijn. Het vervangen van de 50% van de opvulling door echte gegevens zou ertoe kunnen leiden dat 50% meer gegevens worden verwerkt met dezelfde rekeninspanning en dus een dubbele snelheid onder optimale omstandigheden.

Figuur 1: Distributies van Wikipedia-datasets. Afbeelding door auteur.

 

Is dit specifiek voor Wikipedia? Nee.

Is het dan specifiek voor de taal? Nee.

In feite worden scheve lengteverdelingen overal aangetroffen: in taal, genomica en eiwitvouwing. Figuren 2 en 3 tonen verdelingen voor de SQuAD 1.1-dataset en GLUE-datasets.

Figuur 2: SQuAD 1.1 BERT pre-training dataset sequentielengtehistogram voor maximale sequentielengte van 384. Afbeelding door auteur.

 


Figuur 3: Glue-datasetreekslengtehistogrammen voor maximale reekslengte van 128. Afbeelding door auteur.

 

Hoe kunnen we omgaan met de verschillende lengtes en tegelijkertijd computerverspilling vermijden?

De huidige benaderingen vereisen verschillende rekenkernels voor verschillende lengtes of voor de ingenieur om de opvulling programmatisch te verwijderen en deze vervolgens herhaaldelijk weer toe te voegen voor elk aandachtsblok en verliesberekening. Het besparen van rekenkracht door de code op te blazen en complexer te maken was niet aantrekkelijk, dus gingen we op zoek naar iets beters. Kunnen we niet gewoon meerdere reeksen samenvoegen in een pakket met een maximale lengte en dit allemaal samen verwerken? Het blijkt dat we dat kunnen!

Deze aanpak vereist drie belangrijke ingrediënten:

1. Een efficiënt algoritme om te beslissen welke samples moeten worden samengesteld om zo min mogelijk resterende opvulling te hebben
2. Het BERT-model aanpassen om pakketten te verwerken in plaats van reeksen
3. En het aanpassen van de hyperparameters

Verpakking

 
 
In eerste instantie leek het onwaarschijnlijk dat je een grote dataset zoals Wikipedia zeer efficiënt zou kunnen verpakken. Dit probleem staat algemeen bekend als bin-packing. Zelfs als de pakking beperkt is tot drie reeksen of minder, zou het resulterende probleem nog steeds sterk NP-compleet zijn, zonder een efficiënte algoritmische oplossing. Bestaande heuristische verpakkingsalgoritmen waren niet veelbelovend omdat ze een complexiteit van minimaal hadden O(n logboek(n)), waar n is het aantal reeksen (~ 16 miljoen voor Wikipedia). We waren geïnteresseerd in benaderingen die goed zouden kunnen worden geschaald naar miljoenen reeksen.

Twee trucs hebben ons geholpen de complexiteit drastisch te verminderen:

1. Het aantal sequenties in een pakket beperken tot drie (voor onze eerste oplossingsaanpak)
2. Werkt uitsluitend op het histogram van de reekslengte met één bak voor elke voorkomende lengte

Onze maximale reekslengte was 512. Door naar het histogram te gaan, werden de afmetingen en complexiteit dus teruggebracht van 16 miljoen reeksen naar 512 lengtetellingen. Door maximaal drie reeksen in een pakket toe te staan, werd het aantal toegestane lengtecombinaties teruggebracht tot 22K. Dit omvatte al de truc om te eisen dat de reeksen in het pakket op lengte werden gesorteerd. Dus waarom probeer je niet 4 reeksen? Dit verhoogde het aantal combinaties van 22K naar 940K, wat te veel was voor onze eerste modelleringsaanpak. Bovendien bereikte diepte 3 al een opmerkelijk hoge verpakkingsefficiëntie.

Oorspronkelijk dachten we dat het gebruik van meer dan drie reeksen in een pakket de rekenkundige overhead zou vergroten en het convergentiegedrag tijdens de training zou beïnvloeden. Om echter toepassingen zoals inferentie te ondersteunen, die een nog snellere, realtime verpakking vereisen, hebben we het zeer efficiënte Non-Negative Least Squares Histogram-Packing (NNLSHP)-algoritme ontwikkeld.

Niet-negatieve kleinste kwadratenhistogramverpakking (NNLSHP)

 
 
Bin packing wordt vaak geformuleerd als een wiskundig optimalisatieprobleem. Met 16 miljoen sequenties (of meer) is dit echter niet praktisch. Alleen al de probleemvariabelen zouden het geheugen van de meeste machines te boven gaan. Het wiskundige programma voor een op histogrammen gebaseerde benadering is behoorlijk netjes. Voor de eenvoud hebben we gekozen voor een kleinste kwadratenbenadering (Bijl=b) met histogramvector b. We hebben het uitgebreid door de strategievector op te vragen x om niet-negatief te zijn en gewichten toe te voegen om kleine opvulling mogelijk te maken.

Het lastige deel was de strategiematrix. Elke kolom heeft een maximale som van drie en codeert welke reeksen bij elkaar worden gepakt om precies overeen te komen met de gewenste totale lengte; 512 in ons geval. De rijen coderen elk van de mogelijke combinaties om een ​​lengte te bereiken die gelijk is aan de totale lengte. De strategievector x is waar we naar op zoek waren, en beschrijft hoe vaak we een van de 20 combinaties kiezen. Interessant genoeg werden er uiteindelijk slechts ongeveer 600 combinaties geselecteerd. Om een ​​exacte oplossing te krijgen, telt de strategie mee x zouden positieve gehele getallen moeten zijn, maar we realiseerden ons dat dit een benaderende afgeronde oplossing was met alleen niet-negatieve getallen x was voldoende. Voor een benaderende oplossing kan een eenvoudige kant-en-klare oplosser worden gebruikt om binnen 30 seconden een resultaat te krijgen.

Figuur 4: Voorbeeld van een strategiematrix voor reekslengte 8 en pakdiepte 3. De rijen staan ​​voor de reeksen met lengte 1–8 die samen worden gepakt en de kolommen staan ​​voor alle mogelijke lengtecombinaties in een pakket zonder specifieke volgorde. Afbeelding door auteur.

 

Uiteindelijk moesten we enkele voorbeelden repareren waaraan geen strategie was toegewezen, maar die waren minimaal. We hebben ook een variantoplosser ontwikkeld die afdwingt dat elke reeks wordt verpakt, mogelijk met opvulling, en een weging heeft die afhankelijk is van de opvulling. Het duurde veel langer en de oplossing was niet veel beter.

Kortste pakket-eerste histogramverpakking

 
 
NNLSHP heeft voor ons een adequate verpakkingsaanpak geleverd. We vroegen ons echter af of we in theorie een snellere online aanpak konden krijgen en de beperking van het samenvoegen van slechts drie reeksen konden wegnemen.

Daarom hebben we wat inspiratie gehaald uit bestaande pakkingsalgoritmen, maar hebben we ons nog steeds op de histogrammen geconcentreerd.

Er zijn vier ingrediënten voor ons eerste algoritme, Shortest-pack-first histogram-packing (SPFHP):

1. Werk op basis van de tellingen van het histogram, van de langste reeksen tot de kortste
2. Als de huidige reekslengte in geen enkel pakket past, start dan een nieuwe set pakketten
3. Als er meerdere passingen zijn, neem dan het pakket waarvan de som van de reekslengte het kortst is en pas respectievelijk de tellingen aan
4. Controleer opnieuw of de overige tellingen overeenkomen

Deze aanpak was het meest eenvoudig te implementeren en duurde slechts 0.02 seconden.

Een variant was om de grootste som van de reekslengte te nemen in plaats van de kortste en gesplitste tellingen om meer perfecte passingen te krijgen. Over het geheel genomen heeft dit de efficiëntie niet veel veranderd, maar de complexiteit van de code aanzienlijk vergroot.

Hoe het kortste pakket-eerste histogrampakking werkt. Animatie door auteur.

 

Wikipedia, SQuAD 1.1, GLUE-verpakkingsresultaten

 
 
Tabel 1, 2 en 3 tonen de pakkingsresultaten van onze twee voorgestelde algoritmen. Verpakkingsdiepte beschrijft het maximale aantal verpakte sequenties. Verpakkingsdiepte 1 is de basislijn-BERT-implementatie. De maximaal optredende pakkingsdiepte, wanneer er geen limiet is ingesteld, wordt aangegeven met een extra “max”. De aantal pakken beschrijft de lengte van de nieuwe ingepakte dataset. Efficiënt is het percentage echte tokens in de ingepakte dataset. De verpakkingsfactor beschrijft de resulterende potentiële versnelling vergeleken met pakkingdiepte 1.

We hadden vier belangrijke observaties:

1. Hoe schever een verdeling, hoe groter de voordelen van verpakken.
2. Alle datasets profiteren van packing. Sommige zelfs met meer dan een factor 2.
3. SPFHP wordt efficiënter als de pakdiepte niet beperkt is.
4. Voor een maximaal aantal van 3 gepakte sequenties geldt: hoe complexer NNLHP is, hoe efficiënter het is (99.75 vs. 89.44).

Tabel 1: Belangrijkste prestatieresultaten van voorgestelde verpakkingsalgoritmen (SPFHP en NNNLSHP) op Wikipedia. Afbeelding door auteur.

 


Tabel 2: Prestatieresultaten van voorgestelde verpakkingsalgoritmen voor SQUaD 1.1 BERT-vooropleiding. Afbeelding door auteur.

 


Tabel 3: Prestatieresultaten van voorgestelde verpakkingsalgoritmen voor de GLUE-dataset. Alleen de basislijn en de SPFHP-pakkingresultaten worden weergegeven, zonder beperking van de pakkingdiepte. Afbeelding door auteur.

 

BERT-verwerkingsaanpassing

 
 
Iets interessants aan de BERT-architectuur is dat de meeste verwerking op tokenniveau plaatsvindt, wat betekent dat het onze verpakking niet verstoort. Er zijn slechts vier componenten die aanpassing behoeven: het aandachtsmasker, het MLM-verlies, het NSP-verlies en de nauwkeurigheid.

De sleutel voor alle vier de benaderingen om met verschillende aantallen sequenties om te gaan, was vectorisatie en het gebruik van een maximaal aantal sequenties dat aaneengeschakeld kan worden. Ter attentie hadden we al een masker om de opvulling aan te pakken. Dit uitbreiden naar meerdere sequenties was eenvoudig, zoals te zien is in de volgende TensorFlow-pseudocode. Het concept is dat we ervoor hebben gezorgd dat de aandacht beperkt blijft tot de afzonderlijke sequenties en niet verder kan reiken.

Let op maskercodevoorbeeld.

 


Figuur 5: Voorbeeld nul-één-masker

 

Voor de verliesberekening pakken we in principe de reeksen uit en berekenen de afzonderlijke verliezen, waarbij we uiteindelijk het gemiddelde van de verliezen over de reeksen (in plaats van pakketten) verkrijgen.

Voor het MLM-verlies ziet de code er als volgt uit:

Codevoorbeeld voor verliesberekening.

 

Voor het NSP-verlies en de nauwkeurigheid is het principe hetzelfde. In onze openbare voorbeelden vindt u de betreffende code bij ons in huis PopART-framework.

Wikipedia-overhead- en versnellingsschatting

 
 
Bij onze aanpassing van BERT hadden we twee vragen:

1. Hoeveel overhead brengt het met zich mee?
2. Hoeveel hangt de overhead af van het maximale aantal sequenties dat in een pakket wordt samengevoegd?

Omdat datavoorbereiding in BERT omslachtig kan zijn, hebben we een snelkoppeling gebruikt en de code voor meerdere verschillende pakkingsdieptes gecompileerd en de respectievelijke (gemeten) cycli vergeleken. De resultaten worden weergegeven in Tabel 4. Met boven het hoofdgeven we de procentuele afname van de doorvoer aan als gevolg van wijzigingen in het model om inpakken mogelijk te maken (zoals het maskeringsschema voor aandacht en de gewijzigde verliesberekening). De gerealiseerde versnelling is de combinatie van de versnelling als gevolg van packing (de verpakkingsfactor) en de daling van de doorvoer als gevolg van de boven het hoofd.

Tabel 4: Geschatte versnellingsvergelijking van voorgestelde verpakkingsalgoritmen (SPFHP en NNNLSHP) op Wikipedia. Afbeelding door auteur.

 

Dankzij de vectorisatietechniek is de overhead verrassend klein en is er geen nadeel verbonden aan het samenpakken van veel reeksen.

Hyperparameter-aanpassingen

 
 
Met verpakken verdubbelen we (gemiddeld) de effectieve batchgrootte. Dit betekent dat we de hyperparameters van de training moeten aanpassen. Een eenvoudige truc is om het aantal gradiëntaccumulaties te halveren om dezelfde effectieve gemiddelde batchgrootte te behouden als vóór de training. Door een benchmarkinstelling met vooraf getrainde controlepunten te gebruiken, kunnen we zien dat de nauwkeurigheidscurven perfect overeenkomen.

Figuur 6: Vergelijking van leercurven voor verpakte en onverpakte verwerking met kleinere batchgrootte voor de verpakte aanpak. Afbeeldingen per auteur.

 

De nauwkeurigheid komt overeen: het MLM-trainingsverlies kan in het begin enigszins afwijken, maar wordt snel ingehaald. Dit aanvankelijke verschil kan voortkomen uit kleine aanpassingen van de aandachtslagen die in de vorige training mogelijk gericht waren op korte reeksen.

Om vertraging te voorkomen, helpt het soms om de oorspronkelijke batchgrootte hetzelfde te houden en de hyperparameters aan te passen aan de grotere effectieve batchgrootte (verdubbeld). De belangrijkste hyperparameters waarmee u rekening moet houden, zijn de bètaparameters en de leersnelheden. Een veel voorkomende aanpak is het verdubbelen van de batchgrootte, wat in ons geval de prestaties verminderde. Als we naar de statistieken van de LAMB-optimizer kijken, kunnen we bewijzen dat het verhogen van de bètaparameter tot de macht van de pakkingsfactor overeenkomt met het achter elkaar trainen van meerdere batches om momentum en snelheid vergelijkbaar te houden.

Figuur 7: Vergelijking van leercurven voor verpakte en onverpakte verwerking met heuristiek toegepast. Afbeeldingen per auteur.

 

Onze experimenten hebben aangetoond dat het een goede heuristiek is om bèta tot de macht twee te brengen. In dit scenario wordt niet verwacht dat de curven overeenkomen, omdat het vergroten van de batchgrootte doorgaans de convergentiesnelheid in de zin van monsters/epochs verlaagt totdat een doelnauwkeurigheid is bereikt.

De vraag is nu of we in het praktische scenario werkelijk de verwachte versnelling krijgen?

Figuur 8: Vergelijking van leercurven voor verpakte en onverpakte verwerking in de geoptimaliseerde opstelling. Afbeeldingen per auteur.

 

Ja dat doen we! We hebben een extra versnelling behaald omdat we de gegevensoverdracht hebben gecomprimeerd.

Conclusie

 
 
Het samenvoegen van zinnen kan rekeninspanning en het milieu besparen. Deze techniek kan in elk raamwerk worden geïmplementeerd, inclusief PyTorch en TensorFlow. We bereikten een duidelijke 2x versnelling en gaandeweg breidden we de stand van de techniek op het gebied van verpakkingsalgoritmen uit.

Andere toepassingen waar we nieuwsgierig naar zijn, zijn genomica en eiwitvouwing, waarbij vergelijkbare gegevensverdelingen kunnen worden waargenomen. Visietransformatoren kunnen ook een interessant gebied zijn om verpakte afbeeldingen van verschillende grootte toe te passen. Welke applicaties zouden volgens jou goed werken? Wij horen graag van u!

De krant lezen

Toegang tot de code op GitHub

Bedankt

 
 
Dank aan onze collega's in het Applications Engineering-team van Graphcore, Sheng Fu en Mrinal Iyer, voor hun bijdragen aan dit werk en aan Douglas Orr van het onderzoeksteam van Graphcore voor zijn waardevolle feedback.

Referenties

 
 
[1] M. Kosec, S. Fu, MM Krell, Verpakking: richting 2x NLP BERT-versnelling (2021), arXiv

 
Dr.Mario Michael Krell is een Principal Machine Learning Lead bij Graphcore. Mario onderzoekt en ontwikkelt al ruim twaalf jaar machine learning-algoritmen en creëert software voor uiteenlopende sectoren, zoals robotica, automobielsector, telecommunicatie en gezondheidszorg. Bij Graphcore heeft hij bijgedragen aan ons indrukwekkend MLPerf-inzendingen en heeft een passie voor het versnellen van nieuwe niet-standaardmodellen, zoals geschatte Bayesiaanse berekeningen voor statistische COVID-19-gegevensanalyse.

Matej Kosec is een AI-applicatiespecialist bij Graphcore in Palo Alto. Hij heeft eerder als AI-wetenschapper gewerkt aan autonoom rijden bij NIO in San Jose, en heeft een masterdiploma in luchtvaart en ruimtevaart behaald aan Stanford University.

ORIGINELE. Met toestemming opnieuw gepost.

Zie ook:

• Een kenniskaart maken voor het zoeken naar werk met BERT
• Een BERT-model vanaf nul trainen
• BERT begrijpen met knuffelend gezicht