Турнирный подход к выбору рекомендательных алгоритмов разработали в ВШЭ

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

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

Спортивная модель для алгоритмов

В основе метода лежит модель Брэдли — Терри, которая традиционно используется для ранжирования по результатам парных сравнений. В исследовании «игроками» выступали сами алгоритмы, а «матчами» — проверки на данных. Два алгоритма сравнивались по выбранной метрике, например по точности рекомендаций. Тот, кто показывал лучший результат, объявлялся победителем. Проанализировав все попарные исходы, модель оценивала относительную силу каждого участника.

Авторы обучили и протестировали 14 алгоритмов на 89 наборах данных из различных областей. Результаты показали, что позиции алгоритмов в рейтинге сильно зависят от характеристик данных. Например, на последовательных наборах, где важен порядок действий пользователя, лидировали алгоритмы SASRec и GASATF, но на данных без выраженной последовательности они опускались на десятое и одиннадцатое места, уступая первое место LightGCN и ALS.

Устойчивость и прогностическая сила

Дополнительно исследователи проверили, насколько стабильны рейтинги при неполных данных. Оказалось, что модель Брэдли — Терри сохраняет устойчивость даже при отсутствии части сравнений. Более того, расширенная версия модели, учитывающая контекст набора данных (например, число пользователей и объектов), позволяет предсказывать победителей без непосредственного сравнения алгоритмов.

«Идея использовать спортивную модель пришла к нам благодаря работам нашего старшего коллеги Спокойного В.Г. Если приводить аналогию со спортом, на исход поединка влияют не только сами участники, но и условия — например, город или погода. В исследовании таким контекстом стали характеристики набора данных», — пояснил один из авторов статьи, эксперт Международной лаборатории стохастических алгоритмов и анализа многомерных данных Антон Лысенко.

Практическая значимость подхода очевидна: в 78% случаев алгоритм, занявший первое место в рейтинге, действительно попадал в тройку лучших при проверке, в то время как при обычном усреднении показателей этот показатель составлял лишь 16%. Это объясняется тем, что предложенный метод имеет теоретическое обоснование, в отличие от эвристических способов сравнения.

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