3.2 Descida de gradiente

Um pouco de atividade física no meio de uma história de regressão linear não faz mal, mas sente que há outra coisa. A função de erro quadrado médio depende da escolha dos parâmetros \(β_0\) e \(β_0\) - para diferentes combinações de \(β_0\) e \(β_1\) valores, obtemos valores de erro diferentes. Se traçarmos um gráfico desta função, por exemplo, ao longo do eixo x registamos os valores de \(β_0\), ao longo do eixo y registamos os valores de \(β_1\), e ao longo do eixo z registamos os valores de erro, obtemos um gráfico que se parece com o da figura abaixo. Se marcarmos uma seleção aleatória dos parâmetros \(β_0\) e \(β_1\) com um ponto vermelho, para chegar ao ponto em que o valor de erro é menor, realmente temos que descer até o pé dessa superfície. É por isso que a "técnica" que desenvolvemos no exemplo anterior é muito relevante. Só precisamos descobrir como encontrar as direções mais íngremes de descida. As funções ajudar-nos-ão com isso.

Gráfico da função de erro quadrado médio

O menor valor de uma imagem de uma função é chamado de mínimo.

Agora vamos olhar para a função quadrática \(f(x)=(x − 1)^2\), cujo gráfico é mostrado na figura abaixo, e tentar atingir o seu mínimo com a técnica de descida - está no ponto \(x = 1\) e é 0.

Observe o ponto vermelho correspondente a \(x = 3\) (escolhido aleatoriamente) que marca a posição inicial do movimento em direção ao mínimo desta função. Parece que a reta laranja marca a direção mais íngreme ao longo da qual podemos começar a descida. Curiosamente, esta reta na verdade representa a tangente da nossa função no ponto \(x = 3\). Se dermos "um passo" nesta linha, encontramo-nos num novo ponto. Vamos marcar seu valor em vermelho e exibi-lo no gráfico. Está um pouco mais perto do mínimo esperado.

Agora podemos repetir o processo: vamos desenhar uma tangente em um novo ponto e, em seguida, dar um passo nessa linha.

Após um certo número de etapas, este procedimento nos levará à função mínima, ou seja, ao ponto \(x = 1\).

Esta seção é emparelhada com Jupyter Notebook 05-2-gradient_descent.ipynb . Para acompanhar o conteúdo, clique no botão  para abrir o conteúdo no Google Colab. Se estiver visualizando os blocos de anotações no seu dispositivo, localize o bloco de anotações com o mesmo nome entre os conteúdos e execute-o. 

No caderno que acompanha esse material, pode iniciar a animação e certificar-se de que é assim.

Antes de entrarmos em mais detalhes sobre o procedimento que descrevemos, vamos relembrar quais são essas tangentes reais. Para um ponto fixo \(x\), o coeficiente da direção da tangente em \(x\) é igual ao valor da primeira derivada da função em \(x\). A primeira derivada da nossa função é a função \(f′(x)= 2x − 2\) e no ponto inicial \(x = 3\) o valor da derivada é \(f′(x)= 4\). Isto significa que a tangente tem a equação \(y = 4x − 8\) (o número -8 é obtido a partir da condição de que esta reta deve conter um ponto (3, 4 )). É por isso que também podemos dizer que a tangente tem uma direção correspondente à derivada de uma função em um determinado ponto, e para o próprio movimento nessa direção que o movimento ao longo da direção da derivada está nesse ponto. Agora, o dilema é se avançamos ou descemos, ou seja, estamos indo na direção oposta, ou estamos indo na direção oposta? Bem, já que queremos descer ao mínimo, precisamos seguir a direção oposta à direção da derivada da função.

Se agora denotarmos o ponto de partida com \(x_0\), obtemos um novo ponto \(x_1\) dando um passo ao longo da direção da derivada da função no ponto \(x_0\). Se denotarmos o comprimento da etapa com \(α\), calculamos o valor do novo ponto \(x_1\) como \(x_1 = x_0 − αf′(x_0)\). Como repetimos o procedimento, calculamos o valor do ponto \(x_2\) como \(x_2 = x_1 − αf′(x_1)\) e continuamos com os cálculos \(x_3 = x_2 − αf′(x_2)\), \(x4 = x_3 − αf′(x_3)\), ... Repita o procedimento até que, para dois valores consecutivos, digamos \(x_{34}\) e \(x_{35}\), os valores da função estejam próximos o suficiente, ou seja, enquanto o valor absoluto da diferença \(f(x_{35})− f(x_{34})\) não seja inferior a alguma precisão predeterminada, digamos 0,001. Assim, computacionalmente, podemos abordar o conceito de convergência em matemática.

 O valor α introduzimos chama-se taxa de aprendizagem e representa um parâmetro muito importante do algoritmo que descrevemos. Se os valores para α forem muito pequenos, demoraremos muito tempo a atingir o mínimo. Por outro lado, se os valores para α forem muito altos, pode acontecer de pularmos o mínimo ou cairmos em uma armadilha de ziguezague pulando constantemente em torno dele! Veja a imagem abaixo!

O Impacto das Escolhas de Etapas de Aprendizagem

Bloqueio Zigzag

Certifique-se de verificar ambos os comportamentos no bloco de anotações complementar usando as diferentes configurações para a etapa de aprendizagem na animação.

 O algoritmo que descrevemos chama-se Gradient descent  e, apesar da sua simplicidade, é um dos algoritmos mais importantes na aprendizagem automática porque torna possível encontrar o menor valor de uma função de erro. Há muitos detalhes sobre este algoritmo que não entraremos nas propriedades das funções às quais este algoritmo pode ser aplicado com sucesso, o cálculo numérico da derivada e a seleção de etapas de aprendizagem. Todos eles devem ser considerados durante a aplicação prática do algoritmo.

O algoritmo em si não é desagradável de programar, então vamos embarcar em uma aventura. Precisamos de uma função f, que calculará o valor de uma determinada função, e de uma função f_derivative, que calculará o valor da derivada de uma determinada função. Precisamos definir tanto a etapa de aprendizagem alfa quanto os critérios de paragem: suspenderemos o procedimento quando os valores da função em duas iterações sucessivas estiverem próximos o suficiente (a diferença entre seus valores é menor do que alguma precisão épsilon predeterminada) ou quando atingirmos um número finito de iterações max_iterations (também precisamos ter certeza em casos de escolhas inadequadas de etapas de aprendizagem).

Siga o bloco de código. O algoritmo começou por definir um ponto de partida. Como o ponto em que nos movemos pelo algoritmo de descida de gradiente é o ponto de partida da próxima etapa, usamos os marcadores x_old e x_new para marcá-los em etapas sucessivas. O relatório que criamos no final da função contém informações sobre se o algoritmo parou, quantas etapas ele executa, ou seja, iteração necessária e que valor encontrou.

def gradient_descent(f, f_derivative, x, alpha, epsilon, max_iterations):

    # set the initial value for x
    x_old = x

    # in each iteration ...
    for i in range(0, max_iterations):

        # calculate the current value for x
        x_new = x_old - alpha * f_derivative(x_old)

        # and then check if the stopping criterion is met
        if np.abs(f(x_new) - f(x_old)) < epsilon:
            break

        # if the criterion is not met, prepare x for the next iteration
        x_old = x_new

    # at the end of the whole process, prepare a report with information:
    # whether the algorithm stops,
    # how many iterations it lasted,
    # and what value of x was found
    report = {}
    report['stops'] = i != max_iterations
    report['number_of_iterations'] = i
    report['x_min'] = x_old

    return report

A função e sua derivação podem ser definidas pelos seguintes blocos Python:

def f(x):
   return (x-1)**2

def f_izvod(x):
   return 2*x-2

Depois de executar a função gradijentni_spust para os valores dos argumentos \(x_0\) = 3, alfa = 0,1, épsilon = 0,001 e max_broj_iteracija = 100, obtemos que o mínimo da função é 1,0048, o que podemos confirmar. Também pode executar o código por conta própria e certificar-se de obter o resultado. Não se esqueça de examinar como os resultados mudam se outros valores de argumento forem selecionados.

Agora podemos voltar ao problema de encontrar os parâmetros \(β_0\) e \(β_1\) de regressão linear para os quais o valor do erro quadrado médio deve ter o menor valor. A função de erro quadrado médio é uma função de duas variáveis - depende do valor do parâmetro \(β_0\) e do valor do parâmetro \(β_1\). Ao trabalhar com funções de múltiplas variáveis, em geral com n variáveis \(x_1, x_2, x_3, ..., x_n\), a derivada que usamos no algoritmo de descida de gradiente é generalizada por um vetor de derivadas parciais - para cada uma das variáveis calculamos as derivadas individualmente. Por exemplo, para uma função \(\frac{1}{2} (x_1^2 + 10x_2^2)\), a derivada da variável \(x_1\) é obtida declarando a variável \(x_2\) como uma constante e, em seguida, aplicando as regras padrão para calcular a derivada que nos levam a 12 ⋅ 2 ⋅ x_1 = x_1. Por outro lado, a derivada da variável \(x_2\) é calculada declarando a variável \(x_1\) como uma constante e aplicando as regras padrão para calcular a derivada. Agora temos \(\frac{1}{2} ⋅ 10 ⋅ 2 ⋅ x_2 = 10 ⋅ x_2\). Agora temos que o vetor da derivada por variáveis individuais (tais derivadas são chamadas parciais) é o vetor \([x_1,10 ⋅ x_2]\). Em matemática, e mesmo em aprendizagem automática, esses vetores são chamados  de gradientes, daí o nome do próprio algoritmo. Para denotar gradientes, usamos o símbolo triângulo para baixo, \(∇\) chamado nabla. Assim, a notação precisa do gradiente da função inicial f′ seria \(∇ f(x_1, x_2 )= [x_1 ,10 ⋅ x_2 ]\) e nos permitiria acompanhar quais direções do lead deveríamos mover individualmente durante a descida.

As outras etapas do algoritmo de descida de gradiente não diferem muito no caso de funções multivariadas: esperamos que o algoritmo pare depois que a precisão desejada tiver sido alcançada, ou depois que um certo número de iterações tiver sido executado.

Agora que entendemos como funciona a descida de gradiente para funções de múltiplas variáveis, vamos voltar a calcular os parâmetros \(β_0\) e \(β_1\). Dissemos que a equação do erro quadrado médio é \(\frac{1}{N} \sum\limits_{i = 1}^{N}(yi −(β_0 + β1xi))^2\). Como esta é uma função para a qual precisamos encontrar o mínimo, se arregaçarmos as mangas e verificarmos, obtemos que a derivada da função quadrada média por \(β_0\) é exatamente \(\frac{2}{N} \sum\limits_{i = 1}^{N}(β_0 + β_1x_i − y_i)\) e a derivada por \(β_1\) é exatamente \(\frac{1}{N} \sum\limits_{i = 1}^{N}(β_0 + β_1x_i − y_ i) ⋅ x_i\) . Essas derivadas indicam quais direções devemos seguir e o quanto devemos corrigir os valores de \(β_0\) e \(β_1\) em cada etapa da iteração de descida de gradiente.

No bloco de anotações, também pode ver como esses valores são calculados por meio de código e, em seguida, passar por todo o processo de descida de gradiente personalizado. Para o conjunto imobiliário que introduzimos, chegaremos aos valores de \(β_0 = 2.056\) e \(β_0 = 1.198\).

Dissemos que existem certos pré-requisitos que uma função precisa satisfazer para que seu mínimo seja encontrado pela técnica de descida de gradiente (é necessário que a função seja diferenciável). Também é importante saber que, em geral, um mínimo local é atingido desta forma. Por exemplo, a função na figura abaixo tem vários mínimos locais e apenas um mínimo global . Em alguns casos, por exemplo, quando uma função é convexa, os mínimos local e global coincidem, por isso chegamos sempre à solução desejada, o mínimo global. A função de erro quadrado é convexa pelos parâmetros \(β_0\) e \(β_1\).

Mínimos locais e globais.

O campo da matemática que lida com encontrar os valores máximos e mínimos de funções (nós os chamamos de ótimos por um nome) é chamado de otimização matemática . A descida de gradiente é apenas um algoritmo da paleta deste campo.