Gradijentni spust

Ova sveska prati sadržaj lekcije o gradijentnom spustu. U njoj možeš da pokreneš simulaciju gradijentnog spusta i oprobaš šta se događa za različita podešavanja koraka učenja. Možeš da eksperimentišeš i sa vrednostima drugih podešavanja i stekneš bolju predstavu kako ovaj algoritam funkcioniše.

Učitaj prvo biblioteke koje će biti potrebne u daljem radu.

import numpy as np
from matplotlib import pyplot as plt

Intuicija gradijentnog spusta

U sledećim dvema ćelijama su definisane funkcija \(f(x)=(x-1)^2\) i njen izvod \(f'(x)=2x-2\). Izvrši ih da bi dalje mogao da koristiš funkcije.

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

f(3)

Out[3]:

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

f(1)

Out[5]:

Deo koji sledi omogućava da pratiš šta se događa u pojedinačnim koracima gradijentnog spusta.
U ovoj ćeliji možeš da postaviš početnu vrednost tačke `x0` i vrednost koraka učenja `alfa`. Svaki put kada nešto promeniš izvrši i donje ćelije.

 x0 = 3
alfa = 0.25

Niz points će sadržati vrednosti koje se dobijaju pojedinačnim koracima spusta. Njih ćemo moći da prikažemo koristeći funkciju 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()

Funkcija one_step_descent izračunava vrednost za x u koje ćemo se pomeriti jednim korakom gradijentnog spusta. Izvrši ćeliju da bi mogao da je koristiš.

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

  return x_new

Uzastopnim izvršavanjem donje ćelije možeš da pratiš kako se vrši spust ka minimumu funkcije.

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

Možeš sada da se vratiš na početak i probaš sledeće vrednosti:

x0=3 i alfa=0.05 - to će biti test strpljenja zbog sporog spusta!
x0=3 i alfa=1.05 - to će biti iznenađenje jer spusta zapravo nema!
x0=5 ialfa=0.9 - tako ćeš videti šta znači cik-cak zamka!

U ovim eksperimentima obavezno u funkciji show_transition postavi argument show_graph na vrednost True kako bi mogao da ispratiš putanju tačke.

Algoritam gradijentnog spusta

Ova ćelija sadrži sva podešavanja za funkciju gradijentnog spusta.

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

Ova ćelija sadrži implementaciju funkcije gradijentnog spusta. Kada je izvršiš, moći ćeš odmah da pročitaš za koje je to x vrednost funkcije najmanja. Obavezno ispitaj kako se menja rezultat za različita podešavanja ovog algoritma. Recimo , za neke kombinacije koraka učenja i startne tačke spust će biti jako spor.

 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

Izveštaj funkcije nam ispisuje da li se algoritam zaustavio (tj. da li je ostvarena željena tačnost izračunavanja), koliko mu je iteracija trebalo i koja je to tačka u kojoj je vrednost funkcije najmanja. Izvrši naredne ćelija da bi generisao izveštaj.

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

report

Out[15]:

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

Potraga za parametrima \(\beta_0\) i \(\beta_1\)

Kao što smo naučili, za zadati skup tačaka \((x, y)\) srednjekvadratna greška se računa kao suma kvadrata razlika očekivanih vrednosti i predikcija modela po formuli \(\frac{1}{N}\sum_{i = 1}^ N (y_i - (\beta_0 + \beta_1x_i))^ 2 \) tj. \( \frac {1}{N } \sum_{i = 1}^ N (y_i -\beta_0 - \beta_1x_i)^ 2 \). Cilj nam je da odredimo vrednosti parametra \(\beta_0 \) i \(\beta_1 \) za koje je vrednost ove funkcije najmanja. Jasno je da će i funkcija \(\frac{1}{2N} \sum_{i = 1}^ N (y_i -\beta_0 -\beta_1x_i)^ 2 \) za te vrednosti imati najmanju vrednost pa se njen oblik mnogo češće koristi zbog finijih oblika gradijenta. Zato ćemo nju koristiti u nastavku.

Prateći ovu formulu, funkcija ` srednjekvadratna_greska ` za zadate argumente \(\beta_0 \), \(\beta_1 \), \( x \) i \( y \) izračunava vrednost srednjekvadratne greške. Ovo je ujedno i funkcija za koju želimo da pronađemo minimum tehnikom gradijentnog spusta.

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

Minimizaciju greške treba izvršiti po parametrima \(\beta_0 \) i \(\beta_1 \). Zato će nam biti potrebni i gradijenti ove funkcije po \(\beta_0 \) i \(\beta_1 \). Može se proveriti da je to vektor \([-\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]\). Ukoliko minusom prođemo kroz sumu zbog jednostavnijeg računanja dobijamo vektor \([\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]\).

Sada ćemo se baciti na posao prilagođavanja funkcije gradijentnog spusta za zadatak linearne regresije. Treba da vodimo računa da imamo dve promenljive ` beta0 ` i ` beta1 ` i da je funkcija čiji minimum tražimo baš srednjekvadratna greška.

 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

Postavićemo sada vrednosti za ` x ` i ` y ` tako da odgovaraju vrednostima kvadratura nekretnina i njihovih cena iz prethodnog primera.

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])

Odabraćemo i neke početne vrednosti za parametre koji figurišu u algoritmu. Sada je ovaj zadatak dosta teži jer nemamo baš jasnu predstavu gde da se pozicioniramo ni koje vrednosti parametara da odaberemo.

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

Zatim ćemo pokrenuti pretragu pozivom funkcije koju smo pripremili.

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))}

Obavezno isprobaj šta će se desiti kada promeniš neke vrednosti. Opet možeš da očekuješ spor spust, cik-cak zamku ili postupak koji te ne dovodi do rešenja.

U praksi se češće koriste varijante gradijentnog spusta sa promenljivim korakom učenja koje se vode logikom da kada smo sigurni da idemo duž dobrog pravca možemo da pravimo veće korake dok kada smo manje sigurni možemo praviti i manje korake i budemo obazriviji. Praksa je i da se u ovim algoritmima koriste i tehnike standardizacije podataka koje bi ceo proces učinile numerički stabilnijim.

Jedno takvo bolje rešenje koji bi ovi algoritmi pronašli za nas je \(\beta_0 \) = 2.056 i \(\beta_1 \) = 1.198.