¿Cuál es la relación entre el número de vectores de soporte y los datos de entrenamiento y el rendimiento de los clasificadores? [cerrado]

77

Estoy usando LibSVM para clasificar algunos documentos. Los documentos parecen ser un poco difíciles de clasificar como muestran los resultados finales. Sin embargo, he notado algo mientras entrenaba a mis modelos. y eso es: si mi conjunto de entrenamiento es, por ejemplo, 1000, alrededor de 800 de ellos se seleccionan como vectores de soporte. He buscado en todas partes para ver si esto es bueno o malo. Quiero decir, ¿existe una relación entre el número de vectores de soporte y el rendimiento de los clasificadores? He leído esta publicación anterior pero estoy realizando una selección de parámetros y también estoy seguro de que los atributos en los vectores de características están todos ordenados. Solo necesito saber la relación. Gracias. ps: uso un kernel lineal.

Hossein
fuente
Fwiw, RBF-SVM en 50000 dígitos MNIST (784d) da 14398 vectores de soporte, 29%.
denis

Respuestas:

162

Las máquinas vectoriales de soporte son un problema de optimización. Están intentando encontrar un hiperplano que divida las dos clases con el margen más grande. Los vectores de apoyo son los puntos que caen dentro de este margen. Es más fácil de entender si lo construye de simple a más complejo.

SVM lineal de margen duro

En un conjunto de entrenamiento donde los datos son linealmente separables y usted está usando un margen rígido (no se permite holgura), los vectores de apoyo son los puntos que se encuentran a lo largo de los hiperplanos de apoyo (los hiperplanos paralelos al hiperplano divisor en los bordes del margen )

SVM de margen duro

Todos los vectores de soporte se encuentran exactamente en el margen. Independientemente del número de dimensiones o del tamaño del conjunto de datos, el número de vectores de soporte podría ser tan pequeño como 2.

SVM lineal de margen suave

Pero, ¿y si nuestro conjunto de datos no se puede separar linealmente? Introducimos SVM de margen suave. Ya no requerimos que nuestros puntos de datos estén fuera del margen, permitimos que una cierta cantidad de ellos se desvíen de la línea hacia el margen. Usamos el parámetro de holgura C para controlar esto. (nu in nu-SVM) Esto nos da un margen más amplio y un mayor error en el conjunto de datos de entrenamiento, pero mejora la generalización y / o nos permite encontrar una separación lineal de datos que no es linealmente separable.

SVM lineal de margen suave

Ahora, el número de vectores de soporte depende de la holgura que permitamos y de la distribución de los datos. Si permitimos una gran cantidad de holgura, tendremos una gran cantidad de vectores de soporte. Si permitimos muy poca holgura, tendremos muy pocos vectores de soporte. La precisión depende de encontrar el nivel adecuado de holgura para los datos que se analizan. Algunos datos no será posible obtener un alto nivel de precisión, simplemente debemos encontrar el mejor ajuste que podamos.

SVM no lineal

Esto nos lleva a SVM no lineal. Todavía estamos tratando de dividir linealmente los datos, pero ahora estamos tratando de hacerlo en un espacio dimensional superior. Esto se hace mediante una función del kernel, que por supuesto tiene su propio conjunto de parámetros. Cuando traducimos esto de nuevo al espacio de características original, el resultado es no lineal:

ingrese la descripción de la imagen aquí

Ahora, la cantidad de vectores de soporte aún depende de la holgura que permitamos, pero también depende de la complejidad de nuestro modelo. Cada giro y giro en el modelo final en nuestro espacio de entrada requiere uno o más vectores de soporte para definir. En última instancia, la salida de un SVM son los vectores de soporte y un alfa, que en esencia define cuánta influencia tiene ese vector de soporte específico en la decisión final.

Aquí, la precisión depende de la compensación entre un modelo de alta complejidad que puede sobreajustar los datos y un margen grande que clasificará incorrectamente algunos de los datos de entrenamiento en aras de una mejor generalización. La cantidad de vectores de soporte puede variar desde muy pocos hasta cada punto de datos si sobreajusta completamente sus datos. Esta compensación se controla a través de C y mediante la elección de kernel y parámetros del kernel.

Supongo que cuando dijo rendimiento se refería a la precisión, pero pensé que también hablaría del rendimiento en términos de complejidad computacional. Para probar un punto de datos utilizando un modelo SVM, debe calcular el producto escalar de cada vector de soporte con el punto de prueba. Por lo tanto, la complejidad computacional del modelo es lineal en el número de vectores de soporte. Menos vectores de soporte significa una clasificación más rápida de los puntos de prueba.

Un buen recurso: un tutorial sobre máquinas de vectores de soporte para el reconocimiento de patrones

karenu
fuente
¡gran respuesta! pero el enlace ya no funciona ... ¿puedes actualizarlo?
Matteo
"El número de vectores de soporte puede variar desde muy pocos hasta todos los puntos de datos si sobreajusta completamente sus datos". En resumen, una gran cantidad de vectores de soporte no es bueno. Entonces, la pregunta es, ¿800 SV de 1000 muestras de entrenamiento son "grandes"?
Kanmani
¡Gracias! ... Siguiendo enlaces y enlaces encontré esta bonita explicación! :)
leandr0garcia
29

800 de 1000 básicamente le dice que el SVM necesita usar casi todas las muestras de entrenamiento para codificar el conjunto de entrenamiento. Eso básicamente te dice que no hay mucha regularidad en tus datos.

Parece que tienes problemas importantes por no tener suficientes datos de entrenamiento. Además, quizás piense en algunas características específicas que separan mejor estos datos.

Chris A.
fuente
9
Seleccioné esto como la respuesta. Las largas respuestas anteriores son explicaciones irrelevantes de C&P SVM
Valentin Heinitz
7
Estoy de acuerdo. Aunque las otras respuestas intentaron dar un buen resumen, esta es la más relevante para la operación. Si la porción de SV es grande, indica memorización, no aprendizaje, y esto significa mala generalización => error fuera de muestra (error de conjunto de prueba) ser grande.
Kai
12

Tanto el número de muestras como el número de atributos pueden influir en el número de vectores de soporte, haciendo que el modelo sea más complejo. Creo que usa palabras o incluso ngramas como atributos, por lo que hay bastantes de ellos, y los modelos de lenguaje natural son muy complejos en sí mismos. Entonces, 800 vectores de soporte de 1000 muestras parecen estar bien. (También preste atención a los comentarios de @ karenu sobre los parámetros C / nu que también tienen un gran efecto en el número de SV).

Para tener intuición sobre esta idea principal de retiro del mercado de SVM. SVM trabaja en un espacio de características multidimensional e intenta encontrar un hiperplano que separe todas las muestras dadas. Si tiene muchas muestras y solo 2 características (2 dimensiones), los datos y el hiperplano pueden verse así:

ingrese la descripción de la imagen aquí

Aquí solo hay 3 vectores de soporte, todos los demás están detrás de ellos y, por lo tanto, no juegan ningún papel. Tenga en cuenta que estos vectores de soporte están definidos por solo 2 coordenadas.

Ahora imagina que tienes un espacio tridimensional y, por tanto, los vectores de soporte están definidos por 3 coordenadas.

ingrese la descripción de la imagen aquí

Esto significa que hay un parámetro más (coordenada) para ajustar, y este ajuste puede necesitar más muestras para encontrar el hiperplano óptimo. En otras palabras, en el peor de los casos, SVM encuentra solo 1 coordenada de hiperplano por muestra.

Cuando los datos están bien estructurados (es decir, mantienen los patrones bastante bien), solo se pueden necesitar varios vectores de soporte; todos los demás se quedarán atrás. Pero el texto es muy, muy mala información estructurada. SVM hace todo lo posible, tratando de ajustar la muestra lo mejor posible y, por lo tanto, toma como vectores de soporte incluso más muestras que gotas. A medida que aumenta el número de muestras, esta "anomalía" se reduce (aparecen muestras más insignificantes), pero el número absoluto de vectores de apoyo se mantiene muy alto.

amigo
fuente
¡Gracias por tu respuesta! ¿Tiene alguna referencia a lo que mencionó en el último párrafo? "Cuando los datos están bien estructurados (es decir, mantienen los patrones bastante bien), solo se pueden necesitar varios vectores de soporte; todos los demás permanecerán detrás de ellos. Pero el texto es datos muy, muy mal estructurados. SVM hace todo lo posible, tratando de ajustar la muestra lo mejor posible, y por lo tanto toma como vectores de soporte incluso más muestras que gotas ". thx
Hossein
Esto no es correcto: puede tener un conjunto de datos tridimensionales con solo 2 vectores de soporte, si el conjunto de datos es separable linealmente y tiene la distribución correcta. También puede tener el mismo conjunto de datos exacto y terminar con un 80% de vectores de soporte. Todo depende de cómo establezca C. De hecho, en nu-svm puede controlar el número de vectores de soporte estableciendo nu muy bajo (.1)
karenu
@karenu: I no dijo que el crecimiento de número de atributos siempre conduce a un crecimiento del número de vectores de soporte, que acaba de decir que incluso con fijo C / parámetros nu número de vectores de soporte depende del número de dimensiones de características y número de muestras . Y para los datos de texto, que están muy mal estructurados por su naturaleza, el número de vectores de soporte dentro del margen (SVM de margen rígido es inaplicable para la clasificación de texto incluso con núcleos de orden superior) siempre será alto.
ffriend
@Hossein: Me refiero a la separabilidad lineal. Imagínese la tarea de clasificar el spam. Si sus mensajes de spam casi siempre contienen palabras como "Viagra", "comprar", "dinero" y sus mensajes de radioaficionados contienen solo "casa", "hola", "saludos", entonces sus datos están bien estructurados y pueden separarse fácilmente estos vectores de palabras. Sin embargo, en la práctica tiene una combinación de palabras buenas y malas y, por lo tanto, sus datos no tienen patrones obvios. Si tiene 3 palabras de spam dict y 3 de ham, ¿cómo debería clasificar el mensaje? Necesita más funciones, y esa es una de las razones por las que SVM utiliza más vectores de soporte.
ffriend
@friend Me parece engañoso. Decir que depende de mí hace que parezca que si su conjunto de datos aumenta, su número de sv aumentará, que de alguna manera existe una relación entre el número de muestras (o el número de dimensiones) y el número de vectores de soporte. Existe una relación entre la complejidad del modelo y los SV, y los conjuntos de datos más grandes con dimensiones más altas tienden a tener modelos más complejos, pero el tamaño del conjunto de datos o la dimensionalidad no dicta directamente el número de SV.
karenu
7

La clasificación de SVM es lineal en el número de vectores de soporte (SV). El número de SV es, en el peor de los casos, igual al número de muestras de entrenamiento, por lo que 800/1000 aún no es el peor de los casos, pero sigue siendo bastante malo.

Por otra parte, 1000 documentos de formación es un pequeño conjunto de formación. Debe comprobar lo que sucede cuando escala hasta 10000 o más documentos. Si las cosas no mejoran, considere usar SVM lineales, entrenadas con LibLinear , para la clasificación de documentos; aquellos se escalan mucho mejor (el tamaño del modelo y el tiempo de clasificación son lineales en el número de características e independientes del número de muestras de entrenamiento).

Fred Foo
fuente
Solo por curiosidad, ¿qué le hace suponer que el OP no está usando una SVM lineal? Debo haberlo perdido si estaba usando algún kernel no lineal.
Chris A.
1
@ChrisA .: sí, estoy hablando solo de velocidad. La precisión debería ser aproximadamente la misma cuando se utilizan las mismas configuraciones (aunque tanto LibSVM como LibLinear usan cierta aleatorización, por lo que ni siquiera se garantiza que sea la misma en varias ejecuciones del mismo algoritmo de entrenamiento).
Fred Foo
1
Espera, ¿esta aleatorización llega al clasificador final? No he mirado el código de ninguna de las bibliotecas, pero esto viola toda mi comprensión de que se trata de un problema de optimización convexa con un mínimo único.
Chris A.
1
Esta aleatorización solo se realiza en la etapa de entrenamiento como aceleración. El problema de la optimización es realmente convexo.
Fred Foo
1
La aleatorización solo lo ayuda a converger hacia la solución óptima más rápido.
karenu
-1

Existe cierta confusión entre las fuentes. En el libro de texto ISLR 6th Ed, por ejemplo, C se describe como un "presupuesto de violación de límites" de donde se sigue que un C más alto permitirá más violaciones de límites y más vectores de apoyo. Pero en implementaciones de svm en R y python el parámetro C se implementa como "penalización por violación" que es lo opuesto y luego observará que para valores más altos de C hay menos vectores de soporte.

user9365328
fuente