AdaGrad (abreviação de Adaptive Gradient) é um algoritmo de otimização usado em aprendizado de máquina e aprendizado profundo que adapta a taxa de aprendizado para cada parâmetro individualmente. Ao contrário da descida de gradiente estocástica padrão, que aplica uma única taxa de aprendizado a todos os parâmetros, o AdaGrad escala a atualização de cada parâmetro com base nos gradientes quadrados históricos desse parâmetro. Essa adaptação por parâmetro permite que o algoritmo faça atualizações maiores para parâmetros infrequentes e atualizações menores para os frequentes, o que é particularmente útil em configurações de dados esparsos. O AdaGrad foi introduzido por John Duchi, Elad Hazan e Yoram Singer em 2011 e se tornou um método fundamental no desenvolvimento de otimizadores adaptativos posteriores, como RMSProp e Adam.
A ideia central do AdaGrad é manter uma soma acumulada dos quadrados dos gradientes passados para cada parâmetro. A cada iteração, a taxa de aprendizado para um parâmetro é dividida pela raiz quadrada dessa soma acumulada. Isso significa que parâmetros com grandes gradientes históricos recebem taxas de aprendizado efetivas menores, enquanto parâmetros com gradientes pequenos ou infrequentes recebem taxas de aprendizado efetivas maiores. O acúmulo de gradientes quadrados é monotonicamente crescente, o que faz com que a taxa de aprendizado efetiva decaia ao longo do tempo. Essa propriedade pode ser benéfica para a convergência em configurações convexas, mas também pode levar a um decaimento excessivamente agressivo em problemas não convexos, uma limitação que motivou algoritmos posteriores.
Histórico
A otimização em aprendizado de máquina frequentemente envolve minimizar uma função objetivo que é uma soma de funções de perda por exemplo. Para um conjunto de treinamento com n exemplos, o risco empírico é dado por Q(w) = (1/n) Σ Q_i(w), onde w é o vetor de parâmetros e Q_i é a perda para o i-ésimo exemplo. A descida de gradiente padrão calcula o gradiente da soma completa a cada passo, o que pode ser computacionalmente caro quando n é grande. A descida de gradiente estocástica (SGD) aproxima o gradiente usando uma única amostra ou um mini-lote, reduzindo o custo computacional por iteração, mas introduzindo ruído. O algoritmo de Robbins-Monro da década de 1950 estabeleceu as bases para a aproximação estocástica, e a SGD tornou-se um pilar no aprendizado de máquina devido à sua eficiência em grandes conjuntos de dados.
Na SGD, a regra de atualização é w := w - η ∇Q_i(w), onde η é a taxa de aprendizado. Escolher uma taxa de aprendizado fixa é frequentemente subótimo: uma taxa muito grande pode causar divergência, enquanto uma taxa muito pequena desacelera a convergência. Métodos adaptativos como o AdaGrad visam resolver isso ajustando a taxa de aprendizado com base na geometria da paisagem de otimização. A motivação para o AdaGrad veio da observação de que diferentes parâmetros podem exigir tamanhos de passo diferentes, especialmente em problemas com características esparsas, onde alguns parâmetros são atualizados raramente.
Algoritmo
O AdaGrad modifica a atualização da SGD mantendo uma matriz diagonal G_t, onde cada elemento diagonal é a soma dos quadrados dos gradientes passados para o parâmetro correspondente. No passo de tempo t, a atualização para o parâmetro w_i é:
w_i := w_i - (η / sqrt(G_{t,ii} + ε)) ∇Q_i(w_i),
onde ε é uma pequena constante (por exemplo, 1e-8) para evitar divisão por zero. Os gradientes quadrados acumulados G_{t,ii} = Σ_{τ=1}^{t} (∇Q_i(w_τ))^2. Isso pode ser escrito em forma vetorial como:
w := w - η * diag(G_t + εI)^{-1/2} ∇Q(w).
Na prática, o algoritmo é frequentemente aplicado a mini-lotes, onde o gradiente é calculado sobre um subconjunto de exemplos de treinamento. A taxa de aprendizado por parâmetro é, portanto, η_t,i = η / sqrt(G_{t,ii} + ε). Como G_t cresce ao longo do tempo, a taxa de aprendizado efetiva diminui, garantindo que o algoritmo dê passos menores à medida que progride. Isso contrasta com a SGD com momentum, que acumula gradientes para acelerar em direções consistentes.
Propriedades Matemáticas
O AdaGrad foi originalmente analisado no contexto de otimização convexa. Os autores mostraram que, para funções convexas, o AdaGrad alcança um limite de arrependimento que é assintoticamente ótimo para aprendizado online. Especificamente, o arrependimento, que mede a diferença acumulada entre a perda do algoritmo e o melhor parâmetro fixo em retrospectiva, cresce como O(√T) para o AdaGrad, igualando o limite inferior para otimização convexa online. Isso é uma melhoria em relação à SGD padrão com taxa de aprendizado fixa, que pode exigir ajuste cuidadoso do cronograma de aprendizado.
A principal percepção é que o AdaGrad se adapta automaticamente à geometria do espaço de características. Em configurações esparsas, onde muitas características são zero para a maioria dos exemplos, os gradientes acumulados para essas características permanecem pequenos, permitindo atualizações maiores quando elas aparecem. Isso torna o AdaGrad particularmente eficaz para processamento de linguagem natural e outros domínios com entradas esparsas de alta dimensão.
No entanto, o acúmulo de gradientes quadrados é monotonicamente crescente, o que significa que a taxa de aprendizado decai para zero ao longo do tempo. Em problemas não convexos, como o treinamento de redes neurais profundas, isso pode fazer com que o algoritmo pare de aprender prematuramente. Essa limitação levou ao desenvolvimento de variantes como RMSProp, que usa uma média móvel dos gradientes quadrados em vez de uma soma, e Adam, que combina taxas de aprendizado adaptativas com momentum.
Aplicações
O AdaGrad foi aplicado em várias tarefas de aprendizado de máquina, particularmente aquelas envolvendo dados esparsos. Em processamento de linguagem natural, foi usado para treinar modelos em características bag-of-words, onde cada documento é representado por um vetor esparso de contagens de palavras. A adaptação por parâmetro permite que palavras raras recebam atualizações maiores, melhorando a capacidade do modelo de aprender com características infrequentes, mas informativas.
Em sistemas de recomendação, o AdaGrad foi usado para otimizar modelos de fatoração de matrizes, onde embeddings de usuários e itens são atualizados com base em dados de interação esparsos. A capacidade do algoritmo de lidar com frequências variadas de pares usuário-item o torna adequado para tais configurações. Além disso, o AdaGrad foi empregado em cenários de aprendizado online, onde os dados chegam sequencialmente e o modelo deve se adaptar rapidamente.
Apesar de ter sido superado por otimizadores mais avançados em muitas aplicações de aprendizado profundo, o AdaGrad permanece como um padrão de comparação e ainda é usado em alguns domínios onde suas propriedades são vantajosas. Sua influência é evidente no design de métodos adaptativos posteriores, que se baseiam na ideia de taxas de aprendizado por parâmetro.
Limitações e Extensões
A principal limitação do AdaGrad é a taxa de aprendizado monotonicamente decrescente. Em aprendizado profundo, onde a paisagem de perda é não convexa, isso pode levar a convergência lenta ou a ficar preso em mínimos locais ruins. Para resolver isso, pesquisadores propuseram várias extensões:
- RMSProp: Introduzido por Geoffrey Hinton em suas notas de aula, o RMSProp usa uma média exponencialmente decrescente dos gradientes quadrados, permitindo que a taxa de aprendizado se adapte de forma mais flexível.
- Adam: Proposto por Diederik Kingma e Jimmy Ba em 2014, o Adam combina a média móvel do RMSProp com momentum, fornecendo tanto taxas de aprendizado adaptativas quanto momentum.
- AdaDelta: Desenvolvido por Matthew Zeiler, o AdaDelta elimina a necessidade de um hiperparâmetro de taxa de aprendizado usando uma janela de gradientes passados.
Esses algoritmos se tornaram as escolhas padrão para treinar redes neurais profundas, mas todos traçam suas raízes no conceito de gradiente adaptativo introduzido pelo AdaGrad.
Impacto e Legado
O AdaGrad teve um impacto duradouro no campo da otimização em aprendizado de máquina. Foi um dos primeiros algoritmos amplamente adotados a usar taxas de aprendizado por parâmetro, abrindo caminho para uma família de otimizadores adaptativos. Suas garantias teóricas em configurações convexas forneceram uma base sólida para entender métodos adaptativos. O algoritmo é frequentemente citado em livros-texto e artigos de pesquisa como um desenvolvimento-chave na história da otimização.
Na prática, o AdaGrad é menos comumente usado hoje para treinar modelos de aprendizado profundo em larga escala, pois Adam e suas variantes tendem a ter melhor desempenho. No entanto, permanece uma ferramenta útil para problemas específicos, como aqueles com características esparsas, e ainda é ensinado em cursos de aprendizado de máquina como um passo conceitual importante.
Ver Também
- descida de gradiente estocástica
- otimizador Adam
- RMSProp
- aprendizado profundo