Gradientný zostup

Tento poznámkový blok sleduje obsah lekcie o prechodovom zostupe. V ňom môžete spustiť simuláciu gradientného zostupu a vyskúšať, čo sa stane s rôznymi nastaveniami rýchlosti učenia. Môžete experimentovať s hodnotami iných nastavení a lepšie pochopiť, ako tento algoritmus funguje.

Najprv načítajte knižnice, ktoré budú potrebné na ďalšiu prácu.

import numpy as np
from matplotlib import pyplot as plt

Intuícia gradientného zostupu

V nasledujúcich dvoch bunkách je definovaná funkcia \(f(x)=(x-1)^2\) a jej derivácia \(f'(x)=2x-2\). Vykonajte ich, aby ste mohli funkcie ďalej používať.

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

f(3)

Out[3]:

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

f(1)

Out[5]:

Nasledujúca časť vám umožní sledovať, čo sa deje v jednotlivých krokoch stúpania.

V tejto bunke môžete nastaviť počiatočnú hodnotu bodu x0 a rýchlosť učenia alfa. Zakaždým, keď niečo zmeníte, spustite aj bunky nižšie.

 x0 = 3
alfa = 0.25

Body points budú obsahovať hodnoty získané jednotlivými krokmi zostupu. Budeme ich môcť zobraziť pomocou funkcie 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()

Funkcia one_step_descent vypočíta hodnotu pre x, na ktorú sa presunieme v jednom kroku gradientného zostupu. Spustite bunku, aby ste ju mohli používať.

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

  return x_new

Postupným vykonaním bunky nižšie môžete sledovať zostup smerom k minimu funkcie.

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

Teraz sa môžete vrátiť na začiatok a vyskúšať nasledujúce hodnoty:

x0=3 a alfa=0.05 - bude to skúška trpezlivosti kvôli pomalému klesaniu!
x0=3 a alfa=1.05 - to bude prekvapenie, pretože v skutočnosti nie je žiadny kles!
x0=5 a alfa=0.9 - to vám ukáže, čo znamená kľukatá pasca!

V týchto experimentoch nezabudnite vo funkcii show_graphnastaviť argument show_transition na hodnotu True, aby ste mohli sledovať cestu bodu.

Algoritmus gradientného zostupu

Táto bunka obsahuje všetky nastavenia funkcie prechodového zostupu.

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

Táto bunka obsahuje implementáciu funkcie gradientného zostupu. Keď ho vykonáte, budete môcť okamžite vidieť, pre ktoré x je hodnota funkcie najmenšia. Nezabudnite preskúmať, ako sa mení výsledok pre rôzne nastavenia tohto algoritmu. Napríklad pri niektorých kombináciách učebných krokov a východiskových bodov bude zostup veľmi pomalý.

 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

Správa o funkcii nám hovorí, či sa algoritmus zastavil (t. j. či sa dosiahla požadovaná presnosť výpočtu), koľko iterácií trval a v akom bode je hodnota funkcie najmenšia. Vykonajte nasledujúce bunky na vygenerovanie zostavy.

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

report

Out[15]:

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

Vyhľadajte parametre β0 a β1

Vyhľadajte parametre \( \beta_0 \) a \(\beta_1\)

Ako sme sa dozvedeli, pre danú množinu bodov \((x, y)\) sa stredná druhá mocnina chyby vypočíta ako súčet štvorcov rozdielov medzi očakávanými hodnotami a predikciami modelu pomocou vzorca \(\frac{1}{N}\sum_{i=1}^N (y_i - (\beta_0 + \beta_1x_i))^2\) alebo \(\frac{1}{N} \sum_{i=1}^N (y_i -\beta_0 - \beta_1x_i)^2\). Naším cieľom je určiť hodnoty parametrov \(\beta_0\) a \(\beta_1\), pre ktoré je hodnota tejto funkcie najmenšia. Je zrejmé, že funkcia \(\frac{1}{2N} \sum_{i=1}^N (y_i -\beta_0 - \beta_1x_i)^2\) bude mať pre tieto parametre najmenšiu hodnotu, takže jej forma sa oveľa častejšie používa kvôli jemnejším tvarom gradientu. Preto ho použijeme v pokračovaní.

Podľa tohto vzorca funkcia mean_squared_error pre dané argumenty \(\beta_0\), \(\beta_1\), \(x\) a \(y\) vypočíta hodnotu strednej druhej štvorcovej chyby. Toto je tiež funkcia, pre ktorú chceme nájsť minimum pomocou techniky gradientného zostupu.

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

Minimalizácia chýb by sa mala vykonať s ohľadom na parametre \(\beta_0\) a \(\beta_1\). Preto budeme potrebovať aj gradienty tejto funkcie vzhľadom na \(\beta_0\) a \(\beta_1\). Dá sa overiť, že ide o 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]\). Ak prejdeme súčtom s mínusom pre jednoduchší výpočet, dostaneme 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]\).

Teraz sa pustíme do práce na prispôsobení funkcie gradientného zostupu pre úlohu lineárnej regresie. Musíme mať na pamäti, že máme dve premenné beta0a beta1 a že funkcia, ktorej minimum hľadáme, je stredná štvorcová chyba.

 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

Teraz nastavíme hodnoty pre x a y tak, aby zodpovedali hodnotám oblastí nehnuteľností a ich cenám z predchádzajúceho príkladu.

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

Vyberieme tiež niektoré počiatočné hodnoty pre parametre, ktoré figurujú v algoritme. Teraz je táto úloha oveľa ťažšia, pretože nemáme jasnú predstavu o tom, kam sa umiestniť alebo aké hodnoty parametrov zvoliť.

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

Potom začneme vyhľadávanie volaním funkcie, ktorú sme pripravili.

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

Nezabudnite vyskúšať, čo sa stane, keď zmeníte niektoré hodnoty. Opäť môžete očakávať pomalý klesanie, kľukatú pascu alebo proces, ktorý vás neprivedie k riešeniu.

V praxi sa častejšie používajú varianty gradientného zostupu s variabilnou rýchlosťou učenia. Tieto varianty sa riadia logikou, že keď sme si istí, že sa pohybujeme správnym smerom, môžeme robiť väčšie kroky, zatiaľ čo keď sme menej sebavedomí, môžeme robiť menšie kroky a byť opatrnejší. Bežnou praxou je tiež použitie techník štandardizácie údajov v týchto algoritmoch, aby bol celý proces numericky stabilnejší.