Búsqueda cuasialeatoria

Esta unidad se centra en la búsqueda cuasialeatoria.

¿Por qué usar la búsqueda cuasialeatoria?

La búsqueda cuasialeatoria (basada en secuencias de baja discrepancia) es nuestra preferencia por sobre las herramientas de optimización de caja negra más sofisticadas cuando se usa como parte de un proceso de ajuste iterativo destinado a maximizar las estadísticas del problema de ajuste (lo que llamamos “fase de exploración”). La optimización bayesiana y otras herramientas similares son más apropiadas para la fase de explotación. La búsqueda cuasialeatoria basada en secuencias de baja discrepancia desplazadas al azar puede considerarse una "búsqueda de cuadrícula con Jitter y aleatoria", ya que explora un espacio de búsqueda determinado de manera uniforme y aleatoria y distribuye los puntos de búsqueda más que una búsqueda aleatoria.

Entre las ventajas de la búsqueda cuasialeatoria sobre las herramientas de optimización de caja negra más sofisticadas (p.ej., optimización bayesiana y algoritmos evolutivos), se incluyen las siguientes:

  • El muestreo del espacio de búsqueda de forma no adaptable permite cambiar el objetivo de ajuste en el análisis post hoc sin volver a ejecutar los experimentos. Por ejemplo, por lo general, queremos encontrar la mejor prueba en términos de error de validación que se haya logrado en cualquier punto del entrenamiento. Sin embargo, la naturaleza no adaptable de la búsqueda cuasialeatoria permite encontrar la mejor prueba según el error de validación final, el error de entrenamiento o alguna métrica de evaluación alternativa sin volver a ejecutar ningún experimento.
  • La búsqueda cuasialeatoria se comporta de manera coherente y se puede reproducir estadísticamente. Debería ser posible reproducir un estudio de hace seis meses, incluso si cambia la implementación del algoritmo de búsqueda, siempre que mantenga las mismas propiedades de uniformidad. Si usas un software de optimización bayesiano sofisticado, la implementación puede cambiar de una manera importante entre versiones, lo que dificultaría mucho reproducir una búsqueda anterior. No siempre es posible revertir a una implementación anterior (p.ej., si la herramienta de optimización se ejecuta como un servicio).
  • Su exploración uniforme del espacio de búsqueda facilita la razonamiento sobre los resultados y lo que estos podrían sugerir sobre este. Por ejemplo, si el mejor punto del recorrido de la búsqueda cuasialeatoria está en el límite del espacio de búsqueda, esta es una buena señal (pero no infalible) de que se deben cambiar los límites del espacio de búsqueda. Sin embargo, un algoritmo de optimización de caja negra adaptable podría haber desestimado el medio del espacio de búsqueda debido a algunas pruebas iniciales desafortunadas, incluso si contiene puntos igualmente correctos, ya que un buen algoritmo de optimización debe emplear este tipo exacto de falta de uniformidad para acelerar la búsqueda.
  • Ejecutar un número diferente de pruebas en paralelo en comparación con de manera secuencial no produce resultados estadísticamente diferentes cuando se usa la búsqueda cuasialeatoria (o algún otro algoritmo de búsqueda no adaptable), a diferencia de los algoritmos adaptables.
  • Es posible que los algoritmos de búsqueda más sofisticados no siempre manejen los puntos inviables de forma correcta, en especial si no están diseñados para el ajuste de hiperparámetros de redes neuronales.
  • La búsqueda cuasialeatoria es simple y funciona muy bien cuando muchas pruebas de ajuste se ejecutan en paralelo. Anecdóticamente1, es muy difícil que un algoritmo adaptable supere una búsqueda cuasaleatoria que tiene el doble de su presupuesto, en especial cuando muchas pruebas deben ejecutarse en paralelo (y, por lo tanto, hay muy pocas probabilidades de usar los resultados de pruebas anteriores cuando se inician pruebas nuevas). Sin experiencia en la optimización bayesiana y otros métodos avanzados de optimización de caja negra, es posible que no obtengas los beneficios que, en principio, son capaces de proporcionar. Es difícil comparar algoritmos avanzados de optimización de caja negra en condiciones realistas de ajuste de aprendizaje profundo. Son un área de investigación actual muy activa, y los algoritmos más sofisticados tienen sus propias dificultades para los usuarios sin experiencia. Los expertos en estos métodos pueden obtener buenos resultados, pero en condiciones de alto paralelismo, el espacio de búsqueda y el presupuesto tienden a importar mucho más.

Dicho esto, si tus recursos de procesamiento solo permiten que se ejecute una pequeña cantidad de pruebas en paralelo y puedes permitirte ejecutar muchas pruebas en secuencia, la optimización bayesiana se vuelve mucho más atractiva a pesar de que los resultados de ajuste sean más difíciles de interpretar.

Vizier de código abierto tiene una implementación de búsqueda cuasialeatoria. Establece algorithm="QUASI_RANDOM_SEARCH" en este ejemplo de uso de Vizier. Existe una implementación alternativa en este ejemplo de barrido de hiperparámetros. Ambas implementaciones generan una secuencia de Halton para un espacio de búsqueda determinado (destinada a implementar una secuencia de Halton desordenada y desplazada, como se recomienda en Hiperparámetros críticos: No aleatorio, sin llanto).

Si no está disponible un algoritmo de búsqueda cuasialeatorio basado en una secuencia de baja discrepancia, es posible sustituir la búsqueda uniforme pseudoaleatoria, aunque es probable que sea un poco menos eficiente. En 1 o 2 dimensiones, también es aceptable la búsqueda en cuadrícula, aunque no en mayores dimensiones. (Consulta Bergstra y Bengio, 2012).

¿Cuántas pruebas se necesitan para obtener buenos resultados con la búsqueda cuasialeatoria?

No hay forma de determinar cuántas pruebas se necesitan para obtener resultados con la búsqueda cuasialeatoria en general, pero puedes consultar ejemplos específicos. Como se muestra en la Figura 3, la cantidad de pruebas de un estudio puede tener un impacto significativo en los resultados:

Diagrama de caja de la tasa de errores de validación (eje y) frente al presupuesto de ajuste (eje x),
          en el que el presupuesto de ajuste es la cantidad de pruebas. Por lo general, la tasa de errores de validación promedio disminuye a medida que aumenta el presupuesto de ajuste.

Figura 3: ResNet-50 se ajustó en ImageNet con 100 pruebas. Con la inicialización, se simularon diferentes cantidades de presupuesto de ajuste. Se trazan los diagramas de caja de los mejores rendimientos para cada presupuesto de prueba.

 

Ten en cuenta lo siguiente sobre la Figura 3:

  • Los rangos intercuartiles en los que se muestrearon 6 pruebas son mucho más grandes que cuando se muestrearon 20 pruebas.
  • Incluso con 20 pruebas, la diferencia entre los estudios con suerte y los con mala suerte probablemente sea mayor que la variación típica entre los reentrenamientos de este modelo en diferentes orígenes aleatorios, con hiperparámetros fijos, que para esta carga de trabajo pueden ser de alrededor del 0.1% con una tasa de error de validación de ~23%.

  1. Ben Recht y Kevin Jamieson destacaron lo sólida que es la búsqueda aleatoria con un presupuesto doble como modelo de referencia (el artículo sobre hiperbanda hace argumentos similares), pero sin duda es posible encontrar espacios de búsqueda y problemas en los que las técnicas de optimización bayesiana de vanguardia superan las búsquedas aleatorias que tienen el doble del presupuesto. Sin embargo, según nuestra experiencia, superar la búsqueda aleatoria del doble del presupuesto es mucho más difícil en el régimen de paralelismo alto, ya que la optimización bayesiana no tiene la oportunidad de observar los resultados de pruebas anteriores.