Tu sais maintenant que la tokenization par sous-mots est la meilleure approche. Mais comment ça marche concrètement ? Comment un algorithme décide-t-il que « ing » devrait être un token, mais pas « inz » ? Comment construit-on un vocabulaire de 50 000 tokens à partir d'un corpus de texte ? L'algorithme Byte Pair Encoding (BPE) est la réponse — et tu vas l'implémenter from scratch dans cette leçon.
Key Idea
BPE est un algorithme glouton bottom-up : on part des caractères individuels (ou octets), on compte les paires adjacentes les plus fréquentes, on fusionne la paire gagnante en un nouveau token, et on répète jusqu'à atteindre la taille de vocabulaire souhaitée.
Key Idea
WordPiece et Unigram sont deux alternatives à BPE. WordPiece maximise la vraisemblance au lieu de la fréquence brute. Unigram part d'un grand vocabulaire et élague (top-down), à l'inverse de BPE (bottom-up).
L'intuition derrière BPE
Situation
Tu as un corpus de texte anglais. Tu remarques que la séquence t + h apparaît des milliers de fois (dans « the », « that », « this », « with »…). Si tu crées un token th, tu réduis la longueur de toutes ces séquences. Puis tu remarques que th + e est très fréquent — tu crées the. En répétant ce processus, tu construis un vocabulaire qui capture les patterns statistiques de ta langue.
Byte Pair Encoding (BPE)
Algorithme de compression de données adapté à la tokenization NLP par Sennrich et al. (2016). Il construit itérativement un vocabulaire en fusionnant les paires de tokens adjacentes les plus fréquentes dans le corpus d'entraînement.
L'algorithme en pseudo-code :
ENTRÉE : corpus de texte, taille de vocabulaire cible V
SORTIE : vocabulaire de V tokens + liste de règles de fusion
1. Initialiser le vocabulaire avec tous les caractères individuels (ou octets)
2. Tokeniser le corpus en caractères individuels
3. TANT QUE taille(vocabulaire) < V :
a. Compter toutes les paires de tokens adjacentes dans le corpus
b. Trouver la paire (A, B) la plus fréquente
c. Créer un nouveau token AB (fusion de A et B)
d. Ajouter AB au vocabulaire
e. Remplacer toutes les occurrences de (A, B) par AB dans le corpus
f. Enregistrer la règle de fusion : A + B → AB
4. Retourner le vocabulaire et les règles de fusion
BPE à la main : un exemple complet
Situation
Avant de coder, faisons tourner l'algorithme à la main sur un mini-corpus pour bien comprendre chaque étape. Prends le corpus : "low low low low low lower lower newest newest newest newest newest newest widest widest widest".
On commence par compter les fréquences de chaque mot et les décomposer en caractères (avec un symbole de fin de mot _) :
Vocabulaire initial : {l, o, w, e, r, n, s, t, i, d, _}
Corpus tokenisé (avec fréquences) :
"l o w _" × 5
"l o w e r _" × 2
"n e w e s t _" × 6
"w i d e s t _" × 3
Itération 1 : Compter les paires adjacentes :
Paire Fréquence
(e, s) 6 + 3 = 9 ← GAGNANTE
(s, t) 6 + 3 = 9 ← ex aequo, on prend (e, s) par convention
(l, o) 5 + 2 = 7
(o, w) 5 + 2 = 7
(w, _) 5
(t, _) 6 + 3 = 9 ← ex aequo
(n, e) 6
...
On fusionne e + s → es :
"l o w _" × 5
"l o w e r _" × 2
"n e w es t _" × 6
"w i d es t _" × 3
Itération 2 : La paire (es, t) a fréquence 9. On fusionne → est :
"l o w _" × 5
"l o w e r _" × 2
"n e w est _" × 6
"w i d est _" × 3
Itération 3 :(est, _) a fréquence 9. On fusionne → est_ :
"l o w _" × 5
"l o w e r _" × 2
"n e w est_" × 6
"w i d est_" × 3
Itération 4 :(l, o) a fréquence 7. On fusionne → lo :
"lo w _" × 5
"lo w e r _" × 2
"n e w est_" × 6
"w i d est_" × 3
Et ainsi de suite. Chaque fusion crée un token plus long et réduit la longueur totale du corpus tokenisé.
Implémentation Python from scratch
Situation
Tu veux coder BPE toi-même pour vraiment comprendre. Pas de bibliothèque, juste Python pur. On va construire un tokenizer BPE complet en ~60 lignes.
BPE from scratch en Python
def get_stats(ids):
"""Compte les paires adjacentes dans une liste d'entiers."""
counts = {}
for pair in zip(ids, ids[1:]):
counts[pair] = counts.get(pair, 0) + 1
return counts
def merge(ids, pair, idx):
"""Remplace toutes les occurrences de pair par idx dans ids."""
new_ids = []
i = 0
while i < len(ids):
if i < len(ids) - 1 and (ids[i], ids[i + 1]) == pair:
new_ids.append(idx)
i += 2
else:
new_ids.append(ids[i])
i += 1
return new_ids
def train_bpe(text, vocab_size):
"""Entraîne un tokenizer BPE sur un texte."""
assert vocab_size >= 256, "vocab_size doit être >= 256 (octets de base)"
num_merges = vocab_size - 256
# Étape 1 : convertir le texte en octets
tokens = list(text.encode("utf-8"))
print(f"Longueur initiale : {len(tokens)} octets")
# Étape 2 : fusions itératives
merges = {} # (int, int) → int
vocab = {idx: bytes([idx]) for idx in range(256)}
for i in range(num_merges):
stats = get_stats(tokens)
if not stats:
break
top_pair = max(stats, key=stats.get)
new_idx = 256 + i
tokens = merge(tokens, top_pair, new_idx)
merges[top_pair] = new_idx
# Construire la représentation bytes du nouveau token
vocab[new_idx] = vocab[top_pair[0]] + vocab[top_pair[1]]
if i < 10: # Afficher les 10 premières fusions
print(f"Fusion {i+1}: {top_pair} → {new_idx} "
f"({vocab[new_idx]}) | fréq={stats[top_pair]}")
print(f"Longueur finale : {len(tokens)} tokens")
print(f"Taux de compression : {len(text.encode('utf-8'))/len(tokens):.2f}x")
return merges, vocab
# Entraînement sur un petit corpus
corpus = "le chat mange le poisson. le chat dort. le poisson nage." * 100
merges, vocab = train_bpe(corpus, vocab_size=300)
Maintenant, ajoutons l'encodage et le décodage :
Encoder et décoder avec notre BPE
def encode(text, merges):
"""Encode un texte en token IDs avec les règles de fusion BPE."""
tokens = list(text.encode("utf-8"))
while len(tokens) >= 2:
stats = get_stats(tokens)
# Trouver la paire qui a la priorité de fusion la plus basse
pair = min(stats, key=lambda p: merges.get(p, float("inf")))
if pair not in merges:
break # Plus aucune fusion possible
idx = merges[pair]
tokens = merge(tokens, pair, idx)
return tokens
def decode(ids, vocab):
"""Décode une liste de token IDs en texte."""
tokens_bytes = b"".join(vocab[idx] for idx in ids)
return tokens_bytes.decode("utf-8", errors="replace")
# Test round-trip
test = "le chat mange du poisson"
encoded = encode(test, merges)
decoded = decode(encoded, vocab)
print(f"Original : {test}")
print(f"Encodé : {encoded}")
print(f"Décodé : {decoded}")
print(f"Tokens : {len(encoded)} (vs {len(test.encode('utf-8'))} octets)")
assert decoded == test, "Round-trip échoué !"
La pré-tokenization : pourquoi GPT-2 utilise une regex
Situation
Tu appliques ton BPE naïf sur « I'm going to the store. » et tu obtiens des fusions bizarres : le ' de I'm se fusionne avec le g de going parce qu'ils sont adjacents dans la séquence d'octets. Le BPE ne respecte pas les frontières de mots. Comment empêcher ça ?
Pré-tokenization
Étape de découpage grossier du texte avant l'application de BPE. Empêche les fusions de traverser certaines frontières (mots, ponctuation, espaces). Chaque « pré-token » est traité indépendamment par BPE.
GPT-2 utilise cette regex pour la pré-tokenization :
Tu lis le papier de BERT et tu vois qu'il utilise « WordPiece » au lieu de BPE. C'est quoi la différence ? Est-ce que ça change fondamentalement les résultats ?
WordPiece
Variante de BPE utilisée par BERT. Au lieu de fusionner la paire la plus fréquente, WordPiece fusionne la paire qui maximise la vraisemblance du corpus (mesurée par le score de mutual information).
La différence clé est le critère de fusion :
BPE : score(A, B) = count(AB)
WordPiece : score(A, B) = count(AB) / (count(A) × count(B))
WordPiece favorise les paires où les deux éléments apparaissent rarement seuls mais souvent ensemble. BPE favorise simplement les paires les plus fréquentes.
Score WordPiece vs BPE
# Exemple : corpus avec fréquences
counts = {"un": 100, "##able": 80, "unable": 50, "the": 5000, "##re": 3000, "there": 200}
# Score BPE pour "un" + "##able" → "unable"
bpe_score_unable = 50 # fréquence brute de la paire
# Score WordPiece pour "un" + "##able"
wp_score_unable = 50 / (100 * 80) # = 0.00625
# Score BPE pour "the" + "##re" → "there"
bpe_score_there = 200 # fréquence brute
# Score WordPiece pour "the" + "##re"
wp_score_there = 200 / (5000 * 3000) # = 0.0000133
# BPE préfère "there" (200 > 50)
# WordPiece préfère "unable" (0.00625 > 0.0000133)
print(f"BPE : there ({bpe_score_there}) > unable ({bpe_score_unable})")
print(f"WordPiece : unable ({wp_score_unable:.6f}) > there ({wp_score_there:.7f})")
Autre différence notable : WordPiece utilise le préfixe ## pour marquer les sous-mots qui ne sont pas en début de mot :
BPE et WordPiece construisent le vocabulaire de bas en haut (bottom-up). Mais il existe une approche inverse : partir d'un très grand vocabulaire et supprimer les tokens les moins utiles. C'est l'algorithme Unigram, utilisé par SentencePiece (et donc par T5, ALBERT, XLNet).
Unigram Language Model (tokenization)
Algorithme de tokenization top-down proposé par Kudo (2018). Part d'un grand vocabulaire initial (~1M tokens), puis supprime itérativement les tokens dont la suppression augmente le moins la perte (loss) du modèle de langue unigram sur le corpus.
Initialiser un grand vocabulaire (tous les sous-mots fréquents jusqu'à une certaine longueur)
Pour chaque token du vocabulaire, calculer combien la loss augmenterait s'il était supprimé
Supprimer les tokens avec le plus petit impact (typiquement 10-20% à chaque itération)
Répéter jusqu'à atteindre la taille cible
Avantage clé d'Unigram : il peut produire plusieurs tokenizations pour un même texte et choisir la plus probable. Cela permet une régularisation naturelle (subword regularization).
Tokenization probabiliste avec Unigram
# Avec SentencePiece, Unigram peut sampler différentes tokenizations
# "unbelievable" pourrait être tokenisé comme :
# - ["▁un", "believ", "able"] (probabilité 0.4)
# - ["▁un", "believe", "able"] (probabilité 0.3) -- hypothétique
# - ["▁unbeliev", "able"] (probabilité 0.2)
# - ["▁unbelievable"] (probabilité 0.1)
# En entraînement, on peut sampler pour régulariser
# En inférence, on prend la tokenization la plus probable (Viterbi)
Tableau comparatif : BPE vs WordPiece vs Unigram
Situation
Tu dois choisir un algorithme de tokenization pour ton projet. Voici un résumé complet pour t'aider à décider.
Critère
BPE
WordPiece
Unigram
Direction
Bottom-up
Bottom-up
Top-down
Critère de fusion/élagage
Fréquence brute
Vraisemblance (mutual info)
Impact sur la loss
Déterministe ?
Oui
Oui
Non (peut sampler)
Marqueur de sous-mot
Espace en préfixe ( world)
## en préfixe (##ing)
▁ en préfixe (▁world)
Modèles
GPT-2/3/4, LLaMA, Mistral
BERT, DistilBERT, Electra
T5, ALBERT, XLNet, mBART
Bibliothèque
tiktoken, HuggingFace
HuggingFace
SentencePiece
Vitesse d'entraînement
Rapide
Moyen
Lent
Gestion OOV
Byte-level = jamais d'OOV
Possible [UNK]
Possible [UNK]
Régularisation
Non native
Non native
BPE-dropout / sampling natif
BPE-dropout : régulariser via la tokenization
Situation
Ton modèle overfitte sur les patterns de tokenization. Le mot « playing » est toujours tokenisé ["play", "ing"], donc le modèle n'apprend jamais que ["pl", "ay", "ing"] est le même mot. Comment introduire de la variabilité ?
BPE-dropout
Technique de régularisation qui, pendant l'entraînement, ignore aléatoirement certaines fusions BPE avec une probabilité p (typiquement 0.1). Cela produit des tokenizations différentes pour le même texte à chaque epoch, forçant le modèle à être robuste aux variations de découpage.
BPE-dropout simplifié
import random
def encode_with_dropout(text, merges, dropout=0.1):
"""BPE encoding avec dropout sur les fusions."""
tokens = list(text.encode("utf-8"))
while len(tokens) >= 2:
stats = get_stats(tokens)
pair = min(stats, key=lambda p: merges.get(p, float("inf")))
if pair not in merges:
break
# BPE-dropout : ignorer cette fusion avec probabilité dropout
if random.random() < dropout:
# On skip cette fusion, on cherche la suivante
# (implémentation simplifiée)
break
idx = merges[pair]
tokens = merge(tokens, pair, idx)
return tokens
# Même texte, tokenizations différentes à chaque appel
text = "playing"
for i in range(5):
tokens = encode_with_dropout(text, merges, dropout=0.3)
print(f" Run {i+1}: {tokens} ({len(tokens)} tokens)")
Entraîner BPE sur un vrai corpus
Situation
Tu veux aller au-delà du jouet et entraîner un tokenizer BPE sur un vrai corpus. Utilisons la bibliothèque tokenizers de HuggingFace, qui est écrite en Rust et peut traiter des gigaoctets de texte en quelques minutes.
Entraîner BPE avec HuggingFace tokenizers
from tokenizers import Tokenizer
from tokenizers.models import BPE
from tokenizers.trainers import BpeTrainer
from tokenizers.pre_tokenizers import ByteLevel
# Créer un tokenizer BPE vide
tokenizer = Tokenizer(BPE(unk_token=None)) # byte-level = pas d'UNK
tokenizer.pre_tokenizer = ByteLevel(add_prefix_space=False)
# Configurer l'entraînement
trainer = BpeTrainer(
vocab_size=1000,
min_frequency=2,
special_tokens=["<|endoftext|>", "<|padding|>"],
show_progress=True,
)
# Entraîner sur des fichiers texte
tokenizer.train(["corpus.txt"], trainer)
# Tester
output = tokenizer.encode("Bonjour le monde!")
print(f"Tokens : {output.tokens}")
print(f"IDs : {output.ids}")
# Sauvegarder
tokenizer.save("my_tokenizer.json")
Tokenizers — HuggingFace NLP Course
Cette vidéo du cours NLP de HuggingFace explique les trois algorithmes (BPE, WordPiece, Unigram) avec des visualisations claires et des exemples interactifs.
Summary
Concept
Description
BPE
Fusionne itérativement les paires de tokens les plus fréquentes (bottom-up)
Règles de fusion
Liste ordonnée de paires → nouveau token. Appliquées dans l'ordre lors de l'encodage
Pré-tokenization
Découpage grossier avant BPE pour respecter les frontières de mots
WordPiece
Variante de BPE qui maximise la vraisemblance au lieu de la fréquence
Unigram
Approche top-down : part d'un grand vocab et élague les tokens les moins utiles
BPE-dropout
Régularisation par omission aléatoire de fusions pendant l'entraînement
Byte-level BPE
BPE appliqué aux octets UTF-8 (vocabulaire de base = 256)
Références
Sennrich, R., Haddow, B., & Birch, A. (2016). Neural Machine Translation of Rare Words with Subword Units. ACL 2016. arXiv:1508.07909
Gage, P. (1994). A New Algorithm for Data Compression. C Users Journal, 12(2), 23–38.
Schuster, M., & Nakajima, K. (2012). Japanese and Korean Voice Search. ICASSP 2012.
Kudo, T. (2018). Subword Regularization: Improving Neural Network Translation Models with Multiple Subword Candidates. ACL 2018. arXiv:1804.10959
Provilkov, I., Emelianenko, D., & Voita, E. (2020). BPE-Dropout: Simple and Effective Subword Regularization. ACL 2020. arXiv:1910.13267