Tokénisation <i> WordPiece </i>

WordPiece est l’algorithme de tokénisation développé par Google pour prétraîner BERT. Il a depuis été réutilisé dans un grand nombre de modèles de transformers basés sur BERT tels que DistilBERT, MobileBERT, Funnel Transformers et MPNET. Il est très similaire au BPE en termes d’entraînement mais la tokenisation réelle est effectuée différemment.

Algorithme d’entraînement

Comme le BPE, WordPiece part d’un petit vocabulaire comprenant les tokens spéciaux utilisés par le modèle et l’alphabet initial. Puisqu’il identifie les sous-mots en ajoutant un préfixe (comme ## pour BERT), chaque mot est initialement découpé en ajoutant ce préfixe à tous les caractères du mot. Ainsi par exemple, "word" est divisé comme ceci :

w ##o ##r ##d

Ainsi, l’alphabet initial contient tous les caractères présents au début d’un mot et les caractères présents à l’intérieur d’un mot précédé du préfixe de WordPiece.

Ensuite, toujours comme le BPE, WordPiece apprend des règles de fusion. La principale différence réside dans la manière dont la paire à fusionner est sélectionnée. Au lieu de sélectionner la paire la plus fréquente, WordPiece calcule un score pour chaque paire en utilisant la formule suivante : $$\mathrm{score} = (\mathrm{freq\_of\_pair}) / (\mathrm{freq\_of\_first\_element} \times \mathrm{freq\_of\_second\_element})$$

En divisant la fréquence de la paire par le produit des fréquences de chacune de ses parties, l’algorithme donne la priorité à la fusion des paires dont les parties individuelles sont moins fréquentes dans le vocabulaire. Par exemple, il ne fusionnera pas nécessairement ("un", "##able") même si cette paire apparaît très fréquemment dans le vocabulaire car les deux paires "un"” et "##able" apparaîtront probablement chacune dans un batch d’autres mots et auront une fréquence élevée. En revanche, une paire comme ("hu", "##gging") sera probablement fusionnée plus rapidement (en supposant que le mot "hugging" apparaisse souvent dans le vocabulaire) puisque "hu" et "##gging" sont probablement moins fréquents individuellement.

Examinons le même vocabulaire que celui utilisé dans l’exemple d’entraînement du BPE :

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

Les divisions ici seront :

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

Si on oublie les tokens spéciaux pour l’instant, le vocabulaire initial sera donc ["b", "h", "p", "##g", "##n", "##s", "##u"]. La paire la plus fréquente est ("##u", "##g") (présente 20 fois), mais la fréquence individuelle de "##u" est très élevée, donc son score n’est pas le plus élevé (il est de 1 / 36). Toutes les paires avec un "##u" ont en fait le même score (1 / 36). Ainsi le meilleur score va à la paire ("##g", "##s") qui est la seule sans un "##u" avec un score 1 / 20. Et la première fusion apprise est ("##g", "##s") -> ("##gs").

Notez que lorsque nous fusionnons, nous enlevons le ## entre les deux tokens, donc nous ajoutons "##gs" au vocabulaire et appliquons la fusion dans les mots du corpus :

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

À ce stade, " ##u " est dans toutes les paires possibles, donc elles finissent toutes par avoir le même score. Disons que dans ce cas, la première paire est fusionnée, donc ("h", "##u") -> "hu". Cela nous amène à :

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

Ensuite, le meilleur score suivant est partagé par ("hu", "##g") et ("hu", "##gs") (avec 1/15, comparé à 1/21 pour toutes les autres paires). Ainsi la première paire avec le plus grand score est fusionnée :

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

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

Algorithme de tokenisation

La tokénisation diffère dans WordPiece et BPE en ce que WordPiece ne sauvegarde que le vocabulaire final et non pas les règles de fusion apprises. En partant du mot à tokeniser, WordPiece trouve le sous-mot le plus long qui se trouve dans le vocabulaire, puis se sépare sur celui-ci. Par exemple, si nous utilisons le vocabulaire appris dans l’exemple ci-dessus, pour le mot "hugs" le plus long sous-mot en partant du début qui est dans le vocabulaire est "hug". Donc nous le divisons et obtenons ["hug", "##s"]. On continue avec "##s", qui est dans le vocabulaire, donc la tokenisation de "hugs" est ["hug", "##s"].

Avec BPE, nous aurions appliqué les fusions apprises dans l’ordre et la tokénisation aurait été ["hu", "##gs"], l’encodage est donc différent.

Comme autre exemple, voyons comment le mot "bugs" serait tokenisé. "b" est le plus long sous-mot commençant au début du mot qui est dans le vocabulaire donc on le divise et on obtient ["b", "##ugs"]. Ensuite, "##u" est le plus long sous-mot commençant au début de "##ugs" qui est dans le vocabulaire, donc on le sépare et on obtient ["b", "##u, "##gs"]. Enfin, "##gs" est dans le vocabulaire, donc cette dernière liste est la tokenization de "bugs".

Lorsque la tokenisation arrive à un stade où il n’est pas possible de trouver un sous-mot dans le vocabulaire, le mot entier est tokenisé comme inconnu. Par exemple, "mug" serait tokenisé comme ["[UNK]"], tout comme "bum" (même si on peut commencer par ” b ” et ” ##u ”, ” ##m ” ne fait pas partie du vocabulaire, et le tokenizer résultant sera simplement ["[UNK]"] ” et non ["b", "##u", "[UNK]"] ”). C’est une autre différence avec le BPE qui classerait seulement les caractères individuels qui ne sont pas dans le vocabulaire comme inconnus.

Implémentation de <i> WordPiece </i>

Voyons maintenant une implémentation de l’algorithme WordPiece. Comme pour le BPE, il s’agit d’un exemple pédagogique et vous ne pourrez pas l’utiliser sur un grand corpus.

Nous utiliserons le même corpus que dans l’exemple BPE :

corpus = [
    "This is the Hugging Face Course.",
    # C'est le cours d'Hugging Face.
    "This chapter is about tokenization.",
    # This chapter is about tokenization
    "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.
]

Tout d’abord, nous devons prétokéniser le corpus en mots. Puisque nous répliquons un tokenizer WordPiece (comme BERT), nous utiliserons le tokenizer bert-base-cased pour la prétokénisation :

from transformers import AutoTokenizer

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

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

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})

Comme nous l’avons vu précédemment, l’alphabet est l’unique ensemble composé de toutes les premières lettres des mots, et de toutes les autres lettres qui apparaissent dans les mots préfixés par ## :

alphabet = []
for word in word_freqs.keys():
    if word[0] not in alphabet:
        alphabet.append(word[0])
    for letter in word[1:]:
        if f"##{letter}" not in alphabet:
            alphabet.append(f"##{letter}")

alphabet.sort()
alphabet

print(alphabet)

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

Nous ajoutons également les tokens spéciaux utilisés par le modèle au début de ce vocabulaire. Dans le cas de BERT, il s’agit de la liste ["[PAD]", "[UNK]", "[CLS]", "[SEP]", "[MASK]"] :

vocab = ["[PAD]", "[UNK]", "[CLS]", "[SEP]", "[MASK]"] + alphabet.copy()

Ensuite, nous devons diviser chaque mot, avec toutes les lettres qui ne sont pas les premières préfixées par ## :

splits = {
    word: [c if i == 0 else f"##{c}" for i, c in enumerate(word)]
    for word in word_freqs.keys()
}

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

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

    scores = {
        pair: freq / (letter_freqs[pair[0]] * letter_freqs[pair[1]])
        for pair, freq in pair_freqs.items()
    }
    return scores

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

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

('T', '##h'): 0.125
('##h', '##i'): 0.03409090909090909
('##i', '##s'): 0.02727272727272727
('i', '##s'): 0.1
('t', '##h'): 0.03571428571428571
('##h', '##e'): 0.011904761904761904

Maintenant, trouver la paire avec le meilleur score ne prend qu’une rapide boucle :

best_pair = ""
max_score = None
for pair, score in pair_scores.items():
    if max_score is None or max_score < score:
        best_pair = pair
        max_score = score

print(best_pair, max_score)

('a', '##b') 0.2

Ainsi, la première fusion à apprendre est ('a', '##b') -> 'ab' et nous ajoutons 'ab' au vocabulaire :

vocab.append("ab")

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:
                merge = a + b[2:] if b.startswith("##") else a + b
                split = split[:i] + [merge] + 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("a", "##b", splits)
splits["about"]

['ab', '##o', '##u', '##t']

Nous avons maintenant 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 70 :

vocab_size = 70
while len(vocab) < vocab_size:
    scores = compute_pair_scores(splits)
    best_pair, max_score = "", None
    for pair, score in scores.items():
        if max_score is None or max_score < score:
            best_pair = pair
            max_score = score
    splits = merge_pair(*best_pair, splits)
    new_token = (
        best_pair[0] + best_pair[1][2:]
        if best_pair[1].startswith("##")
        else best_pair[0] + best_pair[1]
    )
    vocab.append(new_token)

Nous pouvons ensuite examiner le vocabulaire généré :

print(vocab)

['[PAD]', '[UNK]', '[CLS]', '[SEP]', '[MASK]', '##a', '##b', '##c', '##d', '##e', '##f', '##g', '##h', '##i', '##k',
 '##l', '##m', '##n', '##o', '##p', '##r', '##s', '##t', '##u', '##v', '##w', '##y', '##z', ',', '.', 'C', 'F', 'H',
 'T', 'a', 'b', 'c', 'g', 'h', 'i', 's', 't', 'u', 'w', 'y', '##fu', 'Fa', 'Fac', '##ct', '##ful', '##full', '##fully',
 'Th', 'ch', '##hm', 'cha', 'chap', 'chapt', '##thm', 'Hu', 'Hug', 'Hugg', 'sh', 'th', 'is', '##thms', '##za', '##zat',
 '##ut']

Comme nous pouvons le voir, comparé à BPE, ce tokenizer apprend les parties de mots comme des tokens un peu plus rapidement.

Pour tokeniser un nouveau texte, on le prétokenise, on le divise, puis on applique l’algorithme de tokenisation sur chaque mot. En d’autres termes, nous recherchons le plus grand sous-mot commençant au début du premier mot et le divisons. Puis nous répétons le processus sur la deuxième partie et ainsi de suite pour le reste de ce mot et les mots suivants dans le texte :

def encode_word(word):
    tokens = []
    while len(word) > 0:
        i = len(word)
        while i > 0 and word[:i] not in vocab:
            i -= 1
        if i == 0:
            return ["[UNK]"]
        tokens.append(word[:i])
        word = word[i:]
        if len(word) > 0:
            word = f"##{word}"
    return tokens

Testons-le sur un mot qui fait partie du vocabulaire, et un autre qui n’en fait pas partie :

print(encode_word("Hugging"))
print(encode_word("HOgging"))

['Hugg', '##i', '##n', '##g']
['[UNK]']

Maintenant, écrivons une fonction qui permet de tokeniser un texte :

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]
    encoded_words = [encode_word(word) for word in pre_tokenized_text]
    return sum(encoded_words, [])

On peut l’essayer sur n’importe quel texte :

tokenize("This is the Hugging Face Course!")  # C'est le cours d'Hugging Face

['Th', '##i', '##s', 'is', 'th', '##e', 'Hugg', '##i', '##n', '##g', 'Fac', '##e', 'c', '##o', '##u', '##r', '##s',
 '##e', '[UNK]']

C’est tout pour l’algorithme WordPiece ! Maintenant, jetons un coup d’oeil à Unigram.