Supongamos que mi función de costes es tal que su pendiente sube desde el punto A en z=2 hasta el B en z=4; se mantiene constante hasta el C en z=4; baja hasta el D en z=1; sube hasta el E en z=5.
Si elijo mi punto de partida entre el punto B y el C, la diferencial de la función de coste será 0 (porque la pendiente es 0). Por lo tanto, theta nunca cambiará su valor.
¿Cómo, entonces, mi función alcanzará el mínimo en D?
No lo hará -- el descenso por gradiente sólo encuentra un mínimo local*, y esa "meseta" es uno.
Sin embargo, hay varias formas de modificar el descenso de gradiente para evitar problemas como éste. Una opción es volver a ejecutar el algoritmo de descenso varias veces, utilizando diferentes lugares de inicio para cada ejecución. Las ejecuciones iniciadas entre B y C convergerán a z=4. Las ejecuciones iniciadas entre D y E convergerán a z=1. Como eso es más pequeño, decidirás que D es el (mejor) mínimo local y elegirás ese valor.
Como alternativa, puede añadir un término de impulso . Imagínese una pesada bala de cañón rodando por una colina. Su impulso hace que continúe a través de pequeños desniveles en la colina hasta que se asienta en la parte inferior. Teniendo en cuenta el gradiente en este paso de tiempo Y los anteriores, puede ser capaz de saltar los mínimos locales (más pequeños).
* Aunque es casi universalmente descrito como un buscador de mínimos locales, Neil G señala que el descenso de gradiente en realidad encuentra regiones de curvatura cero. Dado que éstas se encuentran moviéndose hacia abajo lo más rápidamente posible, se trata (con suerte) de mínimos locales, aunque puede establecerse en cualquier lugar donde la superficie de error sea plana, como en tu ejemplo.
Respuesta sencilla: no lo hará.
El descenso de la pendiente sube por una colina. Si llega a una meseta, considera que el algoritmo ha convergido y no se mueve más.
Si crees que esto es un fallo del descenso de gradiente, debes saber que los problemas multimodales son muy difíciles y fuera de una búsqueda de cuadrícula fina (que puede ser fácilmente prohibitivamente costosa desde el punto de vista computacional y requiere que se señale una región donde debe estar la solución), no hay ningún algoritmo genérico real para los problemas multimodales.
Un método simple para manejar esto es reiniciar su algoritmo de escalada (lo siento, estoy acostumbrado a la terminología de maximización, en lugar de la minimización) varias veces desde puntos de partida al azar y utilizar la mejor solución que se obtiene. Si el problema es uni-modal, todas las soluciones deberían estar relativamente cerca. Si el problema es multimodal, es de esperar que uno de tus puntos de partida aleatorios esté en la colina correcta.
Sólo hay una cosa que debes saber sobre el descenso de gradiente. Es una basura total y absoluta, y un algoritmo absolutamente horrible que ni siquiera debería considerarse a menos que haya al menos cientos de millones de variables, en cuyo caso no esperes que funcione bien, excepto cuando se resuelve el mismo problema una y otra vez, para el que se han encontrado buenos valores de tasas de aprendizaje. es una versión pobre y no protegida del descenso más pronunciado, que incluso en forma protegida es malo. Estarás mucho mejor con una región de confianza o un método Quasi-Newton de búsqueda de líneas. No escribas el tuyo propio.
El descenso gradual es un término erróneo. Puede que ni siquiera descienda. Los algoritmos seguros, que utilizan regiones de confianza o búsquedas de líneas, descienden o terminan si no pueden descender. Los algoritmos determinan de forma adaptativa los "ritmos de aprendizaje" en función de lo que encuentran, no se sobrepasan como el descenso por gradiente y pueden acelerar automáticamente cuando se justifica. El descenso gradual ni siquiera era un buen algoritmo hace un siglo.
Una región de pendiente cero prolongada podría causar problemas a cualquier algoritmo de optimización, a menos que se trate de un algoritmo de optimización global riguroso. Los algoritmos de optimización global rigurosos, por ejemplo basados en branch and bound, existen (no me refiero a los algoritmos genéticos y otras porquerías heurísticas, que son el equivalente moral del descenso de gradiente), pero puede que no consigan resolver un problema si es demasiado grande o demasiado difícil, y puede que no acepten todas las funciones. Su algoritmo de optimización local debe comprobar las condiciones óptimas de segundo orden, si es posible. Eso distinguirá un mínimo local de un máximo local o un punto de equilibrio.
Como se ha dicho en otras respuestas, es una buena idea ejecutar un algoritmo de optimización local con varios valores iniciales diferentes. Pero ese algoritmo generalmente no debe ser de descenso de gradiente.
En mi opinión, Andrew Ng ha hecho un gran daño a la gente al enseñarles el descenso por gradiente. La gente cree que sabe cómo optimizar, cuando no sabe más sobre cómo optimizar u optimización que lo que sabe sobre conducir un niño de 3 años que "conduce" con un volante de placebo un coche de plástico pegado a la parte delantera de un carrito de supermercado. (Y para el beneficio de cierto comentarista que afirmó que mi proporcionar una formulación explícita de su (su) problema como un problema de optimización restringida, dijo que yo sólo había repetido su (su) problema, y que la imposición de restricciones después del hecho no era una buena manera de resolver un problema de optimización, y luego se negó a cambiar su (su) punto de vista después de que expliqué cómo funciona la optimización restringida, que no es la imposición de restricciones "después del hecho", y que hay una teoría muy bien desarrollada para la optimización restringida y un software práctico listo para usar para resolver problemas de optimización restringida, entonces él (ella) votó a la baja esa respuesta muy detallada, reflexiva y amistosa, y escribió que ambos podemos estar de acuerdo en que no respondí a su pregunta) hay un software práctico listo para usar para resolver problemas de optimización restringida, que aparentemente muchas personas que "aprendieron" la optimización de Andrew Ng et al no tienen ni idea de que existe. Y los no especialistas no van a hacer un buen trabajo escribiendo su propio software de optimización restringida (o software de optimización no restringida tampoco). Andrew Ng hace un flaco favor a la gente haciéndoles creer que pueden hacerlo. Tampoco hay necesidad de hacerlo, ya que existe un buen software de optimización, aunque R está plagado de software de optimización no tan bueno. Es poco probable que alguien que no sea un experto en optimización numérica y análisis numérico pueda mejorar un buen software ya disponible para aprovechar la estructura especial del problema, por ejemplo.
(1) Muchos educadores y libros de texto describen el descenso por gradiente, así que ¿por qué arrastrar a Andrew Ng? Si él es sólo un ejemplo, debido a la popularidad de su curso, por favor, aclárelo. (2) Comprendo que la hipérbole forma parte del estilo polémico que has decidido adoptar aquí, pero las comillas de miedo en "docto" son un poco insultantes - en todos los campos hay una tendencia a algunos que las personas que acaban de aprender los fundamentos de un método sobrevaloren su competencia en el mismo, lo que considero que es su punto de vista.
Sí, Andrew Ng es sólo un ejemplo, pero uno muy destacado. Mi mención a la gente que ni siquiera sabe que existe el software y los algoritmos restringidos no es en abstracto: hay ejemplos en este foro. si Andrew Ng fuera médico, su enseñanza me parecería constitutiva de mala praxis.
Mark, te agradezco profundamente la experiencia y los conocimientos que has puesto en este post y en otros similares que has aportado aquí. La gente reacciona no sólo a lo que dices, sino también a cómo lo dices. Un poco de entusiasmo está muy bien, pero cuando se desvía hacia argumentos que parecen ad hominem que puede restarle importancia a su mensaje. Estoy seguro de que el voto negativo refleja ese aspecto más que los puntos sustanciales que usted está haciendo. ¿Podría persuadirte de que hagas las ediciones (relativamente pequeñas) que serían necesarias para eliminar esas distracciones, de modo que los méritos de tu mensaje puedan ser apreciados más fácilmente?
I-Ciencias es una comunidad de estudiantes y amantes de la ciencia en la que puedes resolver tus problemas y dudas.
Puedes consultar las preguntas de otros usuarios, hacer tus propias preguntas o resolver las de los demás.
