Введение 3
Постановка задачи 5
Обзор литературы 6
Глава 1. Анализ существующих решений 8
1.1. Коллаборативная фильтрация 8
1.1.1 Тривиальный подход 8
1.1.2 User-based 9
1.1.3 Item-based 9
1.1.4 Латентные модели 11
1.2. Графовые методы 13
Глава 2. Бандитские алгоритмы 15
2.1. Бесконтекстные алгоритмы 15
2.1.1 "-greedy 15
2.1.2 UCB1 16
2.2. Контекстные алгоритмы 17
2.2.1 disjoint-linUCB 17
2.2.2 hybrid-linUCB 19
2.3. «Холодный старт» в задаче многоруких бандитов 21
Глава 3. Метод offline оценки 22
Глава 4. Тестовая задача 25
Глава 5. Задача рекомендации групп 29
5.1. Методы обработки данных 29
5.1.1 Исходные данные 30
5.1.2 Билинейное отображение 31
5.1.3 Кластеризация 32
5.2. Анализ полученных результатов 33
Выводы 37
Заключение 38
Список литературы 39
Крупные онлайн площадки, предоставляющие пользователям доступ к информации, а авторам и сообществам релевантную аудиторию, на данный момент являются неотъемлемой частью нашей жизни. Каждый день мы сталкиваемся с различными сайтами, социальными сетями. И все эти сервисы стремятся максимально угодить пользователям, предоставляя интересный для них контент. Внедрение элементов персонализации в подобные сервисы считается уже де-факто стандартом. Такие ресурсы изменяют свое содержание и наполнение (а иногда даже и функциональность), подстраиваясь к предпочтениям каждого конкретного пользователя.
Одним из решений задач персонализации контента являются рекомендательные системы. Рекомендательная система - это такой метод, который подбирает пары пользователь - ресурс, максимально удовлетворяющие интересы обеих сторон. Например, необходимо подобрать и показать посетителю такой товар в интернет магазине, который наверняка его заинтересует, и он (посетитель) скорее всего это купит. Или нужно показать пользователю на странице в социальной сети сообщество, которое будет удовлетворять его интересам, и к которому он возможно присоединится. Подобных примеров очень много. В связи с тем, что задачи рекомендации чего-либо кому-либо могут иметь разные постановки и конечные цели, существует множество различных подходов к решению данных проблем. При построении рекомендательной системы необходимо выделить следующие характеристики, которые позволяют описать ее:
1. Предмет - это то, что рекомендуется системой. Это могут быть сайты, музыка, объявления и т.д.
2. Цель - для чего это делается. К примеру, покупка, переход по ссылке на сайт, прослушивание определенной композиции.
3. Источник - тот, кто рекомендует. Это могут быть как другие пользователи ресурса, так и сам ресурс в лице его владельцев.
4. Контекст - при каком действии пользователя ему начинают что- либо рекомендовать. Это может быть просмотр новостей, прослушивание музыки или же рекомендации начинаются сразу же при посещении главной страницы сайта.
5. Персонализированность - мера того, насколько сильно будет подстраиваться система под ваши интересы.
На сегодняшний день существует несколько подходов к построению рекомендательных систем: коллаборативная фильтрация, MAB (Multi-Armed Bandits), графовые методы и т.д. Далее будут рассмотрены некоторые вышеперечисленные методы, их достоинства и недостатки, в особенности в контексте проблемы «холодного старта» (cold-start problem). Так или иначе многие из этих подходов сводятся к задачам машинного обучения по имеющейся истории взаимодействий, выбирающих наиболее релевантный контент. Однако во многих ситуациях такой истории нет - например, для новых пользователей, и рекомендательная система не может дать качественный прогноз для такого пользователя. Это и называется проблемой «холодного старта». Однако необходимо и для данной группы пользователей и ресурсов строить адекватные рекомендации, чтобы максимально удовлетворить и тех, и других.
В ходе исследования были подробно изучены некоторые виды алгоритмов многоруких бандитов. Результатами работы являются полученные выводы о сходимости и эффективности этих методов, а также инструментарий для работы с ними.
Важно отметить, что основными недостатками бандитских методов обучения являются высокая чувствительность к исходным данным и вычислительным возможностям рекомендательной системы. В частности, время работы контекстных алгоритмов квадратично зависит от размеров признаковых описаний элементов системы. Именно с этой целью и был разработан инструментарий для предобработки и снижения размерности данных.
Кроме того, важным моментом при решении задач с бандитскими методами является определение множества актуальных объектов. Ведь чем больше это множество, тем больше времени потребуется на обработку одного события, поскольку нужно вычислить ожидаемые выплаты pt;a для каждого объекта из этого множества.
Однако эти методы обладают рядом достоинств. Например, их можно обучать параллельно с тем, пока работает какой-либо другой алгоритм рекомендации, не теряя при этом эффективности на еще необученном алгоритме. Также бандитские алгоритмы могут хорошо справляться с проблемой «холодного старта» по методике, описанной в пункте 2.3 главы 2.
Подводя итоги, можно заключить, что применение бандитских алгоритмов в данной задаче приемлемо, но требует большого внимания к реализации, в частности, к техническим средствам и способу представления исходных данных. Кроме того, обучение этих моделей может занять довольно длительной время.
В дальнейшем планируется продолжить работу по увеличению скорости сходимости реализованных алгоритмов, а также рассмотрению более сложных моделей данного класса, в том числе в новых предметных областях.
