Как мы заняли первое место в хакатоне ВК «Машинное обучение на графах», где не было графов

В сентябре 2022 проходил хакатон «Машинное обучение на графах» от компании ВК на платформе «Цифровой прорыв». В хакатоне участвовала команда Лаборатории машинного обучения Альфа-Банка: Александр Сенин, Георгий Смирнов и Валерий Смирнов.

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

Контекст

В хакатоне допускалось участие команд до 5 человек в каждой. Основная масса участников — студенты вузов МГУ, МФТИ, ИТМО, МИРЭА. Наша команда не была исключением, мы студенты последних курсов ВМК и мехмата МГУ. 

Особенности хакатона:

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

• Хакатон был полностью очным. Все 43 часа требовалось находиться на площадке в офисе ВК. Провести две ночи в офисе — необычный опыт.

• Финальное ранжирование команд проводилось не только по скору в лидерборде, но и с учетом оценок жюри.

Склонность к благотворительности

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

Данные органично распались на 3 домена:

• Табличные данные — больше 1000 признаков для каждого из 160 000 пользователей.

• Последовательности пользовательских состояний — последовательности хэшей средней длины 140, известные для 77% пользователей.

• Признаковые описания топа друзей, известные для 81% пользователей.

Метрика качества — всем привычный ROC AUC. Локально оценивали модели по кросс-валидации.

Обсудим каждый источник данных отдельно.

Табличные данные

Организаторы соревнования преисполнились в вопросе тщательной анонимизации данных — среди 1000 признаков было лишь два столбца с незашифрованными названиями: идентификатор клиента и дата. 

Однако, в названиях остальных признаков были оставлены подсказки. Примеры названий: u0=11, u8=6, i1056. 

Напрашивалось разбить признаки на группы, например, все признаки с префиксом u0. После разбивки нагенерировали новых признаков, применив агрегаты внутри одной группы признаков: сумма группы признаков, среднее и стандартное отклонение, минимум и максимум и т.д. После небольшого EDA добавили других признаков, а также удалили откровенно мусорные признаки, например, константные. 

Не обошлось и без ликов. Наверное, самый популярный в соревнованиях по машинному обучению — это лик в идентификаторе объекта. Добавление признака идентификатора клиента в числовом виде улучшало качество модели на 2 пункта ROC AUC. Скорее всего, идентификатором выступал номер строки в таблице, причем в момент его создания строки не были упорядочены абсолютно случайно. Однако, формат хакатона подразумевает честное рабочее решение без читов с ликами, поэтому от использования такого признака пришлось отказаться.

Последовательные данные

Последовательности пользовательских состояний были представлены в виде списка хэшей, например ['e84b0', '9a767', '0be67', ...]. Здесь можно увидеть еще одну подсказку. В данном случае хэши представлены в строковом виде, а значит имеем последовательность строк. Последовательность строк можно воспринимать как последовательность слов и смотреть на задачу в парадигме обработки текстов на естественном языке (NLP). 

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

В NLP задачах существует популярный бейзлайн с использованием TF-IDF представлений, который часто бывает непросто побить. Применили в нашей задаче TF-IDF, получили 34 000 признаков для каждой последовательности. Понизили размерность через сингулярное разложение до 512 признаков. Это преобразование можно воспринимать как построение эмбеддинга пользователя по последовательности состояний. Такой бейзлайн улучшил итоговое качество на 2 пункта ROC AUC.

Данные друзей

По 81% пользователей были даны признаки их друзей, в среднем, по 76 друзей на пользователя. Признаки здесь те же самые, что и в признаковом описании самого пользователя — вновь признаки с префиксами вида u0=<число>, i<число> и т.д. 

Кроме этих признаков, был ещё один — идентификатор друга. Однако, множество идентификаторов друзей не пересекалось со множеством идентификаторов пользователей. Связать ребрами пользователей только по идентификаторам не получилось бы. Не было и данных по друзьям друзей. Организаторы объяснили это так: если брать данные по всем друзьям в окрестности больше 1, то пришлось бы выгружать весь граф ВК. К тому же, не был известен таргет у друзей.

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

На признаках друзей мы сгенерировали аналогичные признаки, что и на табличных данных основных пользователей. Следующий естественный шаг — отобрать топ признаков (мы взяли топ-100 по feature importance), а затем сделать агрегаты по топу признаков у друзей. Добавление таких усредненных по друзьям признаков увеличило качество еще на 1 пункт ROC AUC.

Ансамбль из коробки

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

Хакатон длился меньше 2 суток, поэтому мы решили не тратить время на тюнинг гиперпараметров, а доверить это готовым фреймворкам. Выбрали LightAutoML, который часто используют в табличных соревнованиях на Kaggle. Из коробки LightAutoML выбивает хорошее качество, которое не так просто улучшить. Под капотом LightAutoML обучает самые популярные модели бустингов (CatBoost и LightGBM) и строит несколько уровней ансамблирования. 

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

А где же граф?

Кейс хакатона назывался «Машинное обучение на графах», хотя в явном виде графов в этой задаче не было.

Мы решили это исправить и самостоятельно восстановить ребра между пользователями. Нужно было:

• перевести пользователей в некоторое пространство эмбеддингов;

• найти в этом пространстве k ближайших соседей к заданному пользователю;

• связать ребрами пользователя с его ближайшими соседями.

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

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

• Нашли для каждого пользователя 4 ближайших соседей, применили аналог target encoding (для каждого соседа известен таргет, можно напрямую использовать таргет соседа, не боясь ликов и переобучения).

• Получили 4 дополнительных признака: таргет ближайшего соседа, таргет второго по удаленности соседа и т.д.

• Применили агрегаты на таргетах соседей (среднее, минимум, максимум).

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

Такой target encoding улучшил качество ещё на 1 пункт ROC AUC.

Время нейросетей

На сырых табличных данных нейросети обычно проигрывают бустингу. Другое дело – обработка последовательных данных (sequence processing) или графовых данных (graph processing). 

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

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

Для обучения эмбеддингов последовательности мы использовали библиотеку pytorch-lifestream. Эта библиотека не первый раз появляется в соревнованиях, например, в этом году ее использовали сразу несколько победителей и призеров в соревновании Data Fusion. С помощью pytorch-lifestream в self-supervised режиме построили эмбеддинги последовательностей (под капотом идея с маскированием, как в трансформерах).

Финальная архитектура на рисунке.

Кто победил?

Особенность хакатона — необходимость защиты решения.

Требовалось в 7-минутном формате запитчить модель. Здесь пригодился скилл грамотной подготовки слайдов и построения интересного устного рассказа.

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

Эпилог

Что мы успели попробовать, но не зашло:

• Графовые нейросети.

• Обучение нейросетевого энкодера на последовательностях end-to-end.

• Обучение независимых моделей на разных доменах данных.

Из очевидных вещей, которые хотелось попробовать, но не успели — заменить TF-IDF по последовательностям на полноценный word2vec. Обучить трансформер на таких объемах данных проблематично, а обычный word2vec, кажется, вполне реально. 

Если смотреть на feature importance финальной модели, то хорошо зашли расстояния и таргеты ближайших соседей, некоторые агрегаты по друзьям и признаки по последовательностям после SVD.

Что почитать?

• Про фреймворк LightAutoML

• Как я участвовал в соревновании по машинному обучению и занял второе место (и почему не первое)

• Как мы участвовали в чемпионате по DS длиной 3,5 месяца

• Как и зачем мы начали искать бизнес-инсайты в отзывах клиентов с помощью машинного обучения

• Нейросетевой подход к кредитному скорингу на данных кредитных историй

• Знакомство с Apache Airflow: установка и запуск первого DAGа

• «Бесполезные» доклады о том, как кочегарить, инференсить и моделировать LTV: как прошёл Data Science Meet Up #2

Также подписывайтесь на Телеграм-канал Alfa Digital — там мы постим новости, опросы, видео с митапов, краткие выжимки из статей, иногда шутим.