Byte pair encoding

Le codage par paires d'octets (également connu sous le nom de BPE pour Byte pair encoding, ou codage de digrammes) est un algorithme, décrit pour la première fois en 1994 par Philip Gage, pour coder des chaînes de texte en chaînes plus petites en créant et en utilisant une table de correspondance^[1]. Une version légèrement modifiée de l'algorithme est utilisée dans les tokeniseurs des grands modèles de langage.

La version initiale de l’algorithme était axée sur la compression. Elle consistait à remplacer la paire d'octets de fréquence la plus élevée par un nouvel octet qui n’était pas contenu dans l’ensemble de données initial. Une table de correspondance était nécessaire pour reconstruire l'ensemble de données initial. La version modifiée génère des « jetons » ou tokens (unités de reconnaissance) qui correspondent à des quantités variables de texte source, allant de simples caractères (y compris des chiffres ou des signes de ponctuation) à des mots entiers (même des mots composés longs)^[2].

L'algorithme BPE fonctionne initialement en remplaçant de manière itérative les séquences de caractères contiguës les plus courantes dans un texte cible par des octets « d'espace réservé » inutilisés. L'itération prend fin lorsqu'il devient impossible de détecter une nouvelle séquence, laissant ainsi le texte cible efficacement compressé. La décompression peut être effectuée en inversant ce processus, en interrogeant les termes d'espace réservé connus par rapport à leur séquence désignée correspondante, à l'aide d'une table de recherche. Dans l’article original, cette table de recherche est codée et stockée avec le texte compressé.

aaabdaaabac

La séquence d'octets « aa » apparaît plus fréquemment et sera donc remplacée par un octet inutilisé dans les données, tel que « Z ». Cela donne lieu aux données suivantes et au tableau de remplacement :

ZabdZabac
Z=aa

Ensuite, le processus est répété avec la paire d'octets « ab », en la remplaçant par « Y » :

ZYdZYac
Y=ab
Z=aa

La seule paire d'octets littéraux restante n'apparaît qu'une seule fois, ce qui permet de mettre fin à l'encodage. Alternativement, le processus pourrait se poursuivre avec un encodage récursif par paires d'octets, en remplaçant par exemple « ZY » par « X ».

XdXac
X=ZY
Y=ab
Z=aa

Ces données ne peuvent plus être compressées davantage par BPE (Byte pair encoding), car il n'y a plus de paires d'octets apparaissant plus d'une fois.

Pour décompresser les données, il suffit d'effectuer les remplacements dans l'ordre inverse.

L'algorithme Byte Pair Encoding^[3],[4],[5] initial a été adapté pour répondre aux besoins de la modélisation du langage, en particulier pour les grands modèles basés sur des réseaux neuronaux. Contrairement à l'algorithme BPE original, cette version modifiée ne vise pas à maximiser la compression du texte, mais plutôt à encoder le texte brut en « jetons », qui sont des nombres naturels^[6].

Tous les jetons uniques trouvés dans un corpus sont répertoriés dans un vocabulaire de jetons, dont la taille, dans le cas de GPT-3.5 et GPT-4, est de 100256^[7].

L'algorithme de tokenisation modifié commence par traiter chaque caractère unique comme un n-gramme d'une longueur de 1 caractère (les jetons initiaux). Ensuite, il fusionne successivement la paire de jetons adjacents la plus fréquente en un nouveau n-gramme plus long, remplaçant toutes les instances de cette paire par le nouveau jeton. Cette opération est répétée jusqu'à ce qu'un vocabulaire de taille définie soit atteint. Il est important de noter que de nouveaux mots peuvent toujours être formés à partir des jetons du vocabulaire final et des caractères initiaux^[8].

Cette approche BPE modifiée a été adaptée au langage des signes au cours des dernières années^[9].

Supposons que nous codons l'exemple précédent de « aaabdaaabac », avec une taille de vocabulaire spécifiée de 6.

Nous commencerions par coder la séquence comme « 0, 0, 0, 1, 2, 0, 0, 0, 1, 0, 3 » en utilisant un vocabulaire initial où « a=0, b=1, d=2, c=3 ».

Ensuite, nous procéderions de la même manière que précédemment, obtenant ainsi « 4, 5, 2, 4, 5, 0, 3 » avec un vocabulaire mis à jour : « a=0, b=1, d=2, c=3, aa=4, ab=5 ».

Jusqu'à présent, le processus est essentiellement identique à ce qui a été décrit précédemment. Cependant, si nous avions spécifié une taille de vocabulaire de 5, le processus s'arrêterait au vocabulaire « a=0, b=1, d=2, c=3, aa=4 », de sorte que l'exemple serait encodé comme « 4, 0, 1, 2, 4, 0, 1, 0, 3 ».

En revanche, si nous avions spécifié une taille de vocabulaire de 8, l'exemple serait encodé comme suit « 7, 6, 0, 3 », avec un vocabulaire de « a=0, b=1, d=2, c=3, aa=4, ab=5, aaab=6, aaabd=7 ». Ce processus n'est pas optimal en termes de compression, mais le BPE modifié ne vise pas à compresser au maximum un ensemble de données. Il cherche plutôt à encoder efficacement le texte pour l'entraînement des modèles de langage^[10].

Dans l'exemple ci-dessus, le résultat du BPE est un vocabulaire qui peut être utilisé pour encoder tout texte écrit avec les lettres « abcd ». Cependant, il ne pourra pas encoder un texte contenant d'autres symboles, comme « no ». Même en attribuant une entrée dans le vocabulaire à chacune des 26 lettres de l'alphabet, il existe de nombreuses langues dans le monde utilisant divers systèmes d'écriture, ce qui rend inévitablement certains symboles non encodables par un tel vocabulaire.

Une solution consiste à remplacer tout symbole non codable par un symbole spécial nommé UNK (« unknown »).

Le byte-level BPE est une autre méthode. Elle consiste à convertir d'abord le texte en UTF-8 et à le traiter comme un flux d'octets. Cela garantit que tout texte encodé en UTF-8 peut être traité par le BPE. Cette technique a été utilisée dans des modèles similaires à BERT, tels que RoBERTa, BART et DeBERTa, ainsi que dans des modèles de type GPT comme GPT-2^{[11],[12],[13]}.

• Réparation
• Algorithme Sequitur

• Portail de l’informatique