Método rápido para encontrar los mejores metaparámetros de SVM (que es más rápido que la búsqueda de cuadrícula)

Estoy usando modelos SVM para hacer pronósticos a corto plazo de contaminantes del aire. Para entrenar un nuevo modelo, necesito encontrar metaparámetros apropiados para un modelo SVM (me refiero a C, gamma, etc.).

La documentación de Libsvm (y muchos otros libros que he leído) sugiere usar la búsqueda de cuadrícula para encontrar estos parámetros, por lo que básicamente entreno el modelo para cada combinación de estos parámetros de un conjunto determinado y elijo el mejor modelo.

¿Hay alguna forma mejor de encontrar metaparámetros óptimos (o casi óptimos)? Para mí es principalmente una cuestión de tiempo de cálculo: una búsqueda en cuadrícula de este problema lleva aproximadamente dos horas (después de hacer algunas optimizaciones).

Ventajas de la búsqueda en la cuadrícula:

• Se puede paralelizar fácilmente: si tiene 20 CPU, se ejecutará 20 veces más rápido, paralelizar otros métodos es más difícil
• Verifica grandes partes del espacio de metaparámetros, por lo que si hay una buena solución, la encontrará.

La desventaja de la búsqueda de cuadrícula es que el tiempo de ejecución crece tan rápido como el producto de la cantidad de opciones para cada parámetro.

Aquí hay una entrada en el blog de Alex Smola relacionada con su pregunta

Aquí hay una cita:

[...] elija, digamos 1000 pares (x, x ') al azar de su conjunto de datos, calcule la distancia de todos esos pares y tome la mediana, el cuantil 0.1 y el 0.9. Ahora elija λ para ser el inverso de cualquiera de estos tres números. Con un poco de validación cruzada, descubrirá cuál de los tres es el mejor. En la mayoría de los casos, no necesitará buscar más.

No lo he intentado yo mismo, pero parece un poco prometedor.

Si supone que hay una función relativamente suave subyacente en la cuadrícula de parámetros, entonces hay ciertas cosas que puede hacer. Por ejemplo, una heurística simple es comenzar con una grilla de parámetros muy gruesa y luego usar una grilla más fina alrededor de la mejor configuración de parámetros de la grilla gruesa.

Esto tiende a funcionar bastante bien en la práctica, con advertencias, por supuesto. Primero es que el espacio no es necesariamente liso, y podría haber óptimos locales . La grilla gruesa puede pasar por alto estos y podría terminar con una solución subóptima. También tenga en cuenta que si tiene relativamente pocas muestras en su conjunto de espera, entonces puede tener una gran cantidad de configuraciones de parámetros que dan la misma puntuación (error o cualquier métrica que esté usando). Esto puede ser particularmente problemático si está aprendiendo en varias clases (por ejemplo, utilizando el método de uno contra todos ), y solo tiene unos pocos ejemplos de cada clase en su conjunto de espera. Sin embargo, sin recurrir a técnicas desagradables de optimización no lineal, esto probablemente sirva como un buen punto de partida.

Hay un buen conjunto de referencias aquí . En el pasado, he adoptado el enfoque de que puede estimar razonablemente un buen rango de hiperparámetros del núcleo mediante la inspección del núcleo (por ejemplo, en el caso del núcleo RBF, asegurando que el histograma de los valores del núcleo proporcione una buena distribución de valores, en lugar de estar sesgado hacia 0 o 1, y también puede hacerlo automáticamente sin demasiado trabajo), lo que significa que puede reducir el rango antes de comenzar. Luego puede enfocar su búsqueda en cualquier otro parámetro, como el parámetro de regularización / capacidad. Sin embargo, por supuesto, esto solo funciona con núcleos precalculados, aunque puede estimar esto en un subconjunto aleatorio de puntos si no desea utilizar núcleos precalculados, y creo que ese enfoque también estaría bien.

Utilizo recocido simulado para buscar parámetros.

El comportamiento se rige por algunos parámetros:

• k es la constante de Boltzmann.
• T_max es tu temperatura inicial
• T_min es tu umbral final.
• mu_T( μ) es cuánto baja la temperatura ( T->T/μ)
• i es el número de iteraciones a cada temperatura
• zes un tamaño de paso: usted determina qué significa exactamente eso. Me muevo al azar dentro old*(1±z).

1. Tome un punto de partida (conjunto de valores de parámetros).
2. Obtenga una energía para ello (qué tan bien se ajusta a sus datos; uso valores de chi-cuadrado).
3. Mire en una dirección aleatoria ("dé un paso").
   • Si la energía es inferior a su punto actual, muévase allí.
   • Si es más alto, muévase allí con una probabilidad p = e^{-(E_{i+1} - E_i)/(kT)}.
4. Repita, ocasionalmente bajando T->T/μcada iiteración hasta que golpee T_min.

Juega un poco con los parámetros y deberías poder encontrar un conjunto que funcione bien y rápido.

Y el Biblioteca Científica GNU incluye recocido simulado.

Si alguien está interesado aquí están algunos de mis pensamientos sobre el tema:

• Como @tdc sugirió, estoy haciendo una búsqueda de grilla gruesa / fina. Esto presenta dos problemas:
  • En la mayoría de los casos, obtendré un conjunto de buenos conjuntos de metaparámetros que tienen parámetros muy diferentes --- Estoy interpretando de esta manera que estos parámetros son soluciones óptimas, pero para asegurarme de que debería verificar todas las cuadrículas finas cerca de todos estos parámetros buenos ( eso tomaría mucho tiempo), así que por ahora solo verifico el conjunto de metaparámetros de vecindad de apuestas.
  • En la mayoría de los casos, la búsqueda fina no aumenta el rendimiento de SVM (eso puede deberse al hecho de que solo estoy comprobando el vecindario del mejor punto de la grilla gruesa).
• Observé el comportamiento de que la mayor parte del tiempo de computación se gasta en conjuntos de metaparemetros que no arrojarán buenos resultados, por ejemplo: la mayoría de los conjuntos de metaparámetros se calcularán en menos de 15 segundos (y la mayoría de ellos tienen una tasa de error del 15%), y algunos tardan 15 minutos ( y la mayoría de estos tienen tasas de error superiores al 100%). Entonces, cuando hago una búsqueda en la cuadrícula, elimino puntos que tardan más de 30 segundos en computarse y supongo que tuvieron un error infinito.
• Yo uso multiprocesamiento (que es lo suficientemente simple)

Si el núcleo es radial, puede usar esta heurística para obtener un$\sigma$ - La optimización de C es mucho más fácil entonces.