Алгоритм BM25

BM25 - один из алгоритмов, который используется поисковыми системами для ранжирования соответствия документов по их релевантности данному поисковому запросу пользователей. Алгоритм основан на вероятностно-поисковом механизме, разработанный еще в 1970-х и 1980-х годах Стивен Э. Робертсономи Карен Спарк Джонсом.

Формула алгоритма BM25 - это поисковая функция в комплексе документов на основании запроса слов, входящих в каждый из этих документов, независимо от взаимо-отношений между терминами запроса в пределах документа (например, их относительная близость). Это не одна функция, а семейство функций, с различными компонентами и параметрами. Алгоритм BM25F учитывает не только сам текст, но и его отдельные участки или зоны. К таким участкам относят тег Title, метатеги, заголовки и подзаголовки, околоссылочный текст.

Одна из распространенных формул этой функции выглядет так:

Пусть дан запрос Q содержащий слова  q1...qn, тогда функция BM25 даёт следующую оценку релевантности документа D запросу Q:

формула BM25

Где f(qi, D) есть частота слова qi в документе D, |D| есть длина документа (количество слов в нём), а avgdl — средняя длина документа в коллекции. k1 и b — свободные коэффициенты, обычно их выбирают как k1 = 2.0 и b = 0.75.

IDF(qi) есть обратная документная частота слова qi. Есть несколько толкований IDF и небольших вариации его формулы. Классически, она определяется как:

классическая формула IDF

где N есть общее количество документов в коллекции, а n(qi) — количество документов, содержащих qi. Но чаще применяются «сглаженные» варианты этой формулы, например:

сглаженная формула IDF

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

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

  • Игнорировать вообще все отрицательные слагаемые в сумме (что эквивалентно занесению в стоп-лист и игнорированию всех соответствующих высокочастотных слов);
  • Налагать на IDF некоторую нижнюю границу \varepsilon: если IDF меньше \varepsilon, то считать её равной \varepsilon.
  • Использовать другую формулу IDF, не принимающую отрицательных значений.

Более человеко -понятная интерпретация работы алгоритма показана на видео ниже:

Источник