Complejidad computacional de la predicción mediante SVM y NN?

Question

He visto respuestas en las que se habla de la complejidad de entrenar SVMs y redes neuronales, pero ¿qué tal para predecir nuevas respuestas una vez que se ha entrenado un modelo?

Para contextualizar, estoy trabajando en una aplicación que debe producir predicciones en tiempo casi real dados los datos de píxeles entrantes y estoy buscando un algoritmo de aprendizaje automático que pueda manejar planos de separación complejos y predecir lo más rápido posible.

Answer 1

Por orden de complejidad creciente en línea:

1. La SVM lineal tiene una complejidad de predicción $O(d)$ con $d$ el número de dimensiones de entrada, ya que se trata de un único producto interior.
2. La complejidad de la NN está relacionada con la arquitectura, pero seguramente estará por encima de la de la SVM lineal.
3. La complejidad de la predicción de la SVM de núcleo depende de la elección del núcleo y suele ser proporcional al número de vectores de soporte. Para la mayoría de los núcleos, incluidos los polinómicos y los RBF, es $O(n_{SV} d)$ donde $n_{SV}$ es el número de vectores de apoyo. Existe una aproximación para las SVM con un núcleo RBF que reduce la complejidad a $O(d^2)$ . Para aplicaciones de visión por ordenador, granos aditivos se utilizan a menudo porque proporcionan una velocidad de predicción muy rápida (independiente del número de SV).

Dado que estás haciendo una aplicación de visión por ordenador, te recomiendo que utilices la aproximación RBF o los kernels aditivos, ya que son muy rápidos en la evaluación y están entre los más avanzados en términos de precisión. Las redes neuronales que pueden rivalizar con el rendimiento de las SVM utilizando estos kernels en aplicaciones de CV suelen ser bastante grandes y, por tanto, más lentas.

Answer 2

Para cualquier tarea de visión por ordenador, una red neuronal convolucional (incluso una simple) superará a cualquier tipo de SVM. Esto ya ocurrió en 2012, cuando una ConvNet redujo a la mitad la tasa de error del estado del arte anterior (véase papers.nips.cc/paper/4824-imagenet-classification-w ).

Además, hay muchas implementaciones eficientes de ConvNets. Quizás github.com/soumith/convnet-benchmarks puede servir de resumen. También hay muchas implementaciones centradas en el uso eficiente en los teléfonos móviles.