Etiquetado de secuencias: cadenas de Markov, HMM y Viterbi
1 El problema: etiquetar secuencias
Hasta ahora hemos clasificado observaciones aisladas: una reseña es positiva o negativa, un correo es spam o no. Pero muchos problemas consisten en etiquetar secuencias, donde cada elemento recibe una etiqueta y las etiquetas dependen entre sí.
El ejemplo clásico es el etiquetado gramatical (POS tagging, del inglés Part-of-Speech tagging): asignar a cada token su categoría léxica (sustantivo, verbo, adjetivo…). En “Why not learn something?” las etiquetas serían adverbio, adverbio, verbo y pronombre. Para no escribir el nombre completo cada vez se usan abreviaturas (tags): VB para verbo, NN para sustantivo, etc.
Las etiquetas describen la estructura gramatical del texto y sirven para inferir significado:
- Reconocimiento de entidades nombradas (NER): las etiquetas pueden aportar características útiles para detectar nombres propios, aunque los sistemas modernos suelen resolver NER directamente con modelos neuronales, como las RNN descritas en el capítulo de redes recurrentes.
- Análisis sintáctico: el etiquetado ayuda a reconstruir la estructura jerárquica de la oración, aunque no todos los analizadores modernos lo exigen como paso previo.
- Reconocimiento de voz: la coherencia lingüística se modela sobre todo con modelos de lenguaje; las etiquetas pueden ser una característica adicional para descartar transcripciones gramaticalmente improbables.
- Búsqueda y preguntas-respuestas: conocer la función gramatical ayuda a interpretar la consulta del usuario.
2 Cadenas de Markov
Una cadena de Markov es un modelo estocástico (es decir, basado en probabilidades) que describe una secuencia de eventos donde la probabilidad de cada evento depende únicamente del estado anterior. Esta es la propiedad de Markov: para predecir lo siguiente, el modelo usa únicamente el presente, no toda la historia. Dicho con más cuidado: la distribución de la etiqueta actual se aproxima usando únicamente la etiqueta anterior, aunque en el lenguaje real puedan influir muchos otros factores. Es una suposición del modelo, no una afirmación exacta sobre el lenguaje.
Aplicada al etiquetado, la cadena de Markov modela la dependencia entre etiquetas:
Cuando añadamos las palabras observadas para construir un HMM, modelaremos además la emisión:
Conviene no confundir ambas: la transición pertenece a la cadena de Markov; la emisión es la pieza propia del HMM. Por ejemplo, después de un determinante esperamos un sustantivo o un adjetivo («la casa», «la gran casa»), aunque las probabilidades concretas se estiman del corpus.
Por ejemplo, con dos estados (verbo VB y sustantivo NN):
- \(P(\text{NN} \mid \text{VB}) = 0.6\): después de un verbo, lo más probable es un sustantivo.
- \(P(\text{VB} \mid \text{VB}) = 0.2\): dos verbos seguidos son raros.
2.1 La matriz de transición
Visualmente se dibuja como un grafo dirigido: los círculos son los estados y las flechas las transiciones, cada una con su probabilidad. Para calcular se usa una representación más compacta, la matriz de transición \(A\): cada fila es el estado actual, cada columna el estado siguiente, y cada celda la probabilidad de esa transición.
| Desde Hacia | NN | VB | Otras |
|---|---|---|---|
| NN | 0.3 | 0.2 | 0.5 |
| VB | 0.6 | 0.2 | 0.2 |
| Otras | 0.4 | 0.1 | 0.5 |
Regla de oro: cada fila debe sumar 1, porque desde un estado dado algo tiene que ocurrir a continuación (0.3 + 0.2 + 0.5 = 1.0 en la primera fila, y lo mismo en las demás).
Queda un detalle: la primera palabra de la oración no tiene antecesora. Se resuelve con un estado especial <START> y las probabilidades iniciales \(\pi\):
(por ejemplo, \(\pi = [0.4, 0.1, 0.5]\), que suma 1). Si se añade <START> como fila extra, se obtiene una representación extendida de dimensiones \((N+1) \times N\); la matriz de transición estándar \(A\) sigue siendo \(N \times N\). Simétricamente puede añadirse un estado <END> para modelar el final de la oración, \(P(\text{END} \mid y_T)\).
En resumen, una cadena de Markov se define por un conjunto \(Q\) de \(N\) estados y una matriz de transición \(A\) con las probabilidades de pasar de un estado a otro (más las iniciales).
3 Estimar las probabilidades desde un corpus
Las probabilidades no se inventan: se cuentan. Si la etiqueta X aparece 10 veces en el corpus de entrenamiento, 6 seguida de Y y 4 seguida de Z:
donde \(C(a, b)\) es el número de veces que la etiqueta \(a\) aparece seguida de \(b\). El denominador cuenta todas las transiciones que parten de \(X\), incluyendo eventualmente una transición al estado <END> si el modelo lo usa.
Surgen dos problemas. Primero, una transición jamás vista recibe probabilidad 0 y el modelo la declara imposible, sin capacidad de generalizar. Segundo, si un estado nunca aparece como origen, su fila suma 0 y la fórmula divide por cero.
La solución es el suavizado aditivo (add-\(\epsilon\)): sumar una cantidad pequeña \(\epsilon\) (típicamente 0.001) a cada recuento del numerador y \(N \cdot \epsilon\) al denominador, con \(N\) el número de estados destino. Cuando \(\epsilon = 1\) se habla propiamente de suavizado de Laplace; la idea es la misma, aplicada aquí a filas de transición. Las filas siguen sumando 1, como se comprueba directamente:
donde \(S\) es la suma de recuentos de la fila. Detalle práctico: en corpus reales no suele suavizarse la fila de probabilidades iniciales, porque permitiría que una oración empezase con cualquier etiqueta, incluida la puntuación.
Importante
Las emisiones también necesitan suavizado, y con más urgencia. Una palabra no vista en entrenamiento tendría probabilidad de emisión cero, y una sola palabra desconocida bastaría para anular todos los caminos que pasan por ella. La solución habitual es sustituir durante el entrenamiento las palabras raras por un símbolo <UNK> y asignar a cualquier palabra no vista la probabilidad \(P(\text{UNK} \mid y)\) estimada de ese modo (el símbolo completo es <UNK>).
4 Modelos ocultos de Markov
Hay un problema: el modelo no observa directamente las etiquetas, solo las palabras. Ante “jump”, un humano reconoce un verbo al instante; el modelo solo dispone de la cadena “j-u-m-p”, que además puede ser sustantivo (“a good jump”). Las etiquetas están ocultas y hay que inferirlas desde lo observable. De ahí los modelos ocultos de Markov (HMM).
- Los estados ocultos son las etiquetas gramaticales (círculos en los diagramas).
- Las observaciones son las palabras reales del texto (rectángulos).
La pieza nueva es la matriz de emisión \(B\): la probabilidad de observar cada palabra dado cada estado, \(P(\text{palabra} \mid \text{etiqueta})\). Cada fila es un estado, cada columna una palabra del vocabulario, y —misma regla de oro— cada fila suma 1. Esto vale para un vocabulario cerrado; en implementaciones reales hay que distinguir entre vocabulario conocido, palabras raras agrupadas como <UNK> y palabras totalmente desconocidas, con el tratamiento visto en la sección anterior. Por ejemplo, \(P(\text{“eat”} \mid \text{VB}) = 0.5\) significa que, estando en estado verbo, la mitad de las veces se emite “eat”.
Una palabra puede emitirse desde varios estados: “back” es sustantivo en “lying on his back” y adverbio en “I will be back”, así que tendrá probabilidad no nula en ambas filas.
Un HMM queda definido por tres elementos: el conjunto \(Q\) de estados ocultos, la matriz de transición \(A\) (cómo se suceden los estados) y la matriz de emisión \(B\) (qué palabras genera cada estado). La pregunta que responde es: dada la secuencia de palabras observadas, ¿cuál es la secuencia de etiquetas más probable que la generó?
5 El algoritmo de Viterbi
Probar todas las secuencias de etiquetas posibles es exponencial. Viterbi lo resuelve con programación dinámica: el mismo patrón de la distancia de edición —rellenar una tabla reutilizando subproblemas y guardar punteros (backtrace) para reconstruir el camino.
Se rellenan dos tablas sobre un diagrama de rejilla (trellis), con una columna por palabra observada y una fila por estado:
- \(V[t, j]\): probabilidad del mejor camino que termina en el estado \(j\) tras observar hasta la palabra \(t\).
- \(Ptr[t, j]\): desde qué estado anterior vino ese mejor camino.
Las fórmulas, con \(\pi_j\) las probabilidades iniciales, \(A\) la transición y \(B\) la emisión:
El puntero se obtiene con el mismo máximo, de modo que el valor de la tabla y la reconstrucción del camino quedan explícitamente conectados:
Al terminar, el mejor estado final es \(s_T = \arg\max_j V[T, j]\), y se retrocede con los punteros hasta la primera palabra. El coste es \(O(T \cdot N^2)\): lineal en la longitud de la secuencia, cuadrático en el número de estados.
5.1 Ejemplo trabajado: condiciones meteorológicas y el perro
Un observador quiere inferir el estado meteorológico (soleado, nublado, lluvioso; en adelante S, N, L) observando solo a su perro (paseó, jugó, se quedó en casa). Los estados ocultos son las condiciones meteorológicas; las observaciones, la actividad.
Probabilidades iniciales: \(\pi = [0.6, 0.3, 0.1]\) para [S, N, L].
Transiciones \(A\) (filas desde, columnas hacia):
| Desde Hacia | S | N | L |
|---|---|---|---|
| S | 0.8 | 0.15 | 0.05 |
| N | 0.4 | 0.3 | 0.3 |
| L | 0.2 | 0.3 | 0.5 |
Emisiones \(B\) (filas estado, columnas actividad):
| Estado | Paseó | Jugó | Casa |
|---|---|---|---|
| S | 0.7 | 0.2 | 0.1 |
| N | 0.2 | 0.5 | 0.3 |
| L | 0.0 | 0.1 | 0.9 |
Observaciones en tres días: paseó, se quedó en casa, paseó. Codificaremos «se quedó en casa» como la observación Casa.
Día 1 (paseó). Inicialización, \(V[1,j] = \pi_j \cdot B[j, \text{paseó}]\):
- \(V[1,S] = 0.6 \times 0.7 = 0.42\)
- \(V[1,N] = 0.3 \times 0.2 = 0.06\)
- \(V[1,L] = 0.1 \times 0.0 = 0.00\)
Día 2 (casa). Para cada estado, el mejor predecesor por el máximo, multiplicado por la emisión:
- \(V[2,S] = \max(0.42 \times 0.8,\; 0.06 \times 0.4,\; 0) \times 0.1 = 0.336 \times 0.1 = 0.0336\), desde S.
- \(V[2,N] = \max(0.42 \times 0.15,\; 0.06 \times 0.3,\; 0) \times 0.3 = 0.063 \times 0.3 = 0.0189\), desde S.
- \(V[2,L] = \max(0.42 \times 0.05,\; 0.06 \times 0.3,\; 0) \times 0.9 = 0.021 \times 0.9 = 0.0189\), desde S.
Día 3 (paseó).
- \(V[3,S] = \max(0.0336 \times 0.8,\; 0.0189 \times 0.4,\; 0.0189 \times 0.2) \times 0.7 = 0.02688 \times 0.7 = 0.018816\), desde S.
- \(V[3,N] = \max(0.0336 \times 0.15,\; 0.0189 \times 0.3,\; 0.0189 \times 0.3) \times 0.2 = 0.00567 \times 0.2 = 0.001134\). El máximo empata entre N y L como predecesor; se desempata arbitrariamente (aquí, N).
- \(V[3,L] = \max(0.0336 \times 0.05,\; 0.0189 \times 0.3,\; 0.0189 \times 0.5) \times 0.0 = 0\).
Fíjate en que, como \(B[L, \text{paseó}] = 0\), cualquier camino que termine en L el día 3 queda descartado de golpe. En modelos reales se evita el cero absoluto con suavizado, salvo que represente una imposibilidad deliberada.
Terminación y retroceso. El máximo final es \(V[3,S] = 0.018816\). Siguiendo los punteros: día 3 → S, día 2 → S, día 1 → S. La secuencia más probable es soleado, soleado, soleado. El resultado completo, de un vistazo:
| Día | Observación | \(V[S]\) | \(V[N]\) | \(V[L]\) |
|---|---|---|---|---|
| 1 | Paseó | 0.42 | 0.06 | 0 |
| 2 | Casa | 0.0336 | 0.0189 | 0.0189 |
| 3 | Paseó | 0.018816 | 0.001134 | 0 |
El resultado ilustra la esencia del modelo: aunque quedarse en casa el día 2 sugiere mal tiempo, la persistencia del sol (\(0.8\) de soleado a soleado) combinada con que quedarse en casa en día soleado es posible (\(0.1\)) hace que “todo soleado” gane a cualquier ruta con nubes o lluvia.
Nota
En la práctica se trabaja con logaritmos. Multiplicar muchas probabilidades pequeñas provoca underflow numérico. Para probabilidades positivas, el máximo de un producto equivale al máximo de la suma de sus logaritmos, así que se rellena la tabla con sumas de log-probabilidades: el camino ganador es el mismo y los números no se desvanecen. Los ceros —como el \(V[1,L] = 0\) del ejemplo— se representan como \(-\infty\), o se evitan con suavizado cuando no expresan una imposibilidad deliberada.
Tip
Viterbi frente a Beam Search. Viterbi es exacto porque aplica programación dinámica: para cada posición y estado conserva únicamente el mejor camino parcial que llega a esa celda; los demás caminos que llegan al mismo estado en la misma posición no pueden producir una solución final mejor, así que se descartan sin enumerar todas las secuencias. En traducción automática, el espacio de secuencias posibles es enorme —longitud variable y todo el vocabulario en cada paso— y a menudo se utiliza Beam Search como aproximación: conserva solo las \(b\) mejores hipótesis. Exactitud frente a escalabilidad.
6 Dónde encaja esto
Los HMM son el puente clásico entre la clasificación probabilística ingenua y las redes secuenciales: Naive Bayes ignora el orden, las cadenas de Markov modelan dependencias entre etiquetas vecinas, y las RNN pueden aprender dependencias más amplias mediante estados vectoriales densos. En aplicaciones actuales, el etiquetado suele abordarse con modelos neuronales y modelos preentrenados, mientras que los CRF siguen siendo útiles como modelos discriminativos y como capas de decodificación (por ejemplo, una capa CRF sobre una red de representación). Viterbi, por su parte, sigue vivo en corrección ortográfica, alineación de secuencias y decodificación: resulta aplicable cuando la puntuación de una secuencia se descompone en probabilidades o costes locales, como ocurre en los HMM y otros modelos de estados finitos.