Quando usar descida de gradiente versus Monte Carlo como uma técnica de otimização numérica

11

Quando um conjunto de equações não pode ser resolvido analiticamente, podemos usar um algoritmo de descida de gradiente. Mas parece que também existe o método de simulação de Monte Carlo que pode ser usado para resolver problemas que não possuem soluções analíticas.

Como saber quando usar a descida de gradiente e quando usar Monte Carlo? Ou estou simplesmente confundindo o termo 'simulação' com 'otimização'?

Muito obrigado!

monte-carlo gradient-descent Vencedor
fonte

Respostas:

4

Essas técnicas fazem coisas diferentes.

A descida de gradiente é uma técnica de otimização, portanto é comum em qualquer método estatístico que exija maximização (MLE, MAP).

A simulação de Monte Carlo é para calcular integrais por amostragem de uma distribuição e avaliação de alguma função nas amostras. Portanto, é comumente usado com técnicas que exigem o cálculo de expectativas (inferência bayesiana, teste de hipóteses bayesiana).

jlimahaverford
fonte
Então a descida do gradiente está conectada à diferenciação (máximos, mínimos) e o monte carlo está associado à integração?
Victor Victor
O gradiente é uma (uma de muitas) generalizações da derivada. Portanto, a descida do gradiente está ligada à diferenciação. Mas eu diria: "O Gradient Descent usa derivadas para otimizar" e "Monte Carlo usa amostragem para integrar", se eu tivesse que usar o mínimo de palavras possível.
jlimahaverford 22/09
4

Ambas são grandes famílias de algoritmos, por isso é difícil dar uma resposta precisa, mas ...

A subida de gradiente (ou descida) é útil quando você deseja encontrar um máximo (ou mínimo). Por exemplo, você pode encontrar o modo de uma distribuição de probabilidade ou uma combinação de parâmetros que minimizam alguma função de perda. O "caminho" necessário para encontrar esses extremos pode falar um pouco sobre a forma geral da função, mas não se destina; de fato, quanto melhor funciona, menos você saberá sobre tudo, exceto os extremos.

Os métodos de Monte Carlo são nomeados após o cassino de Monte Carlo, porque eles, como o cassino, dependem de randomização. Pode ser usado de muitas maneiras diferentes, mas a maioria delas se concentra na aproximação de distribuições. Os algoritmos de Markov Chain Monte Carlo, por exemplo, encontram maneiras de amostrar eficientemente a partir de distribuições de probabilidade complicadas. Outras simulações de Monte Carlo podem gerar distribuições sobre possíveis resultados.

Matt Krause
fonte
"Métodos de Monte Carlo" geralmente se referem ao que você faz com as amostras, em oposição aos métodos para obter as amostras. No MCMC, a "Cadeia de Markov" refere-se ao processo de obtenção das amostras.
Jlimahaverford # 22/15
Realmente? Eu sempre pensei que Monte Carlo implica que há algum tipo de randomização acontecendo e não significa muito mais do que isso. Em MCMC, é verdade que Cadeias de Markov estão envolvidos, mas você também está amostragem aleatória das cadeias (daí Monte-Carlo.) /
Matt Krause
Talvez isso seja uma questão de opinião. Se eu estivesse usando o MCMC para aproximar a média de uma distribuição posterior, eu estaria usando passeios aleatórios em uma cadeia de Markov para obter amostras aproximadamente da minha distribuição não normalizada, eu estaria usando a Integração de Monte Carlo para aproximar a média. Considero os métodos de amostragem como ferramentas que permitem os métodos de Monte Carlo. Por exemplo, eu não chamaria de amostragem por rejeição um método de Monte Carlo, mas posso imaginar alguém usando-os juntos.
Jlimahaverford # 23/15
Tudo isso dito, a Wikipedia considera a amostragem por rejeição um método de Monte Carlo. Portanto, é bem possível que minhas idéias aqui estejam completamente erradas.
Jlimahaverford # 23/15
2

Conforme explicado por outros, a descida / ascensão do gradiente realiza otimização, ou seja, encontra o máximo ou o mínimo de uma função. Monte Carlo é um método de simulação estocástica, ou seja, aproxima uma função de distribuição cumulativa por amostragem aleatória repetida. Isso também é chamado de "integração de Monte Carlo" porque o cdf de uma distribuição contínua é realmente uma integral.

O que é comum entre a descida de gradiente e Monte Carlo é que ambos são particularmente úteis em problemas em que não existe uma solução de forma fechada. Você pode usar diferenciação simples para encontrar o ponto máximo ou mínimo de qualquer função convexa sempre que uma solução analítica for viável. Quando essa solução não existe, você precisa usar um método iterativo, como descida de gradiente. É o mesmo para a simulação de Monte Carlo; basicamente você pode usar a integração simples para calcular analiticamente qualquer cdf, mas não há garantia de que uma solução de formulário fechado sempre seja possível. O problema se torna novamente solucionável com a simulação de Monte Carlo.

Você pode usar a descida gradiente para simulação e o Monte Carlo para otimização? A resposta simples é não. Monte Carlo precisa de um elemento estocástico (uma distribuição) para colher amostras e a descida do gradiente não tem como lidar com problemas de informações estocásticas. No entanto, você pode combinar simulação e otimização para produzir algoritmos de otimização estocástica mais poderosos, capazes de resolver problemas muito complexos que a descida simples do gradiente não consegue resolver. Um exemplo disso seria o Simulated Annealing Monte Carlo.

Digio
fonte
1

Esta resposta está parcialmente errada. Você pode realmente combinar métodos de Monte Carlo com descida de gradiente. Você pode usar os métodos de Monte Carlo para estimar o gradiente de uma função de perda, que é usada pela descida do gradiente para atualizar os parâmetros. Um método popular de Monte Carlo para estimar o gradiente é o estimador de gradiente de pontuação , que pode, por exemplo, ser usado no aprendizado por reforço. Veja Estimativa de gradiente de Monte Carlo no aprendizado de máquina (2019) por Shakir Mohamed et al. para mais informações.

nbro
fonte