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 generó mucho entusiasmo en la comunidad SVM, ya que los métodos previamente disponibles para el entrenamiento de SVM eran mucho más complejos y requerían costosos solucionadores de QP de terceros. [4]
Considere 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 y y i ∈ {-1, +1} es una etiqueta binaria correspondiente al mismo. Una máquina de vectores de soporte de margen blando se entrena resolviendo un problema de programación cuadrática, que se expresa en forma dual de la siguiente manera:
donde C es un hiperparámetro SVM y K ( xi , xj ) es la función del núcleo , 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 más pequeños posibles, que luego se resuelven analíticamente. Debido a la restricción de igualdad lineal que involucra los multiplicadores de Lagrange , el problema más pequeño posible involucra dos de esos multiplicadores. Luego, para dos multiplicadores cualesquiera 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 como sigue:
Cuando todos los multiplicadores de Lagrange satisfacen las condiciones KKT (dentro de una tolerancia definida por el usuario), el problema se resuelve. Aunque se garantiza que este algoritmo convergerá, se utilizan heurísticas para elegir el par de multiplicadores con el fin de acelerar la tasa de convergencia. Esto es fundamental para grandes conjuntos de datos, ya que existen posibles opciones para y .
Bernhard Boser, Isabelle Guyon y Vladimir Vapnik propusieron el primer enfoque para dividir grandes problemas de aprendizaje SVM en una serie de tareas de optimización más pequeñas . [5] Se conoce como "algoritmo de fragmentación". El algoritmo comienza con un subconjunto aleatorio de datos, resuelve este problema y agrega de forma iterativa ejemplos que violan las condiciones de optimización. Una desventaja de este algoritmo es que es necesario resolver los 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 de QP se puede dividir en una serie de subproblemas de QP más pequeños. Se garantiza la convergencia de una secuencia de subproblemas de QP que siempre agregan al menos un infractor de las condiciones de Karush-Kuhn-Tucker (KKT) . El algoritmo de fragmentación obedece las condiciones del teorema y, por tanto, convergerá. [1] El algoritmo SMO puede considerarse 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 de 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 en los que cada paso proyecta el punto primario actual en cada restricción. [1]
