Optimización práctica de hiperparámetros: búsqueda aleatoria versus cuadrícula

Actualmente estoy revisando la búsqueda aleatoria de Bengio y Bergsta para la optimización de hiperparámetros [1], donde los autores afirman que la búsqueda aleatoria es más eficiente que la búsqueda de cuadrícula para lograr un rendimiento aproximadamente igual.

Mi pregunta es: ¿la gente aquí está de acuerdo con esa afirmación? En mi trabajo, he estado usando la búsqueda de cuadrícula principalmente debido a la falta de herramientas disponibles para realizar búsquedas aleatorias fácilmente.

¿Cuál es la experiencia de las personas que usan la cuadrícula versus la búsqueda aleatoria?

La búsqueda aleatoria tiene una probabilidad del 95% de encontrar una combinación de parámetros dentro del 5% óptimo con solo 60 iteraciones. También en comparación con otros métodos, no se atasca en óptimos locales.

Consulte esta gran publicación de blog en Dato de Alice Zheng, específicamente la sección Algoritmos de ajuste de hiperparámetros .

Me encantan las películas donde gana el desvalido, y me encantan los documentos de aprendizaje automático en los que se demuestra que las soluciones simples son sorprendentemente efectivas. Este es el argumento de "Búsqueda aleatoria para la optimización de hiperparámetros" de Bergstra y Bengio. [...] La búsqueda aleatoria no se tomaba muy en serio antes. Esto se debe a que no busca en todos los puntos de la cuadrícula, por lo que no puede superar el óptimo encontrado por la búsqueda de cuadrícula. Pero luego llegaron Bergstra y Bengio. Mostraron que, en sorprendentemente muchos casos, la búsqueda aleatoria se realiza tan bien como la búsqueda de cuadrícula. En general, probar 60 puntos aleatorios muestreados de la cuadrícula parece ser lo suficientemente bueno.

En retrospectiva, hay una explicación probabilística simple para el resultado: para cualquier distribución en un espacio muestral con un máximo finito, el máximo de 60 observaciones aleatorias se encuentra dentro del 5% superior del máximo verdadero, con un 95% de probabilidad. Eso puede sonar complicado, pero no lo es. Imagine el intervalo del 5% alrededor del máximo verdadero. Ahora imagine que tomamos muestras de puntos de su espacio y vemos si alguno de ellos cae dentro de ese máximo. Cada sorteo aleatorio tiene un 5% de posibilidades de aterrizar en ese intervalo, si sacamos n puntos independientemente, entonces la probabilidad de que todos pierdan el intervalo deseado es $\left(1−0.05\right)^{n}$. Entonces, la probabilidad de que al menos uno de ellos logre alcanzar el intervalo es 1 menos esa cantidad. Queremos al menos una probabilidad de éxito de .95. Para calcular la cantidad de sorteos que necesitamos, solo resuelve n en la ecuación:

$$1−\left(1−0.05\right)^{n}>0.95$$

Obtenemos . Ta-da!$n\geqslant60$

La moraleja de la historia es: si la región cercana a la óptima de hiperparámetros ocupa al menos el 5% de la superficie de la cuadrícula, entonces la búsqueda aleatoria con 60 ensayos encontrará esa región con alta probabilidad.

Puede mejorar esa posibilidad con un mayor número de ensayos.

Con todo, si tiene demasiados parámetros para ajustar, la búsqueda de cuadrícula puede volverse inviable. Ahí es cuando intento una búsqueda aleatoria.

Mire nuevamente el gráfico del papel (Figura 1). Supongamos que tiene dos parámetros, con la búsqueda de cuadrícula 3x3 solo verifica tres valores de parámetros diferentes de cada uno de los parámetros (tres filas y tres columnas en el gráfico de la izquierda), mientras que con la búsqueda aleatoria verifica nueve (!) Valores de parámetros diferentes de cada uno de los parámetros (nueve filas distintas y nueve columnas distintas).

Obviamente, la búsqueda aleatoria, por casualidad, puede no ser representativa de todo el rango de los parámetros, pero a medida que crece el tamaño de la muestra, las posibilidades de que esto se reduzca cada vez más.

Si puede escribir una función en la búsqueda de cuadrícula, probablemente sea aún más fácil escribir una función para realizar una búsqueda aleatoria porque no tiene que especificar previamente y almacenar la cuadrícula por adelantado.

Dejando eso de lado, los métodos como LIPO, optimización de enjambre de partículas y optimización bayesiana toman decisiones inteligentes sobre qué hiperparámetros probablemente sean mejores, por lo que si necesita mantener el número de modelos en un mínimo absoluto (por ejemplo, porque es costoso ajustar un modelo), estas herramientas son opciones prometedoras. También son optimizadores globales, por lo que tienen una alta probabilidad de localizar el máximo global. Algunas de las funciones de adquisición de los métodos BO tienen límites de arrepentimiento demostrables, que los hacen aún más atractivos.

Se puede encontrar más información en estas preguntas:

¿Cuáles son algunas de las desventajas de la optimización de hiperparámetros bayesianos?

Optimización cuando la función de costo es lenta para evaluar

Por defecto, la búsqueda aleatoria y la cuadrícula son algoritmos terribles a menos que se cumpla una de las siguientes condiciones.

• Su problema no tiene una estructura global, por ejemplo, si el problema es multimodal y el número de óptimos locales es enorme.
• Su problema es ruidoso, es decir, evaluar la misma solución dos veces conduce a valores de función objetivo diferentes
• El presupuesto de las llamadas a funciones objetivas es muy pequeño en comparación con el número de variables, por ejemplo, más pequeño que 1x o 10x.
• El número de variables es muy pequeño, por ejemplo, menor que 5 (en la práctica).
• Algunas otras condiciones.

La mayoría de las personas afirman que la búsqueda aleatoria es mejor que la búsqueda de cuadrícula. Sin embargo, tenga en cuenta que cuando el número total de evaluaciones de funciones está predefinido, la búsqueda en la cuadrícula conducirá a una buena cobertura del espacio de búsqueda, que no es peor que la búsqueda aleatoria con el mismo presupuesto y la diferencia entre los dos es insignificante, si la hay. Si comienza a agregar algunas suposiciones, por ejemplo, que su problema es separable o casi separable, encontrará argumentos para apoyar la búsqueda en la cuadrícula. En general, ambos son comparativamente terribles a menos que en muy pocos casos. Por lo tanto, no hay necesidad de distinguirlos a menos que se consideren algunos supuestos adicionales sobre el problema.

Encontrar un punto dentro del 95% de los máximos en una topografía 2D con solo un máximo requiere 100% / 25 = 25%, 6.25%, 1.5625%, o 16 observaciones. Mientras las primeras cuatro observaciones determinen correctamente en qué cuadrante están los máximos (extremos). La topografía 1D toma 100/2 = 50, 25, 12.5, 6.25, 3.125 o 5 * 2. Supongo que las personas que buscan múltiples máximos locales lejanos usan una gran búsqueda de cuadrícula inicial y luego regresión o algún otro método de predicción. Una cuadrícula de 60 observaciones debe tener una observación dentro de 100/60 = 1.66% de los extremos. Wikipedia sobre optimización global Sigo pensando que siempre hay un método mejor que la aleatoriedad.

Como lo mostró Tim, puede probar más valores de parámetros con búsqueda aleatoria que con la búsqueda de cuadrícula. Esto es especialmente eficiente si algunos de los parámetros que prueba no resultan impactantes para su problema, como el 'parámetro sin importancia' en la figura 1 del artículo.

Hice una publicación sobre el ajuste de hiperparámetros donde explico las diferencias entre la búsqueda de cuadrícula, la búsqueda aleatoria y la optimización bayesiana. Puede verificarlo (y avíseme si fue útil, ¡le agradecemos sus comentarios!)