If you're seeing this message, it means we're having trouble loading external resources on our website.

Se você está atrás de um filtro da Web, certifique-se que os domínios *.kastatic.org e *.kasandbox.org estão desbloqueados.

Conteúdo principal

Método do gradiente

O método do gradiente é um algoritmo de uso geral que calcula numericamente os mínimos de funções multivariáveis.

Conhecimentos prévios

Então, o que é isso?

O método do gradiente é um algoritmo que estima numericamente em que ponto uma função retorna seus menores valores. Isso significa que ele encontra os mínimos locais, mas não faz com que f=0, como vimos anteriormente. Em vez de encontrar os mínimos por meio da manipulação de símbolos, o método do gradiente faz a aproximação da solução com números. Além disso, tudo o que precisamos para rodar esse algoritmo é o resultado numérico de uma função, nenhuma fórmula é necessária.
Vale destacar essa diferença, porque é ela que torna o método do gradiente útil. Se tivéssemos uma fórmula simples, como f(x)=x24x, então seria fácil calcular f=0 para descobrir que x=2 minimiza f(x). Ou poderíamos usar o método do gradiente para obter uma aproximação numérica, algo como x1,99999967. As duas estratégias nos levam à mesma resposta.
Mas se não tivermos uma fórmula simples para a nossa função, então fica difícil, ou até impossível, calcular f=0. Se nossa função tem uma centena ou um milhão de variáveis, então é impossível manipular os símbolos. É aí que uma solução aproximada é valiosa, e o método do gradiente pode nos dar essas estimativas independentemente do quão elaborada nossa função seja.

Como funciona o método do gradiente

É mais fácil entender a forma como o método do gradiente encontra o mínimo das funções em casos tridimensionais.
Pense em uma função f(x,y) que define um terreno montanhoso quando representado graficamente como um mapa de alturas. Aprendemos que o gradiente calculado em qualquer ponto representa a direção da inclinação mais acentuada desse terreno montanhoso. Isso pode nos dar uma ideia de como poderíamos maximizar a função: iniciar com uma entrada aleatória e, quantas vezes forem possíveis, dar um pequeno passo na direção do gradiente para ir para a região mais elevada. Em outras palavras, temos que subir a montanha.
Para minimizar a função, podemos seguir o gradiente negativo e, então, ir na direção da descida mais íngreme e acentuada. Esse é o método do gradiente. Formalmente, se começamos em um ponto x0 e nos movemos uma distância α na direção do gradiente negativo, então nosso novo e melhorado x1 será assim:
x1=x0αf(x0)
De forma geral, podemos escrever uma fórmula para transformar xn em xn+1:
xn+1=xnαf(xn)
A partir de um palpite inicial x0, continuamos melhorando o palpite, aos poucos, até encontrarmos um mínimo local. Esse processo pode levar milhares de interações, então normalmente implementamos o método do gradiente com um computador.

Exemplo 1

Considere a função f(x)=x2cos(x)x10.
Como podemos ver no gráfico, essa função tem vários mínimos locais. O método do gradiente vai encontrar mínimos diferentes com base no nosso palpite inicial e no tamanho do nosso passo.
Se escolhermos, por exemplo, x0=6 e α=0,2, o método do gradiente se move como mostrado no gráfico abaixo. O primeiro ponto é x0 e as retas conectam cada ponto ao próximo na sequência. Após apenas 10 passos, convergimos para o mínimo próximo de x=4.
Se usarmos o mesmo x0, mas α=1,5, parece que o tamanho do passo é muito grande para o método do gradiente convergir para o mínimo. Vamos retomar esse assunto quando discutirmos as limitações do algoritmo.
Se começarmos em x0=7 com α=0,2, descemos para um mínimo local completamente diferente.

Exemplo 2

Vamos usar o método do gradiente para resolver o problema a seguir: como podemos aproximar sen(x) com um polinômio de grau 5 dentro do intervalo 3<x<3?
p(x)=a0+a1x++a5x5
Para usar o método do gradiente, precisamos pensar no problema de forma a minimizar uma função f. Intuitivamente, nosso objetivo é encontrar os coeficientes a0,,a5 que fazem com que p(x) esteja mais próximo o possível de sen(x) enquanto x está entre 3 e 3. Há diversas formas por meio das quais podemos pensar em uma função para minimizar. Uma delas é chamada de mínimos quadrados:
f(a0,,a5)=33(p(x)sen(x))2dx
Resumindo, definimos o nosso f como a soma do quanto p(x) é incorreto em cada ponto. Por exemplo, p(x)=2 próximo de x=0, então, f vai aumentar muito, pois sen(0)=0, não 2. O método do gradiente vai tentar diminuir f o máximo possível, que é o mesmo que aproximar p(x) de sen(x). Elevamos essa diferença ao quadrado para que a integral sempre seja positiva.
Veja o que acontece se começarmos com a0,,a5 com números negativos e depois nos movermos ao longo do gradiente negativo. O número no canto superior esquerdo nos ostra quantos passos demos, usando um passo de tamanho α=0,001.
Conseguimos uma ótima aproximação de sen(x)!
p(x)=0,00177+0,88974x+0,00287x20,11613x30,00048x4+0,00224x5
Tecnicamente, a animação acima usa o método do gradiente com momento, uma variante que nos ajuda para que não fiquemos presos em mínimos locais.

Limitações

O método do gradiente tem aplicação sempre que tivermos uma função e quisermos minimizá-la, o que é comum, por exemplo, no aprendizado de máquina. Mas é importante conhecer as limitações do método para que possamos nos planejar.
Uma das limitações dele é que ele encontra apenas mínimos locais (não encontra o mínimo global, ou absoluto). Tão logo o algoritmo encontre algum ponto que está em um mínimo local, ele nunca sairá de lá enquanto o tamanho do passo for menor que o tamanho do buraco, isto é, da concavidade que contém o mínimo.
No gráfico acima, cada mínimo local tem seu próprio vale que poderia prender um algoritmo do método do gradiente. Afinal, o algoritmo só tenta ir para baixo, então quando ele encontra um ponto a partir do qual todas as direções levam para cima, ele para. Ao olhar para o gráfico a partir de uma perspectiva diferente, também podemos ver que um mínimo local é mais baixo que o outro.
Quando minimizamos uma função, queremos encontrar o mínimo global, mas não há como o método do gradiente distinguir os mínimos local e global.
Outra limitação do método do gradiente envolve o tamanho do passo, α. Um bom tamanho de passo faz com que nos movamos na direção do mínimo rapidamente, de forma que cada passo nos leve a um progresso substancial.

Um bom tamanho de passo converge rapidamente.
Contudo, se o tamanho do passo for muito grande, podemos nunca convergir para um mínimo local, pois o excedemos toda vez.

Um passo com tamanho muito grande diverge.
Mesmo que tenhamos a sorte do algoritmo convergir mesmo assim, ele levaria muito mais iterações do que o necessário.

Passos de tamanho grande demoram para convergir.
Se o tamanho do passo for muito pequeno, então é provável que consigamos convergir, mas vamos precisar de muito mais iterações do que o necessário. Isso é um problema quando a função minimizada tem milhares ou milhões de variáveis, tornando os cálculos difíceis e pesados.

Passos de tamanho pequeno demoram para convergir.
Uma última limitação é que o método do gradiente só funciona quando nossa função for diferenciável em todos os pontos. Caso contrário, podemos chegar a um ponto no qual o gradiente não é definido, então não podemos usar nossa fórmula de atualização.

O método do gradiente não funciona com funções não diferenciáveis.

Resumo

  • O método do gradiente minimiza funções diferenciáveis que retornam um número como saída e têm qualquer número de variáveis de entrada.
  • Ele faz isso a partir de um palpite x0 e da aplicação sucessiva da fórmula xn+1=xnαf(xn). Em outras palavras, a fórmula nos diz para dar um pequeno passo na direção do gradiente negativo.
  • O método do gradiente não é capaz de dizer se um mínimo encontrado é local ou global.
  • O tamanho do passo α determina se o algoritmo converge para um mínimo lenta ou rapidamente, ou se ele diverge.
  • Muitos problemas do mundo real se resumem a minimizar uma função.

Quer participar da conversa?

Nenhuma postagem por enquanto.
Você entende inglês? Clique aqui para ver mais debates na versão em inglês do site da Khan Academy.