Прежде чем перейти к статье, хочу вам представить, экономическую онлайн игру Brave Knights, в которой вы можете играть и зарабатывать. Регистируйтесь, играйте и зарабатывайте!
Моей супруге, Елене Вишневской, посвящается
С целью автоматизации процесса подбора гиперпараметров автором данной статьи разработан алгоритм Helena.4.0. Конечной целью является создание автоматической системы построения моделей (auto-ML), которая бы подбирала гиперпараметры за минимальное время.
С помощью алгоритма Helena.4.0 можно подбирать гиперпараметры для моделей градиентного бустинга, нейросетей, и более того – для генетических алгоритмов. Автор считает, что алгоритмы Helena могут заменить в генетических алгоритмах генеративную часть – т.е. уйти от биологических аналогий, заменив псевдобиологическую генерацию признаков путем процедур «скрещивания» и «мутаций» на генерацию с помощью указанных алгоритмов.
Для поиска максимума функции алгоритм Helena.4.0 использует только ее значения, и не используют первые и последующие производные. Таким образом, этот алгоритм не требуют ни дифференцируемости, ни непрерывности максимизируемой функции.
Сравнение алгоритма Helena.4.0 с наиболее популярными конкурентами (Optuna, HyperOpt, RandomSearch) показывает его высокую конкурентоспособность.
В отличие от других алгоритмов, не использующих градиент для максимизации функции, алгоритмов Helena.4.0 способен успешно противостоять комбинаторному взрыву. Т.е. алгоритм Helena.4.0 достаточно стабильно работает, несмотря на увеличение размерности пространства. Время, необходимое алгоритму Helena.4.0 для поиска максимума функции, оценивается как квадратичная функция от размерности пространства.
Ниже в статье приведено подробное описание алгоритма Helena.4.0 и результаты сравнительных тестов с алгоритмами-конкурентами.
Основная идея алгоритма
Основная идея алгоритма состоит в поэтапном уменьшении объема пространства, в котором осуществляется поиск максимума функции. При этом уменьшение объема пространства осуществляется не за счет уменьшения количества измерений, а за счет сокращения диапазона, в котором мы ищем максимум. Этот диапазон сокращается по каждому измерению. С течением времени объем пространства, на котором алгоритм ищет максимум, сходится к небольшой величине, в котором и находится максимум функции.
Трансформационная функция как интерфейс связи между ядром алгоритма Helena и максимизируемой функцией
Алгоритм ищет максимум функции для любых гиперпараметров: строковых, дискретных и непрерывных.
При этом «под капотом» Helena всегда ищет оптимальное значение внутри единичного непрерывного гиперкуба, каждое из измерений которого связано с одним из гиперпараметров. Для перевода внутренних значений (непрерывных и распределенных от 0 до 1) во внешние значения (которые могут быть строковыми, дискретными и непрерывными в любом диапазоне) служит специальная трансформационная функция. Она устроена следующим образом.
а) для непрерывных гиперпараметров
Для непрерывных значений мы используем трансформационную функцию:
y = a + (b – a) xg, где:
x – значение гиперпараметра на отрезке [0, 1],
y – значение гиперпараметра, выходное значение трансформационной функции.
Здесь g - параметр, который отвечает за ту часть отрезка, на которой мы преимущественно ищем максимум. При g = 1 значения y будут равномерно распределены на интервале [a, b], при g > 1 мы будем концентрировать поиск преимущественно в левой части интервала, а при g < 1 – в преимущественно в правой части. Чем ближе g к бесконечности, тем больше значения параметра будут концентрироваться около значения a. Напротив, при ближе g к нулю, тем больше значения параметра будут концентрироваться около значения b.
б) для дискретных гиперпараметров
Если наш гиперпараметр – дискретная величина, принимающая значения от 1 до M, то мы разбиваем интервал [0, 1] на M отрезков. Координаты первого будут [0, 1 / M), второго - [1 / M, 2 / M)), последнего [(M – 1)/ M), 1]. Результатом трансформационной функции является номер отрезка, в который попала величина xg . g - по-прежнему параметр, который отвечает за ту часть отрезка, на которой мы преимущественно ищем максимум. Если g велико, то в функцию градиентного бустинга обычно будут попадать значений гиперпараметра, близкие к 1, в противном случае – к М.
Если наша дискретная величина принимает значения K, K + 1, .. K + S, где K не равно 1, то мы строим вышеописанную трансформационную функцию для величин 1 ... (S + 1), и к каждому значению добавляем слагаемое (K – 1).
в) для строковых гиперпараметров
Наконец, если гиперпараметр принимает строковые значения, каждому уникальному строковому значению ставится в соответствие натуральное число, после чего осуществляется кодирование как для функции с дискретными значениями.
Ядро алгоритма – постепенно сжимающийся N-мерный гиперкуб
Алгоритм Helena.4.0 базируется на идее RandomSearch.
На каждом шаге независимо друг от друга случайным образом генерируются числа xi , 1 ≤ i ≤ N, где N - число гиперпараметров. Число xi генерируется с помощью равномерного распределения на отрезке [xil,xir]. Первоначально для всех i: xil = 0,xir = 1. В ходе работы алгоритма xil растет, а xir уменьшается, что приводит к сужению пространства поиска максимума. Числа xi преобразуются в значения гиперпараметров yi с помощью трансформационной функции. Значения гиперпараметров передаются в максимизируемую функцию и рассчитывается ее значение f(y1,y2, …, yN). Набор сгенерированных случайных значений и соответствующее им значение функции {x1,x2, …, xN, f(y1,y2, …, yN)} запоминаются. Значения гиперпараметров {y1,y2, …, yN} не запоминаются – они всегда могут быть восстановлены с помощью трансформационной функции на основе чисел {x1,x2, …, xN}.
Правила сжатия N-мерного гиперкуба
В алгоритме Helena.4.0 сжатие пространства было поставлено на твердую статистическую основу. Каждые Т шагов алгоритм для каждого гиперпараметра по отдельности принимает решение о том, нужно ли сжимать пространство по этому гиперпараметру, или нет. Для этого текущий интервал подбора гиперпараметра делится на две половины: левую и правую. Рассматриваются значения максимизируемой функции за все время работы алгоритма. Они разделяются на две группы. В первую группу объединяются все значения максимизируемой функции, которым соответствуют значения данного гиперпараметра из левой половины интервала. Во вторую группу объединяются все значения максимизируемой функции, которым соответствуют значения данного гиперпараметра из правой половины интервала. Вне этих двух групп оказываются значения функции, которым соответствуют значения гиперпараметра, находящиеся вне текущего интервала подбора гиперпараметра. Такие значения максимизируемой функции в расчетах не участвуют.
Например, текущее значение гиперпараметра – от 0.5 до 0.75. В первую группу попадут значения максимизируемой функции, которые соответствуют значениям гиперпараметра от 0.5 до 0.625. Во вторую – от 0.625 до 0.75. Значения же максимизируемой функции, которые советуют значениям гиперпараметра от 0 до 0.5 и от 0.75 до 1, в расчётах участвовать не будут.
Затем с помощью критерия Манна-Уитни мы сравниваем средние значения максимизируемой функции в каждой из групп. Если среднее значение в первой группе больше среднего значения во второй, это значит, что значениям гиперпареметра из левой половины интервала соответствуют бОльшие значения максимизируемой функции. Поэтому мы сохраняем левую половину интервала, а правую отбрасываем. В дальнейшем мы будем вести поиск максимума только в левой половине интервала.
В противоположном случае мы сохраняем правую половину интервала, а левую отбрасываем.
Если же значения функции в обеих группах статистически неразличимы, то мы сохраняем интервала целиком. На основании критерия Манна-Уитни определяется уровень значимости, на котором мы можем считать средние значения в разных группах одинаковыми. Порог этого уровня значимости (p_value) является параметром алгоритма Helena.4.0.
Чем выше порог, тем раньше мы осуществляем сокращение пространства. С одной стороны, это ускоряет схождение алгоритма. С другой стороны, при высоком пороге мы можем случайно выбрать не тот интервал, на котором находится максимум, а возможности вернуться алгоритм уже не предоставляет.
Качество алгоритма Helena.4.0
Были проведены сравнения алгоритма Helena.4.0 с конкурентами – RandomSearch, Optuna, HyperOpt при подборе гиперпараметров градиентного бустинга. Сравнения осуществлялись по следующим характеристикам: средняя точность решения после 500 итераций, средняя точность решения после 50 итераций, среднее время работы на 500 итерациях. Сравнения показали конкурентосопособность алгоритма Helena.4.0. Результаты сравнений будут опубликованы в ближайшее время.
При этом алгоритм Helena.4.0 полностью превосходит конкурентов при росте числа измерений.
Так, ни один из конкурентов не смог за разумное время максимизировать функцию OneMax для 100 аргументов. Функция OneMax представляет собой среднее значение всех своих аргументов. При этом аргументы функции OneMax – дискретные, принимают значения {0, 1}.
Алгоритмы RandomSearch и HyperOpt не смогли найти максимум функции, Optuna потратила на поиск максимума более 10 часов. Helena.4.0 находит максимум за 47-190 секунд в зависимости от параметров алгоритма.
