.. _sec_gd: Градиентный спуск ================= В этом разделе мы введем основные понятия, лежащие в основе *градиентного спуска*. Хотя он редко используется напрямую в глубоком обучении, понимание градиентного спуска является ключом к пониманию алгоритмов стохастического градиентного спуска. Например, задача оптимизации может расходиться из-за слишком большой скорости обучения. Это явление уже можно наблюдать при градиентном спуске. Аналогично, предварительная обработка (preconditioning) является распространенной техникой в градиентном спуске и переносится на более сложные алгоритмы. Начнем с простого частного случая. Градиентный спуск в одномерном случае ------------------------------------- Градиентный спуск в одномерном случае — отличный пример, поясняющий, почему алгоритм градиентного спуска способен уменьшать значение целевой функции. Рассмотрим некоторую непрерывно дифференцируемую вещественную функцию :math:`f: \mathbb{R} \rightarrow \mathbb{R}`. Используя разложение Тейлора, получаем .. math:: f(x + \epsilon) = f(x) + \epsilon f'(x) + \mathcal{O}(\epsilon^2). :label: gd-taylor То есть в первой линейной аппроксимации :math:`f(x+\epsilon)` определяется значением функции :math:`f(x)` и первой производной :math:`f'(x)` в точке :math:`x`. Не будет преувеличением предположить, что при малых :math:`\epsilon` движение в направлении отрицательного градиента приведёт к уменьшению :math:`f`. Для простоты мы выберем фиксированный размер шага :math:`\eta > 0` и положим :math:`\epsilon = -\eta f'(x)`. Подставляя это в приведённое выше разложение Тейлора, получаем .. math:: f(x - \eta f'(x)) = f(x) - \eta f'^2(x) + \mathcal{O}(\eta^2 f'^2(x)). :label: gd-taylor-2 Если производная :math:`f'(x) \neq 0` не равна нулю, мы достигаем прогресса, поскольку :math:`\eta f'^2(x)>0`. Более того, мы всегда можем выбрать :math:`\eta` достаточно малым, чтобы членами более высокого порядка можно было пренебречь. Таким образом, мы приходим к .. math:: f(x - \eta f'(x)) \lessapprox f(x). Это означает, что, если мы используем .. math:: x \leftarrow x - \eta f'(x) чтобы выполнить итерацию :math:`x`, значение функции :math:`f(x)` может уменьшаться. Поэтому в градиентном спуске мы сначала выбираем начальное значение :math:`x` и константу :math:`\eta > 0`, а затем используем их для непрерывной итерации :math:`x` до тех пор, пока не будет выполнено условие остановки, например, когда величина градиента :math:`|f'(x)|` становится достаточно малой или количество итераций достигает определённого значения. Для простоты мы выберем целевую функцию :math:`f(x)=x^2`, чтобы проиллюстрировать реализацию градиентного спуска. Хотя нам известно, что :math:`x=0` является решением задачи минимизации :math:`f(x)`, мы всё равно используем эту простую функцию, чтобы наблюдать за изменением :math:`x`. .. raw:: latex \diilbookstyleinputcell .. code:: python %matplotlib inline import numpy as np import torch from d2l import torch as d2l .. raw:: latex \diilbookstyleinputcell .. code:: python def f(x): # Objective function return x ** 2 def f_grad(x): # Gradient (derivative) of the objective function return 2 * x Далее мы используем :math:`x=10` в качестве начального значения и предполагаем :math:`\eta=0.2`. Выполняя итерации градиентного спуска :math:`x` 10 раз, мы видим, что в итоге значение :math:`x` приближается к оптимальному решению. .. raw:: latex \diilbookstyleinputcell .. code:: python 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) Ход оптимизации по :math:`x` можно изобразить следующим образом. .. raw:: latex \diilbookstyleinputcell .. code:: python 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) .. _subsec_gd-learningrate: Скорость обучения ~~~~~~~~~~~~~~~~~ Скорость обучения :math:`\eta` задается разработчиком алгоритма. Если использовать слишком малую скорость обучения, это приведет к тому, что :math:`x` будет обновляться очень медленно, и для нахождения лучшего решения потребуется больше итераций. Чтобы проиллюстрировать, что происходит в таком случае, рассмотрим ход решения той же задачи оптимизации для :math:`\eta = 0.05`. Как видно, даже после 10 шагов мы все ещё очень далеки от оптимального решения. .. raw:: latex \diilbookstyleinputcell .. code:: python show_trace(gd(0.05, f_grad), f) С другой стороны, если использовать слишком высокую скорость обучения, :math:`\left|\eta f'(x)\right|` может оказаться слишком большим для формулы разложения Тейлора первого порядка. Это означает, что член :math:`\mathcal{O}(\eta^2 f'^2(x))` в :eq:`gd-taylor-2` может стать значительным. В этом случае мы не можем гарантировать, что итерация :math:`x` позволит уменьшить значение :math:`f(x)`. Например, при задании скорости обучения равной :math:`\eta=1.1`, :math:`x` перелетает через оптимальное решение :math:`x=0` и постепенно расходится. .. raw:: latex \diilbookstyleinputcell .. code:: python show_trace(gd(1.1, f_grad), f) Локальные минимумы ~~~~~~~~~~~~~~~~~~ Чтобы проиллюстрировать, что происходит с невыпуклыми функциями, рассмотрим случай :math:`f(x) = x \cdot \cos(cx)` для некоторой константы :math:`c`. Эта функция имеет бесконечно много локальных минимумов. В зависимости от выбранной скорости обучения и от того, насколько хорошо обусловлена задача, мы можем получить одно из множества решений. Приведённый ниже пример показывает, как (нереалистично) высокая скорость обучения приводит к плохому локальному минимуму. .. raw:: latex \diilbookstyleinputcell .. code:: python 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) Многомерный градиентный спуск ----------------------------- Теперь, когда у нас есть лучшее понимание одномерного случая, рассмотрим ситуацию, когда :math:`\mathbf{x} = [x_1, x_2, \ldots, x_d]^\top`. То есть целевая функция :math:`f: \mathbb{R}^d \to \mathbb{R}` отображает векторы в скаляры. Соответственно, её градиент также является многомерным. Это вектор, состоящий из :math:`d` частных производных: .. math:: \nabla f(\mathbf{x}) = \bigg[\frac{\partial f(\mathbf{x})}{\partial x_1}, \frac{\partial f(\mathbf{x})}{\partial x_2}, \ldots, \frac{\partial f(\mathbf{x})}{\partial x_d}\bigg]^\top. Каждый элемент :math:`\partial f(\mathbf{x})/\partial x_i` градиента, являющийся частной производной, указывает на скорость изменения :math:`f` в точке :math:`\mathbf{x}` по отношению к входной переменной :math:`x_i`. Как и в случае одной переменной, мы можем использовать соответствующее разложение Тейлора для многомерных функций, чтобы получить представление о том, что следует делать. В частности, имеем: .. math:: f(\mathbf{x} + \boldsymbol{\epsilon}) = f(\mathbf{x}) + \mathbf{\boldsymbol{\epsilon}}^\top \nabla f(\mathbf{x}) + \mathcal{O}(\|\boldsymbol{\epsilon}\|^2). :label: gd-multi-taylor Иными словами, с точностью до членов второго порядка в :math:`\boldsymbol{\epsilon}` направление наискорейшего спуска определяется отрицательным градиентом :math:`-\nabla f(\mathbf{x})`. Выбор подходящей скорости обучения :math:`\eta > 0` приводит к классическому алгоритму градиентного спуска: .. math:: \mathbf{x} \leftarrow \mathbf{x} - \eta \nabla f(\mathbf{x}). Чтобы понять, как алгоритм ведет себя на практике, построим целевую функцию :math:`f(\mathbf{x})=x_1^2+2x_2^2` с двумерным вектором :math:`\mathbf{x} = [x_1, x_2]^\top` в качестве входных данных и скаляром в качестве выходных. Градиент задается выражением :math:`\nabla f(\mathbf{x}) = [2x_1, 4x_2]^\top`. Мы будем наблюдать за траекторией :math:`\mathbf{x}` градиентного спуска, начиная с начальной точки :math:`[-5, -2]`. Для начала нам понадобятся две вспомогательные функции. Первая использует функцию обновления и применяет её 20 раз к начальному значению. Вторая вспомогательная функция визуализирует траекторию :math:`\mathbf{x}`. .. raw:: latex \diilbookstyleinputcell .. code:: python 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 .. raw:: latex \diilbookstyleinputcell .. code:: python 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') Далее мы наблюдаем за траекторией переменной оптимизации :math:`\mathbf{x}` при скорости обучения :math:`\eta = 0.1`. Мы видим, что после 20 шагов значение :math:`\mathbf{x}` приближается к своему минимуму в точке :math:`[0, 0]`. Процесс идёт довольно плавно, хотя и довольно медленно. .. raw:: latex \diilbookstyleinputcell .. code:: python 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)) Адаптивные методы ----------------- Как мы видели в :numref:`subsec_gd-learningrate`, подобрать скорость обучения :math:`\eta` «точно в цель» — задача непростая. Если выбрать её слишком маленькой, прогресс будет минимальным. Если же слишком большой, решение будет осциллировать, а в худшем случае алгоритм может даже расходиться. Что, если бы мы могли определять :math:`\eta` автоматически или вовсе отказаться от необходимости выбирать скорость обучения? Методы второго порядка, которые учитывают не только значение и градиент целевой функции, но и её *кривизну*, могут помочь в этом случае. Хотя эти методы нельзя применять в глубоком обучении напрямую из-за вычислительной сложности, они дают полезное представление о том, как проектировать продвинутые алгоритмы оптимизации, имитирующие многие желательные свойства алгоритмов, описанных ниже. Метод Ньютона ~~~~~~~~~~~~~ Рассмотрев разложение Тейлора некоторой функции :math:`f: \mathbb{R}^d \rightarrow \mathbb{R}`, нет необходимости ограничиваться первым членом. На самом деле, его можно записать в виде .. math:: f(\mathbf{x} + \boldsymbol{\epsilon}) = f(\mathbf{x}) + \boldsymbol{\epsilon}^\top \nabla f(\mathbf{x}) + \frac{1}{2} \boldsymbol{\epsilon}^\top \nabla^2 f(\mathbf{x}) \boldsymbol{\epsilon} + \mathcal{O}(\|\boldsymbol{\epsilon}\|^3). :label: gd-hot-taylor Чтобы избежать громоздких обозначений, определим :math:`\mathbf{H} \stackrel{\textrm{def}}{=} \nabla^2 f(\mathbf{x})` как гессиан функции :math:`f`, которая является матрицей размера :math:`d \times d`. Для малых значений :math:`d` и простых задач вычисление :math:`\mathbf{H}` выполняется легко. С другой стороны, в глубоких нейронных сетях размерность :math:`\mathbf{H}` может оказаться чрезмерно большой из-за затрат на хранение :math:`\mathcal{O}(d^2)` элементов. Кроме того, её вычисление с помощью обратного распространения ошибки может быть слишком дорогим. Пока что оставим эти соображения в стороне и посмотрим, какой алгоритм мы получим. В конце концов, минимум функции :math:`f` удовлетворяет условию :math:`\nabla f = 0`. Применяя правила дифференцирования из :numref:`subsec_calculus-grad`, беря производные от :eq:`gd-hot-taylor` по :math:`\boldsymbol{\epsilon}` и пренебрегая членами более высокого порядка, мы получаем .. math:: \nabla f(\mathbf{x}) + \mathbf{H} \boldsymbol{\epsilon} = 0 \textrm{ and hence } \boldsymbol{\epsilon} = -\mathbf{H}^{-1} \nabla f(\mathbf{x}). То есть нам необходимо инвертировать матрицу Гессе :math:`\mathbf{H}` в рамках задачи оптимизации. В качестве простого примера для :math:`f(x) = \frac{1}{2} x^2` имеем :math:`\nabla f(x) = x` и :math:`\mathbf{H} = 1`. Следовательно, для любого :math:`x` получаем :math:`\epsilon = -x`. Иными словами, *одного* шага достаточно для полного схождения без необходимости какой-либо корректировки! Однако здесь нам немного повезло: разложение Тейлора оказалось точным, поскольку :math:`f(x+\epsilon)= \frac{1}{2} x^2 + \epsilon x + \frac{1}{2} \epsilon^2`. Рассмотрим, что происходит в других задачах. Для выпуклой функции гиперболического косинуса :math:`f(x) = \cosh(cx)` при некоторой константе :math:`c` видно, что глобальный минимум в точке :math:`x=0` достигается за несколько итераций. .. raw:: latex \diilbookstyleinputcell .. code:: python 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) Теперь рассмотрим *невыпуклую* функцию, например, :math:`f(x) = x \cos(c x)` при некоторой константе :math:`c`. Обратите внимание, что в методе Ньютона мы делим на гессиан. Это означает, что если вторая производная *отрицательна*, мы можем двигаться в направлении *увеличения* значения :math:`f`. Это фатальный недостаток алгоритма. Давайте посмотрим, что происходит на практике. .. raw:: latex \diilbookstyleinputcell .. code:: python 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) Это пошло совершенно не так. Как это исправить? Один из способов — «исправить» гессиан, заменив его на модуль. Другая стратегия — вернуть скорость обучения. Это, казалось бы, противоречит самой сути метода, но не совсем. Наличие информации второго порядка позволяет нам действовать осторожнее, когда кривизна велика, и делать более длинные шаги, когда целевая функция более плоская. Давайте посмотрим, как это работает при немного меньшей скорости обучения, например, :math:`\eta = 0.5`. Как мы видим, мы получаем довольно эффективный алгоритм. .. raw:: latex \diilbookstyleinputcell .. code:: python show_trace(newton(0.5), f) Анализ сходимости ~~~~~~~~~~~~~~~~~ Мы анализируем скорость сходимости метода Ньютона для некоторой выпуклой и трижды дифференцируемой целевой функции :math:`f`, у которой вторая производная не равна нулю, то есть :math:`f'' > 0`. Многомерное доказательство является прямым обобщением приведённого ниже одномерного рассуждения и опущено, так как оно мало способствует пониманию интуитивной сути. Обозначим через :math:`x^{(k)}` значение :math:`x` на :math:`k^\textrm{th}`-й итерации и пусть :math:`e^{(k)} \stackrel{\textrm{def}}{=} x^{(k)} - x^*` будет расстоянием до оптимальности на :math:`k^\textrm{th}`-й итерации. С помощью разложения в ряд Тейлора получим, что условие :math:`f'(x^*) = 0` можно записать в виде .. math:: 0 = f'(x^{(k)} - e^{(k)}) = f'(x^{(k)}) - e^{(k)} f''(x^{(k)}) + \frac{1}{2} (e^{(k)})^2 f'''(\xi^{(k)}), что верно для некоторого :math:`\xi^{(k)} \in [x^{(k)} - e^{(k)}, x^{(k)}]`. Разделив вышеприведённое разложение на :math:`f''(x^{(k)})`, получаем .. math:: e^{(k)} - \frac{f'(x^{(k)})}{f''(x^{(k)})} = \frac{1}{2} (e^{(k)})^2 \frac{f'''(\xi^{(k)})}{f''(x^{(k)})}. Вспомним, что у нас есть обновление :math:`x^{(k+1)} = x^{(k)} - f'(x^{(k)}) / f''(x^{(k)})`. Подставив это уравнение обновления и взяв абсолютное значение обеих частей, получим .. math:: \left|e^{(k+1)}\right| = \frac{1}{2}(e^{(k)})^2 \frac{\left|f'''(\xi^{(k)})\right|}{f''(x^{(k)})}. Следовательно, всякий раз, когда мы находимся в области с ограниченным :math:`\left|f'''(\xi^{(k)})\right| / (2f''(x^{(k)})) \leq c`, ошибка убывает квадратично .. math:: \left|e^{(k+1)}\right| \leq c (e^{(k)})^2. К слову, исследователи в области оптимизации называют это *линейной* сходимостью, тогда как условие вида :math:`\left|e^{(k+1)}\right| \leq \alpha \left|e^{(k)}\right|` соответствовало бы *постоянной* скорости сходимости. Обратите внимание, что данный анализ имеет ряд оговорок. Во-первых, мы не можем точно гарантировать, когда попадём в область быстрой сходимости. Вместо этого мы лишь знаем, что как только мы её достигнем, сходимость будет очень быстрой. Во-вторых, этот анализ требует, чтобы :math:`f` была достаточно гладкой вплоть до производных более высокого порядка. По сути, это означает необходимость убедиться, что :math:`f` не обладает какими-либо «неожиданными» свойствами с точки зрения изменения своих значений. Предобуславливание ~~~~~~~~~~~~~~~~~~ Как и следовало ожидать, вычисление и хранение полной матрицы Гессе требует значительных затрат. Поэтому целесообразно искать альтернативные подходы. Одним из способов улучшения ситуации является *предусловливание*. Оно позволяет избежать вычисления полной матрицы Гессе, ограничиваясь вычислением только её *диагональных* элементов. Это приводит к алгоритмам обновления вида .. math:: \mathbf{x} \leftarrow \mathbf{x} - \eta \textrm{diag}(\mathbf{H})^{-1} \nabla f(\mathbf{x}). Хотя это и не совсем так хорошо, как полный метод Ньютона, это всё же гораздо лучше, чем отсутствие такого подхода. Чтобы понять, почему это может быть хорошей идеей, рассмотрим ситуацию, в которой одна переменная обозначает высоту в миллиметрах, а другая — в километрах. Предполагая, что естественной шкалой для обеих является метр, мы получаем крайне неудачное несоответствие в параметризации. К счастью, использование предобуславливания устраняет эту проблему. По сути, предобуславливание при градиентном спуске эквивалентно выбору различной скорости обучения для каждой переменной (координаты вектора :math:`\mathbf{x}`). Как мы увидим позже, предобуславливание лежит в основе некоторых инноваций в алгоритмах оптимизации на основе стохастического градиентного спуска. Градиентный спуск с поиском по прямой ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~ Одна из ключевых проблем градиентного спуска заключается в том, что мы можем перешагнуть через цель или сделать недостаточный шаг. Простым решением этой проблемы является использование поиска по прямой в сочетании с градиентным спуском. То есть мы используем направление, задаваемое :math:`\nabla f(\mathbf{x})`, а затем выполняем бинарный поиск для определения такой скорости обучения :math:`\eta`, которая минимизирует :math:`f(\mathbf{x} - \eta \nabla f(\mathbf{x}))`. Этот алгоритм сходится быстро (анализ и доказательство см., например, :cite:t:`Boyd.Vandenberghe.2004`). Однако в контексте глубокого обучения он не вполне применим, поскольку каждый шаг поиска по прямой потребовал бы вычисления целевой функции на всем наборе данных. Это слишком затратно. Резюме ------ - Скорость обучения имеет значение. Слишком большая скорость приводит к расходимости, слишком малая — к отсутствию прогресса. - Градиентный спуск может застрять в локальных минимумах. - В многомерных пространствах настройка скорости обучения является сложной задачей. - Предусловление может помочь с настройкой масштаба. - Метод Ньютона работает значительно быстрее, как только начинает корректно функционировать в выпуклых задачах. - Будьте осторожны при использовании метода Ньютона без каких-либо корректировок для невыпуклых задач. Упражнения ---------- 1. Экспериментируйте с различными скоростями обучения и функциями потерь для градиентного спуска. 2. Реализуйте поиск по прямой для минимизации выпуклой функции на интервале :math:`[a, b]`. 1. Нужны ли нам производные для бинарного поиска, то есть для того, чтобы решить, выбрать ли :math:`[a, (a+b)/2]` или :math:`[(a+b)/2, b]`. 2. Как быстро происходит сходимость алгоритма? 3. Реализуйте алгоритм и примените его для минимизации :math:`\log (\exp(x) + \exp(-2x -3))`. 3. Разработайте целевую функцию, заданную на :math:`\mathbb{R}^2`, для которой градиентный спуск сходится чрезвычайно медленно. Подсказка: масштабируйте различные координаты по-разному. 4. Реализуйте облегченную версию метода Ньютона с предобуславливанием: 1. Используйте диагональную матрицу Гессе в качестве предобуславливателя. 2. Используйте абсолютные значения вместо фактических (возможно, со знаком) значений. 3. Примените это к задаче выше. 5. Примените описанный выше алгоритм к нескольким целевым функциям (выпуклым или нет). Что произойдет, если повернуть координаты на :math:`45` градусов? `Обсуждения `__