BPE de verdad: fusionar, no solo partir

Cuántos tokens tiene una frase, y qué es cada uno, no lo decide la red: lo decide el tokenizador, antes de que la red vea nada. El curso anterior explicó en su lección sobre tokenizaciónDeep Learning para NLP: del Perceptrón al TransformerBloque 1 · Lección 2Tokenización: palabras, caracteres, subpalabrasAntes de decidir qué vector le corresponde a una unidad hay que decidir cuál es la unidad. Esa elección fija el tamaño del vocabulario, la longitud de las secuencias y qué significa que una palabra sea nueva. por qué los modelos de verdad cortan por debajo de la palabra, y la lección sobre el modelo de lenguaje causalBloque 1 · Lección 1Una sola columna: el modelo de lenguaje causalEl curso anterior eligió una columna del Transformer, le puso la máscara en todos los bloques y le pidió el token siguiente, posición a posición. Esta lección hace la pregunta que aquél no hizo, qué probabilidad le da ese modelo a un texto entero, y de la respuesta sale todo lo demás: la regla de la cadena convierte esa probabilidad, sin perder nada, en un producto de condicionales; la máscara causal es lo que permite calcular las T de una ventana en una sola pasada; y la pérdida es el logaritmo de ese producto, cambiado de signo y repartido por token. Sin código a propósito: la cuenta se hace a mano sobre una ventana de cuatro palabras, y sale un dieciseisavo por los dos caminos. escribió la probabilidad de un texto como un producto con un factor por token, contado con palabras enteras porque cabían en una hoja de papel. Ninguna de las dos construyó el tokenizador.

Esta lección lo construye, y es el que usa el mini-GPT de este bloque. Tiene que elegir unos cientos de trozos entre todas las cadenas posibles del español sin que nadie le diga qué es una sílaba o un sufijo, y el procedimiento que lo consigue cabe en una línea: cuenta los pares de vecinos, fusiona el más frecuente, repite. Se llama byte-pair encoding (BPE), y de esa línea salen tres cosas que la lección deja demostradas. Ningún texto se queda sin tokens, ni siquiera uno escrito en otro alfabeto. Cada fusión cambia una entrada más del vocabulario por menos tokens en cada texto, y cada vez a peor precio. Y lo que el algoritmo encuentra no son las unidades de la lengua, sino las del corpus.

Empieza por abajo del todo. Un texto guardado en un fichero no está hecho de letras sino de bytes, números entre 0 y 255, y la codificación que usa casi todo el mundo, UTF-8 (Unicode Transformation Format, 8 bits), escribe cada carácter con entre uno y cuatro. Una letra sin tilde ocupa uno; la ñ, dos, el 195 y el 177; un emoji, cuatro. Tomar los 256 bytes como vocabulario de partida resuelve de golpe lo que el curso anterior arreglaba con <UNK>: cualquier texto, en cualquier idioma, es una secuencia de bytes, así que ninguno se queda fuera. El precio es la longitud. Con un token por byte, El señor dijo que la canción era pequeña. son 44 tokens, y dos de ellos son una ñ partida por la mitad.

BPE compra longitud con vocabulario. Recorre el corpus y cuenta cuántas veces aparece cada par de tokens vecinos; convierte el más frecuente en un token nuevo, sustituye por él todas sus apariciones y el vocabulario gana una entrada. Después vuelve a contar, porque los pares han cambiado, y repite tantas veces como entradas quieras. Antes de nada corta el texto en pre-tokens: una palabra con el espacio que la precede, un número, un tramo de signos. Ninguna fusión cruza de un pre-token al siguiente, y por eso los tokens del mini-GPT empiezan a menudo por espacio ( de, que) y ninguno junta el final de una palabra con el principio de otra.

El explorable lo hace delante de ti sobre un corpus de tres frases, lo bastante corto para leerlo entero y comprobar las cuentas: el recuadro del centro enseña, antes de cada paso, los tres pares más frecuentes, con su $f$. Avanza fusión a fusión y mira tres cosas. La primera fusión junta los dos bytes de la ñ, que sale diez veces y es el par más frecuente de todos. En la 17 el corpus ya tiene ción, y nadie se lo ha enseñado. Y la frase de abajo, que el corpus no contiene, baja de 42 bytes a 22 tokens, con pequeña y enseñó cortadas en trozos que el corpus sí tenía. Después escribe una frase tuya.

Fíjate en lo que el algoritmo no sabe. No sabe qué es una letra: la ñ sale entera porque sus dos bytes siempre van juntos, no porque formen un carácter, y en la lista del mini-GPT hay tres tokens que cortan un carácter por la mitad. Tampoco sabe qué es un sufijo: ción aparece porque esas letras vienen juntas a menudo, y en ese orden. Todo lo que encuentra lo encuentra contando.

Contar pares y fusionar el más frecuente

Fijemos el corpus como una secuencia de tokens $x_1, \dots, x_T$, cortada en pre-tokens, y empecemos con $V_0 = \{0, \dots, 255\}$: cada token es un byte, y $T$ es la longitud del corpus en bytes, que llamaremos $n$. La frecuencia de un par de tokens $(a, b)$ es cuántas veces aparece $a$ seguido de $b$ dentro de un mismo pre-token:

La fusión $i$ elige el par más frecuente,

con los empates resueltos a favor del par de ids menores: una regla arbitraria, pero fija, que hace que dos ejecuciones den el mismo vocabulario. Crea una entrada nueva, $u_i$, cuyos bytes son los de $a_i$ seguidos de los de $b_i$, y sustituye cada aparición del par por ella, de izquierda a derecha y sin solaparse. El vocabulario crece de uno en uno:

(En el código, $u_i$ es el primer número libre, $255 + i$: el código cuenta las fusiones desde cero y lo escribe 256 + i. Y no la escribimos $a_i b_i$ porque dos símbolos juntos se leen como un producto.) Lo que queda tras $m$ fusiones es la lista ordenada de las fusiones, y esa lista es el tokenizador entero: el del mini-GPT son 256 fusiones, guardadas en bpe-merges.json, así que su vocabulario tiene $256 + 256 = 512$ entradas.

Codificar un texto nuevo es aplicar esa lista, no volver a contar:

codificar(texto, fusiones):
    para cada pre-token w de texto:
        ids ← los bytes de w
        mientras algún par de vecinos de ids esté en fusiones:
            fusiona, en todo ids, el par que aparezca antes en la lista
        añade ids a la salida

Las frecuencias del texto nuevo no intervienen. Si lo hicieran, la misma palabra se cortaría de una manera en un documento y de otra en el siguiente, y el modelo, que aprendió a leer los cortes del corpus, recibiría otros. Decodificar es lo contrario: concatenar los bytes de cada token y leerlos como UTF-8.

Con eso el tokenizador cumple las dos exigencias que el curso anterior le hacía (determinismo y reconstrucción) y la totalidad que allí costaba un <UNK>. Es determinista, porque la lista y la regla de desempate fijan cada corte. Es reversible, porque los pre-tokens cubren el texto sin dejarse ningún carácter y una fusión sólo concatena bytes: decodificar lo codificado devuelve el texto byte a byte. Y es total, porque todo texto es una secuencia de $V_0 \subseteq V_m$: en el peor caso, cada byte es su propio token.

Lo que compra cada fusión, y a qué precio

Llamemos $T_i$ a la longitud del corpus en tokens después de $i$ fusiones (el subíndice cuenta fusiones, no posiciones), con $T_0 = n$. Cada aparición del par elegido son dos tokens que pasan a ser uno, así que, si $a_i \neq b_i$,

Con $a_i = b_i$ las apariciones pueden solaparse (en ... hay dos pares (., .) y sólo cabe una fusión) y el ahorro se queda por debajo de $f$. Salvo en ese caso, BPE es un compresor voraz: en cada paso elige el token nuevo que más acorta el corpus en ese momento.

Y cada fusión compra menos que la anterior. Antes de la fusión $i$, ningún par superaba a $(a_i, b_i)$: por eso lo eligió. Después, un par que no contiene $u_i$ sólo puede haber perdido apariciones, porque fusionar borra vecindades entre tokens viejos y no crea ninguna. Un par que sí contiene $u_i$ aparece como mucho tantas veces como $u_i$, que son como mucho $f(a_i, b_i)$. En los dos casos, el máximo no sube:

Es la forma exacta del compromiso entre vocabulario y longitud que planteaba el curso anterior. Con palabras, el vocabulario crecía sin techo a medida que crecía el corpus, como mostraba la ley de Heaps en la lección sobre el vocabulario y las palabras fuera de élDeep Learning para NLP: del Perceptrón al TransformerBloque 1 · Lección 3Vocabulario, frecuencia y el problema OOVLas palabras de un corpus no se reparten por igual: unas pocas lo copan y la mayoría aparece una sola vez. De esa forma salen el tamaño del vocabulario, lo que cuesta recortarlo y el token que recoge todo lo que queda fuera.. Con BPE, $\lvert V \rvert$ se elige, y lo que se paga por elegirlo pequeño es longitud. La $\bar{\ell}$ de aquel curso vuelve, medida en bytes:

donde $\lvert x_t \rvert$ son los bytes del token. Sin fusiones, $\bar{\ell} = 1$; cada fusión la sube, y cada vez menos.

Lo que cuesta cada entrada se paga dentro de la red. La tabla que convierte un token en vector tiene una fila por entrada,

casi la cuarta parte de los $136\,448$ parámetros del mini-GPT, y la misma tabla, leída al revés, es la que da sus logits. Lo que compra es alcance. El mini-GPT lee como mucho $T_{\text{ctx}} = 64$ tokens de una vez (el máximo que admite, no la $T$ de un texto concreto), y cuánto texto son esos 64 tokens lo decide $\bar{\ell}$.

Tu BPE, contra el del mini-GPT

Esta lección no llama todavía al mini-GPT: trabaja con su tokenizador, el bpe.py que las celdas del bloque cargan, y la primera celda lo escribe. Su entrenar hace lo de arriba con un atajo: cuenta los pares una sola vez y, tras cada fusión, recuenta sólo los pre-tokens donde estaba el par (los guarda donde), porque en los demás no ha cambiado nada. Salen las mismas fusiones, varias veces más deprisa, y eso es lo que permite entrenar 64 sobre los $302\,566$ bytes de Marianela, la novela de Galdós que hace de corpus del bloque, en lo que dura una celda. Ejecútala: imprime algunas fusiones con su $f$, y la última línea compara tus 64 con las 64 primeras del mini-GPT.

Las primeras fusiones son un espacio con la letra que lo sigue ( d, e, l), porque el espacio es el carácter más frecuente del corpus y va pegado al principio de cada palabra; la quinta ya es de, la palabra que más se repite. La 18 es la í, que la celda imprime como sus dos bytes, b'\xc3\xad', y la 32 es la raya de los diálogos, que ocupa tres. $f$ no sube ni una vez, de $4\,652$ a $628$, como pide la desigualdad de arriba, y la celda lo comprueba en las 64. La 20, (., .), es la única de las 64 con $a_i = b_i$, y por tanto la única en la que el corpus puede encoger menos que $f$. Y la última línea dice que tu código produce las fusiones del modelo: las mismas, en el mismo orden.

La segunda celda carga bpe.py tal cual, con las 256 fusiones del mini-GPT, codifica tres frases y comprueba en cada una que decodificar devuelve el texto exacto. Después mide el corpus entero con 0, 64 y las 256 fusiones.

En la primera frase, señor es un solo token; la ñ de pequeña es otro (la fusión 71, que la celda localiza) y ción va entera. criptomoneda, que en el curso anterior acababa en <UNK>, sale en ocho trozos. La tercera frase enseña qué hace BPE con lo que no tiene fusionado: el emoji son sus cuatro bytes, cuatro tokens que por separado no son texto y se imprimen como �, y a la ¿ del principio le pasa lo mismo, porque el mini-GPT sólo aprendió a fusionarla con un espacio o una raya delante. Aun así, ver no ha protestado: decodificar lo devolvió todo.

Y la tabla es el compromiso, medido. Las 64 primeras fusiones le quitan al corpus $112\,726$ tokens; las 192 siguientes, el triple de fusiones, sólo $50\,075$. $\bar{\ell}$ pasa de 1.00 a 1.59 con las primeras y, a duras penas, a 2.16 con el resto.

Comprueba tu intuición

Cuatro preguntas y un reto: los bytes de la ñ, por qué que llega antes que qu, qué garantiza el algoritmo y cuánto texto le cabe al mini-GPT de una vez. El reto te pide escribir codificar.

palabra = "año"
print(len(palabra), len(palabra.encode("utf-8")), list("ñ".encode("utf-8")))
 

El tokenizador está terminado y no volverá a cambiar en todo el curso: cada texto que le llegue al mini-GPT pasará antes por estas 256 fusiones. El corpus del bloque es ya una secuencia de $139\,765$ ids entre 0 y 511, y la pérdida de la lección sobre el modelo de lenguaje causalBloque 1 · Lección 1Una sola columna: el modelo de lenguaje causalEl curso anterior eligió una columna del Transformer, le puso la máscara en todos los bloques y le pidió el token siguiente, posición a posición. Esta lección hace la pregunta que aquél no hizo, qué probabilidad le da ese modelo a un texto entero, y de la respuesta sale todo lo demás: la regla de la cadena convierte esa probabilidad, sin perder nada, en un producto de condicionales; la máscara causal es lo que permite calcular las T de una ventana en una sola pasada; y la pérdida es el logaritmo de ese producto, cambiado de signo y repartido por token. Sin código a propósito: la cuenta se hace a mano sobre una ventana de cuatro palabras, y sale un dieciseisavo por los dos caminos. tiene por fin sus números de verdad. Le falta lo principal: la red que apuesta, y unos pesos que apuesten bien.

Esa red es la lección siguiente, sobre entrenar un mini-GPT en NumPy: cortar esa secuencia en ventanas, agruparlas en batches, cargar los pesos del mini-GPT y seguir entrenándolo delante de ti, con la pérdida bajando paso a paso sobre texto que el modelo no ha visto.