Okapi BM25

Okapi BM25 (Best Matching 25) — это вероятностная модель ранжирования документов, используемая в информационном поиске для оценки релевантности документа поисковому запросу. Алгоритм является развитием модели бинарного независимого ранжирования (BIR) и семейства функций BM (Best Matching), разработанных в 1970–1980-х годах группой исследователей под руководством Стивена Робертсона и Карен Спарк Джонс в рамках проекта Okapi в Лондонском университетском колледже. BM25 широко применяется в поисковых системах, библиотечных системах и системах обработки естественного языка благодаря своей эффективности и простоте реализации.

История

Разработка модели BM25 началась в 1970-х годах в рамках проекта Okapi, финансируемого Британской библиотекой. Изначально алгоритм создавался для поиска в текстовых коллекциях, таких как каталоги библиотек и научные статьи. Первая версия, BM1, была предложена в 1976 году, но она имела ограничения, связанные с учётом длины документа. В 1994 году Стивен Робертсон и его коллеги представили BM25, который объединил вероятностный подход с эвристическими поправками на частоту терминов и длину документа. Название «Best Matching 25» происходит от номера версии в серии экспериментов — 25-я итерация алгоритма, показавшая наилучшие результаты на тестовых коллекциях TREC (Text REtrieval Conference). С тех пор BM25 стал стандартом де-факто для оценки релевантности в информационном поиске, уступая лишь более сложным моделям на основе нейронных сетей, появившимся в 2010-х годах.

Основные принципы

BM25 основан на вероятностной модели, оценивающей вероятность того, что документ релевантен запросу, при условии наблюдаемых частот терминов. В отличие от простых моделей, таких как TF-IDF, BM25 учитывает насыщение частоты термина (term frequency saturation) и нормализацию длины документа. Ключевая идея заключается в том, что многократное повторение одного и того же термина в документе не линейно увеличивает его релевантность — после определённого порога каждое новое вхождение даёт всё меньший прирост. Аналогично, длинные документы не должны получать преимущество только за счёт большего количества слов.

Формула

Основная формула BM25 для оценки релевантности документа \( D \) запросу \( Q \) из \( n \) терминов \( q_1, q_2, \dots, q_n \) имеет вид:

\[ \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)} \]

где:

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

Компонент IDF (Inverse Document Frequency) вычисляется по формуле:

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

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

Параметры

• \( k_1 \) — параметр насыщения частоты термина. При \( k_1 = 0 \) модель игнорирует частоту термина (только бинарное вхождение). При больших значениях \( k_1 \) частота термина влияет сильнее, но с насыщением.
• \( b \) — параметр нормализации длины документа. При \( b = 0 \) длина документа не учитывается; при \( b = 1 \) нормализация максимальна. Обычно \( b = 0.75 \) даёт наилучшие результаты на большинстве коллекций.

Варианты и модификации

Существует несколько модификаций BM25, адаптированных для разных задач:

• BM25F — расширение для структурированных документов (например, веб-страниц с заголовками, метаданными и основным текстом). Позволяет задавать разные веса для разных полей документа.
• BM25+ — модификация, вводящая нижнюю границу для частоты термина, чтобы избежать нулевых оценок для редких терминов.
• Okapi BM25 — оригинальная версия, используемая в проекте Okapi. Включает дополнительные эвристики, такие как учёт длины запроса.
• BM25L — вариант, оптимизированный для длинных документов, где стандартная нормализация может быть недостаточной.
• BM25-adpt — адаптивная версия, где параметры \( k_1 \) и \( b \) подбираются автоматически на основе статистики коллекции.

Применение

BM25 широко используется в различных областях информационного поиска:

• Поисковые системы: многие открытые поисковые движки, такие как Apache Lucene, Elasticsearch и Solr, используют BM25 в качестве алгоритма ранжирования по умолчанию (начиная с Lucene 6.0, 2016 год). В коммерческих системах, таких как Google, BM25 применяется как один из компонентов в гибридных моделях.
• Библиотечные системы: системы электронного каталога (OPAC) и цифровые библиотеки (например, Project Gutenberg) используют BM25 для поиска по метаданным и полным текстам.
• Обработка естественного языка: BM25 применяется в задачах извлечения информации, вопросно-ответных системах (например, в модели Dense Passage Retrieval для предварительного отбора кандидатов) и суммаризации текстов.
• Рекомендательные системы: BM25 используется для поиска похожих документов или товаров на основе текстовых описаний.

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

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

• Простота и скорость: BM25 требует только подсчёта частот терминов и статистики коллекции, что позволяет обрабатывать миллионы документов за миллисекунды.
• Интерпретируемость: результаты легко объяснить через частоту терминов и длину документа.
• Эффективность: на большинстве тестовых коллекций (например, TREC, MS MARCO) BM25 показывает результаты, сопоставимые с простыми нейросетевыми моделями.

Недостатки

• Отсутствие семантики: BM25 не учитывает синонимию, многозначность или контекстные отношения между словами. Например, запрос «автомобиль» не найдёт документы, содержащие только слово «машина».
• Чувствительность к параметрам: значения \( k_1 \) и \( b \) требуют настройки под конкретную коллекцию, что может быть трудоёмким.
• Проблема длинных документов: при очень больших документах нормализация длины может быть недостаточной, что приводит к завышению оценок.

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

• TF-IDF: BM25 является эволюцией TF-IDF, добавляя насыщение частоты и нормализацию длины. На стандартных коллекциях BM25 обычно превосходит TF-IDF на 5–15% по метрикам MAP (Mean Average Precision) и NDCG (Normalized Discounted Cumulative Gain).
• Language Models: вероятностные языковые модели (например, модель Дирхле) иногда дают лучшие результаты на коротких запросах, но BM25 более устойчив к шуму в данных.
• Нейросетевые модели: современные модели на основе трансформеров (например, BERT) значительно превосходят BM25 по качеству, но требуют на порядок больше вычислительных ресурсов. BM25 часто используется как «базовый уровень» (baseline) или для предварительного отбора кандидатов в гибридных системах.

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

• Название «Okapi» происходит от названия проекта, который, в свою очередь, был назван в честь животного окапи — редкого лесного жирафа, символизирующего редкость и уникальность информации.
• В 2018 году команда Google предложила модель BM25F для ранжирования веб-страниц, что улучшило качество поиска на 3–5% по сравнению со стандартным BM25.
• BM25 остаётся стандартом в академических исследованиях информационного поиска: на конференциях SIGIR и CIKM большинство новых методов сравниваются именно с ним.

Источники

• 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.
• Trotman, A., Puurula, A., & Burgess, B. (2014). Improvements to BM25 and Language Models Examined. Proceedings of the 2014 Australasian Document Computing Symposium.
• Документация Apache Lucene: BM25 Similarity.