BM25

2018-10-09T14:31:43+00:00

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

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

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

Функция ранжирования

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

Пусть дан запрос {\displaystyle Q}, содержащий слова {\displaystyle q_{1},…,q_{n}}, тогда функция BM25 даёт следующую оценку релевантности документа {\displaystyle D} запросу {\displaystyle Q}:

{\displaystyle {\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}}})}},}

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

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

{\displaystyle \log {\frac {N}{n(q_{i})}},}

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

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

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

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

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