HalvingSearch: ускорение поиска по сетке (grid search). Библиотека sklearn

Подбор гиперпараметров модели – одна из самых распространенных задач в data science. Если заранее неизвестно, какими могут быть оптимальные значения, приходится искать по сетке значений. Если у нас есть m гиперпараметров и для каждого задано n возможных значений, то число вариантов равно mn и для каждого нужно обучить модель и определить ее точность. Если мы используем перекрестную проверку (cross-validation), то это число надо умножить на число частей, на которые мы разбиваем набор данных.

Есть ряд алгоритмов оптимизации поиска, например байесовский – «осмысленный» поиск, при котором рассматриваются не все возможные сочетания гиперпараметров.

Относительно недавно sklearn был реализован еще один метод – halving search.

Ссылка

Метод реализован для регрессии и классификации. Принцип работы обоих вариантов одинаков.

Halving здесь означает «уполовинивание», т.е. деление на две части, хотя на практике используется деление на произвольное число частей (чаще всего на три).

Ниже модели с разными наборами гиперпараметров будем называть «кандидатами».

Идея в том, что проверку можно ускорить, уменьшив число объектов в учебном наборе данных. Однако при этом снижается точность прогноза, поэтому для окончательного отбора кандидатов лучше использовать все имеющиеся данные. Метод основан на следующем предположении:

Предположение: совсем плохих кандидатов можно отсеять, используя только часть выборки.

Видна аналогия с соревнованиями по кубковой системе. В начале участников много и задания не очень сложные. На первом раунде отсеиваются самые слабые. Потом задания усложняются и т.д., пока в финал не выйдут самые сильные, которые будут соревноваться на самых сложных заданиях.

Так же и в данном методе. Главный параметр алгоритма – factor, что можно перевести на русский как кратность (изменения числа кандидатов и размера выборки).

В первом раунде делается обычный поиск по сетке (grid search) для всех кандидатов, но на уменьшенной выборке (ее размер задает параметр min_resorces). На следующем раунде алгоритм уменьшает количество кандидатов в factor раз и увеличивает размер в выборки тоже в тоже число раз. Если все спланировать правильно, то на последней итерации будет использована (почти) вся выборка и число оставшихся кандидатов будет не больше кратности. Т.е. если кратность = 3, то в финале останется два или три кандидата.

Количество кандидатов алгоритм рассчитывает исходя из сетки параметров (param_grid), которую мы задаем так же как в обычном GridSearchCV.

Исходное значение размера выборки для первой итерации задает параметр min_resources.

Важно! Исходный размер выборки и кратность должны быть увязаны друг с другом и с размером полной выборки, чтобы на последней итерации была использована вся выборка и число кандидатов было не больше кратности. Иначе может получиться так, что достигнут полный размер выборки, а число кандидатов все еще больше кратности. Это не так страшно, просто на последней итерации будет много кандидатов, т.е. время работы алгоритма сократится не так сильно, как могло бы. Может получиться и наоборот: на последней итерации число кандидатов будет оптимальным, но размер выборки будет в разы меньше полного, что гораздо хуже.

Минимальный размер выборки можно и не задавать, например указав min_resources=’exhaust’. Тогда алгоритм сам подберет мин. размер так, чтобы на последней итерации получилось оптимальное сочетание.

Единственная возможная проблем здесь в том, что тогда на первой итерации будет слишком маленький размер выборки, для того чтобы сравнение кандидатов давало надежные результаты (или вообще рассчитанный размер выборки будет меньше единицы). В этом случае можно задать параметр aggressive_elimination=True и указать некоторый разумный минимальный размер выборки. Тогда на первых нескольких итерациях будет использован этот минимальный размер, пока размер, рассчитанный алгоритмом, не превысит это значение.

Пример. Полный размер выборки 14580 элементов. Задаем min_resources=1620.

Расчет размеров выборки по итерациям:

Минимальный размер выборки, рассчитанный алгоритмом для первой итерации, 20, но это слишком мало. Однако, поскольку мы задали aggressive_elimination=True и min_resources=1620, вплоть до 4-й итерации будет использовано значение 1620, и только потом оно будет расти, каждый раз увеличиваясь путем умножения на кратность.

Важное замечание: размер выборки, используемой на последней итерации всегда кратен min_resources!

Например, у меня был набор данных размером 42100 объектов. Если задать мин. размер 2000 и кратность 3, то итоге на последней итерации алгоритм будет использовать всего 18000 объектов, т.е. меньше половины выборки (2000 * 3 = 6000; 6000 * 3 = 18000).

В этом случае можно изменить мин. размер на 5262 и кратность на 2, тогда на последней итерации будут использованы почти все объекты – 42096. Также можно задать мин. размер 4677 и кратность 3 (42093 на последней итерации).

Получается, при делении на учебную и валидационную выборки (train_test_split) лучше подбирать размер учебной выборки под кратность и размер минимальной выборки.

Еще одно замечание. Выше в качестве параметра, определявшего сложность каждого раунда «соревнования» между кандидатами, был использован размер выборки. Однако можно использовать и другой параметр (в этом алгоритме его называют «ресурс»), например число деревьев (n_estimators) случайного леса. Для этого указываем resource=n_estimators (по умолчанию число элементов – n_samples).

Прочие параметры аналогичны алгоритму GridSearchCV.

По моему опыту, время действительно сокращается очень сильно. Запустил GridSearchCV утром и прекратил перед сном, потому что алгоритм перебрал менее половины комбинаций. HalvingSearchCV «разобрался» с большим набором гиперпараметров меньше, чем за 7 часов.