¿Por qué la optimización bayesiana no funciona bien en más de 20 dimensiones?

Question

He estado estudiando Optimización bayesiana últimamente e hizo las siguientes anotaciones sobre este tema:

• A diferencia de las funciones deterministas, las funciones del mundo real se construyen utilizando mediciones físicas

• Las mediciones siempre pueden tener errores (por ejemplo, error humano, error de diseño y de experimentación, error aleatorio, error de medición): si se registran las mismas mediciones en las mismas condiciones pero en un momento futuro, es muy probable que estas mediciones puedan ser diferentes de las anteriores.

• Por tanto, una función objetivo basada en mediciones físicas es "inestable" por naturaleza: dos personas pueden registrar las mismas mediciones, obtener valores diferentes y, como resultado, dos funciones objetivo distintas.

• Una función "ruidosa" es también una función "inestable": si tuviéramos que optimizar esta "función ruidosa", los resultados de la optimización podrían no corresponderse con el sistema natural que estamos estudiando debido a los errores inherentes al registrar las mediciones. Esto significa que, en cierto sentido, estamos ante una versión más complicada de "manzanas y naranjas".

• La optimización bayesiana intenta resolver este problema utilizando las mediciones registradas como "clavijas" y montando una "carpa de circo" sobre estas mediciones mediante la forma de un proceso gaussiano. Esto actúa como una especie de "suavizado probabilístico" y trata de tener en cuenta estadísticamente todas las posibles variaciones no capturadas que existen en las mediciones, siempre que la suposición de que el "proceso generador de datos" está bien representado por un proceso gaussiano sea cierta.

• Así, la optimización bayesiana intenta "suavizar" el ruido/variación/error en la función objetivo, añadiendo una "robustez" natural a la solución de optimización final. Todo esto significa que la optimización bayesiana tiene el potencial de darnos mejores resultados.

Ventajas de la optimización bayesiana:

• Robustez (como se ha descrito anteriormente)
• No requiere que la función objetivo sea diferenciable (es decir, es útil en problemas de optimización discretos y combinatorios).
• Como no calcula la derivada, tiene el potencial de ser más "eficiente computacionalmente" en comparación con los métodos de optimización basados en el gradiente.

Desventajas de la optimización bayesiana:

• Requiere que la verdadera función objetivo esté bien modelada por un Proceso Gaussiano
• Empíricamente se ha observado que funciona mal en funciones objetivo de alta dimensión (es decir, más de 20 dimensiones) - sin embargo, no entiendo por qué.

A menudo he oído esta afirmación sobre el bajo rendimiento de la optimización bayesiana en más de 20 dimensiones, pero nunca he sido capaz de entender por qué. He intentado consultar algunas referencias en Internet:

1) "Optimización bayesiana de alta dimensión con subespacios Axis-Aligned Subspaces" (Eriksson et al 2021)

• "La BO de alta dimensionalidad presenta un desafío particular, en parte porque la maldición de la dimensionalidad hace difícil definir -así como hacer inferencia sobre- una clase adecuada de modelos sustitutos".

• "Si bien BO se ha convertido en un algoritmo de caballo de batalla que se emplea en una amplia variedad de entornos, las aplicaciones exitosas a menudo se limitan a problemas de baja dimensión, por ejemplo, menos de menos de veinte dimensiones [Frazier, 2018]. La aplicación de BO a problemas de alta dimensión sigue siendo un desafío significativo. La dificultad se puede remontar a los dos componentes del algoritmo mencionados anteriormente, aunque postulamos que los priors de función adecuados son especialmente importantes para un buen rendimiento. En particular, para que BO sea eficiente en cuanto a la muestra en espacios de alta dimensión, es crucial definir modelos sustitutos que sean lo suficientemente parsimoniosos como para que puedan inferirse a partir de un pequeño número de puntos de consulta. Una clase de modelos Una clase de modelos demasiado flexible puede sufrir de sobreajuste, lo que limita seriamente su eficacia en la toma de decisiones. Del mismo modo, una clase de modelos demasiado rígida probablemente no pueda de la función objetivo. Es esencial un compromiso entre flexibilidad y parsimonia".

2) " High-dimensional Bayesian optimization using low-dimensional feature spaces" (Moriconi et al, 2020)

• "Sin embargo, la BO (optimización bayesiana) está prácticamente limitada a la optimización de 10-20 parámetros. Para escalar BO a dimensiones altas solemos hacer suposiciones estructurales sobre la descomposición del objetivo y/o explotar la baja dimensionalidad intrínseca del problema, por ejemplo, utilizando proyecciones lineales. proyecciones lineales. Podríamos lograr una mayor tasa de compresión con proyecciones no lineales no lineales, pero el aprendizaje de estas incrustaciones no lineales suele requerir muchos datos. datos. Esto contradice el objetivo de BO de un presupuesto de evaluación relativamente pequeño".

3) "Un tutorial sobre optimización bayesiana" (Frazier, 2018)

• "(La optimización bayesiana) es la más adecuada para la optimización en dominios continuos de menos de 20".

• "La entrada x está en R-d para un valor de d que no sea demasiado grande. Típicamente d 20 en la mayoría de las aplicaciones exitosas de BayesOpt".

Mi pregunta : En ningún lugar de estos documentos explican por qué "20 Dimensiones" parece ser un umbral relevante para decidir las condiciones en las que el rendimiento de la Optimización Bayesiana comienza a deteriorarse.

• ¿Puede alguien explicar por qué se dice que "20 dimensiones" es el umbral máximo para la optimización bayesiana?

• Aunque se proporcionan algunas explicaciones que explican la dificultad de la optimización bayesiana en dimensiones superiores, ¿podría alguien ayudarme a entender esto con más detalle?

Referencias:
Optimización bayesiana de alta dimensión con subespacios dispersos alineados por ejes ( PDF )
Tutorial sobre optimización bayesiana ( PDF )
Optimización bayesiana de alta dimensión utilizando espacios de características de baja dimensión ( PDF )

Answer 1

Para ser completamente honesto, es porque todo obtiene malos resultados en más de 20 dimensiones. La optimización bayesiana no es especial en este caso.

Intentar optimizar cualquier función en muchas dimensiones es difícil, porque el volumen de un espacio de alta dimensión aumenta exponencialmente con el número de dimensiones. Consideremos un segmento de línea en $[0, k]$ ; que tiene longitud $k$ . ¿Un cuadrado unitario? Que tiene área $k^2$ . Y así sucesivamente. Así que la cantidad de espacio que tienes que buscar cuando buscas una posible solución aumenta muy, muy, rápido. Te recomiendo que busques más información sobre la "maldición de la dimensionalidad".

Esto siempre será cierto, independientemente del algoritmo que utilices a menos que estás dispuesto a hacer algunas suposiciones simplificadoras sobre la forma de esa función. Por ejemplo, el descenso por gradiente puede funcionar bastante bien en dimensiones altas, siempre que la función sea diferenciable. Si usted tiene una función donde el gradiente es 0 en algún punto además del mínimo estás jodido.

La optimización bayesiana es exactamente igual. Los artículos que has enlazado señalan que si tu función tiene una estructura interesante, puedes explotarla eligiendo buenos priors. En concreto, hay que suponer sparsity (que sólo unas pocas de esas dimensiones son importantes y el resto se puede ignorar), o diferenciabilidad, en cuyo caso se puede utilizar procesos gaussianos mejorados por gradiente . Pero si no tienes esa estructura, estás jodido.

En cuanto a las 20 dimensiones, es un regla de oro. No hay "umbral" ni nada, pero se endurece exponencialmente con rapidez.

Answer 2

No encontrará una justificación teórica/científica para esta afirmación, ¡pues no la hay!

La dificultad de la optimización está relacionada con muchas cosas, y la dimensión es sólo una de ellas, y lo más probable es que ni siquiera sea muy importante. Por ejemplo, si nos limitamos a suponer la continuidad y no la diferenciabilidad de la función objetivo, la cuestión de la dimensión del dominio se vuelve completamente irrelevante. En curvas de llenado de espacio siempre puede reparametrise un $n$ -a una función de una sola variable.

Así, es muy fácil encontrar funciones unidimensionales imposibles de optimizar con BO. Y también es fácil encontrar funciones en cientos o incluso miles de dimensiones que son sencillas de optimizar, ya sean bayesianas o de otro tipo.

Entonces, ¿por qué algunas personas hacen tales afirmaciones y por qué otras las creen?

Creo que hay dos razones para ello:

1. Son (en los casos que al investigador le interesan o conoce) una buena heurística.
2. La calificación completa de esas afirmaciones es demasiado larga y contendría demasiadas complicadas calificaciones "puramente teóricas". Y muchas de esas cualificaciones son probablemente "obvias" para las personas que trabajan en este campo, "se dan por supuestas".

Answer 3

Sí, el espacio de alta dimensión es difícil en general, pero hay un par de cosas que hacen que la optimización bayesiana con procesos gaussianos sea particularmente desconcertante en esos problemas espinosos.

En mi opinión, no hay una única razón por la que la alta dimensión dificulte la BO, sino que la dificultad se debe más bien a una confluencia de múltiples factores.

En primer lugar La optimización bayesiana se realiza clásicamente con un proceso gaussiano que utiliza algo parecido a un núcleo exponencial cuadrado. Se trata de un kernel que proporciona una gran flexibilidad, lo cual es perfecto en dimensiones bajas, pero puede convertirse en un inconveniente en dimensiones altas, ya que pone una masa de probabilidad razonable en demasiados explicaciones de la nube de puntos. Así que el primer problema es que el modelo que estamos utilizando ya está luchando para entender lo que está pasando.

Esto está relacionado con el argumento del volumen de la otra respuesta. Dado que las GP dependen explícitamente de las distancias, cuando todas las distancias entre puntos son iguales y grandes, la GP tiene poco poder de discriminación.

Observe cómo, a medida que avanzamos en la dimensión superior, las distancias entre puntos aleatorios varían menos que en la dimensión inferior:

[ "A survey on high-dimensional Gaussian process modeling with application to Bayesian optimization" por Mickaël Binois y Nathan Wycoff ]

Como mencionas, estructurar la función kernel de forma que estemos aprendiendo un mapeo en un espacio de baja dimensión sobre el que colocamos un proceso gaussiano "estándar" es una buena forma de proceder. Otra opción es asumir una función kernel que combine la información de las dimensiones de entrada de una manera más frugal, como por ejemplo aditivo (Procesos aditivos gaussianos Parte de Avances en Sistemas de Procesamiento de Información Neuronal 24 (NIPS 2011) por David K. Duvenaud, Hannes Nickisch, Carl Rasmussen) o Núcleos ANOVA ("Descomposición ANOVA de procesos gaussianos condicionales para el análisis de sensibilidad con entradas dependientes" Gaëlle Chastaing, Loic Le Gratiet).

En segundo lugar no podemos olvidar que BO es un procedimiento de optimización anidado: cada vez que un algoritmo BO quiere sugerir un siguiente punto para optimizar, ¡tiene que resolver un problema de suboptimización completo sobre todo el espacio! A diferencia del problema de optimización original, el función de adquisición definido por nuestro proceso gaussiano (cuyo punto de optimización es nuestro siguiente candidato en nuestra búsqueda externa) suele tener un gradiente y un hessiano conocidos, lo que es realmente útil para encontrar una solución local.

Sin embargo, la función de adquisición es notoriamente no convexa, lo que significa que en espacios de alta dimensión, por muy rápido que podamos encontrar un óptimo local, podemos tener pocas posibilidades de encontrar algo cercano a un óptimo global sin un esfuerzo considerable. Aunque esto no afecta a la capacidad del proceso gaussiano para modelizar el objetivo desconocido, sí afecta a nuestra capacidad para explotar sus conocimientos para la optimización.

Cuando se combina con los chanchullos del núcleo, a veces la función de adquisición puede optimizarse en un espacio dimensional más bajo, lo que puede facilitar las cosas (o a veces dificultarlas en la práctica; la reducción de la dimensión lineal significa que ahora estamos haciendo programación lineal en lugar de optimización sin restricciones y además no casa bien con las restricciones de hipercaja).

Y tercera es el riesgo de estimación de los hiperparámetros. Los más populares hoy en día son los núcleos anisotrópicos "separables", "ARD", "producto tensorial" o alineados con el eje, que tienen un aspecto similar a $k(\mathbf{x}_1,\mathbf{x}_2) = \sigma^2 e^{\sum_{p=1}^P \frac{(x_{1,p}-x_{2,p})^2}{2\ell_p}}$ y estimar los hiperparámetros de un proceso gaussiano es difícil, tanto desde el punto de vista de la inferencia estadística como del análisis numérico.

Utilizar un mapeo parametrizado en baja dimensión sólo empeora el riesgo de estimación (pero puede compensarse con una clase de funciones de varianza sustancialmente menor a priori ).

Cuarto : Tiempo de cálculo. Las GP son conocidas por sus datos reducidos estadística eficiencia (en términos de error/datos) y grandes datos computacional ineficacia (en términos de inferencia / segundo). En alta dimensión, si realmente queremos encontrar un óptimo global, probablemente vamos a tener que evaluar la función objetivo toneladas de veces y, por lo tanto, disponemos de un amplio conjunto de datos para nuestra GP. Este no es el nicho histórico de las GP, ya que la inferencia de las GP clásicas basadas en la descomposición (es decir, en las que realmente se toma una Cholesky de la matriz del núcleo) se escala con $n^3$ por lo que se vuelve intratable rápidamente.

La optimización de la función de adquisición también se encarece a medida que $n$ también sube. Y ten en cuenta que tienes que hacer esto entre cada iteración de optimización . Por tanto, si tenemos un presupuesto de optimización de $10,000$ ingenuamente tendríamos que hacer toda esta optimización numérica literalmente $10,000-n_{\textrm{init}}$ veces (aunque, por supuesto, en la práctica evaluaríamos lotes de puntos a la vez y sólo optimizaríamos los hiperparámetros cada pocos iters).

Sin embargo, la inferencia GP a gran escala en alta dimensión ha madurado realmente en las últimas décadas, y ha sido el motor de algunos de los últimos trabajos GP-BO a gran escala.