Релевантность: scoring, TF-IDF и BM25

Каждый поиск в этом разделе возвращал документы с полем _score, и мы верили, что выше стоят подходящие лучше. Пора разобраться, откуда берётся это число. Без формул совсем не обойтись, но их всего три, и каждая отвечает на простой житейский вопрос.

Как бы ты ранжировал сам

Клиент ищет «пицца грибы». В каталоге 75 пицц и 38 блюд с грибами. Какое блюдо показать первым?

Подумай как библиотекарь, которого спросили про книги о грибах:

1. Слово встречается в документе: хорошо. Встречается несколько раз: ещё лучше, но не намного. Книга, где грибы упомянуты сто раз, не в сто раз лучше той, где десять.
2. Редкое слово важнее частого. «Пицца» есть у 75 блюд, «грибы» у 38. Совпадение по более редкому слову говорит о документе больше.
3. Короткий документ с совпадением лучше длинного. Если слово нашлось в названии из двух слов, оно главное. В названии из восьми слов оно может быть мимоходом.

Это и есть оценка релевантности. Первые два правила знают как TF-IDF, а с третьим и с поправками получается BM25, формула, которую Elasticsearch использует по умолчанию.

Три множителя BM25

Для каждого слова запроса Elasticsearch считает оценку как произведение:

score = boost × idf × tf

idf, редкость слова. Чем меньше документов со словом, тем больше:

idf = ln(1 + (N − n + 0,5) / (n + 0,5))

где N это сколько всего документов с этим полем, n сколько из них содержат слово. Слово, которое есть в каждом документе, почти ничего не стоит.

tf, частота слова в документе с поправкой на длину:

tf = freq / (freq + k1 × (1 − b + b × dl / avgdl))

где freq это сколько раз слово в поле, dl длина этого поля в терминах, avgdl средняя длина поля по индексу. Два параметра настраивают формулу: k1 = 1,2 отвечает за насыщение (десятое повторение слова добавляет совсем мало), b = 0,75 за то, насколько сильно наказывать длинные поля.

boost в Lucene равен k1 + 1 = 2,2 (так формула нормирована), а ещё его можно поднять самому, если одно поле важнее другого.

Оценки всех слов запроса складываются. Поэтому документ с обоими словами окажется выше документа с одним.