Construiește un tokenizer BPE: de ce modelul tău nu poate număra R-urile

Există două moduri evidente de a da text unei rețele și ambele eșuează din motive care merită înțelese, pentru că eșecul definește forma soluției.

Cuvinte. Împarți după spații, atribui fiecărui cuvânt un număr. Engleza are sute de mii de forme de cuvinte, iar modelul are nevoie de un rând de embedding pentru fiecare, deci vocabularul — și stratul de ieșire, care trebuie să producă un scor pentru fiecare intrare — devine enorm. Mai rău este ce se întâmplă la inferență: un cuvânt pe care modelul nu l-a văzut niciodată la antrenare nu are număr. Aceasta este problema out-of-vocabulary, iar soluția obișnuită de avarie este să mapezi tot ce este necunoscut la un singur token <UNK>, ceea ce aruncă informația. În plus, „cuvânt” nu este un concept bine definit: chineza și japoneza nu pun spații între cuvinte, iar germana compune substantive unele peste altele la nesfârșit.

Caractere. Nu există problemă out-of-vocabulary și ai un vocabular de vreo sută și ceva de simboluri. Dar secvențele devin foarte lungi, iar Capitolul 9 va arăta că costul attention crește pătratic cu lungimea secvenței. Un document de 1000 de cuvinte are în jur de 5000 de caractere — o secvență de patru până la cinci ori mai lungă decât ar trebui, la un preț pătratic. Și fiecare caracter poartă aproape zero sens de unul singur, așa că primele câteva straturi sunt cheltuite reconstruind cuvinte pe care tokenizerul le-ar fi putut preda intacte.

Răspunsul este între ele: subwords. Cuvintele comune devin un singur token, cuvintele rare se împart în bucăți și nimic nu este vreodată necunoscut, pentru că bucățile ajung la nivelul byte-urilor individuale. Partea interesantă este că nimeni nu proiectează împărțirea. Tokenizerul este antrenat, pe același tip de date ca modelul, și învață ce secvențe de bytes merită propriul lor număr numărând cât de des apar împreună.

Algoritmul este din 1994 și era un algoritm de compresie. Philip Gage l-a publicat în C Users Journal ca metodă de a micșora fișierele înlocuind repetat cea mai frecventă pereche de bytes adiacenți cu un byte care nu apare în date.¹ A stat acolo douăzeci și doi de ani până când Sennrich, Haddow și Birch l-au refolosit pentru traducere automată în 2016, ca să rezolve problema out-of-vocabulary.² Acum este, în esență, felul în care citește fiecare model lingvistic mare.

Bucla de antrenare are patru pași repetați:

Iată întregul trainer:

def get_stats(ids):
    counts = {}
    for a, b in zip(ids, ids[1:]):
        counts[(a, b)] = counts.get((a, b), 0) + 1
    return counts


def merge(ids, pair, idx):
    out, i = [], 0
    while i < len(ids):
        if i < len(ids) - 1 and ids[i] == pair[0] and ids[i + 1] == pair[1]:
            out.append(idx)
            i += 2
        else:
            out.append(ids[i])
            i += 1
    return out


class BPE:
    def __init__(self):
        self.merges = {}
        self.vocab = {i: bytes([i]) for i in range(256)}

    def train(self, text, vocab_size):
        ids = list(text.encode("utf-8"))
        for i in range(vocab_size - 256):
            stats = get_stats(ids)
            if not stats:
                break
            pair = max(stats, key=stats.get)      
            idx = 256 + i                         
            ids = merge(ids, pair, idx)           
            self.merges[pair] = idx               
            self.vocab[idx] = self.vocab[pair[0]] + self.vocab[pair[1]]
        return ids

Rulează-l pe 151.191 de bytes de proză engleză și afișează primele douăsprezece merge-uri pe măsură ce apar. Aceasta este partea care merită citită încet, pentru că nimeni nu i-a spus algoritmului nimic despre engleză:

merge   1: b'e' + b' '   -> b'e '     (occurred 4433 times)
merge   2: b' ' + b't'   -> b' t'     (occurred 3302 times)
merge   3: b'\xe2' + b'\x80' -> b'\xe2\x80'  (occurred 3247 times)
merge   4: b' ' + b'a'   -> b' a'     (occurred 2335 times)
merge   5: b' t' + b'h'  -> b' th'    (occurred 2253 times)
merge   6: b'i' + b'n'   -> b'in'     (occurred 2011 times)
merge   7: b't' + b' '   -> b't '     (occurred 1904 times)
merge   8: b'e' + b'r'   -> b'er'     (occurred 1813 times)
merge   9: b'd' + b' '   -> b'd '     (occurred 1703 times)
merge  10: b'o' + b'u'   -> b'ou'     (occurred 1554 times)
merge  11: b' ' + b's'   -> b' s'     (occurred 1467 times)
merge  12: b' th' + b'e '-> b' the '  (occurred 1270 times)

Trei lucruri din lista aceea merită subliniate.

Merge 12 este cuvântul „the” — cu spațiul dinainte și spațiul de după el, ca o singură unitate, descoperită la a douăsprezecea iterație a unei bucle care numără perechi. Nimeni nu a furnizat un dicționar. Este acolo pentru că acei cinci bytes coapar mai des decât oricare alți cinci în engleză.

Merge 3 nu este text deloc. \xe2\x80 sunt primii doi bytes din encodarea UTF-8 a punctuației tipografice — linia de pauză, ghilimelele curbate. Algoritmul nu are habar că UTF-8 există și tocmai a redescoperit o bucată din structura lui, pentru că encodările multibyte sunt, prin construcție, secvențe de bytes care apar mereu împreună.

Majoritatea merge-urilor timpurii implică un spațiu, iar spațiul este de obicei în stânga. Asta este originea unuia dintre cele mai derutante comportamente din practică, la care revenim imediat.

Fiecare merge face secvența mai scurtă și vocabularul mai mare. Cât de departe mergi este o decizie reală și poate fi măsurată — aici pe aceiași 151.191 de bytes:

Randamente descrescătoare, vizibil. Dublarea de la 512 la 1024 cumpără 0,78 bytes per token; dublarea de la 2048 la 4096 cumpără 1,07 — mai bine aici doar pentru că acest corpus este suficient de mic încât merge-urile mai lungi încă se amortizează. Pe un corpus real, curba se aplatizează puternic.

Iar costul unui vocabular mai mare nu este doar memoria. Fiecare token are nevoie de un rând de embedding și — mai costisitor — stratul de ieșire al modelului trebuie să producă un scor pentru fiecare intrare din vocabular la fiecare pas, așa că înmulțirea matricială finală scalează cu dimensiunea vocabularului. Modelele reale stau între 32.000 și 200.000: GPT-2 a folosit 50.257, cl100k al GPT-4 folosește 100.277, o200k al GPT-4o aproape dublează asta. Tendința este ascendentă, iar motivul este în secțiunea următoare.

Iată același paragraf, tradus, măsurat cu tokenizer-ele reale livrate de OpenAI:

Același conținut, același sens, iar cu cl100k versiunea rusă consumă de două ori și jumătate mai mulți tokens. Cum API-urile facturează per token, iar context windows sunt măsurate în tokens, aceasta nu este o curiozitate lingvistică — este o linie în buget, un context window efectiv mai scurt și un răspuns mai lent, toate trei deodată, pentru oricine nu lucrează în engleză.

Mecanismul este dat de datele de antrenare. Un tokenizer antrenat mai ales pe engleză își cheltuie bugetul de merge-uri pe secvențe de bytes englezești. Spaniola împarte alfabetul latin, deci încă primește un anumit beneficiu; rusa aproape deloc, pentru că caracterele chirilice ocupă doi bytes în UTF-8 și puține dintre acele perechi au fost suficient de comune în corpusul de antrenare ca să merite un merge. Japoneza este și mai rău: trei bytes per caracter, iar 72 de caractere devin 79 de tokens — mai mulți tokens decât caractere.

Coloana o200k arată că aceasta este o problemă rezolvabilă și că este în curs de rezolvare. Dublarea vocabularului și reechilibrarea datelor de antrenare reduc overhead-ul spaniol de la +39 % la +16 %, iar pe cel rus de la +152 % la +39 %. Acesta este motivul real pentru care vocabularul tot crește: nu compresia de dragul compresiei, ci faptul că generația anterioară taxa în tăcere o mare parte a lumii în plus.

Antrenarea a produs o listă ordonată de merge-uri. Encodarea textului nou o redă — și trebuie să o redea în aceeași ordine, pentru că merge 12 combină rezultatele merge-urilor 5 și 1. Aplică-le într-o altă ordine și obții o tokenizare diferită, greșită, care nu se va potrivi cu nimic din ce a văzut modelul la antrenare.

    def encode(self, text):
        ids = list(text.encode("utf-8"))
        while len(ids) >= 2:
            stats = get_stats(ids)
            # the pair whose merge came FIRST during training wins   
            pair = min(stats, key=lambda p: self.merges.get(p, float("inf")))   
            if pair not in self.merges:
                break
            ids = merge(ids, pair, self.merges[pair])
        return ids

    def decode(self, ids):
        return b"".join(self.vocab[i] for i in ids).decode("utf-8", errors="replace")

Decodarea este trivială prin comparație: cauți bytes ai fiecărui id, concatenezi, decodezi ca UTF-8. Observă errors="replace": un model poate emite o secvență de token care se termină în mijlocul unui caracter, iar asta nu este ipotetic — este ce se întâmplă când un răspuns streaming este tăiat în mijlocul unui emoji, motiv pentru care API-urile de streaming bufferizează bytes parțiali în loc să decodeze token cu token.

Round-tripping funcționează pe orice, iar aceasta este promisiunea BPE la nivel de byte:

'strawberry'                            -> 6 tokens, decode == original: True
'Alice was beginning to get very tired' -> 14 tokens, decode == original: True
'café — naïve — 日本語'                   -> 23 tokens, decode == original: True

Odată ce mecanismul este clar, un set de nemulțumiri aparent fără legătură se dovedește a fi aceeași nemulțumire.

Aritmetică. Numerele nu sunt împărțite în niciun fel consecvent:

1234     -> 2 tokens  ['123', '4']
12345    -> 2 tokens  ['123', '45']
1000000  -> 3 tokens  ['100', '000', '0']
3.14159  -> 4 tokens  ['3', '.', '141', '59']
2024     -> 2 tokens  ['202', '4']

Ca să adauge 1234 și 12345, modelul trebuie mai întâi să își dea seama că ['123','4'] și ['123','45'] sunt numere ale căror cifre se aliniază într-un anumit fel — iar alinierea diferă pentru fiecare pereche de numere. Cifrele unui număr nu sunt în aceleași locuri de la un număr la altul. Unele tokenizer-e mai noi forțează cifrele să se împartă în grupuri consecvente de trei tocmai ca să elimine acest obstacol, iar modelele antrenate cu acestea sunt măsurabil mai bune la aritmetică.

Indentarea în Python.

'    x = 1'      -> 5 tokens  ['   ', ' x', ' =', ' ', '1']
'        x = 1'  -> 5 tokens  ['       ', ' x', ' =', ' ', '1']
'\tx = 1'        -> 4 tokens  ['\tx', ' =', ' ', '1']

Patru spații și opt spații sunt tokens unici diferiți, iar un tab este fuzionat cu caracterul de după el. Indentarea, care în Python este sintaxă, este reprezentată inconsecvent — ceea ce explică în mare parte de ce modelele obișnuiau să producă Python cu indentare subtil greșită și de ce tokenizer-ele orientate spre cod adaugă tokens expliciți pentru secvențe comune de indentare.

Ortografie și inversare. Aceeași cauză ca la numărarea literelor r: să ceri unui model să inverseze strawberry înseamnă să îi ceri să reordoneze litere în interiorul a trei id-uri opace. Modelele fac asta pentru că au memorat scrieri în timpul antrenării, nu uitându-se la litere, motiv pentru care o fac bine pentru cuvinte comune și prost pentru cele rare.

Glitch tokens. Cel mai izbitor caz este SolidGoldMagikarp și un set de șiruri similare care au făcut GPT-2 și GPT-3 să se comporte bizar — refuzând să le repete, producând output fără legătură, uneori insultând utilizatorul. Explicația este banală și urmează direct din faptul că tokenizerul este antrenat separat de model: acele șiruri erau frecvente în corpusul de antrenare al tokenizerului (erau nume de utilizatori Reddit), deci și-au câștigat propriul token, dar erau rare sau absente în corpusul de antrenare al modelului. Rezultatul este un rând de embedding inițializat aleator și aproape niciodată actualizat. Modelul are un simbol pe care, practic, nu l-a văzut niciodată, iar comportamentul său acolo este orice s-a întâmplat să iasă din inițializarea aleatoare.

Un tokenizer este o interfață cu pierderi între text și numere, iar fiecare comportament ciudat din acest capitol este interfața care se vede. Merită spus clar că schimbul este deliberat: BPE la nivel de byte înseamnă că niciun input nu este vreodată nereprezentabil, secvențele sunt de patru până la cinci ori mai scurte decât ar fi caracterele, iar cuvintele comune sosesc intacte.

Prețul este că atomii modelului nu sunt atomii noștri. Raționează despre text pe care nu îl poate silabisi, în unități alese de o numărătoare de frecvență peste un corpus pe care nu l-a văzut, cu un cost pe limbă pe care nimeni nu l-a negociat.

Acum ai o secvență de întregi. Acesta este formatul de input pentru tot ce urmează în restul Părții II.

Ce nu ai este vreun motiv ca un întreg să urmeze altuia. Capitolul următor introduce obiectivul pe care este antrenat fiecare model lingvistic și este surprinzător de simplu: date fiind tokens de până acum, prezice-l pe următorul. Acest unic obiectiv — fără etichete, fără adnotare, doar text cu propriul viitor drept țintă — este ceea ce transformă întregul internet în date de antrenare și este locul de unde vin primele reprezentări autentice ale modelului.

Mai cere și ca regula lanțului din probabilitate din Capitolul 2 să fie exact corectă, pentru că afirmația că prezicerea unui token pe rând este același lucru cu modelarea documentelor întregi este o factorizare, nu o metaforă.

Capitolul 8 este obiectivul autoregresiv, embeddings și primul loc în care un model învață ceva ce nimeni nu a pus acolo.

Kudo, T. Subword Regularization: Improving Neural Network Translation Models with Multiple Subword Candidates (arXiv:1804.10959) introduce modelul Unigram; Kudo și Richardson, SentencePiece: A simple and language independent subword tokenizer and detokenizer for Neural Text Processing (arXiv:1808.06226) este implementarea pe care o folosesc majoritatea modelelor multilingve; Schuster și Nakajima, Japanese and Korean Voice Search (ICASSP 2012) este originea WordPiece. Let's build the GPT Tokenizer al lui Andrej Karpathy și repository-ul karpathy/minbpe care îl însoțește sunt strămoșii direcți ai codului din acest capitol și merg considerabil mai departe, incluzând regexul GPT-4 și gestionarea special-token. Capitolul 6 din Hugging Face LLM Course acoperă cei trei algoritmi unul lângă altul, cu exemple lucrate.