Методы нулевого порядка 🎲

Все методы, которые ты изучил в этой части курса — от обычного градиентного спуска до Adam, — опираются на одно и то же молчаливое предположение: у функции потерь есть градиент, и этот градиент можно вычислить. Для нейросети это предположение выполняется почти всегда: архитектура состоит из дифференцируемых операций (умножение матриц, свёртки, привычные функции активации), и обратное распространение ошибки (backpropagation) честно вычисляет точную производную по каждому весу за один проход. Но стоит выйти за пределы весов самой сети и задать вопрос «а какое число слоёв взять? какой размер батча? какую скорость обучения?» — и почва под ногами исчезает. Зависимость итогового качества модели от числа слоёв не выражается никакой формулой, которую можно продифференцировать. Единственный способ узнать, насколько хорош выбор гиперпараметров, — реально обучить модель с этим набором значений и посмотреть на метрику. У этой процедуры нет аналитического градиента в принципе, потому что «обучить модель и измерить качество» — это не гладкая математическая функция, а протокол действий, который включает в себя случайную инициализацию весов, обращение к диску за данными и сотни или тысячи итераций самого обучения.

Именно эту ситуацию — когда функция, которую нужно оптимизировать, задана не формулой, а «чёрным ящиком», куда можно подать вход и получить выход, но нельзя заглянуть внутрь и продифференцировать, — и покрывают методы нулевого порядка (derivative-free optimization, zeroth-order optimization). Название отражает суть: методы первого порядка используют градиент (производные первого порядка), методы второго порядка вроде метода Ньютона используют ещё и гессиан (производные второго порядка), а методы нулевого порядка обходятся вовсе без производных — только значениями самой функции, «нулевым порядком» информации о ней.

Причин, по которым градиент оказывается недоступен или бессмыслен, на практике несколько, и они разные по своей природе. Функция может быть буквально «чёрным ящиком» — как в примере с гиперпараметрами: ты не знаешь и не можешь узнать её аналитическую формулу, потому что её попросту нет, есть только процедура вычисления значения. Функция может быть недифференцируемой — например, при оптимизации структуры дерева решений или числа кластеров в алгоритме кластеризации, где сама переменная дискретна и о производной по ней говорить некорректно. Функция может быть зашумлённой — метрика качества модели на одном и том же наборе гиперпараметров может слегка отличаться от запуска к запуску из-за случайной инициализации весов или случайного перемешивания данных, и попытка честно продифференцировать такой шум даст мусор вместо направления. И, наконец, переменные могут быть дискретными или комбинаторными — число слоёв нейросети, тип функции активации, архитектурное решение «добавлять ли пропускающее соединение» (skip-connection) — здесь понятие «направление наискорейшего убывания» просто не определено, потому что нет непрерывного пространства, в котором можно двигаться бесконечно малыми шагами.

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

История

Идея оптимизации без явного вычисления производной не нова: ещё в 1960-х годах, когда компьютеры только начинали применяться для численных расчётов, а автоматическое дифференцирование в современном виде попросту не существовало, исследователям приходилось искать минимумы функций, полагаясь только на значения самой функции. В 1965 году Джон Нелдер и Роджер Мид опубликовали симплекс-метод (не путать с симплекс-методом линейного программирования) — алгоритм, который поддерживает набор пробных точек, образующих симплекс в пространстве переменных, и последовательно двигает его к области с меньшим значением функции, отражая, сжимая или растягивая симплекс в зависимости от того, куда указывают сравнения значений функции в его вершинах. Метод Нелдера-Мида по сей день остаётся одним из самых используемых методов нулевого порядка — он входит, например, в scipy.optimize.minimize под именем 'Nelder-Mead'.

Метод конечных разностей для приближения производной ещё старше — его идея восходит к базовому определению производной через предел разностного отношения, и как численный приём он использовался задолго до появления компьютеров, в ручных инженерных расчётах XIX века. Но настоящий концептуальный прорыв в контексте оптимизации случился в 1992 году, когда американский инженер Джеймс Спалл предложил метод одновременных возмущений SPSA (Simultaneous Perturbation Stochastic Approximation) — способ оценивать градиент не покоординатно, как это делают классические конечные разности, а сразу по всем координатам одним случайным возмущением. SPSA изначально разрабатывался для задач промышленного управления и калибровки сложных систем — например, для настройки параметров ускорителей частиц, — где каждое измерение стоило дорогого времени эксперимента, и Спалл искал способ выжать максимум информации о направлении оптимизации из минимального числа обращений к системе.

Сегодня методы нулевого порядка переживают новую волну интереса в контексте машинного обучения — и вот почему. Подбор гиперпараметров моделей (hyperparameter tuning) — рутинная задача практически любого проекта — по своей природе является задачей оптимизации нулевого порядка: «функция», которую нужно минимизировать (или максимизировать), — это результат полного цикла обучения модели, а не гладкая формула. В обучении с подкреплением (reinforcement learning) методы нулевого порядка применяются для оптимизации политик агента напрямую, оценивая направление улучшения через случайные возмущения весов политики, потому что среда, в которой действует агент, зачастую сама недифференцируема: нельзя продифференцировать физический движок игры или реакцию реального робота по параметрам нейросети-политики. Именно поэтому то, что полвека назад было нишевой техникой численных методов, сегодня — рабочий инструмент любого специалиста, который настраивает модели на практике.

Когда градиент недоступен и почему это меняет всё

Интуиция

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

Метод

Постановка задачи оптимизации нулевого порядка. Дана функция $f(x)$, где $x \in \mathbb{R}^n$ (или дискретное множество), и доступен только оракул нулевого порядка — процедура, которая по любому входу $x$ возвращает значение $f(x)$ (возможно, зашумлённое: $f(x) + \xi$, где $\xi$ — случайный шум). Аналитическое выражение для $\nabla f(x)$ недоступно, автоматическое дифференцирование неприменимо. Требуется найти $x^\* = \arg\min_x f(x)$, используя как можно меньше обращений к оракулу — каждое обращение может быть вычислительно дорогим.

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

Разбор примеров

Пример 1 (гиперпараметры нейросети как чёрный ящик). Пусть ты настраиваешь скорость обучения $\eta$ и размер батча $B$ для сверточной сети, обучаемой на классификации изображений. Функция $f(\eta, B)$ — это «обучить модель на 50 эпохах с параметрами $\eta$ и $B$, вернуть ошибку на валидационной выборке». У этой функции нет аналитической формулы: она зависит от архитектуры сети, инициализации весов, порядка перемешивания батчей, конкретного датасета — от всего того, что нельзя выразить одной дифференцируемой формулой относительно $\eta$ и $B$. Более того, если ты вызовешь $f(0{,}01,\ 64)$ дважды подряд (два независимых обучения с одинаковыми гиперпараметрами, но разной случайной инициализацией), ты, скорее всего, получишь два разных числа — скажем, ошибку $0{,}142$ в первый раз и $0{,}138$ во второй. Это и есть тот самый зашумлённый оракул из формального определения: функция задана нечётко, значения колеблются от запуска к запуску, и никакого градиента здесь принципиально не существует — только результаты отдельных «выпеканий пирога».

Пример 2 (архитектурный выбор как дискретная переменная). Пусть один из параметров, который нужно подобрать, — тип функции активации: ReLU, tanh или sigmoid. Даже если бы у тебя была волшебная возможность посчитать градиент качества модели по «непрерывному параметру функции активации», сама постановка вопроса некорректна: между ReLU и tanh не существует непрерывного пути, вдоль которого можно двигаться маленькими шагами, — это дискретный выбор из конечного множества вариантов, и понятие производной по такой переменной не определено в принципе. Ровно та же ситуация — с числом слоёв сети (3, 4 или 5 — не «3,7 слоя») или с выбором оптимизатора (Adam или SGD).

Пример 3 (обучение с подкреплением и недифференцируемая среда). Представь агента, который управляет роботом-манипулятором, а политика поведения агента задаётся нейросетью с весами $\theta$. Награда за эпизод $R(\theta)$ зависит от весов через цепочку: веса определяют действия агента, действия определяют, как реагирует физическая среда (например, реальный робот или сложный физический симулятор), а реакция среды определяет итоговую награду. Если среда — это реальный робот или «чёрный ящик» физического движка, к внутренностям которого нет доступа, то продифференцировать награду по весам политики напрямую невозможно: нет способа взять частную производную от «того, как отреагировала физическая система» по «весу нейросети». В такой ситуации $R(\theta)$ приходится трактовать как функцию нулевого порядка — единственное, что доступно, это прогнать эпизод с конкретными весами $\theta$ и получить одно число, суммарную награду.

Почему это важно

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

Метод конечных разностей

Интуиция

Раз аналитической формулы для градиента нет, самая прямолинейная идея — вернуться к самому определению производной. Производная функции одной переменной — это предел отношения приращения функции к приращению аргумента при устремлении приращения к нулю. Если предел точно вычислить нельзя (потому что нет формулы, которую можно продифференцировать), можно взять не бесконечно малое, а просто маленькое приращение $\varepsilon$ и посчитать это отношение приближённо, «в лоб» — вызвав функцию-оракул дважды: один раз чуть правее текущей точки, один раз чуть левее.

Метод

Метод конечных разностей (центральная разность). Приближённая оценка производной функции $f$ по переменной $x$ в точке $x_0$:

$$f'(x_0) \approx \frac{f(x_0+\varepsilon) - f(x_0-\varepsilon)}{2\varepsilon}$$

где $\varepsilon > 0$ — малый шаг возмущения. Ошибка такого приближения по порядку величины равна $O(\varepsilon^2)$ (это следует из разложения $f$ в ряд Тейлора вокруг $x_0$) — то есть уменьшение $\varepsilon$ вдесятеро уменьшает ошибку приближения примерно в сто раз, при условии что $\varepsilon$ не настолько мало, чтобы в дело вступала ошибка округления при вычислениях с плавающей точкой.

Обобщение на много переменных. Для функции $f(x_1,\dots,x_n)$ каждая компонента градиента оценивается отдельно, возмущая только одну координату за раз, а остальные фиксируя:

$$\frac{\partial f}{\partial x_i}(x) \approx \frac{f(x+\varepsilon e_i) - f(x-\varepsilon e_i)}{2\varepsilon}$$

где $e_i$ — единичный вектор вдоль оси $i$. Чтобы получить оценку всего градиента $\nabla f(x) \in \mathbb{R}^n$, нужно проделать это для каждой из $n$ координат — то есть $2n$ обращений к функции $f$ на одну оценку градиента.

Разбор примеров

Пример 1 (проверка метода на функции с известной производной). Пусть $f(x) = x^2$, точная производная $f'(x) = 2x$, оцениваем в точке $x_0 = 3$ (точное значение $f'(3) = 6$) с шагом $\varepsilon = 0{,}1$:

Оценка идеально совпала с точным значением — это не случайность, а свойство квадратичной функции: для неё центральная разность даёт точный результат без остаточной ошибки, потому что члены ряда Тейлора третьего и более высоких порядков у квадратичной функции равны нулю. Возьмём менее «удобную» функцию $f(x) = x^3$, точная производная в точке $x_0=2$: $f'(2) = 3\cdot4 = 12$. С тем же $\varepsilon=0{,}1$:

Здесь уже видна небольшая ошибка приближения — $12{,}01$ вместо точных $12{,}00$, отклонение $0{,}01$, что согласуется с теоретической оценкой ошибки порядка $\varepsilon^2 = 0{,}01$.

Пример 2 (оценка градиента для функции двух переменных). Пусть $f(x,y) = x^2 + 3y^2$, точный градиент $\nabla f = (2x,\ 6y)$, оцениваем в точке $(2,1)$ (точное значение $(4,6)$) с $\varepsilon=0{,}01$. Потребуется четыре обращения к функции — по два на каждую из двух координат:

Оценённый градиент $(4{,}00,\ 6{,}00)$ практически идеально совпал с точным $(4,6)$ — четыре вызова функции на двумерную задачу. Обрати внимание: чтобы получить эту оценку, пришлось вызвать функцию $f$ четыре раза, хотя аналитический градиент вычисляется одной формулой мгновенно.

Пример 3 (проблема высокой размерности — стоимость растёт линейно с числом параметров). Вернёмся к задаче подбора гиперпараметров: пусть их не два, а $n = 20$ (архитектура, скорости обучения на разных стадиях, коэффициенты регуляризации, параметры аугментации данных — в реальных проектах именно такое число гиперпараметров совершенно обычное дело). Чтобы методом конечных разностей оценить один-единственный градиент по всем 20 гиперпараметрам, потребуется $2n = 40$ полных обучений модели — по два обучения на каждый гиперпараметр (со сдвигом $+\varepsilon$ и $-\varepsilon$), при том что все остальные 19 гиперпараметров фиксированы. Если одно обучение занимает 2 часа на видеокарте, одна-единственная оценка градиента обойдётся в $40 \times 2 = 80$ часов вычислений — больше трёх суток. А ведь для градиентного спуска одной оценки недостаточно: чтобы дойти до окрестности минимума, нужны десятки таких оценок подряд, что превращает задачу в месяцы вычислений на одном устройстве.

Почему это важно

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

Случайный поиск

Интуиция

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

Метод

Случайный поиск (random search). Задана область поиска $\mathcal{X}$ (например, допустимые диапазоны значений каждого гиперпараметра). Алгоритм на каждой итерации $t = 1, \dots, T$:

1. Выбирает случайную точку $x_t \in \mathcal{X}$ (из равномерного или другого заданного распределения).
2. Вычисляет $f(x_t)$ — одно обращение к оракулу.
3. Запоминает лучшую из всех точек, встреченных к этому моменту: $x^\*_t = \arg\min_{s \le t} f(x_s)$.

После $T$ итераций возвращается $x^\*_T$ как найденное приближение к оптимуму. Ключевое свойство метода — полная независимость итераций друг от друга: точка $x_{t+1}$ выбирается заново из области $\mathcal{X}$, не опираясь на результат в $x_t$ (в отличие от градиентных методов, где каждый шаг явно строится на основе предыдущего).

Разбор примеров

Пример 1 (случайный поиск против сеточного перебора на двух гиперпараметрах). Пусть нужно подобрать скорость обучения $\eta \in [0{,}0001,\ 0{,}1]$ (в логарифмическом масштабе) и коэффициент регуляризации $\lambda \in [0{,}00001,\ 0{,}01]$ (тоже в логарифмическом масштабе), при бюджете в 9 обращений к оракулу. Сеточный перебор (grid search) разбил бы каждый диапазон на 3 значения и перебрал все $3 \times 3 = 9$ комбинаций — получилась бы регулярная сетка $3\times3$, где по факту опробовано только 3 различных значения $\eta$ и 3 различных значения $\lambda$. Случайный поиск с теми же 9 обращениями выбрал бы 9 случайных пар $(\eta,\lambda)$, и — что важно — при этом было бы опробовано, как правило, около 9 различных значений $\eta$ и около 9 различных значений $\lambda$ по отдельности, просто в случайных сочетаниях друг с другом. Если, как это часто бывает на практике, качество модели существенно зависит только от одного из двух гиперпараметров (скажем, от $\eta$, а $\lambda$ почти не влияет в разумном диапазоне), сеточный перебор тратит впустую 6 из 9 обращений на повторение одних и тех же трёх значений $\eta$ при разных $\lambda$, тогда как случайный поиск успевает опробовать в разы больше различных значений именно того параметра, который действительно важен.

Пример 2 (случайный поиск на простой одномерной функции с числовой трассировкой). Пусть $f(x) = (x-3)^2 + 1$ на отрезке $x \in [0,10]$ (точный минимум в $x^\*=3$, $f(3)=1$). Смоделируем 6 итераций случайного поиска со следующими случайными точками (для наглядности зафиксируем конкретные значения, как если бы их выдал генератор случайных чисел): $x_1=7{,}2,\ x_2=1{,}5,\ x_3=4{,}1,\ x_4=2{,}8,\ x_5=8{,}9,\ x_6=3{,}3$.

Обрати внимание: точки вовсе не образуют плавную сходящуюся траекторию, как у градиентного спуска, — они разбросаны по всему отрезку почти хаотично (итерация 5 даёт откровенно плохую точку $8{,}9$ со значением $35{,}81$). Но лучшее найденное значение $x^\*_t$ монотонно улучшается (или остаётся тем же) с каждой итерацией просто по построению алгоритма, и уже после четырёх случайных попыток метод нашёл точку $2{,}8$ с $f(2{,}8)=1{,}04$ — очень близко к истинному минимуму $f(3)=1$.

Пример 3 (случайный поиск для дискретного архитектурного выбора). Вернёмся к задаче выбора типа функции активации из примера про дискретные переменные. Пусть область поиска — комбинация из трёх дискретных решений: функция активации (ReLU / tanh / sigmoid), число слоёв (2 / 3 / 4 / 5) и наличие dropout (да / нет) — всего $3\times4\times2=24$ возможные комбинации. Случайный поиск здесь работает без всяких модификаций: на каждой итерации просто равновероятно выбирается одна из 24 комбинаций, обучается модель, фиксируется результат. Это ровно тот случай, где метод конечных разностей неприменим в принципе (нет непрерывной переменной, по которой можно сдвигаться на $\varepsilon$), а случайный поиск работает без единой модификации алгоритма — потому что для него не важна структура пространства поиска, важно только умение из этого пространства случайно доставать точки и умение сравнивать значения функции в них.

Почему это важно

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

Метод одновременных возмущений (SPSA)

Интуиция

Вернёмся к проблеме метода конечных разностей: чтобы оценить градиент по $n$ переменным, нужно $2n$ обращений к функции — по паре на каждую координату отдельно. Идея SPSA (Simultaneous Perturbation Stochastic Approximation, метод одновременных возмущений) в том, чтобы не трогать координаты по одной, а сдвинуть все координаты сразу, причём случайным образом — и всего с двумя такими «одновременными» сдвигами (а не с $2n$) получить достаточно информации, чтобы построить осмысленную оценку направления движения. Это как если бы вместо того, чтобы по очереди наклонять каждую ножку стола, проверяя устойчивость, ты один раз слегка тряхнул весь стол во всех направлениях сразу и по тому, как он качнулся, сделал вывод о том, какие ножки нужно подправить.

Метод

SPSA — оценка градиента через одно случайное возмущение. Пусть текущая точка $x \in \mathbb{R}^n$. Генерируется случайный вектор возмущения $\Delta \in \mathbb{R}^n$, каждая компонента которого независимо принимает значение $+1$ или $-1$ с равной вероятностью (распределение Радемахера). Функция вызывается всего дважды:

$$y_+ = f(x + c\Delta), \qquad y_- = f(x - c\Delta)$$

где $c>0$ — малый параметр шага возмущения. Оценка градиента по каждой координате $i$ строится по формуле:

$$\widehat{\nabla f}_i(x) = \frac{y_+ - y_-}{2c\,\Delta_i}$$

Обрати внимание на принципиальное отличие от метода конечных разностей: там для получения $i$-й компоненты градиента возмущалась только $i$-я координата, а здесь возмущаются все координаты сразу вектором $\Delta$, а вклад $i$-й компоненты в общее изменение функции «выделяется» делением на $\Delta_i$. Для одной итерации SPSA требуется всего 2 обращения к функции — независимо от размерности $n$, тогда как конечным разностям требуется $2n$. Оценка $\widehat{\nabla f}_i(x)$ по одному-единственному случайному возмущению — зашумлённая и грубая для каждой отдельной координаты в отдельности, но в среднем (по математическому ожиданию за много случайных $\Delta$) она указывает верное направление, и на практике SPSA используют внутри итеративного процесса, похожего на стохастический градиентный спуск: $x_{t+1} = x_t - a_t\,\widehat{\nabla f}(x_t)$, где $a_t$ — убывающая последовательность шагов, а шум от неточной оценки на отдельных итерациях сглаживается за счёт их большого числа.

Разбор примеров

Пример 1 (одна итерация SPSA на функции с известным градиентом — проверка идеи). Пусть $f(x_1,x_2) = x_1^2 + 3x_2^2$ (та же функция, что и в примере 2 про конечные разности), точный градиент в точке $(2,1)$ — $(4,6)$. Зададим $c=0{,}01$ и случайное возмущение $\Delta = (+1,-1)$ (одно из двух возможных направлений в двумерном случае):

Оценка получилась $(-2{,}00,\ 2{,}00)$ — заметно далека от точного градиента $(4,6)$ по каждой отдельной компоненте, причём знак по первой координате даже перепутан! Это ожидаемо и совершенно нормально для одной реализации SPSA: оценка сильно зашумлена именно потому, что одно и то же изменение функции $y_+-y_-$ пытается объяснить сразу обе координаты одновременно.

Пример 2 (усреднение по нескольким случайным возмущениям резко улучшает оценку). Повторим ту же процедуру для точки $(2,1)$ ещё с тремя случайными возмущениями: $\Delta^{(2)}=(-1,+1)$, $\Delta^{(3)}=(+1,+1)$, $\Delta^{(4)}=(-1,-1)$, с тем же $c=0{,}01$.

Усредним по всем четырём оценкам: по первой координате $(-2{,}00+2{,}00+10{,}00+10{,}00)/4 = 20{,}00/4=5{,}00$, по второй координате $(2{,}00-2{,}00+10{,}00+10{,}00)/4=20{,}00/4=5{,}00$. Усреднённая оценка $(5{,}00,\ 5{,}00)$ уже заметно ближе к истинному градиенту $(4,6)$, чем любая из отдельных оценок по одному возмущению, хотя всё ещё не идеальна при таком малом числе усреднений. Этот пример иллюстрирует главный компромисс SPSA: одна оценка почти бесполезна по отдельности, но экономична (всего 2 вызова функции), а качество направления улучшается за счёт накопления по многим итерациям самого процесса оптимизации — точно так же, как шум отдельных мини-батчей в стохастическом градиентном спуске сглаживается по ходу многих шагов.

Пример 3 (сравнение стоимости SPSA и конечных разностей на 20 гиперпараметрах). Вернёмся к примеру из раздела про конечные разности — 20 гиперпараметров, каждое обучение модели занимает 2 часа. Методу конечных разностей для одной оценки градиента требовалось $2n=40$ обращений — 80 часов. Методу SPSA для одной оценки градиента требуется ровно 2 обращения, независимо от того, 20 гиперпараметров или 2000, — 4 часа. Если для сходимости алгоритму требуется, скажем, 50 таких оценок подряд (50 итераций SPSA-версии градиентного спуска), суммарная стоимость составит $50\times2=100$ обращений — 200 часов для SPSA против $50\times40=2000$ обращений — 4000 часов для конечных разностей при том же числе итераций. SPSA здесь выигрывает в 20 раз по числу вызовов оракула — ровно во столько же раз, сколько переменных в задаче, потому что именно от размерности $n$ зависит выигрыш SPSA над конечными разностями: чем больше параметров, тем сильнее конечные разности проигрывают SPSA в стоимости.

Почему это важно

SPSA — это прямой и элегантный ответ на главную проблему конечных разностей: зависимость стоимости оценки градиента от размерности задачи. Освобождаясь от этой зависимости (2 вызова функции вместо $2n$), SPSA становится практически применимым там, где конечные разности заведомо неприменимы — например, при оптимизации политики нейросети с тысячами весов в обучении с подкреплением, где $2n$ обращений к среде обошлись бы совершенно неподъёмно. Цена за это — резко возросший шум в оценке направления на каждой отдельной итерации (как ты видел в примере 1), который компенсируется не точностью одной оценки, а большим числом итераций самого процесса оптимизации. Это ровно тот же компромисс точности отдельного шага и общей стоимости, с которым ты уже встречался в теме стохастического градиентного спуска: там тоже жертвовали точностью оценки градиента на одном шаге (используя один мини-батч вместо всего датасета) ради того, чтобы делать в целом гораздо больше дешёвых шагов за то же вычислительное время.

Практика: 30 заданий

Базовые задания (1–10)

Задание 1: Функция $f(x) = x^2$, оценить $f'(2)$ методом конечных разностей с $\varepsilon=0{,}1$.

Задание 2: Функция $f(x) = x^3$, оценить $f'(1)$ методом конечных разностей с $\varepsilon=0{,}1$.

Задание 3: Сколько обращений к функции требует метод конечных разностей для оценки градиента функции $n=5$ переменных?

Задание 4 (машинное обучение): Обучение модели с одним набором гиперпараметров занимает 30 минут. Требуется оценить градиент качества модели по 8 гиперпараметрам методом конечных разностей. Сколько времени это займёт?

Задание 5: Функция $f(x,y)=2x^2+y^2$, точка $(1,2)$, оценить $\partial f/\partial x$ методом конечных разностей с $\varepsilon=0{,}01$.

Задание 6: Объяснить своими словами, почему нельзя вычислить аналитический градиент функции «качество модели после обучения» по гиперпараметру «число слоёв».

Задание 7: Случайный поиск на функции $f(x)=(x-5)^2$ на отрезке $[0,10]$ дал точки $x_1=1,\ x_2=8,\ x_3=6,\ x_4=4{,}5$ со значениями $f(x_1)=16,\ f(x_2)=9,\ f(x_3)=1,\ f(x_4)=0{,}25$. Какая точка будет возвращена как лучшая после всех четырёх итераций?

Задание 8: Сколько обращений к функции требует одна итерация SPSA, оценивающая градиент функции от 100 переменных?

Задание 9: SPSA, точка $x=(1,1)$, возмущение $\Delta=(+1,+1)$, $c=0{,}1$. Найти точки $x+c\Delta$ и $x-c\Delta$.

Задание 10 (машинное обучение): При одинаковом бюджете в 12 обращений к оракулу сравнить, сколько итераций (оценок градиента) успеет сделать метод конечных разностей на задаче с 6 гиперпараметрами и метод SPSA.

Средние задания (11–20)

Задание 11: Функция $f(x)=x^4$, оценить $f'(1)$ методом конечных разностей с $\varepsilon=0{,}1$ и сравнить с точным значением.

Задание 12: Оценить $f'(1)$ для $f(x)=x^4$ из предыдущего задания с более мелким шагом $\varepsilon=0{,}01$ и показать, что ошибка уменьшилась примерно в 100 раз.

Задание 13 (машинное обучение): Датасет для оценки гиперпараметров: 15 гиперпараметров, обучение модели занимает 45 минут. Требуется 10 итераций градиентного метода на основе конечных разностей. Сколько суммарно часов это займёт?

Задание 14 (машинное обучение): Та же задача (15 гиперпараметров, 45 минут на обучение, 10 итераций), но с использованием SPSA. Сколько часов это займёт, и во сколько раз это быстрее конечных разностей?

Задание 15: Случайный поиск на функции $f(x,y)=x^2+y^2$ на квадрате $[-5,5]\times[-5,5]$ дал три точки: $(3,3)$ с $f=18$, $(-1,2)$ с $f=5$, $(0{,}5,\,0{,}5)$ с $f=0{,}5$. Какая точка лучшая и насколько она близка к истинному минимуму?

Задание 16: Объяснить, почему сеточный перебор (grid search) может быть менее эффективен, чем случайный поиск, если качество модели чувствительно только к одному из двух гиперпараметров.

Задание 17: SPSA, функция $f(x,y)=x^2+y^2$, точка $(3,1)$, возмущение $\Delta=(+1,-1)$, $c=0{,}05$. Вычислить оценку градиента $\widehat{\nabla f}$.

Задание 18: По результату предыдущего задания объяснить, почему знак оценки $\widehat{\nabla f}_2$ оказался правильным (отрицательным для минимизации в сторону уменьшения $y$... уточнить), а величина — заметно искажена.

Задание 19 (машинное обучение): В задаче обучения с подкреплением веса политики $\theta$ имеют размерность $n=500$. Оценить, во сколько раз SPSA дешевле метода конечных разностей для одной оценки градиента.

Задание 20: Функция $f(x)=\sin(x)$, оценить $f'(0)$ методом конечных разностей с $\varepsilon=0{,}1$ и сравнить с точным значением $f'(0)=\cos(0)=1$.

Продвинутые задания (21–30)

Задание 21 (машинное обучение): Обучение модели с заданными гиперпараметрами стоит в среднем 15 долларов вычислительного времени в облаке. Нужно оценить градиент качества по 12 гиперпараметрам методом конечных разностей, а затем сделать 8 итераций градиентного спуска в пространстве гиперпараметров. Оценить общую стоимость в долларах.

Задание 22 (машинное обучение): Та же задача, что в предыдущем задании, но с использованием SPSA вместо конечных разностей. Оценить экономию в долларах.

Задание 23: Функция $f(x,y,z)=x^2+2y^2+3z^2$, точка $(1,1,1)$, точный градиент $(2,4,6)$. Оценить, сколько обращений к функции потребует метод конечных разностей для полной оценки этого градиента, и вычислить оценку по координате $z$ с $\varepsilon=0{,}01$.

Задание 24: Для той же функции $f(x,y,z)=x^2+2y^2+3z^2$ в точке $(1,1,1)$ выполнить одну итерацию SPSA с возмущением $\Delta=(+1,+1,-1)$ и $c=0{,}01$, вычислив оценки по всем трём координатам.

Задание 25: Случайный поиск для подбора трёх дискретных архитектурных решений: тип функции активации (3 варианта), число слоёв (4 варианта), наличие батч-нормализации (2 варианта). Сколько всего различных комбинаций в пространстве поиска, и почему метод конечных разностей здесь неприменим в принципе?

Задание 26 (машинное обучение): В задаче обучения с подкреплением награда за эпизод зашумлена: при одних и тех же весах политики $\theta$ повторный запуск даёт разные значения награды из-за случайности среды. Объяснить, почему это делает метод конечных разностей особенно ненадёжным по сравнению с SPSA в такой обстановке.

Задание 27: Оценить, при каком минимальном числе гиперпараметров $n$ метод SPSA становится хотя бы в 10 раз дешевле метода конечных разностей по числу обращений к функции на одну оценку градиента.

Задание 28: Функция $f(x)=e^x$, оценить $f'(0)$ методом конечных разностей с $\varepsilon=0{,}2$ и сравнить с точным значением $f'(0)=e^0=1$.

Задание 29 (машинное обучение): Спроектировать (описать словами, без кода) стратегию подбора трёх гиперпараметров нейросети — скорости обучения, размера батча и коэффициента регуляризации, — используя случайный поиск при бюджете в 30 полных обучений модели. Указать, какие распределения разумно использовать для каждого гиперпараметра.

Задание 30 (машинное обучение): Сравнить три метода нулевого порядка урока (конечные разности, случайный поиск, SPSA) по критерию «число гиперпараметров», при котором каждый из них становится практически неприменимым или явно невыгодным, и обосновать вывод.

Частые ошибки

Разберём типичные ошибки, которые встречаются при первом знакомстве с методами нулевого порядка.

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

• Выбирают слишком маленький шаг $\varepsilon$ в методе конечных разностей, не учитывая шум оракула. Если функция зашумлена (как метрика качества модели, которая колеблется от запуска к запуску), слишком малый $\varepsilon$ приводит к тому, что разница $f(x+\varepsilon)-f(x-\varepsilon)$ оказывается сопоставима по величине со случайным шумом самой функции, а не с реальным изменением от сдвига аргумента — оценка градиента превращается в шум, усиленный делением на маленькое число $2\varepsilon$.

• Забывают, что стоимость конечных разностей растёт линейно с числом переменных. Как показано в примере с 20 гиперпараметрами и в задании 21, метод, прекрасно работающий на функции двух-трёх переменных, может оказаться абсолютно неприменимым на практике при 20-50 переменных просто из-за числа необходимых обращений к дорогому оракулу — об этом нужно думать заранее, выбирая метод, а не сталкиваться с этим после нескольких дней бесплодных вычислений.

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

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

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

Главное запомнить

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

• Подбор гиперпараметров модели — классический пример задачи оптимизации нулевого порядка: «функция» здесь — это «обучить модель и посмотреть на качество», у которой нет аналитического градиента по гиперпараметрам в принципе.

• Метод конечных разностей приближает градиент через $f'(x)\approx\dfrac{f(x+\varepsilon)-f(x-\varepsilon)}{2\varepsilon}$, требуя $2n$ обращений к функции для оценки градиента по $n$ переменным — стоимость растёт линейно с размерностью, что делает метод непрактичным при десятках и сотнях переменных.

• Случайный поиск — простейший метод нулевого порядка: пробует случайные точки и запоминает лучшую из найденных; он одинаково легко работает с непрерывными, дискретными и смешанными пространствами переменных, но не использует историю испытаний для направленного улучшения поиска.

• SPSA оценивает градиент всего за 2 обращения к функции (вместо $2n$ у конечных разностей), возмущая сразу все координаты одним случайным вектором и вычисляя вклад каждой координаты делением на её компоненту в этом векторе.

• Цена экономии SPSA — сильно зашумлённая оценка на каждой отдельной итерации; метод работает корректно только как часть итеративного процесса со многими случайными возмущениями, где шум усредняется по итерациям.

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

• Метод конечных разностей практически неприменим при десятках-сотнях переменных; SPSA хорошо масштабируется именно по этому параметру и потому используется там, где счёт параметров идёт на сотни и тысячи, — например, при оптимизации весов политики в обучении с подкреплением.

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

Связь с темами курса

Этот урок стоит на границе двух больших семейств методов курса. С одной стороны, метод конечных разностей и SPSA — по своей структуре они всё ещё пытаются восстановить градиент, просто приближённо, а не аналитически, и затем используют его почти так же, как это делал обычный градиентный спуск из урока 285 или стохастический градиентный спуск из урока 286: сделать шаг против оценённого направления, повторить. В этом смысле сегодняшний урок — прямое продолжение градиентной линии курса, только с заменой точного $\nabla f$ на приближённую оценку $\widehat{\nabla f}$.

С другой стороны, случайный поиск, разобранный в этом уроке, уже не пытается оценивать градиент вовсе — он полагается только на сравнение значений функции в случайных точках. Это прямой мост к следующим урокам курса — эволюционным алгоритмам, генетическим алгоритмам, методу роя частиц (particle swarm optimization) и алгоритму имитации отжига (simulated annealing), которые ты изучишь в уроках 295–298. Все эти методы объединяет одна общая идея — они не оценивают градиент вообще, ни точно, ни приближённо, а поддерживают набор (популяцию, рой, одну блуждающую точку) кандидатов и целенаправленно улучшают их на основе сравнения значений функции, используя механизмы, вдохновлённые естественной эволюцией или физическими процессами. Методы нулевого порядка сегодняшнего урока и метаэвристики следующих уроков решают одну и ту же задачу — оптимизацию без градиента, — но идут к решению разными путями: один путь имитирует градиентный спуск с шумной заменой производной, другой отказывается от идеи «направления» и заменяет её идеей «отбора среди множества кандидатов». Понимание обоих подходов и трезвая оценка их сравнительных издержек — именно то, что понадобится, когда придёт время выбирать конкретный инструмент для настройки гиперпараметров реального проекта.

Интересные факты

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

• В библиотеках для подбора гиперпараметров (например, scikit-learn с RandomizedSearchCV) случайный поиск реализован как полноценная встроенная альтернатива сеточному перебору именно потому, что на практике при ограниченном бюджете испытаний он регулярно показывает более высокое качество итогового результата при том же числе полных обучений модели.

• Существует эффектная модификация SPSA — двусторонняя оценка не только градиента, но и гессиана (2SPSA), которая позволяет строить приближённый аналог метода Ньютона для оптимизации нулевого порядка, используя всего несколько дополнительных вызовов функции сверх обычного SPSA.

• В обучении с подкреплением методы, родственные SPSA и случайному поиску, легли в основу целого направления под названием «стратегии эволюции» (evolution strategies) — в 2017 году исследователи из OpenAI показали, что подход, во многом похожий на оптимизацию через случайные возмущения весов политики, способен обучать сложных агентов не хуже, а иногда быстрее классических методов «градиента политики» (policy gradient), требующих дифференцируемости среды.

Лайфхаки

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

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

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

• При выборе шага $\varepsilon$ в методе конечных разностей избегай обеих крайностей: слишком большой $\varepsilon$ даёт грубое приближение из-за нелинейности функции (задание 28), слишком маленький — усиливает шум оракула и ошибку округления при вычислениях; разумная отправная точка — пробовать несколько порядков величины и смотреть на устойчивость оценки.

• Держи в уме простое правило масштаба: если параметров меньше пяти и оракул дешёвый — конечные разности вполне рабочий выбор; если параметров десятки и больше или оракул дорогой — переходи к SPSA, случайному поиску или методам следующих уроков курса.

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

На этом граница между двумя мирами этого раздела курса пройдена: ты видел, как градиентные методы — от простого спуска до Adam — управляют обучением моделей, когда есть доступ к точной производной, и как методы нулевого порядка позволяют действовать даже тогда, когда этой роскоши нет вовсе. Но и конечные разности, и SPSA, и случайный поиск — всё ещё методы, которые работают с одной текущей точкой или одним направлением за раз, пусть даже приближённым или зашумлённым. В следующих уроках курса — про эволюционные и генетические алгоритмы, метод роя частиц и имитацию отжига — ты увидишь принципиально другой взгляд на ту же проблему: вместо одной блуждающей точки — целая популяция кандидатов, которая эволюционирует, соревнуется и отбирается по аналогии с живой природой. Это следующий, куда более изобретательный шаг в мире оптимизации без градиента — и он начинается прямо со следующего урока.