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

41

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?

Bar
fuente
La búsqueda aleatoria es mejor y siempre debe preferirse. Sin embargo, sería aún mejor usar bibliotecas dedicadas para la optimización de hiperparámetros, como Optunity , hyperopt o bayesopt.
Marc Claesen
Bengio y col. escriba sobre esto aquí: papers.nips.cc/paper/… Entonces, GP funciona mejor, pero RS también funciona muy bien.
Guy L
10
@Marc Cuando proporciona un enlace a algo con lo que está involucrado, debe dejar en claro su asociación con él (una o dos palabras pueden ser suficientes, incluso algo tan breve como referirse a él como our Optunitydebería hacerlo); como la ayuda en el comportamiento dice: "... si algunas resultan ser acerca de su producto o sitio web, que está bien Sin embargo, debe revelar su afiliación."
Glen_b -Reinstate Mónica

Respuestas:

39

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 (10.05)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(10.05)n>0.95

Obtenemos . Ta-da!n60

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.

Firebug
fuente
3
El enlace a la publicación del blog está inactivo :( ¿Podría ser este el mismo artículo? Oreilly.com/ideas/evaluating-machine-learning-models/page/5/…
n1k31t4
@DexterMorgan Hola, gracias por el aviso. Sí, el blog aparentemente no funciona, y no estoy seguro de que deba vincular a otras fuentes que podrían no ser "oficiales" , así que lo dejaré como está por ahora, creo.
Firebug
El blog aún no funciona ... gracias por citarlo y @ n1k31t4 gracias por proporcionar un enlace para leer más.
llrs
8

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

Rejilla vs búsqueda aleatoria

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.

Tim
fuente
6

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

Sycorax dice reinstalar a Mónica
fuente
2

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.

IndieSolver
fuente
puedes proponer algo mejor? ¿Cómo podemos saber qué es lo mejor si no lo intentamos? Me parece que la búsqueda aleatoria en muchos modelos es la mejor solución de compromiso.
JPErwin
0

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.

ran8
fuente
El recocido simulado es una forma de búsqueda aleatoria que ha existido durante varios años.
Michael R. Chernick
-1

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.

ingrese la descripción de la imagen aquí

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

JPro
fuente