Estoy familiarizado con el algoritmo de descenso de gradiente que puede encontrar el mínimo local (máximo) de una función determinada.
¿Hay alguna modificación del descenso de gradiente que permita encontrar el mínimo absoluto (máximo), donde la función tiene varios extremos locales?
¿Existen técnicas generales, cómo mejorar un algoritmo que puede encontrar el extremo local, para encontrar el extremo absoluto?
Respuestas:
Supongo que estás hablando de minimización sin restricciones. Su pregunta debe especificar si está considerando una estructura de problema específica. De lo contrario, la respuesta es no.
Primero debería disipar un mito. Ni siquiera se garantiza que el método clásico de descenso de gradiente (también llamado método de descenso más pronunciado ) encuentre un minimizador local. Se detiene cuando ha encontrado un punto crítico de primer orden, es decir, uno donde el gradiente se desvanece. Dependiendo de la función particular que se minimiza y del punto de partida, ¡puede terminar en un punto de apoyo o incluso en un maximizador global!
Ahora, prácticamente todos los métodos de optimización basados en gradientes sufren de esto por diseño. Su pregunta es realmente sobre la optimización global . Una vez más, la respuesta es no, no hay recetas generales para modificar un método a fin de garantizar que se identifique un minimizador global. Simplemente pregúntese: si el algoritmo devuelve un valor y dice que es un minimizador global, ¿cómo comprobaría que es cierto?
Hay clases de métodos en la optimización global. Algunos introducen la aleatorización. Algunos usan estrategias de inicio múltiple. Algunos explotan la estructura del problema, pero esos son para casos especiales. Elija un libro sobre optimización global. Lo disfrutarás.
fuente
Probablemente no haya una respuesta única para su pregunta. Pero es posible que desee analizar algoritmos de recocido simulados u otros enfoques que se basan en los métodos de Monte Carlo de cadena de Markov (MCMC). Estos también se pueden combinar con métodos locales como el descenso de gradiente.
fuente
Hay muchas referencias sobre la "optimización global de las redes neuronales". Las técnicas son similares al recocido simulado [ver otra respuesta]. La idea básica es reiniciar el descenso de gradiente de red comenzando en muchos puntos de inicio de peso diferentes, muestreados aleatoriamente o sistemáticamente. cada resultado del descenso del gradiente es como una "muestra". cuantas más muestras se toman, mayor es la probabilidad de que una de las muestras sea el óptimo global, especialmente si la función objetivo se "comporta bien" en el sentido de continua, diferenciable, etc.
referencias en línea
[1] Optimización global de los pesos de las redes neuronales por Hamm et al.
[2] Un enfoque de optimización global para el entrenamiento de redes neuronales Voglis / Lagaris
[3] Calibración de redes neuronales artificiales mediante Pinter de optimización global
[4] Optimización global de redes neuronales utilizando un enfoque híbrido determinista Beliakov
[5] Optimización global para el entrenamiento de redes neuronales Shang / Wah
fuente
En general, es computacionalmente difícil optimizar funciones no convexas multivariadas. La dureza viene en diferentes sabores (criptográfico, NP-duro). Una forma de ver esto es que los modelos de mezcla (como la mezcla de guasianos o HMM) son difíciles de aprender, pero serían fáciles (*) si fuera posible maximizar la probabilidad de manera eficiente. Para obtener resultados sobre la dureza del aprendizaje de HMM, consulte http://alex.smola.org/journalclub/AbeWar92.pdf http://link.springer.com/chapter/10.1007%2F3-540-45678-3_36 http: // www.math.ru.nl/~terwijn/publications/icgiFinal.pdf
(*) modulo las condiciones usuales de no degeneración e identificabilidad
fuente
Debo estar en desacuerdo con Dominique. Hajek demostró a mediados de la década de 1980 que el recocido de un problema no convexo bajo ciertas condiciones estrictas está garantizado para alcanzar el mínimo global: http://dx.doi.org/10.1287/moor.13.2.311
fuente