Tokenisation <i> Unigram </i>

L’algorithme Unigram est souvent utilisé dans SentencePiece, qui est l’algorithme de tokenization utilisé par des modèles comme ALBERT, T5, mBART, Big Bird et XLNet.

Algorithme d’entraînement

Comparé au BPE et WordPiece, Unigram fonctionne dans l’autre sens : il part d’un grand vocabulaire et enlève des tokens jusqu’à atteindre la taille de vocabulaire désirée. Il existe plusieurs options pour construire ce vocabulaire de base. Nous pouvons par exemple prendre les sous-chaînes les plus courantes dans les mots prétokénisés ou appliquer le BPE sur le corpus initial avec une grande taille de vocabulaire.

À chaque étape de l’entraînement, l’algorithme Unigram calcule une perte sur le corpus compte tenu du vocabulaire actuel. Ensuite, pour chaque symbole du vocabulaire, l’algorithme calcule de combien la perte globale augmenterait si le symbole était supprimé et recherche les symboles qui l’augmenteraient le moins. Ces symboles ont un effet moindre sur la perte globale du corpus, ils sont donc en quelque sorte « moins nécessaires » et sont les meilleurs candidats à la suppression.

Comme il s’agit d’une opération très coûteuse, nous ne nous contentons pas de supprimer le symbole unique associé à la plus faible augmentation de la perte mais le$p$ pourcent des symboles associés à la plus faible augmentation de la perte. (p\) est un hyperparamètre que vous pouvez contrôler, valant généralement 10 ou 20. Ce processus est ensuite répété jusqu’à ce que le vocabulaire ait atteint la taille souhaitée.

Notez que nous ne supprimons jamais les caractères de base, afin de nous assurer que tout mot peut être tokenisé.

Tout ceci peut paraître encore un peu vague. En effet, la partie principale de l’algorithme est de calculer une perte sur le corpus et de voir comment elle change lorsque nous supprimons certains tokens du vocabulaire mais nous n’avons pas encore expliqué comment le faire. Cette étape repose sur l’algorithme de tokénisation Unigram, nous allons donc l’aborder à présent.

Nous allons réutiliser le corpus des exemples précédents :

("hug", 10), ("pug", 5), ("pun", 12), ("bun", 4), ("hugs", 5) # "câlin", "carlin", "jeu de mots", "brioche", "câlins"...

et pour cet exemple, nous prendrons toutes les sous-chaînes strictes pour le vocabulaire initial :

["h", "u", "g", "hu", "ug", "p", "pu", "n", "un", "b", "bu", "s", "hug", "gs", "ugs"]

Algorithme de tokenisation

Un modèle Unigram est un type de modèle de langage qui considère que chaque token est indépendant des tokens qui le précèdent. Il s’agit du modèle de langage le plus simple, dans le sens où la probabilité du token X compte tenu du contexte précédent est simplement la probabilité du token X. Ainsi, si nous utilisions un modèle de langage Unigram pour générer du texte, nous prédirions toujours le token le plus courant.

La probabilité d’un token donné est sa fréquence (le nombre de fois que nous le trouvons) dans le corpus original, divisée par la somme de toutes les fréquences de tous les tokens dans le vocabulaire (pour s’assurer que la somme des probabilités est égale à 1). Par exemple, "ug" est présent dans "hug", "pug", et "hugs". Il a donc une fréquence de 20 dans notre corpus.

Voici les fréquences de tous les sous-mots possibles dans le vocabulaire :

("h", 15) ("u", 36) ("g", 20) ("hu", 15) ("ug", 20) ("p", 17) ("pu", 17) ("n", 16)
("un", 16) ("b", 4) ("bu", 4) ("s", 5) ("hug", 15) ("gs", 5) ("ugs", 5)

Ainsi, la somme de toutes les fréquences est de 210 et la probabilité du sous-mot "ug" est donc de 20/210.

Maintenant, pour tokeniser un mot donné, nous examinons toutes les segmentations possibles en tokens et calculons la probabilité de chacune d’entre elles selon le modèle Unigram. Puisque tous les tokens sont considérés comme indépendants, cette probabilité est juste le produit de la probabilité de chaque token. Par exemple, la tokenisation ["p", "u", "g"] de "pug" a la probabilité : $$P([``p", ``u", ``g"]) = P(``p") \times P(``u") \times P(``g") = \frac{5}{210} \times \frac{36}{210} \times \frac{20}{210} = 0.000389$$

Comparativement, la tokenization ["pu", "g"] a la probabilité : $$P([``pu", ``g"]) = P(``pu") \times P(``g") = \frac{5}{210} \times \frac{20}{210} = 0.0022676$$

donc celle-là est beaucoup plus probable. En général, les tokénisations comportant le moins de tokens possible auront la probabilité la plus élevée (en raison de la division par 210 répétée pour chaque token), ce qui correspond à ce que nous voulons intuitivement : diviser un mot en un nombre de tokens le plus faible possible.

La tokenisation d’un mot avec le modèle Unigram est donc la tokenisation avec la plus haute probabilité. Dans l’exemple de "pug", voici les probabilités que nous obtiendrions pour chaque segmentation possible :

["p", "u", "g"] : 0.000389
["p", "ug"] : 0.0022676
["pu", "g"] : 0.0022676

Ainsi, "pug" sera tokenisé comme ["p", "ug"] ou ["pu", "g"], selon la segmentation rencontrée en premier (notez que dans un corpus plus large, les cas d’égalité comme celui-ci seront rares).

Dans ce cas-ci, cela a été facile de trouver toutes les segmentations possibles et de calculer leurs probabilités, mais en général ce sera un peu plus difficile. Il existe un algorithme classique utilisé pour cela, appelé algorithme de Viterbi. Essentiellement, on peut construire un graphe pour détecter les segmentations possibles d’un mot donné en disant qu’il existe une branche du caractère a au caractère b si le sous-mot de a à b est dans le vocabulaire, et attribuer à cette branche la probabilité du sous-mot.

Pour trouver le chemin qui va avoir le meilleur score dans ce graphe, l’algorithme de Viterbi détermine, pour chaque position dans le mot, la segmentation avec le meilleur score qui se termine à cette position. Puisque nous allons du début à la fin, ce meilleur score peut être trouvé en parcourant en boucle tous les sous-mots se terminant à la position actuelle, puis en utilisant le meilleur score de tokenization de la position à laquelle ce sous-mot commence. Ensuite, il suffit de dérouler le chemin emprunté pour arriver à la fin.

Prenons un exemple en utilisant notre vocabulaire et le mot "unhug". Pour chaque position, les sous-mots avec les meilleurs scores se terminant là sont les suivants :

Character 0 (u): "u" (score 0.171429)
Character 1 (n): "un" (score 0.076191)
Character 2 (h): "un" "h" (score 0.005442)
Character 3 (u): "un" "hu" (score 0.005442)
Character 4 (g): "un" "hug" (score 0.005442)

Ainsi, "unhug" serait tokenisé comme ["un", "hug"].

Retour à l’entraînement

Maintenant que nous avons vu comment fonctionne la tokenisation, nous pouvons nous plonger un peu plus profondément dans la perte utilisée pendant l’entraînement. À n’importe quelle étape, cette perte est calculée en tokenisant chaque mot du corpus, en utilisant le vocabulaire courant et le modèle Unigram déterminé par les fréquences de chaque token dans le corpus (comme vu précédemment).

Chaque mot du corpus a un score, et la perte est le négatif du logarithme de ces scores, c’est-à-dire la somme pour tous les mots du corpus de tous les -log(P(word)).

Revenons à notre exemple avec le corpus suivant :

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

La tokenisation de chaque mot avec leurs scores respectifs est :

"hug": ["hug"] (score 0.071428)
"pug": ["pu", "g"] (score 0.007710)
"pun": ["pu", "n"] (score 0.006168)
"bun": ["bu", "n"] (score 0.001451)
"hugs": ["hug", "s"] (score 0.001701)

Donc la perte est :

10 * (-log(0.071428)) + 5 * (-log(0.007710)) + 12 * (-log(0.006168)) + 4 * (-log(0.001451)) + 5 * (-log(0.001701)) = 169.8

Maintenant, nous devons calculer comment la suppression de chaque token affecte la perte. C’est plutôt fastidieux, donc nous allons le faire pour deux tokens ici et garder tout le processus pour quand nous aurons du code pour nous aider. Dans ce cas (très) particulier, nous avions deux tokenizations équivalentes de tous les mots. Par exmeple, comme nous l’avons vu précédemment, "pug" pourrait être tokenisé en ["p", "ug"] avec le même score. Ainsi, enlever le token "pu" du vocabulaire donnera exactement la même perte.

D’un autre côté, supprimer le mot "hug" aggravera la perte, car la tokenisation de "hug" et "hugs" deviendra :

"hug": ["hu", "g"] (score 0.006802)
"hugs": ["hu", "gs"] (score 0.001701)

Ces changements entraîneront une augmentation de la perte de :

- 10 * (-log(0.071428)) + 10 * (-log(0.006802)) = 23.5

Par conséquent, le token "pu" sera probablement retiré du vocabulaire, mais pas "hug".

Implémentation d’ <i> Unigram </i>

Maintenant, implémentons tout ce que nous avons vu jusqu’à présent dans le code. Comme pour le BPE et WordPiece, ce n’est pas une implémentation efficace de l’algorithme Unigram (bien au contraire), mais elle devrait vous aider à le comprendre un peu mieux.

Nous allons utiliser le même corpus que précédemment comme exemple :

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*.
]

Cette fois, nous allons utiliser xlnet-base-cased comme modèle :

from transformers import AutoTokenizer

tokenizer = AutoTokenizer.from_pretrained("xlnet-base-cased")

Comme pour le BPE et WordPiece, nous commençons par compter le nombre d’occurrences de chaque mot dans le corpus :

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

word_freqs

Ensuite, nous devons initialiser notre vocabulaire à une taille plus grande que celle du vocabulaire que nous voudrons à la fin. Nous devons inclure tous les caractères de base (sinon nous ne serons pas en mesure de tokeniser chaque mot), mais pour les sous-chaînes plus grandes, nous ne garderons que les plus communs. AInsi nous les trions par fréquence :

char_freqs = defaultdict(int)
subwords_freqs = defaultdict(int)
for word, freq in word_freqs.items():
    for i in range(len(word)):
        char_freqs[word[i]] += freq
        # Boucle à travers les sous-mots de longueur au moins égale à 2
        for j in range(i + 2, len(word) + 1):
            subwords_freqs[word[i:j]] += freq

# Trier les sous-mots par fréquence
sorted_subwords = sorted(subwords_freqs.items(), key=lambda x: x[1], reverse=True)
sorted_subwords[:10]

[('▁t', 7), ('is', 5), ('er', 5), ('▁a', 5), ('▁to', 4), ('to', 4), ('en', 4), ('▁T', 3), ('▁Th', 3), ('▁Thi', 3)]

Nous regroupons les caractères avec les meilleurs sous-mots pour arriver à un vocabulaire initial de taille 300 :

token_freqs = list(char_freqs.items()) + sorted_subwords[: 300 - len(char_freqs)]
token_freqs = {token: freq for token, freq in token_freqs}

Ensuite, nous calculons la somme de toutes les fréquences, pour convertir les fréquences en probabilités. Pour notre modèle, nous allons stocker les logarithmes des probabilités, car c’est plus stable numériquement d’additionner des logarithmes que de multiplier des petits nombres. Cela simplifiera aussi le calcul de la perte du modèle :

from math import log

total_sum = sum([freq for token, freq in token_freqs.items()])
model = {token: -log(freq / total_sum) for token, freq in token_freqs.items()}

Maintenant la fonction principale est celle qui tokenise les mots en utilisant l’algorithme de Viterbi. Comme nous l’avons vu précédemment, cet algorithme calcule la meilleure segmentation de chaque sous-chaîne du mot que nous allons stocker dans une variable nommée best_segmentations. Nous allons stocker un dictionnaire par position dans le mot (de 0 à sa longueur totale), avec deux clés : l’index du début du dernier token dans la meilleure segmentation et le score de la meilleure segmentation. Avec l’index du début du dernier token, nous serons en mesure de récupérer la segmentation complète une fois que la liste est complètement remplie.

Le remplissage de la liste se fait à l’aide de deux boucles seulement : la boucle principale passe en revue chaque position de départ et la seconde boucle essaie toutes les sous-chaînes commençant à cette position de départ. Si la sous-chaîne est dans le vocabulaire, nous avons une nouvelle segmentation du mot jusqu’à cette position finale que nous comparons à ce qui est dans best_segmentations.

Une fois que la boucle principale est terminée, nous commençons juste à la fin et sautons d’une position de départ à une autre, en enregistrant les tokens au fur et à mesure, jusqu’à ce que nous atteignions le début du mot :

def encode_word(word, model):
    best_segmentations = [{"start": 0, "score": 1}] + [
        {"start": None, "score": None} for _ in range(len(word))
    ]
    for start_idx in range(len(word)):
        # Doit être correctement rempli par les étapes précédentes de la boucle
        best_score_at_start = best_segmentations[start_idx]["score"]
        for end_idx in range(start_idx + 1, len(word) + 1):
            token = word[start_idx:end_idx]
            if token in model and best_score_at_start is not None:
                score = model[token] + best_score_at_start
                # Si nous avons trouvé une meilleure segmentation se terminant à end_idx, nous mettons à jour
                if (
                    best_segmentations[end_idx]["score"] is None
                    or best_segmentations[end_idx]["score"] > score
                ):
                    best_segmentations[end_idx] = {"start": start_idx, "score": score}

    segmentation = best_segmentations[-1]
    if segmentation["score"] is None:
        # Nous n'avons pas trouvé de tokenization du mot -> inconnu (<unk>)
        return ["<unk>"], None

    score = segmentation["score"]
    start = segmentation["start"]
    end = len(word)
    tokens = []
    while start != 0:
        tokens.insert(0, word[start:end])
        next_start = best_segmentations[start]["start"]
        end = start
        start = next_start
    tokens.insert(0, word[start:end])
    return tokens, score

Nous pouvons déjà essayer notre modèle initial sur quelques mots :

print(encode_word("Hopefully", model))
print(encode_word("This", model))

(['H', 'o', 'p', 'e', 'f', 'u', 'll', 'y'], 41.5157494601402)
(['This'], 6.288267030694535)

Il est maintenant facile de calculer la perte du modèle sur le corpus !

def compute_loss(model):
    loss = 0
    for word, freq in word_freqs.items():
        _, word_loss = encode_word(word, model)
        loss += freq * word_loss
    return loss

Nous pouvons vérifier que cela fonctionne sur le modèle que nous avons :

compute_loss(model)

413.10377642940875

Le calcul des scores pour chaque token n’est pas très difficile non plus. Il suffit de calculer la perte pour les modèles obtenus en supprimant chaque token :

import copy


def compute_scores(model):
    scores = {}
    model_loss = compute_loss(model)
    for token, score in model.items():
        # Nous gardons toujours les tokens de longueur 1.
        if len(token) == 1:
            continue
        model_without_token = copy.deepcopy(model)
        _ = model_without_token.pop(token)
        scores[token] = compute_loss(model_without_token) - model_loss
    return scores

Nous pouvons l’essayer sur un token donné :

scores = compute_scores(model)
print(scores["ll"])
print(scores["his"])

Puisque "ll" est utilisé dans la tokenisation de "Hopefully", et que le supprimer nous fera probablement utiliser le token "l" deux fois à la place, nous nous attendons à ce qu’il ait une perte positive. "his" n’est utilisé qu’à l’intérieur du mot "This", qui est tokenisé comme lui-même, donc nous nous attendons à ce qu’il ait une perte nulle. Voici les résultats :

6.376412403623874
0.0

Une fois tout cela en place, la dernière chose à faire est d’ajouter les tokens spéciaux utilisés par le modèle au vocabulaire, puis de boucler jusqu’à ce que nous ayons élagué suffisamment de tokens du vocabulaire pour atteindre la taille souhaitée :

percent_to_remove = 0.1
while len(model) > 100:
    scores = compute_scores(model)
    sorted_scores = sorted(scores.items(), key=lambda x: x[1])
    # Supprime les tokens percent_to_remove ayant les scores les plus bas
    for i in range(int(len(model) * percent_to_remove)):
        _ = token_freqs.pop(sorted_scores[i][0])

    total_sum = sum([freq for token, freq in token_freqs.items()])
    model = {token: -log(freq / total_sum) for token, freq in token_freqs.items()}

Ensuite, pour tokeniser un texte, il suffit d’appliquer la prétokénisation et d’utiliser la fonction encode_word() :

def tokenize(text, model):
    words_with_offsets = tokenizer.backend_tokenizer.pre_tokenizer.pre_tokenize_str(text)
    pre_tokenized_text = [word for word, offset in words_with_offsets]
    encoded_words = [encode_word(word, model)[0] for word in pre_tokenized_text]
    return sum(encoded_words, [])


tokenize("This is the Hugging Face course.", model)

['▁This', '▁is', '▁the', '▁Hugging', '▁Face', '▁', 'c', 'ou', 'r', 's', 'e', '.']

C’est tout pour Unigram ! Avec un peu de chance, vous vous sentez à présent être un expert des tokenizers. Dans la prochaine section, nous allons nous plonger dans les blocs de construction de la bibliothèque 🤗 Tokenizers et allons vous montrer comment vous pouvez les utiliser pour construire votre propre tokenizer.