¿Cuál es la diferencia entre la optimización bayesiana (procesos gaussianos) y el recocido simulado en la práctica

8

Parece que ambos procesos se usan para estimar el valor máximo de una función desconocida, y ambos obviamente tienen diferentes formas de hacerlo.

Pero en la práctica, ¿cualquier método es esencialmente intercambiable? ¿Dónde me gustaría usar uno sobre el otro?

https://en.wikipedia.org/wiki/Simulated_annealing

http://www.iro.umontreal.ca/~bengioy/cifar/NCAP2014-summerschool/slides/Ryan_adams_140814_bayesopt_ncap.pdf

Pregunta similar ¿
Optimización bayesiana o pendiente de gradiente?

cañón289
fuente
No creo que esto sea lo suficientemente exhaustivo como para ser una respuesta, pero el recocido simulado generalmente requiere una mayor cantidad de evaluaciones de funciones para encontrar un punto cercano al óptimo global. Por otro lado, la optimización bayesiana está construyendo un modelo en cada iteración, pero requiere relativamente pocas evaluaciones de funciones. Entonces, dependiendo de lo costosa que sea evaluar la función, preferiría uno a otro porque uno tendrá un tiempo de pared más pequeño: optimización bayesiana en casos en que la función es muy costosa y recocida cuando la función es relativamente barata.
Sycorax dice Reinstate Monica
@Sycorax Bumping 10 publicaciones sobre más o menos el mismo tema en 10 minutos: un poco excesivo, ¿no te parece? Aparentemente no, pero yo sí.
Mark L. Stone el
@ MarkL.Stone Es más o menos "tiempo lento" (8 p. M. Un viernes, en el momento de las ediciones), que es el momento preferido para hacer esto. Hay un hilo meta.
Sycorax dice Reinstate Monica el

Respuestas:

8

El recocido simulado (SA) es un algoritmo muy simple en comparación con la optimización bayesiana (BO). Ninguno de los métodos supone la convexidad de la función de costo y ninguno de los dos métodos depende en gran medida de la información del gradiente.

SA es, en cierto modo, una caminata aleatoria ligeramente educada. La solución candidata salta sobre el espacio de la solución que tiene un horario de salto particular (el parámetro de enfriamiento). No te importa dónde aterrizaste antes, no sabes dónde aterrizarás después. Es un enfoque típico de la cadena de Markov. No modela suposiciones fuertes sobre la superficie de la solución subyacente. La optimización de MCMC ha recorrido un largo camino desde SA (véase, por ejemplo, Hamiltoniano Monte Carlo ), pero no nos expandiremos más. Una de las cuestiones clave con SA es que necesita evaluar muchas veces "rápido". Y tiene sentido, necesita tantas muestras como sea posible para explorar tantos estados (es decir, soluciones candidatas) como sea posible. Utiliza solo un poquito de información de gradiente (que casi siempre acepta soluciones "mejores").

Mira ahora a BO. BO (o la regresión simplista del Proceso Gaussiano (GP) sobre sus evaluaciones de función de costo) intenta hacer exactamente lo contrario en términos de evaluación de función. Intenta minimizar el número de evaluaciones que realiza. Construye un modelo no paramétrico particular (generalmente un GP) para su función de costo que a menudo supone ruido. No utiliza información de gradiente en absoluto. BO le permite crear un modelo informativo de su función de costos con un pequeño número de evaluaciones de funciones. Luego "consulta" esta función ajustada para sus extremos. De nuevo el diablo está en los detalles; necesita muestrear inteligentemente (y asumir que su anterior también es medio razonable). Hay trabajo sobre dónde evaluar su función a continuación, especialmente cuando sabe que su función realmente evoluciona ligeramente con el tiempo (por ejemplo, aquí ).

Una ventaja obvia de SA sobre BO es que dentro de SA es muy sencillo poner restricciones en el espacio de su solución. Por ejemplo, si desea soluciones no negativas, simplemente limite su distribución de muestra en soluciones no negativas. Lo mismo no es tan directo en BO porque incluso si evalúa sus funciones de acuerdo con sus restricciones (por ejemplo, no negatividad), también necesitará restringir su proceso; Esta tarea, aunque no imposible, es más complicada.

En general, uno preferiría SA en casos en que la función de costo es barata de evaluar y BO en casos en que la función de costo es costosa de evaluar. Creo que SA está cayendo lenta pero constantemente en desgracia; especialmente el trabajo de optimización sin gradiente (por ejemplo , NEWQUA , BOBYQA ) elimina una de sus principales ventajas en comparación con los métodos de descenso de gradiente estándar que no tiene que evaluar una derivada. Del mismo modo, el trabajo sobre MCMC adaptativo (p. Ej., Ver referencia anterior) lo convierte en un desperdicio en términos de optimización de MCMC para casi todos los casos.

usεr11852
fuente
Gracias por la respuesta. Veo que probablemente tengas razón sobre el recocido que cae en desgracia. scipy lo desaprobó a favor de basinhopping docs.scipy.org/doc/scipy-0.15.1/reference/generated/…
canyon289
Me alegro de poder ayudar. Gracias por el consejo; No estaba al tanto de ese cambio en SciPy.
usεr11852
A menos que las restricciones sean realmente retorcidas, ¿cuál es el problema con restringir un ajuste GP? Por supuesto, cuando "consulta" la función ajustada, realiza una optimización restringida. No estoy tratando de ser sarcástico, realmente quiero saber qué dificultades ves. Por ejemplo, las restricciones lineales de igualdad y desigualdad deberían ser pan comido. Si tiene restricciones no convexas, como las restricciones de igualdad no lineales o las restricciones de enteros, esas podrían caer en mi categoría retorcida.
Mark L. Stone el
@ MarkL.Stone: Incluso las restricciones lineales (y mucho menos las retorcidas ) pueden afectar severamente el ajuste en las dimensiones superiores, incluso si se ajusta a " algo ", dudaría seriamente de que este ajuste sea una representación precisa de lo que desea. Además, la mayoría de los resultados basados ​​en la continuidad detrás de la optimización de GPR salen de la ventana ... Para ser claros: no he usado BO ampliamente porque siempre resultó ser subóptimo para los problemas con los que trabajo. Suponiendo que el método estándar Cuasi-Newton falla, siempre recomendaría primero un enfoque sin derivados o un enfoque HMC.
usεr11852
Bueno, si tengo restricciones, lo que quiero es que la función ajustada satisfaga las restricciones. Créeme, tengo mis dudas sobre qué tan bien un ajuste GP será una representación precisa de lo que quiero, restricciones o no. Las buenas restricciones pueden ayudarlo: limitan las cosas a donde deberían estar y le evitan perder el tiempo en regiones malas. Por supuesto, eso es si están bien implementados. ¿Puede dar un ejemplo de un resultado basado en la continuidad detrás de la optimización de GPR que sale por la ventana cuando hay restricciones lineales? Para ser un ejemplo válido, mejor haber estado en la ventana sin restricciones.
Mark L. Stone