Byte Pair Encoding

Byte Pair Encoding^[1][2] (auch BPE, deutsch Byte-Paar-Kodierung)^[3] ist ein 1994 erstmals von Philip Gage beschriebener Algorithmus zur Kodierung von Textsequenzen in kürzere Segmente durch die Erstellung und Nutzung einer Übersetzungstabelle.^[4] Eine leicht angepasste Version des Algorithmus wird in der Tokenisierung von Large Language Models (LLMs) verwendet.

Der ursprüngliche Algorithmus konzentrierte sich vor allem auf die Komprimierung von Text. Dabei wird das Byte-Paar, welches am häufigsten vorkommt, mit einem neuen Byte ersetzt, welches in den ursprünglichen Daten nicht enthalten war. Eine Tabelle mit den entsprechenden Übersetzungen ist hierbei notwendig, um den ursprünglichen Datensatz neu zu erstellen. Die modifizierte Version im Kontext von LLMs erstellt hingegen sogenannte „Tokens“ (Erkennungseinheiten), die mit unterschiedlichen Mengen des Ausgangstextes übereinstimmen. Diese gebildeten Tokens reichen von einzelnen Zeichen (einschließlich einzelner Ziffern oder Satzzeichen) bis hin zu ganzen Wörtern (einschließlich langen zusammengesetzten Wörtern).^[5]

Der ursprüngliche BPE-Algorithmus ersetzt iterativ die häufigsten zusammenhängenden Zeichensequenzen in einem Zieltext durch unbenutzte "Platzhalter"-Bytes. Die Iteration endet, wenn keine Sequenzen mehr gefunden werden können, womit der Zieltext erfolgreich komprimiert wurde. Indem dieser Prozess umgekehrt wird, kann der Text wiederum dekomprimiert werden. Dazu wird eine Nachschlagetabelle benötigt anhand derer die "Platzhalter"-Bytes mit den entsprechenden Sequenzen abgeglichen werden können. Diese Nachschlagetabelle wird zusammen mit dem komprimierten Text gespeichert.

Angenommen, die zu kodierenden Daten sind

aaabdaaabac

Das Byte-Paar „aa“ kommt am häufigsten vor und wird deshalb mit einem Byte ersetzt, welches nicht in den Daten zu finden ist, z. B. „Z“. Damit sehen ergibt sich eine neue Version der Daten sowie eine Ersetzungstabelle:

ZabdZabac
Z=aa

Nun wird der Prozess für das Byte-Paar "ab" wiederholt, welches mit „Y“ ersetzt wird:

ZYdZYac
Y=ab
Z=aa

Das einzig verbleibende Byte-Paar „ac“ kommt nur einmal vor und die Kodierung könnte hiermit enden. Alternativ kann der Prozess mit einer rekursiven Byte-Paar-Kodierung fortgesetzt werden, wobei „ZY“ durch „X“ ersetzt wird:

XdXac
X=ZY
Y=ab
Z=aa

Die Daten können jetzt nicht mehr weiter komprimiert werden, da es keine Byte-Paare mehr gibt, die mehr als ein Mal vorkommen.

Um die Daten zu dekomprimieren, muss dieser Prozess nun einfach umgekehrt werden, wobei die Byte-Paare umgekehrter Reihenfolge ersetzt werden.

Der ursprüngliche BPE-Algorithmus wurde an die Modellierung von Sprache angepasst, insbesondere an Sprachmodelle, die auf neuronalen Netzwerken basieren. Im Gegensatz zu dem ursprünglichen Algorithmus zielt die modifizierte Version allerdings nicht auf die maximale Komprimierung des Textes ab. Stattdessen soll der Text in Tokens kodiert werden, die natürliche Zahlen sind. Alle Tokens, die auf diese Weise in einem Korpus gefunden werden, werden in einem Token-Vokabular aufgelistet. Dieses beträgt im Falle von GPT-3.5 und GPT-4 zum Beispiel eine Größe von 100256 Tokens.

Der modifizierte Algorithmus zur Tokenisierung erfasst die Menge der eindeutigen Schriftzeichen zunächst als Monogramme (1-Zeichen-lange N-Gramme). Dann wird nach und nach das häufigste Paar benachbarter Tokens zu einem neuen, längeren N-Gramm zusammengefügt und alle Instanzen dieses Paares werden durch neue Tokens ersetzt. Dieser Prozess wird so lange wiederholt, bis ein Vokabular einer zuvor festgelegten Größe erreicht wird. Neue Wörter können immer aus den Tokens des endgültigen Vokabulars und den Zeichen des Originaltextes gebildet werden.^[6]

Dieser modifizierte BPE-Ansatz wurde in den letzten Jahren von der gesprochenen Sprache auf die Gebärdensprache ausgeweitet.^[7]

Angenommen, wir kodieren das vorige Beispiel „aaabdaaabac“ mit einer festgelegten Vokabulargröße von 6. Hierzu würden wir die Sequenz zunächst als „0, 0, 0, 1, 2, 0, 0, 0, 1, 0, 3“ mit einem Vokabular von „a=0, b=1, d=2, c=3“ kodieren. Der nächste Schritt würde wie zuvor häufige Byte-Paare für eine effizientere Kodierung nutzen, womit wir eine neue Sequenz von „4, 5, 2, 4, 5, 0, 3“ mit einem Vokabular von „a=0, b=1, d=2, c=3, aa=4, ab=5“ erhalten.

Bis jetzt ist der Vorgang im Wesentlichen derselbe wie zuvor. Hätten wir jedoch nur eine Vokabulargröße von 5 festgelegt, dann würde der Prozess mit einem Vokabular von „a=0, b=1, d=2, c=3, aa=4“ enden, sodass unsere Sequenz als „4, 0, 1, 2, 4, 0, 1, 0, 3“ kodiert wäre. Hätten wir dagegen eine Vokabulargröße von 8 festgelegt, würde die Sequenz als „7, 6, 0, 3“ mit einem Vokabular von „a=0, b=1, d=2, c=3, aa=4, ab=5, aaab=6, aaabd=7“ kodiert werden. Das ist nicht maximal effizient, jedoch zielt der modifizierte BPE-Algorithmus auch nicht darauf ab, eine Sequenz maximal zu komprimieren. Vielmehr sollen Sprachdaten effizient für das Trainieren von Sprachmodellen kodiert werden.

Im obigen Beispiel ist das Ergebnis des BPE-Algorithmus ein Vokabular, mit dem jeder Text kodiert werden kann, der mit den Buchstaben „abcd“ geschrieben ist. Es ist nicht in der Lage, Text zu kodieren, der andere Symbole enthält, wie z. B. „nein“. Selbst wenn es zu jedem Buchstaben des Alphabets einen Eintrag im Vokabular gäbe, würden unweigerlich einige Schriftzeichen nicht kodierbar sein, da viele Sprachen viele verschiedene Schriften verwenden.

Eine Lösung besteht darin, jedes nicht kodierbare Symbol durch ein spezielles Symbol mit der Bezeichnung UNK (englisch unknown, deutsch unbekannt) zu ersetzen.

Das Byte-Level BPE ist ein alternativer Ansatz. Hierbei wird der Text zunächst in UTF-8 konvertiert und dann als Strom von Bytes behandelt. Durch dieses Vorgehen wird sichergestellt, dass jeder in UTF-8 kodierte Text von dem BPE kodiert werden kann. Dieser Ansatz wird in vielen BERT-ähnlichen Modellen wie z. B. RoBERTa, BART, and DeBERTa, sowie GPT-ähnlichen Modellen wie GPT-2, verwendet.^[8]

1. ↑ Philip Gage: A New Algorithm for Data Compression. In: The C User Journal. 1994 (englisch, pennelynn.com). 
2. ↑ A New Algorithm for Data Compression. In: Dr. Dobb's Journal. 1. Februar 1994, abgerufen am 10. August 2020 (englisch). 
3. ↑ Ian H. Witten: Managing Gigabytes : Compressing and Indexing Documents and Images. Springer US, Berlin 1994, ISBN 978-0-442-01863-4. 
4. ↑ Byte Pair Encoding. Archiviert vom Original am 26. März 2016; abgerufen im 1. Januar 1 (englisch). 
5. ↑ google/sentencepiece. Google, 2. März 2021, abgerufen am 2. März 2021 (englisch). 
6. ↑ Foundation Models for Natural Language Processing : Pre-trained Language Models Integrating Media. Springer International Publishing, Cham 2023, ISBN 978-3-03123190-2, doi:10.1007/978-3-031-23190-2_2. 
7. ↑ Taro Miyazaki, Sihan Tan, Tsubasa Uchida, Hiroyuki Kaneko: Sign Language Translation with Gloss Pair Encoding. In: Proceedings of the 11th Workshop on the Representation and Processing of Sign Languages. 25. Mai 2024 (englisch, aclanthology.org [PDF]). 
8. ↑ Byte-Pair Encoding tokenization - Hugging Face NLP Course. In: huggingface.co. Abgerufen am 27. Januar 2025 (englisch).