Descida em gradiente em lote versus descida em gradiente estocástico

101

Suponha que tenhamos algum conjunto de treinamento para . Suponha também que executemos algum tipo de algoritmo de aprendizado supervisionado no conjunto de treinamento. As hipóteses são representadas como . Precisamos encontrar os parâmetros que minimizem a "distância" entre e . Seja(x(i),y(i))i=1,,mhθ(x(i))=θ0+θ1x(i)1++θnx(i)nθy(i)hθ(x(i))

J(θ)=12i=1m(y(i)hθ(x(i))2

Então queremos encontrar que minimize . Na descida gradiente, inicializamos cada parâmetro e executamos a seguinte atualização:θJ(θ)

θj:=θjαθjJ(θ)

Qual é a principal diferença entre a descida do gradiente em lote e a descida do gradiente estocástico?

Ambos usam a regra de atualização acima. Mas um é melhor que o outro?

user20616
fonte

Respostas:

121

A aplicabilidade da descida em lote ou gradiente estocástico realmente depende do coletor de erros esperado.

A descida do gradiente em lote calcula o gradiente usando o conjunto de dados inteiro. Isso é ótimo para coletores de erros convexos ou relativamente suaves. Nesse caso, avançamos um pouco diretamente em direção a uma solução ótima, local ou global. Além disso, a descida do gradiente em lote, dada uma taxa de aprendizado recozido, encontrará o mínimo localizado em sua bacia de atração.

A descida do gradiente estocástico (SGD) calcula o gradiente usando uma única amostra. A maioria das aplicações do SGD realmente usa um minibatch de várias amostras, por razões que serão explicadas um pouco mais tarde. O SGD funciona bem (suponho que não seja bom, mas melhor que a descida do gradiente em lote) para manifolds de erro que possuem muitos máximos / mínimos locais. Nesse caso, o gradiente um tanto mais ruidoso calculado usando o número reduzido de amostras tende a empurrar o modelo dos mínimos locais para uma região que, esperamos, seja mais ideal. Amostras únicas são realmente barulhentas, enquanto minibatches tendem a calcular um pouco a média do ruído emitido. Assim, a quantidade de empurrão é reduzida ao usar minibatches. Um bom equilíbrio é alcançado quando o tamanho do minibatch é pequeno o suficiente para evitar alguns dos mínimos locais pobres, mas grande o suficiente para que não t evitar os mínimos globais ou mínimos locais com melhor desempenho. (Incidentalmente, isso pressupõe que os melhores mínimos possuam uma bacia de atração maior e mais profunda e, portanto, são mais fáceis de cair.)

Um benefício do SGD é que ele é computacionalmente muito mais rápido. Geralmente, grandes conjuntos de dados não podem ser mantidos na RAM, o que torna a vetorização muito menos eficiente. Em vez disso, cada amostra ou lote de amostras deve ser carregado, trabalhado, com os resultados armazenados e assim por diante. O Minibatch SGD, por outro lado, geralmente é intencionalmente pequeno o suficiente para ser computacionalmente tratável.

Geralmente, essa vantagem computacional é aproveitada pela realização de muito mais iterações do SGD, executando muito mais etapas do que a descida do gradiente em lote convencional. Isso geralmente resulta em um modelo muito próximo ao encontrado por descida em gradiente de lote ou melhor.

A maneira como gosto de pensar em como o SGD funciona é imaginar que tenho um ponto que representa minha distribuição de entrada. Meu modelo está tentando aprender essa distribuição de entrada. Ao redor da distribuição de entrada há uma área sombreada que representa as distribuições de entrada de todos os minibatches possíveis que eu poderia provar. Geralmente, é uma suposição razoável de que as distribuições de entrada de minibatch estão próximas da verdadeira distribuição de entrada. A descida do gradiente de lote, em todas as etapas, segue a rota mais íngreme para alcançar a verdadeira distribuição de entrada. O SGD, por outro lado, escolhe um ponto aleatório dentro da área sombreada e segue a rota mais íngreme em direção a esse ponto. Em cada iteração, porém, ele escolhe um novo ponto. A média de todas essas etapas aproximará a verdadeira distribuição de entrada, geralmente muito bem.

Jason_L_Bens
fonte
13
Na prática, ninguém usa descida de gradiente em lote. É simplesmente muito caro computacionalmente para um ganho não muito grande. (O ganho é que você está realmente diminuindo o gradiente "verdadeiro".) Quando você tem uma função de perda altamente não convexa, basta seguir na maioria das vezes na direção certa e, eventualmente, convergir para um mínimo local. Assim, minibatch SGD.
sabalaba
@Jason_L_Bens você tem alguma referência (documentos ou textos on-line) onde posso ler mais sobre esses algoritmos?
precisa saber é o seguinte
1
@ user110320 Não estou de cabeça para baixo, não, embora sejam algoritmos muito comuns e, portanto, deve haver uma tonelada de recursos disponíveis no tópico com um pouco de pesquisa. Se você estiver procurando uma abordagem geral, recomendo a leitura de algumas das arquiteturas profundas de aprendizagem da IA ​​Yoshua Bengio. É onde eu comecei.
Jason_L_Bens
6

Como outra resposta sugere, o principal motivo para usar o SGD é reduzir o custo de computação do gradiente, mantendo a direção do gradiente em grande parte, quando a média é calculada sobre muitos mini lotes ou amostras - o que certamente ajuda a levá-lo aos mínimos locais.

  1. Por que o minibatch funciona .

A matemática por trás disso é que, o gradiente "verdadeiro" da função de custo (o gradiente para o erro de generalização ou para amostras infinitamente grandes configuradas) é a expectativa do gradiente sobre os dados verdadeiros que geram a distribuição ; o gradiente real calculado sobre um lote de amostras é sempre uma aproximação ao gradiente real com a distribuição empírica de dados . pdatap^data

g=Epdata(J(θ)θ)
A descida do gradiente em lote pode fornecer o possível gradiente "ideal", considerando todas as amostras de dados, embora não seja o gradiente "verdadeiro". Um lote menor (minibatch) provavelmente não é tão ideal quanto o lote inteiro, mas ambas são aproximações - o mesmo ocorre com o minibatch de amostra única (SGD). A diferença entre os erros padrão deles é inversamente proporcional aos tamanhos do minibatch. Ou seja,
SE(g^(n))SE(g^(m))=mn
Ou seja, a redução do erro padrão é a raiz quadrada do aumento do tamanho da amostra. A equação acima é para os gradientes calculados em uma etapa da descida do gradiente de minibatch. Ao iterar as etapas das atualizações de gradiente de minibatch e usar todas as amostras de treinamento finalmente em uma época, você está virtualmente computando a média dos gradientes com base em todas as amostras fornecidas. Ou seja, para minibatch tamanho , A partir das equações acima, podemos concluir que, em uma época, seus gradientes médios com diferentes tamanhos de minibatchm
Ep^data(g^(m))=Ep^data(J(θ)θ)
m (de um para o lote completo) têm o mesmo erro padrão e, mais importante, todas são aproximações fiéis ao gradiente "verdadeiro", ou seja, movendo-se para a direção correta do gradiente "verdadeiro".
  1. Por que o minibatch pode funcionar melhor .

Em primeiro lugar, o minibatch faz com que alguns problemas de aprendizado sejam tecnicamente invencíveis para serem atacáveis ​​devido à demanda reduzida de computação com menor tamanho de lote.

Em segundo lugar, o tamanho reduzido do lote não significa necessariamente precisão reduzida do gradiente. As amostras de treinamento têm muitos ruídos, outliers ou vieses. Um minibatch amostrado aleatoriamente pode refletir a verdadeira distribuição de dados melhor (ou não pior) que o lote completo original. Se algumas iterações das atualizações de gradiente de minibatch fornecerem uma estimativa melhor, em geral o resultado médio de uma época pode ser melhor do que o gradiente calculado a partir de um lote completo.

Em terceiro lugar, o minibatch não apenas ajuda a lidar com amostras de dados desagradáveis, mas também ajuda a lidar com a função de custo desagradável que possui muitos mínimos locais. Como Jason_L_Bens menciona, algumas vezes os coletores de erro podem ser mais fáceis de capturar um gradiente regular em mínimos locais, enquanto mais difícil de capturar o gradiente temporariamente aleatório calculado com minibatch.

Finalmente, com a descida gradiente, você não está alcançando os mínimos globais em uma única etapa, mas repetindo a variedade de erros. O gradiente em grande parte fornece apenas a direção para iterar. Com o minibatch, você pode iterar muito mais rápido. Em muitos casos, quanto mais iterações, melhor o ponto que você pode alcançar. Você realmente não se importa em todas as condições climáticas, o ponto é ideal globalmente ou mesmo localmente. Você só deseja alcançar um modelo razoável que traga um erro de generalização aceitável. O Minibatch facilita isso.

Você pode achar que o livro "Deep learning", de Ian Goodfellow et al., Tem boas discussões sobre esse tópico, se você o ler com atenção.

Xiao-Feng Li
fonte
Para problemas de otimização convexos, o que você disse está bem. Mas, para usar métodos de gradiente em funções não convexas, você perdeu um motivo muito crítico de que o SGD é melhor que o GD em lote. Veja minha resposta datascience.stackexchange.com/questions/16807/…
horaceT
Obrigado pelo seu comentário. Como o ponto que você mencionou foi descrito por Jason_L_Bens acima com detalhes, não me preocupei em repetir, mas referindo sua resposta no último terceiro parágrafo, com o devido respeito. Para o problema de otimização da descida do gradiente, o não-convexo é refletido pelos mínimos locais, incluindo o ponto de sela (consulte o último terceiro parágrafo); e, para fins de descrição, minha resposta descreve o SGD como minibatch, mas com um tamanho de lote de 1 (consulte o terceiro parágrafo).
Xiao-Feng Li
3

Para mim, o gradiente em lote se assemelha ao gradiente lean. No gradiente lean, o tamanho do lote é escolhido para que todos os parâmetros que devem ser atualizados também variem independentemente, mas não necessariamente ortogonalmente, no lote. Por exemplo, se o lote contiver 10 experiências, 10 linhas, é possível formar colunas independentes. 10 linhas permitem a atualização independente, mas não ortogonal, de 512 parâmetros.2101=512

Sven Ahlinder
fonte