Optimización cuando la Función de Costo Lento para Evaluar

Question

Gradiente de la pendiente y muchos otros métodos son útiles para la búsqueda de mínimos locales en las funciones de costo. Se puede ser eficiente cuando la función de coste se puede evaluar rápidamente en cada punto, ya sea numérica o analítica.

Tengo lo que me parece una situación inusual. Cada evaluación de mi función de costo es caro. Estoy tratando de encontrar un conjunto de parámetros que minimizan una superficie 3D en contra de la verdad debido a las superficies. Siempre que puedo cambiar un parámetro, necesito ejecutar el algoritmo en contra de toda la cohorte de la muestra para medir su efecto. Para calcular el gradiente, necesito cambiar todos 15 los parámetros de forma independiente, lo que significa que me tiene que regenerar todas las superficies y se compara con la muestra de la cohorte demasiadas veces por la pendiente, y sin duda demasiadas veces en el curso de optimización.

He desarrollado un método para eludir este problema y actualmente estoy evaluando, pero me sorprende que no he encontrado mucho en la literatura sobre el costo caro función de las evaluaciones. Esto hace que me pregunte si estoy haciendo el problema más difícil de lo que es y que podría ser una mejor manera ya disponible.

Así que mi pregunta(s) son básicamente esto: ¿alguien sabe de métodos para la optimización de funciones de costo, convexo o no, cuando la evaluación es lento? O estoy haciendo algo tonto, en primer lugar por volver a ejecutar el algoritmo y se comparan con la muestra de la cohorte tantas veces?

Answer 1

Bayesiano en la Optimización de métodos de tipo de acumulación de Gauss proceso de sustituto de los modelos para explorar el espacio de parámetros. La idea principal es que el parámetro de tuplas que están más cerca juntos, serán similares, los valores de la función, por lo que la asunción de una co-variación de la estructura de puntos permite que el algoritmo de hacer conjeturas acerca de lo mejor parámetro tupla es más que vale la pena tratar la siguiente. Esta estrategia ayuda a reducir el número de función de las evaluaciones; de hecho, la motivación de BO métodos es mantener el número de función de las evaluaciones de tan baja como sea posible, mientras que "el uso de todo el búfalo" para hacer una buena estimación acerca de qué punto a la prueba siguiente. Hay diferentes figuras de mérito (mejora esperada, que se espera cuantil de mejora, la probabilidad de mejora...) que se utilizan para comparar los puntos a visitar la próxima.

Contraste esto con algo parecido a un grid de búsqueda, los cuales nunca utilizar cualquier información de su anterior función de las evaluaciones para informar a dónde ir.

Por cierto, este es también un poderoso global de la optimización de la técnica, y como tal no hace suposiciones acerca de la convexidad de la superficie. Además, si la función es estocástica (por ejemplo, evaluaciones, algunos inherentes al ruido aleatorio), esto puede ser directamente representaron en el modelo GP.

Por otro lado, tendrás que encajar al menos un GP en cada iteración (o varios, escoger el "mejor", o un promedio de más alternativas, o totalmente Bayesiano métodos). Entonces, el modelo se utiliza para hacer (probablemente miles) de predicciones, generalmente en la forma de multistart optimización local, con la observación de que es mucho más barato para evaluar el GP función de predicción de la función en virtud de la optimización. Pero incluso con esta sobrecarga computacional, tiende a ser el caso que, nonconvex funciones puede ser optimizada con un relativamente pequeño número de llamadas a la función.

El trabajo seminal sobre el tema se Jones et al, "Eficiente Optimización Global de la Cara a la Caja Negra de las Funciones." Pero hay muchas variaciones de esta idea.

Answer 2

La literatura sobre la evaluación de las caras de "caja negra" de la función es muy amplio, y generalmente se basa en sustituto de métodos de modelo, como a otras personas, señaló. La caja negra de aquí significa que poco se sabe acerca de la función subyacente, la única cosa que usted puede hacer es evaluar $f(x)$ a un punto elegido $x$ (gradientes generalmente no están disponibles).

Yo diría que el actual estándar de oro para la evaluación de la (muy) costosos de "caja negra" de la función es (global) Bayesiano de optimización (BO). user777 ya se ha descrito algunas de las características de BO, así que estoy añadiendo algo de información que podría ser útil.

Como punto de partida, es posible que desee leer este documento general [1]. También hay una más reciente [2].

Bayesiano de optimización ha ido creciendo de forma constante como un campo en los últimos años, con una serie de talleres especializados (por ejemplo, BayesOpt, y echa un vistazo a estos vídeos de Sheffield taller sobre BO), ya que tiene aplicaciones prácticas en el aprendizaje de máquina, como para la optimización de hyper-parámetros de ML algoritmos; ver, por ejemplo, este papel [3] y relacionados con la caja de herramientas, la Menta verde. Hay muchos otros paquetes en varios idiomas, que implementar diversos tipos de Bayesiana algoritmos de optimización.

Como he mencionado, el requisito subyacente es que cada función de la evaluación es muy costoso, por lo que el BO-cálculos relacionados con agregar un insignificante sobrecarga. Para dar un estadio de béisbol, BO puede ser sin duda útil si su función se evalúa en un tiempo del orden de minutos o más. También se puede aplicar para cálculos más rápidos (por ejemplo, decenas de segundos), pero dependiendo del algoritmo que se utilice puede adoptar diversas aproximaciones. Si su función se evalúa en la escala de tiempo de segundos, creo que lo están golpeando los límites de la investigación actual y tal vez de otros métodos podrían ser más útiles. También, tengo que decir, BO rara vez es realmente caja negra y que a menudo tienen que ajustar los algoritmos, a veces mucho, para hacer que funcione a plena potencia con un determinado problema de la vida real.

BO a un lado, para una revisión general de los derivados-libre de optimización de los métodos que usted puede echar un vistazo a esta revisión [4] y verificación de algoritmos que tienen buenas propiedades de rápida convergencia. Por ejemplo, Multi-nivel de Coordinar la Búsqueda (MCS) generalmente converge muy rápidamente a un barrio, de un mínimo (no siempre el mínimo global, por supuesto). MCS está pensado para la optimización global, pero se puede hacer local mediante la configuración apropiada obligado restricciones.

---

Referencias:

[1] Brochu et al., "Un Tutorial sobre Bayesiano de Optimización de Costo Caro Funciones, con Aplicación a Usuario Activo de Modelado y Jerárquica El Aprendizaje Por Refuerzo" (2010).

[2] Shahriari et al., "Tomando el Humano Fuera del circuito: Una Revisión de la Bayesiano de Optimización" (2015).

[3] Snoek et al., "Práctica Bayesiano de Optimización de Algoritmos de Aprendizaje automático", NIPS (2012).

[4] Rios y Sahinidis, "Derivado libre de optimización: una revisión de los algoritmos y la comparación de implementaciones de software", Revista de Optimización Global (2013).

Answer 3

No sé los algoritmos de mí mismo, pero creo que el tipo de algoritmo de optimización que usted está buscando es derivado libre de optimización, que se utiliza cuando el objetivo es costoso o ruidoso.

Por ejemplo, echa un vistazo a este documento, cuyo resumen parece indicar que esto es exactamente lo que usted desea:

El documento considera la optimización global de los costosos funciones objetivo, es decir, el problema de encontrar el mínimo global cuando hay varios mínimos locales y cada valor de la función se lleva mucho tiempo de CPU para calcular. Tales problemas suelen surgir en los sectores industriales y aplicaciones financieras, donde un valor de la función podría ser el resultado de un consumo de tiempo de simulación por ordenador o de optimización. Los derivados son más a menudo difícil de obtener, y los algoritmos presentados sin el uso de dicha información.

Answer 4

Las dos simples estrategias que he utilizado con éxito en el pasado son:

1. Si es posible, trate de encontrar un simple sustituto de la función de la aproximación de su costo total de la función de evaluación-típico de un modelo analítico sustitución de una simulación. Optimizar esta simple función. A continuación, validar y afinar la solución resultante con su exacta de la función de costo.
2. Si es posible, trate de encontrar una manera de evaluar una exacta "delta-costo" de la función -- exacto como opuesto a ser una aproximación del uso del gradiente. Que es, desde un inicial de 15-dimensional punto para el que tiene el costo total evaluado, encontrar una manera de derivar cómo el costo sería de cambio por lo que un pequeño cambio en uno (o varios) de los 15 componentes de su punto actual. Usted necesita para explotar las propiedades de localización de una pequeña perturbación en su caso en su caso en particular y es muy probable que necesite definir, la memoria caché y la actualización de un interno del estado de la variable a lo largo del camino.

Dichas estrategias son muy específica para cada caso, no sé si pueden ser aplicables en su caso o no, lo siento si no lo son. Ambos podrían ser aplicables (como fue en mi casos de uso): aplicar el "delta-costo" estrategia para un simple modelo analítico -- puede mejorar el rendimiento en varios órdenes de magnitud.

Otra estrategia sería utilizar un segundo método de orden que normalmente se tiende a reducir el número de iteraciones (pero cada iteración es más complejo) -- por ejemplo, el de Levenberg–Marquardt algoritmo. Pero teniendo en cuenta que no parecen tener una forma directa y evaluar de manera eficiente el gradiente, esto probablemente no es una opción viable en este caso.