Проблема «холодного старта» | Статья в журнале «Молодой ученый»

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

Опубликовать статью в журнале

Библиографическое описание:

Проблема «холодного старта» / Р. З. Омаров, А. В. Востротина, А. Д. Ли [и др.]. — Текст : непосредственный // Молодой ученый. — 2019. — № 26 (264). — С. 85-88. — URL: https://moluch.ru/archive/264/61285/ (дата обращения: 21.09.2020).



В данной работе рассказывается о проблеме «холодного старта» в рекомендательных системах.

Ключевые слова: бандитский алгоритм, машинное обучение, 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 из вершины, для которой необходимо составить рекомендацию).

Заключение

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

Литература:

  1. MachineLearning.ru — профессиональный информационно- аналитический ресурс, посвященный машинному обучению, распознаванию образов и интеллектуальному анализу данных. [Электронный ресурс]: URL:http://www.machinelearning.ru (дата обращения: 17.06.19).
  2. 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.
  3. Musical recommendations and personalization in a social network // Proceedings of the 7th ACM Conference on Recommender Systems. 2013. P. 367–370.
  4. 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.
  5. 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).
Основные термины (генерируются автоматически): пользователь, CTR, алгоритм, система, ACM, MAB, бандит, данные, задача, машинное обучение.


Ключевые слова

машинное обучение, бандитский алгоритм, ACM, CTR

Похожие статьи

Тестирование интернет-страниц как решение задачи о многоруком...

Задача о многоруком бандите является частным случаем дилеммы

В силу простоты реализации жадный алгоритм широко используется для решения задачи о многоруком

Рассмотрим несколько случаев входных данных, на которых продемонстрируем работу...

Микросервисная архитектура при решении задач машинного...

Машинное обучение (как и «глубокое обучение») становятся все более популярными и широко используемыми.

обучение (также известное как разработка или создание модели). Учебный конвейер («training pipeline») анализирует данные с использованием выбранного вами...

Предсказание уходов пользователей сервиса с помощью...

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

Задача предсказания уходов пользователей в ближайшее время представима в виде задачи

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

Роль больших данных в глубинном обучении | Статья в журнале...

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

Алгоритм К-средних сначала выбирает данные K случайным образом в качестве исходного центра кластера, а остальные данные...

Применение машинного обучения для обнаружения сетевых...

Обнаружение вторжений изучается в течение последних 20 лет. Вторжение — это деятельность, которая нарушает политику безопасности информационной системы [1]. Обнаружение вторжений основано на предположении...

Алгоритмы распознавания объектов | Статья в сборнике...

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

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

Разработка вопросно-ответной системы с использованием...

Обоснована задача создания автоматизированной вопросно-ответной системы.

Данный подход требует от пользователя времени на прочтение перечня вопросов и выявление среди них

Затем этот же алгоритм применяется к вопросу, заданному пользователем системы.

Анализ поисковых алгоритмов при решении задач...

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

Анализ применения гомоморфных схем шифрования...

Для решения этой задачи часто применяется метод машинного обучения — актуальной и

Одиночные стрелки указывают входные данные алгоритма, а двойные стрелки указывают

Наиболее перспективным методом шифрования в схемах машинного обучения является...

Похожие статьи

Тестирование интернет-страниц как решение задачи о многоруком...

Задача о многоруком бандите является частным случаем дилеммы

В силу простоты реализации жадный алгоритм широко используется для решения задачи о многоруком

Рассмотрим несколько случаев входных данных, на которых продемонстрируем работу...

Микросервисная архитектура при решении задач машинного...

Машинное обучение (как и «глубокое обучение») становятся все более популярными и широко используемыми.

обучение (также известное как разработка или создание модели). Учебный конвейер («training pipeline») анализирует данные с использованием выбранного вами...

Предсказание уходов пользователей сервиса с помощью...

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

Задача предсказания уходов пользователей в ближайшее время представима в виде задачи

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

Роль больших данных в глубинном обучении | Статья в журнале...

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

Алгоритм К-средних сначала выбирает данные K случайным образом в качестве исходного центра кластера, а остальные данные...

Применение машинного обучения для обнаружения сетевых...

Обнаружение вторжений изучается в течение последних 20 лет. Вторжение — это деятельность, которая нарушает политику безопасности информационной системы [1]. Обнаружение вторжений основано на предположении...

Алгоритмы распознавания объектов | Статья в сборнике...

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

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

Разработка вопросно-ответной системы с использованием...

Обоснована задача создания автоматизированной вопросно-ответной системы.

Данный подход требует от пользователя времени на прочтение перечня вопросов и выявление среди них

Затем этот же алгоритм применяется к вопросу, заданному пользователем системы.

Анализ поисковых алгоритмов при решении задач...

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

Анализ применения гомоморфных схем шифрования...

Для решения этой задачи часто применяется метод машинного обучения — актуальной и

Одиночные стрелки указывают входные данные алгоритма, а двойные стрелки указывают

Наиболее перспективным методом шифрования в схемах машинного обучения является...

Задать вопрос