Search & Ranking

Google обрабатывает 8.5 миллиардов поисковых запросов в день и возвращает релевантные результаты за 0.2 секунды. Разница между показом правильного результата на позиции 1 и на позиции 10 - это миллиарды долларов выручки. Search ranking - самая масштабная ML-система в мире.

• **Google Search** - 8.5 миллиардов запросов в день обрабатываются каскадом BM25 retrieval, bi-encoder filtering и cross-encoder re-ranking, каждый этап улучшает качество ранжирования на 5-15% NDCG по сравнению с предыдущим
• **YouTube рекомендации** - two-tower архитектура отбирает top-1000 видео из миллиардов за 10ms, затем более тяжёлая ranking модель с сотнями features выбирает финальные 20 видео для показа на главной странице
• **E-commerce (Amazon, Ozon)** - поисковый запрос 'красные кроссовки Nike' проходит через BM25 (фильтрация по словам), semantic search (находит 'красные беговые Nike' даже без слова 'кроссовки') и personalized ranking (учитывает историю покупок и бюджет пользователя)

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

• Recommendation Systems

PageRank, BM25 и обучение ранжированию

У ранжирования в поиске несколько переплетённых корней. Со статистической стороны Стивен Робертсон и Стив Уокер формализовали BM25 примерно в 1994 году, вероятностную ранжирующую функцию, которая оценивала документы по частоте термина и обратной документной частоте, и она до сих пор остаётся сильным базовым решением в поисковых движках. Со стороны анализа ссылок в 1998 году Сергей Брин и Ларри Пейдж, тогда аспиранты Стэнфорда, опубликовали PageRank, ранжировавший веб-страницы так, будто ссылки это голоса, и взвешивавший каждый голос важностью ссылающейся страницы. PageRank стал фундаментом Google. Третий корень это машинное обучение. В 2005 году Крис Бёрджес с коллегами в Microsoft Research представил RankNet, нейросеть, обучаемую на парах документов предсказывать, какой должен стоять выше, что положило начало современной области learning to rank. RankNet привёл к LambdaRank и LambdaMART, которые оптимизировали ранжирующие метрики напрямую и годами обеспечивали работу коммерческих поисковиков.

Learning to Rank

Задача поискового ранжирования: дан запрос и набор документов, нужно отсортировать документы по **релевантности**. Это не обычная классификация (релевантен/нет), а именно **упорядочивание** - документ A должен стоять выше документа B. Learning to Rank (LTR) - это семейство ML-подходов, которые обучаются ранжировать по размеченным данным. Разметка обычно делается экспертами-асессорами по шкале: 0 (нерелевантен), 1 (частично релевантен), 2 (релевантен), 3 (идеальный ответ).

**NDCG (Normalized Discounted Cumulative Gain)** - главная метрика ранжирования. Она учитывает и релевантность, и позицию: документ с оценкой 3 на позиции 1 ценнее, чем на позиции 10. Дисконтирование логарифмическое: gain / log2(position + 1). NDCG нормализуется от 0 до 1, где 1 - идеальное ранжирование. **MAP (Mean Average Precision)** - альтернативная метрика для бинарной релевантности (релевантен/нет), усредняет precision на каждой позиции, где стоит релевантный документ.

**LambdaMART - стандарт индустрии:** LambdaMART = Lambda (gradients) + MART (Multiple Additive Regression Trees, то есть gradient boosted trees). Идея: вместо оптимизации NDCG напрямую (она недифференцируема), LambdaMART вычисляет **lambda-градиенты** - приближение градиента NDCG через попарные сравнения. Каждая пара документов (A, B) получает градиент, пропорциональный изменению NDCG при их перестановке. Реализации: - **XGBoost** с objective='rank:ndcg' или 'rank:pairwise' - **LightGBM** с objective='lambdarank' - **CatBoost** с loss_function='YetiRank' LambdaMART выигрывал практически все соревнования по ранжированию до 2020 года и до сих пор используется в продакшене Google, Bing, Yahoo.

**Признаки для LTR** делятся на три группы: **query-зависимые** (длина запроса, тип запроса), **document-зависимые** (PageRank, длина документа, свежесть, количество ссылок) и **query-document** (BM25 score, количество совпадений терминов, TF-IDF similarity). На практике у крупных поисковых систем от 500 до 1000+ признаков на пару (запрос, документ). LambdaMART на gradient boosted trees отлично работает с таким количеством разнородных признаков.

BM25: классика информационного поиска

**BM25 (Best Matching 25)** - алгоритм 1994 года, который остаётся основой информационного поиска в 2024 году. Elasticsearch, Solr, Lucene - все используют BM25 по умолчанию. Идея: релевантность документа запросу определяется тем, **как часто слова запроса встречаются в документе** (term frequency), с учётом **насколько редко это слово встречается во всех документах** (inverse document frequency). Слово 'квантовый' в документе о физике ценнее, чем слово 'является', потому что 'квантовый' встречается редко.

**Насыщение TF** - главное отличие BM25 от простого TF-IDF. В TF-IDF, если слово 'Python' встречается 100 раз, документ получает в 100 раз больше баллов, чем документ с 1 упоминанием. Но 100 упоминаний не означают 100-кратную релевантность - это может быть просто SEO-спам. BM25 ограничивает влияние повторений: после определённого порога дополнительные вхождения почти не добавляют к скору. Параметр k1 контролирует точку насыщения.

**Параметры k1 и b - когда их менять:** **k1 (default 1.5):** - k1 = 0: TF полностью игнорируется, важно только наличие слова - k1 = 1.2: быстрое насыщение (хорошо для коротких запросов) - k1 = 2.0: медленное насыщение (хорошо для длинных документов) **b (default 0.75):** - b = 0: длина документа не учитывается (все документы "равны") - b = 0.75: стандартная нормализация (работает в большинстве случаев) - b = 1.0: полная нормализация (штрафует длинные документы сильнее) **Когда менять:** - Web search: k1=1.2, b=0.75 (стандарт) - Академические статьи (длинные, однородные): k1=1.5, b=0.3 - Твиты и заголовки (короткие): k1=1.5, b=0.0 На практике default параметры работают хорошо в 90% случаев.

**Почему BM25 до сих пор актуален?** Во-первых, скорость: BM25 с инвертированным индексом обрабатывает миллионы документов за миллисекунды. Во-вторых, интерпретируемость: причина высокого скора документа всегда прозрачна. В-третьих, надёжность: BM25 не требует обучения (только два параметра) и работает из коробки на любом языке. Neural ranking модели превосходят BM25 по качеству, но они в 100-1000 раз медленнее. Поэтому современные поисковые системы используют BM25 как **первый этап** (retrieval), а нейросети - для **переранжирования** top-K результатов.

Neural Ranking: BERT и семантический поиск

BM25 ищет по точным совпадениям слов: запрос 'как лечить головную боль' не найдёт документ, где написано 'методы терапии мигрени'. **Neural ranking** решает эту проблему, сравнивая **смысл** запроса и документа через embeddings нейросетей. Базовый подход - **cross-encoder**: берём BERT, подаём на вход пару [CLS] запрос [SEP] документ [SEP], и обучаем выходной слой предсказывать релевантность. Cross-encoder видит все взаимодействия между словами запроса и документа, что даёт лучшее качество.

Проблема cross-encoder: для каждого запроса нужно прогнать BERT через ВСЕ кандидаты. При 1 миллионе документов это 1 миллион forward passes BERT - часы на один запрос. **Bi-encoder** решает это: query и document кодируются **независимо** в векторы фиксированной размерности. Документы кодируются один раз при индексации. При поиске кодируется только запрос, а ближайшие документы находятся через similarity (dot product или cosine). Но bi-encoder хуже по качеству: он не видит взаимодействий между словами запроса и документа.

**ColBERT - лучшее из двух миров (late interaction):** ColBERT (Contextualized Late Interaction over BERT) - компромисс между cross-encoder и bi-encoder. Идея: каждое слово запроса и документа кодируется в отдельный вектор (не один вектор на текст). Релевантность = сумма максимальных схожестей каждого слова запроса с любым словом документа: score = SUM_i MAX_j similarity(q_i, d_j) - Документы кодируются offline (как bi-encoder) - Но сохраняется взаимодействие на уровне слов (как cross-encoder) - Качество близко к cross-encoder, скорость близка к bi-encoder - Минус: хранение требует больше памяти (один вектор на каждое слово)

**Пайплайн современной поисковой системы**: BM25 retrieval (top-1000) -> bi-encoder re-ranking (top-100) -> cross-encoder re-ranking (top-10) -> business logic (top-K для пользователя). Каждый этап точнее, но медленнее. BM25 обрабатывает миллионы документов за миллисекунды, cross-encoder тратит ~10ms на одну пару (запрос, документ). Этот каскадный дизайн позволяет сочетать скорость BM25 с качеством нейросетей.

Two-Tower архитектура

**Two-tower** (двухбашенная) архитектура - индустриальный стандарт для retrieval в масштабе. Идея: две отдельные нейросети ("башни") кодируют запрос и документ в векторы одинаковой размерности. Похожесть определяется через dot product или cosine similarity. Главное преимущество: документы кодируются **один раз при индексации**, а при поиске нужно закодировать только запрос и найти ближайшие векторы. Это основа поиска в Google, YouTube, Facebook, Amazon и практически любой крупной поисковой системе.

Критический компонент two-tower системы - **Approximate Nearest Neighbors (ANN)**. Точный поиск ближайшего вектора среди 1 миллиарда имеет сложность O(N) - слишком медленно. ANN-индексы находят *приблизительно* ближайших соседей за O(log N), жертвуя точностью (recall ~95-99%) ради скорости. Главные библиотеки: **FAISS** (Facebook), **ScaNN** (Google), **Annoy** (Spotify), **HNSW** (hnswlib). FAISS может искать среди миллиарда векторов за 1-10 миллисекунд на одном сервере.

**Hard negatives - секрет качественного обучения two-tower:** Обучение через случайные negative примеры (random negatives) недостаточно: модель быстро выучит отличать "рецепт торта" от "квантовая физика", но не отличит "рецепт шоколадного торта" от "рецепт ванильного торта". **Hard negatives** - документы, которые похожи на релевантные, но не являются правильным ответом: 1. **BM25 negatives:** top результаты BM25, которые не помечены как релевантные 2. **In-batch negatives:** другие документы в текущем batch (дешёвый способ) 3. **Self-mining:** документы, которые текущая модель ошибочно ранжирует высоко Итеративный процесс: обучить модель v1 -> найти hard negatives моделью v1 -> обучить v2 на hard negatives -> повторить 2-3 раза.

**Online serving** two-tower модели в production: document tower прогоняется offline для всех документов (миллиарды), векторы индексируются в FAISS или ScaNN. Query tower работает online - при каждом запросе кодирует его в вектор за ~1ms на GPU. ANN-поиск находит top-K ближайших векторов за ~5ms. Итого: от запроса до top-K результатов из миллиарда документов за ~10ms. Далее top-K переранжируются cross-encoder для финального порядка. Это стандартная архитектура поиска в Google, YouTube, Pinterest, Airbnb.

Итоги

• **Learning to Rank:** LambdaMART на gradient boosted trees - стандарт ранжирования, оптимизирует NDCG через попарные сравнения документов, используя сотни query-document features
• **BM25:** алгоритм 1994 года, который остаётся основой поиска благодаря скорости (миллионы документов за миллисекунды), насыщению TF (защита от спама) и нормализации длины документов
• **Neural Ranking:** cross-encoder BERT даёт лучшее качество за счёт полного внимания к паре (запрос, документ), bi-encoder жертвует качеством ради скорости, ColBERT - компромисс через late interaction
• **Two-Tower + ANN:** query tower и document tower кодируют тексты в векторы, FAISS/ScaNN ищут ближайших среди миллиарда за 10ms - именно так работает поиск, который за 0.2 секунды находит лучший результат из 8.5 миллиардов запросов в день

Связанные темы

Search & Ranking объединяет классический information retrieval, NLP и системы масштабирования, связывая фундаментальные алгоритмы с production ML:

• Рекомендательные системы — Two-tower архитектура пришла из рекомендаций: та же идея кодирования user и item в векторы, тот же ANN-поиск для retrieval, то же каскадное ранжирование. Разница: в поиске главный сигнал - текстовое совпадение, в рекомендациях - поведение пользователя
• BERT и GPT — Cross-encoder и bi-encoder для ранжирования построены на BERT: cross-encoder использует full attention между запросом и документом, bi-encoder - CLS token каждого текста отдельно. Понимание архитектуры трансформера критично для neural ranking
• Gradient Boosting (XGBoost) — LambdaMART - это gradient boosted trees с lambda-градиентами для оптимизации NDCG. Все принципы XGBoost (регуляризация, обработка пропусков, split finding) напрямую применяются в ranking-моделях
• Word Embeddings — Bi-encoder создаёт sentence embeddings - развитие идеи word2vec на уровне предложений и документов. Те же операции (cosine similarity, nearest neighbors) применяются к текстовым представлениям более высокого уровня

Вопросы для размышления

• BM25 был создан в 1994 году, а neural ranking появился в 2018-2019. Почему BM25 до сих пор используется как первый этап практически в каждой поисковой системе? В каких условиях можно обойтись без BM25 полностью?
• Cross-encoder даёт лучшее качество, но bi-encoder/two-tower - лучшую скорость. ColBERT - компромисс. Как выбрать архитектуру для системы с 10 миллионами документов и требованием latency < 100ms?
• Hard negatives критичны для обучения two-tower модели. Почему обучение только на random negatives приводит к плохому качеству, и как итеративный self-mining hard negatives решает эту проблему?

Связанные уроки

• ml-51-recommendation-systems — Ранжирование и recsys делят логику поиска
• ml-37-bert-gpt — Семантическое ранжирование на трансформерах
• ml-22-gradient-boosting — Learning-to-rank использует gradient boosting
• ml-35-word-embeddings — Сопоставление query-doc через эмбеддинги
• sd-21-search-systems — Тот же паттерн retrieval-then-rank
• stat-09-regression