В этой статье наглядно объясняется, как работает алгоритм CMA-ES в библиотеке Optuna. Подойдёт тем, кто хочет понять принцип оптимизации, не углубляясь в сложную математику и английскую документацию.

Что такое Optuna и сэмплинг

Optuna — это библиотека для оптимизации гиперпараметров. Вместо полного перебора она использует результаты предыдущих запусков, чтобы умно выбирать новые значения гиперпараметров, например, такие, которые уменьшат loss или улучшат метрики вроде recall и precision.

Каждый запуск модели с определённым набором гиперпараметров (например, learning_rate = 0.01, batch_size = 32) — это одна точка в пространстве возможных решений. Задача Optuna — находить следующую точку так, чтобы приблизиться к оптимальному решению.

Процесс выбора следующей точки называется сэмплированием. Алгоритмы, которые это делают, — сэмплеры. Они определяют, в какую сторону двигаться и какие значения выглядят многообещающе. Основные сэмплеры в Optuna:

• TPE
• Random
• CMA-ES (Covariance Matrix Adaptation Evolution Strategy)

В этой статье подробно разбирается CMA-ES.

Шаг 1: Задание пространства гиперпараметров

Цель CMA-ES — найти глобальный минимум целевой функции. На практике это может быть, например, ошибка модели XGBoost в зависимости от гиперпараметров scale_pos_weight и max_depth.

Начнём с точки (0, -1). Алгоритм будет искать следующие точки в окрестности текущей. Эту окрестность можно представить как доверительный эллипс — область, в которой с высокой вероятностью будут находиться перспективные точки.

Для начала зададим:

• sigma = 0.8 — начальный шаг поиска (влияет на радиус области)
• среднее — начальный центр поиска (координаты начальной точки)
• ковариационная матрица C — единичная матрица, что означает симметричный поиск (форма области — круг, а не эллипс)

Таким образом, область поиска — круг радиусом σ·√5.991 ≈ 1.96, в котором с 95% вероятностью будут сгенерированные точки. Единичная ковариационная матрица означает, что поиск ведётся одинаково во всех направлениях.

Шаг 2: Сэмплирование точек

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

На каждой итерации генерируется 15 новых точек по формуле:

x = mean + sigma × N(0, C)

где:

• mean — текущее среднее (центр поиска)
• sigma — длина шага
• N(0, C) — двумерное нормальное распределение с нулевым средним и ковариационной матрицей C
• C — ковариационная матрица
• 15 — размер выборки

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

Шаг 3: Отбор лучших точек

Лучшими считаются точки с минимальным значением целевой функции. Из 15 сгенерированных выбираем топ-7 (половину).

Эти лучшие (красные) точки используются для определения направления дальнейшего поиска. Худшие (синие) отбрасываются.

Каждой лучшей точке присваивается вес — чем лучше точка, тем больше её вклад в обновление центра поиска.

Новое среднее (новый центр поиска) вычисляется как взвешенное среднее координат лучших точек. Это похоже на градиентный спуск: мы двигаемся туда, где функция даёт лучшие значения.

Шаг 4: Адаптация ковариационной матрицы и шага поиска

Ковариационная матрица C определяет форму области поиска. Её обновление позволяет алгоритму «запоминать» удачные направления и адаптироваться к ландшафту функции.

Новая матрица — это комбинация старой и новой, построенной по лучшим точкам. Формула обновления:

C = (1 - c_cov) × C + c_cov × Σ(w_i × d_i × d_i^T)

где:

• c_cov — скорость обучения для обновления матрицы (например, 0.9)
• d_i — нормализованные шаги лучших точек
• w_i — веса точек

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

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

Формула включает несколько ключевых параметров:

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

Если алгоритм уверенно движется в одном направлении, шаг увеличивается. Если топчется на месте — уменьшается. Это позволяет балансировать между скоростью и точностью.

Резюме: как работает CMA-ES

Алгоритм повторяется до сходимости. Основные шаги:

1. Начинаем с одной точки и круговой области поиска
2. Генерируем новые точки вокруг центра
3. Оцениваем их по значению целевой функции
4. Выбираем лучшие и перемещаем центр поиска
5. Обновляем форму области (через ковариационную матрицу)
6. Регулируем размер шага в зависимости от уверенности в направлении
7. Повторяем, пока не найдём глобальный минимум

Преимущества CMA-ES

CMA-ES — мощный метод оптимизации без градиентов. Его ключевые преимущества:

• Работает с функциями, у которых нет производных, есть шум, разрывы или локальные минимумы
• Не требует тонкой настройки — большинство параметров адаптируется автоматически
• Эффективен в пространствах от нескольких до сотен измерений
• Хорошо масштабируется и поддерживает параллельные вычисления
• Сходится быстро на квадратичных функциях, даже без градиентов

Основная идея — адаптация ковариационной матрицы и управление шагом поиска — позволяет алгоритму учиться геометрии функции на ходу.

Таким образом, CMA-ES сочетает случайный поиск и интеллектуальную адаптацию, оставаясь надёжным инструментом для сложных задач оптимизации в Optuna.

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

Optuna - библиотека для оптимизации гиперпараметров. Вместо полного перебора она использует историю своих прошлых попыток, чтобы предполагать, какие значения параметров сработают лучше - например, уменьшат лосс или оптимизируют метрики recall, precission и др.

Каждая отдельная попытка optuna - запуск модели с определенным набором гиперпараметров. Например: learning rate = 0.01, batch_size = 32 и т.д. . В пространстве всех возможных комбинаций такой набор является отдельной точкой. Задача optuna - выбрать следующую точку для проверки так, чтобы с каждой попыткой приближаться к оптимальному решению (например, минимизировать loss)

Такой процесс выбора следующей точки называется сэмплированием (sampling), а алгоритмы, которые выбирают точку - сэмплерами. Они решают в какую сторону двигаться и какие значения гиперпараметров выглядят "многообещающе". Можно выделить 3 основных сэмплера:

1. TPE
2. Random
3. Covariance Matrix Adaptation Evolution Strategy или сокращенно CMA-ES(будет рассмотрен в статье)Перейдем к разбору алгоритма

1 шаг : Задание пространства гиперпараметров

Для начала определим целевую функцию, которую будем минимизировать. Пусть это будет двумерная функция (на практике это непосредственно функция от гиперпараметров того же XGBoost, например f(scale_pos_weight, max_depth) = ошибка модели):

Итак, задача CMA-ES: найти глобальный минимум.

За начальную точку возьмем точку (0, -1).

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

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

Введемначальный шаг поискаsigma = 0.8 (будет влиять на радиус, в котором ищется следующая точка),начальное среднее области(пока что у нас область характеризует одна точка, поэтому среднее это есть непосредственно координаты этой точки),начальную ковариационную матрицуC как единичную (она будет задавать форму области поиска) - область поиска будет кругом (Шаг поиска и ковариационная матрица и способ их задания подробнее рассмотрим в шаге 4) :

Мы встали в начальную точку и приготовились искать. Область поиска - круг радиусом σ·√5.991 ≈ 1.96, внутри которого с вероятностью 95% окажутся сгенерированные точки. Ковариационная матрица = I означает, что сначала мы ищем одинаково во всех направлениях (круг, а не эллипс).

2 шаг: Сэмплирование точек

Этап сэмплирования находится в генерации потенциально "хороших" точек - тех, кто больше всего устремит нас в точку глобального экстремума. Мы уже выделили доверительный интервал, внутри которого с 95-процентной вероятностью будут находиться эти точки.

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

где:- k-й кандидат в поколении g+1- текущее среднее (центр поиска)  (сейчас - центр окружности)- текущая длина шага (0.8)- нормальное распределение (у нас двумерное)- ковариационная матрица, отвечающая за форму области поиска (сейчас единичная)— размер выборки (возьмем 15)

Таким образом мы отправляем точки в разные стороны на поиск минимума.

3 шаг: Отбор лучших точек

Интуитивно понятно, что лучшие точки - те, в которой целевая функция будет минимальна. Поэтому посмотрим на значения функции в этих точках и выделим топ-7 (половину):

Таким образом, мы оценили, кто из первично сгенерированных 15 точек нашел самые "глубокие" места. Лучшие (красные) точки будут использованы, чтобы решить, куда двигаться дальше. Худшие (синие) отбрасываются.

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

Теперь обновим среднее* (новый центр лучших точек) - новое среднее распределения поиска - это взвешенное среднее отобранных красных точек из выборки (веса уже были вычислены на предыдущем шаге)

*Формула взвешенного среднего:

Тогда новый центр поиска:

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

4 шаг: Адаптация ковариационной матрицы и глобального шага

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

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

Формула обновления:

- обновленная ковариационная матрица- текущая ковариационная матрица— learning rate для rank-μ update () (возьмем 0.9)- нормализованные шаги лучших точек- веса точек с прошлого шага ()— количество лучших точек

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

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

"Дальность поиска" (sigma)

- эволюционный путь (cumulative step-size adaptation path)- ожидаемая длина вектора из стандартного нормального распределения- скорость обучения (learning rate)- демпфирующий параметр

Разберем подробнее, что означает каждый из этих параметров

Эта формула довольно обьемная и, так как целью является понять принцип работы и неглубоко копаться в мат. части, важно понять принцип каждого из параметров, а также как он влияет на итоговую величину sigma.

1. (эволюционный путь). Это вектор в пространстве поиска, который накапливает информацию о том, в каком направлении двигался центр распределения (среднее) на протяжении последних итераций.

2.(ожидаемая длина вектора из стандартного нормального распределения) - эталонная длина. Если бы центр распределения двигался совершенно случайно (без всякого влияния отбора точек), то средняя длина его пути стремилась бы именно к этому значению. Это то, что мы бы наблюдали при отсутствии направленного движения.

3.(скорость обучения). Это коэффициент скорости обучения, который определяет, как быстро алгоритм учитывает новую информацию при обновлении направления поиска. Его можно интерпретировать как “длину памяти” алгоритма:

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

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

Таким образом, после каждой итерации CMA-ES мы смотрим, насколько уверенно движемся. Если мы некоторое время уверенно двигались в одном направлении, то есть смысл увеличить шаг (есть уверенность, что мы движемся в нужную сторону). Если же мы топчемся на месте, необходимо уменьшить шаг (сделать его точнее).

Резюмируем шаги алгоритма

Продолжим алгоритм до сходимости для наглядности:

Таким образом, CMA-ES помогает для нахождения глобального минимума loss-a без использования производных:

1. Начинаем с одной точки и круговой области поиска
2. Генерируем точки
3. Смотрим, какие точки пришли в самое глубокое место ладшафта (находим минимумы функции)
4. Перемещаем центр к лучшим точкам
5. Изменяем форму поиска (эллипс) под ландшафт
6. Увеличиваем или уменьшаем шаг в зависимости от успеха
7. Повторяем, пока не найдем глобальный минимум

Covariance Matrix Adaptation Evolution Strategy (CMA-ES)имеет уникальные свойства, которые делают его важным инструментом для решения сложных задач, где многие подходы терпят неудачу.

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

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

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

Кроме того, CMA-ES не требует особенно тонкой настройки параметров. Его стандартные параметры хорошо работают на огромном классе задач. Нужно только задать начальную точку и начальный шаг - все остальное алгоритм сделает сам, адаптируясь по ходу поиска.

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

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

В итоге CMA-ES объединяет случайный поиск и более продвинутые методы оптимизации. Благодаря этому он остаётся надёжным и универсальным инструментом для решения сложных задач.

Нам будет очень приятно, если Вам понравилась данная статья! Статью подготовили студенты 4 курса Антонова Анна и Сорокина Ольга.