La máquina estructurada de vectores de soporte es un algoritmo de aprendizaje automático que generaliza el clasificador de máquinas de vectores de soporte (SVM). Mientras que el clasificador SVM admite clasificación binaria , clasificación multiclase y regresión , el SVM estructurado permite el entrenamiento de un clasificador para etiquetas de salida estructuradas generales .
Como ejemplo, una instancia de muestra podría ser una oración en lenguaje natural y la etiqueta de salida es un árbol de análisis anotado . El entrenamiento de un clasificador consiste en mostrar pares de muestras correctas y pares de etiquetas de salida. Después del entrenamiento, el modelo SVM estructurado permite predecir para nuevas instancias de muestra la etiqueta de salida correspondiente; es decir, dada una oración en lenguaje natural, el clasificador puede producir el árbol de análisis sintáctico más probable.
Capacitación
Para un conjunto de instancias de entrenamiento , de un espacio muestral y espacio de etiqueta , la SVM estructurada minimiza la siguiente función de riesgo regularizada.
La función es convexa en porque el máximo de un conjunto de funciones afines es convexo. La funciónmide una distancia en el espacio de la etiqueta y es una función arbitraria (no necesariamente una métrica ) que satisface y . La funciónes una función de características que extrae algún vector de características de una muestra y etiqueta determinadas. El diseño de esta función depende mucho de la aplicación.
Debido a que la función de riesgo regularizada anterior no es diferenciable, a menudo se reformula en términos de un programa cuadrático mediante la introducción de una variable de holgura.para cada muestra, cada una representando el valor del máximo. La formulación primaria de SVM estructurada estándar se da como sigue.
Inferencia
En el momento de la prueba, solo una muestra es conocido, y una función de predicción lo asigna a una etiqueta predicha desde el espacio de la etiqueta . Para SVM estructuradas, dado el vector obtenido del entrenamiento, la función de predicción es la siguiente.
Por lo tanto, el maximizador sobre el espacio de la etiqueta es la etiqueta predicha. La resolución de este maximizador es el llamado problema de inferencia y es similar a hacer una predicción máxima a posteriori (MAP) en modelos probabilísticos. Dependiendo de la estructura de la función, resolver el maximizador puede ser un problema difícil.
Separación
El programa cuadrático anterior implica un número muy grande, posiblemente infinito, de restricciones de desigualdad lineal. En general, el número de desigualdades es demasiado grande para optimizarlo explícitamente. En cambio, el problema se resuelve mediante el uso de la generación de restricciones retrasada donde solo se usa un subconjunto finito y pequeño de las restricciones. La optimización sobre un subconjunto de restricciones amplía el conjunto factible y producirá una solución que proporciona un límite inferior al objetivo. Para probar si la soluciónviola las restricciones del conjunto completo de desigualdades, es necesario resolver un problema de separación. A medida que las desigualdades se descomponen en las muestras, para cada muestra el siguiente problema debe resolverse.
El objetivo del lado derecho que se va a maximizar se compone de la constante y un término que depende de las variables optimizadas, a saber . Si el objetivo del lado derecho alcanzado es menor o igual a cero, no existen restricciones violadas para esta muestra. Si es estrictamente mayor que cero, se ha identificado la restricción más violada con respecto a esta muestra. El problema se agranda por esta restricción y se resuelve. El proceso continúa hasta que no se pueden identificar desigualdades violadas.
Si las constantes se eliminan del problema anterior, obtenemos el siguiente problema a resolver.
Este problema se parece mucho al problema de la inferencia. La única diferencia es la adición del término. La mayoría de las veces, se elige de tal manera que tenga una descomposición natural en el espacio de la etiqueta. En ese caso, la influencia de puede codificarse en el problema de inferencia y resolver la restricción más violatoria es equivalente a resolver el problema de inferencia.
Referencias
- Ioannis Tsochantaridis, Thorsten Joachims , Thomas Hofmann y Yasemin Altun (2005), Métodos de margen grande para variables de salida estructuradas e interdependientes , JMLR, vol. 6, páginas 1453-1484.
- Thomas Finley y Thorsten Joachims (2008), Entrenamiento de SVM estructurales cuando la inferencia exacta es intratable , ICML 2008.
- Sunita Sarawagi y Rahul Gupta (2008), Entrenamiento de margen máximo preciso para espacios de salida estructurados , ICML 2008.
- Gökhan BakIr, Ben Taskar, Thomas Hofmann, Bernhard Schölkopf, Alex Smola y SVN Vishwanathan (2007), Predicción de datos estructurados , MIT Press.
- Vojtěch Franc y Bogdan Savchynskyy Discriminative Learning of Max-Sum Classifiers , Journal of Machine Learning Research, 9 (enero): 67-104, 2008, Microtome Publishing
- Kevin Murphy [1] Aprendizaje automático, MIT Press