Tokénisation <i> Byte-Pair Encoding </i>

Le Byte-Pair Encoding (BPE) a été initialement développé en tant qu’algorithme de compression de textes puis utilisé par OpenAI pour la tokenisation du pré-entraînement du modèle GPT. Il est utilisé par de nombreux transformers dont GPT, GPT-2, RoBERTa, BART et DeBERTa.

Algorithme d’entraînement

L’entraînement du BPE commence par le calcul de l’unique ensemble de mots utilisés dans le corpus (après les étapes de normalisation et de prétokénisation), puis la construction du vocabulaire en prenant tous les symboles utilisés pour écrire ces mots. A titre d’exemple, disons que notre corpus utilise ces cinq mots :

"hug", "pug", "pun", "bun", "hugs" # "câlin", "carlin", "jeu de mots", "brioche", "câlins"

Le vocabulaire de base sera alors ["b", "g", "h", "n", "p", "s", "u"]. Dans le monde réel, le vocabulaire de base contient au moins tous les caractères ASCII et probablement aussi quelques caractères Unicode. Si un exemple que vous tokenisez utilise un caractère qui n’est pas dans le corpus d’entraînement, ce caractère est converti en token inconnu. C’est l’une des raisons pour lesquelles de nombreux modèles de NLP sont par exemple très mauvais dans l’analyse de contenus contenant des emojis.

Après avoir obtenu ce vocabulaire de base, nous ajoutons de nouveaux tokens jusqu’à ce que la taille souhaitée du vocabulaire soit atteinte en apprenant les fusions qui sont des règles permettant de fusionner deux éléments du vocabulaire existant pour en créer un nouveau. Ainsi, au début, ces fusions créeront des tokens de deux caractères, puis au fur et à mesure de l’entraînement, des sous-mots plus longs.

À chaque étape de l’entraînement du tokenizer, l’algorithme BPE recherche la paire la plus fréquente de tokens existants (par « paire », nous entendons ici deux tokens consécutifs dans un mot). Cette paire la plus fréquente est celle qui sera fusionnée. Nous rinçons et répétons pour l’étape suivante.

Pour revenir à notre exemple précédent, supposons que les mots ont les fréquences suivantes :

("hug", 10), ("pug", 5), ("pun", 12), ("bun", 4), ("hugs", 5)

ce qui veut dire que "hug" était présent 10 fois dans le corpus, "pug" 5 fois, "pun" 12 fois, "bun" 4 fois et "hugs"” 5 fois. Nous commençons l’entraînement en divisant chaque mot en caractères (ceux qui forment notre vocabulaire initial) afin de voir chaque mot comme une liste de tokens :

("h" "u" "g", 10), ("p" "u" "g", 5), ("p" "u" "n", 12), ("b" "u" "n", 4), ("h" "u" "g" "s", 5)

Ensuite, nous regardons les paires. La paire ("h", "u") est présente dans les mots "hug" et "hugs", donc 15 fois au total dans le corpus. Ce n’est cependant pas la paire la plus fréquente. Cet honneur revient à ("u", "g") qui est présent dans "hug", "pug", et "hugs", pour un total de 20 fois dans le vocabulaire.

Ainsi, la première règle de fusion apprise par le tokenizer est ("u", "g") -> "ug", ce qui signifie que "ug" est ajouté au vocabulaire et que la paire doit être fusionnée dans tous les mots du corpus. A la fin de cette étape, le vocabulaire et le corpus ressemblent à ceci :

Vocabulary: ["b", "g", "h", "n", "p", "s", "u", "ug"]
Corpus: ("h" "ug", 10), ("p" "ug", 5), ("p" "u" "n", 12), ("b" "u" "n", 4), ("h" "ug" "s", 5)

Nous avons maintenant quelques paires qui aboutissent à un token de plus de deux caractères. Par exemple la paire ("h", "ug") présente 15 fois dans le corpus. La paire la plus fréquente à ce stade est ("u", "n"), présente 16 fois dans le corpus, donc la deuxième règle de fusion apprise est ("u", "n") -> "un". En ajoutant cela au vocabulaire et en fusionnant toutes les occurrences existantes, nous obtenons :

Vocabulary: ["b", "g", "h", "n", "p", "s", "u", "ug", "un"]
Corpus: ("h" "ug", 10), ("p" "ug", 5), ("p" "un", 12), ("b" "un", 4), ("h" "ug" "s", 5)

Maintenant la paire la plus fréquente est ("h", "ug") donc nous apprenons la règle de fusion ("h", "ug") -> "hug". Cela nous donne donc notre premier token de trois lettres. Après la fusion, le corpus ressemble à ceci :

Vocabulary: ["b", "g", "h", "n", "p", "s", "u", "ug", "un", "hug"]
Corpus: ("hug", 10), ("p" "ug", 5), ("p" "un", 12), ("b" "un", 4), ("hug" "s", 5)

Et nous continuons ainsi jusqu’à ce que nous atteignions la taille de vocabulaire souhaitée.

Algorithme de tokenisation

La tokenisation suit de près le processus d’entraînement, dans le sens où les nouvelles entrées sont tokenisées en appliquant les étapes suivantes :

1. Normalisation
2. Prétokénisation
3. Découpage des mots en caractères individuels
4. Application des règles de fusion apprises dans l’ordre sur ces divisions.

Prenons l’exemple que nous avons utilisé pendant l’entraînement, avec les trois règles de fusion apprises :

("u", "g") -> "ug"
("u", "n") -> "un"
("h", "ug") -> "hug"

Le mot « bug » sera traduit par « [“b”, “ug”] ». Par contre, le mot « mug » (tasse en français) sera traduit par « [”[UNK]”, “ug”] » puisque la lettre « m » ne fait pas partie du vocabulaire de base. De la même façon, le mot « thug » (voyou en français) sera tokenisé en « [”[UNK]”, “hug”] » car la lettre « t » n’est pas dans le vocabulaire de base et l’application des règles de fusion résulte d’abord en la fusion de « u » et « g » et ensuite en la fusion de « hu » et « g ».

Implémentation du BPE

Voyons maintenant une implémentation de l’algorithme BPE. Il ne s’agira pas d’une version optimisée que vous pourrez utiliser sur un grand corpus. Nous voulons simplement vous montrer le code afin que vous puissiez comprendre un peu mieux l’algorithme.

Tout d’abord, nous avons besoin d’un corpus, alors créons un corpus simple avec quelques phrases :

corpus = [
    "This is the Hugging Face Course.",
    # C'est le cours d'Hugging Face.
    "This chapter is about tokenization.",
    # Ce chapitre traite de la tokenisation.
    "This section shows several tokenizer algorithms.",
    # Cette section présente plusieurs algorithmes de tokenizer.
    "Hopefully, you will be able to understand how they are trained and generate tokens.",
    # Avec un peu de chance, vous serez en mesure de comprendre comment ils sont entraînés et génèrent des tokens.
]

Ensuite, nous devons prétokeniser ce corpus en mots. Puisque nous répliquons un tokenizer BPE (comme celui du GPT-2), nous utiliserons le tokenizer gpt2 pour la prétokénisation :

from transformers import AutoTokenizer

tokenizer = AutoTokenizer.from_pretrained("gpt2")

Ensuite, nous calculons les fréquences de chaque mot dans le corpus comme nous le faisons pour la prétokénisation :

from collections import defaultdict

word_freqs = defaultdict(int)

for text in corpus:
    words_with_offsets = tokenizer.backend_tokenizer.pre_tokenizer.pre_tokenize_str(text)
    new_words = [word for word, offset in words_with_offsets]
    for word in new_words:
        word_freqs[word] += 1

print(word_freqs)

defaultdict(int, {'This': 3, 'Ġis': 2, 'Ġthe': 1, 'ĠHugging': 1, 'ĠFace': 1, 'ĠCourse': 1, '.': 4, 'Ġchapter': 1,
    'Ġabout': 1, 'Ġtokenization': 1, 'Ġsection': 1, 'Ġshows': 1, 'Ġseveral': 1, 'Ġtokenizer': 1, 'Ġalgorithms': 1,
    'Hopefully': 1, ',': 1, 'Ġyou': 1, 'Ġwill': 1, 'Ġbe': 1, 'Ġable': 1, 'Ġto': 1, 'Ġunderstand': 1, 'Ġhow': 1,
    'Ġthey': 1, 'Ġare': 1, 'Ġtrained': 1, 'Ġand': 1, 'Ġgenerate': 1, 'Ġtokens': 1})

L’étape suivante consiste à calculer le vocabulaire de base, formé par tous les caractères utilisés dans le corpus :

alphabet = []

for word in word_freqs.keys():
    for letter in word:
        if letter not in alphabet:
            alphabet.append(letter)
alphabet.sort()

print(alphabet)

[ ',', '.', 'C', 'F', 'H', 'T', 'a', 'b', 'c', 'd', 'e', 'f', 'g', 'h', 'i', 'k', 'l', 'm', 'n', 'o', 'p', 'r', 's',
  't', 'u', 'v', 'w', 'y', 'z', 'Ġ']

Nous ajoutons également les tokens spéciaux utilisés par le modèle au début de ce vocabulaire. Dans le cas du GPT-2, le seul token spécial est "<|endoftext|>" :

vocab = ["<|endoftext|>"] + alphabet.copy()

Nous devons maintenant diviser chaque mot en caractères individuels pour pouvoir commencer l’entraînement :

splits = {word: [c for c in word] for word in word_freqs.keys()}

Maintenant que nous sommes prêts pour l’entraînement, écrivons une fonction qui calcule la fréquence de chaque paire. Nous devrons l’utiliser à chaque étape de l’entraînement :

def compute_pair_freqs(splits):
    pair_freqs = defaultdict(int)
    for word, freq in word_freqs.items():
        split = splits[word]
        if len(split) == 1:
            continue
        for i in range(len(split) - 1):
            pair = (split[i], split[i + 1])
            pair_freqs[pair] += freq
    return pair_freqs

Jetons un coup d’œil à une partie de ce dictionnaire après les premières divisions :

pair_freqs = compute_pair_freqs(splits)

for i, key in enumerate(pair_freqs.keys()):
    print(f"{key}: {pair_freqs[key]}")
    if i >= 5:
        break

('T', 'h'): 3
('h', 'i'): 3
('i', 's'): 5
('Ġ', 'i'): 2
('Ġ', 't'): 7
('t', 'h'): 3

Maintenant, trouver la paire la plus fréquente ne demande qu’une rapide boucle :

best_pair = ""
max_freq = None

for pair, freq in pair_freqs.items():
    if max_freq is None or max_freq < freq:
        best_pair = pair
        max_freq = freq

print(best_pair, max_freq)

('Ġ', 't') 7

Donc la première fusion à apprendre est ('Ġ', 't') -> 'Ġt', et on ajoute 'Ġt' au vocabulaire :

merges = {("Ġ", "t"): "Ġt"}
vocab.append("Ġt")

Pour continuer, nous devons appliquer cette fusion dans notre dictionnaire splits. Écrivons une autre fonction pour cela :

def merge_pair(a, b, splits):
    for word in word_freqs:
        split = splits[word]
        if len(split) == 1:
            continue

        i = 0
        while i < len(split) - 1:
            if split[i] == a and split[i + 1] == b:
                split = split[:i] + [a + b] + split[i + 2 :]
            else:
                i += 1
        splits[word] = split
    return splits

Et nous pouvons regarder le résultat de la première fusion :

splits = merge_pair("Ġ", "t", splits)
print(splits["Ġtrained"])

['Ġt', 'r', 'a', 'i', 'n', 'e', 'd']

Maintenant, nous avons tout ce dont nous avons besoin pour boucler jusqu’à ce que nous ayons appris toutes les fusions que nous voulons. Visons une taille de vocabulaire de 50 :

vocab_size = 50

while len(vocab) < vocab_size:
    pair_freqs = compute_pair_freqs(splits)
    best_pair = ""
    max_freq = None
    for pair, freq in pair_freqs.items():
        if max_freq is None or max_freq < freq:
            best_pair = pair
            max_freq = freq
    splits = merge_pair(*best_pair, splits)
    merges[best_pair] = best_pair[0] + best_pair[1]
    vocab.append(best_pair[0] + best_pair[1])

En conséquence, nous avons appris 19 règles de fusion (le vocabulaire initial avait une taille de 31 : 30 caractères dans l’alphabet plus le token spécial) :

print(merges)

{('Ġ', 't'): 'Ġt', ('i', 's'): 'is', ('e', 'r'): 'er', ('Ġ', 'a'): 'Ġa', ('Ġt', 'o'): 'Ġto', ('e', 'n'): 'en',
 ('T', 'h'): 'Th', ('Th', 'is'): 'This', ('o', 'u'): 'ou', ('s', 'e'): 'se', ('Ġto', 'k'): 'Ġtok',
 ('Ġtok', 'en'): 'Ġtoken', ('n', 'd'): 'nd', ('Ġ', 'is'): 'Ġis', ('Ġt', 'h'): 'Ġth', ('Ġth', 'e'): 'Ġthe',
 ('i', 'n'): 'in', ('Ġa', 'b'): 'Ġab', ('Ġtoken', 'i'): 'Ġtokeni'}

Et le vocabulaire est composé du token spécial, de l’alphabet initial, et de tous les résultats des fusions :

print(vocab)

['<|endoftext|>', ',', '.', 'C', 'F', 'H', 'T', 'a', 'b', 'c', 'd', 'e', 'f', 'g', 'h', 'i', 'k', 'l', 'm', 'n', 'o',
 'p', 'r', 's', 't', 'u', 'v', 'w', 'y', 'z', 'Ġ', 'Ġt', 'is', 'er', 'Ġa', 'Ġto', 'en', 'Th', 'This', 'ou', 'se',
 'Ġtok', 'Ġtoken', 'nd', 'Ġis', 'Ġth', 'Ġthe', 'in', 'Ġab', 'Ġtokeni']

Pour tokeniser un nouveau texte, on le prétokenise, on le divise, puis on applique toutes les règles de fusion apprises :

def tokenize(text):
    pre_tokenize_result = tokenizer._tokenizer.pre_tokenizer.pre_tokenize_str(text)
    pre_tokenized_text = [word for word, offset in pre_tokenize_result]
    splits = [[l for l in word] for word in pre_tokenized_text]
    for pair, merge in merges.items():
        for idx, split in enumerate(splits):
            i = 0
            while i < len(split) - 1:
                if split[i] == pair[0] and split[i + 1] == pair[1]:
                    split = split[:i] + [merge] + split[i + 2 :]
                else:
                    i += 1
            splits[idx] = split

    return sum(splits, [])

Nous pouvons essayer cela sur n’importe quel texte composé de caractères de l’alphabet :

tokenize("This is not a token.")

['This', 'Ġis', 'Ġ', 'n', 'o', 't', 'Ġa', 'Ġtoken', '.']

C’est tout pour l’algorithme BPE ! Nous allons nous intéresser à WordPiece dans la suite.