Градиентный спуск: как метод учится на числах

Функция задана, минимизировать надо: невязка модели, энергия конструкции, ошибка предсказания на миллионе параметров. Формулы для точки минимума нет — есть только возможность вычислять $f$ и её градиент. Градиентный спуск отвечает на такую постановку честно и минимально: шагаем против градиента, смотрим, куда выведет, повторяем. Метод стоит в фундаменте обучения почти всех моделей машинного обучения, но устроен до смешного просто и полностью просчитывается руками. Протестируем его на квадратичной функции $f(x,y)=x^2+4y^2$, где видно всё: и выбор шага, и скорость сходимости, и место, где метод ломается.

Идея антиградиента: куда идти вниз#

Градиент — вектор из частных производных, он указывает направление наискорейшего роста функции. Значит, минус-градиент — наискорейшее убывание: производная по направлению $-\nabla f$ среди всех направлений единичной длины минимальна. Отсюда итерация метода — небольшой шаг в сторону минус-градиента:

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

Выбор шага: цена ошибки в обе стороны#

Тестовая функция одной переменной $f(x)=x^2$: градиент равен $2x$, и спуск даёт умножение координаты на константу. Вся судьба метода — в этой константе:

Слишком большой шаг — итерации разлетаются: при $\alpha =1,1$ множитель $-1,2$, точка скачет через минимум, размах растёт. Слишком маленький — спуск жив, но ползёт: при $\alpha =0,001$ множитель $0,998$, и чтобы уменьшить ошибку в тысячу раз, нужно примерно $\ln (0,001)/\ln (0,998)\approx 3453$ шага. Для квадратичной функции с кривизнами ${\lambda }_i$ (собственными числами матрицы Гессе — как их считать численно, см. численный поиск собственных значений) за один шаг ошибка умножается на худший из множителей:

Спуск на f(x, y) = x² + 4y²: числа по шагам#

Градиент: $\nabla f=(2x,8y)$. Старт $(1;1)$, шаг $\alpha =0,1$ — вдвое меньше границы $0,25$, запас есть. Минимум в нуле, стартовое значение $f=5$.

При $\alpha$ ближе к границе картина меняется качественно: возьмите $\alpha =0,2$ — и множитель по $y$ станет $1-8\cdot 0,2=-0,6$, координата начнёт проскакивать ноль, а траектория превратится в зигзаг поперёк «долины». Значение функции всё ещё убывает, но путь становится длинным и дёрганым — узнаваемая картинка, которую рисуют в каждом курсе по обучению моделей.

Как выбирать шаг без гадания? Дробление: шагнули, если $f$ выросла — вернитесь и уменьшите $\alpha$ вдвое. Для квадратичных функций работает и прикидка по кривизне: $\alpha =1/L$ всегда внутри границы $2/L$, а для нашего примера даёт $0,125$ — множители $0,75$ по $x$ и ровно $0$ по $y$: минимум по крутой координате достигается за один шаг. По $x$ остаётся множитель $0,75$, и до точности $10^{-3}$ нужно $\ln (10^{-3})/\ln (0,75)\approx 25$ шагов — против 31 при $\alpha =0,1$, причём без всякого риска взрыва. Одна цифра $L$ экономит и время, и нервы.

Овраги, зигзаги и стохастическое спасение#

Отношение кривизн $\kappa ={\lambda }_{\max }/{\lambda }_{\min }$ — «овражность» функции. У нашего примера $\kappa =4$ — терпимо: с оптимальным шагом множитель ошибки $(\kappa -1)/(\kappa +1)=0,6$. Но при $\kappa =100$ он даёт $0,98$: спуск тысячами шагов молотит поперёк оврага, продвигаясь вдоль него со скоростью улитки. Лекарства разные: предобусловливание и нормировка признаков выравнивают кривизны, метод Ньютона использует вторые производные и снимает проблему одной шкалой, спуск с моментом накапливает движение вдоль оврага. Для ограничений вида «не выходить из области» оптимизацию ведут через функцию Лагранжа либо проекционные варианты спуска.

Стохастическая версия (SGD) решает другую проблему — объём данных. Полный градиент на миллионе примеров дорог, вместо него берут случайную мини-выборку: её градиент шумный, но в среднем правильный, а стоит в сто раз меньше. Парадокс в том, что шум полезен: он выбивает траекторию из зигзагов и помогает проскакивать неглубокие ямы невыпуклого ландшафта. Шаг обучения при этом обычно убывает по расписанию: большие шаги вначале — быстро добраться до окрестности минимума, мелкие в конце — точная доводка.

• Считать градиент в старой точке, а шаг делать по новым координатам — классическая ошибка реализации: сначала пересчитали градиент, потом шагнули.
• Выбирать α без проверки: при α > 2/λmax спуск расходится, а не «медленно сходится» — ищите ошибку знака или масштаба.
• Мерить сходимость значением f, а не нормой градиента ‖∇f‖: на овражной функции значение стагнирует далеко от минимума.
• Ждать глобального минимума от невыпуклой функции: спуск честно сходится к стационарной точке, которая бывает седлом или локальной ямой.
• Забывать про масштаб переменных: овраг возникает из-за разнокалиберных координат, нормировка дешевле хитрых методов.
• Держать один и тот же шаг до конца обучения: убывающее α (например, α₀/(1 + k/50)) обычно выигрывает и по скорости, и по точности.

Итог: антиградиент задаёт направление, шаг задаёт судьбу. Квадратичный пример $x^2+4y^2$ показал всё за пять итераций — от падения функции в шесть раз до разгона координат с разными множителями. Там, где минимизация сводится к линейной системе — например, нормальные уравнения МНК, это численные методы для СЛАУ, — спуск конкурирует с прямыми методами; в больших невыпуклых задачах у него конкурентов почти нет. Дальше по теме: стохастические варианты, момент и адаптивные шаги — но их логика целиком вырастает из того, что мы посчитали руками.