Bytepaar-Kodierung

In der Informatik ist die Byte-Pair-Codierung ( BPE ) ^{[ 1 ] [ 2 ]} oder Digrammcodierung [ ^{3 ]} ein Algorithmus , ^der 1994 von Philip Gage erstmals beschrieben wurde, um Textzeichenketten mithilfe einer Übersetzungstabelle in kleinere Zeichenketten zu kodieren. ^{[ 4 ]} Eine leicht modifizierte Version des Algorithmus wird in Tokenisierern großer Sprachmodelle verwendet.

Die ursprüngliche Version des Algorithmus konzentrierte sich auf die Komprimierung. Dabei wurde das häufigste Bytepaar durch ein neues Byte ersetzt , das nicht im ursprünglichen Datensatz enthalten war. Um den ursprünglichen Datensatz wiederherzustellen, war eine Nachschlagetabelle der Ersetzungen erforderlich. Die modifizierte Version erzeugt „Tokens“ (Erkennungseinheiten), die unterschiedlich lange Abschnitte des Quelltextes abdecken, von einzelnen Zeichen (einschließlich einzelner Ziffern oder Satzzeichen) bis hin zu ganzen Wörtern (auch langen zusammengesetzten Wörtern). ^{[ 5 ] [ 6 ] [ 7 ]}

Der ursprüngliche BPE-Algorithmus ersetzt iterativ die häufigsten zusammenhängenden Zeichenfolgen eines Zieltextes durch ungenutzte Platzhalterbytes. Die Iteration endet, sobald keine passenden Zeichenfolgen mehr gefunden werden, wodurch der Zieltext effektiv komprimiert wird. Die Dekomprimierung erfolgt durch Umkehrung dieses Prozesses: Mithilfe einer Nachschlagetabelle werden bekannte Platzhalterbegriffe mit den entsprechenden Zeichenfolgen abgeglichen. In der Originalveröffentlichung wird diese Nachschlagetabelle zusammen mit dem komprimierten Text kodiert und gespeichert.

Angenommen, die zu kodierenden Daten lauten: ^{[ 8 ]}

aaabdaaabac 

Das Bytepaar „aa“ kommt am häufigsten vor und wird daher durch ein Byte ersetzt, das in den Daten nicht verwendet wird, beispielsweise „Z“. Es ergibt sich folgende Daten- und Ersetzungstabelle:

ZabdZabac Z=aa 

Dann wird der Vorgang mit dem Bytepaar "ab" wiederholt, wobei dieses durch "Y" ersetzt wird:

ZYdZYac Y=ab Z=aa 

Das letzte verbleibende Bytepaar kommt nur einmal vor, und die Kodierung könnte hier beendet werden. Alternativ könnte der Prozess mit rekursiver Bytepaarkodierung fortgesetzt werden, wobei "ZY" durch "X" ersetzt wird.

XdXac X=ZY Y=ab Z=aa 

Diese Daten können durch Bytepaar-Codierung nicht weiter komprimiert werden, da es keine Bytepaare gibt, die mehr als einmal vorkommen.

Um die Daten zu dekomprimieren, führen Sie die Ersetzungen einfach in umgekehrter Reihenfolge durch.

Der ursprüngliche BPE-Algorithmus wurde für die Sprachmodellierung , insbesondere für große, auf neuronalen Netzen basierende Sprachmodelle, modifiziert. Im Vergleich zum ursprünglichen BPE zielt der modifizierte BPE nicht auf maximale Textkomprimierung ab, sondern auf die Kodierung von Klartext in „Tokens“, die natürlichen Zahlen entsprechen. ^{[ 9 ]} Alle in einem Korpus gefundenen eindeutigen Tokens werden in einem Token-Vokabular aufgelistet. Dieses kann je nach Anwendungsfall auch weitere spezielle Tokens enthalten. Die Größe des Token-Vokabulars beträgt bei GPT-3.5 und GPT-4 100.258 (100.000 Tokens aus dem BPE-Algorithmus und 258 zusätzliche spezielle Tokens). ^{[ 10 ]}

Der modifizierte Tokenisierungsalgorithmus behandelt die Menge der eindeutigen Zeichen zunächst als einstellige n-Gramme (die initialen Token). Anschließend wird sukzessive das häufigste Paar benachbarter Token zu einem neuen, längeren n-Gramm zusammengefasst und alle Vorkommen dieses Paares durch dieses neue Token ersetzt. Dieser Vorgang wird wiederholt, bis ein Vokabular der vorgegebenen Größe erreicht ist. Es ist zu beachten, dass sich aus den Token des finalen Vokabulars und den Zeichen der initialen Menge stets neue Wörter bilden lassen. ^{[ 11 ]}

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

Angenommen, wir kodieren das vorherige Beispiel „aaabdaaabac“ mit einer festgelegten Vokabulargröße von 6, dann würde es 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“ kodiert. Anschließend würde der Vorgang wie zuvor fortgesetzt, und wir erhielten „4, 5, 2, 4, 5, 0, 3“ mit einem Vokabular von „a=0, b=1, d=2, c=3, aa=4, ab=5“.

Bislang ist dies im Wesentlichen unverändert. Hätten wir jedoch nur eine Vokabulargröße von 5 festgelegt, würde der Prozess bei dem Vokabular „a=0, b=1, d=2, c=3, aa=4“ stoppen, sodass das Beispiel als „4, 0, 1, 2, 4, 0, 1, 0, 3“ kodiert würde. Hätten wir hingegen eine Vokabulargröße von 8 festgelegt, würde es als „7, 6, 0, 3“ kodiert, mit dem Vokabular „a=0, b=1, d=2, c=3, aa=4, ab=5, aaab=6, aaabd=7“. Dies ist keine maximale Komprimierung, da die modifizierte BPE nicht auf maximale Komprimierung abzielt. Stattdessen strebt sie eine Kodierung an, die für das Training von Sprachmodellen effizient und praktikabel ist. ^{[ 13 ]}

Im obigen Beispiel ist die Ausgabe des BPE ein Vokabular, mit dem sich jeder Text kodieren lässt, der aus den Buchstaben „abcd“ besteht. Texte mit anderen Symbolen, wie beispielsweise „no“, können damit nicht kodiert werden. Selbst wenn man jedem der 26 Buchstaben einen Eintrag im Vokabular zuweist, bleiben aufgrund der vielen Sprachen und Schriftsysteme weltweit zwangsläufig einige Symbole unkodierbar.

Eine Lösung besteht darin, jedes nicht kodierbare Symbol durch ein spezielles Symbol namens UNK ("unbekannt") zu ersetzen.

Die Byte-Level-BPE ist ein weiterer Ansatz. Sie konvertiert den Text zunächst in UTF-8 und behandelt ihn dann als Byte-Stream. Dadurch wird sichergestellt, dass jeder in UTF-8 kodierte Text auch von der BPE kodiert werden kann. Dieses Verfahren wurde in BERT -ähnlichen Modellen wie RoBERTa, BART und DeBERTa sowie in GPT- ähnlichen Modellen wie GPT-2 verwendet . ^{[ 14 ] [ 15 ] [ 16 ]}

• Reparieren
• Sequitur-Algorithmus