Función estocástica mínimo-máxima de pocas variables

Question

Me encuentro ante un problema de optimización que tendré que ejecutar (con una variedad de hiperparámetros diferentes) y me gustaría recibir algunos consejos sobre la mejor manera de optimizarlo. Tengo una función $f$ que sólo puedo evaluar de forma ruidosa, es decir, hay una varianza aleatoria. Tengo unas 7 variables en el grupo "A", y otras 4 variables en el grupo "B". Me gustaría maximizar la expectativa de $f$ con respecto a las variables A, mientras que simultáneamente se minimiza con respecto a "B". Cada evaluación de $f$ tarda entre unos segundos y un minuto, por lo que no me importa ejecutar un algoritmo relativamente complicado utilizando los datos de todas mis evaluaciones anteriores, con el fin de converger en menos llamadas a $f$ . La única restricción es que las variables sean todas positivas. Dado que también están operando en escalas muy diferentes (algunos son ~1, algunos son ~0,001, algunos son ~1000), por lo que estoy haciendo el problema un poco más fácil tomando el logaritmo de todos los parámetros primero. Es decir, en realidad estoy evaluando $f(\exp(\bf x))$ y ajustando mi vector de parámetros $\bf x$ . Espero que el cambio de mi destino óptimo sea dentro de $\pm 3$ en cada coordenada de $\bf x$ entonces. (Por lo tanto, dentro de un orden de magnitud de mis parámetros originales.) Esto también significa que el problema es esencialmente completamente sin restricciones ahora.

Esta es una idea que he tenido: Empezar por evaluar $f$ en un punto inicial $\bf x_0$ y, a continuación, evaluar $f$ a otros valores para $x_0$ con cada coordenada $\pm 1$ . Haga un ajuste cuadrático a estos puntos (ya tengo una biblioteca preparada para hacerlo), y luego inspeccione el término cuadrático. Si sólo tuviera variables del grupo A, entonces comprobaría que el término cuadrático es positivo definido, y luego haría una prueba en el óptimo global estimado de esa cuadrática. A medida que tome más y más puntos de prueba cerca del óptimo, el ajuste cuadrático empezará a prestar más atención a ajustarse correctamente alrededor de ahí (ya que tengo más muestras), y así esto debería converger al valor correcto. El inconveniente es que podría acabar ponderando "incorrectamente" los valores alejados del óptimo durante bastante tiempo; et No estoy seguro de cómo manejaría cuando no es positiva definitiva (sólo ejecutar un punto de prueba al azar cerca de un viejo óptimo esperado, tal vez??); et No estoy seguro de cómo manejaría la adición en las variables del grupo B manejaría esto.

Una posibilidad sería escribirla como la suma de una cuadrática A en y una cuadrática en B, y luego pasar al máximo de un término y al mínimo del otro. Pero esto descuida los términos cruzados de la variable A/B, que espero que importen aquí. De nuevo, lo ideal es que, a medida que se acumulen más datos alrededor del verdadero óptimo, éste converja (es decir, que todos los datos de B se recojan cerca del óptimo de A, y viceversa), pero esa convergencia podría ser muy lenta. Y todavía no estoy seguro de cómo abordar la definición positiva.

He podido encontrar algo de información sobre algoritmos de optimización estocástica, pero todos parecen estar mucho más diseñados para el caso con restricciones de memoria muy ajustadas, de forma que evitan utilizar demasiado las evaluaciones anteriores. Por ejemplo, este es el problema con el algoritmo de Python noisyopt algoritmos. Dado que estoy min-maxing en diferentes variables, también, básicamente tengo que optimizar con respecto a A, y luego manteniendo A constante, optimizar el otro con respecto a B, que no es algo que la mayoría de los paquetes parecen gustar mucho, así que creo que tengo que rodar mi propio algoritmo aquí (y estoy muy feliz de hacerlo - Sólo quiero que estas optimizaciones sean rápidas!)

El código final en el que ejecuto muchos de estos problemas de optimización, espero ejecutarlo en el transcurso de un mes más o menos como parte de un proyecto de investigación, por lo que estoy muy contento de escribir mi propio algoritmo si creo que será más estable y requerirá menos invocaciones.

Answer 1

Sugiero probar Aproximación estocástica de perturbación simultánea . El enlace tiene un tutorial para principiantes muy claro y un enlace al código de Matlab; alteraré el algoritmo básico ligeramente para tratar el problema de mínimo/máximo y presentaré algo de código R en un problema de punto de silla de montar de juguete.

El SPSA está diseñado para problemas que implican la minimización o maximización de una función estocástica continua sin restricciones. Puede extenderse con bastante facilidad a problemas con un pequeño número de restricciones, y también existe una variante de búsqueda de raíces. También se ha extendido a problemas discretos. Lo he utilizado en problemas con cientos de parámetros con éxito.

La idea básica es que, en cada iteración $k$ formamos una estimación del gradiente en una dirección elegida al azar mediante el muestreo de la función $f$ en dos puntos $\theta_k \pm c_k\Delta$ en torno al valor del parámetro actual $\theta_k$ . $\Delta$ se suele elegir generando un vector de $\pm 1$ valores; $c_k$ es un parámetro de escala que disminuye lentamente a medida que aumenta el número de iteraciones. Nuestra estimación del gradiente se forma de la manera obvia:

$$g_k = (f(\theta + c_k\Delta)-f(\theta - c_k\Delta)/2c_k\Delta$$

donde la división se realiza de forma elemental por lo que $g$ es un vector de la longitud adecuada. Una vez que tenemos un gradiente, damos un paso en la dirección apropiada (dependiendo de si estamos minimizando o maximizando) para obtener la estimación de la siguiente iteración de $\theta$

$$\theta_{k+1} = \theta_k - \alpha_kg_k$$

donde $a_k$ es un tamaño de paso que disminuye a medida que $k$ aumenta. Obviamente, he asumido que estamos ante un problema de minimización en la línea anterior. Pautas para elegir las secuencias $a_k, c_k$ abundan, pero en realidad es bastante fácil y, según mi experiencia, no se necesita mucha experimentación.

En tu caso, como estás minimizando con respecto a algunos parámetros y maximizando con respecto a otros, simplemente cambiarías el signo de la derivada para los parámetros que estás maximizando.

Un ejemplo Tenemos la función $f(x) = x_1^2 - x_2^2$ con algo de ruido (distribuido $N(0,1)$ ) añadido al valor de retorno. Intentaremos minimizar con respecto al primer parámetro y maximizar con respecto al segundo. Utilizando el excelente paquete plot3D en R, trazamos la función desanonizada en las proximidades del punto de equilibrio:

El punto de la silla de montar, que estamos tratando de encontrar, está en $x = (0,0)$ . Empezaremos en $x=(2,-2)$ para lo cual $f(x)=0$ , al igual que en el punto de la silla de montar. El código de R, escrito para mayor claridad en lugar de eficiencia, es:

f <- function(x) {
   x[1]*x[1] - x[2]*x[2] + rnorm(1)
}

# Parameters for SPSA
alpha <- 0.606  # Often used as a default value
gamma <- 0.16   # Often used as a default value
A <- 10         # Set at 5-10% of rough guess at max iteration count
a0 <- 1
c0 <- 1

x_history <- matrix(0,51,2)

# Starting values (optimum is (0,0))
# Note f at starting values = f at optimum = 0
x_history[1, ] <- c(2,-2)

# SPSA loop a fixed number of times, as this is a demo
for (k in 1:(nrow(x_history)-1)) {
   # Step size parameters 
   ck <- c0 / (k^gamma)
   ak <- a0 /(A+k)^alpha

   # Random step direction
   delta <- ck * (2*rbinom(2, 1, 0.5) - 1)

   # Function evaluation + derivative calculation
   f_plus <- f(x_history[k,] + delta)
   f_minus <- f(x_history[k,] - delta)
   deriv <- (f_plus - f_minus) / (2*delta)

   # We are trying to maximize on the second parameter, 
   # so switch the sign of its "derivative"
   deriv[2] <- -deriv[2]

   x_history[k+1,] <- x_history[k,] - ak*deriv
}

La traza de los valores de los parámetros en cada iteración tiene el siguiente aspecto:

> matplot(x_history, xlab='Iteration count', ylab='Parameter values')

O bien, superpuesto a la función desanestesiada:

> f_values <- function(x,y) x*x - y*y
> M <- mesh(seq(-2.2, 2.2, by=0.1), seq(-2.2, 2.2, by=0.1))
> surf3D(x=M$x, y=M$y, z=f_values(M$x, M$y), theta=30)
> scatter3D(x=x_history[,1], y=x_history[,2], z=f_values(x_history[,1], x_history[,2]), 
          type='b', add=TRUE, pch=19, colkey=FALSE)

Como podemos ver, el algoritmo es, más o menos aleatorio, se mueve hacia $x = (0,0)$ a lo largo de la línea $f(x) = 0$ . En esta iteración de la respuesta, en realidad saltó casi todo el camino en la iteración 4.

Un enfoque común para formar la estimación final de los valores óptimos de los parámetros es promediar un cierto número de iteraciones. Esto no es útil si alpha = 1 por razones técnicas, pero es más útil como alpha -> 0.606 (el más bajo que debería ser.) Para nuestra ejecución de muestra, obtenemos:

> colMeans(x_history[4:51,])
[1] 0.1106594 0.0896351
> f_values(0.1106594, 0.0896351)
[1] 0.004211052

que no está tan mal, dado que no hemos hecho ningún ajuste de parámetros. Tenga en cuenta que, como los valores en cada paso van a estar autocorrelacionados, la desviación estándar de la muestra estará sesgada, aunque podría eliminar gran parte del sesgo aplicando un modelo ARMA simple a la serie sobre las iteraciones en las que parece haberse estabilizado y utilizando las estimaciones resultantes.

Por supuesto, su kilometraje variará. Es posible que necesite varios cientos de iteraciones para lograr la convergencia, lo que, teniendo en cuenta los tiempos de evaluación de las funciones, podría llevar varias horas de cálculo. El ajuste de los parámetros también puede llevar un tiempo considerable. Hay versiones de segunda derivada que convergen más rápidamente cuando se llega a la vecindad del óptimo, pero requieren algo más de codificación y ajuste de parámetros. Existe una forma estructurada de seleccionar el $\Delta$ en cada iteración que puede acelerar un poco la convergencia. Pero, en general, no he encontrado ninguna técnica estándar para optimizar funciones estocásticas que sea tan buena en una gama tan amplia de problemas como SPSA y sus variantes.