Метод инерции Поляка

Материал из MachineLearning.

СТАТЬЯ В РАЗРАБОТКЕ: Этот материал сейчас находится в процессе активного редактирования и доработки участником Polina Khadralinova. Просьба не оценивать статью до снятия этой пометки.

Промпт приводится полностью в Обсуждение:Метод инерции Поляка

Введение

Метод инерции (широко известный в машинном обучении как метод Momentum) — это алгоритм градиентной оптимизации, предложенный советским математиком Борисом Теодоровичем Поляком в 1964 году. Данный метод является развитием классического градиентного спуска и предназначен для ускорения сходимости за счёт накопления информации о предыдущих направлениях движения.

Концепцию метода Поляка легче всего понять через интуитивную физическую аналогию, известную как метод «тяжёлого шарика». Представьте, что процесс минимизации функции — это скатывание шарика по холмистому ландшафту в самую глубокую впадину. В этой аналогии каждый элемент физического мира имеет строгий математический эквивалент в задаче машинного обучения:

• Положение шарика на холме — это текущий вектор весов (параметров) модели .
• Высота холма (рельеф ландшафта) — это значение функции потерь (эмпирического риска) . Чем ниже шарик, тем меньше ошибка модели.
• Сила тяжести, толкающая шарик вниз — это антиградиент (направление наискорейшего спуска в текущей точке).
• Масса шарика — это инерция (накапливаемая скорость). В обычном стохастическом градиентном спуске (SGD) шарик условно «невесомый» (пушинка): он движется строго туда, куда указывает локальный уклон, и останавливается мгновенно, как только поверхность становится горизонтальной. В методе Поляка шарик тяжёлый. Набрав скорость на крутом склоне, он по инерции катится дальше, даже если локальный уклон временно исчез.
• Трение среды (сопротивление воздуха или вязкость жидкости) — это коэффициент затухания скорости , который не даёт шарику бесконечно проскакивать минимум и плавно тормозит его на дне, рассеивая кинетическую энергию.

Математический аппарат и свойства

Математически метод инерции реализуется путём введения дополнительного вектора — вектора скорости , который накапливает экспоненциальное скользящее среднее (ЭСС) градиентов прошлых итераций.

На каждом шаге для случайного объекта обучающей выборки происходит пересчёт скорости и обновление параметров:

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

• — градиентный шаг (или темп обучения, learning rate). Определяет масштаб изменения весов на одной итерации.
• — коэффициент инерции (сохранения скорости). Это число в полуинтервале , обычно принимающее значения или .

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

Борьба с препятствиями оптимизации

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

Проблема «оврагов» (патологическая кривизна) Часто функция потерь имеет форму вытянутого оврага: вдоль одного направления (поперёк оврага) градиент очень велик, а вдоль другого (по дну оврага к глобальному минимуму) — очень мал. Обычный SGD в такой ситуации совершает неэффективные поперечные колебания («зигзаги») от одной стенки к другой, крайне медленно продвигаясь к цели. Метод инерции решает эту проблему: градиенты, направленные к противоположным стенкам оврага, имеют разные знаки и при усреднении в векторе взаимно гасят друг друга. Поперечные колебания исчезают. В то же время, малые градиенты, указывающие вдоль дна оврага, имеют одинаковый знак и накапливаются, многократно ускоряя движение в правильном направлении.

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

Развитие метода: Ускоренный градиент Нестерова (NAG)

В 1983 году выдающийся математик Юрий Евгеньевич Нестеров предложил модификацию метода Поляка, которая получила название Nesterov Accelerated Gradient (NAG). Идея Нестерова заключалась в том, чтобы сделать инерцию более «дальновидной».

В классическом методе Поляка мы сначала вычисляем градиент в текущей точке , а затем сдвигаемся по направлению вектора скорости. Однако мы уже знаем, что из-за инерции мы совершенно точно сместимся на вектор . Логично вычислять градиент не в текущей точке , а «заглядывая вперёд» — в той точке , куда нас отнесёт инерция.

Формулы метода Нестерова (NAG) принимают вид:

За счёт вычисления градиента «по ходу движения» метод Нестерова получает возможность вовремя заметить подъём (дно минимума) и начать тормозить ещё до того, как шарик проскочит оптимум. Это существенно снижает нежелательные осцилляции в окрестности точки минимума и обеспечивает доказанное теоретическое ускорение сходимости для выпуклых задач.

Практическая реализация на Python

Ниже приведена лаконичная и эффективная реализация метода Поляка на языке Python с использованием библиотеки NumPy. Оптимизатор оформлен в виде класса для сохранения внутреннего состояния (вектора скорости ) между вызовами.

import numpy as np
 
class PolyakMomentumOptimizer:
    def __init__(self, learning_rate=0.01, gamma=0.9):
        # Инициализация параметров оптимизатора
        self.h = learning_rate
        self.gamma = gamma
        # Вектор скорости (инерции) изначально не задан
        self.v = None
 
    def step(self, w, grad):
        # Инициализация вектора скорости нулями при первом вызове функции
        if self.v is None:
            self.v = np.zeros_like(w)
 
        # Шаг 1: обновление вектора скорости (учёт инерции и нового градиента)
        # Соответствует: v = gamma * v + (1 - gamma) * grad
        self.v = self.gamma * self.v + (1 - self.gamma) * grad
 
        # Шаг 2: шаг против градиента (обновление весов модели)
        # Соответствует: w = w - h * v
        w = w - self.h * self.v
 
        return w

См. также

• Стохастический градиентный спуск
• Минимизация эмпирического риска

Литература

• Поляк Б. Т. Некоторые способы ускорения сходимости итерационных методов. — М.: Журнал вычислительной математики и математической физики, 1964. — T. 4. — С. 791–803.
• Нестеров Ю. Е. Метод минимизации выпуклых функций со скоростью сходимости O(1/k^2). — М.: Доклады АН СССР, 1983. — T. 269. — С. 543–547.