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

Материал из MachineLearning.

Статья написана с использованием LLM Gemini Pro 3.1 и проверена участником Nikita Zinoviсh 19:08, 18 июля 2026 (MSD)

Содержание

1 Формальная постановка задачи информационного поиска
2 Вероятностная модель ранжирования
3 Бинарная модель независимости (BIM)
- 3.1 Вывод функции веса термина
- 3.2 Аппроксимация вероятностей и IDF
4 Ограничения BIM и двухпуассоновская модель (2-Poisson)
- 4.1 Функция насыщения частоты
5 Нормализация по длине документа
6 Финальная математическая модель BM25
7 См. также
8 Литература

Формальная постановка задачи информационного поиска

В основе алгоритма BM25 лежит вероятностная модель информационного поиска. Пусть задана конечная коллекция документов $D_j \in \mathcal{D}$ объемом $N$ и пользовательский запрос $Q$ . Словарь коллекции (множество всех уникальных терминов) обозначим как $V$ .

Введем бинарную целевую случайную величину релевантности $R \in \{0, 1\}$ , где событие $R = 1$ означает, что документ удовлетворяет информационную потребность пользователя (релевантен), а $R = 0$ — не удовлетворяет.

Математическая задача ранжирования сводится к сортировке множества $\mathcal{D}$ по убыванию апостериорной вероятности $P(R=1 \mid D, Q)$ .

Вероятностная модель ранжирования

Согласно принципу вероятностного ранжирования (Probabilistic Ranking Principle), монотонное преобразование функции ранжирования не меняет порядка документов. Поэтому вместо вычисления самой вероятности вычисляется отношение шансов (odds ratio).

Применяя теорему Байеса к числителю и знаменателю, получаем:

$O(R \mid D, Q) = \frac{P(R=1 \mid D, Q)}{P(R=0 \mid D, Q)} = \frac{P(D \mid R=1, Q) P(R=1 \mid Q)}{P(D \mid R=0, Q) P(R=0 \mid Q)}$

Поскольку априорные шансы $\frac{P(R=1 \mid Q)}{P(R=0 \mid Q)}$ являются константой для данного запроса и не зависят от конкретного документа $D$ , их можно отбросить. Для вычислительной устойчивости и перевода умножения в сложение ранжирующую функцию (Retrieval Status Value, RSV) определяют как логарифм отношения правдоподобий:

$\mathrm{RSV} \propto \log \frac{P(D \mid R=1, Q)}{P(D \mid R=0, Q)}$

Бинарная модель независимости (BIM)

Для вычисления $P(D \mid R, Q)$ используется Бинарная модель независимости. Документ $D$ представляется как вектор инцидентности $\mathbf{x} = (x_1, x_2, \dots, x_{|V|})$ , где $x_i \in \{0, 1\}$ показывает присутствие ( $1$ ) или отсутствие ( $0$ ) термина $i$ в документе.

Вводится сильное предположение об условной независимости признаков (аналогично наивному байесовскому классификатору):

$P(D \mid R, Q) = \prod_{i=1}^{|V|} P(x_i \mid R, Q)$

Вывод функции веса термина

Обозначим вероятности появления термина в релевантных и нерелевантных документах как:

$p_i = P(x_i=1 \mid R=1, Q), \quad q_i = P(x_i=1 \mid R=0, Q)$

Тогда вероятность генерации документа принимает вид:

$P(D \mid R=1, Q) = \prod_{i=1}^{|V|} p_i^{x_i} (1-p_i)^{1-x_i}$

$P(D \mid R=0, Q) = \prod_{i=1}^{|V|} q_i^{x_i} (1-q_i)^{1-x_i}$

Подставим это в функцию RSV:

$\mathrm{RSV} = \log \prod_{i=1}^{|V|} \frac{p_i^{x_i} (1-p_i)^{1-x_i}}{q_i^{x_i} (1-q_i)^{1-x_i}}$

Перегруппируем множители, умножив и разделив выражение под произведением на $(1-p_i)^{x_i}$ и $(1-q_i)^{x_i}$ :

$\mathrm{RSV} = \log \prod_{i=1}^{|V|} \left( \frac{p_i (1-q_i)}{q_i (1-p_i)} \right)^{x_i} \left( \frac{1-p_i}{1-q_i} \right)$

Разделим логарифм произведения на сумму логарифмов:

$\mathrm{RSV} = \sum_{i=1}^{|V|} x_i \log \frac{p_i (1-q_i)}{q_i (1-p_i)} + \sum_{i=1}^{|V|} \log \frac{1-p_i}{1-q_i}$

Второе слагаемое является константой для всех документов (зависит только от свойств запроса и коллекции), поэтому его можно исключить. Поскольку $x_i = 0$ для терминов, отсутствующих в документе, и мы предполагаем, что для терминов вне запроса $Q$ выполняется $p_i = q_i$ , итоговая сумма вычисляется только по терминам запроса:

$\mathrm{RSV} = \sum_{i \in Q, x_i=1} \log \frac{p_i (1-q_i)}{q_i (1-p_i)} = \sum_{i \in Q, x_i=1} w_i$

Аппроксимация вероятностей и IDF

Для вычисления веса $w_i$ требуются оценки $p_i$ и $q_i$ . Пусть в коллекции из $N$ документов известно $R$ релевантных. Термин $i$ встречается в $n_i$ документах всей коллекции и в $r_i$ релевантных документах. Применяя сглаживание по правилу Халдейна (прибавление $0.5$ ), получаем:

$p_i = \frac{r_i + 0.5}{R + 1}, \quad q_i = \frac{n_i - r_i + 0.5}{N - R + 2}$

В ситуации первичного поиска (ad-hoc retrieval), когда информация о релевантности отсутствует ( $R=0, r_i=0$ ), принимается допущение, что термин с равной вероятностью может встретиться в релевантном документе ( $p_i = 0.5$ ). Вероятность $q_i$ оценивается как доля документов с термином во всей коллекции. Подставляя эти значения в $w_i$ , получаем классическую формулу обратной частоты документа (Inverse Document Frequency):

$\mathrm{IDF}_i = \log \frac{0.5 \cdot (N - n_i + 0.5)}{0.5 \cdot (n_i + 0.5)} = \log \frac{N - n_i + 0.5}{n_i + 0.5}$

Ограничения BIM и двухпуассоновская модель (2-Poisson)

BIM оперирует бинарными векторами, теряя информацию о частоте термина в документе (Term Frequency, $\mathrm{tf}$ ). Для строгого моделирования $\mathrm{tf}$ исследователи (в частности, С. Робертсон) обратились к модели элитных множеств.

Предполагается существование скрытой переменной элитности $E_i \in \{0, 1\}$ . Если документ «элитен» по отношению к термину $i$ (то есть действительно посвящен этой теме), то частота термина моделируется распределением Пуассона с высоким математическим ожиданием $\lambda_1$ . Для неэлитных документов используется $\lambda_2$ , причем $\lambda_1 \gg \lambda_2$ . Априорная вероятность элитности равна $\pi$ . Распределение частоты описывается смесью:

$P(\mathrm{tf}_i = k) = \pi \frac{e^{-\lambda_1} \lambda_1^k}{k!} + (1-\pi) \frac{e^{-\lambda_2} \lambda_2^k}{k!}$

Функция насыщения частоты

Байесовский вывод весовых коэффициентов из этой смеси приводит к сложным нелинейным уравнениям. Для практического применения была выведена асимптотическая аппроксимация — функция насыщения (TF saturation).

В отличие от векторной модели TF-IDF, где вес термина растет линейно или логарифмически, в BM25 вес асимптотически стремится к пределу:

$S(\mathrm{tf}_i) = \frac{\mathrm{tf}_i}{\mathrm{tf}_i + k_1}$

где гиперпараметр $k_1 \ge 0$ контролирует скорость насыщения. Первое вхождение слова (переход от $0$ к $1$ ) дает наибольший прирост функции. При $\mathrm{tf}_i \to \infty$ значение функции стремится к $1$ .

Нормализация по длине документа

Функция насыщения должна учитывать длину документа. Существуют две конфликтующие гипотезы: 1. Гипотеза многословности (Verbosity): Длинный документ содержит те же понятия, что и короткий, но описывает их бо́льшим числом слов. В этом случае абсолютная частота $\mathrm{tf}$ должна быть жестко нормирована. 2. Гипотеза многотемности (Scope): Длинный документ охватывает больше независимых тем. Нормировка должна быть минимальной, так как совпадение термина — независимое событие в рамках новой темы.

Для баланса в BM25 вводится параметр $b \in [0, 1]$ . Параметр $k_1$ масштабируется множителем длины $B$ :

$B = 1 - b + b \cdot \frac{|D|}{\mathrm{avdl}}$

где $|D|$ — длина текущего документа в словах, $\mathrm{avdl}$ (average document length) — средняя длина документа в корпусе. Подстановка $B$ в знаменатель функции насыщения дает:

$S'(\mathrm{tf}_i) = \frac{\mathrm{tf}_i}{\mathrm{tf}_i + k_1 \cdot \left(1 - b + b \cdot \frac{|D|}{\mathrm{avdl}}\right)}$

При $b=1$ применяется полная нормализация (документы считаются многословными), при $b=0$ нормализация отключается (документы считаются многотемными).

Финальная математическая модель BM25

Сборка всех вероятностных компонентов — логарифма отношения шансов (IDF), функции насыщения частоты термина в документе и опциональной функции частоты термина в самом запросе ( $\mathrm{qtf}_i$ ) — дает итоговое уравнение семейства Okapi BM25:

$\mathrm{RSV}(D, Q) = \sum_{i \in Q} \mathrm{IDF}_i \cdot \frac{\mathrm{tf}_i \cdot (k_1 + 1)}{\mathrm{tf}_i + k_1 \cdot \left(1 - b + b \cdot \frac{|D|}{\mathrm{avdl}}\right)} \cdot \frac{\mathrm{qtf}_i \cdot (k_3 + 1)}{\mathrm{qtf}_i + k_3}$

Множители $(k_1 + 1)$ и $(k_3 + 1)$ в числителях выступают в роли нормировочных констант, не влияющих на относительный порядок ранжирования, но обеспечивающих предел насыщения функции, равный $1$ (до умножения на IDF). Для коротких пользовательских запросов, где слова встречаются по одному разу ( $\mathrm{qtf}_i = 1$ ), третий множитель тождественно равен единице и часто опускается в программных реализациях.

См. также

Литература

Robertson, S., Zaragoza, H. The Probabilistic Relevance Framework: BM25 and Beyond. — Foundations and Trends in Information Retrieval, 2009.
Manning, C. D., Raghavan, P., Schütze, H. Introduction to Information Retrieval. — Cambridge University Press, 2008.
Sparck Jones, K., Walker, S., Robertson, S. E. A probabilistic model of information retrieval: development and comparative experiments. — Information Processing & Management, 2000.
Baeza-Yates, R., Ribeiro-Neto, B. Modern Information Retrieval: The Concepts and Technology behind Search (2nd Edition). — Addison-Wesley, 2011.

Источник — «http://poligon.machinelearning.ru/wiki/index.php?title=%D0%90%D0%BB%D0%B3%D0%BE%D1%80%D0%B8%D1%82%D0%BC_%D0%B8%D0%BD%D1%84%D0%BE%D1%80%D0%BC%D0%B0%D1%86%D0%B8%D0%BE%D0%BD%D0%BD%D0%BE%D0%B3%D0%BE_%D0%BF%D0%BE%D0%B8%D1%81%D0%BA%D0%B0_BM25»