Окапи БМ25

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

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

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

BM25 — это функция поиска пакетов слов , которая ранжирует набор документов на основе терминов запроса, встречающихся в каждом документе, независимо от их близости внутри документа. Это семейство скоринговых функций с несколько разными компонентами и параметрами. Одна из наиболее известных реализаций функции выглядит следующим образом.

Дан запрос Q , содержащий ключевые слова $q_{1},...,q_{n}$, оценка BM25 документа D равна:

${\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 \left(1-b+b\cdot {\frac {|D|}{\text{avgdl}}}\right)}}$

где $f(q_{i},D)$ это количество раз, когда ключевое слово $q_{i}$ встречается в документе D , $|D|$ — длина документа D в словах, а avgdl — средняя длина документа в текстовой коллекции, из которой извлекаются документы. $k_{1}$ и b — свободные параметры, обычно выбираемые при отсутствии расширенной оптимизации, как $k_{1}\in [1.2,2.0]$ и $b=0.75$. ${\text{IDF}}(q_{i})$ вес IDF ( обратная частота документов ) термина запроса $q_{i}$. Обычно он рассчитывается как:

${\text{IDF}}(q_{i})=\ln \left({\frac {N-n(q_{i})+0.5}{n(q_{i})+0.5}}+1\right)$

где N — общее количество документов в коллекции, а $n(q_{i})$ количество документов, содержащих $q_{i}$.

Существует несколько интерпретаций IDF и небольшие вариации ее формулы. В исходной версии BM25 компонент 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}$. Если два термина встречаются в документах совершенно независимо друг от друга, то вероятность увидеть оба $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})}}.$

С небольшими вариациями именно это и выражает компонент ЦАХАЛа БМ25.

Модификации

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

• БМ25+ является расширением BM25. BM25+ был разработан для устранения одного недостатка стандарта BM25, в котором компонент нормализации частоты терминов по длине документа не имеет должным образом нижнего ограничения; В результате этого недостатка длинные документы, которые действительно соответствуют термину запроса, часто могут быть несправедливо оценены BM25 как имеющие аналогичную релевантность с более короткими документами, которые вообще не содержат термин запроса. Формула подсчета очков BM25+ имеет только один дополнительный свободный параметр. $\delta$ (значение по умолчанию — 1,0 при отсутствии данных обучения) по сравнению с BM25:

${\text{score}}(D,Q)=\sum _{i=1}^{n}{\text{IDF}}(q_{i})\cdot \left[{\frac {f(q_{i},D)\cdot (k_{1}+1)}{f(q_{i},D)+k_{1}\cdot \left(1-b+b\cdot {\frac {|D|}{\text{avgdl}}}\right)}}+\delta \right]$

Общие ссылки

• Стивен Э. Робертсон; Стив Уокер; Сьюзан Джонс; Мишлин Хэнкок-Болье и Майк Гэтфорд (ноябрь 1994 г.). Окапи на ТРЭК-3 . Материалы Третьей конференции по поиску текста (TREC 1994) . Гейтерсберг, США.
• Стивен Э. Робертсон; Стив Уокер и Мишлин Хэнкок-Болье (ноябрь 1998 г.). Окапи на ТРЭК-7 . Материалы седьмой конференции по текстовому поиску . Гейтерсберг, США.
• Сперк Джонс, К .; Уокер, С.; Робертсон, SE (2000). «Вероятностная модель поиска информации: Разработка и сравнительные эксперименты: Часть 1». Обработка информации и управление . 36 (6): 779–808. CiteSeerX   10.1.1.134.6108 . дои : 10.1016/S0306-4573(00)00015-7 .
• Сперк Джонс, К .; Уокер, С.; Робертсон, SE (2000). «Вероятностная модель поиска информации: Разработка и сравнительные эксперименты: Часть 2». Обработка информации и управление . 36 (6): 809–840. дои : 10.1016/S0306-4573(00)00016-9 .
• Стивен Робертсон и Уго Сарагоса (2009). «Структура вероятностной релевантности: BM25 и далее» . Основы и тенденции в области информационного поиска . 3 (4): 333–389. CiteSeerX   10.1.1.156.5282 . дои : 10.1561/1500000019 . S2CID   207178704 .

Внешние ссылки

• Робертсон, Стивен ; Сарагоса, Уго (2009). Модель вероятностной релевантности: BM25 и далее (PDF) . СЕЙЧАС Publishers, Inc. ISBN  978-1-60198-308-4 .