Для начала поймём, в чём отличие параметров модели от гиперпараметров:
Рассмотрим, например, модель линейной регрессии:
\[f(X) = X w,\]где
Эта модель может обучаться посредством минимизации следующего функционала:
\[\mathcal{L} = \| y - X w\|^2 + C \| w \|^2,\]где $y$ — целевая переменная, $C$ — коэффициент регуляризации. В процессе минимизации $\mathcal{L}$ веса $w$ настраиваются по обучающей выборке, то есть являются параметрами. В то же время величина коэффициента регуляризации задаётся до начала обучения, то есть является гиперпараметром.
Ещё хороший пример — решающее дерево. Его гиперпараметры: максимальная глубина дерева, критерий ветвления, минимальное число семплов в листе дерева и ещё много других. А параметром является сама структура решающего дерева: обучение состоит в том, чтобы на каждом уровне дерева выбрать, по какому признаку должно произойти ветвление и с каким пороговым значением этого признака.
Качество модели может очень сильно варьироваться в зависимости от гиперпараметров, поэтому существуют разнообразные методы и инструменты для их подбора. При этом, вне зависимости от выбранного вами метода подбора гиперпараметров, оценку и сравнение моделей нужно проводить грамотно. Пусть у нас есть несколько моделей разной природы (метод ближайших соседей, случайный лес, логистическая регрессия) или несколько нейросеток с разными архитектурами. Нужно для каждой из моделей подобрать гиперпараметры, а затем модели с наилучшими гиперпараметрами сравнить между собой. Есть два наиболее часто используемых варианта:
Разделить выборку на тренировочную, валидационную и тестовую части, для каждой модели выбирать гиперпараметры, максимизирующие её метрики на валидации, а окончательное сравнение моделей проводить по тестовым метрикам. Разделения только на тренировочную и тестовую выборки недостаточно, так как в модель через подобранные гиперпараметры просачивается информация о тестовой выборке. Это означает, что на новых данных модели могут не сохранить свои качества и что их сравнение не будет честным.
Провести кросс-валидацию. Кросс-валидация может быть нужна в случаях, если данных мало или мы не хотим зависеть от конкретного выбора валидационного множества. Примерный алгоритм (картинка ниже):
Подробное описание процесса сравнения моделей между собой можно найти в разделах, посвящённых кросс-валидации и сравнению и оценке качества моделей. Далее мы рассмотрим несколько методов подбора гиперпараметров для моделей, а в конце будет приведён список питоновских библиотек, в которых эти методы реализованы, и дано верхнеуровневое сравнение всех описанных методов между собой.
Самый естественный способ организовать перебор наборов гиперпараметров — сделать перебор по сетке (Grid Search):
Примеры:
Перебор некоторых значений гиперпараметров можно вести по логарифмической шкале, так как это позволяет быстрее определить правильный порядок параметра и в то же время значительно уменьшить время поиска. Так можно подбирать, например, значение learning rate для градиентного спуска, значение константы регуляризации для линейной регрессии или метода SVM.
Сразу же видно естественное ограничение данного метода: если комбинаций параметров слишком много либо каждое обучение / тест длится долго, алгоритм не завершится за разумное время.
Полезные ссылки
Если у вас возникает очень большое количество комбинаций параметров, вы можете какими-то способами пытаться справляться с этой проблемой:
Последний способ называется Random Search. Для каждого гиперпараметра задаётся распределение, из которого выбирается его значение, и комбинация гиперпараметров составляется семплированием из этих распределений (хорошие советы по поводу выбора распределений можно найти в документации sklearn). Таким образом, благодаря случайному выбору очередной комбинации гиперпараметров вы можете найти оптимальную комбинацию за меньшее число итераций. Вот эта картиночка хорошо иллюстрирует отличия поиска по сетке от случайного поиска:
(картинка из оригинальной статьи)
Идея, проиллюстрированная на этой картинке, примерно в следующем (пояснение заимствовано из этого блог-поста). Качество нашей модели в зависимости от гиперпараметров — это функция многих переменных с некоторой нетривиальной поверхностью. Но эта поверхность может от одной из своих переменных зависеть сильно меньше, чем от другой. Если бы мы знали, какой гиперпараметр важнее для перформанса модели, мы бы рассмотрели больше его возможных значений, но часто у нас нет такой информации, и мы рассматриваем некоторое наперёд заданное число значений для каждого гиперпараметра. Random Search может за то же число итераций, что и Grid Search, рассмотреть более разнообразные значения гиперпараметров. Тем самым он с большей вероятностью найдёт те значения, которые больше всего влияют на качество модели, а значит, с большей вероятностью найдёт наилучшую комбинацию значений гиперпараметров.
В другом блог-посте есть ещё одно довольно интересное объяснение того, почему Random Search работает хорошо. Рассмотрим случай, когда у нас конечная сетка гиперпараметров (каждому гиперпараметру сопоставлено конечное число значений). В этой сетке выделим группу размера $5\%$ от общего числа наборов гиперпараметров, на которой модель достигает лучшего качества (можно мысленно отранжировать все наборы по качеству в некоторый список и взять топ $5\%$ этого списка). Тогда некоторый набор гиперпараметров не попадает в эту группу с вероятностью $1 - 0.05$. Если мы насемплировали $n$ наборов, то каждый из них не попал в эту группу с вероятностью $(1 - 0.05)^n$, и, соответственно, вероятность того, что хотя бы один насемплированный набор попал в лучшую группу, равна $1 - (1 - 0.05)^n$. Мы можем решить неравенство
\[1 - (1 - 0.05)^n \ge 0.95\]и выяснить, что при $n \ge 60$ мы попадём в топ $5\%$ с вероятностью, не меньшей $0.95$. Это в большинстве случаев значительно быстрее, чем перебор всех комбинаций гиперпараметров с помощью Grid Search.
Если в рассуждении выше у нас некоторым гиперпараметрам соответствует непрерывное распределение, то всегда можно предположить, что мы уже насемплировали из этих распределений некоторое конечное число значений (равное числу итераций Random Search), а дальше считать, что мы работаем с конечной сеткой.
Конечно, остаётся наша зависимость от самой сетки гиперпараметров, и не всякая сетка обязана содержать в себе глобальный максимум перформанса модели или даже гиперпараметры из интервала вокруг него.
Полезные ссылки
В машинном обучении достаточно часто встречаются такие термины, как exploration и exploitation. Суть этих терминов хорошо поясняет следующий пример из реальной жизни. Допустим, перед вами стоит выбор, в какой ресторан пойти сегодня. Пусть ваш любимый ресторан находится прямо за углом. Вы ходите туда каждый день и поэтому достаточно уверены в том, насколько вкусным будет ваш обед. Но при этом не рассматриваете никакие другие опции и, возможно, упускаете возможность поесть гораздо вкуснее в другом месте. Если же вы будете обедать каждый раз в новом месте, то очень часто будете не удовлетворены результатом.
В описанных далее методах подбора гиперпараметров будет так или иначе происходить поиск баланса между exploration и exploitation. Одно из основных отличий всех методов, которые будут описаны далее, от Grid Search и Random Search — возможность учитывать результаты предыдущих вычислений. Одна из возможных стратегий выбора точки для следующей итерации — exploration: исследование тех областей, в которых у нас мало семплов на текущей итерации, что даёт нам возможность с меньшей вероятностью пропустить оптимальное значение. Другая стратегия — exploitation: выбирать больше семплов в областях, которые мы достаточно неплохо изучили и где, как мы считаем, с большой вероятностью находится оптимум.
Байесовская оптимизация — это итерационный метод, позволяющий оценить оптимум функции, не дифференцируя её. Кроме того, на каждой итерации метод указывает, в какой следующей точке мы с наибольшей вероятностью улучшим нашу текущую оценку оптимума. Это позволяет значительно сократить количество вычислений функции, каждое из которых может быть довольно затратным по времени.
Подбор гиперпараметров тоже можно сформулировать в виде задачи, которая может решаться с помощью байесовской оптимизации. Пусть, например, наша функция — значение валидационных метрик в зависимости от текущего сочетания гиперпараметров. Её вычисление затратно по времени (нужно натренировать и провалидировать модель), и мы не можем вычислить градиенты этой функции по её переменным (нашим гиперпараметрам).
Байесовская оптимизация имеет две основные компоненты:
Простой пример acquisition function — сумма среднего вероятностной модели и стандартного отклонения с некоторым весом:
\[\alpha(x) = \mu(x) + \beta \sigma(x),\]где $x$ — точка из пространства, в котором мы оптимизируем целевую функцию (в нашем контексте — вектор значений гиперпараметров). На картинке ниже изображены обе компоненты, из которых складывается данная acquisition function, — среднее вероятностной модели $\mu$ (синий график) и доверительный интервал, ширина которого в каждой точке пропорциональна стандартному отклонению вероятностной модели (серая область). Среднее модели $\mu$ стремится приблизить искомую функцию $f$ и в точности равно $f$ в тех точках, где значения $f$ известны. Доверительный интервал имеет переменную ширину, так как чем дальше находится некоторая точка от тех, значения в которых известны, тем более не уверена модель в том, какое значение функции в этой точке, и тем шире доверительный интервал. Наоборот, в точках, где значения известны, доверительный интервал имеет нулевой радиус.
Байесовская оптимизация в общем случае представляет из себя следующий алгоритм. Пусть $S_t$ — множество предыдущих наблюдений целевой функции $f$: $(f(x_1), \ldots, f(x_t))$, а $\alpha(\cdot)$ — некоторая acquisition function.
Чтобы такой алгоритм работал эффективно, $\alpha$ должна быть легко вычислимой и дифференцируемой.
На рисунке ниже изображены три итерации этого алгоритма. Здесь пунктирная линия — это целевая функция, сплошная линия — график среднего вероятностной модели, фиолетовым цветом обозначен доверительный интервал модели.
Зелёный график снизу — это график acquisition function. Её значения велики там, где вероятностная модель предсказывает большие значения целевой функции (exploitation), и там, где велика неуверенность вероятностной модели (exploration).
На каждой итерации находится точка максимума acquisition function (чёрный крестик), и следующая итерация произойдёт в этой точке (серый кружок на графике функции). На нижнем графике побеждает exploitation, так как acquisition function верно предсказала, что наблюдения из неизвестных областей слабо повлияют на нашу текущую оценку максимума $f$.
Байесовская оптимизация хорошо работает, когда нужно оптимизировать небольшое число гиперпараметров, так как в наивной реализации алгоритм не поддаётся распараллеливанию. При большой размерности пространства гиперпараметров скорость сходимости не лучше, чем у обычного Random Search (как утверждается в этой статье).
Байесовская оптимизация в изначальной постановке предполагалась для работы с непрерывными гиперпараметрами, а для работы с категориальными гиперпараметрами ей нужны некоторые трюки:
Если нужно найти оптимальное значение только одного гиперпараметра и этот параметр категориальный, то можно, например, использовать Thompson sampling (как тут в разделе «Beta-Bernoulli bandit»). Вообще, проблему выбора наилучшего значения категориального гиперпараметра можно переформулировать как multi-armed bandit problem и использовать любой известный способ решения этой задачи.
Если категориальных гиперпараметров больше одного и кроме них есть некатегориальные, то:
Для дальнейших подробностей по байесовской оптимизации (в частности, конкретных примеров вероятностных моделей и разных acquisition function) можно использовать следующие источники:
Алгоритм TPE, как и алгоритм байесовской оптимизации, итерационный: на каждой итерации принимается решение о том, какие следующие значения гиперпараметров нужно выбрать, исходя из результатов предыдущих итераций. Но идейно имеет довольно сильные отличия.
Предположим сначала, что мы хотим сделать поиск оптимального значения для одного гиперпараметра.
На нескольких первых итерациях алгоритму требуется «разогрев»: нужно иметь некоторую группу значений данного гиперпараметра, на которой известно качество модели. Самый простой способ собрать такие наблюдения — провести несколько итераций Random Search (количество итераций определяется пользователем).
Следующим шагом будет разделение собранных во время разогрева данных на две группы. В первой группе будут те наблюдения, для которых модель продемонстрировала лучшее качество, а во второй — все остальные. Размер доли лучших наблюдений задаётся пользователем: чаще всего это $10-25\%$ от всех наблюдений. Картинка ниже иллюстрирует такое разбиение:
Далее некоторым образом строятся оценки распределения $\ell(x)$ лучших наблюдений и распределения $g(x)$ всех остальных в пространстве значений рассматриваемого гиперпараметра.
Если гиперпараметр принимает непрерывные значения, то распределения $\ell(x)$ и $g(x)$ можно оценить на основе Parzen window density estimation. Идея данного метода в следующем. Пусть у нас имеются точки $x_1, \ldots, x_n$, которые были насемплированы из некоторого неизвестного распределения $f$. Нам нужно каким-то образом оценить $f$ по известным данным. Для этого каждое наблюдение $x_i$ помещается в центр некоторого симметричного распределения $K$ с дисперсией $h$, а оценкой для $f$ становится смесь этих распределений:
\[\hat f_h(x) = \frac{1}{nh} \sum_{i = 1}^n K \left(\frac{x - x_i}{h}\right)\]Распределения $K$ обычно называют ядрами, примеры ядер можно найти тут. На картинке ниже показана зависимость вида итогового распределения от параметра $h$ (который часто называют bandwidth):
Чем больше у нас наблюдений, тем точнее можем оценить целевое распределение:
Если гиперпараметр категориальный и принимает значения $c_1, \ldots, c_n$, то в качестве $\ell(x)$ и $g(x)$ можно задать категориальные распределения в виде наборов из $n$ вероятностей $(p_1, \ldots, p_n)$, где $p_i$ соответствует вероятности насемплировать значение $c_i$. Значения $p_i$ для $\ell(x)$ будут пропорциональны числу раз, которое каждое из значений $c_i$ встретилось в группе лучших наблюдений (и, соответственно, худших наблюдений в случае $g(x)$). Например, пусть у гиперпараметра всего 3 значения и уже прошло 60 итераций алгоритма. Пусть среди лучших 15 испытаний 2 раза встретилось значение $c_1$, 5 раз встретилось значение $с_2$ и 8 раз встретилось значение $c_3$. Тогда $\ell(x) \sim \left( p_1 = \frac{2}{15}, p_2 = \frac{5}{15}, p_3 = \frac{8}{15} \right)$. Аналогично будет строиться $g(x)$.
На следующем шаге алгоритма мы семплируем несколько значений-кандидатов из распределения $\ell(x)$ (количество таких семплирований тоже задаётся пользователем, можно задать их число равным, например, 1000). Из насемплированных кандидатов мы хотим найти тех, кто с большей вероятностью окажется в первой группе (состоящей из лучших наблюдений), чем во второй. Для этого для каждого кандидата $x$ вычисляется Expected Improvement:
На самом деле стоит отметить, что в оригинальной статье величина $EI$ имеет более общее определение. Но там же доказывается, что максимизация $EI$ в исходном определении эквивалентна максимизации отношения выше.
Кандидат с наибольшим значением $EI(x)$ будет включён в множество рассматриваемых гиперпараметров на следующей итерации:
После того как было выбрано значение-кандидат, максимизирующее $EI$, обучается модель с этим значением гиперпараметра. После обучения мы замеряем её качество на валидационной выборке и в соответствии с этим результатом обновляем распределения $\ell(x)$ и $g(x)$: снова ранжируем всех имеющихся кандидатов по качеству модели с учётом последнего, из топ $10-25\%$ формируется обновлённое $\ell(x)$, из остальных — $g(x)$. Так происходит столько раз, сколько итераций алгоритма мы задали.
Теперь опишем, как алгоритм работает в общем случае, когда гиперпараметров более одного. Алгоритм работает с гиперпараметрами, представляя их в форме дерева (отсюда «tree» в названии). Например, в документации Hyperopt можно увидеть такой пример:
from hyperopt import hp
space = hp.choice('classifier_type', [
{
'type': 'naive_bayes',
},
{
'type': 'svm',
'C': hp.lognormal('svm_C', 0, 1),
'kernel': hp.choice('svm_kernel', [
{'ktype': 'linear'},
{'ktype': 'RBF', 'width': hp.lognormal('svm_rbf_width', 0, 1)},
]),
},
{
'type': 'dtree',
'criterion': hp.choice('dtree_criterion', ['gini', 'entropy']),
'max_depth': hp.choice('dtree_max_depth',
[None, hp.qlognormal('dtree_max_depth_int', 3, 1, 1)]),
'min_samples_split': hp.qlognormal('dtree_min_samples_split', 2, 1, 1),
},
])
На рисунке ниже изображено дерево, соответствующее данному примеру:
Корень дерева $\varepsilon$ — фиктивная вершина, введённая для удобства. Здесь первым уровнем дерева является выбор классификатора (наивный байес, SVM, решающее дерево). Дальнейшие уровни — гиперпараметры самих классификаторов и зависящие уже от них гиперпараметры (например, SVM $\to$ kernel $\to$ RBF $\to$ width). Движение по дереву во время итераций алгоритма происходит по некоторому пути от корня к листу и обратно вдоль пройденного пути (этот процесс подробнее описан ниже).
Под некоторыми вершинами записан набор гиперпараметров в скобках (например, kernel
и C
под SVM). Это означает, что при приходе в эту вершину значения всех гиперпараметров, перечисленных в скобках, должны так или иначе быть выбраны. Каждой вершине дерева, в которой будет происходить семплирование значений, сопоставляется своя пара $\ell(x)$ и $g(x)$ с учётом значений, насемплированных на этапе «разогрева». Каждому гиперпараметру, перечисленному в скобках, соответствует своя собственная пара. Если из названия гиперпараметра не идут стрелки (например, C
у SVM и min_samples_split
у Decision Tree), то это означает, что от его значения не зависят значения никаких других гиперпараметров. Поэтому либо будет выбрано его значение, максимизирующее $EI$ для соответствующих ему $\ell$ и $g$, либо уже ничего не нужно семплировать (как, например, в вершинах linear
или gini
). Если же из гиперпараметра идут стрелки на следующий уровень, то с помощью максимизации $EI$ будет выбрано, в каком направлении сделать переход. Например, из корня $\varepsilon$ выбирается, какой классификатор рассмотреть на следующем этапе, а из параметра kernel
можно перейти либо к RBF
, либо к linear
.
Теперь опишем сам алгоритм. Сначала так же, как и в одномерном случае, происходит «разогрев»: проводится некоторое количество итераций Random Search с теми изначальными распределениями, которые были заданы для гиперпараметров (в примере из Hyperopt эти распределения задаются как hp.qlognormal
, hp.lognormal
и т.д.). Затем начинается итерационное обновление дерева гиперпараметров. Обновление дерева на каждой итерации происходит в два этапа:
Пусть вы находитесь в корне $\varepsilon$ и выбираете классификатор. Допустим, классификатор SVM оказался оптимальным по критерию $EI$. Вы переходите в соответствующую ему вершину, и здесь вам нужно провести семплирование значений для двух гиперпараметров: kernel
и C
. Для C
вы выбираете некоторое значение, которое максимизирует $EI$. Пусть оно оказалось равно $0.1$. А для kernel
вы с помощью максимизации $EI$ выбираете, в какую вершину на следующем уровне вы отправитесь. Пусть эта вершина — RBF
. Для него вы семплируете конкретное значение width
— пусть оно оказалось равным $0.9$. Получилось, что вы прошли полный путь и получили модель с заданным набором гиперпараметров: $SVM(C = 0.1, kernel = RBF(width = 0.9))$, которую теперь можно провалидировать.
В качестве окончательного ответа алгоритм выдаёт набор гиперпараметров (или, как в примере выше, не только гиперпараметры, но даже саму модель), на котором было получено лучшее качество за все итерации. Число итераций алгоритма задаётся пользователем.
За дальнейшими деталями о процедуре обновления дерева для алгоритма TPE можно обратиться к данной статье и к исходному коду алгоритма TPE из библиотеки Hyperopt.
Стоит заметить, что если гиперпараметры не лежат вместе ни в одном пути в дереве, то TPE считает их независимыми. Это является недостатком данного алгоритма, так как некоторые гиперпараметры, находящиеся по смыслу в разных путях в дереве, зависят от друг от друга. Например, с регуляризацией мы можем тренировать нейросеть большее число эпох, чем без регуляризации, потому что без регуляризации сеть на большом числе эпох может начать переобучаться. В этом конкретном примере можно использовать такой трюк:
hp.choice('training_parameters', [
{
'regularization': True,
'n_epochs': hp.quniform('n_epochs', 500, 1000, q=1),
}, {
'regularization': False,
'n_epochs': hp.quniform('n_epochs', 20, 300, q=1),
},
])
Но если внутренние зависимости между гиперпараметрами вам неизвестны, то алгоритм не сможет найти их сам.
Критерий $EI$ позволяет методу TPE балансировать между exploration и exploitation. Семплирование из распределения $\ell(x)$ — это, с одной стороны, exploitation, так как гиперпараметры, семплируемые из него, близки к оптимуму, но это же привносит элемент exploration, так как семплируемые гиперпараметры не равны оптимуму в точности.
Для дальнейшего изучения темы можно использовать следующие источники:
Этот метод использует идеи из теории эволюционных стратегий и с самого начала включает в себя параллельные вычисления.
Методы, описанные выше, имеют свои сильные и слабые стороны.
В алгоритме PBT была сделана попытка объединить сильные стороны обеих групп, что проиллюстрировано на картинке ниже:
(источник картинки — статья, в которой был предложен алгоритм)
В процессе работы алгоритм обучает не одну модель, а целую популяцию $\mathcal{P}$ моделей — набор моделей одинакового типа, отличающихся только набором гиперпараметров:
\[\mathcal{P} = \{(\theta_i, h_i) \, | \, i = 1, \ldots, N \},\]где $\theta_i$ и $h_i$ — веса и гиперпараметры модели $i$ соответственно. Предполагается также, что модели обучаются как-то итерационно, например градиентным спуском (но могут использоваться и безградиентные методы, такие как эволюционные стратегии). Изначально каждая модель в популяции имеет случайные веса и гиперпараметры. Каждая модель из популяции тренируется параллельно с остальными, и периодически качество каждой модели замеряется независимо от остальных. Как только какая-то модель считается «созревшей» для обновления (например, прошла достаточное число шагов градиентного спуска или преодолела некоторый порог по качеству), у неё появляется шанс быть обновлённой относительно всей остальной популяции:
При таком подходе только лучшие пары моделей и гиперпараметров выживут и будут обновляться, что позволяет добиться более высокой утилизации ресурсов.
(источник картинки — статья, в которой был предложен алгоритм)
Стоит отметить, что наиболее оптимальный размер популяции, выявленный авторами в результате экспериментов, — от 20 до 40, что довольно много и не реализуется на обычном ноутбуке.
Красивая гифка с демонстрацией работы алгоритма:
Полезные ссылки
В библиотеке Scikit-learn есть реализации Grid Search и Random Search, что очень удобно, если вы используете модели из sklearn. Примеры их использования можно найти здесь.
В библиотеке Hyperopt реализованы три метода оптимизации гиперпараметров:
У них есть небольшой туториал по тому, как начать пользоваться библиотекой. Кроме того, у них есть обёртка над sklearn, позволяющая работать с моделями оттуда: Hyperopt-sklearn.
В библиотеке Optuna реализованы те же методы оптимизации, что и в Hyperopt, но по многим параметрам она оказывается удобнее. Хорошее сравнение Optuna и Hyperopt можно найти здесь.
В библиотеке Scikit-Optimize реализованы алгоритмы байесовской оптимизации и Random Search. Кроме самих методов оптимизации библиотека предоставляет отличный инструментарий для различных визуализаций. Хорошее описание возможностей библиотеки можно найти тут.
Библиотека Keras Tuner позволяет подбирать гиперпараметры для нейросеток, написанных на TensorFlow 2.0, и для обычных моделей из Scikit-learn. Доступные методы оптимизации — Random Search и Hyperband. Хороший гайд по использованию данной библиотеки можно найти тут.
Список описанных методов не исчерпывает все существующие на данный момент методы оптимизации гиперпараметров: остались за кадром такие алгоритмы, как ASHA, Hyperband, BOHB. Хороший сравнительный обзор этих трёх алгоритмов можно найти здесь. Далее приведено общее summary описанных выше алгоритмов, а также некоторые дополнительные замечания.
Grid Search. Хорошо работает, когда у вас совсем мало гиперпараметров либо вы смогли распараллелить его работу.
В защиту этого метода хочется сказать, что часто на практике приходится делать перебор гиперпараметров вообще вручную (если один инстанс вашей модели учится недели две и использует много ресурсов) либо по очень небольшой сетке. Так что метод вполне в ходу :)
Random Search. Метод представляет собой небольшое усложнение над Grid Search, но при этом оказывается намного более эффективным.
Байесовская оптимизация
Tree-structured Parzen Estimator
Population Based Training