В этом курсе мы изучим алгоритм градиентного спуска, который позволяет, начиная со случайной точки, за несколько итераций достигать локального минимума заданной функции.
Сначала мы объясним интуицию, лежащую в основе этого алгоритма, затем мы приведем простой пример его применения для оптимизации функции с одной переменной, и, наконец, мы будем использовать этот алгоритм для поиска оптимальных параметров линейной регрессии.
Давайте начнем с описания интуитивного понимания этого алгоритма с помощью очень простой иллюстрации, которая выглядит следующим образом:
Предположим, вы находитесь на вершине этого холма и хотите спуститься вниз как можно быстрее, но, поскольку вы не хотите навредить себе, вы хотите спускаться спокойно и шаг за шагом.
На первом шаге вы окажетесь на самой высокой точке холма, дальше можно осмотреться и найти место с очень крутым склоном, но где возможен спуск, вы идете выбирать место и идете к следующее место следующим образом
Оказавшись в этом новом положении, вы повторите ту же процедуру, вы будете искать вокруг себя место с максимальным уклоном, но на котором нет риска получения травмы, затем вы перейдете к следующему положению.
Мы можем повторять эту же процедуру в каждой новой позиции, пока не достигнем самой низкой точки холма, как показано на рисунке ниже.
Эта очень простая итеративная процедура может спустить вас вниз за конечное число шагов, количество шагов зависит от риска, на который вы готовы пойти на каждый шаг. Чем круче склон, тем быстрее может быть спуск.
У нас также может быть несколько путей, ведущих к одной и той же цели, каждый путь будет зависеть от направления спуска, которое вы выбрали на каждом этапе.
Теперь предположим, что эта иллюстрация создается функцией J с двумя переменными. Можно подумать, что мы можем выполнить ту же процедуру, чтобы минимизировать эту функцию и найти локальный минимум.
Мы можем начать со случайной точки на поверхности, порожденной функцией J, а затем итеративно прийти к локальному минимуму. Но как это формализовать математически и как узнать, в каком направлении двигаться в каждой новой позиции?
Чтобы иметь направление спуска, мы будем изучать производную функции, которая согласно Википедии определяется следующим образом.
«В математике производная функции действительной переменной измеряет чувствительность к изменению значения функции (выходного значения) по отношению к изменению ее аргумента (входного значения)». Википедия
Как указано в определении, производная функции позволяет нам узнать, как изменится значение функции, если мы внесем небольшое изменение в ее входные данные. Для одномерной функции это можно математически сформулировать следующим образом:
Обычно производная не определяется таким образом, а вычисляется непосредственно из заданной функции. Эта формулировка дает более подробную информацию об идее, лежащей в основе производной.
Рассмотрим следующую функцию
Его производная может быть формально вычислена следующим образом
Мы можем представить значение производной для нескольких позиций функции f следующим образом.
На рисунке выше мы видим график, сгенерированный функцией f, а также значение ее производной f’.
Мы можем заметить, что производная имеет отрицательное значение для всех точек слева от глобального минимума, расположенного в точке x = 2, как только мы достигнем минимального значения, производная равна нулю, затем обратимся к положительному значению для всех точек к справа от минимума.
Это согласуется с определением производной, в первой части при спуске величина f(x+dx)-f(x) всегда отрицательна, а во второй части при подъеме эта сумма всегда положительна.
Производную также можно рассматривать как наклон линии между (x, f (x)) и (x + dx, f (x + dx)), как показано на рисунке ниже.
Математически это можно сформулировать следующим образом
В алгоритме градиентного спуска мы будем просто использовать противоположное значение производной для спуска в направлении с максимальным наклоном на каждом шаге, это можно сформулировать следующим образом
Параметр α поможет нам взвесить значение градиента функции, чтобы не было очень резкого спуска.
Мы проиллюстрируем внутреннюю работу этого алгоритма, чтобы минимизировать функцию, использованную выше, мы будем использовать следующий код Python.
import matplotlib.pyplot as plt
import numpy as np
def f(x):
return (x-2)**2+1
def f_prime(x):
return 2*(x-2)
# 100 linearly spaced numbers
x = np.linspace(-5,5,100)
# the function
y =f(x)
#Gradient descent
x_history=[-1.5]
for n in range(100):
t=x_history[-1]+-0.1*(f_prime(x_history[-1]))
x_history.append(t)
# setting the axes at the centre
fig = plt.figure()
ax = fig.add_subplot(1, 1, 1)
ax.spines['left'].set_position('center')
ax.spines['bottom'].set_position('zero')
ax.spines['right'].set_color('none')
ax.spines['top'].set_color('none')
ax.xaxis.set_ticks_position('bottom')
ax.yaxis.set_ticks_position('left')
# plot the function
plt.plot(x,y, 'r')
plt.scatter(x_history,f(np.array(x_history)))
# show the plot
plt.show()
Код производит следующий вывод
Мы можем заметить, что алгоритм работает правильно, после нескольких итераций мы достигаем глобального минимума, расположенного в точке x = 2.
Одним из наиболее важных моментов этого алгоритма является правильный выбор параметра α, неправильный выбор может повредить хорошему функционированию алгоритма, при выборе этого параметра могут произойти две вещи.
- α слишком мало: в этом случае градиент будет уменьшен до очень малого значения, поэтому новое значение x будет увеличено на очень маленькое значение, для сходимости алгоритма потребуется большое количество итераций.
- α слишком велико: в этом случае алгоритм может расходиться, если, например, мы находимся в точке, очень близкой к минимуму, очень большое значение alpha вызовет значительное приращение значение x, которое может выйти за пределы минимума.
Две возможности проиллюстрированы на следующем рисунке,
Значение α обычно выбирается равным 0,001.
Теперь, когда мы установили основу этого алгоритма, мы попробуем использовать его для решения задачи линейной регрессии.
Давайте начнем с создания и визуализации нашего набора данных, для этого мы будем использовать следующий код Python:
import numpy as np from matplotlib import pyplot as plt #Creating the dataset (as previously) x = np.linspace(0,1,40) noise = 1*np.random.uniform( size = 40) y = 1.5*x-0.8 #np.sin(x * 1.5 * np.pi ) y_noise = (y + noise).reshape(-1,1) plt.scatter(x,y_noise) The code produces the following output
Предположим, что эти данные можно смоделировать с помощью линейной регрессии с помощью функции h, определенной следующим образом:
Для того, чтобы найти оптимальные параметры этой функции, попробуем минимизировать евклидово расстояние между значениями этой функции и реальными значениями наших данных, более формально
Где m — количество обучающих выборок.
Теперь воспользуемся градиентным спуском для минимизации функции стоимости J, градиент функции J можно рассчитать следующим образом
Как только градиент будет рассчитан, мы можем итеративно увеличивать наши параметры с помощью алгоритма градиентного спуска, пока не достигнем минимума.
Мы используем следующий код Python для применения алгоритма градиентного спуска к функции J.
import numpy as np
import pandas as pd
from matplotlib import pyplot as plt
from mpl_toolkits.mplot3d import Axes3D
def costfunction(X,y,theta):
m = np.size(y)
#Cost function in vectorized form
h = X @ theta
J = float((1./(2*m)) * (h - y).T @ (h - y));
return J;
def gradient_descent(X,y,theta,alpha = 0.0005,num_iters=1000):
#Initialisation of useful values
m = np.size(y)
J_history = np.zeros(num_iters)
theta_0_hist, theta_1_hist = [], [] #For plotting afterwards
for i in range(num_iters):
#Grad function in vectorized form
h = X @ theta
theta = theta - alpha * (1/m)* (X.T @ (h-y))
#Cost and intermediate values for each iteration
J_history[i] = costfunction(X,y,theta)
theta_0_hist.append(theta[0,0])
theta_1_hist.append(theta[1,0])
return theta,J_history, theta_0_hist, theta_1_hist
#Creating the dataset (as previously)
x = np.linspace(0,1,40)
noise = 1*np.random.uniform( size = 40)
y = 1.5*x-0.8
y_noise = (y + noise).reshape(-1,1)
X = np.vstack((np.ones(len(x)),x)).T
#Setup of meshgrid of theta values
T0, T1 = np.meshgrid(np.linspace(-1,3,100),np.linspace(-6,2,100))
#Computing the cost function for each theta combination
zs = np.array( [costfunction(X, y_noise.reshape(-1,1),np.array([t0,t1]).reshape(-1,1))
for t0, t1 in zip(np.ravel(T0), np.ravel(T1)) ] )
#Reshaping the cost values
Z = zs.reshape(T0.shape)
#Computing the gradient descent
theta_result,J_history, theta_0, theta_1 = gradient_descent(X,y_noise,np.array([0,-6]).reshape(-1,1),alpha = 0.3,num_iters=1000)
#Angles needed for quiver plot
anglesx = np.array(theta_0)[1:] - np.array(theta_0)[:-1]
anglesy = np.array(theta_1)[1:] - np.array(theta_1)[:-1]
%matplotlib inline
fig = plt.figure(figsize = (16,8))
#Surface plot
ax = fig.add_subplot(1, 2, 1, projection='3d')
ax.plot_surface(T0, T1, Z, rstride = 5, cstride = 5, cmap = 'jet', alpha=0.5)
ax.plot(theta_0,theta_1,J_history, marker = '*', color = 'r', alpha = .4, label = 'Gradient descent')
ax.set_xlabel('theta 0')
ax.set_ylabel('theta 1')
ax.set_zlabel('Cost function')
ax.set_title('Gradient descent: Root at {}'.format(theta_result.ravel()))
ax.view_init(45, 45)
#Contour plot
ax = fig.add_subplot(1, 2, 2)
ax.contour(T0, T1, Z, 70, cmap = 'jet')
ax.quiver(theta_0[:-1], theta_1[:-1], anglesx, anglesy, scale_units = 'xy', angles = 'xy', scale = 1, color = 'r', alpha = .9)
plt.show()
Код выдает следующий результат
Мы видим, что начиная со случайной точки на поверхности и после нескольких итераций мы достигаем минимума, который дает следующую прямую линию
Мы замечаем, что прямая линия хорошо подходит для наших данных.
Вывод
В этом курсе мы определили, что такое метод градиентного спуска, мы указали различные параметры, которые его составляют, а затем использовали его для решения задачи линейной регрессии.
