Tokenizarea Unigram

Algoritmul Unigram este adesea utilizat în SentencePiece, care este algoritmul de tokenizare utilizat de modele precum AlBERT, T5, mBART, Big Bird și XLNet.

💡 Această secțiune acoperă Unigram în profunzime, mergând până la prezentarea unei implementări complete. Puteți sări la sfârșit dacă doriți doar o prezentare generală a algoritmului de tokenizare.

Algoritm de antrenare

În comparație cu BPE și WordPiece, Unigram lucrează în cealaltă direcție: pornește de la un vocabular mare și elimină tokeni din acesta până când ajunge la dimensiunea dorită. Există mai multe opțiuni pentru a construi acel vocabular de bază: putem lua, de exemplu, cele mai comune substrings din cuvintele pre-tokenizate sau putem aplica BPE pe corpusul inițial cu o dimensiune mare a vocabularului.

La fiecare etapă a antrenării, algoritmul Unigram calculează o pierdere pe corpus oferit, având în vedere vocabularul curent. Apoi, pentru fiecare simbol din vocabular, algoritmul calculează cu cât ar crește pierderea globală dacă simbolul ar fi eliminat și caută simbolurile care ar crește cel mai puțin pierderea. Aceste simboluri au cel mai redus efect asupra pierderii globale din corpus, deci, într-un fel, sunt “mai puțin necesare” și sunt cei mai buni candidați pentru eliminare.

Aceasta este o operațiune foarte costisitoare, așa că nu eliminăm doar simbolul asociat cu cea mai mică creștere a pierderii, ci procentul$p$ (\(p\) fiind un hyperparametru pe care îl poți controla, de obicei 10 sau 20) din simbolurile asociate cu cea mai mică creștere a pierderilor. Acest proces este se repetă până când vocabularul atinge dimensiunea dorită.

Rețineți că nu eliminăm niciodată caracterele de bază, pentru a ne asigura că orice cuvânt poate fi tokenizat.

Acum, acest lucru este încă puțin vag: partea principală a algoritmului este de a calcula o pierdere asupra corpusului și de a vedea cum se schimbă atunci când eliminăm unele tokenuri din vocabular, dar nu am explicat încă cum să facem acest lucru. Acest pas se bazează pe algoritmul de tokenizare al unui model Unigram, așa că îl vom analiza în continuare.

Vom reutiliza corpusul din exemplele anterioare:

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

iar pentru acest exemplu, vom lua toate substringurile stricte pentru vocabularul inițial:

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

Algoritm de tokenizare

Un model Unigram este un tip de model lingvistic care consideră că fiecare token este independent de tokenii anteriori. Este cel mai simplu model lingvistic, în sensul că probabilitatea simbolului X având în vedere contextul anterior este doar probabilitatea simbolului X. Astfel, dacă am utiliza un model lingvistic Unigram pentru a genera text, am prezice întotdeauna simbolul cel mai frecvent.

Probabilitatea unui token dat este frecvența sa (numărul de ori în care îl găsim) în corpusul original, împărțită la suma tuturor aparițiilor tuturor tokenilor din vocabular (pentru a ne asigura că probabilitățile sunt egale cu 1). De exemplu, "ug" este prezent în "hug", "pug", și "hugs", deci are o frecvență de 20 în corpusul nostru.

Iată frecvențele tuturor subcuvintelor posibile din vocabular:

("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)

Astfel, suma tuturor frecvențelor este 210, iar probabilitatea subcuvântului "ug" este 20/210.

✏️ Acum este rândul tău! Scrie codul pentru a calcula frecvențele de mai sus și verifică de două ori dacă rezultatele afișate sunt corecte, precum și suma totală.

Acum, pentru a tokeniza un cuvânt dat, ne uităm la toate segmentările posibile în tokeni și calculăm probabilitatea fiecăruia în conformitate cu modelul Unigram. Deoarece toate token-urile sunt considerate independente, această probabilitate este doar produsul probabilității fiecărui token. De exemplu, tokenizarea ["p", "u", "g"] a lui "pug" are probabilitatea: $$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$$

Comparativ, tokenizarea ["pu", "g"] are probabilitatea: $$P([``pu", ``g"]) = P(``pu") \times P(``g") = \frac{5}{210} \times \frac{20}{210} = 0.0022676$$

astfel încât una este mult mai probabilă decât alta. În general, tokenizările cu cei mai puțini tokeni posibili vor avea cea mai mare probabilitate (din cauza acelei împărțiri la 210 repetată pentru fiecare token), ceea ce corespunde cu ceea ce dorim intuitiv: să împărțim un cuvânt în cel mai mic număr de tokenuri posibil.

Tokenizarea unui cuvânt cu modelul Unigram este atunci tokenizarea cu cea mai mare probabilitate. În exemplul "pug", iată probabilitățile pe care le-am obține pentru fiecare segmentare posibilă:

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

Astfel, "pug" ar fi tokenizat ca ["p", "ug"] sau ["pu", "g"], în funcție de care dintre aceste segmentări este întâlnită prima (rețineți că într-un corpus mai mare, cazurile de egalitate ca acesta vor fi rare).

În acest caz, a fost ușor să găsim toate segmentările posibile și să le calculăm probabilitățile, dar în general va fi puțin mai greu. Există un algoritm clasic utilizat pentru acest lucru, numit algoritmul Viterbi. În esență, putem construi un grafic pentru a detecta segmentările posibile ale unui cuvânt dat, spunând că există o ramură de la caracterul a la caracterul b dacă subcuvântul de la a la b se află în vocabular, și atribuind ramurii respective probabilitatea subcuvântului.

Pentru a găsi calea din acest grafic care va avea cel mai bun scor, algoritmul Viterbi determină, pentru fiecare poziție din cuvânt, segmentarea cu cel mai bun scor care se termină la poziția respectivă. Deoarece mergem de la început la sfârșit, cel mai bun scor poate fi găsit prin parcurgerea în buclă a tuturor subcuvintelor care se termină la poziția curentă și apoi folosind cel mai bun scor de tokenizare de la poziția la care începe acest subcuvânt. Apoi, trebuie doar să derulăm calea parcursă pentru a ajunge la sfârșit.

Să aruncăm o privire la un exemplu folosind vocabularul nostru și cuvântul "unhug". Pentru fiecare poziție, subcuvintele cu cele mai bune scoruri care se termină acolo sunt următoarele:

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)

Astfel, "unhug" ar fi tokenizat ca ["un", "hug"].

✏️ Acum e rândul tău! Determinați tokenizarea cuvântului "huggun" și scorul acestuia.

Înapoi la antrenare

Acum că am văzut cum funcționează tokenizarea, putem analiza mai în profunzime pierderea utilizată în timpul antrenării. În orice etapă dată, această pierdere este calculată prin tokenizarea fiecărui cuvânt din corpus, utilizând vocabularul curent și modelul Unigram determinat de frecvențele fiecărui token din corpus (după cum am văzut mai devreme).

Fiecare cuvânt din corpus are un scor, iar pierderea este negative log likelihood a acestor scoruri - adică suma pentru toate cuvintele din corpus a tuturor -log(P(word)).

Să ne întoarcem la exemplul nostru cu următorul corpus:

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

Tokenizarea fiecărui cuvânt cu scorurile lor respective este:

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

Deci, pierderea este:

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

Acum trebuie să calculăm modul în care eliminarea fiecărui token afectează pierderea. Acest lucru este destul de plictisitor, așa că îl vom face doar pentru doi tokeni aici și vom păstra întregul proces pentru atunci când vom avea cod care să ne ajute. În acest caz (foarte) special, aveam două tokenizări echivalente ale tuturor cuvintelor: după cum am văzut mai devreme, de exemplu, "pug" ar putea fi tokenizat ["p", "ug"] cu același scor. Astfel, eliminarea simbolului "pu" din vocabular va produce exact aceeași pierdere.

Pe de altă parte, eliminarea lui "hug" va agrava pierderea, deoarece tokenizarea lui "hug" și "hugs" va deveni:

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

Aceste modificări vor determina creșterea pierderii cu:

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

Prin urmare, tokenul "pu" va fi probabil eliminat din vocabular, dar nu și "hug".

Implementarea Unigram

Acum să implementăm în cod tot ceea ce am văzut până acum. Ca și în cazul BPE și WordPiece, aceasta nu este o implementare eficientă a algoritmului Unigram (dimpotrivă), dar ar trebui să vă ajute să-l înțelegeți puțin mai bine.

Vom folosi ca exemplu același corpus ca și până acum:

corpus = [
    "This is the Hugging Face Course.",
    "This chapter is about tokenization.",
    "This section shows several tokenizer algorithms.",
    "Hopefully, you will be able to understand how they are trained and generate tokens.",
]

De data aceasta, vom folosi xlnet-base-cased ca modelul nostru:

from transformers import AutoTokenizer

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

Ca și pentru BPE și WordPiece, începem prin a număra numărul de apariții ale fiecărui cuvânt în 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

Apoi, trebuie să inițializăm vocabularul nostru la ceva mai mare decât dimensiunea vocabularului pe care o vom dori la final. Trebuie să includem toate caracterele de bază (altfel nu vom putea tokeniza fiecare cuvânt), dar pentru substringurile mai mari le vom păstra doar pe cele mai comune, așa că le vom sorta după frecvență:

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
        # Loop through the subwords of length at least 2
        for j in range(i + 2, len(word) + 1):
            subwords_freqs[word[i:j]] += freq

# Sortarea subcuvintelor după frecvență
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)]

Grupăm caracterele cu cele mai bune subcuvinte pentru a ajunge la un vocabular inițial de dimensiunea 300:

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

💡 SentencePiece utilizează un algoritm mai eficient numit Enhanced Suffix Array (ESA) pentru a crea vocabularul inițial.

În continuare, calculăm suma tuturor frecvențelor, pentru a converti frecvențele în probabilități. Pentru modelul nostru, vom stoca logaritmii probabilităților, deoarece este mai stabil din punct de vedere numeric să adăugăm logaritmi decât să multiplicăm numere mici, iar acest lucru va simplifica calcularea pierderii modelului:

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

Acum funcția principală este cea care tokenizează cuvintele folosind algoritmul Viterbi. După cum am văzut mai devreme, acest algoritm calculează cea mai bună segmentare a fiecărui substring din cuvânt, pe care o vom stoca într-o variabilă numită best_segmentations. Vom stoca un dicționar pentru fiecare poziție din cuvânt (de la 0 la lungimea totală a acestuia), cu două chei: indicele de început al ultimului token din cea mai bună segmentare și scorul celei mai bune segmentări. Cu ajutorul indicelui de început al ultimului token, vom putea extrage segmentarea completă odată ce lista este complet populată.

Popularea listei se face cu doar două bucle: bucla principală trece peste fiecare poziție de început, iar a doua buclă încearcă toate subcuvintele care încep la acea poziție de început. Dacă substringul se află în vocabular, avem o nouă segmentare a cuvântului până la acea poziție finală, pe care o comparăm cu cea din best_segmentations.

Odată ce bucla principală este terminată, pornim de la sfârșit și sărim de la o poziție de început la alta, înregistrând tokenii pe parcurs, până când ajungem la începutul cuvântului:

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)):
        # This should be properly filled by the previous steps of the loop
        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
                # If we have found a better segmentation ending at end_idx, we update
                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:
        # We did not find a tokenization of the word -> unknown
        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

Putem încerca deja modelul nostru inițial pe câteva cuvinte:

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

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

Acum este ușor de calculat pierderea modelului pe 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

Putem verifica dacă funcționează pe modelul pe care îl avem:

compute_loss(model)

413.10377642940875

Nici calcularea scorurilor pentru fiecare token nu este foarte dificilă; trebuie doar să calculăm pierderea pentru modelele obținute prin ștergerea fiecărui tokeb:

import copy


def compute_scores(model):
    scores = {}
    model_loss = compute_loss(model)
    for token, score in model.items():
        # We always keep tokens of length 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

Îl putem încerca pe un token dat:

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

Deoarece "ll" este folosit în tokenizarea lui "Hopefully", iar eliminarea lui ne va face, probabil, să folosim tokenul "l" de două ori în schimb, ne așteptăm să aibă o pierdere pozitivă. "his" este folosit doar în interiorul cuvântului "This", care este tokenizat ca el însuși, deci ne așteptăm să aibă o pierdere zero. Iată rezultatele:

6.376412403623874
0.0

💡 Această abordare este foarte ineficientă, astfel încât SentencePiece utilizează o aproximare a pierderii modelului fără simbolul X: în loc să înceapă de la zero, înlocuiește simbolul X cu segmentarea sa în vocabularul rămas. În acest fel, toate scorurile pot fi calculate odată, în același timp cu pierderea modelului.

Cu toate acestea la locul lor, ultimul lucru pe care trebuie să îl facem este să adăugăm la vocabular tokeni speciali utilizate de model, apoi să facem o buclă până când am eliminat suficienți tokeni din vocabular pentru a ajunge la dimensiunea dorită:

percent_to_remove = 0.1
while len(model) > 100:
    scores = compute_scores(model)
    sorted_scores = sorted(scores.items(), key=lambda x: x[1])
    # Remove percent_to_remove tokens with the lowest scores.
    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()}

Apoi, pentru a tokeniza un text, trebuie doar să aplicăm pre-tokenizarea și apoi să folosim funcția 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', '.']

Asta e tot pentru Unigram! Sperăm că până acum vă simțiți ca un expert în toate lucrurile legate de tokenizer. În secțiunea următoare, vom aprofunda elementele de bază ale bibliotecii 🤗 Tokenizers și vă vom arăta cum le puteți utiliza pentru a vă construi propriul tokenizer.