Okapi BM25

Материал из Википедии — свободной энциклопедии
Перейти к: навигация, поиск

В информационном поиске, Okapi BM25 — функция ранжирования, используемая поисковыми системами для упорядочивания документов по их релевантности данному поисковому запросу. Она основывается на вероятностной модели, разработанной в 1970-х и 1980-х годах Стивеном Робертсоном, Карен Спарк Джоунс и другими.

Сама функция носит название BM25 (BM от англ. best match), но её часто называют «Okapi BM25», по названию поисковой системы Okapi, созданной в Лондонском городском университете в 1980-х и 1990-х годах, в которой эта функция была впервые применена.

BM25 и его различные более поздние модификации (например, BM25F) представляют собой современные TF-IDF-подобные функции ранжирования, широко используемые на практике в поисковых системах. В веб-поиске эти функции ранжирования часто входят как компоненты более сложной, часто машинно-обученной, функции ранжирования.

Функция ранжирования[править | править исходный текст]

BM25 — поисковая функция на неупорядоченном множестве термов («мешке слов») и множестве документов, которые она оценивает на основе встречаемости слов запроса в каждом документе, без учёта взаимоотношений между ними (например, близости). Это не одна функция, а семейство функций с различными компонентами и параметрами. Одна из распространенных форм этой функции описана ниже.

Пусть дан запрос Q, содержащий слова q_1, ..., q_n, тогда функция 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 (1 - b + b \cdot \frac{|D|}{\text{avgdl}})},

где f(q_i, D) есть частота слова (англ. term frequency, TF) q_i в документе D, |D| есть длина документа (количество слов в нём), а avgdl — средняя длина документа в коллекции. k_1 и b — свободные коэффициенты, обычно их выбирают как k_1 = 2.0 и b = 0.75.

\text{IDF}(q_i) есть обратная документная частота (англ. inverse document frequency, IDF) слова q_i. Есть несколько толкований IDF и небольших вариации его формулы. Классически, она определяется как:

\log \frac{N}{n(q_i)},

где N есть общее количество документов в коллекции, а n(q_i) — количество документов, содержащих q_i. Но чаще применяются «сглаженные» варианты этой формулы, например:

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

Заметим, что вышеуказанная формула IDF имеет следующий недостаток. Для слов, входящих в более чем половину документов из коллекции, значение IDF отрицателно. Таким образом, при наличии любых двух почти идентичных документов, в одном из которых есть слово, а в другом — нет, второй может получить бо́льшую оценку.

Иными словами, частовстречающиеся слова испортят окончательную оценку документа. Это нежелательно, поэтому во многих приложениях вышеприведённая формула может быть скорректирована следующими способами:

  • Игнорировать вообще все отрицательные слагаемые в сумме (что эквивалентно занесению в стоп-лист и игнорированию всех соответствующих высокочастотных слов);
  • Налагать на IDF некоторую нижнюю границу \varepsilon: если IDF меньше \varepsilon, то считать её равной \varepsilon.
  • Использовать другую формулу IDF, не принимающую отрицательных значений.

Интерпретация IDF в теории информации[править | править исходный текст]

Положим, что поисковое слово q встречается в n(q) документах. Тогда случайно выбранный документ D содержит слово с вероятностью \frac{n(q)}{N} (где N есть мощность множества документов в коллекции). В таком случае информационная ценность фразы «D содержит q» будет такова:

-\log \frac{n(q)}{N} = \log \frac{N}{n(q)}.

Теперь положим, что имеется два поисковых слова q_1 и q_2. Если они входят в документ независимо друг от друга, то вероятность обнаружить их в случайно выбранном документе D такова:

\frac{n(q_1)}{N} \cdot \frac{n(q_2)}{N},

и содержание этого события

\sum_{i=1}^{2} \log \frac{N}{n(q_i)}.

Это примерно то, что выражается компонентой IDF в BM25.

Модификации[править | править исходный текст]

  • При экстремальных значениях коэффициента b в функции BM25 получаются функции ранжирования, известные под названиями BM11 (при b=1) и BM15 (при b=0).[1]
  • BM25F[2] — модификация BM25, в которой документ рассматривается как совокупность нескольких полей (таких как, например, заголовки, основной текст, ссылочный текст), длины которых независимо нормализуются, и каждому из которых может быть назначена своя степень значимости в итоговой функции ранжировании.

Примечания[править | править исходный текст]

  1. Xapian: BM25 Weighting Scheme
  2. Hugo Zaragoza, Nick Craswell, Michael Taylor, Suchi Saria, and Stephen Robertson. Microsoft Cambridge at TREC-13: Web and HARD tracks. In Proceedings of TREC-2004, 2004.

Литература[править | править исходный текст]

  • Stephen E. Robertson, Steve Walker, Susan Jones, Micheline Hancock-Beaulieu, and Mike Gatford. Okapi at TREC-3. In Proceedings of the Third Text REtrieval Conference (TREC 1994). Gaithersburg, USA, November 1994.
  • Stephen E. Robertson, Steve Walker, and Micheline Hancock-Beaulieu. Okapi at TREC-7. In Proceedings of the Seventh Text REtrieval Conference. Gaithersburg, USA, November 1998.
  • Karen Spärck Jones, Steve Walker, and Stephen E. Robertson. A Probabilistic Model of Information Retrieval: Development and Comparative Experiments (parts 1 and 2). Information Processing and Management, 36(6):779-840. 2000.
  • Nick Craswell, Hugo Zaragoza, Stephen Robertson. Microsoft Cambridge at TREC-14: Enterprise Track. In Proceedings of the Fourteenth Text REtrieval Conference (TREC 2005). Gaithersburg, USA, November 2005. Describes application and tuning of Okapi BM25F.

Ссылки[править | править исходный текст]