¿Cuál es el cuello de botella de velocidad en sklearn.svm.SVC.predict?

Question

Estoy trabajando con algunas imágenes de alta resolución de especímenes en tubos de ensayo y he encontrado que el uso de un SVC para clasificar cada píxel por el valor HSV me ayuda a un gran trabajo en la segmentación de sólo el espécimen del resto de la imagen.

El problema es que es no trivialmente lento hacer un predicción (en otras preguntas del foro se pregunta por la formación, esto no es así). Una imagen de 768x768 tarda del orden de un segundo.

Sé lo suficiente sobre SVMs como para entender que para cada píxel el algoritmo tiene que aplicar la función kernel, en mi caso rbf, y luego calcular un producto punto (o algo así). Mi mejor suposición es que el kernel rbf es el cuello de botella, pero todavía no estoy seguro de por qué se debe tomar tanto tiempo.

¿Alguna idea al respecto? ¿Y alguna idea de cómo puedo acelerar las cosas?

Answer 1

Está realizando la clasificación por píxeles, por lo que un 768x768 es en realidad 589824 muestras.

El número de vectores de apoyo también podría ser un cuello de botella, si tiene muchos de ellos, porque debe construir un $n_\text{sv}\times n$ matriz del núcleo, que es enorme.

Answer 2

Es muy probable que el problema sea el número de vectores de soporte: si la fracción de puntos mal clasificados es sólo del 5%, en su caso tendrá al menos 29K vectores de soporte.

Hay varias técnicas diferentes que se pueden utilizar para lograr una solución más escasa; véase, por ejemplo aquí o aquí (entre otros muchos).

Una sencilla técnica alternativa que puede utilizar (que se inspira en este documento que utiliza límites de compresión en los que se observa el número de bits que se necesitan para codificar una solución que clasifique correctamente todos los puntos de entrenamiento), consiste en crear una nueva solución dispersa a partir de los vectores de soporte. La idea se basa en el hecho de que:

1. Un plano de decisión que clasifique todos los puntos de los márgenes como +1/-1 será muy escaso y clasificará correctamente la gran mayoría de los puntos (en particular los que están más allá del margen).
2. Los puntos mal clasificados pueden ser una gran fracción, pero -al ser erróneos- no hacen un buen trabajo de apoyo a la separación entre las clases, en particular si tienen grandes pérdidas. Además, cualquier modificación de la solución no puede hacerla funcionar peor desde la perspectiva de la pérdida 0-1 para estos puntos.
3. Los puntos que están cerca del límite de decisión, pero que siguen siendo clasificados correctamente, son más sensibles a ser clasificados erróneamente que los puntos que están lejos del límite. Estos puntos también son más importantes para definir la forma "local" del límite de decisión.

Basándonos en lo anterior, definimos el siguiente enfoque. Sea $\delta \in [0,1)$ ser un límite para los puntos del tercer grupo, por ejemplo $\delta = 0.1$ significaría que consideraríamos todos los puntos con pérdida en el rango $[1-\delta, 1)$ para estar en ese grupo. Que el primer grupo sea $M$ (en el caso de los SV en el margen, se trata de SV no vinculados que tienen $0 \leq \alpha_i < C$ y el tercer grupo sea $P_\delta$ . Entonces resolvemos el siguiente programa lineal para crear una nueva solución definida como $w = \sum_i \beta_i y_i x_i$ resolviendo:

$$ \min_{i \in M \bigcup P_\delta} \sum |\beta_i| \\ \textrm{s.t.}\\ \forall j \in M: \sum \beta_i y_i y_j k(x_i,x_j) = 1 \\ \forall j \in P_\delta: \sum \beta_i y_i y_j k(x_i,x_j) > 0 $$ El número de puntos adicionales mal clasificados según este enfoque será bastante pequeño (y de hecho puede ser negativo, ya que algunos puntos previamente mal clasificados pueden ser ahora clasificados correctamente), mientras que la solución será significativamente más escasa.

Answer 3

Para añadir una dimensión distinta a mi respuesta anterior, hay dos aspectos que pueden afectar a la velocidad de evaluación para la predicción.

1. El número de vectores de soporte - esto da el número de evaluaciones del kernel que necesita hacer.
2. El coste de la evaluación de la función del núcleo, que en este caso está directamente ligado a la dimensionalidad del problema y al rendimiento de las operaciones.

Mi respuesta anterior se centraba en cómo reducir el número de evaluaciones del núcleo. La otra parte que se puede intentar mejorar es reducir el coste. Existen numerosos enfoques para acelerar la evaluación del RBF. Este documento evalúa los métodos de aproximación de Taylor y Random Fourier - este último también se utilizó en un enfoque escalable en términos de número de muestras. También se puede intentar aprovechar la reducción de la dimensionalidad: hay resultados bien conocidos en este espacio para, por ejemplo, utilizar Proyección aleatoria que podría ser relevante - en particular si las distancias euclidianas están bien aproximadas después de la proyección, entonces la RBF también estaría bien aproximada. Hay que tener en cuenta que, por lo general, este sería un paso de preprocesamiento, antes del entrenamiento.