Автор оригинала: Mehreen Saeed.
Вступление
Этот учебник представляет собой введение в простую технику оптимизации под названием градиентный спуск , которая нашла широкое применение в современных моделях машинного обучения.
Мы разработаем программу общего назначения для реализации градиентного спуска и применим ее для решения различных задач, включая классификацию с помощью контролируемого обучения.
В этом процессе мы получим представление о работе этого алгоритма и изучим влияние различных гиперпараметров на его производительность. В качестве примеров мы также рассмотрим пакетный и стохастический градиентный спуск варианты.
Что такое Градиентный спуск?
Градиентный спуск-это метод оптимизации, который может найти минимум целевой функции . Это жадный метод, который находит оптимальное решение, делая шаг в направлении максимальной скорости уменьшения функции.
Напротив, Градиентное восхождение является близким аналогом, который находит максимум функции, следуя направлению максимальной скорости увеличения функции.
Чтобы понять, как работает градиентный спуск, рассмотрим многомерную функцию \(f(\textbf{w})\), где \(\textbf w = [w_1, w_2, \ldots, w_n]^T \). Чтобы найти \( \textbf{w}\), при котором эта функция достигает минимума, градиентный спуск использует следующие шаги:
Выберите начальное случайное значение \( \textbf{w} \)
Выберите количество максимальных итераций
TВыберите значение для скорости обучения \( \eta \in [a,b] \)
Повторяйте следующие два шага до тех пор, пока \(f\) не изменится или итерации не превысят
a.Вычислить: \( \Delta \textbf{w} = – \eta \nabla_\textbf{w} f(\textbf{w}) \)
b. обновите \(\textbf{w} \) как: \(\textbf{w} \leftarrow \textbf{w} + \Delta \textbf{w} \)
Символ стрелки влево-это математически правильный способ написания оператора присваивания.
Здесь \( \nabla_\textbf{w} f \) обозначает градиент \(f\), заданный следующим образом: $$ \nabla_\textbf{w} f(\textbf{w}) = \begin{bmatrix} \frac{\partial f(\textbf{w})}{\partial w_1} \ \frac{\partial f(\textbf{w})}{\partial w_2} \ \vdots\ \frac{\partial f(\textbf{w})}{\partial w_n} \end{bmatrix} $$
Рассмотрим пример функции двух переменных \(^2+w_2^2 \), то на каждой итерации \( (w_1,w_2) \) обновляется как:
$$ \$$ \begin {bmatrix} w_1 \ w_2 \end {bmatrix} \leftarrow \begin {bmatrix} w_1 \ w_2 \end {bmatrix} – \beta \begin {bmatrix} 2 w_1 \ 2 w_2 \end {bmatrix} $$
На рисунке ниже показано, как работает градиентный спуск для этой функции.
Круги – это контуры этой функции. Если мы будем двигаться вдоль контура, то значение функции не изменится и останется постоянным .
Это противоположно направлению градиента, где функция изменяется с максимальной скоростью. Поэтому направление градиента функции в любой точке является нормальным к касательной контуров в этой точке.
Проще говоря, градиент можно принять за стрелку, указывающую направление, в котором функция изменяется больше всего.
Следование отрицательному направлению градиента приведет к точкам, где значение функции уменьшается с максимальной скоростью. Скорость обучения , также называемая размером шага , определяет, насколько быстро или медленно мы движемся по направлению градиента.
Добавление импульса
При использовании градиентного спуска мы сталкиваемся со следующими проблемами:
Попадание в ловушку локального минимума, что является прямым следствием жадности этого алгоритма
Промах и отсутствие глобального оптимума-это прямой результат слишком быстрого движения вдоль направления градиента
Осцилляция-это явление, которое возникает, когда значение функции существенно не меняется, независимо от того, в каком направлении она движется. Вы можете думать об этом как о навигации по плато, вы находитесь на одной и той же высоте независимо от того, куда вы идете
Для борьбы с этими проблемами к выражению для \( \Delta \ textbf{w}\) добавляется импульсный член \(\alpha\), чтобы стабилизировать скорость обучения при движении к глобальному оптимальному значению.
Ниже мы используем верхний индекс \(i\) для обозначения номера итерации: $$ \Delta \textbf{w}^i = – \eta \nabla_\textbf{w} f(\textbf{w}^i) + \alpha \textbf{w}^{i-1} $$
Реализация градиентного спуска в Python
Прежде чем мы начнем писать фактический код для градиентного спуска, давайте импортируем некоторые библиотеки, которые мы будем использовать, чтобы помочь нам:
import numpy as np import matplotlib import matplotlib.pyplot as plt import sklearn.datasets as dt from sklearn.model_selection import train_test_split
Теперь, когда с этим покончено, давайте продолжим и определим функцию gradient_descent () . В этой функции цикл заканчивается, когда либо:
Количество итераций превышает максимальное значение
Разница в значениях функций между двумя последовательными итерациями падает ниже определенного порога
Параметры обновляются на каждой итерации в соответствии с градиентом целевой функции.
Функция будет принимать следующие параметры:
max_iterations: Максимальное количество итераций для запускаthreshold: Остановка, если разница в значениях функции между двумя последовательными итерациями падает ниже этого порогаw_init: Начальная точка, с которой начинается градиентный спускobj_func: Ссылка на функцию, которая вычисляет целевую функциюgrad_func: Ссылка на функцию, вычисляющую градиент функцииextra_params: Дополнительные параметры (при необходимости) для obj_func и grad_funclearning_rate: Размер шага для градиентного спуска. Он должен быть в [0,1]momentum: Momentum to use. Он должен быть в [0,1]
Кроме того, функция вернет:
w_history: Все точки в пространстве, посещенные градиентным спуском, в которых оценивалась целевая функцияf_history: Соответствующее значение целевой функции, вычисленное в каждой точке
# Make threshold a -ve value if you want to run exactly
# max_iterations.
def gradient_descent(max_iterations,threshold,w_init,
obj_func,grad_func,extra_param = [],
learning_rate=0.05,momentum=0.8):
w = w_init
w_history = w
f_history = obj_func(w,extra_param)
delta_w = np.zeros(w.shape)
i = 0
diff = 1.0e10
while ithreshold:
delta_w = -learning_rate*grad_func(w,extra_param) + momentum*delta_w
w = w+delta_w
# store the history of w and f
w_history = np.vstack((w_history,w))
f_history = np.vstack((f_history,obj_func(w,extra_param)))
# update iteration number and diff between successive values
# of objective function
i+=1
diff = np.absolute(f_history[-1]-f_history[-2])
return w_history,f_history
Оптимизация функций с помощью градиентного спуска
Теперь, когда у нас есть универсальная реализация градиентного спуска, давайте запустим ее на нашем примере 2D-функции \(^2+w_2^2 \) с круговыми контурами.
Функция имеет минимальное значение нуля в начале координат. Давайте сначала визуализируем функцию, а затем найдем ее минимальное значение.
Визуализация целевой функции f(x)
Функция visualize_fw() ниже генерирует 2500 равномерно расположенных точек на сетке и вычисляет значение функции в каждой точке.
Функция function_plot() отображает все точки разными цветами в зависимости от значения \(f(\textbf w)\) в этой точке. Все точки, в которых значение функции одинаково, имеют один и тот же цвет:
def visualize_fw():
xcoord = np.linspace(-10.0,10.0,50)
ycoord = np.linspace(-10.0,10.0,50)
w1,w2 = np.meshgrid(xcoord,ycoord)
pts = np.vstack((w1.flatten(),w2.flatten()))
# All 2D points on the grid
pts = pts.transpose()
# Function value at each point
f_vals = np.sum(pts*pts,axis=1)
function_plot(pts,f_vals)
plt.title('Objective Function Shown in Color')
plt.show()
return pts,f_vals
# Helper function to annotate a single point
def annotate_pt(text,xy,xytext,color):
plt.plot(xy[0],xy[1],marker='P',markersize=10,c=color)
plt.annotate(text,xy=xy,xytext=xytext,
# color=color,
arrowprops=dict(arrowstyle="->",
color = color,
connectionstyle='arc3'))
# Plot the function
# Pts are 2D points and f_val is the corresponding function value
def function_plot(pts,f_val):
f_plot = plt.scatter(pts[:,0],pts[:,1],
c=f_val,vmin=min(f_val),vmax=max(f_val),
cmap='RdBu_r')
plt.colorbar(f_plot)
# Show the optimal point
annotate_pt('global minimum',(0,0),(-5,-7),'yellow')
pts,f_vals = visualize_fw()
Запуск градиентного спуска с различными гиперпараметрами
Теперь пришло время запустить градиентный спуск, чтобы минимизировать нашу целевую функцию. Чтобы вызвать gradient_descent() , мы определяем две функции:
f(): Вычисляет целевую функцию в любой точкевнутриgrade(): Вычисляет градиент в любой точкевнутри
Чтобы понять влияние различных гиперпараметров на градиентный спуск, функция solve_fw() вызывает gradient_descent() с 5 итерациями для различных значений скорости обучения и импульса.
Функция visualize_learning () выводит значения \((w_1 , w_2)\), причем значения функций отображаются разными цветами. Стрелки на графике облегчают отслеживание того, какая точка была обновлена с последней:
# Objective function
def f(w,extra=[]):
return np.sum(w*w)
# Function to compute the gradient
def grad(w,extra=[]):
return 2*w
# Function to plot the objective function
# and learning history annotated by arrows
# to show how learning proceeded
def visualize_learning(w_history):
# Make the function plot
function_plot(pts,f_vals)
# Plot the history
plt.plot(w_history[:,0],w_history[:,1],marker='o',c='magenta')
# Annotate the point found at last iteration
annotate_pt('minimum found',
(w_history[-1,0],w_history[-1,1]),
(-1,7),'green')
iter = w_history.shape[0]
for w,i in zip(w_history,range(iter-1)):
# Annotate with arrows to show history
plt.annotate("",
xy=w, xycoords='data',
xytext=w_history[i+1,:], textcoords='data',
arrowprops=dict(arrowstyle='<-',
connectionstyle='angle3'))
def solve_fw():
# Setting up
rand = np.random.RandomState(19)
w_init = rand.uniform(-10,10,2)
fig, ax = plt.subplots(nrows=4, ncols=4, figsize=(18, 12))
learning_rates = [0.05,0.2,0.5,0.8]
momentum = [0,0.5,0.9]
ind = 1
# Iteration through all possible parameter combinations
for alpha in momentum:
for eta,col in zip(learning_rates,[0,1,2,3]):
plt.subplot(3,4,ind)
w_history,f_history = gradient_descent(5,-1,w_init, f,grad,[],eta,alpha)
visualize_learning(w_history)
ind = ind+1
plt.text(-9, 12,'Learning Rate = '+str(eta),fontsize=13)
if col==1:
plt.text(10,15,'momentum = ' + str(alpha),fontsize=20)
fig.subplots_adjust(hspace=0.5, wspace=.3)
plt.show()
Давайте запустим solve_fw() и посмотрим, как скорость обучения и импульс влияют на градиентный спуск:
solve_fw()
Этот пример проясняет роль как импульса, так и скорости обучения.
На первом графике с нулевым импульсом и скоростью обучения, установленной на уровне 0,05, обучение идет медленно, и алгоритм не достигает глобального минимума. Увеличение импульса ускоряет процесс обучения, как мы видим из графиков в первом столбце. Другая крайность-последняя колонка, где скорость обучения поддерживается высокой. Это вызывает колебания, которыми можно управлять в определенной степени, добавляя импульс.
Общее руководство для градиентного спуска заключается в использовании малых значений скорости обучения и более высоких значений импульса.
Градиентный спуск для минимизации среднеквадратичной ошибки
Градиентный спуск – это хороший и простой метод минимизации среднеквадратичной ошибки в контролируемой задаче классификации или регрессии.
Предположим, что нам даны \(m\) обучающие примеры \([x_{ij}]\) с\ldots m\), где каждый пример имеет \(n\) признаков, т. Е.\ldots n \). Если соответствующие целевое и выходное значения для каждого примера равны \(t_i\) и \(o_i\) соответственно, то функция среднеквадратичной ошибки \(E\) (в данном случае наша объектная функция) определяется как:
$$ E = \frac{1}{m}}^m (t_i – o_i)^2 $$
Где выход \(o_i\) определяется взвешенной линейной комбинацией входов, заданной:
$$ + $$ + w_1 x_{i 1} + w_2 x_{i 2} + \ldots + w_n x_{in} $$
Неизвестным параметром в приведенном выше уравнении является весовой вектор \(\textbf w = [w_0,w_1,\ldots,w_n]^T\).
Целевой функцией в этом случае является среднеквадратичная ошибка с градиентом, заданным:
$$ \nabla_{\textbf w}E(\textbf w) =}^{m} (t_i – o_i) \textbf{x}_i $$
Где \(x_{i}\) – i-й пример. или массив признаков размера n .
Все, что нам сейчас нужно, – это функция для вычисления градиента и функция для вычисления среднеквадратичной ошибки.
Затем функцию gradient_descent() можно использовать как есть. Обратите внимание, что все обучающие примеры обрабатываются вместе при вычислении градиента. Следовательно, эта версия градиентного спуска для обновления весов называется пакетное обновление или пакетное обучение :
# Input argument is weight and a tuple (train_data, target)
def grad_mse(w,xy):
(x,y) = xy
(rows,cols) = x.shape
# Compute the output
o = np.sum(x*w,axis=1)
diff = y-o
diff = diff.reshape((rows,1))
diff = np.tile(diff, (1, cols))
grad = diff*x
grad = -np.sum(grad,axis=0)
return grad
# Input argument is weight and a tuple (train_data, target)
def mse(w,xy):
(x,y) = xy
# Compute output
# keep in mind that wer're using mse and not mse/m
# because it would be relevant to the end result
o = np.sum(x*w,axis=1)
mse = np.sum((y-o)*(y-o))
mse = mse/2
return mse
Запуск градиентного спуска на OCR
Чтобы проиллюстрировать градиентный спуск в задаче классификации, мы выбрали наборы данных цифр, включенные в sklearn.datasets .
Чтобы все было просто, давайте проведем тестовый запуск градиентного спуска на двухклассовой задаче (цифра 0 против цифры 1). Приведенный ниже код загружает цифры и отображает первые 10 цифр. Это дает нам представление о природе тренировочных точек:
# Load the digits dataset with two classes
digits,target = dt.load_digits(n_class=2,return_X_y=True)
fig,ax = plt.subplots(nrows=1, ncols=10,figsize=(12,4),subplot_kw=dict(xticks=[], yticks=[]))
# Plot some images of digits
for i in np.arange(10):
ax[i].imshow(digits[i,:].reshape(8,8),cmap=plt.cm.gray)
plt.show()
Нам также нужен метод train_test_split from sklearn.model_selection для разделения обучающих данных на поезд и тестовый набор. Приведенный ниже код запускает градиентный спуск на обучающем наборе, изучает веса и строит среднеквадратичную ошибку на разных итерациях.
При выполнении градиентного спуска мы будем поддерживать скорость обучения и импульс очень малыми, поскольку входные данные не нормализованы и не стандартизированы. Кроме того, пакетная версия градиентного спуска требует меньшей скорости обучения:
# Split into train and test set
x_train, x_test, y_train, y_test = train_test_split(
digits, target, test_size=0.2, random_state=10)
# Add a column of ones to account for bias in train and test
x_train = np.hstack((np.ones((y_train.size,1)),x_train))
x_test = np.hstack((np.ones((y_test.size,1)),x_test))
# Initialize the weights and call gradient descent
rand = np.random.RandomState(19)
w_init = rand.uniform(-1,1,x_train.shape[1])*.000001
w_history,mse_history = gradient_descent(100,0.1,w_init,
mse,grad_mse,(x_train,y_train),
learning_rate=1e-6,momentum=0.7)
# Plot the MSE
plt.plot(np.arange(mse_history.size),mse_history)
plt.xlabel('Iteration No.')
plt.ylabel('Mean Square Error')
plt.title('Gradient Descent on Digits Data (Batch Version)')
plt.show()
Это выглядит великолепно! Давайте проверим частоту ошибок нашего OCR на обучающих и тестовых данных. Ниже приведена небольшая функция для вычисления частоты ошибок классификации, которая вызывается на обучающем и тестовом множестве:
# Returns error rate of classifier
# total miclassifications/total*100
def error(w,xy):
(x,y) = xy
o = np.sum(x*w,axis=1)
#map the output values to 0/1 class labels
ind_1 = np.where(o>0.5)
ind_0 = np.where(o<=0.5)
o[ind_1] = 1
o[ind_0] = 0
return np.sum((o-y)*(o-y))/y.size*100
train_error = error(w_history[-1],(x_train,y_train))
test_error = error(w_history[-1],(x_test,y_test))
print("Train Error Rate: " + "{:.2f}".format(train_error))
print("Test Error Rate: " + "{:.2f}".format(test_error))
Train Error Rate: 0.69 Test Error Rate: 1.39
Стохастический градиентный спуск в Python
В предыдущем разделе мы использовали схему пакетного обновления для градиентного спуска.
Другая версия градиентного спуска-это схема обновления online или stochastic , где каждый обучающий пример берется по одному для обновления весов.
Как только все обучающие примеры пройдены, мы говорим, что эпоха завершена. Обучающие примеры перемешиваются перед каждой эпохой для достижения лучших результатов.
Приведенный ниже фрагмент кода представляет собой небольшую модификацию функции gradient_descent() для включения ее стохастического аналога. Эта функция принимает (обучающий набор, цель) в качестве параметра вместо дополнительного параметра. Термин “итерации” был переименован в “эпохи”:
# (xy) is the (training_set,target) pair
def stochastic_gradient_descent(max_epochs,threshold,w_init,
obj_func,grad_func,xy,
learning_rate=0.05,momentum=0.8):
(x_train,y_train) = xy
w = w_init
w_history = w
f_history = obj_func(w,xy)
delta_w = np.zeros(w.shape)
i = 0
diff = 1.0e10
rows = x_train.shape[0]
# Run epochs
while ithreshold:
# Shuffle rows using a fixed seed to reproduce the results
np.random.seed(i)
p = np.random.permutation(rows)
# Run for each instance/example in training set
for x,y in zip(x_train[p,:],y_train[p]):
delta_w = -learning_rate*grad_func(w,(np.array([x]),y)) + momentum*delta_w
w = w+delta_w
i+=1
w_history = np.vstack((w_history,w))
f_history = np.vstack((f_history,obj_func(w,xy)))
diff = np.absolute(f_history[-1]-f_history[-2])
return w_history,f_history
Давайте запустим код, чтобы увидеть, как выглядят результаты для стохастической версии градиентного спуска:
rand = np.random.RandomState(19)
w_init = rand.uniform(-1,1,x_train.shape[1])*.000001
w_history_stoch,mse_history_stoch = stochastic_gradient_descent(
100,0.1,w_init,
mse,grad_mse,(x_train,y_train),
learning_rate=1e-6,momentum=0.7)
# Plot the MSE
plt.plot(np.arange(mse_history_stoch.size),mse_history_stoch)
plt.xlabel('Iteration No.')
plt.ylabel('Mean Square Error')
plt.title('Gradient Descent on Digits Data (Stochastic Version)')
plt.show()
Давайте также проверим частоту ошибок:
train_error_stochastic = error(w_history_stoch[-1],(x_train,y_train))
test_error_stochastic = error(w_history_stoch[-1],(x_test,y_test))
print("Train Error rate with Stochastic Gradient Descent: " +
"{:.2f}".format(train_error_stochastic))
print("Test Error rate with Stochastic Gradient Descent: "
+ "{:.2f}".format(test_error_stochastic))
Train Error rate with Stochastic Gradient Descent: 0.35 Test Error rate with Stochastic Gradient Descent: 1.39
Сравнение пакетной и стохастической версий
Давайте теперь сравним как пакетную, так и стохастическую версии градиентного спуска.
Мы установим скорость обучения для обеих версий на одно и то же значение и изменим импульс, чтобы увидеть, как быстро они сходятся. Начальные веса и критерии остановки для обоих алгоритмов остаются одинаковыми:
fig, ax = plt.subplots(nrows=3, ncols=1, figsize=(10,3))
rand = np.random.RandomState(11)
w_init = rand.uniform(-1,1,x_train.shape[1])*.000001
eta = 1e-6
for alpha,ind in zip([0,0.5,0.9],[1,2,3]):
w_history,mse_history = gradient_descent(
100,0.01,w_init,
mse,grad_mse,(x_train,y_train),
learning_rate=eta,momentum=alpha)
w_history_stoch,mse_history_stoch = stochastic_gradient_descent(
100,0.01,w_init,
mse,grad_mse,(x_train,y_train),
learning_rate=eta,momentum=alpha)
# Plot the MSE
plt.subplot(130+ind)
plt.plot(np.arange(mse_history.size),mse_history,color='green')
plt.plot(np.arange(mse_history_stoch.size),mse_history_stoch,color='blue')
plt.legend(['batch','stochastic'])
# Display total iterations
plt.text(3,-30,'Batch: Iterations='+
str(mse_history.size) )
plt.text(3,-45,'Stochastic: Iterations='+
str(mse_history_stoch.size))
plt.title('Momentum = ' + str(alpha))
# Display the error rates
train_error = error(w_history[-1],(x_train,y_train))
test_error = error(w_history[-1],(x_test,y_test))
train_error_stochastic = error(w_history_stoch[-1],(x_train,y_train))
test_error_stochastic = error(w_history_stoch[-1],(x_test,y_test))
print ('Momentum = '+str(alpha))
print ('\tBatch:')
print ('\t\tTrain error: ' + "{:.2f}".format(train_error) )
print ('\t\tTest error: ' + "{:.2f}".format(test_error) )
print ('\tStochastic:')
print ('\t\tTrain error: ' + "{:.2f}".format(train_error_stochastic) )
print ('\t\tTest error: ' + "{:.2f}".format(test_error_stochastic) )
plt.show()
Momentum = 0 Batch: Train error: 0.35 Test error: 1.39 Stochastic: Train error: 0.35 Test error: 1.39 Momentum = 0.5 Batch: Train error: 0.00 Test error: 1.39 Stochastic: Train error: 0.35 Test error: 1.39 Momentum = 0.9 Batch: Train error: 0.00 Test error: 1.39 Stochastic: Train error: 0.00 Test error: 1.39
Хотя нет существенной разницы в точности между двумя версиями классификатора, стохастическая версия является явным победителем, когда дело доходит до скорости сходимости. Требуется меньше итераций, чтобы достичь того же результата, что и его пакетный аналог.
Выводы
Градиентный спуск-это простая и простая в реализации техника.
В этом уроке мы проиллюстрировали градиентный спуск на функции двух переменных с круговыми контурами. Затем мы расширили наш пример, чтобы минимизировать среднеквадратичную ошибку в задаче классификации, и построили простую систему распознавания. Мы также обсудили стохастическую версию градиентного спуска.
В этом учебном пособии была разработана функция общего назначения для реализации градиентного спуска. Мы рекомендуем читателям использовать эту функцию в различных задачах регрессии и классификации с различными гиперпараметрами для лучшего понимания ее работы.