Как работают рекомендательные системы. Лекция в Яндексе
Привет, меня зовут Михаил Ройзнер. Недавно я выступил перед студентами Малого Шада Яндекса с лекцией о том, что такое рекомендательные системы и какие методы там бывают. На основе лекции я подготовил этот пост.План лекции:
Виды и области применения рекомендательных систем.
Простейшие алгоритмы.
Введение в линейную алгебру.
Алгоритм SVD.
Измерение качества рекомендаций.
Направление развития.
Начнем с простого: что вообще такое рекомендательные системы, и какими они бывают. Наверное, все уже сталкивались с ними в интернете. Первый пример — рекомендательные системы фильмов.
На сайте imdb.com пользователи могут оценивать фильмы по десятибалльной шкале. Оценки агрегируются, получается средний рейтинг фильма. На этом же сайте есть блок с рекомендациями для конкретного пользователя. Если я зашел на сайт и оценил несколько фильмов, imdb сможет порекомендовать мне еще какие-нибудь фильмы. Похожий блок есть и на фейсбуке.
Нечто сходное, но только для музыки, делает last.fm. Он рекомендует мне исполнителей, альбомы, мероприятия, на которые мне стоит сходить. Сервис Pandora в России почти неизвестен, т.к. у нас он не работает, однако в Америке он очень популярен. Это такое персональное радио, которое постепенно подстраивается под пользователя на основе его оценок, и в итоге играет только те треки, которые ему нравятся.
Еще одна известная область — рекомендация товаров. На картинке ниже у нас, конечно же, Amazon. Если вы купили что-то на амазоне, за вами будут охотиться с дополнительными предложениями: похожими товарами или аксессуарами. Это хорошо и для пользователей (им не нужно искать эти товары самостоятельно), и конечно, это хорошо для самого магазина.
Мы перечислили три категории, но на самом деле их гораздо больше: заведения на карте, новости, статьи, сайты, концерты, театры, выставки, видео, книги, приложения, игры, путешествия, социальные связи и многое другое.
Виды рекомендательных системМожно выделить два основных типа рекомендательных систем. Их, конечно же больше, но мы сегодня будем рассматривать именно эти и в особенности коллаборативную фильтрацию.Content-basedПользователю рекомендуются объекты, похожие на те, которые этот пользователь уже употребил. Похожести оцениваются по признакам содержимого объектов. Сильная зависимость от предметной области, полезность рекомендаций ограничена. Коллаборативная фильтрация (Collaborative Filtering)Для рекомендации используется история оценок ккак самого пользователя, так и других пользователей. Более универсальный подход, часто дает лучший результат. Есть свои проблемы (например, холодный старт). Рекомендательные системы появились в интернете достаточно давно, около 20 лет назад. Однако настоящий подъем в этой области случился примерно 5–10 лет назад, когда произошло соревнование Netflix Prize. Компания Netflix тогда давала в прокат не цифровые копии, а рассылала VHS-кассеты и DVD. Для них было очень важно повысить качество рекомендаций. Чем лучше Netflix рекомендует своим пользователям фильмы, тем больше фильмов они берут в прокат. Соответственно, растет и прибыль компании. В 2006 году они запустили соревнование Netflix Prize. Они выложили в открытый доступ собранные данные: около 100 миллионов оценок по пятибалльной шкале с указанием ID проставивших их пользователей. Участники соревнования должны были как можно лучше предугадывать, какую оценку поставит определенному фильму тот или иной пользователь. Качество предсказания измерялось при помощи метрики RMSE (средне-квадратичное отклонение). У Netflix уже был алгоритм, который предсказывал оценки пользователей с качеством 0.9514 по метрике RMSE. Задача была улучшить предсказание хотя бы на 10% — до 0.8563. Победителю был обещан приз в $ 1 000 000. Соревнование длилось примерно три года. За первый год качество улучшили на 7%, дальше все немного замедлилось. Но в конце две команды с разницей в 20 минут прислали свои решения, каждое из которых проходило порог в 10%, качество у них было одинаковое с точностью до четвертого знака. В задаче, над которой множество команд билось три года, все решили каких-то двадцать минут. Опоздавшая команда (как и многие другие, участвовавшие в конкурсе) остались ни с чем, однако сам конкурс очень сильно подстегнул развитие в этой области.Простейшие алгоритмы Для начала формализуем нашу задачу. Что мы имеем? У нас есть множество пользователей
