12.3. Градиентный спуск¶
В этом разделе мы введем основные понятия, лежащие в основе градиентного спуска. Хотя он редко используется напрямую в глубоком обучении, понимание градиентного спуска является ключом к пониманию алгоритмов стохастического градиентного спуска. Например, задача оптимизации может расходиться из-за слишком большой скорости обучения. Это явление уже можно наблюдать при градиентном спуске. Аналогично, предварительная обработка (preconditioning) является распространенной техникой в градиентном спуске и переносится на более сложные алгоритмы. Начнем с простого частного случая.
12.3.1. Градиентный спуск в одномерном случае¶
Градиентный спуск в одномерном случае — отличный пример, поясняющий, почему алгоритм градиентного спуска способен уменьшать значение целевой функции. Рассмотрим некоторую непрерывно дифференцируемую вещественную функцию \(f: \mathbb{R} \rightarrow \mathbb{R}\). Используя разложение Тейлора, получаем
То есть в первой линейной аппроксимации \(f(x+\epsilon)\) определяется значением функции \(f(x)\) и первой производной \(f'(x)\) в точке \(x\). Не будет преувеличением предположить, что при малых \(\epsilon\) движение в направлении отрицательного градиента приведёт к уменьшению \(f\). Для простоты мы выберем фиксированный размер шага \(\eta > 0\) и положим \(\epsilon = -\eta f'(x)\). Подставляя это в приведённое выше разложение Тейлора, получаем
Если производная \(f'(x) \neq 0\) не равна нулю, мы достигаем прогресса, поскольку \(\eta f'^2(x)>0\). Более того, мы всегда можем выбрать \(\eta\) достаточно малым, чтобы членами более высокого порядка можно было пренебречь. Таким образом, мы приходим к
Это означает, что, если мы используем
чтобы выполнить итерацию \(x\), значение функции \(f(x)\) может уменьшаться. Поэтому в градиентном спуске мы сначала выбираем начальное значение \(x\) и константу \(\eta > 0\), а затем используем их для непрерывной итерации \(x\) до тех пор, пока не будет выполнено условие остановки, например, когда величина градиента \(|f'(x)|\) становится достаточно малой или количество итераций достигает определённого значения.
Для простоты мы выберем целевую функцию \(f(x)=x^2\), чтобы проиллюстрировать реализацию градиентного спуска. Хотя нам известно, что \(x=0\) является решением задачи минимизации \(f(x)\), мы всё равно используем эту простую функцию, чтобы наблюдать за изменением \(x\).
%matplotlib inline
import numpy as np
import torch
from d2l import torch as d2l
def f(x): # Objective function
return x ** 2
def f_grad(x): # Gradient (derivative) of the objective function
return 2 * x
Далее мы используем \(x=10\) в качестве начального значения и предполагаем \(\eta=0.2\). Выполняя итерации градиентного спуска \(x\) 10 раз, мы видим, что в итоге значение \(x\) приближается к оптимальному решению.
def gd(eta, f_grad):
x = 10.0
results = [x]
for i in range(10):
x -= eta * f_grad(x)
results.append(float(x))
print(f'epoch 10, x: {x:f}')
return results
results = gd(0.2, f_grad)
Ход оптимизации по \(x\) можно изобразить следующим образом.
def show_trace(results, f):
n = max(abs(min(results)), abs(max(results)))
f_line = torch.arange(-n, n, 0.01)
d2l.set_figsize()
d2l.plot([f_line, results], [[f(x) for x in f_line], [
f(x) for x in results]], 'x', 'f(x)', fmts=['-', '-o'])
show_trace(results, f)
12.3.1.1. Скорость обучения¶
Скорость обучения \(\eta\) задается разработчиком алгоритма. Если использовать слишком малую скорость обучения, это приведет к тому, что \(x\) будет обновляться очень медленно, и для нахождения лучшего решения потребуется больше итераций. Чтобы проиллюстрировать, что происходит в таком случае, рассмотрим ход решения той же задачи оптимизации для \(\eta = 0.05\). Как видно, даже после 10 шагов мы все ещё очень далеки от оптимального решения.
show_trace(gd(0.05, f_grad), f)
С другой стороны, если использовать слишком высокую скорость обучения, \(\left|\eta f'(x)\right|\) может оказаться слишком большим для формулы разложения Тейлора первого порядка. Это означает, что член \(\mathcal{O}(\eta^2 f'^2(x))\) в (12.3.2) может стать значительным. В этом случае мы не можем гарантировать, что итерация \(x\) позволит уменьшить значение \(f(x)\). Например, при задании скорости обучения равной \(\eta=1.1\), \(x\) перелетает через оптимальное решение \(x=0\) и постепенно расходится.
show_trace(gd(1.1, f_grad), f)
12.3.1.2. Локальные минимумы¶
Чтобы проиллюстрировать, что происходит с невыпуклыми функциями, рассмотрим случай \(f(x) = x \cdot \cos(cx)\) для некоторой константы \(c\). Эта функция имеет бесконечно много локальных минимумов. В зависимости от выбранной скорости обучения и от того, насколько хорошо обусловлена задача, мы можем получить одно из множества решений. Приведённый ниже пример показывает, как (нереалистично) высокая скорость обучения приводит к плохому локальному минимуму.
c = torch.tensor(0.15 * np.pi)
def f(x): # Objective function
return x * torch.cos(c * x)
def f_grad(x): # Gradient of the objective function
return torch.cos(c * x) - c * x * torch.sin(c * x)
show_trace(gd(2, f_grad), f)
12.3.2. Многомерный градиентный спуск¶
Теперь, когда у нас есть лучшее понимание одномерного случая, рассмотрим ситуацию, когда \(\mathbf{x} = [x_1, x_2, \ldots, x_d]^\top\). То есть целевая функция \(f: \mathbb{R}^d \to \mathbb{R}\) отображает векторы в скаляры. Соответственно, её градиент также является многомерным. Это вектор, состоящий из \(d\) частных производных:
Каждый элемент \(\partial f(\mathbf{x})/\partial x_i\) градиента, являющийся частной производной, указывает на скорость изменения \(f\) в точке \(\mathbf{x}\) по отношению к входной переменной \(x_i\). Как и в случае одной переменной, мы можем использовать соответствующее разложение Тейлора для многомерных функций, чтобы получить представление о том, что следует делать. В частности, имеем:
Иными словами, с точностью до членов второго порядка в \(\boldsymbol{\epsilon}\) направление наискорейшего спуска определяется отрицательным градиентом \(-\nabla f(\mathbf{x})\). Выбор подходящей скорости обучения \(\eta > 0\) приводит к классическому алгоритму градиентного спуска:
Чтобы понять, как алгоритм ведет себя на практике, построим целевую функцию \(f(\mathbf{x})=x_1^2+2x_2^2\) с двумерным вектором \(\mathbf{x} = [x_1, x_2]^\top\) в качестве входных данных и скаляром в качестве выходных. Градиент задается выражением \(\nabla f(\mathbf{x}) = [2x_1, 4x_2]^\top\). Мы будем наблюдать за траекторией \(\mathbf{x}\) градиентного спуска, начиная с начальной точки \([-5, -2]\).
Для начала нам понадобятся две вспомогательные функции. Первая использует функцию обновления и применяет её 20 раз к начальному значению. Вторая вспомогательная функция визуализирует траекторию \(\mathbf{x}\).
def train_2d(trainer, steps=20, f_grad=None): #@save
"""Optimize a 2D objective function with a customized trainer."""
# `s1` and `s2` are internal state variables that will be used in Momentum, adagrad, RMSProp
x1, x2, s1, s2 = -5, -2, 0, 0
results = [(x1, x2)]
for i in range(steps):
if f_grad:
x1, x2, s1, s2 = trainer(x1, x2, s1, s2, f_grad)
else:
x1, x2, s1, s2 = trainer(x1, x2, s1, s2)
results.append((x1, x2))
print(f'epoch {i + 1}, x1: {float(x1):f}, x2: {float(x2):f}')
return results
def show_trace_2d(f, results): #@save
"""Show the trace of 2D variables during optimization."""
d2l.set_figsize()
d2l.plt.plot(*zip(*results), '-o', color='#ff7f0e')
x1, x2 = torch.meshgrid(torch.arange(-5.5, 1.0, 0.1),
torch.arange(-3.0, 1.0, 0.1), indexing='ij')
d2l.plt.contour(x1, x2, f(x1, x2), colors='#1f77b4')
d2l.plt.xlabel('x1')
d2l.plt.ylabel('x2')
Далее мы наблюдаем за траекторией переменной оптимизации \(\mathbf{x}\) при скорости обучения \(\eta = 0.1\). Мы видим, что после 20 шагов значение \(\mathbf{x}\) приближается к своему минимуму в точке \([0, 0]\). Процесс идёт довольно плавно, хотя и довольно медленно.
def f_2d(x1, x2): # Objective function
return x1 ** 2 + 2 * x2 ** 2
def f_2d_grad(x1, x2): # Gradient of the objective function
return (2 * x1, 4 * x2)
def gd_2d(x1, x2, s1, s2, f_grad):
g1, g2 = f_grad(x1, x2)
return (x1 - eta * g1, x2 - eta * g2, 0, 0)
eta = 0.1
show_trace_2d(f_2d, train_2d(gd_2d, f_grad=f_2d_grad))
12.3.3. Адаптивные методы¶
Как мы видели в Section 12.3.1.1, подобрать скорость обучения \(\eta\) «точно в цель» — задача непростая. Если выбрать её слишком маленькой, прогресс будет минимальным. Если же слишком большой, решение будет осциллировать, а в худшем случае алгоритм может даже расходиться. Что, если бы мы могли определять \(\eta\) автоматически или вовсе отказаться от необходимости выбирать скорость обучения? Методы второго порядка, которые учитывают не только значение и градиент целевой функции, но и её кривизну, могут помочь в этом случае. Хотя эти методы нельзя применять в глубоком обучении напрямую из-за вычислительной сложности, они дают полезное представление о том, как проектировать продвинутые алгоритмы оптимизации, имитирующие многие желательные свойства алгоритмов, описанных ниже.
12.3.3.1. Метод Ньютона¶
Рассмотрев разложение Тейлора некоторой функции \(f: \mathbb{R}^d \rightarrow \mathbb{R}\), нет необходимости ограничиваться первым членом. На самом деле, его можно записать в виде
Чтобы избежать громоздких обозначений, определим \(\mathbf{H} \stackrel{\textrm{def}}{=} \nabla^2 f(\mathbf{x})\) как гессиан функции \(f\), которая является матрицей размера \(d \times d\). Для малых значений \(d\) и простых задач вычисление \(\mathbf{H}\) выполняется легко. С другой стороны, в глубоких нейронных сетях размерность \(\mathbf{H}\) может оказаться чрезмерно большой из-за затрат на хранение \(\mathcal{O}(d^2)\) элементов. Кроме того, её вычисление с помощью обратного распространения ошибки может быть слишком дорогим. Пока что оставим эти соображения в стороне и посмотрим, какой алгоритм мы получим.
В конце концов, минимум функции \(f\) удовлетворяет условию \(\nabla f = 0\). Применяя правила дифференцирования из Section 2.4.3, беря производные от (12.3.8) по \(\boldsymbol{\epsilon}\) и пренебрегая членами более высокого порядка, мы получаем
То есть нам необходимо инвертировать матрицу Гессе \(\mathbf{H}\) в рамках задачи оптимизации.
В качестве простого примера для \(f(x) = \frac{1}{2} x^2\) имеем \(\nabla f(x) = x\) и \(\mathbf{H} = 1\). Следовательно, для любого \(x\) получаем \(\epsilon = -x\). Иными словами, одного шага достаточно для полного схождения без необходимости какой-либо корректировки! Однако здесь нам немного повезло: разложение Тейлора оказалось точным, поскольку \(f(x+\epsilon)= \frac{1}{2} x^2 + \epsilon x + \frac{1}{2} \epsilon^2\).
Рассмотрим, что происходит в других задачах. Для выпуклой функции гиперболического косинуса \(f(x) = \cosh(cx)\) при некоторой константе \(c\) видно, что глобальный минимум в точке \(x=0\) достигается за несколько итераций.
c = torch.tensor(0.5)
def f(x): # Objective function
return torch.cosh(c * x)
def f_grad(x): # Gradient of the objective function
return c * torch.sinh(c * x)
def f_hess(x): # Hessian of the objective function
return c**2 * torch.cosh(c * x)
def newton(eta=1):
x = 10.0
results = [x]
for i in range(10):
x -= eta * f_grad(x) / f_hess(x)
results.append(float(x))
print('epoch 10, x:', x)
return results
show_trace(newton(), f)
Теперь рассмотрим невыпуклую функцию, например, \(f(x) = x \cos(c x)\) при некоторой константе \(c\). Обратите внимание, что в методе Ньютона мы делим на гессиан. Это означает, что если вторая производная отрицательна, мы можем двигаться в направлении увеличения значения \(f\). Это фатальный недостаток алгоритма. Давайте посмотрим, что происходит на практике.
c = torch.tensor(0.15 * np.pi)
def f(x): # Objective function
return x * torch.cos(c * x)
def f_grad(x): # Gradient of the objective function
return torch.cos(c * x) - c * x * torch.sin(c * x)
def f_hess(x): # Hessian of the objective function
return - 2 * c * torch.sin(c * x) - x * c**2 * torch.cos(c * x)
show_trace(newton(), f)
Это пошло совершенно не так. Как это исправить? Один из способов — «исправить» гессиан, заменив его на модуль. Другая стратегия — вернуть скорость обучения. Это, казалось бы, противоречит самой сути метода, но не совсем. Наличие информации второго порядка позволяет нам действовать осторожнее, когда кривизна велика, и делать более длинные шаги, когда целевая функция более плоская. Давайте посмотрим, как это работает при немного меньшей скорости обучения, например, \(\eta = 0.5\). Как мы видим, мы получаем довольно эффективный алгоритм.
show_trace(newton(0.5), f)
12.3.3.2. Анализ сходимости¶
Мы анализируем скорость сходимости метода Ньютона для некоторой выпуклой и трижды дифференцируемой целевой функции \(f\), у которой вторая производная не равна нулю, то есть \(f'' > 0\). Многомерное доказательство является прямым обобщением приведённого ниже одномерного рассуждения и опущено, так как оно мало способствует пониманию интуитивной сути.
Обозначим через \(x^{(k)}\) значение \(x\) на \(k^\textrm{th}\)-й итерации и пусть \(e^{(k)} \stackrel{\textrm{def}}{=} x^{(k)} - x^*\) будет расстоянием до оптимальности на \(k^\textrm{th}\)-й итерации. С помощью разложения в ряд Тейлора получим, что условие \(f'(x^*) = 0\) можно записать в виде
что верно для некоторого \(\xi^{(k)} \in [x^{(k)} - e^{(k)}, x^{(k)}]\). Разделив вышеприведённое разложение на \(f''(x^{(k)})\), получаем
Вспомним, что у нас есть обновление \(x^{(k+1)} = x^{(k)} - f'(x^{(k)}) / f''(x^{(k)})\). Подставив это уравнение обновления и взяв абсолютное значение обеих частей, получим
Следовательно, всякий раз, когда мы находимся в области с ограниченным \(\left|f'''(\xi^{(k)})\right| / (2f''(x^{(k)})) \leq c\), ошибка убывает квадратично
К слову, исследователи в области оптимизации называют это линейной сходимостью, тогда как условие вида \(\left|e^{(k+1)}\right| \leq \alpha \left|e^{(k)}\right|\) соответствовало бы постоянной скорости сходимости. Обратите внимание, что данный анализ имеет ряд оговорок. Во-первых, мы не можем точно гарантировать, когда попадём в область быстрой сходимости. Вместо этого мы лишь знаем, что как только мы её достигнем, сходимость будет очень быстрой. Во-вторых, этот анализ требует, чтобы \(f\) была достаточно гладкой вплоть до производных более высокого порядка. По сути, это означает необходимость убедиться, что \(f\) не обладает какими-либо «неожиданными» свойствами с точки зрения изменения своих значений.
12.3.3.3. Предобуславливание¶
Как и следовало ожидать, вычисление и хранение полной матрицы Гессе требует значительных затрат. Поэтому целесообразно искать альтернативные подходы. Одним из способов улучшения ситуации является предусловливание. Оно позволяет избежать вычисления полной матрицы Гессе, ограничиваясь вычислением только её диагональных элементов. Это приводит к алгоритмам обновления вида
Хотя это и не совсем так хорошо, как полный метод Ньютона, это всё же гораздо лучше, чем отсутствие такого подхода. Чтобы понять, почему это может быть хорошей идеей, рассмотрим ситуацию, в которой одна переменная обозначает высоту в миллиметрах, а другая — в километрах. Предполагая, что естественной шкалой для обеих является метр, мы получаем крайне неудачное несоответствие в параметризации. К счастью, использование предобуславливания устраняет эту проблему. По сути, предобуславливание при градиентном спуске эквивалентно выбору различной скорости обучения для каждой переменной (координаты вектора \(\mathbf{x}\)). Как мы увидим позже, предобуславливание лежит в основе некоторых инноваций в алгоритмах оптимизации на основе стохастического градиентного спуска.
12.3.3.4. Градиентный спуск с поиском по прямой¶
Одна из ключевых проблем градиентного спуска заключается в том, что мы можем перешагнуть через цель или сделать недостаточный шаг. Простым решением этой проблемы является использование поиска по прямой в сочетании с градиентным спуском. То есть мы используем направление, задаваемое \(\nabla f(\mathbf{x})\), а затем выполняем бинарный поиск для определения такой скорости обучения \(\eta\), которая минимизирует \(f(\mathbf{x} - \eta \nabla f(\mathbf{x}))\).
Этот алгоритм сходится быстро (анализ и доказательство см., например, Boyd and Vandenberghe (2004)). Однако в контексте глубокого обучения он не вполне применим, поскольку каждый шаг поиска по прямой потребовал бы вычисления целевой функции на всем наборе данных. Это слишком затратно.
12.3.4. Резюме¶
Скорость обучения имеет значение. Слишком большая скорость приводит к расходимости, слишком малая — к отсутствию прогресса.
Градиентный спуск может застрять в локальных минимумах.
В многомерных пространствах настройка скорости обучения является сложной задачей.
Предусловление может помочь с настройкой масштаба.
Метод Ньютона работает значительно быстрее, как только начинает корректно функционировать в выпуклых задачах.
Будьте осторожны при использовании метода Ньютона без каких-либо корректировок для невыпуклых задач.
12.3.5. Упражнения¶
Экспериментируйте с различными скоростями обучения и функциями потерь для градиентного спуска.
Реализуйте поиск по прямой для минимизации выпуклой функции на интервале \([a, b]\).
Нужны ли нам производные для бинарного поиска, то есть для того, чтобы решить, выбрать ли \([a, (a+b)/2]\) или \([(a+b)/2, b]\).
Как быстро происходит сходимость алгоритма?
Реализуйте алгоритм и примените его для минимизации \(\log (\exp(x) + \exp(-2x -3))\).
Разработайте целевую функцию, заданную на \(\mathbb{R}^2\), для которой градиентный спуск сходится чрезвычайно медленно. Подсказка: масштабируйте различные координаты по-разному.
Реализуйте облегченную версию метода Ньютона с предобуславливанием:
Используйте диагональную матрицу Гессе в качестве предобуславливателя.
Используйте абсолютные значения вместо фактических (возможно, со знаком) значений.
Примените это к задаче выше.
Примените описанный выше алгоритм к нескольким целевым функциям (выпуклым или нет). Что произойдет, если повернуть координаты на \(45\) градусов?