Optimización mínima secuencial

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 utiliza ampliamente para entrenar máquinas de vectores de soporte y está implementado por la popular herramienta LIBSVM . ^{[ 2 ] [ 3 ]} La publicación del algoritmo SMO en 1998 generó gran entusiasmo en la comunidad de SVM, ya que los métodos disponibles anteriormente para el entrenamiento de SVM eran mucho más complejos y requerían costosos solucionadores QP de terceros. ^{[ 4 ]}

Consideremos un problema de clasificación binaria con un conjunto de datos ( x ₁ , y ₁ ), ..., ( x _n , y _n ), donde x _i es un vector de entrada e y _i ∈ {-1, +1} es una etiqueta binaria que le corresponde. Una máquina de vectores de soporte de margen suave se entrena resolviendo un problema de programación cuadrática, que se expresa en forma dual de la siguiente manera:

${\displaystyle \max _{\alpha }\sum _{i=1}^{n}\alpha _{i}-{\frac {1}{2}}\sum _{i=1}^{n}\sum _{j=1}^{n}y_{i}y_{j}K(x_{i},x_{j})\alpha _{i}\alpha _{j},}$

sujeto a:

${\displaystyle 0\leq \alpha _{i}\leq C,\quad {\mbox{ para }}i=1,2,\ldots ,n,}$

${\displaystyle \sum _{i=1}^{n}y_{i}\alpha _{i}=0}$

donde C es un hiperparámetro de SVM y K ( x _i , x _j ) es la función kernel , ambos proporcionados por el usuario; y las variables${\displaystyle \alpha _{i}}$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 posible, que luego se resuelven analíticamente. Debido a la restricción de igualdad lineal que involucra a los multiplicadores de Lagrange${\displaystyle \alpha _{i}}$, el problema más pequeño posible involucra dos de esos multiplicadores. Entonces, para cualesquiera dos multiplicadores${\displaystyle \alpha _{1}}$y${\displaystyle \alpha _{2}}$, las restricciones se reducen a:

${\displaystyle 0\leq \alpha _{1},\alpha _{2}\leq C,}$

${\ Displaystyle y_ {1} \ alpha _ {1} + y_ {2} \ alpha _ {2} = k,}$

y este problema reducido puede resolverse analíticamente: basta con encontrar el mínimo de una función cuadrática unidimensional.${\displaystyle k}$es el negativo de la suma sobre el resto de los términos en la restricción de igualdad, que es fija en cada iteración.

El algoritmo procede de la siguiente manera:

1. Halla un multiplicador de Lagrange${\displaystyle \alpha _{1}}$que viola las condiciones de Karush-Kuhn-Tucker (KKT) para el problema de optimización.
2. Elige un segundo multiplicador${\displaystyle \alpha _{2}}$y optimizar el par${\displaystyle (\alpha _{1},\alpha _{2})}$.
3. Repita los pasos 1 y 2 hasta que se alcance la convergencia.

Cuando todos los multiplicadores de Lagrange satisfacen las condiciones de KKT (dentro de una tolerancia definida por el usuario), el problema se ha resuelto. Aunque se garantiza la convergencia de este algoritmo, se utilizan heurísticas para elegir el par de multiplicadores con el fin de acelerar la tasa de convergencia. Esto es fundamental para conjuntos de datos grandes, ya que hay${\displaystyle n(n-1)/2}$posibles opciones para${\displaystyle \alpha _{i}}$y${\displaystyle \alpha _{j}}$.

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 conoce como el "algoritmo de segmentació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 QP que escalan 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 segmentació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 problema QP grande puede dividirse en una serie de subproblemas QP más pequeños. Se garantiza la convergencia de una secuencia de subproblemas QP que siempre añaden al menos un violador de las condiciones de Karush-Kuhn-Tucker (KKT) . El algoritmo de agrupamiento obedece las condiciones del teorema y, por lo 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 denominados 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 primal actual sobre cada restricción. ^{[ 1 ]}

• perceptrón de núcleo