Byte pair encoding
Cet article est orphelin. Moins de trois articles lui sont liés ().
[[Byte pair encoding]] dans les articles relatifs au sujet.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èle de language.
La version initial 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 » (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].
Algorithme d'origine
[modifier | modifier le code]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é.
Exemple
[modifier | modifier le code]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.
Algorithme modifié
[modifier | modifier le code]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].
Byte-level BPE
[modifier | modifier le code]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].
Voir aussi
[modifier | modifier le code]- ↑ « Byte Pair Encoding » [archive du ]
- ↑ « google/sentencepiece », Google, (consulté le )
- ↑ Gage, « A New Algorithm for Data Compression », The C User Journal, (lire en ligne)
- ↑ « A New Algorithm for Data Compression », Dr. Dobb's Journal, (consulté le )
- ↑ Ian H. Witten, Alistair Moffat et Timothy C. Bell, Managing Gigabytes, New York, Van Nostrand Reinhold, (ISBN 978-0-442-01863-4)
- ↑ (en) « Counting Ability of Large Language Models and Impact of Tokenization », arXiv (consulté le )
- ↑ (en) « What is BBPE - Tokenizer behind LLMs », Kaggle (consulté le )
- ↑ Gerhard Paaß et Sven Giesselbach, Foundation Models for Natural Language Processing, coll. « Artificial Intelligence: Foundations, Theory, and Algorithms », , 19–78 p. (ISBN 9783031231902, DOI 10.1007/978-3-031-23190-2_2), « Pre-trained Language Models »
- ↑ Taro Miyazaki, Sihan Tan, Tsubasa Uchida, Hiroyuki Kaneko, « Sign Language Translation with Gloss Pair Encoding », Proceedings of the 11th Workshop on the Representation and Processing of Sign Languages, (lire en ligne)
- ↑ (en) Suhas Pai, Designing Large Language Model Applications: A Holistic Approach to LLMs, O'Reilly Media, (ISBN 978-1-0981-5046-4)
- ↑ « Byte-Pair Encoding tokenization », Hugging Face NLP Course (consulté le )
- ↑ (en) Savaş Yıldırım et Meysam Asgari Chenaghlu, Mastering Transformers: Build state-of-the-art models from scratch with advanced natural language processing techniques, Packt Publishing Ltd, (ISBN 978-1-80107-889-4)
- ↑ (en) Wang et Cho, « Neural Machine Translation with Byte-Level Subwords », AAAI Conference on Artificial Intelligence, vol. 34, no 05, , 9154–9160 (ISSN 2374-3468, DOI 10.1609/aaai.v34i05.6451, arXiv 1909.03341)
