Алгоритмы подбора гиперпараметров для моделей
Введение
В предыдущих сериях (статья 1, 2) мы рассмотрели разновидности алгоритмов градиентного спуска, которые позволяют находить минимум функции. А у неё можно посчитать градиент. В реальном мире встречаются задачи, где градиент недоступен, либо слишком дорогой для вычисления. Например, подбор гиперпараметров модели — параметров, которые не обучаются на данных, а задаются заранее. В таких случаях стандартные методы градиентного спуска не применимы. Значит, нужны методы оптимизации без градиента.
Они, в свою очередь, опираются на другие подходы: исследуют пространство параметров случайным образом, оценивая качество решения и постепенно улучшая найденные варианты. К ним относятся и простые подходы (Random Search и Grid Search), и более сложные — эволюционные алгоритмы и байесовская оптимизация.
В статье рассмотрим несколько алгоритмов, которые реализованы в Optuna и помогают эффективно находить оптимальные параметры при минимизации одной метрики, даже если градиенты недоступны. Давайте начинать 🙂
Grid Search
💡Grid Search — полный перебор всех возможных комбинаций значений гиперпараметров и выбор такой комбинации, при которой значение оптимизируемой функции минимально.
Этот метод гарантированно находит минимум на заданной сетке, но с ростом числа гиперпараметров и размера их диапазонов, он очень быстро замедляется. То есть его асимптотика
Пример: предположим, вы хотите купить квартиру в Москве и приходите на просмотры.
С Grid Search ваш подход будет выглядеть примерно так — вы заранее составляете сетку районов и параметров:
- районы: Хамовники, Марьино, Ховрино, Пресненский;
- тип дома: панельный, кирпичный;
- этаж: 1, 5, 10.
Затем строго по списку ходите смотреть все возможные комбинации. Даже если вы с первого показа поняли, что Хамовники вам не нравятся, вы всё равно продолжите просмотр в этом районе. Более того, вы никогда не пойдёте в квартиры на 2-ом этаже, хотя потенциально они могут быть хорошими.
Random Search
💡Random Search — метод подбора гиперпараметров, при котором значения выбираются случайным образом из заданного диапазона.
Для каждой случайной комбинации оценивается качество модели, и в итоге сохраняется лучшая из них. Этот метод не гарантирует нахождение глобального минимума, но в большинстве случаев находит хорошие решения быстрее, особенно при большом числе гиперпараметров.
Рассмотрим пример сравнения Random Search и Grid Search.
Пусть есть два гиперпараметра:
- A — почти не влияет на результат,
- B — сильно влияет на качество модели.
В случае с Grid Search, предположим, значения разбиваются с помощью равномерной сетки с шагом 0.1. То есть совершается 10*10=100 запусков обучения и валидации, а перебор только 10 уникальных значений «полезного» гиперпараметра. Более того, если оптимальное значение B, например, равно 0.65, то его не будут исследовать, так как оно не лежит в сетке.
Если же запустить Random Search 100 раз — каждый раз выберутся случайные A и B, значит, будет исследовано 100 уникальных значений «полезного» гиперпараметра. Эти значения не ограничены сеткой, как в Grid Search, что повышает шансы найти близкое к оптимуму решение.
Представьте, что вы ищете квартиру, используя Random Search.
Вместо того, чтобы обходить всё по сетке, вы просто:
- Берёте общий список квартир по Москве.
- Закрываете глаза и случайным образом выбираете, какие объявления посмотреть.
- Ездите на просмотры в хаотичном порядке: сегодня — элитка в Пресненском, завтра — однушка в Митино, послезавтра — «что-то среднее» в Перово.
Иногда вы случайно попадаете в отличную квартиру уже на 5-ом просмотре. И покрываете больше разных значений (возможно, зайдёте в квартиру на 2-ом этаже).
А иногда нет.
Quasi Monte Carlo
У классического Random Search есть один серьёзный недостаток: точки генерируются случайно. Из-за этого участки исследуются неравномерно. К счастью, эта проблема решается с помощью использования квазислучайных последовательностей, например, Sobol или Halton. Они генерируют точки так, чтобы равномерно покрывать пространство, но при этом оставаться детерминированными и не повторяться. Правда, это даёт ощутимое преимущество только для низкоразмерных пространств из-за проклятия размерности.
Tree-structured Parzen Estimator
Перечисленные выше алгоритмы не учитывали точки, полученные на предыдущих шагах. Но интуитивно понятно, что оптимальное значение стоит искать в области, где уже наблюдались хорошие значения. Именно так и работает Tree-structured Parzen Estimator (TPE): алгоритм ищет области, где с наибольшей вероятностью будет найден оптимум, основываясь на предыдущих значениях.
Алгоритм сначала оценивает значение минимизируемой функции для случайных точек и делит их на «хорошие» и «плохие», затем строит вероятностные модели для каждой группы. Далее выбирает следующую точку для проверки из области, где максимальное отношение вероятности встретить «хорошую» точку к вероятности встретить «плохую».
Возвратимся к примеру с покупкой квартиры. Сначала вы посещаете десять случайных квартир. Со временем вы понимаете, что именно вам нравится: в Хамовниках большинство квартир красивые, но есть пара с «бабушкиным ремонтом», а вот на первом этаже жить совсем не хочется. Вы перестаёте ходить на показы квартир на первом этаже, чаще выбираете Хамовники и замечаете, что в панельках жить тоже не хотите — область поиска сужается. Но тут вы замечаете пару ЖК в Марьино, которые вам нравятся, и начинаете ездить туда тоже.
Tree-structured Parzen Estimator работает так: постепенно учится на прошлом опыте, выделяет хорошие варианты, отбрасывает плохие и концентрируется на областях, где высоки шансы найти оптимальный вариант.
В следующих параграфах рассмотрим подробно составные части этого алгоритма.
Разделение точек на «плохие» и «хорошие»
Алгоритм строит вероятностную модель гиперпараметров, то есть использует апостеорное распределение, чтобы выбрать новые значения. В обычном байесовском подходе моделируется распределение функции ошибки \(p(f|x)\) при заданных параметрах \(x\), а в TPE — два распределения, для «хороших» и «плохих» параметров:
- \(l(x)=p(x∣f<f^∗)\) — «хорошие» параметры со значением оптимизируемой функции ниже, чем \(f^*\);
- \(g(x)=p(x∣f≥f^∗)\) — «плохие» параметры со значением оптимизируемой функции выше, чем \(f^*\).
Когда анализируются точки, в которых известны значения функции — \(k\%\) лучших помечаются как «хорошие», а остальные считаются «плохими». То есть \(f^*\) — пороговое значение, такое, что лучше него \(k\%\) точек. Процент «хороших» точек \(k\) является гиперпараметром и по умолчанию равен \(15\).
Построение распределений
Предположим, есть набор «хороших» наблюдений \(x_1, x_2…x_n\). У каждого существует несколько параметров, которые считаются независимыми.
Чтобы оценить, где чаще встречаются «хорошие» точки, строится плотность вероятности и размывается каждая точка с помощью ядра \(K\) в её окрестностях. После прохода по всем объектам строится отдельное распределение для каждого параметра:
Так как параметры независимы, рассчитывается финальная плотность вероятности по всем координатам с помощью перемножения по ним:
\(l(x)=\prod l_j(x_j)\)
Ядро K — функция, которая «размазывает» точку, чтобы получить гладкую кривую. Чаще всего используют гауссовское ядро:
\(K(t)=\frac{1}{\sqrt{2\pi}\sigma}exp(-\frac{t^2}{2\sigma^2})\)
Где:
- \(\sigma\), равная минимальному расстоянию между точками \(x\);
- каждый \(x_i\) создаёт «горку», с их суммой аппроксимируется распределение плотности.
Ядро позволяет получить гладкую функцию, где точки, близкие к «хорошим», получают высокую вероятность. Благодаря этому TPE учитывает предыдущие значения.
Аналогично для «плохих» точек строится \(g(x)\).
💡Важно отметить: в этом подходе не важно, насколько одна точка лучше другой, и у всех них одинаковый вес. Это можно учесть, используя взвешенное ядро, но обычно (Optuna/Hyperopt) так не делают.
💡Для категориальных переменных, \(l(x)\) и \(g(x)\), это просто дискретное распределение по частотам. Если какое-то из значений не встречалось в предыдущих наблюдениях — ему присваивается небольшая вероятность.
Выбор следующего значения
Следующее значение \(x\) выбирается так, чтобы отношение вероятности встретить «хорошую» точку к вероятности встретить «плохую» было бы максимальным:
\(x_{next}=argmax(\frac{l(x)}{g(x)})\)
Независимость случайных величин
В классическом TPE при построении распределений \(l(x)\) и \(g(x)\) параметры считаются независимыми, то есть распределение по всем координатам вычисляется как произведение отдельных распределений для каждой переменной. Это позволяет легко строить плотности даже в высоких размерностях и ускоряет выбор следующей точки.
Однако TPE может учитывать структурированные зависимости между параметрами, если они задаются в виде дерева (как, например, в Optuna).
В то же время некоторые параметры могут быть зависимыми. Например, если оптимизируются гиперпараметры для SVM, то для полиномиального ядра тюнится степень, но для других ядер это не имеет смысла. В таких случаях распределение строится условно, тогда алгоритм никогда не предложит невозможные комбинации. Именно поэтому в названии алгоритма фигурирует слово «TREE» — оно отражает деревоподобную структуру зависимостей между параметрами, где выбор одного параметра определяет, какие другие параметры становятся активными для оптимизации.
Также существует модификация под названием Multivariate TPE, которая строит совместное распределение для всех параметров, что позволяет учитывать корреляцию между ними. Она сложна в плане вычислительных ресурсов, поэтому для большого числа параметров её не стоит использовать, но для небольшого набора гиперпараметров — окей!
Эволюционные алгоритмы
В этом разделе мы рассмотрим общий подход в эволюционных алгоритмах и рассмотрим один из них — CMA-ES.
Общий принцип
Эволюционные алгоритмы вдохновлены реальным процессом эволюции и состоят из нескольких шагов: Отбор, Мутация и Скрещивание (Рекомбинация).
Процесс выглядит следующим образом:
- Генерация случайной популяции индивидов. Выбирается несколько точек в пространстве поиска. Для каждого индивида рассчитывается значение фитнесс-функции (насколько этот индивид «приспособлен» для того, чтобы быть решением). Если ищется максимум функции, можно использовать её саму как фитнесс-функцию.
- Отбор. Лучшие индивиды отбираются по значению фитнесс-функции. Например, можно взять N лучших или отобрать с вероятностью, пропорциональной значению фитнесс-функции.
- Скрещивание индивидов. Берутся несколько индивидов-родителей (обычно два), создаётся новый потомок на основании характеристик родителей. Например, при оптимизации двухмерной функции, можно брать X от одного родителя, а Y — от другого.
- Мутация. С некоторой вероятностью потомок «мутирует». В случае оптимизации двухмерной функции можно, например, немного изменить X или Y.
- Проверка условия остановки. Новые потомки добавляются к старым индивидам, либо заменяют их, пока не выполнится условие остановки (например, число итераций или определённый порог фитнесс-функции).
CMA-ES
CMA-ES (Covariance Matrix Adaptation Evolution Strategy) — один из самых мощных эволюционных алгоритмов для оптимизации непрерывных функций. Он похож на классический эволюционный алгоритм: есть популяция точек, они оцениваются по фитнесс-функции, далее отбираются лучшие и создаются новые точки через комбинацию и мутации.
Главная особенность CMA-ES — он автоматически подстраивает распределение, из которого генерируются новые точки, учитывая форму функции и корреляции между параметрами. То есть алгоритм «учится» на том, как устроено пространство поиска.
Основная идея алгоритма: на каждой итерации поддерживается многомерное нормальное распределение кандидатов: \(x∼N(m,\sigma^2C)\), где \(m\) — центр области поиска, \(\sigma\) — размер шага, а \(C\) — ковариационная матрица, описывающая форму области поиска. Такое распределение выбирается, потому что оно удобно для адаптивного поиска: его центр, масштаб и ковариация легко подстраиваются под форму функции, а генерация новых точек остаётся симметричной и плавной в многомерном пространстве.
💡Ковариационная матрица — матрица, отвечающая за форму распределения. Она определяет направление поиска и корреляцию между координатами.
- На первом шаге это единичная матрица, то есть все координаты независимы, и форма области поиска — круг.
- Если у неё разные диагональные значения — распределение вытянуто по осям.
- Если есть ненулевые элементы вне диагонали — координаты скоррелированы, и распределение повернуто по осям.
На каждом шаге сэмплируются кандидаты из \(x∼N(m,\sigma^2C)\), отбираются лучшие по значению оптимизируемой функции и обновляются \(m\), \(\sigma\) и \(C\), чтобы движение происходило в многообещающем (promising) направлении.
Алгоритм обновления \(m\), \(\sigma\) и \(C\)
Обновление \(m\)
Для обновления центра области поиска используется простое взвешенное среднее лучших кандидатов:
\(m^{(g+1)}=\sum w_ix_i\)
Точкам с лучшим значением функции даётся больший вес, а сумма весов равна единице. Веса остаются неизменными на протяжении всей работы алгоритма и задаются с помощью позиции точки в списке от лучшей к худшей: чем выше позиция (лучше решение), тем больше вес, обычно с логарифмическим убыванием.
Формулу можно переписать в эквивалентном виде, так как сумма весов равна единице:
\(m^{(g+1)}=m^{(g)}+(\sum w_ix_i -\sum w_im^{(g)})=m^{(g)}+\sum w_i(x_i -m^{(g)})\)
Степенью со скобками будет обозначен номер шага. Тогда можно добавить параметр \(c_m\), отвечающий за скорость обновления среднего, то есть движения в сторону минимума (аналог learning rate для Gradient Dsecent):
\(m^{(g+1)}=m^{(g)}+c_m\sum w_i(x_i -m^{(g)})\)
Но в большинстве случаев он берётся равным единице.
Эволюционный путь
Для обновления \(\sigma\) используется эволюционный путь \(\rho_{\sigma}\) — накопительный вектор, который хранит информацию о направлении и длине шагов:
Первое слагаемое \((1-c_{\sigma})\rho_{\sigma}^{(g)}\) отвечает за забывание старых шагов и использует \(c_{\sigma}\) — коэффициент скорости забывания.
Во втором слагаемом используется нормализированное смещение среднего. В знаменателе — сдвиг среднего, а в числителе \(\sigma\). Так мы считаем не абсолютный шаг, а относительный:
\(\frac{m^{(g+1)}-m^{(g)}}{\sigma^{(g)}}\)
Нормализированное смещение среднего умножается на \(C^{-1/2}\), чтобы выровнять координаты по осям (убирается влияние ориентации), и масштабируется на множитель \(\sqrt{c_{\sigma}(2-c_{\sigma})u}\) . Он компенсирует уменьшение дисперсии от экспоненциального сглаживания и стабилизирует ожидаемую длину пути.
\(u=\frac{1}{\sum(w_i^2)} — эффективное\ количество\ родителей\)
Обновление \(\sigma\)
Эволюционный путь используется для обновления сигмы:
\(\sigma^{(g+1)}=\sigma^{(g)}*\exp(\frac{c_\sigma}{d_{\sigma}}\frac{||\rho_\sigma||}{e}-1)\)
Здесь \(e\) — теоретическая длина случайного вектора из многомерного стандартного нормального распределения, которая является константой для фиксированного числа параметров:
\(e=||N(0,I)||\)
Если длина эволюционного пути больше, чем случайные, то \(\sigma\) увеличивается, а в противном случае — уменьшается.
Коэффициент \(c_\sigma/d_\sigma\) контролирует скорость адаптации.
Таким образом, CMA-ES контролирует эффективность движения среднего: если оно движется в одном направлении, значит, нужно идти дальше, а если нет — нужно «собрать больше информации» и для этого «потоптаться на месте». А благодаря эволюционному пути мы сглаживаем колебания.
Обновление \(C\)
Последняя часть — обновление матрицы ковариации:
\(
C^{(g+1)}=(1-c_1-c_u\sum w)C^{(g)}+c_1p_c^{(g+1)}p_c{^{(g+1)}}^T +c_u\sum^\lambda_iw_iy_{i:\lambda}^{g+1}{y_{i:\lambda}^{g+1}}^T\)
В этой формуле используется ldf дополнительных параметра:
- rank-one коэффициент \(c_1\):
\(с_1=\frac{2}{n^2}\)
- rank-\(u\) коэффициент \(c_u\), которые зависят только от размерности задачи:
\(c_u=min(\frac{u}{n^2},1-c_1)\)
Первое слагаемое отвечает за затухание старой ковариации (оно может быть равно единице). Второе учитывает длинные успешные направления среднего за несколько поколений. Это матрица, которая задаёт эллипс вдоль направления эволюционного пути и подталкивает ковариацию в сторону, где алгоритм стабильно улучшался, а не на отдельные точки.
Последнее слагаемое содержит \(y_{i:\lambda}\) — нормализованное отклонение:
\(y_i=\frac{x_{i:\lambda}-m^{(g)}}{\sigma}\)
Итоговая матрица для третьего слагаемого отражает рассеивание лучших точек, подстраивая эллипс под локальную кривизну.
💡Алгоритм приближает градиентный метод второго порядка (метод Ньютона).
В Ньютоновском методе — шаг:
\(Δx=−H^{−1}∇f\)
А в CMA-ES — ковариационная матрица играет роль приближения к \(H^{-1}\), но без явного вычисления градиента или гессиана.
Заключение
Резюмируем информацию по каждому алгоритму в виде таблицы с кратким описанием, при каком сценарии применять различные алгоритмы.
| Метод | Основная идея | Преимущества | Недостатки | Применение |
|---|---|---|---|---|
| Grid Search | Полный перебор по сетке значений | Прост в реализации, находит лучшее значение на сетке | Очень медленный при большом числе гиперпараметров, не учитывает информацию о прошлых запусках | Малое число гиперпараметров, ограниченные диапазоны |
| Random Search | Случайная выборка комбинаций (лучше использовать квазислучайные последовательности) | Быстрее Grid Search, хорошо покрывает пространство | Не учитывает прошлые запуски | Большое число гиперпараметров,когда часть из них не важна |
| TPE | Байесовский оптимизатор, строит модели лучших и худших гиперпараметров | Использует информацию о прошлых запусках, быстрее находит хорошие решения. Может работать с непрерывными, дискретными и категориальными гиперпараметрами | Сложнее в реализации, требует настройки распределений | Средние и большие задачи, смешанные типы гиперпараметров |
| CMA-ES | Эволюционный алгоритм с адаптивной ковариацией | Эффективен для непрерывных высокоразмерных задач, подстраивается под форму функции | Сложнее в реализации, больше вычислений на поколение | Непрерывные гиперпараметры, высокая размерность |
Помимо перечисленных алгоритмов существуют и другие, менее известные, но интересные подходов в оптимизации без градиента, например, симуляция отжига (Simulated Annealing), методы роя частиц (Particle Swarm Optimization). Также есть множество разновидностей эволюционных алгоритмов — их (не)полный список с кратким описанием можно посмотреть в документации библиотеки PyMoo.
Полезные ссылки
- Tree-Structured Parzen Estimator: Understanding Its Algorithm Components and Their Roles for Better Empirical Performance
- The CMA Evolution Strategy: A Tutorial
Cтарт — 9 марта
Computer Vision Rocket
