A Ideia por Trás do Gradiente Descendente

Autor

Douglas Braga

Nota

Esta seção corresponde a The Idea Behind Gradient Descent, do capítulo 8 de Grus (2019).

Em ciência de dados, resolver um problema frequentemente se resume a achar, para alguma função \(f\), o vetor de entrada que a minimiza ou maximiza. Isso significa resolver vários problemas de otimização sem chamar um otimizador pronto. A técnica que vamos usar, o gradiente descendente, é justamente a que melhor se presta a isso: cabe em poucas linhas e não esconde nada.

Suponha que temos alguma função \(f\) que recebe como entrada um vetor de números reais e devolve um único número real. Uma função simples desse tipo é a que já apareceu no Capítulo 4:

from scratch.linear_algebra import Vector, dot

def sum_of_squares(v: Vector) -> float:
    """Calcula a soma dos elementos ao quadrado em v"""
    return dot(v, v)

sum_of_squares([1, 2, 3])
14

Frequentemente vamos precisar maximizar ou minimizar funções como essa — isto é, achar o v de entrada que produz o maior (ou o menor) valor possível.

Para funções como a nossa, o gradiente — se você lembra do seu cálculo, é o vetor de derivadas parciais — aponta, no espaço de entrada, a direção em que a função cresce mais rápido.

Uma forma de maximizar uma função é, então: escolher um ponto de partida aleatório, calcular o gradiente, dar um passo pequeno na direção do gradiente (a direção que faz a função crescer mais) e repetir a partir do novo ponto. Da mesma forma, dá para minimizar uma função dando passos pequenos na direção oposta.

O procedimento

O procedimento inteiro é este:

  1. Escolha um ponto de partida qualquer.
  2. Calcule o gradiente nesse ponto.
  3. Dê um passo pequeno na direção oposta ao gradiente (se o objetivo é minimizar).
  4. Repita a partir do novo ponto.
Figura 21.1: Descida de gradiente sobre f(x, y) = x² + 5y²: as curvas de nível são elipses, e o caminho se curva para ficar perpendicular a cada uma delas

As curvas de nível do gráfico são as curvas onde f vale o mesmo — elipses, não círculos: como o termo em y pesa cinco vezes mais que o termo em x, para manter f constante uma variação em y precisa ser bem menor que a variação equivalente em x. Isso faz a tigela ser mais íngreme na direção de y do que na de x.

Repare no que isso faz com o caminho. Cada ponto vermelho ainda se move perpendicular à curva de nível em que está — essa regra não muda —, mas agora “perpendicular” não aponta para a origem: o passo inicial desce quase reto (a direção íngreme domina), e só depois de y encolher é que o caminho vira e passa a rastejar ao longo de x, a direção rasa. O caminho se curva. Numa tigela circular — o caso hipotético em que x e y pesassem igual, sem um termo dominando o outro —, isso seria invisível: direção radial e direção perpendicular à curva de nível coincidiriam por acaso. Aqui, não: a curvatura da função aparece no formato do caminho, e vai reaparecer, com números, quando a seção 5.4 explicar por que o tamanho certo do passo depende dela.

Aviso

Uma ressalva do próprio Grus (2019): se uma função tem um único mínimo global, este procedimento provavelmente o encontra. Se a função tem múltiplos mínimos locais, o procedimento pode “achar” o mínimo errado — nesse caso, você pode rodar o procedimento de novo a partir de pontos de partida diferentes. E se a função não tiver mínimo nenhum, é possível que o procedimento rode para sempre.

Falta uma peça: como, exatamente, calculamos o gradiente de uma função? É isso que a próxima seção resolve.

Grus, Joel. 2019. Data Science from Scratch: First Principles with Python. 2nd ed. O’Reilly Media.