Okapi BM25

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

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

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

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

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

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

$\text{score}(D,Q)=\underset{i=1}{\overset{n}{\sum <!--\; \sum \; -->}}\text{IDF}(q_i)\cdot <!--\; \cdot \; -->\frac{f(q_i,D)\cdot <!--\; \cdot \; -->(k_1+1)}{f(q_i,D)+k_1\cdot <!--\; \cdot \; -->(1-<!--\; -\; -->b+b\cdot <!--\; \cdot \; -->\frac{|D|}{\text{avgdl}})},$${\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)$$f(q_{i},D)$  есть частота слова (англ. term frequency, TF) $q_i$$q_{i}$  в документе $D$$D$ , $|D|$$|D|$  есть длина документа (количество слов в нём), а $avgdl$$avgdl$  — средняя длина документа в коллекции. $k_1$$k_{1}$  и $b$$b$  — свободные коэффициенты, обычно их выбирают как $k_1=2.0$$k_{1}=2.0$  и $b=0.75$$b=0.75$ .

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

$\log <!--\; \; -->\frac{N}{n(q_i)},$$\log {\frac {N}{n(q_{i})}},$ 

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

$\text{IDF}(q_i)=\log <!--\; \; -->\frac{N-<!--\; -\; -->n(q_i)+0.5}{n(q_i)+0.5},$${\text{IDF}}(q_{i})=\log {\frac {N-n(q_{i})+0.5}{n(q_{i})+0.5}},$ 

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

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

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

Интерпретация IDF в теории информацииПравить

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

$-<!--\; -\; -->\log <!--\; \; -->\frac{n(q)}{N}=\log <!--\; \; -->\frac{N}{n(q)}.$$-\log {\frac {n(q)}{N}}=\log {\frac {N}{n(q)}}.$ 

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

$\frac{n(q_1)}{N}\cdot <!--\; \cdot \; -->\frac{n(q_2)}{N},$${\frac {n(q_{1})}{N}}\cdot {\frac {n(q_{2})}{N}},$ 

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

$\underset{i=1}{\overset{2}{\sum <!--\; \sum \; -->}}\log <!--\; \; -->\frac{N}{n(q_i)}.$$\sum _{{i=1}}^{{2}}\log {\frac {N}{n(q_{i})}}.$ 

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

МодификацииПравить

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

ЛитератураПравить

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