В этой статье я наглядно покажу, как именно работает алгоритм 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) = ошибка модели):

Визуализация функции Розенброка с глобальным минимумом в точке (1,1)

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

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

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

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

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

Инициализация начальной точки с координатами (0,-1)

Мы встали в начальную точку и приготовились искать. Область поиска - круг радиусом σ·√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 мы смотрим, насколько уверенно движемся. Если мы некоторое время уверенно двигались в одном направлении, то есть смысл увеличить шаг (есть уверенность, что мы движемся в нужную сторону). Если же мы топчемся на месте, необходимо уменьшить шаг (сделать его точнее).

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

Шаги алгоритма

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

2D-визуализация

3D-визуализация

Таким образом, 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 курса Антонова Анна и Сорокина Ольга.