Como a descida estocástica do gradiente evita o problema de um mínimo local?

19

Eu sei que a descida estocástica do gradiente tem comportamento aleatório, mas não sei por quê.
Existe alguma explicação sobre isso?

SunshineAtNoon
fonte
10
O que sua pergunta tem a ver com o seu título?
Neil G

Respostas:

22

O algoritmo de gradiente estocástico (SG) se comporta como um algoritmo de recozimento simulado (SA), onde a taxa de aprendizado do SG está relacionada à temperatura do SA. A aleatoriedade ou ruído introduzido pela SG permite escapar dos mínimos locais para atingir um mínimo melhor. Obviamente, isso depende da rapidez com que você diminui a taxa de aprendizado. Leia a seção 4.2, de Aprendizagem estocástica por gradiente em redes neurais (pdf) , onde é explicada em mais detalhes.

clara
fonte
4
Não olhe bem para a Seção 4.1, onde o segundo teorema é para um caso limitado de funções não-convexas, dizendo que apenas converge (com infinitas amostras) para algum ponto do gradiente 0. Pode não ser o mínimo global ou até o máximo. . O SGD é mais interessante por razões mais práticas, como a aprendizagem distribuída, não com certeza que "evitará" o mínimo local.
nil
2

Na descida do gradiente estocástico, os parâmetros são estimados para cada observação, em oposição a toda a amostra na descida regular do gradiente (descida do gradiente em lote). É isso que dá muita aleatoriedade. O caminho da descida do gradiente estocástico vagueia por mais lugares e, portanto, é mais provável que "salte" de um mínimo local e encontre um mínimo global (Nota *). No entanto, a descida do gradiente estocástico ainda pode ficar presa no mínimo local.

Nota: É comum manter a taxa de aprendizado constante; nesse caso, a descida do gradiente estocástico não converge; apenas vagueia pelo mesmo ponto. No entanto, se a taxa de aprendizado diminuir ao longo do tempo, digamos, estiver inversamente relacionada ao número de iterações, a descida do gradiente estocástico convergirá.

Akavall
fonte
Não é verdade que a descida estocástica do gradiente não converja realmente e apenas se pergunte em torno de um certo ponto. Esse seria o caso se a taxa de aprendizado fosse mantida constante. No entanto, as taxas de aprendizado tendem a zero porque, dessa maneira, quando o algoritmo está próximo do mínimo de uma função convexa, ele para de oscilar e convergir. A chave da prova de convergência do gradiente estocástico são as condições impostas às séries de taxas de aprendizado. Veja as equações (6) e (27) do artigo original de Robbins e Monro.
Clara
2

Como já foi mencionado nas respostas anteriores, a descida do gradiente estocástico tem uma superfície de erro muito mais ruidosa, pois você está avaliando cada amostra iterativamente. Enquanto você está dando um passo em direção ao mínimo global na descida do gradiente em lote a cada época (passe o conjunto de treinamento), as etapas individuais do gradiente de descida do gradiente estocástico nem sempre devem apontar para o mínimo global, dependendo da amostra avaliada.

Para visualizar isso usando um exemplo bidimensional, aqui estão algumas figuras e desenhos da aula de aprendizado de máquina de Andrew Ng.

Primeira descida do gradiente:

insira a descrição da imagem aqui

Segundo, descida de gradiente estocástico:

insira a descrição da imagem aqui

O círculo vermelho na figura inferior deve ilustrar que a descida do gradiente estocástico "continuará atualizando" em algum lugar na área em torno do mínimo global, se você estiver usando uma taxa de aprendizado constante.

Então, aqui estão algumas dicas práticas se você estiver usando descida de gradiente estocástico:

1) embaralhe o conjunto de treinamento antes de cada época (ou iteração na variante "padrão")

2) use uma taxa de aprendizado adaptável para "recozer" mais perto do mínimo global


fonte
Por que você deseja embaralhar o conjunto de treinamento antes de cada época? O algoritmo do SGD seleciona os exemplos de treinamento aleatoriamente.
Vladislavs Dovgalecs
O embaralhamento é basicamente uma maneira de fazê-lo escolher essas amostras de treinamento aleatoriamente. Em minhas implementações, eu costumo misturar o conjunto de treinamento antes de cada época e depois é só for-loop através do conjunto embaralhado
2
Hm, na wikipedia, o algoritmo SGD é descrito como "sem substituição", no entanto, Bottou o descreve como você fez (Bottou, Léon. "Aprendizado de máquina em larga escala com descida de gradiente estocástico." Anais do COMPSTAT'2010. Physica-Verlag HD, 2010. 177-186.), E acho que aqui tenderia a confiar em Bottou mais do que nesta entrada da Wikipedia.
4
@xeon Confira este artigo , que argumenta que a amostragem sem substituição é melhor. Meu entendimento é que, sem substituição, tende a ser empiricamente superior, mas as análises teóricas não estavam disponíveis até recentemente.
Dougal 03/04
1
@xeon Acabei de ler meus slides em PDF do curso de Andrew Ng, e parece que ele o descreveu como na Wikipedia (a variante "sem substituição") não como Bottou. Fiz upload de uma captura de tela aqui