Okapi BM25 - Википедия - Okapi BM25

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

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

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

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

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

{ 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)}}}

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

{ displaystyle { text {IDF}} (q_ {i}) = ln ({ frac {N-n (q_ {i}) + 0,5} {n (q_ {i}) + 0,5}} + 1)}

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

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

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

Каждому слагаемому может быть присвоено значение 0, чтобы исключить общие термины;
Для функции IDF можно задать пол постоянного ${ displaystyle epsilon}$ , чтобы вообще избежать игнорирования общих терминов;
Функцию IDF можно заменить неотрицательной или строго положительной аналогичной формы, чтобы избежать игнорирования терминов.

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

Вот интерпретация теории информации. Предположим, термин запроса ${ displaystyle q}$ появляется в ${ Displaystyle п (д)}$ документы. Затем случайно выбранный документ ${ displaystyle D}$ будет содержать член с вероятностью ${ Displaystyle { frac {п (д)} {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.

Модификации

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

{ 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]}

Общие ссылки

Стивен Э. Робертсон; Стив Уокер; Сьюзан Джонс; Мишлин Хэнкок-Болье и Майк Гэтфорд (ноябрь 1994 г.). Окапи на ТРЭК-3. Труды Третьей конференции по поиску текста (TREC 1994). Гейтерсбург, США.
Стивен Э. Робертсон; Стив Уокер и Мишлин Хэнкок-Больё (ноябрь 1998 г.). Окапи на ТРЭК-7. Труды Седьмой конференции по поиску текста. Гейтерсбург, США.
Спэрк Джонс, К.; Уокер, S .; Робертсон, С. (2000). «Вероятностная модель информационного поиска: Разработка и сравнительные эксперименты: Часть 1». Обработка информации и управление. 36 (6): 779–808. CiteSeerX 10.1.1.134.6108. Дои:10.1016 / S0306-4573 (00) 00015-7.
Спэрк Джонс, К.; Уокер, S .; Робертсон, С. (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.

внешняя ссылка

Робертсон, Стивен; Сарагоса, Хьюго (2009). Структура вероятностной релевантности: BM25 и выше (PDF). СЕЙЧАС Publishers, Inc. ISBN 978-1-60198-308-4.

[1] Кристофер Д. Мэннинг, Прабхакар Рагхаван, Хинрих Шютце. Введение в поиск информации, Cambridge University Press, 2009, стр. 233.

[2] «Схема взвешивания BM25».

[3] Хьюго Сарагоса, Ник Крэсвелл, Майкл Тейлор, Сучи Сария и Стивен Робертсон. Microsoft Cambridge на TREC-13: Web и HARD треки. В материалах TREC-2004.

[robertson2009-4] Стивен Робертсон и Хьюго Сарагоса (2009). «Модель вероятностной релевантности: BM25 и выше». Основы и тенденции поиска информации. 3 (4): 333–389. CiteSeerX 10.1.1.156.5282. Дои:10.1561/1500000019.

[5] Юаньхуа Львов и Чэн Сян Чжай. Нормализация частоты нижнего члена. В материалах ЦИКМ'2011, стр. 7–16.

[1]

[2]

[3]

[4]

[5]