Constrúe un tokenizador BPE: por que o teu modelo non pode contar os R

Hai dúas maneiras obvias de alimentar texto a unha rede, e ambas fallan por razóns que paga a pena entender, porque ese fallo define a forma da solución.

Palabras. Separar por espazos, asignar un número a cada palabra. O inglés ten centos de miles de formas de palabra e o modelo necesita unha fila de embedding para cada unha, así que o vocabulario —e a capa de saída, que debe producir unha puntuación para cada entrada— faise enorme. Peor aínda é o que pasa na inferencia: unha palabra que o modelo nunca viu no adestramento non ten número. Ese é o problema fóra de vocabulario, e o parche habitual é mapear todo o descoñecido a un único token <UNK>, o que tira a información. Ademais, «palabra» non é un concepto ben definido: o chinés e o xaponés non poñen espazos entre palabras, e o alemán encadea substantivos indefinidamente.

Caracteres. Sen problema fóra de vocabulario, e cun vocabulario dun cento e pico de símbolos. Pero as secuencias fanse moi longas, e o Capítulo 9 amosará que o custo de attention medra cuadraticamente coa lonxitude da secuencia. Un documento de 1000 palabras ten arredor de 5000 caracteres: unha secuencia catro ou cinco veces máis longa do necesario, cun prezo cuadrático. E cada carácter leva moi pouco significado por si só, así que as primeiras capas dedícanse a recompoñer palabras que o tokenizador podería ter entregado intactas.

A resposta está no medio: subpalabras. As palabras comúns convértense nun token, as palabras raras divídense en pezas, e nada é nunca descoñecido porque as pezas rematan, no fondo, en bytes individuais. O interesante é que ninguén deseña a división. O tokenizador adéstrase, co mesmo tipo de datos ca o modelo, e aprende que secuencias de bytes merecen o seu propio número contando cantas veces aparecen xuntas.

O algoritmo é de 1994, e era un algoritmo de compresión. Philip Gage publicouno no C Users Journal como unha forma de reducir ficheiros substituíndo repetidamente o par máis frecuente de bytes adxacentes por un byte que non aparecía nos datos.¹ Quedou aí durante vinte e dous anos ata que Sennrich, Haddow e Birch o reaproveitaron para tradución automática en 2016 para resolver o problema fóra de vocabulario.² Agora é, esencialmente, como le todo gran modelo de linguaxe.

O bucle de adestramento son catro pasos repetidos:

Aquí tes o adestrador completo:

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

Execútao sobre 151.191 bytes de prosa en inglés e imprime as doce primeiras fusións conforme suceden. Esta é a parte que convén ler amodo, porque ninguén lle contou ao algoritmo nada sobre o inglés:

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)

Hai tres cousas nesa lista que paga a pena sinalar.

A fusión 12 é a palabra «the»: co espazo antes e o espazo despois, como unha soa unidade, descuberta na duodécima iteración dun bucle que conta pares. Ninguén achegou un dicionario. Está aí porque eses cinco bytes coaparecen máis ca calquera outros cinco no inglés.

A fusión 3 non é texto en absoluto. \xe2\x80 son os dous primeiros bytes da codificación UTF-8 da puntuación tipográfica: o guión longo, as comiñas curvas. O algoritmo non ten nin idea de que UTF-8 existe, e acaba de redescubrir unha peza da súa estrutura, porque as codificacións multibyte son, por construción, secuencias de bytes que sempre aparecen xuntas.

A maioría das primeiras fusións inclúen un espazo, e o espazo adoita estar á esquerda. Esa é a orixe dun dos comportamentos máis confusos na práctica, ao que volvemos axiña.

Cada fusión fai a secuencia máis curta e o vocabulario máis grande. Ata onde levalo é unha decisión real, e pódese medir; aquí, cos mesmos 151.191 bytes:

Rendementos decrecentes, claramente. Duplicar de 512 a 1024 compra 0,78 bytes por token; duplicar de 2048 a 4096 compra 1,07 —mellor aquí só porque este corpus é pequeno dabondo para que as fusións máis longas sigan compensando. Nun corpus real, a curva achándase moito.

E o custo dun vocabulario maior non é só memoria. Cada token necesita unha fila de embedding e —máis caro aínda— a capa de saída do modelo ten que producir unha puntuación para cada entrada do vocabulario en cada paso, así que a multiplicación matricial final escala co tamaño do vocabulario. Os modelos reais móvense entre 32.000 e 200.000: GPT-2 usaba 50.257, o cl100k de GPT-4 usa 100.277, o o200k de GPT-4o case duplica iso. A tendencia é ascendente, e a razón está na seguinte sección.

Aquí está o mesmo parágrafo, traducido, medido cos tokenizadores reais que distribúe OpenAI:

O mesmo contido, o mesmo significado, e con cl100k a versión rusa consome dúas veces e media máis tokens. Como as API cobran por token e as context windows mídense en tokens, isto non é unha curiosidade lingüística: é unha liña nun orzamento, unha context window efectiva máis curta e unha resposta máis lenta, as tres cousas á vez, para todo o mundo que non traballa en inglés.

O mecanismo son os datos de adestramento. Un tokenizador adestrado sobre todo en inglés gasta o seu orzamento de fusións en secuencias de bytes do inglés. O español comparte o alfabeto latino, así que aínda recibe algo de beneficio; o ruso case ningún, porque os caracteres cirílicos ocupan dous bytes en UTF-8 e poucos deses pares foron o bastante comúns no corpus de adestramento como para gañar unha fusión. O xaponés é aínda peor: tres bytes por carácter, e 72 caracteres convértense en 79 tokens: máis tokens ca caracteres.

A columna o200k mostra que este é un problema solucionable e que se está solucionando. Duplicar o vocabulario e reequilibrar os datos de adestramento reduce o sobrecusto do español do +39 % ao +16 %, e o do ruso do +152 % ao +39 %. Esa é a verdadeira razón pola que os vocabularios seguen medrando: non a compresión por si mesma, senón o feito de que a xeración anterior lle estaba cobrando silenciosamente de máis a unha gran parte do mundo.

O adestramento produciu unha lista ordenada de fusións. Codificar texto novo reprodúcea, e debe reproducila na mesma orde, porque a fusión 12 combina os resultados das fusións 5 e 1. Aplícaas noutra orde e obterás unha tokenización distinta e incorrecta que non coincidirá con nada que o modelo vise no adestramento.

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

Decodificar é trivial en comparación: busca os bytes de cada id, concatena e decodifica como UTF-8. Observa o errors="replace": un modelo pode emitir unha secuencia de tokens que remata no medio dun carácter, e iso non é hipotético; é o que pasa cando unha resposta en streaming se corta no medio dun emoji, e por iso as API de streaming almacenan bytes parciais nun búfer en vez de decodificar token por token.

A ida e volta funciona con calquera cousa, que é a promesa do BPE a 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

Unha vez que o mecanismo está claro, un conxunto de queixas que parecían non relacionadas resultan ser a mesma queixa.

Aritmética. Os números non se dividen de ningunha maneira consistente:

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

Para sumar 1234 e 12345, o modelo primeiro debe descubrir que ['123','4'] e ['123','45'] son números cuxos díxitos se aliñan dunha maneira concreta, e o aliñamento cambia para cada par de números. Os díxitos dun número non están nos mesmos lugares dun número ao seguinte. Algúns tokenizadores máis novos obrigan os díxitos a dividirse en grupos consistentes de tres precisamente para eliminar este obstáculo, e os modelos adestrados con eles son mediblemente mellores en aritmética.

Indentación de Python.

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

Catro espazos e oito espazos son tokens únicos diferentes, e unha tabulación fúndese co carácter que a segue. A indentación, que en Python é sintaxe, represéntase de maneira inconsistente; isto explica boa parte de por que os modelos adoitaban producir Python cunha indentación sutilmente incorrecta, e por que os tokenizadores centrados en código engaden tokens explícitos para secuencias habituais de indentación.

Deletrear e inverter. A mesma causa ca contar os r: pedirlle a un modelo que inverta strawberry é pedirlle que reordene letras dentro de tres ids opacos. Os modelos fano porque memorizaron grafías durante o adestramento, non porque estean mirando, e por iso o fan ben con palabras comúns e mal con palabras raras.

Glitch tokens. O caso máis rechamante é SolidGoldMagikarp e un conxunto de cadeas similares que fixeron que GPT-2 e GPT-3 se comportasen de maneira estraña: negándose a repetilas, producindo saída non relacionada, ás veces insultando o usuario. A explicación é mundana e despréndese directamente do feito de que o tokenizador se adestra por separado do modelo: esas cadeas eran frecuentes no corpus de adestramento do tokenizador (eran nomes de usuario de Reddit), así que gañaron o seu propio token, pero eran raras ou estaban ausentes no corpus de adestramento do modelo. O resultado é unha fila de embedding que se inicializou aleatoriamente e case nunca se actualizou. O modelo ten un símbolo que, na práctica, case nunca viu, e o seu comportamento aí é o que cadrase coa inicialización aleatoria.

Un tokenizador é unha interface con perdas entre texto e números, e cada comportamento estraño deste capítulo é a interface deixándose ver. Convén ter claro que o intercambio é deliberado: o BPE a nivel de byte significa que ningunha entrada é irrepresentable, as secuencias son catro ou cinco veces máis curtas do que serían con caracteres, e as palabras comúns chegan intactas.

O prezo é que os átomos do modelo non son os nosos átomos. Razoa sobre texto que non pode deletrear, en unidades escollidas por un reconto de frecuencia sobre un corpus que el non viu, cun custo por lingua que ninguén negociou.

Agora tes unha secuencia de enteiros. Ese é o formato de entrada para todo o resto da Parte II.

O que non tes é ningunha razón para que un enteiro siga a outro. O seguinte capítulo presenta o obxectivo co que se adestra todo modelo de linguaxe, e é sorprendentemente simple: dados os tokens ata agora, predicir o seguinte. Ese único obxectivo —sen etiquetas, sen anotación, só texto co seu propio futuro como obxectivo— é o que converte toda internet en datos de adestramento, e é de onde saen as primeiras representacións xenuínas do modelo.

Tamén require que a regra da cadea da probabilidade do Capítulo 2 sexa exactamente correcta, porque a afirmación de que predicir un token cada vez é o mesmo que modelar documentos completos é unha factorización, non unha metáfora.

O Capítulo 8 é o obxectivo autorregresivo, os embeddings e o primeiro lugar onde un modelo aprende algo que ninguén puxo alí.

Kudo, T. Subword Regularization: Improving Neural Network Translation Models with Multiple Subword Candidates (arXiv:1804.10959) introduce o modelo Unigram; Kudo e Richardson, SentencePiece: A simple and language independent subword tokenizer and detokenizer for Neural Text Processing (arXiv:1808.06226) é a implementación que usan a maioría dos modelos multilingües; Schuster e Nakajima, Japanese and Korean Voice Search (ICASSP 2012) é a orixe de WordPiece. Let's build the GPT Tokenizer, de Andrej Karpathy, e o repositorio karpathy/minbpe que o acompaña son os devanceiros directos do código deste capítulo e van bastante máis alá, incluíndo a regex de GPT-4 e o manexo de special-token. O capítulo 6 do Hugging Face LLM Course cobre os tres algoritmos lado a lado con exemplos desenvolvidos.