Maximizando la función ruidosa desconocida

Estoy interesado en maximizar una función , donde . $f(\mathbf \theta)$ $\theta \in \mathbb R^p$

El problema es que no conozco la forma analítica de la función o de sus derivados. Lo único que puedo hacer es evaluar la función de manera puntual, conectando un valor y obtener una estimación NOISY en ese punto. Si quiero, puedo disminuir la variabilidad de estas estimaciones, pero tengo que pagar costos informáticos crecientes. $\theta_*$ $\hat{f}(\theta_*)$

Esto es lo que he intentado hasta ahora:

Descenso más empinado estocástico con diferencias finitas: puede funcionar pero requiere mucha afinación (por ejemplo, secuencia de ganancia, factor de escala) y, a menudo, es muy inestable.
Recocido simulado: funciona y es confiable, pero requiere muchas evaluaciones de funciones, así que lo encontré bastante lento.

Por lo tanto, solicito sugerencias / ideas sobre un posible método de optimización alternativo que pueda funcionar en estas condiciones. Mantengo el problema lo más general posible para alentar sugerencias de áreas de investigación diferentes a la mía. Debo agregar que estaría muy interesado en un método que me pudiera dar una estimación de la arpillera en convergencia. Esto se debe a que puedo usarlo para estimar la incertidumbre de los parámetros . De lo contrario, tendré que usar diferencias finitas alrededor del máximo para obtener una estimación. $\theta$

optimization monte-carlo simulation Jugurtha
fuente

Si no puede decir nada más específico sobre el ruido asociado con la salida de su función, no estoy seguro de que algo más sofisticado que el recocido simulado (incluso tendrá que ajustar esto, en cierta medida), será de ayuda.

Aron Ahmadia

Desafortunadamente, no sé mucho sobre el ruido aleatorio asociado con cada evaluación de función. Su distribución es desconocida, y puede ser una función de . Por otro lado, los ruidos que afectan las evaluaciones de funciones sucesivas son independientes. Obviamente, supongo que la variación del ruido no es enorme, de lo contrario la maximización sería imposible.

θ

$\theta$

Jugurtha

Por otro lado, suponga que sé algo sobre la distribución del ruido, por ejemplo, que . ¿Me ayudaría este conocimiento?

\hat{f} (θ_{*}) \sim N (f (θ_{*}), σ)

$\hat{f}(\theta_*) \sim N(f(\theta_*),\sigma)$

Jugurtha

Parece que estoy corregido por el Prof. Neumaier :)

Aron Ahmadia

Los físicos aquí, utilicé CMA-ES para la conformación de fase óptica (optimizando la fase de un pulso láser a través de un pulseshaper), que es bastante ruidoso.

tillsten

Respuestas:

Nuestro paquete Matlab SnobFit fue creado precisamente para este propósito. No se necesita suponer la distribución del ruido. Además, los valores de las funciones se pueden proporcionar a través de archivos de texto, por lo que puede aplicarlo a las funciones implementadas en cualquier sistema capaz de escribir un archivo de texto. Ver
http://www.mat.univie.ac.at/~neum/software/snobfit/

SnobFit se había desarrollado para una aplicación en la que la función a optimizar ni siquiera existía, y los valores de la función (una medida de la calidad de fabricación) se obtuvieron mediante equipos costosos especializados que crean productos de muestra y los miden a mano, lo que da como resultado aproximadamente 50 funciones evaluaciones por día.

Arnold Neumaier
fuente

Muchas gracias por su respuesta. He comenzado a leer su artículo sobre el paquete SnobFit, y me parece realmente interesante. Además, mientras leía la introducción a su artículo, me di cuenta de que el problema que estoy tratando (en un contexto estadístico) es bastante frecuente en las matemáticas industriales. Existe una vasta literatura de la que no estaba completamente al tanto. En realidad, el enfoque en el que estaba trabajando es algo similar a la aproximación cuadrática de Powell (2002).

Jugurtha

¿Snobfit funciona bien con 128 grados de libertad? Solo para saber que vale la pena probar mi caso.

tillsten

@tillsten: Ningún método para problemas ruidosos funciona bien con 128 dof a menos que pueda gastar una gran cantidad de valores de función. Sin embargo, puede probar nuestro VXQR1, que no es para problemas ruidosos, pero a veces maneja bien los problemas ruidosos.

Arnold Neumaier

El límite para Snobfit es de aproximadamente 20 variables. si tiene más, debe seleccionar por grupos de sentido común de 20 variables que optimiza parcialmente a su vez. O puede dejar deslizar algunas variables simultáneamente para reducir la dimensión.

Arnold Neumaier

Hay varias técnicas de optimización bayesianas que puedes probar. Los más fáciles se basan en el proceso gaussiano:

Harold J. Kushner. Un nuevo método para ubicar el máximo de una curva multipeak arbitraria en presencia de ruido. Journal of Basic Engineering, páginas 86: 97-106, marzo de 1964.
J. Mockus. El enfoque bayesiano para la optimización global. Lecture Notes in Control and Information Sciences, 38: 473–481, 1982.
Niranjan Srinivas, Andreas Krause, Sham Kakade y Matthias Seeger. Optimización del proceso gaussiano en el entorno de los bandidos: sin remordimientos y diseño experimental. En proc. Conferencia internacional sobre aprendizaje automático (ICML), 2010.
Andreas Krause, Ajit Singh y Carlos Guestrin. Ubicaciones de sensores casi óptimas en procesos gaussianos: teoría, algoritmos eficientes y estudios empíricos. J. Mach. Aprender. Res., 9: 235–284, junio de 2008.

Funcionan formando una función posterior sobre funciones plausibles, dan observaciones hasta el momento y sugieren el siguiente punto para aprender rápidamente la función, así como para encontrar los máximos globales (vea mi publicación de blog ).

Otra ventaja es que puede estimar el Hessian en los máximos. Sin embargo, debe especificar un modelo de ruido.

Memming
fuente

El algoritmo SPSA de James Spall (abreviatura de recocido simulado de perturbación estocástica, si no recuerdo mal) ha sido diseñado para este tipo de problema. Tiene un par de documentos donde los usa para problemas como el que usted describe.

Wolfgang Bangerth
fuente

He intentado el enfoque de Spall basado en una versión estocástica del descenso más pronunciado y Raphson Newton. Probé el recocido simulado, pero no la versión sugerida por Spall, debería probarlo. No estoy realmente entusiasmado con el recocido simulado, porque no puedo obtener una estimación del Hessian en la convergencia (mientras que, por ejemplo, con el estocástico Raphson Newton puedo obtener una aproximación al Hessian "gratis").

Jugurtha