company_banner

Как работают рекомендательные системы. Лекция в Яндексе

    Привет, меня зовут Михаил Ройзнер. Недавно я выступил перед студентами Малого Шада Яндекса с лекцией о том, что такое рекомендательные системы и какие методы там бывают. На основе лекции я подготовил этот пост.



    План лекции:
    1. Виды и области применения рекомендательных систем.
    2. Простейшие алгоритмы.
    3. Введение в линейную алгебру.
    4. Алгоритм SVD.
    5. Измерение качества рекомендаций.
    6. Направление развития.



    Начнем с простого: что вообще такое рекомендательные системы, и какими они бывают. Наверное, все уже сталкивались с ними в интернете. Первый пример — рекомендательные системы фильмов.



    На сайте imdb.com пользователи могут оценивать фильмы по десятибалльной шкале. Оценки агрегируются, получается средний рейтинг фильма. На этом же сайте есть блок с рекомендациями для конкретного пользователя. Если я зашел на сайт и оценил несколько фильмов, imdb сможет порекомендовать мне еще какие-нибудь фильмы. Похожий блок есть и на фейсбуке.

    Нечто сходное, но только для музыки, делает last.fm. Он рекомендует мне исполнителей, альбомы, мероприятия, на которые мне стоит сходить. Сервис Pandora в России почти неизвестен, т.к. у нас он не работает, однако в Америке он очень популярен. Это такое персональное радио, которое постепенно подстраивается под пользователя на основе его оценок, и в итоге играет только те треки, которые ему нравятся.



    Еще одна известная область — рекомендация товаров. На картинке ниже у нас, конечно же, Amazon. Если вы купили что-то на амазоне, за вами будут охотиться с дополнительными предложениями: похожими товарами или аксессуарами. Это хорошо и для пользователей (им не нужно искать эти товары самостоятельно), и конечно, это хорошо для самого магазина.



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

    Виды рекомендательных систем


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

    1. Content-based
      • Пользователю рекомендуются объекты, похожие на те, которые этот пользователь уже употребил.
      • Похожести оцениваются по признакам содержимого объектов.
      • Сильная зависимость от предметной области, полезность рекомендаций ограничена.
    2. Коллаборативная фильтрация (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%, качество у них было одинаковое с точностью до четвертого знака. В задаче, над которой множество команд билось три года, все решили каких-то двадцать минут. Опоздавшая команда (как и многие другие, участвовавшие в конкурсе) остались ни с чем, однако сам конкурс очень сильно подстегнул развитие в этой области.

    Простейшие алгоритмы


    Для начала формализуем нашу задачу. Что мы имеем? У нас есть множество пользователей 𝑢 ∈ 𝑈, множество объектов 𝑖 ∈ 𝐼 (фильмы, треки, товары и т.п.) и множество событий (𝑟𝑢𝑖, 𝑢, 𝑖, ...) ∈ 𝒟 (действия, которые пользователи совершают с объектами). Каждое событие задается пользователем 𝑢, объектом 𝑖, своим результатом 𝑟𝑢𝑖 и, возможно, еще какими-то характеристиками. От нас требуется:

    • предсказать предпочтение:
      𝑟̂𝑢𝑖 = Predict (𝑢,𝑖,...) ≈ 𝑟𝑢𝑖.
    • персональные рекомендации:
      𝑢 ⟼ (𝑖1,...,𝑖𝘒) = Recommend𝘒(𝑢,...).
    • похожие объекты:
      𝑢 ⟼ (𝑖1,...,𝑖𝑀) = Similar𝑀(𝑖).

    Таблица оценок


    Допустим, нам дана таблица с оценками пользователей:



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



    Кластеризация пользователей


    Напомним, что основная идея коллаборативной фильтрации — похожим пользователям обычно нравятся похожие объекты. Начнем с самого простого метода.

    • Выберем некоторую условную меру схожести пользователей по их истории оценок 𝑠𝑖𝑚(𝑢, 𝑣).
    • Объединим пользователей в группы (кластеры) так, чтобы похожие пользователи оказывались в одном кластере: 𝑢 ⟼ 𝐹(𝑢).
    • Оценку пользователя объекту будем предсказывать как среднюю оценку кластера этому объекту:



    У этого алгоритма есть несколько проблем:
    • Нечего рекомендовать новым/нетипичным пользователям. Для таких пользователей не найдется подходящего кластера с похожими на них пользователями.
    • Не учитывается специфика каждого пользователя. В каком-то смысле мы делим всех пользователей на какие-то классы (шаблоны).
    • Если в кластере никто не оценивал объект, то предсказание сделать не получится.

    User-based


    Попробуем несколько улучшить предыдущий метод и заменить жесткую кластеризацию на следующую формулу:



    Однако у этого алгоритма также есть свои проблемы:
    • Нечего рекомендовать новым/нетипичным пользователям. Для таких пользователей мы все еще не можем найти похожих.
    • Холодный старт — новые объекты никому не рекомендуются.

    Item-based


    Есть абсолютно симметричный алгоритм:

    В предыдущем методе мы отталкивались от идеи, что, скажем, фильм понравится пользователю, если он понравился его друзьям. Здесь же мы считаем, что фильм понравится пользователю, если ему понравились похожие фильмы.

    Проблемы:
    • Холодный старт — новые объекты никому не рекомендуются.
    • Рекомендации часто тривиальны.

    Общие проблемы перечисленных методов


    Все перечисленные методы обладают следующими недостатками:
    • Проблема холодного старта.
    • Плохие предсказания для новых/нетипичных пользователей/объектов.
    • Тривиальность рекомендаций.
    • Ресурсоемкость вычислений. Для того, чтобы делать предсказания нам нужно держать в памяти все оценки всех пользователей.


    Поэтому перейдем к более сложному алгоритму, который практически лишен этих недостатков.

    Алгоритм SVD


    Для этого алгоритма нам потребуется несколько понятий из линейной алгебры: векторы, матрицы и операции с ними. Я не буду здесь приводить все определения, если вам нужно освежить эти знания, то все объяснения есть в видеозаписи лекции примерно с 33 минуты.

    SVD (Singular Value Decomposition), переводится как сингулярное разложение матрицы. В теореме о сингулярном разложении утверждается, что у любой матрицы 𝐀 размера 𝑛×𝑚 существует разложение в произведение трех матриц: 𝑈, Ʃ и 𝑉𝑇:


    Матрицы 𝑈 и 𝑉 ортогональные, а Ʃ — диагональная (хотя и не квадратная).


    Причем лямбды в матрице Ʃ будут упорядочены по невозрастанию. Сейчас мы эту теорему не будем доказывать не будем, просто воспользуемся самим разложением.

    Но что нам с того, что мы можем какую-то матрицу в произведение трех еще более непонятных матриц. Для нас тут будет интересно следующее. Помимо обычного разложения бывает еще усеченное, когда из лямбд, остаются только первые 𝑑 чисел, а остальные мы полагаем равными нулю.


    Это равносильно тому, что у матриц 𝑈 и 𝑉 мы оставляем только первые 𝑑
    столбцов, а матрицу Ʃ обрезаем до квадратной 𝑑×𝑑.


    Так вот, оказывается, что полученная матрица 𝐀′ хорошо приближает исходную матрицу 𝐀 и, более того, является наилучшим низкоранговым приближением с точки зрения средне-квадратичного отклонения.

    SVD для рекомендаций


    Как же использовать все это для рекомендаций? У нас была матрица, мы разложили ее в произведение трех матриц. При чем разложили не точно, а приблизительно. Упростим все немного, обозначив произведение первых двух матриц за одну матрицу:


    Теперь отвлечемся немного от всех этих матриц и сконцентрируемся на получившемся алгоритме: чтобы предсказать оценку пользователя 𝑈 для фильма 𝐼, мы берем некоторый вектор 𝑝𝑢 (набор параметров) для данного пользователя и вектор для данного фильма 𝑞𝑖. Их скалярное произведение и будет нужным нам предсказанием: 𝑟̂𝑢𝑖 = ⟨𝑝𝑢,𝑞𝑖⟩.

    Алгоритм достаточно простой, но дает удивительные результаты. Он не просто позволяет нам предсказывать оценки. С его помощью мы можем по истории пользователей выявлять скрытые признаки объектов и интересы пользователей. Например, может так получиться, что на первой координате вектора у каждого пользователя будет стоять число, показывающее, похож ли пользователь больше на мальчика или на девочку, на второй координате — число, отражающее примерный возраст пользователя. У фильма же первая координата будет показывать, интересен ли он больше мальчикам или девочкам, а вторая — какой возрастной группе пользователей он интересен.

    Но не все так просто. Есть несколько проблем. Во-первых, матрица оценок 𝑹 нам полностью не известна, поэтому мы не можем просто взять ее SVD-разложение. Во-вторых, SVD-разложение не единственное: (𝑈Ω)Ʃ(𝑉Ω)𝑇=𝑈Ʃ𝑉𝑇, поэтому даже если мы найдем хоть какое-то разложение, вряд ли именно в нем первая координата будет соответствовать полу пользователя, а вторая — возрасту.

    Обучение


    Попробуем разобраться с первой проблемой. Тут нам понадобится машинное обучение. Итак, мы не можем найти SVD-разложение матрицы, т.к. мы не знаем саму матрицу. Но мы хотим воспользоваться этой идеей и придумать модель предсказания, которая будет работать сходным с SVD образом. Наша модель будет зависеть от многих параметров — векторов пользователей и фильмов. Для заданных параметров, чтобы предсказать оценку, мы возьмем вектор пользователя, вектор фильма и получим их скалярное произведение:


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


    Итак, мы хотим найти такие параметры θ, чтобы квадрат ошибки был как можно меньше. Но тут есть парадокс: мы хотим меньше ошибаться в будущем, но мы не знаем, какие оценки у нас будут спрашивать. Соответственно и оптимизировать это мы не можем. Но нам известны уже проставленные пользователями оценки. Попробуем подобрать параметры так, чтобы на тех оценках, которые у нас уже есть, ошибка была как можно меньше. Кроме того, добавим еще одно слагаемое — регуляризатор.


    Зачем нужен регуляризатор?


    Регуляризация нужна для борьбы с переобучением — явлением, когда построенная модель хорошо объясняет примеры из обучающей выборки, но достаточно плохо работает на примерах, не участвовавших в обучении. Вообще, методов борьбы с переобучением существует несколько, хочется отметить два из них. Во-первых, нужно выбирать простые модели. Чем проще модель, тем лучше она обобщается на будущие данные (это похоже на известный принцип бритвы Оккама). А второй метод — это как раз регуляризация. Когда мы настраиваем модель для обучающей выборки, мы оптимизируем ошибку. Регуляризация заключается том, что мы оптимизируем не просто ошибку, а ошибку плюс некоторая функция от параметров (например, норма вектора параметров). Это позволяет ограничить размер параметров в решении, уменьшает степень свободы модели.

    Численная оптимизация


    Как же нам найти оптимальные параметры? Нам нужно оптимизировать вот такой функционал:


    Параметров много: для каждого пользователя, для каждого объекта у нас есть свой вектор, который мы хотим оптимизировать. У нас есть функция, зависящая от большого количества переменных. Как найти ее минимум? Тут нам потребуется градиент — вектор из частных производных по каждому параметру.


    Градиент очень удобно представлять себе визуально. На иллюстрации у нас изображена поверхность: функция от двух переменных. Например, высота над уровнем моря. Тогда градиент в какой-нибудь конкретной точке — это такой вектор, направленный в ту сторону, куда больше всего растет наша функция. А если пустить воду из этой точки, она потечет по направлению противоположному градиенту.


    Самый известный метод оптимизации функций — градиентный спуск. Допустим у нас есть функция от многих переменных, мы хотим ее оптимизировать. Мы берем какое-нибудь изначальное значение, а потом смотрим, куда можно двигаться, чтобы минимизировать это значение. Метод градиентного спуска — это итеративный алгоритм: он многократно берет параметры определенной точки, смотрит на градиент и шагает против его направления:



    Проблемы этого метода заключаются в том, что он, во-первых, в нашем случае работает очень медленно и, во-вторых, находит локальные, а не глобальные минимумы. Вторая проблема для нас не так страшна, т.к. в нашем случае значение функционала в локальных минимумах оказывается близким к глобальному оптимуму.

    Alternating Least Squares


    Однако метод градиентного спуска применять нужно не всегда. Например, если нам нужно посчитать минимум для параболы, действовать этим методом необходимости нет, мы точно знаем, где находится ее минимум. Оказывается, что функционал, который мы пытаемся оптимизировать — сумма квадратов ошибок плюс сумма квадратов всех параметров — это тоже квадратичный функционал, он очень похож на параболу. Для каждого конкретного параметра, если мы зафиксируем все остальные, это будет как раз параболой. Т.е. минимум по одной координате мы можем точно определить. На этом соображении и основан метод Alternating Least Squares. Я не буду на нем подробно останавливаться. Скажу лишь, что в нем мы попеременно точно находим минимумы то по одним координатам, то по другим:


    Мы фиксируем все параметры объектов, оптимизируем точно параметры пользователей, дальше фиксируем параметры пользователей и оптимизируем параметры объектов. Действуем итеративно:


    Работает все это достаточно быстро, при этом каждый шаг можно распараллелить.

    Измерение качества рекомендаций


    Если мы хотим улучшить качество рекомендаций, нам нужно научиться его измерять. Для этого алгоритм, обученный на одной выборке — обучающей, проверяется на другой — тестовой. Netflix предложил измерять качество рекомендаций по метрике RMSE:


    Сегодня это стандартная метрика для предсказания оценки. Однако у нее есть свои недостатки:

    • У каждого пользователя свое представление о шкале оценок. Пользователи, у которых разброс оценок более широкий, будут больше влиять на значение метрики, чем другие.
    • Ошибка в предсказании высокой оценки имеет такой же вес, что и ошибка в предсказании низкой оценки. При этом предсказать оценку 9 вместо настоящей оценки 7 страшнее, чем предсказать 4 вместо 2 (по десятибалльной шкале).
    • Можно иметь почти идеальную метрику RMSE, но иметь очень плохое качество ранжирования, и наоборот.


    Метрики ранжирования


    Существуют и другие метрики — метрики ранжирования, например, основанные на полноте и точности. Пусть 𝑹 — множество рекомендованных объектов, 𝑷 — множество объектов, которые на самом деле пользователю понравятся.


    Тут тоже есть проблемы:

    • Нет данных про рекомендованные объекты, которые пользователь не оценивал.
    • Оптимизировать эти метрики напрямую почти невозможно.


    Другие свойства рекомендаций


    Оказывается, что на восприятие рекомендаций влияет не только качество ранжирования, но и некоторые другие характеристики. Среди них, например, разнообразие (не стоит выдавать пользователю фильмы только на одну тему или из одной серии), неожиданность (если рекомендовать очень популярные фильмы, то такие рекомендации будут слишком банальными и почти бесполезными), новизна (многим нравятся классические фильмы, но рекомендациями обычно пользуются, чтобы открыть для себя что-то новое) и многие другие.

    Похожие объекты


    Похожесть объектов не такая уж очевидная вещь. К этой задаче могут быть разные подходы:

    • Похожие объекты — это объекты, похожие по своим признакам (content-based).
    • Похожие объекты — это объекты, которые часто используют вместе («клиенты, купившие 𝑖, также покупали 𝑗»).
    • Похожие объекты — это рекомендации пользователю, которому понравился данный объект.
    • Похожие объекты — это просто рекомендации, в которых данный объект выступает в качестве контекста.


    Направления развития


    Концептуальные вопросы


    • Как строить списки рекомендаций на основе предсказаний? (Обычный топ — не всегда лучшая идея.)
    • Как улучшать качество именно рекомендаций, а не предсказаний?
    • Как измерять похожести объектов?
    • Как обосновывать рекомендации? (Оказывается, пользователи намного лучше воспринимают рекомендации, если снабжать их какими-то объяснениями.)


    Технические вопросы


    • Как решать проблему холодного старта для новых пользователей и новых объектов?
    • Как быстро обновлять рекомендации? (От этого может сильно зависеть польза введения рекомендаций в ваш сервис.)
    • Как быстро находить объекты с наибольшим предсказанием?
    • Как измерять качество онлайн-рекомендаций? (Традиционный подход с обучающей и тестовой выборками может работать не очень хорошо.)
    • Как масштабировать систему?


    Как учитывать дополнительную информацию?


    • Как учитывать не только явный (explicit), но и неявный (implicit) фидбек? (Неявного фидбека часто бывает на порядки больше.)
    • Как учитывать контекст? (Context-aware recommendations)
    • Как учитывать признаки объектов? (Гибридные системы)
    • Как учитывать связи между объектами? (таксономию)
    • Как учитывать признаки и связи пользователей?
    • Как учитывать информацию из других источников и предметных областей? (Cross-domain recommendations)


    Литература


    • Введение в алгебру, Кострикин А. И.
    • Математический анализ, Зорич В. А.
    • Машинное обучение, Воронцов К. В., курс лекций

    Яндекс

    480,00

    Как мы делаем Яндекс

    Поделиться публикацией
    Комментарии 42
      0
      Статью в ворде готовили?
      Некоторые символы отображаются квадратиками
      Красивые квадратики разных размеров
        0
        У меня все ок. У вас другой юникод? :)
          +1
          Видимо, да. Виноват. Мобильный браузер показывает не все символы юникода. Пойду посыпать голову пеплом.
          +1
          Аналогично, некоторые символы в виде квадратов. Браузер Google Chrome 38, на ноутбуке, кодировка UTF-8 (автоматически).
          Квадратные символы
            0
            Десктопный Safari показывает всё, у мобильного проблемы с некоторыми символами.
              0
              Хром Версия 38.0.2125.111 m на ноуте
              то же самое (квадраты).
              Дайте знать, когда поправите — тогда и почитаю…
              +3
              Тоже самое. UTF-8. Яндекс Браузер :)
                0
                От шрифтов же зависит.
                  +2
                  Ну да, «для прочтения этой статьи извольте сменить браузер и установить набор шрифтов».

                  При том, что для куда менее разумных целей все и каждый нынче грузят веб-фонты, и все отлично работает (хотя и тупо долго не отображается при загрузке).
              0
              SVD — аббревиатура от Singular Value Decomposition, a не Single Value Decomposition. Поправьте, пожалуйста.
                0
                Спасибо!
                +1
                Победителю был обещан приз в $ 1 000 000. Соревнование длилось примерно три года. За первый год качество улучшили на 7%, дальше все немного замедлилось. Но в конце две команды с разницей в 20 минут прислали свои решения, каждое из которых проходило порог в 10%, качество у них было одинаковое с точностью до четвертого знака.
                Какова вероятность, что два года две команды готовили практически два одинаковых решения и выложили его с интервалом в два десятка минут??? Кто помог одной команде срерайтить код другой команды? Чьи команды были???
                  0
                  почайте историю этого соревнования. комманды не ждали два года а потом раааз и выложили, они выкладывали свои алгоритмы регулярно в течении 2х лет, каждый раз улучшая их. В последние дни комманды работали в режиме 24 часа в сутки. Разница в 20 минут, это разница между их последними «коммитами».
                    0
                    Нужно понимать, что обе команды приблизились к условной «асимптоте» качества рекомендаций. Так что нет ничего удивительного в том, качество у них так сильно совпадало, даже если использовались разные алгоритмы.
                    0
                    Вопрос — как конкретно вычисляется норма в функционале J? Дело в том, что модульная функция не дифференцируема в точке экстремума, а, следовательно, применять градиентный метод для неё нельзя. Выход из ситуации — использовать численные методы нулевого порядка. Это как раз то, что описано в пункте «Alternating Least Squares». В нашей литературе этот метод называется методом покоординатного спуска. Но даже если функция дифференцируема, применять градиентный метод нужно с осторожностью, ведь для сходимости градиентного метода нужно, чтобы градиент целевой функции удовлетворял условию Липшица (см., например, книгу Бориса Теодоровича Поляка «Введение в оптимизацию», стр. 31).
                      0
                      Норма там вторая, так что всё нормально.

                      В ALS совсем не то, используется тот факт, что при зафиксированной матрице P или Q имеется аналитическое решение.
                      0
                      В случае выпуклой целевой функции экстремум единственен и оба метода (при выполнении условий сходимости) будут сходиться к нему, локальных экстремумов нет.
                        0
                        Опять же обычно методы первого порядка сходятся к экстремуму быстрее, чем методы нулевого порядка. В Вашем случае Вы почему-то отказываетесь от этого (если не выполняются условия сходимости, то отказ обоснован).
                          0
                          Или трудно вычислить частные производные — повод отказаться от градиентного метода.
                            0
                            Вообще, в подобных задачах обычно полноценный градиентный спуск слишком (вычислительно) сложен, ибо размер обучающего множества может быть очень велик, вычислять такое на каждой итерации дорого. На практике используется только стохастический градиентный спуск, у которого из-за стохастичности имеются шумы, так что сходится он ещё дольше, а на шаг нужно налагать условия Роббинса-Монро.
                          +3
                          Все хорошо в рекомендациях, но, вот, для примера:

                          Зашел я на Яндекс-Музыку. Слушаю то, что мне близко, но тут увидел обложку альбома незнакомого исполнителя. Обложка понравилась, имя певца прозвучано нормально — я щелкнул по альбому. Послушал, и решил, что «нет, я такое не хочу».

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

                          И кто кому что навязывает и что первично — моя любовь к какому-то типу музыки, или неверное, в общем, предположение системы, что мне нравится нечто вовсе другое? Причем предположение это подтолкнуто самой же системой.

                          Как вариант, могу предложить ситуацию: если у рок-группы есть одна-две милых гитарных романтичных баллад (отличающихся от их обычного стиля), и я их прослушаю в рамках сборника «романтические мелодии к дню Валентина», то меня, как, в рокеры запишут, в романтики, в любителей сборников — и что я в сумме буду получать в рекомендациях?

                          Как вывод — ОЧЕНЬ хочется иметь кнопку «я НЕ люблю этого, не советовать мне», и «я уже купил этот тип товара, хватит доставать!» А то стоит день поискать в каталоге холодильник, как тебе его Контекст будет сватать еще два месяца :(
                            0
                            Ни разу ещё ни одна система рекомендаций не показала мне чего либо стоящего.
                              0
                              Потому что ее разума хватает на логику контекстной рекламы — «купили холодильник — вот вам инфа про холодильник», т.е. работаем по тому, что вроде знаем, но не учитываем текущего состояния юзера.

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

                              Главное, что отладка системы рекомендации — штука странная: юзер даже на лажовую рекомендовалку может пару раз щелкнуть мышкой, чтобы просто посмеяться, а разработчики рекомендовалки будут радоваться и пищать «смотри-ка, нашей системой пользуются!»

                              Один выход — следить за каждым, вести на него постоянное досье, и из этого уже…
                            +2
                            Кстати, вот она, авторекомендация во всей красе:

                            image

                            «Машина времени» и «Машина Времени» — рекомендации друг к другу. Отличный пример, когда за математикой и механической работой алгоритма теряется суть идеи советовать похожее.

                            Не говоря уже, что во фразе
                            Если вы купили что-то на амазоне, за вами будут охотиться с дополнительными предложениями: похожими товарами или аксессуарами

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

                              В общем, это обычный баг, по какой-то причине Last.FM не смог / не захотел использовать уже существующего исполнителя, что ввело рекомендательный алгоритм в замешательство. Общему подходу от этого ни жарко, ни холодно — с таким же успехом можно было где-нибудь в алгоритме заменить умножение на сложение, только баг был бы виден лучше.
                              Не стоит ожидать от математических алгоритмов совершенства, они всегда основаны на некоторых предположениях (далеко не всегда адекватных реальному миру).
                                0
                                Все бы хорошо, этот лозунг «сначала нормализуем, зато потом оно полетит» все как-то часто не выдерживает столкновения с реальностью.

                                С теми же песнями: берем Синатру, берем его My Way, загоняем в базу — красотааа! А теперь берем все его пластинки, и, ба, на каждой пятой эта песня есть. Это одна и та же песня (та же запись), или чем-то отличаются? Наверное, отличаются, хотя бы часть из них. Но названия одни и те же. Как нам их хранить, в виде одного файла (какой тогда вариант берем), или в каждом «альбоме» храним отдельную копию и зовем ее «my way — версия из альбома такого-то»?

                                Дальше — больше. На каких-нибудь «Зайцев-нет» имеем для каждого исполнителя единицы, а то и десятки дублей песен, вида «синатра — мой путь», «синатра — my way» и даже «синатра — супер песня!»

                                Я к тому, что нормализовать жизнь — это не только задача сравнения названий. Нет одинаковых листьев на одном дереве (по сути — объекты «лист» (почти) всегда уникальны), и нет одинаковых песен (объекты «песня такая-то» тоже (почти) уникальны). На эту тему рекомендовалка должна скуксится, только если ей не загрубить порог восприятия — «человек слушает Синатру — рекомендуем вам также послушать Круга и группу Лесоповал» (потому что у кого-то Синатра и Круг оказались в одном треклисте).
                                  +2
                                  Во-первых, я не говорил, что для нормализации достаточно названия сверить. Посыл мой был в том, что нормализация есть отдельная задача, ортогональная рекомендации.
                                  Можно, например, анализировать аудиопток, отсеивая таким образом дубликаты. Или как-то иначе, суть от этого не изменится: это отдельная задача со своими методами.

                                  К чему здесь Зайцы — непонятно. Надо было бы им строить рекомендации или делать другую аналитику — привели бы свою свалку в порядок. Тут, вроде, не plug-and-play решение предлагается.

                                  Касательно Вашего примера:
                                  Я считаю, что задачей рекомендательных систем является преподнесение чего-то нового, о чём пользователь раньше не знал. Другой вариант трека, конечно, может быть интересен, но в меньшей степени, чем совершенно новый неизвестный ранее трек (возможно, нового исполнителя, у которого есть ещё много «вкусного»).
                                  Опять же, если человек знает исполнителя, что мешает ему пойти и послушать всю его дискографию? На мой взгляд, в рекомендации уже известного исполнителя смысла мало (тут я лукавлю, и это зависит от того, как мы собираемся использовать систему. В случае радио, например, мы хотим составлять плейлист автоматически, не требуя от пользователя даже присутствия. Но в таком случае нет никакой разницы, поставим мы Машину времени или Машину Времени).

                                  Ну а вообще, в случае несколькиз различных треков можно сделать по-разному:
                                  1. Если мы уверены в качестве контента, а различия невелики, то можно все дубли считать за один трек, а проигрывать случайный.
                                  2. Если различия велики (акустическая версия, например), то есть смысл создать отдельную запись под такой трек, отразив это в названии.

                                  Более того, можно усложнить модель, введя таксономию на разных версия одной песни, так что рекомендовать мы их всё-таки будем, но с меньшим «весом».
                                    0
                                    Вы знаете, я про рекомендации думаю именно в ключе «покажи мне новое, такое, чтобы было интересно». Это не всегда легко: скажем, приятель мне может сказать, глядя на мое состояние, на текущую манеру общения, зная о моих проблемах и радостях, что мне, может, стоило бы послушать не Машину, а, скажем, группу противоположного стиля — а машина этого всего не знает (да и вообще не «знает», а механически реагирует, скорее всего)

                                    Может, конечно, глобальная следилка за человеком и сможет так точно предсказать, что у него на душе сейчас творится, но это уже какая-то рекомендовался «а'ля Эшелон» получится )

                                    P.S. Кейс с плейлистом на радио — да, это идея, но такую станцию будет грустно слушать, она сама себя будет накручивать, не находите?
                                      0
                                      Вы гонитесь за точностью во всех случаях, что близко к сильному ИИ. Более того, далеко не каждый Ваш друг, я уверен, сможет так точно порекомендовать что-нибудь (даже зная ваши предпочтения), я уверен.

                                      Эффективность математических моделей и машинного обучения в частности, как мне кажется, связана с тем, что многие вещь в мире хоть и сложны и, кажется, почти случайны, всё же имеют некоторую структуру под собой. Как бы изменичивы Ваши предпочтения ни были, это всё же не белый шум. Опять же, машины учатся хорошо работать в среднем, а не во всех случаях. Если раз в году на полнолуние после дождичка в четверг Вы слушаете Бразильские народные песни, а всё остальное время исключительно классику, то алгоритм вряд ли научится советовать Вам бразильскую музыку по тем самым дням. Хотя бы потому что такой сценарий неотличим от случая, когда к Вам приехали в гости родственники и какая-нибудь 12-летняя племянница захотела послушать Ранеток, которых Вы, в рассматриваемой ситуации, слушать не хотите.

                                      Рассматриваемый Вами случай специфичен тем, что он не располагает никаких фидбеком от Вас в момент рекомендации. Ваш друг тоже ничего Вам не посоветует, если Вы будете сидеть с закрытым ртом и ничего ему про своё текущее состояние не скажете. Если же соответстующий фидбек у системы есть (Вы, например, решили что-то послушать, а машина на той же страничке предложила Вам что-то ещё), то у системы есть шанс на успех ибо
                                      1. Ваши предпочтения не белый шум
                                      2. Вы не единственный пользователь системы

                                      Кого будет накручивать радио я не понял. Я ведь ни слова не сказал о том, какую модель, как и на каких данных мы собрались обучать. Более того, я нигде не говорил про то, что рекомендации должны быть детерминированы.
                                        0
                                        Так вот я и переживаю (по опыту), что, случись мне слушать классику (которая внутри еще делится на много вариантов) весь год, потом несколько раз слушаю что-то другое, а машина складывает все это и осредняет, давай мне что-то не точное и откровенно левое.

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

                                        Второй вопрос, что с утра (скажем) мне хорошо пойдет ритмы нанайского севера, в обед — классика, вечером — бразильское танго. И это по рабочим дням, а по выходным что-то еще. Машина с ума сойдет, и будет всегда неправа, пока не поймет, что нужно привязываться к а) времени суток б) времени года, в) жизни вокруг (обобщая). Если спросить меня, как да что, я скажу в ответ, что лучше я личные треклисты сам набью и себе сохраню для ручного переключения.

                                        Еще есть момент, что, скажем, певец может часть всего своего творчества (а то и просто альбома) петь в одном стиле и с одном настроением, а потом как-то измениться. Т.е. с точностью до исполнителя не насоветуешься. Остается, как я и наблюдаю, «бить по площадям», в надежде, что хоть кому-то рекомендация покажется более-менее нормальной.

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

                                        А ИИ — это вы правы, от компа ждать чего-то реально стоящего трудно. Тут не просто ИИ нужен, но и упомянутая мною слежка за его поведением.

                                        Хм… Мир вещей мог бы продаванам такую инфу сливать! :)
                                          0
                                          С чего Вы решили, что машина просто усредняет? Более того, даже в случае банального усреднения результат был бы больше похож на классику ибо частота её прослушивания больше, чем частота всего остального.

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

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

                                          Ваша аналогия с почтовым спамом очень странная. Спам приходит сам по себе, а от использования сервиса можно отказаться.
                                            +1
                                            Слежу за вашими вопросами и восхищаюсь — вы уже задали кучу правильных вопросов, которые приводят к целым большим направлениям в исследованиях рекомендательных систем.

                                            Например, ваш вопрос выше насчёт «покажи мне новое» приводит к тому, что иногда нам нужно не просто выдать топ-рекомендации, оптимизируя, грубо говоря, суммарный ожидаемый рейтинг, а оптимизировать ещё и что-нибудь другое. Для этого вводят различные метрики разнообразия (diversity, novelty, serendipity и т.д.) [Vargas, 2011; Castells et al., 2011].

                                            А ваш вопрос насчёт «с утра или вечером» приводит к рекомендательным системам, учитывающим контекст (context-aware recommender systems, CARS) [Adomavicius, Tuzhilin, 2010].

                                            Задавайте больше вопросов. :)
                                +1
                                Мне кажется, статья была быинтересна более широкому кругу читателей, если бы к формулам прилагалась расшифровка обозначений.
                                Спасибо.
                                  0
                                  А какие именно обозначения имеются в виду? Я старался вводить все обозначения, кроме стандартных математических.
                                    0
                                    На самом деле, вопросы «Что такое рекомендательные системы» и «как соптимизировать некий частный случай некоторой сложной высшей матричной алгеброй» надо бы очень сильно разводить по разным статьям. Иначе не очень съедобно получается.
                                      0
                                      А что должно быть в статье про рекомендательные системы? «Оптимизация некоего частного случая» является примером конкретного алгоритмы для решения конкретной задачи. Обилие математики обусловлено сложностью задачи.

                                      На мой взгляд статья «Что такое рекомендательные системы» будет исключительно философско-болтологической, а для таких статей теперь существует GeekTimes. Эта же статья вполне подходит тематике Хабра.

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

                                      Как писали ТМ в статье о разделении
                                      «Хабрахабр» исключительно [...] профессиональный, хардкорный ресурс, где айтишники делятся опытом друг с другом и улучшают свои профессиональные навыки.
                                        –1
                                        Так не надо тогда начинать с поверхностного обзора. Кратко дать в обзорной врезке у второго абзаца вот эту ссылку, дополнить комментом про то, о чем там наврали или недоговорили, а всю статью целиком посвятить именно своей узкой математике, объявив тему узкоматематичной в первом же абзаце. Это ж статья на профильном ресурсе, тут есть куда сослаться, как вы правильно заметили.

                                        Хотя и на лекции — тоже, смесь обзорки с дебрями частного случая — форменное безобразие. Кому нужен частный случай, обзорка не нужна, и наоборот. Сначала скучают одни, потом недоумевают другие. Нельзя так смешивать аудитории.
                                  +2
                                  Жизнь хабра тоже развивается по спирали. :) Когда-то я писал вводный цикл о рекомендательных системах с примерно тем же по сути содержанием.

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

                                  И совсем уж на правах рекламы — в других статьях того же блога Surfingbird я писал о вероятностных графических моделях, примерно так же «на пальцах»:
                                    0
                                    Сергей, спасибо. Ваши статьи я тоже читал.
                                    Кстати, если будете в Моккве и будет желание — заходите к нам в Яндекс, расскажите что-нибудь про свой опыт.
                                      0
                                      Михаил, спасибо за приглашение! Вряд ли я смогу о рекомендательных системах что-то радикально новое рассказать Яндексу, но вообще пообщаться и установить связи было бы хорошо. Я часто бываю в Москве, пару раз в месяц уж точно, так что, думаю, всё должно получиться.
                                    0
                                    Считаю, что неправильно брать среднюю оценку пользователя как некоторую его границу между «хороший» и «плохой» (особенно в случае с фильмами). Дело в том, что в большинстве случаев люди смотрят фильмы, которые им нравятся, потому что перед просмотром можно выбрать фильм, который с большой вероятностью понравится (по чужим оценкам, жанру, описанию и т.д.). Соответственно, средняя оценка находится выше границы хороший-плохой.

                                    Например, человек ставит большинству фильмам оценки от 7 до 9, и двум-трём оценку 2. Для него средняя оценка будет примерно 8, и те фильмы, которым он поставил 7, будут рассматриваться алгоритмом как фильмы, которые ему не понравились (хотя на самом деле они ему понравились).
                                      0
                                      Так используйте перцентиль.

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

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