Optimización bayesiana

La optimización bayesiana es una estrategia secuencial basada en modelos para la optimización global de funciones objetivo de caja negra cuyas evaluaciones son costosas. ^{[ 1 ] [ 2 ] [ 3 ]} Se utiliza comúnmente cuando una sola observación requiere un experimento, un cálculo de ingeniería, una simulación numérica o una ejecución de aprendizaje automático, y cuando las derivadas no están disponibles o no son fiables. La función objetivo no necesita tener una expresión de forma cerrada.

El método construye un modelo probabilístico de la función desconocida, a menudo un proceso gaussiano (PG), y utiliza la distribución predictiva resultante para elegir el siguiente punto de evaluación. Esta elección se realiza optimizando un criterio de muestreo, también llamado función de adquisición. ^{[ 3 ] [ 2 ]}

Las aplicaciones comunes incluyen la optimización de hiperparámetros en el aprendizaje automático , donde cada prueba puede requerir el entrenamiento y la validación de un modelo, ^{[ 4 ] [ 5 ]} y problemas de diseño de ingeniería impulsados ​​por simulaciones numéricas costosas. ^{[ 6 ] [ 2 ]}

Los primeros enfoques bayesianos para la optimización global incluyen el trabajo de Harold J. Kushner sobre la localización de extremos de funciones ruidosas y el trabajo de Jonas Mockus sobre métodos bayesianos para la búsqueda de extremos. ^{[ 7 ] [ 8 ] [ 9 ] [ 1 ]}

La mejora esperada es un criterio de muestreo destacado en este campo. En 1998, Donald R. Jones, Matthias Schonlau y William J. Welch introdujeron el algoritmo de optimización global eficiente (EGO), que utilizaba un modelo de kriging o de proceso gaussiano con mejora esperada para funciones de caja negra costosas. ^{[ 6 ]}

Trabajos posteriores extendieron la optimización bayesiana a observaciones ruidosas, restricciones, evaluaciones por lotes y en paralelo, objetivos múltiples y espacios de búsqueda mixtos o de alta dimensión. ^{[ 3 ] [ 10 ]}

En un entorno estándar de un solo objetivo, la optimización bayesiana busca un punto

${\displaystyle x^{\star }\in \operatorname {arg\,min} _{x\in {\mathcal {X}}}f(x)}$

dónde${\displaystyle {\mathcal {X}}}$es un espacio de búsqueda y${\displaystyle f}$es una función objetivo desconocida. Un problema de maximización puede escribirse de la misma forma minimizando${\displaystyle -f}$Aunque el espacio de búsqueda puede ser, en principio, continuo, discreto, categórico o mixto, la formulación estándar es más directamente aplicable a dominios continuos de baja a moderada dimensión. Métodos posteriores intentan flexibilizar estas restricciones abordando variables mixtas, espacios de alta dimensión, restricciones, evaluaciones paralelas y objetivos múltiples. ^{[ 3 ] [ 10 ]}

Una distinción útil es la que existe entre optimización sin ruido y con ruido . Muchas aplicaciones reales también implican restricciones, evaluaciones paralelas o múltiples objetivos. Estas variantes modifican la forma en que se definen el modelo probabilístico, la solución actual y el criterio de muestreo. ^{[ 3 ] [ 10 ]}

Un procedimiento típico de optimización bayesiana construye una secuencia de puntos de evaluación. ^{[ 3 ] [ 2 ]} Partiendo de un diseño inicial${\displaystyle X_{0}}$El algoritmo produce puntos de evaluación adicionales${\displaystyle x_{1},x_{2},\ldots }$. Después${\displaystyle n}$evaluaciones secuenciales,${\displaystyle X_{n}=X_{0}\cup \{x_{1},\ldots ,x_{n}\}}$denota los puntos evaluados y${\displaystyle {\mathcal {D}}_{n}}$denota las observaciones correspondientes. El siguiente punto${\displaystyle x_{n+1}}$, o un lote de puntos, se selecciona optimizando un criterio de muestreo calculado a partir del modelo probabilístico actual.

El procedimiento tiene la siguiente forma:

1. Elija un diseño inicial${\displaystyle X_{0}}$, a menudo mediante un diseño que llena el espacio o un muestreo aleatorio.
2. Evalúe la función objetivo y cualquier restricción, si la hubiera, en los puntos de diseño iniciales.
3. Construir o actualizar un modelo probabilístico utilizando los datos observados.${\displaystyle {\mathcal {D}}_{n}}$.
4. Defina un criterio de muestreo, también llamado función de adquisición o criterio de relleno, a partir del modelo probabilístico.
5. Optimizar el criterio de muestreo para seleccionar${\displaystyle x_{n+1}}$o un conjunto de puntos, para su evaluación.
6. Evalúe el punto o los puntos seleccionados y actualice el conjunto de datos.
7. Repita el proceso hasta alcanzar un presupuesto de evaluación, un criterio de convergencia o una regla de parada.

La estrategia bayesiana trata la función objetivo desconocida como una función aleatoria y le asigna una distribución a priori . Esta distribución a priori refleja supuestos sobre el comportamiento de la función. Tras recopilar las observaciones, la distribución a priori se actualiza para formar una distribución a posteriori sobre la función objetivo. Esta distribución a posteriori se utiliza para construir el criterio de muestreo que determina el siguiente punto de consulta.

La optimización bayesiana requiere un modelo probabilístico de la función objetivo desconocida y, cuando existen, de las restricciones desconocidas. A partir de las evaluaciones observadas hasta el momento, el modelo proporciona una distribución predictiva para los puntos no evaluados en el espacio de búsqueda. Los criterios de muestreo se definen a partir de esta distribución predictiva, por lo que el modelo proporciona tanto valores objetivo predichos como estimaciones de incertidumbre. ^{[ 3 ] [ 2 ]} Estos modelos probabilísticos suelen denominarse modelos sustitutos o metamodelos, ya que se utilizan en lugar de evaluaciones directas de la función objetivo costosa al seleccionar puntos candidatos.

La regresión de procesos gaussianos es el modelo probabilístico estándar en las presentaciones clásicas de optimización bayesiana y sigue siendo común en las aplicaciones. Una distribución a priori de proceso gaussiano define una distribución sobre funciones. Después de recopilar las observaciones, la media y la varianza predictivas posteriores se utilizan para criterios de muestreo como la mejora esperada, la probabilidad de mejora y los criterios del límite superior de confianza. ^{[ 6 ] [ 3 ]} Se pueden utilizar otros modelos probabilísticos cuando el espacio de búsqueda, la dimensionalidad o el tamaño de los datos favorecen otra representación. ^{[ 10 ] [ 2 ]}

La optimización bayesiana se suele describir mediante un problema de un solo objetivo y sin ruido, pero el mismo bucle basado en modelos se adapta a varios entornos relacionados.

En la optimización bayesiana ruidosa, las evaluaciones devuelven observaciones como:${\displaystyle y=f(x)+\varepsilon }$en lugar de valores exactos del objetivo latente. El modelo probabilístico puede representar tanto la incertidumbre sobre${\displaystyle f}$y ruido de observación. La mejora esperada clásica sobre el mejor valor observado es un criterio sin ruido. En entornos ruidosos, se pueden definir reglas de recomendación y criterios de muestreo para el objetivo latente, para futuras observaciones ruidosas o para el valor de la información. Algunos ejemplos incluyen criterios de gradiente de conocimiento y de teoría de la información. ^{[ 3 ] [ 11 ] [ 12 ] [ 13 ]}

En la optimización bayesiana con restricciones, el objetivo se optimiza sujeto a restricciones de factibilidad. Si las restricciones también son funciones de caja negra desconocidas, se pueden construir modelos probabilísticos separados para el objetivo y las restricciones, y el criterio de muestreo puede combinar la mejora prevista con la probabilidad de factibilidad. ^{[ 14 ]}

En la optimización bayesiana por lotes o en paralelo, el método propone varios puntos candidatos antes de que se disponga de las observaciones correspondientes. Los métodos por lotes son útiles cuando se pueden ejecutar experimentos, simulaciones o tareas de aprendizaje automático simultáneamente. Pueden optimizar un criterio de muestreo conjunto o elegir puntos secuencialmente teniendo en cuenta las evaluaciones pendientes. ^{[ 15 ]}

En la optimización bayesiana multiobjetivo, se optimizan varias funciones objetivo a la vez y el resultado suele ser una aproximación a un frente de Pareto . Los métodos incluyen enfoques de escalarización como ParEGO, que reducen el problema a una secuencia de subproblemas de un solo objetivo, y enfoques basados ​​en indicadores que utilizan criterios como la mejora esperada del hipervolumen. ^{[ 16 ] [ 17 ]} La optimización bayesiana multiobjetivo con restricciones combina estas extensiones modelando objetivos y restricciones y utilizando criterios de muestreo basados ​​en reglas de dominación extendidas y la mejora esperada del hipervolumen. ^{[ 18 ]}

Un criterio de muestreo, también llamado función de adquisición en la literatura de aprendizaje automático o criterio de relleno en la optimización basada en sustitutos, asigna puntos candidatos utilizando la distribución predictiva actual. Suele ser económico de evaluar y se optimiza en lugar de la costosa función objetivo. Los criterios de muestreo expresan la compensación entre exploración y explotación al asignar valores altos a puntos con un valor objetivo predicho bajo, alta incertidumbre o ambas. ^{[ 3 ] [ 2 ]} Un ejemplo fundamental en el entorno sin ruido es la mejora esperada, que asigna un punto candidato según la ganancia esperada posterior sobre el mejor valor observado hasta el momento. ^{[ 6 ] [ 3 ]} Otros criterios incluyen la probabilidad de mejora, ^{[ 7 ]} criterios de límites de confianza superior o inferior como GP-UCB, ^{[ 19 ]} muestreo de Thompson , ^{[ 20 ]} criterios de gradiente de conocimiento, ^{[ 11 ]} criterios de teoría de la información que incluyen el criterio de minimización de entropía IAGO, búsqueda de entropía y búsqueda de entropía predictiva, ^{[ 12 ] [ 13 ] [ 21 ]} y carteras o híbridos de varios criterios. ^{[ 22 ]}

El criterio de muestreo suele ser económico de evaluar en relación con el objetivo, pero su optimización puede constituir un problema auxiliar no convexo. Su óptimo se busca a menudo mediante discretización, optimización local multi-arranque o métodos numéricos deterministas como el método de Newton y métodos cuasi-Newton como el algoritmo de Broyden-Fletcher-Goldfarb-Shanno . También se utilizan métodos estocásticos para esta búsqueda auxiliar, especialmente para criterios multimodales o de variables mixtas. Algunos ejemplos son los algoritmos genéticos y otros algoritmos evolutivos , así como los métodos secuenciales de Monte Carlo . ^{[ 3 ] [ 2 ] [ 18 ]}

Varios métodos de optimización sin derivadas utilizan distribuciones de probabilidad sin modelar la función objetivo desconocida en sí. Los algoritmos de estimación de distribución construyen y muestrean modelos probabilísticos explícitos de soluciones candidatas seleccionadas. ^{[ 23 ]} El método de entropía cruzada y CMA-ES también actualizan distribuciones de muestreo paramétricas, con CMA-ES adaptando la media, el tamaño del paso y la matriz de covarianza de una distribución normal multivariada. ^{[ 24 ] [ 25 ]} Estos métodos utilizan valores objetivo para actualizar una distribución sobre puntos candidatos. En la optimización bayesiana, el modelo probabilístico representa el objetivo o las restricciones, y el siguiente punto se elige optimizando un criterio derivado de ese modelo.

El diseño secuencial de procesos gaussianos también se utiliza en el análisis de confiabilidad para estimar una probabilidad de falla. Para una función de estado límite${\displaystyle f}$, entrada aleatoria${\displaystyle X}$y umbral${\displaystyle t}$, el objetivo puede ser${\displaystyle \mathbb {P} (f(X)\leq t)}$, o más generalmente la medida de un conjunto de excursiones. Las estrategias de reducción de incertidumbre por pasos eligen evaluaciones para reducir la incertidumbre sobre esta probabilidad, en lugar de encontrar el minimizador o el maximizador de${\displaystyle f}$. ^{[ 26 ]}

La optimización bayesiana también está relacionada con los problemas de bandidos multi-brazos . Ambos estudian decisiones secuenciales que equilibran la exploración y la explotación, y criterios como los límites superiores de confianza y el muestreo de Thompson aparecen en ambos contextos. ^{[ 19 ] [ 20 ]} Una distinción común es que los algoritmos de bandidos a menudo se formulan para controlar el arrepentimiento acumulado en una secuencia de acciones, mientras que la optimización bayesiana a menudo enfatiza encontrar un buen optimizador de una función costosa después de un pequeño presupuesto de evaluación. ^{[ 3 ] [ 2 ]}

La optimización bayesiana se utiliza en aplicaciones donde las evaluaciones objetivas son costosas. Algunos ejemplos que se discuten en estudios y libros de texto incluyen la optimización de hiperparámetros y la configuración de algoritmos, el diseño de ingeniería y la optimización basada en simulación, ^{[ 27 ]} la robótica, las redes de sensores y el diseño experimental en las ciencias físicas. ^{[ 3 ] [ 2 ] [ 10 ]}

• Bandido de múltiples brazos
• Kriging
• Muestreo de Thompson
• Optimización global
• Diseño experimental bayesiano
• Métodos numéricos probabilísticos
• óptimo de Pareto
• Aprendizaje activo (aprendizaje automático)
• Optimización multiobjetivo