Descida de gradiente estocástica (frequentemente abreviada como SGD) é um método iterativo para otimizar uma função objetivo com propriedades de suavidade adequadas, como diferenciabilidade ou subdiferenciabilidade. Pode ser considerada uma aproximação estocástica da otimização por descida de gradiente, pois substitui o gradiente real, calculado a partir do conjunto de dados inteiro, por uma estimativa dele, calculada a partir de um subconjunto de dados selecionado aleatoriamente. Especialmente em problemas de otimização de alta dimensão, isso reduz a carga computacional muito elevada, alcançando iterações mais rápidas em troca de uma taxa de convergência menor. A ideia básica por trás da aproximação estocástica pode ser rastreada até o algoritmo de Robbins–Monro da década de 1950. Hoje, a descida de gradiente estocástica tornou-se um método de otimização importante em aprendizado de máquina e áreas relacionadas.
Tanto a estimação estatística quanto o aprendizado de máquina consideram o problema de minimizar uma função objetivo que tem a forma de uma soma: Q(w) = (1/n) Σ Q_i(w), onde o parâmetro w que minimiza Q(w) deve ser estimado. Cada função somanda Q_i é tipicamente associada à i-ésima observação no conjunto de dados usado para treinamento. Em estatística clássica, problemas de minimização de somas surgem em mínimos quadrados e na estimação de máxima verossimilhança para observações independentes. A classe geral de estimadores que surgem como minimizadores de somas é chamada de M-estimadores. No entanto, em estatística, há muito tempo é reconhecido que exigir até mesmo a minimização local é restritivo demais para alguns problemas de estimação de máxima verossimilhança. Portanto, teóricos estatísticos contemporâneos frequentemente consideram pontos estacionários da função de verossimilhança, ou zeros de sua derivada, a função de escore, e outras equações de estimação. O problema de minimização de somas também surge na minimização de risco empírico, onde Q_i(w) é o valor da função de perda no i-ésimo exemplo, e Q(w) é o risco empírico.
Quando usado para minimizar a função acima, um método padrão (ou "em lote") de descida de gradiente realizaria as seguintes iterações: w := w - η ∇Q(w) = w - (η/n) Σ ∇Q_i(w). O tamanho do passo é denotado por η, às vezes chamado de taxa de aprendizado em aprendizado de máquina, e ":=" denota a atualização de uma variável no algoritmo. Em muitos casos, as funções somandas têm uma forma simples que permite avaliações baratas da função soma e do gradiente da soma. Por exemplo, em estatística, famílias exponenciais de um parâmetro permitem avaliações econômicas de funções e gradientes. No entanto, em outros casos, avaliar o gradiente da soma pode exigir avaliações caras dos gradientes de todas as funções somandas. Quando o conjunto de treinamento é enorme e não existem fórmulas simples, avaliar as somas de gradientes torna-se muito caro, porque avaliar o gradiente exige avaliar os gradientes de todas as funções somandas. Para economizar no custo computacional a cada iteração, a descida de gradiente estocástica amostra um subconjunto de funções somandas a cada passo. Isso é muito eficaz no caso de problemas de aprendizado de máquina em larga escala.
Método Iterativo
Na descida de gradiente estocástica (ou "on-line"), o gradiente verdadeiro de Q(w) é aproximado por um gradiente em uma única amostra: w := w - η ∇Q_i(w). À medida que o algoritmo percorre o conjunto de treinamento, ele realiza a atualização acima para cada amostra de treinamento. Várias passagens podem ser feitas sobre o conjunto de treinamento até que o algoritmo convirja. Se isso for feito, os dados podem ser embaralhados a cada passagem para prevenir ciclos. Implementações típicas podem usar uma taxa de aprendizado adaptativa para que o algoritmo convirja. Em pseudocódigo, a descida de gradiente estocástica pode ser apresentada da seguinte forma:
- Escolha um vetor de parâmetros inicial w e uma taxa de aprendizado η.
- Repita até a convergência:
- Embaralhe as amostras de treinamento.
- Para cada amostra de treinamento i:
- Calcule o gradiente ∇Q_i(w).
- Atualize os parâmetros: w := w - η ∇Q_i(w).
Um compromisso entre calcular o gradiente verdadeiro e o gradiente em uma única amostra é calcular o gradiente contra mais de uma amostra de treinamento, chamado de "mini-lote", a cada passo. Isso pode ter um desempenho significativamente melhor do que a descida de gradiente estocástica "verdadeira" descrita, porque o código pode usar bibliotecas de vetorização em vez de calcular cada passo separadamente, como foi demonstrado pela primeira vez em um artigo de 1986, onde foi chamado de "algoritmo de retropropagação em modo de lote". Também pode resultar em convergência mais suave, pois o gradiente calculado a cada passo é calculado em média sobre mais amostras de treinamento.
A convergência da descida de gradiente estocástica foi analisada usando as teorias de minimização convexa e de aproximação estocástica. Resumidamente, quando as taxas de aprendizado η diminuem a uma taxa apropriada e, sujeito a suposições relativamente brandas, a descida de gradiente estocástica converge quase certamente para um mínimo global quando a função objetivo é convexa ou pseudoconvexa, e, caso contrário, converge quase certamente para um mínimo local. Isso é, na verdade, uma consequência do teorema de Robbins–Siegmund.
Regressão Linear
Suponha que queremos ajustar uma linha reta y = w^T x a um conjunto de exemplos de treinamento (x_i, y_i). A função objetivo é o erro quadrático médio: Q(w) = (1/n) Σ (y_i - w^T x_i)^2. O gradiente para um único exemplo é ∇Q_i(w) = -2 (y_i - w^T x_i) x_i. Na descida de gradiente estocástica, a regra de atualização torna-se w := w + 2η (y_i - w^T x_i) x_i. Isso é equivalente ao algoritmo de mínimos quadrados médios (LMS), também conhecido como regra de Widrow-Hoff, introduzido por Bernard Widrow e Ted Hoff em 1960. O algoritmo LMS é um exemplo clássico de aproximação estocástica e tem sido amplamente usado em processamento adaptativo de sinais.
Aplicações em Aprendizado de Máquina
O gradiente descendente estocástico é o algoritmo de otimização central para o treinamento de redes neurais, incluindo modelos de aprendizado profundo. No aprendizado profundo moderno, o SGD e suas variantes são usados para minimizar funções de perda, como entropia cruzada para classificação ou erro quadrático médio para regressão. A eficiência do algoritmo no manuseio de grandes conjuntos de dados o torna essencial para treinar modelos em corpora massivos, como os usados em modelos de linguagem de grande escala. Por exemplo, o treinamento de modelos baseados em transformadores, conforme introduzido no artigo de 2017 "Attention Is All You Need" por Jakob Uszkoreit, Lukasz Kaiser e outros, depende do SGD ou de suas variantes adaptativas, como o otimizador Adam.
O SGD também é usado em outras áreas da inteligência artificial, incluindo visão computacional, processamento de linguagem natural e aprendizado por reforço. No aprendizado por reforço, o SGD é usado para atualizar parâmetros de política e função de valor, como em métodos de gradiente de política. A natureza estocástica do algoritmo permite que ele escape de mínimos locais em problemas de otimização não convexa, o que é particularmente importante para treinar redes profundas com paisagens de perda complexas.
Variantes e Melhorias
Várias variantes do gradiente descendente estocástico foram desenvolvidas para melhorar a convergência e a estabilidade. Uma melhoria comum é o uso de momentum, que acumula um vetor de velocidade para acelerar gradientes em direções consistentes e amortecer oscilações. Outra é o gradiente acelerado de Nesterov, que calcula o gradiente em uma posição de antecipação. Métodos de taxa de aprendizado adaptativa, como o otimizador Adam, ajustam a taxa de aprendizado por parâmetro com base em estimativas dos primeiros e segundos momentos dos gradientes. Esses métodos são amplamente usados na prática e são frequentemente considerados otimizadores padrão para treinar redes neurais.
Outras técnicas relacionadas incluem agendamentos de taxa de aprendizado, que ajustam a taxa de aprendizado ao longo do tempo, e recorte de gradiente, que previne gradientes explosivos ao reduzir a escala de gradientes grandes. Normalização em lote e normalização de camada são frequentemente usadas em conjunto com o SGD para estabilizar o treinamento e permitir taxas de aprendizado mais altas. Além disso, estratégias de inicialização de pesos, como a inicialização de Xavier ou He, são cruciais para um treinamento eficaz com SGD.
Desafios e Considerações
Um dos principais desafios no gradiente descendente estocástico é a seleção da taxa de aprendizado. Se a taxa de aprendizado for muito alta, o algoritmo pode divergir; se muito baixa, a convergência pode ser lenta. Na prática, agendamentos de taxa de aprendizado ou métodos adaptativos são usados para mitigar esse problema. Outro desafio é o ruído introduzido pelo uso de um subconjunto de dados, que pode causar flutuações na perda. No entanto, esse ruído também pode ser benéfico, pois pode ajudar o algoritmo a escapar de mínimos acentuados e encontrar mínimos mais planos que generalizam melhor.
O SGD é sensível à escala das características, então a normalização de características é frequentemente recomendada. A escolha do tamanho do mini-lote também afeta o desempenho: lotes menores introduzem mais ruído, mas exigem menos memória, enquanto lotes maiores fornecem gradientes mais suaves, mas podem levar a uma pior generalização. No treinamento distribuído, o SGD pode ser paralelizado usando técnicas como atualizações síncronas ou assíncronas, conforme implementado em estruturas como TensorFlow e PyTorch.
Contexto Histórico
As raízes do gradiente descendente estocástico remontam ao algoritmo de Robbins–Monro, desenvolvido por Herbert Robbins e Sutton Monro em 1951, que introduziu a ideia de aproximação estocástica para encontrar raízes. Na década de 1960, o algoritmo LMS de Bernard Widrow e Ted Hoff aplicou princípios semelhantes à filtragem adaptativa. A conexão com o treinamento de redes neurais foi estabelecida na década de 1980 com a popularização da retropropagação. Em 1986, David Rumelhart, Geoffrey Hinton e Ronald Williams publicaram um artigo que demonstrou a eficácia da retropropagação com SGD para aprender representações internas. Desde então, o SGD se tornou uma pedra angular do aprendizado de máquina, permitindo avanços em áreas como reconhecimento de imagem, reconhecimento de fala e processamento de linguagem natural.
Na década de 2010, o aumento do aprendizado profundo e a disponibilidade de grandes conjuntos de dados e hardware poderoso, como GPUs da NVIDIA e AMD, aceleraram a adoção do SGD. Instituições de pesquisa como Stanford AI Lab, BAIR (Berkeley AI Research) e University of Toronto contribuíram para avanços teóricos e práticos. Hoje, o SGD permanece uma área ativa de pesquisa, com trabalho contínuo sobre a compreensão de suas propriedades de generalização e o desenvolvimento de novas variantes.