Сравнение модификаций алгоритмов BM25

"Научный аспект №6-2024" - Информ. технологии

УДК 004.021

Максименко Олег Евгеньевич – аспирант Национального исследовательского ядерного университета (Московского инженерно-физического института).

Аннотация: Статья посвящена обзору и сравнению модификаций алгоритма BM25 на данных, использующихся для информационного поиска. Этот алгоритм нашел широкое применение в поисковых системах, где требуется определить степень релевантности запроса пользователя и текстовой информации в потенциально искомых документах. BM25 — это общее название для семейства функций ранжирования документов, которые оценивают число ключевых запросов в каждом из рассматриваемых документов. Часто ее еще называют и Okapi BM25, так как существует несколько модификаций – BM25L, BM25+ и другие. Алгоритм можно использовать как для создания полноценного поискового движка на его базе, так и в качестве одной из составляющих в поиске в качестве первого этапа отсева неподходящих результатов. В статье будет рассмотрена работа с некоторыми из них на данных из CISI – датасета, используемого для оценки поисковых алгоритмов, состоящего из более чем 100 запросов и 1500 документов. Цель исследования состоит в том, чтобы выяснить в каких ситуациях лучше использовать конкретную модификацию, какую предобработку для текста лучше использовать (стемминг, лемматизация, вариант без предварительной обработки). Оцениваться будет точность алгоритма в качестве основной метрики.

Ключевые слова: алгоритм, лемматизация, стемминг, BM25, точность, информационный поиск.

Введение

Алгоритм BM25 (Best Matching 25) – это один из самых популярных алгоритмов для оценки релевантности документов в поисковых системах. Он основан на вероятностной модели информационного поиска и широко применяется в поисковых системах, таких как Elasticsearch, Apache Solr и других.

Принцип работы BM25 основан на оценке вероятности того, что документ релевантен для конкретного запроса пользователя. Алгоритм учитывает не только частоту встречаемости слова в документе и в запросе, но и его длину, а также общую длину документа в коллекции.

Основные параметры BM25 включают:

1. k1: это параметр, который контролирует вес частоты слова в документе. Большие значения k1 увеличивают влияние частоты слова.
2. b: этот параметр контролирует влияние длины документа на его релевантность. Большие значения b означают большее влияние длины документа.

BM25 также имеет несколько подвидов, которые изменяют некоторые аспекты базового алгоритма для более точного поиска или удовлетворения конкретных потребностей:

1. BM25F: это расширение BM25, которое позволяет учитывать множество полей (например, заголовок, текст, дата публикации и т. д.) при оценке релевантности документа.
2. BM25+: это модификация BM25, которая учитывает дополнительные факторы, такие как синонимы слов в запросе и документе, а также синонимы слов в смежных документах [1].
3. BM25L: это вариант BM25, который используется для поиска по длинным документам, таким как документы с большим объемом текста [2].

Каждый из этих подвидов алгоритма BM25 может быть настроен и адаптирован в соответствии с конкретными требованиями поисковой системы или задачами поиска информации.

Материалы и методы

В данной работе для сравнения алгоритмов используются данные, которые были собраны Центром изобретений и научной информации ("ISI") и состоят из текстовых данных о 1460 документах и 112 связанных с ними запросах. Его назначение - использовать для построения моделей поиска информации, в которых данный запрос возвращает список идентификаторов документов, соответствующих запросу. Файл "CISI.REL" содержит правильный список (т.е. "золотой стандарт" или "обоснование") соответствия запроса документу, и вашу модель можно сравнить с этим "золотым стандартом", чтобы увидеть, как она работает.

Для проведения эксперимента была выбрана библиотека rank_bm25. Библиотека rank_bm25 – это Python-библиотека, реализующая алгоритм BM25 для оценки релевантности документов в поисковых системах. Эта библиотека предоставляет простой и удобный способ реализации и использования алгоритма BM25 в ваших собственных проектах. Она также предоставляет возможность настройки параметров алгоритма BM25, таких как k1 и b, а также поддерживает работу с дополнительными фичами, такими как множество полей в документах.

BM25

Функция BM25 (Best Matching 25) - это математическая формула, используемая для оценки релевантности документов в поисковых системах [1]. Она вычисляет оценку релевантности для каждого документа в коллекции по отношению к заданному запросу. Вот основная формула BM25:

Где:

• D - документ из коллекции
• Q - запрос пользователя
• n - количество уникальных слов в запросе
• qi- i-е уникальное слово в запросе
• f(qi, D) - частота слова q в документе D
• |D| - длина документа D в токенах
• avgdl - средняя длина документов в коллекции
• IDF(qi) - обратная частота документа (IDF) для слова qi
• k1 и b - параметры, настраиваемые пользователем

Каждый компонент этой формулы выполняет определенную функцию:

1. Обратная частота документа (IDF): Это мера, показывающая, насколько слово редкое в коллекции документов. Чем реже слово, тем выше его значение IDF.
2. Частота слова в документе (TF): Это количество раз, которое слово встречается в документе. Чем чаще слово появляется в документе, тем больше его значение TF.
3. Параметры k1 и b: Эти параметры позволяют настраивать влияние TF и длины документа на итоговую оценку релевантности. k1 контролирует насыщение (saturation) веса TF, а b управляет влиянием длины документа на оценку.

Функция BM25 может быть реализована как отдельная функция в программном коде, где вы можете передавать документы, запросы и другие параметры, чтобы вычислить оценку релевантности.

BM25+

Алгоритм BM25+ – это улучшенная версия алгоритма BM25 (Best Matching 25). BM25 является одним из наиболее распространенных и эффективных алгоритмов для ранжирования документов в поисковых системах [2]. BM25+ был разработан с целью дополнительного улучшения качества ранжирования.

Основные особенности алгоритма BM25+ включают в себя:

1. Учет длины документа: BM25+ учитывает длину документа, чтобы сделать оценку релевантности более точной. Это позволяет уменьшить влияние длинных документов на ранжирование.
2. Улучшенная обработка частоты терминов: BM25+ может использовать различные методы обработки частоты терминов, что позволяет более гибко настраивать алгоритм под конкретные условия.
3. Учет контекста запроса: BM25+ может учитывать контекст запроса для более точного определения релевантности документов. Например, это может включать анализ семантической близости терминов в запросе или учет специфики пользовательского поведения.
4. Механизмы адаптивного обучения: Некоторые реализации BM25+ могут использовать механизмы адаптивного обучения для автоматической настройки параметров алгоритма на основе обратной связи от пользователей [3].

В целом, алгоритм BM25+ стремится к улучшению качества ранжирования документов в поисковых системах путем учета различных факторов, таких как длина документа, контекст запроса и частота терминов.

BM25L

Алгоритм BM25L – это вариант алгоритма BM25 (Best Matching 25) для оценки релевантности документов в поисковых системах. Он является модификацией исходного BM25, специально разработанной для работы с длинными текстами или документами переменной длины, такими как веб-страницы или длинные статьи [4].

В отличие от классического BM25, который просто использует длину документа для вычисления оценки релевантности, BM25L (где "L" означает "length normalization") применяет дополнительное масштабирование на основе длины документа. Это делается для того, чтобы учесть возможное влияние длины документа на его релевантность.

Результаты

Стемминг

Стемминг текста – это процесс нахождения основы слова путем удаления его окончаний [5, 6]. Это помогает сократить слово до его базовой или "с тем мы". Например, слова "running", "runs", и "ran" после стемминга могут быть преобразованы к одной теме "run".

В Python для стемминга текста можно использовать различные библиотеки, такие как NLTK (Natural Language Toolkit) с его классом LancasterStemmer, SnowballStemmer или PorterStemmer, которые предоставляют различные алгоритмы стемминга. Библиотека LancasterStemmer – это часть естественно языковой обработки (NLP) в Python, которая используется для стемминга, процесса нахождения основы слова. Она основана на алгоритме Ланкастера и предоставляет функционал для обработки текста, убирая окончания слов и приводя их к базовой форме, или "стему". Этот процесс полезен для различных задач обработки текста, таких как кластеризация, классификация и анализ тональности.

Таблица 1 - Результаты с обработкой стеммингом

Модификация	Precision
BM25	0.58
BM25+	0.66
BM25L	0.62

Лемматизация

Лемматизация текста – это процесс приведения слова к его базовой или словарной форме, называемой леммой [7]. В отличие от стемминга, который просто обрезает окончания слов, лемматизация учитывает грамматическую информацию о слове, чтобы найти его базовую форму. WordNetLemmatizer – это класс в библиотеке NLTK (Natural Language Toolkit) для лемматизации слов на английском языке. Он использует ресурс WordNet, который предоставляет информацию о лексической и семантической структуре английского языка.

Лемматизация, выполняемая с помощью WordNetLemmatizer, преобразует слова к их базовой или канонической форме (лемме), учитывая грамматические правила языка. Это позволяет более точно определять основные формы слов, чем простое удаление окончаний, как в случае со стеммингом.

Таблица 2 - Результаты с обработкой лемматизацией

Модификация	Precision
BM25	0.6
BM25+	0.67
BM25L	0.62

Без предварительной обработки текста функции показали следующие результаты

Таблица 3 - Результаты без обработки

Модификация	Precision
BM25	0.43
BM25+	0.5
BM25L	0.45

Обсуждение

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

Заключение

Были проведены эксперименты с bm25 и его модификациями на датасете CISI. Исходный текст поисковых запросов и ответов был подвергнут предварительной обработке - приведение к нижнему регистру, удаление цифр и тд. В дальнейшем была применена лемматизация и стемматизация чтобы продемонстрировать результаты работы функций.

Отдельно можно отметить то что использование алгоритмов, рассматриваемых в статье возможно как и для организации поиска путем использования только их, так и применения их на одной и стадий для первичной сортировки релевантных документов.

Список литературы

1. Л.В., Ю., К. Чжай, когда документы очень длинные, BM25 выходит из строя! SIGIR, 2011, с. 1103-1104.
2. Л.В., Ю., К. Чжай, Нормализация частоты использования термина с нижней границей, CIKM, 2011, с. 7-16.
3. Илья Смирнов. Обзор алгоритмов вывода (англ.) // Механический перевод. — 2008.
4. Lv, Y., C. Чжай, Рекомендация по сравнительной оценке биомедицинских аналогичных статей, 2022, Журнал биомедицинской информатики, стр. 10
5. Зализняк А. А. Грамматический словарь русского языка. Словоизменение. Около 100000 слов. М.: “Русский язык”,1977, 880с.
6. Большакова Е. И., Воронцов К. В., Ефремова Н. Э., Клышинский Э. С., Лукашевич Н. В., Саяпин А. С. Автоматическая обработка текстов на естественном языке и анализ данных: учеб. пособие. М.: НИУ ВШЭ, 2017
7. Рио Прамана, Систематический обзор литературы по стеммингу и лемматизации для определения сходства предложений, 2022, 7-я международная конференция IEEE по информационным технологиям и цифровым приложениям
8. Сиддхартха Б.С., Интерпретация лемматизации и стемминга в обработке естественного языка, 2021, Журнал Шанхайского университета науки и техники, стр. 350-357
9. Корнелиус Дамар, Р. Рисаль Иснанто, Арис Пуджи Видодо, Обзор Систематической Литературы О методах анализа настроений, 2021, Журнал современных проблем бизнеса и правительства, стр. 12-15
10. Чжичэн Чжан (Zhicheng Zhang), Усовершенствованный алгоритм BM25 для поддержки принятия клинических решений в прецизионной медицине, основанный на совместном анализе слов и поиске с помощью Cuckoo, 2021, BMC Medical Informatics and Decision Making, стр. 10-15