Descida de gradiente

Este caderno segue o conteúdo da aula sobre descida de gradiente. Nele, pode executar uma simulação de descida de gradiente e experimentar o que acontece com diferentes configurações de taxa de aprendizagem. Você pode experimentar os valores de outras configurações e entender melhor como esse algoritmo funciona.

Primeiro, carregue as bibliotecas que serão necessárias para o trabalho futuro.

import numpy as np
from matplotlib import pyplot as plt

Intuição da Descida de Gradiente

Nas duas células seguintes, a função \(f(x)=(x-1)^2\) e sua derivada \(f'(x)=2x-2\) são definidas. Execute-os para poder usar ainda mais as funções.

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

f(3)

Out[3]:

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

f(1)

Out[5]:

A seção a seguir permite que você acompanhe o que acontece em etapas individuais da descida do gradiente.

Nesta célula, você pode definir o valor inicial do ponto x0 e a taxa de aprendizagem alfa. Cada vez que você alterar algo, execute as células abaixo também.

 x0 = 3
alfa = 0.25

Os points da matriz conterão os valores obtidos por etapas de descida individuais. Poderemos exibi-los usando a função show_graph.

points = [x0]

def show_graph(f, iteration=0, show_transition=False):
  x = np.linspace(-4, 6, 100, endpoint=True)
  y = f(x)

  plt.xticks(np.arange(-4, 6), np.arange(-4, 6))
  plt.plot(x, y)

  for t in points:
    plt.scatter(t, f(t), color='red')

  if show_transition == True:
    num_points = len(points)
    for i in range(0, num_points-1):
      plt.plot([points[i], points[i+1]], [f(points[i]), f(points[i+1])], linestyle='--', color='gray')

  plt.title('Iteration number: {iteration}: '.format(iteration=iteration))
  plt.show()

A função one_step_descent calcula o valor de x para o qual nos moveremos em uma etapa de descida de gradiente. Execute a célula para poder usá-la.

def one_step_descent(f, f_derivative, x, alpha):
  x_new = x - alpha * f_derivative(x)

  return x_new

Ao executar consecutivamente a célula abaixo, você pode acompanhar a descida em direção ao mínimo da função.

iteration = 1

# calculate the new point
x = one_step_descent(f, f_izvod, x0, alfa)

# add the point to the list of points
points.append(x)

# display the graph
show_graph(f, iteration, show_transition=False)

# increment the iteration number
iteration = iteration + 1

# set the position for the next descent
x0 = x

Agora você pode voltar ao início e tentar os seguintes valores:

x0=3 e alfa=0.05 - este será um teste de paciência devido à descida lenta!
x0=3 e alfa=1.05 - esta será uma surpresa porque na verdade não há descida!
x0=5 e alfa=0.9 - isto irá mostrar-lhe o que significa uma armadilha em ziguezague!

Nessas experiências, certifique-se de definir o argumento show_transition como True na função show_graph para que possa acompanhar o caminho do ponto.

Algoritmo de descida de gradiente

Esta célula contém todas as configurações para a função de descida de gradiente.

x0 = 3
alpha = 0.1
epsilon = 0.001
max_iterations = 100

Esta célula contém a implementação da função de descida de gradiente. Ao executá-lo, será capaz de ver imediatamente para qual x o valor da função é o menor. Certifique-se de examinar como o resultado muda para diferentes configurações desse algoritmo. Por exemplo, para algumas combinações de etapas de aprendizagem e pontos de partida, a descida será muito lenta.

 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['num_iterations'] = i
    report['x_min'] = x_old

    return report

O relatório de função nos diz se o algoritmo parou (ou seja, se a precisão de cálculo desejada foi alcançada), quantas iterações ele levou e o ponto em que o valor da função é o menor. Execute as seguintes células para gerar o relatório.

report = gradient_descent(f, f_izvod, x0, alfa, epsilon, max_iterations)

report

Out[15]:

{'stops': True, 'num_iterations': 6, 'x_min': 1.03125}

Pesquisa dos parâmetros β0 e β1

Pesquisar parâmetros \( \beta_0 \) e \(\beta_1\)

Como aprendemos, para um determinado conjunto de pontos \((x, y)\), o erro quadrado médio é calculado como a soma dos quadrados das diferenças entre os valores esperados e as previsões do modelo usando a fórmula \(\frac{1}{N}\sum_{i=1}^N (y_i - (\beta_0 + \beta_1x_i))^2\) ou \(\frac{1}{N} \sum_{i=1}^N (y_i -\beta_0 - \beta_1x_i)^2\). Nosso objetivo é determinar os valores dos parâmetros \(\beta_0\) e \(\beta_1\) para os quais o valor desta função é o menor. É claro que a função \(\frac{1}{2N} \sum_{i=1}^N (y_i -\beta_0 - \beta_1x_i)^2\) terá o menor valor para esses parâmetros, então sua forma é muito mais comumente usada devido às formas mais finas do gradiente. Portanto, vamos usá-lo na continuação.

Seguindo esta fórmula, a função mean_squared_error para determinados argumentos \(\beta_0\), \(\beta_1\), \(x\) e \(y\) calcula o valor do erro quadrático médio. Esta é também a função para a qual queremos encontrar o mínimo usando a técnica de descida de gradiente.

 def mean_squared_error(beta0, beta1, x, y):
    return 0.5 * np.average((y - beta0 - beta1 * x) ** 2)

A minimização de erros deve ser realizada em relação aos parâmetros \(\beta_0\) e \(\beta_1\). Portanto, também precisaremos dos gradientes dessa função em relação a \(\beta_0\) e \(\beta_1\). Pode-se verificar que este é o vetor \([-\frac{1}{N} \sum_{i=1}^{N}(y_i - \beta_0-\beta_1x_i), -\frac{1}{N} \sum_{i=1}^{N}(y_i - \beta_0 -\beta_1x_i)\cdot x_i]\). Se passarmos pela soma com um menos para um cálculo mais simples, obtemos o vetor \([\frac{1}{N} \sum_{i=1}^{N}(\beta_0 + \beta_1x_i - y_i), \frac{1}{N} \sum_{i=1}^{N}(\beta_0 + \beta_1x_i - y_i)\cdot x_i]\).

Agora vamos começar a trabalhar na adaptação da função de descida de gradiente para a tarefa de regressão linear. Precisamos ter em mente que temos duas variáveis beta0 e beta1 e que a função cujo mínimo estamos procurando é o erro quadrado médio.

 def gradient_descent_linear_regression(x, y, mean_squared_error, beta0, beta1, alpha, epsilon, max_iterations, plot=False):

    # set the initial value for beta0 and beta1
    beta0_old = beta0
    beta1_old = beta1

    # calculate the initial value of the error function
    error_old = mean_squared_error(beta0_old, beta1_old, x, y)

    # to be able to track how the value of the error function changes
    # we will store all calculated values in the errors array
    errors = [error_old]

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

        # calculate the current value for beta0 and beta1 by:

        # first calculate the gradient directions
        beta0_correction = np.average(beta0_old + beta1_old * x - y)
        beta1_correction = np.average((beta0_old + beta1_old * x - y) * x)

        # and then update the values for beta0 and beta1
        beta0_new = beta0_old - alpha * beta0_correction
        beta1_new = beta1_old - alpha * beta1_correction

        # for these calculated values, calculate the value
        # of the mean squared error
        error_new = mean_squared_error(beta0_new, beta1_new, x, y)

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

        # alternatively, the stopping criterion can be that
        # the value of the gradient is less than some predefined value
        # if np.linalg.norm(np.array([beta0_correction, beta1_correction])) < epsilon:
        #   break

        # if the criterion is not met, prepare beta0 and beta1 for the next iteration
        beta0_old = beta0_new
        beta1_old = beta1_new

        # prepare the value of the error function
        error_old = error_new

        # and add it to the array with all errors
        errors.append(error_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 beta0 and beta1 was found

    report = {}

    report['stops'] = i != max_iterations - 1
    report['num_iterations'] = i
    report['b_min'] = (beta0_old, beta1_old)

    # if the plot argument is set
    # we will also plot the error function during the parameter search
    if plot == True:
        plt.title('Error Function')
        plt.xlabel('Number of iterations')
        plt.ylabel('Mean Squared Error')
        plt.plot(np.arange(0, len(errors)), np.log(errors))

    return report

Vamos agora definir os valores para x e y para corresponder aos valores das áreas de propriedade e seus preços do exemplo anterior.

x = np.array([43, 25, 66, 80, 105, 70, 40, 85, 84, 102])
y = np.array([60, 32.1, 88.4, 111.4, 120.32, 72.1, 46.3, 90.1, 99.6, 139.2])

Também selecionaremos alguns valores iniciais para os parâmetros que figuram no algoritmo. Agora, essa tarefa é muito mais difícil porque não temos uma ideia clara de onde nos posicionar ou quais valores de parâmetro escolher.

beta0 = 2.5
beta1 = 1.5
alpha = 0.00001
epsilon = 0.000001
max_iterations = 200

Em seguida, iniciaremos a pesquisa chamando a função que preparamos.

gradient_descent_linear_regression(x, y, mean_squared_error, beta0, beta1, alpha, epsilon, max_iterations, plot=False)

{'stops': np.True_,
 'num_iterations': np.int64(151),
 'b_min': (np.float64(2.4960466912761294), np.float64(1.1930132064518595))}

Certifique-se de tentar o que acontece quando você altera alguns valores. Novamente, você pode esperar uma descida lenta, uma armadilha em ziguezague ou um processo que não o leva a uma solução.

Na prática, variantes de descida de gradiente com uma taxa de aprendizagem variável são mais comumente usadas. Estas variantes seguem a lógica de que, quando estamos confiantes de que estamos a avançar na direção certa, podemos dar passos maiores, enquanto quando estamos menos confiantes, podemos dar passos mais pequenos e ser mais cautelosos. Também é prática comum usar técnicas de padronização de dados nesses algoritmos para tornar todo o processo numericamente mais estável.

Uma solução tão melhor que esses algoritmos encontrariam para nós é \(\beta_0\)=2.056 e \(\beta_1\)=1.198.