# Tokenisation Unigram 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. > [!TIP] > 💡 Cette section couvre *Unigram* 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 tokénisation. ## 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. > [!TIP] > ✏️ **A votre tour !** Ecrivez le code permettant de calculer les fréquences ci-dessus et vérifiez que les résultats affichés sont corrects, de même que la somme totale. 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"]`. > [!TIP] > ✏️ **A votre tour !** Déterminer la tokenization du mot `"huggun"` et son score. ## 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'Unigram 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 : ```python 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 : ```python 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 : ```python 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 : ```python 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] ``` ```python out [('▁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 : ```python token_freqs = list(char_freqs.items()) + sorted_subwords[: 300 - len(char_freqs)] token_freqs = {token: freq for token, freq in token_freqs} ``` > [!TIP] > 💡 *SentencePiece* utilise un algorithme plus efficace appelé *Enhanced Suffix Array* (ESA) pour créer le vocabulaire initial. 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 : ```python 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 : ```python 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 () return [""], 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 : ```python print(encode_word("Hopefully", model)) print(encode_word("This", model)) ``` ```python out (['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 ! ```python 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 : ```python compute_loss(model) ``` ```python out 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* : ```python 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é : ```python 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 : ```python out 6.376412403623874 0.0 ``` > [!TIP] > 💡 Cette approche est très inefficace, c'est pourquoi *SentencePiece* utilise une approximation de la perte du modèle sans le *token* X. Au lieu de partir de zéro, il remplace simplement le *token* X par sa segmentation dans le vocabulaire restant. De cette façon, tous les scores peuvent être calculés en une seule fois, en même temps que la perte du modèle. 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 : ```python 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()` : ```python 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) ``` ```python out ['▁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*.