Рекомендательные системы: постановка задачи

    Всем привет! Меня зовут Сергей, я математик, и я определяю развитие рекомендательной системы Surfingbird. Этой статьёй мы открываем цикл, посвящённый машинному обучению и рекомендательным системам в частности – пока не знаю, сколько в цикле будет инсталляций, но постараюсь писать их регулярно. Сегодня я расскажу вам, что такое рекомендательные системы вообще, и поставлю задачу чуть более формально, а в следующих сериях мы начнём говорить о том, как её решать и как учится наша рекомендательная система Tachikoma.

    image

    Рекомендательные системы – это модели, которые лучше вас знают, чего вам хочется. Недавно слышал показательный анекдот: как известно, сети супермаркетов обычно стараются предсказать, чего вам хочется, чтобы вам это рекламировать (и это пример рекомендательной системы); в частности, супермаркет может попытаться распознать по изменившимся предпочтениям, что женщина забеременела, и начать это использовать. Так вот, рассказывают, что однажды в офис одного супермаркета ворвался разъярённый отец, чьей дочери-школьнице начали приходить по почте купоны на памперсы и детскую одежду; менеджеру пришлось долго извиняться и рассказывать, что все рекомендательные модели вероятностные, и ошибки вполне возможны. Через пару месяцев отец пришёл ещё раз и извинился сам – оказалось, что он далеко не всё знал о собственной дочери…

    Системы коллаборативной фильтрации – это модели, которые пытаются предсказать, насколько вам понравится тот или иной продукт, получая на вход данные о том, как вы и другие пользователи оценивали этот и другие продукты в прошлом. Коллаборативная фильтрация – это самый популярный ныне вид рекомендательных систем. В Surfingbird, например, ваши оценки – это кнопки like и dislike (а также тот факт, что вы посмотрели страницу и никакой оценки не поставили, но об этом позже). Чем больше у нас данных о ваших предпочтениях, тем более интересные страницы мы можем вам порекомендовать!

    Вот несколько других примеров широко известных рекомендательных систем.
    • Amazon – один из лидеров области; Amazon рекомендует вам книги и другие товары, основываясь на том, что вы покупали, что просматривали, какие рейтинги ставили, какие оставляли отзывы… Да, как это обычно и бывает, Большой Брат собирает всё, даже если кое-что пока не умеет использовать.
    • Netflix – в России мало знают эту компанию, да она и не работает на Россию, однако именно Netflix громче всех заявила о себе в научном сообществе, когда объявила знаменитый Netflix Prize, пообещав $1M за то, чтобы улучшить качество их алгоритма предсказаний на 10% (о Netflix Prize и уроках, которые из него удалось извлечь, мы поговорим в одной из следующих серий). Основа бизнеса Netflix – аренда фильмов; сейчас компания перешла на потоковое видео, однако первые десять лет своей жизни они рассылали по почте физические DVD, которые потом нужно было отсылать обратно, чтобы получить следующий (деньги при этом брались за подписку). Русскому человеку, конечно, трудно понять, как это – платить деньги за то, чтобы скачать фильм, или даже не скачать, а посмотреть онлайн – но модель оказалась очень успешной, а опубликованный для Netflix Prize набор данных на несколько лет стал главным тестовым примером для систем коллаборативной фильтрации (сейчас Netflix убрала его из открытого доступа по причине возможной деанонимизации, и на смену ему пришёл Yahoo! KDD Cup Dataset).
    • Last.fm и Pandora рекомендуют музыку. Они придерживаются разных стратегий рекомендации: Last.fm использует, кроме собственно рейтингов других пользователей, исключительно “внешние” данные о музыке – автор, стиль, дата, тэги и т.п., а Pandora основывается на “содержании” музыкальной композиции, используя очень интересную идею – Music Genome Project, в котором профессиональные музыканты анализируют композицию по нескольким сотням атрибутов (к сожалению, сейчас Pandora недоступна в России). Анализировать композиции автоматически пока, правда, никто хорошо не умеет – и это ещё одно интересное приложение усилий для машинного обучения...
    • Google, Yahoo!, Яндекс – можно сказать, что они тоже рекомендуют пользователям сайты? Формально — да, но в реальности это другие системы: поисковики пытаются предсказать, насколько данный документ релевантен данному запросу, а рекомендатели – пытаются предсказать, какой рейтинг данный пользователь поставит данному продукту. Конечно, в успехе поисковиков есть немалая заслуга моделей, основанных на данных от пользователей (click logs), и, конечно, поисковая выдача часто бывает персонализованной, но всё-таки задача немножко другая. Несколько ближе к нашей задаче проблема того, какую рекламу показывать пользователю (AdSense, Яндекс.Директ и т.д.) – здесь пользователи действительно «голосуют ногами» за рекламные объявления, и нужно «порекомендовать» те из них, которые скорее всего вызовут положительную реакцию. Но дело осложняется экономической стороной вопроса (рекламодатели платят деньги, между ними нужно устроить аукцион за право разместить рекламу), так что эти задачи мы тоже рассматривать сейчас не будем. Однако у ведущих поисковиков есть масса побочных проектов, основанных на рекомендательных системах – например, мы уже упоминали Yahoo! Music.

    Итак, возвращаемся к нашим баранам. Представим себе, что у нас есть множество пользователей и множество продуктов (для Surfingbird это веб-страницы, для Netflix – фильмы, для Last.fm – композиции), причём некоторые пользователи как-то оценили некоторые продукты. Формально говоря, данные состоят из троек вида image, где i обозначает пользователя, a – продукт, а image – рейтинг, который пользователь i поставил продукту a.

    Можно представить себе эти данные как матрицу, каждая строка которой соответствует пользователю, а столбец – продукту. Наша задача – предсказать неизвестные элементы матрицы; если быть точным, наша задача – предсказать, какие из неизвестных элементов будут максимальными в своей строке, то есть какие продукты больше всего понравятся тому или иному пользователю.

    У систем коллаборативной фильтрации есть несколько общих проблем, которые должна так или иначе решать любая модель.
    1. Матрица рейтингов, как правило, очень разреженная (sparse) – обычно и пользователей, и продуктов много, а рейтингов на деле гораздо меньше, чем их произведение, ведь средний пользователь оценивает совсем немного продуктов; остальные же элементы матрицы нам неизвестны, и как раз их-то и надо предсказывать.
    2. Проблема холодного старта (cold start). Для пользователей – когда приходит новый пользователь, у которого ещё нет рейтингов, что с ним делать? Ну хорошо, когда совсем нет, это ещё ничего – можно просто рекомендовать самые популярные продукты; а что делать, если пользователь уже что-то оценил, но пока очень мало чего? Для продуктов – сколько нужно рейтингов для нового продукта, прежде чем его можно будет уверенно рекомендовать? И откуда вообще возьмутся эти рейтинги, если не рекомендовать его никому?

    В следующих сериях мы поговорим о том, что делать с этими и другими проблемами, а также о том, как вообще можно предсказывать неизвестные рейтинги – следите за развитием событий!
    Surfingbird 75,93
    Компания
    Поделиться публикацией
    Похожие публикации
    Ой, у вас баннер убежал!

    Ну. И что?
    Реклама
    Комментарии 22
    • +10
      Есть очень важный культурный аспект таких систем.

      Все эти системы фильтрации контента, начинают немного пугать. Началось это примерно с момента, когда фейсбук начал показывать новости на основании «личных предпочтений», ему и только ему известными алгоритмами.

      Оказалось, что те люди, новости которых мне интересны, попали под автоматический фильтр.

      Лично меня это тревожит. Такие системы, начинают закрывать для нас все новые и новые горизонты и ограничивают наши круги интересов на все более узкие темы.
      В итоге это сеть станет настолько монотематична, что мозги деградировать будут.

      Так случилось у меня с Last.fm. Незаметно, он построил такую базу, за рамки которой я выйти просто не мог. Тоесть, он определил мои далеко не полные муз. предпочтения, и замкнулся на них.

      Печально что к этому стремится гугл и все новостные сайты. Каждый сам себе интеллектуальную тюрьму построит.
      • +2
        Этот культурный аспект известен как filter bubble, про это есть целая книжка. У меня своего отношения к этому нет; мне кажется, что это всё задачи, поддающиеся решению, и если будет спрос на то, чтобы выйти из filter bubble, то будут и решения, которые это делают.
        • 0
          > Этот культурный аспект известен как filter bubble

          Будем знать! Хотя название какое-то неудачное.

          Личный опыт подсказывает, что спрос может создавать маргинальное меньшинство. Большинство будет «хавать что дают».

          И прошу это не принимать как снобизм. Я не причисляю себя к «тем золотым 5%». Есть области, где я вхожу и в 5% и есть где в 1%. Но это узкоспециализированные темы связанные с тем что у меня есть специальное образование или специальные знания на тему.

          А есть целая пропасть тем и областей, где я преспокойно вхожу 95%. Также и каждый нормальный человек.

          Поэтому в массе своей мы не в состоянии создать спрос. Тут будет играть роль предложение.
          • 0
            Название из метафоры – каждый сидит в своём bubble, который создан коллаборативной фильтрацией, и за пределы не вылезает.

            > спрос может создавать маргинальное меньшинство
            Да, наверное, но ведь любое «маргинальное меньшинство» в интернете может включать в себя миллионы людей. Например, Minecraft – это очень маргинальная игра, на большого любителя. :)

            Но вообще да, для surfingbird будет важно пытаться вывести пользователя за пределы его привычного окружения – собственно, это ведь один из главных use cases…
            • 0
              > Название из метафоры – каждый сидит в своём bubble

              Да, я понял. Просто она не «сочная» какая-то :) Но и я лучшего ничего пока не придумал :)

              > «маргинальное меньшинство» в интернете может включать в себя миллионы людей

              Тоже правда.

              > вывести пользователя за пределы его привычного окружения – собственно, это ведь один из главных use cases

              Отлично!

              • 0
                Filter globe?
                (шутка в том, что то, что должно быть глобальным, оказывается больше похоже на snow globe)
        • 0
          Вот и вот хорошие способы выйти «за рамки базы» в Last.fm
          • 0
            Это во многом вопрос интерфейса. Если пользователь видит только то, что рекомендовано — такое эффект есть. Если рекомендация работает как подсказка — он минимален. Правда, и в этом случае можно направлять действия пользователя — тем не менее, при желании он всегда может не пользоваться этой подсказкой.
            • 0
              Уже вроде как определились, что эти системы жестко щемат и агрессивно фильтруют.
          • +1
            Надеюсь, с вашей системой не случится того же самого, что в итоге случилось с Татикомами из сериала)
            А то те тоже… Доучились.
            • 0
              Обожаю татиком, жду дальнейших статей
              • 0
                Не Татикомы а Тачикомы, двоечники. Верить надо не корявым субтитрам а оригиналу.
                • +1
                  Холивар на тему Поливанова на хабре?!
                  • 0
                    Не, на эту тему хай филологи холиварят. Мы же по простому, по рабоче-крестьянски, указали заблудшим душам как надо и… все… :-)
              • +1
                Очень интересный аспект рекомендательных систем, который зачастую не рассматривают, это целевая функция. Можно ведь рекомендовать, достигая определенных целей. Так, например, Amazon не ставит себе цель максимально удовлетворить пользователя, его задача — продать на как можно большую сумму. Существует уйма целей: максимальная оценка от пользователя, максимальная продажа, расширить опыт пользователя, неожиданность рекомендации (serendipity), рекомендации для группы пользователей (какой фильм посмотреть вместе с друзьями), и так далее.
                • 0
                  У нас, к счастью, ситуация достаточно чистая. Мы видим ваши лайки и хотим сделать так, чтобы вы ставили их почаще. :)
                • 0
                  большое спасибо за статью, всё думал откуда взять датасет для экспериментов
                  • 0
                    Netflix и KDDCup – большие датасеты, очень большие, они задуманы ещё и как проверка на «сможете ли вы хорошо реализовать то, что придумали». Для экспериментов лучше что-нибудь поменьше, например, movielens:
                    www.grouplens.org/node/73
                  • 0
                    Эх, в лучших традициях сериалов — на самом интересном месте.

                    А по теме, да, цель рекомендации важна. Я вот как-то им не доверяю, особенно если они это действительно рекомендуют (купить), а не просто информируют «кто покупает книжку, которую вы смотрите часто покупает и эту». Может цели и алгоритмы одни и те же, но даже формулировка отношение меняет. Из интереса можно посмотреть. То что навязывают рекомендуют — не буду.

                    А вот чего не видел — рекомендательного сервиса новостей. Приходится держать с пяток сайтов открытыми и время от времени их рефришить в надежде, что глаз за что-то зацепится.
                    • 0
                      Новости – это почти всегда тоже рекомендательная система, только другого типа: коллаборативная фильтрация – это «оффлайн-рекомендации», а новости – это «онлайн-рекомендации», когда главное – быстро за трендами следовать. Про это обязательно будет отдельная инсталляция, но, наверное, не очень скоро.
                    • 0
                      С нетерпением жду продолжения.

                      Кстати, ваша книжка про Винни-Пуха — одна из любимых по этой тематике :)

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

                    Самое читаемое