Predicción estructurada

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 . ^[¹^]

De forma similar a las técnicas de aprendizaje supervisado de uso común, los modelos de predicción estructurados se entrenan típicamente mediante datos observados, comparando el valor predicho con el valor real para ajustar los parámetros del modelo. Debido a la complejidad del modelo y a las interrelaciones de las variables predichas, los procesos de entrenamiento e inferencia suelen ser computacionalmente inviables, por lo que se utilizan métodos de aprendizaje e inferencia 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 considerarse 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 campos, incluyendo la bioinformática , el procesamiento del lenguaje natural (PLN), el reconocimiento de voz y la visión por computadora .

Ejemplo: etiquetado de secuencias

El etiquetado de secuencias es una clase de problemas frecuentes en el PLN (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 se presenta de diversas formas, como el etiquetado de partes de la oración (etiquetado POS) y el reconocimiento de entidades nombradas . En el etiquetado POS, por ejemplo, cada palabra de una secuencia debe ser "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 puede resolverse simplemente clasificando los tokens individuales , este enfoque no tiene en cuenta el hecho empírico de que las etiquetas no aparecen de forma independiente; en cambio, cada etiqueta muestra una fuerte dependencia condicional de la etiqueta de la palabra anterior. Este hecho puede aprovecharse en un modelo de secuencia como un modelo oculto de Markov o un campo aleatorio condicional ^{[ 2 ]} que predice la secuencia completa de etiquetas para una oración (en lugar de solo etiquetas individuales) mediante el algoritmo de Viterbi .

Técnicas

Los modelos gráficos probabilísticos constituyen una amplia clase de modelos de predicción estructurada. 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 máquinas de vectores de soporte estructuradas (SVM) , las redes de lógica de Markov , la lógica suave probabilística y los modelos condicionales restringidos . Las principales técnicas son:

perceptrón estructurado

Una de las formas más sencillas de comprender los algoritmos para la predicción estructurada general es el perceptrón estructurado de Collins . ^{[ 3 ]} Este algoritmo combina el algoritmo del perceptrón para el aprendizaje de 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 como sigue:

Primero, define una función. $\phi (x,y)$ que mapea una muestra de entrenamiento $x$ y una predicción de candidatos $y$ a un vector de longitud $n$ ( $x$ y $y$ puede tener cualquier estructura; $n$ depende del problema, pero debe fijarse para cada modelo). $GEN$ ser una función que genere predicciones candidatas.
Entonces:

Dejar

w

sea un vector de peso de longitud

n

Para un número predeterminado de iteraciones:

Para cada muestra

x

en el conjunto de entrenamiento con salida verdadera

t

:

Haz una predicción

{\hat {y}}

:

{\hat {y}}={\operatorname {arg\,max} }\,\{y\in GEN(x)\}\,(w^{T},\phi (x,y))

Actualizar

w

(de

{\hat {y}}

hacia

t

):

w=w+c(-\phi (x,{\hat {y}})+\phi (x,t))

, dónde

c

es la tasa de aprendizaje .

En la práctica, encontrar el argmax sobre ${GEN}({x})$ Esto se realiza utilizando un algoritmo como Viterbi o el de suma máxima , en lugar de una búsqueda exhaustiva a través de un conjunto exponencialmente grande de candidatos.

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

Referencias

↑ Gökhan BakIr, Ben Taskar, Thomas Hofmann, Bernhard Schölkopf, Alex Smola y SVN Vishwanathan (2007), Predicción de datos estructurados , MIT Press.
1 2 Lafferty, J.; McCallum, A.; Pereira, F. (2001). "Campos aleatorios condicionales: modelos probabilísticos para la segmentación y el etiquetado de datos de secuencias" (PDF) . Actas de la 18.ª Conferencia Internacional sobre Aprendizaje Automático . págs. 282–289 .
↑ 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

[1] Gökhan BakIr, Ben Taskar, Thomas Hofmann, Bernhard Schölkopf, Alex Smola y SVN Vishwanathan (2007), Predicción de datos estructurados , MIT Press.

[Laf:McC:Per01-2] 1 2 Lafferty, J.; McCallum, A.; Pereira, F. (2001). "Campos aleatorios condicionales: modelos probabilísticos para la segmentación y el etiquetado de 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.

[

[ 3 ]