Рекомендательные системы

Candidate Generation

Цели урока

Понять принцип работы HNSW и trade-offs ANN Search
Спроектировать two-stage retrieval с несколькими источниками кандидатов
Применить Bloom Filter для эффективной дедупликации виденных айтемов
Сравнить LSH и HNSW по ключевым характеристикам

YouTube в 2016 году опубликовал статью о своей рекомендательной системе. Главная инженерная проблема: из 800 миллионов видео нужно за 200 мс вернуть персональный список из 10. Решение - двухэтапная архитектура с ANN Search для retrieval - стала стандартом индустрии. Netflix, Spotify, TikTok используют ту же схему.

**YouTube** - two-stage с матричной факторизацией для retrieval, DNN для ranking
**Spotify** - HNSW для ANN поиска по 80M треков, Bloom Filter для viewed exclusion
**Pinterest** - LSH для pin recommendations при постоянно обновляемом каталоге

Предварительные знания

Embeddings и векторное сходство
Основы matrix factorization
Big-O рассуждения о latency и throughput

Two-Tower Retrieval и эпоха глубокого обучения в YouTube

В 2016 году Paul Covington, Jay Adams и Emre Sargin из YouTube опубликовали "Deep Neural Networks for YouTube Recommendations", где разбили задачу на две стадии: глубокая сеть candidate-generation, сужающая миллионы видео до сотен, и затем отдельная ранжирующая сеть. Модель кандидатов формулировала retrieval как extreme multiclass classification и обучала его через sampled softmax, аппроксимируя softmax по всему каталогу на небольшом наборе негативов. При обслуживании запросов выученный вектор пользователя обращается к предвычисленному индексу векторов видео через approximate nearest neighbor search. Этот двухбашенный двухстадийный дизайн стал паттерном retrieval по умолчанию во всей индустрии, потому что точный скоринг всего каталога на каждый запрос невозможен на веб-масштабе.

ANN Search: HNSW и ScaNN

Библиотека Spotify содержит 80 миллионов треков, каждый представлен вектором из 128 чисел. Найти 1000 треков, ближайших к профилю пользователя, методом полного перебора (brute-force) - это 80M умножений за каждый запрос. При 10 000 запросов в секунду это невозможно. **ANN (Approximate Nearest Neighbor) Search** - это класс алгоритмов, которые находят достаточно близкие векторы за миллисекунды, жертвуя небольшим процентом точности.

**HNSW (Hierarchical Navigable Small World)** строит многоуровневый граф: верхние слои - редкие «хайвеи» для быстрого перемещения, нижние - детальная карта соседей. Поиск начинается с вершины и спускается вниз, на каждом уровне приближаясь к цели. **ScaNN (Scalable Nearest Neighbors)** от Google использует product quantization и асимметричное расстояние для 10-20x ускорения через SIMD-инструкции процессора.

HNSW хранит граф в RAM - для 80M векторов dim=128 нужно ~40 GB. В продакшне индекс делят на шарды по userId % N и каждый шард хранится на отдельном хосте. Milvus и Weaviate реализуют это из коробки.

В чём главный trade-off ANN Search по сравнению с точным (brute-force) поиском?

Two-Stage Architecture

Нельзя прогнать сложную ранжирующую модель (200+ фичей, 50 мс на инференс) по всем 80 миллионам треков. Но и ANN без контекста даёт слишком грубый результат. Индустриальное решение - **two-stage (двухэтапная) архитектура**: первый этап быстро вытаскивает сотни кандидатов, второй точно ранжирует только их.

Зачем в two-stage рекомендательной системе используется несколько источников кандидатов (ANN + item2item + trending)?

Bloom Filter для дедупликации

Пользователь уже видел 50 000 видео. При каждом запросе нужно исключить их из кандидатов. Хранить Set из 50 000 ID в памяти на каждый запрос дорого, а проверять каждого кандидата в Redis - слишком медленно. **Bloom Filter** - это вероятностная структура данных: занимает в 100 раз меньше памяти, отвечает «возможно видел» или «точно не видел» за O(1).

Bloom Filter никогда не даёт ложных отрицаний (false negative): если говорит «не видел» - значит точно не видел. Ложные положительные (false positive) допустимы: иногда покажем уже виденный айтем. Для рекомендаций это нормально - user_experience лучше, чем постоянно рекомендовать просмотренное.

Bloom Filter говорит, что пользователь «возможно видел» видео X. Это означает:

Locality-Sensitive Hashing

HNSW хранит весь граф в RAM - для 1 миллиарда векторов это сотни гигабайт. **Locality-Sensitive Hashing (LSH)** предлагает альтернативу: вместо графа - хеш-таблицы, где похожие векторы попадают в одинаковые bucket-ы. Метод основан на случайных проекциях: если два вектора близки в оригинальном пространстве, их проекции на случайную гиперплоскость имеют одинаковый знак с высокой вероятностью.

LSH помещает похожие векторы в одинаковые bucket-ы через случайные проекции. Какое свойство это использует?