Esta página aún no se ha traducido para esta versión. Puede ver la versión más reciente de esta página en inglés.

Algoritmo de optimización bayesiana

Contorno del algoritmo

El algoritmo de optimización bayesiana intenta minimizar una función de objetivo escalar f(x) en un dominio enlazado.x La función puede ser determinista o estocástica, lo que significa que puede devolver resultados diferentes cuando se evalúa en el mismo punto.x Los componentes de pueden ser Reals continuos, enteros o categóricos, lo que significa un conjunto discreto de nombres.x

Nota

A lo largo de esta discusión, D representa el número de componentes de.x

Los elementos clave en la minimización son:

  • Un modelo de proceso Gaussiano de f(x).

  • Procedimiento de actualización bayesiana para modificar el modelo de proceso Gaussiano en cada nueva evaluación de f(x).

  • Unfunción de adquisición a(x) (basado en el modelo de proceso Gaussiano de) que maximice para determinar el siguiente punto para la evaluación.fx Para obtener más información, consulte y.Tipos de función de adquisiciónFunción de adquisición maximización

Esquema del algoritmo:

  • Evaluar yi = f(xi) para puntosNumSeedPoints Xi, tomadas aleatoriamente dentro de los límites variables. es un ajuste.NumSeedPointsbayesopt Si hay errores de evaluación, tome más puntos aleatorios hasta que haya evaluaciones exitosas.NumSeedPoints La distribución de probabilidad de cada componente es uniforme o de escala logaritmo, dependiendo del valor en.TransformoptimizableVariable

A continuación, repita los siguientes pasos:

  1. Actualice el modelo de proceso Gaussiano de f(x) para obtener una distribución posterior de las funciones Q(f|xi, yi for i = 1,...,t). (Internamente, se usa para ajustar un modelo de proceso Gaussiano a los datos.)bayesoptfitrgp

  2. Encuentre el nuevo punto que maximiza la función de adquisiciónx a(x).

El algoritmo se detiene después de alcanzar cualquiera de los siguientes:

Para las diferencias algorítmicas en paralelo, vea.Algoritmo Bayesiano paralelo

Regresión del proceso Gaussiano para ajustar el modelo

El modelo probabilístico subyacente para la función objetiva es un proceso Gaussiano previo con ruido Gaussiano añadido en las observaciones.f Así que la distribución previa en f(x) es un proceso Gaussiano con media μ(x;θ) y la función kernel de covarianza k(x,x′;θ). Aquí, es un vector de parámetros del kernel.θ Para la función de kernel en particular, consulte.bayesoptFunción kernel

En un poco más de detalle, denotan un conjunto de puntos X = xi con los valores de función objetivo asociados F = fi. La distribución conjunta anterior de los valores de función es normal multivariada, con matriz Mean () y de covarianza (,), dondeFμXKXX Kij = k(xi,xj).

Sin pérdida de generalidad, la media anterior se da como.0

Además, se supone que las observaciones han añadido ruido Gaussiano con varianzaσ2. Así que la distribución anterior tiene covarianza K(X,X;θ) + σ2I.

El ajuste de un modelo de regresión de proceso Gaussiano a observaciones consiste en encontrar valores para la varianza de ruidoσ2 y los parámetros del kernel.θ Este accesorio es un proceso intensivo computacionalmente realizado por.fitrgp

Para obtener más información sobre cómo ajustar un proceso Gaussiano a las observaciones, consulte.Regresión del proceso Gaussiano

Función kernel

La función del kernel k(x,x′;θ) puede afectar significativamente a la calidad de una regresión del proceso Gaussiano. utiliza el kernel de ARD Matérn 5/2 definido en.bayesoptOpciones de función de kernel (covarianza)

Vea a Snoek, Larochelle y Adams.[3]

Tipos de función de adquisición

Seis opciones de funciones de adquisición están disponibles para.bayesopt Hay tres tipos básicos, también modificados por o:expected-improvementper-secondplus

  • predeterminado'expected-improvement-per-second-plus'

  • 'expected-improvement'

  • 'expected-improvement-plus'

  • 'expected-improvement-per-second'

  • 'lower-confidence-bound'

  • 'probability-of-improvement'

Las funciones de adquisición evalúan la "bondad" de un punto basado en la función de distribución posterior.xQ Cuando hay restricciones acopladas, incluida la restricción error (ver), todas las funciones de adquisición modifican su estimación de "bondad" siguiendo una sugerencia de Gelbart, Snoek y Adams.Errores de función objetiva[2] Multiplique la "bondad" por una estimación de la probabilidad de que se cumplan las restricciones, para llegar a la función de adquisición.

Mejora esperada

La familia de funciones de adquisición evalúa la cantidad esperada de mejora en la función objetiva, ignorando los valores que causan un aumento en el objetivo.'expected-improvement' En otras palabras, defina

  • xbest como la ubicación de la media posterior más baja.

  • μQ(xbest) como el valor más bajo de la media posterior.

Entonces la mejora esperada

EI(x,Q)=EQ[max(0,μQ(xbest)f(x))].

Probabilidad de mejora

La función de adquisición hace un cálculo similar, pero más simple, como.'probability-of-improvement''expected-improvement' En ambos casos, primero calculabayesoptxbest Y μQ(xbest). A continuación, para, calcula la probabilidad de que un nuevo punto conduce a un mejor valor de función objetivo, modificado por un parámetro de "margen":'probability-of-improvement'bayesoptPIxm

PI(x,Q)=PQ(f(x)<μQ(xbest)m).

toma como la desviación estándar de ruido estimada. evalúa esta probabilidad comobayesoptmbayesopt

PI=Φ(νQ(x)),

Dónde

νQ(x)=μQ(xbest)mμQ(x)σQ(x).

Aquí Φ(·) es el CDF normal de la unidad, y ΣQ es la desviación estándar posterior del proceso Gaussiano en.x

Menor confianza vinculada

La función de adquisición examina la curva dos desviaciones estándar por debajo de la media posterior en cada punto:'lower-confidence-bound'G

G(x)=μQ(x)2σQ(x).

() es el 2GxΣQ menor dotación de confianza del modelo de función objetiva. a continuación, maximiza el negativo de:bayesoptG

LCB=2σQ(x)μQ(x).

Por segundo

A veces, el tiempo para evaluar la función objetiva puede depender de la región. Por ejemplo, muchos cálculos de máquina de vectores de soporte varían en la temporización de una buena oferta sobre ciertos rangos de puntos. Si es así, puede obtener una mejor mejora por segundo utilizando la ponderación de tiempo en su función de adquisición.bayesopt Las funciones de adquisición ponderadas por costes tienen la frase en sus nombres.per-second

Estas funciones de adquisición funcionan de la siguiente manera. Durante las evaluaciones de la función objetiva, mantiene otro modelo bayesiano de tiempo de evaluación de la función objetiva en función de la posición.bayesoptx La mejora esperada por segundo que utiliza la función de adquisición es

EIpS(x)=EIQ(x)μS(x),

Dónde ΜS() es la media posterior del modelo de proceso Gaussiano de temporización.x

Más

Para escapar de una función objetivo local mínima, las funciones de adquisición con sus nombres modifican su comportamiento cuando estiman que son un área.plussobreexplotar Para entender la sobreexplotación, deja que ΣF() ser la desviación estándar de la función objetivo posterior en.xx Seamos la desviación estándar posterior del ruido aditivo, de modo queσ

ΣQ2( ) =x ΣF2( ) +xσ2.

Definir Tσ ser el valor de la opción, un número positivo.ExplorationRatio Las funciones de adquisición, después de cada iteración, evalúan si el siguiente punto satisfacebayesoptplusx

ΣF( ) <x Tσ.σ

Si es así, el algoritmo declara que está sobreexplotando.x A continuación, la función de adquisición modifica su multiplicando por el número de iteraciones, como sugiere Bull.Función kernelθ[1] Esta modificación eleva la varianza ΣQ para puntos entre observaciones. A continuación, genera un nuevo punto basado en la nueva función de kernel ajustada. Si el nuevo punto está sobreexplotando de nuevo, la función de adquisición se multiplica por un factor adicional de 10 e intenta de nuevo.xθ Continúa de esta manera hasta cinco veces, tratando de generar un punto que no está sobreexplotando.x El algoritmo acepta el nuevo como el siguiente punto.x

por lo tanto, controla un equilibrio entre explorar nuevos puntos para una mejor solución global, versus concentrarse cerca de puntos que ya han sido examinados.ExplorationRatio

Función de adquisición maximización

Internamente, maximiza una función de adquisición mediante los siguientes pasos generales:bayesopt

  1. Para los algoritmos que empiezan por y para, estima la media factible más pequeña de la distribución posterior'expected-improvement''probability-of-improvement'bayesopt μQ(xbest) probando varios miles de puntos dentro de los límites variables, tomando varios de los mejores (valor medio bajo) puntos factibles, y mejorándolos utilizando la búsqueda local, para encontrar el ostensible mejor punto factible. Factible significa que el punto satisface las restricciones (ver).Las restricciones en la optimización bayesiana

  2. Para todos los algoritmos, muestras de varios miles de puntos dentro de los límites variables, toma varios de los mejores (alta función de adquisición) puntos factibles, y los mejora mediante la búsqueda local, para encontrar el ostensible mejor punto factible.bayesopt El valor de la función de adquisición depende de la distribución posterior modelada, no de una muestra de la función objetiva, por lo que se puede calcular rápidamente.

Referencias

[1] Bull, A. D. Convergence rates of efficient global optimization algorithms. https://arxiv.org/abs/1101.3501v3, 2011.

[2] Gelbart, M., J. Snoek, R. P. Adams. Bayesian Optimization with Unknown Constraints. https://arxiv.org/abs/1403.5607, 2014.

[3] Snoek, J., H. Larochelle, R. P. Adams. Practical Bayesian Optimization of Machine Learning Algorithms. https://arxiv.org/abs/1206.2944, 2012.

Temas relacionados