Skip to content

English · Español

02 — El algoritmo BPE: entrenamiento y codificación, totalmente desarrollados

🇪🇸 BPE entrena así: cuenta los pares adyacentes más frecuentes, fusiona el ganador en un símbolo nuevo, repite hasta llegar al tamaño del vocabulario. La codificación re-aplica esas fusiones, en orden, sobre nuevos textos. Sin trucos. La parte difícil es la contabilidad y el desempate.

Entrenamiento: el algoritmo

Entrada: un corpus C (lista de cadenas); un tamaño de vocabulario objetivo V; tokens especiales reservados opcionales S.

Salida: un vocabulario vocab (lista que mapea token-id → bytes); una lista ordenada de merges merges.

Paso 0 — inicializar.

  • Reserva IDs 0..|S|-1 para tokens especiales.
  • Añade los 256 bytes individuales (IDs |S|..|S|+255). El alfabeto base de BPE byte-level son los valores de byte, cada uno de ellos, siempre.
  • Divide cada cadena en \(C\) en una lista de bytes individuales. Así "hi" se vuelve [b'h', b'i'] se vuelve [(b'h',), (b'i',)] — una tupla por pre-token. (Usamos tuplas de bytes para que sean hashables para el diccionario de conteo de pares.)

Paso 1 — contar pares.

Para cada "pre-token" (una tupla de byte-símbolos), mira todos los pares adyacentes. Cuéntalos a lo largo del corpus.

for pretoken_tuple, count in corpus_with_counts:
    for i in range(len(pretoken_tuple) - 1):
        pair = (pretoken_tuple[i], pretoken_tuple[i+1])
        pair_counts[pair] += count

(corpus_with_counts es el corpus con consolidación de duplicados de pre-token — el mismo pre-token apareciendo \(k\) veces obtiene el conteo \(k\), no enumerado \(k\) veces.)

Paso 2 — elegir al ganador.

winner = min(pair_counts, key=lambda p: (-pair_counts[p], p))

La clave-tupla (-count, pair) es la regla de desempate: entre pares con el conteo máximo, los empates van al par lexicográficamente menor (para determinismo). La negación voltea min a "max por conteo, min por par". Documéntalo.

Paso 3 — fusionar al ganador.

Para cada tupla de pre-token que contiene el par ganador como elementos adyacentes, reemplaza esos dos elementos con un nuevo símbolo combinado.

new_symbol = winner[0] + winner[1]   # bytes concatenation
for pretoken in corpus:
    pretoken = replace_pair(pretoken, winner, new_symbol)

Añade new_symbol al vocab (con el siguiente ID disponible). Registra el merge: merges.append(winner).

Paso 4 — repite los pasos 1–3.

Hasta que len(vocab) == V. Eso es todo.

El ejemplo juguete, en pleno — cinco frases con verbos en inglés

Corpus (5 cadenas extraídas del tema §A13):

"I work"
"I work"
"I worked"
"he works"
"he worked"

Por brevedad, colapsamos la normalización de espacio inicial e ignoramos el espacio antes del salto de línea. Tratamos los pre-tokens como las secuencias de bytes de abajo (_ denota un byte de espacio literal 0x20):

Pre-token-con-conteos: 

("I","_","w","o","r","k")          : 2
("I","_","w","o","r","k","e","d")  : 1
("h","e","_","w","o","r","k","s")  : 1
("h","e","_","w","o","r","k","e","d"): 1

Iteración 1 — contar pares:

("w","o"): 5    ("o","r"): 5    ("r","k"): 5
("I","_"): 3    ("_","w"): 3
("h","e"): 2    ("e","_"): 2
("k","e"): 2    ("e","d"): 2
("k","s"): 1

Ganador: empates con conteo 5 entre ("w","o"), ("o","r"), ("r","k"). El orden lexicográfico sobre la tupla del par escoge ("o","r") (o > w pero el primer elemento gana; en realidad o < w lexicográficamente, así que ("o","r") < ("r","k") < ("w","o") — el ganador es ("o","r")).

Fusiona a "or".

Pre-tokens tras el merge: 

("I","_","w","or","k")            : 2
("I","_","w","or","k","e","d")    : 1
("h","e","_","w","or","k","s")    : 1
("h","e","_","w","or","k","e","d"): 1

merges = [("o","r")]. Vocab ahora: especiales + 256 bytes + "or".

Iteración 2 — contar pares:

("w","or"): 5   ("or","k"): 5
("I","_"): 3    ("_","w"): 3
("h","e"): 2    ("e","_"): 2
("k","e"): 2    ("e","d"): 2
("k","s"): 1

Ganador: empate en 5; lex escoge ("or","k") (ya que or > _ > I pero or < w; entre los pares con conteo 5 ("or","k") < ("w","or")). Fusiona a "ork".

Pre-tokens: 

("I","_","w","ork")            : 2
("I","_","w","ork","e","d")    : 1
("h","e","_","w","ork","s")    : 1
("h","e","_","w","ork","e","d"): 1

merges = [("o","r"), ("or","k")].

Iteración 3 —

("w","ork"): 5
("I","_"): 3    ("_","w"): 3
("h","e"): 2    ("e","_"): 2
("ork","e"): 2  ("e","d"): 2
("ork","s"): 1

Ganador: ("w","ork") con 5. Fusiona a "work".

Pre-tokens: 

("I","_","work")            : 2
("I","_","work","e","d")    : 1
("h","e","_","work","s")    : 1
("h","e","_","work","e","d"): 1

merges = [("o","r"), ("or","k"), ("w","ork")].

…y así sucesivamente. Tras algunas iteraciones más verías work (con espacio inicial) emerger como un único token, luego worked (el merge de la forma pasada de work + ed), luego works (el merge de 3ª persona). Estas son las victorias morfológicas — observables desde el registro de merges.

Este es el algoritmo completo. El Lab 00 hace que Borja haga exactamente esto sobre un corpus juguete fresco.

Codificación: aplicando los merges

Una vez entrenado, BPE codifica nuevas cadenas aplicando los merges en orden de entrenamiento, de forma codiciosa.

Algoritmo:

  1. Empieza con la tupla de bytes de la cadena de entrada.
  2. Para cada regla de merge (a, b) → ab en merges (en orden de entrenamiento):
  3. Escanea la tupla de bytes; reemplaza cada ocurrencia de a inmediatamente seguido por b con ab.
  4. Devuelve los IDs de la tupla resultante.

Crucial: el orden importa. Aplicar ("w","ork") antes de ("o","r") nunca dispararía — no hay símbolo "ork" en el flujo de bytes de una nueva entrada hasta que el merge ("o","r") se ejecute primero.

Codificación más rápida (versión de producción): en lugar de escanear de izquierda a derecha por cada merge, construye una priority queue sobre los merges candidatos en la secuencia actual. En cada paso, aplica el merge con el menor rango de entrenamiento. Esto evita el escaneo lineal y es \(O(L \log L)\) por entrada en lugar de \(O(L \times |\text{merges}|)\). Implementamos la versión simple.

Decodificación: trivialmente

decode(ids) = b''.join(id_to_bytes[id] for id in ids).decode('utf-8')

Mapea cada ID de vuelta a su secuencia de bytes, concatena, decodifica UTF-8.

La propiedad de ida y vuelta decode(encode(s)) == s se cumple para cualquier entrada UTF-8 válida si se implementa correctamente. Tested mediante property tests.

Casos límite que el algoritmo de arriba maneja

  • Cadena vacía: encode("") == [], decode([]) == "". Trivial.
  • Carácter único: encode("a") produce un ID (el byte 97 → token ID). No se aplican merges (no hay pares adyacentes en una tupla de longitud 1).
  • UTF-8 multibyte: encode("mañana") comienza como [m, a, 0xC3, 0xB1, a, n, a] (7 bytes; ñ son 2 bytes 0xC3 0xB1). Si mañana (o cualquiera de sus subsecuencias) aparece a menudo en el entrenamiento, BPE puede fusionar 0xC3 + 0xB1 en un símbolo ñ, luego a + ñ → añ, etc.
  • Emoji: encode("🦊") comienza como 4 byte-singletons (UTF-8 de 🦊 es 0xF0 0x9F 0xA6 0x8A). A menos que los emojis sean frecuentes en el entrenamiento (no lo son en nuestro corpus de verbos), no se aplican merges — el emoji se decodifica de vuelta exactamente como 4 bytes en bruto.
  • Caracteres de control, BOM: mismo tratamiento — son solo bytes.
  • Cadenas con múltiples palabras: sin pre-tokenización (nuestra elección v1), los espacios son solo el byte 0x20 en la secuencia. BPE fusionará o no con vecinos según la frecuencia.

Casos límite que el algoritmo de arriba no maneja (y cómo manejarlos)

  • Tokens especiales (<|endoftext|>, <|pad|>, <|sep|>): el trainer no debe fusionarlos ni fusionar a través de ellos. Implementación: reserva sus IDs en el paso 0, márcalos como "atómicos" — nunca participan en el conteo de pares. En el encoder, divide previamente la entrada en los límites de los tokens especiales antes de BPE, luego re-une.
  • Corpora muy grandes: el trainer naive es \(O(V \times N)\). Para nuestro pequeño corpus bootstrap (~30 frases ≈ 1 KiB) y \(V = 512\), eso es V × N ≈ 5 × 10⁵ operaciones de conteo de pares. En el i5-8250U de Borja esto es sub-segundo en Python. El corpus completo de la Fase 12 (~600 formas ≈ 30 KiB) es V × N ≈ 1.5 × 10⁷ ops — aún sub-segundo.

Complejidad, más cuidadosamente

Op Naive Priority-queue
Entrenamiento \(O(V \times N)\) donde \(N\) = bytes del corpus \(O(V \log N + N)\)
Codificación (por entrada de longitud \(L\)) \(O(L \times \|\text{merges}\|)\) \(O(L \log L)\)
Decodificación \(O(L)\) \(O(L)\)
Memoria \(O(V + N)\) \(O(V + N)\)

Implementamos naive. Nota que existe la versión con priority queue.

Desempate — el detalle poco discutido

Cuando dos pares empatan en conteo, el trainer debe escoger uno deterministicamente. Convenciones comunes:

  1. Lexicográfico sobre la tupla del par (lo que usamos). (b'a', b'b') < (b'a', b'c') — la comparación de tuplas de Python lo maneja.
  2. El primero visto gana (dependiente del orden — malo para reproducibilidad a menos que canonices el orden de recorrido del corpus).
  3. Desempate aleatorio con semilla explícita (perilla extra — la evitamos).

Sin desempate explícito, el entrenamiento es no-determinista incluso con una semilla fija. El orden de iteración del hash de los dicts de Python ha sido estable desde 3.7 pero fue un bug real en versiones anteriores. Usamos la convención (1) y la documentamos.

Esquema de implementación (para lab 01)

class BPETokenizer:
    def __init__(self):
        self.vocab: list[bytes] = []
        self.bytes_to_id: dict[bytes, int] = {}
        self.merges: list[tuple[bytes, bytes]] = []

    def train(self, corpus: Iterable[str], vocab_size: int, ...):
        # Step 0
        self._reserve_specials_and_bytes(...)

        # Step 0.5: convert corpus to pretoken-tuples-with-counts
        pretokens: dict[tuple[bytes, ...], int] = collections.Counter(...)

        # Step 1-4: iterate
        while len(self.vocab) < vocab_size:
            pair_counts = self._count_pairs(pretokens)
            if not pair_counts:
                break
            winner = max(pair_counts, key=lambda p: (pair_counts[p], p))
            pretokens = self._apply_merge(pretokens, winner)
            self._record_merge(winner)

    def encode(self, text: str) -> list[int]:
        bs = text.encode('utf-8')
        symbols = [bytes([b]) for b in bs]
        for (a, b) in self.merges:
            symbols = self._merge_in_place(symbols, a, b)
        return [self.bytes_to_id[s] for s in symbols]

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

errors='replace' en decode es una red de seguridad para secuencias de bytes inválidas en la salida (que puede ocurrir si un aprendiz construye IDs malos a mano; la ida y vuelta encode-then-decode sobre entrada UTF-8 válida es exacta).

Problemas de práctica

Soluciones en solutions/02-bpe-algorithm-ref.md (apertura de fase).

  1. Para el corpus ["he eats", "he eats", "I eat", "you eat"] con vocab objetivo = bytes base + 4 merges, haz 4 iteraciones de BPE a mano. Muestra la tabla de conteo de pares en cada paso y el vocabulario resultante. Predice si eat se vuelve un único token en la iteración 4.
  2. Argumenta por qué aplicar merges en orden de entrenamiento durante la codificación (en vez de en orden alfabético, o algún otro orden) es necesario para que encode(s) ≡ retokenize(decode(encode(s))) se cumpla.
  3. Con un corpus de \(N\) bytes y vocab objetivo \(V\), el trainer naive recalcula los conteos de pares desde cero en cada iteración. Sugiere la "actualización incremental" más simple que evite el recuento y analiza su complejidad.
  4. El ejemplo juguete de arriba tiene ("o","r") fusionándose antes de ("w","or"). Supón que el corpus tuviese cada "or" precompuesto como un solo byte (hipotético). ¿Cuál sería la secuencia de merges? (Pista: traza los nuevos conteos de pares.)

Lo que esta página de teoría NO cubre

  • Regex de pre-tokenización (pat de GPT-2). Tocado en theory 01; no implementado en nuestro BPE.
  • Regularización de subpalabra (BPE-dropout). Fase 18+ si se necesita; no se usa aquí.
  • Formato de serialización del vocabulario. El Lab 01 especifica el formato en disco (merges.txt + vocab.json).
  • Entrenamiento multi-corpus / multi-dominio. Fuera de alcance; un corpus, un BPE.

Recapitulación en un párrafo

Entrenamiento BPE: inicializa con los 256 bytes; cuenta repetidamente los pares adyacentes, escoge el más frecuente (con desempate determinista), fusiónalo en un nuevo símbolo, hasta alcanzar el tamaño del vocabulario. Codificación: aplica los merges entrenados en orden, codicioso, sobre la tupla de bytes de la entrada. Decodificación: concatena los bytes de cada ID, decodifica UTF-8. La complejidad naive es \(O(V \times N)\) para el entrenamiento; \(O(L \times \|\text{merges}\|)\) para codificación; ambas están bien para nuestro pequeño corpus bilingüe de verbos. El detalle de implementación poco discutido es el desempate determinista — usamos lexicográfico sobre la tupla del par.

Siguiente: theory/03-byte-level-and-unicode.md.