Real-time Machine Learning For Recommendations
Юджин Ян разбирает, как машинное обучение в реальном времени применяется в рекомендательных системах, отталкиваясь от наблюдения Chip Huyen о том, что китайские компании в MLOps опережают американские. Большинству задач достаточно пакетных (batch) рекомендаций — они дешевле и проще в эксплуатации, тогда как рекомендации в реальном времени оправданы, когда поведение клиента контекстно и миссия-ориентировано (шопинг, выбор фильма, реклама, холодный старт новых пользователей). Автор объясняет основы (коллаборативные vs контентные рекомендации, i2i vs u2i, генерация кандидатов и ранжирование) и показывает, как CF и алгоритм Swing от Alibaba позволяют инкрементально обновлять рекомендации; приводятся архитектуры Alibaba 1688, Tencent, YouTube, Instagram и Netflix. У Tencent A/B-тесты дали прирост CTR на 6–8% для новостей и 6–18% для e-commerce. В финале описывается дешёвый MVP: эмбеддинги через word2vec (skip-gram), генерация кандидатов через ANN (ScaNN), ранжирование логистической регрессией с cross-фичами и развёртывание на AWS SageMaker — 30 инстансов m5.xlarge выдают 1200 запросов в секунду с медианной задержкой 25 мс при стоимости около 5,5 тыс. в месяц.
Real-time Machine Learning For Recommendations
Машинное обучение в реальном времени для рекомендаций
[ teardown machinelearning recsys production 🔥 ] · 21 мин чтения
A few weeks ago, Chip compared the state of real-time machine learning in China and US: While many Chinese companies have adopted real-time ML, US companies are still assessing its value. She also wrote about ML going real-time here.
Несколько недель назад Chip сравнила состояние машинного обучения в реальном времени в Китае и США: пока многие китайские компании уже внедрили real-time ML, американские компании всё ещё оценивают его ценность. Она также писала о переходе ML в реальное время здесь.
Talking to Internet companies in China gives me the impression that their MLOps infra is away ahead.
Many US Internet co. are still wondering if there's value in real-time ML. Chinese counterparts are already doing real-time inference + online training.
Are my samples biased?
Общение с интернет-компаниями в Китае оставляет впечатление, что их MLOps-инфраструктура заметно опережает. Многие интернет-компании в США всё ещё гадают, есть ли ценность в real-time ML. Их китайские коллеги уже делают инференс в реальном времени + онлайн-обучение. Не предвзята ли моя выборка? — Chip Huyen (@chipro) 10 декабря 2020
This post continues the thread and shares how real-time ML looks in practice. Drawing from my experience and industry papers/blogs, we’ll discuss real-time recommendations.
Этот пост продолжает тему и рассказывает, как real-time ML выглядит на практике. Опираясь на мой опыт и отраслевые статьи/блоги, мы обсудим рекомендации в реальном времени.
Когда рекомендации в реальном времени имеют смысл? А когда нет? Как китайские и американские компании реализовали рекомендатели реального времени? Как спроектировать и реализовать простой MVP?
Note: This discussion assumes basic knowledge of recommendation systems, such as the difference between item-to-item and user-to-item, and the candidate generation & ranking paradigm. Fret not if those terms are unfamiliar. We’ll have two primers to help you get up to speed. Click on the 👉 below to start with the first.
Примечание: это обсуждение предполагает базовое знание рекомендательных систем, например различие между item-to-item и user-to-item, а также парадигму генерации кандидатов и ранжирования. Не переживайте, если эти термины незнакомы. У нас будет два вводных раздела, которые помогут вам войти в курс дела. Нажмите на 👉 ниже, чтобы начать с первого.
If you understand the difference between collaboration vs. content-based recommendations, and item-to-item vs. user-to-item, feel free to skip this section.
Если вы понимаете разницу между коллаборативными и контентными рекомендациями, а также между item-to-item и user-to-item, можете смело пропустить этот раздел.
Collaboration-based recommendations are based on user behavior. Assume I like movie X and dislike movie Y. To recommend movies to me, we first find users similar to me (i.e., like X, dislike Y). Then, from those users, what are movies they liked, but I’ve not watched? Those movies are then recommended to me. With user behavioral data, users can “collaborate” to create recommendations for each other. Collaborative filtering is probably the most well-known approach.
Коллаборативные рекомендации основаны на поведении пользователей. Предположим, мне нравится фильм X и не нравится фильм Y. Чтобы порекомендовать мне фильмы, мы сначала находим пользователей, похожих на меня (то есть тех, кому нравится X и не нравится Y). Затем смотрим: какие фильмы понравились им, но я их ещё не смотрел? Эти фильмы и рекомендуются мне. С помощью данных о поведении пользователи могут «сотрудничать», создавая рекомендации друг для друга. Коллаборативная фильтрация — пожалуй, самый известный подход.
Content-based recommendations are based on item metadata. Given the movies I’ve watched (and enjoyed), content-based recommenders suggest movies of similar genre, time period, director, etc. Relative to collaboration-based recommenders, content-based recommenders tend to be more effective when the movie is new and we don’t have enough user behavioral data about it yet (i.e., cold-start problem)
Контентные рекомендации основаны на метаданных объектов. Исходя из фильмов, которые я смотрел (и которые мне понравились), контентные рекомендатели предлагают фильмы похожего жанра, периода, режиссёра и т. д. По сравнению с коллаборативными рекомендателями, контентные обычно эффективнее, когда фильм новый и у нас ещё недостаточно данных о поведении пользователей по нему (то есть проблема холодного старта, cold-start).
In item-to-item (i2i) recommendations, given an item, we recommend other items. Here’s an example of i2i recommendations on IMDB, under the “More Like This” widget. This works well in scenarios where the focus is the item (e.g., item detail page).
В item-to-item (i2i) рекомендациях по заданному объекту мы рекомендуем другие объекты. Вот пример i2i-рекомендаций на IMDB — в виджете «More Like This». Это хорошо работает в сценариях, где в центре внимания сам объект (например, страница с детальной информацией о товаре).
More like Independence Day on IMDB
Похожие на «День независимости» на IMDB
In user-to-item (u2i), given a user, we recommend items. We see this on the home page of Netflix, Amazon, Taobao, sometimes with the name of “Recommended For You”. Our social media feeds (e.g., Twitter, LinkedIn, Facebook) are u2i recommendations too. In such scenarios, the user (and their historical preferences) is the focus.
В user-to-item (u2i) по заданному пользователю мы рекомендуем объекты. Мы видим это на главной странице Netflix, Amazon, Taobao — иногда под названием «Recommended For You». Наши ленты в соцсетях (например, Twitter, LinkedIn, Facebook) — это тоже u2i-рекомендации. В таких сценариях в центре внимания находится пользователь (и его историчные предпочтения).
Recommended For You on Amazon
«Recommended For You» на Amazon
Taken together, i2i and u2i recommendations provide coverage for the bulk of user traffic via detail pages and home pages.
Вместе i2i- и u2i-рекомендации обеспечивают покрытие основной массы пользовательского трафика — через детальные страницы и главные страницы.
When (not) to use real-time recommendations?
Когда (не) стоит использовать рекомендации в реальном времени?
Before we get too excited, let me first say that most use cases won’t need real-time recommendations; batch recommendations are good enough.
Прежде чем мы слишком воодушевимся, сразу скажу, что большинству сценариев рекомендации в реальном времени не нужны; пакетных (batch) рекомендаций вполне достаточно.
Relative to real-time recommendations, batch recommendations are computationally cheaper. They are usually generated once a day and benefit from batch processing’s economies of scale. The recommendations are then loaded into a key-value store (e.g., Redis, DynamoDB) and served via a key-value lookup.
По сравнению с рекомендациями в реальном времени, пакетные рекомендации вычислительно дешевле. Обычно их генерируют раз в день, и они выигрывают от эффекта масштаба пакетной обработки. Затем рекомендации загружаются в key-value-хранилище (например, Redis, DynamoDB) и отдаются по ключу.
Batch recommendations are also simpler ops-wise. By caching pre-computed recommendations (in our key-value store), we decouple computation from serving. Thus, even if the compute step fails, there’s no customer-facing impact; we continue to serve the previous batch of (slightly stale) recommendations. The cache provides a buffer and ensures almost 100% uptime, reducing ops burden on the team (e.g., on-call, complaints).
Пакетные рекомендации также проще с точки зрения эксплуатации. Кэшируя предвычисленные рекомендации (в нашем key-value-хранилище), мы отделяем вычисление от отдачи. Поэтому даже если этап вычислений упадёт, на клиента это никак не повлияет; мы продолжаем отдавать предыдущую партию (слегка устаревших) рекомендаций. Кэш служит буфером и обеспечивает почти 100% доступность, снижая эксплуатационную нагрузку на команду (например, дежурства, жалобы).
Batch vs. streaming in the case of analytics (source)
Batch против стриминга на примере аналитики (источник)
In contrast, real-time recommendations usually require more computation. For example, we might aggregate streamed events (e.g., click, like, purchase) and generate new recommendations on-demand, based on user interactions. (In comparison, batch recommendations only compute a single set daily.) Furthermore, such computation is done individually and does not benefit from economies of scale. (Nonetheless, we save on not generating recommendations for customers who don’t visit our app).
Напротив, рекомендации в реальном времени обычно требуют больше вычислений. Например, мы можем агрегировать потоковые события (например, клик, лайк, покупку) и генерировать новые рекомендации по запросу, на основе действий пользователя. (Для сравнения: пакетные рекомендации вычисляют лишь один набор раз в день.) Более того, такие вычисления выполняются индивидуально и не выигрывают от эффекта масштаба. (Тем не менее мы экономим, не генерируя рекомендации для клиентов, которые не заходят в наше приложение.)
Operating real-time recommendations in production is also far tricker. Instead of using ephemeral Spark clusters (for compute) and a DynamoDB (for serving), we’ll need low-latency high-throughput APIs with 24/7 uptime. In the strictest scenario, we won’t have our key-value store as a buffer. The line between compute and serving disappears. Ops burden will increase (read: we’ll be paged in the middle of the night for an outage in another timezone 🚨).
Эксплуатировать рекомендации в реальном времени в продакшене также гораздо сложнее. Вместо эфемерных Spark-кластеров (для вычислений) и DynamoDB (для отдачи) нам понадобятся низколатентные высокопроизводительные API с доступностью 24/7. В самом строгом сценарии у нас не будет key-value-хранилища как буфера. Граница между вычислением и отдачей исчезает. Эксплуатационная нагрузка вырастет (читай: нас разбудят посреди ночи из-за сбоя в другом часовом поясе 🚨).
Why real-time recommendations then? They’re useful when the customer journey is mission-centric and depends on the context. Such missions are often time-sensitive. Real-time demand fades quickly; demand could be met (on a competitor site) or the user might lose interest. We’ll examine this in two examples: shopping and watching a movie.
Зачем тогда рекомендации в реальном времени? Они полезны, когда путь клиента миссия-ориентирован и зависит от контекста. Такие «миссии» часто чувствительны ко времени. Спрос в реальном времени быстро угасает; потребность может быть удовлетворена (на сайте конкурента), либо пользователь потеряет интерес. Мы рассмотрим это на двух примерах: шопинг и просмотр фильма.
Shopping is a mission-centric activity. Though a customer might predominately purchase a category of products, their shopping behavior is often punctuated with tangential missions. For example, if I usually shop for clothes, my u2i recommendations will mostly be fashion recommendations. However, if I need a new wide-screen monitor and start browsing for one, my u2i recommendations should update ASAP to help me quickly fulfill my mission (lest I go to a competing app).
Шопинг — это миссия-ориентированная активность. Хотя клиент может преимущественно покупать одну категорию товаров, его покупательское поведение часто перемежается побочными «миссиями». Например, если я обычно покупаю одежду, мои u2i-рекомендации в основном будут модными. Однако если мне понадобился новый широкоэкранный монитор и я начинаю его искать, мои u2i-рекомендации должны обновиться как можно скорее, чтобы помочь мне быстро выполнить мою миссию (иначе я уйду в конкурирующее приложение).
In this scenario, batch recommendations don’t react fast enough. And even when the recommendations are updated, due to the data imbalance, such mission-related needs are not met (More in Section 2.1 of this Netflix paper).
В этом сценарии пакетные рекомендации реагируют недостаточно быстро. И даже когда рекомендации обновляются, из-за дисбаланса данных такие связанные с миссией потребности не удовлетворяются (подробнее в разделе 2.1 этой статьи Netflix).
The movies we watch depend on context (though our long-term preferences are fairly stable). For example, we might watch different movies depending on whether we’re alone, with friends, with a romantic interest, or with children. It might also depend on our mood, as well as the time of day. Similar to shopping, daily batch recommendations face the same challenges here.
Фильмы, которые мы смотрим, зависят от контекста (хотя наши долгосрочные предпочтения довольно стабильны). Например, мы можем смотреть разные фильмы в зависимости от того, одни ли мы, с друзьями, с романтическим партнёром или с детьми. Это также может зависеть от настроения и времени суток. Как и в случае с шопингом, ежедневные пакетные рекомендации сталкиваются здесь с теми же трудностями.
Other than the examples above, real-time recommendations are also handy in:
Помимо приведённых выше примеров, рекомендации в реальном времени также удобны в:
Путешествия (наши места отдыха часто меняются) YouTube (за один день мы смотрим видео про программирование, йогу и рецепты) Показ рекламы (наш интерес чувствителен ко времени; наша концентрация внимания сокращается)
Real-time recommendations are also useful when the majority of our customers are new (i.e., cold-start). This happens when we’re in the customer acquisition stage, such as when we’ve just launched a new product or entered a new market (e.g., e-commerce in Southeast Asia in 2013 - 2015).
Рекомендации в реальном времени также полезны, когда большинство наших клиентов — новые (то есть холодный старт). Это происходит на этапе привлечения клиентов, например когда мы только что запустили новый продукт или вышли на новый рынок (скажем, e-commerce в Юго-Восточной Азии в 2013–2015 годах).
Imagine you’ve just downloaded an e-commerce app. Since we’re uncertain of your gender, the home page will have a mix of categories catering to each gender, from dresses to men’s shirts, from GPUs to makeup. If you click on a dress, we can immediately build a persona (that you’re female) and personalize your shopping experience. In this case, the u2i recommendations on your home page will tilt towards female products.
Представьте, что вы только что скачали приложение для e-commerce. Поскольку мы не знаем ваш пол, главная страница будет содержать смесь категорий для обоих полов — от платьев до мужских рубашек, от GPU до косметики. Если вы кликнете на платье, мы можем немедленно построить персону (что вы женщина) и персонализировать ваш опыт покупок. В этом случае u2i-рекомендации на вашей главной странице склонятся в сторону женских товаров.
Given that 1 in 4 users abandon mobile apps after only one use, quickly responding to customer needs—from the very first touchpoint—helps with acquisition and retention.
Учитывая, что 1 из 4 пользователей бросает мобильные приложения после всего одного использования, быстрая реакция на потребности клиента — с самого первого касания — помогает в привлечении и удержании.
Primer II: Candidate generation and ranking
Вводный раздел II: генерация кандидатов и ранжирование
Did you miss the first primer (collaborative vs. content-based, item-to-item vs. user-to-item)? Click on the 👉 here.
Пропустили первый вводный раздел (коллаборативные vs контентные, item-to-item vs user-to-item)? Нажмите на 👉 здесь.
Most modern recommenders have two key components: candidate generation and ranking.
Большинство современных рекомендателей имеют два ключевых компонента: генерацию кандидатов и ранжирование.
Candidate generation is a fast—but coarse—approach to get (hundreds of) item candidates from millions of items. We trade off precision for efficiency to reduce the search space (e.g., from 100 million to 1,000 candidates, a 99.999% reduction). This is usually done via metadata-based filters (e.g., category, brand) or k-nearest neighbors.
Генерация кандидатов — это быстрый, но грубый способ получить (сотни) объектов-кандидатов из миллионов объектов. Мы жертвуем точностью ради эффективности, чтобы сократить пространство поиска (например, со 100 миллионов до 1000 кандидатов — сокращение на 99,999%). Обычно это делается через фильтры по метаданным (например, категория, бренд) или через метод k ближайших соседей.
Ranking is a slower—but more precise—approach to sort and select top recommendation candidates. We have leeway to include features that might not have been feasible in the candidate generation step. Such features include user persona (e.g., demographics, price propensity), item metadata (e.g., attributes, engagement statistics), cross features (e.g., interaction between each feature pair), and media embeddings.
Ранжирование — это более медленный, но более точный способ отсортировать и отобрать лучшие объекты-кандидаты. У нас есть свобода включить признаки, которые могли быть невозможны на этапе генерации кандидатов. Такие признаки включают персону пользователя (например, демография, склонность к цене), метаданные объекта (например, атрибуты, статистику вовлечённости), кросс-признаки (например, взаимодействие между каждой парой признаков) и медиа-эмбеддинги.
Ranking can be framed as either a classification or learning to rank problem. As a classification problem, we can score candidates based on probability of click or purchase. Logistic regression with crossed features is simple to implement and a difficult baseline to beat. Decision trees are also commonly used. As a learning to rank problem, commonly used algorithms include LambdaMart, XGBoost, and LightGBM. Neural networks are also gaining adoption, thanks to gains in model efficiency via distillation, pruning, quantization, etc.
Ранжирование можно сформулировать либо как задачу классификации, либо как задачу learning to rank. Как задачу классификации — мы можем оценивать кандидатов по вероятности клика или покупки. Логистическую регрессию с кросс-признаками просто реализовать, и её сложно превзойти как базовую модель. Также широко используются деревья решений. Как задачу learning to rank — часто применяются алгоритмы LambdaMart, XGBoost и LightGBM. Нейронные сети также набирают популярность благодаря росту эффективности моделей за счёт дистилляции, прунинга, квантизации и т. д.
Industry examples of real-time recommendations
Отраслевые примеры рекомендаций в реальном времени
This general reference sheds light on recommendation systems from a Chinese perspective. It’s organized based on the paradigm discussed, with sections for candidate generation (“Match”) and ranking (“Rank”). It also discusses two other components: profile (building user preferences) and post-processing (e.g., excluding previously purchased goods, item-deduplication across recommendation sets).
Этот общий справочный материал проливает свет на рекомендательные системы с китайской точки зрения. Он организован по обсуждаемой парадигме, с разделами для генерации кандидатов («Match») и ранжирования («Rank»). В нём также обсуждаются два других компонента: профиль (построение предпочтений пользователя) и постобработка (например, исключение ранее купленных товаров, дедупликация объектов между наборами рекомендаций).
To see how recommendations can be incrementally updated, we’ll discuss two algorithms: the humble collaborative filtering (CF) and Alibaba’s Swing algorithm that improves on CF.
Чтобы увидеть, как рекомендации можно обновлять инкрементально, мы обсудим два алгоритма: скромную коллаборативную фильтрацию (CF) и алгоритм Swing от Alibaba, который её улучшает.
Collaborative filtering (for i2i recommendations) is implemented via the three formulas below. Let’s try to understand what they do and the intuition behind them.
Коллаборативная фильтрация (для i2i-рекомендаций) реализуется с помощью трёх формул ниже. Давайте попробуем понять, что они делают и какая интуиция за ними стоит.
User weight: A user’s weight is inversely proportionate to their number of item interactions (e.g., click, like, wish-listed). Intuition: Users who browse a lot tend to be less discriminative and thus have more noisy behavioral data.
Вес пользователя: вес пользователя обратно пропорционален числу его взаимодействий с объектами (например, кликов, лайков, добавлений в список желаемого). Интуиция: пользователи, которые много просматривают, как правило, менее разборчивы, и потому их поведенческие данные более зашумлены.
Item weight: The more users interact with an item, the higher its weight.
Вес объекта: чем больше пользователей взаимодействует с объектом, тем выше его вес.
Item similarity score: To calculate similarity between a pair of items, we sum the weight of users who interacted with both items, and divide it by the product of item weights. Intuition: The greater the overlap in user-interactions, the higher the item similarity (similar to collaborative filtering via matrix factorization or alternating least squares).
Оценка схожести объектов: чтобы вычислить схожесть пары объектов, мы суммируем веса пользователей, которые взаимодействовали с обоими объектами, и делим это на произведение весов объектов. Интуиция: чем больше пересечение по взаимодействиям пользователей, тем выше схожесть объектов (аналогично коллаборативной фильтрации через матричную факторизацию или метод чередующихся наименьших квадратов).
The Swing algorithm differs in that the weight (of a pair of users) depends on the number of items they both interacted with (in contrast, CF keeps user weights constant). The greater the proportion of items both users interacted with (i.e., intersection), the higher the user weights.
Алгоритм Swing отличается тем, что вес (пары пользователей) зависит от числа объектов, с которыми оба они взаимодействовали (в отличие от CF, где веса пользователей постоянны). Чем больше доля объектов, с которыми взаимодействовали оба пользователя (то есть пересечение), тем выше веса пользователей.
User weight: Similar to collaborative filtering.
Вес пользователя: аналогично коллаборативной фильтрации.
User-pair weight: Product of user weights. For n users, we have n^2 user-pair weights.
Вес пары пользователей: произведение весов пользователей. Для n пользователей у нас есть n^2 весов пар пользователей.
Item similarity score: Similar to collaborative filtering. The key difference is that the denominator only considers the intersection of products both users have interacted with. (In contrast, CF considers all products any user has interacted with).
Оценка схожести объектов: аналогично коллаборативной фильтрации. Ключевое отличие в том, что знаменатель учитывает только пересечение товаров, с которыми взаимодействовали оба пользователя. (В отличие от CF, где учитываются все товары, с которыми взаимодействовал любой пользователь.)
To make things clearer, here’s how we would calculate item similarity in code:
Чтобы было понятнее, вот как мы вычислили бы схожесть объектов в коде:
for i in xrange(0, len(u2items)):
wi = math.pow(len(u2items[i]) + 5, -0.35)
for j in xrange(i + 1, len(u2items)):
intersection = u2items[i] & u2items[j]
wj = wi * math.pow(len(u2items[j]) + 5, -0.35)
for product_id in intersection:
i2i[product_id] = i2i.get(product_id, 0.0) + wj / (1 + len(intersection))
# u2items = array of users and their items
# u2items[i] = items user i clicked on
# u2items[j] = items user j clicked on
# intersection = items both user i and user j clicked on
# wj = product-pair score
# i2i is incrementally updated as we loop through users (we won't use a loop in production)
for i in xrange(0, len(u2items)): wi = math.pow(len(u2items[i]) + 5, -0.35) for j in xrange(i + 1, len(u2items)): intersection = u2items[i] & u2items[j] wj = wi * math.pow(len(u2items[j]) + 5, -0.35) for product_id in intersection: i2i[product_id] = i2i.get(product_id, 0.0) + wj / (1 + len(intersection)) # u2items = массив пользователей и их объектов # u2items[i] = объекты, на которые кликнул пользователь i # u2items[j] = объекты, на которые кликнул пользователь j # intersection = объекты, на которые кликнули и пользователь i, и пользователь j # wj = оценка пары товаров # i2i инкрементально обновляется по мере прохода по пользователям (в продакшене мы не будем использовать цикл)
Intuitively, if two users with very different tastes (and product interactions) click on the same product-pair, this suggests a strong relationship between the product-pair. Conversely, if two users have similar tastes (and many product pairs), the product-pair relationship is weaker. This reduces the noise from herd behavior (e.g., Harry Potter problem) and identifies more meaningful i2i recommendations.
Интуитивно: если два пользователя с очень разными вкусами (и разными взаимодействиями с товарами) кликают на одну и ту же пару товаров, это говорит о сильной связи между этой парой. И наоборот, если у двух пользователей похожие вкусы (и много общих пар товаров), связь между парой товаров слабее. Это снижает шум от стадного поведения (например, проблема «Гарри Поттера») и выявляет более осмысленные i2i-рекомендации.
From these simple equations, we see how recommendations can be incrementally updated in real-time. Instead of batch matrix multiplication, user and item weights are updated with each customer interaction, perhaps in a key-value store. The weights can then be combined—via summation—to update i2i recommendations.
Из этих простых уравнений видно, как рекомендации можно инкрементально обновлять в реальном времени. Вместо пакетного умножения матриц веса пользователей и объектов обновляются при каждом взаимодействии клиента, возможно, в key-value-хранилище. Затем веса можно скомбинировать — через суммирование — чтобы обновить i2i-рекомендации.
These equations can also be adapted to calculate user affinity towards category, brand, seller, price point, etc. Such affinities are then be used to weigh recommendation candidates. For example, if a user has historical preference for a specific brand, we give items with that brand a higher weight.
Эти уравнения можно также адаптировать для вычисления привязанности пользователя к категории, бренду, продавцу, ценовому сегменту и т. д. Такие привязанности затем используются для взвешивания объектов-кандидатов. Например, если у пользователя есть историческое предпочтение к конкретному бренду, мы даём товарам этого бренда больший вес.
Here’s an example of Swing and category affinity used in real-time recommendations at Alibaba. This implementation is for the “Recommended For You” widget on the home page of 1688, a B2B e-commerce. The widget receives clicks from 72% of users.
Вот пример использования Swing и привязанности к категории в рекомендациях в реальном времени в Alibaba. Эта реализация — для виджета «Recommended For You» на главной странице 1688, B2B-площадки e-commerce. Виджет получает клики от 72% пользователей.
Real-time recommendations architecture for Alibaba 1688 (source)
Архитектура рекомендаций в реальном времени для Alibaba 1688 (источник)
A quick rundown of the infra components:
Краткий обзор компонентов инфраструктуры:
iGraph: распределённая графовая база данных. Воспринимайте её как key-value-хранилище, где узлы и рёбра — это ключи, а веса — значения. Позволяет эффективно выполнять соединения узлов и рёбер и графовые запросы. Используется для хранения предпочтений пользователей и метаданных объектов (например, весов пользователей и объектов из обсуждаемых алгоритмов). ABFS: Alibaba basic feature server. Используется для вычисления в реальном времени статистических признаков по взаимодействиям пользователей (например, клики, лайки, покупки и т. д.). BE: Basic engine. Высокоэффективные фильтры на уровне объектов и kNN на основе эмбеддингов. Используется для генерации кандидатов. RTP: Real-time prediction. Модели для оценки объектов по различным целям (например, CTR, конверсия). Включает логистическую регрессию, Wide & Deep, Product-based Neural Network и Behavioral Sequence Transformer. Используется для ранжирования. Porsche: распределённое обучение моделей. Используется для офлайн-обучения и валидации. Может также использоваться для обновления параметров модели онлайн, хотя здесь это не применяется. TPP: Taobao personalization platform. Слой абстракции над перечисленными выше компонентами инфраструктуры для повышения продуктивности и удобства разработчиков.
Here’s how recommendations are updated and served. As the user browses on the app:
Вот как рекомендации обновляются и отдаются. По мере того как пользователь просматривает приложение:
При каждом взаимодействии с объектом (например, клик, лайк, добавление в корзину, покупка) ABFS вычисляет статистические признаки пользователя и объекта. Они передаются в BE и, опционально, асинхронно обновляются в iGraph. BE генерирует топ-1000 кандидатов на основе признаков пользователя и объекта (то есть предпочтений пользователя, трендов по объектам) из ABFS. На изображении мы видим, что BE использует алгоритмы Swing i2i и c2i (category-to-item). RTP ранжирует 1000 кандидатов. На этом этапе можно добавить признаки, такие как профиль пользователя (пол, возраст, склонность к цене), атрибуты объекта (категория, бренд, продавец), контекст (совпадение с последним кликом/поиском пользователя), кросс-признаки (то есть признаки взаимодействия) и последовательностные признаки (последовательность кликов/категорий). Топ-600 товаров показываются пользователю.
Tencent’s approach is similar. The crux is to break up item-based CF into two aggregates: item count and pair count. Item-to-item similarity is then computed using these aggregates. Thus, item and pair aggregates can be incrementally updated and combined to generate recommendations in real-time. Their system is implemented on Apache Storm and used in Tencent News, Tencent Videos, YiXun (e-commerce), and QQ ads (messaging).
Подход Tencent похож. Суть в том, чтобы разбить item-based CF на два агрегата: счётчик объектов и счётчик пар. Затем схожесть объект-к-объекту вычисляется с использованием этих агрегатов. Таким образом, агрегаты объектов и пар можно инкрементально обновлять и комбинировать для генерации рекомендаций в реальном времени. Их система реализована на Apache Storm и используется в Tencent News, Tencent Videos, YiXun (e-commerce) и QQ ads (мессенджер).
A/B tests showed that real-time recommendations led to 6 - 8% increase in CTR for news recommendations, and 6 - 18% increase in CTR for e-commerce recommendations.
A/B-тесты показали, что рекомендации в реальном времени привели к росту CTR на 6–8% для новостных рекомендаций и на 6–18% для рекомендаций e-commerce.
The paper also shares tricks used to solve several challenges (listed below). Highly recommended read.
В статье также описаны приёмы, использованные для решения нескольких задач (перечислены ниже). Настоятельно рекомендую к прочтению.
Границы Хёффдинга для отсечения избыточных событий взаимодействия пользователей Кластеризация на основе демографии для борьбы с проблемами холодного старта Кэширование для обработки высокой нагрузки чтения из-за всплесков трафика Буферы для устранения перекосов в данных (так называемая «проблема горячего объекта»)
Next, we look west and see how US companies have implemented real-time recommendations.
Далее мы смотрим на запад и видим, как американские компании реализовали рекомендации в реальном времени.
First, here’s YouTube’s video recommendation system. We should be familiar with the overall design paradigm by now.
Сначала вот система рекомендации видео YouTube. К этому моменту нам уже должна быть знакома общая парадигма проектирования.
Real-time recommendation architecture for YouTube (source)
Архитектура рекомендаций в реальном времени для YouTube (источник)
For candidate generation, approximate kNN is applied on video and search embeddings to select hundreds of videos from millions (probably billions by now).
Для генерации кандидатов применяется приближённый kNN на эмбеддингах видео и поиска, чтобы отобрать сотни видео из миллионов (вероятно, уже миллиардов на сегодняшний день).
For ranking, a deep neural network is used to score each video and select the best couple dozen. Additional features (e.g., query and video statistics, previous user interaction) help improve precision. The neural network is trained via weighted logistic regression, where positive labels are weighted by video watch time (negative labels are unweighted). This reflects the business objective of increasing expected watch time per video impression.
Для ранжирования используется глубокая нейронная сеть, чтобы оценить каждое видео и отобрать пару десятков лучших. Дополнительные признаки (например, статистика по запросам и видео, предыдущие взаимодействия пользователя) помогают повысить точность. Нейронная сеть обучается с помощью взвешенной логистической регрессии, где положительные метки взвешиваются по времени просмотра видео (отрицательные метки не взвешиваются). Это отражает бизнес-цель — увеличение ожидаемого времени просмотра на одно показанное видео.
Instagram’s approach is similar. In the candidate generation stage, account embeddings are used to identify accounts similar to those the user has previously interacted with. From these account candidates, they sample 500 media candidates (e.g., photos, stories).
Подход Instagram похож. На этапе генерации кандидатов эмбеддинги аккаунтов используются для выявления аккаунтов, похожих на те, с которыми пользователь ранее взаимодействовал. Из этих аккаунтов-кандидатов они выбирают 500 медиа-кандидатов (например, фото, истории).
Real-time recommendation architecture for Instagram (source)
Архитектура рекомендаций в реальном времени для Instagram (источник)
Then, these media candidates go through a three-pass ranking process which uses a combination of techniques to shrink neural network models:
Затем эти медиа-кандидаты проходят трёхэтапный процесс ранжирования, в котором используется комбинация техник для сжатия нейросетевых моделей:
Первый проход: дистиллированная модель имитирует поздние этапы с минимальным набором признаков и возвращает топ-150 ранжированных кандидатов. Второй проход: лёгкая нейронная сеть использует полный набор плотных (dense) признаков и возвращает топ-50 ранжированных кандидатов. Финальный проход: глубокая нейронная сеть использует полный набор плотных (dense) и разреженных (sparse) признаков и возвращает топ-25 ранжированных кандидатов (для первой страницы сетки Explore).
For our final example, we look at how Netflix re-ranks recommendations in real-time. On most Netflix pages, we’ll see several recommendation rows. Each recommendation row has dozens of movies. The goal is to reorder the recommendation rows (i.e., North-South ordering) as well as the movies within each recommendation row (i.e., East-West order).
В качестве последнего примера рассмотрим, как Netflix переранжирует рекомендации в реальном времени. На большинстве страниц Netflix мы видим несколько строк рекомендаций. В каждой строке рекомендаций — десятки фильмов. Цель — переупорядочить строки рекомендаций (то есть порядок «север-юг») а также фильмы внутри каждой строки (то есть порядок «запад-восток»).
Recommendation rows on Netflix's home screen (source)
Строки рекомендаций на главном экране Netflix (источник)
Horizontal scrolls (on the recommendation rows) are used as user-interaction signals. They showed that video play probability is positively correlated with the number of horizontal scrolls.
Горизонтальные прокрутки (по строкам рекомендаций) используются как сигналы взаимодействия пользователя. Они показали, что вероятность воспроизведения видео положительно коррелирует с числом горизонтальных прокруток.
Relationship between horizontal scrolling and watch probability (source)
Связь между горизонтальной прокруткой и вероятностью просмотра (источник)
In contrast to previous examples, re-ranking is carried out on the client device, avoiding a roundtrip to the server. (However, this also prevents candidate generation.) Given that viewing devices can be low-powered (e.g., TVs), computation needs to be lightweight. Thus, the algorithms used are simple—yet effective—probabilistic models. This allows recommendation rows below the fold (i.e., not on screen) to be updated on-the-fly as users perform horizontal scrolling above the fold.
В отличие от предыдущих примеров, переранжирование выполняется на устройстве клиента, что избавляет от обращения к серверу. (Однако это также не позволяет выполнять генерацию кандидатов.) Поскольку устройства просмотра могут быть маломощными (например, телевизоры), вычисления должны быть лёгкими. Поэтому используемые алгоритмы — простые, но эффективные вероятностные модели. Это позволяет обновлять строки рекомендаций ниже сгиба (то есть не на экране) на лету, по мере того как пользователь выполняет горизонтальную прокрутку выше сгиба.
Thus, we see that real-time recommendations are increasingly common, both in China and US. However, are they only available to big tech? No. Here’s how to cheaply build an MVP.
Итак, мы видим, что рекомендации в реальном времени становятся всё более распространёнными как в Китае, так и в США. Однако доступны ли они только крупным технологическим компаниям? Нет. Вот как дёшево построить MVP.
How to design and implement an MVP
Как спроектировать и реализовать MVP
After the examples above, you’re might think real-time recommenders require specialized infra, deep learning models, and all that jazz. I hope to convince you otherwise.
После приведённых выше примеров вы, возможно, думаете, что рекомендатели реального времени требуют специализированной инфраструктуры, моделей глубокого обучения и всего такого. Надеюсь убедить вас в обратном.
We’ll briefly go through how to design and build an MVP, focusing on what’s commonly viewed as the bottleneck of real-time recommenders: compute and serving. In contrast, training is relatively easier and widely discussed.
Мы кратко пройдёмся по тому, как спроектировать и построить MVP, сосредоточившись на том, что обычно считается узким местом рекомендателей реального времени: вычисления и отдача. В отличие от этого, обучение относительно проще и широко обсуждается.
To begin, I think it’s useful to approach DS/ML systems in three broad strokes:
Для начала, я считаю полезным подходить к DS/ML-системам в трёх широких мазках:
Требования (или ограничения): как выглядит успех? Чего мы не можем делать? Методология: как мы будем использовать данные и код для достижения успеха? Реализация: какая инфраструктура нужна в продакшене?
When defining requirements, we should start from the customer. How will real-time recommendations improve the customer experience, and in turn benefit the business? What business metrics are important? Goals and success metrics will vary based on the business and use case, and will not be defined here.
Определяя требования, мы должны отталкиваться от клиента. Как рекомендации в реальном времени улучшат клиентский опыт и, в свою очередь, принесут пользу бизнесу? Какие бизнес-метрики важны? Цели и метрики успеха будут различаться в зависимости от бизнеса и сценария использования и здесь определяться не будут.
For our MVP, perhaps more important than requirements are constraints (i.e., how not to solve the problem). Here are some constraints for our real-time recommender:
Для нашего MVP, пожалуй, важнее требований сами ограничения (то есть как не решать задачу). Вот некоторые ограничения для нашего рекомендателя реального времени:
Задержка (latency): отзывчивость приложения критична для пользовательского опыта. Google обнаружил, что дополнительные 500 мс на генерацию результатов поиска снижали трафик на 20%. Amazon сообщил, что дополнительные 100 мс задержки снижают прибыль на 1%. Поэтому для нашего MVP мы задаём бюджет в 200 мс задержки (без учёта сетевой задержки от пользователей до нашего сервера). Пропускная способность (throughput): чтобы оценить масштабируемость нашего дизайна, мы задаём ожидаемую пропускную способность в 1000 запросов в секунду (QPS), или около 84 миллионов запросов в день. Скорее всего, нам не понадобится 1000 QPS в течение всего дня, так как трафик колеблется. Стоимость (cost): чтобы добиться здорового ROI, стоимость должна быть долей ожидаемой выручки. Предполагая, что рекомендации в реальном времени приносят дополнительные 100 тыс. в месяц, мы задаём инфраструктурный бюджет в 10 тыс. в месяц (то есть 10%).
We should also consider other aspects such as availability (aka redundancy), security, privacy, ethics, etc. Nonetheless, for our MVP, the first three constraints are technical and business showstoppers which we’ll focus on.
Нам также следует учесть и другие аспекты, такие как доступность (она же резервирование), безопасность, приватность, этика и т. д. Тем не менее для нашего MVP первые три ограничения — технические и бизнесовые «стоп-факторы», на которых мы и сосредоточимся.
To train item embeddings, we adopt the simple but effective word2vec approach, specifically, the skip-gram model. (This is also used by Instagram, Twitter, and Alibaba.) I’ve previously written about how to create embeddings via word2vec and DeepWalk and won’t go into details here.
Для обучения эмбеддингов объектов мы применяем простой, но эффективный подход word2vec, а именно модель skip-gram. (Его также используют Instagram, Twitter и Alibaba.) Я писал ранее о том, как создавать эмбеддинги через word2vec и DeepWalk, и здесь не буду вдаваться в детали.
To generate candidates, we apply k-nearest neigbours (à la YouTube’s implementation). However, exact kNN is slow and we don’t really need the precision at this stage. Thus, we’ll use approximate nearest neighbours (ANN) instead.
Для генерации кандидатов мы применяем метод k ближайших соседей (как в реализации YouTube). Однако точный kNN медленный, и на этом этапе нам на самом деле не нужна такая точность. Поэтому вместо него мы используем приближённый метод ближайших соседей (ANN).
There are several open-sourced ANN implementations, such as Facebook’s FAISS, Google’s ScANN, and Hierarchical Navigable Small Word Graphs (hnswlib). We’ll benchmark them on the recall/latency trade-off. To mimic production conditions, each query consists of a single embedding (i.e., batch size = 1). The graph below shows ScaNN outperforming the other two implementations. (FAISS, in particular, is optimized for batch queries.)
Существует несколько реализаций ANN с открытым исходным кодом, таких как FAISS от Facebook, ScANN от Google и Hierarchical Navigable Small World Graphs (hnswlib). Мы сравним их по компромиссу recall/задержка. Чтобы имитировать продакшен-условия, каждый запрос состоит из одного эмбеддинга (то есть размер батча = 1). График ниже показывает, что ScaNN превосходит две другие реализации. (FAISS, в частности, оптимизирован под батчевые запросы.)
Benchmarking ANNs on recall vs latency; top-right is better.
Бенчмаркинг ANN по recall vs задержка; правый верхний угол лучше.
Installing ScaNN on a Mac is tricky and took a few frustrating hours to figure out. If you run into problems, you might find this step-by-step helpful.
Установка ScaNN на Mac непростая и заняла несколько мучительных часов, чтобы разобраться. Если вы столкнётесь с проблемами, вам может пригодиться эта пошаговая инструкция.
In addition, here are some GitHub issues that might help:
Кроме того, вот несколько GitHub-issues, которые могут помочь:
TF_SHARED_LIBRARY_NAME set with typos when configure Error: Reason: image not found Building from source shows error (undefined symbol: _Py_ZeroStruct)
To rank candidates, we start with a single-layer neural network (read: logistic regression) with cross features—simple, yet difficult to beat. Cross features are created by combining all possible pairs of features to capture their interactions. While this blows up the feature space, it’s not a problem for logistic regression.
Для ранжирования кандидатов мы начинаем с однослойной нейронной сети (читай: логистической регрессии) с кросс-признаками — просто, но трудно превзойти. Кросс-признаки создаются путём комбинирования всех возможных пар признаков для захвата их взаимодействий. Хотя это раздувает пространство признаков, для логистической регрессии это не проблема.
Beyond machine learning metrics (i.e., recall@k, NDCG, AUC), it’s probably more important to consider business metrics (circling back to requirements). Different goals call for different metrics:
Помимо метрик машинного обучения (то есть recall@k, NDCG, AUC), вероятно, важнее учитывать бизнес-метрики (возвращаясь к требованиям). Разные цели требуют разных метрик:
Если наша цель — повышение вовлечённости или продажа рекламы на основе кликов, мы захотим учитывать абсолютное число кликов, click-thru-rate, среднесуточное число пользователей. Если наша цель — привлечение клиентов, мы захотим оптимизировать первую продажу (например, число проданных единиц, конверсию), среднемесячное число пользователей и будем готовы пожертвовать выручкой. Если наша цель — рост выручки, мы захотим сосредоточиться на выручке за сессию, среднем размере корзины и пожизненной ценности клиента (customer lifetime value).
From experience, business stakeholders will usually have conflicting goals. Marketing wants to make the first sale (regardless of item price), customer experience wants to takedown poor quality products (even if they sell well), and commercial wants to maximize profit (by selling higher-priced items). Getting everyone to agree on key metrics and guardrails can be more difficult than improving our models.
По опыту, у бизнес-стейкхолдеров обычно конфликтующие цели. Маркетинг хочет совершить первую продажу (независимо от цены товара), клиентский опыт хочет убрать товары низкого качества (даже если они хорошо продаются), а коммерческий отдел хочет максимизировать прибыль (продавая более дорогие товары). Заставить всех договориться о ключевых метриках и ограничениях может быть сложнее, чем улучшить наши модели.
Will our MVP require specialized infrastructure? Not necessarily. A cost-effective approach is to use EC2 instances that can scale horizontally with a load balancer in front. To further simplify things, we can just use AWS SageMaker.
Потребует ли наш MVP специализированной инфраструктуры? Не обязательно. Экономичный подход — использовать инстансы EC2, которые могут горизонтально масштабироваться с балансировщиком нагрузки впереди. Чтобы ещё больше упростить дело, мы можем просто использовать AWS SageMaker.
SageMaker takes care of load-balancing on multiple instances (image source)
SageMaker берёт на себя балансировку нагрузки на нескольких инстансах (источник изображения)
To assess latency and throughput, we have various options including serverless-artillery (AWS guide) and locust. Running several load tests showed that a SageMaker endpoint backed by 30 m5.xlarge instances was able to serve 1,200 queries per second without breaking a sweat. At this throughput, median latency was 25ms while the 99th percentile was 65ms. There were zero errors.
Для оценки задержки и пропускной способности у нас есть различные варианты, включая serverless-artillery (гайд AWS) и locust. Несколько нагрузочных тестов показали, что эндпоинт SageMaker на 30 инстансах m5.xlarge смог обслуживать 1200 запросов в секунду без особых усилий. При такой пропускной способности медианная задержка составила 25 мс, а 99-й перцентиль — 65 мс. Ошибок не было ни одной.
With regard to cost, m5.xlarge (16 gb RAM, 4 CPUs) instances in US West (Oregon) have an hourly rate of $0.269. Running 30 instances for 28 days works out to approximately 5.5k, well within our 10k budget. Using reserved instances and/or auto-scaling can help with lowering cost.
Что касается стоимости, инстансы m5.xlarge (16 ГБ RAM, 4 CPU) в US West (Oregon) имеют почасовую ставку $0,269. Запуск 30 инстансов на 28 дней выходит примерно в 5,5 тыс., что вполне укладывается в наш бюджет в 10 тыс. Использование зарезервированных инстансов и/или автомасштабирования может помочь снизить стоимость.
Our simple MVP deliberately excludes several considerations. For example, to let other services query our item embeddings, we might want to expose them as a separate service. This will require additional infra (e.g., DynamoDB) which will increase cost and ops burden. The additional service call (for item embeddings) will also add latency (10-30ms) though it can be minimized via a good network setup. Also, how can we expose our candidate generation and ranking services via generic APIs, so other users can mix-and-match as required? We’ll want to consider these in the long-term roadmap.
Наш простой MVP намеренно исключает несколько соображений. Например, чтобы другие сервисы могли запрашивать наши эмбеддинги объектов, мы можем захотеть выставить их как отдельный сервис. Это потребует дополнительной инфраструктуры (например, DynamoDB), что увеличит стоимость и эксплуатационную нагрузку. Дополнительный вызов сервиса (для эмбеддингов объектов) также добавит задержку (10–30 мс), хотя её можно минимизировать при хорошей настройке сети. Также: как мы можем выставить наши сервисы генерации кандидатов и ранжирования через универсальные API, чтобы другие пользователи могли комбинировать их по необходимости? Это стоит учесть в долгосрочном роадмапе.
Building a real-time recommender need not be hard
Построить рекомендатель реального времени не обязательно сложно
I hope this improves your understanding of real-time machine learning in the context of recommendation systems, and demonstrates that it’s not an insurmountable challenge. Libraries (e.g., ScaNN) and managed services (e.g., AWS SageMaker) abstract away much of the nitty-gritty such as optimization, health checks, auto-scaling, recovery, etc. Building on them allows for effective, low-cost, real-time ML.
Надеюсь, это улучшит ваше понимание машинного обучения в реальном времени в контексте рекомендательных систем и продемонстрирует, что это не непреодолимая задача. Библиотеки (например, ScaNN) и управляемые сервисы (например, AWS SageMaker) скрывают большую часть рутины — такой как оптимизация, проверки работоспособности, автомасштабирование, восстановление и т. д. Построение на их основе позволяет создавать эффективный, недорогой real-time ML.
Designing and implementing machine learning systems can be difficult. If you’re building one and would like another pair of eyes or feedback, reach out via @eugeneyan or email.
Проектирование и реализация систем машинного обучения могут быть сложными. Если вы создаёте такую систему и хотели бы получить взгляд со стороны или обратную связь, свяжитесь через @eugeneyan или email.
How does real-time ML look in practice?
We discuss real-time recommenders, drawing on my experience & industry papers:
• When does it make sense? When does it not?
• How have China & US companies implemented them?
• How do we design & build an MVP? https://t.co/hSfRr3q2ie
Как выглядит real-time ML на практике? Мы обсуждаем рекомендатели реального времени, опираясь на мой опыт и отраслевые статьи: • Когда это имеет смысл? А когда нет? • Как китайские и американские компании их реализовали? • Как нам спроектировать и построить MVP? https://t.co/hSfRr3q2ie — Eugene Yan (@eugeneyan) 12 января 2021
References
Источники
applied-ml repository推荐系统技术 机器如何“猜你喜欢”？深度学习模型在1688的应用实践 TencentRec: Real-time Stream Recommendation in Practice Deep Neural Networks for YouTube Recommendations Powered by AI: Instagram’s Explore recommender system Using Navigation to Improve Recommendations in Real-Time 为电商而生的知识图谱，如何感应用户需求 The Secret Behind Taobao’s AI-Powered Personalized Recommendations Personalized Bundle List Recommendation Embeddings@Twitter Billion-scale Commodity Embedding for Recommendation in Alibaba Больше статей по рекомендательным системам в репозитории applied-ml
Thanks to Yang Xinyi, Karl Higley, Will Larson, and Tushar Chandra for reading drafts of this. Thanks to Hammad Khan for a correction.
Благодарю Yang Xinyi, Karl Higley, Will Larson и Tushar Chandra за прочтение черновиков. Благодарю Hammad Khan за исправление.
If you found this useful, please cite this write-up as:
Если вам это оказалось полезным, пожалуйста, цитируйте эту статью так:
Yan, Ziyou. (Jan 2021). Real-time Machine Learning For Recommendations. eugeneyan.com. https://eugeneyan.com/writing/real-time-recommendations/.
Yan, Ziyou. (Jan 2021). Real-time Machine Learning For Recommendations. eugeneyan.com. https://eugeneyan.com/writing/real-time-recommendations/.
or
или
@article{yan2021realttime,
title = {Real-time Machine Learning For Recommendations},
author = {Yan, Ziyou},
journal = {eugeneyan.com},
year = {2021},
month = {Jan},
url = {https://eugeneyan.com/writing/real-time-recommendations/}
}
@article{yan2021realttime, title = {Real-time Machine Learning For Recommendations}, author = {Yan, Ziyou}, journal = {eugeneyan.com}, year = {2021}, month = {Jan}, url = {https://eugeneyan.com/writing/real-time-recommendations/} }
Join 11,800+ readers getting updates on machine learning, RecSys, LLMs, and engineering.
Присоединяйтесь к 11 800+ читателям, которые получают обновления о машинном обучении, RecSys, LLM и инженерии.