Etiquetado de secuencias: CRF, HMM y Viterbi

1Una etiqueta por token

El etiquetado de secuencias le da a cada token una etiqueta, así que la salida es tan larga como la entrada. El etiquetado POS ya tiene esa forma, porque cada token es su propia unidad. Un nombre puede abarcar varios tokens, así que el reconocimiento de entidades nombradas marca dónde empieza cada nombre, B- por beginning (comienzo); los tokens que lo continúan, I- por inside (dentro); y todo lo demás, O por outside (fuera). Después del guion va el tipo del nombre. Aquí hay dos tipos, personas y lugares, así que hay K = 2 · 2 + 1 = 5 etiquetas:

donde los tokens de una oración son x = (x₁, …, x_N) y sus etiquetas y = (y₁, …, y_N), con N su largo. Un nombre empieza en cada B- y sigue por las I- de su tipo que vienen después. Una I- después de una O, al comienzo, o después de un nombre del otro tipo no continúa nada y rompe el esquema. Los nombres no se anidan: la Mancha dentro del nombre del caballero es I-PER, como el apunte sobre palabras subrayó el nombre entero. En la figura, elige una frase y haz clic en una palabra para cambiar su etiqueta.

Las dos lecturas del nombre del caballero son válidas: una persona, o una persona y un lugar. Las etiquetas solas no pueden elegir entre ellas; el modelo de las secciones 3 y 4 las sopesa. La segunda frase muestra por qué el esquema necesita la B-: con los tipos solos, dos nombres que se tocan se leen como uno. En el retablo del capítulo XXVI de la segunda parte, don Quijote dice que los títeres parecían de verdad, «que Melisendra era Melisendra, don Gaiferos don Gaiferos, Marsilio Marsilio». Ramshaw y Marcus (1995) introdujeron las tres letras para los sintagmas nominales, con B- solo donde dos sintagmas se tocan; la versión que se usa aquí, y en la mayoría de los etiquetadores, la pone en cada comienzo.

2Un encoder, muchos cabezales

Un encoder es cualquier cosa que le da a cada token un vector. El más simple es una tabla entrenada de vectores de palabras: aquí los vectores del libro con subwords del apunte sobre subwords, d = 100, que le dan un vector a cada token, el mismo en cada oración. Se quedan como se entrenaron; solo se entrena lo que va encima, y esa parte, el cabezal, decide la tarea. Un cabezal que le da una etiqueta al texto entero es el clasificador de los apuntes de los modelos lineales y de los vectores de palabras; un cabezal que compara los vectores de dos textos es el coseno del apunte de los vectores de palabras; un cabezal que le da una etiqueta a cada token es el de este apunte.

El cabezal que etiqueta es una capa lineal, la misma en cada token. Le da a cada token una puntuación por etiqueta, la puntuación w_k^Tx del apunte de los modelos lineales con el vector del token en lugar de x. Las puntuaciones se apilan en una tabla P con una fila por token y una columna por etiqueta,

donde v_xi es el vector del token i con un 1 adelante, para que el sesgo quede en w_k, la fila k de la matriz de la capa. Una softmax por token convierte cada fila en probabilidades, y cada token se queda con la más alta:

El libro no trae los nombres etiquetados, así que para este apunte se hizo una lista de sus personas y lugares, unas 90 entradas de personas y 38 de lugares, y se etiquetó cada aparición, salvo las pocas impresas en mayúsculas, que quedan en O: don abre el nombre de una persona, mientras Rocinante y Dios quedan en O. Los cabezales se entrenan con el libro salvo el capítulo I de la primera parte y uno de cada diez capítulos, que quedan fuera para medirlos. La figura dibuja P de costado, una columna por token y una fila por etiqueta, con cada columna sombreada según las probabilidades de su token. Elige una frase y una casilla, y comprueba que las columnas de «de la Mancha» no cambian entre las dos frases.

El cabezal decide cada token por separado, y la fila de una palabra es la misma dondequiera que esté. Mancha es parte del nombre del caballero en unas tres de cada cuatro de sus apariciones en el libro, así que el cabezal la etiqueta I-PER incluso después de «un lugar de», y nada impide una I- justo después de una O: las dos frases terminan en etiquetas que el esquema prohíbe. Por sí solo, «el Toboso» se lee O I-PER en cuatro de los cinco entrenamientos, porque Toboso está sobre todo en «Dulcinea del Toboso». Los vectores se entrenaron con el texto en minúsculas, así que este cabezal nunca ve una mayúscula, la pista que señaló el apunte sobre palabras. Lo que falta es una manera de que la etiqueta de un token mire la de su vecina.

3La matriz de transiciones y la puntuación de una secuencia

Un campo aleatorio condicional (CRF; Lafferty, McCallum y Pereira 2001) agrega una tabla A, la matriz de transiciones, una puntuación por cada par ordenado de etiquetas seguidas: qué etiqueta puede seguir a cuál. El primer token no tiene etiqueta antes, así que una etiqueta de inicio y₀ va antes de la oración, y A tiene una fila más, A_y0,k, para cómo puede empezar una oración. La puntuación de una secuencia recorre la oración sumando, en cada token, lo que el cabezal dice de su etiqueta y lo que la tabla dice del paso hacia ella:

con A ∈ ℝ^K×K más su fila de inicio: 30 números, frente a los K(d + 1) = 505 del cabezal. La tabla se aprende junto con el cabezal, como explica la sección 4; nadie escribe en ella las reglas del esquema. Lample et al. (2016) pusieron esta tabla sobre las puntuaciones de una red recurrente, que trata un apunte posterior; aquí va sobre los vectores estáticos y una capa lineal. Lample et al. agregaron además una etiqueta de fin, una columna de A para cómo puede terminar una oración; este etiquetador tiene solo la fila de inicio. De aquí en adelante, el cabezal es el que se entrenó junto con la tabla, así que sus puntuaciones difieren de las de la sección 2: ahora la tabla hace parte del trabajo. En la figura, elige una etiqueta por token y lee la puntuación de la secuencia.

La tabla aprendió lo que hacían las etiquetas. Una I-PER justo después de una O puntúa −8.86, y al comienzo −6.04; la segunda palabra de un lugar después de la primera puntúa +4.55. Aprendió los datos, no las reglas: B-PER justo después de B-PER, dos nombres que se tocan, es válida pero queda en −6.40, porque el libro etiquetado la tiene dos veces, mientras la prohibida I-LOC → I-PER queda en apenas −1.84. El entrenamiento baja un paso solo mientras el modelo todavía siente la tentación de darlo, así que un paso válido que casi nunca se ve se hunde como uno prohibido, y un paso prohibido que rara vez tienta queda suave. Nada impide una secuencia rota si las puntuaciones del cabezal empujan lo bastante.

4El normalizador Z y la recursión hacia adelante

Una puntuación es un número cualquiera. Para que sea una probabilidad, se exponencia y se divide por la suma sobre todas las secuencias, la softmax del apunte de los modelos lineales con una clase por secuencia:

Z(x) depende de la oración, no de las etiquetas: se calcula una vez por oración y lo comparten todas sus secuencias, y no cambia cuál es la mejor. Pero hay K^N secuencias, el normalizador costoso del apunte de word2vec en su peor versión. La cuadrícula evita enumerarlas. Sea α_i(k) la suma de e^s sobre todas las secuencias de los primeros i tokens que terminan en la etiqueta k, con la puntuación detenida en el token i. Todo camino así pasa por alguna casilla de la columna anterior, y e^a+b = e^ae^b, así que cada casilla es la columna anterior por un paso:

Esta es la recursión hacia adelante (no las ecuaciones de transferencia de una red). Usa N·K números y cerca de N·K² multiplicaciones, frente a K^N secuencias. La softmax por token de la sección 2 sumaba una columna de la cuadrícula; Z suma todos los caminos que la cruzan. En la figura, elige una casilla para ver lo que entra en ella, o la casilla Z a la derecha.

Sumar e^s sobre las 625 secuencias da el mismo Z, 1484. El entrenamiento baja, sobre las oraciones de entrenamiento, la pérdida de cada oración etiquetada (Lample et al. 2016),

con logaritmos naturales en este apunte. Bajarla sube la puntuación de la secuencia correcta y, a través de Z, baja todas las demás; el cabezal y A aprenden juntos con una variante del descenso de gradiente. En la práctica e^s desborda en oraciones largas: una oración de 165 tokens del capítulo III de la primera parte ya tiene un log Z de 727, mientras un número de 64 bits no guarda nada mayor que e^709.78. Por eso los programas guardan log α y suman en logs, con log-sum-exp: log(e^a + e^b) = m + log(e^a−m + e^b−m), con m el mayor entre a y b, así que ninguna exponencial pasa de 1 (la fila «En logs» del resumen); el código del apunte de word2vec resta z.max() antes de su softmax por lo mismo. Los tamaños crecen rápido: las seis primeras palabras del libro, «En un lugar de la Mancha», tienen 15 625 secuencias y 30 casillas, y la oración mediana del libro, de 35 tokens, tiene unas 2.9 × 10²⁴ secuencias y 175 casillas.

En «don Quijote de la Mancha», el etiquetador le da a una persona una probabilidad de 0.70 y a una persona y un lugar 0.22: prefiere el nombre, como el libro etiquetado. En los capítulos que quedaron fuera, medido contra la lista de nombres, entre el 93% y el 96% de los nombres que marca coinciden con uno de la lista en extensión y tipo, y encuentra entre el 80% y el 84% de los nombres de la lista, en los cinco entrenamientos; el cabezal entrenado por sí solo coincide entre el 80% y el 85% y encuentra entre el 72% y el 82%. Deja a lo más una I- rota en 1101 oraciones, donde el cabezal por sí solo deja entre 33 y 75. Los pasos prohibidos se hunden solo con suficiente entrenamiento: después de 8 lecturas de los capítulos de entrenamiento en vez de 30, con un quinto de la tasa de aprendizaje, A_O,I-PER valía −2.53, quedaban cuatro I- rotas, y «En un lugar de la Mancha» salía O O O O O I-PER.

5El modelo oculto de Markov, entrenado contando

¿Se podrían contar simplemente las tablas de un etiquetador en un texto que alguien etiquetó? Un modelo oculto de Markov (HMM) describe cómo pudo haberse producido una oración: una cadena de etiquetas, cada una dependiente solo de la anterior (una cadena de Markov, no la cadena de hiperónimos del apunte sobre palabras), y cada etiqueta produciendo su palabra, que depende solo de su etiqueta. Sus etiquetas se escriben h, de hidden (oculto): en una oración nueva solo llegan las palabras. En este apunte h significa esto, no la salida logística de apuntes anteriores, y muchos textos escriben la cadena oculta como q y las palabras como o; aquí x es siempre la entrada. y y h son el mismo tipo de cosa, etiquetas, como las escriben el CRF y el HMM.

La segunda vale también dadas las otras palabras: una palabra depende solo de su propia etiqueta. Juntas dan la probabilidad de las palabras y las etiquetas juntas, la conjunta, no la de las etiquetas dadas las palabras:

con h₀ el inicio. Una P recta seguida de paréntesis, como P(x, h) o P(h_i | h_i−1), es una probabilidad; la P cursiva con dos índices sigue siendo la tabla de puntuaciones del cabezal. La tarea cambia a categorías gramaticales, las etiquetas de Universal Dependencies del apunte sobre palabras, porque hay mucho texto etiquetado a mano con ellas: los conteos salen de dos treebanks, corpus anotados a mano, UD Spanish GSD (15 586 oraciones y 411 492 tokens contados; sus otras 427 oraciones se guardan para la prueba) y UD English EWT. El entrenamiento ve palabras y etiquetas, y cada tabla se cuenta y se divide:

donde c cuenta. c(j) cuenta cada j, también la última etiqueta de una oración, a la que sigue el fin de la oración, una columna propia, así que las partes de cada fila suman 1 entre las etiquetas y el fin; la cadena de una oración entera termina con ese paso más, P(fin | h_N), que la cláusula de las figuras, que no termina su oración, deja fuera. Estas partes son las que hacen más probable el texto etiquetado, por la misma razón por la que, en el apunte de word2vec, la predicción que minimiza ℒ le daba a cada palabra su fracción de los pares; no se itera nada, cosa que solo hace falta cuando no se dan las etiquetas. Quedan dos tablas, las transiciones y las emisiones, y el log de la cadena es una suma, log P(x, h) = ∑_i [log P(h_i | h_i−1) + log P(x_i | h_i)]. En la figura, la cláusula «la tomó por la mano», del capítulo XLII de la primera parte, tomada como si abriera una oración (dentro de la suya, Viterbi le da las mismas etiquetas), está en la cuadrícula con una casilla solo donde el treebank le dio a una palabra esa etiqueta en al menos uno de cada 50 usos. Elige una etiqueta para cada palabra y mira el log de la cadena.

Las otras etiquetas son posibles pero raras, y decodificar sobre estas casillas da la misma cadena que sobre las 17 etiquetas. Las celdas que deciden: un verbo sigue a un pronombre con P(VERB | PRON) = 6476 / 12 312 ≈ 0.53, pero a un determinante con apenas 46 / 52 486 ≈ 0.0009. El HMM es un CRF con log-probabilidades: con A_j,k = log P(h_i = k | h_i−1 = j) y P_i,k = log P(x_i | h_i = k), la puntuación de la sección 3 es log P(x, h), y el Z(x) de la sección 4, con el paso hacia el fin, se vuelve P(x), la probabilidad que el modelo le da a la oración. Las dos cadenas recorren las etiquetas; la diferencia es qué modela cada uno y cómo aprende. El HMM cuenta tablas que explican cómo se escribieron las palabras, la conjunta; el CRF aprende puntuaciones que distinguen etiquetas dadas las palabras, la condicional. Un par que nunca se contó da log 0 = −∞, una cadena que el HMM declara imposible, cosa que una A aprendida nunca llega a hacer. Una palabra que el treebank nunca vio recibe una parte estimada a partir de las palabras vistas una vez que, como ella, empiezan o no con mayúscula y terminan en las mismas tres letras; sin eso, tendría probabilidad 0 con cualquier etiqueta.

6Viterbi: la mejor secuencia sin probarlas todas

Con 17 etiquetas por palabra, ¿cómo encuentra un etiquetador la mejor cadena sin probar 17^N, y por qué no elegir cada etiqueta sobre la marcha? Sea δ_i(k) la probabilidad de la mejor cadena que llega a la etiqueta k en la palabra i, usando solo las palabras hasta ahí. Es la cuadrícula de la sección 4 con un máximo en lugar de la suma (Viterbi 1967):

con δ₁(k) = P(h₁ = k | h₀) P(x₁ | h₁ = k). Cada casilla guarda solo su mejor cadena entrante, y recuerda de qué etiqueta vino, su puntero hacia atrás. El mayor δ de la última columna es la probabilidad de la mejor cadena, P(x, h*) = max_k δ_N(k); su argmax da solo la última etiqueta, y la cadena se lee siguiendo los punteros de derecha a izquierda: h*_N = argmax_k δ_N(k), h*_i−1 = argmax_j δ_i−1(j) P(h_i = h*_i | h_i−1 = j). δ cae a lo largo de la oración, porque cada paso multiplica una probabilidad más, así que las casillas se comparan dentro de una columna, nunca entre columnas, y δ se guarda en logs: un producto de factores de 0.001 es exactamente 0 en números de 64 bits después de 108 factores, y la mejor cadena de una oración de 101 tokens del capítulo XXVIII de la primera parte ya tiene un log de −748.5, mientras un número de 64 bits se redondea a 0 por debajo de e⁻⁷⁴⁵, aproximadamente. Elegir las etiquetas una por una, de izquierda a derecha (greedy), compromete cada etiqueta antes de ver la palabra siguiente; Viterbi la espera, con el mismo costo que la recursión hacia adelante, N·K² pasos. En la figura, compara los dos.

Cada palabra sola, con su etiqueta más frecuente, da DET VERB ADP DET NOUN, con un log de −30.91. En las oraciones de prueba de cada treebank, cada palabra sola etiqueta bien el 93.4% de las palabras, una por una el 93.8%, y Viterbi el 94.8% (en el inglés EWT: 89.3%, 90.0%, 92.4%). En el libro entero, Viterbi etiqueta la como pronombre 885 veces, cosa que ni cada palabra sola ni una por una hacen nunca. Los treebanks son modernos y el libro no: el 9.6% de sus tokens son palabras que el treebank español nunca vio, como dellos y conocióle.

El CRF decodifica igual sobre sus puntuaciones, que se suman a lo largo de un camino, así que su δ suma donde el del HMM multiplica (Lample et al. 2016): δ_i(k) = max_j [δ_i−1(j) + A_j,k] + P_i,k. En «lugar de la Mancha» da O O B-LOC I-LOC, con una puntuación de 7.10, aunque en la la mejor cadena hasta ahí terminaba en O (4.70 frente a −3.08 para B-LOC): la última palabra cambió la respuesta. Corrida con la suma en vez del máximo, la cuadrícula del HMM da P(x), la recursión de la sección 4; los dos modelos usan las dos recursiones. El cabezal de aquí lee el vector de una palabra a la vez. Las redes recurrentes del próximo apunte le dan a cada token un vector que depende de sus vecinas, y convierten la etiqueta oculta del HMM en un vector oculto.

7Resumen

Las ideas del apunte en NumPy. vecs guarda los vectores de los tokens, una fila cada uno con un 1 al comienzo; w es el cabezal, una fila por etiqueta; A tiene K + 1 filas, la última la de la etiqueta de inicio; trans tiene K + 1 filas (la última el inicio) y K + 1 columnas (la última el fin de la oración, como lo cuenta la sección 5), y emit una fila por etiqueta y una columna por palabra; tagged guarda las oraciones del treebank como pares de arreglos de índices, y V es su número de palabras distintas; x, y y h son arreglos de índices, y N el largo de la oración.

Los datos del apunte: los libros son el Don Quijote de Project Gutenberg (#2000) y la traducción de Ormsby (#996). Los vectores del libro con subwords se entrenaron para estos apuntes, y la lista de personas y lugares del libro, sus etiquetas y los etiquetadores se hicieron para este apunte. Los conteos del modelo oculto de Markov salen de los treebanks English EWT y Spanish GSD de Universal Dependencies, con la licencia Creative Commons Atribución-CompartirIgual 4.0; la página solo muestra conteos calculados con ellos, compartidos con la misma licencia.