TF-IDF и BM25

Elasticsearch хранит индекс в 50 миллиардов документов и отвечает за 200 миллисекунд. BM25 - алгоритм 1994 года - до сих пор внутри. Не потому что не было времени заменить. Потому что ничто не сравнялось с ним по скорости на таком масштабе. BERT обрабатывает один документ за 10 мс. BM25 - за микросекунды. Понять почему эта 30-летняя формула всё ещё работает - значит понять архитектуру каждого современного поискового движка.

• **Elasticsearch** и **Apache Solr** используют BM25 как дефолтный алгоритм ранжирования для миллионов приложений
• **Amazon Product Search** комбинирует BM25 по title, description и reviews для ранжирования товаров
• **GitHub Code Search** использует field weighting: совпадение в имени файла весит больше, чем в содержимом

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

• Inverted Index

Robertson и рождение BM25

1994 год. Stephen Robertson и коллеги из City University London публикуют Okapi BM25 в рамках системы Okapi для конкурса TREC. BM расшифровывается как «Best Match» - вероятностная модель ранжирования. «25» - номер итерации формулы. До BM25 были BM1, BM11, BM15 - каждая версия исправляла проблемы предыдущей. TF насыщение (параметр k1) и нормализация по длине (параметр b) - ключевые улучшения над TF-IDF Карен Спарк Джонс 1972 года. Тридцать лет спустя BM25 остаётся default в Elasticsearch, Solr и практически каждой поисковой системе мира.

TF-IDF

Не все слова одинаково полезны для поиска. Слово «the» встречается в каждом английском документе - оно ничего не говорит о теме. А вот «квантовый» встречается редко и сразу сужает область. **TF-IDF** количественно выражает эту интуицию: вес слова растёт с частотой в документе (TF) и редкостью в коллекции (IDF).

На практике используют **сглаженный IDF**: `log(1 + N/df)` - чтобы избежать деления на ноль и слишком экстремальных весов. Также TF часто берут как `1 + log(TF)` - логарифмическое масштабирование, потому что 10 вхождений слова не в 10 раз полезнее одного.

TF-IDF - это не один алгоритм, а целое **семейство** вариантов. SMART notation описывает комбинации: `lnc.ltc` означает log TF + no IDF + cosine norm для документа, log TF + IDF + cosine norm для запроса. Всего десятки вариантов!

BM25

TF-IDF имеет проблемы: TF растёт линейно (документ со словом 100 раз получает в 100 раз больший вес, чем с 1 разом - это неправильно). **Okapi BM25** - вероятностная модель ранжирования, которая решает эти проблемы и остаётся золотым стандартом поиска уже 30 лет.

Параметр **k1** контролирует насыщение TF. При k1 = 0 вес не зависит от частоты (binary model). При k1 → ∞ BM25 приближается к линейному TF-IDF. Значение k1 = 1.2 означает: первые вхождения слова важны, но 100-е вхождение добавляет ничтожно мало.

Параметр **b** контролирует нормализацию по длине документа. При b = 0 длина не учитывается. При b = 1 длинные документы сильно штрафуются. Значение b = 0.75 - компромисс: длинный документ может быть релевантен, но длина не должна давать незаслуженное преимущество из-за большего числа слов.

Field Weighting

Реальные документы имеют структуру: заголовок, тело, URL, мета-описание. Слово в **заголовке** гораздо сильнее сигнализирует о теме документа, чем то же слово в тексте. **Field weighting** - присвоение разных весов разным полям документа.

**BM25F** (BM25 with Field weighting) - расширение BM25, которое вычисляет взвешенную сумму TF по полям. В Elasticsearch это реализуется через **multi_match** запрос с boost-параметрами:

**Anchor text** - текст гиперссылок, ведущих на страницу - особенно ценный сигнал. Если 1000 страниц ссылаются на сайт текстом «лучший курс Python», значит сайт вероятно об этом. Google активно использует anchor text для ранжирования.

Выбор boost-коэффициентов - эмпирическая задача. На практике их подбирают через **A/B-тесты** и **learning to rank**: обучают модель на размеченных данных (пары запрос-документ с оценкой релевантности), и модель находит оптимальные веса полей.

Document Length Normalization

Длинный документ содержит больше слов - и статистически больше шансов, что любое слово запроса в нём встретится. Без нормализации длинные документы будут несправедливо доминировать в результатах. **Document length normalization** - механизм компенсации этого эффекта.

В BM25 параметр **b** управляет степенью нормализации. При b = 1 длинные документы штрафуются максимально. При b = 0 длина игнорируется. Оптимальное b зависит от коллекции: для однородных документов (научные абстракты) b можно уменьшить, для разнородных (веб) - увеличить.

Существует альтернатива: **cosine normalization** (делим TF-IDF вектор на его длину). Используется в TF-IDF, но не в BM25. Ещё один подход - **pivoted document length normalization**: задаём «точку разворота» (pivot), документы короче неё получают бонус, длиннее - штраф.

Нормализация по длине - это лишь один аспект. Современные системы также учитывают **query length** (длинные запросы нужно обрабатывать иначе), **coordination factor** (бонус за совпадение большего количества слов запроса) и **proximity** (слова запроса близко друг к другу в документе - хороший знак).

Ключевые идеи

• **TF-IDF** = частота в документе × редкость в коллекции: редкие слова важнее частых
• **BM25** решает проблемы TF-IDF: насыщение TF (параметр k1) и нормализация по длине (параметр b)
• **Field weighting** (BM25F): слово в заголовке ×5 важнее, чем в тексте ×1
• Архитектура **retrieve-then-rerank**: BM25 быстро выбирает топ-1000, нейросети переранжируют

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

TF-IDF и BM25 связывают информационный поиск с машинным обучением и NLP:

• Инвертированный индекс — BM25 скоры вычисляются на основе TF и DF, хранимых в posting lists
• Введение в информационный поиск — BM25 - конкретная реализация концепции ранжирования из первого урока

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

• Почему в BM25 используется гармоническое ограничение TF вместо линейного? В каких случаях линейный TF мог бы быть лучше?
• Как подобрать параметры k1 и b для поисковой системы интернет-магазина (товары с коротким описанием vs отзывы)?
• Если BERT так хорош в понимании смысла, почему нельзя просто заменить BM25 на BERT для всех 100B документов?

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

• ir-02 — Инвертированный индекс хранит TF и DF для BM25 расчётов
• ir-01 — Базовые концепции IR: релевантность и ранжирование
• ir-04 — Vector space model и cosine similarity следуют из TF-IDF
• aie-13-advanced-rag — Hybrid search в RAG комбинирует BM25 с dense retrieval
• nlp-03 — NLP preprocessing: stemming, stopwords влияют на TF-IDF качество
• rec-03 — TF-IDF и matrix factorization оба ищут сигнал в разреженных данных
• stat-03-mle