Zbuduj BPE Tokenizer: dlaczego model nie umie policzyć liter R

Istnieją dwa oczywiste sposoby podania tekstu sieci i oba zawodzą z powodów, które warto zrozumieć, bo ta porażka definiuje kształt rozwiązania.

Słowa. Podziel tekst po spacjach, przypisz każdemu słowu liczbę. Angielski ma setki tysięcy form wyrazowych, a model potrzebuje wiersza embedding dla każdej z nich, więc vocabulary — oraz warstwa wyjściowa, która musi wygenerować wynik dla każdego wpisu — robi się ogromne. Jeszcze gorsze jest to, co dzieje się przy inference: słowo, którego model nigdy nie widział podczas treningu, nie ma numeru. To problem out-of-vocabulary, a typową łatą jest mapowanie wszystkiego, co nieznane, na jeden token <UNK>, co wyrzuca informację. Do tego „słowo” nie jest pojęciem dobrze zdefiniowanym: chiński i japoński nie stawiają spacji między słowami, a niemiecki potrafi doklejać rzeczownik do rzeczownika w nieskończoność.

Znaki. Nie ma problemu out-of-vocabulary, a vocabulary ma około stu symboli. Ale sekwencje stają się bardzo długie, a rozdział 9 pokaże, że koszt attention rośnie kwadratowo wraz z długością sekwencji. Dokument na 1000 słów to około 5000 znaków — sekwencja cztery do pięciu razy dłuższa niż musi być, za kwadratową cenę. A każdy znak sam w sobie niesie prawie zerowe znaczenie, więc pierwsze warstwy zużywają się na ponowne składanie słów, które tokenizer mógłby przekazać w całości.

Odpowiedź leży pośrodku: subwords. Częste słowa stają się jednym token, rzadkie słowa dzielą się na kawałki, a nic nigdy nie jest nieznane, bo kawałki schodzą aż do pojedynczych bytes. Najciekawsze jest to, że nikt nie projektuje tego podziału. Tokenizer jest trenowany na takim samym rodzaju danych jak model i uczy się, które sekwencje bytes zasługują na własny numer, zliczając, jak często występują razem.

Algorytm pochodzi z 1994 roku i był algorytmem kompresji. Philip Gage opublikował go w C Users Journal jako sposób zmniejszania plików przez wielokrotne zastępowanie najczęstszej pary sąsiadujących bytes takim byte, który nie występuje w danych.¹ Leżał tam przez dwadzieścia dwa lata, aż Sennrich, Haddow i Birch w 2016 roku przerobili go na potrzeby tłumaczenia maszynowego, aby rozwiązać problem out-of-vocabulary.² Dziś tak właśnie czyta zasadniczo każdy duży model językowy.

Pętla treningowa to cztery powtarzane kroki:

Oto cały 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

Uruchom go na 151 191 bytes angielskiej prozy i wypisz pierwsze dwanaście merges w chwili, gdy powstają. Tę część warto czytać powoli, bo nikt nie powiedział algorytmowi nic o angielskim:

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)

W tej liście warto wskazać trzy rzeczy.

Merge 12 to słowo „the” — ze spacją przed nim i spacją po nim, jako jedna jednostka, odkryta w dwunastej iteracji pętli, która liczy pary. Nikt nie dostarczył słownika. Jest tam dlatego, że te pięć bytes współwystępuje w angielskim częściej niż jakiekolwiek inne pięć.

Merge 3 wcale nie jest tekstem. \xe2\x80 to pierwsze dwa bytes kodowania UTF-8 interpunkcji typograficznej — półpauzy, cudzysłowów drukarskich. Algorytm nie ma pojęcia, że istnieje UTF-8, a właśnie ponownie odkrył fragment jego struktury, bo kodowania wielobajtowe z definicji są sekwencjami bytes, które zawsze występują razem.

Większość wczesnych merges obejmuje spację, a spacja zwykle znajduje się po lewej. To źródło jednego z najbardziej mylących zachowań w praktyce; wrócimy do niego za chwilę.

Każdy merge skraca sekwencję i powiększa vocabulary. Jak daleko to pchać, to realna decyzja, którą można zmierzyć — tutaj na tych samych 151 191 bytes:

Malejące korzyści — widać je gołym okiem. Podwojenie z 512 do 1024 daje 0,78 byte na token; podwojenie z 2048 do 4096 daje 1,07 — tutaj lepiej tylko dlatego, że corpus jest na tyle mały, iż dłuższe merges wciąż się opłacają. Na prawdziwym corpus krzywa mocno się wypłaszcza.

A koszt większego vocabulary to nie tylko pamięć. Każdy token potrzebuje wiersza embedding i — co droższe — warstwa wyjściowa modelu musi wygenerować wynik dla każdego wpisu w vocabulary na każdym kroku, więc końcowe mnożenie macierzy skaluje się z rozmiarem vocabulary. Prawdziwe modele mieszczą się między 32 000 a 200 000: GPT-2 używał 50 257, cl100k w GPT-4 używa 100 277, a o200k w GPT-4o mniej więcej to podwaja. Trend jest wzrostowy, a przyczyna znajduje się w następnej sekcji.

Oto ten sam akapit, przetłumaczony i zmierzony prawdziwymi tokenizers dostarczanymi przez OpenAI:

Ta sama treść, to samo znaczenie, a przy cl100k wersja rosyjska zużywa dwa i pół razy więcej tokens. Skoro API rozliczają za token, a context windows mierzy się w tokens, nie jest to językowa ciekawostka — to pozycja w budżecie, krótsze efektywne context window i wolniejsza odpowiedź, wszystko naraz, dla każdego, kto nie pracuje po angielsku.

Mechanizm tkwi w danych treningowych. Tokenizer trenowany głównie na angielskim wydaje swój budżet merges na angielskie sekwencje bytes. Hiszpański współdzieli alfabet łaciński, więc nadal coś zyskuje; rosyjski prawie nic, bo cyrylica zajmuje w UTF-8 dwa bytes, a niewiele z tych par było w corpus treningowym na tyle częstych, by zasłużyć na merge. Japoński ma jeszcze gorzej: trzy bytes na znak, a 72 znaki stają się 79 tokens — więcej tokens niż znaków.

Kolumna o200k pokazuje, że to problem rozwiązywalny i że faktycznie jest rozwiązywany. Podwojenie vocabulary i zrównoważenie danych treningowych obcina hiszpański narzut z +39 % do +16 %, a rosyjski z +152 % do +39 %. To prawdziwy powód, dla którego vocabularies wciąż rosną: nie kompresja dla samej kompresji, lecz fakt, że poprzednia generacja po cichu doliczała sporą część świata do rachunku.

Trening wyprodukował uporządkowaną listę merges. Kodowanie nowego tekstu ją odtwarza — i musi odtwarzać ją w tej samej kolejności, bo merge 12 łączy wyniki merges 5 i 1. Zastosuj je w innej kolejności, a dostaniesz inną, błędną tokenizację, która nie będzie odpowiadać niczemu, co model widział podczas treningu.

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

Dekodowanie jest w porównaniu z tym trywialne: znajdź bytes dla każdego id, sklej je i zdekoduj jako UTF-8. Zwróć uwagę na errors="replace": model może wyemitować sekwencję tokens kończącą się w połowie znaku, i to nie jest hipotetyczne — tak dzieje się, gdy streaming response zostanie ucięta w środku emoji, dlatego streaming APIs buforują częściowe bytes zamiast dekodować token po token.

Round-trip działa na wszystkim, i to jest obietnica byte-level 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

Gdy mechanizm jest jasny, zestaw pozornie niezwiązanych narzekań okazuje się jednym i tym samym narzekaniem.

Arytmetyka. Liczby nie są dzielone w żaden spójny sposób:

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

Żeby dodać 1234 i 12345, model musi najpierw ustalić, że ['123','4'] i ['123','45'] są liczbami, których cyfry wyrównują się w określony sposób — a wyrównanie różni się dla każdej pary liczb. Cyfry liczby nie znajdują się w tych samych miejscach od jednej liczby do następnej. Niektóre nowsze tokenizers wymuszają podział cyfr na spójne grupy po trzy właśnie po to, by usunąć tę przeszkodę, a modele trenowane z nimi są mierzalnie lepsze w arytmetyce.

Wcięcia w Pythonie.

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

Cztery spacje i osiem spacji to różne pojedyncze tokens, a tabulator jest zlepiony ze znakiem po nim. Wcięcia, które w Pythonie są składnią, są reprezentowane niespójnie — to duża część powodu, dla którego modele dawniej generowały Pythona z subtelnie błędnymi wcięciami, oraz powód, dla którego tokenizers ukierunkowane na kod dodają jawne tokens dla częstych ciągów wcięć.

Pisownia i odwracanie. Ta sama przyczyna co przy liczeniu liter r: prośba do modelu, by odwrócił strawberry, to prośba, by przestawił litery wewnątrz trzech nieprzezroczystych ids. Modele robią to dzięki zapamiętanym pisowniom z treningu, a nie dzięki patrzeniu, dlatego radzą sobie dobrze z częstymi słowami i słabo z rzadkimi.

Glitch tokens. Najbardziej uderzającym przypadkiem jest SolidGoldMagikarp i zestaw podobnych stringów, które sprawiały, że GPT-2 i GPT-3 zachowywały się dziwacznie — odmawiały ich powtórzenia, produkowały niezwiązany output, czasem obrażały użytkownika. Wyjaśnienie jest przyziemne i wynika wprost z faktu, że tokenizer jest trenowany osobno od modelu: te stringi były częste w corpus treningowym tokenizera (były nazwami użytkowników Reddita), więc dostały własny token, ale były rzadkie albo nieobecne w corpus treningowym modelu. Wynikiem jest wiersz embedding, który został zainicjalizowany losowo i prawie nigdy nie był aktualizowany. Model ma symbol, którego właściwie nigdy nie widział, więc jego zachowanie w tym miejscu jest tym, co akurat wynikło z losowej inicjalizacji.

Tokenizer jest stratnym interfejsem między tekstem a liczbami, a każde dziwne zachowanie w tym rozdziale to prześwitujący interfejs. Warto powiedzieć jasno, że ten kompromis jest celowy: byte-level BPE oznacza, że żaden input nigdy nie jest niereprezentowalny, sekwencje są cztery do pięciu razy krótsze niż byłyby przy znakach, a częste słowa trafiają do modelu w całości.

Cena polega na tym, że atomy modelu nie są naszymi atomami. Rozumuje on o tekście, którego nie potrafi przeliterować, w jednostkach wybranych przez zliczanie częstości na corpus, którego nie widział, z kosztem per język, którego nikt nie negocjował.

Masz teraz sekwencję liczb całkowitych. To format input dla wszystkiego w pozostałej części części II.

Nie masz natomiast żadnego powodu, by jedna liczba następowała po drugiej. Następny rozdział wprowadza cel, na którym trenowany jest każdy model językowy, i jest on zaskakująco prosty: mając dotychczasowe tokens, przewiduj następny. Ten jeden cel — bez etykiet, bez anotacji, tylko tekst z własną przyszłością jako target — zamienia cały internet w dane treningowe i właśnie stąd biorą się pierwsze autentyczne reprezentacje modelu.

Wymaga to też, aby reguła łańcuchowa prawdopodobieństwa z rozdziału 2 była dokładnie poprawna, bo twierdzenie, że przewidywanie jednego token naraz jest tym samym co modelowanie całych dokumentów, jest faktoryzacją, nie metaforą.

Rozdział 8 dotyczy celu autoregresyjnego, embeddings i pierwszego miejsca, w którym model uczy się czegoś, czego nikt tam nie włożył.

Kudo, T. Subword Regularization: Improving Neural Network Translation Models with Multiple Subword Candidates (arXiv:1804.10959) wprowadza model Unigram; Kudo i Richardson, SentencePiece: A simple and language independent subword tokenizer and detokenizer for Neural Text Processing (arXiv:1808.06226) to implementacja używana przez większość modeli multilingual; Schuster i Nakajima, Japanese and Korean Voice Search (ICASSP 2012) to źródło WordPiece. Let's build the GPT Tokenizer Andreja Karpathy’ego i towarzyszące repozytorium karpathy/minbpe są bezpośrednimi przodkami kodu w tym rozdziale i idą znacznie dalej, w tym w regex GPT-4 i obsługę special-token. Rozdział 6 kursu Hugging Face LLM Course omawia trzy algorytmy obok siebie na przepracowanych przykładach.