One-hot encoding y la maldición de la dimensionalidad

La lección anterior, sobre vocabulario y frecuencia, dejó el vocabulario completamente definido: una lista cerrada de $\lvert V \rvert$ entradas, construida a partir de las palabras más frecuentes y completada con <UNK> para todo lo que queda fuera. Con eso, $r$ ya puede recibir cualquier texto. Solo queda decidir qué vector asignar a cada una de las entradas del vocabulario.

Hay una respuesta inmediata a esa pregunta, y la lección existe porque esa respuesta es correcta: cumple una por una las exigencias que la lección sobre el problema de representar el lenguajeBloque 1 · Lección 1El problema de representar el lenguajeUna red solo opera con números reales; el texto no lo es. Este es el enunciado preciso del problema del que vive todo el bloque. le puso a $r$, y aun así no basta. Tiene nombre —one-hot encoding— y lo que queda por hacer con ella es ponerle precio. Una parte del precio se ve venir, porque los vectores salen enormes, y es precisamente la parte que no importa. La otra aparece al preguntar qué puede aprender un modelo que recibe entradas así, y esa no la arregla ninguna máquina más grande.

Mira colocadas de las dos maneras las tres palabras con las que aquella lección descartó $d = 1$, antes de leer una sola fórmula. Sobre la recta, los índices $1$, $2$ y $3$ dejan a gato a distancia $1$ de casa y a perro a distancia $2$: hay un medio, y alguien lo ocupa. Con un eje por palabra hay tres ejes perpendiculares y cada palabra cae sobre el suyo, en $(1,0,0)$, $(0,1,0)$ y $(0,0,1)$. Cuenta cuántos lados distintos tiene el triángulo que forman.

Un eje para cada entrada del vocabulario

Ordena el vocabulario de una vez por todas y escríbelo como $V = \{w_1, w_2, \dots, w_{\lvert V \rvert}\}$. El orden da igual —alfabético, por frecuencia, el que salga— mientras no cambie después; es el determinismo que la lección sobre el problema de representar el lenguajeBloque 1 · Lección 1El problema de representar el lenguajeUna red solo opera con números reales; el texto no lo es. Este es el enunciado preciso del problema del que vive todo el bloque. exigía. Lo que ese orden aporta es una correspondencia: la entrada que ocupa la posición $i$ tendrá reservada la coordenada $i$ del vector, y ninguna otra entrada la usará. Posiciones del vocabulario y coordenadas del vector son, de aquí en adelante, la misma lista de números de $1$ a $\lvert V \rvert$.

Queda precisar de qué está hecha esa lista, porque el resto de la lección lo da por sabido. Las entradas de $V$ son tokens, y qué sean depende de la tokenización que fijó la lección sobre tokenizaciónBloque 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.: palabras enteras con un tokenizador de palabras, trozos de palabra con uno de subpalabras. Nada de lo que sigue cambia por eso, y los ejemplos usan palabras enteras porque se leen mejor.

La representación one-hot asigna a la entrada $w_i$ el vector de $\lvert V \rvert$ coordenadas que vale $1$ en la posición $i$ y $0$ en todas las demás. Coordenada a coordenada, escribiendo $(\mathbf{o}_w)_j$ para la $j$-ésima coordenada del vector de la entrada $w$:

Es una $r$ como la que pedía la lección sobre el problema de representar el lenguajeBloque 1 · Lección 1El problema de representar el lenguajeUna red solo opera con números reales; el texto no lo es. Este es el enunciado preciso del problema del que vive todo el bloque., con la dimensión fijada por el propio vocabulario: $r(w) = \mathbf{o}_w$ y $d = \lvert V \rvert$. Un texto de $T$ tokens se convierte entonces en una matriz $\mathbf{X} \in \mathbb{R}^{T \times \lvert V \rvert}$, una fila por posición.

Ahora la propiedad por la que se elige. Toma dos entradas distintas del vocabulario, $u$ en la posición $i$ y $v$ en la posición $j$, con $i \neq j$. Su producto escalar recorre las coordenadas $k$ y en cada una encuentra un cero:

porque el único término que podría no anularse exigiría $k = i$ y $k = j$ a la vez. Los vectores son ortogonales, dos a dos, todos.

Y la distancia entre ellos sale de la misma cuenta. La escribimos con doble barra: $\lVert \mathbf{x} \rVert$ es la longitud euclídea de $\mathbf{x}$, la raíz de la suma de sus coordenadas al cuadrado. La resta $\mathbf{o}_u - \mathbf{o}_v$ vale $+1$ en la posición $i$, $-1$ en la $j$ y $0$ en el resto, de modo que

y por tanto $\lVert \mathbf{o}_u - \mathbf{o}_v \rVert = \sqrt{2}$, sean cuales sean $u$ y $v$, y sea cual sea el tamaño del vocabulario. Ahí está lo que se buscaba, escrito en una línea: todos los pares de palabras están exactamente a la misma distancia. Ninguna queda entre otras dos, y nada de lo que la representación dice del idioma se puede leer mal, porque no dice nada. La geometría inventada de la lección sobre el problema de representar el lenguajeBloque 1 · Lección 1El problema de representar el lenguajeUna red solo opera con números reales; el texto no lo es. Este es el enunciado preciso del problema del que vive todo el bloque. ha desaparecido.

Lo que cuesta no afirmar nada

El precio ya estaba escrito en la lección anterior, solo faltaba sustituir. Guardar $r$ como una tabla, una fila por entrada del vocabulario y $d$ columnas, cuesta $\lvert V \rvert \cdot d$ números; con $d = \lvert V \rvert$ eso es

Con el vocabulario de subpalabras de la lección sobre tokenizaciónBloque 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., entre 30 000 y 50 000 entradas, son entre 900 y 2 500 millones de números: unos 10 GB con cuatro bytes cada uno. Y crece al cuadrado: duplicar el vocabulario cuadruplica la tabla.

Esa cifra pide una corrección inmediata, porque nadie paga esos 10 GB. La tabla del one-hot es la matriz identidad, y una matriz identidad no contiene información: está determinada por su tamaño. Se guarda el índice $i$ de cada entrada —un entero— y el vector se fabrica cuando hace falta, o ni siquiera se fabrica. El coste de almacenar la representación desaparece.

Lo que no desaparece es la dimensión. El vector que el sistema recibe tiene $\lvert V \rvert$ coordenadas y solo una es distinta de cero, así que la parte del vector que lleva información, con 50 000 entradas, es

Antes de seguir, un apunte a favor. La lección sobre el problema de representar el lenguajeBloque 1 · Lección 1El problema de representar el lenguajeUna red solo opera con números reales; el texto no lo es. Este es el enunciado preciso del problema del que vive todo el bloque. te pidió que guardaras una observación: allí, añadir agua al vocabulario renumeraba palabras que no tenían nada que ver con ella y dejaba inservible cualquier modelo entrenado antes. El one-hot no tiene ese defecto. Añade una entrada al final y cada vector antiguo conserva sus coordenadas; solo le crece un cero. Es la estabilidad que faltaba. Es real, aunque en la práctica $V$ se congela una sola vez —para eso está <UNK>— y la ocasión casi no llega.

Por qué la ortogonalidad impide aprender

Queda la cuenta que da título a la lección, y no es la de la memoria. Un sistema que lee una ventana de $n$ tokens seguidos recibe los $n$ vectores uno detrás de otro, $n \lvert V \rvert$ coordenadas en total. ¿Cuántas entradas distintas puede recibir? Cada una de las $n$ posiciones admite cualquiera de las $\lvert V \rvert$ entradas del vocabulario, con independencia de las demás, así que

Pon números de los pequeños: $\lvert V \rvert = 30\,000$ y una ventana de $n = 5$ tokens, un cuarto de la frase de veinte tokens de la lección sobre vocabulario y frecuenciaBloque 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.. Son $30\,000^{5} \approx 2.4 \times 10^{22}$ entradas posibles. Un corpus enorme tiene del orden de $T = 10^{10}$ tokens, y por tanto como mucho $10^{10}$ ventanas distintas, de modo que el modelo llega a ver

del espacio de entradas. Cuatro diezmillonésimas de millonésima. Y no hay corpus que arregle eso: el exponente está en $n$, así que mirar un token más de contexto multiplica el espacio por $30\,000$ mientras el corpus sigue donde estaba. Esta es la maldición de la dimensionalidad: el número de configuraciones distintas crece exponencialmente con la dimensión de la entrada, y cualquier cantidad de datos cubre una fracción que tiende a cero.

Dicho así suena a condena general, y no lo es. Los modelos trabajan con entradas de dimensión enorme y aprenden de todos modos, porque en esas entradas hay vecindad: dos fotografías que difieren en un píxel son parecidas, lo aprendido sobre una vale para la otra, y por eso una fracción minúscula del espacio alcanza. Ese es el argumento que salva a cualquier representación de dimensión alta, y es el que el one-hot no puede usar. La equidistancia desarrollada arriba dice, con otras palabras, que aquí no hay vecinos: la ventana el niño juega en la plaza y la ventana la niña juega en la plaza están a la misma distancia entre sí que de cualquier otra.

De modo que la virtud es el defecto, y es la misma propiedad vista dos veces. Pedimos una representación que no afirmara parecidos falsos y salió una que no afirma parecidos, punto. Cada una de esas $2.4 \times 10^{22}$ entradas hay que aprenderla por separado, porque ninguna se parece a ninguna, y solo se van a ver $10^{10}$.

La matriz one-hot en NumPy, y lo que pesaría

La celda construye el one-hot de un vocabulario diminuto en español y comprueba sobre él las tres afirmaciones de arriba: que los vectores son ortogonales, que todas las distancias valen $\sqrt{2}$ y qué fracción de cada vector es distinta de cero. Después hace las cuentas de tamaño sin reservar memoria, que es la única forma de hacerlas: una tabla de 50 000 por 50 000 no cabe en el navegador, y ese es parte del resultado.

Las tres comprobaciones salen exactas y una conviene mirarla dos veces: el conjunto de distancias entre pares tiene un solo elemento. No es que se parezcan, es que no hay más de un valor. Con ocho palabras se ve de un vistazo; con 50 000 sigue siendo el problema.

La tabla de tamaños tiene una fila que sorprende y otra que no. La que no: 50 000 entradas piden 9.31 GB, y por eso nadie guarda esta tabla. La que sí: la columna de la derecha, el porcentaje de coordenadas no nulas, que ya con 30 000 entradas es 0.003 %. Y las últimas líneas son la maldición de la dimensionalidad en cuatro renglones: con una o dos palabras de contexto el corpus cubre el espacio entero, con tres cubre ya solo el 0.04 %, y con cinco la fracción se escribe con doce ceros detrás del punto. El salto ocurre entre la segunda palabra de contexto y la tercera, no en el infinito.

Una prueba de treinta segundos. Cambia V por un vocabulario de dos palabras y vuelve a ejecutar: la distancia entre pares sigue valiendo $\sqrt{2}$, exactamente igual que con ocho. Ahí ves que $\lvert V \rvert$ no entra en esa cuenta.

Comprueba tu intuición

Cuatro preguntas sobre lo que acabas de obtener: cuánto mide la distancia entre dos palabras, qué arregla el one-hot respecto de la lección sobre el problema de representar el lenguajeBloque 1 · Lección 1El problema de representar el lenguajeUna red solo opera con números reales; el texto no lo es. Este es el enunciado preciso del problema del que vive todo el bloque., qué cuesta la tabla y qué pasa con dos palabras que se parecen.

El one-hot cumple las tres exigencias, es estable, y su geometría no afirma nada falso sobre el idioma. También es un callejón sin salida, y por el mismo motivo por el que cumple: una representación que no relaciona ninguna palabra con ninguna otra obliga a aprenderlo todo por separado, y no hay corpus para eso. Para salir hacen falta dos cosas a la vez, y son las dos que faltan aquí: muchas menos coordenadas que $\lvert V \rvert$, y coordenadas que signifiquen algo, de modo que dos palabras parecidas acaben cerca.

La segunda es la difícil y ocupa el resto del bloque. Pero antes hay un cambio de pregunta que sale casi gratis desde aquí, y conviene hacerlo ahora, con los vectores one-hot todavía a la vista. Hasta ahora $r$ representa una palabra, y lo que un sistema suele necesitar es el vector de un documento entero: una reseña, un correo, una noticia. La forma más directa de obtenerlo es sumar los vectores one-hot de todos sus tokens, $\sum_{t=1}^{T} \mathbf{o}_{w_t}$, donde $t$ recorre las $T$ posiciones del documento y no las entradas del vocabulario. Cada coordenada pasa entonces a contar cuántas veces sale su palabra. Eso ya no es un vector de ceros y unos, y ya no es tan mudo: la coordenada de gol distingue una crónica deportiva de una receta. Sigue teniendo $\lvert V \rvert$ dimensiones y sigue sin saber en qué orden iban las palabras. Es la bolsa de palabras, y con la corrección que la hace útil —TF-IDF— es la lección sobre la bolsa de palabras y TF-IDF.