[Перевод] Разбираем алгоритм полнотекстового поиска BM25
BM25, или Best Match 25 — это широко используемый алгоритм полнотекстового поиска. Среди прочего, он по умолчанию применяется в Lucene/Elasticsearch и SQLite. В последнее время в рамках «гибридного поиска» часто начали комбинировать полнотекстовый поиск и поиск по схожести векторов. Мне захотелось понять, как работает полнотекстовый поиск и в частности BM25, поэтому в этой статье я постараюсь разобраться в этом.
Моя мотивация: можно ли сравнивать численные оценки BM25 между разными запросами?
Для контекста объясню, почему я заинтересовался поисковыми алгоритмами: я разрабатываю персонализированную ленту контента, подыскивающую в шумных источниках контент, соответствующий интересам пользователя. Поначалу я применял поиск по схожести векторов и хотел добавить полнотекстовый поиск, чтобы улучшить обработку точных ключевых слов (например, моему другу интересен Solid.js, но если применять поиск по схожести векторов, то находится больше контента, связанного с React, а не с Solid).
Начать глубоко разбираться с BM25 меня мотивировал такой вопрос: можно ли сравнивать численные оценки документов BM25 между различными запросами, чтобы определить, какому запросу лучше соответствует документ?
И ChatGPT, и Claude поначалу сказали мне, что это невозможно, однако после того, как я глубже разобрался в этом и сумел сформулировать более точный вопрос, они оба ответили утвердительно. Что ж, давайте рассмотрим BM25 подробнее, а потом я расскажу о своих выводах по этому вопросу.
Вероятностное ранжирование документов
Если упростить, то цель алгоритма полнотекстового поиска заключается в нахождении наиболее релевантных запросу документов из множества вариантов.
Однако мы не знаем на самом деле, какие документы «релевантны», поэтому можем лишь гадать. В частности, мы можем ранжировать документы на основании вероятности того, что они релевантны запросу. (Это называется «принципом вероятностного ранжирования», Probability Ranking Principle.)
Как вычислить вероятность того, что документ релевантен?
Для полнотекстового, или лексического поиска мы используем только свойства поискового запроса и каждого из документов в нашей коллекции. (В отличие от него, поиск по схожести векторов может использовать модель эмбеддингов, обученную на внешнем корпусе текстов для создания представления значения (семантики) запроса и документа.)
Компоненты BM25
В BM25 используются компоненты запроса и множества документов:
Элементы запроса: если поисковый запрос составлен из нескольких элементов, то BM25 вычисляет отдельную численную оценку для каждого элемента, а затем суммирует их.
Обратная частотность документа, Inverse Document Frequency (IDF): редкость вхождения конкретного поискового элемента во всей коллекции документов. Мы считаем, что часто встречающиеся слова (например, «the» или «and») менее информативны, чем редкие, поэтому хотим повысить важность редких слов.
Частотность элемента запроса в документе: количество вхождений поискового элемента в конкретном документе. Мы считаем, что количество повторений элемента запроса в документе увеличивает вероятность того, что документ связан с элементом. Однако BM25 ещё и регулирует это таким образом, чтобы каждое повторение элемента вносило всё меньший вклад.
Длина документа: длина конкретного документа по сравнению с остальными. В длинных документах количество повторений элемента может быть выше просто из-за их длины. Мы не хотим несправедливо отдавать предпочтение более длинным документам, поэтому BM25 применяет нормализацию на основании того, насколько длина документа соотносится со средней.
Из этих четырёх компонентов и состоит BM25. Давайте теперь рассмотрим, как же они используются.
Математика
Нематематикам алгоритм BM25 может показаться пугающим (когда я впервые увидел его, мой взгляд остекленел), но гарантирую, что понять его не так сложно!
Вот его полное уравнение:
А теперь давайте разберём его по частям.
Элементы запроса
D — конкретный документ
Q — полный запрос, потенциально состоящий из множественных элементов запроса
n — количество элементов запроса
qi — каждый из элементов запроса
Эта часть уравнения гласит следующее: для данного документа и запроса мы суммируем численную оценку для каждого из элементов запроса.
А теперь давайте изучим, как вычисляется численная оценка для каждого из элементов запроса.
Обратная частотность документа (Inverse Document Frequency, IDF)
Первый компонент оценки при помощи IDF вычисляет редкость элемента запроса во всей коллекции документов.
Самые важные части этого уравнения:
N — общее количество элементов в коллекции
n (qi) — количество документов, содержащих элемент запроса
Следовательно, N − n (qi) — это количество документов, не содержащих элемент запроса
Проще говоря, эта часть сводится к следующему: частые элементы встречаются во многих документах. Если элемент встречается во многих документах, то мы получим малое число (N−n (qi), или количество документов, не содержащих этот элемент), делённое на N. В результате этого частые элементы будут слабо влиять на численную оценку.
И наоборот: редкие элементы будут встречаться лишь в немногих документах, поэтому n (qi) будет малым, а N−n (qi) — большим. Таким образом, редкие элементы будут сильнее влиять на оценку.
Константы 0,5 и 1 здесь используются для сглаживания уравнения, чтобы результаты не варьировались слишком сильно, если элемент или слишком редкий, или слишком распространённый.
Частотность элемента в документе
На предыдущем этапе мы вычисляли редкость элемента во всём множестве документов. Теперь давайте учтём, насколько часто встречается запрос в конкретном документе.
Это уравнение состоит из следующих членов:
qi — это запрос
D — это документ
f (qi, D) — частотность запроса в документе
k1 — это регулировочный параметр, обычно имеющий значение от 1,2 до 2
Это уравнение позволяет учесть частотность элемента внутри документа, но гарантирует, что повторение элемента будет давать всё менее значимые результаты. Принцип здесь заключается в том, на определённом этапе документ уже будет вероятно связан с элементом запроса, и мы не хотим, чтобы бесконечное количество повторений имело слишком большой вес в численной оценке.
Параметр k1 управляет тем, насколько снижается значимость повторения элемента. Вот, как меняется кривая в зависимости от этого параметра:
Из The Probabilistic Relevance Framework: BM25 and Beyond
Нормализация длины документа
Последнее, что нам нужно сравнить — это длина конкретного документа относительно к длинам других документов в коллекции.
В этот раз перечислим параметры справа налево:
|D| — это длина документа
avgdl — средняя длина документа в нашей коллекции
b — ещё один регулировочный параметр, управляющий тем, насколько мы выполняем нормализацию по длине документа
Длинные документы просто из-за своей длины с большей вероятностью чаще содержат поисковые элементы. Так как мы не хотим несправедливо завышать оценку длинных документов, весь этот член будет находиться в делителе всего окончательного уравнения. То есть документ длиннее среднего (|D| / avgdl > 1) будет получать штраф.
Параметр b может настраивать пользователь. При b=0 нормализация длины документа отключена, а b=1 применяет её полностью. Обычно этому коэффициенту задают значение 0,75.
Соединяем всё вместе
Если мы объединим все рассмотренные выше компоненты, то снова получим полное уравнение BM25:
Если читать слева направо, то мы увидим, что здесь суммируются численные оценки для каждого элемента запроса. Для каждого мы берём обратную частотность документа, умножаем её на частотность элемента в документе (с убывающим влиянием), а затем нормализуем по длине документа.
Гениальность BM25 и его предшественники
Мы рассмотрели все компоненты уравнения BM25, но я думаю, что стоит ненадолго остановиться, чтобы подчеркнуть два его самых гениальных аспекта.
Ранжирование по вероятности без вычисления вероятности
Как говорилось выше, BM25 основан на принципе вероятностного ранжирования (Probability Ranking Principle). Если вкратце, он гласит:
Если извлечённые документы упорядочены по уменьшению вероятности релевантности данным, то эффективность системы оптимальна для этих данных.
К сожалению, вычислить «истинную» вероятность релевантности документа запросу почти невозможно.
Однако на самом деле нам больше важен порядок документов, а не точная вероятность. Поэтому исследователи осознали, что можно упростить уравнения и сделать их практичными. В частности можно убрать из уравнения члены, которые бы требовались для вычисления полной вероятности, в тех местах, где их устранение не повлияет на порядок.
Хоть мы и используем принцип вероятностного ранжирования, на самом деле мы вычисляем не вероятность, а «вес».
Это уравнение вычисляет вес на основании частотности элементов. В частности:
W (d) — это вес рассматриваемого документа
P (F=ft, d|R=1) — это вероятность того, что элемент запроса встретится в документе с заданной частотой (ft, d), если документ релевантен (R=1)
Смысл членов уравнения сводится к вероятности того, что мы увидим определённую частотность элемента запроса в документе, если документ релевантен или не релевантен, и вероятности того, что элемент совсем не встретится, если документ релевантен или не релевантен.
Вес Роберсона-Спарка-Джонса — это способ оценки этих вероятностей, но только благодаря использованию количеств в разных множествах документов:
Уравнение состоит из следующих членов:
r — это количество релевантных документов, содержащих элемент запроса
N — общее количество документов в коллекции
R — количество релевантных документов в коллекции
n — количество документов, содержащих элемент запроса
Огромная проблема этого уравнения заключается в том, что сначала нужно знать, какие документы релевантны запросу. Как нам их получить?
Предполагаем, что большинство документов нерелевантно
Вопрос возможности применения веса Робертсона-Спарка-Джонса ставил в тупик всех исследователей на протяжении примерно пятнадцати лет. Уравнение было основано на прочном теоретическом фундаменте, то из-за необходимости наличия информации о релевантности его почти невозможно было использовать.
Чтобы сделать шаг вперёд, разработчики BM25 сделали крайне умное предположение.
Для каждого конкретного запроса можно предположить, что большинство документов не будет ему релевантно. Если допустить, что количество релевантных документов настолько мало, что им можно пренебречь, тогда мы можем просто сделать эти числа нулями!
Если подставить это в уравнение веса Робертсона-Спарка-Джонса, мы приблизительно получим член IDF, используемый в BM25:
Благодаря независимости от информации о релевантности BM25 оказался существенно полезнее, сохранив при этом те же теоретические обоснования. Виктор Лавренко назвал это «очень впечатляющим прыжком в неизвестность», и мне кажется, это очень милая часть истории BM25.
Заключение: численные оценки BM25 можно сравнивать в рамках одной коллекции
Как я говорил в начале статьи, к исследованию меня мотивировал вопрос, смогу ли я сравнивать оценки BM25 между запросами, чтобы понять, какой запрос лучше всего соответствует документу.
В целом, численные оценки BM25 нельзя сравнивать напрямую (и именно об этом говорили мне ChatGPT и Claude в ответ на мои первые запросы). Алгоритм не вычисляет оценку от 0 до 1, которую легко сравнивать между разными системами, и он даже не пытается вычислять вероятность релевантности документа. Он отдаёт приоритет ранжированию документов в определённой коллекции в порядке, аппроксимирующем вероятность их релевантности запросу. Чем выше оценка BM25, тем релевантнее документ, но это не реальная вероятность его релевантности.
Насколько я пока понял, можно сравнивать оценки BM25 между запросами для той же коллекции документов.
Предположил я это потому, что BM25 суммирует оценки для каждого элемента запроса. Не должно существовать семантической разницы между сравнением оценок для двух элементов запросов и двух полных запросов.
Однако стоит подчеркнуть, что это справедливо для того же документа в той же коллекции. BM25 использует IDF, или редкость элементов, а также среднюю длину документов в коллекции. Поэтому у нас может и не быть возможности сравнивать оценки на протяжении интервалов времени, потому что внесение любых изменений в коллекцию может изменять оценки.
Впрочем, для моих задач алгоритм полезен. Это значит, что я могу выполнять полнотекстовый поиск для каждого из интересов пользователя в моей коллекции контента и сравнивать оценки BM25, чтобы определять, какие блоки лучше соответствуют его интересам.
Я буду продолжать писать об алгоритмах ранжирования и о том, как я использую оценки релевантности. Надеюсь, мой разбор BM25 был интересным и/или полезным!
Благодарю Алекса Кеслинга и Нэтана Ласта за отзывы о черновиках поста.
Дальнейшее чтение
Если вы хотите глубже изучить теорию и историю BM25, то крайне рекомендую посмотреть сделанный в 2016 году доклад разработчика Elastic Бритты Вебер Improved Text Scoring with BM25 и прочитать The Probabilistic Relevance Framework: BM25 and Beyond Стивена Робертсона и Хьюго Сарагосы.
Изначально я хотел включить в пост сравнения между BM25 и другими алгоритмами, но он и так уже получился слишком длинным. Такие сравнения можно найти в другом посте: Comparing full text search algorithms: BM25, TF-IDF, and Postgres.
