¿El "asombroso poder oculto" de la búsqueda aleatoria?

Question

Tengo la siguiente pregunta que compara la optimización por búsqueda aleatoria con la optimización por descenso de gradiente:

Basado en la (sorprendente) respuesta proporcionada aquí Optimización cuando la función de costes es lenta de evaluar Me di cuenta de algo muy interesante sobre la búsqueda aleatoria:

Búsqueda aleatoria

Incluso cuando la función de costes es costosa de evaluar, la búsqueda aleatoria puede ser útil. La búsqueda aleatoria es muy sencilla de implementar. La La única elección que tiene que hacer el investigador es establecer el probabilidad $p$ que quiere que sus resultados estén en algún cuantificar $q$ el resto procede automáticamente utilizando los resultados de la probabilidad básica.

Supongamos que su cuantil es $q = 0.95$ y quieres un $p=0.95$ probabilidad de que los resultados del modelo estén en lo más alto $100\times (1-q)=5$ por ciento de todas las tuplas de hiperparámetros. La probabilidad de que todas las $n$ las tuplas intentadas son no en esa ventana es $q^n = 0.95^n$ (porque se eligen independientemente al azar de la misma distribución), por lo que la probabilidad de que al menos uno la tupla está en esa región es $1 - 0.95^n$ . Si lo juntamos todo, tenemos

$$ 1 - q^n \ge p \implies n \ge \frac{\log(1 - p)}{\log(q)} $$

que en nuestro caso concreto da como resultado $n \ge 59$ .

Este resultado es la razón por la que la mayoría de la gente recomienda $n=60$ intentos de tuplas para búsqueda aleatoria. Cabe destacar que $n=60$ es comparable a la número de experimentos necesarios para obtener buenos resultados con los métodos basados en procesos gaussianos cuando hay un número moderado de parámetros. A diferencia de los procesos gaussianos, el número de tuplas de consulta no no cambia con el número de hiperparámetros a buscar; de hecho, para un gran número de hiperparámetros, un método basado en procesos gaussianos puede puede necesitar muchas iteraciones para avanzar.

Dado que se tiene una caracterización probabilística de lo bueno que es el resultados, este resultado puede ser una herramienta persuasiva para convencer a su de que la realización de más experimentos dará lugar a rendimientos marginales decrecientes. rendimientos marginales.

Utilizando la búsqueda aleatoria, se puede demostrar matemáticamente que: independientemente del número de dimensiones que tenga su función, ¡hay un 95% de probabilidades de que sólo se necesiten 60 iteraciones para obtener una respuesta en el 5% superior de todas las soluciones posibles!

• Suponga que hay 100 soluciones posibles para su función de optimización (esto no depende del número de dimensiones). Un ejemplo de solución es $(X_1 = x_1, X_2 = x_2.... X_n = x_n)$ .

• El 5% de las soluciones más altas incluirá las 5 soluciones más altas (es decir, las 5 soluciones que proporcionan los 5 valores más bajos de la función que se quiere optimizar)

• La probabilidad de encontrar al menos una de las 5 primeras soluciones en " $n$ iteraciones" : $\boldsymbol{1 - [(1 - 5/100)^n]}$

• Si quieres esta probabilidad $= 0.95$ se puede resolver para $n$ : $ \boldsymbol {1 - [(1 - 5/100)^n] = 0.95}

• Así, $\boldsymbol{n = 60}$ ¡iteraciones!

Pero lo fascinante es que, $\boldsymbol{n = 60}$ iteraciones sigue siendo válida independientemente del número de soluciones que existan. Por ejemplo, aunque existan 1.000.000.000 de soluciones, sólo se necesitan 60 iteraciones para garantizar una probabilidad del 0,95 de encontrar una solución en el 5% superior de todas las soluciones.

• $\boldsymbol{1 - [(1 - ( (0.05 \times 1000000000) /1000000000 )^{n} )] = 0.95}$

• " $\boldsymbol{n}$ " ¡seguirán siendo 60 iteraciones!

Mi pregunta: Basándonos en este sorprendente "poder oculto" de la búsqueda aleatoria, y teniendo en cuenta además que la búsqueda aleatoria es mucho más rápida que el descenso de gradiente, ya que la búsqueda aleatoria no requiere calcular las derivadas de funciones de pérdida complejas multidimensionales (por ejemplo, las redes neuronales) : ¿Por qué utilizamos el descenso de gradiente en lugar de la búsqueda aleatoria para optimizar las funciones de pérdida en las redes neuronales?

La única razón que se me ocurre es que si la distribución de los valores de optimización está "muy sesgada negativamente", entonces el 1% superior podría ser significativamente mejor que el 2%-5% superior, y la cantidad de iteraciones necesarias para encontrar una solución en el 1% superior también será significativamente mayor:

Pero incluso con esa distribución de las puntuaciones de optimización, ¿el descenso por gradiente seguiría teniendo sus ventajas? ¿El descenso de gradiente (o el descenso de gradiente estocástico) tiene realmente la capacidad de competir con este "poder oculto" de la búsqueda aleatoria? Si se cumplen ciertas condiciones, debido a sus atractivas propiedades teóricas (por ejemplo, la convergencia), ¿tiene el descenso de gradiente la capacidad de alcanzar la mejor solución (no el mejor 5%, sino la mejor solución) mucho más rápido que la búsqueda aleatoria? O en aplicaciones de la vida real con funciones objetivo no convexas y ruidosas, ¿estas "propiedades teóricas atractivas" del descenso de gradiente generalmente no se aplican, y una vez más - el "increíble poder oculto" de la búsqueda aleatoria gana de nuevo?

En resumen: basándonos en este increíble "poder oculto" (y velocidad) de la búsqueda aleatoria, ¿por qué utilizamos el descenso de gradiente en lugar de la búsqueda aleatoria para optimizar las funciones de pérdida en las redes neuronales?

¿Puede alguien comentar esto?

Nota: Basándome en el gran volumen de literatura que insiste y alaba la capacidad del descenso de gradiente estocástico, estoy asumiendo que el descenso de gradiente estocástico tiene muchas ventajas en comparación con la búsqueda aleatoria.

Nota: Pregunta relacionada que ha resultado de una respuesta dada a esta pregunta: El teorema del almuerzo gratis y la búsqueda aleatoria

Answer 1

1. Una de las limitaciones de la búsqueda aleatoria es que buscar en un gran espacio es un gran reto; incluso una pequeña diferencia puede estropear el resultado.

   El artículo de Émile Borel de 1913 "Mécanique Statistique et Irréversibilité" afirmaba que si un millón de monos pasara diez horas al día frente a una máquina de escribir, es muy poco probable que la calidad de su escritura fuera igual al contenido de una biblioteca. Y, por supuesto, entendemos la intuición: el lenguaje está muy estructurado (no es aleatorio), por lo que pulsar teclas al azar no va a producir un texto coherente. Incluso un texto que sea extremadamente similar al lenguaje puede volverse incoherente por un pequeño error.

   

   En cuanto a la estimación de un modelo, hay que estimar todo correctamente simultáneamente . Obtención de la pendiente correcta $\hat{\beta}_1$ en el modelo $y = \beta_0 + \beta_1 x +\epsilon$ no tiene mucho sentido si $\hat{\beta}_0$ está muy muy lejos de la verdad. En un número mayor de dimensiones, como en una red neuronal, habrá que encontrar una buena solución en miles o millones de parámetros simultáneamente. Es poco probable que esto ocurra al azar.

   Esto está directamente relacionado con la maldición de la dimensionalidad . Supongamos que su objetivo es encontrar una solución con una distancia inferior a 0,05 de la solución verdadera, que está en el centro del intervalo unitario. Utilizando un muestreo aleatorio, la probabilidad de que esto ocurra es de 0,1. Pero a medida que aumentamos la dimensión del espacio de búsqueda a un cuadrado unitario, a un cubo unitario y a dimensiones superiores, el volumen ocupado por nuestra "buena solución" (una solución con una distancia a la solución óptima inferior a 0,05) se reduce, y la probabilidad de encontrar esa solución mediante un muestreo aleatorio también se reduce. (Y, naturalmente, el aumento de la tamaño del espacio de búsqueda, pero mantener la dimensionalidad constante también disminuye rápidamente la probabilidad).

   El "truco" de la búsqueda aleatoria es que pretende vencer este proceso manteniendo la probabilidad constante mientras la dimensión crece; esto debe implicar que el volumen asignado a la "buena solución" aumenta, correspondientemente, para mantener constante la probabilidad asignada al evento. Esto no es perfecto, porque la calidad de las soluciones dentro de nuestro radio es peor (porque estas soluciones tienen una distancia media mayor del valor verdadero).

2. No tienes forma de saber si tu espacio de búsqueda contiene un buen resultado . La hipótesis central de la búsqueda aleatoria es que su espacio de búsqueda contiene una configuración que es "suficientemente buena" para resolver su problema. Si una solución "suficientemente buena" no se encuentra en el espacio de búsqueda (quizás porque se ha elegido una región demasiado pequeña), la probabilidad de encontrar esa buena solución es 0. La búsqueda aleatoria sólo puede encontrar el 5% de las soluciones con una probabilidad positiva de entre las soluciones del espacio de búsqueda .

   Se podría pensar que ampliar el espacio de búsqueda es una buena manera de aumentar las probabilidades. Aunque puede hacer que la región de búsqueda contenga una región de altísima calidad, la probabilidad de seleccionar algo en esa región se reduce rápidamente al aumentar el tamaño del espacio de búsqueda.

   

3. Los parámetros de los modelos de alta calidad suelen residir en valles estrechos. Al considerar los hiperparámetros, a menudo es cierto que la superficie de respuesta de los hiperparámetros cambia sólo gradualmente; hay grandes regiones del espacio donde muchos valores de los hiperparámetros son básicamente iguales en términos de calidad. Además, un pequeño número de hiperparámetros contribuye en gran medida a mejorar el modelo; véase Ejemplos de que el rendimiento de un modelo de aprendizaje automático es más sensible a un pequeño subconjunto de hiperparámetros que a otros?

Pero en términos de estimación del modelo parámetros En la actualidad, vemos el fenómeno contrario. Por ejemplo, los problemas de regresión tienen probabilidades que tienen picos prominentes alrededor de sus valores óptimos (siempre que se tengan más observaciones que características); además, estos picos se vuelven más y más "puntiagudos" a medida que aumenta el número de observaciones. Los picos de los valores óptimos son una mala noticia para la búsqueda aleatoria, porque significa que la "región óptima" es en realidad bastante pequeña, y todos los valores "cercanos" son en realidad mucho más pobres en comparación con el valor óptimo.

Para hacer una comparación justa entre la búsqueda aleatoria y el descenso de gradiente, establezca un presupuesto de iteraciones (por ejemplo, el $n=60$ valor derivado de la búsqueda aleatoria). A continuación, compare la calidad del modelo de una red neuronal ajustada con $n$ iteraciones de descenso de gradiente ordinario y backprop a un modelo que utiliza $n$ iteraciones de búsqueda aleatoria. Mientras el descenso de gradiente no diverja, estoy seguro de que vencerá a la búsqueda aleatoria con alta probabilidad.

4. La obtención de garantías aún más sólidas se vuelve rápidamente costosa. Por supuesto, puede ajustar $p$ o $q$ para aumentar las garantías de que encontrará una solución de muy alta calidad, pero si calcula la aritmética, encontrará que $n$ se vuelve rápidamente muy grande (es decir, la búsqueda aleatoria se vuelve cara rápidamente). Además, en una comparación justa, el descenso por gradiente también tardará $n$ pasos de optimización, y tienden a encontrar soluciones aún mejores que la búsqueda aleatoria.

Un poco más de discusión, con una ilustración intuitiva: ¿Depende la búsqueda aleatoria del número de dimensiones buscadas?

Answer 2

Consideremos un modelo de red neuronal con 100 pesos. Si pensamos sólo en acertar con el signo de los pesos y no nos preocupamos por el momento de su magnitud. Hay 2^100 combinaciones de los signos de estos pesos, lo que supone un muy gran número. Si tomamos una muestra de 60 vectores de pesos al azar, sólo habremos visto una proporción minúscula de ese espacio, ni siquiera lo suficiente como para estar seguros de que tenemos al menos una solución para la que siete pesos dados tienen el signo correcto. Por tanto, incluso para una red neuronal pequeña, el muestreo aleatorio tiene una probabilidad muy pequeña de acertar todos los signos de los pesos.

Ahora bien, la estructura de la red neuronal implica que hay simetrías que significan que hay múltiples soluciones equivalentes (por ejemplo, invertir los signos de todos los pesos de entrada de una neurona y sus pesos de salida), pero esto no reduce mucho el número de combinaciones equivalentes de signos.

Sospecho que parte del problema es que la distribución del rendimiento está muy marcada en torno a las mejores soluciones. Así que, aunque 60 muestras te sitúen en el 5% de las mejores soluciones, si el espacio de búsqueda es muy grande y el óptimo de la función de costes está muy localizado, un 5% de las mejores soluciones al azar puede seguir siendo un sinsentido y necesitarás, quizás, un 0,0005% de las mejores soluciones o más para tener un rendimiento aceptable.

Si la búsqueda aleatoria fuera una forma efectiva de entrenar redes neuronales, entonces esperaría que alguien lo hubiera descubierto, en lugar de ~50 años de descenso de gradiente.

Sin embargo, la búsqueda aleatoria es útil para la búsqueda de hiperparámetros, pero sobre todo porque la dimensión es menor, y los modelos se entrenan con los datos utilizando el descenso de gradiente, por lo que se elige entre un conjunto de soluciones plausiblemente buenas, en lugar de al azar. En ese caso, la mayor parte del espacio de búsqueda tiene soluciones más o menos buenas, y el óptimo de la función de coste no está muy localizado (al menos no para los métodos de aprendizaje del núcleo).

Answer 3

Supongamos que queremos responder a su pregunta con una respuesta de 1000 caracteres. Una forma de hacerlo podría ser muestrear 60 1000-tuplas de caracteres, signos de puntuación y espacios en blanco. Con un 95% de probabilidad, una de ellas estará dentro del 5% más útil de todas las posibles respuestas de Stack Exchange dentro de este límite de caracteres.

Básicamente, el problema que señalas es que estar dentro de algún cuantil clasificado de todas las soluciones posibles no suele ser muy interesante. Generalmente se tiene alguna función de evaluación, y lo que realmente interesa es la diferencia entre el mejor modelo posible o algún modelo actual y el modelo definido por el nuevo conjunto de parámetros. La búsqueda aleatoria es útil cuando se optimizan los hiperparámetros porque (realmente si, no siempre es útil) la optimización no aleatoria de los parámetros que sigue a la selección de los hiperparámetros ya te restringe a una clase de modelos generalmente útiles.

Answer 4

Hay un resultado matemático en la optimización, menos interesante de lo que parece en un principio, llamado "El teorema del almuerzo gratis" . Dice que para un problema discreto (como la respuesta de @JonnyLomond), ningún algoritmo puede superar la búsqueda aleatoria cuando su rendimiento se promedia entre todas las posibles funciones a optimizar. Es decir, se tiene una función $f:\Omega\to L$ donde $\Omega$ es un espacio discreto finito (como el espacio de las cadenas de 1000 caracteres) y $L$ es un espacio discreto de valores numéricos (como 1:10 o 1:1000000000). Sólo hay un número finito de tales $f$ .

Puede definir cualquier algoritmo que evalúe $f(\omega_1)$ , $f(\omega_2)$ y así sucesivamente para $n$ intentos, eligiendo $\omega_{i+1}$ en términos de resultados anteriores, y luego tomar $\max_i f(\omega_i)$ como su mejor resultado. Ningún algoritmo superará a la búsqueda aleatoria en promedio sobre todos los $f$ . Una idea de prueba es considerar $f$ como elegidas al azar entre las posibles funciones con igual probabilidad. Dado que $f$ podría ser cualquier cosa, con igual probabilidad, las evaluaciones en $\omega_1,\ldots,\omega_i$ son independientes de $f(\omega_{i+1})$ no se puede aprender nada.

Este resultado no es tan interesante porque normalmente no nos interesa el rendimiento medio de todas las funciones objetivo posibles. Pero implica que el razón La búsqueda aleatoria no es un buen competidor porque las funciones objetivo que nos interesan tienen estructura. Algunas tienen una estructura suave (o más bien suave): los valores de los parámetros cercanos al óptimo dan mejores resultados que los alejados del mismo. A veces la estructura es más complicada. Pero hay una estructura (típica).

[El teorema del no-free-lunch también es quizás menos interesante de lo que parece porque no parece tener un análogo para espacios de parámetros continuos]

Answer 5

1. En cuanto se pasa de los espacios de búsqueda discretos a los continuos, se hace necesario especificar una distribución en el espacio de parámetros para realizar la búsqueda aleatoria. Entonces es evidente que el rendimiento de la búsqueda aleatoria dependerá en gran medida de las características de esta distribución. De hecho, uno de los desarrollos clave en la historia del entrenamiento de redes neuronales fue el desarrollo de varios procedimientos de inicialización de pesos aleatorios (Glorot, He, etc.). Así que, en cierto sentido, la búsqueda aleatoria ya se utiliza como un primer paso (muy importante) para el entrenamiento de las redes.

2. De hecho, hay trabajos recientes que demuestran que los enfoques de búsqueda aleatoria pura pueden utilizarse para entrenar redes neuronales con gran precisión . Esto está relacionado con la hipótesis del billete de lotería, que ya ha sido mencionada por msuzen. Pero lo que es aún más dramático, es que resulta que las grandes redes neuronales iniciadas al azar contienen subredes que pueden casi igualar el rendimiento del modelo entrenado sin formación ( Zhou et. al. Ramanujan et. al. ).

Sin embargo, puedes notar que he hecho un pequeño juego de manos. En los artículos enlazados, buscan las subredes básicamente en el espacio de todas las subredes de la red original. No es que estén tomando muestras de 60 subredes a la vez. Pero esto subraya una observación crucial que hace que el enfoque de búsqueda aleatoria sea algo factible para las redes neuronales: El muestreo de una sola red grande equivale al muestreo de un gran número de redes pequeñas . Esto se debe a que una red grande tiene un número muy grande de subredes. El problema es que el espacio de búsqueda es mucho más de 60: de hecho, la combinatoria hace imposible una enumeración exhaustiva. Por eso, en los artículos enlazados, tienen que utilizar algoritmos de búsqueda especializados para identificar la mejor (o casi mejor) subred. No pretendo que ésta sea la mejor manera de entrenar una red neuronal, pero en principio La búsqueda aleatoria es un procedimiento de formación factible.

3. Usted pregunta "¿Por qué utilizamos descenso de gradiente en lugar de la búsqueda aleatoria?". Así que en realidad no se trata sólo de una pregunta sobre la búsqueda aleatoria, sino también sobre el descenso de gradiente. Se ha planteado la hipótesis de que el propio algoritmo de descenso de gradiente estocástico es la clave de la notable capacidad de generalización de las redes neuronales. (Aquí hay un algunos ejemplos de artículos que adoptan este enfoque) Esto se denomina a veces "regularización algorítmica" o "regularización implícita". Un ejemplo sencillo: supongamos que ajustamos una regresión lineal subdeterminada utilizando el descenso de gradiente. Hay múltiples mínimos globales, pero resulta que el GD siempre converge al mínimo que tiene la norma más pequeña. Así que el punto es que el descenso de gradiente tiene un sesgo hacia ciertos tipos de soluciones, que puede ser importante cuando los modelos están sobre parametrizados, con muchos mínimos globales. Se puede encontrar fácilmente una tonelada de literatura sobre esto buscando en Google estas palabras clave. Pero el resultado es el siguiente: supongamos que podemos entrenar redes neuronales utilizando 60 iteraciones de búsqueda aleatoria. Entonces el descenso de gradiente estocástico seguiría siendo, probablemente, la forma preferida de entrenarlas, porque las soluciones encontradas por la búsqueda aleatoria no tienen ninguna regularización útil .