System Design for Recommendations and Search

eugeneyan

Start Here Writing Speaking Prototyping About

Системный дизайн для рекомендаций и поиска

[ teardown production engineering recsys 🔥 ] · 13 мин чтения

Также переведено на корейский благодаря Zimin Park.

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

Если говорить именно о системах обнаружения (то есть рекомендациях и поиске), большинство встреченных мной реализаций следуют схожей парадигме: компоненты и процессы разделены на оффлайн- и онлайн-среды, а также на этапы candidate retrieval и ranking. Матрица 2×2 ниже пытается упростить это представление.

Матрица 2×2 онлайн- и оффлайн-сред, а также candidate retrieval и ranking.

Оффлайн-среда в основном содержит батч-процессы: обучение моделей (например, representation learning, ranking), создание эмбеддингов для товаров каталога, построение индекса approximate nearest neighbors (ANN) или графа знаний для поиска похожих объектов. Сюда же может входить загрузка данных о товарах и пользователях в feature store, который используется для обогащения входных данных во время ranking.

Онлайн-среда затем использует сгенерированные артефакты (например, ANN-индексы, графы знаний, модели, feature stores) для обработки отдельных запросов. Типичный подход — преобразование входного товара или поискового запроса в эмбеддинг с последующим candidate retrieval и ranking. Существуют также другие шаги предобработки (например, нормализация запросов, токенизация, проверка орфографии) и постобработки (например, фильтрация нежелательных товаров, бизнес-логика), но в этой заметке мы их не рассматриваем.

Candidate retrieval — быстрый, но грубый шаг для сужения миллионов товаров до сотен кандидатов. Мы жертвуем точностью ради эффективности, чтобы быстро сузить пространство поиска (например, с миллионов до сотен — сокращение на 99,99%) для последующей задачи ranking. Большинство современных методов retrieval преобразуют вход (товар, поисковый запрос) в эмбеддинг, а затем используют ANN для поиска похожих объектов. Тем не менее, в примерах ниже мы увидим и системы, использующие графы (DoorDash) и деревья решений (LinkedIn).

Ranking — более медленный, но более точный шаг для оценки и упорядочивания топ-кандидатов. Поскольку мы обрабатываем меньше объектов (сотни вместо миллионов), у нас есть пространство для добавления признаков, которые были бы невозможны на этапе retrieval (из-за ограничений по вычислениям и задержкам). Такие признаки включают данные о товарах и пользователях, а также контекстную информацию. Можно также использовать более сложные модели с большим числом слоёв и параметров.

Ranking можно моделировать как задачу learning-to-rank или классификации, причём вторая встречается чаще. Если применяется deep learning, итоговый выходной слой представляет собой либо softmax по каталогу товаров, либо sigmoid, предсказывающий вероятность взаимодействия пользователя (например, клик, покупка) для каждой пары пользователь-товар.

Далее посмотрим, как описанные процессы складываются вместе в рекомендательной или поисковой системе.

Базовый системный дизайн для рекомендаций и поиска на основе матрицы 2×2 выше.

В оффлайн-среде данные движутся снизу вверх: мы используем обучающие данные и данные о товарах/пользователях для создания артефактов — моделей, ANN-индексов и feature stores. Эти артефакты затем загружаются в онлайн-среду (через пунктирные стрелки). В онлайн-среде каждый запрос проходит слева направо, через шаги retrieval и ranking, прежде чем вернуть набор результатов (например, рекомендации, поисковую выдачу).

Дополнительные пояснения к некоторым стрелкам на схеме:

С помощью обученной модели representation learning эмбеддируем товары в каталоге. На основе эмбеддингов товаров строим ANN-индекс, позволяющий находить похожие эмбеддинги и соответствующие им товары. Получаем (исторические) признаки для обогащения обучающих данных модели ranking. Используем один и тот же feature store при оффлайн-обучении и онлайн-сервинге, чтобы минимизировать train-serve skew. Может потребоваться time travel. Используем эмбеддинг входного запроса/товара(ов) для извлечения k похожих объектов через ANN. Добавляем признаки товаров и пользователей к кандидатам для последующего ranking. Ранжируем кандидатов по целевым метрикам — клики, конверсии и т. п.

Обновление: эта матрица 2×2 с тех пор упоминалась в других материалах, в том числе: NVIDIA «Recommender Systems, Not Just Recommender Models» и Xavier Amatriain «Blueprints for RecSys Architectures».

Примеры от Alibaba, Facebook, JD, Doordash и других

Далее кратко обсудим высокоуровневый системный дизайн нескольких систем обнаружения по их статьям и техноблогам. Я выделю, как эти системы разделены на оффлайн- и онлайн-среды и шаги retrieval и ranking. За полным описанием методологии, моделей и т. п. рекомендую обратиться к самим статьям и публикациям.

Начнём с публикации Alibaba о построении эмбеддингов товаров для candidate retrieval. В оффлайн-среде взаимодействия пользователь-товар на уровне сессий анализируются для построения взвешенного двунаправленного графа товаров. Затем граф используется для генерации последовательностей товаров с помощью случайных блужданий. Эмбеддинги товаров обучаются через representation learning (word2vec skip-gram), что устраняет необходимость в разметке. Наконец, имея эмбеддинги, для каждого товара находят ближайшего соседа и сохраняют его в item-to-item (i2i) similarity map (хранилище ключ-значение).

Дизайн Alibaba для candidate retrieval в Taobao через эмбеддинги товаров и ANN.

В онлайн-среде, когда пользователь запускает приложение, Taobao Personalization Platform (TPP) начинает с получения последних товаров, с которыми взаимодействовал пользователь (клик, лайк, покупка). Эти товары затем используются для извлечения кандидатов из i2i similarity map. Кандидаты передаются в Ranking Service Platform (RSP) для ранжирования через глубокую нейросеть, после чего отображаются пользователю.

Alibaba также поделилась похожим примером, где применяет графовую сеть для ranking. В оффлайн-среде они объединяют существующий граф знаний (G), поведение пользователей (например, показано, но не кликнуто, кликнуто) и данные о товарах, чтобы создать адаптивный граф знаний (G_ui). Затем он объединяется с данными о пользователях (демография, предпочтения пользователь-товар) для обучения модели ranking — Adaptive Target-Behavior Relational Graph Network (ATBRN).

Дизайн Alibaba для ranking в Taobao через графовую сеть (ATBRN).

В онлайн-среде на запрос пользователя генератор кандидатов извлекает набор кандидатов и user ID, после чего передаёт их в Real-Time Prediction (RTP) платформу. RTP затем запрашивает граф знаний и feature stores для атрибутов товаров и пользователей. Графовые представления, данные о товарах и пользователях подаются в модель ranking (ATBRN), которая предсказывает вероятность клика по каждому кандидату. Кандидаты затем переупорядочиваются по вероятности и показываются пользователю.

Далее посмотрим на embedding-based retrieval для поиска от Facebook. В оффлайн-среде (правая половина изображения) они сначала обучают двухбашенную сеть — с энкодером запросов и энкодером документов — которая выдаёт косинусное сходство для каждой пары запрос-документ (на изображении не показано). Это гарантирует, что поисковые запросы и документы (например, профили пользователей, группы) находятся в одном эмбеддинг-пространстве.

Дизайн Facebook для embedding-based retrieval через энкодеры запросов и документов.

Затем с помощью энкодера документов они эмбеддируют каждый документ через батч-задачи Spark. Эмбеддинги квантуются и публикуются в их ANN-индексе («inverted index»). Этот ANN-индекс основан на Faiss и доработан (см. раздел 4.1 статьи). Эмбеддинги также публикуются в forward index без квантования — для ranking. Forward index может также включать иные данные, например атрибуты профилей и групп, для обогащения кандидатов во время ranking.

В онлайн-среде каждый поисковый запрос проходит через query understanding и эмбеддируется через энкодер запросов. Запрос и связанный эмбеддинг затем проходят через шаг retrieval, чтобы получить ближайших соседей через ANN-индекс и булеву фильтрацию (например, совпадение по имени, локации и т. п.). Кандидаты затем обогащаются полными эмбеддингами и дополнительными данными из forward index перед ранжированием.

JD поделились похожим подходом к семантическому retrieval для поиска. В оффлайн-среде обучается двухбашенная модель с энкодером запросов и энкодером товаров, выдающая оценку сходства для каждой пары запрос-товар. Энкодер товаров затем эмбеддирует товары каталога и загружает их в embedding index (хранилище ключ-значение).

Основные стадии e-commerce поисковых систем (слева), дизайн JD для candidate retrieval (справа).

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

В статье также приводятся практические советы по оптимизации обучения и сервинга моделей. Что касается обучения, они отметили, что де-факто вход — взаимодействия пользователь-товар, данные о товарах и пользователях — дублируется: данные о товарах и пользователях встречаются в каждой строке, занимая значительное место на диске. Чтобы решить эту проблему, они построили кастомный TensorFlow dataset, где данные о пользователях и товарах сначала загружаются в память как lookup-словари. Затем во время обучения эти словари запрашиваются, чтобы добавить атрибуты пользователей и товаров к обучающей выборке. Эта простая практика сократила размер обучающих данных на 90%.

Они также подчеркнули важность обеспечения согласованности оффлайн-обучения и онлайн-сервинга. Для их системы самым критичным шагом была токенизация текста, которая выполняется трижды (предобработка данных, обучение, сервинг). Чтобы минимизировать train-serve skew, они построили токенизатор на C++ с тонкой Python-обёрткой, который использовался для всех задач токенизации.

Что касается сервинга моделей, они рассказали, как снизили задержку, объединив сервисы. Их модель имела два ключевых шага: эмбеддинг запроса и ANN-поиск. Простой подход — сделать каждый из них отдельным сервисом, но это потребовало бы двух сетевых вызовов и, соответственно, удвоило бы сетевую задержку. Поэтому они объединили модель эмбеддинга запроса и ANN-поиск в одном инстансе, где эмбеддинг запроса передаётся в ANN через память, а не через сеть.

Они также рассказали, как запускают сотни моделей одновременно — для разных задач retrieval и различных A/B-тестов. Каждый «servable» состоит из модели эмбеддинга запроса и ANN-поиска и требует десятки гигабайт. Поэтому у каждого servable свой инстанс, а прокси-модуль (или балансировщик нагрузки) направляет входящие запросы к нужному servable.

Как JD организует модель эмбеддинга и ANN-индексы в нескольких версиях.

(Отступление: мои системы candidate retrieval имеют похожий паттерн. Embedding stores и ANN-индексы хостятся в одном docker-контейнере — вы удивитесь, насколько далеко это работает при эффективно подобранных размерах эмбеддингов. Кроме того, Docker облегчает версионирование, развёртывание и откат каждой модели, а также горизонтальное масштабирование. Балансировщик нагрузки перед инстансами моделей берёт на себя направление входящих запросов, blue-green deployments и A/B-тестирование. SageMaker делает это простым.)

Далее уходим от парадигмы эмбеддинги + ANN и смотрим, как DoorDash использует граф знаний для расширения запросов и retrieval. В оффлайн-среде они обучают модели для query understanding, расширения запросов и ranking. Они также загружают документы (рестораны и блюда) в ElasticSearch для использования в retrieval, а данные атрибутов (рейтинги, ценовые категории, теги) — в feature store.

DoorDash разделяет поиск на оффлайн и онлайн, а также retrieval (recall) и ranking (precision).

В онлайн-среде каждый входящий запрос сначала нормализуется (проверка орфографии) и синонимизируется (через вручную составленный словарь). Затем граф знаний (Neo4J) расширяет запрос, находя связанные теги. Например, запрос «KFC» вернёт теги «fried chicken» и «wings». Эти теги затем используются для извлечения похожих ресторанов вроде «Popeyes» и «Bonchon».

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

Наконец, посмотрим, как LinkedIn персонализирует поиск талантов. Их система во многом опирается на XGBoost: сначала как модель для извлечения топ-1000 кандидатов для ranking, а затем как генератор признаков (оценки модели, взаимодействия деревьев) для последующей модели ranking — generalized linear mixed model, она же GLMix.

Оффлайн-дизайн LinkedIn для генерации признаков на основе деревьев и обучения моделей ranking GLMix.

В оффлайн-среде они сначала объединяют данные о показах и разметку для создания обучающих данных (шаг 1 на изображении выше). Метки состоят из случаев, когда рекрутер отправлял сообщение потенциальному кандидату, и пользователь отвечал положительно. Обучающие данные затем подаются в предобученную модель XGBoost для генерации оценок модели и признаков взаимодействия деревьев (шаг 3 на изображении выше) для обогащения обучающих данных. Эти обогащённые данные затем используются для обучения модели ranking (GLMix).

Онлайн-дизайн LinkedIn для candidate retrieval, обогащения признаками и ranking через GLMix.

В онлайн-среде на каждый поисковый запрос поисковый движок (возможно, Elastic или Solr?) сначала извлекает кандидатов, которых затем оценивает модель XGBoost первого уровня. Топ-1000 кандидатов затем обогащаются (i) дополнительными признаками (шаг 2 на изображении выше) и (ii) признаками взаимодействия деревьев через модель XGBoost второго уровня (шаг 3 на изображении выше). Наконец, эти обогащённые кандидаты ранжируются, и топ-125 результатов показываются пользователю.

Заключение

Это был краткий обзор паттерна оффлайн-онлайн и retrieval-ranking для поиска и рекомендаций. Хотя это не единственный подход к системам обнаружения, по моему опыту, это самый распространённый паттерн проектирования. Мне показалось полезным разделять онлайн-системы с ограничениями по задержкам от менее требовательных оффлайн-систем, а также делить онлайн-процесс на шаги retrieval и ranking.

Если вы только начинаете строить свою систему обнаружения, начните с candidate retrieval через простые эмбеддинги и approximate nearest neighbors, а затем добавьте ranker сверху. Альтернативно можно рассмотреть граф знаний — как сделали Uber и DoorDash. Но прежде чем слишком увлекаться, серьёзно подумайте, действительно ли вам нужны realtime retrieval и ranking, или батчевых рекомендаций будет достаточно.

Я что-то упустил? Пожалуйста, напишите мне и расскажите!

Давайте разберём, как recsys и поиск часто делятся на: • Онлайн-среды с ограничениями по задержкам vs. менее требовательные оффлайн-среды • Быстрый, но грубый candidate retrieval vs. более медленный и точный ranking. Примеры от Alibaba, Facebook, JD, DoorDash и других. https://t.co/zTsfElLw1z — Eugene Yan (@eugeneyan) June 30, 2021

Обновление (2022-04-14): Even Oldridge и Karl Byleen-Higley из NVIDIA расширили двухстадийный дизайн до четырёхстадийного, добавив шаг фильтрации и разделив ranking на scoring и ordering. Они также представили это на воркшопе Industrial Recommender Systems на KDD.

Even Oldridge и Karl Byleen-Higley (NVIDIA) дополнили мой двухстадийный дизайн ещё двумя стадиями.

Источники

Billion-scale Commodity Embedding for E-commerce Recommendation Alibaba Adaptive Target-Behavior Relational Graph Network for Recommendation Alibaba Embedding-based Retrieval in Facebook Search Facebook An End-to-End Solution for E-commerce Search via Embedding Learning JD Things Not Strings: Understanding Search Intent with Better Recall DoorDash Entity Personalized Talent Search Models with Tree Interaction Features LinkedIn Faiss: A Library for Efficient Similarity Search Facebook

Спасибо Yang Xinyi за чтение черновиков.

Если этот материал был полезен, пожалуйста, цитируйте его как:

Yan, Ziyou. (Jun 2021). System Design for Recommendations and Search. eugeneyan.com. https://eugeneyan.com/writing/system-design-for-discovery/.

или

@article{yan2021system, title = {System Design for Recommendations and Search}, author = {Yan, Ziyou}, journal = {eugeneyan.com}, year = {2021}, month = {Jun}, url = {https://eugeneyan.com/writing/system-design-for-discovery/} }

Присоединяйтесь к 11 800+ читателей, получающих обновления о машинном обучении, RecSys, LLM и инженерии.