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 de 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]
Clase | Algoritmo de optimización para máquinas de vectores de soporte de entrenamiento |
---|---|
Rendimiento en el peor de los casos | O ( n ³) |
Problema de optimizacion
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 a ella. 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:
- sujeto a:
donde C es un hiperparámetro de SVM y K ( x i , x j ) es la función del kernel , ambos proporcionados por el usuario; y las variablesson multiplicadores de Lagrange .
Algoritmo
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 a los multiplicadores de Lagrange, el problema más pequeño posible involucra dos de esos multiplicadores. Entonces, para dos multiplicadores cualesquiera y , las restricciones se reducen a:
y este problema reducido se puede resolver analíticamente: se necesita 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:
- Encuentra un multiplicador de Lagrange que viola las condiciones de Karush-Kuhn-Tucker (KKT) para el problema de optimización.
- Elige un segundo multiplicador y optimizar el par .
- Repita los pasos 1 y 2 hasta 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 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 hay posibles opciones para y .
Trabajo relacionado
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 , Vladimir Vapnik . [5] Se lo conoce como el "algoritmo de fragmentación". El algoritmo comienza con un subconjunto aleatorio de 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 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 a 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 una buena heurística. [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 de fila. Estos métodos resuelven problemas de programación convexa con restricciones lineales. Son métodos iterativos donde cada paso proyecta el punto primario actual en cada restricción. [1]
Ver también
Referencias
- ↑ a b c d e Platt, John (1998). "Optimización mínima secuencial: un algoritmo rápido para la formación de máquinas vectoriales de soporte" (PDF) . CiteSeerX 10.1.1.43.4376 . Cite journal requiere
|journal=
( ayuda ) - ^ Chang, Chih-Chung; Lin, Chih-Jen (2011). "LIBSVM: una biblioteca para máquinas de vectores de soporte". Transacciones ACM sobre tecnología y sistemas inteligentes . 2 (3).
- ^ Zanni, Luca (2006). "Software paralelo para la formación de máquinas vectoriales de soporte a gran escala en sistemas multiprocesador" (PDF) .
- ^ Rifkin, Ryan (2002). Todo lo viejo es nuevo de nuevo: una nueva mirada a los enfoques históricos del aprendizaje automático (tesis doctoral). Instituto de Tecnología de Massachusetts. pag. 18. hdl : 1721,1 / 17549 .
- ^ Boser, BE; Guyon, MI; Vapnik, VN (1992). "Un algoritmo de entrenamiento para clasificadores de márgenes óptimos". Actas del quinto taller anual sobre teoría del aprendizaje computacional - COLT '92 . pag. 144. CiteSeerX 10.1.1.21.3818 . doi : 10.1145 / 130385.130401 . ISBN 978-0897914970.
- ^ Osuna, E .; Freund, R .; Girosi, F. (1997). "Un algoritmo de entrenamiento mejorado para máquinas de vectores de soporte". Redes neuronales para el procesamiento de señales [1997] VII. Actas del taller IEEE de 1997 . págs. 276-285. CiteSeerX 10.1.1.392.7405 . doi : 10.1109 / NNSP.1997.622408 . ISBN 978-0-7803-4256-9.