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

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

(Различия между версиями)
Перейти к: навигация, поиск

Nikita Zinoviсh (Обсуждение | вклад)
(Новая: {{well|Статья написана с использованием LLM '''Gemini Pro 3.1''' и проверена участником ~~~~}} == Формальная постановк...)
К следующему изменению →

Версия 15:06, 18 июля 2026

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


Содержание

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

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

Цель вероятностной модели — отранжировать документы по убыванию условной вероятности P(R=1 \mid D, Q) .

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

Согласно принципу вероятностного ранжирования, вместо самой вероятности удобно использовать отношение шансов (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)}

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

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

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

Для вычисления условных вероятностей документа применяется Бинарная модель независимости (Binary Independence Model). Документ D и запрос Q представляются как векторы в V -мерном пространстве словаря коллекции, где x_i \in \{0, 1\} отражает присутствие или отсутствие i -го термина.

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

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

Тогда формула RSV разбивается на сумму по терминам запроса (термины, отсутствующие в запросе, сокращаются):

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

где p_i = P(x_i=1 \mid R=1) — вероятность появления термина в релевантных документах, а q_i = P(x_i=1 \mid R=0) — в нерелевантных.

При отсутствии априорной информации о релевантности документов (в начале поиска), предполагается, что p_i постоянно для всех терминов (например, 0.5 ), а q_i аппроксимируется долей документов, содержащих термин во всей коллекции. Пусть N — общее число документов, а \mathrm{df}_i — число документов, содержащих термин i . Тогда q_i \approx \frac{\mathrm{df}_i}{N} , и мы получаем классическую формулу Inverse Document Frequency (IDF):

\mathrm{IDF}_i = \log \frac{N - \mathrm{df}_i + 0.5}{\mathrm{df}_i + 0.5}

Ограничения BIM и учет частоты терминов (TF)

Главный недостаток BIM — бинарность вектора, игнорирующая частоту термина (Term Frequency, TF). Для учета многократного вхождения термина используется модель элитных множеств на основе распределения Пуассона (2-Poisson model).

В отличие от линейного учета частоты, BM25 вводит нелинейную функцию «насыщения» (TF saturation). Суть в том, что первое появление слова в тексте несет огромный сигнал, а разница между десятым и одиннадцатым вхождениями минимальна. Функция насыщения имеет вид:

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

где \mathrm{tf}_i — частота термина i в документе, а k_1 \ge 0 — эмпирический гиперпараметр, регулирующий скорость насыщения. При k_1 \to 0 модель вырождается в бинарную, а при k_1 \to \infty стремится к линейному учету частоты.

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

Вероятность встретить термин возрастает в длинных текстах. Существуют две гипотезы о длинных документах: гипотеза «многословности» (verbosity) и гипотеза «многотемности» (scope). BM25 использует параметр b \in [0, 1] для гибкой интерполяции нормализации длины документа.

Вводится штрафной множитель длины:

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

где |D| — длина текущего документа, \mathrm{avdl} — средняя длина документа в коллекции. Параметр k_1 в функции насыщения заменяется на k_1 \cdot 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)}

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

Объединяя логарифм отношения шансов из BIM, пуассоновское насыщение частоты и нормализацию длины, получаем итоговое уравнение функции ранжирования 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)}

Дополнительный множитель (k_1 + 1) в числителе введен исключительно для удобства масштабирования: таким образом асимптотический предел функции насыщения при \mathrm{tf}_i \to \infty равен 1 (до умножения на IDF).

Эта математически обоснованная комбинация весов оказалась настолько надежной, что остается индустриальным стандартом (baseline) для лексического поиска, обеспечивая строгий баланс между редкостью слова, его частотой в документе и размером самого документа.

См. также

Литература

  • 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.
Источник — «http://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»
Личные инструменты