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, в которой документ рассматривается как совокупность нескольких полей (таких как, например, заголовки, основной текст, ссылочный текст), длины которых независимо нормализуются, и каждому из которых может быть назначена своя степень значимости в итоговой функции ранжирования.

Примечания

Xapian: BM25 Weighting Scheme
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.

This article is issued from Wikipedia. The text is licensed under Creative Commons - Attribution - Sharealike. Additional terms may apply for the media files.

[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.