By Dr. Mario Michael Krell, Principal Machine Learning Lead bei Graphcore & Matej Kosec, Spezialist für KI-Anwendungen bei Graphcore

Bild vom Autor.

 

Durch die Verwendung eines neuen Packalgorithmus haben wir die Verarbeitung natürlicher Sprache beim Training von BERT-Large um mehr als das Doppelte beschleunigt. Unsere neue Packtechnik entfernt das Auffüllen und ermöglicht eine wesentlich effizientere Berechnung.

Wir vermuten, dass dies auch auf Genomik- und Proteinfaltungsmodelle und andere Modelle mit verzerrten Längenverteilungen angewendet werden könnte, um eine viel breitere Wirkung in verschiedenen Branchen und Anwendungen zu erzielen.

Wir haben den hocheffizienten Non-Negative Least Squares Histogram-Packing-Algorithmus (oder NNLSHP) von Graphcore sowie unseren BERT-Algorithmus, der auf gepackte Sequenzen angewendet wird, in einem neuen Artikel [1] vorgestellt.

Computational Waste im NLP durch Sequence Padding

 
 
Wir haben begonnen, neue Möglichkeiten zur Optimierung des BERT-Trainings zu untersuchen, während wir an unserem jüngsten Benchmark-Einreichungen an MLPerf™. Ziel war es, nützliche Optimierungen zu entwickeln, die leicht in reale Anwendungen übernommen werden können. BERT war eine naheliegende Wahl als eines der Modelle, auf die man sich für diese Optimierungen konzentrieren sollte, da es in der Industrie und bei vielen unserer Kunden weit verbreitet ist.

Es hat uns wirklich überrascht zu erfahren, dass in unserer eigenen BERT-Large-Trainingsanwendung, die den Wikipedia-Datensatz verwendet, 50% der Token im Datensatz aufgefüllt wurden – was zu viel Rechenverschwendung führte.

Das Auffüllen von Sequenzen, um sie alle auf die gleiche Länge auszurichten, ist ein bei GPUs üblicher Ansatz, aber wir dachten, es wäre einen anderen Ansatz wert.

Sequenzen weisen aus zwei Gründen eine große Variation der Länge auf:

1. Die zugrunde liegenden Wikipedia-Daten zeigen eine große Variation der Dokumentlänge
2. Die BERT-Vorverarbeitung selbst reduziert zufällig die Größe der extrahierten Dokumente, die zu einer Trainingssequenz kombiniert werden

Das Auffüllen der Länge bis zur maximalen Länge von 512 führt dazu, dass 50 % aller Tokens Padding-Token sind. Das Ersetzen der 50% des Paddings durch echte Daten könnte dazu führen, dass bei gleichem Rechenaufwand 50% mehr Daten verarbeitet werden und somit unter optimalen Bedingungen eine 2-fache Geschwindigkeit erreicht wird.

Abbildung 1: Verteilungen von Wikipedia-Datensätzen. Bild vom Autor.

 

Ist das spezifisch für Wikipedia? Nein.

Nun, ist es dann spezifisch für die Sprache? Nein.

Tatsächlich findet man überall verzerrte Längenverteilungen: in der Sprache, Genomik und Proteinfaltung. Die Abbildungen 2 und 3 zeigen Verteilungen für den SQuAD 1.1-Datensatz und GLUE-Datensätze.

Abbildung 2: SQuAD 1.1 BERT-Sequenzlängenhistogramm vor dem Training für die maximale Sequenzlänge von 384. Bild vom Autor.

 


Abbildung 3: Histogramme der GLUE-Datensatzsequenzlänge für eine maximale Sequenzlänge von 128. Bild vom Autor.

 

Wie können wir mit den unterschiedlichen Längen umgehen und gleichzeitig Rechenverschwendung vermeiden?

Aktuelle Ansätze erfordern unterschiedliche Rechenkerne für unterschiedliche Längen oder für den Ingenieur, die Auffüllung programmgesteuert zu entfernen und sie dann für jede Aufmerksamkeitsblock- und Verlustberechnung wiederholt hinzuzufügen. Rechenleistung zu sparen, indem man den Code aufbläst und komplexer macht, war nicht attraktiv, also suchten wir nach etwas Besserem. Können wir nicht einfach mehrere Sequenzen in einem Pack mit maximaler Länge zusammenfassen und alles zusammen verarbeiten? Es stellt sich heraus, wir können!

Dieser Ansatz erfordert drei wichtige Zutaten:

1. Ein effizienter Algorithmus, um zu entscheiden, welche Samples zusammengestellt werden sollen, um so wenig Rest-Padding wie möglich zu haben
2. Anpassung des BERT-Modells, um Packs statt Sequenzen zu verarbeiten
3. Und die Hyperparameter anpassen

Packing

 
 
Zunächst schien es unwahrscheinlich, dass Sie einen großen Datensatz wie Wikipedia sehr effizient packen können. Dieses Problem wird allgemein als Bin-Packing bezeichnet. Selbst wenn das Packen auf drei Folgen oder weniger beschränkt ist, wäre das resultierende Problem immer noch stark NP-vollständig und es fehlt eine effiziente algorithmische Lösung. Bestehende heuristische Packalgorithmen waren nicht erfolgversprechend, da sie eine Komplexität von mindestens O(n-Protokoll(n)), wo n ist die Anzahl der Sequenzen (~16M für Wikipedia). Wir waren an Ansätzen interessiert, die sich gut auf Millionen von Sequenzen skalieren lassen.

Zwei Tricks haben uns geholfen, die Komplexität drastisch zu reduzieren:

1. Begrenzung der Anzahl der Sequenzen in einer Packung auf drei (für unseren ersten Lösungsansatz)
2. Betrieb ausschließlich auf dem Histogramm der Sequenzlänge mit einem Bin für jede vorkommende Länge

Unsere maximale Sequenzlänge war 512. Der Wechsel zum Histogramm reduzierte die Dimension und Komplexität von 16 Millionen Sequenzen auf 512 Längenzählungen. Das Zulassen von maximal drei Sequenzen in einem Paket reduzierte die Anzahl der zulässigen Längenkombinationen auf 22K. Darin war bereits der Trick enthalten, dass die Sequenzen im Pack nach Länge sortiert werden müssen. Warum also nicht 4 Sequenzen ausprobieren? Dadurch erhöhte sich die Anzahl der Kombinationen von 22 auf 940, was für unseren ersten Modellierungsansatz zu viel war. Zudem erreichte Tiefe 3 bereits eine bemerkenswert hohe Packungseffizienz.

Ursprünglich dachten wir, dass die Verwendung von mehr als drei Sequenzen in einem Paket den Rechenaufwand erhöhen und das Konvergenzverhalten während des Trainings beeinflussen würde. Um jedoch Anwendungen wie Inferenz zu unterstützen, die ein noch schnelleres Echtzeit-Packen erfordern, haben wir den hocheffizienten Non-Negative Least Squares Histogram-Packing (NNLSHP)-Algorithmus entwickelt.

Histogrammpackung mit nicht negativen kleinsten Quadraten (NNLSHP)

 
 
Bin Packing wird häufig als mathematisches Optimierungsproblem formuliert. Bei 16 Millionen Sequenzen (oder mehr) ist dies jedoch nicht praktikabel. Allein die Problemvariablen würden den Speicher der meisten Maschinen übersteigen. Das mathematische Programm für einen histogrammbasierten Ansatz ist recht ordentlich. Der Einfachheit halber haben wir uns für einen Ansatz der kleinsten Quadrate (Ax=b) mit Histogrammvektor b. Wir haben es erweitert, indem wir den Strategievektor angefordert haben x nicht negativ sein und Gewichte hinzufügen, um kleinere Auffüllungen zu ermöglichen.

Der knifflige Teil war die Strategiematrix. Jede Spalte hat eine maximale Summe von drei und kodiert, welche Sequenzen zusammengepackt werden, um genau der gewünschten Gesamtlänge zu entsprechen; 512 in unserem Fall. Die Zeilen codieren jede der möglichen Kombinationen, um eine Länge der Gesamtlänge zu erreichen. Der Strategievektor x ist das, wonach wir gesucht haben, das beschreibt, wie oft wir eine der 20 Kombinationen auswählen. Interessanterweise wurden am Ende nur rund 600 Kombinationen ausgewählt. Um eine exakte Lösung zu erhalten, zählt die Strategie mit x positive ganze Zahlen sein müssten, aber wir haben festgestellt, dass eine ungefähre gerundete Lösung mit nur nicht-negativen x war ausreichend. Für eine Näherungslösung könnte ein einfacher Out-of-the-Box-Solver verwendet werden, um innerhalb von 30 Sekunden ein Ergebnis zu erhalten.

Abbildung 4: Beispiel einer Strategiematrix für Sequenzlänge 8 und Packungstiefe 3. Die Zeilen stehen für die zusammengepackten Sequenzen der Längen 1–8 und die Spalten stehen für alle möglichen Längenkombinationen in einer Packung ohne besondere Reihenfolge. Bild vom Autor.

 

Am Ende mussten wir einige Samples korrigieren, denen keine Strategie zugewiesen wurde, aber diese waren minimal. Wir haben auch einen Varianten-Solver entwickelt, der erzwingt, dass jede Sequenz gepackt wird, möglicherweise mit Padding, und eine Gewichtung hat, die vom Padding abhängt. Es dauerte viel länger und die Lösung war nicht viel besser.

Kürzeste-Pack-First-Histogramm-Packung

 
 
NNLSHP lieferte für uns einen ausreichenden Verpackungsansatz. Wir haben uns jedoch gefragt, ob wir theoretisch einen schnelleren online-fähigen Ansatz bekommen und die Beschränkung aufheben könnten, nur 3 Sequenzen zusammenzustellen.

Daher haben wir uns von bestehenden Packalgorithmen inspirieren lassen, uns aber weiterhin auf die Histogramme konzentriert.

Es gibt vier Zutaten für unseren ersten Algorithmus, Shortest-Pack-First Histogram-Packing (SPFHP):

1. Arbeiten Sie mit den Zählungen des Histogramms von den längsten Sequenzen bis zu den kürzesten
2. Wenn die aktuelle Sequenzlänge in kein Paket passt, starten Sie einen neuen Satz von Paketen
3. Wenn mehrere Anpassungen vorhanden sind, nehmen Sie das Paket, bei dem die Summe der Sequenzlängen am kürzesten ist, und ändern Sie die Anzahl entsprechend
4. Überprüfen Sie erneut, ob die verbleibenden Zählungen passen

Dieser Ansatz war am einfachsten zu implementieren und dauerte nur 0.02 Sekunden.

Eine Variante bestand darin, die größte Summe der Sequenzlänge anstelle der kürzesten und geteilten Anzahl zu verwenden, um perfektere Anpassungen zu erhalten. Insgesamt hat dies nicht viel an der Effizienz geändert, aber die Codekomplexität stark erhöht.

So funktioniert Shortest-Pack-First-Histogramm-Packing. Animation vom Autor.

 

Wikipedia, SQuAD 1.1, GLUE Verpackungsergebnisse

 
 
Tabelle 1, 2 und 3 zeigen die Packergebnisse unserer beiden vorgeschlagenen Algorithmen. Packtiefe beschreibt die maximale Anzahl gepackter Sequenzen. Packungstiefe 1 ist die grundlegende BERT-Implementierung. Die maximal vorkommende Packungstiefe, bei der keine Begrenzung eingestellt ist, wird mit einem zusätzlichen „max“ gekennzeichnet. Die Anzahl Packungen beschreibt die Länge des neuen gepackten Datensatzes. Effizienz ist der Prozentsatz der echten Token im gepackten Dataset. Die Verpackungsfaktor beschreibt die resultierende potenzielle Beschleunigung gegenüber Packungstiefe 1.

Wir hatten vier Hauptbeobachtungen:

1. Je schiefer eine Verteilung ist, desto höher sind die Vorteile der Verpackung.
2. Alle Datensätze profitieren vom Packen. Manche sogar um mehr als den Faktor 2.
3. SPFHP wird effizienter, wenn die Packtiefe nicht begrenzt ist.
4. Für eine maximale Anzahl von 3 gepackten Sequenzen ist NNLSHP umso effizienter (99.75 vs. 89.44), je komplexer NNLSHP ist.

Tabelle 1: Key Performance-Ergebnisse der vorgeschlagenen Packalgorithmen (SPFHP und NNLSHP) auf Wikipedia. Bild vom Autor.

 


Tabelle 2: Leistungsergebnisse der vorgeschlagenen Packalgorithmen für das SQUaD 1.1 BERT-Vortraining. Bild vom Autor.

 


Tabelle 3: Leistungsergebnisse der vorgeschlagenen Packalgorithmen für den GLUE-Datensatz. Es werden nur die Basislinie und die SPFHP-Packungsergebnisse ohne Begrenzung der Packungstiefe angezeigt. Bild vom Autor.

 

Anpassung der BERT-Verarbeitung

 
 
Interessant an der BERT-Architektur ist, dass die meisten Verarbeitungen auf Token-Ebene erfolgen, was bedeutet, dass sie unser Packen nicht beeinträchtigt. Es gibt nur vier Komponenten, die angepasst werden müssen: die Aufmerksamkeitsmaske, der MLM-Verlust, der NSP-Verlust und die Genauigkeit.

Der Schlüssel für alle vier Ansätze zum Umgang mit unterschiedlichen Anzahlen von Sequenzen war die Vektorisierung und die Verwendung einer maximalen Anzahl von Sequenzen, die verkettet werden können. Für Aufmerksamkeit hatten wir bereits eine Maske, um die Polsterung anzusprechen. Die Erweiterung auf mehrere Sequenzen war unkompliziert, wie im folgenden TensorFlow-Pseudocode zu sehen ist. Das Konzept ist, dass wir darauf geachtet haben, dass die Aufmerksamkeit auf die einzelnen Sequenzen beschränkt ist und nicht darüber hinausgehen kann.

Codebeispiel für Achtungsmaske.

 


Abbildung 5: Beispiel einer Null-Eins-Maske

 

Für die Verlustberechnung entpacken wir im Prinzip die Sequenzen und berechnen die einzelnen Verluste, um schließlich den Durchschnitt der Verluste über die Sequenzen (anstelle von Packs) zu erhalten.

Für den MLM-Verlust sieht der Code wie folgt aus:

Beispiel für einen Verlustberechnungscode.

 

Für den NSP-Verlust und die Genauigkeit gilt das gleiche Prinzip. In unseren öffentlichen Beispielen finden Sie den jeweiligen Code mit unserem hauseigenen PopART-Framework.

Wikipedia-Overhead- und Beschleunigungsschätzung

 
 
Bei unserer Modifikation von BERT hatten wir zwei Fragen:

1. Wie viel Overhead bringt es mit sich?
2. Wie stark hängt der Overhead von der maximalen Anzahl von Sequenzen ab, die in einem Pack zusammengestellt werden?

Da die Datenaufbereitung in BERT umständlich sein kann, haben wir eine Abkürzung verwendet und den Code für mehrere unterschiedliche Packtiefen kompiliert und die jeweiligen (gemessenen) Zyklen verglichen. Die Ergebnisse sind in Tabelle 4 dargestellt. Mit oben, bezeichnen wir die prozentuale Abnahme des Durchsatzes aufgrund von Änderungen am Modell, um das Packen zu ermöglichen (wie das Maskierungsschema für Aufmerksamkeit und die geänderte Verlustberechnung). Die realisierte Beschleunigung ist die Kombination der Beschleunigung durch das Packen (die Verpackungsfaktor) und die Abnahme des Durchsatzes aufgrund der oben.

Tabelle 4: Geschätzter Geschwindigkeitsvergleich der vorgeschlagenen Packalgorithmen (SPFHP und NNLSHP) auf Wikipedia. Bild vom Autor.

 

Dank der Vektorisierungstechnik ist der Overhead überraschend gering und es gibt keinen Nachteil, viele Sequenzen zusammenzupacken.

Hyperparameter-Anpassungen

 
 
Beim Verpacken verdoppeln wir die effektive Losgröße (im Durchschnitt). Das bedeutet, dass wir die Trainingshyperparameter anpassen müssen. Ein einfacher Trick besteht darin, die Anzahl der Gradientenakkumulationen zu halbieren, um die gleiche effektive durchschnittliche Batchgröße wie vor dem Training beizubehalten. Durch die Verwendung einer Benchmark-Einstellung mit vortrainierten Prüfpunkten können wir sehen, dass die Genauigkeitskurven perfekt übereinstimmen.

Abbildung 6: Vergleich der Lernkurven für gepackte und ungepackte Verarbeitung mit reduzierte Losgröße für den gepackten Ansatz. Bilder nach Autor.

 

Die Genauigkeit stimmt: Der MLM-Trainingsverlust kann zu Beginn etwas anders sein, holt aber schnell auf. Dieser anfängliche Unterschied könnte von geringfügigen Anpassungen der Aufmerksamkeitsschichten herrühren, die im vorherigen Training möglicherweise auf kurze Sequenzen ausgerichtet waren.

Um eine Verlangsamung zu vermeiden, hilft es manchmal, die ursprüngliche Batchgröße gleich zu halten und die Hyperparameter an die erhöhte effektive Batchgröße anzupassen (verdoppelt). Die wichtigsten zu berücksichtigenden Hyperparameter sind die Betaparameter und die Lernraten. Ein gängiger Ansatz besteht darin, die Batchgröße zu verdoppeln, was in unserem Fall die Leistung verringert. Mit Blick auf die Statistiken des LAMB-Optimierers konnten wir beweisen, dass das Anheben des Beta-Parameters mit dem Packfaktor dem Training mehrerer Batches nacheinander entspricht, um Impuls und Geschwindigkeit vergleichbar zu halten.

Abbildung 7: Vergleich der Lernkurven für gepackte und ungepackte Verarbeitung mit Heuristiken angewandt. Bilder nach Autor.

 

Unsere Experimente haben gezeigt, dass Beta hoch zwei eine gute Heuristik ist. In diesem Szenario wird nicht erwartet, dass die Kurven übereinstimmen, da eine Erhöhung der Batchgröße normalerweise die Konvergenzgeschwindigkeit im Sinne von Samples/Epochen verringert, bis eine Zielgenauigkeit erreicht ist.

Nun stellt sich die Frage, ob wir im praktischen Szenario wirklich die erwartete Beschleunigung erreichen?

Abbildung 8: Vergleich der Lernkurven für gepackte und ungepackte Verarbeitung im optimiertes Setup. Bilder nach Autor.

 

Ja, machen wir! Wir haben eine zusätzliche Beschleunigung gewonnen, weil wir die Datenübertragung komprimiert haben.

Zusammenfassung

 
 
Das Zusammenpacken von Sätzen kann Rechenaufwand und die Umwelt sparen. Diese Technik kann in jedem Framework implementiert werden, einschließlich PyTorch und TensorFlow. Wir haben eine deutliche 2-fache Beschleunigung erreicht und nebenbei den Stand der Technik bei Packalgorithmen erweitert.

Andere Anwendungen, auf die wir neugierig sind, sind Genomik und Proteinfaltung, bei denen ähnliche Datenverteilungen beobachtet werden können. Vision-Transformatoren könnten auch ein interessanter Bereich sein, um unterschiedlich große gepackte Bilder anzuwenden. Welche Anwendungen würden Ihrer Meinung nach gut funktionieren? Wir würden uns freuen, von Ihnen zu hören!

Lies das Dokument

Auf den Code auf GitHub zugreifen

Vielen Dank.

 
 
Danke an unsere Kollegen im Anwendungstechnik-Team von Graphcore, Sheng Fu und Mrinal Iyer, für ihre Beiträge zu dieser Arbeit und danke an Douglas Orr vom Graphcore-Forschungsteam für sein wertvolles Feedback.

Bibliographie

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

 
Dr. Mario Michael Krell ist Principal Machine Learning Lead bei Graphcore. Mario erforscht und entwickelt seit mehr als 12 Jahren Algorithmen für maschinelles Lernen und entwickelt Software für so unterschiedliche Branchen wie Robotik, Automobil, Telekommunikation und Gesundheitswesen. Bei Graphcore hat er zu unserem beeindruckenden MLPerf-Einreichungen und hat eine Leidenschaft, neuartige Nicht-Standard-Modelle wie die approximative Bayessche Berechnung für die statistische COVID-19-Datenanalyse zu beschleunigen.

Matej Kosec ist Spezialist für KI-Anwendungen bei Graphcore in Palo Alto. Zuvor arbeitete er als KI-Wissenschaftler für autonomes Fahren am NIO in San Jose und hat einen Master-Abschluss in Luft- und Raumfahrt der Stanford University.

Original. Mit Genehmigung erneut veröffentlicht.

Related:

• Erstellen eines Wissensgraphen für die Jobsuche mit BERT
• Wie man ein BERT-Modell von Grund auf trainiert
• BERT mit umarmendem Gesicht verstehen