CMA-ES с маржей: новый вариант CMA-ES для оптимизации черного ящика со смешанными целыми числами, представленный в…

В этой статье представлена CMA-ES с Margin, которая реализована в Optuna v3.1.0. CMA-ES с маржой [1] — это вариант CMA-ES для оптимизации смешанного целочисленного черного ящика (MI-BBO), где пространство поиска содержит как непрерывные, так и целочисленные переменные, такие как оптимизация гиперпараметров.

В этой статье для объяснения CMA-ES с маржей упоминается следующее:

Внедрение оригинального CMA-ES.
Проблемы адаптации CMA-ES к MI-BBO.
Основные идеи CMA-ES с Margin.
Преимущества CMA-ES с запасом по сравнению с другими методами.

Что такое CMA-ES в первую очередь?

Стратегия эволюции адаптации ковариационной матрицы (CMA-ES) [2] является одним из перспективных методов непрерывной оптимизации черного ящика, где целевая функция не задана в аналитической форме. CMA-ES проводит оптимизацию в следующие этапы:

Выборка нескольких решений (непрерывных векторов) из многомерного распределения Гаусса (MGD)
Оцените решения с помощью целевой функции
Обновление параметров распределения MGD на основе ранжирования решений
Повторите шаги с 1 по 3

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

Применение CMA-ES к оптимизации черного ящика смешанных целых чисел

CMA-ES часто применяется для смешанно-целочисленной оптимизации черного ящика (MI-BBO), включая оптимизацию гиперпараметров [3]. Поскольку CMA-ES представляет собой метод непрерывной оптимизации черного ящика, необходимо дискретизировать часть выборочного непрерывного вектора, чтобы адаптировать его к MI-BBO. Однако из-за плато, вызванного дискретизацией, целые переменные возможных решений фиксируются на одной целочисленной переменной. Следующая анимация показывает поведение, когда CMA-ES минимизирует f(x) = x_0^2 + x_1^2, где x_0 — непрерывная переменная, а x_1 — целочисленная переменная.

Целочисленная переменная x_1 получается путем округления непрерывной переменной, выбранной из MGD. Пунктирный эллипс представляет собой эллипс достоверности MGD. Красная звезда указывает оптимальное положение решения. Мы наблюдаем, что значение x_1 для решения-кандидата, отобранного из MGD, зафиксировано на уровне 3. Эта фиксация происходит, если дисперсия маргинального распределения меньше, чем ширина целочисленной переменной. Когда фиксация происходит на ранней стадии оптимизации, становится сложно улучшить значение оценки.

CMA-ES с запасом

CMA-ES с запасом (CMA-ESwM) [1] представляет собой вариант CMA-ES, недавно предложенный для MI-BBO. CMA-ESwM вводит нижнюю границу предельной вероятности, называемую границей, так что выборка не привязана к одной целочисленной переменной. Запас — это распространенный метод оценки алгоритмов распределения (EDA) для двоичных доменов для решения проблемы фиксации битов на 0 или 1. Ниже приводится описание того, как включить идеи запаса в CMA-ES.

Как показано на рисунке выше, мы рассматриваем случай дискретизации непрерывной переменной, выбранной из MGD, в двоичную переменную. В левой части рисунка видно, что вероятность выборки непрерывной переменной в области, дискретизируемой до 0, высока, а результирующая целочисленная переменная фиксируется на 0, т. Е. Целочисленная переменная 1 редко выбирается . MGD немного изменен, чтобы исключить фиксацию, как показано на правой стороне рисунка. Затем коррекция увеличивает вероятность выборки целочисленной переменной 1, тем самым устраняя фиксацию. Эту идею также можно применить к фиксации целочисленных переменных, но подробности в этой статье опущены.

Следующая анимация показывает поведение, когда CMA-ESwM минимизирует f(x) = x_0^2 + x_1^2, где x_0 — непрерывная переменная, а x_1 — целочисленная переменная.

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

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

Преимущества CMA-ES с запасом по сравнению с другими методами

Если вы планируете применить CMA-ES к MI-BBO, например, для оптимизации гиперпараметров, я рекомендую вместо этого использовать CMA-ESwM. В частности, чем значительнее доля целочисленных переменных, тем больше преимущество CMA-ESwM над CMA-ES. Вы можете увидеть сравнение между CMA-ES и CMA-ESwM с использованием задач HPO-bench здесь. Кроме того, в [4] представлено сравнение с другими методами оптимизации черного ящика, где показано, что CMA-ESwM превосходит другие методы при более высоких размерностях.

Как использовать CMA-ES с Маржей в Оптуне

В Optuna вы можете легко использовать CMA-ES с Margin, просто указав аргумент with_margin для CmaEsSampler следующим образом:

import optuna
from optuna.samplers import CmaEsSampler

def objective(trial):
    ...  # Include discrete search space.

study = optuna.create_study(sampler=CmaEsSampler(with_margin=True))
study.optimize(objective, ...)

Заключение

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