Всем привет! Во втором семестре все первокурсники программы Прикладная математика и информатика в Питерской Вышке делают командные проекты по С++. Мы занимались разработкой умной футболки.

О том, что это такое, и что мы успели сделать за время работы над проектом, читайте в этой статье.


Мы Денис Тарасов и Денис Филиппов студенты уже второго курса бакалавриата Прикладная математика и информатика в Питерской Вышке. Мы работали над проектом вместе с Яном Фрейдкиным и Иваном Чунаревым. С ними мы учились в одной школе: Санкт-Петербургском ГФМЛ 30.

В 11 классе у Яна и Ивана был проект по робототехнике Умная футболка (она на первой фотографии). Идея такова: берётся футболка, на неё крепятся различные датчики (акселерометр, гироскоп и другие). По считываемым данным можно определить некоторые показатели, например, корректность осанки. Ребята успели принять участие в нескольких конференциях и собирались после окончания школы продолжить работу над проектом, но поняли, что им нужны программисты. Собственно вот мы и здесь.

Футболка Яна и Ивана могла считывать ЭКГ и отслеживать корректность осанки. Для этого использовалась Arduino UNO платформа разработки с устаревшими микроконтроллерами AVR. Достаточно скоро им стало не хватать памяти для кода. На новой стадии работы над проектом мы поняли, что нужно предъявлять более строгие требования к микроконтроллеру:

• Чтобы можно было подключить больше датчиков, необходим был процессор с большей частотой, большее количество периферии и более скоростная периферия;
• Больший объем flash памяти, оперативной памяти;
• Меньшая стоимость;
• Стабильность работы микроконтроллера.

Мы решили, что нужно менять микроконтроллер. У нас было два варианта: использовать более мощный микроконтроллер серии AVR (в нашем случае Arduino) или перейти на другую серию микроконтроллеров, а именно ARM (в нашем случае STM32). Несмотря на большое сообщество Arduino и простоту в использовании этого микроконтроллера, мы решили перейти на STM32, потому что его производительность лучше, а объем памяти больше. Сейчас мы используем микроконтроллер серии STM32f4*.


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

Первые шаги. Зажгли светодиод

У нас не было опыта программирования микроконтроллеров, и мы прочитали, что инициализация и объявление датчикови пинов на STM это долго и сложно. Поэтому мы использовали высокий уровень абстракции с помощью библиотеки HAL и STM32CubeMX. STM32CubeMX инструмент, который с помощью графического интерфейса настраивает порты микроконтроллера и генерирует соответствующий код, использующий библиотеку HAL. Сначала мы решили сделать самую базовую в программировании микроконтроллеров вещь (на уровне Hello world) зажечь светодиод.


Интерфейс STM32CubeMX

После долгого поиска IDE, которая была бы кроссплатформенной, бесплатной и удобной для разработки, мы остановились на STM32CubeIDE.



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

Прошивка микроконтроллера

После того, как мы научились зажигать светодиод и поняли, как вообще программировать микроконтроллер, мы занялись написанием основы прошивки микроконтроллера, на базе которой в дальнейшем можно было бы добавлять различный функционал. Для начала нужно было научиться инициализировать датчики и получать информацию с них. Из датчиков мы успели добраться лишь до IMU-сенсоров: гироскопа и акселерометра. У нас были сенсоры MPU-6050.


Общение с микроконтроллером осуществляется по шине I2C. Благодаря библиотеке HAL передача данных производится легко: необходимо вызвать функцию для чтения/записи. Пример чтения данных с акселерометра из кода:

HAL_I2C_Mem_Read(i2c_handle, addres, ACCEL_XOUT_H_REG, 1, buffer, 6, 1000)

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

HAL_I2C_Mem_Write(i2c_handle, addres, GYRO_CONFIG_REG, 1, &Data, 1, 1000)

Также у нас был Bluetooth модуль (HC-05 и HC-06), но он не требовал каких-либо особых манипуляций для работы. После его подключения можно просто слать данные через универсальный асинхронный приемопередатчик (UART) специальное устройство внутри микроконтроллера, которое позволяет общаться с другими устройствами. Для него в HAL предусмотрены функции, схожие с функциями для I2C. Мы лишь написали небольшую обертку над ними, чтобы было проще выводить сообщения во время отладки.


HC-06

Далее мы создали класс Controller, который осуществляет инициализацию датчиков, запускает основной цикл программы и обрабатывает запросы, приходящие из приложения. Запросы хранятся в очереди, поступают через Bluetooth и принимаются с помощью механизма прерываний. Прерывание сигнал от программного или аппаратного обеспечения, сообщающий процессору о наступлении какого-либо события, которое требует немедленного внимания. Механизм прерывания нужен в том числе для быстрого реагирования системы на важные события.

Также Controller хранит список функций футболки с помощью базового класса BaseFunc. На данный момент у нас есть только обработка осанки, но в будущем при добавлении нового функционала достаточно будет просто создать класс-наследник и добавить его в список функций. Контроллер выглядит примерно так:

class Controller {std::vector<std::unique_ptr<IMU>> IMUSensors; // список сенсоровstd::queue<Request> reqQueue; // очередь запросовstd::vector<std::pair<std::unique_ptr<BaseFunc>, bool>> mithrilFuncs; // список пар //<функция футболки, включена ли она>Controller();void Run(); // основной цикл программы};

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

Что там по прототипу

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

Из-за пандемии мы больше не могли встречаться и работать над футболкой вчетвером, и у нас фактически не было возможности ездить к Яну и Ивану, чтобы в случае проблем с прототипами оперативно их решать. Ян и Иван разработали прототип футболки, на котором можно было расставлять датчики, протягивая провода так, чтобы они не влияли на показания своим весом и натяжением. Ребята послали нам с Денисом по экземпляру футболки, а также изоленты, провода и др., чтобы мы сами могли устранять возможные поломки.

Приложение для Android

Мы поставили перед собой цель создать Android-приложение с возможностью общаться через Bluetooth с микроконтроллером. Как и в случае с программированием микроконтроллеров, опытом написания приложений под Android мы не обладали, однако найти информацию про Android оказалось намного легче, чем про STM32. Основы мы изучали при помощи курса на Stepik.org (курс действительно неплохой), где сначала разбирают основы языка Kotlin, а затем рассказывают о программировании под Android.

Первая версия приложения позволяла подключаться к микроконтроллеру через Bluetooth и передавать ему сообщения. Последняя версия не сильно отличается от первой (написание приложение для нас не было в приоритете): в ней появились виджеты для запуска калибровки и включения/выключения функции слежения за корректностью осанки.

На то, чтобы написать первую рабочую версию приложения, ушло около 6 часов мы потратили больше времени на изучение теории. Код такого простенького приложения занял примерно 400 строк, что приятно удивило. При этом наверняка его можно написать компактнее.


Меню навигации


Вкладка для подключения через Bluetooth


Вкладка для обмена данными

Обработка осанки

Мы пришли к двум разным способам обработки осанки: с помощью методов анализа данных и без них.

Обработка осанки с помощью методов анализа данных

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

Сначала мы сняли с себя данные: углы закручивания и показания акселерометра с каждого из датчиков. Получили примерно 2000 замеров: около 1000 положительных и 1000 отрицательных. Конфигурация датчиков была следующая (два датчика расположены на лопатках и два на позвоночнике):



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



Проекции данных в двумерное пространство.

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


Далее необходимо было выбрать модели для предсказания. Мы решили попробовать линейную регрессию, а точнее ее модификацию Ridge, метод опорных векторов (SVM) с линейным ядром и дерево принятия решений. Выбор обусловлен простотой переноса моделей на микроконтроллер: первые две описываются некоторым количеством коэффициентов, а последняя представляет из себя набор условий if-else. Модели были взяты из библиотеки scikit-learn. Пример переноса линейной регрессии:

bool isPostureCorrect =(a11 * deviceAngles1[0] + a12 * deviceAngles1[1] + a13 * deviceAngles1[2] +           g11 * deviceGravity1[0] + g12 * deviceGravity1[1] + g13 * deviceGravity1[2] +           a21 * deviceAngles2[0] + a22 * deviceAngles2[1] + a23 * deviceAngles2[2] +           g21 * deviceGravity2[0] + g22 * deviceGravity2[1] + g23 * deviceGravity2[2] +           a41 * deviceAngles3[0] + a42 * deviceAngles3[1] + a43 * deviceAngles3[2] +           g41 * deviceGravity3[0] + g42 * deviceGravity3[1] + g43 * deviceGravity3[2]) > bias;

значения a??, g??, bias берутся из обученной модели.

Точность моделей с разной конфигурацией на тестовой выборке можно увидеть в таблице:


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

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


Пример дерева принятия решений.

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

Обратка осанки без методов анализа данных

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

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


Показатели осанки у людей с большим депрессивным расстройством до (A) и после (B) лечения из статьи J.Canales et al (2010)

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



Конфигурация датчиков

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


В результате из двух углов, которые я пытался измерить (углы 3 и 4 на изображении из статьи), один измерялся корректно, а другой нет. Значения угла 3 совпадали с нормальными, указанными в статье. Угол 4 измерялся плохо из-за особенностей конструкции. Скорее всего, проблема заключается в том, что футболка в некоторых местах не плотно прилегает к телу, из-за чего угол наклона касательных вычисляется неверно.

Демо-видео

Вот демо-видео работы футболки и приложения:


Сначала включается обработка осанки, затем запускается калибровка, а после этого начинают приходить сообщения о корректности осанки.

Заключение

В результате у нас получилось обработать осанку двумя способами, разобраться с программированием под Android, написать приложение для Android и заодно немного разобраться с программированием микроконтроллера STM32.

Конечно, нельзя считать, что наша футболка закончена но пока мы работали над ней в течение одного семестра первого курса. Еще многое остается доделать, и в следующем году мы планируем продолжить!

Теперь немного о наших планах на будущее. Мы хотим:

• Усовершенствовать приближения позвоночника с помощью функции, чтобы точнее измерять углы, связанные с позвоночником.
• Собрать побольше данных для обработки осанки. На текущий момент данные сняты только с нас двоих и наши прототипы немного отличаются.
• Расширить функционал. Например, добавить снятие электрокардиограммы, чтобы по ней можно было выявлять различные болезни, отклонения и т.д.
• Усовершенствовать приложение: расширить его функционал. Например, подсчитывать статистику, анализировать её, рисовать графики.
• Создать прототип футболки, который будет иметь более товарный вид. На текущем этапе прототипы предназначены исключительно для тестирования функционала. Хочется собрать футболку, готовую для полноценного использования.

Ссылки на гитхаб проекта:

github.com/DT6A/Mithril прошивка микроконтроллера,
github.com/DT6A/MithrilApp приложение для android,
github.com/DT6A/MithrilData работа с данными.

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

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



Кратко: каждой команде назначили менторов из числа действующих разработчиков или студентов старших курсов с опытом работы в IT-компаниях. Еженедельно первокурсники рассказывали о прогрессе и сложностях, с которыми пришлось столкнуться, в анкете и во время созвона с ментором. Чтобы команды потренировались выступать публично (а заодно чтобы установить дедлайны, к которым нужно готовиться), мы организовали две предзащиты. На финальной защите все команды успешно представили проекты, средний балл студентов 9,0 по 10-балльной шкале.

Теперь подробнее:

Об организаторах

Мы Наташа Мурашкина, Саша Орлова и Оля Лупуляк студентки старших курсов Прикладной математики и информатики в Питерской Вышке. Мы занимались организацией проектов под руководством куратора направления и лектора курса по С++ Егора Суворова.

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

О проектах

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

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


Демо-видео проекта Fivaproljo (мультиплеерный платформер)

К концу семестра необходимо было получить хотя бы MVP проекта, но многие команды успели добавить больше функциональностей, а кто-то даже написать тесты и оформить страницу на GitHub с описанием и инструкцией по запуску. Примеры: Моделирование и визуализация динамических систем, Анализатор кода UB-tester tool, Компьютерная версия игры Колонизаторы.

Подготовка

В начале семестра студенты разделились на 21 команду по 3 человека. Каждая команда самостоятельно выбрала тему проекта и согласовала ее с организаторами, после чего получила контакты своего ментора.

Ментор это сотрудник IT-компании или студент старших курсов с опытом промышленной разработки. Менторы помогали с распределением задач и решением технических проблем. Они еженедельно созванивались со студентами, чтобы обсудить прогресс и составить план работ на следующую неделю. В число менторов вошли стажеры и сотрудники JetBrains, Яндекса, ВКонтакте, Huawei, Google, Delightex, VeeRoute и других компаний, преподаватели Летней компьютерной школы (ЛКШ), а также студенты нашего факультета, московского кампуса Вышки и кафедры КТ университета ИТМО.

В качестве эксперимента мы даже пригласили мета-ментора (ментора для ментора): опытный сотрудник Google наставлял нашего старшекурсника в менторстве команды.

Работа в течение семестра

Каждую неделю студентам нужно было созвониться с ментором и заполнить анкету о проделанной работе.

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

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

Воркшопы

За семестр студенты дважды тренировались выступать перед публикой и отвечать на вопросы во время воркшопов. Каждая команда представляла работу за 7 минут, показывала короткое демо-видео и еще 7 минут отвечала на вопросы аудитории.

Идея проводить репетиции не нова, и в нашем случае мы вдохновлялись воркшопами по публичным выступлениям, в которых Наташа участвовала во время стажировки в Google.

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

Структура презентации для воркшопов

• Титульный слайд
• Введение в область
• Краткое описание проекта
• Сравнение с аналогами
• Сравнение технологий
• Разбиение на подзадачи для каждого участника (по слайду на участника)
  
  • Описание подзадачи, решение, выводы
• Описание текущего состояния проекта (что было сделано с начала)
• Описание прогресса с предыдущей презентации
• Планы до конца разработки
• Можно сделать демо-видео не длиннее 30 секунд

Кстати, в блоге Питерской Вышки на Хабре уже есть инструкция по подготовке коротких докладов от декана нашего факультета Александра Владимировича Омельченко.


Демо-видео проекта Моделирование и визуализация динамических систем

Как оценивали вклад каждого участника

Здесь нам помогали коммиты студентов на GitHub и анкеты менторов.

К первому воркшопу и к защитам мы попросили студентов залить код проекта на GitHub. Количество строчек кода это, конечно, нечестная метрика, и нельзя судить только по ней, но ее мы использовали как первый фильтр. После вчитывались в содержание.

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

Итоговая оценка каждого студента за семестр складывалась из трех частей:

• 30% работа в течение семестра. Для хорошей оценки нужно вовремя сдавать анкеты.
• 35% оценка ментора. Для хорошей оценки нужно, чтобы ментор оценил прогресс.
• 35% оценка комиссии на защите. Для хорошей оценки нужно, чтобы в итоге что-то получилось.

Итоги

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


Скриншот с защиты проекта TorrentX

Мы довольны результатами ребят. Трое студентов (из 61) получили оценку удовлетворительно, все остальные хорошо и отлично. Средний балл 9,0 по 10-балльной шкале.

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

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

Менторы, судя по обратной связи, получили удовольствие от работы.

Как и мы :) Так что в следующем году планируем продолжить.

Планы на будущее

• Составить короткие тренинги или чек-листы ведения беседы для менторов. У многих менторов в этом году был управленческий или преподавательский опыт, но будет здорово, если мы сможем наладить систему и помочь тем, у кого такого опыта нет.

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

• Улучшить матчинг команда ментор, возможно, ввести собеседования между командой и ментором и маленькие тестовые задания. Учитывать пожелания менторов руководить более подготовленной (требует больше знаний) или менее опытной но не менее старательной! командой (требует лучших управленческих навыков).

• Улучшить качество обратной связи на воркшопах. Планируем вовлечь менторов и создать список блиц-вопросов по содержанию, которые мы со студентами сможем задавать выступающей команде.

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

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

И еще +100 заметок, которые мы бережно сохраняли в течение семестра.

Если вы хотели бы на волонтёрских основах побыть ментором студентов-первокурсников в следующем году, заполните форму или напишите нам в Телеграме (@murfel). Будем рады!

Всем привет! В этом посте я расскажу о проекте, который выполнил совместно с командой 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-ом также часто имеют в виду предобученные модели, которые опубликовали авторы метода, и которые можно очень легко и быстро дообучать для вашей задачи.

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Для сравнения результатов в наборе 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.

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

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

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

Что такое BBO

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

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

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

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

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

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

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

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

• означает максимальную глубину дерева (целое число от 1 до 15);
• означает минимальное число в процентах от всех сэмплов для того, чтобы дальше рассматривать разбиения этой вершины (вещественное число от 0.01 до 0.99);
• означает минимальное число в процентах от всех сэмплов, которое должно быть в любом листе (вещественное число от 0.01 до 0.49);
• означает минимальный вес, который должен находиться в любом из листьев (вещественное число от 0.01 до 0.49);
• означает максимальный процент от всего числа признаков, которые мы будем рассматривать для одного разбиения (вещественное число от 0.01 до 0.99);
• стоит за минимальным уменьшением 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 опять остается пустым.

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

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

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

С работой гауссовских процессов разберемся на примере задачи максимизации функции одной переменной . Для оптимизации этой функции мы построим суррогатную модель , которая будет приближать истинную функцию . Описываться наша суррогатная модель будет гауссовским процессом. Значения будут совпадать с значениями в тех точках , результаты которых мы знаем. Значения в остальных точках наша модель будет представлять распределениями, ведь мы не знаем их наверняка. Используя гауссовский процесс, эти распределения будут нормальными . Оценки на среднее и дисперсию получаются из определения гауссовского процесса, который задается значениями в определенных точках и матрицей ковариаций с выбранным ядром. Более подробно про технику гауссовского процесса и нахождения и можно почитать, например, в Википедии. Нам же будет важно его применение для оптимизации.

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

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

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

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

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

1. Строим гауссовский процесс по уже имеющимся наблюдениям .
2. Сэмплируем какое-то количество кандидатов (в нашем решении , где количество оптимизируемых параметров).
3. Используя построенный гауссовский процесс, мы вычисляем оценки на средние и дисперсии значений в кандидатах.
4. Вычисляем функцию приобретения в этих кандидатах и выбираем 8 с наибольшими значениями.
5. Возвращаем эти точки как наши предложения проверяющему коду.

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

Наш подход

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

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

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

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

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

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

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

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

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

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

Заключение

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

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

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