La máquina de vectores de soporte estructurada es un algoritmo de aprendizaje automático que generaliza el clasificador de la máquina de vectores de soporte (SVM). Mientras que el clasificador SVM admite la clasificación binaria , la clasificación multiclase y la regresión , la SVM estructurada permite el entrenamiento de un clasificador para etiquetas de salida estructuradas generales .
Por 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 pares de etiquetas de salida y de muestra correctos. 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 más probable.
Para un conjunto de instancias de entrenamiento , de un espacio muestral y un espacio de etiquetas , el SVM estructurado 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ón mide una distancia en el espacio de etiquetas y es una función arbitraria (no necesariamente una métrica ) que satisface y . La función es una función característica, que extrae un vector de características de una muestra y una etiqueta dadas. El diseño de esta función depende en gran medida de la aplicación.
Debido a que la función de riesgo regularizada anterior no es diferenciable, a menudo se la reformula en términos de un programa cuadrático introduciendo una variable de holgura para cada muestra, cada una de las cuales representa el valor del máximo. La formulación primaria estándar de SVM estructurada se presenta a continuación.
En el momento de la prueba, solo se conoce una muestra y una función de predicción la asigna a una etiqueta predicha del espacio de etiquetas . Para las 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 etiquetas es la etiqueta predicha. La solució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 , la solución del maximizador puede ser un problema difícil.
El programa cuadrático anterior implica una cantidad muy grande, posiblemente infinita, de restricciones de desigualdad lineal. En general, la cantidad de desigualdades es demasiado grande para optimizarla explícitamente. En cambio, el problema se resuelve utilizando la generación de restricciones retrasadas, donde solo se utiliza un subconjunto finito y pequeño de las restricciones. La optimización sobre un subconjunto de las restricciones amplía el conjunto factible y producirá una solución que proporciona un límite inferior al objetivo. Para probar si la solución viola las restricciones de las desigualdades del conjunto completo, se debe resolver un problema de separación. A medida que las desigualdades se descomponen sobre las muestras, para cada muestra se debe resolver el siguiente problema.
El objetivo del lado derecho que se debe maximizar se compone de la constante y un término dependiente de las variables optimizadas, es decir . 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 amplía con esta restricción y se resuelve. El proceso continúa hasta que no se pueden identificar desigualdades violadas.
Si se eliminan las constantes del problema anterior, obtenemos el siguiente problema a resolver.
Este problema es muy similar al problema de inferencia. La única diferencia es la adición del término . La mayoría de las veces, se elige de manera que tenga una descomposición natural en el espacio de etiquetas. En ese caso, la influencia de se puede codificar en el problema de inferencia y resolver la restricción que más la viola es equivalente a resolver el problema de inferencia.
