¿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]

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.

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 )

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.

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:

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

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.

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í:

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.

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.

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).

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.