Окапи BM25

Функция ранжирования, используемая поисковыми системами

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

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

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

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

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

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

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

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

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

Существует несколько интерпретаций IDF и небольшие вариации его формулы. В оригинальном выводе BM25 компонент IDF выводится из модели двоичной независимости .

Информационно-теоретическая интерпретация IDF

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

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

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

${\displaystyle {\frac {n(q_{1})}{N}}\cdot {\frac {n(q_{2})}{N}},}$

и информационное содержание такого события:

${\displaystyle \sum _{i=1}^{2}\log {\frac {N}{n(q_{i})}}.}$

С небольшими вариациями это именно то, что выражает компонент IDF BM25.

Модификации

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

• BM25+ ^[7] является расширением BM25. BM25+ был разработан для устранения одного недостатка стандарта BM25, в котором компонент нормализации частоты терминов по длине документа не имеет должным образом нижней границы; в результате этого недостатка длинные документы, которые соответствуют термину запроса, часто могут быть несправедливо оценены BM25 как имеющие аналогичную релевантность более коротким документам, которые вообще не содержат термин запроса. Формула оценки BM25+ имеет только один дополнительный свободный параметр (значение по умолчанию равно 1,0 при отсутствии обучающих данных) по сравнению с BM25: ${\displaystyle \delta }$

${\displaystyle {\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]}$

Ссылки

1. "OKAPI". smcse.city.ac.uk . Получено 2023-10-16 .
2. Stephen Robertson & Hugo Zaragoza (2009). «The Probabilistic Relevance Framework: BM25 and Beyond». Основы и тенденции в области поиска информации . 3 (4): 333–389. CiteSeerX 10.1.1.156.5282 . doi :10.1561/1500000019. S2CID  207178704. 
3. Кристофер Д. Мэннинг, Прабхакар Рагхаван, Хинрих Шютце. Введение в поиск информации , Издательство Кембриджского университета, 2009, стр. 233.
4. «Схема взвешивания BM25».
5. Уго Сарагоса, Ник Красвелл, Майкл Тейлор, Сучи Сария и Стивен Робертсон. Microsoft Cambridge на TREC-13: Web и HARD-треки. В материалах TREC-2004.
6. Робертсон, Стивен; Сарагоса, Хьюго; Тейлор, Майкл (2004-11-13). "Простое расширение BM25 для нескольких взвешенных полей". Труды тринадцатой международной конференции ACM по управлению информацией и знаниями . CIKM '04. Нью-Йорк, штат Нью-Йорк, США: Ассоциация вычислительной техники. стр. 42–49. doi :10.1145/1031171.1031181. ISBN 978-1-58113-874-0. S2CID  16628332.
7. Юаньхуа Лв и Чэнсян Чжай. Нормализация частоты нижних граничных членов. В трудах CIKM'2011, страницы 7-16.

Общие ссылки

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

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

• Робертсон, Стивен ; Сарагоса, Хьюго (2009). Вероятностная структура релевантности: BM25 и далее (PDF) . NOW Publishers, Inc. ISBN 978-1-60198-308-4.