Градиентный спуск

Оптимизаторы важный компонент архитектуры нейронных сетей. Они играют важную роль в процессе тренировки нейронных сетей, помогая им делать всё более точные прогнозы. Специально к старту нового потока расширенного курса помашинному и глубокому обучению, делимся с вами простым описанием основных методик, используемых оптимизаторами градиентного спуска, такими как SGD, Momentum, RMSProp, Adam и др.

Оптимизаторы определяют оптимальный набор параметров модели, таких как вес и смещение, чтобы при решении конкретной задачи модель выдавала наилучшие результаты.

Самой распространённой техникой оптимизации, используемой большинством нейронных сетей, является алгоритм градиентного спуска.

Большинство популярных библиотек глубокого обучения, например PyTorch и Keras, имеют множество встроенных оптимизаторов, базирующихся на использовании алгоритма градиентного спуска, например SGD, Adadelta, Adagrad, RMSProp, Adam и пр.

Но почему алгоритмов оптимизации так много? Как выбрать из них правильный?

В документации к каждому из таких оптимизаторов приводится формула, с помощью которой такие оптимизаторы обновляют параметры модели. Что же означает каждая формула, и в чём её смысл?

Хочу уточнить, что данная статья написана для того, чтобы вы поняли общую картину и как в такую картину вписывается каждый алгоритм. Я не буду здесь погружаться в глубинные смыслы самих формул, так как рассуждать о математических тонкостях лучше всего в отдельной статье.

Обзор методов оптимизации на базе алгоритма градиентного спуска

Кривая потерь

Начнём с того, что рассмотрим на 3D-изображении, как работает стандартный алгоритм градиентного спуска.

На рисунке показана сеть с двумя весовыми параметрами:

• На горизонтальной плоскости размещаются две оси для весов w1 и w2, соответственно.

• На вертикальной оси откладываются значения потерь для каждого сочетания весов.

Другими словами, форма кривой является отражением ландшафта потерь в нейронной сети. Кривая представляет потери для различных значений весов при сохранении неизменным фиксированного набора входных данных.

Синяя линия соответствует траектории алгоритма градиентного спуска при оптимизации:

• Работа алгоритма начинается с выбора некоторых случайных значений обоих весов и вычисления значения потери.

• После каждой итерации весовые значения будут обновляться (в результате чего, как можно надеяться, снизится потеря), и алгоритм будет перемещаться вдоль кривой к следующей (более нижней) точке.

• В конечном итоге алгоритм достигает цели, то есть приходит в нижнюю точку кривой в точку с самым низким значением потерь.

Вычисление градиента

Алгоритм обновляет значения весов, основываясь на значениях градиента кривой потерь в данной точке, и на параметре скорости обучения.

Градиент измеряет уклон и рассчитывается как значение изменения в вертикальном направлении (dL), поделённое на значение изменения горизонтальном направлении (dW). Другими словами, для крутых уклонов значение градиента большое, для пологих маленькое.

Практическое применение алгоритма градиентного спуска

Визуальное представление кривых потерь весьма полезно для понимания сути работы алгоритма градиентного спуска. Однако нужно помнить, что описываемый сценарий скорее идеален, чем реален.

• Во-первых, на приведённом выше рисунке кривая потерь идёт идеально плавно. На самом деле горбов и впадин на ней гораздо больше, чем плавных мест.

• Во-вторых, мы будем работать не с двумя параметрами, а с гораздо большим их числом. Параметров может быть десятки или даже сотни миллионов, их просто невозможно визуализировать и представить даже мысленно.

На каждой итерации алгоритм градиентного спуска работает, "озираясь по всем направлениям, находя самый перспективный уклон, по которому можно спуститься вниз". Но что произойдёт, если алгоритм выберет лучший, по его мнению, уклон, но это будет не лучшее направление? Что делать, если:

• Ландшафт круто уходит вниз в одном направлении, но, чтобы попасть в самую нижнюю точку, нужно двигаться в направлении с меньшими изменениями высоты?

• Весь ландшафт представляется алгоритму плоским во всех направлениях?

• Алгоритм попадает в глубокую канаву? Как ему оттуда выбраться?

Давайте рассмотрим несколько примеров кривых, перемещение по которым может создавать трудности.

Трудности при оптимизации градиентного спуска

Локальные минимумы

На стандартной кривой потерь, кроме глобального минимума, может встретиться множество локальных минимумов. Главной задачей алгоритма градиентного спуска, как следует из его названия, является спуск всё ниже и ниже. Но, стоит ему спуститься до локального минимума и подняться оттуда наверх часто становится непосильной задачей. Алгоритм может просто застрять в локальном минимуме, так и не попав на глобальный минимум.

Седловые точки

Ещё одной важной проблемой является прохождение алгоритмом "седловых точек". Седловой называют точку, в которой в одном направлении, соответствующем одному параметру, кривая находится на локальном минимуме; во втором же направлении, соответствующем другому параметру, кривая находится на локальном максимуме.

Какую опасность таят в себе седловые точки, которые алгоритм может встретить на своём пути? Опасность в том, что область, непосредственно окружающая седловую точку, как правило, довольно плоская, она напоминает плато. Плоская область означает практически нулевые градиенты. Оптимизатор начинает колебаться (осциллировать) вокруг седловой точки в направлении первого параметра, не догадываясь спуститься вниз по уклону в направлении второго параметра.

Алгоритм градиентного спуска при этом ошибочно полагает, что минимум им найден.

Овраги

Ещё одна головная боль алгоритма градиентного спуска пересечение оврагов. Овраг это протяжённая узкая долина, имеющая крутой уклон в одном направлении (т.е. по сторонам долины) и плавный уклон в другом (т.е. вдоль долины). Довольно часто овраг приводит к минимуму. Поскольку навигация по такой форме кривой затруднена, такую кривую часто называют патологическим искривлением (Pathological Curvature).

Представьте узкую речную долину, плавно спускающуюся с холмов и простирающуюся вниз до озера. Вам нужно быстро спуститься вниз по реке, туда, где пролегает долина. Но алгоритм градиентного спуска вполне может начать движение, отталкиваясь попеременно от сторон долины, при этом движение вниз по направлению реки будет весьма медленным.

Алгоритм ванильного градиентного спуска, несмотря на его недостатки, по-прежнему считается основным, в частности, по той причине, что существуют специальные методы его оптимизации.

Первое улучшение алгоритма градиентного спуска стохастический градиентный спуск (SGD)

Под обычным градиентным спуском (по умолчанию) обычно понимается "градиентный спуск со сменой коэффициентов после обсчёта всей выборки", то есть потери и градиент рассчитываются с использованием всех элементов набора данных.

Также применяется промежуточный стохастический градиентный спуск с мини-пакетами вариант, при котором коэффициенты меняются после обсчета N элементов выборки, то есть для каждой тренировочной итерации алгоритм выбирает случайное подмножество набора данных.

Случайность выбора хороша тем, что она помогает глубже исследовать ландшафт потерь.

Ранее мы говорили, что кривая потерь получается за счёт изменения параметров модели с сохранением фиксированного набора входных данных. Однако если начать изменять входные данные, выбирая различные данные в каждом мини-пакете, значения потерь и градиентов также будут меняться. Другими словами, изменяя набор входных данных, для каждого мини-пакета мы получим собственную кривую потерь, которая немного отличается от других.

То есть, даже если алгоритм застрянет на каком-либо месте ландшафта в одном мини-пакете, можно будет запустить другой мини-пакет с другим ландшафтом, и вполне вероятно, что алгоритм сможет двигаться дальше. Данная техника предотвращает застревание алгоритма на определённых участках ландшафта, особенно на ранних этапах тренировки.

Второе усовершенствование алгоритма градиентного спуска накопление импульса (Momentum)

Динамическая корректировка количества обновлений

Один из интересных аспектов алгоритма градиентного спуска связан с его поведением на крутых уклонах. Так как градиент на крутых уклонах большой, алгоритм в этих местах может делать большие шаги, между тем, именно здесь вы на самом деле хотите перемещаться медленно и осторожно. Это может привести к тому, что алгоритм будет "скакать" назад и вперёд, замедляя тем самым процесс тренировки.

В идеале частоту обновлений хочется изменять динамически, чтобы алгоритм мог подстраиваться под изменения окружающего ландшафта. Если уклон очень крутой, алгоритм должен притормаживать. Если склон довольно пологий, скорость вполне можно повысить, и так далее.

Алгоритм градиентного спуска обновляет веса на каждом шаге, используя в качестве параметров значения градиента и скорости обучения. Таким образом, для изменения количества обновлений можно выполнить два действия:

• Скорректировать градиент.

• Скорректировать значение скорости обучения.

SGD с функцией накопления импульса и обычный SGD

Первое действие, то есть корректировка градиента, выполняется с помощью функции накопления импульса.

В SGD учитывается только текущее значение градиента, а значения всех прошлых градиентов игнорируются. Это означает, что, если алгоритм внезапно натолкнётся на аномалию на кривой потерь, он может пойти не по нужной траектории.

С другой стороны, при использовании SGD с накоплением импульса учитываются значения прошлых градиентов, общее направление сохраняется, и траектория остаётся правильной. Это позволяет использовать знания об окружающем ландшафте, полученные алгоритмом до того, как он добрался до данной точки, и смягчить эффект аномалии кривой потерь.

1. Сразу встаёт вопрос как далеко можно углубляться в прошлое? Чем глубже мы погрузимся в прошлое, тем меньше вероятность воздействия аномалий на конечный результат.

2. И второй вопрос все ли градиенты из прошлого можно расценивать одинаково? Вполне логично рассудить, что вещи из недавнего прошлого должны иметь более высокую значимость, чем вещи из далёкого прошлого. Поэтому, если изменение ландшафта представляет собой не аномалию, а естественное структурное изменение, на такие изменения нужно реагировать соответственно и менять курс постепенно.

Функция накопления импульса использует при работе экспоненциальное скользящее среднее, а не текущее значение градиента.

Переходы через овраги с помощью функции накопления импульса

Функция накопления импульса помогает решить проблему узкого оврага с патологическим искривлением, градиент которого, с одной стороны, очень большой для одного весового параметра, а, с другой стороны, очень маленький для другого параметра.

С помощью функции накопления импульса можно сгладить зигзагообразные скачки алгоритма SGD.

• Для первого параметра с крутым уклоном большое значение градиента приведёт к резкому повороту от одной стороны оврага к другой. Однако на следующем шаге такое перемещение будет скомпенсировано резким поворотом в обратном направлении.

• Если же взять другой параметр, мелкие обновления на первом шаге будут усиливаться мелкими обновлениями на втором шаге, так как эти обновления имеют то же направление. И именно такое направление вдоль оврага будет направлением, в котором необходимо двигаться алгоритму.

Вот некоторые примеры алгоритмов оптимизации, использующих функцию накопления импульса в разных формулах:

• SGD с накоплением импульса

• Ускоренный градиент Нестерова

Третье усовершенствование алгоритма градиентного спуска изменение скорости обучения (на базе значения градиента)

Как уже было сказано выше, вторым способом изменения количества обновлений параметров является изменение скорости обучения.

До сих пор на разных итерациях мы сохраняли скорость обучения постоянной. Кроме того, при обновлении градиентов для всех параметров использовалось одно и то же значение скорости обучения.

Однако, как мы уже убедились, градиенты с различными параметрами могут довольно ощутимо отличаться друг от друга. Один параметр может иметь крутой уклон, а другой пологий.

Мы можем использовать это обстоятельство, чтобы адаптировать скорость обучения к каждому параметру. Чтобы выбрать скорость обучения для данного параметра, мы можем обратиться к прошлым градиентам (для каждого параметра отдельно).

Данная функциональность реализована в нескольких алгоритмах оптимизации, использующих разные, но похожие методы, например Adagrad, Adadelta, RMS Prop.

Например, метод Adagrad возводит в квадрат значения прошлых градиентов и суммирует их в равных весовых пропорциях. Метод RMSProp также возводит в квадрат значения прошлых градиентов, но приводит их к экспоненциальному скользящему среднему, тем самым придавая более высокую значимость последним по времени градиентам.

После возведения градиентов в квадрат все они становятся положительными, то есть получают одно и то же направление. Таким образом, перестаёт действовать эффект, проявляющийся при применении функции накопления импульса (градиенты имеют противоположные направления).

Это означает, что для параметра с крутым уклоном значения градиентов будут большими, и возведение таких значений в квадрат даст ещё большее и всегда положительное значение, поэтому такие градиенты быстро накапливаются. Для погашения данного эффекта алгоритм рассчитывает скорость обучения посредством деления накопленных квадратов градиентов на коэффициент с большим значением. За счет этого алгоритм притормаживает на крутых уклонах.

Рассуждая аналогично, если уклоны небольшие, накопления также будут небольшими, поэтому при вычислении скорости обучения алгоритм разделит накопленные квадраты градиентов на коэффициент с меньшим значением. Таким образом, скорость обучения на пологих склонах будет увеличена.

Некоторые алгоритмы оптимизации используют сразу оба подхода изменяют скорость обучения, как это описано выше, и меняют градиент с помощью функции накопления импульса. Так поступает, например, алгоритм Adam и его многочисленные варианты, а также алгоритм LAMB.

Четвёртое усовершенствование алгоритма градиентного спуска изменение скорости обучения (на базе тренировочной выборки)

В предыдущем разделе скорость обучения менялась на основе градиентов параметров. Плюс к этому, мы можем менять скорость обучения в зависимости от того, как продвигается процесс тренировки. Скорость обучения устанавливается в зависимости от эпохи тренировочного процесса и не зависит от параметров модели в данной точке.

На самом деле эту задачу выполняет не оптимизатор, а особый компонент нейронной сети, называемый планировщиком. Я упоминаю здесь об этом только для полноты картины и для того, чтобы показать связь с техниками оптимизации, о которых мы здесь говорили. Саму же эту тему логично осветить в отдельной статье.

Заключение

Мы ознакомились с основными приёмами, используемыми методиками оптимизации на базе алгоритма градиентного спуска, рассмотрели причины их использования и взаимосвязи друг с другом. Представленная информация позволит лучше понять принцип действия многих специфических алгоритмов оптимизации. А если вы хотите получить больше знаний обратите внимание на наш расширенныйкурс по машинному и глубокому обучению, в рамках которого вы научитесь строить собственные нейронные нейронные сети и решать различные задачи с их помощью.

Узнайте, как прокачаться и в других специальностях или освоить их с нуля:

• Профессия Data Scientist

• Профессия Data Analyst

• Курс по Data Engineering

• Курс "Алгоритмы и структуры данных"

Задача и требования

• Основная цель - создать алгоритм, который найдет максимальное значение по модулю минимума на заданном радиусе.

• Алгоритм должен быть эффективным и работать достаточно быстро

• Результат должен быть отображен на графике

Введение, описание алгоритма

Рабочая область функции (заданный интервал) разбита на несколько точек. Выбраны точки локальных минимумов. После этого все координаты передаются функции в качестве аргументов и выбирается аргумент, дающий наименьшее значение. Затем применяется метод градиентного спуска.

Реализация

Прежде всего, numpy необходим для функций sinus, cosinus и exp. Также необходимо добавить matplotlib для построения графиков.

import numpy as npimport matplotlib.pyplot as plot

Константы

radius = 8                                  # working plane radiuscentre = (global_epsilon, global_epsilon)   # centre of the working circlearr_shape = 100                             # number of points processed / 360step = radius / arr_shape                   # step between two points

arr_shape должна быть 100, потому что, если она больше, программа начинает работать значительно медленнее. И не может быть меньше, иначе это испортит расчеты.

Функция, для которой рассчитывается минимум:

def differentiable_function(x, y):    return np.sin(x) * np.exp((1 - np.cos(y)) ** 2) + \           np.cos(y) * np.exp((1 - np.sin(x)) ** 2) + (x - y) ** 2

Затем выбирается приращение аргумента:

Поскольку предел аргумента стремится к нулю, точность должна быть небольшой по сравнению с радиусом рабочей плоскости:

global_epsilon = 0.000000001                # argument increment for derivative

Для дальнейшего разбиения плоскости необходим поворот вектора:

Если вращение применяется к вектору (x, 0), повернутый вектор будет вычисляться следующим образом:

def rotate_vector(length, a):    return length * np.cos(a), length * np.sin(a)

Расчет производной по оси Y, где эпсилон - значение y:

def derivative_y(epsilon, arg):    return (differentiable_function(arg, epsilon + global_epsilon) -            differentiable_function(arg, epsilon)) / global_epsilon

Вычисление производной по оси X, где эпсилон - значение x:

def derivative_x(epsilon, arg):    return (differentiable_function(global_epsilon + epsilon, arg) -            differentiable_function(epsilon, arg)) / global_epsilon

Расчет градиента:

Поскольку градиент вычисляется для 2D-функции, k равно нулю

gradient = derivative_x(x, y) + derivative_y(y, x)

Схема генерации точек

Возвращаемое значение представляет собой массив приблизительных локальных минимумов.

Локальный минимум распознается по смене знака производной с минуса на плюс. Подробнее об этом здесь: https://en.wikipedia.org/wiki/Maxima_and_minima

def calculate_flip_points():    flip_points = np.array([0, 0])    points = np.zeros((360, arr_shape), dtype=bool)    cx, cy = centre    for i in range(arr_shape):        for alpha in range(360):            x, y = rotate_vector(step, alpha)            x = x * i + cx            y = y * i + cy            points[alpha][i] = derivative_x(x, y) + derivative_y(y, x) > 0            if not points[alpha][i - 1] and points[alpha][i]:                flip_points = np.vstack((flip_points, np.array([alpha, i - 1])))    return flip_points

Выбор точки из flip_points, значение функции от которой минимально:

def pick_estimates(positions):    vx, vy = rotate_vector(step, positions[1][0])    cx, cy = centre    best_x, best_y = cx + vx * positions[1][1], cy + vy * positions[1][1]    for index in range(2, len(positions)):        vx, vy = rotate_vector(step, positions[index][0])        x, y = cx + vx * positions[index][1], cy + vy * positions[index][1]        if differentiable_function(best_x, best_y) > differentiable_function(x, y):            best_x = x            best_y = y    for index in range(360):        vx, vy = rotate_vector(step, index)        x, y = cx + vx * (arr_shape - 1), cy + vy * (arr_shape - 1)        if differentiable_function(best_x, best_y) > differentiable_function(x, y):            best_x = x            best_y = y    return best_x, best_y

Метод градиентного спуска:

def gradient_descent(best_estimates, is_x):    derivative = derivative_x if is_x else derivative_y    best_x, best_y = best_estimates    descent_step = step    value = derivative(best_y, best_x)    while abs(value) > global_epsilon:        descent_step *= 0.95        best_y = best_y - descent_step \            if derivative(best_y, best_x) > 0 else best_y + descent_step        value = derivative(best_y, best_x)    return best_y, best_x

Нахождение точки минимума:

def find_minimum():    return gradient_descent(gradient_descent(pick_estimates(calculate_flip_points()), False), True)

Формирование сетки точек для построения:

def get_grid(grid_step):    samples = np.arange(-radius, radius, grid_step)    x, y = np.meshgrid(samples, samples)    return x, y, differentiable_function(x, y)

Построение графика:

def draw_chart(point, grid):    point_x, point_y, point_z = point    grid_x, grid_y, grid_z = grid    plot.rcParams.update({        'figure.figsize': (4, 4),        'figure.dpi': 200,        'xtick.labelsize': 4,        'ytick.labelsize': 4    })    ax = plot.figure().add_subplot(111, projection='3d')    ax.scatter(point_x, point_y, point_z, color='red')    ax.plot_surface(grid_x, grid_y, grid_z, rstride=5, cstride=5, alpha=0.7)    plot.show()

Функция main:

if __name__ == '__main__':    min_x, min_y = find_minimum()    minimum = (min_x, min_y, differentiable_function(min_x, min_y))    draw_chart(minimum, get_grid(0.05))

График:

Заключение

Процесс вычисления минимального значения с помощью алгоритма может быть не очень точным при вычислениях в более крупном масштабе, например, если радиус рабочей плоскости равен 1000, но он очень быстрый по сравнению с точным. Плюс в любом случае, если радиус большой, результат находится примерно в том положении, в котором он должен быть, поэтому разница не будет заметна на графике.

Исходный код:

import numpy as npimport matplotlib.pyplot as plotradius = 8                                  # working plane radiusglobal_epsilon = 0.000000001                # argument increment for derivativecentre = (global_epsilon, global_epsilon)   # centre of the working circlearr_shape = 100                             # number of points processed / 360step = radius / arr_shape                   # step between two pointsdef differentiable_function(x, y):    return np.sin(x) * np.exp((1 - np.cos(y)) ** 2) + \           np.cos(y) * np.exp((1 - np.sin(x)) ** 2) + (x - y) ** 2def rotate_vector(length, a):    return length * np.cos(a), length * np.sin(a)def derivative_x(epsilon, arg):    return (differentiable_function(global_epsilon + epsilon, arg) -            differentiable_function(epsilon, arg)) / global_epsilondef derivative_y(epsilon, arg):    return (differentiable_function(arg, epsilon + global_epsilon) -            differentiable_function(arg, epsilon)) / global_epsilondef calculate_flip_points():    flip_points = np.array([0, 0])    points = np.zeros((360, arr_shape), dtype=bool)    cx, cy = centre    for i in range(arr_shape):        for alpha in range(360):            x, y = rotate_vector(step, alpha)            x = x * i + cx            y = y * i + cy            points[alpha][i] = derivative_x(x, y) + derivative_y(y, x) > 0            if not points[alpha][i - 1] and points[alpha][i]:                flip_points = np.vstack((flip_points, np.array([alpha, i - 1])))    return flip_pointsdef pick_estimates(positions):    vx, vy = rotate_vector(step, positions[1][0])    cx, cy = centre    best_x, best_y = cx + vx * positions[1][1], cy + vy * positions[1][1]    for index in range(2, len(positions)):        vx, vy = rotate_vector(step, positions[index][0])        x, y = cx + vx * positions[index][1], cy + vy * positions[index][1]        if differentiable_function(best_x, best_y) > differentiable_function(x, y):            best_x = x            best_y = y    for index in range(360):        vx, vy = rotate_vector(step, index)        x, y = cx + vx * (arr_shape - 1), cy + vy * (arr_shape - 1)        if differentiable_function(best_x, best_y) > differentiable_function(x, y):            best_x = x            best_y = y    return best_x, best_ydef gradient_descent(best_estimates, is_x):    derivative = derivative_x if is_x else derivative_y    best_x, best_y = best_estimates    descent_step = step    value = derivative(best_y, best_x)    while abs(value) > global_epsilon:        descent_step *= 0.95        best_y = best_y - descent_step \            if derivative(best_y, best_x) > 0 else best_y + descent_step        value = derivative(best_y, best_x)    return best_y, best_xdef find_minimum():    return gradient_descent(gradient_descent(pick_estimates(calculate_flip_points()), False), True)def get_grid(grid_step):    samples = np.arange(-radius, radius, grid_step)    x, y = np.meshgrid(samples, samples)    return x, y, differentiable_function(x, y)def draw_chart(point, grid):    point_x, point_y, point_z = point    grid_x, grid_y, grid_z = grid    plot.rcParams.update({        'figure.figsize': (4, 4),        'figure.dpi': 200,        'xtick.labelsize': 4,        'ytick.labelsize': 4    })    ax = plot.figure().add_subplot(111, projection='3d')    ax.scatter(point_x, point_y, point_z, color='red')    ax.plot_surface(grid_x, grid_y, grid_z, rstride=5, cstride=5, alpha=0.7)    plot.show()if __name__ == '__main__':    min_x, min_y = find_minimum()    minimum = (min_x, min_y, differentiable_function(min_x, min_y))    draw_chart(minimum, get_grid(0.05))