Pixie, система рекомендаций в реальном времени в Pinterest [Paper Summary]

Бумага :

Pixie: система для рекомендации 3+ миллиардов товаров 200+ миллионам пользователей в режиме реального времени

Цель: создать масштабируемую систему рекомендаций в реальном времени под названием Pixie в Pinterest.

О компании Pixie:

  • Разработан на C ++ через SNAP (Стэнфордская платформа сетевого анализа)
  • Характеристики графика: 3 миллиарда узлов (контактов и плат), 17 миллиардов ребер в основной памяти объемом 120 ГБ
  • Структура: содержит вручную подобранный неориентированный двудольный граф из 7 миллиардов выводов и плат и более 100 миллиардов ребер.
  • Метрики: поддерживает 1200 запросов в секунду на машину, задержка, p99: 60 мс.
  • Общее количество запросов в секунду кластера: 100000
  • Технические характеристики машины: AWS R2.8xlarge, 244 ГБ оперативной памяти
  • Ввод: пользовательские функции; Результат: персонализированные рекомендации на основе PixieRandomWalk.

Плюсы системы рекомендаций в реальном времени:

  • Отзывчивость на изменение намерений и поведения пользователей
  • Обновление рекомендаций для неактивных пользователей занимает много времени, дисков и энергии.

Предыдущая работа над рекомендациями:

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

- Случайные блуждания: есть обходной путь, например. Персонализированный алгоритм SALSA. Pixie предлагает новый подход к случайному блужданию.

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

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

Основная идея:

  • Создается набор запросов (Q), включающий контакты, с которыми недавно взаимодействовали, а также контакты, с которыми пользователь взаимодействовал давным-давно, с весами.
  • Затем выполняется случайное блуждание на двудольном графе булавок и досок. Выполняется N шагов, при этом каждая длина шага выбирается из статического распределения, полученного из функции, параметризованной альфа. Длина ходьбы варьируется в зависимости от требований, например. узкие рекомендации требуют более коротких прогулок, а более исследовательские могут иметь более длительные.
  • Большой объем оперативной памяти гарантирует, что случайные блуждания не будут пересекаться между машинами. Прогулки параллельны
  • На графе G выполняется множество коротких случайных блужданий, начиная с вывода запроса p. Это делается для всех выводов запроса в наборе запросов Q.
  • Важным моментом здесь было то, что общее количество необходимых шагов зависит от степени вывода запроса q. Чем выше степень q, тем больше шагов необходимо для выработки рекомендаций.
  • Регистрируется количество посещений для каждого пина. Общее количество шагов здесь означает сложность. Пины, которые посещались чаще всего, возвращаются в качестве рекомендаций.
  • Основное внимание уделяется масштабируемой рекомендательной системе в реальном времени с максимально интересным контентом.
  • Алго работает в постоянное время, независимо от размера графа
  • Пикси Случайное блуждание зависит от конкретного пользователя. Здесь они делают это только на основе темы или предпочтительного языка. Это смещение можно сделать, установив больше весов для ребер между узлами с похожими функциями (например, тема / язык здесь). Это улучшает персонализацию и качество.
  • Захватывает весь контекст прошлого поведения пользователя, используя несколько булавок с весом в виде Q, чтобы рекомендовать элементы.
  • Объединяет несколько рекомендаций из разных случайных блужданий, начиная с разных контактов в Q, чтобы предоставить множество соответствующих рекомендаций. Здесь пикси использует усилитель с несколькими ударами, который усиливает пины, связанные с несколькими пинами запроса в наборе запросов Q. Это достигается путем обновления счетчика посещений с учетом того, что популярные пины имеют больше посещений, и это нужно дисконтировать, чтобы показать множество булавок.

Пусть, Sq = степень q * (максимальная степень выступов на графике - журнал (степень q))
Общее количество шагов для обходов, начиная с точки q (Nq) = Wq * N * (Sq / S для всех контактов в Q)

Посетите обновление счетчика (V) для вывода p:

V [p] = (Для всех q в Q, root (Vq [p])) ²

  • Использует специальные критерии сравнения для преждевременного останова, обеспечивая производительность и пропускную способность в реальном времени. Критерии, используемые в пикси, заключаются в продолжении случайных блужданий до тех пор, пока не будут пройдены N шагов, или остановка, когда есть хотя бы Np узлов с Nv посещениями, что считается достаточным, чтобы показывать эти узлы как рекомендации с высокой степенью уверенности.
  • Pixie algo рекомендует как пины, так и доски.
  • Обрезка графа: удаление досок, не имеющих особой тематики.
    Это приводит к уменьшению размера диаграммы, которая может уместиться на более дешевых машинах.
    Это также повышает качество рекомендаций, а также производительность, поскольку различные платы рассеивают прогулки в слишком многих направлениях, что снижает производительность.
    - ›Вычислить энтропию распределения тем в досках. Вероятностные тематические векторы, полученные с помощью LDA на описаниях выводов
    - ›Платы с высокой энтропией удаляются из графа вместе с их ребрами.
  • Размер набора запросов Q и общее количество шагов меняют время выполнения Pixie.
  • Дисперсия лучших результатов K была проверена для разного количества шагов. Дополнительный прирост стабильности, полученный за счет увеличения количества шагов, уменьшается примерно после 200 000 шагов.
  • Смещение приводит к лучшей производительности.
  • Оценка значений np и nv: np = 2 000 и nv = 4, привела к хорошему сходству с набором результатов золотого стандарта (84%), улучшив время выполнения в три раза.
  • Задача состоит в том, чтобы предсказать набор выводов, которые будут сохранены на плате после отметки времени t. Для данной платы последние добавленные контакты принимаются как набор запросов Q. Контакты, которые будут сохранены на плате после отметки времени t, рассматриваются как X, а рекомендованные контакты после PixieRandomWalk с входом Q принимаются как R. для них вычисляется и берется оценка F1. Оценка F1 продолжает меняться, поскольку они продолжают сокращать график.
  • Когда δ (степень отсечения) уменьшается, граф становится все более и более обрезанным. «При δ = 0,91 оценка F1 достигает пика на 58% выше необрезанного графа F1, и граф содержит только 20% от исходного количества ребер. Это означает, что сокращение графика фактически улучшает качество рекомендаций на 58%, а также сокращает график только до шестой части его размера ».

Примеры использования в Pinterest:

  • Домашнее питание
  • Рекомендуемые контакты
  • Связанные платы