La optimización mínima secuencial ( SMO ) es un algoritmo para resolver el problema de programación cuadrática (QP) que surge durante el entrenamiento de máquinas de vectores de soporte (SVM). Fue inventado por John Platt en 1998 en Microsoft Research . [1] SMO se usa ampliamente para entrenar máquinas de vectores de soporte y se implementa mediante la popular herramienta LIBSVM . [2] [3] La publicación del algoritmo SMO en 1998 ha generado mucho entusiasmo en la comunidad SVM, ya que los métodos disponibles anteriormente para el entrenamiento de SVM eran mucho más complejos y requerían solucionadores QP costosos de terceros. [4]
Consideremos un problema de clasificación binaria con un conjunto de datos ( x 1 , y 1 ), ..., ( x n , y n ), donde x i es un vector de entrada e y i ∈ {-1, +1} es una etiqueta binaria que le corresponde. Se entrena una máquina de vectores de soporte de margen suave resolviendo un problema de programación cuadrática, que se expresa en la forma dual de la siguiente manera:
donde C es un hiperparámetro SVM y K ( x i , x j ) es la función kernel , ambos proporcionados por el usuario; y las variables son multiplicadores de Lagrange .
SMO es un algoritmo iterativo para resolver el problema de optimización descrito anteriormente. SMO divide este problema en una serie de subproblemas lo más pequeños posibles, que luego se resuelven analíticamente. Debido a la restricción de igualdad lineal que involucra a los multiplicadores de Lagrange , el problema más pequeño posible involucra dos de esos multiplicadores. Luego, para cualesquiera dos multiplicadores y , las restricciones se reducen a:
y este problema reducido se puede resolver analíticamente: es necesario encontrar un mínimo de una función cuadrática unidimensional. es el negativo de la suma sobre el resto de términos en la restricción de igualdad, que se fija en cada iteración.
El algoritmo procede de la siguiente manera:
Cuando todos los multiplicadores de Lagrange satisfacen las condiciones KKT (dentro de una tolerancia definida por el usuario), el problema se ha resuelto. Aunque se garantiza que este algoritmo converge, se utilizan heurísticas para elegir el par de multiplicadores de modo de acelerar la tasa de convergencia. Esto es fundamental para grandes conjuntos de datos, ya que existen opciones posibles para y .
El primer enfoque para dividir grandes problemas de aprendizaje de SVM en una serie de tareas de optimización más pequeñas fue propuesto por Bernhard Boser, Isabelle Guyon y Vladimir Vapnik . [5] Se lo conoce como "algoritmo de fragmentación". El algoritmo comienza con un subconjunto aleatorio de los datos, resuelve este problema y agrega iterativamente ejemplos que violan las condiciones de optimalidad. Una desventaja de este algoritmo es que es necesario resolver problemas de QP escalando con el número de SV. En conjuntos de datos dispersos del mundo real, SMO puede ser más de 1000 veces más rápido que el algoritmo de fragmentación. [1]
En 1997, E. Osuna, R. Freund y F. Girosi demostraron un teorema que sugiere un conjunto completamente nuevo de algoritmos QP para SVM. [6] En virtud de este teorema, un gran problema QP se puede descomponer en una serie de subproblemas QP más pequeños. Se garantiza que una secuencia de subproblemas QP que siempre agreguen al menos un infractor de las condiciones de Karush-Kuhn-Tucker (KKT) convergerá. El algoritmo de fragmentación obedece las condiciones del teorema y, por lo tanto, convergerá. [1] El algoritmo SMO se puede considerar un caso especial del algoritmo de Osuna, donde el tamaño de la optimización es dos y ambos multiplicadores de Lagrange se reemplazan en cada paso con nuevos multiplicadores que se eligen mediante buenas heurísticas. [1]
El algoritmo SMO está estrechamente relacionado con una familia de algoritmos de optimización llamados métodos Bregman o métodos de acción por filas. Estos métodos resuelven problemas de programación convexa con restricciones lineales. Son métodos iterativos donde cada paso proyecta el punto primario actual sobre cada restricción. [1]
