BM25

BM25 (Best Matching 25) — это вероятностная модель ранжирования документов, используемая в информационном поиске для оценки релевантности документа поисковому запросу. Относится к классу функций ранжирования (ранжирующих функций), которые вычисляют числовую оценку (score) соответствия между текстом запроса и текстом документа. BM25 является развитием модели вероятностного взвешивания терминов (Probabilistic Relevance Model) и на протяжении длительного времени служит эталоном (baseline) для задач текстового поиска, а также входит в состав многих современных поисковых систем, включая Apache Lucene, Elasticsearch и OpenSearch.

История

Модель BM25 была разработана в 1970–1980-х годах в рамках исследований в области вероятностного информационного поиска. Основной вклад внесли британские учёные Стивен Робертсон (Stephen Robertson) и Карен Спарк Джонс (Karen Spärck Jones), работавшие в City University London. В 1976 году Робертсон и Спарк Джонс предложили вероятностную модель ранжирования (Probabilistic Relevance Model), основанную на принципе «вероятность релевантности» (Probability Ranking Principle). В 1994 году Робертсон, Уокер и Хэнкок-Бьюли опубликовали работу, в которой была формализована функция BM25, получившая название «Best Match 25» (где 25 — номер версии в серии экспериментов). Впоследствии модель была доработана и получила название Okapi BM25 (по названию экспериментальной поисковой системы Okapi, разработанной в City University London).

С 2000-х годов BM25 стала стандартной функцией ранжирования в системах полнотекстового поиска, а также вошла в состав библиотек для обработки естественного языка (NLTK, gensim, scikit-learn). В 2010-х годах появились модификации BM25, такие как BM25F (для полей документов с разными весами) и BM25+ (с дополнительным сглаживанием).

Формула и принцип работы

BM25 вычисляет оценку релевантности документа \(D\) для запроса \(Q\) как сумму весов по каждому термину запроса, входящему в документ. Базовая формула имеет вид:

\[ \text{score}(D, Q) = \sum_{i=1}^{n} \text{IDF}(q_i) \cdot \frac{f(q_i, D) \cdot (k_1 + 1)}{f(q_i, D) + k_1 \cdot \left(1 - b + b \cdot \frac{|D|}{\text{avgdl}}\right)} \]

где:

• \(q_i\) — i-й термин запроса;
• \(f(q_i, D)\) — частота термина в документе (TF);
• \(|D|\) — длина документа (в словах);
• \(\text{avgdl}\) — средняя длина документа в коллекции;
• \(k_1\) и \(b\) — параметры настройки (обычно \(k_1 \in [1.2, 2.0]\), \(b \in [0.5, 0.8]\));
• \(\text{IDF}(q_i)\) — обратная документная частота термина.

Компоненты формулы

1. Частота термина (TF) — учитывает, сколько раз термин встречается в документе. В BM25 используется нелинейное насыщение: при увеличении TF рост оценки замедляется, что предотвращает доминирование очень частых терминов.
2. Длина документа — нормализация по длине: длинные документы имеют больше шансов содержать термин, поэтому их оценка корректируется вниз. Параметр \(b\) управляет степенью этой нормализации (при \(b=0\) нормализация отключается).
3. Обратная документная частота (IDF) — отражает, насколько термин редок в коллекции. Чем реже термин встречается, тем выше его вес. В классической реализации BM25 используется формула IDF Робертсона-Спарк Джонс:

\[ \text{IDF}(q_i) = \log \frac{N - n(q_i) + 0.5}{n(q_i) + 0.5} \]

где \(N\) — общее количество документов, \(n(q_i)\) — количество документов, содержащих термин.

Параметры и настройка

BM25 имеет два основных параметра:

• \(k_1\) — управляет насыщением TF. Значение \(k_1 = 0\) эквивалентно бинарной модели (TF не учитывается). Типичные значения: 1.2–2.0.
• \(b\) — степень нормализации длины документа. При \(b = 0\) длина не учитывается, при \(b = 1\) — нормализация максимальна. Типичные значения: 0.5–0.8.

Подбор параметров осуществляется эмпирически на основе метрик качества поиска (например, NDCG, MAP) с использованием коллекций тестовых запросов (TREC, CLEF, MIRACL). Для русского языка оптимальные значения могут отличаться из-за особенностей морфологии и длины слов.

Разновидности

BM25F (Fielded BM25)

Расширение BM25 для документов, состоящих из нескольких полей (например, заголовок, аннотация, основной текст). Каждому полю назначается свой вес, а TF нормализуется по длине поля. Применяется в системах, где структура документа важна (веб-поиск, поиск по документам с метаданными).

BM25+ (Plus)

Модификация, предложенная в 2011 году, добавляет константу \(\delta\) (обычно 0.5–1.0) к TF для предотвращения нулевых оценок у коротких документов. Улучшает качество ранжирования на коллекциях с большим разбросом длин документов.

BM25L (L — Lower bound)

Версия, в которой IDF вычисляется с использованием логарифмического сглаживания, что снижает влияние очень редких терминов.

Применение

BM25 широко применяется в следующих областях:

• Поисковые системы — Apache Lucene, Elasticsearch, OpenSearch, Sphinx, Meilisearch (в модифицированном виде).
• Библиотеки для информационного поиска — Whoosh, Rank-BM25 (Python), Terrier.
• Обработка естественного языка — в задачах извлечения ключевых слов (например, YAKE!), поиска ответов на вопросы, реферирования текста.
• Рекомендательные системы — для поиска похожих документов по текстовому содержанию.
• Анализ тональности — как часть пайплайна для фильтрации релевантных текстов.

В России BM25 используется в поисковых системах Яндекса (в составе внутренних алгоритмов, хотя точная реализация не раскрывается), а также в корпоративных системах поиска (например, в «КонсультантПлюс» и «Гарант»).

Преимущества и недостатки

Преимущества

• Высокая эффективность при низких вычислительных затратах — не требует обучения на больших данных.
• Хорошо работает на небольших и средних коллекциях (до нескольких миллионов документов).
• Прозрачность и интерпретируемость — каждый компонент формулы имеет интуитивное объяснение.
• Надёжность — BM25 редко даёт сбои по сравнению с более сложными нейросетевыми моделями.

Недостатки

• Не учитывает семантику слов (синонимы, многозначность) — работает только на уровне лексического совпадения.
• Чувствителен к качеству токенизации и стемминга/лемматизации.
• Параметры \(k_1\) и \(b\) требуют ручной настройки под конкретную коллекцию.
• Неэффективен для очень больших коллекций (более 100 миллионов документов) без дополнительной индексации.

Сравнение с другими моделями

BM25 остаётся стандартом для задач, где важна скорость и предсказуемость, а также используется как baseline при оценке новых методов.

Интересные факты

• Название «Okapi BM25» происходит от поисковой системы Okapi, разработанной в City University London. «Okapi» — это название африканского животного (окапи), а «BM25» — номер версии модели.
• BM25 входит в состав стандарта ANSI/NISO Z39.50 для информационного поиска.
• В 2020 году компания Elasticsearch заменила TF-IDF на BM25 в качестве функции ранжирования по умолчанию, что подтвердило её статус индустриального стандарта.
• Существует реализация BM25 на языке SQL, позволяющая выполнять полнотекстовый поиск непосредственно в реляционных базах данных (например, в PostgreSQL через расширение pg_bm25).

Источники

• Robertson, S. E., & Sparck Jones, K. (1976). Relevance weighting of search terms. Journal of the American Society for Information Science, 27(3), 129–146.
• Robertson, S. E., Walker, S., & Hancock-Beaulieu, M. (1994). Okapi at TREC-3. Proceedings of the Third Text REtrieval Conference (TREC-3).
• Robertson, S. E., & Zaragoza, H. (2009). The Probabilistic Relevance Framework: BM25 and Beyond. Foundations and Trends in Information Retrieval, 3(4), 333–389.
• Manning, C. D., Raghavan, P., & Schütze, H. (2008). Introduction to Information Retrieval. Cambridge University Press.