#
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.

> 💡 Cette section couvre le BPE en profondeur, allant jusqu’à montrer une implémentation complète. Vous pouvez passer directement à la fin si vous souhaitez simplement avoir un aperçu général de l’algorithme de tokenisation.

##
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.

> Les tokenizers du GPT-2 et de RoBERTa (qui sont assez similaires) ont une façon intelligente de gérer ce problème : ils ne considèrent pas les mots comme étant écrits avec des caractères Unicode mais avec des octets. De cette façon, le vocabulaire de base a une petite taille (256) et tous les caractères auxquels vous pouvez penser seront inclus dedans et ne finiront pas par être convertis en un token inconnu. Cette astuce est appelée byte-level BPE.

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.

> ✏️ A votre tour ! A votre avis, quelle sera la prochaine règle de fusion ?

##
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 ».

> ✏️ A votre tour ! Comment pensez-vous que le mot « unhug » (détacher en français) sera tokenisé ?

##
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']

> 💡 Utiliser `train_new_from_iterator()` sur le même corpus ne donnera pas exactement le même vocabulaire. C’est parce que lorsqu’il y a un choix de la paire la plus fréquente, nous avons sélectionné la première rencontrée, alors que la bibliothèque 🤗 Tokenizers sélectionne la première en fonction de ses identifiants internes.

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', '.']

> ⚠️ Notre implémentation lancera une erreur s’il y a un caractère inconnu puisque nous n’avons rien fait pour les gérer. GPT-2 n’a pas réellement de token inconnu (il est impossible d’obtenir un caractère inconnu en utilisant le BPE au niveau de l’octet) mais cela pourrait arriver ici car nous n’avons pas inclus tous les octets possibles dans le vocabulaire initial. Cet aspect du BPE dépasse le cadre de cette section, nous avons donc laissé ces détails de côté.

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

Update on GitHub