Estou familiarizado com o algoritmo de descida de gradiente, que pode encontrar o mínimo local (máximo) de uma determinada função.
Existe alguma modificação na descida do gradiente que permita encontrar o mínimo absoluto (máximo), onde a função possui vários extremos locais?
Existem técnicas gerais, como aprimorar um algoritmo que pode encontrar o extremo local, para encontrar o extremo absoluto?
Respostas:
Presumo que você esteja falando de minimização irrestrita. Sua pergunta deve especificar se você está considerando uma estrutura de problemas específica. Caso contrário, a resposta é não.
Primeiro eu deveria dissipar um mito. O método clássico de descida com gradiente (também chamado de método de descida mais íngreme ) nem garante que encontre um minimizador local. Para quando encontra um ponto crítico de primeira ordem, ou seja, onde o gradiente desaparece. Dependendo da função específica que está sendo minimizada e do ponto de partida, você pode muito bem acabar em um ponto de sela ou mesmo em um maximizador global!
Agora praticamente todos os métodos de otimização baseados em gradiente sofrem com isso por design. Sua pergunta é realmente sobre otimização global . Novamente, a resposta é não, não há receitas gerais para modificar um método, a fim de garantir que um minimizador global seja identificado. Apenas pergunte a si mesmo: se o algoritmo retorna um valor e diz que é um minimizador global, como você verificaria se é verdade?
Existem classes de métodos na otimização global. Alguns introduzem a randomização. Alguns usam estratégias multi-start. Alguns exploram a estrutura do problema, mas são para casos especiais. Pegue um livro sobre otimização global. Você vai se divertir.
fonte
Provavelmente, não há uma resposta única para sua pergunta. Mas você pode querer procurar algoritmos de recozimento simulados ou outras abordagens que dependam dos métodos de Monte Carlo da cadeia de Markov (MCMC). Eles também podem ser combinados com métodos locais, como descida de gradiente.
fonte
existem muitas referências sobre "otimização global de redes neurais". as técnicas são semelhantes ao recozimento simulado [ver outra resposta]. a idéia básica é reiniciar a descida do gradiente da rede começando em vários pontos de partida de peso diferentes, amostrados aleatoriamente ou sistematicamente. cada resultado da descida do gradiente é como uma "amostra". quanto mais amostras forem coletadas, maior a probabilidade de uma das amostras ser a ideal global, especialmente se a função de destino for "bem comportada" no sentido de contínuo, diferenciável etc.
refs online
[1] Otimização global de pesos de redes neurais por Hamm et al.
[2] Uma abordagem de otimização global para o treinamento em redes neurais Voglis / Lagaris
[3] Calibração de redes neurais artificiais por Pinter de otimização global
[4] Otimização global de redes neurais usando uma abordagem híbrida determinística Beliakov
[5] Otimização global para treinamento em redes neurais Shang / Wah
fonte
Em geral, é computacionalmente difícil otimizar funções multivariadas não-convexas. A dureza vem em diferentes sabores (criptográfico, NP-hard). Uma maneira de ver isso é que os modelos de mistura (como a mistura de guassianos ou HMMs) são difíceis de aprender, mas seriam fáceis (*) se fosse possível maximizar com eficiência a probabilidade. Para obter resultados sobre a dureza da aprendizagem de HMMs, 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 das condições usuais de não degeneração e identificabilidade
fonte
devo discordar de Dominique. foi demonstrado pelo hajek em meados da década de 1980 que o recozimento de um problema não-convexo sob certas condições estritas é garantido para atingir o mínimo global: http://dx.doi.org/10.1287/moor.13.2.311
fonte