Градиент
Материал из MachineLearning.
Градиент (англ. gradient) — вектор, составленный из частных производных скалярной функции нескольких переменных. Градиент показывает направление наиболее быстрого локального возрастания функции, а противоположный ему вектор — направление наиболее быстрого убывания.
Градиент является одним из основных понятий математического анализа и численной оптимизации. В машинном обучении он используется для настройки параметров моделей, минимизации функций потерь и обучения нейронных сетей. На вычислении градиента основаны метод градиентного спуска, метод стохастического градиента и многие современные алгоритмы оптимизации.
Если обычная производная показывает скорость изменения функции одной переменной, то градиент объединяет информацию об изменении функции по всем координатам.
Определение
Пусть задана дифференцируемая функция
где аргумент функции представляет собой вектор
Градиентом функции в точке
называется вектор её частных производных:
Для обозначения градиента используются записи ,
и
. Последняя запись явно указывает переменные, по которым выполняется дифференцирование.
Символ называется оператором набла (англ. nabla operator). В декартовых координатах его формально записывают как
В трёхмерном пространстве градиент функции имеет вид
где ,
и
— базисные векторы.
Интуитивная интерпретация
Функцию двух переменных можно представить в виде поверхности, высота которой над точкой
равна значению функции. В таком представлении градиент указывает направление наиболее крутого подъёма, а его норма характеризует крутизну поверхности.
Для уменьшения функции требуется двигаться в противоположную сторону — по направлению антиградиента:
Эта идея лежит в основе градиентного спуска (англ. gradient descent).
Градиент также можно интерпретировать с помощью линий уровня. Линия уровня объединяет точки, в которых функция принимает одинаковое значение. Градиент направлен поперёк линии уровня в сторону увеличения функции.
Локальное линейное приближение
Основное свойство градиента связано с локальным линейным приближением (англ. local linear approximation). Для малого приращения выполняется
При достаточно малом можно использовать приближённое равенство
Таким образом, скалярное произведение градиента на изменение аргумента показывает приближённое изменение значения функции.
Дифференциал функции записывается в виде
Локальное линейное приближение лежит в основе градиентных методов оптимизации: алгоритм использует поведение функции в текущей точке, чтобы выбрать направление следующего шага.[1]
Геометрический смысл
Производная по направлению
Пусть — единичный вектор. Производная по направлению (англ. directional derivative) определяется как
Если функция дифференцируема, производная по направлению выражается через градиент:
Пусть — угол между векторами
и
. Тогда
Максимальная производная по направлению достигается при . Следовательно, функция наиболее быстро возрастает в направлении
Максимальная скорость возрастания равна норме градиента:
Наиболее быстрое убывание происходит в противоположном направлении:
Утверждение о наиболее быстром изменении предполагает использование стандартной евклидовой нормы. При другой геометрии пространства направление наискорейшего изменения может отличаться.
Линии и поверхности уровня
Множеством уровня (англ. level set) функции называется множество
где — некоторое постоянное значение.
Для функции двух переменных множества уровня обычно являются линиями, а для функции трёх переменных — поверхностями.
Если , то градиент перпендикулярен множеству уровня, проходящему через точку
. При движении вдоль множества уровня значение функции не изменяется, поэтому для любого касательного направления
Следовательно, градиент ортогонален всем касательным направлениям.
Это свойство используется при решении задач оптимизации с ограничениями, построении нормалей к поверхностям, обработке изображений и моделировании физических полей.
Пример вычисления
Рассмотрим функцию
Её частные производные равны
Следовательно,
В точке получаем
Это означает, что в окрестности точки функция наиболее быстро возрастает в направлении вектора
и наиболее быстро убывает в направлении
.
Единичное направление наиболее быстрого возрастания равно
В точке градиент обращается в нуль:
Для рассматриваемой функции эта точка является глобальным минимумом. Однако в общем случае нулевой градиент не гарантирует наличие минимума.
Связь с якобианом и гессианом
Для функции одной переменной градиент состоит из одной компоненты и совпадает с обычной производной:
Для скалярной функции нескольких переменных полная производная является линейным отображением
В евклидовом пространстве она представляется с помощью градиента:
Для векторнозначной функции
используется матрица Якоби, или якобиан (англ. Jacobian matrix):
Матрица вторых частных производных скалярной функции называется матрицей Гессе, или гессианом (англ. Hessian matrix):
Градиент описывает локальный наклон функции, а гессиан — изменение градиента и локальную кривизну.
В литературе встречаются разные соглашения о представлении градиента в виде строки или столбца. В данной статье градиент считается вектором-столбцом.
Правила вычисления
Для дифференцируемых функций и
и постоянной
выполняются правила
Для композиции функций применяется цепное правило (англ. chain rule). Пусть
Тогда
Последовательное применение цепного правила позволяет вычислять градиенты сложных композиций функций. На этом принципе основаны обратное распространение ошибки и автоматическое дифференцирование.
Стационарные точки
Точка , в которой
называется стационарной точкой (англ. stationary point).
Равенство градиента нулю является необходимым условием локального экстремума во внутренней точке области определения дифференцируемой функции. Однако это условие не является достаточным.
Стационарная точка может быть:
- локальным минимумом;
- локальным максимумом;
- седловой точкой (англ. saddle point);
- частью плоской области;
- вырожденной точкой.
Например, для функции
градиент равен
В точке он обращается в нуль. При этом
а
Следовательно, точка является седловой.
Если гессиан в стационарной точке положительно определён, точка является строгим локальным минимумом. Если гессиан отрицательно определён, точка является строгим локальным максимумом. Неопределённый гессиан соответствует седловой точке.[1]
Зависимость от геометрии пространства
Производная скалярной функции является линейным функционалом, или ковектором (англ. covector). Для её представления в виде вектора необходимо выбрать скалярное произведение.
В евклидовом пространстве градиент определяется равенством
Пусть скалярное произведение задаётся симметричной положительно определённой матрицей :
Тогда градиент относительно этой геометрии равен
Следовательно, направление наиболее быстрого убывания зависит от выбранной метрики. Обычный антиградиент задаёт это направление только относительно стандартной евклидовой нормы.
В машинном обучении с этим связаны влияние масштаба признаков и эффективность предобусловливания (англ. preconditioning). Изменение масштаба координат может существенно изменить траекторию градиентного метода.
Применение в оптимизации
Для минимизации дифференцируемой функции используется метод градиентного спуска. Его итерация имеет вид
где — величина шага.
В машинном обучении величину шага часто называют скоростью обучения (англ. learning rate).
Выбор антиградиента объясняется локальным приближением:
Если градиент не равен нулю, то при достаточно малом положительном значение функции уменьшается.
Слишком маленький шаг приводит к медленной сходимости, а слишком большой может вызвать колебания или расходимость. Для выбора шага применяются постоянная скорость обучения, убывающая последовательность шагов, поиск шага (англ. line search) и адаптивные методы.
Градиент используется в следующих методах:
- градиентный спуск;
- метод стохастического градиента;
- стохастический градиентный спуск;
- ускоренный градиентный метод Нестерова;
- метод сопряжённых градиентов;
- квазиньютоновские методы;
- алгоритмы AdaGrad, RMSProp и Adam;
- методы оптимизации с ограничениями.
Градиент содержит информацию только первого порядка. Методы Ньютона и квазиньютоновские методы дополнительно используют гессиан или его приближение.
Градиент в машинном обучении
Настройка параметров модели
Пусть алгоритм
зависит от вектора параметров
Качество алгоритма на обучающей выборке может задаваться функционалом эмпирического риска
где — функция потерь, а
— число объектов обучающей выборки.
Градиент
показывает чувствительность эмпирического риска к изменению каждого параметра модели. Общая постановка задачи рассматривается в статье Минимизация эмпирического риска.
Компонента
показывает, как локально изменится ошибка при изменении параметра , если остальные параметры остаются фиксированными.
Градиентные методы применяются при обучении линейной регрессии, логистической регрессии, многослойных персептронов и других дифференцируемых моделей.
Пример: линейная регрессия
Рассмотрим линейную модель
где — матрица признаков,
— вектор параметров,
— вектор целевых значений.
Для квадратичной функции потерь
градиент равен
Вектор
содержит остатки модели. Умножение на объединяет ошибки с соответствующими значениями признаков и определяет направление изменения каждого параметра.
При добавлении квадратичной регуляризации
градиент принимает вид
Добавка направляет параметры к нулю и ограничивает сложность модели.
Нейронные сети
Выход нейронной сети является композицией большого числа функций. Отдельный слой можно записать как
где — матрица весов,
— вектор смещений, а
— функция активации.
Для обучения сети требуется вычислить производные функции потерь по всем параметрам. Для этого используется обратное распространение ошибки (англ. backpropagation) — последовательное применение цепного правила от выходного слоя к входному.
Работа Д. Румельхарта, Дж. Хинтона и Р. Уильямса 1986 года сыграла важную роль в распространении обратного распространения ошибки для обучения многослойных нейронных сетей.[1]
Обратное распространение вычисляет градиенты, но не определяет способ обновления параметров. Полученные градиенты передаются алгоритму оптимизации: градиентному спуску, SGD, Adam или другому методу.
Стохастическая оценка градиента
При большой обучающей выборке вычисление полного градиента на каждой итерации может быть слишком затратным. Поэтому градиент часто оценивают по случайному мини-пакету (англ. mini-batch) :
При случайном равновероятном выборе объектов эта величина является несмещённой оценкой полного градиента:
Случайная оценка имеет ненулевую дисперсию, поэтому отдельные шаги могут не уменьшать функцию потерь. Однако вычисление одной итерации становится значительно дешевле.
Такой подход лежит в основе метода стохастического градиента и стохастического градиентного спуска.
Теоретические основы стохастической аппроксимации были предложены Г. Роббинсом и С. Монро в 1951 году.[1]
Другие применения
В машинном обучении градиенты используются также:
- для анализа чувствительности модели к входным признакам;
- при построении локальных объяснений предсказаний;
- в состязательных атаках на модели;
- при обучении с подкреплением;
- при оптимизации гиперпараметров;
- в метаобучении;
- в градиентном бустинге.
В градиентном бустинге оптимизация выполняется в пространстве функций. На очередной итерации базовый алгоритм приближает направление антиградиента функции потерь.
Способы вычисления градиента
Аналитическое дифференцирование
При аналитическом дифференцировании формула градиента выводится вручную с помощью правил дифференцирования.
Такой подход позволяет получить эффективную формулу, однако для сложных моделей ручной вывод становится трудоёмким и подверженным ошибкам.
Символьное дифференцирование
Символьное дифференцирование (англ. symbolic differentiation) преобразует исходное математическое выражение в новое выражение для его производной.
Например,
Недостатком является возможное быстрое увеличение размера промежуточных выражений.
Численное дифференцирование
При численном дифференцировании производная приближается конечными разностями (англ. finite differences).
Правая разность имеет вид
Центральная разность определяется формулой
Центральная разность обычно имеет меньшую ошибку аппроксимации, но требует двух вычислений функции для каждой координаты.
Выбор шага является компромиссом. Слишком большой шаг увеличивает ошибку аппроксимации, а слишком малый усиливает влияние машинного округления.
Численное дифференцирование редко используется для обучения моделей с большим числом параметров, поскольку его вычислительная стоимость растёт линейно с размерностью. Однако оно применяется для проверки градиента (англ. gradient checking).
Для проверки можно сравнить вычисленный градиент с численной оценкой
:
Малое значение указывает на согласованность двух способов вычисления.
Автоматическое дифференцирование
Автоматическое дифференцирование (англ. automatic differentiation, AD) применяет цепное правило непосредственно к последовательности элементарных операций программы.
В отличие от численного дифференцирования, оно не заменяет производную конечной разностью. В отличие от символьного дифференцирования, оно обычно не строит отдельное выражение для всей производной.
Различают два основных режима:
- прямой режим (англ. forward mode);
- обратный режим (англ. reverse mode).
Прямой режим удобен, если число входных переменных мало по сравнению с числом выходов. Обратный режим особенно эффективен для функций с большим числом входов и одним скалярным выходом.
Именно такая ситуация возникает при обучении нейронной сети: входами для дифференцирования являются многочисленные параметры, а выходом — одно значение функции потерь.
Обратное распространение ошибки является частным случаем обратного режима автоматического дифференцирования.[1]
Ограничения и типичные ошибки
Недифференцируемость
Градиент существует не во всех точках. Например, функция
не имеет производной при .
Для выпуклых недифференцируемых функций используются субградиенты (англ. subgradients). Вектор является субградиентом выпуклой функции
в точке
, если для всех
В отличие от обычного градиента, субградиент в одной точке может быть не единственным.
Нулевой градиент
Условие
не гарантирует, что точка является минимумом. Она может быть максимумом, седловой точкой или частью плоской области.
Кроме того, тест по вторым производным иногда не позволяет определить тип стационарной точки. Например, для функции
в точке первая и вторая производные равны нулю, хотя эта точка является строгим минимумом.
Локальный характер информации
Градиент описывает поведение функции только в окрестности текущей точки. Направление, локально уменьшающее функцию, не обязано вести к глобальному минимуму.
В невыпуклой задаче алгоритм может попасть в локальный минимум, седловую точку или плоскую область. При слишком большой величине шага значение функции может увеличиться даже при движении по антиградиенту.
Масштаб признаков
Если разные координаты имеют существенно различные масштабы, линии уровня функции могут быть сильно вытянуты. В этом случае градиентный спуск часто движется по зигзагообразной траектории и медленно приближается к минимуму.
Для уменьшения этой проблемы применяются:
- стандартизация признаков;
- нормализация;
- предобусловливание;
- адаптивные алгоритмы оптимизации;
- методы, использующие информацию о кривизне функции.
Исчезающие и взрывающиеся градиенты
При многократном применении цепного правила производные перемножаются. В глубоких и рекуррентных нейронных сетях это может приводить к двум явлениям:
- исчезающему градиенту (англ. vanishing gradient);
- взрывающемуся градиенту (англ. exploding gradient).
При исчезновении градиента ранние слои сети получают очень малые обновления и практически перестают обучаться. Это явление подробнее описано в статье Проблема исчезающего градиента.
При взрыве градиента его норма быстро увеличивается, что приводит к большим обновлениям параметров и численной нестабильности.
Для борьбы с этими проблемами применяются:
- подходящая инициализация параметров;
- функции активации ReLU и их модификации;
- нормализация;
- остаточные соединения;
- архитектуры LSTM и GRU;
- обрезка градиента (англ. gradient clipping).
При обрезке по норме градиент заменяется выражением
где — максимально допустимая норма.[1]
Ошибки программной реализации
При программировании градиентов часто встречаются следующие ошибки:
- неправильное применение цепного правила;
- несогласованность размерностей векторов и матриц;
- пропущенное транспонирование;
- дифференцирование по неправильной переменной;
- неправильное усреднение градиентов мини-пакета;
- накопление градиентов между итерациями;
- случайное отсоединение части вычислительного графа;
- численная неустойчивость функции потерь.
Для проверки нестандартных функций потерь и слоёв рекомендуется сравнивать аналитический или автоматически вычисленный градиент с конечными разностями.
История
Современное понятие градиента сформировалось вместе с развитием анализа функций нескольких переменных и векторного анализа.
Символ связан с работами Уильяма Роуэна Гамильтона. Система операций современного векторного анализа развивалась в работах Джозайи Уилларда Гиббса и Оливера Хевисайда.
Учебник Эдвина Уилсона, основанный на лекциях Гиббса и опубликованный в 1901 году, способствовал распространению обозначений градиента, дивергенции и ротора.[1]
В XX веке градиентные методы стали важной частью численной оптимизации. Развитие стохастической аппроксимации, обратного распространения ошибки и автоматического дифференцирования сделало вычисление градиента одной из центральных операций машинного обучения.
См. также
- Метод градиентного спуска
- Метод стохастического градиента
- Стохастический градиентный спуск
- Ускоренный градиент Нестерова
- Метод сопряжённых градиентов
- Вычисление матриц Якоби и Гессе
- Минимизация эмпирического риска
- Искусственная нейронная сеть
- Многослойный персептрон
- Проблема исчезающего градиента
- Градиентный бустинг
Примечания
Литература
- Boyd S., Vandenberghe L. Convex Optimization. Cambridge University Press, 2004.
- Goodfellow I., Bengio Y., Courville A. Deep Learning. MIT Press, 2016.
- Nocedal J., Wright S. J. Numerical Optimization. 2nd ed. Springer, 2006.
- Поляк Б. Т. Введение в оптимизацию. М.: Наука, 1983.
- Baydin A. G., Pearlmutter B. A., Radul A. A., Siskind J. M. Automatic Differentiation in Machine Learning: a Survey // Journal of Machine Learning Research. 2018. Vol. 18. No. 153. P. 1—43.
- Robbins H., Monro S. A Stochastic Approximation Method // The Annals of Mathematical Statistics. 1951. Vol. 22. No. 3. P. 400—407.
- Rumelhart D. E., Hinton G. E., Williams R. J. Learning representations by back-propagating errors // Nature. 1986. Vol. 323. P. 533—536.

