Питерская вышка

Как объединить 10 BERT-ов для задач общего понимания текста?

22.07.2020 16:08:14 |

Автор: admin

Всем привет! В этом посте я расскажу о проекте, который выполнил совместно с командой Google Brain во время исследовательской стажировки в Цюрихе. Мы работали над моделью обработки естественного языка, которая решает задачи на общее понимание текста (задачи из набора GLUE: General Language Understanding Evaluation).

BERT-подобные модели мы комбинировали с помощью маршрутизирующих сетей и добились того, что при увеличении мощности скорость вывода почти не изменилась. Финальная модель объединяет 10 BERT_large моделей и имеет более 3,4 миллиарда параметров. Подробности под катом!

Меня зовут Никита Сазанович, я учусь на 2-м курсе магистратуры Программирование и анализ данных в Питерской Вышке. В январе я поехал на 17-недельную стажировку в Google Brain (правда, физически находился в Цюрихе только 11 из них: из-за карантина последние 6 недель пришлось работать удаленно). Мой проект был связан с обработкой естестественного языка с использованием маршрутизирующих сетей а это новое понятие в машинном обучении, с которым мы далее и разберемся.

Начнем издалека

Задачи обработки естественного языка (Natural Language Processing, NLP) включают в себя машинный перевод, распознавание текста, анализ тональности текстов и др. В этой статье мы поговорим про задачи из набора GLUE. Они были разработаны экспертами машинного обучения, чтобы оценивать, насколько модель способна к общему пониманию текста (откуда и название набора: General Language Understanding Evaluation).

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

Рассмотрим одну из них: Quora Question Pairs, или QQP. Как ясно из названия, нужно будет что-то сказать про пару вопросов из сайта Quora. Вопросы необходимо сравнить и сообщить, семантически эквивалентны ли они / является ли один дубликатом другого. Сразу приведу два примера:

1) Вопросы "What are natural numbers?" и "What is a least natural number?" не являются дубликатами.

2) А вопросы "How do you start a bakery?" и "How can one start a bakery business?" семантически эквивалентны.

То есть в этой задаче по тексту двух вопросов просят провести бинарную классификацию: разбить их на два класса. Задачу классификации в машинном обучении решают уже давно и научились это делать хорошо, но не в тех случаях, когда дело касается обработки естественного языка. Можно решить эту проблему, если привести текст к формату, на котором осуществлять классификацию более удобно. Например, преобразовать его в единый числовой вектор, который и послужит входом для классификации! Такой вектор называют представлением языка, а получением таких векторов занимается область обучения представлений языка, или language representation learning.

Итак, для того чтобы оценить, насколько модель способна к общему пониманию текста, ей предлагают решить несколько задач из набора GLUE, а для того чтобы она могла решать эти задачи, нужно подать ей данные в удобном формате в формате представления языка (то есть вектора). Далее мы поговорим об одном из современных подходов к получению представлений языка.

BERT: Теория

Обычно к обработке текста подходят с помощью токенизации, то есть разбиения предложения на токены из заданного словаря. Под токеном понимается определенная последовательность символов. Токены и словари строятся различными способами, мы будет говорить о подходе WordPiece. При таком подходе слово, которое не встречается в словаре целиком, будет разбито на части так, чтобы каждая часть была токеном словаря WordPiece. Пример такой токенизации:

1) Входное предложение: "Jet makers feud over seat width with big orders at stake".

2) Разбиение на токены (где символ _ приписывается к токенам, с которых слова начинаются): "_J et _makers _fe ud _over _seat _width _with _big _orders _at _stake". Здесь можно видеть, что слов "Jet" и "feud" не оказалось целиком в словаре, поэтому они были разбиты на части, присутствующие в словаре.

В словаре WordPiece содержится несколько десятков тысяч токенов. Большинство слов, которые встречаются наиболее часто, он содержит целиком.

Итак, мы разбили текст на токены! Для получения представления текста нам осталось как-то отобразить каждый из этих токенов в вектор, а затем скомбинировать вектора в один. Первый шаг большинство моделей осуществляют, храня словарь векторов представлений для каждого токена в отдельности, без контекста. Но многие исследования проводят для ответа на вопрос: как организовать обучение, чтобы в итоге представления для токенов учитывали контекст текста, в котором они находятся?

В 2017 году был представлен механизм внимания, который умеет учитывать контекст. Еще один плюс механизма в том, что зависимости в обученной модели легко интерпретировать для каждого входного текста. Рассмотрим пример на картинке снизу:

Если мы посмотрим на слово making в предложении It is in this spirit that a majority of American governments have passed new laws since 2009 making the registration or voting process more difficult, мы можем обратить внимание также на слова more difficult, laws, 2009: они помогают понять смысл. В предложении говорится о том, как с 2009 года правительства США принимали законы, которые делают процесс голосования сложнее. В таком контексте представление слова making в механизме внимания формируется в основном из представлений предыдущего слоя для слов making, more и difficult. Математически механизм внимания представляет собой блок модели, который отображает последовательность векторов токенов. При этом блок можно устроить таким образом, чтобы выходное представление каждого токена формировалось как взвешенная сумма всех представлений токенов с предыдущего слоя. В каком-то смысле у каждого слова есть ограниченное внимание, которое оно разделяет между всеми словами предыдущего слоя.

В той же статье авторы показали модель, которая состояла из нескольких последовательных блоков с механизмом внимания, и назвали ее Трансформер.

Позже был представлен способ предобучения представлений BERT, который использует модель Трансформера, а также описывает датасет и функцию обучения. Под BERT-ом также часто имеют в виду предобученные модели, которые опубликовали авторы метода, и которые можно очень легко и быстро дообучать для вашей задачи.

Вернемся к вопросу представления текста. Допустим, после каких-то преобразований мы получили последовательность векторов $inline$ , $inline$ , ..., $z_{n_i}$ для токенов текста $inline$ , $inline$ , ..., $x_{n_i}$ . Как теперь проводить классификацию или регрессию на всем тексте? В BERT модели предлагают элегантное решение: к каждой последовательности токенов добавить токен $inline$ и получить по нему представление $inline$ описанным выше способом. Благодаря специальному устройству функции обучения оно будет представлять информацию, которая содержится во всем тексте. Для более подробного устройства можно обратиться к самой статье о BERT.

Ниже я расскажу о том, как эти BERT-подобные модели можно комбинировать с помощью нового для машинного обучения понятия маршрутизирующих сетей при решении набора задач GLUE. Под BERT-подобными моделями мы будет подразумевать BERTы, которые имеют разные гиперпараметры и/или обучены на отличном от оригинального датасете (примеры таких моделей).

Маршрутизирующие сети

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

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

Формулировать и обучать процесс маршрутизации можно по-разному. К примеру, в статье по ссылке для каждой возможности маршрутизации задачи через модуль модели использовалось распределение Бернулли, которое обучалось с помощью Gumbel Softmax. Ниже вы можете видеть пример такой модели с двумя задачами. Цветами отмечено, какое подмножество модулей используется для каждой из них: красным обозначены модули, которые вычисляются на маршруте для первой задачи, синим для второй, а фиолетовым для обеих. Если в одном слое таких модулей для одной задачи несколько, нужна агрегация результатов, например, усреднение. Наличие общих модулей и позволяет задачам совместно обучать модули, которые выгодно разделять.

Как видно на картинке, модули этой сети состоят из сверточных слоев (Conv 3x3, Conv 5x5, Conv 7x7). Значит, задачи относились к области компьютерного зрения. А что если в качестве таких модулей мы будем использовать BERT-подобные модели и попытаемся искать маршруты для задач из набора GLUE? Это и стало идеей для моего проекта.

Маршрутизация и процесс тренировки

На вход модель получает токенизированный текст (x) и числовой идентификатор задачи (t), который превращается в вектор представления задачи. Используя этот вектор, маршрутизатор выбирает набор модулей/экспертов для задачи, которым подается на вход токенизированный текст x. После обработки экспертами происходит агрегация результатов и получается представление текста. Затем представление направляется в небольшую сеть (отдельную для каждой задачи t), которая преобразует представление к ответу задачи (регрессии или классификации). Стоит также заметить, что для задач GLUE эксперты инициализируются предобученными моделями.

Представления задач моделируются как вектора размерности M (в экспериментах M было равно 10):

$v_t\ для\ t = [1, .., T],\ где\ T - число\ задач \\ v_t\in R^M,\ где\ M - размерность\ представлений$

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

$G(v) = Softmax(KeepTopK(H(v), k)) \\ KeepTopK(h, k)_i = \begin{cases} h_i & \text{если $h_i$ в k наибольших элементах в h} \\ 0 & \text{иначе} \end{cases} \\ G(v) \in R^N, где\ N - число\ экспертов$

Сами представления языка формируются как взвешенная сумма результатов экспертов, причем эксперту не нужно вычислять результат, если коэффициент равен нулю:

$x \in X_t\ для\ t = [1, .., T] \\ f(x, t) = \sum\limits_{i=1}^{M} G(v_t)_i E_i(x),\ где\ E_i - функция\ i{\text -}ого\ эксперта$

Изначально мы предпочитаем опрашивать малое число экспертов, чтобы объем вычислений был сравним с тем, который требуется при использовании одного эксперта. Как видно из устройства модели, если наш маршрутизатор при любом количестве экспертов всегда выбирает два пути, то объем вычислений для одного запроса будет лишь в два раза превышать объем для одного эксперта, а скорость вывода после обучения не будет превышать времени вывода двух экспертов на одном устройстве. Это и отвечает на вопрос об устройстве модели обучения, поставленный в самом начале статьи.

Далее под спойлером для любителей описаны технические подробности настройки этой модели. Для полноты картины расскажу про нее в нескольких словах. Лучший результат достигается, если использовать 10 BERT _large экспертов, а не трех или одного (из-за затрат времени и ресурсов мы провели эксперименты только для 1, 3 и 10 экспертов). Оптимальное количество путей два. Оптимизировать выгодно стохастическим градиентным спуском с импульсом. При такой настройке модель имеет 3,4 миллиарда параметров и обучать ее пришлось на 24 тензорных процессорах Google.

Детали настройки модели

Процесс тренировки проходит параллельно на батчах из всех задач GLUE и требует какой-то агрегации между задачами. Один из вариантов линейная комбинация потерь $inline$ каждой из задач:

$L_{total} = \sum\limits_{t=1}^{T} C(t) L_t$

В таблице далее представлены варианты агрегации и соответствующие им GLUE оценки, если в качестве экспертов брать одну модель BERT_base.

В первых трех строках можно видеть разные способы задания коэффициента, который может включать количество задач или размер данных для задачи. Ниже представлены два способа, которые имеют другую форму (статья про последний способ). Лучшим из пяти способов оказался третий вид, но если рассмотреть общую форму с нормированием до единицы и учетом размера датасета:

$L_{total} = \sum\limits_{t=1}^{T} \frac{1}{\mathcal{N}} |D_t|^p L_t$

то можно было достичь GLUE оценки в 80.06 при значении p=0.3. Я использую такую агрегацию функций потерь каждой из задач в дальнейших экспериментах по настройке модели.

Важным элементов при масштабировании модели является метод оптимизации, так как он увеличивает размер необходимой памяти, тем самым уменьшая мощность модели при фиксированном бюджете. Я проверил 6 оптимизаторов: Adam, Adam с weight decay (угасание весов к нулю), LAMB, LAMB с weight decay, стохастический градиентный спуск (SGD) и стохастический градиентный спуск с импульсом (SGDM). SGD практически не расходует дополнительной памяти, SGDM запоминает импульсы для каждой переменной, поэтому расходует x2 памяти, а остальные рассмотренные оптимизаторы расходуют x3 памяти. Результаты оптимизации маршрутизируемого BERT-а с одним BERT_large экспертом можно видеть в таблице. SGDM достигает лучшего результата в исследуемом пространстве, при этом используя лишь в два раза больше памяти. Я использую его в финальной модели.

Рассматривая зависимость качества от числа BERT_large экспертов и путей, я заметил, что качество улучшается при увеличении числа экспертов, а при увеличении количества путей не всегда. Лучший результат дало использование 10 экспертов и 2 путей.

В такой модели 10 x 340 миллионов = 3,4 миллиарда параметров, а ее обучение происходило на 24 TPUv2 (тензорных процессорах Google) с параллелизмом по данных равным 4 и параллелизмом модели равным 6. Параллелизм модели равен 6, так как 5 процессоров держат по 2 BERT_large модели, а еще один отвечает за все сети задач после агрегации.

Анализ результатов

Для сравнения результатов в наборе GLUE был предложен способ комплексной оценки, который совмещает результаты на каждой из задач набора. Эта оценка лежит в диапазоне от 0 (все неверно) до 100 (идеальные ответы). Я сравнил маршрутизируемый BERT с опубликованными результатами мультизадачного обучения BAM! (оно основано на дистилляции) и настройкой одного BERTа под каждую задачу. Маршрутизируемый BERT достиг лучшей оценки общего понимания языка.

Интересны также различия между результатами на задачах. Например, выгоду при тренировке с маршрутизируемыми сетями получает задача RTE, которая имеет наименьший тренировочный набор (2,5 тысячи примеров). Сравните ее оценки в 1-й и 3-й строках. Эта выгода на задаче достигается засчет использования дополнительных знаний из других задач, тренировочный набор которых больше по размеру.

Еще один результат этой модели возможность исследовать отношения между задачами. Ниже представлен результат сокращения размерности векторов для представлений задач. Вектора, которые изначально находятся в 10-мерном пространстве (M=10), сокращены до векторов размера 2, т. е. точек. Это сделано при помощи метода t-SNE, который очень популярен для таких визуализаций и про который можно почитать в другом блоге на Хабре. Здесь каждая из задач располагается на плоскости, а расстояние между ними позволяет судить о том, насколько они близки с точки зрения маршрутизатора. Как и ожидалось, mnli-m и mnli-mm задачи с одним и тем же тренировочным набором располагаются близко. Так же близко расположены sst-2 и qqp, cola и rte пары, сходство которых отмечали и другие исследователи.

Итоги

В результате мы разобрались, как можно использовать маршрутизирующие сети для обучения представлений языка. С их помощью мы улучшили результат работы исходной модели с точки зрения оценки GLUE на 1,75 пункта и в качестве бонуса смогли визуализировать отношения между задачами набора. Важное свойство такого подхода сохранение скорости вывода в конечной модели. Было бы интересно продолжить работу над проектом, использовав разнородных экспертов с одинаковым интерфейсом (таких как ALBERT и RoBERTa), а также добавить к набору задачи предобучения представлений (таких как MLM BERT-а) для тренировки сети с нуля без использования предобученных моделей.

Код этой модели остался в Google, но могу сказать, что написан он был на любимом в компании TensorFlow.

Подробнее..

Категории: Алгоритмы , Искусственный интеллект , Машинное обучение , Учебный процесс в it , Обработка естественного языка , Блог компании питерская вышка , Hse , Питерская вышка , Обучение представлений , Bert , Google brain

Black-Box Optimization Challenge, или как подбирать гиперпараметры для моделей

27.01.2021 12:10:40 |

Автор: admin

Всем привет! В этом посте я расскажу, как наша команда участвовала и заняла третье место в Black-Box Optimization Challenge соревновании по автоматическому подбору параметров для моделей машинного обучения. Особенность соревнования в том, что алгоритм не знает, какая модель машинного обучения используется, какую задачу она решает, и за что отвечает каждый из оптимизируемых параметров.

Звучит как соревнование, в котором лучше случайного поиска ничего не придумаешь, но существует целый класс алгоритмов для таких задач, о которых мы и поговорим под катом.

Меня зовут Никита Сазанович, я учусь на 2-м курсе магистратуры Программирование и анализ данных в Питерской Вышке. На протяжении трех месяцев мы с командой из JetBrains Research участвовали в соревновании по Black-Box Optimization (BBO) и заняли в нем третье место. Команда состояла из меня, Юрия Белоусова и Анастасии Никольской, которые тоже учатся в магистратуре, и руководителя нашей лаборатории Алексея Шпильмана. Наше решение строит разбиение пространства параметров и оптимизирует какой-то его участок, используя байесовскую оптимизацию. Про соревнование, наше решение и смежные понятия мы и поговорим в статье.

Что такое BBO

С понятием black box, вероятно, встречался каждый разработчик или в контексте black box тестирования, или программного обеспечения с закрытым исходным кодом, или чего-то еще. Все эти моменты объединяет то, что в абстракции black box наблюдаются только входные и выходные данные, а само устройство системы представляет собой черный ящик:

Например, при black box тестировании, тесты, как правило, пишутся теми, кто не принимал участия в написании тестируемого кода и не знает его устройства. Эти тестировщики руководствуются общими принципами тестирования функциональности программы (граничные случаи для входа, разбиение всех тестовых случаев на категории) без каких-либо предположений о том, как эта программа может быть реализована.

По аналогии, black box оптимизация должна оптимизировать какую-то модель, или в общем случае функцию $inline$ , у которой есть несколько входов $inline$ , и есть возможность наблюдать выходной результат. Что за модель, для какой задачи мы наблюдаем результат, и что представляют из себя абстрактные параметры $inline$ , мы не знаем. К примеру, для линейной регрессии $inline$ по $inline$ мы можем определить два параметра: наклон $inline$ и сдвиг $inline$ . А в качестве функции $inline$ будем считать среднеквадратическую ошибку на нашем датасете $\{x_i, y_i\}$ в предположении того, что модель выглядит как $inline$ . Тогда, зная, что у модели есть два вещественных параметра, алгоритм BBO оптимизации должен подобрать оптимальные наклон и сдвиг на нашем датасете.

Конечно, линейная регрессия имеет оптимальное решение в закрытой форме, и оптимизацию таким способом нам проводить не обязательно. Кроме того, даже если мы решили оптимизировать параметры линейной регрессии, а не найти их в закрытой форме, почему бы нам не использовать градиенты среднеквадратической ошибки? И это разумный вопрос, потому что если у нас есть возможность найти градиенты для каждого параметра, мы можем проводить оптимизацию классическими методами. Поэтому BBO в основном применяется в случаях, когда нет возможности посчитать градиент функции потерь по параметрам. Обычно такими параметрами являются гиперпараметры алгоритмов машинного обучения. Например, для метода k-ближайших соседей гиперпараметрами являются количество рассматриваемых соседей $n_{neighbors}$ и степень расстояния $inline$ , которое используется для определения близости.

Соревнование по BBO

Разобравшись в том, зачем и что собой представляет BBO, давайте поговорим про соревнование. Black-Box Optimization Challenge был организован разработчиками таких компаний, как Twitter, SigOpt, Valohai, Facebook, и проходил в рамках конференции NeurIPS 2020. Вся информация про соревнование расположена по адресу: https://bbochallenge.com.

Постановка задачи была следующая. Проверяющий код загадывает какую-то модель машинного обучения, выбирает датасет и метрику, с помощью которой он будет оценивать наборы гиперпараметров. Для однообразности, в случае если большее значение метрики соответствует лучшему результату (к примеру, метрика точности), проверяющий код будет возвращать отрицание ее значения, чтобы задача всегда заключалась в минимизации. Вашему алгоритму на старте передается информация о количестве параметров и ограничения на каждый из них вида $inline$ это вещественное число в диапазоне [0.01, 100], $inline$ это целое число в диапазоне [1, 4], а $inline$ принимает категориальные значения из набора ['linear', 'poly', 'rbf', 'sigmoid']. Eсли провести обучение загаданной модели на выбранном датасете с предлагаемыми вами параметрами, ваш алгоритм должен предлагать какие-то наборы этих параметров, на которые проверяющий код будет возвращать значения метрики,. Более того, ваш алгоритм должен предлагать не один, а восемь наборов в каждой итерации, после чего он получает результаты. И количество таких итераций (загадал -> получил результаты -> ...) ограничено 16. То есть всего ваш алгоритм может предложить 128 конфигураций. Проверяющий код выставляет вам оценку в зависимости от того, насколько вам удалось уменьшить значение метрики одним из предложенных наборов.

Для лучшего понимания давайте посмотрим, как такое взаимодействие происходит для решения на задаче оптимизации точности классификации рукописных цифр (описание датасета) деревом принятия решений. У дерева принятия решений выделено шесть параметров, которые описаны в классе sklearn DecisionTreeClassifier:

$max\_depth$ означает максимальную глубину дерева (целое число от 1 до 15);
$min\_samples\_split$ означает минимальное число в процентах от всех сэмплов для того, чтобы дальше рассматривать разбиения этой вершины (вещественное число от 0.01 до 0.99);
$min\_samples\_leaf$ означает минимальное число в процентах от всех сэмплов, которое должно быть в любом листе (вещественное число от 0.01 до 0.49);
$min\_weight\_fraction\_leaf$ означает минимальный вес, который должен находиться в любом из листьев (вещественное число от 0.01 до 0.49);
$max\_features$ означает максимальный процент от всего числа признаков, которые мы будем рассматривать для одного разбиения (вещественное число от 0.01 до 0.99);
$min\_impurity\_decrease$ стоит за минимальным уменьшением impurity (число, использующееся для выбора разбиений) в нашем дереве (вещественное число от 0.0 до 0.5).

Рассмотрим некоторые итерации взаимодействия (все вещественные числа представлены с точностью до 3 цифр после запятой):

в __init__ алгоритм получает информацию о 6 параметрах, их типах и диапазонах значений;
в первом suggest алгоритм предлагает наборы (значения для параметров в порядке представления выше)
[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];
в первом вызове observe получает результаты
[-0.107, -0.107, -0.107, -0.107, -0.107, -0.107, -0.107, -0.107];
в последнем suggest алгоритм предлагает наборы
[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];
и получает в observe результаты
[-0.740, -0.757, -0.614, -0.476, -0.738, -0.747, -0.750, -0.766];
в итоге проверяющий код выставляет алгоритму оценку 109.78492, которая получается из минимума полученной метрики и границам, установленными авторами этого теста.

Заметим, что результаты, которые получает алгоритм, это отрицание точности классификации, так как в любом тесте ставится задача минимизации. На первой итерации наши предложения получают точность ~10%, что приблизительно соответствует случайной классификации 10 цифр. Но на последней итерации точности гораздо выше и достигают 76%.

Вы как участник должны реализовать следующий интерфейс. Он состоит из описанных выше методов инициализации (__init__), предложения наборов параметров (suggest) и обработки результатов (observe).

Как решать BBO

Одно из самых базовых вариантов решения такой задачи это использование случайного поиска. Это метод и являлся baseline-ом, с которым сравнивались все предложенные решения. Для задачи с двумя параметрами рассмотренные этим методом наборы могут выглядеть так:

Техника довольно простая: мы знаем, сколько каких параметров, и какие значения они принимают. В __init__ мы запоминаем параметры и их диапазоны. На каждой итерации suggest мы сэмплируем 8 наборов из диапазонов и предлагаем их. Обработка результатов нас не интересует, поэтому observe оставляем пустым. Реализация этого метода представлена здесь.

Понятно, что метод далеко не оптимален, т.к. мы не учитываем результаты. Более того, алгоритм может предложить все наши 128 наборов в неоптимальном регионе, и мы так и не попробуем наборы из других регионов. Тем не менее, это уже способ, которым можно подбирать гиперпараметры, а не обучать модель только на первых установленных значениях.

Все же у многих поиск гиперпараметров ассоциируется с grid search-ем. И он является валидным решением задачи BBO. Grid search реализован во многих библиотеках. И, наверное, каждый, кто задумывается об оптимизации гиперпараметров для своей модели, следует ему. Вы для себя выбираете параметры, значения которых, как вам кажется, больше всего влияют на вашу модель, предполагаете их разумный диапазон, и отмечаете в нем несколько значений. Взяв каждую возможную комбинацию значений этих параметров, вы получаете grid или сетку поиска. Например, если у вас есть два гиперпараметра, и вы определили три значения для параметра 1 и три значения для параметра 2, то получится следующая сетка:

Обучив модель на каждой такой комбинации, вы оставляете лучший результат. В случае нашего интерфейса соревнования, в __init__ нужно сгенерировать такую сетку по описанию параметров, и в suggest предлагать еще не исследованные комбинации. Метод observe опять остается пустым.

Как же использовать результаты, возвращаемые алгоритму? Ведь понятно, что если мы сами последовательно подбираем гиперпараметры, то мы опираемся на результаты. Пусть мы попробовали два набора $inline$ и $inline$ , и на наборе $inline$ наша точность классификации составляет $92\%$ , а на наборе $inline$ $54\%$ . Мы не равнодушны к таким результатам. Вероятно, мы не будем больше пробовать обучить нашу модель на параметрах близких к $inline$ , а будем пробовать что-то близкое к $inline$ .

Наиболее популярным способом учета результатов является байесовская оптимизация. Оптимизация происходит из предположения о начальном распределении значений (prior), и с получением дополнительных результатов оно перестраивается (posterior). При использовании байесовской оптимизации в BBO чаще всего прибегают к гауссовским процессам. О них мы и поговорим далее.

Гауссовские процессы

С работой гауссовских процессов разберемся на примере задачи максимизации функции одной переменной $inline$ . Для оптимизации этой функции мы построим суррогатную модель $inline$ , которая будет приближать истинную функцию $inline$ . Описываться наша суррогатная модель будет гауссовским процессом. Значения $inline$ будут совпадать с значениями $inline$ в тех точках $inline$ , результаты которых мы знаем. Значения в остальных точках $inline$ наша модель будет представлять распределениями, ведь мы не знаем их наверняка. Используя гауссовский процесс, эти распределения будут нормальными $\mathcal{N}(\mu,\sigma^2)$ . Оценки на среднее $\mu$ и дисперсию $\sigma^2$ получаются из определения гауссовского процесса, который задается значениями в определенных точках и матрицей ковариаций с выбранным ядром. Более подробно про технику гауссовского процесса и нахождения $\mu$ и $\sigma^2$ можно почитать, например, в Википедии. Нам же будет важно его применение для оптимизации.

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

Здесь пунктирной линией показана истинная функция $inline$ , а сплошной оценки на среднее значение суррогатной модели $inline$ . Синим фоном можно видеть оценку на отклонение значения от среднего. Для оптимизации функции нам нужно определиться, каким способом мы будем выбирать следующую точку. Эта стратегия обычно называется acquisition function или функцией приобретения. Существует множество способов выбора этой функцией. Наиболее популярными являются вероятность улучшения (Probability of Improvement, PI) и ожидаемое улучшение (Expected Improvement, EI). Они обе вычисляются по текущему оптимуму и оценке на среднее и дисперсию в точке. На рисунке в качестве следующей точки мы выбираем ту, у которой функция приобретения (на рисунке изображена зеленым цветом) максимальна, и предлагаем ее. Получив результат, мы видим следующее:

Добавляется новое наблюдение, и максимум функции приобретения переходит в другую точку, которую мы и запрашиваем далее:

Таким образом происходит оптимизация, пока мы не достигнем предела итераций или наши улучшения станут незначительными. Гауссовский процесс также обобщается на несколько переменных.

В случае BBO нам нужно лишь проводить не максимизацию, а минимизацию, к которой легко перейти. В итоге имеем следующий алгоритм. В __init__ мы запоминаем наше пространство и преобразуем все переменные к вещественным значениям. Далее мы сэмплириуем (используя, например, Latin hypercube sampling) наборы для инициализации в течение нескольких первых итераций. В первых вызовах suggest мы предлагаем наши заготовленные наборы для инициализации. При вызове observe мы всегда лишь сохраняем пары $\{x_i, y_i\}$ . А в дальнейших suggest мы поступаем следующим образом:

Строим гауссовский процесс по уже имеющимся наблюдениям $\{x_i, y_i\}$ .
Сэмплируем какое-то количество кандидатов $n_{cand}$ (в нашем решении $n_{cand}=min(100*D, 5000)$ , где $inline$ количество оптимизируемых параметров).
Используя построенный гауссовский процесс, мы вычисляем оценки на средние и дисперсии значений в кандидатах.
Вычисляем функцию приобретения в этих $n_{cand}$ кандидатах и выбираем 8 с наибольшими значениями.
Возвращаем эти точки как наши предложения проверяющему коду.

Этот подход уже является сильным baseline-ом для задач, в которых нет явных ограничений на количество параметров и/или количество общих итераций.

Наш подход

Так как в соревновании все же было ограничение на количество итераций, и оно было равно 16, что довольно немного, мы решили упростить работу байесовской оптимизации.

В качестве подхода байесовской оптимизации мы использовали алгоритм TuRBO, которой является небольшим ответвлением от классических гауссовских процессов. Основное отличие состоит в том, что оптимизация проводится в доверительном регионе (откуда и название Trust Region Bayesian Optimization). Для интересующихся можно почитать оригинальную статью или код от организаторов соревнования.

Важной же частью нашего решения стало построение разбиения пространства гиперпараметров. Идея состоит в том, что если мы как-то ограничим все пространство допустимых значений, то байесовской модели будет проще получить хорошие результаты за столь малое количество итераций. В примере с методом k-ближайших соседей если мы каким-нибудь обучаемым методом поймем, что хорошее решение лежит в подпространстве, где $n_{neighbors}>50$ и $p\le2$ , то имея меньшее пространство (а иногда и количество измерений), наша байесовская модель будет точнее.

Вот как этот обучаемый метод работает. Каждые 4 итерации (то есть не более 4 раз, т.к. всего имеем 16 итераций) мы перестраиваем разбиение всего пространства параметров. Пусть мы перестраиваем разбиение на итерации $inline$ (от 1 to $inline$ ), и у нас есть набор наблюдений $inline$ который состоит из запрошенных нами точек и результатов $inline$ , ..., $(x_{n_t}, y_{n_t})$ , где $inline$ . Мы рекурсивно делим текущий набор наблюдений на левое и правое поддеревья. Деление выглядит следующим образом:

Мы запускаем метод k-средних, чтобы разделить наши наблюдения на 2 кластера по значению метрики, которую мы пытается минимизировать. Под 1-ым кластером будем подразумевать точки с меньшим средним значением метрики, а под 2-ым с большим.
Использую эти метки кластеров, мы обучаем SVM модель, которая будет классифицировать точки в кластер 1 или 2. Мы знаем метки для текущих точек, и на них и обучаем модель.
Так как у модели не всегда получается идеально приблизить метки, то наша SVM модель может классифицировать имеющиеся точки не так, как им были назначены кластера. Поэтому для каждой точки мы вычисляем ее кластер заново относительно SVM, и все точки с предсказаниями 1 отправляются в левое поддерево, а с 2 в правое.

Мы продолжаем этот процесс рекурсивно пока не достигнем максимальной глубины $max_{depth}=5$ , или количество точек в какой-то вершине станет недостаточным для инициализации байесовской модели в дальнейшем.

Исполнив этот метод, мы получаем дерево, в листьях которого расположены какие-то наборы точек, а в вершинах с детьми находятся SVM модели (критерии разбиения). Имея какую-то случайную точку, мы можем однозначно сопоставить ее с регионом нашего дерева, пройдя по этому дереву от корня до листа.

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

К примеру, рассмотрим такое разбиение и работу TuRBO для модели SVM, у которой было выделено три параметра: коэффициент регуляризации $inline$ , параметр ядра $inline$ и эпсилон для критерия остановки $inline$ . Три параметра образуют трехмерное пространство. После разбиения пространства можно выделить два региона: точки, которые лежат в самом левом листе (зеленый цвет), и все остальные (красный цвет). Вот как это выглядит:

Темно-зеленым здесь отмечен доверительный регион TuRBO, и именно в нем и строится гауссовский процесс. Черным цветом обозначены 8 точек, которые будут возвращены нашим алгоритмом из suggest в рассматриваемой итерации.

Заключение

Все оставшиеся технические детали нашего решения можно найти в нашей статье. А код был опубликован на GitHub.

В этой статье мы поговорили о black box оптимизации, соревновании на эту тему, общие подходы к решениям и особенности нашего алгоритма, который занял третье место в этом соревновании.

Если вы хотите попробовать такие алгоритмы, то начальный код от авторов соревнования очень полезен. Запустить базовые решения можно, следуя инструкциям в этом репозитории.