Sestavte BPE tokenizér: proč váš model neumí spočítat R

Existují dva zjevné způsoby, jak síti předložit text, a oba selhávají z důvodů, kterým stojí za to rozumět, protože právě toto selhání určuje tvar řešení.

Slova. Rozdělit podle mezer, každému slovu přiřadit číslo. Angličtina má stovky tisíc slovních tvarů a model potřebuje řádek embedding pro každý z nich, takže slovník — a výstupní vrstva, která musí vyprodukovat skóre pro každou položku — naroste do obřích rozměrů. Horší je, co se stane při inferenci: slovo, které model během tréninku nikdy neviděl, nemá číslo. To je problém out-of-vocabulary a obvyklou záplatou je namapovat všechno neznámé na jediný <UNK> token, čímž se informace zahodí. Navíc „slovo“ není dobře definovaný pojem: čínština a japonština nedávají mezi slova mezery a němčina může donekonečna skládat jedno podstatné jméno k druhému.

Znaky. Žádný problém out-of-vocabulary a slovník o zhruba stovce symbolů. Jenže sekvence jsou velmi dlouhé a kapitola 9 ukáže, že náklady na attention rostou kvadraticky s délkou sekvence. Dokument o 1000 slovech má kolem 5000 znaků — sekvenci čtyřikrát až pětkrát delší, než je nutné, za kvadratickou cenu. A každý znak sám o sobě nese skoro nulový význam, takže prvních pár vrstev se spotřebuje na znovuskládání slov, která mohl tokenizér předat už hotová.

Odpověď leží mezi nimi: subwords. Běžná slova se stanou jedním token, vzácná slova se rozdělí na části a nic nikdy není neznámé, protože části končí až u jednotlivých bajtů. Zajímavé je, že rozdělení nikdo nenavrhuje ručně. Tokenizér se trénuje na stejném typu dat jako model a učí se, které bajtové sekvence si zaslouží vlastní číslo, tím, že počítá, jak často se vyskytují společně.

Algoritmus pochází z roku 1994 a byl to kompresní algoritmus. Philip Gage ho publikoval v C Users Journal jako způsob, jak zmenšovat soubory opakovaným nahrazováním nejčastější dvojice sousedních bajtů bajtem, který se v datech nevyskytuje.¹ Ležel tam dvaadvacet let, než ho Sennrich, Haddow a Birch v roce 2016 použili pro strojový překlad k řešení problému out-of-vocabulary.² Dnes je to v podstatě způsob, jakým čte každý velký jazykový model.

Trénovací smyčka jsou čtyři opakované kroky:

Tady je celý trenér:

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

Spusťte ho na 151 191 bajtech anglické prózy a vypište prvních dvanáct sloučení tak, jak vznikají. Tohle je část, kterou se vyplatí číst pomalu, protože algoritmu nikdo neřekl nic o angličtině:

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)

Na tomto seznamu stojí za vypíchnutí tři věci.

Sloučení 12 je slovo „the“ — s mezerou před ním i mezerou za ním, jako jedna jednotka, objevená ve dvanácté iteraci smyčky, která počítá dvojice. Nikdo nedodal slovník. Je tam proto, že těchto pět bajtů se v angličtině společně vyskytuje častěji než jakýchkoli jiných pět.

Sloučení 3 vůbec není text. \xe2\x80 jsou první dva bajty UTF-8 kódování typografické interpunkce — dlouhé pomlčky, zakroucených uvozovek. Algoritmus nemá ponětí, že UTF-8 existuje, a právě znovuobjevil část jeho struktury, protože vícebajtová kódování jsou z konstrukce sekvence bajtů, které se vždy objevují společně.

Většina raných sloučení zahrnuje mezeru a mezera je obvykle vlevo. To je původ jednoho z nejmatoucích praktických chování, ke kterému se brzy vrátíme.

Každé sloučení zkracuje sekvenci a zvětšuje slovník. Jak daleko zajít, je skutečné rozhodnutí a dá se měřit — zde na stejných 151 191 bajtech:

Viditelně klesající výnosy. Zdvojnásobení z 512 na 1024 koupí 0,78 bajtu na token; zdvojnásobení z 2048 na 4096 koupí 1,07 — tady lepší jen proto, že tento korpus je dost malý na to, aby se delší sloučení ještě vyplácela. Na reálném korpusu se křivka prudce zploští.

A cena většího slovníku není jen paměť. Každý token potřebuje řádek embedding a — ještě nákladněji — výstupní vrstva modelu musí v každém kroku vyprodukovat skóre pro každou položku ve slovníku, takže závěrečné násobení matic škáluje s velikostí slovníku. Reálné modely se pohybují mezi 32 000 a 200 000: GPT-2 používal 50 257, cl100k od GPT-4 používá 100 277, o200k od GPT-4o to zhruba zdvojnásobuje. Trend míří nahoru a důvod je v další části.

Tady je stejný odstavec v překladu, změřený skutečnými tokenizéry, které dodává OpenAI:

Stejný obsah, stejný význam, a s cl100k ruská verze spotřebuje dvaapůlkrát víc tokens. Protože API účtují podle token a context window se měří v token, není to jazyková kuriozita — je to řádek v rozpočtu, kratší efektivní context window a pomalejší odpověď, všechno najednou, pro každého, kdo nepracuje v angličtině.

Mechanismus spočívá v trénovacích datech. Tokenizér trénovaný převážně na angličtině utratí svůj rozpočet sloučení za anglické bajtové sekvence. Španělština sdílí latinku, takže z toho ještě něco má; ruština skoro nic, protože znaky cyrilice berou v UTF-8 dva bajty a jen málo z těchto dvojic bylo v trénovacím korpusu dost běžných na to, aby si vysloužily sloučení. Japonština je na tom ještě hůř: tři bajty na znak a 72 znaků se stane 79 tokens — více tokens než znaků.

Sloupec o200k ukazuje, že je to řešitelný problém a že se řeší. Zdvojnásobení slovníku a vyvážení trénovacích dat snižuje španělskou režii z +39 % na +16 % a ruskou z +152 % na +39 %. To je skutečný důvod, proč slovníky dál rostou: ne komprese pro kompresi samotnou, ale fakt, že předchozí generace potichu účtovala velké části světa přirážku.

Trénování vytvořilo seřazený seznam sloučení. Kódování nového textu ho přehrává — a musí ho přehrát ve stejném pořadí, protože sloučení 12 kombinuje výsledky sloučení 5 a 1. Použijte je v jiném pořadí a dostanete jinou, špatnou tokenizaci, která nebude odpovídat ničemu, co model viděl při trénování.

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

Dekódování je ve srovnání s tím triviální: vyhledejte bajty každého id, spojte je, dekódujte jako UTF-8. Všimněte si errors="replace": model může emitovat sekvenci tokens, která končí uprostřed znaku, a není to hypotetické — přesně to se děje, když se streamovaná odpověď usekne uprostřed emoji. Proto streamovací API bufferují neúplné bajty místo toho, aby dekódovala token po token.

Round-trip funguje na čemkoli, což je slib bajtového BPE:

'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

Jakmile je mechanismus jasný, ukáže se, že sada zdánlivě nesouvisejících stížností je ve skutečnosti jedna a tatáž stížnost.

Aritmetika. Čísla se nerozdělují nijak konzistentně:

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']

Aby model sečetl 1234 a 12345, musí nejdřív přijít na to, že ['123','4'] a ['123','45'] jsou čísla, jejichž číslice se mají zarovnat určitým způsobem — a toto zarovnání se liší pro každou dvojici čísel. Číslice čísla nejsou u různých čísel na stejných místech. Některé novější tokenizéry nutí číslice dělit se do konzistentních skupin po třech právě proto, aby tuto překážku odstranily, a modely trénované s nimi jsou v aritmetice měřitelně lepší.

Odsazení v Pythonu.

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

Čtyři mezery a osm mezer jsou odlišné samostatné tokens a tabulátor je spojený se znakem po něm. Odsazení, které je v Pythonu syntaxe, je reprezentováno nekonzistentně — což je velká část důvodu, proč modely dříve vytvářely Python s nenápadně špatným odsazením, a proč tokenizéry zaměřené na kód přidávají explicitní tokens pro běžné běhy odsazení.

Hláskování a obracení. Stejná příčina jako počítání písmen r: požádat model, aby obrátil strawberry, znamená požádat ho, aby přeuspořádal písmena uvnitř tří neprůhledných id. Modely to dělají tak, že si během tréninku zapamatovaly pravopis, ne tím, že se dívají, a proto jim to jde dobře u běžných slov a špatně u vzácných.

Glitch tokens. Nejvýraznější případ je SolidGoldMagikarp a sada podobných řetězců, kvůli nimž se GPT-2 a GPT-3 chovaly bizarně — odmítaly je opakovat, produkovaly nesouvisející výstup, někdy uživatele urážely. Vysvětlení je všední a plyne přímo z faktu, že tokenizér se trénuje odděleně od modelu: tyto řetězce byly časté v trénovacím korpusu tokenizéru (byla to uživatelská jména z Redditu), takže si vysloužily vlastní token, ale v trénovacím korpusu modelu byly vzácné nebo chyběly. Výsledkem je řádek embedding, který byl inicializován náhodně a skoro nikdy aktualizován. Model má symbol, který v podstatě nikdy neviděl, a jeho chování v tomto místě je takové, jaké náhodná inicializace zrovna způsobila.

Tokenizér je ztrátové rozhraní mezi textem a čísly a každé zvláštní chování v této kapitole je jen místo, kde toto rozhraní prosvítá. Stojí za to říct jasně, že jde o záměrný obchod: bajtové BPE znamená, že žádný vstup nikdy není nereprezentovatelný, sekvence jsou čtyřikrát až pětkrát kratší, než by byly znaky, a běžná slova dorazí vcelku.

Cena je, že atomy modelu nejsou naše atomy. Uvažuje o textu, který neumí vyhláskovat, v jednotkách zvolených frekvenčním počtem nad korpusem, který neviděl, s náklady podle jazyka, o nichž nikdo nevyjednával.

Teď máte sekvenci celých čísel. To je vstupní formát pro všechno ve zbytku části II.

Nemáte ale žádný důvod, proč by jedno celé číslo mělo následovat po druhém. Další kapitola představí cíl, na kterém se trénuje každý jazykový model, a je překvapivě jednoduchý: na základě dosavadních tokens předpovědět další. Tento jediný cíl — žádné štítky, žádné anotace, jen text se svou vlastní budoucností jako target — promění celý internet v trénovací data a právě odtud pocházejí první skutečné reprezentace modelu.

Vyžaduje to také, aby řetězové pravidlo pravděpodobnosti z kapitoly 2 bylo přesně správně, protože tvrzení, že předpovídat jeden token po druhém je totéž jako modelovat celé dokumenty, je faktorizace, ne metafora.

Kapitola 8 je autoregresivní cíl, embeddings a první místo, kde se model naučí něco, co tam nikdo nevložil.

Kudo, T. Subword Regularization: Improving Neural Network Translation Models with Multiple Subword Candidates (arXiv:1804.10959) představuje model Unigram; Kudo a Richardson, SentencePiece: A simple and language independent subword tokenizer and detokenizer for Neural Text Processing (arXiv:1808.06226) je implementace, kterou používá většina vícejazyčných modelů; Schuster a Nakajima, Japanese and Korean Voice Search (ICASSP 2012) je původ WordPiece. Let's build the GPT Tokenizer od Andreje Karpathyho a doprovodný repozitář karpathy/minbpe jsou přímými předky kódu v této kapitole a jdou podstatně dál, včetně regex GPT-4 a práce se special-token. Kapitola 6 kurzu Hugging Face LLM Course probírá všechny tři algoritmy vedle sebe na řešených příkladech.