В данной работе рассказывается о проблеме «холодного старта» в рекомендательных системах.
Ключевые слова: бандитский алгоритм, машинное обучение, ACM, CTR.
Каждый день мы сталкиваемся с различными сайтами и социальными сетями. Все эти сервисы, предоставляя интересный контент, стремятся максимально угодить пользователям. Такие ресурсы изменяют свое содержание и наполнение, подстраиваясь к предпочтениям каждого конкретного пользователя. Одним из решений задач персонализации контента являются рекомендательные системы.
На сегодняшний день существует несколько подходов к построению таких систем: коллаборативная фильтрация [1], MAB (Multi-Armed Bandits) [2], графовые методы [3] и т. д. Так или иначе многие из этих подходов сводятся к задачам машинного обучения по имеющейся истории взаимодействий, выбирающих наиболее релевантный контент. Однако во многих ситуациях такой истории нет, например, для новых пользователей, и рекомендательная система не может дать качественный прогноз для данного пользователя. Это и называется проблемой «холодного старта». Далее будут рассмотрены некоторые вышеперечисленные методы в контексте проблемы «холодного старта». Необходимо для данной группы пользователей и ресурсов построить адекватные рекомендации.
Бандитские алгоритмы
Подробнее остановимся на алгоритмах многоруких бандитов из-за их малоизученности и специфичности применения.
Представим, что перед нами стоит N различных игровых автоматов. При нажатии на ручку мы получаем какой-то выигрыш. Необходимо максимизировать суммарную прибыль всех нажатий на ручки. Задача заключается в нахождении оптимального способа выбора ручки на очередном шаге. Математически это можно записать так:
A — множество доступных действий («ручек»);
— контекст (информация об объектах и/или пользователях) на определенном шаге. Он определяется средой, в которой рассматриваются многорукие бандиты;
— ожидаемые выплаты для ручки a, которые можно получить в момент времени t при заданном контексте 
;
— реальная награда, наблюдаемая на шаге t.
В данной работе рассмотрены некоторые виды алгоритмов многоруких бандитов, а именно UCB1 и ε-greedy [4], disjoint-linUCB и hybrid-linUCB [2]. Проверка их эффективности проводилась на примере задачи Yahoo! [5] по рекомендации новостей пользователям. При этом использовалась метрика CTR (отношение числа кликов к числу показов). Результаты приведены на рисунках 1, 2.
При этом во время работы алгоритмов считалось, что изначально все объекты и пользователи являются новыми для системы, т. к. до старта алгоритмов не использовалась никакая информация об истории показов. Вся работа методов основана на статистических данных и признаковых представлениях объектов и пользователей (только для контекстных алгоритмов).
Рис. 1: Бесконтекстные алгоритмы
Рис. 2: Контекстные алгоритмы
«Холодный старт» в рекомендательных системах.
Как уже упоминалось ранее, проблема «холодного старта» является одной из основных задач, возникающих при построении рекомендательных систем: что рекомендовать новым пользователям и кому показывать новые объекты. В бесконтекстных алгоритмах эта задача решается с помощью накопленной статистической информации. В частности, новому пользователю чаще всего будут показаны наиболее популярные объекты (с большим значением
) и с некоторой вероятностью, которая определяется значениями параметров ε и α для ε-greedy и UCB1 соответственно, новые объекты. В случае, когда в систему попал новый объект item, алгоритм UCB1 из-за особенностей определения показываемых ручек (в формуле 
+ + 
второе слагаемое будет стремится к бесконечности из-за малости 
для новых объектов) будет некоторое время показывать именно item для сбора информации о нем. При этом, ε-greedy будет по-прежнему использовать наиболее популярные ручки, но с вероятностью 
, где k = |A|, покажет очередному пользователю item. Контекстные алгоритмы, в свою очередь, для новых элементов используют начальные данные о них. Для пользователя, например, это могут быть его пол, возраст, регион, род деятельности и т. д. По этим данным строятся некоторые вектора контекстов 
и 
и осуществляется действие алгоритма. В этих контекстах будут только те компоненты, которые определяются по начальным данным, о которых говорилось выше. Остальные будут нулевыми. При этом будет собираться статистика и выявляться зависимость между объектами и пользователями, которая хранится во время исполнения алгоритма внутри различных матриц и векторов. Далее если встретится очередной новый пользователь user с контекстом, похожим на тот, который уже видела система, то рекомендация будет строится уже с учетом информации, полученной во время предыдущего взаимодействия пользователя, похожего на user. В отличие от алгоритмов многоруких бандитов прочие методы такие, как коллаборативная фильтрация и графовые методы, не имеют встроенных возможностей для решения задачи «холодного старта». С этой целью разработаны различные методики для доработки функциональности этих алгоритмов. В методах коллаборативной фильтрации для пользователя/объекта строится некое усредненное представление по схожим элементам. Для пользователей, например, рассматриваются их демографические признаки такие, как пол, возраст, семейное положение, регион и т. д. Для объектов рассматриваются схожести по жанру, автору (новая книга известного автора скорее всего будет рекомендоваться гораздо чаще остальных) и т. д. в зависимости от сущности объектов. Для графовых методов согласно [3] используются различные эвристики популярности объектов и пользователей с введением разнообразных функций релевантности rel(v). При этом рекомендации осуществляются с помощью различных способов обхода графа вкусов с использованием этих функций релевантности (например, random walk из вершины, для которой необходимо составить рекомендацию).
Заключение
В результате проведенного исследования выявлено, что бандитские алгоритмы достаточно хорошо справляются с проблемой холодного старта. Это видно на рисунках, демонстрирующих эффективность алгоритмов. Также стоит заметить, что данные методы работают хорошо и для старых объектов. В дальнейшем будет продолжено исследование в области применения класса многоруких бандитов с более сложными моделями как для задач рекомендации, так и в новых областях науки и человеческой деятельности.
Литература:
- MachineLearning.ru — профессиональный информационно- аналитический ресурс, посвященный машинному обучению, распознаванию образов и интеллектуальному анализу данных. [Электронный ресурс]: URL:http://www.machinelearning.ru (дата обращения: 17.06.19).
- Li L., Chu W., Langford J., Schapire R. E. A contextual-bandit approach to personalized news article recommendation // Proceedings of the 19th International Conference on World Wide Web. 2010. P. 661–670.
- Musical recommendations and personalization in a social network // Proceedings of the 7th ACM Conference on Recommender Systems. 2013. P. 367–370.
- Auer P., Cesa-Bianchi N., Fischer P. Finite-time analysis of the multiarmed bandit problem // Machine Learning. 2002. Vol. 47. No 2–3. P. 235–256.
- Yahoo! Front page today module user click log dataset, version 1.0 (1.1 GB) [Электронный ресурс]: URL:https://webscope.sandbox.yahoo. com/catalog.php?datatype=r&did=49 (дата обращения: 17.06.19).
