Predicción estructurada

Técnicas de aprendizaje automático supervisado

La predicción estructurada o el aprendizaje de salida estructurada es un término general para las técnicas de aprendizaje automático supervisado que implican la predicción de objetos estructurados, en lugar de valores discretos o reales . ^[1]

De manera similar a las técnicas de aprendizaje supervisado que se utilizan habitualmente, los modelos de predicción estructurados suelen entrenarse mediante datos observados en los que el valor predicho se compara con la realidad fundamental , y esto se utiliza para ajustar los parámetros del modelo. Debido a la complejidad del modelo y las interrelaciones de las variables predichas, los procesos de entrenamiento e inferencia del modelo suelen ser computacionalmente inviables, por lo que se utilizan métodos de inferencia y aprendizaje aproximados .

Aplicaciones

Un ejemplo de aplicación es el problema de traducir una oración en lenguaje natural a una representación sintáctica como un árbol de análisis sintáctico . Esto puede verse como un problema de predicción estructurada ^[2] en el que el dominio de salida estructurada es el conjunto de todos los árboles de análisis sintáctico posibles. La predicción estructurada se utiliza en una amplia variedad de dominios, incluidos la bioinformática , el procesamiento del lenguaje natural (PLN), el reconocimiento de voz y la visión artificial .

Ejemplo: etiquetado de secuencia

El etiquetado de secuencias es una clase de problemas que prevalecen en el procesamiento del lenguaje natural en los que los datos de entrada suelen ser secuenciales, por ejemplo, oraciones de texto. El problema del etiquetado de secuencias aparece de varias formas, como el etiquetado de partes del discurso (etiquetado POS) y el reconocimiento de entidades con nombre . En el etiquetado POS, por ejemplo, cada palabra de una secuencia debe estar "etiquetada" con una etiqueta de clase que represente el tipo de palabra:

El principal desafío de este problema es resolver la ambigüedad : en el ejemplo anterior, las palabras "sentence" y "tagged" en inglés también pueden ser verbos.

Si bien este problema se puede resolver simplemente realizando una clasificación de tokens individuales , este enfoque no tiene en cuenta el hecho empírico de que las etiquetas no ocurren de forma independiente; en cambio, cada etiqueta muestra una fuerte dependencia condicional de la etiqueta de la palabra anterior. Este hecho se puede explotar en un modelo de secuencia como un modelo Markov oculto o un campo aleatorio condicional ^[2] que predice la secuencia de etiquetas completa para una oración (en lugar de solo etiquetas individuales) a través del algoritmo de Viterbi .

Técnicas

Los modelos gráficos probabilísticos forman una gran clase de modelos de predicción estructurados. En particular, las redes bayesianas y los campos aleatorios son populares. Otros algoritmos y modelos para la predicción estructurada incluyen la programación lógica inductiva , el razonamiento basado en casos , las SVM estructuradas , las redes lógicas de Markov , la lógica blanda probabilística y los modelos condicionales restringidos . Las principales técnicas son:

• Campos aleatorios condicionales
• Máquinas de vectores de soporte estructuradas
• K vecinos más próximos estructurados
• Redes neuronales recurrentes , en particular redes Elman .

Perceptrón estructurado

Una de las formas más sencillas de entender los algoritmos de predicción estructurada general es el perceptrón estructurado de Collins . ^[3] Este algoritmo combina el algoritmo del perceptrón para aprender clasificadores lineales con un algoritmo de inferencia (clásicamente el algoritmo de Viterbi cuando se utiliza en datos de secuencia) y se puede describir de forma abstracta de la siguiente manera:

1. En primer lugar, defina una función que asigne una muestra de entrenamiento y una predicción candidata a un vector de longitud ( y puede tener cualquier estructura; depende del problema, pero debe ser fija para cada modelo). Sea una función que genere predicciones candidatas. ${\displaystyle \phi (x,y)}$ ${\displaystyle x}$ ${\displaystyle y}$ ${\displaystyle n}$ ${\displaystyle x}$ ${\displaystyle y}$ ${\displaystyle n}$ ${\displaystyle GEN}$
2. Entonces:

Sea un vector de peso de longitud ${\displaystyle w}$ ${\displaystyle n}$

Para un número predeterminado de iteraciones:

Para cada muestra del conjunto de entrenamiento con salida verdadera : ${\displaystyle x}$ ${\displaystyle t}$

Haz una predicción : ${\displaystyle {\hat {y}}}$ ${\displaystyle {\hat {y}}={\operatorname {arg\,max} }\,\{y\in GEN(x)\}\,(w^{T},\phi (x,y))}$

Actualización (desde hacia ): , donde es la tasa de aprendizaje . ${\displaystyle w}$ ${\displaystyle {\hat {y}}}$ ${\displaystyle t}$ ${\displaystyle w=w+c(-\phi (x,{\hat {y}})+\phi (x,t))}$ ${\displaystyle c}$

En la práctica, para encontrar el argmax se utiliza un algoritmo como Viterbi o un max-sum , en lugar de una búsqueda exhaustiva a través de un conjunto exponencialmente grande de candidatos. ${\displaystyle {GEN}({x})}$

La idea del aprendizaje es similar a la de los perceptrones multiclase .

Referencias

1. Gökhan BakIr, Ben Taskar, Thomas Hofmann, Bernhard Schölkopf, Alex Smola y SVN Vishwanathan (2007), Predicción de datos estructurados, MIT Press.
2. Lafferty, J.; McCallum, A.; Pereira, F. (2001). "Campos aleatorios condicionales: modelos probabilísticos para segmentar y etiquetar datos de secuencias" (PDF) . Actas de la 18.ª Conferencia Internacional sobre Aprendizaje Automático . págs. 282–289.
3. Collins, Michael (2002). Métodos de entrenamiento discriminativo para modelos ocultos de Markov: teoría y experimentos con algoritmos de perceptrón (PDF) . Proc. EMNLP. Vol. 10.

• Noah Smith, Predicción de la estructura lingüística, 2011.
• Michael Collins, Métodos de entrenamiento discriminativo para modelos ocultos de Markov, 2002.

Enlaces externos

• Implementación del perceptrón estructurado de Collins