Máquinas de vectores soporte

Una máquina de vectores de soporte [ səˈpɔːt ˈvektə məˈʃiːn ] ( SVM , la traducción del inglés , “ máquina de vectores de soporte ” o método de vectores de soporte no está en uso) sirve como clasificador (ver clasificación ) y regresor (ver análisis de regresión ). Una máquina de vectores de soporte divide un conjunto de objetos en clases de tal manera que el área más amplia posible alrededor de los límites de la clase permanece libre de objetos; se trata de un llamado amplio margen clasificador (Esp. "amplio margen clasificador").

Las máquinas de vectores de soporte no son máquinas en el sentido convencional, es decir, no constan de componentes tangibles. Es un método puramente matemático de reconocimiento de patrones que se implementa en programas de computadora . En consecuencia, la parte de la máquina de nombres no se refiere a una máquina , sino al área de origen de las máquinas de vectores de soporte, aprendizaje automático .

Funcionalidad básica

Dos posibles líneas divisorias con diferentes tamaños de borde

El punto de partida para construir una máquina de vectores de soporte es un conjunto de objetos de entrenamiento, para los cuales se sabe a qué clase pertenecen. Cada objeto está representado por un vector en un espacio vectorial . La tarea de la máquina de vectores de apoyo es colocar un hiperplano en este espacio , que actúa como una superficie de separación y divide los objetos de entrenamiento en dos clases. Se maximiza la distancia entre los vectores más cercanos al hiperplano. Este borde ancho y vacío debería garantizar más adelante que los objetos que no corresponden exactamente a los objetos de entrenamiento se clasifiquen de la manera más confiable posible.

Al utilizar el hiperplano, no es necesario considerar todos los vectores de entrenamiento. Los vectores que están más lejos del hiperplano y que están, por así decirlo, "ocultos" detrás de un frente de otros vectores no afectan la ubicación y posición del plano de separación. El hiperplano solo depende de los vectores más cercanos a él, y solo estos son necesarios para describir el plano matemáticamente exactamente. Estos vectores son los más cercanos a sus vectores de soporte de función (Engl. Support vectors ) llamados y ayudaron a soportar máquinas de vectores a su nombre.

Separabilidad lineal

Un hiperplano no puede "doblarse", de modo que una separación limpia con un hiperplano solo es posible si los objetos se pueden separar linealmente . Esta condición generalmente no se cumple para conjuntos de objetos de entrenamiento reales. En el caso de datos separables de forma no lineal, las máquinas de vectores de soporte utilizan el truco del núcleo para dibujar un límite de clase no lineal.

La idea detrás del truco del kernel es transferir el espacio vectorial y, por lo tanto, también los vectores de entrenamiento en él a un espacio de dimensiones superiores. En un espacio con un número suficientemente alto de dimensiones - en caso de duda, infinito - incluso el conjunto de vectores más anidado se puede separar linealmente. En este espacio de dimensiones superiores, ahora se determina el hiperplano de separación. Durante la transformación inversa en el espacio de dimensiones inferiores, el hiperplano lineal se convierte en una hipersuperficie no lineal, posiblemente incluso no contigua , que separa claramente los vectores de entrenamiento en dos clases.

Hay dos problemas con este proceso: la alta transformación es extremadamente pesada computacionalmente y la representación de la interfaz en el espacio de baja dimensión es generalmente increíblemente compleja y por lo tanto prácticamente inutilizable. Aquí es donde entra el truco del kernel. Si se utilizan funciones de kernel adecuadas para describir la interfaz, que describen el hiperplano en las dimensiones altas y siguen siendo “benignas” en las dimensiones bajas, es posible implementar la transformación directa e inversa sin tener que realizarla aritméticamente. Aquí, también, algunos de los vectores son suficientes, a saber, nuevamente los vectores de soporte, para describir completamente el límite de clase.

Tanto las máquinas de vectores de soporte lineales como no lineales se pueden diseñar de manera más flexible con variables de deslizamiento adicionales . Las variables de deslizamiento permiten al clasificador clasificar incorrectamente objetos individuales, pero al mismo tiempo "castiga" cualquier clasificación errónea. De esta forma, por un lado, se evita el sobreajuste y, por otro lado, se reduce el número necesario de vectores de apoyo.

Implementación matemática

El SVM determina basándose en un conjunto de ejemplos de entrenamiento

${\ Displaystyle \ {(\ mathbf {x} _ {i}, y_ {i}) \ mid i = 1, \ dotsc, m; \ y_ {i} \ in \ {- 1,1 \} \}}$

un hiperplano que separa las dos clases lo más claramente posible.

Esto claramente significa lo siguiente: Un vector normal  describe una línea recta a través del origen de coordenadas. Los hiperplanos corren perpendiculares a esta línea recta. Cada uno interseca la línea a una cierta distancia del origen (medida en la dirección opuesta a ). Esta distancia se llama sesgo . Juntos, el vector normal y el sesgo definen claramente un hiperplano, y lo siguiente se aplica a los puntos que le pertenecen : ${\ Displaystyle \ mathbf {w}}$${\ Displaystyle {\ tfrac {b} {\ | \ mathbf {w} \ | _ {2}}}}$${\ Displaystyle \ mathbf {w}}$${\ Displaystyle \ mathbf {x}}$

${\ Displaystyle \ langle \ mathbf {w}, \ mathbf {x} \ rangle + b = 0}$.

Para los puntos que no están en el hiperplano, el valor no es cero, sino positivo (en el lado que apunta) o negativo (en el otro lado). El letrero se puede usar para nombrar el lado en el que se encuentra el punto. ${\ Displaystyle \ mathbf {w}}$

Si el hiperplano separa las dos clases, entonces el signo es positivo para todos los puntos de una clase y negativo para todos los puntos de la otra clase. El objetivo ahora es encontrar tal hiperplano.

Si uno expresa la membresía de la clase en los ejemplos de capacitación , esto da como resultado una condición de fórmula ${\ Displaystyle y_ {i} = \ pm 1}$

${\ Displaystyle y_ {i} = \ operatorname {sgn} (\ langle \ mathbf {w}, \ mathbf {x} _ {i} \ rangle + b)}$

Si tal hiperplano existe, entonces hay infinitos muchos que difieren solo mínimamente y a veces están muy cerca de una u otra clase. Pero luego existe el riesgo de que los puntos de datos que se encontrarán en el futuro estén en el lado "incorrecto" del hiperplano y, por lo tanto, se interpreten incorrectamente.

Por lo tanto, el hiperplano debe ser tal que la distancia más pequeña de los puntos de entrenamiento al hiperplano, el llamado margen (del margen inglés , margen), se maximice para garantizar la mejor generalización posible al clasificador.

El objetivo del llamado entrenamiento es calcular los parámetros y este "mejor" hiperplano. ${\ Displaystyle \ mathbf {w}}$${\ Displaystyle b}$

El hiperplano se utiliza entonces como función de decisión . Esto significa: se supone que el signo calculado también reflejará correctamente la pertenencia a la clase para puntos de datos futuros. En particular, una computadora puede realizar la clasificación de manera fácil y automática simplemente calculando el signo.

Datos lineales separables

Muchos algoritmos de aprendizaje funcionan con un hiperplano , que se puede representar en términos bidimensionales mediante una función lineal . ¿Son dos clases de ejemplos separables entre sí por un hiperplano, es decir, H. linealmente separables , sin embargo, suele haber un número infinito de hiperplanos que separan las dos clases entre sí. El SVM se diferencia de otros algoritmos de aprendizaje en que selecciona el que tiene la norma cuadrática mínima de todos los hiperplanos de separación posibles , de modo que se aplica lo mismo para cada ejemplo de entrenamiento . Esto equivale a maximizar la distancia más pequeña al hiperplano (el margen ). Según la teoría del aprendizaje estadístico , la complejidad de la clase de todos los hiperplanos con un cierto margen es menor que la de la clase de todos los hiperplanos con un margen más pequeño. A partir de esto, se pueden derivar los límites superiores para el error de generalización esperado de la SVM. ${\ Displaystyle \ | \ mathbf {w} \ | _ {2} ^ {2}}$${\ Displaystyle y_ {i} (\ langle \ mathbf {w}, \ mathbf {x} _ {i} \ rangle + b) \ geq 1}$${\ Displaystyle \ mathbf {x} _ {i}}$

El problema de optimización se puede escribir como:

Minimice el plazo ajustando las variables ,${\ Displaystyle {\ frac {1} {2}} \ | \ mathbf {w} \ | _ {2} ^ {2}}$${\ Displaystyle \ mathbf {w}, b}$

de modo que la restricción se aplique a todos .${\ Displaystyle y_ {i} (\ langle \ mathbf {w}, \ mathbf {x} _ {i} \ rangle + b) \ geq 1}$${\ Displaystyle 1 \ leq i \ leq m}$

Datos separables no linealmente

Por regla general, los ejemplos de formación no se pueden separar de forma estrictamente lineal. Esto puede incluir errores de medición en los datos, o el hecho de que las distribuciones de las dos clases se superponen naturalmente. En este caso, el problema de optimización se modifica de tal manera que es posible que se produzcan violaciones de las condiciones secundarias, pero las violaciones deben mantenerse lo más pequeñas posible. Para ello, se introduce una variable de deslizamiento positivo para cada condición secundaria, cuyo valor es la violación de las condiciones secundarias. significa que se infringe la condición secundaria. Dado que la suma de las infracciones debe mantenerse lo más pequeña posible, la suma de los errores se agrega a la función de destino y, por lo tanto, también se minimiza. Además, esta suma se multiplica por una constante positiva que regula el equilibrio entre la minimización y la correcta clasificación de los ejemplos de entrenamiento. El problema de optimización tiene la siguiente forma: ${\ Displaystyle m}$ ${\ Displaystyle \ xi _ {i}}$${\ Displaystyle \ xi _ {i}> 0}$${\ Displaystyle C}$${\ Displaystyle {\ frac {1} {2}} \ | \ mathbf {w} \ | _ {2} ^ {2}}$

Minimice el plazo ajustando las variables ,${\ Displaystyle {\ frac {1} {2}} \ | \ mathbf {w} \ | _ {2} ^ {2} + C \ sum _ {i = 1} ^ {m} \ xi _ {i} }$${\ Displaystyle \ mathbf {w}, b, \ xi _ {i}}$

de modo que la restricción se aplique a todos .${\ Displaystyle y_ {i} (\ langle \ mathbf {w, x_ {i}} \ rangle + b) \ geq 1- \ xi _ {i}}$${\ Displaystyle 1 \ leq i \ leq m}$

Problema dual

Ambos criterios de optimización son convexos y pueden resolverse de manera eficiente con métodos modernos. Esta simple optimización y la propiedad que soporta las máquinas vectoriales evitan en gran medida el ajuste excesivo a los datos de prueba utilizados para diseñar el clasificador, han hecho que el método sea extremadamente popular y ampliamente utilizado.

Ejemplo de clasificación con SVM. El hiperplano separador (línea negra) y los vectores de apoyo (encerrados en un círculo en turquesa fino) se pueden ver en la sala de entrada.

El problema de optimización descrito anteriormente generalmente se resuelve en su forma dual. Esta formulación es equivalente al problema primario en el sentido de que todas las soluciones al problema dual son también soluciones al problema primario. La conversión resulta del hecho de que el vector normal se puede escribir como una combinación lineal de ejemplos de entrenamiento: ${\ Displaystyle \ mathbf {w}}$

${\ Displaystyle \ mathbf {w} = \ sum _ {i = 1} ^ {m} \ alpha _ {i} y_ {i} \ mathbf {x} _ {i}}$

La forma dual se deriva con la ayuda de los multiplicadores de Lagrange y las condiciones de Karush-Kuhn-Tucker . Es:

maximizar para : ,${\ Displaystyle \ mathbf {\ alpha}}$${\ Displaystyle \ sum _ {i = 1} ^ {m} \ alpha _ {i} - {\ frac {1} {2}} \ sum _ {i = 1} ^ {m} \ sum _ {j = 1} ^ {m} \ alpha _ {i} \ alpha _ {j} y_ {i} y_ {j} \ langle \ mathbf {x} _ {i}, \ mathbf {x} _ {j} \ rangle}$

para que las restricciones y se apliquen.${\ Displaystyle 0 \ leq \ alpha _ {i} \ leq C}$${\ Displaystyle \ sum _ {i = 1} ^ {m} \ alpha _ {i} y_ {i} = 0}$

La regla de clasificación resulta así:

${\ displaystyle f (\ mathbf {x}) = \ operatorname {sgn} (\ langle \ mathbf {w, x} \ rangle + b) = \ operatorname {sgn} \ left (\ sum _ {i = 1} ^ {m} \ alpha _ {i} y_ {i} \ langle \ mathbf {x_ {i}, x} \ rangle + b \ right)}$

El SVM obtuvo su nombre de un subconjunto especial de los puntos de entrenamiento, que son variables de Lagrange . Estos se denominan vectores de soporte y están en el margen (si ) o dentro del margen ( ). ${\ Displaystyle \ alpha _ {i} \ neq 0}$${\ Displaystyle y_ {i} (\ langle \ mathbf {w, x} \ rangle + b) = 1}$${\ Displaystyle \ xi _ {i}> 0}$

Extensión no lineal con funciones del kernel

El algoritmo descrito anteriormente clasifica los datos mediante una función lineal. Sin embargo, esto solo es óptimo si el problema de clasificación subyacente también es lineal. En muchas aplicaciones, este no es el caso. Una posible salida es mapear los datos en un espacio de mayores dimensiones.

${\ Displaystyle \ phi \ colon \ mathbb {R} ^ {d_ {1}} \ rightarrow \ mathbb {R} ^ {d_ {2}}, \ mathbf {x} \ mapsto \ phi (\ mathbf {x}) }$

Se aplica lo siguiente . Este mapeo aumenta el número de posibles separaciones lineales (teorema de Cover). Las SVM se caracterizan por el hecho de que esta extensión se puede integrar de forma muy elegante. En el problema de optimización en el que se basa el algoritmo en la formulación presentada en último lugar, los puntos de datos solo se incluyen en productos escalares. Por lo tanto, es posible reemplazar el producto escalar en el espacio de entrada con un producto escalar en y calcularlo directamente en su lugar. El costo de este cálculo se puede reducir en gran medida si en su lugar se usa una función de kernel definida positivamente : ${\ Displaystyle d_ {1} <d_ {2}}$${\ Displaystyle \ mathbf {x} _ {i}}$${\ Displaystyle \ langle \ mathbf {x} _ {i}, \ mathbf {x} _ {j} \ rangle}$${\ Displaystyle \ mathbb {R} ^ {d_ {1}}}$${\ Displaystyle \ mathbb {R} ^ {d_ {2}}}$${\ Displaystyle \ langle \ phi (\ mathbf {x} _ {i}), \ phi (\ mathbf {x} _ {j}) \ rangle}$

${\ Displaystyle k (\ mathbf {x} _ {i}, \ mathbf {x} _ {j}) = \ langle \ phi (\ mathbf {x} _ {i}), \ phi (\ mathbf {x} _ {j}) \ rangle}$

Mediante este método, un hiperplano (es decir, una función lineal) en un espacio de alta dimensión se puede calcular implícitamente. El clasificador resultante tiene la forma

${\ Displaystyle f (\ mathbf {x}) = \ operatorname {sgn} (\ langle \ mathbf {w}, \ mathbf {\ phi (x)} \ rangle + b) = \ operatorname {sgn} \ left (\ suma _ {i = 1} ^ {m} \ alpha _ {i} y_ {i} k (\ mathbf {x} _ {i}, \ mathbf {x}) + b \ right)}$

con . Al utilizar funciones del kernel , las SVM también pueden operar en estructuras generales como gráficos o cadenas y, por lo tanto, son muy versátiles. Aunque el mapeo utiliza implícitamente un espacio posiblemente de dimensión infinita, SVM todavía generaliza muy bien. Se puede demostrar que el error de prueba esperado para los clasificadores de margen máximo es limitado y no depende de la dimensionalidad del espacio. ${\ Displaystyle \ textstyle \ mathbf {w} = \ sum _ {i = 1} ^ {m} \ alpha _ {i} y_ {i} \ phi (\ mathbf {x} _ {i})}$${\ Displaystyle \ phi}$

historia

Ronald A. Fisher tuvo la idea de la separación a través de un hiperplano ya en 1936 . Frank Rosenblatt lo retomó en 1958 en su contribución a la teoría de las redes neuronales artificiales . La idea de las máquinas de vectores de soporte se remonta al trabajo de Wladimir Wapnik y Alexei Jakowlewitsch Chervonenkis . A nivel teórico, el algoritmo está motivado por el principio de minimización del riesgo estructural, que establece que no solo el error de entrenamiento sino también la complejidad del modelo utilizado determinan la capacidad de generalización de un clasificador. Las SVM tuvieron su gran avance a mediados de la década de 1990, y en los últimos años se han publicado numerosos avances y modificaciones.

software

Bibliotecas para SVM

• libsvm , implementado en C ++ y portado a Java
• liblinear , implementado en C ++ y portado a Java
• SVMlight , basado en C

Software de aprendizaje automático y minería de datos que incluye SVM

• GNU Octave usa SVMlight
• KNIME
• Matlab usa libsvm , SVMlight y Spider
• RapidMiner usa libsvm y una SVM implementada en Java
• Scikit-learn usa libsvm y liblinear .
• Shogun usa libsvm y SVMlight
• WEKA usa libsvm y Spider

Módulos SVM para lenguajes de programación (selección)

• Perl tiene módulos para libsvm y SVMlight
• R , tiene paquetes basados ​​en libsvm (paquete e1071 ), SVMlight (paquete klaR ) y tiene el paquete kernlab para el aprendizaje del kernel con SVM
• Ruby tiene módulos para libsvm y SVMlight

literatura

• Bernhard Schölkopf , Alex Smola: Aprendizaje con núcleos: máquinas de vectores de soporte, regularización, optimización y más (Computación adaptativa y aprendizaje automático) , MIT Press, Cambridge, MA, 2002, ISBN 0-262-19475-9 .
• Ingo Steinwart , Andreas Christmann: Support Vector Machines , Springer, Nueva York, 2008. ISBN 978-0-387-77241-7 . 602 págs.
• Nello Cristianini, John Shawe-Taylor: Métodos kernel para el análisis de patrones , Cambridge University Press, Cambridge, 2004, ISBN 0-521-81397-2
• Christopher JC Burges: Tutorial sobre máquinas de vectores de apoyo para el reconocimiento de patrones , la minería de datos y el descubrimiento de conocimientos, 2 (2): 121-167, 1998.
• Vladimir Vapnik : teoría del aprendizaje estadístico , Wiley, Chichester, GB, 1998.
• Vladimir Vapnik: The Nature of Statistical Learning Theory , Springer Verlag, Nueva York, NY, EE. UU., 1995.

Evidencia individual

1. ↑ Schölkopf, Smola: Learning with Kernels, MIT Press, 2001
2. ↑ Fisher, RA (1936), "El uso de mediciones múltiples en problemas taxonómicos", en Annals of Eugenics 7 : 179-188, doi : 10.1111 / j.1469-1809.1936.tb02137.x
3. ↑ Rosenblatt, F. (1958), "El perceptrón, un modelo probabilístico para el almacenamiento y la organización de la información en el cerebro", en Psychological Review, 62/386, págs. 386-408, doi : 10.1037 / h0042519 .
4. ↑ Vapnik y Chervonenkis, Teoría del reconocimiento de patrones, 1974 (traducción al alemán: Wapnik y Tschervonenkis, Teoría del reconocimiento de patrones, 1979)
5. ^ David Meyer y otros: R-Paket e1071. Funciones varias del Departamento de Estadística, Grupo de teoría de la probabilidad (anteriormente: E1071), TU Wien. En: CRAN. The R Foundation, consultado el 14 de mayo de 2016 (inglés, versión actual: 1.6-7). 
6. ↑ Uwe Ligges y otros: R-Paket klaR. Clasificación y visualización. En: CRAN. The R Foundation, consultado el 14 de mayo de 2016 (inglés, versión actual: 0.6-12). 
7. ↑ Alexandros Karatzoglou, Alex Smola, Kurt Hornik: kernlab de R-Paket. Laboratorio de aprendizaje automático basado en kernel. En: CRAN. The R Foundation, consultado el 14 de mayo de 2016 (inglés, versión actual: 0.9-24).