Всем привет! В этом посте я расскажу, как наша команда приняла участие и заняла третье место в Black-Box Optimization Challenge — соревновании по автоматическому выбору параметров для моделей машинного обучения.
Особенность конкурса в том, что алгоритм не знает, какая модель машинного обучения используется, какую задачу она решает и за что отвечает каждый из оптимизируемых параметров.
Звучит как соревнование, в котором нельзя придумать ничего лучше случайного поиска, но существует целый класс алгоритмов для таких задач, о которых мы поговорим под катом.
Меня зовут Никита Сазанович, я студент 2 курса магистратуры» Программирование и анализ данных "в питерской ВШ?.
Три месяца я и моя команда из JetBrains Research участвовали в конкурсе Black-Box Optimization (BBO) и заняли третье место.
В состав команды входили я, Юрий Белоусов и Анастасия Никольская, которые также учатся на степень магистра и руководитель нашей лаборатории Алексей Шпильман Наше решение строит разбиение пространства параметров и оптимизирует некоторую его часть с помощью байесовской оптимизации.
О конкурсе, нашем решении и связанных с ним концепциях мы поговорим в статье.
Что такое ББО
Каждый разработчик, вероятно, сталкивался с концепцией «черного ящика» либо в контексте тестирования «черного ящика», либо в контексте программного обеспечения с закрытым исходным кодом, либо в чем-то еще.
Все эти моменты объединяет то, что в абстракции черного ящика наблюдаются только входные и выходные данные, а сама структура системы представляет собой «черный ящик»: 
Например, при тестировании методом «черного ящика» тесты обычно пишут те, кто не участвовал в написании тестируемого кода и не знает его структуру.
Эти тестировщики руководствуются общими принципами тестирования функциональности программы (граничные случаи для входа, категоризация всех тестовых случаев), не делая никаких предположений о том, как программа может быть реализована.
По аналогии, оптимизация черного ящика должна оптимизировать какую-то модель или вообще функцию.
, который имеет несколько входов 
, и можно наблюдать выходной результат. Что это за модель, для какой задачи мы наблюдаем результат и каковы абстрактные параметры? 
, Мы не знаем.
Например, для линейной регрессии 
К 
мы можем определить два параметра: наклон 
и сдвиг 
.
И как функция
мы рассчитаем среднеквадратическую ошибку в нашем наборе данных 
если предположить, что модель выглядит так 
.
Затем, зная, что модель имеет два реальных параметра, алгоритм оптимизации BBO должен выбрать оптимальный наклон и сдвиг в нашем наборе данных.
Конечно, линейная регрессия имеет оптимальное решение в закрытой форме, и нам не нужно оптимизировать таким образом.
Кроме того, даже если мы решим оптимизировать параметры линейной регрессии, а не находить их в закрытой форме, почему бы нам не использовать градиенты среднеквадратичной ошибки? И это резонный вопрос, ведь если у нас есть возможность находить градиенты для каждого параметра, мы можем оптимизировать классическими методами.
Поэтому BBO в основном используется в тех случаях, когда невозможно вычислить градиент функции потерь по параметрам.
Обычно эти параметры являются гиперпараметрами алгоритмов машинного обучения.
Например, для метода k-ближайших соседей гиперпараметры — это количество рассматриваемых соседей.
и степень расстояния 
, который используется для определения близости.
конкурс ВВО
Разобравшись, почему и что такое BBO, поговорим о конкуренции.Black-Box Optimization Challenge был организован разработчиками из таких компаний, как Твиттер , СигОпт , Валохай , Фейсбук и состоялось в рамках конференции НейрИПС 2020 .
Вся информация о конкурсе находится по адресу: https://bbochallenge.com .
Постановка задачи заключалась в следующем.
Проверочный код предлагает какую-то модель машинного обучения, выбирает набор данных и метрику, с помощью которой он будет оценивать наборы гиперпараметров.
Для согласованности, если большее значение метрики соответствует лучшему результату (например, метрика точности), проверочный код вернет отрицание ее значения, так что задачей всегда является минимизация.
На старте вашему алгоритму предоставляется информация о количестве параметров и ограничениях на каждый из них вида 
— действительное число в диапазоне [0,01, 100], 
целое число в диапазоне [1, 4], а 
принимает категориальные значения из набора ['linear', 'poly', 'rbf', 'sigmoid'].
Если вы обучаете данную модель на выбранном наборе данных с предложенными вами параметрами, ваш алгоритм должен предлагать несколько наборов этих параметров, для которых проверочный код будет возвращать значения метрик.
Более того, ваш алгоритм должен предлагать не один, а восемь наборов на каждой итерации, после чего он выдает результаты.
И количество таких итераций (загадал желание -> получил результат -> .
) ограничено 16. То есть всего ваш алгоритм может предложить 128 конфигураций.
Код проверки выставляет вам оценку в зависимости от того, насколько вам удалось уменьшить значение метрики, используя один из предложенных наборов.
Для лучшего понимания давайте посмотрим, как происходит это взаимодействие для решения задачи оптимизации точности классификации рукописных цифр ( описание набора данных ) Древо решений.
В дереве решений выделено шесть параметров, которые описаны в классе sklearn Дерево РешенияКлассификатор :
-
означает максимальную глубину дерева (целое число от 1 до 15); -
означает минимальное количество в процентах от всех выборок для дальнейшего рассмотрения разбиений данной вершины (действительное число от 0,01 до 0,99); -
означает минимальное количество в процентах от всех образцов, которое должно быть в любом листе (действительное число от 0,01 до 0,49); -
означает минимальный вес, который должен быть в любом из листьев (действительное число от 0,01 до 0,49); -
означает максимальный процент от общего количества признаков, которые мы будем учитывать для одного раздела (действительное число от 0,01 до 0,99); -
стоит за минимальным уменьшением примеси (числа, используемого для выбора расщеплений) в нашем дереве (действительное число от 0,0 до 0,5).
- в __init__ алгоритм получает информацию о 6 параметрах, их типах и диапазонах значений;
- в первом предложении алгоритм предлагает наборы (значения параметров в порядке представления выше) [5, 0.112, 0.011, 0.010, 0.204, 0.250], [13, 0.144, 0.052, 0.017, 0.011, 0.362], [4, 0.046, 0.077, 0.013, 0.079, 0.075], [8, 0.014, 0.204, 0.072, 0.036, 0.237], [9, 0.985, 0.065, 0.067, 0.015, 0.122], [13, 0.379, 0.142, 0.266, 0.097, 0.313], [15, 0.015, 0.088, 0.142, 0.143, 0.438], [14, 0.461, 0.020, 0.030, 0.613, 0.204];
- при первом вызове наблюдения получает результаты [-0.107, -0.107, -0.107, -0.107, -0.107, -0.107, -0.107, -0.107];
- в последнем предложении алгоритм предлагает наборы [9, 0.066, 0.013, 0.031, 0.915, 0.000], [8, 0.024, 0.012, 0.019, 0.909, 0.010], [9, 0.185, 0.020, 0.025, 0.925, 0.005], [15, 0.322, 0.014, 0.024, 0.962, 0.001], [10, 0.048, 0.018, 0.011, 0.939, 0.015], [12, 0.082, 0.017, 0.021, 0.935, 0.006], [7, 0.045, 0.015, 0.027, 0.954, 0.009], [12, 0.060, 0.014, 0.017, 0.921, 0.011];
- и получает результаты в режиме наблюдения [-0.740, -0.757, -0.614, -0.476, -0.738, -0.747, -0.750, -0.766];
- В результате код тестирования дает алгоритму оценку 109,78492, которая получается из минимума полученной метрики и ограничений, установленных авторами этого теста.
В первой итерации наши предложения достигают точности ~10%, что примерно эквивалентно случайной классификации 10 цифр.
Но на последней итерации точность гораздо выше и достигает 76%.
Вы как участник должны реализовать следующее интерфейс .
Он состоит из описанных выше методов инициализации (__init__), предложения наборов параметров (suggest) и обработки результатов (observe).
Как решить ББО
Одним из самых основных вариантов решения этой проблемы является использование случайного поиска.Этот метод был базовым, с которым сравнивались все предложенные решения.
Для задачи с двумя параметрами множества, рассматриваемые этим методом, могут выглядеть так: 
Методика довольно проста: мы знаем, сколько параметров и какие значения они принимают. В __init__ мы запоминаем параметры и их диапазоны.
На каждой итерации предложения мы выбираем 8 наборов из диапазонов и предлагаем их.
Обработка результатов нас не интересует, поэтому мы оставляем поле Observe пустым.
Представлена реализация этого метода.
Здесь .
Понятно, что метод далек от оптимального, поскольку мы не учитываем результаты.
Более того, алгоритм может предложить все наши 128 наборов в неоптимальном регионе, и мы никогда не будем пробовать наборы из других регионов.
Однако это уже способ выбора гиперпараметров, а не обучение модели только на первых заданных значениях.
Тем не менее, многие люди связывают поиск гиперпараметров с поиском по сетке.
И это правильное решение проблемы BBO. Поиск по сетке реализован во многих библиотеках.
И, наверное, этому следуют все, кто задумывается об оптимизации гиперпараметров для своей модели.
Вы выбираете для себя параметры, значения которых, по вашему мнению, больше всего влияют на вашу модель, предполагаете для них разумный диапазон и отмечаете в нем несколько значений.
Взяв все возможные комбинации значений этих параметров, вы получите сетку или сетку поиска.
Например, если у вас есть два гиперпараметра и вы определяете три значения для параметра 1 и три значения для параметра 2, вы получите следующую сетку: 
Обучая модель на каждой такой комбинации, вы оставляете лучший результат. В случае с нашим интерфейсом соревнований, в __init__ нам нужно сгенерировать такую сетку на основе описания параметров, а в предложить нам нужно предложить еще не исследованные комбинации.
Метод наблюдения снова остается пустым.
Как использовать результаты, возвращаемые алгоритму? Ведь понятно, что если мы сами последовательно подбираем гиперпараметры, то мы опираемся на результаты.
Давайте попробуем два набора 
И 
и на съемочной площадке
точность нашей классификации 
и на съемочной площадке
— 
.
Мы небезразличны к таким результатам.
Вероятно, мы больше не будем пытаться обучать нашу модель на параметрах, близких к
, но мы попробуем что-то близкое к
.
Самый популярный способ учета результатов — байесовская оптимизация.
Оптимизация происходит из предположения об исходном распределении значений (априорное), а по мере получения дополнительных результатов перестраивается (апостериорное).
При использовании байесовской оптимизации в BBO чаще всего прибегают к гауссовым процессам.
О них мы поговорим дальше.
Гауссовы процессы
Разберемся в работе гауссовских процессов на примере задачи максимизации функции одной переменной.
.
Чтобы оптимизировать эту функцию, мы построим суррогатную модель.
, что будет аппроксимировать истинную функцию
.
Наша суррогатная модель будет описываться гауссовским процессом.
Ценности
будет соответствовать значениям
в эти моменты
, результаты которого нам известны.
Значения в других точках
наша модель будет представлять распределения, потому что мы не знаем их наверняка.
При использовании гауссова процесса эти распределения будут нормальными.
.
Средние оценки 
и дисперсия 
получаются из определения гауссовского процесса, который задается значениями в определенных точках и ковариационной матрицей с выбранным ядром.
Более подробно о технике гауссова процесса и нахождении
И
Вы можете прочитать, например, в Википедия .
Нам будет важно использовать его для оптимизации.
Давайте теперь рассмотрим его применение к задаче максимизации функции одной переменной.
После получения отправных точек и построения первой суррогатной модели у нас будет что-то похожее на: 
Здесь пунктирная линия показывает истинную функцию
, и Solid — оценки среднего значения суррогатной модели
.
На синем фоне можно увидеть оценку отклонения значения от среднего.
Чтобы оптимизировать функцию, нам нужно решить, как мы будем выбирать следующую точку.
Эту стратегию обычно называют функцией приобретения.
Есть много способов выбрать эту функцию.
Наиболее популярными являются вероятность улучшения (PI) и ожидаемое улучшение (EI).
Оба они рассчитываются с использованием текущего оптимума и оценки среднего значения и дисперсии в определенной точке.
На рисунке в качестве следующей точки выбираем точку с максимальной функцией сбора (на рисунке показана зеленым цветом) и предлагаем ее.
Получив результат, мы видим следующее: 
Добавляется новое наблюдение, и максимум функции сбора данных перемещается в другую точку, которую мы затем запрашиваем: 
Оптимизация продолжается таким образом до тех пор, пока мы не достигнем предела итераций или пока наши улучшения не станут незначительными.
Гауссов процесс также обобщается на несколько переменных.
В случае с БВО нам необходимо провести только не максимизацию, а минимизацию, к которой легко перейти.
В результате имеем следующий алгоритм.
В __init__ мы запоминаем наше пространство и преобразуем все переменные в реальные значения.
Далее мы отбираем (используя, например, Выборка латинского гиперкуба ) наборы инициализации для первых нескольких итераций.
При первых звонках на предложение мы предлагаем для инициализации свои подготовленные наборы.
При вызове Observe мы всегда просто сохраняем пары.
.
И в дальнейшем предлагаем поступить следующим образом:
- Строим гауссов процесс на основе существующих наблюдений
. - Мы отбираем определенное количество кандидатов
(в нашем решении
, Где
— количество оптимизируемых параметров). - С помощью построенного гауссова процесса вычисляем оценки средних и дисперсий значений кандидатов.
- Мы вычисляем функцию приобретения в этих
кандидатов и выберите 8 с наибольшими значениями. - Мы возвращаем эти точки в качестве предложений проверяющему коду.
Наш подход
Поскольку у конкурентов все же было ограничение на количество итераций, и оно было равно 16, что довольно мало, мы решили упростить работу по байесовской оптимизации.В качестве подхода байесовской оптимизации мы использовали алгоритм TuRBO, который является небольшим ответвлением классических гауссовских процессов.
Основное отличие состоит в том, что оптимизация выполняется в доверительной области (отсюда и название «Байесовская оптимизация доверительной области»).
Кому интересно, можете прочитать оригинальная статья или код от организаторов конкурса.
Важной частью нашего решения было построение разбиения пространства гиперпараметров.
Идея состоит в том, что если мы каким-то образом ограничим все пространство допустимых значений, то байесовской модели будет легче получить хорошие результаты за такое небольшое количество итераций.
В примере с методом k-ближайших соседей, если мы с помощью какого-то метода обучения поймем, что хорошее решение находится в подпространстве, где 
И 
, то, имея меньше места (а иногда и больше измерений), наша байесовская модель будет более точной.
Вот как работает этот обучаемый метод. Каждые 4 итерации (то есть не более 4 раз, так как всего итераций у нас 16) мы перестраиваем разбиение всего пространства параметров.
Перестроим раздел на итерации 
(от 1 до 
), и у нас есть набор наблюдений 
который состоит из запрошенных нами баллов и результатов 
, .
, 
, Где 
.
Мы рекурсивно делим текущий набор наблюдений на левое и правое поддеревья.
Разделение выглядит следующим образом:
- Мы используем метод k-средних, чтобы разделить наши наблюдения на 2 кластера на основе значения метрики, которую мы пытаемся минимизировать.
Под 1-м кластером мы подразумеваем точки с меньшим средним значением метрики, а под 2-м кластером – с большим.
- Используя эти метки кластера, мы обучаем модель SVM, которая будет классифицировать точки в кластер 1 или 2. Мы знаем метки текущих точек и обучаем модель на них.
- Поскольку модель не всегда может идеально аппроксимировать метки, наша модель SVM может классифицировать существующие точки иначе, чем назначенные им кластеры.
Поэтому для каждой точки мы пересчитываем ее кластер относительно SVM, и все точки с прогнозом 1 отправляются в левое поддерево, а все точки с прогнозом 2 — вправо.
, или количество точек в какой-то вершине станет недостаточным для инициализации байесовской модели в будущем.
Выполняя этот метод, мы получаем дерево, листья которого содержат некоторые наборы точек, а вершины с дочерними элементами содержат модели SVM (критерии разделения).
Учитывая некоторую случайную точку, мы можем однозначно связать ее с областью нашего дерева, пройдя по этому дереву от корня к листу.
Что более важно в этом разделе, так это то, что если мы хотим оптимизировать нашу функцию, то все листья в левом поддереве будут «более перспективными» в этом отношении, чем листья в правом поддереве (поскольку мы отправили влево точки, которые соответствовал кластеру с меньшим средним значением метрики).
Затем, после построения такого разбиения, мы выбираем область, соответствующую крайнему левому листу, и проводим там байесовскую оптимизацию до следующей перестройки.
Например, рассмотрим такой раздел и работу TuRBO для модели SVM, которая имела выделено три параметра: коэффициент регуляризации 
, параметр ядра 
и эпсилон для критерия остановки 
.
Три параметра образуют трехмерное пространство.
После разделения пространства можно выделить две области: точки, лежащие на крайнем левом листе (зеленые) и все остальные (красные).
Вот как это выглядит:
Здесь темно-зеленым отмечена доверительная область TuRBO, и именно в ней строится гауссов процесс.
Черным цветом обозначены 8 точек, которые наш алгоритм вернет из предложения в рассматриваемой итерации.
Заключение
Все остальные технические подробности нашего решения можно найти в наша статья .И код был опубликован на GitHub .
В этой статье мы рассказали об оптимизации черного ящика, конкурсах по этой теме, общих подходах к решениям и особенностях нашего алгоритма, занявшего третье место в этом конкурсе.
Если вы хотите попробовать такие алгоритмы, вам очень поможет исходный код от авторов конкурса.
Вы можете запустить базовые решения, следуя инструкциям в этот репозиторий .
Теги: #Машинное обучение #Алгоритмы #Образовательный процесс в ИТ #машинное обучение #оптимизация #черный ящик #ВШ? #конкурсы по машинному обучению #Санкт-Петербург.
Петербургская башня
-
Доказательство Работы Эффективно
19 Oct, 24 -
Основные Характеристики Качественного Кода
19 Oct, 24
