¿Qué son las SVM?

Por ahí Alfredo me preguntó qué eran las SVM o Support Vector Machines... y realmente ese debería ser tema obligado para este blog! así que ya es hora de acometer esa tarea.


Una especie de definición

Las SVM (o Máquinas de Vectores de Soporte) son un tipo de Máquinas de Aprendizaje. En particular son de esas que necesitan primero entrenarse con situaciones en las que se les dice la respuesta correcta sobre muchos ejemplos, y una vez ella se ha entrenado, entra en fase de "uso", y simplemente se convierte en una caja que devuelve la respuesta ante un nuevo caso (en pocas palabras, es un método de aprendizaje supervisado).

Quienes inventaron las SV fueron Vladimir Vapnik (una persona orientada hacia la estadística) y sus compañeros de AT&T. El método se basa en el uso de programación matemática, formulada de forma que la interpretación estadística del modelo resulta particularmente apropiada. El modelo está rigurosamente sustentado por las teorías estadísticas de aprendizaje propuestas por Vapnik.


Importancia

¿Qué tienen de particular que las hace famosas? Bueno... desde que fueron inventadas, superaron con creces la eficiencia de los algoritmos antecesores, tanto en tareas de clasificación, como de regresión. Hasta el momento, las SVMs no han sido superadas sino por ellas mismas, con los diferentes ajustes y variaciones que se han venido haciendo.


¿y para qué sirven?

Bueno, los modelos SVM nos servirán para predecir datos, siempre y cuando hayamos entrenado a la máquina. Esta predicción puede ser de varios tipos:

• predicción de clasificación binaria
  
• predicción de clasificación multi-categoría
• predicción de regresión general.
  

¿y cómo funcionan?

La forma en que trabaja es muy interesante. Supongamos que tenemos la tarea de realizar predicciones de clasificación binaria (p.e.: tenemos valores de un exámen médico rutinario de una persona, y queremos saber si tiene diabetes o no). Vamos a imaginarnos que los valores recogidos en el exámen son sólo 2, en lugar de sopotocientos. Cada paciente que efectivamente tiene diabetes lo podemos poner en un plano cartesiando (donde cada eje es uno de los dos valores que recoge el exámen médico). Colocamos a los pacientes que efectivamente tenían diabetes como círculos negros en el plano en las coordenadas que corresponden a cada uno de ellos (según sus resultados de exámen), y a los que no tenían diabetes, como rombos de centro blanco. Vamos a tener algo así:
las SVM encuentran una "superficie" que intenta separar los ejemplos negativos y positivos con el margen más grande posible a ambos lados del hiperplano. En este caso, bi-dimencional, la "superficie" sería una línea. En un caso 3D (tres atributos para cada paciente) sería un plano. En un caso de más de 3 dimensiones, sería un hiper-plano o hiper-superficie con el número apropiado de variables.

Hay muchas formas de hacer esto, propuestas por métodos estadísticos, por la gente de redes neurales, por la gente de optimización, etcétera. Lo que distingue a las SVMs es que el hiper-plano resultante se consigue logrando, como dije antes, que el margen que separa los datos es el mayor posible.


...entendiendo lo del margen, o ¿por qué lejos es mejor?

¿Y qué es eso de "margen"? Bueno, primero acudamos a la intuición, y luego definiré la palabra "margen" en este contexto. Para los datos que tenemos en el ejemplo, podríamos tener varias posibles superficies (infinitas), pero tomemos como ejemplo estas dos:


Preguntémonos ¿cuál es mejor? Vapnik demuestra estadísticamente, que mientras más lejos esté el hiper-plano de los puntos a los que clasifica, mejor. En este caso, pareciera que la Superficie A es mejor que la Superficie B.

Pero dije que iba a irme primero por la intuición: preguntémonos.... ¿Por qué lejos es mejor?

Para verlo intuitivamente, podemos imaginarnos el caso extremo, es decir, que la superficie estuviese "adherida" a algunos de los puntos de uno de los conjuntos, como en la siguiente figura:

Tengamos en cuenta que esos datos son de los pacientes para los cuales, hasta ahora, sabemos si tienen diabetes o no. Si dejamos que la superficie clasificadora esté allí, "adherida" a los pacientes sanos, intuitivamente podemos imaginar que es bastante probable que aparezca algún paciente con características similares a las de alguno de los pacientes a los cuales está "adherido" el hiper-plano. Pero cuando digo "similar", intuitivamente estamos aceptando que no hay dos pacientes exactamente iguales. Debe haber alguna pequeña diferencia. ¿Cierto?

¿Y si esa pequeña diferencia hiciera que el paciente estuviese justo un ligeramente más allá de la superficie separadora? Si eso ocurriera, la máquina diría que ese paciente pertenece al grupo de los que tienen diabetes, es decir, diría que es un "círculo negro", cuando en realidad el afortunado paciente podría no tener diabetes. Estaríamos dando un falso positivo con cierta frecuencia.

Si el hiper-plano estuviese "adherido" a los pacientes del grupo de entrenamiento que eran diabéticos, estaríamos haciendo una máquina que produciría concierta frecuencia falsos negativos (porque pacientes muy parecidos a los que ya tienen diabetes, podrían estar ya el otro lado de la superficie separadora). Uno no desearía darles falsas expectativas a un paciente, así que esto tampoco es conveniente.

Para lograr alejar la superficie de los puntos de ambos conjuntos, Vapnick define el "margen" a maximizar como la distancia entre los dos hiper-planos, paralelos al hiper-plano separador, que están, cada uno, adherido a los puntos de uno de los conjuntos. En las Superficies A y B, el "margen" vendría a ser la distancia entre las líneas punteadas que se muestran abajo:
Como podemos ver, en el caso de la Superficie A, está mucho mejor que en la B. El método, adicionalmente, coloca la superficie, en general, en la mitad de esa distancia.


¿y dónde dejamos a las Redes Neurales Artificiales?

Obviamente, las SVM están relacionadas con las redes neurales. De hecho, un modelo de SVM que use una sigmoide (aproximación a la función escalón que mencioné en mi post sobre redes neurales) como función para el cálculo de la salida, es equivalente a un perceptron (una neurona de salida binaria). En otras palabras, los parámetros para una neurona de clasificación (perceptrón), podríamos hallarlos mediante el uso del método SVM.

Cuando no es posible separar completamente los puntos de los dos conjuntos, la forma matemática en que se plantean los SVM obtiene excelentes resultados, minimizando los errores.


Kernels, o ¿qué hago cuando necesito un hiper-plano torcido?

Si nos encontráramos en un caso en el que los datos no pudieran ser separados por un hiper-plano, podría ser que una superficie no-lineal pudiera separar los conjuntos, como en el ejemplo de abajo:
.. lo que se hace en SVM (y en muchas otras técnicas) es transformar el espacio de los atributos (lo que llaman el kernel). Esto suena complicado, pero si nos fijamos en el ejemplo, podemos ver que una elipse podría resolver el problema, de la siguiente forma:
Esa sería la superficie no-lineal que necesitamos. Todo lo que hemos venido hablando, ha sido referido a hiper-planos, y claramente la elipse no es un hiper-plano. Sin embargo, sabemos que la elipse es una figura "Cónica", expresada más o menos así (en nuestro eje cartesiano del ejemplo):

a*(x1 + b)^2 + c*(x2 + d)^2 = e

donde {a, b, c, d, e} es un conjunto de constantes, y {x1, x2} nuestras variables (discúlpenme por renegar del par {x,y} jejeje).

En general, cualquier superifice cónica, termina siendo algo como esto:

a1*(x1)^2 + a2*(x1) + a3*(x1)*(x2) + a4*(x2) + a5*(x2)^2 = a6

Ahora, esto ni de casualidad es lineal en un espacio definido por las variables {x1, x2}. Pero si nos imaginamos un espacio donde las variables son esas dos, mas 3 variables nuevas (tres dimensiones) extra: {x3, x4, x5}, donde cada una de ellas representa a los términos cuadráticos de la expresión de arriba, tenemos:

x3 = x1^2

x4 = x2^2
x5 = x1*x2

Y volviendo a escribir la ecuación cónica genérica (o cuadrática, como sería mejor llamarle), tenemos que nos queda así:

a1*(x3) + a2*(x1) + a3*(x5) + a4*(x2) + a5*(x4) = a6

¡Y acá estaremos todos de acuerdo con que se trata de una ecuación bastante lineal! Dense cuenta de que lo que se desprende de todo esto, es que un hiper-plano en este espacio de atributos ampliado, equivale a una elipse en nuestro espacio bi-dimensional (definido tan sólo por {x1, x2}).

Si pudiésemos representar gráficamente lo que ocurre en este espacio 5-dimensional, sería algo así:

Repito: acá aplican ahora todos los conceptos de margen y linealidad que se habían manejado anteriormente. Como puede verse, acá el SVM, aunque modelaría un simple hiper-plano separando grupos de puntos, estaría comportándose como una superficie no-lineal.


Algunas consideraciones de modelaje del SVM y el problema a optimizar

Sin embargo, quiero hacer notar una cosa importante: este kernel cuadrático resultó bastante apropiado para el problema del ejemplo. Pero podría no ser suficiente para otro problema. En general, la estrategia de complicar el kernel depende de nuestra suposición de la estructura y complejidad de los datos, y siempre aumenta la dificultad de obtener un resultado.

Si tenemos 9 atributos principales, resolver el problema cuadrático implica añadir una cantidad mucho más grande de variables "extra", representando los cuadrados de los principales y los productos entre ellas.

Un ejemplo de un problema que no podría resolverse con un kernel cuadrático, sería este, en el que se necesitaría de un kernel basado en funciones de base radial (gaussianas):

Separar conjuntos con superficies no-lineales, es algo que se ha logrado con perceptrones clásicos multi-capa (redes neurales). Sin embargo, dado que cada perceptrón posee una función de transferencia sigmoidal (buscando comportarse como una función escalón), la optimización a la que debe acudirse en las redes neurales tipo perceptrón, equivale a una optimización de este tipo:
donde o(x) es la salida de la red (su propuesta de clasificación), y c(x) es la verdadera clasificación del individuo "x". Los w, theta, nu y tau son simplemente parámetros de las neuronas del perceptrón multicapa.

¿por qué la superficie a optimizar es así? Fácil: Porque es el error cuadrático de clasificación. El algoritmo de optimización (Backpropagation y sus primos, típicamente) va ajustando el parámetro de alguna neurona o peso de dendrita, hasta que ¡Zas! una de las neuronas cambia su salida de 0 a 1, o de 1 a 0, y con ello la respuesta de la red, posiblemente. Se sigue moviendo levemente (según un parámetro de paso) los parámetros, y posiblemente no pasa nada, hasta que se cruza otro límite de alguna de las sigmoides, y ¡Zas! ocurre otro cambio de 0 a 1, o de 1 a 0.

Mientras cambias los parámetros pero no pasa nada, se comporta de forma "estacionaria" la función del error (derivada = 0). Luego encuentras otro lugar, donde hay el cambio de respuesta, y la función de error cambia de forma brusca (derivada = mucho), ya que es la subida del "escalón" aproximado de la sigmoide. Nótese que idealmente el sigmoide sería lo más parecido a una función escalón, pero para que la derivada sea manejable numéricamente por los algoritmos de backpropagation, en el lugar donde está el umbral, se disminuye bastante, por lo que la red termina teniendo respuestas "difusas" cuando los elementos caen en el borde del umbral de alguna de las neuronas. Esto, a mi modo de ver, es indieseable.

Así pues, entrenar un perceptrón multi-capa implica un problema de optimización:

1. no convexo
2. con múltiples puntos estacionarios (donde suelen estancarse los algoritmos de optimización)
   
3. con elevada cantidad óptimos locales
   
4. no acotado
5. asume sigmoides suavizadas (por lo que la red da respuestas difusas posteriormente)
   

Es decir: ¡todo lo que un optimizador no desea encontrar!

Es mucho más atractivo resolver un problema como el de las SVM, porque es optimización cuadrática con restricciones lineales,... es decir: de los problemas más fáciles de solucionar. Más adelante les hablaré de un método que utiliza Programación Lineal para generar perceptrones multi-capa, sin usar Backpropagation. Si el problema de resolver una red neural, hubiese sido atacado inicialmente, por gente de investigación de operaciones, dudo que hubiésen optado por algo como el Backpropagation, realmente.


¿Y cómo es eso de "Vectores de Soporte"?

Ahora, para cerrar, quiero aclarar la duda que siempre surge cuando uno conoce a las SVMs:
¿por qué el nombre?

La respuesta es sencilla: si asumimos que cada uno de los ejemplos de los que disponemos (círculos oscuroes y rombos blancos) es un vector en el espacio, resolver SVMs es: encontrar los vectores en los que podamos apoyar los hiper-planos que definan el mayor margen de separación. Es decir, buscamos los vectores en los cuales "soportar" los hiper-planos paralelos, uno hacia un conjunto, y uno hacia el otro, para trazar justo en el medio de ambos, nuestro hiper-plano de separación. Veámoslos señalados por círculos rojos en la siguiente figura:

¡Ahí los tienen!

Ahora lo de "Máquinas de Vectores de Soporte" suena menos oscuro ¿verdad?
En verdad espero que esta explicación les haya sido de utilidad ¡y disculpen lo extenso!
Para los que deseen profundizar, les recomiendo esta página: http://www.dtreg.com/svm.htm
Es mucho menos "básica" la explicación, pero mucho más completa.

NOTA: Si alguien detecta en mi post algún error, no duden en contactarme para decírmelo, ¿vale? ¡Gracias de antemano!.